CloudCompare 点云核心算法实现解析

实现原理:

1. 对每个点，搜索邻域
2. 计算点到邻域中心的距离 d
3. 计算邻域距离的标准差 σ
4. 如果 d > absError + nSigma × σ，标记为噪声

2. 配准算法

2.1 ICP (Iterative Closest Point)

文件位置:

• CloudCompare/qCC\ccRegistrationTools.h/cpp
• CloudCompare/qCC\ccLibAlgorithms.cpp (行 596-835)

核心实现:

bool ccRegistrationTools::ICP( ccHObject* data,// 数据云（要对齐的） ccHObject* model,// 模型云（参考） ccGLMatrix& transMat,// 输出：变换矩阵 double& finalScale,// 输出：最终尺度 double& finalRMS,// 输出：最终 RMS 误差 unsigned& finalPointCount,// 输出：最终点数 const CCCoreLib::ICPRegistrationTools::Parameters& inputParameters,bool useDataSFAsWeights,// 数据标量场作为权重 bool useModelSFAsWeights,// 模型标量场作为权重 QWidget* parent )

ICP 参数结构:

struct Parameters{// 收敛类型 enum ConvergenceMethod{ MAX_ERROR_CONVERGENCE,// 最大误差收敛 MAX_ITER_CONVERGENCE // 最大迭代次数收敛}; ConvergenceMethod convType;// 收敛参数 double minRMSDecrease;// 最小 RMS 减少量 unsigned nbMaxIterations;// 最大迭代次数 // 变换参数 bool adjustScale;// 是否调整尺度 unsigned samplingLimit;// 采样点数限制（默认 50000） double finalOverlapRatio;// 最终重叠率（0-1） // 变换过滤器 enum TransformationFilters{ SKIP_NONE =0, SKIP_ROTATION =1, SKIP_TRANSLATION =2, SKIP_ROTATION_TRANS =3}; int transformationFilters;// 法向量匹配 enum NormalsMatching{ NO_NORMAL =0, OPPOSITE_NORMALS =1, DOUBLE_SIDED_NORMALS =2}; int normalsMatching;};

算法流程:

┌─────────────────────────────────┐ │ 1. 预处理阶段 │ ├─ 如果模型是网格，采样点 │ ├─ 创建临时标量场 │ └─ 计算八叉树 └─────────┬───────────────────────┘ ↓ ┌─────────────────────────────────┐ │ 2. 重叠区域估计 │ ├─ 计算近似距离 │ ├─ 对距离排序 │ └─ 确定最大搜索距离 └─────────┬───────────────────────┘ ↓ ┌─────────────────────────────────┐ │ 3. 迭代配准 │ ├─ 查找最近邻 │ ├─ 计算变换矩阵 │ ├─ 应用变换 │ ├─ 计算 RMS 误差 │ └─ 检查收敛 └─────────┬───────────────────────┘ ↓ ┌─────────────────────────────────┐ │ 4. 输出结果 │ ├─ 变换矩阵 │ ├─ RMS 误差 │ ├─ 最终点数 │ └─ 最终尺度 └─────────────────────────────────┘ 

重叠区域估计 (关键优化):

// 计算近似距离以确定最大重叠距离 int gridLevel =log10(max(dataSize, modelSize))+2; CCCoreLib::DistanceComputationTools::computeApproxCloud2CloudDistance( dataCloud, modelCloud, gridLevel);// 对距离排序，选择对应重叠率的点 ParallelSort(distances.begin(), distances.end()); double margin =0.1;// 10% 边际 unsigned count = distances.size(); maxSearchDist = distances[count *(finalOverlapRatio + margin)-1];

迭代配准核心:

CCCoreLib::ICPRegistrationTools::Register( modelCloud,// 参考云 modelMesh,// 参考网格（可选） dataCloud,// 数据云 params,// 参数 transform,// 输出：变换矩阵 finalRMS,// 输出：RMS 误差 finalPointCount // 输出：点数);

输出变换矩阵:

// CCCoreLib::PointProjectionTools::Transformation struct Transformation{ SquareMatrixd R;// 旋转矩阵（3×3） CCVector3d T;// 平移向量 double s;// 尺度因子};// 转换为 ccGLMatrix transMat =FromCCLibMatrix<double,float>( transform.R, transform.T, transform.s); finalScale = transform.s;

典型用法:

// 1. 设置参数 CCCoreLib::ICPRegistrationTools::Parameters params; params.convType = MAX_ERROR_CONVERGENCE; params.minRMSDecrease =1e-5; params.nbMaxIterations =20; params.adjustScale =false; params.samplingLimit =50000; params.finalOverlapRatio =1.0; params.transformationFilters = SKIP_NONE; params.normalsMatching = NO_NORMAL;// 2. 执行 ICP ccGLMatrix transMat; double finalScale, finalRMS; unsigned finalPointCount; bool success = ccRegistrationTools::ICP( dataCloud, modelCloud, transMat, finalScale, finalRMS, finalPointCount, params,false,false, parent );// 3. 应用变换 if(success){ dataCloud->applyGLTransformation_recursive(&transMat); ccLog::Print(QString("ICP converged: RMS=%1, Points=%2").arg(finalRMS).arg(finalPointCount));}

2.2 尺度匹配算法

文件位置: ccLibAlgorithms.cpp (行 596-835)

支持的方法:

enum ScaleMatchingAlgorithm{ BB_MAX_DIM,// 包围盒最大维度 BB_VOLUME,// 包围盒体积 PCA_MAX_DIM,// PCA 主成分最大维度 ICP_SCALE // 基于 ICP 的尺度估计};

实现示例 - BB_MAX_DIM:

double ComputeScale_BB_MAX_DIM( ccHObject* entities1, ccHObject* entities2){ ccBBox box1 = entities1->getOwnBB(); ccBBox box2 = entities2->getOwnBB(); CCVector3 diag1 = box1.getDiagVec(); CCVector3 diag2 = box2.getDiagVec(); double maxDim1 = std::max(diag1.x, std::max(diag1.y, diag1.z)); double maxDim2 = std::max(diag2.x, std::max(diag2.y, diag2.z)); return maxDim2 / maxDim1;}

3. 分割算法

3.1 RANSAC 形状检测

插件位置: CloudCompare/plugins\core\Standard\qRANSAC_SD/

支持的几何图元:

1. 平面 (Plane)
2. 球体 (Sphere)
3. 圆柱 (Cylinder)
4. 圆锥 (Cone)
5. 圆环 (Torus)

核心参数:

struct RansacParams{double epsilon;// 点到形状的最大距离 double bitmapEpsilon;// 采样分辨率 double maxNormalDev_deg;// 最大法向量偏差（度） double probability;// 概率阈值（默认 0.01） unsigned supportPoints;// 最小支撑点数（默认 500） // 形状约束 bool enablePlane; bool enableSphere; double minSphereRadius, maxSphereRadius; bool enableCylinder; double minCylinderRadius, maxCylinderRadius; double minCylinderLength, maxCylinderLength; bool enableCone; double maxConeAngle_deg; double minConeRadius, maxConeRadius; double minConeLength, maxConeLength; bool enableTorus; double minTorusMinorRadius, maxTorusMinorRadius; double minTorusMajorRadius, maxTorusMajorRadius;};

检测流程:

// 1. 初始化 RANSAC 检测器 RansacShapeDetector detector(params); detector.Add(newPlanePrimitiveShapeConstructor()); detector.Add(newSpherePrimitiveShapeConstructor()); detector.Add(newCylinderPrimitiveShapeConstructor()); detector.Add(newConePrimitiveShapeConstructor()); detector.Add(newTorusPrimitiveShapeConstructor());// 2. 执行检测 MiscLib::Vector<std::pair<MiscLib::RefCountPtr<PrimitiveShape>, size_t>> shapes; size_t remainingPoints = detector.Detect(*cloud,0,// 起始索引 cloud->size(),// 结束索引 shapes // 输出：检测到的形状);// 3. 处理检测结果 for(constauto& shapePair : shapes){ PrimitiveShape* shape = shapePair.first; size_t pointCount = shapePair.second;// 根据形状类型创建 CloudCompare 对象 if(dynamic_cast<PlanePrimitiveShape*>(shape)){ ccPlane* plane =CreatePlane(shape, pointCount); container->addChild(plane);}elseif(dynamic_cast<SpherePrimitiveShape*>(shape)){ ccSphere* sphere =CreateSphere(shape, pointCount); container->addChild(sphere);}// ... 其他形状类型}

RANSAC 原理:

1. 随机选择最小点集（例如 3 个点定义平面）
2. 拟合形状参数
3. 计算内点数量（距离<epsilon 的点）
4. 重复 N 次，选择内点最多的形状
5. 提取内点，从点云中移除
6. 重复直到剩余点数<minPoints

迭代次数估算:

N = log(1 - probability) / log(1 - w^s) 其中： - probability: 至少找到一个好模型的概率 - w: 内点比例（估计值） - s: 最小点集大小（平面 3，球 4，圆柱 7 等）

3.2 区域生长分割

基于连通性的分割，常用于分离独立对象。

核心算法:

// 使用 CCCoreLib 的连通组件算法 CCCoreLib::ReferenceCloudContainer components; int componentCount = CCCoreLib::AutoSegmentationTools::labelConnectedComponents( cloud, octreeLevel,// 八叉树层级 false,// 使用 6 连通还是 26 连通 &progressDialog, octree );// 为每个连通组件创建子云 for(int i =0; i < componentCount;++i){ CCCoreLib::ReferenceCloud* component = components[i]; ccPointCloud* subCloud = cloud->partialClone(component); subCloud->setName(QString("Component_%1").arg(i +1)); container->addChild(subCloud);}

4. 法向量计算

4.1 法向量估计方法

文件位置: CloudCompare/qCC\ccEntityAction.cpp (行 2075-2370)

支持的局部模型:

enum LOCAL_MODEL_TYPES{ LS =0,// 最小二乘平面拟合（最常用） QUADRIC =1,// 二次曲面拟合（更准确，但慢） TRI =2// 三角化方法};

计算方法:

方法 1: 基于八叉树

bool success = cloud->computeNormalsWithOctree( model,// LS/QUADRIC/TRI preferredOrientation, defaultRadius,// 邻域半径 &progressDialog );

数学原理（LS 平面拟合）:

1. 对每个点 P，搜索半径 R 内的邻域点 {P₁, P₂, …, Pₙ}
2. 法向量 = 最小特征值对应的特征向量

计算 M 的特征值和特征向量:

M·v = λ·v 

构建协方差矩阵:

M = (1/n) Σ (Pᵢ - C)(Pᵢ - C)ᵀ 

计算邻域中心:

C = (1/n) Σ Pᵢ 

代码实现:

// CCCoreLib/GeometricalAnalysisTools.cpp bool ComputeCharactersitic( GeomCharacteristic c,int subOption, ccGenericPointCloud* cloud, PointCoordinateType radius,const CCVector3* roughnessUpDir, GenericProgressCallback* progressCb, DgmOctree* inputOctree){// 为每个点计算 for(unsigned i =0; i < pointCount;++i){const CCVector3* P = cloud->getPoint(i);// 搜索邻域 DgmOctree::NeighboursSet neighbours; octree->getPointsInSphericalNeighbourhood(*P, radius, neighbours);// 计算中心 CCVector3 C(0,0,0);for(auto& n : neighbours){ C +=*cloud->getPoint(n.pointIndex);} C /= neighbours.size();// 构建协方差矩阵 SquareMatrixd covMat(3);for(auto& n : neighbours){ CCVector3d d =CCVector3d(*cloud->getPoint(n.pointIndex))- C;for(int row =0; row <3;++row){for(int col =0; col <3;++col){ covMat.m_values[row][col]+= d.u[row]* d.u[col];}}} covMat /= neighbours.size();// 计算特征值和特征向量 SquareMatrixd eigVectors(3); std::vector<double> eigValues;if(Jacobi<double>::ComputeEigenValuesAndVectors( covMat, eigVectors, eigValues,true)){// 法向量 = 最小特征值的特征向量 int minEigIndex =0;if(eigValues[1]< eigValues[minEigIndex]) minEigIndex =1;if(eigValues[2]< eigValues[minEigIndex]) minEigIndex =2; CCVector3 N( eigVectors.m_values[0][minEigIndex], eigVectors.m_values[1][minEigIndex], eigVectors.m_values[2][minEigIndex]);// 存储法向量 cloud->addNorm(N);}}}

方法 2: 基于扫描网格

bool success = cloud->computeNormalsWithGrids( minGridAngle_deg,// 网格三角形最小角度（默认 1 度） &progressDialog, preferredOrientation );

适用场景: TLS（地基激光扫描）数据，已有结构化网格

4.2 法向量半径自动估计

文件位置: ccOctree.cpp

struct BestRadiusParams{int aimedPopulationPerCell =16;// 目标单元格点数 int aimedPopulationRange =4;// 点数范围 int minCellPopulation =6;// 最小单元格点数 double minAboveMinRatio =0.97;// 高于最小值的比例}; PointCoordinateType ccOctree::GuessBestRadius( ccGenericPointCloud* cloud,const BestRadiusParams& params, ccOctree::Shared octree, GenericProgressCallback* progressCb){// 1. 随机采样最多 200 个点 unsigned sampleCount = std::min(cloud->size(),200u); std::vector<unsigned> sampleIndexes;for(unsigned i =0; i < sampleCount;++i){ sampleIndexes.push_back(rand()% cloud->size());}// 2. 对每个采样点测试不同半径 std::vector<double> testedRadii; double minRadius = cloud->getOwnBB().getDiagNorm()*0.001; double maxRadius = cloud->getOwnBB().getDiagNorm()*0.1;for(double r = minRadius; r <= maxRadius; r *=1.5){ testedRadii.push_back(r);}// 3. 统计每个半径下的邻域点数分布 std::map<double, std::vector<int>> radiusToNeighbourCounts;for(double radius : testedRadii){ std::vector<int> counts;for(unsigned idx : sampleIndexes){ DgmOctree::NeighboursSet neighbours; octree->getPointsInSphericalNeighbourhood(*cloud->getPoint(idx), radius, neighbours); counts.push_back(neighbours.size());} radiusToNeighbourCounts[radius]= counts;}// 4. 选择满足统计要求的最小半径 for(double radius : testedRadii){constauto& counts = radiusToNeighbourCounts[radius];// 计算有多少点的邻域点数在目标范围内 int validCount =0;for(int count : counts){if(count >= params.aimedPopulationPerCell - params.aimedPopulationRange && count <= params.aimedPopulationPerCell + params.aimedPopulationRange){ validCount++;}}// 检查是否满足条件 double validRatio =static_cast<double>(validCount)/ counts.size();if(validRatio >= params.minAboveMinRatio){return radius;// 返回第一个满足条件的半径}}// 5. 如果没有找到合适的半径，返回中间值 return testedRadii[testedRadii.size()/2];}

4.3 法向量方向调整

支持的方向调整方法:

方法 1: 基于扫描网格

cloud->orientNormalsWithGrids();

使用结构化扫描数据确定法向量方向（朝向传感器）

方法 2: 基于传感器

cloud->orientNormalsTowardViewPoint(sensorPosition);

所有法向量朝向给定视点

方法 3: 首选方向

enum Orientation{ PLUS_X, MINUS_X, PLUS_Y, MINUS_Y, PLUS_Z, MINUS_Z, PLUS_SENSOR_ORIGIN, MINUS_SENSOR_ORIGIN, UNDEFINED }; cloud->orientNormalsWithFM(preferredOrientation);

方法 4: 最小生成树（MST）

cloud->orientNormalsWithMST( mstNeighbors,// 邻居数量（默认 6） &progressDialog );

MST 原理:

1. 构建 KNN 图（每个点连接到 K 个最近邻）
2. 边权重 = 法向量夹角
3. 计算最小生成树
4. 从根节点开始传播方向（确保相邻法向量方向一致）

5. 几何特征计算

5.1 支持的特征类型

文件位置: CloudCompare/qCC\ccLibAlgorithms.cpp (行 168-421)

特征枚举:

namespace CCCoreLib {namespace GeometricalAnalysisTools {enum GeomCharacteristic{// ===== 特征值分析 ===== Feature_EigenValuesSum,// λ₁ + λ₂ + λ₃ Feature_Omnivariance,// ³√(λ₁·λ₂·λ₃) Feature_EigenEntropy,// -Σ λᵢ·ln(λᵢ) Feature_Anisotropy,// (λ₁ - λ₃) / λ₁ Feature_Planarity,// (λ₂ - λ₃) / λ₁ Feature_Linearity,// (λ₁ - λ₂) / λ₁ Feature_PCA1,// λ₁ / (λ₁ + λ₂ + λ₃) Feature_PCA2,// λ₂ / (λ₁ + λ₂ + λ₃) Feature_SurfaceVariation,// λ₃ / (λ₁ + λ₂ + λ₃) Feature_Sphericity,// λ₃ / λ₁ Feature_Verticality,// 1 - |N·Z| Feature_EigenValue1,// λ₁ Feature_EigenValue2,// λ₂ Feature_EigenValue3,// λ₃// ===== 曲率 ===== Curvature_GAUSSIAN,// 高斯曲率 κ₁·κ₂ Curvature_MEAN,// 平均曲率 (κ₁+κ₂)/2 Curvature_NORMAL_CHANGE_RATE,// 法向量变化率// ===== 密度 ===== Density_KNN,// KNN 密度 Density_2D,// 2D 表面密度 Density_3D,// 3D 体密度// ===== 其他 ===== Roughness,// 粗糙度 MomentOrder1 // 一阶矩};}}

5.2 计算流程

bool ComputeGeomCharacteristic( CCCoreLib::GeometricalAnalysisTools::GeomCharacteristic c,int subOption, PointCoordinateType radius, ccHObject::Container& entities,const CCVector3* roughnessUpDir, QWidget* parent, ccProgressDialog* progressDialog){for(ccHObject* entity : entities){ ccPointCloud* pc = ccHObjectCaster::ToPointCloud(entity);if(!pc)continue;// 1. 创建标量场 QString sfName =GetScalarFieldName(c);int sfIdx = pc->addScalarField(sfName.toStdString()); pc->setCurrentScalarField(sfIdx);// 2. 计算八叉树 ccOctree::Shared octree = pc->getOctree();if(!octree){ octree = pc->computeOctree(progressDialog);}// 3. 调用核心算法 bool success = CCCoreLib::GeometricalAnalysisTools::ComputeCharactersitic( c, subOption, pc, radius, roughnessUpDir, progressDialog, octree.data());if(success){// 4. 更新显示 pc->setCurrentDisplayedScalarField(sfIdx); pc->showSF(true); pc->getCurrentInScalarField()->computeMinAndMax();// 5. 粗糙度特殊处理（对称色标） if(c == Roughness && roughnessUpDir){ pc->getCurrentInScalarField()->setSymmetricalScale(true);}}}returntrue;}

5.3 特征值分析示例

计算 Planarity（平面性）:

// 对每个点 for(unsigned i =0; i < pointCount;++i){// 1. 搜索邻域 DgmOctree::NeighboursSet neighbours; octree->getPointsInSphericalNeighbourhood(*P, radius, neighbours);// 2. 计算协方差矩阵 SquareMatrixd covMat =ComputeCovarianceMatrix(neighbours);// 3. 计算特征值 std::vector<double> eigValues;ComputeEigenValues(covMat, eigValues);// 按降序排序：λ₁ ≥ λ₂ ≥ λ₃ std::sort(eigValues.begin(), eigValues.end(), std::greater<double>());// 4. 计算平面性 double planarity =(eigValues[1]- eigValues[2])/ eigValues[0];// 5. 存储到标量场 sf->setValue(i, planarity);}

物理意义:

• Planarity ≈ 1: 点在平面上（屋顶、墙壁）
• Planarity ≈ 0: 点在线或体积中（边缘、散乱点）

6. 距离计算

6.1 Cloud-to-Cloud 距离

对话框: CloudCompare/qCC\ccComparisonDlg.h

比较类型:

enum CC_COMPARISON_TYPE{ CLOUDCLOUD_DIST =0,// 点云到点云 CLOUDMESH_DIST =1// 点云到网格};

核心功能:

// 近似距离计算（快速） int octreeLevel = ccComparisonDlg::getBestOctreeLevel( comparedCloud, referenceCloud); CCCoreLib::DistanceComputationTools::computeApproxCloud2CloudDistance( comparedCloud, referenceCloud, octreeLevel, maxSearchDist,&progressDialog, comparedOctree.data());

精确距离计算（慢但准确）:

int result = CCCoreLib::DistanceComputationTools::computeCloud2CloudDistances( comparedCloud, referenceCloud, params,&progressDialog, comparedOctree.data(), referenceOctree.data());

6.2 M3C2 算法（多尺度模型到模型云比较）

插件位置: CloudCompare/plugins\core\Standard\qM3C2/

文献: Lague, D., Brodu, N. and Leroux, J., 2013
'Accurate 3D comparison of complex topography with terrestrial laser scanner'

核心参数:

struct M3C2Params{// 投影参数 PointCoordinateType projectionRadius;// 投影半径 PointCoordinateType projectionDepth;// 投影深度 // 法向量参数 bool updateNormal;// 更新法向量 bool exportNormal;// 导出法向量 // 统计参数 bool useMedian;// 使用中位数（更鲁棒） bool computeConfidence;// 计算置信区间 unsigned minPoints4Stats;// 统计最小点数（默认 3） // 搜索参数 bool progressiveSearch;// 渐进式搜索（自适应深度） bool onlyPositiveSearch;// 仅正向搜索 // 配准参数 double registrationRms;// 配准 RMS 误差};

输出标量场:

staticconstchar M3C2_DIST_SF_NAME[]="M3C2 distance"; staticconstchar DIST_UNCERTAINTY_SF_NAME[]="distance uncertainty"; staticconstchar SIG_CHANGE_SF_NAME[]="significant change"; staticconstchar STD_DEV_CLOUD1_SF_NAME[]="StdDev_cloud1"; staticconstchar STD_DEV_CLOUD2_SF_NAME[]="StdDev_cloud2"; staticconstchar DENSITY_CLOUD1_SF_NAME[]="Npoints_cloud1"; staticconstchar DENSITY_CLOUD2_SF_NAME[]="Npoints_cloud2";

M3C2 距离计算:

bool ComputeM3C2DistForPoint(const CCVector3& P,// 核心点 const CCVector3& N,// 法向量 ccPointCloud* cloud1,// 云 1 ccPointCloud* cloud2,// 云 2 const M3C2Params& params,double& dist,// 输出：M3C2 距离 double& LOD)// 输出：检测限（Level of Detection）{// 1. 提取圆柱形邻域（云 1） CCCoreLib::DgmOctree::ProgressiveCylindricalNeighbourhood cn1; cn1.center = P; cn1.dir = N; cn1.level = level1; cn1.maxHalfLength = params.projectionDepth; cn1.radius = params.projectionRadius;unsigned n1 = octree1->getPointsInCylindricalNeighbourhood(cn1);if(n1 < params.minPoints4Stats){returnfalse;// 点数不足}// 2. 计算统计量（云 1） double mean1, stdDev1; qM3C2Tools::ComputeStatistics( cn1.neighbours, params.useMedian, mean1,// 输出：沿法向量的平均位置 stdDev1 // 输出：标准差);// 3. 提取圆柱形邻域（云 2） CCCoreLib::DgmOctree::ProgressiveCylindricalNeighbourhood cn2; cn2.center = P + N * mean1;// 从云 1 的平均位置开始 cn2.dir = N; cn2.level = level2; cn2.maxHalfLength = params.projectionDepth; cn2.radius = params.projectionRadius;unsigned n2 = octree2->getPointsInCylindricalNeighbourhood(cn2);if(n2 < params.minPoints4Stats){returnfalse;}// 4. 计算统计量（云 2） double mean2, stdDev2; qM3C2Tools::ComputeStatistics( cn2.neighbours, params.useMedian, mean2, stdDev2 );// 5. M3C2 距离 dist = mean2 - mean1;// 6. 距离不确定性（LOD - Level of Detection） double LODStdDev;if(params.usePrecisionMaps){// 使用精度图 LODStdDev = stdDev1 * stdDev1 + stdDev2 * stdDev2;}else{// 标准 M3C2 LODStdDev =(stdDev1 * stdDev1)/ n1 +(stdDev2 * stdDev2)/ n2;}// 95% 置信区间 LOD =1.96*(sqrt(LODStdDev)+ params.registrationRms);returntrue;}

显著性变化检测:

// 如果距离大于 LOD，认为是显著变化 bool significant =(dist <-LOD || dist > LOD);// 存储到标量场 sigChangeSF->setValue(pointIndex, significant ?1.0f:0.0f);

渐进式搜索优化:

// 自适应调整圆柱深度，直到有足够的点或达到最大深度 while(cn1.currentHalfLength < cn1.maxHalfLength){unsigned n = octree->getPointsInCylindricalNeighbourhoodProgressive(cn1);if(n >= params.minPoints4Stats){ComputeStatistics(cn1.neighbours, params.useMedian, mean1, stdDev1);// 检查是否足够精确（均值±2σ < 当前深度） if(abs(mean1)+2* stdDev1 < cn1.currentHalfLength){break;// 足够精确，停止搜索}}// 扩大搜索深度 cn1.currentHalfLength *=1.5;}

7. 重采样和子采样

7.1 子采样方法

文件位置: CloudCompare/qCC\ccSubsamplingDlg.cpp

支持的方法:

enum CC_SUBSAMPLING_METHOD{ RANDOM =0,// 随机采样 RANDOM_PERCENT =1,// 百分比随机采样 SPATIAL =2,// 空间采样（泊松盘） OCTREE =3// 八叉树采样};

方法 1: 随机采样

CCCoreLib::ReferenceCloud* subsampledCloud = CCCoreLib::CloudSamplingTools::subsampleCloudRandomly( cloud, count,// 要保留的点数 progressCb );

实现: 随机洗牌，取前 N 个点

方法 2: 百分比随机采样

unsigned count = cloud->size()*(percentage /100.0); CCCoreLib::ReferenceCloud* subsampledCloud = CCCoreLib::CloudSamplingTools::subsampleCloudRandomly( cloud, count, progressCb);

方法 3: 空间采样（泊松盘）

// 基于最小点间距的泊松盘采样 PointCoordinateType minDist =0.01;// 最小点间距 // 可选：标量场调制 CCCoreLib::CloudSamplingTools::SFModulationParams modParams; modParams.enabled =true; modParams.a =(sfMaxSpacing - sfMinSpacing)/ deltaSF; modParams.b = sfMinSpacing - modParams.a * sfMin; CCCoreLib::ReferenceCloud* subsampledCloud = CCCoreLib::CloudSamplingTools::resampleCloudSpatially( cloud, minDist, modParams, octree, progressCb );

数学原理:

• 基于泊松盘采样
• 可选标量场调制：spacing(p) = a × SF(p) + b
• 保证任意两点间距 ≥ minDist
• 优先保留特征区域的点（通过标量场）

方法 4: 八叉树采样

unsignedchar level =7;// 八叉树层级（1-21） CCCoreLib::ReferenceCloud* subsampledCloud = CCCoreLib::CloudSamplingTools::subsampleCloudWithOctreeAtLevel( cloud, level, NEAREST_POINT_TO_CELL_CENTER,// 采样策略 progressCb, octree );

采样策略:

• NEAREST_POINT_TO_CELL_CENTER: 选择最接近单元中心的点
• RANDOM_POINT: 随机选择一个点

层级 vs 分辨率:

层级 1: 1 个单元 层级 2: 8 个单元 层级 3: 64 个单元 ... 层级 N: 8^(N-1)个单元 

8. 八叉树和空间索引

8.1 八叉树结构

类定义: CloudCompare/libs\qCC_db\include\ccOctree.h

class ccOctree:public QObject,public CCCoreLib::DgmOctree{public:// ===== 构建与更新 ===== static Shared ComputeOctree( ccGenericPointCloud* cloud, GenericProgressCallback* progressCb =nullptr);// ===== 包围盒操作 ===== voidmultiplyBoundingBox(PointCoordinateType multFactor);voidtranslateBoundingBox(const CCVector3& T); ccBBox getSquareBB()const; ccBBox getPointsBB()const;// ===== 显示模式 ===== enum DisplayMode{ WIRE =0,// 线框 MEAN_POINTS =1,// 平均点 MEAN_CUBES =2// 实体立方体};// ===== 绘制 ===== voiddraw(CC_DRAW_CONTEXT& context);};

8.2 邻域搜索

球形邻域搜索

DgmOctree::NeighboursSet neighbours;unsigned count = octree->getPointsInSphericalNeighbourhood(*queryPoint, radius, neighbours );// 处理结果 for(constauto& n : neighbours){unsigned pointIndex = n.pointIndex;double squaredDist = n.squareDistd;// ...}

圆柱形邻域搜索（M3C2 专用）

CCCoreLib::DgmOctree::CylindricalNeighbourhood cn; cn.center = P; cn.dir = N; cn.radius =0.1; cn.maxHalfLength =1.0; cn.level =7;unsigned count = octree->getPointsInCylindricalNeighbourhood(cn);

KNN 搜索

unsigned K =10; DgmOctree::NeighboursSet neighbours;unsigned count = octree->findPointNeighbourhood(*queryPoint,&neighbours, K, octreeLevel );

8.3 点拾取

bool ccOctree::pointPicking(const CCVector2d& clickPos,// 鼠标点击位置（屏幕坐标） const ccGLCameraParameters& camera,// 相机参数 PointDescriptor& output,// 输出：拾取的点信息 double pickWidth_pix =3.0// 拾取宽度（像素）)const{// 1. 构建拾取射线 CCVector3d rayOrigin, rayDir; camera.unproject(clickPos, rayOrigin, rayDir);// 2. 遍历八叉树单元 // 3. 对射线附近的点进行投影距离检测 // 4. 返回最近的点 return found;}