摘要：鞋楦数字化模型是进行鞋楦个性化快速定制的基础，提出了一种基于点云模型进行鞋楦曲面三角网格模型快速重构的方法。采用k-d树方法快速搜寻点的k邻域，以特征值分解方法求取顶点的法矢，并对其进行一致化处理。在计算空间一点的有符号距离的基础上，采用Marching Cubes 算法生成三角网格模型，完成曲面重构过程。最后给出了一个鞋楦曲面重构的实例，并实验讨论了重构参数对重构结果的影响。
Last Model Triangular Mesh Surfaces Reconstruction Using Point Cloud Data
Key word: Shoe last; Surface reconstruction; Signed distance field; Point cloud
Abstract: Digital model conduce to shoe last rapid customization. A new method based on point cloud for triangular mesh model rapid reconstruction is designed. K-D tree method is used for searching the K neighborhood of point. The normal of vertex is calculated by eigenvector decompositions, and then is uniformed. Based on the calculating for Signed distance of one point in 3D space, Surface of triangular mesh model was generated by Marching Cubes algorithm. Finally, a example of show last surface reconstruction was given. The effect of reconstruction parameters to reconstruction result was studied by experiments.
Abstract: The digital model is the base for shoe last customization. Point cloud model shoe last rapid
Key word: Shoe last; Surface reconstruction; Signed distance field; Point cloud;
0 引言*
鞋楦作为鞋的基准，其设计制作过程是制鞋的关键工序之一。随着信息技术的发展，将数字化技术应用到鞋业生产中，能够有效缩短制鞋周期，加快产品更新换代的周期，提高企业的市场竞争力。本文采用自主研制开发的三维楦型激光扫描仪获得鞋楦的三维表面点云数据，基于有符号距离场表面重构方法构造鞋楦曲面网格模型，实现鞋楦的数字化设计，为个性化鞋楦快速定制奠定基础。
1 鞋楦模型重构
常用的曲面重构方法主要有： Delaunay三角剖分的方法、切片法（Slicing）、径向基函数方法（Radial Basis Function）、水平集方法（Level Set）和有向距离场隐函数方法等。本文采用基于有向距离场的三角网格曲面重构方法，该方法的原理示意图如图1所示[1][2]。空间任意一点到待求曲面的距离与该点在曲面上最近点的法矢方向有关，如果该点和其对应点的法矢方向一致，则设该点到曲面的距离为正，否则为负，则正距离与负距离场的界面——0等值面即为所求曲面。
图 1 有向距离场示意图
该方法的主要计算流程为：
图 2 点云三角网格模型重构流程
1.1 点云数据获取
本文采用我们自主研制开发的鞋楦/脚型激光扫描测量系统进行楦面数据采集，获得鞋楦的点云数据。获得的
1.2 顶点法矢计算
由于点云数据只包含点的坐标信息，没有任何的拓扑结构信息，所以每一点的微分几何信息，如曲率、法矢等，只能由其最临近的一些点来决定。搜索点云中任一点的K个最临近点的方法一般有栅格法、八叉树法、近似最近邻库ANN方法（Approximate Nearest Neighbor，ANN）以及k-d树方法等[3]。本文采用k-d树方法来快速构建点云中每一点的K-邻近。
设点云中一点Pi的K-邻域为S={Vj | j = 1,…,K}，则该邻域的形心坐标（各点的平均坐标）为
（1）
其协方差矩阵为
（2）
对协方差矩阵C进行特征分解，计算其特征值以及与其对应的特征向量，则其最小的特征值对应的特征向量即为该点的法矢。这里需要注意的是，矩阵的特征分解对积累误差比较敏感，在计算过程中，最好采用双精度变量进行计算，否则有可能导致计算失败。
1.3 法矢一致化
在用上述方法得出各点的法矢后，并不能保证所有的法矢方向具有一致协调性，即保证所有的法矢朝向模型外侧或内侧，因而，我们必须依序逐一修正各个取样点的法矢。然而，在两个不同但相当接近的曲面上，利用[1]所进行的法矢方向修正，却可能在两平面上跳跃修正，如此一来，即有可能在法矢方向修正完毕后，仍然有法矢方向不一致性的问题产生，如图3（a）所示。
（a）修正后仍有法向量不一致的情况
（b）采用新成本函数得到的调整结果
图3 法矢一致化调整
为了解决这个问题，我们参照文献[4]中的方法，采用一种新的成本函数，来协助修正法矢的方向，这种新的成本函数对于在两个不同平面上但有相似方向的取样点有较高的成本。该成本函数为
（3）
其中， 为从点p指向点q的单位向量， 和 分别为点p和点q的法矢，（?）表示两向量的内积。对于相同平面上的两点p和q，其计算出的成本较低，如图4（a）所示，而对于不同平面上的两点p和q，其计算出的成本较高，如图4（b）所示。
（a）相同平面上的两点 （b）不同平面上的两点
图 4 新的成本函数示意图
以点云模型中z坐标值最大的测点作为法矢调整的种子点，调整其切平面法矢的方向，使之与矢量(0, 0, 1) 的点积大于0，这将使调整后的法矢指向曲面外侧。以成本函数作为权值遍历由点云模型构成的无向图的最小生成树，每遍历一个顶点，若父顶点ni与子顶点nj满足ni?nj < 0, 则将nj反向。遍历完毕，则点云的法矢也调整完毕，保证其整体的一致性。
1.4 有向距离计算
将切平面作为待重建曲面M的局部线性逼近，可以构造空间一点p到M的有符号距离函数d(p)，
（4）
其中xi为所有测点中与p最近的点，ni为相对应的切平面法矢。
为了能够实现带边界曲面的重构，对于密度为ρ，噪声为δ的点集X，式（4）可改写为：
if (L(z, X) < (ρ+δ)) then
else
其中L (z , X ) 表示z与测量点集X中最近点间的距离。
为了减少计算量，首先以点集X构造k-d树，在空间点p的一个指定半径的球体范围内搜索其在X中的最近点，如果得到了最近点，则按上式计算其有符号距离；如果没有得到其在X内的对应最近点，则直接给该点的有符号距离值赋值undefine，而不用再按上式计算。这样不但减少了有符号距离计算量，也有利于下一步的三角网格生成。
1.5 三角网格曲面生成
在计算出空间任意一点的有符号距离之后，就要根据有符号距离场的分布情况进行三角网格曲面重构，其中常采用的三角形生成方法为Marching Cubes 算法。
Marching Cubes 算法的基本原理是基于一个假设，即沿着立方体的棱边，数据是连续线变化的，例如: 如果等值面的值介于一条边的两个顶点值的中间，则等值面必与该条边相交于一点。根据此原理可以计算出与等值面相交的立方体。为确定体元中等值面的结构，需要首先给出一个阈值以便求出等值面，然后对立方体的8 个顶点进行分类，以顶点位于等值面之内还是位于等值面之外为分类规则；最后再根据顶点分类的结果确定等值面的结构模式。其中分类顶点的规则是
(1) 当顶点的数据值大于等值面的值，则设定该顶点位于等值面内部，记为“0”；
(2) 当顶点的数据值小于等值面的值，则设定该顶点位于等值面外部，记为“1”。
由于每个顶点有两种状态，因此，8个顶点共有28= 256种组合结果。由此可见，从立方体的256 种状态中求出等值面还是非常烦琐的。在实践中，人们根据互补对称性和旋转对称性将这256种组合状态化简为15种。
除了生成用于组合成等直面的三角形，Marching Cubes算法还必须计算出用于3D显示的表面法向量，得到三角形的法向量，就可以利用相应的光照模型计算光照，最后生成具有真实感的3D图形。等值面上的每一点，在沿面的切线方向的梯度分量为零，这说明每一点的梯度矢量方向就代表了点的法向量。直接计算三角形的法向量的运算量很大，而且由于三角形的法向量在方向上有较大的随机性，在三角形之间的链接处也会出现不连续性，使三维显示图形不能很好的表现目标的结构。因此，目前比较常见的法向量计算方法是通过三角形各顶点的法向量，生成哥罗德(Gouraud) 模型来绘制三角形，进而组合成等值面。本文采用中心差分的方法计算各立方体顶点处的梯度，然后通过棱边的两个顶点的梯度线性差值求出三角形三个顶点的梯度，即为顶点法向量，计算公式为：
2 应用实例与讨论
本文所提方法已通过VC6.0和OpenGL编程在微机平台上实现，图5为鞋楦模型重构的一个例子。点云模型中共有63750个顶点，重构后的三角网格模型中有50464个三角形，在CPU为2.26 GHz，内存为2.0GB的PC机上共用时9s。
(a) 点云模型
(b) 三角网格模型
图5 鞋楦模型重构结果
点云三角网格曲面重构的主要参数有最临近点个数K、噪声影响系数、网格间距系数、是否考虑边界的影响以及是否进行法矢一致化处理等，如图6所示。最临近点个数K一般取8~15，过大，难以重构尖锐特征，过小则易受噪声的影响。噪声影响系数是以点云密度（点云顶点间的平均距离）为基准的比例系数，曲面中小于噪声的细节是不能重建的。网格间距系数是以点云密度为基准，定义网格格子间距的大小。
图6 点云模型重构参数面板
图7为鞋楦表面采集的点云模型的一部分在不同的重构参数下重构结果的对比图。图7（b）中不考虑边界的影响，因而构造出的三角网格曲面明显比点云模型多出一部分；图7（c）（d）都是考虑边界的影响，但网格间距系数不一样，所得重构结果也不一样。
(a)点云模型
(b)不考虑边界影响的重构结果
(c)考虑边界影响，步进网格间距系数为1
(d) 考虑边界影响，步进网格间距系数为0.9
图 7 重构参数对重构结果的影响
3 结论
本文给出了一种基于点云数据重构鞋楦曲面模型的方法。采用改进的成本函数实现点云模型法矢的一致化；采用k-d树数据结构加速搜索过程并减少有符号距离场的计算量。算法实例显示，本文算法是有效的，能够应用于鞋楦曲面逆向工程的实践。
参考文献
[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
|
