The multi-LREP decomposition of solids and its application to a point-in-polyhedron inclusion test | The Visual Computer
Skip to main content
Springer Nature Link
Log in

The multi-LREP decomposition of solids and its application to a point-in-polyhedron inclusion test

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

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

This paper presents a scheme for decomposing polyhedra called multi-LREP. The scheme is based on the L-REP decomposition, which classifies the triangular faces of a polyhedron into a set of layered tetrahedra. In the multi-LREP these layered tetrahedra are grouped into regions of a space subdivision. The paper also describes an efficient method for constructing the L-REP decomposition and how the multi-LREP can be applied to speed up two L-REP applications: the point-in-polyhedron inclusion test and the ray-scene intersection. An experimental comparison with other point-in-polyhedron tests is presented as well.

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
¥17,985 /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 includes VAT (Japan)

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. Akenine, M., Haines, E.: Real-time Rendering, 2nd edn. A.K. Peters, Natick (2002), p. 835

    Google Scholar 

  2. de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopt, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000), p. 367

    MATH  Google Scholar 

  3. Bergen, G.: Efficient collision detection of complex deformable models using AABB tress. J. Graph. Tools 2(4), 1–13 (1997)

    MATH  Google Scholar 

  4. Feito, F.R., Torres, J.C.: Inclusion test for general polyhedra. Comput. Graph. 21(1), 23–30 (1997)

    Article  Google Scholar 

  5. Glassner, A.S.: Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl. 4(10), 15–22 (1984)

    Google Scholar 

  6. Haines, E.: Point in polygon strategies. In: Heckbert, P. (ed.) Graphics Gems IV, pp. 24–45. Academic Press, San Diego (1994)

    Google Scholar 

  7. Martínez, F., Rueda, A.J., Feito, F.R.: The multi-L-REP decomposition and its application to a point-in-polygon inclusion test. Comput. Graph. 30(6), 947–958 (2006)

    Article  Google Scholar 

  8. Ogayar, C.J., Segura, R.J., Feito, F.R.: Point in solid strategies. Comput. Graph. 29(4), 616–624 (2005)

    Article  Google Scholar 

  9. Rueda, A.J., Feito, F.R., Ortega, L.M.: Layer-based decomposition of solids and its applications. Vis. Comput. 21(6), 406–417 (2005)

    Article  Google Scholar 

  10. Rueda, A.J., Feito, F.R., Rivero, M.L.: A triangle-based representation for polygons and its applications. Comput. Graph. 26(5), 805–814 (2002)

    Article  Google Scholar 

  11. Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, San Mateo (2006), p. 993

    MATH  Google Scholar 

  12. Wang, W., Li, J., Sun, H., Wu, E.: Layer-based representation of polyhedrons for point containment test. IEEE Trans. Vis. Comput. Graph. 14(1), 73–83 (2008)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Informática, Universidad de Jaén, Campus Las Lagunillas s/n, 23071, Jaén, Spain

    Francisco Martínez, Antonio J. Rueda & Francisco R. Feito

Authors
  1. Francisco Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonio J. Rueda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francisco R. Feito
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco Martínez.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Martínez, F., Rueda, A.J. & Feito, F.R. The multi-LREP decomposition of solids and its application to a point-in-polyhedron inclusion test. Vis Comput 26, 1361–1368 (2010). https://doi.org/10.1007/s00371-009-0413-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-009-0413-6

Search

Navigation