Skip to main content
SpringerLink
Log in

Shape reconstruction with Delaunay complex

Invited paper

  • Conference paper
  • First Online:
LATIN'98: Theoretical Informatics (LATIN 1998)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1380))

Included in the following conference series:

Abstract

The reconstruction of a shape or surface from a finite set of points is a practically significant and theoretically challenging problem. This paper presents a unified view of algorithmic solutions proposed in the computer science literature that are based on the Delaunay complex of the points.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. P. S. Alexandrov. über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung. Math. Ann. 98 (1928), 617–635.

    Article  MathSciNet  Google Scholar 

  2. N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Manuscript, 1998.

    Google Scholar 

  3. N. Amenta, M. Bern and D. Eppstein. The crust and the Β-skeleton: combinatorial curve reconstruction. Graphical Models and Image Process., to appear.

    Google Scholar 

  4. D. Attali. r-regular shape reconstruction from unorganized points. In “Proc. 13th Ann. Sympos. Comput. Geom., 1997”, 248–253.

    Google Scholar 

  5. F. Aurenhammer. Voronoi diagrams — a study of a fundamental geometric data structure. ACM Comput. Surveys 23 (1991), 345–405.

    Article  Google Scholar 

  6. D. Avis and J. Horton. Remarks on the sphere of influence graph. In “Proc. Conf. Discrete Geom. Convexity”, J. E. Goodman et al. (eds.), Ann. New York Acad. Sci. 440 (1985), 323–327.

    Google Scholar 

  7. C. L. Bajaj, F. Bernardini and G. Xu. Automatic reconstruction of surfaces and scalar fields from 3D scans. Comput. Graphics, Proc. siggraph 1995, 109–118.

    Google Scholar 

  8. F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using α-shapes. In “Proc. 9th Canadian Conf. Comput. Geom., 1997”, 193–198.

    Google Scholar 

  9. J.-D. Boissonnat. Geometric structures for three-dimensional shape representation. ACM Trans. Graphics 3 (1984), 266–286.

    Article  Google Scholar 

  10. J.-D. Boissonnat and B. Geiger. Three-dimensional reconstruction of complex shapes based on the Delaunay triangulation. In “Proc. Biomedical Image Process. Biomed. Visualization, 1993”, 964–975.

    Google Scholar 

  11. J. Brandt and V. R. Algazi. Continuous skeleton computation by Voronoi diagram. Comput. Vision, Graphics, Image Process. 55 (1992), 329–338.

    MATH  Google Scholar 

  12. C. Bregler and S. M. Omohundro. Nonlinear manifold learning for visual speech recognition. In “Proc. 5th Internat. Conf. Comput. Vision, 1995”, 494–499.

    Google Scholar 

  13. M. Burns. Automated Fabrication. Improving Productivity in Manufacturing. Prentice Hall, Englewood Cliffs, New Jersey, 1993.

    Google Scholar 

  14. L. P. Chew. Guaranteed-quality mesh generation for curved surfaces. In “Proc. 9th Ann. Sympos. Comput. Geom., 1993”, 274–280.

    Google Scholar 

  15. B. Curless and M. Levoy. A volumetric method for building complex models from range images. Comput. Graphics, Proc. siggraph 1996, 303–312.

    Google Scholar 

  16. W. D'Arcy Thompson. Growth and Form. Cambridge Univ. Press, 1917.

    Google Scholar 

  17. H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom. 13 (1995), 415–440.

    MATH  MathSciNet  Google Scholar 

  18. H. Edelsbrunner. Surface reconstruction by wrapping finite sets in space. Rept. rgi-tech-96-001, Raindrop Geomagic, Urbana, Illinois, 1996.

    Google Scholar 

  19. H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Inform. Theory 29 (1983), 551–559.

    Article  MathSciNet  MATH  Google Scholar 

  20. H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graphics 9 (1990), 66–104.

    Article  MATH  Google Scholar 

  21. H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graphics 13 (1994), 43–72.

    Article  MATH  Google Scholar 

  22. H. Edelsbrunner, G. Rote and E. Welzl. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoret. Comput. Sci. 66 (1989), 157–180.

    Article  MathSciNet  MATH  Google Scholar 

  23. H. Edelsbrunner and N. R. Shah. Triangulating topological spaces. Internat. J. Comput. Geom. Appl. 7 (1997), 365–378.

    Article  MathSciNet  MATH  Google Scholar 

  24. A. Flores. über die Existenz n-dimensionaler Komplexe, die nicht in den ℝ2n topologisch einbettbar sind. Ergeb. Math. Kolloq. 5 (1932/33), 17–24.

    Google Scholar 

  25. H. Fuchs, Z. M. Kedem and S. P. Uselton. Optimal surface reconstruction from planar contours. Commun. ACM 20 (1977), 693–702.

    Article  MathSciNet  MATH  Google Scholar 

  26. H. Hoppe, T. de Rose, T. Duchamp, J. McDonald, and W. Stützle. Surface reconstruction from unorganized points. Comput. Graphics, Proc. siggraph 1992, 71–78.

    Google Scholar 

  27. D. G. Kirkpatrick and J. D. Radke. A framework for computational morphology. In Computational Morphology, G. Toussaint (ed.), Elsevier (1985), 217–248.

    Google Scholar 

  28. B. Lee and F. M. Richards. The interpretation of protein structures: estimation of static accessibility. J. Mol. Biol. 55 (1971), 379–400.

    Article  Google Scholar 

  29. J. Leray. Sur la forme des espaces topologiques et sur les point fixes des représentations. J. Math. Pures Appl. 24 (1945), 95–167.

    MATH  MathSciNet  Google Scholar 

  30. J. Liang, H. Edelsbrunner and C. Woodward. Anatomy of protein pockets and cavities: measurement of binding site geometry and implications for ligand design. Manuscript, 1997.

    Google Scholar 

  31. S. K. Lodha and R. Franke. Scattered data techniques for surfaces. In Scientific Visualization: Methods and Applications, G. M. Nielson, H. Hagen and F. Post (eds.), Springer-Verlag, Heidelberg, to appear.

    Google Scholar 

  32. W. E. Lorensen and H. E. Cline. Marching cubes: a high resolution 3D surface construction algorithm. Comput. Graphics 21, Proc. siggraph 1987, 163–169.

    Google Scholar 

  33. T. Martinetz and K. Schulten. Topology representing networks. Neural Networks 7 (1994), 507–522.

    Article  Google Scholar 

  34. M. Melkemi. A-shapes of a finite point set. Correspondence in “Proc. 13th Ann. Sympos. Comput. Geom., 1997”, 367–369.

    Google Scholar 

  35. D. Meyers, S. Skinner and K. Sloan. Surfaces from contours. ACM Trans. Graphics 11 (1992), 228–258.

    Article  MATH  Google Scholar 

  36. Y.-L. O, A. Toet, D. Foster, H. J. A. M. Heijmans and P. Meer (eds.) Shape in Picture. Mathematical Description of Shape in Grey-level images. NATO ASI Series F: Computer and Systems Sciences 126, Springer-Verlag, Berlin, 1994.

    MATH  Google Scholar 

  37. Raindrop Geomagic, Inc. www.geomagic.com.

    Google Scholar 

  38. G. P. Robinson, A. C. F. Colchester, L. D. Griffin and D. J. Hawkes. Integrated skeleton and boundary shape representation for medical image interpretation. In “Proc. European Conf. Comput. Vision, 1992”, 725–729.

    Google Scholar 

  39. R. Thom. Structural Stability and Morphogenesis. Addison Wesley, Reading, Massachusetts, 1989.

    MATH  Google Scholar 

  40. E. R. van Kampen. Komplexe in euklidischen Räumen. Abh. Math. Sem. Univ. Hamburg 9 (1933), 72–78.

    Article  Google Scholar 

  41. R. C. Veltkamp. Closed Object Boundaries from Scattered Points. Springer-Verlag, Berlin, 1994.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. Comput. Sci., Univ. Illinois at Urbana-Champaign, and Raindrop Geomagic, Champaign, Illinois, USA

    Herbert Edelsbrunner

Authors
  1. Herbert Edelsbrunner
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Cláudio L. Lucchesi Arnaldo V. Moura

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Edelsbrunner, H. (1998). Shape reconstruction with Delaunay complex. In: Lucchesi, C.L., Moura, A.V. (eds) LATIN'98: Theoretical Informatics. LATIN 1998. Lecture Notes in Computer Science, vol 1380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054315

Download citation

  • DOI: https://doi.org/10.1007/BFb0054315

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64275-6

  • Online ISBN: 978-3-540-69715-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation