Efficient ray shooting and hidden surface removal. (English) Zbl 0813.68160
This paper deals with the computational ray-shooting problem for polyhedral objects in \(R^ 3\). With preprocessing, efficient (i.e. logarithmic) query time algorithms are shown for axis-parallel polyhedra, curtains (hanging vertically down from a segment), horizontal triangles whose angles cannot be too small, as well as general triangles in \(R^ 3\). As a novel feature, they do not assume a depth order between the objects (as in the painter’s algorithm).
Reviewer: H.Brönnimann (Palaiseau)
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
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. · Zbl 0766.68131 |
| [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. · Zbl 0784.68087 |
| [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. · Zbl 0764.68166 |
| [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. · Zbl 0769.68119 |
| [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. · Zbl 0748.68082 |
| [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. · Zbl 0695.68033 · doi:10.1007/BF02187747 |
| [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. · Zbl 0788.68141 |
| [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. · Zbl 0800.68362 |
| [13] | K. Clarkson, New Applications of Random Sampling in Computational Geometry,Discrete Comput. Geom. 2 (1987), 195-222. · Zbl 0615.68037 · doi:10.1007/BF02187879 |
| [14] | R. Cole and M. Sharir, Visibility Problems for Polyhedral Terrains,J. Symbolic Comput. 7 (1989), 11-30. · doi:10.1016/S0747-7171(89)80003-3 |
| [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. · Zbl 0752.68083 |
| [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. · Zbl 0804.68150 |
| [18] | D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348-361. · Zbl 0646.68077 · doi:10.1016/0196-6774(87)90015-0 |
| [19] | D. P. Dobkin and D. Kirkpatrick, A Linear Algorithm for Determining the Separation of Convex Polyhedra,J. Algorithms 6 (1985), 381-392. · Zbl 0577.52004 · doi:10.1016/0196-6774(85)90007-0 |
| [20] | H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987. · Zbl 0634.52001 |
| [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. · Zbl 0619.68056 · doi:10.1007/BF02187876 |
| [23] | D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM J. Comput. 12 (1983), 28-35. · Zbl 0501.68034 · doi:10.1137/0212002 |
| [24] | M. McKenna, Worst-Case Optimal Hidden Surface Removal,ACM Trans. Graphics 6 (1987), 19-28. · doi:10.1145/27625.27627 |
| [25] | M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees,BIT 30 (1990), 385-403. · Zbl 0696.68068 · doi:10.1007/BF01931656 |
| [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. · Zbl 0765.68212 |
| [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. |
| [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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
