Abstract
We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems:
-
1.
Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles.
-
2.
Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term.
-
3.
Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term.
-
4.
Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra.
-
5.
Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal. Partitioning arrangements of lines, I: An efficient deterministic algorithm.Discrete & Computational Geometry, 5:449–483, 1990.
P. K. Agarwal. Partitioning arrangements of lines, II: Applications.Discrete & Computational Geometry, 5:533–573, 1990.
J. Arvo and D. Kirk. Fast ray tracing by ray classification, In M. C. Stone, editor,SIGGRAPH '87 Conference Proceedings, pages 55–63, 1987.
B. Aronov, J. Matoušek, and M. Sharir. On the sum of squares of cell complexities in hyperplane arrangements. InProceedings of the 7th ACM Symposium on Computational Geometry, pages 307–313, 1991.
B. Aronov, M. Pellegrini, and M. Sharir. On the zone of an algebraic surface in a hyperplane arrangement.Discrete & Computational Geometry. To appear. Preliminary version inProceedings of the 1991 Workshop on Algorithms and Data Structures, pages 13–19. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991.
P. K. Agarwal and M. Sharir. Applications of a new space partitioning technique. InProceedings of the 1991 Workshop on Algorithms and Data Structures, pages 379–391. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991.
M. Bern, D. Dobkin, D. Eppstein, and R. Grossman. Visibility with a moving point. InProceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, pages 107–117, 1990.
M. Bern. Hidden surface removal for rectangles. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 183–192, 1988.
B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. InProceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 590–600, 1988.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Lines in space: combinatorices, algorithms and applications. InProceedings of the 21st Symposium on Theory of Computing, pages 382–393, 1989.
B. Chazelle.Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity, pages 145–156. Lecture Notes in Computer Sciences, Volume 185. Springer-Verlag, Berlin, 1985.
B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 586–591, 1989.
B. Chazelle. An optimal convex hull algorithm and new results on cuttings. InProceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 29–38, 1991.
K. L. Clarkson. New applications of random sampling in computational geometry.Discrete & Computational Geometry, 2:195–222, 1987.
K. L. Clarkson. A randomized algorithm for closest-point queries.SI AM Journal on Computing, 17:830–847, 1988.
R. Cole and M. Sharir. Visibility Problems for Polyhedral Terrains. Technical Report 266, CIMS, December 1986.
B. Chazelle and M. Sharir. An Algorithm for Generalized Point Location and Its Applications. Technical Report 153, Robotics Laboratory, Courant Institute of Mathematical Sciences, May 1988.
B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 23–33, 1990.
M. de Berg, D. Halperlin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficent ray-shooting and hidden surface removal. InProceedings of the 7th ACM Symposium on Computational Geometry, pages 21–30, 1991.
D. Dobkin and D. Kirkpatrick. Determining the separation of preprocessed polyhedra: a unified approach. InProceedings of the 17th International Colloquium on Automata,Languages and Programming, pages 400–413, 1990.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
[EGS] H. Edelsbrunner, L. Guibas, and M. Sharir. The complexity of many faces in arrangements of lines and segments. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 44–55, 1988.
H. Edelsbrunner, H. Mauer, F. Preparata, E. Welzl, and D. Wood. Stabbing line segments.BIT, 22:274–281, 1982.
H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15:341–363, 1986.
A. S. Glassner, editor.Ray Tracing. Academic Press, New York, 1989.
L. Guibas, M. Overmars, and M. Sharir. Ray Shooting, Implicit Point Location and Related Queries in Arrangements of Segments. Technical Report TR433, Courant Institute, 1989.
T. L. Kay and J. T. Kajiya. Ray tracing complex scenes.Computer Graphics, 20:269–278, 1986.
J. Matoušek. Cutting hyperplane arrangements. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 1–9, 1990.
D. S. Mitrinovic.Analytic Inequalities. Springer-Verlag, New York, 1970.
M. McKenna and J. O'Rourke. Arrangements of lines in 3-space: A data structure with applications. InProceedings of the 4th Annual Symposium on Computational Geometry, pages 371–380, 1988.
D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra.Theoretical Computer Science, 7:217–236, 1978.
K., Mehlhorn and K. Simon. Intersecting two polyhedra one of which is convex. InProceedings of Fundamentals of Computation Theory, pages 534–542. Lecture Notes in Computer Science, Volume 199. Springer-Verlag, Berlin, 1985.
M. Overmars and M. Sharir, Output-sensitive hidden surface removal. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 598–603, 1989.
M. H. Overmars and M. Sharir. Merging visibility maps. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 1681–176, 1990.
M. Pellegrini. Stabbing and ray shooting in 3-dimensional space. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 177–186, 1990.
M. Pellegrini. Combinatorial and Algorithmic Analysis of Stabbing and Visibility Problems in 3-Dimensional Space. Ph.D. thesis, New York University-Courant Institute of Mathematical Sciences, February 1991. Report Number 241, Robotics Laboratory, Courant Institute.
M. Pellegrini. Ray shooting and isotopy classes of lines in 3-dimensional space. In Proceedings of the1991, pages 20–31. Lecture Notes in Computer Science, Volume 519. Springer-Verlag, Berlin, 1991.
M. Pellegrini and P. Shor. Finding stabbing lines in 3-dimensional space. InProceedings of the Second SIAM-ACM Symposium on Discrete Algorithms, pages 24–31, 1991.
M. S. Paterson and F. F. Yao. Binary partitions with applications to hidden surface removal and solid modelling. InProceedings of the 5th ACM Symposium on Computational Geometry, pages 23–32, 1989.
S. D. Roth. Ray casting for modeling solids.Computer Graphics and Image Processing, 18:109–144, 1982.
J. H. Reif and S. Sen. An efficient output-sensitive hidden-surface removal algorithm and its parallelization. InProceedings of the 4th A CM Symposium on Computational Geometry, pages 193–200, 1988.
R. Seidel. Constructing higher-dimensional convex hulls at logarithmic cost per face. InProceedings of the 18th Annual Symposium on Theory of Computing, pages 404–413,1986.
M. Sharir. The shortest watchtower and related problems for polyhedral terrains.Information Processing Letters, 29:265–270, 1988.
A. Schmitt, H. Muller, and W. Leister. Ray tracing algorithms-theory and practice. In R. A. Earnshaw, editor,Theoretical Foundations of Computer Graphics and CAD, pages 997–1030. NATO ASI, Volume 40. Springer-Verlag, New York, 1988.
D. M. H. Sommerville.Analytical geometry of Three Dimensions. Cambridge University Press, Cambridge, 1951.
J. T. Schwartz and M. Sharir. On the piano mover's problem: II. General techniques for computing topological properties of real algebraic manifolds.Advances in Applied Mathematics, 4:298–35l, 1983.
J. Stolfi. Primitives for Computational Geometry. Technical Report 36, Digital SRC, 1989.
R. E. Tarjan.Data Structures and Newtork Algorithms. CBMS-BSF Regional Conference Series in Applied Mathematics, Volume 44. SIAM, Philadelphia, PA, 1983.
Author information
Authors and Affiliations
Additional information
Communicated by Leonidas J. Guibas.
This research was supported by NSF Grant CCR-8901484, and by Eni and Enidata within the AXL project. Results presented in this paper have appeared in preliminary form in [Pe1] and [Pe3].
Rights and permissions
About this article
Cite this article
Pellegrini, M. Ray shooting on triangles in 3-space. Algorithmica 9, 471–494 (1993). https://doi.org/10.1007/BF01187036
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01187036