设计曲面上测量数据点最近点的计算研究

佘抒萌

摘 要： 在曲面匹配过程中，需要大量计算测量点到设计曲面的最近点及其距离，这一过程需要大量时间。而求解测量点到设计曲面距离的快速算法是解决曲面匹配问题的关键所在。如果采用测量数据点沿曲面法向投影到设计曲面，通过求解与曲面的交点得到最近点解，由于需要计算曲面上各位置处的法向，这样计算量较大。为简化算法，本文提出了一种近似的设计曲面上测量数据点最近点的计算方法。

关键词： 曲面匹配 测量点 设计曲面 距离 快速算法

引言

以汽车覆盖件模具型面为例，由于汽车覆盖件模具型面设计大多采用自由曲面，但对于某一汽车覆盖件模具曲面，其曲面形状往往不是由单一的曲面组成的，而是由多个曲面（其中含规则曲面和不规则曲面）经过拉伸、裁减等处理拼合而成的。因此本文将设计曲面离散成小三角面片接近曲面形状。计算测量点到设计曲面的最近点时，对于复杂曲面来说，通常所用的方法是Newton法和快速迭代算法[1]，[2]，但是这些迭代算法的成功在很大程度上取决于给定的初始点，初值选取不当，会导致计算发散，同时由于其计算耗时，不是理想的计算方法。

1.快速算法理论

为简化计算，本文采用一种近似的方法：首先将设计曲面离散成较高密度的三角网格面片，将毛坯曲面测量数据点沿设计曲面三角面片所在法向投影到三角面片上寻求测量点到曲面的近似最近点，以测量数据点到设计曲面微小三角片的距离，（该测量数据点的投影点必须在小三角面片内或其边界上）代替该点到设计曲面的距离以实现匹配点对的搜寻。如图1所示为曲面测量数据点沿设计曲面离散三角网格面片法向投影的示意图。

要缩短计算测量点到设计曲面三角面片的最近距离的时间，关键在于如何搜索测量点在设计曲面上投影点的最邻近三角面片，以及减少该测量点在设计曲面上投影点的最邻近三角面片的候选数量。因为一旦确定了测量点在设计曲面上投影点的最邻近三角面网格顶点，则距离的计算就变成了一个相对简单的问题。目前，对这类问题的求解主要有两类算法：第一类是基于Gilbert算法[3]的多面体分解算法，Gilbert算法给出了计算复杂度为O（n）的求点到任意凸体最近距离的方法，因此这类算法的共同点就是首先通过各种方法将任意非凸面多面体分解为一系列凸体，然后再利用Gilbert算法求解。但这种方法不能保证正确处理任意复杂的情况，其应用受到一定的限制；另一类是利用八叉树剖分技术[4]搜索最近三角面片，该方法在利用八叉树剖分物体模型后，在测量点周围的临近三角面片数目可能会很多，需要计算从测量点到每一个临近三角面片的距离，这样将使效率有所下降，因此要与其他方法相结合，减少测量点的临近三角面片数目。

2.曲面上测量数据点最近点计算步骤

本文在计算测量点到曲面投影点的最近点的距离采用了三个步骤：首先搜索测量点到设计曲面投影点邻近的三角网格顶点；然后是计算测量点到设计曲面三角形网格顶点的距离或三角形所在平面的距离并判断测量点在三角形所在平面的投影点是否在三角形内；最后比较二者的距离值，距离较小者即为所求。

步骤一：距离待匹配测量点邻近的（设计曲面上）候选匹配点集的确定。

如果求设计曲面上所有离散数据点与测量点的距离，然后确定设计曲面上离测量点的最近点，这样会导致计算量太大。为此，以测量点为圆心，以定长R为半径作一个球，在球面内包含的点求与测量点的最近网格点。定长R可以根据实际情况确定，一般可以取离散三角形的最大边长，如不合适，可以取离散三角形边长的两倍及数倍等。

步骤二：计算测量点到三角形所在平面的距离。

步骤三：对同一测量点，比较该测量点到最近网格顶点的距离与到三角面片的距离的大小，距离小者即为所求。

3.结语

曲面匹配是数字化加工与检测的基础，在自由曲面产品的加工制造和检测中有着非常重要的应用（如定位安装等）。本文研究了离散三角网格曲面的精确配准算法，计算中将“点一点”对齐法和“点一面”对齐法结合使用进行精匹配，对同一待匹配点，“点一点"对齐法和“点一面”对齐法求出的配对点中距离较小者即为所求。在搜寻待匹配测量点的最近点时提出了直接以待匹配测量点为中心的动态球搜索算法，可在设计曲面离散数据点中快速搜寻到距离测量点的最近点，使算法效率显著提高。

参考文献：

[1]Peng Q S.An algorithm for dingding the intersection lines between two B—spline surfaces.Computer-aided design，1984，16（4）：191-196.

[2]Bamhill R E，Farin G，Jordon Metal.Surface/surface intersection.Computer aided geometric design，1987，4（2）：277-289.

[3]Gilbert B G，Johnson D W，Keerthi S S.A Fast Procedure for Computing the Distance Between Complex Objects in Three—dimensional Space.IEEE Journal of Robotics and Automation，1988，4（2）：193-203.

[4]Zachmann G.Rapid collision detection by dynamically aligned DOP-trees.In：IEEE Proceedings Virtual Reality Annual International Symposium，Atlanta，Georgia，1998：90-97.