article

Free access

Hierarchical triangulation for multiresolution surface description

Authors:

Leila De Floriani,

Enrico PuppoAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 14, Issue 4

Pages 363 - 411

https://doi.org/10.1145/225294.225297

Published: 01 October 1995 Publication History

Abstract

A new hierarchical triangle-based model for representing surfaces over sampled data is proposed, which is based on the subdivision of the surface domain into nested triangulations, called a hierarchical triangulation (HT). The model allows compression of spatial data and representation of a surface at successively finer degrees of resolution. An HT is a collection of triangulations organized in a tree, where each node, except for the root, is a triangulation refining a face belonging to its parent in the hierarchy. We present a topological model for representing an HT, and algorithms for its construction and for the extraction of a triangulation at a given degree of resolution. The surface model, called a hierarchical triangulated surface (HTS) is obtained by associating data values with the vertices of triangles, and by defining suitable functions that describe the surface over each triangular patch. We consider an application of a piecewise-linear version of the HTS to interpolate topographical data, and we describe a specialized version of the construction algorithm that builds an HTS for a terrain starting from a high-resolution rectangular grid of sampled data. Finally, we present an algorithm for extracting representations of terrain at variable resolution over the domain.

References

[1]

AGARWAL, P. K., AND SURI, S. 1994. Surface approximation and geometric partitions. In Proceedings of the 5th ACM SIAM,Symposium on Discrete Algorithms. ACM, New York, pp. 24 33.

Digital Library

[2]

At;~;^aWAI., A., GUmAS, L. J., SAXE, J., AND SHOR, P. 1989. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4,591-604.

Digital Library

[3]

BANK. R. E. 1986. A posteriori error estimate. Adaptive local mesh refinement and multigrid iteration. In Multigrid Methods II. Lecture Notes in Mathematics, 1228, Springer-Verlag, New York, 7 22.

[4]

B^RaER^, R., AND VAZQUEZ, A. N. 1984. A hierarchical method for representing relief. In Proceedings of the Peeora IX Symposium on Spatial Information Technologies for Remote ~ensing Today and Tomorrow (Sioux Falls, S.D., Oct.), 87-92.

[5]

BERTOLO~IY), M., DE FLORIANI, L., AND MARZANO, P. 1995a. Pyramidal simplicial complexes. In 3rd ACM Symposium on Solid Modeling and Applications (Salt Lake City, Utah, May 17-19). ACM, New York, 153 162.

Digital Library

[6]

BERTOLOTTO, M., DE FLOR1ANI, L., AND MARZANO, P. 1995b. A unifying framework for multilevel description of spatial data. In Spatial Information Theory--A Theoretical Basis for GIS (Proceedings COS1T95), A. U. Frank and W. Kuhn, Eds., Lecture Notes in Computer Science 988, Springer, New York, 259-278.

[7]

BERTOLOTTO, M., DE FLORIANI, L., AND PUPPO, E. 1994. Hierarchical hypersurface modeling. In IGIS 94: Geographic Information Systems, J. Nievergelt, T. Roos, H. Schek, and P. Widmayer, Eds. Lecture Notes in Computer Science, 884. Springer-Verlag, New York, 88 97.

Digital Library

[8]

BERTOLOq'FO, M., MAGILLO, P., DE FLOR{ANI, L. 1995. Overlapping hierarchical maps. In Proceedings 3rd ACM Workshop on Advances in Geographic Information Systems (Baltimore, Md., Dec. 1-2).

[9]

CHEN, Z. T., AND TOBLER, W. R. 1986. Quadtree representation of digital terrain. In Proceedings of Autocarto (London), 475 484.

[10]

C1GNONI, r., PuPPO, E., AND SCOPIGNO, R. 1995. Representation and visualization of terrain surfaces at variable resolution. In Scientific Visualization 95, R. Scateni, Ed., World Scientific, Singapore, 50-68.

[11]

CIGNONI, P., DE FLORIANI, L., MONTANI, C., PuPPo, E, AND SCOPIGNO, R. 1994. Multiresolution modeling and visualization of volume data based on simplicial complexes. In Proceedings of the 1994 ACM Symposium on Volume Visualization (Washington, D.C., Oct. 17 18). ACM, New York, 19-26.

Digital Library

[12]

DE BERG, M., AND DOBRINDT, K. T. G. 1995. On the levels of detail in terrains. In 11th ACM Symposium on Computational Geometry (Vancouver, B.C., June 5-7). ACM, New York.

Digital Library

[13]

DE FLORIANI, L. 1989. A pyramidal data structure for triangle-based surface description. IEEE Comput. Graph. Appl. (Mar.), 67-78.

Digital Library

[14]

DE FLORtANI, L., AND MAGILLO, P. 1995. Horizon computation on a hierarchical triangulated terrain model. Visual Comput. 11, 134 149.

[15]

DE FLORIANI, L., AND PuPPo, E. 1992. A hierarchical triangle-based model for terrain description. In Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, A. U. Frank, I. Campari, and U. Formentini, Eds. Lecture Notes in Computer Science, 639. Springer-Verlag, New York, 236-251.

Digital Library

[16]

DE FLORIANI, L., MIRRA, D., AND PuPPo, E. 1993. Extracting contour lines from a hierarchical surface model. Comput. Graph. Forum. (EUROGRAPHICS Conference Issue) 12, 3 (Sept.), 249-260.

[17]

DE FLORIANI, L., FALCIDIENO, B., PIENOVl, C., AND NAGY, G. 1984. A hierarchical data structure for surface approximation. Comput. Graph. 8, 2, 475-484.

[18]

DE FLORIANI, L., GATTORNA, G., MARZANO, P., AND PUPPO, E. 1994. Spatial queries on a hierarchical terrain model. In Proceedings of the 6th International Symposium on Spatial Data Handling (Edinburgh, U.K., Sept. 5 9), 819-834.

[19]

DOUGLAS, D. H., AND PEUCKER, T. K. 1973. Algorithms for the reduction of the number of points required to represent a line or its caricature. Can. Cartogr. 10, 2, 112-122.

[20]

DYN, N., LEVlN, D., AND GREGORY, J. A. 1990. A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. 9, 2 (Apr.), 160-169.

Digital Library

[21]

EDELSBRUNNER, H. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag, New York.

Digital Library

[22]

EDEI,SBRUNNER, H., AND TAN, T. S. 1992. An upper bound for conforming Delaunay triangulations. In Proceedings of the 8th ACM Symposium on Computational Geometry. ACM, New York, 53-62.

Digital Library

[23]

FARIN, G. 1986. Triangular Bernstein-B6zier patches. Comput. Aided Geom. Des. 3, 2, 83-128.

Digital Library

[24]

FEKETE, G., AND DAVIS, L. S. 1984. Property spheres: A new representation for 3-D object recognition. In Proceedings of the Workshop on Computer Vision: Representation and Control. CS Press, Los Alamitos, Calif., 192-201.

[25]

FONG, P., AND SE1DEL, H.-P. 1993. An implementation of triangular B-spline surfaces over arbitrary triangulations. Comput. Aided Geom. Des. 10, 267-275.

Digital Library

[26]

FOWLER, R. J., AND LITTLE, J. J. 1979. Automatic extraction of irregular network digital terrain models. Comput. Graph. 13, 3 (Aug.), 199-207.

Digital Library

[27]

GOMEZ, D., AND GUZM_~, A. 1979. Digital model for three-dimensional surface representation. Geo-Processing 1, 53-70.

[28]

GOODCmL9, M. F., AND SHIREN, Y. 1992. A hierarchical spatial data structure for global geographic information systems. CVGIP--Graph. Models Image Process. 54, 1 (Jan.), 31-44.

Digital Library

[29]

Gum~, L. J., ~,'~o STOLFI, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 74-123.

Digital Library

[30]

HERSHBERGER, J., x~o SNOEYINK, J. 1992. Speeding up the Douglas-Peucker line simplification algorithm. In Proceedings of the 5th International Symposium on Spatial Data Handling (Charleston, S.C., Aug. 3-7), 134-143.

[31]

I~Rr~~ATRtCK, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 28-35.

[32]

LEE, J. 1991. Comparison of existing methods for building triangular irregular network models of terrain from grid digital elevation models. Int. J. Geog. Inf. Syst. 5, 3, 267-285.

[33]

POTTMANN, H., ~O Ecg, M. 1990. Modified multiquadric methods for scattered data interpolation over a sphere. Comput. Aided Geom. Des. 7, 313-321.

Digital Library

[34]

PREPARATA, F. P., AND SHAMOS, M. I. 1985. Computational Geometry: An Introduction. Springer-Verlag, Berlin.

Digital Library

[35]

RENKA, R. J., ^~o CLIniC, A. K. 1984. A triangle-based CI interpolation method. Rocky MT J. Math. 14, 1, 223-237.

[36]

RIPPA, S. 1990. Minimal roughness property of Delaunay triangulation. Comput. Aided Geom. Des. 7, 489-497.

Digital Library

[37]

RIPPA, S. 1992. Adaptive approximations by piecewise linear polynomials on triangulations of subsets of scattered data. SIAM J. Sci. Stat. Comput. 13, 1, 1123-1141.

Digital Library

[38]

SAMET, H. 1990. Applications of Spatial Data Structures. Addison-Wesley, Reading, Mass.

Digital Library

[39]

SCARLATOS, L. L., AND PAVLIDIS, T. 1992. Hierarchical triangulation using cartographic coherence. CVGIP: Graph. Models Image Process. 54, 2, 147-161.

Digital Library

[40]

SCHUMAKER, L. L. 1993. Computing optimal triangulations using simulated annealing. Comput. Aided Geom. Des. 10, 329-345.

Digital Library

[41]

SEIDEL, H. P. 1992. Polar forms and triangular B-spline surfaces. In Computing in Euclidean Geometry, D.-Z. Du and F. Hwang, Eds. World Scientific, Singapore.

[42]

SILVESTER, P. P., AND FERI~RI, R. L. 1990. Finite Elements for Electrical Engineers. 2nd ed. Cambridge University Press, New York.

[43]

VON HERZEN, B., AND BARR, A. H. 1987. Accurate triangulations of deformed, intersecting surfaces. Comput. Graph. 21, 4 (July), 103-110.

Digital Library

[44]

Woo, T. C. 1985. A combinatorial analysis of boundary data structure schemata. IEEE Comput. Graph. Appl. 5, 3, 19-27.

Digital Library

Cited By

Mazaheri HGoli SNourollah A(2024)Path planning in three-dimensional space based on butterfly optimization algorithmScientific Reports10.1038/s41598-024-52750-914:1Online publication date: 28-Jan-2024
https://doi.org/10.1038/s41598-024-52750-9
GharehTappeh ZPeng Q(2021)Simplification and unfolding of 3D mesh models: review and evaluation of existing toolsProcedia CIRP10.1016/j.procir.2021.05.023100(121-126)Online publication date: 2021
https://doi.org/10.1016/j.procir.2021.05.023
Zhang LShe JTan JWang BSun Y(2019)A Multilevel Terrain Rendering Method Based on Dynamic Stitching StripsISPRS International Journal of Geo-Information10.3390/ijgi80602558:6(255)Online publication date: 30-May-2019
https://doi.org/10.3390/ijgi8060255
Show More Cited By

Index Terms

Hierarchical triangulation for multiresolution surface description
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Recommendations

Well-Centered Triangulation

Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs. We prove that well-centered meshes also have optimality ...
Single-strip triangulation of manifolds with arbitrary topology
SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

This video illustrates a new method for subdividing the surface of a triangulated 3d polyhedron, without changing the geometry of the model, so that the triangles of the subdivided mesh can be ordered into a single triangle strip. Our method guarantees ...
Multiresolution Surface Modeling Based on Hierarchical Triangulation

This paper describes a sequential multiresolution surface modeling technique. The initial model consists in a surface triangulation resulting from the integration of a set of range views. Thereafter, a hierarchical triangulation algorithm iteratively ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 14, Issue 4

Oct. 1995

101 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/225294

Editor:
Andrew Glassner
Microsoft Research, Redmond, WA

Issue’s Table of Contents

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1995

Published in TOG Volume 14, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

111
Total Citations
View Citations
1,239
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)12

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mazaheri HGoli SNourollah A(2024)Path planning in three-dimensional space based on butterfly optimization algorithmScientific Reports10.1038/s41598-024-52750-914:1Online publication date: 28-Jan-2024
https://doi.org/10.1038/s41598-024-52750-9
GharehTappeh ZPeng Q(2021)Simplification and unfolding of 3D mesh models: review and evaluation of existing toolsProcedia CIRP10.1016/j.procir.2021.05.023100(121-126)Online publication date: 2021
https://doi.org/10.1016/j.procir.2021.05.023
Zhang LShe JTan JWang BSun Y(2019)A Multilevel Terrain Rendering Method Based on Dynamic Stitching StripsISPRS International Journal of Geo-Information10.3390/ijgi80602558:6(255)Online publication date: 30-May-2019
https://doi.org/10.3390/ijgi8060255
Marks DElmore PBlain CBourgeois BPetry FFerrini V(2017)A variable resolution right TIN approach for gridded oceanographic dataComputers & Geosciences10.1016/j.cageo.2017.07.008109:C(59-66)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1016/j.cageo.2017.07.008
Boots BShiode N(2016)Recursive Voronoi DiagramsEnvironment and Planning B: Planning and Design10.1068/b1298430:1(113-124)Online publication date: 2-Dec-2016
https://doi.org/10.1068/b12984
Gerace SErhart KKassab ADivo E(2014)A model-integrated localized collocation meshless method for large scale three-dimensional heat transfer problemsEngineering Analysis with Boundary Elements10.1016/j.enganabound.2014.01.01445(2-19)Online publication date: Aug-2014
https://doi.org/10.1016/j.enganabound.2014.01.014
Stuetzle CFranklin W(2012)Representing Terrain with Mathematical OperatorsAdvances in Spatial Data Handling10.1007/978-3-642-32316-4_10(143-155)Online publication date: 3-Nov-2012
https://doi.org/10.1007/978-3-642-32316-4_10
Bader MBader M(2012)Refinement Trees and Space-Filling CurvesSpace-Filling Curves10.1007/978-3-642-31046-1_9(129-142)Online publication date: 1-Aug-2012
https://doi.org/10.1007/978-3-642-31046-1_9
Bader MBader M(2012)Space-Filling Curves in 3DSpace-Filling Curves10.1007/978-3-642-31046-1_8(109-127)Online publication date: 1-Aug-2012
https://doi.org/10.1007/978-3-642-31046-1_8
Bader MBader M(2012)Further Space-Filling CurvesSpace-Filling Curves10.1007/978-3-642-31046-1_7(93-108)Online publication date: 1-Aug-2012
https://doi.org/10.1007/978-3-642-31046-1_7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents