基于可展条求交：CAD点云模型中光滑特征曲线的计算与生成方法

LHOS T E D B Y可在www.sciencedirect.com网站上查阅计算设计与工程学报3（2016）102www.elsevier.com/locate/jcde基于可展条求交李嘉华a，彭波波b，na中国香港浸会大学中国哈尔滨工业大学接收日期：2015年4月8日;接受日期：2015年7月20日2015年8月13日在线发布摘要本文研究了从CAD类型的点云模型中计算光滑特征曲线的问题。该方法从可展带对的交点重构特征曲线，可展带对近似于特征两侧的区域。可展曲面的生成是基于通过变分形状近似方法对给定点云的线性近似。提出了一种线段排序算法，用于将特征线段收集到不同的特征序列中，以及收集到连续的数据点组中。一个可展曲面近似程序被用来细化数据点的入射近似平面为可展带。一些实验结果被包括来证明所提出的方法的性能&2015 年 CAD/CAM 工 程 师 协 会 。 由 Elsevier 制 作 和 主 持 。 这 是 一 个 在 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：特征提取;点云;可展曲面;逆向工程1. 介绍随着激光扫描技术的迅速发展，许多CAD模型都是以无组织的点云形式存储的。直接从点云中提取感兴趣的信息而不首先将其转换为其他紧凑表示（如网格）是一个重要且具有挑战性的问题。本文研究了从点云数据中提取特征曲线的问题，提出的方法在几何处理中有着广泛的应用，如模型重建和几何压缩。我们提出了一个框架，从点云模型中提取特征曲线。参照图 1的点云模型和使用我们的方法提取的那些相关的特征曲线。我们的方法首先计算点云的分段线性近似基于这种线性近似，我们设计了一种技术，用于拟合光滑的可展曲面到模型的各个特征区域最后，平滑特性n通讯作者。电邮地址：lee.kai. gmail.com（K.W. Lee），pengbo@hitwh.edu.cn（P. Bo）。曲线被计算为相应的相邻可展曲面的相交曲线。1.1. 相关作品变分形状近似：Cohen等人首先提出了一个变分框架，使用基于法线的误差度量2; 1[1]来解决三角形网格的形状近似问题。Kobbelt等人[2]丰富了几何代理的种类，从简单的平面到包括球体，圆柱体和滚球作为额外的几何代理。这里的关键观察是，技术CAD对象大多具有显示这些类似几何形状的面片。Yan等人[3]遵循类似的思路，将代理集推广为二次曲面，并提出了一种新的平滑分割区域之间不规则边界曲线的算法。他们的推广扩大了近似的范围，不仅适用于技术CAD对象，也适用于像斯坦福兔子这样的有机我们扩展了点云分割的变分框架，这是我们从点云提取特征管道特征提取：虽然特征提取已经被作为许多数字网格处理http://dx.doi.org/10.1016/j.jcde.2015.07.0012288-4300/2015 CAD/CAM工程师协会。&由Elsevier制作和主持。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。K.W. 李，P。博/计算设计与工程学报3（2016）10210331/1C¼ðÞCXX我C C¼fC CgP我J8C¼P我公司简介ð ÞP¼ fg形状匹配、压缩等算法的改进，寻求更好的网格和点云特征提取算法仍然是众多研究者关注的焦点。Chica[4]最近提出从密集点云中提取特征，首先将点云转换为离散体积表示，并从中计算可见性图。基于可见性信息检测顶点、边和面等曲面组件。Daniel等人[5]利用鲁棒移动最小二乘（RLMS）[6]的概念，并提出了一种用于从点云中提取鲁棒平滑特征的多步精化方法。潜在的特征点首先用RMLS算子识别，然后投影到RMLS框架局部近似的特征附近的相交表面上[6]。采用基于主成分分析（PCA）的平滑方法，对由RMLS-projection产生的锯齿状边缘进行了修正。Gumhold等人[7]和Pauly等人报道了更多关于从点云数据中提取特征线的工作。[8]的一项建议。可展曲面：可展曲面是一个直纹曲面，可以展开成平面而不会变形。它是一个单参数平面族的包络，它在任何地方都消失了高斯曲率[9]。这些优良的性质使可展曲面广泛应用于工业，如造船[10]。可展曲面的几何特性使其成为建筑中自由形状建模的良好表示和设计工具[11]。切线可展曲面是由3D空间中一条曲线的切线构成的，该曲线是奇异曲线，或者回归曲线[9]。在文献[12]中采用了可展曲面的方法来建立纸张弯曲的模型，其形状为2. 线性特征提取在本节中，我们提出了一种从点云中查找线性特征的算法。该算法包括两个步骤：（1）寻找特征线段作为近似给定点云的平面的交点。线性近似计算采用变分形状近似方法;（2）一个排序算法，用于收集特征线段成组的模型中的特征曲线2.1. 点云我们将著名的变分形状近似方法扩展到点云。给定一个非结构化点云p1;假设每个数据点pi有一个由n pi表示的关联法线。我们的目标是划分成k个不相交的点簇i，使得i≠jiaj和kki，并最终表示每个具有最佳拟合平面的聚类，该最佳拟合平面具有定义的误差公制将点聚类i的形状代理表示为代表对PiXi;Ni，其中Xi是聚类i中的点的重心，而Ni是由与聚类Ci的协方差矩阵的最小特征值相关联的特征向量指示的方向。一组数据点Ci并且其对应的代理Pi由下式测量：EC;PXEp;PpjACi可通过编辑测地线曲线进行编辑。有一些论文讨论了可展曲面的拟合问题。在文献[13]中，锥被用作变分框架中的代理来近似三角形3D模型。在[14]中，在对偶空间中研究了拟合点云的可展曲面。文献[11]提出了自由形状设计的可展条模型。这种曲面的半离散表示是一种新的形状设计方法，比平面元素更强大，比双曲面需要更少的努力[15，16]。1/4J nnnpjn-NiJ2pjACi当一组与点群相关联的代理Pi的分区1;.; k的i最小化EC;P Ci;Pii¼1图1.一、（a）CAD模型的原始数据点;以及（b）重构的特征曲线。104K.W. 李，P。博/计算设计与工程学报3（2016）102CPCð ÞCðÞðÞCðÞ¼ðÞ¼ðÞ1/4 fgC该算法由以下步骤组成：1. k：首先选择k个随机点作为k个聚类的初始种子。代理P iX i;N i计算每个聚类i的最小二乘拟合平面到点集NK si，这些点是使用[17]从初始种子收集的K个最近邻居。通常，K在15至20的范围2. 集群增长：然后我们用代理增长集群C iPiX i;N i通过将点p j添加到具有最小误差E pj;P i的聚类，从初始种子s i中取出。从初始种子s i开始，我们计算作为初始种子的K个最近邻居的点p j的误差E pj;P i。每个错误连同指示错误来自哪个聚类i的标签i将计算的Pi插入全局优先级队列。然后，通过以最小错误重复地从优先级队列中弹出点来执行集群增长过程，直到队列为空。什么也不会做，如果弹出点Pj已经被分配给簇。否则，点pj将被分配给由关联标签i指示的聚类i。3. 代理拟合：一旦点云被分割成k个聚类，我们需要更新聚类的代表代理，以便代理能够最好地代表新发现的聚类。 对于新群集，一、新的代理人计算Pi Xi;Ni，其中Xi是聚类的质心，Ni是聚类i的点法线的平均值。4. 停止标准：停止标准被设置为达到最大迭代次数或两次连续迭代的总近似误差之间的差异小于定义的阈值。CAD模型的分割结果见图2。通过计算相邻数据点簇的代理平面的相交，可以很容易地2.2. 分段线性特征曲线点云的线性逼近，即由平面代理，提供了一个忠实的几何蓝图，从该特征段可以提取。我们将识别特征线段，然后提出一种新的程序来收集不相交的线段到对应于同一特征曲线的特征线段序列中。2.2.1. 特征线段提取相交线段是任意两个相邻代理之间的相交线。收集交点线段后，将识别要素线段作为那些二面角大于预定阈值的相交段。这种简单而有效的方法被广泛用于其他特征边缘识别[18]。在我们的实验中，我们发现将阈值设置为361对于所使用的CAD类点云是足够的。Example. 在图7（d）中，相邻代理之间的相交线段以红色呈现。最初有145条线段，但最终有105条线段，这些线段被识别为特征段，如图所示。 7（e）.2.2.2. 查找要素线序列到目前为止，我们得到的特征线段是无组织的，即使它们中的一些可能有助于相同的特征曲线。然后，我们提出了一种新的算法，将所有线段组织成连续线段组，其中每组指单个特征曲线。 此外，每一组特征线与其两侧的相关数据点簇相耦合，这些数据点簇很容易通过识别有助于这些特征线相交计算的簇来找到。请参阅图4中的一些连续线段和相关的数据点簇我们的排序算法的特征线段是基于一些几何条件，确定组成同一特征曲线的入射线段。粗略地说，我们希望为每个特征线段si找到相邻的特征线段sj，其中它们之间的过渡是平滑的。设球面i表示线段si的边界球面，该线段的中心是si的中点，半径是si长度的一半。在下文中，我们将推导出2D中连续线段的必要条件，其中边界球图二、点云的变分分割（a）原始点云;（b）分割结果;以及（c）来自代理相交的多边形网格K.W. 李，P。博/计算设计与工程学报3（2016）102105s我1K每一条线段都变成了一个圆。条件我们直接在3D空间工作。条件1：（圆相交约束）。我们要求两个连续线段的边界圆彼此相交。设线段的两个边界圆为C1和C2，圆心分别为c1和c2，半径分别为r1和r2。很容易看出，C1和C2彼此相交，如果（图）。（第3（a）段）Jc1-c2Jrr1r2：11条件2：（线封闭性约束）。两个连续的线段的端点应落在两个封闭圆的相交区域内，如图所示。 3（b）款。该约束被定义为δ1rr2 和δ2rr1δ2r其中δ1是从线段s1的端点e1到中心c2和δ2是从端点e2的距离既然我们有Ju1-u2 J¼ Jc1-c2 J- Jc1-u2 J- jc2-u1 J1-c2J-1 -c 31/4r1/4r2/4Jc1-c2J哪里r1和r2是 圆的半径c1和 C2分别因此，条件（3）变为Je1-e2Jrr1r2Jc1-c2J：144条件4：（平滑度约束）。线段序列尽可能平滑地增长。为了最小化在显影过程中的弯曲，具有最小出射角的相邻段被选择在那些潜在段中。见图第3段（d）分段。arg minsisj5jANsi段序列S^fs;线段S2到中心C1。条件3：（线相交约束）。 双线分段-片段给定具有N个特征段的集合S的点云我们将通过将S划分为m来找到集合S的划分R不相交的片段序列，使得首先是任意段s1/1如图3（c）所示，这些部分彼此相交。线段将彼此相交的条件是：Je1-e2 Jr Ju1-u2J：3i最多会有两个潜在的满足条件（1）、（2）、（4）和（5）的线段sj和sk，（5）由于存在两个端点，其中线段s为i。因此，单个序列可以通过递归地探索潜在段sj和sk来增长，直到序列经历任何急转弯。C1C2R1R2C1c1 c2C2C1C2e2e1δ2Sδ1C2S21C1图三.用于确定连续要素线线段的约束。(a)圆相交约束;（b）线接近约束;（c）线相交约束;以及(d)平滑度约束。C1ee1C22Su2u1C2S21C1C3S3CC31C2SS21C1C2106K.W. 李，P。博/计算设计与工程学报3（2016）102SRð Þ ð Þ （<>>：m>S ’图四、要素线序列和关联的数据点聚类。当出射角大于601时，检测到条件，因此序列将终止于类CAD点云模型的拐角处在算法2.1中概述了提取以片段s开始的单个片段序列的算法，在算法2.2中概述了从给定的一组特征段生长所有序列。算法2.2. G行ALLS设备S。’m8>sM算法2.1. G行S方程。程序EXPLORE（s）θ注释：收集si;sj如果siasisoθ则SeqEXPLOREASESi如果sjasjsoθ（Seq而SaSR返回R3. 用可展曲面拟合假设所有要素线段S都已划分为m组：Si;i/1; 每组S i <$fs1;...; s kg 是一然后主要EXPLOREORESj对于点集模型中的每个特征，我们也有两个平面代理序列和与这些平面代理相关的点集全局序列塞格什探索return（Seq）在这一点上，我们已经获得了一系列的特征段Si，它可以作为点云模型的特征曲线的近似。显然，增加平面代理的数量来近似点云模型K.W. 李，P。博/计算设计与工程学报3（2016）102107ðÞð Þ ð Þ ð Þ ð Þ图五、可展曲面初始化。（a）原始数据点;（b）一系列平面;（c）表面的控制多边形;以及（d）初始直纹表面。可以随后提高对特征曲线的近似的精度然而，大量的平面代理可能会导致我们的特征线段提取的不稳定性与太多的相邻代理交点和微小的线段。因此，而不是直接增加代理的数量，以提高近似精度，我们提出了一种新的方法，利用可展曲面，以进一步提高特征曲线提取过程。我们的方法是首先找到一对可展曲面来近似提取的特征序列两侧的平面代理。然后，可展曲面对被进一步优化以拟合由代理表示的原始数据点。最后，提取新的特征序列作为可展曲面对的交集。这个想法源于这样的知识，即单参数平面族的包络是可展曲面。使用可展曲面的优点如下：(1) 处理可展曲面比处理许多平面容易得多.(2) 可展曲面可以进一步优化，以提高其接近点集和可展性。(3) 两个可展曲面的交线是一条光滑曲线而不是一条光滑曲线。3.1. 直纹面初始化我们的可展曲面拟合算法需要一个直纹曲面作为初始化，然后通过提高其可展性以及与参考数据点的接近度来进一步细化。我们使用的表面表示法是张量积B样条曲面，定义为我们首先计算相邻代理平面的相交线。结果是一系列直线L。使用平面代理的知识，我们找到两个平行的平面PL1和PL2，它们大致垂直于这些直线，并且在它们之间有数据点在计算L与PL1和PL2的交点后，我们得到两条折线，这两条折线被视为两条B样条曲线p（u）和q（u）的控制多边形。以这种方式构造的直纹曲面可能不太可展，也不太接近参考点集，但它作为进一步优化的初始状态已经足够好了，从而提高了它的质量。生成初始规则面的过程如图53.2. 可展曲面拟合我们的目标是细化初始直纹曲面，以提高其可展性和与数据点D的接近度。我们将目标函数公式化为f约为λfdev：6fapprox是测量可展曲面与数据点D的接近程度的项。它是从点DiAD到可展曲面X u;v的距离之和。fdev是可展曲面上某些采样点的可展性之和。λ在fapprox和fdev之间取得平衡。可展曲面沿同一刻线具有相同的法线方向。我们使用一个可展性条件，迫使两条直线的距离为我们用p3q表示由点p和点q所张成的直线.在参数ui处，规则段为p ui3q ui。在p ui或q ui处与边界曲线相切的线段表示为3.pup_ uJpui-quiJ;我X u; vvpu 1- vqu;其中p（u）和q（u）是两条B样条曲线。和.Jp_uiJJpui-quiJJq_uiJ计算逼近每个簇的可展曲面顺序为了生成初始直纹曲面的控制多边形，我们使用与Ci对应的平面代理Pi。这两条线段形成一个四边形。发展-可操作性条件等于该四边形的对角线的零距离。表示两条对角线之间的距离回想一下，对于特征序列的任一侧，我们都有一组连续的数据点聚类Ci。我们的目标是qui3quiq_ui：108K.W. 李，P。博/计算设计与工程学报3（2016）102X¼d：108mmð ÞðÞ半]¼ð Þli<$qui3puið Þ ðÞp_ui我角点是两条或多条要素线的交点线l1和l2由一个可展曲面拟合点集D是一个小我我di¼dist l1; l2; 7比D的大小更大，因为很难确定它到底是如何形成的。我我哪里.我Jpu-quJ大开发应该是一个大的发展。由于这种策略，相交曲线的一部分可能会从点集逃逸。这部分很容易通过计算l1½pui3qui和我我jq_ uiJq_ui距离的点集，并简单地丢弃作为一个后，加工步骤。二、Jpu i-qu iJJp_uiJ3.4. 角点检测整个直纹曲面的可展性为采样条件为fdev2我从数据点Di到可展曲面X u;v的距离计算需要计算Di在Xu;v上的足迹。Di的足点表示为t Di。足迹查找是最耗时的步骤[19]，并在许多论文中进行了研究[20]。这是一个非线性问题，需要迭代求解。为了减少优化所用的时间，我们首先在预处理步骤中在可展曲面上采样足够密集的点，并构建ANN树[17]以加速最近点查询。当查询点Di的足迹时，找到最近的点Fi作为其在X u;v上的粗略足迹。然后采用牛顿法对以Fi为初始值的足点计算进行了改进。由于牛顿法具有二次收敛性，因此不超过5次迭代就可以达到一个好的足迹点。贴近度项的公式为：f约为¼X距离2毫米;t毫米直径：19毫米目标函数（6）使用高斯-牛顿法最小化。由于B样条的局部性质，在每个优化步骤中要求解的线性系统的矩阵是稀疏矩阵。我们使用Levenberg-Marquardt正则化[21]，因此这些矩阵是正定的。我们使用Cholesky分解，使用稀疏矩阵求解器库TAUCS[22]计算解决方案。对于本文中的模型，最复杂的特征需要大约15秒的优化时间，没有代码优化。3.3. 可展曲面求交有两个可展曲面拟合数据点，相交曲线应该是一个很好的近似特征。设两个可展曲面为X1和X2.我们首先将X1离散成三角形或四边形族，记为TR。然后，我们在X2上从一端行进到另一端，在参数域0; 1中前进。在每个位置vi，我们计算划线LiX2vi与TR的交点。所有的交点形成一个交线，它是交线的离散表示，因此是特征的良好表示 参照图 6（a）举例说明。以立方体为例。它的角是三个这条线是三个平面的交点。前面部分中的讨论每次都处理每条要素线。因此，在一个拐角处会有三条相交线，这些线可能不会恰好穿过一个点。我们注意到，靠近两条以上特征线的点非常接近精确的角点。为了得到一致的角点，我们在优化中强制约束，即两个可展曲面对两个不同的特征和同一个面有贡献，在角点处应该共享相同的切平面。参考图6（b）的示例。4. 实验结果在本节中，FanDisk和L-joint点云用于实验。首先，使用我们在图1和图2中提出的变分点云分割框架将FanDisk和L-joint点云模型分别分割为50和60个点簇。7（b）和8（b）。点云模型的线性平面近似是从点群的平面代理的交点导出的，如图1A和1B所示。7（c）和8（c）。一旦收集了来自相邻代理的相交线，就应用过滤来从所有相交线段中提取那些特征线段（图1A和1B）。图7（d）和8（d）），结果示于图7（d）和8（d）。7（e）和8（e）。通过应用我们的新的序列开发算法，特征段被分组到不同的不相交顺序序列集的可展曲面拟合。一旦特征序列被收集，序列的每个单独段的入射平面代理用于序列两侧的可展表面拟合。光滑的特征线从序列的两个拟合可展曲面之间的相交处获得。图图7（f）和图8（f）示出了在FanDisk和L-joint上获得的平滑特征线。图9中的特写视图展示了特征段序列和平滑特征线之间的平滑度差异。5. 结论我们已经提出了一个框架，从点云采样技术CAD对象的特征提取。我们将变分形状近似的框架扩展到点云分割，并推导出一个线性几何近似的点云与平面代理。特征我：K.W. 李，P。博/计算设计与工程学报3（2016）102109图六、（a）可展曲面优化和曲面相交。（b）模型上的角点检测见图7。 (a)原始数据点;（b）聚类结果;（c）线性平面近似;（d）相交线;（e）特征线段;以及（f）平滑特征线。从代理的交集中识别片段，并使用我们提出的算法收集片段序列的有序集。然后，将特征线序列与平面代理一起与优化的可展曲面拟合，从优化的可展曲面中提取平滑的特征线从可展开曲面的交点形成折线。实验结果报告通过应用我们的算法的点云模型的CAD模型。对于未来的工作，我们想研究的关系，船舶的数量集群在点云110K.W. 李，P。博/计算设计与工程学报3（2016）102见图8。(a)L形模型的原始数据点;（b）聚类结果;（c）线性平面近似;（d）相交线;（e）特征线段;以及（f）平滑特征线。见图9。特征线与光滑特征曲线的一些细节比较。(a)特征线段;（b）平滑特征曲线;（c）特征线段;以及（d）平滑特征曲线。分割到最终特征线的平滑度。此外，使用用户指定数量的聚类，直到形状近似误差低于某个阈值。它有必要了解近似误差如何影响可展曲面拟合，从而最终影响特征线的质量。K.W. 李，P。博/计算设计与工程学报3（2016）102111利益冲突作者没有任何利益冲突确认本课题得到了国家自然科学基金项目（No.61202275）和山东省优秀青年科学家奖项目（No.20000000）的资助。BS 2013ZZ001）。引用[1] 放大图片作者：J.变分形状近似。ACM Transactions on Graphics2004;23（3）905[2] 吴J，Kobbelt Leif.基于混合变分曲面近似的结构恢复。计算机图形论坛2005; 24（九月（8））277-84。[3] 严丹明，刘永，王伟.基于变分形状逼近的二次曲面提取。In：GMP;2006; p. 73比86[4] 奇 卡 河 基 于 可 见 性 的 离 散 模 型 特 征 提 取 。 在 ： SPM '08 ：Proceedings of the 2008 ACM Symposium on Solid and PhysicalModeling ， ACM ， New York ， NY ， USA; 2008; p. 347-352.http://dx.doi.org/10.1145/1364901.1364951。[5] Daniels JI，Ha LK，Ochotta T，Silva CT.从点云数据中提取鲁棒的光 滑 特 征 。 在 ： SMIhttp://dx.doi.org/10 的 网 站 。1109/SMI.2007.32。[6] Fleishman S，Cohen-Or D，Silva CT：鲁棒移动最小二乘拟合与尖锐 特 征 ， ACM 图 形 学 报 2005;24 （ 3 ） 544-552 。http://dx.doi.org/10.1145/1073204.1073227网站。[7] 放大图片创作者：Gumhold S，Wang X，Macleod R.点云特征提取。见：第10届国际啮合圆桌会议记录; 2001年;第293-305页。[8] Pauly M，Keiser R，Gross MH.点采样曲面的多尺度特征提取。计算机图形论坛2003; 22（3）281-90.[9] Carmo MD.曲线与曲面的微分几何，Prentice Hall，1976年。[10] Perez F，Suarez JA.拟可展b样条曲面在船体设计中的应用。计算机辅助设计2007; 39（10）853-62。[11] Pottmann H ， Schiftner A ， Bo P ， Schmiedhofer H ， Wang W ，Baldassini N，Wallner J.单曲面的自由曲面，ACM Transaction onGraphics2008;27（3），Proceedings of SIGGRAPH.[12] 放大图片作者：Bo P，Wang W.用于纸张弯曲建模的测地线控制的可展曲面。计算机图形论坛2007; 26（3）365-74.[13] 放大图片Julius D，Kraevoy V，Sheffer A. D图：准可展网格分割。In：Computer Graphics Forum，Proceedings of Euro- graphics 2005;2005; p. 第581-590页。[14] 彼得内尔·M 可展曲面拟合点云。计算机辅助几何设计2004; 21（8）785-803.[15] 刘毅，杨永良，王伟. 使用圆锥形网格和可展曲面进行几何建模。ACM Transactions onGraphics 2006; 25（3）681-9.[16] 刘毅，刘毅，王伟，王伟. 建筑用多层自由结构的几何学。 ACMTransactions on Graphics2007; 26（3）65：1-1.[17] Arya，S.，芒特，D. ANN：用于近似最近邻搜索的库。CGC计算几何研讨会论文集。IEEE：Providence，RI. 1998.[18] Hubeli A，Gross MH.非结构网格的多分辨率特征提取。In：IEEEVisualization; 2001.[19] 杨宏，王伟，孙军. B样条曲线逼近的控制点调整.计算机辅助几何设计 2004;36（7）.[20] 胡S-M，Wallner J.曲线曲面正交投影的二阶算法。计算机辅助几何设计2005; 22（3）251-60.[21] 凯利BCT。迭代优化方法，SIAM，费城，1999年。[22] 托 莱 多 湾 TAUCS 是 一 个 稀 疏 线 性 解 算 器 库 。 C Library ，www.tau.ac.il/Tstoledo/taucs/，2003。