Skip to main content
SpringerLink
Log in

Efficient ray shooting and hidden surface removal

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ > 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn).

We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ > 0, we can obtain an algorithm with running time\(O(n^{1 + \varepsilon } \sqrt k )\), wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.

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

Access this article

Log in via an institution

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

References

  1. P. K. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number,Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 315–325.

  2. P. K. Agarwal and J. Matoušek, Ray Shooting and Parametric Search,Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 517–526.

  3. P. K. Agarwal and M. Sharir, Applications of a New Space Partitioning Technique,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 379–391.

    Google Scholar 

  4. P. K. Agarwal, M. van Kreveld, and M. Overmars, Intersection Queries for Curved Objects,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 41–50.

  5. B. Aronov and M. Sharir, On the Zone of a Surface in a Hyperplane Arrangement,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 13–19.

    Google Scholar 

  6. B. Chazelle, An Optimal Convex Hull Algorithm and New Results on Cuttings,Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 29–38.

  7. B. Chazelle, H. Edelsbrunner, M. Gringi, L. J. Guibas, M. Sharir, and J. Snoeyink, Ray Shooting in Polygons Using Geodesic Triangulations,Proc. 18th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 510, Springer-Verlag, Berlin, 1991, pp. 661–673.

    Google Scholar 

  8. B. Chazelle, H. Edelsbrunner, L. J. Guibas, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, Counting and Cutting Cycles of Lines and Rods in Space,Comput. Geom. Theory Appl. 1 (1992), pp. 305–323.

    Google Scholar 

  9. B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir, Lines in Space-Combinatorics, Algorithms and Applications,Proc. 21st ACM Symp. on Theory of Computing, 1989, pp. 382–393.

  10. B. Chazelle and L. J. Guibas, Visibility and Intersection Problems in Plane Geometry,Discrete Comput. Geom. 4 (1989), 551–581.

    Google Scholar 

  11. B. Chazelle, M. Sharir, and E. Welzl, Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 23–33.

  12. S. W. Cheng and R. Janardan, Space-Efficient Ray-Shooting and Intersection Searching: Algorithms, Dynamization and Applications,Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 7–16.

  13. K. Clarkson, New Applications of Random Sampling in Computational Geometry,Discrete Comput. Geom. 2 (1987), 195–222.

    Google Scholar 

  14. R. Cole and M. Sharir, Visibility Problems for Polyhedral Terrains,J. Symbolic Comput. 7 (1989), 11–30.

    Google Scholar 

  15. M. de Berg and M. H. Overmars, Hidden Surface Removal for Axis-Parallel Polyhedra,Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 252–261.

  16. M. de Berg and M. H. Overmars, Hidden Surface Removal forc-Oriented Polyhedra,Comput. Geom. Theory Appl. 1 (1992), 247–268.

    Google Scholar 

  17. M. de Berg, M. H. Overmars, and O. Schwarzkopf, Computing and Verifying Depth Orders,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 138–145.

  18. D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348–361.

    Google Scholar 

  19. D. P. Dobkin and D. Kirkpatrick, A Linear Algorithm for Determining the Separation of Convex Polyhedra,J. Algorithms 6 (1985), 381–392.

    Google Scholar 

  20. H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.

    Google Scholar 

  21. L. Guibas, M. Overmars, and M. Sharir, Ray Shooting, Implicit Point Location and Related Queries in Arrangements of Segments, Technical Report No. 443, Courant Institute of Mathematical Sciences, New York University, 1989.

  22. D. Haussler and E. Welzl, Epsilon-Nets and Simplex Range Queries,Discrete Comput. Geom. 2 (1987), 127–151.

    Google Scholar 

  23. D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM J. Comput. 12 (1983), 28–35.

    Google Scholar 

  24. M. McKenna, Worst-Case Optimal Hidden Surface Removal,ACM Trans. Graphics 6 (1987), 19–28.

    Google Scholar 

  25. M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees,BIT 30 (1990), 385–403.

    Google Scholar 

  26. M. H. Overmars and M. Sharir, Output-Sensitive Hidden Surface Removal,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 598–603.

  27. M. Pellegrini, Stabbing and Ray Shooting in 3-Dimensional Space,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 177–186.

  28. M. Pellegrini, New Results on Ray Shooting and Isotopy Classes of Lines in 3-Dimensional Space,Proc. Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 20–31.

    Google Scholar 

  29. A. Schmitt, H. Müller, and W. Leister, Ray Tracing Algorithms-Theory and Practice, in: R. A. Earnshaw (ed.),Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series, Vol. F40, Springer-Verlag, Berlin, 1988, pp. 997–1030.

    Google Scholar 

  30. O. Schwarzkopf, Ray Shooting in Convex Polytopes,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 286–295.

  31. J. Stolfi, Primitives for Computational Geometry, Ph.D. Thesis, Computer Science Department, Stanford University, 1988.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands

    M. de Berg, M. Overmars & M. van Kreveld

  2. Department of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel

    D. Halperin

  3. Department of Computer Science, University of British Columbia, 6356 Agricultural Rd, V6T 1Z2, Vancouver, BC, Canada

    J. Snoeyink

Authors
  1. M. de Berg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Halperin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Overmars
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. Snoeyink
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. M. van Kreveld
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Leonidas J. Guibas.

This research was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The first and third authors were also supported by the Dutch Organization for Scientific Research (N.W.O.).

Rights and permissions

Reprints and permissions

About this article

Cite this article

de Berg, M., Halperin, D., Overmars, M. et al. Efficient ray shooting and hidden surface removal. Algorithmica 12, 30–53 (1994). https://doi.org/10.1007/BF01377182

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation