“Guaranteed ray intersections with implicit surfaces” by Kalra and Barr

In this paper, we present a robust and mathematically sound ray-intersection algorithm for implicit surfaces. The algorithm is guaranteed to numerically find the nearest intersection of the surface with a ray, and is guaranteed not to miss fine features of the surface. It does not require fine tuning or human choice of interactive parameters. Instead, it requires two upper bounds: “L” that limits the net rate of change of the implicit surface function f(x,y,z) and “G” that limits the rate of change of the gradient. We refer to an implicit surface with these rate limits as an “LG-implicit surface.”Existing schemes to intersect a ray with an implicit surface have typically been guaranteed to work only for a limited set of implicit functions, such as quadric surfaces or polynomials, or else have been ad-hoc and have not been guaranteed to work. Our technique significantly extends the ability to intersect rays with implicit surfaces in a guaranteed fashion.

1. Alan H. Barr, Superquadrics and Angle-Preserving Transformations, IEEE Computer Graphics and Applications, Jan ’81.
2. Alan H. Barr, Global And Local De.formations of Solid Primitives, Computer Graphics, July ’84.
3. James F. Blinn, A generalization of Algebraic Surface Drawing, ACM Transactions on Graphics, Vol. 1, No. 3, July 1982, pp 235-256.
4. Jules Blomenthal, Modeling the Mighty Maple, Computer Graphics, Vol 19, No. 3, July 1985.
5. Jules Blomenthal, Polygonization of Implicit Surfaces, Course Notes on “The Modeling of Natural Phenomena”, Siggraph 1987.
6. Collins, G.E. and Akritas, A. G., Polynomial real root isolation using Descartes’ rule of signs, Proc. 1976 AOM Symposium on Symbolic and Algebraic Computation.
7. Gear, G. William, Numerical lnitial Value Problems in Ordinary Di.~erential Equations, Prentice-Hall, Englewood Cliffs, N J, 1971.
8. Space Subdivision for Fast Ray Tracingr Andrew S. Glassnet, IEEE Computer Graphics and Applications, October ’84.
9. Pat Hanrahan, Ray Tracing Algebraic Surfaces, Computer Graphics. July ’83.
10. Devendra Kalra and Alan H. Barr, Guaranteed lntersection.~ with lmplicit surfaces, Galtech Computer Science Tech Report.
11. Mathematics Applied To Deterministic Problems In The Natural Sciences, C. C. Lin and L. A. Segel, Macmillan Publishing Co., Inc., New York.
12. Marching Cubes: A high resolution 3d surface construction algorithm, William E. Lorensen and Harvey E. Cline, Computer Graphics, July 1987.
13. Alan E. Middleditch and Kenneth H. Sears, Blend Surfaces for Set theoretic volume Modeling Systems, Computer Graphics, Vol. 19, No. 3, July 1985, pp. 161-170.
14. John Ptatt and Alan Barr, Constraint Methods for Flexible Models, Computer Graphics, Aug 88.
15. Steven Wolfram et ~1,, SMP: A symbol manipulation Package, California Institute of Technology, 1981.
16. Demetri Terzopoulos, John Pl~tt, A1 Barr, Kurt Fleischer, Elastically Deformable Models, Computer Graphics, July 87.
17. Uspensky, J. V., Theory of Equations, McGraw-Hill, 1948.
18. Brian P. Van Herzen, Sampling Deformed, Intersecting Surfaces with Quadtrees, Master’s Thesis, Caltech, 1984.
19. Brian Van Herzen, Applications of SurJace Networks to Sampling Problems in Computer Graphics, (Jnltech Ph D Thesis.
20. Brian Van Herzen, Alan H, Barr, Harold R. Zatz, Collision Determination for Parametric Surfaces, Caltech CS Technica} Report.
21. Space Division for Ray Tracing in CSG, GeolJ Wyvill, Tosiyasu L. Kunii and Yasuto Shirai, IEEE Computer Graphics and Applications, April ’86.
22. Solid Texturing of Soft Objects, Geo}J Wyvill, Brian Wyvill, Craig Pheeters, IEEE Computer Graphics and Applications, December ’87.
23. Animating Soft Objects, Geoff Wyvill, Craig Pheeters, Brian Wyvill, The Visual Computer, (1986)2.