Ray tracing parametric surface patches utilizing numerical techniques and ray coherence

ABSTRACT

A new algorithm for ray tracing parametric surface patches is presented. The method uses quasi-Newton iteration to solve for the ray/surface intersection and utilizes ray-to-ray coherence by using numerical information from adjoining rays as initial approximations to the quasi-Newton algorithm. Techniques based upon object space subdivision are used to insure convergence to the correct interesection point. Examples are given of the use of the algorithm in scenes containing Bézier surface patches. Results show that a significant number of ray/surface intersections on these parametric surface patches can be found using very few iterations, giving a significant computational savings.

REFERENCES

• 1: Appel, A., "Some Techniques for Shading Machine Renderings of S~lids," Proc. AFIPS Sprin~ Joint Computer Canf., Vol. 32, 1068, 37-49.
• 2: B}inn, J.F., "Computer display of curved surface~," Ph.D. dissertation, Department of Computer Science, University cf Utah, December Ig78.
• 3: 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]
• 4: Bouknight, J., and K. Kelley, *An Algorithm for Producing H~|f-Tone Computer Graphics Presentations with Shadows ~nd Movable Light Sources," Prac. AFIPS Spring Joint Computer Conf., Vot. 36, 1~70, 1-10.
• 5: Broyden, C.G., "The convergence of a class o1" double-rank minimization algorithms," Paxtz I and I{, J.I.M.A. 6, 76-90, 222- 236.
• 6: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.137-145, January 1984
• 7: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 8: Mark Dippé , John Swensen, An adaptive subdivision algorithm and parallel architecture for realistic image synthesis, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.149-158, January 1984
• 9: Mark A. Z. Dippé , Erling Henry Wold, Antialiasing through stochastic sampling, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.69-78, Jul. 1985
• 10: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 11: Fletcher, R., "A new approach to variable metric algorithms," Computer Journal 13, 317-322.
• 12: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 13: 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]
• 14: Gtassner, A.S., "Space subdivision for fast ray tracing," IEEE Computer Graphica and Applicationo 4, No. 10, November 1984, 15-22.
• 15: Goldfaxb, D., "A family of variable metric methods derived by vaxiatJona} mean~," Math. Camp. tLt, 23-26~
• 16: 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
• 17: Joy, K.I., "On the use of quasi-Newton methods in ray tracing parametric ~urface patches," Technical Report CSE-85- 10, Computer Science Division, Department of Electrical at~d Computer Engineering, University of California, Davis, October, 1985.
• 18: Kaplan, M.R., "Space tracing: a constant time ray tracer," 1985 SIGGRAPH Tutorial on State of the Art in Image Synthesis, July, 1985.
• 19: James T. Kajiya, Ray tracing parametric patches, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.245-254, July 26-30, 1982, Boston, Massachusetts, United States
• 20: James T. Kajiya, New Techniques for Ray Tracing Procedurally Defined Objects, ACM Transactions on Graphics (TOG), v.2 n.3, p.161-181, July 1983 [doi>10.1145/357323.357324]
• 21: Mark E. Lee , Richard A. Redner , Samuel P. Uselton, Statistically optimized sampling for distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.61-68, Jul. 1985
• 22: Thomas W. Sederberg , David C. Anderson, Ray tracing of Steiner patches, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.159-164, January 1984
• 23: Shanno, D.F., "Conditioning of quasi-Newton methods for function minimization," Math. Camp. 24, 657-664.
• 24: L R Speer , T D DeRose , B A Barsky, A theoretical and empirical analysis of coherent ray-tracing, Proceedings of Graphics Interface '85 on Computer-generated images: the state of the art, p.11-25, January 1986, Montreal, Quebec, Canada
• 25: Sweeney, M.A.J. and R.H. Barrels, "Ray Tracing Free-Form B-Spline Surfaces", IEEE Computer Graphics and Application~ Vol. 6, No. 2, February 1986, 41-49.
• 26: Daniel L. Toth, On ray tracing parametric surfaces, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.171-179, Jul. 1985
• 27: Hank Weghorst , Gary Hooper , Donald P. Greenberg, Improved Computational Methods for Ray Tracing, ACM Transactions on Graphics (TOG), v.3 n.1, p.52-69, Jan. 1984 [doi>10.1145/357332.357335]
• 28: 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

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