A smooth interpolatory subdivision algorithm for the generation of surfaces over arbi-trary triangulations is introduced and its convergence properties over nonuniform triangulationsstudied. For uniform data, this met...A smooth interpolatory subdivision algorithm for the generation of surfaces over arbi-trary triangulations is introduced and its convergence properties over nonuniform triangulationsstudied. For uniform data, this method is a generalization of the analysis for univariatesubdivision algorithms and for nonuniform data, an extraordinary point analysis is introducedand the local subdivision matrix anaiysis presented. It is proved that the algorithm producessmooth surfaces over arbitrary triangular networks provided the shape parameters are kept with-in an appropriate range. Finally, two graphical examples of surface interpolation overnonuniform data are given to show the smoothing process of the algorithm.AMS (MOS): 65D05, 65D15,65D17.展开更多
An improved algorithm of Delaunay triangulation is proposed by expanding the scope from a convex polygon to an arbitrary polygon area in which holes can be contained in the subdivision procedure. The data structure of...An improved algorithm of Delaunay triangulation is proposed by expanding the scope from a convex polygon to an arbitrary polygon area in which holes can be contained in the subdivision procedure. The data structure of generated triangles and the exuviationslike method play a key role, and a single connectivity domain (SCD) without holes is constructed as the initial part of the algorithm. Meanwhile, some examples show that the method can be applied to the triangulation of the trimmed NURBS surface. The result of surface tessellation can be used in many applications such as NC machining, finite element analysis, rendering and mechanism interference detection.展开更多
Interpolatory subdivision algorithms for the generation of curves and surfaces play a veryimportant rule in shape design and modelling in CAD/CAM systems. In this paper, by using the dif-ference and divided difference...Interpolatory subdivision algorithms for the generation of curves and surfaces play a veryimportant rule in shape design and modelling in CAD/CAM systems. In this paper, by using the dif-ference and divided difference analysis, a systematic method to construct Cn (n≥ 0) interpolatorycurves by subdivision from given data is described and the mask (filter) of the algorithm is presentedexplicitly. This algorithm generates a Cn smooth curve which interpolates the initial control points.Control parameters are also provided so that the shape of the final curve can be adjusted according torequirements. An immediate generalisation of the method is the construction of smooth interpolatorysubdivision algorithms over uniform triangular networks (tensor product type data) in Rm. The mainresults of this algorithm for smooth interpolatory surface subdivision algorrthm are also included.AMS(MOS) : 65D05 , 65D15 , 65D17.展开更多
Surface reconstruction is a problem in the field of computational geometry that is concerned with recreating a surface from scattered data points sampled from an unknown surface. To date, the primary application of su...Surface reconstruction is a problem in the field of computational geometry that is concerned with recreating a surface from scattered data points sampled from an unknown surface. To date, the primary application of surface reconstruction algorithms has been in computer graphics, where physical models are digitized in three dimensions with laser range scanners or mechanical digitizing probes (Bernardini?et al., 1999?[1]). Surface reconstruction algorithms are used to convert the set of digitized points into a wire frame mesh model, which can be colored, textured, shaded, and placed into a 3D scene (in a movie or television commercial, for example). In this paper, we discuss some computational geometry preliminaries, and then move on to a summary of some different techniques used to address the surface reconstruction problem. The coming sections describe two algorithms: that of Hoppe,?et al. (1992?[2]) and Amenta,?et al. (1998?[3]). Finally, we present other applications of surface reconstruction and a brief comparison for some algorithms in this filed emphasizing on their advantages and disadvantages.展开更多
Based on the butterfly subdivision scheme and the modified butterfly subdivision scheme, an improved butterfly subdivision scheme is proposed. The scheme uses a small stencil of six points to calculate new inserting v...Based on the butterfly subdivision scheme and the modified butterfly subdivision scheme, an improved butterfly subdivision scheme is proposed. The scheme uses a small stencil of six points to calculate new inserting vertex, 2n new vertices are inserted in the 2n triangle faces in each recursion, and the n old vertices are kept, special treatment is given to the boundary, achieving higher smoothness while using small stencils is realized. With the proposed scheme, the number of triangle faces increases only by a factor of 3 in each refinement step. Compared with the butterfly subdivision scheme and the modified butterfly subdivision scheme, the size of triangle faces changes more gradually, which allows one to have greater control over the resolution of a refined mesh.展开更多
The problem of computing a piecewise linear approximation to a surface from its sample has been a focus of research in geometry modeling and graphics due to its widespread applications in computer aided design. In thi...The problem of computing a piecewise linear approximation to a surface from its sample has been a focus of research in geometry modeling and graphics due to its widespread applications in computer aided design. In this paper, we give a new algorithm, to be called offset surface filtering (OSF) algorithm, which computes a piecewise-linear approximation of a smooth surface from a finite set of cloud points. The algorithm has two main stages. First, the surface normal on every point is estimated by the least squares best fitting plane method. Second, we construct a restricted Delaunay triangulation, which is a tubular neighborhood of the surface defined by two offset surfaces. The algorithm is simple and robust. We describe an implementation of it and show example outputs.展开更多
文摘A smooth interpolatory subdivision algorithm for the generation of surfaces over arbi-trary triangulations is introduced and its convergence properties over nonuniform triangulationsstudied. For uniform data, this method is a generalization of the analysis for univariatesubdivision algorithms and for nonuniform data, an extraordinary point analysis is introducedand the local subdivision matrix anaiysis presented. It is proved that the algorithm producessmooth surfaces over arbitrary triangular networks provided the shape parameters are kept with-in an appropriate range. Finally, two graphical examples of surface interpolation overnonuniform data are given to show the smoothing process of the algorithm.AMS (MOS): 65D05, 65D15,65D17.
文摘An improved algorithm of Delaunay triangulation is proposed by expanding the scope from a convex polygon to an arbitrary polygon area in which holes can be contained in the subdivision procedure. The data structure of generated triangles and the exuviationslike method play a key role, and a single connectivity domain (SCD) without holes is constructed as the initial part of the algorithm. Meanwhile, some examples show that the method can be applied to the triangulation of the trimmed NURBS surface. The result of surface tessellation can be used in many applications such as NC machining, finite element analysis, rendering and mechanism interference detection.
文摘Interpolatory subdivision algorithms for the generation of curves and surfaces play a veryimportant rule in shape design and modelling in CAD/CAM systems. In this paper, by using the dif-ference and divided difference analysis, a systematic method to construct Cn (n≥ 0) interpolatorycurves by subdivision from given data is described and the mask (filter) of the algorithm is presentedexplicitly. This algorithm generates a Cn smooth curve which interpolates the initial control points.Control parameters are also provided so that the shape of the final curve can be adjusted according torequirements. An immediate generalisation of the method is the construction of smooth interpolatorysubdivision algorithms over uniform triangular networks (tensor product type data) in Rm. The mainresults of this algorithm for smooth interpolatory surface subdivision algorrthm are also included.AMS(MOS) : 65D05 , 65D15 , 65D17.
文摘Surface reconstruction is a problem in the field of computational geometry that is concerned with recreating a surface from scattered data points sampled from an unknown surface. To date, the primary application of surface reconstruction algorithms has been in computer graphics, where physical models are digitized in three dimensions with laser range scanners or mechanical digitizing probes (Bernardini?et al., 1999?[1]). Surface reconstruction algorithms are used to convert the set of digitized points into a wire frame mesh model, which can be colored, textured, shaded, and placed into a 3D scene (in a movie or television commercial, for example). In this paper, we discuss some computational geometry preliminaries, and then move on to a summary of some different techniques used to address the surface reconstruction problem. The coming sections describe two algorithms: that of Hoppe,?et al. (1992?[2]) and Amenta,?et al. (1998?[3]). Finally, we present other applications of surface reconstruction and a brief comparison for some algorithms in this filed emphasizing on their advantages and disadvantages.
文摘Based on the butterfly subdivision scheme and the modified butterfly subdivision scheme, an improved butterfly subdivision scheme is proposed. The scheme uses a small stencil of six points to calculate new inserting vertex, 2n new vertices are inserted in the 2n triangle faces in each recursion, and the n old vertices are kept, special treatment is given to the boundary, achieving higher smoothness while using small stencils is realized. With the proposed scheme, the number of triangle faces increases only by a factor of 3 in each refinement step. Compared with the butterfly subdivision scheme and the modified butterfly subdivision scheme, the size of triangle faces changes more gradually, which allows one to have greater control over the resolution of a refined mesh.
基金Project supported by the National Natural Science Foundation of China (No. 10371110) and the National Basic Research Program (973) of China (No. 2004CB318000)
文摘The problem of computing a piecewise linear approximation to a surface from its sample has been a focus of research in geometry modeling and graphics due to its widespread applications in computer aided design. In this paper, we give a new algorithm, to be called offset surface filtering (OSF) algorithm, which computes a piecewise-linear approximation of a smooth surface from a finite set of cloud points. The algorithm has two main stages. First, the surface normal on every point is estimated by the least squares best fitting plane method. Second, we construct a restricted Delaunay triangulation, which is a tubular neighborhood of the surface defined by two offset surfaces. The algorithm is simple and robust. We describe an implementation of it and show example outputs.
