摘要
基于点的点云处理技术是随着数据测量技术的进步而迅速发展起来的一门新兴技
术。该项技术以点作为曲面绘制和造型的基本元素,在提高模型绘制与重建的速度、加
强处理超大规模点云的能力和简化计算量等方面体现出独特的优势,目前已成为反求工
程的一个研究热点。本文针对该项技术中的若干关键问题,结合国家十五重点科技攻关
项目“产品设计 CAD”(项目编号:2001BA201A02)进行了深入研究。
点集简化是点云处理中首要的预处理环节。为尽量避免损失被测物体的工程信息,
提出了一种基于模糊聚类的简化算法。通过引入几何相似性隶属度来表征被测物体形状
的自然变化,使简化点集倾向于聚集在曲面的陡峭区域,降低简化可能导致的形状损失;
同时以强制约束相似性隶属度反映设计者的工程和设计要求,能有效抑制工程信息和设
计信息的缺失。
特征线提取是点云处理中另一项重要的预处理工作。为保证特征线提取的稳定性及
精度要求,提出了一种基于数字图像薄化的多尺度特征线提取算法。利用局部熵和重复
度描述采样点在不同尺度下属于某个特征的可能性大小,保证算法的稳定性;通过将提
取的特征点云映射为数字图像和进行薄化处理,获取光滑的特征线,能在一定程度上处
理密度分布不均的点云,并保证特征线的质量。
曲面重建是点云处理的核心。为加快曲面重建的前处理速度,避免因采样点的少量
丢失而导致重建表面出现缝隙,探讨了一种基于曲面单元分解的重建算法。借鉴推进波
前法,基于子域环的构造和中心环的推衍,使所有点的法向指向被测物体的外侧,可缩
短法矢检验的时间;在各采样点处建立相互交迭的曲面单元,以近似包围在点云内部的
空间,可得到质量良好的重建表面。
曲面编辑是点云处理不可缺少的研究内容。为获取灵活的曲面编辑能力,设计了一
种基于超二次曲面的约束变形算法。建立基于超二次曲面的一般约束变形模型,使物体
在多种类型的约束下按指定的曲线位移产生多样化的变形;采用局部熵加权的方式,使
采样点能自动估计变形的程度,并在采样不足的区域插补适当数目的点,保证点云在变
形前后的采样率基本一致。
在上述理论研究成果的基础上,研制开发了基于点的三维散乱数据处理原型系统,
并已作为一个模块嵌入三维CAD系统-Intesolid中。
Advances in 3D scanning technologies have promoted the emergence and rapid
development of point-based techniques. Point-based techniques, by which points are used as
surface modeling and rendering primitives, has become an important research field of reverse
engineering. The particular dominance of point-based techniques includes the efficiency at
reconstructing and rendering very complex objects and environments, capability of dealing
with dense scattered point cloud, and simplicity of rendering algorithms. Based on the
overview of point-based techniques, several key issues including data reduction, feature line
extraction, surface modeling and editing are studied in this dissertation, which is sponsored by
the National Key Research Project of the 10th five-year-plan of China (Grant No.
2001BA201A02).
Data reduction is the first preprocessing step of point-based data treatment. To avoid loss
of engineering information hidden in the measured object, a data reduction algorithm on the
basis of fuzzy clustering analysis is proposed. By introducing geometric similarity
membership, surface variation can be naturally represented, forcing samples to gather in
regions where surface varies drastically. And imperative constraint similarity membership is
introduced to reflect engineering demand of designers, which is in favor of retaining
engineering detail features.
Feature line extraction from a point cloud is another necessary preprocessing step for
surface reconstruction. To satisfy the demand for stability and accuracy of feature line
extraction, a multi-scale feature line extraction algorithm based on digital image thinning is
presented. Local entropy and repeatability rate are introduced to classify points according to
the likelihood that they belong to some feature at different size of local window, which
achieves robust and stable feature point detection for noisy surfaces. By mapping the
extracted feature point cloud into 2D digital images and thinning the images, smooth feature
lines are recovered. Scanty data can be dealt with and the top-quality feature lines can be
recovered.
Surface reconstruction is the key problem of point-based data treatment. To save time on
surface reconstruction and avoid gaps of the reconstructed surface when parts of the data get
lost during transmission, a new surface reconstruction algorithm by use of decomposition of
II
surface elements is discussed. Similar to the theory of Advancing Front Method, the
consistent tangent plane estimation of each sample is performed by constructing local loops
and advancing the center loop. The volume enclosed by the given point cloud is approximated
with the set of overlapping surface elements built at each sample point.
Surface editing is indispensable in point-based data treatment. To achieve a flexible
capability for surface editing, a superquadric-based general constrained deformation
algorithm is designed. By building a superquadric-based general constrained deformation
model, surface can be deformed according to user-specified curvilinear displacement under
constraints, which can consist of points, lines, surfaces and volumes. During surface editing,
new samples are inserted to the original point cloud and located in proper positions by using
weighted local entropy method to preserve the overall sampling density.
On the basis of the above theoretic achievement, a point-based data treating system from
3D unorganized data points is developed and embedded in 3D CAD system - Intesolid.
引文
[1] Várady T., Martin R. R. and Cox J. Reverse engineering of geometric models – an
introduction. Computer-Aided Design, 1997, 29(4): 255~268
[2] Motavalli S. Review of reverse engineering approaches. The 23th International
Conference on Computers and Industrial Engineering, 1998, 35(1&2): 25~28
[3] 刘之生. 反求工程技术. 北京:机械工业出版社. 1996
[4] Aronson R. B. Forward thinkers take to reverse engineering. Manufacturing Engineering.
Nov., 1996, 34~44
[5] D. P. Luebke. A developer’s survey of polygonal simplification algorithms. IEEE
Computer Graphics & Applications, 2001, 24~35
[6] Cignoni P., Montani C. and Scopigno R. A comparison of mesh simplification algorithms.
Computers & Graphics, 1998, 22(1): 37~54
[7] Erikson C. Polygonal simplification: an overview. Department of computer science. UNC
Chapel Hill Computer Science Technical Report TR96-016, 1996
[8] Auck and Yuen M. M. F. Feature-based reverse engineering of mannequin for garment
design. Computer-Aided Design, 1999, 31: 751~759
[9] Dey T. K. and Giesen J. Detecting undersampling in surface reconstruction. Proceedings
of the 17th ACM Symposium Computational Geometry, June, 2001. 257~263
[10]Hubeli A. and Gross M. Multi-resolution feature extraction from unstructured meshes.
IEEE Visusualization’ 01, 2001, 19~27
[11]Hoppe H., DeRose T., Duchamp T. et al. Piecewise smooth surface reconstruction.
SIGGRAPH’94, 1994, 28(4): 295~302
[12]Eck M. and Hoppe H. Automatic reconstruction of B-spline surfaces of arbitrary
topological type. SIGGRAPH’96, 1996, 30(4): 325~334
[13]唐泽圣. 三维数据场可视化. 北京:清华大学出版社. 1999, 130~148
[14]Hoppe H., Derose T., Duchamp T. et al. Surface reconstruction from unorganized points.
SIGGRAPH’92, 1992, 26(4): 71~78
[15]Edelsbrunner H. and Muche E. P. Three-dimensional alpha shapes. ACM Transactions on
Graphics. 1994, 13(1): 43~72
[16]Teichmann M. and Capps M. Surface reconstruction with anisotropic dense-scaled alpha
shapes. IEEE Visualization’98, proceedings, 1998.67~72
116
[17]Bernardini F., Mittleman J., Rushmeier H. et al. The ball-pivoting algorithm for surface
reconstruction. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4):
349~359
[18]Turk G. Re-tiling polygonal surfaces. SIGGRAPH’92, 1992, 26(4): 55~64
[19]James D. L. and Pai D. K. ARTDEFO: accurate real time deformable objects.
SIGGRAPH’99, 1999, 33(4): 3~12
[20]孙玉文,王晓明,刘健. 密集散乱数据的三角形网格曲面逼近方法. 计算机辅助设计
与图形学学报. 2000, 12(4): 281~285
[21]施云惠,王子才,赵明. 基于W空间上的神经网络自由曲面重构算法. 计算机辅助设
计与图形学学报. 2000, 12(5): 344~348
[22]Barhak J. and Fischer A. Parameterization and Reconstruction from 3D Scattered Points
Based on Neural Network and PDE Techniques. IEEE Transactions on Visualization and
SIGGRAPH’01, 2001, 7(1): 1~16
[23]Cong G. and Parvin B. An algebraic solution to surface recovery from cross-sectional
contours. Graphical Models and Image Process, 1999, 61: 222~243
[24]Lai Y. and Ueng W. D. Reconstruction of surfaces of revolution from measured points.
Computers in Industry, 2001, 41: 147~161
[25]周儒荣, 张丽艳, 苏旭 等. 海量散乱点的曲面重建算法研究. 软件学报, 2001, 12(2):
249~255
[26]M. Stamminger and G. Drettakis. Interactive sampling and rendering for complex and
procedural geometry. In Proceedings of the 12th Eurographics Workshop on Rendering,
2001, 76~89
[27]A. R. Smith. Smooth Operator. The Economist, Science and Technology Section, 1999,
73~74
[28]种永民, 杨海成. 测量造型技术中的数据处理方法. 西北工业大学学报, 1997, 15(4):
624~628
[29]Gu P. and Yan X. Neural network approach to reconstruction of freeform surfaces for
reverse engineering. Computer-Aided Design. 1995, 27(1): 59~64
[30]孙玉文. 面向快速原型制造的反求工程关键技术研究: [博士学位论文]. 大连: 大连
理工大学图书馆, 2000年
[31]瞿建武, 李江雄, 柯映林. 基于实物的复杂曲面零件反求工程中未知区域测量数据
补充及曲面重构技术. 机械工程学报, 2002, 38(9): 110~117
117
[32]张丽艳, 周儒荣, 蔡炜斌 等. 海量测量数据的简化技术研究. 计算机辅助设计与图
形学学报, 2001, 13(7): 1019~1023
[33]谭昌柏. 结构件反求建模中的数据处理技术: [硕士学位论文]. 南京: 南京航空航天
大学, 2003年
[34]Pauly M., Gross M. and Kobbelt L. Efficient simplification of point-sampled geometry.
IEEE Visualization’02, 2002, 41~49
[35]Pauly M. and Gross M. Spectral processing of point sampled geometry. SIGGRAPH’01,
2001. 35(4): 379~386
[36]Linsen L. Point cloud representation. Technical Report, Faculty of Computer Science,
University of Karlsruhe, 2001
[37]M. Pauly, L. Kobbelt and M. Gross. Multiresolution modeling of point-sampled geometry.
ETH Zurich Technical Report, 2002
[38]Huang M. C. and Tai C. C. The preprocessing of data points for curve fitting in reverse
engineering. International Journal of Advanced Manufacturing Technology, 2000, 16(9):
635~342
[39]A. C. and Chan C. F. Point data processing and error analysis in reverse engineering.
International Journal of Advanced Manufacturing Technology, 1998, 14(11): 824~834
[40]Pauly M., Keiser R. and Gross M. Multi-scale feature extraction on point-sampled
surfaces. Eurographics’03, 2003, 22(3): 32~41
[41]Choi S. N. and Kolluri R. The power crust. ACM Symposium on solid Modeling and
Applications, 2001, 25~37
[42]Gumhold S., Wang X. and McLeod R. Feature extraction from point clouds. Proc. 10th
Int. Meshing Roundatable, 2001, 51~64
[43]李培华, 张田文. 主动轮廓线模型(蛇模型)综述. 软件学报, 2000, 11(6): 751~757
[44]S?derkvist I. Introductory overview of surface reconstruction methods. Research report,
department of Mathematics, Lule? University, Sweden, 1999.
[45]A. Kalaiah and A. Varshney. Differential point rendering. In Proceedings of the 12th
Eurographics Workshop on Rendering, August 2001, 61~74
[46]A. Kalaiah and A. Varshney. Modeling and rendering of points with local geometry. IEEE
Transactions on Visualization and Computer Graphics, 2002, 30~42
[47]Alexa M., Behr J., Cohen O. D. et al. Point set surfaces. IEEE Visualization’01, 2001.
21~28
118
[48]S. Fleishman, Daniel C. O., M. Alexa et al. Progressive point set surfaces. ACM
Transactions on Graphics, 2002, 20~36
[49]M. Zwicker, M. Pauly, O. Knoll et al. Pointshop 3D: an interactive system for point-based
surface editing. SIGGRAPH’02, 36(4): 322~329
[50]M. Levoy and T. Whitted. The use of points as display primitives. Technical Report TR
85-022, The University of North Carolina at Chapel Hill, Department of Computer
Science, 1985
[51]R. L. Cook, L. Carpenter, and E. Catmull. The Reyes image rendering architecture.
SIGGRAPH’87, 1987, 21(4): 95~102
[52]R. Szeliski and D. Tonnesen. Surface modeling with oriented particle systems.
SIGGRAPH’92, 1992, 26(4): 185~194
[53]A. P. Witkin and P. S. Heckbert. Using particles to sample and control implicit surfaces.
SIGGRAPH’92, 1992, 26(4): 269~277
[54]J. P. Grossman. Point sample rendering. Master’s thesis, Department of Electrical
Engineering and Computer Science, MIT, August 1998
[55]H. Pfister, M. Zwicker, J. v. Baar et al. Surfels: surface elements as rendering primitives.
SIGGRAPH’ 00, 2000, 34(4): 335~342
[56]S. Rusinkiewicz and M. Levoy. QSplat: a multiresolution point rendering system for large
meshes. SIGGRAPH’ 00, 2000, 34(4): 343~352
[57]D. Lischinski and A. Rappoport. Image-based rendering for non-diffuse synthetic scenes.
In Rendering Techniques’98, Springer, Wien, Vienna, Austria, June 1998, 301~314
[58]M. Zwicker, H. Pfister, J. v. Baar et al. Surface splatting. SIGGRAPH’ 01, 2001, 35(4):
31~39
[59]P. S. Heckbert. Fundamentals of texture mapping and image warping. Master’s thesis,
Dept. of Electrical Engineering and Computer Science, University of California,
Berkeley, June 1989.
[60]S. Rusinkiewicz and M. Levoy. Streaming QSplat: A Viewer for Networked Visualization
of Large, Dense Models. SIGGRAPH’00, 2000, 34(4): 21~27
[61]D. Luebke and B. Hallen. Perceptually driven interactive rendering. Technical Report
CS-2001-01, University of Virginia, 2001
[62]M. Botsch, A. Wiratanaya, and L. Kobbelt. Efficient high quality rendering of point
sampled geometry. In Proceedings of the 13th Eurographics Workshop on Rendering,
2002
119
[63]L. Coconu and H. C. Hege. Hardware-accelerated point-based rendering of complex
scenes. In Proceedings of the 13th Eurographics Workshopon Rendering, 2002
[64]Jussi R?s?nen. Surface splatting: Theory, extensions and implementation. Master’s thesis,
Dept of Computer Science, Helsinki University of Technology, May, 2002
[65]M. Zwicker, H. Pfister, J. Baar et al. EWA splatting. IEEE transactions on Visualization
and Computer Graphics, 2002, 8(3): 223~238
[66]B. Chen and M. X. Nguyen. POP: A hybrid point and polygon rendering system for large
data. IEEE Visualization’01, 2001, 63~71
[67]J. D. Cohen, D. G. Aliaga, and W. Zhang. Hybrid simplification: Combining
multi-resolution polygon and point rendering. IEEE Visualization’01, 2001
[68]T. K. Dey and J. Hudson. PMR: Point to mesh rendering, a feature-based approach. IEEE
Visualization ’02, 2002, 155~162
[69]M. Wand and W. Stra?er. Multi-resolution rendering of complex animated scenes.
Eurographics’02, 2002, 21(3): 51~60
[70]Lin A. C., Liu H. T. Automatic generation of NC cutter path from massive data points.
Computer-Aided Design, 1998, 30(1): 77~90
[71]S. C. Park and Y. C. Chung. Tool-path generation from measured data. Computer-Aided
Design, 2003, 35: 467~475
[72]Park S. C. and Choi B. K. Boundary extraction algorithm for cutting area detection.
Computer-Aided Design, 2001, 33(8): 571~579
[73]Lee K. H., Woo H. and Suk T. Data reduction methods for reverse engineering. The
International Journal of Advanced Manufacturing Technology, 2001, 17, 735~743
[74]Xiaodong T., Yuexian W., Xionghui Z. et al. Mesh simplification based on super-face and
genetic algorithm in reverse engineering. The International Journal of Advanced
Manufacturing Technology, 2002, 20, 303~312
[75]Cchroeder W., Zarge J. and Lorenson W. Decimation of triangle meshes. SIGGRAPH’92,
1992, 26(4): 65~70
[76]Low K. L. and Tan T. S. Model simplification using vertex clustering. Proc. 1997 Symp.
Interactive 3D Graphics, ACM Press, New York, 1997, 75~92
[77]Eck M., DeRose T., Duchamp T. et al. Multiresolution analysis of arbitrary meshes.
SIGGRAPH’95, 1995, 29(4): 173~182
[78]He Taosong, Hong Lichan, Kaufman A. et al. Voxel-based object simplification.
Proceedings of Visualization’95, 1995, 296~303
120
[79]Garland M. and Heckbert P. Simplification using quadric error metrics. SIGGRAPH’97,
1997, 31(4): 209~216
[80]Hoppe H. New quadric metric for simplifying meshes with appearance attributes. Proc.
IEEE Visualization’99, 1999, 59~66
[81]Cohen J., Varshney A., Manocha D. et al. Simplification envelopes. SIGGRAPH’96,
1996, 30(4): 119~128
[82]Cohen J., Olano M. and Manocha D. Appearance preserving simplification.
SIGGRAPH’98, 1998, 32(4): 115~122
[83]Lindstrom P. and Turk G. Image-driven simplification. ACM Transactions on Graphics,
2000, 19(3): 204~241
[84]Hoppe H. Progressive meshes. SIGGRAPH’96, 1996, 30(4): 99~108
[85]Hoppe H. Efficient implementation of progressive meshes. Computers & Graphics, 1998,
22(1): 27~36
[86]Luebke D. and Erikson C. View–dependent simplification of arbitrary polygonal
environments. SIGGRAPH’97, 1997, 31(4): 199~208
[87]韩立岩, 汪培庄. 应用模糊数学(修订版). 北京:首都经济贸易大学出版社, 1989
[88]Mencl R. and Muller H. A Graph-based approach to surface reconstruction.
Eurographics’95, 1995: 445~456
[89]刘胜兰. 三角网格模型的特征线提取. 计算机辅助设计与图形学学报,2003, 15(4):
444~453
[90]孟庆生. 信息论. 西安:西安交通大学出版社, 1986
[91]Levin D. The approximation power of moving least-squares. Math. Comp. 1998, 67(224):
1517~1531
[92]Levin D. Mesh-independent surface interpolation. Geometric Modeling for Scientific
Visualization, Springer-Verlag, 2003
[93]姚海根. 图像处理. 2000年1月, 238~258
[94]A. A. Goshtasby. Grouping and parameterizing irregularly spaced points for curved fitting.
ACM Transaction on Graphics, 2000, 9(3): 185~203
[95]崔屹. 图像处理与分析:数学形态学方法与应用. 北京:科学出版社, 2000
[96]Chen S. E. Quicktime VR – an image-based approach to virtual environment navigation.
SIGGRAPH’95, 1995, 29(4): 29~38
[97]Kaufman A., Cohen D. and Yagel R. Volume Graphics. Computer, 1993, 26(7): 51~64
121
[98]Levoy M., Pulli K., Curless B. et al. The digital Michelangelo project: 3D scanning of
large statues. SIGGRAPH’00, 2000, 34(4)
[99]O. Deussen, C. Colditz, M. Stamminger et al. Interactive visualization of complex plant
ecosystems. IEEE Visualization’02, 2002
[100] 胡恩球, 张新访, 向文, 周济. 有限元网格生成方法发展综述. 计算机辅助设计
与图形学学报, 1997, 9(4): 378~383
[101] 关振群, 宋超, 顾元宪, 隋晓峰. 有限元网格生成方法研究的新进展. 计算机辅
助设计与图形学学报, 2003, 15(1): 1~14
[102] Lo S. H. Volume discretization into tetrahedra——I. Verification and orientation of
boundary surfaces. Computers and Structures, 1991, 39(5): 493~500
[103] Lohner R., Parikh P. and Gumbert C. Interactive generation of unstructured grid for
three-dimensional problems. In: Proceedings of Numerical Grid Generation in
Computational Fluid Mechanics’88, Pineridge Press , 1988. 687~697
[104] Rassineux A. Generation and optimization of tetrahedral meshes by advancing front
technique. International Journal for Numerical Methods in Engineering, 1998, 41(4):
651~674
[105] Bischoff S. and Kobbelt L. Ellipsoid decomposition of 3D-models, 2002, 3DPVT
proceedings, 480~488
[106] Bischoff S. and Kobbelt L. Towards robust broadcasting of geometry data.
Computers & Graphics, 2003, 27: 41~47
[107] Alexa M., Behr J., Cohen O. D. et al. Computing and rendering point set surfaces.
IEEE TVCG, 2002, 33~43
[108] Bechmann D. Space deformation models survey. Computers & Graphics, 1994, 18(4):
571~586
[109] Barr A. H. Global and local deformation of solid primitives. SIGGRAPH’84, 1984,
18(4): 21~30
[110] Sederberg T. W. and Parry S. R. Free-form deformation of solid geometric Models.
SIGGRAPH’86, 1986, 20(4): 151~160
[111] Coquillart S. Extended free-form deformation: a sculptureing tool for 3D geometric
modeling. SIGGRAPH’90, 1990, 24(4): 187~196.
[112] Lamousin H., Waggernspack W. NURBS-based free-form deformation. IEEE
Computer Graphics and Applicatins, 1994, 4(9): 59~65
122
[113] MacCracken R. and Joy K. Free-form deformation with lattice of arbitrary topology.
SIGGRAPH’96, 1996, 30(4): 181~183
[114] Hsu W. M., Hughes J. F. and Kaufman H. Direct manipulation of free-form
deformations. SIGGRAPH’92, 1992, 26(4): 177~184
[115] Change Y. and Rckwood A. A generalized de casteliau approach to 3D free-form
deformation. SIGGRAPH’97, 1997, 31(4): 257~260
[116] Raffin R., Neveu M. and Jaar F. Curvilinear Displacement of Free-form-based
Deformation. The Visual Computer, 2000, 16: 38~46
[117] Borrel P. and Bechmann D. Deformation of n-dimensional objects. International
Journal of Computational Geometry and Applications, 1991, 1(4): 427~453
[118] Borrel P. and Rappoport A. Simple constrainted deformations for geometric modeling
and interactive design. ACM Transactions on Graphics, 1994, 13: 137~155
[119] Jin X. G., Li Y. F. and Peng Q. S. General Constrained Deformations Based on
Generalized Metaballs. Computers & Graphics, 2000, 24: 219~231
[120] 彭群生, 鲍虎军, 金小刚. 计算机真实感图形的算法基础. 北京:科学出版社,
1999, 6月, 5~6