范 然， 金小刚

（浙江大学CAD&CG国家重点实验室，浙江 杭州 310058）

逆向工程中最普遍的应用模式是利用基于光学原理的扫描设备测量零件或模具外表面形成点云数据，从中提取几何特征进而重建多边形或 NURBS曲面[1]。随着扫描硬件精度的提升，原始扫描数据能够较好逼近物理模型的曲面形态，但是，删减处理始终是不可或缺的关键步骤。根据被测物体的摆放方式，扫描点云中不可避免地包含如墙面、支撑物等非目标背景数据，解决这一问题需设计能够高效并灵活指定大规模点云中待删除区域的选择算法。此外，原始扫描点云通常由多次测量的单片数据拼合而成，接合处存在重叠冗余采样，而且数据规模大、分布不均匀，普通计算机的计算及内存资源不易直接对其进行曲面重建。针对这一问题，点云精简算法的目标是减少数据量并使采样点依几何特征自适应均衡分布。

由于常用计算机输入方式是二维指针设备，二维套索UI是点云选择最直观的交互方式。研究领域通常使用简单空间形体实现点云选择[2]，并未给出支持套索UI的点云选择算法。目前，在逆向工程应用领域中多使用Geomagic[3]、Rapidform[4]等商业软件进行处理，相关算法并未公开，无法满足研究领域构建低成本三维扫描系统的需求。因此本文提出了一种支持套索UI的大规模点云选择算法，利用套索形状的矩形覆盖与输入点云八叉树编码剔除大部分点在多边形内判断。不同于传统的平面射线奇偶法及其改进算法，本文方法利用了扫描点云密集分布的特点，能够整体判断点云的局部区域。……