17.1 最优包围盒 (Optimal Bounding Box)

17.1.0 类比解释：包裹不规则礼物

生活场景类比

想象你要邮寄一个形状不规则的礼物（如一个复杂的雕塑）给朋友。邮局提供各种标准尺寸的盒子，你希望找到能装下这个礼物的最小盒子，以节省运费。

轴对齐包围盒（AABB）：就像把礼物直着放进盒子，不管礼物是什么方向，盒子的边都与货架对齐。这很简单，但可能浪费很多空间（比如长条形的礼物斜着放）。

最优包围盒（OBB）：你可以旋转礼物，找到最紧凑的摆放方式。比如一根长长的拐杖，直着放需要大盒子，但斜着放可能只需要很小的盒子。

核心问题：如何找到最优的旋转角度，使得包围盒的体积最小？

为什么困难：

不能尝试所有可能的旋转（无限多种可能）
局部最优不一定全局最优
需要在精度和计算时间之间权衡

为什么需要最优包围盒？

场景1：碰撞检测优化

游戏开发中，需要快速判断两个物体是否碰撞。
- 使用AABB：简单快速，但紧密性差
- 使用OBB：更紧密，减少误报
- 使用最优OBB：最紧密，最佳性能

示例：一辆长长的卡车
- AABB体积：1000 m³
- PCA-based OBB体积：400 m³  
- 最优OBB体积：250 m³
- 碰撞检测效率提升：4倍

场景2：空间分割

在k-d树或八叉树中，紧密的包围盒可以减少节点重叠，
提高查询效率。

场景3：物理模拟

计算物体的转动惯量、质心等物理属性时，
紧密的包围盒提供更准确的近似。

17.1.1 理论基础

问题定义

最优包围盒问题旨在找到一个包含给定三维点集的最小体积长方体。与轴对齐包围盒(AABB)不同，最优包围盒可以任意旋转，因此能够更紧密地包裹物体。

数学表述：给定三维点集 $P = p_{1}, p_{2}, ..., p_{n}$ ，寻找一个旋转矩阵 $R$ 使得旋转后的点集 $P^{'} = R p_{1}, R p_{2}, ..., R p_{n}$ 的轴对齐包围盒体积最小：

$mi n_{R in SO (3)} V (R) = (x_{ma x} - x_{min}) (y_{ma x} - y_{min}) (z_{ma x} - z_{min})$

其中 $SO (3)$ 是三维特殊正交群（所有行列式为1的正交矩阵）。

几何解释：

场景：2D中的最优矩形包围盒

原始点集（不规则分布）：
    Y
    5 |     *   *
    4 |   *   *
    3 | *   *
    2 |   *   *
    1 | *   *
    0 +-----------
      0 1 2 3 4 5 X

AABB（轴对齐）：
    +-----------+
    |     *   *|
    |   *   *  |
    | *   *    |
    |   *   *  |
    | *   *    |
    +-----------+
    体积 = 5 × 5 = 25

最优OBB（旋转45度）：
      +-----+
     /       \
    /  *   *  \
   / *   *     \
  /  *   *      \
 /   *   *       \
+-----+           +
 \\   *   *       /
  \\-----+       /
   
    体积 = 4 × 3 = 12（显著减小！）

算法原理

CGAL的oriented_bounding_box实现基于Chang、Gorissen和Melchior(2011)提出的混合优化算法，结合了以下技术：

遗传算法：全局搜索旋转空间
Nelder-Mead单纯形法：局部优化
2D精确算法：沿当前最优轴进行精确优化

算法流程可视化：

输入：点云（如一个兔子模型）

Step 1: 凸包预处理
- 计算凸包，减少点数
- 10000个点 → 500个凸包顶点

Step 2: 初始种群生成（遗传算法）
生成30个随机旋转矩阵（种群）：
    R1, R2, ..., R30

Step 3: 评估适应度
对每个Ri，计算旋转后点的AABB体积：
    fitness(Ri) = volume(AABB(Ri × points))

Step 4: 进化迭代（100代）
For gen = 1 to 100:
    a. 选择：保留体积最小的15个矩阵
    b. 交叉：配对生成15个新矩阵
       R_new = QR(α×Ra + (1-α)×Rb)  // QR保持正交性
    c. 变异：添加小随机扰动
    d. 局部优化：对前5个用Nelder-Mead精化

Step 5: 返回最优解
最佳旋转矩阵 R_best
应用R_best得到最优包围盒

凸包预处理

算法首先计算输入点集的凸包，将问题规模从 $O (n)$ 减少到 $O (h)$ ，其中 $h$ 是凸包上的点数。这是基于以下观察：最优包围盒的顶点必然位于凸包上。

凸包示例：

原始点集：1000个点（内部有大量冗余）

凸包计算后：
    只有表面上的50个点是关键的
    内部950个点不影响包围盒

计算加速：
- 凸包计算：O(n log n)
- 但后续优化：从O(1000)降到O(50)
- 总体加速：20倍

17.1.2 架构分析

类层次结构

CGAL::oriented_bounding_box() [入口函数]
    └── CGAL::Optimal_bounding_box::internal::
        └── construct_oriented_bounding_box()
            ├── extreme_points_3() [凸包计算]
            └── compute_best_transformation()
                └── Evolution::evolve() [主优化循环]

核心组件

1. Oriented_bounding_box_traits_3

template <typename K>
class Oriented_bounding_box_traits_3 : public K
{
public:
    typedef typename K::FT FT;
    typedef CGAL::Aff_transformation_3<K> Aff_transformation_3;
    typedef CGAL::Eigen_matrix<FT, 3, 3> Matrix;
    typedef CGAL::Eigen_vector<FT, 3> Vector;
    
    // QR分解获取正交矩阵
    static Matrix get_Q(const Matrix& m);
};

该traits类提供：

基于Eigen的矩阵运算支持
QR分解确保旋转矩阵的正交性
与CGAL几何内核的集成

2. Evolution类

遗传算法的主控制器，管理种群的进化过程：

template <typename PointRange, typename Traits>
class Evolution
{
    void evolve(std::size_t max_generations,
                std::size_t population_size,
                std::size_t nelder_mead_iterations);
    void genetic_algorithm();  // 遗传操作
};

3. Population和Vertex

template<typename Traits>
struct Vertex_with_fitness {
    Matrix m_mat;    // 旋转矩阵
    FT m_val;        // 适应度值（包围盒体积）
};
 
template<typename Traits>
class Population {
    typedef std::array<Vertex, 4> Simplex;  // 单纯形顶点
    std::vector<Simplex> m_simplices;       // 种群
};

文件组织

Optimal_bounding_box/
├── include/CGAL/
│   ├── optimal_bounding_box.h                    # 主入口
│   └── Optimal_bounding_box/
│       ├── oriented_bounding_box.h               # 核心算法
│       ├── Oriented_bounding_box_traits_3.h      # Traits定义
│       └── internal/
│           ├── evolution.h                       # 遗传算法
│           ├── population.h                      # 种群管理
│           ├── fitness_function.h                # 适应度计算
│           ├── nelder_mead_functions.h           # NM优化
│           ├── optimize_2.h                      # 2D精确优化
│           └── helper.h                          # 辅助函数
├── examples/
│   └── obb_example.cpp                           # 使用示例
└── test/                                         # 测试用例

17.1.3 实现细节

核心算法流程

// 来自 oriented_bounding_box.h
template <typename PointRange, typename Traits>
void compute_best_transformation(
    const PointRange& points,
    typename Traits::Aff_transformation_3& transformation,
    typename Traits::Aff_transformation_3& inverse_transformation,
    CGAL::Random& rng,
    const Traits& traits)
{
    const std::size_t max_generations = 100;
    const std::size_t population_size = 30;
    const std::size_t nelder_mead_iterations = 20;
 
    // 创建进化优化器
    Evolution<PointRange, Traits> search_solution(points, rng, traits);
    
    // 执行进化优化
    search_solution.evolve(max_generations, population_size, 
                          nelder_mead_iterations);
    
    // 获取最优旋转矩阵
    const Matrix& rot = search_solution.get_best_vertex().matrix();
    
    // 构造CGAL变换对象
    transformation = Aff_transformation_3(
        rot(0, 0), rot(0, 1), rot(0, 2),
        rot(1, 0), rot(1, 1), rot(1, 2),
        rot(2, 0), rot(2, 1), rot(2, 2));
    
    // 正交矩阵的逆等于转置
    inverse_transformation = Aff_transformation_3(
        rot(0, 0), rot(1, 0), rot(2, 0),
        rot(0, 1), rot(1, 1), rot(2, 1),
        rot(0, 2), rot(1, 2), rot(2, 2));
}

算法可视化：

输入：点云（如斯坦福兔子模型）

Phase 1: 凸包计算
原始点：35,947个顶点
凸包顶点：约500个
时间：0.1秒

Phase 2: 遗传算法进化
初始种群（随机旋转）：
    R1: 体积 = 1500
    R2: 体积 = 2300
    ...
    R30: 体积 = 1800

第10代：
    最佳体积：850
    平均体积：1200

第50代：
    最佳体积：620
    平均体积：750

第100代：
    最佳体积：598（收敛）

Phase 3: 局部精化（Nelder-Mead）
初始：598
迭代5次：585
迭代10次：582
迭代20次：581（收敛）

最终OBB体积：581（相比初始最佳提升61%）

遗传算法实现

// 来自 evolution.h
void genetic_algorithm()
{
    const std::size_t m = m_population.size();
    const std::size_t first_group_size = m / 2;
    const std::size_t second_group_size = m - first_group_size;
    
    // 随机分组
    std::vector<std::size_t> group1(first_group_size), group2(first_group_size);
    std::generate(group1.begin(), group1.end(), 
                  [&]{ return m_rng.get_int(0, im); });
    
    // 交叉操作I：选择较优父代
    const FT lweight = 0.4, uweight = 0.6;
    for(std::size_t i=0; i<first_group_size; ++i) {
        const FT fitnessA = m_population[group1[i]][j].fitness();
        const FT fitnessB = m_population[group2[i]][j].fitness();
        const FT threshold = (fitnessA < fitnessB) ? uweight : lweight;
        
        if(r < threshold)
            offspring[j] = m_population[group1[i]][j];
        else
            offspring[j] = m_population[group2[i]][j];
    }
    
    // 交叉操作II：矩阵插值
    for(std::size_t i=0; i<second_group_size; ++i) {
        const FT lambda = (fitnessA < fitnessB) ? uweight : lweight;
        const FT rambda = FT(1) - lambda;
        
        // 矩阵线性组合后QR正交化
        offspring[j] = Vertex{m_traits.get_Q(lambda*lm + rambda*rm), 
                              m_points, m_traits};
    }
}

适应度计算

// 来自 fitness_function.h
template <typename Traits, typename PointRange>
typename Traits::FT compute_fitness(
    const typename Traits::Matrix& R,
    const PointRange& points,
    const Traits&)
{
    FT xmin, ymin, zmin, xmax, ymax, zmax;
    xmin = ymin = zmin = FT((std::numeric_limits<double>::max)());
    xmax = ymax = zmax = FT(std::numeric_limits<double>::lowest());
 
    // 计算旋转后点的包围盒
    for(const Point& pt : points) {
        Vector pv(3);
        pv.set(0, pt.x());
        pv.set(1, pt.y());
        pv.set(2, pt.z());
        pv = R * pv;  // 应用旋转
 
        xmin = (std::min)(xmin, pv(0));
        ymin = (std::min)(ymin, pv(1));
        zmin = (std::min)(zmin, pv(2));
        xmax = (std::max)(xmax, pv(0));
        ymax = (std::max)(ymax, pv(1));
        zmax = (std::max)(zmax, pv(2));
    }
 
    // 返回体积作为适应度（越小越好）
    return ((xmax - xmin) * (ymax - ymin) * (zmax - zmin));
}

Nelder-Mead优化

// 来自 nelder_mead_functions.h
template <typename Simplex, typename PointRange, typename Traits>
void nelder_mead(Simplex& simplex,
                 const std::size_t nelder_mead_iterations,
                 const PointRange& points,
                 const Traits& traits)
{
    for(std::size_t t=0; t<nelder_mead_iterations; ++t) {
        // 按适应度排序
        std::sort(simplex.begin(), simplex.end(),
                  [](const Vertex& vi, const Vertex& vj) -> bool
                  { return vi.fitness() < vj.fitness(); });
 
        // 计算前三个最优点的质心
        const Matrix centroid_m = nm_centroid(simplex[0].matrix(),
                                              simplex[1].matrix(),
                                              simplex[2].matrix(), traits);
 
        // 反射操作
        const Matrix refl_m = reflection(centroid_m, simplex[3].matrix());
        
        // 根据反射结果选择：反射、扩展、收缩或缩减
        // ... 省略详细逻辑
    }
}

17.1.4 使用示例

基本用法

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/optimal_bounding_box.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
 
namespace PMP = CGAL::Polygon_mesh_processing;
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point;
typedef CGAL::Surface_mesh<Point> Surface_mesh;
 
int main(int argc, char** argv)
{
    const std::string filename = (argc > 1) ? argv[1] 
        : CGAL::data_file_path("meshes/pig.off");
 
    Surface_mesh sm;
    if(\!PMP::IO::read_polygon_mesh(filename, sm) || sm.is_empty()) {
        std::cerr << "Invalid input file." << std::endl;
        return EXIT_FAILURE;
    }
 
    // 计算最优包围盒
    std::array<Point, 8> obb_points;
    CGAL::oriented_bounding_box(sm, obb_points,
        CGAL::parameters::use_convex_hull(true));
 
    // 从8个顶点构造网格
    Surface_mesh obb_sm;
    CGAL::make_hexahedron(
        obb_points[0], obb_points[1], obb_points[2], obb_points[3],
        obb_points[4], obb_points[5], obb_points[6], obb_points[7], 
        obb_sm);
 
    // 计算体积
    PMP::triangulate_faces(obb_sm);
    std::cout << "Volume: " << PMP::volume(obb_sm) << std::endl;
 
    return EXIT_SUCCESS;
}

获取变换矩阵

// 获取旋转矩阵而非顶点
CGAL::Aff_transformation_3<K> transformation;
CGAL::oriented_bounding_box(sm, transformation);
 
// 应用变换将物体对齐到坐标轴
CGAL::Aff_transformation_3<K> inverse = transformation.inverse();
for(auto& p : sm.points()) {
    p = inverse.transform(p);
}

点云输入

std::vector<Point> points;
// ... 填充点云
 
std::array<Point, 8> obb_points;
CGAL::oriented_bounding_box(points, obb_points);

17.1.5 复杂度分析

时间复杂度

阶段	复杂度	说明
凸包计算	$O (n l o g n)$	使用CGAL的convex_hull_3
遗传算法	$O (G c d o tP c d o t (N c d o t h + I_{NM} c d o t h))$	G=代数，P=种群大小，h=凸包点数
2D精确优化	$O (G c d o t h l o g h)$	每代执行一次
总体	$O (n l o g n + G c d o tP c d o tN c d o t h)$	主导项

其中：

$n$ ：输入点数
$h$ ：凸包点数（通常 $h ll n$ ）
$G = 100$ ：最大代数
$P = 30$ ：种群大小
$N = 20$ ：Nelder-Mead迭代次数

空间复杂度

点存储： $O (n)$
凸包： $O (h)$
种群： $O (P c d o t 4 c d o t 9) = O (1)$ （固定大小）
总体： $O (n)$

数值稳定性

正交矩阵保持：通过QR分解确保所有旋转矩阵保持正交性
体积计算：使用双精度浮点数，避免溢出
早期退出：在适应度计算中，当部分体积已超过当前最优值时提前终止

精度与性能权衡

use_convex_hull(true)：推荐，显著加速但结果相同
随机种子：可通过random_seed参数设置以获得可重复结果
迭代次数：可通过模板参数调整，默认设置平衡了精度和速度

17.1.6 实用指导

调试技巧

技巧1：可视化包围盒计算过程

// 记录每代最佳体积，绘制收敛曲线
class EvolutionTracker {
    std::vector<double> best_volumes;
    std::vector<double> avg_volumes;
    
public:
    void record_generation(const auto& population) {
        double best = std::numeric_limits<double>::max();
        double sum = 0;
        
        for(const auto& individual : population) {
            double vol = individual.fitness();
            best = std::min(best, vol);
            sum += vol;
        }
        
        best_volumes.push_back(best);
        avg_volumes.push_back(sum / population.size());
    }
    
    void plot_convergence() const {
        std::cout << "Generation\\tBest\\tAverage" << std::endl;
        for(size_t i = 0; i < best_volumes.size(); ++i) {
            std::cout << i << "\\t"
                      << best_volumes[i] << "\\t"
                      << avg_volumes[i] << std::endl;
        }
    }
};

技巧2：验证结果正确性

// 验证包围盒确实包含所有点
bool validate_obb(const std::array<Point, 8>& obb, 
                  const std::vector<Point>& points)
{
    // 计算OBB的8个顶点的凸包
    // 检查每个点是否在凸包内
    
    for(const auto& p : points) {
        bool inside = CGAL::bounded_side_3(
            obb.begin(), obb.end(), p, K())
            \!= CGAL::ON_UNBOUNDED_SIDE;
        
        if(\!inside) {
            std::cerr << "Point outside OBB: " << p << std::endl;
            return false;
        }
    }
    return true;
}

技巧3：比较不同方法

// 比较AABB、PCA-OBB和最优OBB
void compare_bounding_boxes(const Surface_mesh& mesh) {
    // AABB
    auto aabb = CGAL::bounding_box(mesh.points().begin(), 
                                   mesh.points().end());
    double aabb_vol = (aabb.xmax() - aabb.xmin()) *
                      (aabb.ymax() - aabb.ymin()) *
                      (aabb.zmax() - aabb.zmin());
    
    // PCA-based OBB（简化实现）
    // ...
    
    // 最优OBB
    std::array<Point, 8> obb;
    CGAL::oriented_bounding_box(mesh, obb);
    // 计算体积...
    
    std::cout << "AABB volume: " << aabb_vol << std::endl;
    std::cout << "PCA-OBB volume: " << pca_vol << std::endl;
    std::cout << "Optimal OBB volume: " << optimal_vol << std::endl;
    std::cout << "Improvement: " << (1 - optimal_vol/aabb_vol) * 100 << "%" << std::endl;
}

常见错误FAQ

Q1: 计算结果不稳定，每次运行结果不同？

A: 遗传算法使用随机初始化。解决方案：

// 设置随机种子以获得可重复结果
CGAL::Random random(12345);  // 固定种子
CGAL::oriented_bounding_box(mesh, obb_points,
    CGAL::parameters::random_seed(12345));

Q2: 对于简单形状（如立方体），计算很慢？

A: 简单形状不需要复杂优化：

// 先检查是否已经是紧密包围盒
auto aabb = CGAL::bounding_box(points.begin(), points.end());
double aabb_vol = ...;
 
// 如果是立方体或球体，AABB已经是最优的
if(is_cubic_or_spherical(points)) {
    return aabb;  // 跳过OBB计算
}

Q3: 如何处理大规模数据（>100万点）？

A: 使用采样策略：

// 对大规模数据进行采样
std::vector<Point> sampled;
sampled.reserve(10000);
 
// 均匀采样
for(size_t i = 0; i < points.size(); i += points.size() / 10000) {
    sampled.push_back(points[i]);
}
 
// 在采样上计算OBB
CGAL::oriented_bounding_box(sampled, obb_points);

Q4: 如何保存和加载计算的OBB？

A: 保存变换矩阵：

// 保存
CGAL::Aff_transformation_3<K> transform;
CGAL::oriented_bounding_box(mesh, transform);
 
std::ofstream file("obb_transform.txt");
for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 4; ++j) {
        file << transform.m(i,j) << " ";
    }
    file << std::endl;
}
 
// 加载
// ... 读取矩阵并重建Aff_transformation_3

性能优化实战

场景：批量处理多个物体的OBB

// 并行计算多个物体的OBB
#include <CGAL/Parallel_tag.h>
#include <thread>
 
void compute_obbs_parallel(const std::vector<Surface_mesh>& meshes)
{
    std::vector<std::array<Point, 8>> obbs(meshes.size());
    
    // 使用OpenMP并行
    #pragma omp parallel for
    for(size_t i = 0; i < meshes.size(); ++i) {
        CGAL::oriented_bounding_box(meshes[i], obbs[i],
            CGAL::parameters::use_convex_hull(true));
    }
}

17.1.7 与其他包围盒的比较

类型	计算复杂度	紧致度	适用场景
AABB	$O (n)$	低	快速碰撞检测
OBB (PCA)	$O (n)$	中	方向性强的物体
OBB (CGAL)	$O (n l o g n)$	高	需要最优包裹
包围球	$O (n)$	低	球形物体
k-DOP	$O (kn)$	中-高	固定方向集

CGAL的OBB实现通过混合优化策略，在可接受的时间内获得接近最优的包围盒，特别适用于：

碰撞检测的预处理
空间分割结构构建
物体方向标准化
体积计算和物理模拟

Chunibyo

Explorer

17.1 最优包围盒 (Optimal Bounding Box)

17.1 最优包围盒 (Optimal Bounding Box) §

相关章节 §

17.1.0 类比解释：包裹不规则礼物 §

生活场景类比 §

为什么需要最优包围盒？ §

17.1.1 理论基础 §

问题定义 §

算法原理 §

凸包预处理 §

17.1.2 架构分析 §

类层次结构 §

核心组件 §

文件组织 §

17.1.3 实现细节 §

核心算法流程 §

遗传算法实现 §

适应度计算 §

Nelder-Mead优化 §

17.1.4 使用示例 §

基本用法 §

获取变换矩阵 §

点云输入 §

17.1.5 复杂度分析 §

时间复杂度 §

空间复杂度 §

数值稳定性 §

精度与性能权衡 §

17.1.6 实用指导 §

调试技巧 §

技巧1：可视化包围盒计算过程 §

技巧2：验证结果正确性 §

技巧3：比较不同方法 §

常见错误FAQ §

性能优化实战 §

17.1.7 与其他包围盒的比较 §

Graph View

Table of Contents

Backlinks

17.1 最优包围盒 (Optimal Bounding Box)

相关章节

17.1.0 类比解释：包裹不规则礼物

生活场景类比

为什么需要最优包围盒？

17.1.1 理论基础

问题定义

算法原理

凸包预处理

17.1.2 架构分析

类层次结构

核心组件

文件组织

17.1.3 实现细节

核心算法流程

遗传算法实现

适应度计算

Nelder-Mead优化

17.1.4 使用示例

基本用法

获取变换矩阵

点云输入

17.1.5 复杂度分析

时间复杂度

空间复杂度

数值稳定性

精度与性能权衡

17.1.6 实用指导

调试技巧

技巧1：可视化包围盒计算过程

技巧2：验证结果正确性

技巧3：比较不同方法

常见错误FAQ

性能优化实战

17.1.7 与其他包围盒的比较