“Ray tracing parametric surface patches utilizing numerical techniques and ray coherence” by Joy and Bhetanabhotla

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.

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. Blinn, J.F., “A generalization of algebraic surface drawing,” ACM Trans. on Graphite, Vol 1, No. 3, July 1982, 236-256.
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. Cook, R.L., T. Porter and L. Carpenter, “Distributed ray tracing,” Computer Graphic~ lg, No. 3, (Proceedings of SIGGRAPH/84), July 1984, 137-144.
7. Dennis, J.E., and R.B. Sohnabet, Numerical Method~ for Unconstrained Optimization and non-Linear Equatione Prentice- Hall, Englewood Cliffs, N J, 1983.
8. Dipp~, M.A.Z., and J. Swensen, “An adaptive subdivision algorithm and parallel architecture for realistic image synthesis,” Computer Graphics 18, No. 3, (Proceedings of SIGGRAPH/84), July 1984, 149-158.
9. Dipp$, M.A.Z. and E.H. Wold, “Antialiasing through stochastic sampling,” Computer Graphics I#, No. 3, (Proceedings of S|GGRAPH/85), July 1985, ~9-78.
10. Faux, I.D., and M.J. Pratt, Csmpulalisnai Geometry far Deaign and Manufacture Ellis Horwood, Chiehester, 1982.
11. Fletcher, R., “A new approach to variable metric algorithms,” Computer Journal 13, 317-322.
12. Fletcher, R., Practical Methoff~ of Optimization, John Wiley Sons, Chichester, England, 1980.
13. Fujimoto, A., T. Tanaka and K. lwata, “ARTS: Accelerated Ray Tracing System,” IEEE Computer Graphics and Applications Vol. 6, No. 4, April 1986, 15-26.
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. Hanrahan, P., “Ray tracing algebraic surfaces,” Computer Graphics 17, (Proceedings of SIGGRAPH/83), No. 3, July 1983, 83-86.
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. Kajiya, J.T., “Ray tracing parametric patches,” Computer Graphics 16, (Proceedings of SIGGRAPH/82) (3), 1982, 245-254.
20. Kajiva, J.T., “New techniques for ray tracing procedurally defined objects,” ACM Trans. on Graphica ~., No. 3, July 1983, 161-181.
21. Lee, M.E., R.A. Redner and S.P. Uselton, “Statistically optimized sampling for distributed ray tracing,” Computer Graphics 19, No. 3, (Proceedings of SIGGRAPH/85), 61-68.
22. Sederberg, T.W., and D.C. Ander~on, “Ray tracing of Steiner patches,” Computer Graphic8 18~ No. 3, (Proceedings of SIGGRAPH/84), July 1984, 159-164.
23. Shanno, D.F., “Conditioning of quasi-Newton methods for function minimization,” Math. Camp. 24, 657-664.
24. Speer, L.R., T.D. DeRose and B.A. Barsky, “A theoretical and empirical analysis of coherent ray-tr~eing,” Proceedings ~1 Graphic~ Interface 85, May, 1985, 1-8.
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. Toth, D.L., “On ray tracing parametric surfaces,” Computer Graphic~ 19~ (Proceedings of SIGGRAPH/85}, No. 3, July 1985, 171-179.
27. Weghorst, H., G. Hooper and D.P. Greenber~,, “Improved computational met, hods for ray tracing,” ACM Trans. on Graphic# 8, No. l, January 1984, 52-69,
28. Whitted, T., “An improved illumination model for shaded display,” CACM~ Vol. 23, No. 6, June 1980, 343-349.