摘要
近年来随着激光和结构光等三维数据采样技术和硬件设备的日益完善，随
着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着
CAD＼CAM或者其它快速成型技术的需求，三角形网格生成与简化成为三维重
建这一研究领域的热点之一。
三角形网格生成与简化的基本思想是对从三维测量得到的离散数据或造
型软件的输出结果进行处理，形成规范和通用的数据格式，去除冗余信息而又
保证模型的准确度，以利于图形显示的实时性、数据存储的经济性和数据传输
的快速性。
本文在总结了国内外一些经典的由海量离散数据点进行曲面重建的算法和
一些三角形网格简化算法的基础上，结合我们使用现有的三维测量仪器的进行
采集所得到数据的特点，提出了一种新的曲面重建算法和简化算法。使用这些
算法计算速度快，得到的三角形网格的图象质量高，完全可以满足我们的要求。
具体的研究结果如下：
1．提出了一种基于动态圆的散乱数据点的三角网格生成算法。该算法适用范
围广，计算效率高，生成的曲面的效果好。它可以直接处理来源于光学测
量系统或者其他的一些三维测量系统的数据，而不用经过去除杂点的数据
预处理过程；输出三角形网格的解析度可以由用户通过设置一些参数来进
行控制；这个算法还可以处理一些来自于点云的点所带的除了(x，y，z)坐
标以外的一些信息，比如说颜色信息(RGB)等；此外我们还提供了几种可以
实现的纹理映射(texture mapping)的思路。
2．本文给出一种简化三角形网格表示的三维模型的算法，算法采用以曲面的
曲率的二阶导数为简化条件并以边折叠为基本简化方式，在简化的过程中，
三角形简化与否取决于该三角形所处的平面以及周围三角形平面的曲率变
化的大小，所以输出三角形的解析度可以随着物体表面的梯度的变化而变
化的大小，所以输出三角形的解析度可以随着物体表面的梯度的变化而变
化。在新顶点生成时，引入了二次误差的概念，新顶点的坐标就是当二次
误差取最小值时的坐标。这个简化算法可以用于简化各种曲面，如非封闭
曲面，简单封闭曲面，多连通封闭曲面。
3.使用OpenGL技术对处理前后的三维模型进行显示，可以直接在屏幕上观
察到三维模型经过处理后得到的结果，并且可以对图形进行放大、缩小、
平移、旋转等基本操作，完全可以满足我们对图形显示的要求。
4.输出格式很容易转化成现在计算机图形学软件所使用的.VRML文件格式，
从而使我们的数据可以直接输出到因特网或应用于其他的一些三维造型软
件，从而使我们数据可以在更广泛的领域得到应用。
With the recent development of 3D data collection technologies and hardware facilities (e.g. laser and structured light), the higher requirements of authenticity, real time and interaction of computer graphic visualization, the demands of CAD, CAM and other quick molding technologies, the technology of triangle mesh generation and simplification have become one of the hotspots in the field of 3D reconstruction. The basic thought of triangle mesh generation and simplification is to process disperse data points obtained by 3D measurement or the output results from molding software to generate data in a standard and common format, wipe off the redundant information while at the same time by keeping the accuracy of the model to guarantee the real-time graphic visualization, the efficient of data storage and quickness of data transmission
This thesis sums up some classical algorithms of surface reconstruction with vast disperse data and several simplification algorithms of triangle mesh. Based on these algorithms and the features of the data obtained by our 3D measurement instrument, a new surface construction and simplification algorithm is presented in this thesis. Using these algorithms, the programs are efficient and the obtained graphics of triangle mesh are of good quality, which meet our requirements quite well. The detailed results of the research are listed below:
1. Presents an algorithm of triangle mesh generation of disperse data points based on dynamic circles. This algorithm is efficient, and the obtained cured surface is of good quality. It processes these data that gathered from the optical measurement system or other 3D measuring apparatus directly without the
preprocessing of wiping off noise points. User can define the resolution of the exported triangle mesh through setting a few parameters. It still can process other information of the points of cloud except for the x, y, z coordinates, such as color information (RGB). Besides, several feasible ideas of texture mapping are presented in this paper.
2. Presents an algorithm of 3D model represented in simplified triangle mesh. This algorithm adopts the 2nd derivative of the curvature of the curved surface as the condition of simplification and the edge contraction as the basic simplification manner. The concept of quadric error is introduced in the generation of a new vertex.
3. The results of the numerical experiments are visualized using OpenGL. The real-time processing results of three dimensions can be viewed on the screen. And the model can be zoomed , panned and rotated.
4. It is easily to export three-dimensional geometry with a mapped texture into .VRML format. So we can directly export these data into Internet and use the data in other software, and extend the range of application.
引文
[1] 汪国兴，张明敏，潘志庚一种新的连续多分辨率模型自动生成算法，系统仿真学报，14(8)，2002．8
[2] 王国谨，曲面造型技术的现状和发展趋势，浙江大学CAD&CG国家重点实验室，浙江大学应用数学系
[3] 宋万忠 光学三维传感中多视点距离像配准与复杂曲面展平，博士论文，电子信息学院，四川大学
[4] 李际军，程耀东，柯映林．复合三角Bezier曲面的裁剪．计算机辅助设计与图形学学报，2000，12(1)：65～69．
[5] 董洪伟，周来水，周儒荣．一种曲面裁剪的快速新算法．工程图学学报，2000，(2)：46～51
[6] 王强，马利庄，鲍虎军．基于骨架的断层间复杂轮廓线的三角片曲面重构．计算机学报，2000，23(8)：842～846．
[7] 王进，彭群生．一个二次连续的平面网格细分算法及其应用．计算机学报，2000，23(9)：899～904
[8] David F.Rogers，石教英等译计算机图形学的算法基础，机械工业出版社。
[9] Hoppe,H. ,De Rose,T. ,Duchamp,T.,et al. Surface reconstruction from unorganized points. Computer Graphics, 1992,26(2):71～78
[10] 于青，王融清，鲍虎军等．散乱数据点的增量快速曲面重建算法．软件学报．2000,11(9)：1221-1227
[11] Amenta, M. Bern and M. Kamvysselis. A New Voronoi-Based Surface reconstruction Algorithm. In: Proceedings of SIGGRAPH'98. 1998, Jul., 415-421.
[12] William J.Schroder,Jonathan A.Zarge,et al. Lorensen. Decimation of triangle meshes [J] .Computer Graphics, 1992,26(2):65-70.
[13] Hugeues Hoppe. Progressive_meshes[A].InSIGGRAPH'96[C], 1996.99-108
[14] Michael Garland Paul S. Heckbert+Simplifying Surfaces with Color and Texture using Quadric Error Metrics InSIGGRAPH'97[C], 1997.209-216
[15] H. Hoppe, T. DeRose and T. Duchamp. Surface reconstruction from unorganized points.ln: Proceedings of SIGGRAPH'92. 1992, Jul., 71-78.
[16]苏显渝，李继陶．信息光学，科学出版社
[17]F. Chen, G.M. Brown, M. Song, Overview of three-dimensional shape measurement using optical methods, Optical Engineering, 39(1), 10-22(2000)
[18]Xianyu Su, Wenjing Chen, "Fourier transform profilometry: a review", Optics and Lasers engineering, 2001,35(5), P263-284.
[19]苏显渝，谭松新等，基于付里叶变换轮廓术方法的复杂物体三维面形测量，光学学报，1998，18(9)，1228—1233，
[20]杨虎，陈文静，苏显渝，抽样对傅里叶变换轮廓术的影响，光学学报，19(7)，1999
[21]苏礼昆，苏显渝，一基于调制度测量的三维轮廓术，光学学报，19(9)，1257-1262(1999)，
[22]苏显渝，周文胜，采用罗奇光栅离焦投影的位相测量剖面术，光电工程，20(4)，8(1993)．
[23]王静，薛为民，毋茂盛，从点集重构曲面网格方法综述
[24]Boissonnat J-D。Geometric structures for three-dimensional shape representation. ACM Transactions on Graphics, 1984,3(4):266-286
[25]Edelsbrunner H,Mucke E P. Three-Dimensional alpha shapes. ACM Transactions on Graphics, 1994,13(1):43-72
[26]J.F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Trans.on Graphics,Vol.1,No.3,pp.235-256,1982
[27]S. Muraki, Volumetric Shape Description of Range Data using:Blobbly Model,Computer G raphics,Vol.25,No.4,1991,pp.227-235
[28]Robert Sitnik, Matagorzata Kujawinska, From cloud-of-point coordinates to three-dimensional virtual environment: the data conversion system: Optical Engineering,2002, 41(2)416-427。
[29]张宗华，彭翔等，平面域任意散乱点自动三角化的研究，工程图学学报，2000，2
[30]实现3D离散点优化三角划分的三维算法：柯映林 周儒荣，计算机辅助设计与图形学学报，1994．10
[31]海量散乱点的曲面重建算法研究：周儒荣 张丽艳等，软件学报，2001．12
[32]海量测量数据简化技术研究 张丽艳 周儒荣等，计算机辅助设计与图形学学报，2001．11
[33]散乱数据点的增量快速曲面重建算法：王青 王融清等，软件学报，2000．11
[34]一个通用的快速三角化算法 李伟青 彭群生等，计算机辅助设计与图形学学报，2001，9
[35]反求工程中三角网格拓扑生成的算法研究 田小东 王晖等，机械设计与制造工程，2001．9
[36]多连通曲面离散点集的3D三角划分算法研究：肖双九 邱泽阳等，软件学报，2002．4
[37]提高网格逼近精度的一种新方法 黄雪梅 李成刚等，华中理工大学学报，1999，4
[38]一种受约束的散乱点三角划分方法 李江雄，机械科学与技术，2000，3
[39]周焰，李德华，三维物体的表面三角划分快速算法，中国图像图形学报，2000，9
[40]苏海，汪林样，反求工程中几种自由曲面重构方法的分析，昆明理工大 学学报，2001，8
[41]E.Bittar, N.Tsingos,M.-P. Gascuel,Automatic Reconstruction of Unstructured 3D data:Combing a Medial Axis and Implicit Surfaces ,Computer Graphics forum ,Vol. 14, No.3,1995
[42]DeHamer Jr M, Zyda M J.Simplification of objects rendered by polygonal approximations. Computers Graphics, 1991, 25(2)
[43]Schroeder W J, Zarge J A et al. Decimation of triangle meshes. Computer Graphics, 1992,26(2)
[44]Turk G. Re-tiling polygonal surface. Computer Graphics, 1992, 26(2): 55—64
[45]Rossignac J,Borrel P. Multiresolution 3D approximation for rendering complex scenes. In: Falcidieno B, Kunii Teds. Geometric Modeling in Computer Graphics. New York: Springer Verlag, 1993
[46]Hoppe H, DeRose T et al.Mesh optimization. Computer Graphics, 1993, 27(1)
[47]Hamann, B. A data reduction scheme for triangulated surfaces. Computer Graphics, 1994,11(3)
[48]Eck M, DeRose Tet al. Multiresolution analysis ofarbirtary meshes. 1995, 29(2)
[49]Islet V, kau R W H, Green Mark.Real-time multi-resolution modeling for complex virtual enviromnents. In: Proc of VRST'96. HongKong, 1996.
[50]Cohen J, Varshney A, Manocha D et al.Simplification envelopes.1996, 30(2)
[51]潘志庚，马小虎，石教英．虚拟环境中多细节层次模型自动生成算法．软件学报，1996，7(9)
[52]朱万忠，苏显渝．激光三维扫描仪距离像的平滑和建模．光电子激光．2001，12(12)
[53]宋万忠，苏显渝．不规则三角形网格曲面的展平．四川大学学报(工学版)．
[54]曾芬芳，周琴，姚烃，基于边折叠的网格简化算法及其应用，计算机应用，2002．1
[55]李现民，李桂清，基于子分规则的边折叠简化方法，计算机辅助设计与图形学学报，2002．1
[56]吴亚东，刘玉树，基于二次误差度量的网格简化算法，北京理工大学学报2000．10
[57]王军安，魏生民，距离加权的二次误差测度网格简化算法，计算机辅助设计与图形学学报，2001．2
[58]马小虎，一种新的基于二次误差的三角形网格简化方法，计算机应用，2001．12
[59]周昆，潘志庚，石教英，基于三角形折叠的网格简化算法，计算机学报，1998．6
[60]张丽艳，周儒荣，带属性的三角网格模型简化算法研究，计算机辅助设计与图形学学报，2002．3
[61]成基华，范玉青，基于体积准则的网格模型简化方法，北京航天航空大学学报，2000．8
[62]Markosian L,Cohen J,Crulli T,et al.Skin:a constructive approach to modeling flee-form shapes[A].Rockwood A.Proceedings of SIGGRAPH 99,Computer Graphics Proceedings,Annual Conference Series[C].1999.
[63]王火亮等，OpenGL参考手册，
[64]刘长松，程连冀译，3D图形编程指南，青松出版社。
[65]潇湘工作室译，OpenGL超级宝典，人民邮电出版社。
[66]Foley,van Dam,Computer,Graphics:Principles and Practice Addison-Wesly Publishing Company INC.。