| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Multiresolution Indexing of Triangulated Irregular Networks
July/August 2004 (vol. 10 no. 4)
pp. 484-495
Abstract—We show how to build a continuous, one-dimensional index of the points on a triangulated irregular network (TIN). The index is constructed by first finding an ordering of the triangles in which consecutive triangles share a vertex or an edge. Then, the space within each triangle is continuously indexed with a space-filling curve that begins at one vertex of the triangle and ends at another. The space-filling curve is oriented such that the first point in each triangle is a vertex shared with the previous triangle and the last point is a vertex shared with the next triangle. Furthermore, our index can be refined locally and, therefore, efficiently when the TIN is augmented by filling any face with another TIN (to make a hierarchical TIN). Such processes arise, for example, in the elaboration of detail on a graphical surface.
[1] 484 M. Abdelguerfi, C. Wynne, E. Cooper, L. Roy, and K. Shaw, Representation of 3-D Elevation in Terrain Databases Using Hierarchical Triangulated Irregular Networks: A Comparative Analysis Int'l J. Geographical Information Science, vol. 12, no. 8, pp. 853-873, 1998.[2] D.J. Abel and D.M. Mark, A Comparative Analysis of Some Two-Dimensional Orderings Int'l J. Geographical Information Systems, vol. 4, no. 1, pp. 21-31, 1990.[3] E.M. Arkin, M. Held, J.S.B. Mitchell, and S.S. Skiena, Hamiltonian Triangulations for Fast Rendering Proc. Visualization '95, 1995.[4] J.J. Bartholdi III and P. Goldsman, Continuous Indexing of Hierarchical Subdivisions of the Globe Int'l J. Geographical Information Science, vol. 15, no. 6, pp. 489-522, 2001.[5] J.J. Bartholdi III and P. Goldsman, Vertex-Labeling Algorithms for the Hilbert Spacefilling Curve Software Practice and Experience, vol. 31, pp. 395-408, 2001.[6] J.J. Bartholdi III and L.K. Platzman, An$O \left( n \log n \right)$Planar Travelling Salesman Heuristic Based on Spacefilling Curves Operations Research Letters, vol. 1, pp. 121-125, 1982.[7] J.J. Bartholdi III and L.K. Platzman, Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space Management Science, vol. 34, no. 3, pp. 291-305, 1988.[8] J.J. Bartholdi III, L.K. Platzman, R.L. Collins, and W.H. Warden, A Minimal Technology Routing System for Meals-on-Wheels Interfaces, vol. 13, pp. 1-8, June 1983.[9] A. Bogomjakov and C. Gotsman, Universal Rendering Sequences for Transparent Vertex Caching of Progressive Meshes Computer Graphics Forum, vol. 21, no. 2, pp. 137-148, 2002.[10] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. New York: Elsevier North Holland, Inc., 1979.[11] L. De Floriani, P. Magillo, and E. Puppo, Compressing Triangulated Irregular Networks Geoinformatica, vol. 4, no. 2, pp. 67-88, Mar. 2000.[12] L. De Floriani and E. Puppo, Hierarchical Triangulation for Multiresolution Surface Description ACM Trans. Graphics, vol. 14, no. 4, pp. 363-411, Oct. 1995.[13] F. Evans, S. Skiena, and A. Varshney, Optimizing Triangle Strips for Fast Rendering Proc. IEEE Visualization '96, pp. 319-326, 1996.[14] M.F. Goodchild and A.W. Grandfield, Optimizing Raster Storage: An Examination of Four Alternatives Proc. Auto Carto 6, vol. 2, pp. 400-407, 1983.[15] C. Gotsman and M. Lindenbaum, On the Metric Properties of Discrete Spacefilling Curves Proc. Int'l Conf. Pattern Recognition, vol. 3, pp. 98-102, 1994.[16] C. Gotsman and M. Lindenbaum, On the Metric Properties of Discrete Spacefilling Curves IEEE Trans. Image Processing, vol. 5, no. 5, pp. 794-797, May 1996.[17] M. Isenburg, Triangle Strip Compression Proc. Graphics Interface 2000, pp. 197-204, May 2000.[18] Z. Karni, A. Bogomjakov, and C. Gotsman, Efficient Compression and Rendering of Multi-Resolution Meshes Proc. IEEE Visualization 2002, pp. 347-354, 2002.[19] R. Laurini and D. Thompson, Fundamentals of Spatial Information Systems. San Diego, Calif.: Academic Press, 1992.[20] A.W.F. Lee, W. Sweldens, P. Schröder, L. Cowsar, and D. Dobkin, Maps: Multiresolution Adaptive Parameterizaton of Surfaces Proc. SIGGRAPH '98, pp. 95-104, 1998.[21] W.G. Nulty and J.J. Bartholdi III, Robust Spatial Searching with Spacefilling Curves Advances in GIS Research, Proc. Sixth Int'l Symp. Spatial Data Handling, T.C. Waugh and R.G. Healey, eds., Sept. 1994.[22] L.K. Platzman and J.J. Bartholdi III, Spacefilling Curves and the Planar Travelling Salesman Problem J. ACM, vol. 36, no. 4, pp. 717-737, Oct. 1989.[23] J. Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 1, pp. 47-61, Jan.-Mar. 1999.[24] H. Sagan, Space-Filling Curves. New York: Springer-Verlag, 1994.[25] W. Sierpinski, Sur une Nouvelle Courbe Qui Remplit Toute une Aire Plaine Bull. Acad. Sci. Cracovie, Serie A, pp. 462-478, 1912.[26] G. Taubin and J. Rossignac, Geometric Compression through Topological Surgery ACM Trans. Graphics, vol. 17, no. 2, pp. 84-115, Apr. 1998.[27] C. Touma and C. Gotsman, Triangle Mesh Compression Proc. Graphics Interface 1998, pp. 26-34, 1998,[28] L. Velho, L.H. de Figueiredo, and J. Gomes, Hierarchical Generalized Triangle Strips The Visual Computer, vol. 15, no. 1, pp. 21-35, 1999.
Index Terms:
Triangulated irregular network, TIN, space-filling curve, hierarchical triangulation, multiresolution triangulation, triangle mesh, spatial index.
Citation:
John J. Bartholdi, Paul Goldsman, "Multiresolution Indexing of Triangulated Irregular Networks," IEEE Transactions on Visualization and Computer Graphics, vol. 10, no. 4, pp. 484-495, July/Aug. 2004, doi:10.1109/TVCG.2004.14
