Ray tracing complex models containing surface tessellations

ABSTRACT

An approach to ray tracing complex models containing mathematically defined surfaces is presented. Parametric and implicit surfaces, and boolean combinations of these, are first tessellated into triangles. The resulting triangles from many such surfaces are organized in a hierachy of lists and 3D grids, allowing efficient calculation of ray/model intersections.The technique has been used to ray trace models containing billions of traiangles and surfaces never before ray traced. The organizing scheme developed is also independently useful for efficiently ray tracing any complex model, whether or not it contains surface tessellations.

REFERENCES

• Burr 81: Burr, Alan H., "Superquadrics and Angle Preserving Transformations," Computer Graphics and Appffcations, 1(1}.
• Baxr 86: Alan H. Barr, Ray tracing deformed surfaces, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.287-296, Aug. 1986
• Cyrus 78: Cyrus, Iv{. and J. Beck, ~Generalized two and three dimensional Clipping~" Computers and Graphics, 3(1)~ 1978, pp. 23-28.
• Pujimoto 86: Akira Fujimoto , Takayuki Tanaka , Kansei Iwata, ARTSccelerated ray-tracing system, IEEE Computer Graphics and Applications, v.6 n.4, p.16-26, April 1986 [doi>10.1109/MCG.1986.276715]
• Glassner 84: Glassner, Andrew S., ~Space Subdivision for Fast Ray Tracing, ~ IEEE Computer Graphics and Applications, 4(10), October, 1984, pp. 15-22.
• Kalra 86: Kalra, Devendra, M.S. dissertation in preparation.
• Kaplan 85: Kaplan, Michael R., ~The Uses of Spatial Coherence in Ray Tracing," ACM SIGGRAPH '85 Course Notes 11, July 22-26 1985.
• Kajiya 82: James T. Kajiya, Ray tracing parametric patches, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.245-254, July 1982
• Kay 86: Timothy L. Kay , James T. Kajiya, Ray tracing complex scenes, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.269-278, Aug. 1986
• Joy 86: Kenneth I. Joy , Murthy N. Bhetanabhotla, Ray tracing parametric surface patches utilizing numerical techniques and ray coherence, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.279-285, Aug. 1986
• Rubin 80: Steven M. Rubin , Turner Whitted, A 3-dimensional representation for fast rendering of complex scenes, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.110-116, July 1980
• Toth 85: Daniel L. Toth, On ray tracing parametric surfaces, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.171-179, Jul. 1985
• Von Hersen 85: Von Hersen, Brian P.,"Sampling Deformed, Intersecting Surfaces with Quadtrees," Caltech CS Technical Report 5179:TR:85, pp. t-40.
• Vou Herzen 87: Brian Von Herzen , Alan H. Barr, Accurate triangulations of deformed, intersecting surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.103-110, July 1987
• Whirred 80: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Performance, Theory