1. 为什么搞点云的都绕不开凸包
做点云处理这几年，我有个很深的感触：凸包（Convex Hull）是那种"你没主动找它、但它总会在某个环节蹦出来"的几何工具。无论是做机器人抓取时给机械臂算碰撞体积，还是给一堆散乱点云估算体积，又或者是给配准算法做粗对齐，最后都会落到"先把这堆点用最小的凸多面体包起来"这个操作上。PCL里封装好的pcl::ConvexHull类，就是干这件事的。
这篇文章不是从数学定义开始念书，而是想把我实际用PCL做三维凸包计算的经验完整记录下来：算法在底层到底做了什么、API的每个参数背后是什么逻辑、reconstruct输出的顶点和面片应该怎么理解、哪些输入会让结果翻车，以及凸包算完之后还能往哪个方向延伸。给正在做点云处理、机器人感知或者三维重建的同学一个可以直接参考的实战笔记。
先给个结论，后文会展开：PCL里的凸包实现基于QuickHull算法，核心思路是"从初始四面体开始，不断往外扩张，直到把所有点都吞进多面体内部"。它跟二维凸包的最大区别在于，三维要做的是"面"的扩张而不是"边"的扩张，输出也不是一个简单多边形，而是一组顶点加一组三角面片。
2. QuickHull在PCL里是怎么把散点"收拢"成多面体的
2.1 从二维到三维：算法思路的本质区别
二维凸包大家比较熟，Graham扫描或者Andrew单调链都能在O(n log n)时间内搞定。但这两个算法很难推广到三维，原因很简单：二维里你是沿着一个方向扫过去找"最外侧的边"，三维里没有一条明确的扫描路径，你需要同时管理"当前多面体的所有面"以及"每个面外侧还悬空着哪些点"。
QuickHull走的是另一条路，它不依赖扫描顺序，而是依赖"递归分割"：先在点集里找一个初始四面体，然后反复找一个"当前某个面外侧最远的点"，把它加进来，更新多面体结构，直到所有点都被包含。这个过程很像往气球里不断地顶，每顶一次气球就大一圈，最后顶到把所有点都包住为止。
PCL的pcl::ConvexHull底层用的就是QuickHull的思想，平均复杂度在O(n log n)量级，对大多数扫描得到的点云来说完全够用。最坏情况会退化到O(n²)，但实际工程里很少遇到那种极端输入。
2.2 初始四面体与"最远点"的选择逻辑
算法第一步是在所有点里挑出六个极端点：分别在x、y、z三个轴上取最小和最大。这六个点共同决定一个初始包围结构，然后从里面选出四个点构成初始四面体。为什么要选极端点？因为凸包的点一定包含这些极端点，以它们为种子，可以保证初始多面体不会偏离真实凸包太远。
接下来进入迭代：对当前多面体的每一个面，遍历所有还没被包含的点，找距离这个面最远的那个。如果最远距离小于某个阈值，说明这个面外侧已经没有悬空点了，面就可以"封顶"；否则就把这个最远点接进来，原来的面被拆成三个新面，然后继续对这三个新面重复同样的检查。
这里有个关键参数epsilon，PCL里默认是0.0。它的作用是控制"共面判定"的容差：当某些点跟某个面的距离非常非常接近时，如果epsilon设得大一些，算法会把这些点当作"在面上"而不是"在面外"，从而减少最后输出的顶点数量。代价是凸包会稍微粗糙一点。工程里如果你只要一个粗略的包围体，把epsilon稍微调大反而更省计算量。
2.3 面片顶点怎么来的：不是所有输入点都被保留
这点很多人第一次用都会懵。reconstruct输出的顶点云，并不是输入点云的子集或者全部点，而是算法最终保留的那些"真正构成凸包边界"的点。中间那些被吞进多面体内部的点，算法会直接丢弃。所以输出顶点数通常远小于输入点数。
举个例子，一个球面上均匀采样了5万个点，求出来的凸包顶点数量大概只有几十到几百个。这很容易理解：球面的凸包就是围绕它的一个多面体，多面体的顶点只是球面点的一部分。这个特性在工程里很好用——你相当于拿到一个点数大幅压缩、但几何形状完全包住原物体的简化模型。
3. ConvexHull类使用手册：从参数到输出的完整链路
3.1 核心接口与版本差异提醒
PCL里使用凸包的核心代码非常短：
#include <pcl/surface/convex_hull.h> pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>); // 假设cloud已经加载好 pcl::ConvexHull<pcl::PointXYZ> hull; hull.setInputCloud(cloud); hull.setDimension(3); hull.setEpsilon(0.0); // 可选，默认就是0 hull.setComputeAreaVolume(true); // 计算面积和体积 pcl::PointCloud<pcl::PointXYZ>::Ptr hull_vertices(new pcl::PointCloud<pcl::PointXYZ>); std::vector<pcl::Vertices> polygons; hull.reconstruct(*hull_vertices, polygons);这里必须提醒一句：不同PCL版本的ConvexHull接口有差异。在部分旧版本里，hull.reconstruct之后要分别通过getHullArea()和getHullVolume()拿面积和体积；而在一些新版本里，这两个方法改名成了getTotalArea()和getTotalVolume()，而且要求你提前调用了setComputeAreaVolume(true)。我自己就遇到过换版本之后代码编译通过但运行拿不到面积的情况，所以建议先看一下你本地PCL头文件里到底暴露了哪个接口，再写取值逻辑。
3.2 setDimension(2)和setDimension(3)到底差在哪
setDimension决定算法是在二维空间还是三维空间里做凸包。
- 设为3，就是对原始三维点云做真正的空间凸包，输出一个封闭多面体。
- 设为2，PCL会先把所有点做PCA投影到主平面上，然后在二维平面上算凸包，输出一个平面多边形。
二维模式适合什么场景？典型的是你拿到的是某个平面上的点云，比如桌面上的物体轮廓、墙上喷的字、地平面上的障碍物分布。把这些点直接做三维凸包没有意义，因为它们在z方向几乎重合，算出来的多面体会极度扁平，数值稳定性也差。这时候降维到2D平面，求一个多边形轮廓，反而能拿到有意义的包围区域。
但二维模式有个隐藏的坑：它做PCA投影时用的主平面是从数据本身算的。如果你的点云并不严格在一个平面上，比如有少量点明显翘起来，这些点会"拉扯"主平面的方向，导致投影结果偏斜。所以用setDimension(2)之前，最好确认你的点云确实是平面结构，或者先做一个平面拟合看看残差。
3.3 reconstruct的两个输出：顶点云与面片索引
reconstruct有两个输出参数，理解它们的配合关系是用好这个接口的关键：
- 第一个输出
hull_vertices，是一个点云，存储凸包的所有顶点坐标。 - 第二个输出
polygons，类型是std::vector<pcl::Vertices>，其中每个pcl::Vertices都包含一个vertices字段，存的是一组uint32_t索引，指向hull_vertices里的点。
换句话说，polygons里的每个元素描述一个凸多边形的面。比如一个典型的长方体点云求凸包后，hull_vertices可能只有8个点，而polygons有6个面，每个面的vertices数组里可能有4个索引。如果你的点云很"圆润"，面片基本都是三角形；如果恰好在平面上采样稀疏，可能出现四边形甚至五边形面。
拿到这两个输出后，你可以直接用PCL的pcl::PolygonMesh把它们装配成一个可视化网格：
pcl::PolygonMesh mesh; mesh.cloud = *hull_vertices; mesh.polygons = polygons;然后放进pcl::visualization::PCLVisualizer里就能直接看结果。实际操作中我习惯把原始点云和凸包网格同时显示，这样一眼就能确认凸包有没有严重偏离原始形状。
4. 实测一个完整流程：点云去噪、下采样、求凸包、算体积
4.1 预处理：为什么不能直接把原始点云丢进去
很多人拿到点云就直接调reconstruct，十次里有八次结果不理想。原因在于凸包对"最外侧点"极其敏感——只要你的点云里有一个离群点飘在远处，凸包就会被它往外撑出一个大尖角，整个包围体瞬间大一圈。这在体积估算里是非常致命的误差。
我测试过一个模拟场景：一个边长1米的正方体点云，里面故意加了5个离群点，散布在距离表面0.5米外的位置。算出来的凸包体积从1.0立方米直接飙到2.3立方米，误差超过一倍。所以求凸包之前，去噪和下采样几乎是必须的步骤。
推荐的处理管线是：
- 先移除NaN点：
cloud->is_dense为false时，用pcl::removeNaNFromPointCloud清理。 - 再用
pcl::StatisticalOutlierRemoval滤掉稀疏离群点。 - 点特别多的话（比如超过几十万个点），先做一次
pcl::VoxelGrid下采样，把点密度压下来。
第三步不是可有可无。QuickHull虽然是O(n log n)平均复杂度，但当点数量级到了百万级别，而且分布很复杂时，计算时间和内存都会明显上升。VoxelGrid下采样后点数降到十分之一，凸包结果几乎不变——因为凸包只依赖最外层的点，内部点的密度对结果没有影响。
4.2 完整代码示例：从PCD文件到体积输出
下面是一个我经常用的完整流程代码，加了注释方便直接改：
#include <pcl/point_types.h> #include <pcl/point_cloud.h> #include <pcl/io/pcd_io.h> #include <pcl/filters/voxel_grid.h> #include <pcl/filters/statistical_outlier_removal.h> #include <pcl/surface/convex_hull.h> #include <iostream> int main(int argc, char** argv) { if (argc < 2) { std::cerr << "usage: " << argv[0] << " input.pcd" << std::endl; return -1; } pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>); if (pcl::io::loadPCDFile(argv[1], *cloud) == -1) { std::cerr << "failed to load" << std::endl; return -1; } std::cout << "input points: " << cloud->size() << std::endl; // 1. 移除NaN std::vector<int> nan_indices; pcl::removeNaNFromPointCloud(*cloud, *cloud, nan_indices); // 2. 统计滤波去噪 pcl::StatisticalOutlierRemoval<pcl::PointXYZ> sor; sor.setInputCloud(cloud); sor.setMeanK(20); sor.setStddevMulThresh(2.0); sor.filter(*cloud); // 3. 体素下采样 pcl::VoxelGrid<pcl::PointXYZ> voxel; voxel.setInputCloud(cloud); voxel.setLeafSize(0.01f, 0.01f, 0.01f); // 根据你的尺度调整 voxel.filter(*cloud); std::cout << "after filter: " << cloud->size() << std::endl; // 4. 凸包 pcl::ConvexHull<pcl::PointXYZ> hull; hull.setInputCloud(cloud); hull.setDimension(3); hull.setComputeAreaVolume(true); pcl::PointCloud<pcl::PointXYZ>::Ptr hull_vertices(new pcl::PointCloud<pcl::PointXYZ>); std::vector<pcl::Vertices> polygons; hull.reconstruct(*hull_vertices, polygons); std::cout << "hull vertices: " << hull_vertices->size() << std::endl; std::cout << "faces: " << polygons.size() << std::endl; // 面积和体积的接口名按版本二选一 // 旧版本: hull.getHullArea() / hull.getHullVolume() // 新版本: hull.getTotalArea() / hull.getTotalVolume() std::cout << "surface area: " << hull.getTotalArea() << std::endl; std::cout << "volume: " << hull.getTotalVolume() << std::endl; return 0; }我在实际项目里用这套流程处理过一组无人机扫描的土堆点云，点云原始20万个点，滤波和下采样之后剩下4万左右，凸包计算耗时在几十毫秒量级，输出体积跟人工测量值的偏差控制在3%以内。这个精度对工程估算来说已经非常好了。
4.3 验证凸包结果是否可靠：两个自查手段
算完凸包之后，我强烈建议至少做两个自查：
第一个是把凸包网格跟原始点云一起可视化。打开可视化窗口，旋转视角，重点看两个地方：凸包表面有没有明显的"凹陷"（理论上凸包不会有任何凹陷）；凸包的边界有没有超出原始点云太远。如果看到某个尖角特别突兀，基本就是离群点没滤干净或者epsilon设错了。
第二个是检查polygons里的面片是否有"翻面"。所谓翻面，指的是相邻两个面片的法线方向不连续，或者面片的顶点顺序混乱。出现这种情况时，getTotalArea()计算出来的面积会和实际对不上。这个问题的根源通常是PCL版本差异或者输入点云坐标尺度异常（比如坐标值达到1e8量级），可以通过把点云先做一次去中心化来缓解：把每个点的坐标减去点云质心，计算完凸包后再把结果平移回去。这个小技巧能显著提升数值稳定性。
5. 翻车记录：维度选错、退化输入、边界点异常，这些坑怎么排查
5.1 setDimension(2)配三维数据：结果看似正常实则错误
这是我第一次用ConvexHull就踩的坑。当时拿了一个桌面上的物体点云，想算它的包围轮廓，想当然地设了setDimension(2)。结果reconstruct之后拿到的是一个平面多边形，看起来好像也没问题，但仔细一看，这个多边形的方向跟桌面完全不平行，而是斜着切过去的。原因是PCA投影出来的主平面被物体上的几个凸起点带偏了，多边形所在的平面根本不是我心里想的桌面平面。
排查方法很直接：把hull_vertices画出来，叠加原始点云，如果发现多边形跟点云的主体分布不在一个平面上，那就是投影方向出了问题。如果你确实想要"某个已知平面上的二维凸包"，更稳的办法是先手动把点云旋转到该平面与z轴对齐，再设setDimension(2)，这样PCA投影出来的主平面就不会乱跑。
5.2 少于四个非共面点：退化凸包没有体积
QuickHull的三维版本需要一个非退化的种子四面体。如果输入点云里的点全部共面（比如就落在x-y平面上），或者有效点数少于4个，算法就构造不出初始四面体，getTotalVolume()会返回0，甚至reconstruct可能直接报错。
这种情况在真实数据里并不罕见。比如你扫描一面墙，墙面的点云严格来说所有点都在一个平面上，虽然点很多，但仍然是共面的。处理办法：要么用setDimension(2)把它当成平面问题算轮廓；要么在预处理阶段就给点云人为加一个很小的z方向扰动，但这只是权宜之计，不建议在生产环境这么干。更好的思路是先用pcl::SACSegmentation拟合平面，识别出"这堆点本质上是平面"，再走二维凸包的路径。
5.3 epsilon调大之后顶点数骤降：是bug还是feature
有一次我处理一个噪声较大的点云，为了压掉噪声对凸包边界的拉扯，把epsilon从0调到了0.05。结果凸包顶点从原来的300多个直接降到了60多个，整体形状也从"贴合点云表面"变成了"一个大致的笼子"。当时我以为是参数设置出了问题，后来检查代码才明白，epsilon的本质是共面判定的容忍度：epsilon越大，越多的"微小凸起"会被当作共面，这些凸起对应的点就会被合并，顶点自然少了。
所以epsilon的使用要视应用场景而定。如果你要的是精确的体积测量，epsilon越小越好，宁可用更严格的去噪来保证边界干净，也不要靠调大epsilon来掩盖噪声。如果你只是给碰撞检测提供一个粗略的包围体，epsilon大一点反而能让模型面数更低、碰撞计算更快。
5.4 坐标尺度悬殊导致的计算异常
还有一个容易被忽略的问题：点云坐标的尺度。如果数据是从大地测量或者GPS场景来的，坐标值可能有几十万甚至上百万的量级，而物体本身的尺寸只有几米。这种情况下，浮点数精度不够，QuickHull在比较点到面的距离时会出现误判，导致凸包形状异常，或者面片出现自交。
我的经验是：在求凸包之前，先做去中心化和归一化，把点云移动到原点附近，统一尺度到单位量级。算完凸包后再把顶点坐标变换回原始坐标系。这一步听起来多余，但在处理跨尺度的数据时能省掉无数排查时间。
6. 从凸包延伸出去：OBB、凹包与碰撞检测管线
6.1 用凸包辅助计算OBB：比直接算PCA更稳
很多场景下你要的不是凸包本身，而是一个带方向的包围盒（OBB），用来估计物体的主朝向和尺寸。最常见的做法是对原始点云做PCA，取三个主方向作为OBB的轴。这个方法在没有噪声时很好用，但一旦点云里有离群点，PCA的主方向会被带偏，OBB会歪得离谱。
一个更稳的替代方案是：先算出凸包，再用凸包的顶点做PCA。因为凸包顶点已经抛弃了内部点和大部分离群点的影响，主体方向更加鲁棒。我对比过同一份带噪数据：直接PCA算出的OBB主轴角度偏差能达到15度以上，而用凸包顶点算PCA的偏差可以压到2度以内。
PCL里也有现成的pcl::MomentOfInertiaEstimation可以同时输出OBB和AABB，如果你不想手动拼PCA，可以直接用它替代整套流程。但要注意它内部也是基于原始点云的协方差矩阵，对离群点同样敏感，所以预处理还是不能省。
6.2 凹包（ConcaveHull）：什么时候凸包满足不了你
凸包有个天然的问题：它只能表达外凸的形状。如果你处理的是"L形"或者"月牙形"物体，凸包会把这些凹陷全部填平，包围体比实际物体大很多，这在精确碰撞检测里是不能接受的。
PCL提供了pcl::ConcaveHull类，核心参数是alpha。alpha可以理解为一个"滚球半径"：用这个半径的球在点云表面滚动，凡是球滚不进去的地方就保留为凹形边界。alpha越小，结果越能贴合凹陷细节，但计算量也越大，而且容易产生破碎的面片；alpha越大，结果越接近凸包。
一个经验取值：alpha设为点云平均点间距的3到5倍，通常能在保留主要凹陷形状和面片完整性之间找到不错的平衡。注意ConcaveHull的输出也是hull_vertices加polygons，结构跟ConvexHull一致，所以可视化代码几乎不用改。
6.3 凸包到碰撞检测：一整套现成的管线
最后说一个我觉得很实用的方向：凸包算出来后的典型下游任务——碰撞检测。
三维凸包的顶点加面片结构，恰好是很多碰撞检测库需要的"凸包网格"格式。比如FCL库里面的fcl::Convex可以直接把hull_vertices和polygons转换进去，然后用GJK算法做两个凸包之间的最近距离计算。机器人运动规划里，机械臂的连杆、夹爪、障碍物都可以预先算好凸包，运行时做凸包之间的碰撞检测，比直接做三角网格碰撞快一个数量级。
整个管线的流程是：
- 对每个物体点云做滤波和下采样。
- 用
pcl::ConvexHull计算凸包，拿到顶点和面片。 - 把顶点和面片转成碰撞库的凸包数据结构。
- 在规划循环里用GJK或EPA做距离查询和碰撞响应。
我自己在某个模拟项目里用过这条管线，机械臂的每个连杆模型提取凸包后，面片数量从原始网格的几万面骤降到几百面，碰撞检测的每帧耗时从十几毫秒降到了1毫秒以内。这个收益在实时规划里非常可观。
凸包这个东西，说深了可以聊一堆数学推导，但回到工程落地，真正重要的其实是三件事：输入数据干不干净、维度参数选得对不对、输出结构有没有被下游正确消费。把这三点想清楚，PCL的ConvexHull就能在很多项目里稳定地当你的"几何基石"。
