点的正交投影：计算设计与工程杂志综述

计算设计与工程杂志，卷。号12（2014）116~127www.jcde.orgCAD/CAM应用中的点的正交投影：综述Kwanghee Ko1，2 *和Takis Sakkalis31光州科技大学机电一体化学院，123 Cheomdangwagiro，Bukgu，Gwangju，500-712，Korea2韩国文化技术研究所，光州科学技术学院，123 Cheomdangwagiro，Bukgu，Gwangju，500-712，Korea3.雅典农业大学科学系，雅典，118 55，希腊（2014年1月8日接收;2014年2月24日修订;2014年2月25日接受摘要本文旨在审查的方法，计算正交投影的点到曲线和曲面，这是在隐式或参数形式或作为点云。特别强调的是放置在二次曲线上的正交投影，以及在隐式和参数形式的曲线和曲面上的点的正交投影的评论除了二次曲线，计算方法分为两大类的核心方法：迭代和细分为基础。本文将点的正交投影推广到曲线在曲面上的正交投影接下来，继续讨论点到点云上的正交投影，这在正交投影的上下文中产生了不同的算法分支最后，本文对各种应用程序的适当选择方法的指导意见关键词：正交投影;点投影;曲线投影;配准;最小距离;有向投影1. 介绍点的正交投影是在曲线或曲面上找到一个点的过程，使得连接空间中的点和曲线或曲面上的点的向量变得垂直于曲线或曲面。正交投影是计算机辅助几何设计和应用中最关键的运算之一，而高效、鲁棒的正交投影计算对于计算曲线或曲面上的最近点（足点）、空间点的参数估计、求交计算以及相似性等各种运算都是必不可少的正交投影对于点和曲线以及点和曲面的配对有效。它也被扩展到覆盖正交投影的曲线到曲面上。表1示出了可以考虑正交投影的实体对在这项工作中，一个点到曲线或曲面上的正交投影是一个主要的操作。计算曲线或曲面上的一点到给定点的最小距离是正交投影的一个重要应用（这里排除了不能计算正交投影的情况当一点相对靠近曲线或曲面时，曲线或曲面上最靠近给定点*通讯作者。联系电话：+82-62-715-3225，传真：+82-62-715-2384电子邮件地址：khko@gist.ac.kr© 2014 CAD/CAM工程师协会Techno-Press doi：10.7315/JCDE. 2014. 012是点在曲线或曲面上的正交投影需要这种计算的典型示例是定位。定位，也称为配准，是尽可能接近地匹配两个对象的考虑3D空间中的一组点和一个曲面。点与曲面之间的对应关系是通过计算曲面上的点来建立的，这些点之间的距离最小这些点称为曲面上的足点Besl和McKay [1]提出了一种配准算法，称为ICP算法，该算法基于最近点的计算以进行对应。该方法的变体已在[2]-[5]中给出，仅举几例。它们通常使用附加信息来提高迭代的收敛性或减少对初始值的依赖性表1.基于几何实体的正交投影分类。这里，“x”表示未定义正交投影。“t”表示可以定义正交投影，但实际上可能不使用。“o”表示正交投影有效的情况。点曲线表面点XOO曲线X不O表面XX不K. Ko等/Journal of Computational Design and Engineering，Vol.号12（2014）116~127117点的位置和表面的收敛。参数估计是估计曲线或曲面逼近中给定点的参数值的过程这是逆向工程或物体重建中的重要步骤，当形状由一组点定义时。参数化是CAD/CAM、计算机图形学等领域中的一个重要课题。不过，这里介绍其中的一些。Ma和Kruth [6]引入了用于3D点的参数估计的基面的概念使用3D点创建基础曲面，这是对点的粗略近似。接着，将这些点正交投影到基面上，并将基面上的投影点的参数作为3D点的参数给出Piegl和Tiller [7]重新研究了类似的方法。他们提出了一种高效计算正交投影的方法正交投影可用于计算曲线曲面的交线Limaien和Trochu[8]利用正交投影的性质，即当两个对象（曲线或曲面）相交时，从初始点开始的连续正交投影点将收敛到交点。Escobar等人[9]使用正交投影作为对齐曲面三角剖分与曲线的关键操作。给定曲线，三角形网格的边界边与曲线轨迹对齐。Flory和Hessel [10]使用正交投影作为在曲面上设计曲线的一种操作他们解决了用曲线拟合曲面上的点的问题，该曲线被约束为位于曲面上给定点云和拟合曲线的初始位置，通过最小化拟合误差来更新曲线的位置，所述拟合误差使用切空间中的距离范数来计算。通过正交投影计算曲线上给定点的足点，并计算各点到足点的距离，以评价拟合误差。Zheng和Chen [11]讨论了一般情况下的正交投影他们解决了计算规则曲面上点和曲线之间的最短路径这里，从给定点到曲线的最短路径成为它们之间的测地线此外，还发现曲线上给出最短路径的点该方法通过引入“正交性”条件实现了对现有方法的改进正交投影用作将几何特征拟合到2D或3D点云的组件拟合误差通常用给定点到几何特征的正交距离来度量最小化这样的误差涉及满足尽管正交投影点可能不被显式地计算该方法为点与各种几何实体的最小二乘拟合提供了基础。Ahn等人[12]讨论了圆、球、椭圆、双曲线、抛物线对给定点的最小二乘拟合问题一个目标函数，称为性能指标，推导出，它提供了正交距离的平方和。该目标函数的最优解使用高斯-牛顿型迭代获得。这一思想也适用于[13]和[14]中的隐式曲线和曲面许多研究人员对最小二乘拟合进行了进一步的讨论，例如[15]和[16]，仅举几例。在数学上，正交点投影不一定与最小距离计算相同[17]。可能存在多个正交投影点，或者不存在这样的点。另一方面，总是可以计算最小距离。3D空间中的正交点投影产生最小距离的足点的情况是当该点比任何其他边缘、边界和拐角点更靠近曲线或表面的内部时当给定一组点时，通过点的正交投影，可以计算出大多数点大量的文献致力于开发计算点到曲线或曲面的正交投影的高效且鲁棒的求解方法特别是牛顿-拉夫逊方法，一种迭代寻找正交投影的局部方案，经常被选为求解方法。虽然对该方法进行了充分的数学分析，并认识到其优缺点，但没有一种方法可以同时满足鲁棒性、效率和本文研究曲线曲面的正交投影问题。给出了点和曲线正交投影的数学定义，为深入理解这一问题提供了坚实的基础。接下来，对迄今为止在各个学科中介绍的各种方法分为两类：基于迭代的方法和基于细分的方法。前者通过代数和几何迭代求解来计算正交投影。后者将曲线或曲面细分为较小的曲线或曲面，然后选择包含解决方案的曲线或曲面。对于精确的解，可以采用基于迭代的方法，例如牛顿-拉夫森方法讨论扩展到覆盖点到点云的正交投影。最后，本文对各种应用程序的适当选择方法的指导意见。2. 正交投影术语正交投影起源于欧几里德几何学，当一个点P投影到3D空间中的平面TP上（它的脚点Q）时。 正如术语正交所指示的，矢量P-Q与eve成90度角-直角-118K. Ko等/ Journal of Computational Design and Engineering，Vol.号12（2014）116~127位于T P中的ry向量。由于位于T P中的每个向量都可以被认为与TP相切，因此可以很容易地将这个概念推广到具有切向量的对象，从而推广到微分几何领域。定义1. 设S是Rn的一个非空子集，使得对于每个点a∈S，都有S在a处的切向量Ta。对于点P Rn，P在S上的正交投影是点集Q S，使得向量P-Q垂直于TQ。□在本书中，除非另有说明，我们将主要处理光滑（闭合）曲线和曲面2.1 点在曲线或曲面上的投影设c是 Rn中的一条（闭）参数曲线，即c：t<$[0，1]→Rn，它是光滑的，除了可能在有限个点处。对于点PRn，正交投影集由c上的所有点组成，使得（P-c（t））=0.（一）在正交投影点不是连续变化的点，但存在切向量T的情况下，我们仍然可以通过调用定义1来定义一组正交投影。当S是参数给定时，该定义可以直接应用现在让s是Rn中的（闭）光滑曲面，由s={q|F（q）= 0，q<$Rn}，其中F：Rn→ R是光滑函数. 那么，PRn在s上的正交投影的集合等于rorth ={Q| （ P-Q ） //Af （ Q ） ， P ∈ Rn}.（二）2.2 曲线在曲面上的投影现在让我们集中在3D的情况下，并考虑c=（c1，c2，c3）：[0，1] →R3是参数曲线，s是R3中的光滑超曲面。假设s是参数化的;也就是说，s是正则函数s：[0，1] ×[0，1] → R3，s（u，v）=（s1，s2，s3）。那么，su× sv是在s（u，v）处垂直于s的非零向量。因此，c在s上的正交投影应该是s上的点的集合，使得（c（t）-s（u，v））·su= 0和（c（t）-s（u，v））·sv=0。对于s是隐式定义的情况，我们可以导出类似的方程。2.3 正交投影与最小距离正交投影与点和集合之间的最小距离以及点到集合上的距离投影的概念有关定义2. 设P∈Rn，S是Rn的非空子集.然后，从P到S的距离d（P，S）被定义为：d（ P，S） = infQ∈S d（ P，Q）.（三）□P在S上的距离投影被定义为Γ dist ={Q| Q ∈ cl（S）且d（P，Q）= d（P，S）}.（四）这里，cl（S）是S的闭包，是Rn中所有包含S的闭子集的交集。的确，如果C和S是光滑的，并且距离投影是Int（S），则dist北卡罗来纳州。这里，Int（S）是由包含在S中的所有开集的并集定义的S的内部。然而，反过来就不对了。实际上，距离函数d（P，Q）的任何临界点，Q是正交投影点，但不一定是下界3. 正交投影一个点在曲线或曲面上的正交投影可以通过求解方程来获得。（一）.这里，曲线和曲面是数学定义的。然而，该方程是一个非线性方程，除了几种特殊情况外，不容易解析求解因此，各种数值方法已被认为是找到正交投影的基础上方程。（一）.对一般曲线曲面进行正交投影然而，一组研究人员专注于二次曲线，并试图开发有效计算二次曲线上正交投影的方法。3.1 二次曲线上的正交当考虑二次曲线（椭圆、双曲线、抛物线）时，正交投影问题可以用更严格的数学方式处理一般情况下，这个问题是在最小二乘拟合的二次几何实体的上下文中解决的，正交投影是拟合过程中的关键操作。Zerov和Wijew-ickrema [18]解决了点投影到二次曲线上的问题。他们的重点放在具有良好的精度和简单性的解决方案算法的鲁棒性和实用性方面。虽然讨论了几种方法，这些方法相对较快，如[12]，[13]和[14]，但只有少数方法在理论上被证明是稳健的[16]。[19]”[20]。对这些方法进行了分析，并在[18]中提出了[19]的改进算法一点在二次曲线上的正交投影问题用公式表示如下。圆锥曲线定义为：U（ x，y） = Ax2 + 2Bxy + Cy2 + 2Dx + 2Ey + F =0.（五）考虑一个点（xp，yp）。则点在二次曲线上的正交投影应满足正交条件K. Ko等/Journal of Computational Design and Engineering，Vol.号12（2014）116~127119ppxp- x = tp（ Ax + By + D），yp-y = tp（ Bx + Cy + E），（6）一些tp。从几何上讲，这些条件是由向量（xp-x，yp-y）平行于U的正交性导出的.求解x和y的方程组产生作为tp的函数的两个表达式，然后将其代入圆锥方程，其中，和是实数。当det（M）= 0且θ= 0时，给定的二次曲线Eq.（5）减少到一条或一对线。然后，可以容易地执行正交投影。当detM 0且= 1时，则我们有zT Ez = 0，E = αM + N.（十一）在这里，det（E）满足等式det（E）= 0。这意味着Eq.（11）是简并的，并且由两条线组成，或者c t4 + c t3 + c t2 + c t+ c = 0。（七）一条线。然后，求出了正投影的足点，4 p 3 p2 p 1 p 0将给定点简化为二次曲线（5）的交点这里，系数ck用A、B、C、D、E和F表示。方程的解是二次曲线上的正交投影点然而，找到解决方案并不是一件简单的任务。虽然存在解该方程的解析公式，但由于其复杂性，它不能容易地在实践中使用。各种数值方法，包括本地和全球计划可以用来找到根的方程。[21]-[25].然而，在性能和稳定性方面，它们不能容易地在实践中使用。 文献[16]提出了一种点在二次曲线上的正交投影算法。随着tp的消除，Eq. (6)可以重写为R（ x，y） =（xp-x）（Bx + Cy + E）- （yp-y）（Ax + By + D） = 0。（八）在正交投影点处，等式（5）和（8）是饱和的。使用矩阵符号，我们能够重写方程。和台词选择输给给定点的点作为最终的正交投影点。Eberly该方法被开发用于椭圆上的正交投影，后来被扩展到其他二次曲线和3D二次曲面[15]。这些点的选择从平移和旋转椭圆的坐标系开始，如等式2所示（12）获得正则坐标中的表示X2y 2a2+ b2- 1 = 0，a ≥ b> 0.（十二）接下来，类似于Eq.（6），在Eq中替换（12）产生变量t p的方程。(5)（8）如下。P（tp）=（t的2x2+ a2）2+（tb2y2+b2）2 - 1= 0。（十三）p pzT Mz = 0，zT Nz = 0，（9）哪里一B D然后，Eq的根。(13)对应于正交投影点。为了解决Eq。（13），选择起始点为M =[B C E]D E FN =-2B A-C xp B - yp A -E[A-C 2B xp C - yp B + D]xp B - yp A - E xp C - yp B + D 2（xp E -yp D）且z=[xy1]T.当给定的二次曲线是圆时，正交投影可由初等几何解析计算除了这种情况，正交投影点是方程中两个二次曲线的交点（九）、方程的相交计算(9)通过考虑由下式给出的一系列二次曲线得到：zT（ αM + βN） z = 0，（10）tpi = max{axp-a2，byp-b2}，（14）由此可以用牛顿Eberly方法的改进版本他们遵循类似的过程，以埃伯利一般曲线曲面上的正交投影比二次曲线曲面上的正交投影复杂得多，因为二次曲线曲面的形状是以一种更为复杂的方式定义的。因此，在大多数情况下，在这些曲线和曲面上的正交投影的解析计算可能是不可能的。相反，各种数值方法已被引入。根据算法的不同，这些方法可以分为两类前者是通过求解一个控制方程来计算正交投影，(1)以迭代的方式。这120K. Ko等/ Journal of Computational Design and Engineering，Vol.号12（2014）116~1270 1 j=1jj方法需要一个起始值，该值应该是正交投影点的良好近似值。接下来，它迭代地找到精确的解决方案。后者是通过将感兴趣的域细分为更小的域来找到方程的根假定包含根的细分区域被进一步细分。这种递归细分继续，直到细分区域的每个轴中的间隔的大小小于用户定义的公差，或者直到满足细分区域的平坦度3.2 基于迭代3.2.1 代数求根计算一点的正交投影等价于求解方程。（一）.可以使用代数或几何方法来获得该解，这些方法基本上以迭代方式搜索正交投影点Newton-Raphson方法是计算方程根的典型方法（一）.因为方程的导数是解析计算的，所以该方法可以在没有进一步几何信息的情况下找到方程的根。在计算最小距离的背景下，Mortenson [26]提出了表面距离测量的方程，可以使用牛顿迭代法求解Hartmann [27]使用曲线的标准形来计算点的曲线上考虑R2中的光滑隐曲线c（x），x<$Rn.如果存在连续可微函数h，|拉克什|=1，则方程h = 0称为c（x）的正规形。正规形的值等于测试点与其足点之间的适当定向的距离，并且h的梯度是足点处的单位法线足点对应于梯度为h的正交投影点，单位法向量。该算法是将曲线切线上的足点和切线段上的近似足点结合起来计算的法需要一个好的初始值来使用牛顿迭代法迭代地找到解这个要求在这个方案中是至关重要的，因为找到正确根的成功很大程度上取决于初始值。然而，提供这样的初始值不是一个容易的问题，因为由曲线或曲面的复杂形状引起的方程的复杂性[28]。3.2.2 几何迭代正交投影点可以通过迭代搜索满足正交条件的曲线或曲面上的点搜索是基于几何属性（如切向量或平面和曲率）执行的在每一点上，正交投影的控制方程如Eq.测试（1）以检查该点是否接近真正的正交投影点。Limaien和Trochu [8]提出了一种计算点在参数曲线或参数曲面上的正交投影的方法。他们使用了Matheron[29]提出的“双克里金法”概念利用对偶克里格法，可以自动构造一组点的光滑参数曲线方程[29]。克里金是一种基于高斯过程回归的插值方法。它被认为是使用数据点的线性组合给出局部估计值的估计量。插值的值由具有先验协方差的高斯过程建模，这导致最佳线性无偏预测。克里金法的另一种公式称为对偶克里金法，它使用协方差函数的线性组合提供估计值光滑的参数曲线和曲面可以使用来自一组点的双克里金法来表示[8]。例如，克里格曲线可以以参数形式定义，该参数形式包括用于曲线的平均形状的线性部分和对平均形状的校正部分，如下所述。拉波拉。在每个迭代步骤中，基于这些足点迭代地计算曲线上的精确足点本质上，这种方法类似于牛顿型迭代c（ t） = a + a t + ∑ NB| t -T |3（十五）图1.曲线的一阶近似和P在切线上的正交投影其中t是曲线c（t）从t = t0开始的弧长，a0和a1确定曲线的平均形状，与bj的求和调整平均形状。这里，平均形状表示为漂移，三次项表示为广义协方差。这些校正项允许曲线拟合给定的数据点。曲线情况的正交投影计算如下。 假设P是一个测试点，Qi表示曲线上的当前点，Ti是Qi处的切向量。 在正交投影点处，应满足（P-Q i）<$Ti = 0。 考虑到（P-Q i）<$Ti的符号，定位了具有两个连续点Qi和Qi+1的曲线的跨度，它包含P的正交投影。然后，通过两点之间的逆克里金法计算P的正交投影，如下所示曲线上的中间点是针对Pa获得K. Ko等/Journal of Computational Design and Engineering，Vol.号12（2014）116~127121拉美特斯岛这里，逆克里金法的中间点的数量取决于所需的精度。接下来，通过使用参数ti的标量值（P-Qi）<$Ti对参数ti进行插值来构造函数t = f（（P-Q）<$T）。然后通过计算满足t=f（0）的参数t来获得P的曲线上的正交投影的参数值对于曲面的情形，考虑曲面上的等参曲线，并迭代地应用在曲线上的正交投影Hoschek和Lasser [30]提出了一种用于参数化的迭代参数调整方法。他们没有明确地讨论正交点在曲线或曲面上的投影然而，他们的方法可以直接应用于寻找正交投影。将正交投影到曲线上的过程总结如下。考虑点P和参数曲线c（t）。然后，迭代地调整参数t，以使误差向量D=c（t）- P每次迭代的调整量dt由P在c（t）处的切线上的投影与点c（t）之间的距离获得随着迭代的继续，调整量dt收敛到零，导致P到c（t）上的正交投影的参数值t该方案可以推广到表面的情况。在这个过程中，曲线的一阶导数被用来近似曲线的局部形状，如图1所示。Hoschek和Lasser的方法也提出了两个不同的版本。使用泰勒展开式，直到展开式的一阶导数的项被用于参数平差的公式[31]。在[32]中，函数DD用于导出校正量也就是说，Ho- scheck和Lasser另一方面，Hu和Wallner [33]提出了一种基于曲线或曲面的二阶导数性质的正交点投影方法点投影到曲线上的核心思想是用曲率圆来近似曲线上一点的局部形状接下来，将给定的点投影到圆上以产生Q，如图2所示使用Q，t的参数值的量是es-图2.Hu和Wallner图3.曲面的Hu和Wallner估计以获得曲线上的正交投影点图2给出了这种方法的说明，其中C是曲率圆的中心该过程继续，直到调整量小于用户定义的公差。该方案直接应用于曲面上的正交点投影问题。图3给出了曲面情况的示意图，其中s是曲面。从s 0计算P方向上的法向曲率。然后，使用具有曲率中心C的法向曲率和法向曲率的值来定义圆。接下来，将点P投影到圆上以产生如图所示的近似投影点Q使用投影点Q，估计表面的参数u和v的更新量。重复此过程，直到获得所需的精度。与Newton-Raphson方法相比，该方法具有更好的稳定性，并且性能类似然而，该方法不能克服初始值的依赖性收敛到正确的解决方案。推广了Hu和Wallner的方法，由Liu等人提出。[34]第30段。与Hu和Wallner表面的局部形状近似于图4所示的环面贴片。环面的长圆和短圆是使用最大值和最小值图4.创建一个圆环面面片来近似s0附近曲面的局部形状122K. Ko等/ Journal of Computational Design and Engineering，Vol.号12（2014）116~127主曲率接下来，将测试点投影到面片上。利用曲面片上的投影点Q，估计出原曲面在环面片上的正交投影所对应的参数值对于该参数估计，表面被泰勒展开到二阶。然后，采用牛顿迭代法求出曲面参数随投影点的变化。该方法在速度和稳定性方面比Hu和Wallner的方法表现出更好的性能然而，由于它需要牛顿型迭代方法来寻找曲面上的参数值，因此不能保证该方法的稳定性。Ko [35]提出了一种将点正交投影到二维平面曲线上的方法。他近似的地方几何形状的曲线在一个点使用二次多项式的基础上泰勒展开的曲线在这一点。然后，使用多项式解析地计算近似的正交投影点，然后将其作为下一次迭代的输入。这个过程一直持续到以用户定义的精度获得正交投影点在他的方法中，提出了使用曲线的三阶导数来提高点投影的整体性能的可能性Song等人[36]使用双圆弧来近似感兴趣点附近的参数曲线的局部几何结构。计算到双圆弧近似上的投影重复该过程，直到满足终止条件在这里，双圆弧近似的概念是主要的兴趣。双圆弧由两个在公共端点连接的圆弧双圆弧被设计成在包含投影点的一定区间上近似曲线的局部形状，该投影点具有边界位置和一阶导数。几何迭代法的核心思想是用一个简单的解析表达式尽可能逼近曲线或曲面上一点附近的曲线或曲面的形状，并有效地计算近似形状上的正交投影点。根据近似投影点，计算参数的调整量以产生新的参数值。重复该过程，直到计算出的正交投影点收敛到精确的正交投影点。这意味着，如果形状可以尽可能精确地近似于真实形状，并且可以有效地获得近似形状上的正交点，则可以加速向真实正交投影点的收敛，并且可以降低对初始点到目前为止，已提出了一阶和二阶近似方法.此外，已经有人尝试使用三阶导数性质的局部形状近似。对于除直线段或平面以外的一般曲线或曲面，一阶近似方法比一阶近似方法具有更好的性能。当曲线被隐式定义时，Aigner和Juttler [20]提出了一种计算正交投影的鲁棒方法，称为圆收缩法。这种方法的核心思想如下。考虑一个点P和一条曲线c（x，y）= 0，它是隐式定义的。 当Q是正交投影点时，可以定义一个圆，其圆心和半径为P，|P-Q|分别表示。因为Q是距离P最近的点，所以圆只在Q处与曲线相交，这意味着曲线上没有其他点在圆内，并且隐函数值要么为零，要么与P具有相同的符号。如图5所示，曲线上的Qi被提供为迭代的初始点。然后，以P为圆心创建一个通过Q i的圆。 测试函数（P-Q i）θ c以检查Q i是否是正交投影点。 如果不是，则在圆上选择Q i的邻域中的点Q+。Q+可以是c（x，y）沿着从Q1开始的弧的第一个局部最大值。接下来，获得连接P和Q+的线段。计算直线和曲线之间的相交，表示为Qi+1。重复该过程，直到连续圆的半径的变化不超过一定的公差。几何迭代方法与几何造型和几何处理有着密切的关系因此，它们可以自然地嵌入到整个应用程序管道中。在不久的将来，将对解决这两个问题进行更多的研究。3.3 细分法3.3.1 曲线或曲面细分Piegl和Tiller [7]讨论了从一组随机点进行曲面拟合的参数化背景下的点投影他们使用一个基面，通过将给定点投影到基面上并获取投影点的参数值来估计给定点的参数值他们声称，标准的投影方法需要一个好的初始猜测，这是昂贵的，容易出错。他们提出了一种方法，以摆脱牛顿-拉夫逊法找到投影点的表面。基础曲面被细分为四边形，每个点都投影到最近的四边形上。然后，根据最近四边形的角点的参数值计算该点的参数值初始猜测的依赖性不再存在。然而，估计参数化的准确性取决于分解的质量分解应该以这样一种方式执行，即细分的四边形在大小上是均匀的，并且是基于基础曲面的几何形状和曲率创建Ma和Hewitt [37]提出了一种计算点投影和反演的方法。他们的概念有点类似于Piegl和Tiller的但不同之处在于细分策略，即将曲线或曲面细分为Bezier曲线或Bezier曲面。K. Ko等/Journal of Computational Design and Engineering，Vol.号12（2014）116~127123然后，控制多边形被用来找到正交投影的候选递归地将候选者细分为子曲线，直到子曲线的控制多边形变得这里，控制多边形是然后，通过将点投影在直线或平面上来获得近似投影点。为了提高计算精度，可采用牛顿-拉夫逊法. Ma和Hewitt表明，他们的方法在计算时间和稳定性方面优于Piegl和Tiller然而，曲线或曲面的细分仍然是昂贵的操作。马和Hewitt[38]第30段。他们提供了一个例子，马和休伊特此缺陷可能导致性能下降。Selimovic [39]提出了Ma和Hewitt方法的改进版本该方法与Ma和Hewitt的方法一样，对曲线或曲面进行递归细分然而，通过引入新的消除准则，大量的细分部分被排除在计算之外，可以提高计算性能。端点插值、凸壳性质和切锥被用来建立曲线曲面的判别准则。结果表明，与Ma和Hewitt的方法相比，该方法可大大减少投影检验的细分部分。性能的改善是更明显的曲面比曲线，这是在他们的论文中演示。Chen等人[40]提出了圆形裁剪算法，该算法比[37]和[39]中的算法更有效他们使用平面曲线的圆或3D曲线的球体作为消除区域。细分后，圆弧或球面外的曲线段被消除.重复该过程，直到满足终止条件。Oh等人[41]采用了[40]的圆/球裁剪方法的概念，但引入了一种更有效的技术，使用分离轴和k-DOP类型的边界方案，用于在迭代过程中剔除或裁剪曲线或曲面此外，通过对细分区域内投影点的唯一性检验，提高了计算效率Oh et al.[41]扩展到计算移动查询点到自由曲线上的投影[42]。stein形式，然后将其作为投影多面体（PP）算法[44]的输入，该算法通过细分缩小包含根的域来找到方程的解这种方法不限于点投影或点反演的问题这种方法是鲁棒的，因为只要投影点存在，它总是能找到它。然而，这种方法在实现方面是复杂的，并且是如此昂贵，以至于它可能不用于需要处理大量点的应用这些方法不使用任何初始值，并且在计算正交投影点时考虑了整个感兴趣区域，因此具有鲁棒性然而，它们在性能方面表现出缺点，因为它们需要细分曲线或曲面，这是一种昂贵的操作。由于计算时间长，一般不采用细分方法来计算精确的正交投影点相反，它们通常用于找到初始点，然后将其用作各种数值计算方法的输入，以获得精确的正交投影点，例如Newton-Raphson方法。因此，这些方法必须在考虑鲁棒性和性能之间的权衡后使用3.4 点的正交投影的延拓将点在曲面上的正交投影推广到曲线在曲面上的正交投影在这里，曲线以3D形式给出，并且其在表面上的投影也是3D形式的曲线，但是位于表面上因此，它可以被认为是一种在曲面上进行曲线设计的方法Pegna和Wolter [17]讨论了曲线在曲面上的正交投影问题他们导出了一组微分方程，用以跟踪曲面上的投影曲线对于这一发展，有几个假设是必要的。首先，表面应该是规则的和二阶连续的。接下来，曲线本身应该定位得足够靠近曲面，并且投影的曲线应该位于曲面的内部。这些假设有些严格。然而，曲线在曲面上的正交投影的概念考虑一个参数曲面s（u，v）（0≤u，v≤ 1）和一条以t为参数的空间曲线c（t）（0 ≤t ≤1）。则s上的投影曲线，记为m（t），由（t）=s（u（t），v（t））给出，（y（ t）- c（t））s= 0，3.3.2基于细分的求根当Eq.（1）被公式化为多项式方程，则方程的根可以使用细分来获得u（y（t）-c（t））吉夫（十六）基于方法。Zhou等人[43]提出了一种计算距离函数的驻点的这些点的子集对应于曲线或曲面上的正交投影点。方程在伯尔尼表示在取Eq的导数（16）关于t，以及利用链式法则，我们得到124K. Ko等/ Journal of Computational Design and Engineering，Vol.号12（2014）116~127F + ρM G + ρN杜德克斯[dt] Kdvdc开关点云的作用。Alexa和Adamson [50]分析了Levin的MLS方法[51]，用于通过点集计算曲面的法线。基于Levin方法的方法DT哪里德涅斯特河沿岸与估计的切线坐标系的距离不是实际的曲面法线。他们提供了一种改进的算法，用于使用修正的正态计算方案计算他们假设这些点隐含地定义了一个K = [E + ρLF + ρM]，ρ = |y（t）-c（t）|.（十八）E、F和G分别是s的第一基本形式系数，L、M和N分别是s的第二基本形式系数给定表面上初始点的u和v的参数值，系统Eq.数值求解方程（17），以跟踪对应于表面上的投影曲线的u和v这里，可以采用Runge-Kutta方法 。 初 始 点 通 过 计 算 曲 面 上 的 正 交 投 影 点 Ko [45]extended- ed Eq.（17）复盖曲面上的曲线和测地曲线的正交投影Song等人[46]提出了一种曲线在参数曲面上正交投影的二阶跟踪方法。利用曲面参数域中定义的二阶跟踪公式计算从起始点开始的连续跟踪点然后在参数域中基于Hausdorff测度将计算出的点近似到一个点集上，然后将其映射到曲面上以产生曲面上的正交投影曲线。虽然与一阶方法相比，相关理论比较复杂，但二阶方法被认为比一阶方法更Wang等人在[47]和[48]中提出了用法向投影法在自由曲面上构造G1和G2利用文献[17]中的法向投影条件，对法向投影曲线建立了不同形式的微分方程。Xu等人[49]提出了一种使用二阶近似方案的曲线在参数曲面上的正交投影方法。它们的主要区别在于曲面上的基于二阶泰勒近似，导出了一组微分方程，并通过误差调整进行了数值求解4. 点在点集3D扫描设备的普及正在增长，点云被广泛用于模型表示。因此，越来越多的形状和渲染过程被开发来处理用于各种操作（例如对象拟合）的点云。由于精确形状表示的不确定性，点到点云上的正交投影光滑曲面，并引入隐函数f如下。f（ x） = n（ x）T（x-a（ x））（19）近似曲面由满足f（x）= 0的点x这里，n（x）和a（x）是位置x处的法线和点的加权平均值。然后，x的正交投影可以估计如下[50]和[52]：1) 设=x2) 计算a（）、n（）和f（x）。3)x=x-gf（），g=（n（x）T（a（x）-x ））/（n（x）f（x））。4) 如果||（n（x）T（a（x）-x））||”回到第二步。重复调整点x，使得向量（x-x）变为方向为f（x）。利用点集的曲面隐式表示，可以估计精确的法线，由此可以计算精确的正交以更一般的方式讨论了点到点集的正交投影也就是说，给定点云Cn、任意点P和投影方向np，在方向np上的投影，称为有向投影，是P在Cn上在直线Q*（t）=P+tnp上的点，其中t是参数。这在直观上等价于找到Q*（t）和Cn之间的交集。 Azariadis和Sapartis [53]使用有向投影作为其主要组成部分，用于解决在由点云定义的表面上生成光滑曲线的问题。他们提出了一种迭代算法来寻找有向投影点。利用P和n定义的距离和轴，以启发式的方式提出了一个权重函数。利用权重，获得Q*作为以下最小化问题的根N-1最小化E（ Q）= aiQ-P2i=0时重复这些步骤，直到迭代收敛到投影点。这个问题可以推广到计算正交投影。Liu等人[54]讨论了一种处理投影方向未给出的情况的方法。他们提出了一种估计投影方向的方法，以及一种计算3D点到一组点的投影的迭代算法事实证明他们的方法K. Ko等/Journal of Computational Design and Engineering，Vol.号12（2014）116~127125固有地计算给定点到点云上的正交投影或法向杜刘[55][53]解决了该方法对于异常值缺乏鲁棒性的问题Zhang和Ge [56]针对有向投影问题提出了一种改进的MLS算法.与MLS投影方法的解总是沿着法线方向不同，他们提出的方法通过沿着投影方向搜索解来计算有向投影。此外，它们避免了评估加权值的点的不正确选择的问题。现有的MLS方法是根据与给定点的最短距离来选择相邻点，当曲面的几何形状复杂时，这种方法容易出错对于该标准，使用距投影向量的最短距离来改进收敛性。5. 结论正交投影是几何造型、计算机辅助设计和计算机图形学中的一个重要过程这个问题本身可以用数学上严格的方式来表述然而，该问题的实际解决方法仍然经历稳定性和性能问题，因为正交投影通常被给定为非线性方程的根，并且求解它们通常是不稳定且耗时的操作。因此，从配准，曲线和曲面拟合，和相似性评估，需要准确的正交投影的各种应用是不可避免地遭受鲁棒性和性能下降。在这篇综述中，对正交投影进行了数学讨论，并对计算正交投影的方法进行求解方法主要分为两类：基于迭代的方法和基于细分的方法。扩展到曲线投影和投影到一个点云进行了探索。针对每一类问题，提出了各种求解方法，并进行了比较.在数学上，正交投影要求在曲线或曲面上的投影点处存在切向量这意味着曲线或曲面应该是规则的，并且应该存在切向量或切平面。当曲面或曲线上存在不满足这样的条件的点时，正交投影不能在数学上定义，这是退化的情况。如果计算正交投影是主要目标，则需要小心处理退化情况以避免计算方法的崩溃情况。当一阶导数在曲线或曲面上的一点处消失时，曲线或曲面不再是正则的，并且在该点处不考虑切线或切平面这样的点称为奇点，在这里不能考虑微分几何，也不能得到唯一的法向量因此，正交投影的数学定义不再适用于这种情况。但这种为了正交投影计算的鲁棒性，退化情况应该被在计算上，退化情况可以通过在计算期间检查一阶导数值来检测如果导数变得小于用户定义的公差，则计算方法停止，分析奇异性的类型，并且调用处理这种类型的例程来处理这种情况。本文主要研究光滑曲线或光滑曲面的正则性。当存在奇点时，曲线或曲面被细分为区域，每个区域都变得规则。接下来，执行正交投影如果计算的最小距离是一个主要任务，这种退化的情况下，可以使用最小化例程处理正交投影的推荐选择可以根据曲线或曲面的表示方法进行如果曲线以隐式形式给出，则通过[20]可以使用，因为它在计算中的鲁棒性对于参数形式的曲线和曲面，需要考虑两个方面：鲁棒性和计算时间。为了保证正交投影计算的鲁棒性，应采用基于剖分的全局格式，然后采用牛顿型迭代以提高精度。在点集足够接近目标曲线或曲面的情况下，简单的牛顿型迭代法因其速度快且简单而成为最佳选择。然而，满足这样的条件是相当任意的。因此，可以使用[33]或[34]中的任一种方法在这里，[33]在实现方面比[34]简单，但在鲁棒性方面不如[34]指出目前还没有一种能同时满足高精度、鲁棒性和有效计算时间的正交投影问题的相反，许多文献都集中在解决方案的方法的鲁棒性，虽然预计会有一定的时间损失，这是一个合理的研究方向在正交投影计算中具有增加的鲁棒性的方法在实际应用中将比具有更少计算时间的不稳定方法更有益，因为计算时间可以通过优化的硬件和软件来处理由于求解过程的鲁棒性是正交投影计算中最关键的组成部分，也是对其它应用影响最大的部分，因此建议加强对提高正交投影计算鲁棒性的研究致谢该研究由基础科学研究计划通过韩国教育科学技术部资助的韩国国家研究基金会（NRF）提供支