Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Handling degenerate cases in exact geodesic computation on triangle meshes

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

The computation of exact geodesics on triangle meshes is a widely used operation in computer-aided design and computer graphics. Practical algorithms for computing such exact geodesics have been recently proposed by Surazhsky et al. [5]. By applying these geometric algorithms to real-world data, degenerate cases frequently appear. In this paper we classify and enumerate all the degenerate cases in a systematic way. Based on the classification, we present solutions to handle all the degenerate cases consistently and correctly. The common users may find the present techniques useful when they implement a robust code of computing exact geodesic paths on meshes.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Edelsbrunner, H., Mucke, E.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9(1), 66–104 (1990)

    Article  MATH  Google Scholar 

  2. Hoffmann, C.: Robustness in geometric computations. J. Comput. Info. Sci. Eng. 1(2), 143–155 (2001)

    Article  Google Scholar 

  3. Mitchell, J., Mount, D., Papadimitriou, C.: The discrete geodesic problem. SIAM J. Comput. 16(4), 647–668 (1987)

    Article  MATH  Google Scholar 

  4. Sugihara, K., Iri, M., Inagaki, H., Imai, T.: Topology-oriented implementation: an approach to robust geometric algorithms. Algorithmica 27(11), 5–20 (2000)

    Article  MATH  Google Scholar 

  5. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., Hoppe, H.: Fast exact and approximate geodesics on meshes. In: ACM SIGGRAPH 2005, pp. 553–560 (2005)

  6. Zachary, J.: Introduction to Scientific Programming. TELOS, Santa Clara, CA (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Technology, Tsinghua University, East Main Building, Beijing, 100084, China

    Yong-Jin Liu, Qian-Yi Zhou & Shi-Min Hu

Authors
  1. Yong-Jin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qian-Yi Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shi-Min Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yong-Jin Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, YJ., Zhou, QY. & Hu, SM. Handling degenerate cases in exact geodesic computation on triangle meshes. Visual Comput 23, 661–668 (2007). https://doi.org/10.1007/s00371-007-0136-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-007-0136-5

Keywords

Search

Navigation