Guaranteed ray intersections with implicit surfaces

ABSTRACT

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.

REFERENCES

• BARR 81: Alan H. Barr, Superquadrics and Angle-Preserving Transformations, IEEE Computer Graphics and Applications, Jan '81.
• BARR 84: Alan H. Barr, Global and local deformations of solid primitives, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.21-30, July 1984
• BLINN 82: James F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Transactions on Graphics (TOG), v.1 n.3, p.235-256, July 1982 [doi>10.1145/357306.357310]
• BLOOMENTHAL 85: Jules Bloomenthal, Modeling the mighty maple, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.305-311, Jul. 1985
• BLOOMENTHAL 87: Jules Blomenthal, Polygonization of Implicit Surfaces, Course Notes on "The Modeling of Natural Phenomena", Siggraph 1987.
• COLLINS AND AKRITAS 76: George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
• GEAR 71: C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice Hall PTR, Upper Saddle River, NJ, 1971
• GLASSNER 84: Space Subdivision for Fast Ray Tracingr Andrew S. Glassnet, IEEE Computer Graphics and Applications, October '84.
• HANRAHAN 83: Pat Hanrahan, Ray tracing algebraic surfaces, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.83-90, July 25-29, 1983, Detroit, Michigan, United States
• KALRA and BARR 89: Devendra Kalra and Alan H. Barr, Guaranteed lntersection.~ with lmplicit surfaces, Galtech Computer Science Tech Report.
• LIN AND SEGEL 74: Mathematics Applied To Deterministic Problems In The Natural Sciences, C. C. Lin and L. A. Segel, Macmillan Publishing Co., Inc., New York.
• LORENSEN AND CLINE 87: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• MIDDLEDITCH et al 85: Alan E. Middleditch , Kenneth H. Sears, Blend surfaces for set theoretic volume modelling systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.161-170, Jul. 1985
• PLATT and BARR: John C. Platt , Alan H. Barr, Constraints methods for flexible models, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.279-288, Aug. 1988
• SMP: Steven Wolfram et ~1,, SMP: A symbol manipulation Package, California Institute of Technology, 1981.
• TERZOPOULOS et al: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• USPENSKY 48: Uspensky, J. V., Theory of Equations, McGraw-Hill, 1948.
• VON HERZEN 84: Brian P. Van Herzen, Sampling Deformed, Intersecting Surfaces with Quadtrees, Master's Thesis, Caltech, 1984.
• VON HERZEN 88: B. Von Herzen, Applications of surface networks to sampling problems in computer graphics, California Institute of Technology, Pasadena, CA, 1989
• VON HERZEN 89: Brian Van Herzen, Alan H, Barr, Harold R. Zatz, Collision Determination for Parametric Surfaces, Caltech CS Technica} Report.
• WYVILL 86: Geoff Wyvill , Tosiyasu L Kunii , Yasuto Shirai, Space division for ray tracing in CSG, IEEE Computer Graphics and Applications, v.6 n.4, p.28-34, April 1986 [doi>10.1109/MCG.1986.276717]
• WYVILL 87(1): Solid Texturing of Soft Objects, Geo}J Wyvill, Brian Wyvill, Craig Pheeters, IEEE Computer Graphics and Applications, December '87.
• WYVILL 87(2): Animating Soft Objects, Geoff Wyvill, Craig Pheeters, Brian Wyvill, The Visual Computer, (1986)2.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms