Four-triangles adaptive algorithms for RTIN terrain meshes. (English) Zbl 1165.65321
Summary: We present a refinement and coarsening algorithm for the adaptive representation of Right-Triangulated Irregular Network (RTIN) meshes. The refinement algorithm is very simple and proceeds uniformly or locally in triangle meshes. The coarsening algorithm decreases mesh complexity by reducing unnecessary data points in the mesh after a given error criterion is applied. We describe the most important features of the algorithms and give a brief numerical study on the propagation associated with the adaptive scheme used for the refinement algorithm. We also present a comparison with a commercial tool for mesh simplification, Rational Reducer, showing that our coarsening algorithm offers better results in terms of accuracy of the generated meshes.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Software:
MetroReferences:
| [1] | Cignoni, P.; Montani, C.; Varshney, A., A comparison of mesh simplification algorithms, Comput. Graph., 22, 1, 37-54 (1998) |
| [2] | Cignoni, P.; Rocchini, C.; Scopigno, R., Metro: measuring error on simplified surfaces, Comput. Graph. Forum, 17, 2, 167-174 (1998) |
| [3] | Bellenger, E.; Coorevits, P., Adaptive mesh refinement for the control of cost and quality in finite element analysis, Finite Elem. Anal. Des., 41, 15, 1413-1440 (2005) |
| [4] | Evans, W.; Kirkpatrick, D.; Townsend, G., Right-triangulated irregular networks, Algorithms for Geographical Information Systems. Algorithms for Geographical Information Systems, Algorithmica, 30, 2, 264-286 (2001), (special issue) · Zbl 0984.65014 |
| [5] | Li, M. H.; Cheng, H. P.; Yeh, G. T., An adaptive multigrid approach for the simulation of contaminant transport in the 3d subsurface, Comput. Geosci., 31, 8, 1028-1041 (2005) |
| [6] | P. Lindstrom, D. Koller, W. Ribarsky, L. Hodeges, N. Faust, G. Turner, Real-time, continuous level of detail rendering of height fields, in: ACM Computer Graphics, Conf. Proc. Annual Conference Series, SIGGRAPH’96, 1996; P. Lindstrom, D. Koller, W. Ribarsky, L. Hodeges, N. Faust, G. Turner, Real-time, continuous level of detail rendering of height fields, in: ACM Computer Graphics, Conf. Proc. Annual Conference Series, SIGGRAPH’96, 1996 |
| [7] | System in motion. Rational reducer. http://www.rational-reducer.com; System in motion. Rational reducer. http://www.rational-reducer.com |
| [8] | R. Pajarola, Large scale terrain visualization using the restricted quadtree triangulation, in: Proceedings IEEE Visualization, 1998, pp. 19-26; R. Pajarola, Large scale terrain visualization using the restricted quadtree triangulation, in: Proceedings IEEE Visualization, 1998, pp. 19-26 |
| [9] | R. Pajarola, M. Antonijuan, R. Lario, Quadtin: Quadtree based triangulated irregular networks, in: Proceedings IEEE Visualization, 2002, pp. 395-402; R. Pajarola, M. Antonijuan, R. Lario, Quadtin: Quadtree based triangulated irregular networks, in: Proceedings IEEE Visualization, 2002, pp. 395-402 |
| [10] | Plaza, A.; Suárez, J. P.; Padrón, M. A.; Falcón, S.; Amieiro, D., Mesh quality improvement and other properties in the four-triangles longest-edge partition, Comput. Aided Geome. Design, 21, 4, 353-369 (2004) · Zbl 1069.65530 |
| [11] | Rivara, M. C.; Iribarren, G., The 4-triangles longest-side partition of triangles and linear refinement algorithms, Math. Comp., 65, 216, 1485-1502 (1996) · Zbl 0853.65096 |
| [12] | Rossignac, J.; Borrel, P., Multiresolution 3D approximation for rendering complex scenes, (Geometric Modeling in Computer Graphics (1993), Springer Verlag), 455-465 |
| [13] | Suárez, J. P.; Plaza, A., Refinement and hierarchical coarsening schemes for triangulated surfaces, Journal of WSCG, 11 (2003), WSCG’2003, Feb. 3-7, Plzen, Czech Republic |
| [14] | Suárez, J. P.; Plaza, A.; Carey, G. F., Graph based data structures for skeleton based refinement algorithms, Commun. Numer. Methods Eng., 17, 12, 903-910 (2001) · Zbl 0995.65126 |
| [15] | Suárez, J. P.; Plaza, A.; Carey, G. F., Propagation of longest-edge mesh pattern in local adaptive refinement, Commun. Numer. Methods Eng. (2007) · Zbl 1145.65106 |
| [16] | J.P. Suárez, A. Plaza, M.A. Padrón, Mesh graph structure for longest-edge refinement algorithms, 7th International Meshing Roundtable, Michigan, USA. SAND 98-2250, Sandia National Laboratories, 1998; J.P. Suárez, A. Plaza, M.A. Padrón, Mesh graph structure for longest-edge refinement algorithms, 7th International Meshing Roundtable, Michigan, USA. SAND 98-2250, Sandia National Laboratories, 1998 |
| [17] | Velho, L.; Zorin, D., 4-8 subdivision, Computer-Aided Geometric Design, 18, 5, 397-427 (2001), Special issue on subdivision techniques · Zbl 0969.68157 |
| [18] | Wang, Y.; Renaud, J.-P.; Anderson, M. G.; Allen, C. B., A boundary and soil interface conforming unstructured local mesh refinement for geological structures, Finite Elem. Anal. Des., 40, 1429-1443 (2004) |
| [19] | Zoraster, S., A surface modeling algorithm designed for speed and ease of use with all petroleum industry data, Comput. Geosci., 29, 1175-1182 (2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
