散乱点集曲面重建的理论、方法及应用研究
|
摘要
曲面重建技术在曲面测量造型与可视化等领域有着广泛的应用背景。作为最具普遍性的曲面重建问题，散乱点集曲面重建无论在理论上还是在实用上都有重要意义。
第一章绪论对解决曲面重建问题的几种相关技术，即三角剖分与拓扑重建技术、网格优化与简化技术、曲面造型与几何重建技术等作了简要回顾。结合曲面重建问题的研究现状，围绕拓扑重建与几何重建这两个关键技术，提出了本文付诸研究并取得进展的若干问题。
第二章将曲面三角剖分与曲面集的邻域特征相联系，讨论了在曲面集上测取一个散乱点集来刻划曲面集的二维流形特征时应该考虑的三个因素：即单张曲面的局部弯曲程度、单张曲面的整体弯曲程度以及不同曲面间的邻近程度。在此基础上，给出了平展的曲面三角剖分、局部分离样本以及全局分离样本的定义。
第三章研究了散乱点集的邻域结构及其经典算法。提出并论证了两种计算散乱点集Delaunay三角剖分的方法，即平面点集Delaunay三角剖分的局部构造算法和空间点集Delaunay三角剖分的健壮算法。提出了二维流形可辨性问题，并指出了散乱点集的邻域结构与二维流形可辨性之间的关系。
第四章提出一种基于二维流形可辨性的散乱数据曲面拓扑重建算法。该算法适用于包括单侧曲面在内的光滑且不自交的任意拓扑曲面集，且重建结果是相对优化的曲面三角形剖分。当所给点集是闭曲面集的局部分离样本或已知采样空洞半径的全局分离样本时，本算法将给出正确的重建结果；当所给点集在某些样点处不满足分离条件时，算法将给出相应的空洞以供参考。本章还给出了从拓扑相容的三角形集合中提取拓扑信息的算法和公式。
第五章针对任意拓扑曲面的几何重建问题，提出了两种新的C-T分割算法：一种采用了三角域上的B-B曲面，另一种采用了矩形域上的Bézier曲面。第一种算法的特点是重建结果不依赖于顶点的处理顺序，不需要进行控制顶点的初估及修正，可使各控制顶点的计算一次完成。第二种算法的创新之处在于它首次在该问题上采用了矩形域上的Bézier曲面，因而可被大多数CAD/CAM软件所直接采用。由于两种算法都是完全局部的，且对多余的自由度进行了合理的分配，因此具有较高的效率，并可构造相对光顺的插值曲面。
第六章讨论了Floater关于四边拓扑曲面的双三次B样条几何重建方法在圆
一
摘 要 浙江大学博士学位论文
一
盘拓扑曲面上的应用，并将其推广到平环与Mbbius带上。指出并证明了Floater
线性方程组的一个重要性质，并在此基础上提出了该方程组的一种专用解法。
该解法在时间和空间上都获得了线性复杂度，其数值稳定性与标度化全选主元
素法相同，从而显著提高了Floater方法的效率。
第七章以皮鞋CAD软件的开发为背景，着重介绍了其中曲面测量造型系统
的主要功能、实现方法与应用实例。同时给出了本文算法在有限元网格自动剖
分中的应用。
第八章对本文的研究工作进行了总结，并对曲面重建领域的发展前景进行
了展望。
The technique of surface reconstruction has extensive use in surface measuring modification and visualization and such fields. The technique of surface reconstruction from scattered points, for its universality, is very important both theoretically and practically.
In chapter 1, a brief review is made about several relative techniques, e.g., triangulation vs. topologic reconstruction, mesh optimization or simplification, and surface modification vs. geometric reconstruction. Based on the present state of investigation, several problems are put forward about topologic reconstruction and geometric reconstruction which have been studied carefully in this dissertation .
In chapter 2, surface triangulation and local feature of a surface set are considered together. Three factors are discussed which should be taken into account when sampling points from a surface set to describe its 2d manifold feature. These three factors are local bending degree of a single piece of surface, overall bending degree of a single piece of surface and vicinity degree between different surfaces. The definitions of flat surface triangulation, local separate sample and overall separate sample are given based on this discussion.
In chapter 3, the local structure of a scattered point set and its classical algorithms are investigated. Two algorithms for Delaunay triangulation from scattered points are suggested, one of which is from points in plane and the other from points in space. The problem of recognizability of 2d manifold is promoted and the relationship is pointed out between such recognizability and the local structure of a scattered point set.
In chapter 4, based .on the recognizability of 2d manifold, an algorithm is presented for topologic reconstruction from scattered points. The algorithm is applicable to nonself-intersectant smooth surface set of any topology, including nonorientable surfaces, and its result is optimal surface triangulation in a way. When the given point set is a local separate sample of a closed surface set or an overall separate sample with known radius of sampling hole, the algorithm will reconstruct a correct result; when the separate condition is not satisfied at some points, the algorithm will give result with corresponding holes. The algorithms and formulas are promoted for extracting the topological information from a set of triangles which are topologically compatible.
In chapter 5, two new C-T algorithms are proposed for geometric reconstruction, one of which adopts B-B patches on triangles and the other Bezier patches on
rectangles. The first algorithm gives unique result unaffected by the handling order of points concerned, and it calculates the control vertexes at once without estimation and correction. The originality innovation of the second algorithm is that it adopts Bezier patches on rectangles for the first time in this problem, hence can be directly adopted by most CAD/CAM software. Because the two algorithms are confined to local area, and assign redundant degrees of freedom reasonably, they are highly efficient and can give relatively smooth fitting surface.
In chapter 6, the usage of Floater's algorithm on a disk is discussed which is for geometric reconstruction of surface with four edges using double cubic B-spline surface, and the algorithm is generalized to a cylinder and a Mobius. An important property of the Floter linear system is pointed out and proved, and based on this, a special solution method for it is proposed. This solution method has a linear complexity both in time and space, and its numerical stability is similar to that of overall selected host element with normalization, hence remarkably improves the efficiency of Floater's algorithm.
In chapter 7, under the background of Shoe CAD software development, the surface measuring modification system therein is introduced with its main functions, implementation methods and application samples. At the same time, the algorithm in this dissertation is used to generate finite element mesh automatically.
In cha
第一章绪论对解决曲面重建问题的几种相关技术，即三角剖分与拓扑重建技术、网格优化与简化技术、曲面造型与几何重建技术等作了简要回顾。结合曲面重建问题的研究现状，围绕拓扑重建与几何重建这两个关键技术，提出了本文付诸研究并取得进展的若干问题。
第二章将曲面三角剖分与曲面集的邻域特征相联系，讨论了在曲面集上测取一个散乱点集来刻划曲面集的二维流形特征时应该考虑的三个因素：即单张曲面的局部弯曲程度、单张曲面的整体弯曲程度以及不同曲面间的邻近程度。在此基础上，给出了平展的曲面三角剖分、局部分离样本以及全局分离样本的定义。
第三章研究了散乱点集的邻域结构及其经典算法。提出并论证了两种计算散乱点集Delaunay三角剖分的方法，即平面点集Delaunay三角剖分的局部构造算法和空间点集Delaunay三角剖分的健壮算法。提出了二维流形可辨性问题，并指出了散乱点集的邻域结构与二维流形可辨性之间的关系。
第四章提出一种基于二维流形可辨性的散乱数据曲面拓扑重建算法。该算法适用于包括单侧曲面在内的光滑且不自交的任意拓扑曲面集，且重建结果是相对优化的曲面三角形剖分。当所给点集是闭曲面集的局部分离样本或已知采样空洞半径的全局分离样本时，本算法将给出正确的重建结果；当所给点集在某些样点处不满足分离条件时，算法将给出相应的空洞以供参考。本章还给出了从拓扑相容的三角形集合中提取拓扑信息的算法和公式。
第五章针对任意拓扑曲面的几何重建问题，提出了两种新的C-T分割算法：一种采用了三角域上的B-B曲面，另一种采用了矩形域上的Bézier曲面。第一种算法的特点是重建结果不依赖于顶点的处理顺序，不需要进行控制顶点的初估及修正，可使各控制顶点的计算一次完成。第二种算法的创新之处在于它首次在该问题上采用了矩形域上的Bézier曲面，因而可被大多数CAD/CAM软件所直接采用。由于两种算法都是完全局部的，且对多余的自由度进行了合理的分配，因此具有较高的效率，并可构造相对光顺的插值曲面。
第六章讨论了Floater关于四边拓扑曲面的双三次B样条几何重建方法在圆
一
摘 要 浙江大学博士学位论文
一
盘拓扑曲面上的应用，并将其推广到平环与Mbbius带上。指出并证明了Floater
线性方程组的一个重要性质，并在此基础上提出了该方程组的一种专用解法。
该解法在时间和空间上都获得了线性复杂度，其数值稳定性与标度化全选主元
素法相同，从而显著提高了Floater方法的效率。
第七章以皮鞋CAD软件的开发为背景，着重介绍了其中曲面测量造型系统
的主要功能、实现方法与应用实例。同时给出了本文算法在有限元网格自动剖
分中的应用。
第八章对本文的研究工作进行了总结，并对曲面重建领域的发展前景进行
了展望。
The technique of surface reconstruction has extensive use in surface measuring modification and visualization and such fields. The technique of surface reconstruction from scattered points, for its universality, is very important both theoretically and practically.
In chapter 1, a brief review is made about several relative techniques, e.g., triangulation vs. topologic reconstruction, mesh optimization or simplification, and surface modification vs. geometric reconstruction. Based on the present state of investigation, several problems are put forward about topologic reconstruction and geometric reconstruction which have been studied carefully in this dissertation .
In chapter 2, surface triangulation and local feature of a surface set are considered together. Three factors are discussed which should be taken into account when sampling points from a surface set to describe its 2d manifold feature. These three factors are local bending degree of a single piece of surface, overall bending degree of a single piece of surface and vicinity degree between different surfaces. The definitions of flat surface triangulation, local separate sample and overall separate sample are given based on this discussion.
In chapter 3, the local structure of a scattered point set and its classical algorithms are investigated. Two algorithms for Delaunay triangulation from scattered points are suggested, one of which is from points in plane and the other from points in space. The problem of recognizability of 2d manifold is promoted and the relationship is pointed out between such recognizability and the local structure of a scattered point set.
In chapter 4, based .on the recognizability of 2d manifold, an algorithm is presented for topologic reconstruction from scattered points. The algorithm is applicable to nonself-intersectant smooth surface set of any topology, including nonorientable surfaces, and its result is optimal surface triangulation in a way. When the given point set is a local separate sample of a closed surface set or an overall separate sample with known radius of sampling hole, the algorithm will reconstruct a correct result; when the separate condition is not satisfied at some points, the algorithm will give result with corresponding holes. The algorithms and formulas are promoted for extracting the topological information from a set of triangles which are topologically compatible.
In chapter 5, two new C-T algorithms are proposed for geometric reconstruction, one of which adopts B-B patches on triangles and the other Bezier patches on
rectangles. The first algorithm gives unique result unaffected by the handling order of points concerned, and it calculates the control vertexes at once without estimation and correction. The originality innovation of the second algorithm is that it adopts Bezier patches on rectangles for the first time in this problem, hence can be directly adopted by most CAD/CAM software. Because the two algorithms are confined to local area, and assign redundant degrees of freedom reasonably, they are highly efficient and can give relatively smooth fitting surface.
In chapter 6, the usage of Floater's algorithm on a disk is discussed which is for geometric reconstruction of surface with four edges using double cubic B-spline surface, and the algorithm is generalized to a cylinder and a Mobius. An important property of the Floter linear system is pointed out and proved, and based on this, a special solution method for it is proposed. This solution method has a linear complexity both in time and space, and its numerical stability is similar to that of overall selected host element with normalization, hence remarkably improves the efficiency of Floater's algorithm.
In chapter 7, under the background of Shoe CAD software development, the surface measuring modification system therein is introduced with its main functions, implementation methods and application samples. At the same time, the algorithm in this dissertation is used to generate finite element mesh automatically.
In cha
引文
[1] A. Bowyer. Computing Dirichlet tessellations. The Computer Journal. 1981,24(2) : 162-166．
[2] A. Kalvin and R. Taylor. Superfaces Polygonal mesh simplification with bounded error. IEEE Computer Graphics & Applications. 1996,16(3) : 64-77．
[3] A. Rockwood and J. Winget. Three-demensional object reconstruction from two-dimensional images. Commputer Aided Design. 1997,29(4) : 279-285．
[4] B. Choi, Y. Shin etc. Triangulation of scattered data in 3D space. Computer-Aided Desing. 1988,20(5) : 239-248．
[5] B. C. Vemuri, A. Mitiche and J. K. Aggarwal. Curvaturebased representation of objects from range data. Image and Vision Computing. 1986,4(2) : 107-114．
[6] B. Guo, J. Menon and B. Willette. Surface reconstruction using Alpha Shapes. Computer Graphics forum. 1997,16(4) : 177-190．
[7] B. Guo. Surface reconstructon: from points to splines. Computer Aided Design, 1997,29(4) : 269-277．
[8] B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design. 1994,11(2) : 197-214．
[9] B. Joe. Construction of three-dimensional Delaunay triangulations using local transformations. Computer Aided Geometric Design, 1991, 8: 123-142．
[10] B. Joe. Delaunay versus Max-min solid angle triangulations for three-dimensional mesh generation. International Journal of Numerical Methods hi Engineering. 1991, 31: 987-997．
[11] C. Grimm and J. Hughes. Modeling surfaces of arbitrary topology using manifolds. SIGGRAPH'95 Proceedings, 1995: 359-368．
[12] C. Hazlewood. Approximating constrained tetrahedrizations. Computer Aided Geometric Design. 1993,10: 67-87．
[13] C. Lawson. Generation a triangular grid with application of contour plotting. Technical Memo. 299． Jet Propulation Laboratory, Pasadena, California. 1972．
[14] C. Lawson. Softsare for C1 surface interpolation. In: Mathematical Software III. Edited by: J. Rice. Academic Press. New York. 1977．
[15] C. Loop. Smooth Spline Surfaces Over Irregular Meshes. SIGGRAPH'94
Proceedings, 1994: 303-310．
[16] D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design. 1978, 10(6) : 356-360．
[17] D. Watson. Computing the n-dimensional Delaunay tessellation with application to Vornoi poltopes. The Computer Journal. 1981,24(2) : 167-172．
[18] E.Catmull and J.Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 1978,10(6) :350~355．
[19] E. Sadek. A scheme for the automatic mesh generation on surfaces of polyhedra. IEEE transactions on magnetics. 1983,19(6) : 1539-1542．
[20] F. Aurenhammer. Voronoi diagrams: a survey of a fundamental data structure. ACM Computing Surveys. 1991, 23(3) : 345-405．
[21] F. Schmitt, B. Barsky and W. Du. An adaptive subdivision method for surface fitting from sampled data. Computer Graphics, 1986, 21(2) : 179-188．
[22] G. Chaikin. An algorithm for high speed curve generation. Computer Graphices and Image Processing. 1974, 3: 346-349．
[23] G. Farin. A modified Clough-Tocher interpolant. Computer Aided Geometric Design. 1985, 2: 19-27．
[24] G. Farin. Designing C1 surfaces consisting of triangular cubic patches. Computer Aided Design, 1982,14(5) :253~256．
[25] G. Farin. Smooth interpolation to scattered 3D data. In: Surface in CAGD, Edited by R. Barnhill and W. Boehm. North-Holland Publishing Company. 1983．
[26] G. Farin. Trianular Bernstein Bezier patch. Computer Aided Geometric Design. 1988,3．
[27] G. Strang and G. Fix. An analysis of the finite element method. Prentice-Hall. New York. 1973．
[28] G. Subramanian, V. Raveendra and M. Kamath. Robust boundary triangulation and Delaunay triangulation of arbitrary planar Domains. International Journal of Numerical Methods in Engineering. 1994, 37: 1779-1789．
[29] G. Turk and M. Levoy. Zippered polygon meshes from range images. Computer Graphics. 1994:311-318．
[30] G. Turk. Re-tiling polygonal surfaces. Computer Graphics. 1992, 26(2) : 55-64．
[31] G. Wyvill, C. McPheeters and B. Wyvill. Data structures for soft objects. The
Visual Computer. 1986, 2(4) : 227-234．
[32] H. Borouchaki, P. Laun, P. L. George. Parametric surface meshing using a combined advancing-front generalized Delauney approach. Int. J. Numer. Meth. Engng. 2000, 49:233-259．
[33] H. Chiyokura and F. Kimura. A new surface interpolation method for irregular modes. Computer Graphics Forum. 1984, 3: 209-218．
[34] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Mesh Optimization. SIGGRAPH'93 Proceedings, 1993: 19-26．
[35] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Surface reconstruction from unorganized points. SIGGRAPH'92 Proceedings. 1992: 71-78．
[36] H. Jin and R. Tanner. Generation of unstructured tetrahedral meshes by advancing front technique. International Journal of Numerical Methods in Engineering. 1993,36: 1805-1823．
[37] H. Li and S. Liu. Local interpolation of curvature-continuous surfaces. Computer Aided Design. 1992,24(9) : 182-188．
[38] J. Brinkley. Knowledge-driven ultrasonic three-dimensional organ modeling. IEEE Trangs. On Pattern Analysis and Machine intelligence. 1985, 7(4) : 431-441．
[39] J. C. Cuilliere. An adaptive method for the automatic triangulation of 3D parametric surfaces. Computer Aided Design. 1998, 30(2) : 139-149．
[40] J. Ferguson. Multivarite curve interpolation. Journal of ACM. 1964, 11(2) : 221-228．
[41] J. Gregory. C1 rectangular and non-rectangular surface patch. In: Surfaces in CAGD, R. Barnhill and W. Boehm. North-Holland Publishing Company. 1983．
[42] J. Vergest. Connecting arbitrary surfaces under geometric constains. Computers in Industry. 1987, 8(1) : 3-12．
[43] J. Wright and A. Jack. Aspects of three-dimensional constrained Delaunay Meshing. International Journal of Numerical Methods in Engineering. 1994,37: 1841-1861．
[44] K. Hollig and H. Mogerle. G-splines. Computer Aided Geometric Design. 1990, 7: 197-207．
[45] K. ReinHard. Multiresolution representations for surfaces meshes based on the
vertex decimation method. Computer & Graphics. 1998, 22(1) : 13~26．
[46] L. Chandrajit and R. Daniel. Toplogy preserving data simplification with error bounds. Computer & Graphics. 1998, 22(1) : 3-12．
[47] L. Parida and S. Mudur. Constraint-satisfying planar development of complex surfaces. Computer Aided Design. 1993, 24(4) : 225-232．
[48] L. Shirman and C. Sequin. Local surface interpolation with Bezier patches. Computer Aided Geometric Design. 1988, 4(4) : 279-296．
[49] M. Algorri and F. Schmitt. Mesh simplification. Eurographics'96 Proceedings. 1996,15(3) : 78-86．
[50] M. De Haemer and M. Zyda. Simplification of objects rendered by polygonal approximations. Computer & Graphics. 1991,15(2) : 175-184．
[51] M. Eck, T. Derose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle. Multiresolution Analysis of Arbitrary Meshes, Computer Graphics. 1995, 8: 173-182．
[52] M. Floater. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design. 1997, 14: 231-250．
[53] M. Halstead, M. Kass, T. DeRose. Efficient, fair interpolation using Catmull-Clark surfaces. SIGGRAPH'93 Proceedings, 1993: 35-44．
[54] M. Lounsbery, S. Mann and T. DeRose. Prametric surface interpolation. IEEE Computer Graphics & Applications. 1992,12(5) : 45-52．
[55] M. Reddy. Perceptually-driven polygon reduction. Computer Graphics Forum. 1996, 16(6) : 24-32．
[56] M. Yerry and M. Shephard. A Modified quadtree aproach ti finite element mesh generation. IEEE Computer Graphics & Applications. 1983, 2: 39-46．
[57] M. Yerry and M. Shephard. Automatic three-dimensional mesh generation by the modified-octree technique. International Jounal of Numerical Methods in Enginering. 1984,20: 1965-1990．
[58] N. Amenta, M. Bern and M. Kamvysselis. A new Voronoi-based surface reconstruction algorithm. SIGGRAPH'98 Proceedings. 1998: 415-421．
[59] N. Weatherill and O. Hassan. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints. International Journal of Numerical Methods in Engineering. 1994,37: 2005-2039．
[60] P. Bezier. Mathematical and practical possibility of UNISURF. In: Computer Aided Geometric Design, Edited by R. Barnhill and R. Riesenfield. Academic press. 1974: 127-152．
[61] P. George, F. Hecht and E. Saltel. Automatic 3D mesh geeration with prescribed meshed boundaries. IEEE transactions on magnetics. 1990,26(2) : 771-774．
[62] P. Green and R. Silbson. Computing Dirichlet tesellation in the plane. The Computer Jounal. 1978,2(2) : 168-173．
[63] P. J. Frey, H. Borouchaki. Surface mesh quality evaluation, hit. J. Numer. Meth. Engng.2000,45:101-118．
[64] P. Veron and J. Leon. Static polyhedron simplification using error measurements. Computer-Aided Design, 1997,29(4) : 287-298．
[65] R. Aronson. Forward thinkers take to reverse engineering. Manufacturing Engineering. 1996,12: 34-44．
[66] R. Barnhill. Asurvey of the repesentation and design of surface. IEEE Computer Graphics & Applications. 1983, 3(10) : 9-16．
[67] R. Barnhill. Reperentation and approximation of surfaces. In: Mathematical Software III. Edited by: J. Rice. Academic Press. New York. 1977．
[68] R. Bolle and B. Vemuri. On three-demensional surface reconstruction methods. IEEE Trans. On Pattern Analysis and Machine intelligence. 1991,13(1) : 1-13．
[69] R. Forrest. Interactive interpolation and approximation by Bezer polynomical. Computer Journal. 1972,15: 71-79．
[70] R. LOhner and P. Parikh. Generation of three-dimensional unstuctured grid by the advancing front method. International Journal of Numerical Methods in Fluids. 1988, 8: 1135-1149．
[71] R. Silbson. Locally equiangular tirnagulations. The Computer Journal. 1978, 21(3) : 243-245．
[72] S. Coons. Surface for computer aided design. MCA-TR-41． MIT. U.S.A. 1964．
[73] S. Kumar and D. Manocha. Efficient renderign of trimmed NURBS surfaces. Computer Aided Design. 1995, 27(7) : 509-520．
[74] S. Lo. A new mesh generation scheme for arbitrary planar donains. International Journal of Numerical Methods in Engineering. 1985, 21: 1403-1426．
[75] S. Lo. Automatic mesh generation over intersecting surfaces. International
Journal of Numerical Methods in Engineerign. 1995, 38: 943-954．
[76] S. Muraki. Volumetric shape description of range data using "blobby model". SIGGRAPH'91 Proceedings, 1991: 227-235．
[77] S. Sloa. A fast algorithm generating constrained Delaunay triangulations. Computers & Structures. 1993,47(3) : 441-450．
[78] T. Dey, K. Sugihara and C. Bajaj. Delauany triangulations in three dimensions with finite precision arithmetic. Computer Aided Geometric Design. 1992, 9: 457-470．
[79] T. Fang and L. Piegl. Algorithm for Delaunay triangulation and convex-hull computation using a sparse matrix. Computer Aided Design. 1989, 21(4) : 248-253．
[80] T. Fang and L. Piegl. Delaunay Triangulation in Thee Dimensions. IEEE Computer Graphics & Applications. 1995, 9: 62-69．
[81] T. Foley and G. Nielson. Knot selection for parametric spline interpolation, in: Lyche, T. and Schumaker, L., eds., Mathematical Methods in Computer Aided Geometic Design II, Academeic Press, New York, 261-271． 1992．
[82] T. Hermann. On the smoothness of offset surfaces. Computer Aided Geometric Design. 1998,15: 529-533．
[83] T. Varady, R. Martin and J. Cox. Reverse engineering of geometic models-an introduction. Computer Aided Design. 1997,29(4) : 255-268．
[84] T. Whelan. A representation of a C2 interpolant over triangles. Computer Aided Geometric Design. 1986, 3: 53-66．
[85] V. Pratt. Direct least-squares fitting of algebraic sufaces. SIGGRAPH'87 Proceedings, 1987: 145-152．
[86] W. Gordon and R. Riesenfled Bernstein Bezier methods for the computer aided design of free form curves and surfaces. Journal of the ACM. 1974, 21(2) : 293-310．
[87] W. Gordon. Spline blended surface interpolation through curve network. Journal of Mathematics and Mechanics. 1969,18:931-952．
[88] W. Schroeder, J. Zarge and W. Lorensen. Decimation of triangle meshes. SIGGRAPH'92 Proceedings, 1992, 26(2) : 65-70．
[89] W. Welch and A. Witkin. Free-Form shape Design Using Triangulated Surfaces. SIGGRAPH'94 Proceedings, 1994: 247-256．
[90]W. Welch and A. Witkin. Variational Surface Modeling. SIGGRAPH'92 Proceedings, 1992:157～166.
[91]X. Sheng and B. Hirsch. Triangulation of trimmed surfaces in parametric space. Computer Aided Design. 1992, 24(8): 437～444.
[92]Y. Jung and K. Lee. Tetrahedron-based octree endoding for automatic mesh generation. Computer Aided Design. 1993, 25(3): 141～153.
[93]陈洪亮，谭建荣．一种基于渐变物理属性的三角网格简化方法．计算机学报．2000，23(3)：285～292．
[94]高曙明，彭群生．一种通用的Trimmed曲面三角化算法．计算机辅助设计与图形学学报．1992，4(4)：9～15．
[95]季敏雯，杨长贵，孙家广．Trimmed NURBS曲面参数域的快速三角化算法．计算机学报．1996，19(6)：450～456．
[96]柯映林．离散数据几何造型技术及其应用研究．博士学位论文．南京．南京航空航天大学．1992．
[97]柯映林，周儒荣．参数B(?)z(?)er三角曲面的GC~1构造及其在复杂曲面产品测量中的应用．浙江大学学报．1995，29(3)：354～360．
[98]李江雄．复杂曲面反求工程CAD建模技术研究，博士学位论文．杭州．浙江大学．1998．
[99]李立新，谭建荣．约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法．计算机学报．1999，22(10)：1114-1118．
[100]闵卫东，唐泽圣．二维任意域内点集的Delaunay三角划分生成算法．计算机学报，1995，18(5)：365-371．
[101]刘鼎元．B(?)zer曲面片光滑连接的几何条件．应用数学学报．1986，9(4)：12～17．
[102]刘之生．反求工程技术．北京．机械工业出版社．1996．
[103]卢朝阳，吴成柯，陆心如．简单多边形的优化三角剖分．电子学报．1991，19(2)：82-87．
[104]卢朝阳，吴成柯．任意多边形内带特征约束的散列数据的最优三角剖分．计算机辅助设计与图形学学报．1997，9(4)：302～308．
[105]卢朝阳，吴成柯，陆心如．优化TSP算法的完善及推广．电子学报．1994，22(1)：86-89．
[106]卢朝阳，吴成柯，周幸妮．满足全局Delaunay特性的带特征约束的散乱数据最优化三角剖分．计算机学报．1997，20(2)：118-124．
[107]马小虎，潘志庚，石教英．基于三角形移去准则的多面体模型简化方法．计算机学报．1998，21(7)：492～498．
[108]梅中义，范玉青，胡世光．NURBS曲面的有限元网格三角剖分．计算机辅助设计与图形学学报．1997，9(4)：289～294．
[109]彭群生．关于实用几何造型系统的研究报告．浙江大学数学系．1990．
[110]任仲贵．CAD/CAM原理．清华大学出版社．1991．
[111]石教英，蔡文立．科学计算可视化算法与系统．科学出版社．1996．
[112]苏步青，刘鼎元．计算几何．上海科学出版社．1980．
[113]唐荣锡．CAD/CAM技术．北京．北京航空航天大学出版社．1994．
[114]王会成，牟欣，张利波．Trimmed曲面的三角剖分算法研究．计算机辅助设计与图形学学报．
[115]王青，王融清，鲍虎军，彭群生．散乱数据点的增量快速曲面重建算法．软件学报．2000，11(9)：1221～1227．
[116]熊有伦，杨叔子．测量自动化、集成化和智能化．中国机械工程．1992，1：20～22．
[117]徐永安．约束Delaunay三角剖化的关键问题研究与算法实现及应用．博士学位论文．杭州．浙江大学．1999．
[118]尤成业．基础拓扑学讲义．北京大学出版社．1997．
[119]张梅华，顾元宪等．三维有限元网格自动剖分中对边界的处理方法：单元提取法．计算机辅助设计与图形学学报．1997，9(3)：200～206．
[120]赵东福．复杂曲面测量造型和数控加工技术的研究．博士学位论文．杭州．浙江大学．1997．
[121]周晓云，刘慎权．实现约束Delaunay三角剖分的健壮算法．计算机学报．1996，29(8)：615～624．
[2] A. Kalvin and R. Taylor. Superfaces Polygonal mesh simplification with bounded error. IEEE Computer Graphics & Applications. 1996,16(3) : 64-77．
[3] A. Rockwood and J. Winget. Three-demensional object reconstruction from two-dimensional images. Commputer Aided Design. 1997,29(4) : 279-285．
[4] B. Choi, Y. Shin etc. Triangulation of scattered data in 3D space. Computer-Aided Desing. 1988,20(5) : 239-248．
[5] B. C. Vemuri, A. Mitiche and J. K. Aggarwal. Curvaturebased representation of objects from range data. Image and Vision Computing. 1986,4(2) : 107-114．
[6] B. Guo, J. Menon and B. Willette. Surface reconstruction using Alpha Shapes. Computer Graphics forum. 1997,16(4) : 177-190．
[7] B. Guo. Surface reconstructon: from points to splines. Computer Aided Design, 1997,29(4) : 269-277．
[8] B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design. 1994,11(2) : 197-214．
[9] B. Joe. Construction of three-dimensional Delaunay triangulations using local transformations. Computer Aided Geometric Design, 1991, 8: 123-142．
[10] B. Joe. Delaunay versus Max-min solid angle triangulations for three-dimensional mesh generation. International Journal of Numerical Methods hi Engineering. 1991, 31: 987-997．
[11] C. Grimm and J. Hughes. Modeling surfaces of arbitrary topology using manifolds. SIGGRAPH'95 Proceedings, 1995: 359-368．
[12] C. Hazlewood. Approximating constrained tetrahedrizations. Computer Aided Geometric Design. 1993,10: 67-87．
[13] C. Lawson. Generation a triangular grid with application of contour plotting. Technical Memo. 299． Jet Propulation Laboratory, Pasadena, California. 1972．
[14] C. Lawson. Softsare for C1 surface interpolation. In: Mathematical Software III. Edited by: J. Rice. Academic Press. New York. 1977．
[15] C. Loop. Smooth Spline Surfaces Over Irregular Meshes. SIGGRAPH'94
Proceedings, 1994: 303-310．
[16] D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design. 1978, 10(6) : 356-360．
[17] D. Watson. Computing the n-dimensional Delaunay tessellation with application to Vornoi poltopes. The Computer Journal. 1981,24(2) : 167-172．
[18] E.Catmull and J.Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 1978,10(6) :350~355．
[19] E. Sadek. A scheme for the automatic mesh generation on surfaces of polyhedra. IEEE transactions on magnetics. 1983,19(6) : 1539-1542．
[20] F. Aurenhammer. Voronoi diagrams: a survey of a fundamental data structure. ACM Computing Surveys. 1991, 23(3) : 345-405．
[21] F. Schmitt, B. Barsky and W. Du. An adaptive subdivision method for surface fitting from sampled data. Computer Graphics, 1986, 21(2) : 179-188．
[22] G. Chaikin. An algorithm for high speed curve generation. Computer Graphices and Image Processing. 1974, 3: 346-349．
[23] G. Farin. A modified Clough-Tocher interpolant. Computer Aided Geometric Design. 1985, 2: 19-27．
[24] G. Farin. Designing C1 surfaces consisting of triangular cubic patches. Computer Aided Design, 1982,14(5) :253~256．
[25] G. Farin. Smooth interpolation to scattered 3D data. In: Surface in CAGD, Edited by R. Barnhill and W. Boehm. North-Holland Publishing Company. 1983．
[26] G. Farin. Trianular Bernstein Bezier patch. Computer Aided Geometric Design. 1988,3．
[27] G. Strang and G. Fix. An analysis of the finite element method. Prentice-Hall. New York. 1973．
[28] G. Subramanian, V. Raveendra and M. Kamath. Robust boundary triangulation and Delaunay triangulation of arbitrary planar Domains. International Journal of Numerical Methods in Engineering. 1994, 37: 1779-1789．
[29] G. Turk and M. Levoy. Zippered polygon meshes from range images. Computer Graphics. 1994:311-318．
[30] G. Turk. Re-tiling polygonal surfaces. Computer Graphics. 1992, 26(2) : 55-64．
[31] G. Wyvill, C. McPheeters and B. Wyvill. Data structures for soft objects. The
Visual Computer. 1986, 2(4) : 227-234．
[32] H. Borouchaki, P. Laun, P. L. George. Parametric surface meshing using a combined advancing-front generalized Delauney approach. Int. J. Numer. Meth. Engng. 2000, 49:233-259．
[33] H. Chiyokura and F. Kimura. A new surface interpolation method for irregular modes. Computer Graphics Forum. 1984, 3: 209-218．
[34] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Mesh Optimization. SIGGRAPH'93 Proceedings, 1993: 19-26．
[35] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Surface reconstruction from unorganized points. SIGGRAPH'92 Proceedings. 1992: 71-78．
[36] H. Jin and R. Tanner. Generation of unstructured tetrahedral meshes by advancing front technique. International Journal of Numerical Methods in Engineering. 1993,36: 1805-1823．
[37] H. Li and S. Liu. Local interpolation of curvature-continuous surfaces. Computer Aided Design. 1992,24(9) : 182-188．
[38] J. Brinkley. Knowledge-driven ultrasonic three-dimensional organ modeling. IEEE Trangs. On Pattern Analysis and Machine intelligence. 1985, 7(4) : 431-441．
[39] J. C. Cuilliere. An adaptive method for the automatic triangulation of 3D parametric surfaces. Computer Aided Design. 1998, 30(2) : 139-149．
[40] J. Ferguson. Multivarite curve interpolation. Journal of ACM. 1964, 11(2) : 221-228．
[41] J. Gregory. C1 rectangular and non-rectangular surface patch. In: Surfaces in CAGD, R. Barnhill and W. Boehm. North-Holland Publishing Company. 1983．
[42] J. Vergest. Connecting arbitrary surfaces under geometric constains. Computers in Industry. 1987, 8(1) : 3-12．
[43] J. Wright and A. Jack. Aspects of three-dimensional constrained Delaunay Meshing. International Journal of Numerical Methods in Engineering. 1994,37: 1841-1861．
[44] K. Hollig and H. Mogerle. G-splines. Computer Aided Geometric Design. 1990, 7: 197-207．
[45] K. ReinHard. Multiresolution representations for surfaces meshes based on the
vertex decimation method. Computer & Graphics. 1998, 22(1) : 13~26．
[46] L. Chandrajit and R. Daniel. Toplogy preserving data simplification with error bounds. Computer & Graphics. 1998, 22(1) : 3-12．
[47] L. Parida and S. Mudur. Constraint-satisfying planar development of complex surfaces. Computer Aided Design. 1993, 24(4) : 225-232．
[48] L. Shirman and C. Sequin. Local surface interpolation with Bezier patches. Computer Aided Geometric Design. 1988, 4(4) : 279-296．
[49] M. Algorri and F. Schmitt. Mesh simplification. Eurographics'96 Proceedings. 1996,15(3) : 78-86．
[50] M. De Haemer and M. Zyda. Simplification of objects rendered by polygonal approximations. Computer & Graphics. 1991,15(2) : 175-184．
[51] M. Eck, T. Derose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle. Multiresolution Analysis of Arbitrary Meshes, Computer Graphics. 1995, 8: 173-182．
[52] M. Floater. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design. 1997, 14: 231-250．
[53] M. Halstead, M. Kass, T. DeRose. Efficient, fair interpolation using Catmull-Clark surfaces. SIGGRAPH'93 Proceedings, 1993: 35-44．
[54] M. Lounsbery, S. Mann and T. DeRose. Prametric surface interpolation. IEEE Computer Graphics & Applications. 1992,12(5) : 45-52．
[55] M. Reddy. Perceptually-driven polygon reduction. Computer Graphics Forum. 1996, 16(6) : 24-32．
[56] M. Yerry and M. Shephard. A Modified quadtree aproach ti finite element mesh generation. IEEE Computer Graphics & Applications. 1983, 2: 39-46．
[57] M. Yerry and M. Shephard. Automatic three-dimensional mesh generation by the modified-octree technique. International Jounal of Numerical Methods in Enginering. 1984,20: 1965-1990．
[58] N. Amenta, M. Bern and M. Kamvysselis. A new Voronoi-based surface reconstruction algorithm. SIGGRAPH'98 Proceedings. 1998: 415-421．
[59] N. Weatherill and O. Hassan. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints. International Journal of Numerical Methods in Engineering. 1994,37: 2005-2039．
[60] P. Bezier. Mathematical and practical possibility of UNISURF. In: Computer Aided Geometric Design, Edited by R. Barnhill and R. Riesenfield. Academic press. 1974: 127-152．
[61] P. George, F. Hecht and E. Saltel. Automatic 3D mesh geeration with prescribed meshed boundaries. IEEE transactions on magnetics. 1990,26(2) : 771-774．
[62] P. Green and R. Silbson. Computing Dirichlet tesellation in the plane. The Computer Jounal. 1978,2(2) : 168-173．
[63] P. J. Frey, H. Borouchaki. Surface mesh quality evaluation, hit. J. Numer. Meth. Engng.2000,45:101-118．
[64] P. Veron and J. Leon. Static polyhedron simplification using error measurements. Computer-Aided Design, 1997,29(4) : 287-298．
[65] R. Aronson. Forward thinkers take to reverse engineering. Manufacturing Engineering. 1996,12: 34-44．
[66] R. Barnhill. Asurvey of the repesentation and design of surface. IEEE Computer Graphics & Applications. 1983, 3(10) : 9-16．
[67] R. Barnhill. Reperentation and approximation of surfaces. In: Mathematical Software III. Edited by: J. Rice. Academic Press. New York. 1977．
[68] R. Bolle and B. Vemuri. On three-demensional surface reconstruction methods. IEEE Trans. On Pattern Analysis and Machine intelligence. 1991,13(1) : 1-13．
[69] R. Forrest. Interactive interpolation and approximation by Bezer polynomical. Computer Journal. 1972,15: 71-79．
[70] R. LOhner and P. Parikh. Generation of three-dimensional unstuctured grid by the advancing front method. International Journal of Numerical Methods in Fluids. 1988, 8: 1135-1149．
[71] R. Silbson. Locally equiangular tirnagulations. The Computer Journal. 1978, 21(3) : 243-245．
[72] S. Coons. Surface for computer aided design. MCA-TR-41． MIT. U.S.A. 1964．
[73] S. Kumar and D. Manocha. Efficient renderign of trimmed NURBS surfaces. Computer Aided Design. 1995, 27(7) : 509-520．
[74] S. Lo. A new mesh generation scheme for arbitrary planar donains. International Journal of Numerical Methods in Engineering. 1985, 21: 1403-1426．
[75] S. Lo. Automatic mesh generation over intersecting surfaces. International
Journal of Numerical Methods in Engineerign. 1995, 38: 943-954．
[76] S. Muraki. Volumetric shape description of range data using "blobby model". SIGGRAPH'91 Proceedings, 1991: 227-235．
[77] S. Sloa. A fast algorithm generating constrained Delaunay triangulations. Computers & Structures. 1993,47(3) : 441-450．
[78] T. Dey, K. Sugihara and C. Bajaj. Delauany triangulations in three dimensions with finite precision arithmetic. Computer Aided Geometric Design. 1992, 9: 457-470．
[79] T. Fang and L. Piegl. Algorithm for Delaunay triangulation and convex-hull computation using a sparse matrix. Computer Aided Design. 1989, 21(4) : 248-253．
[80] T. Fang and L. Piegl. Delaunay Triangulation in Thee Dimensions. IEEE Computer Graphics & Applications. 1995, 9: 62-69．
[81] T. Foley and G. Nielson. Knot selection for parametric spline interpolation, in: Lyche, T. and Schumaker, L., eds., Mathematical Methods in Computer Aided Geometic Design II, Academeic Press, New York, 261-271． 1992．
[82] T. Hermann. On the smoothness of offset surfaces. Computer Aided Geometric Design. 1998,15: 529-533．
[83] T. Varady, R. Martin and J. Cox. Reverse engineering of geometic models-an introduction. Computer Aided Design. 1997,29(4) : 255-268．
[84] T. Whelan. A representation of a C2 interpolant over triangles. Computer Aided Geometric Design. 1986, 3: 53-66．
[85] V. Pratt. Direct least-squares fitting of algebraic sufaces. SIGGRAPH'87 Proceedings, 1987: 145-152．
[86] W. Gordon and R. Riesenfled Bernstein Bezier methods for the computer aided design of free form curves and surfaces. Journal of the ACM. 1974, 21(2) : 293-310．
[87] W. Gordon. Spline blended surface interpolation through curve network. Journal of Mathematics and Mechanics. 1969,18:931-952．
[88] W. Schroeder, J. Zarge and W. Lorensen. Decimation of triangle meshes. SIGGRAPH'92 Proceedings, 1992, 26(2) : 65-70．
[89] W. Welch and A. Witkin. Free-Form shape Design Using Triangulated Surfaces. SIGGRAPH'94 Proceedings, 1994: 247-256．
[90]W. Welch and A. Witkin. Variational Surface Modeling. SIGGRAPH'92 Proceedings, 1992:157～166.
[91]X. Sheng and B. Hirsch. Triangulation of trimmed surfaces in parametric space. Computer Aided Design. 1992, 24(8): 437～444.
[92]Y. Jung and K. Lee. Tetrahedron-based octree endoding for automatic mesh generation. Computer Aided Design. 1993, 25(3): 141～153.
[93]陈洪亮，谭建荣．一种基于渐变物理属性的三角网格简化方法．计算机学报．2000，23(3)：285～292．
[94]高曙明，彭群生．一种通用的Trimmed曲面三角化算法．计算机辅助设计与图形学学报．1992，4(4)：9～15．
[95]季敏雯，杨长贵，孙家广．Trimmed NURBS曲面参数域的快速三角化算法．计算机学报．1996，19(6)：450～456．
[96]柯映林．离散数据几何造型技术及其应用研究．博士学位论文．南京．南京航空航天大学．1992．
[97]柯映林，周儒荣．参数B(?)z(?)er三角曲面的GC~1构造及其在复杂曲面产品测量中的应用．浙江大学学报．1995，29(3)：354～360．
[98]李江雄．复杂曲面反求工程CAD建模技术研究，博士学位论文．杭州．浙江大学．1998．
[99]李立新，谭建荣．约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法．计算机学报．1999，22(10)：1114-1118．
[100]闵卫东，唐泽圣．二维任意域内点集的Delaunay三角划分生成算法．计算机学报，1995，18(5)：365-371．
[101]刘鼎元．B(?)zer曲面片光滑连接的几何条件．应用数学学报．1986，9(4)：12～17．
[102]刘之生．反求工程技术．北京．机械工业出版社．1996．
[103]卢朝阳，吴成柯，陆心如．简单多边形的优化三角剖分．电子学报．1991，19(2)：82-87．
[104]卢朝阳，吴成柯．任意多边形内带特征约束的散列数据的最优三角剖分．计算机辅助设计与图形学学报．1997，9(4)：302～308．
[105]卢朝阳，吴成柯，陆心如．优化TSP算法的完善及推广．电子学报．1994，22(1)：86-89．
[106]卢朝阳，吴成柯，周幸妮．满足全局Delaunay特性的带特征约束的散乱数据最优化三角剖分．计算机学报．1997，20(2)：118-124．
[107]马小虎，潘志庚，石教英．基于三角形移去准则的多面体模型简化方法．计算机学报．1998，21(7)：492～498．
[108]梅中义，范玉青，胡世光．NURBS曲面的有限元网格三角剖分．计算机辅助设计与图形学学报．1997，9(4)：289～294．
[109]彭群生．关于实用几何造型系统的研究报告．浙江大学数学系．1990．
[110]任仲贵．CAD/CAM原理．清华大学出版社．1991．
[111]石教英，蔡文立．科学计算可视化算法与系统．科学出版社．1996．
[112]苏步青，刘鼎元．计算几何．上海科学出版社．1980．
[113]唐荣锡．CAD/CAM技术．北京．北京航空航天大学出版社．1994．
[114]王会成，牟欣，张利波．Trimmed曲面的三角剖分算法研究．计算机辅助设计与图形学学报．
[115]王青，王融清，鲍虎军，彭群生．散乱数据点的增量快速曲面重建算法．软件学报．2000，11(9)：1221～1227．
[116]熊有伦，杨叔子．测量自动化、集成化和智能化．中国机械工程．1992，1：20～22．
[117]徐永安．约束Delaunay三角剖化的关键问题研究与算法实现及应用．博士学位论文．杭州．浙江大学．1999．
[118]尤成业．基础拓扑学讲义．北京大学出版社．1997．
[119]张梅华，顾元宪等．三维有限元网格自动剖分中对边界的处理方法：单元提取法．计算机辅助设计与图形学学报．1997，9(3)：200～206．
[120]赵东福．复杂曲面测量造型和数控加工技术的研究．博士学位论文．杭州．浙江大学．1997．
[121]周晓云，刘慎权．实现约束Delaunay三角剖分的健壮算法．计算机学报．1996，29(8)：615～624．