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.
Similar content being viewed by others
References
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.
P. K. Agarwal and J. Matoušek, Ray Shooting and Parametric Search,Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 517–526.
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.
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.
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.
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.
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.
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.
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.
B. Chazelle and L. J. Guibas, Visibility and Intersection Problems in Plane Geometry,Discrete Comput. Geom. 4 (1989), 551–581.
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.
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.
K. Clarkson, New Applications of Random Sampling in Computational Geometry,Discrete Comput. Geom. 2 (1987), 195–222.
R. Cole and M. Sharir, Visibility Problems for Polyhedral Terrains,J. Symbolic Comput. 7 (1989), 11–30.
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.
M. de Berg and M. H. Overmars, Hidden Surface Removal forc-Oriented Polyhedra,Comput. Geom. Theory Appl. 1 (1992), 247–268.
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.
D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348–361.
D. P. Dobkin and D. Kirkpatrick, A Linear Algorithm for Determining the Separation of Convex Polyhedra,J. Algorithms 6 (1985), 381–392.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.
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.
D. Haussler and E. Welzl, Epsilon-Nets and Simplex Range Queries,Discrete Comput. Geom. 2 (1987), 127–151.
D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM J. Comput. 12 (1983), 28–35.
M. McKenna, Worst-Case Optimal Hidden Surface Removal,ACM Trans. Graphics 6 (1987), 19–28.
M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees,BIT 30 (1990), 385–403.
M. H. Overmars and M. Sharir, Output-Sensitive Hidden Surface Removal,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 598–603.
M. Pellegrini, Stabbing and Ray Shooting in 3-Dimensional Space,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 177–186.
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.
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.
O. Schwarzkopf, Ray Shooting in Convex Polytopes,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 286–295.
J. Stolfi, Primitives for Computational Geometry, Ph.D. Thesis, Computer Science Department, Stanford University, 1988.
Author information
Authors and Affiliations
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
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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01377182