基于点云的鞋楦模型三角网格曲面重构

(华侨大学机电及自动化学院，福建 厦门361021）

鞋楦作为鞋的基准，其设计制作过程是制鞋的关键工序之一。随着信息技术的发展，将数字化技术应用到鞋业生产中，能够有效缩短制鞋周期，加快产品更新换代的周期，提高企业的市场竞争力。笔者采用自主研制开发的三维楦型激光扫描仪获得鞋楦的三维表面点云数据，基于有符号距离场表面重构方法构造鞋楦曲面网格模型，实现鞋楦的数字化设计，为个性化鞋楦快速定制奠定基础。

1 鞋楦模型重构

常用的曲面重构方法主要有Delaunay三角剖分的方法、切片法、径向基函数法、水平集法和有向距离场隐函数法等。笔者采用基于有向距离场的三角网格曲面重构方法，其原理示意图如图1所示[1-2]。空间任意一点到待求曲面的距离与该点在曲面上最近点的法矢方向有关，如果该点和其对应点的法矢方向一致，则设该点到曲面的距离为正，否则为负，则正距离与负距离场的界面——0等值面即为所求曲面。

点云三角网格模型重构流程如图2所示。

图1 有向距离场示意图

1．1 点云数据获取

采用自主研制开发的鞋楦／脚型激光扫描测量系统进行楦面数据采集，获得鞋楦的点云数据。

1．2 顶点法矢计算

由于点云数据只包含点的坐标信息，没有任何的拓扑结构信息，所以每一点的微分几何信息如曲率、法矢等，只能由其最临近的一些点来决定。搜索点云中任一点的k个最临近点的方法一般有栅格法、八叉树法、近似最近邻库ANN方法以及k-d树方法等[3]。笔者采用k-d树方法来快速构建点云中每一点的k-邻近。

设点云中一点Pi的k-邻域为S= ｛Vj｜j=1，…，k｝，则该邻域的形心坐标（各点的平均坐标）为：

图2 点云三角网格模型重构流程

其协方差矩阵为：

对协方差矩阵C进行特征分解，计算其特征值以及与其对应的特征向量，则其最小的特征值对应的特征向量即为该点的法矢。这里需要注意的是，矩阵的特征分解对积累误差比较敏感，在计算过程中，最好采用双精度变量进行计算，否则有可能导致计算失败。

1．3 法矢一致化

在用上述方法得出各点的法矢后，并不能保证所有的法矢方向具有一致协调性，即保证所有的法矢朝向模型外侧或内侧，因而必须依序逐一修正各个取样点的法矢。然而，在2个不同但相当接近的曲面上，用文献 [1]所进行的法矢方向修正，却可能在2平面上跳跃修正，如此一来，即有可能在法矢方向修正完毕后，仍然有法矢方向不一致性的问题产生，如图3（a）所示。

图3 法矢一致化调整

为了解决该问题，参照文献 [4]中的方法，采用一种新的成本函数来协助修正法矢的方向，这种新的成本函数对于在2个不同平面上但有相似方向的取样点有较高的成本。该成本函数为：

式中，d为从点p指向点q的单位向量；np和nq分别为点p和点q的法矢；（·）表示2向量的内积。对于相同平面上的2点p和q，其计算出的成本较低，如图4（a）所示；对于不同平面上的2点p和q，其计算出的成本较高，如图4（b）所示。图3（a）数据采用新的成本函数进行法矢调整的结果如图3（b）所示。

图4 新的成本函数示意图

以点云模型中z坐标值最大的测点作为法矢调整的种子点，调整其切平面法矢的方向，使之与矢量(0，0，1）的点积大于0，这将使调整后的法矢指向曲面外侧。以成本函数作为权值遍历由点云模型构成的无向图的最小生成树，每遍历1个顶点，若父顶点ni与子顶点nj满足ni·nj＜0，则将nj反向。遍历完毕，则点云的法矢也调整完毕，保证其整体的一致性。

1．4 有向距离计算

将切平面作为待重建曲面M的局部线性逼近，可以构造空间一点p到M的有符号距离函数d（p）：

式中，xi为所有测点中与p最近的点；ni为相对应的切平面法矢。

为了能够实现带边界曲面的重构，对于密度为ρ，噪声为δ的点集X，式（4）可改写如下。

p点到最近切平面的投影为：

式中，L（z，X）表示z与测量点集X中最近点间的距离。

为了减少计算量，首先以点集X构造k-d树，在空间点p的一个指定半径的球体范围内搜索其在X中的最近点，如果得到了最近点，则按改写的式（4）计算其有符号距离；如果没有得到其在X内的对应最近点，则直接给该点的有符号距离值赋值undefine，而不用再按改写的式(4）计算。这样不但减少了有符号距离计算量，也有利于下一步的三角网格生成。

1．5 三角网格曲面生成

在计算出空间任意一点的有符号距离之后，就要根据有符号距离场的分布情况进行三角网格曲面重构，其中常采用的三角形生成方法为Marching Cubes算法。该算法的基本原理是基于一个假设，即沿着立方体的棱边，数据是连续线变化的，比如，如果等值面的值介于1条边的2个顶点值的中间，则等值面必与该条边相交于一点。根据该原理可以计算出与等值面相交的立方体。为确定体元中等值面的结构，需要首先给出一个阈值以便求出等值面，然后对立方体的8个顶点进行分类，以顶点位于等值面之内还是位于等值面之外为分类规则；最后再根据顶点分类的结果确定等值面的结构模式。其中分类顶点的规则是：①当顶点的数据值大于等值面的值，则设定该顶点位于等值面内部，记为 “0”；②当顶点的数据值小于等值面的值，则设定该顶点位于等值面外部，记为 “1”。由于每个顶点有2种状态，因此，8个顶点共有28=256种组合结果。由此可见，从立方体的256种状态中求出等值面还是非常烦琐的。在实践中，可以根据互补对称性和旋转对称性将这256种组合状态化简为15种。

除了生成用于组合成等直面的三角形，Marching Cubes算法还必须计算出用于3D显示的表面法向量，得到三角形的法向量，就可以利用相应的光照模型计算光照，最后生成具有真实感的3D图形。等值面上的每一点，在沿面的切线方向的梯度分量为零，这说明每一点的梯度矢量方向就代表了点的法向量。直接计算三角形的法向量的运算量很大，而且由于三角形的法向量在方向上有较大的随机性，在三角形之间的链接处也会出现不连续性，使三维显示图形不能很好的表现目标的结构。因此，目前比较常见的法向量计算方法是通过三角形各顶点的法向量，生成哥罗德(Gouraud）模型来绘制三角形，进而组合成等值面[2-4]。笔者采用中心差分的方法计算各立方体顶点处的梯度，然后通过棱边的2个顶点的梯度线性差值求出三角形3个顶点的梯度，即为顶点法向量[2]。

2 应用实例

通过VC6．0和OpenGL编程在微机平台上实现笔者提出的方法，在CPU为2．26GHz、内存为2．0GB的PC机上共用时9s。

图5所示为鞋楦模型重构结果，其中点云模型中共有63750个顶点(见图5（a）），重构后的三角网格模型中有50464个三角形(见图5（b））。

图5 鞋楦模型重构结果

点云三角网格曲面重构的主要参数有最临近点个数k、噪声影响系数、网格间距系数、是否考虑边界的影响以及是否进行法矢一致化处理等，如图6所示。最临近点个数k过大，难以重构尖锐特征，过小则易受噪声的影响，一般取8～15。噪声影响系数是以点云密度(点云顶点间的平均距离）为基准的比例系数，曲面中小于噪声的细节是不能重建的。网格间距系数是以点云密度为基准，定义网格格子间距的大小。

重构参数对重构结果的影响如图7所示。图7（b）中不考虑边界的影响，因而构造出的三角网格曲面明显比点云模型多出一部分；图7（c）和图7（d）都考虑边界的影响，但网格间距系数不一样，所得重构结果也不一样。

图6 点云模型重构参数面板

3 结 论

给出了一种基于点云数据重构鞋楦曲面模型的方法。利用改进的成本函数实现点云模型法矢的一致化，采用k-d树数据结构加速搜索过程并减少有符号距离场的计算量。算法实例显示，该方法是有效的，能够应用于鞋楦曲面逆向工程实践。

图7 重构参数对重构结果的影响

[1]Hoppe H，DeRo se T，Duchamp T，et al．Surface reconstruction from unorganized points [J]．Computer Graphics，1992，26（2）：71-78．

[2]周儒荣，张丽艳，苏旭，等．海量散乱点的曲面重建算法研究 [J]．软件学报，2001，12（2）：249-255．

[3]熊邦书，何明一，俞华璟．三维散乱数据的k个最近邻域快速搜索算法 [J]．计算机辅助设计与图形学学报，2004，16（7）：909-912．

[4]钟武洋．利用局部点特性进行有效率之表面重建 [D]．新竹：中原大学，2005．