一种大规模散乱数据自适应压缩与 曲面重建方法

王晓明， 刘吉晓

（山东交通学院数理系，山东 济南 250023）

针对大规模散乱数据的曲面重建是反向工程，计算机辅助设计，计算机图形学等领域的关键问题。目前以NURBS 为主的参数曲面和三角网格曲面是最常用的两种方法。三角网格曲面在实际中有广泛的应用，但由于实际中所测得的数据往往规模大，密度高，直接对其进行三角网格重建一般是困难的，而且也是不必要的。文献[2]给出一种基于曲率抽样网格的NURBS 曲面重建算法。该算法能将数据点云压缩成一个由适合数量的点连成的四边形网格，进而由网格直接进行NURBS 拟合。那么，能否利用上述算法设计一种三角网格生成算法。本文正是基于此，给出了一种自适应数据压缩和三角网格重建算法。

1 初始插值曲面的构造

虽然径向基插值曲面质量很好，但其也有一个弱点。当插值点数量增加时，运算时间也随之急剧增加。故对于大规模的数据点集，采用文献[5]中的分片插值策略。将曲面定义域F 剖分为若干小区域，每个小区域上的曲面由该区域中所有点以及相邻区域中的若干点插值而成。如图1 所示，小区域A上的曲面片由D中落在深色小矩形内的点插值而成。该方法虽然不能保证曲面整体的连续性，但由于曲面良好的光顺性和光滑性，使其在分片交界处也不会太大差异。

图1 区域剖分以及局部插值示意

2 基于曲率和距离的抽样三角网格

由于直接对大规模高密度散乱数据三角化是非常耗时而且也是不必要的，故一般须先对散乱数据进行压缩，然后再进行重建。本文给出一种基于曲率和距离的三角网格抽样方法。将数据压缩和曲面重建同时进行。

2.1 网格抽样原理

现考察图2 所示的质点系，若沿x 轴分布的质点1m 和 3m 分别位于1x 和3x 处，则质点系的质心2x 满足

图2 质点系

由此给出如下的网格抽样原理。

（1） 情形一：考虑曲率。

若定义r ( x, y)为反映曲面 f ( x, y )曲率的形状函数 (r ( x, y)＞0)，将其类比于式（3）中的质量，可得

显然在形状函数r ( x, y )较大的地方，所需的抽样点较多。这里r ( x, y)可以采用文献[1-2]中的定义

它可以通过如下迭代求解

（2） 情形二：考虑距离

（3） 情形三：综合考虑曲率与距离

由于要生成三角网格，如果只考虑曲率，将会出现大量的狭长三角片，导致三角网格曲面质量不高，如图4(a)。如果仅考虑距离，则没有有效利用固定数量的点充分刻画曲面细节，如图4(b)。所以这里考虑将二者加权平均，令式(4)～式(8)中

图3 曲面10sin sin 局部

图4 对图3 曲面分别用3 种方法抽样的结果

2.2 三角网格抽样步骤

下面结合一个实例给出本文算法。对所给散乱数据点（图5(a)），首先利用第二节中所介绍的算法。得到一张插值曲面。然后在曲面上设计一张初始三角网格曲面。该初始网格约束在曲面定义域F 内。该网格可以随机定义，如文献[1-2]中的四边形网格均为随机定义。但考虑初始网格的好坏会直接影响到后面的迭代次数，故在这里 人为指定。首先将曲面定义域F 沿 yx, 方向分别等分为 m1,m2份，使 m1m2=m。这样得到m 个 等分点。同时按照点的分布建立起点与点之间的拓扑关系，如图5(b)所示。然后将这种拓扑关系对应到曲面上，就得到了初始的三角网格曲面图5(c)。可以看出，由于点在定义域上均匀分布，使得初始三角网格不能很好地刻画曲面的细节特征，如嘴巴，鼻子眼睛等部位。利用式(7)～式(9)进行迭代计算。在迭代过程中位于边界曲面上的点只能在相应的边界上滑动，而4 个角点位置保持不动。最终可得如图5(e)的抽样网格。图5(d)是其在xoy 平面的投影。可以看到，在曲面细节处聚集了较多的点，故网格能很好刻画曲面细节特征。

由于定义域的边界一般不是数据点集的边界，最后还需寻找真实边界。将网格和数据点集均投影到xoy 平面（也就是只利用每个点的前两个坐标）。分别称其投影为投影网格和投影点集。从投影网格四边向内，逐个删除三角网格中的三角片，直到遇到其投影网格中包含投影点集中点的三角片。这样就可以得到一张基本反映数据点集形状的三角网格。更进一步还可以通过用离每个网格点最近的原始数据点代换该网格点得到实际的三角网格曲面，如图5(f)所示。

3 总 结

本文给出一种针对大规模散乱数据的自适应压缩术和曲面重建算法。算法简单高效，另外，由于生成的三角网格中内点的度均为六，这对进一步生成高阶光滑的细分曲面是十分有利的。

[1] Li S Z. Adaptive sampling and mesh generation [J]. Computer-Aided Design, 1995, 27(3)： 235-240.

[2] 来新民, 等. 基于NURBS 的散乱数据点自由曲面重构[J]. 计算机辅助设计与图形学学报, 1999, 11(5)： 433-436.

[3] 史利民, 王仁宏, 几种基于散乱数据拟合的局部插值方法[J]. 数学研究与评论, 2006, 26(2)： 283-291.

[4] Richard Franke. Scattered data interpolation tests of some methods [J]. Mathematics of Computation, 1982, 38(157)： 181-200.

[5] Bradley C, Vickers G W. Free-form surface reconstruction for machine vision rapid prototyping [J]. Optical Engineering, 1993, 32(9)： 2191-2199.

图5 将本文方法用到人脸数据的结果