Triangulation of NURBS surfaces through adaptive refinement

• Autorzy: Sugier, J.
• Języki publikacji: EN

Abstrakty

EN

This paper discusses adaptive approach to the problem of automatic triangulation of NURBS surfaces. The algorithm presented here generates triangulation through the so-called adaptive refinement - a process carried out entirely in a parametric space with a variable triangle size adjucted to the local curvature of the surface, so that the imposed approximation error is not exceeded. The mesh is generated as an adaptive one right from the start, and no further decimation is required. Sample triangulations generated by the algorithm as well as a discussion of its computational complexity are included. Running times of the computer implementation confirm that an average computational cost of the algorithm is ~ O (N), with N denoting the total number of traingles in the final mesh.

Słowa kluczowe

EN

tesselation of surface; NURBS; adaptive triangulation

• Czasopismo: Machine Graphics and Vision
• Rocznik: 2002
• Tom: Vol. 11, No. 1
• Strony: 37-52
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Sugier, J.

• Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17, 50-372 Wroclaw, Poland,

Bibliografia

• [1] Watson D. F.: Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. The Computer Journal, 24(2), 167-172. 1980.
• [2] Filip D., Magedson R., Markot R.: Surface algorithms using bounds on derivatives. CAGD, 3, 295-311. 1986.
• [3] Frey W. H.: Selective refinement: a new strategy for automatic node placement in graded triangularmeshes. Int. J. Numerical Methods in Engineering, 24, 2183-2200. 1987.
• [4] Preparata F. P., Shamos M. I.: Computational Geometry. An Introduction. NY, S-V. 1988.
• [5] Cheng F.: Estimating subdivision depths for rational curves and surfaces. ACM Trans. Graphics, 11 (2), 140-151. 1992.
• [6] Sheng X., Hirsch B. E.: Triangulation of trimmed surfaces in parametric space. C-AD, 24(8), 437-444. 1992.
• [7] Tiller W.: Knot-removal algorithms for NURBS curves and surfaces. C-AD, 24(8), 445-453. 1992.
• [8] Chew L. P.: Guaranteed-quality mesh generation for curved surfaces. Proc. 9th Annual Symp. Computational Geometry, San Diego, Calif., 274-280. 1993.
• [9] Dolenc A., Makela I.: Optimised triangulation of parametric surfaces. Computer-Aided Surface Geometry and Design, A. Bowyer (Ed.), Oxford Univ. Pres, 169-183. 1994.
• [10] Brunet P., Vigo M.: Piecewise linear approximation of trimmed surfaces. Geometric Modelling, H. Hagen, G. Farin, H. Noltemeier (Eds.), Computing Supplements 10, S-V, 341-356. 1995.
• [11] Piegl L. A., Richard A. M.: Tesselating trimmed NURBS surfaces. C-AD, 27(1), 16-26. 1995.
• [12] Cougny H., Shephard M.: Surface meshing using vertex insertion. Proc. 5th Int. Meshing Roundtable, Sandia National Laboratories. 1996.
• [13] Elber G.: Error bounded piecewise linear approximation of freeform surfaces. C-AD, 28(1), 55-57. 1996.
• [14] Luken W. L.: Tessellation of trimmed NURBS surface. CAGD, 13, 163-177. 1996.
• [15] Borouchaki H., Hecht F., Frey P. J.: Mesh gradiation control. Proc. 6th Intl Meshing Roundtable, Sandia National Laboratories, 131-141. 1997.
• [16] Chen H., Bishop J.: Delaunay triangulations for curved surfaces. Proc. 6th Int. Meshing Roundtable, Sandia National Laboratories, 115-127. 1997.
• [17] Tookey R., Cripps R.: Improved surface bounds based on derivatives. CAGD, 14, 787-791. 1997.
• [18] Vigo M., Pla N., Brunet P.: Directional adaptive surface trangulation. CAGD, 16, 107-126. 1997.
• [19] Piegl L. A., Tiler W.: Geometry-based triangulation of trimmed NURBS surfaces. C-AD, 30(1), 11-18. 1998.
• [20] Shimada K., Gossard D.: Autornatic triangular mesh generation of trimmed parametric surfaces for finite element analysis. CAGD, 15 (3), 199-222. 1998.
• [21] Sugier J.: Tesselation of NURBS surfaces controlled by local curvature. Proc. Image and Multidimensional Digital Signal Processing Workshop, Alpbach, Austria, 299-302. 1998.
• [22] Sugier J.: Triangulation of irregular parametric surfaces through adaptive refinement. PhD dissertation, Dept. Electronics, Wrocław Univ. of Technology, Wrocław , Poland (in Polish). 1999.
• [23] Shimada K., Yamada A., Itoh T.: Anisotropic triangulation of parametric surfaces via close packing of ellipsoids. Int. J. Computational Geometry and Appliations, 10(4), 417-440. 2000.