“On ray tracing parametric surfaces” by Toth

  • ©Daniel L. Toth




    On ray tracing parametric surfaces



    A new method for ray tracing parametric surfaces is presented. The new algorithm solves the ray surface intersection directly using multivariate Newton iteration. This provides enough generality to render surfaces which could not be ray traced using existing methods. To overcome the problem of finding a starting point for the Newton algorithm, techniques from Interval Analysis are employed. The results are presented in terms of solving a general nonlinear system of equations f(x)= 0, and thus can be extended to a large class of problems which arise in computer graphics.


    1. J. E Blinn, “A Generalization of Algebraic Surface Drawing”, ACM Trans. on Graphics, Vol. I, No. 3, July 1982, pp. 236-256.
    2. R. L. Cook, T. Porter and L. Carpenter, “Distributed Ray Tracing”, Computer Graphics, Vol. 18, No. 3, pp. 137-144.
    3. R. A. Hall, “A Methodology for Realistic Image Synthesis”, Masters Thesis, Cornell University, 1983.
    4. P. Hanrahan, “Ray Tracing Algebraic Surfaces”, Computer Graphics, Vol. 17, No. 3, July 1983, pp. 83-90.
    5. I. D. Faux, and M. J. Pratt, Computational Geometry for Design and Manufacture, Ellis Horwood, Chichester, 1979.
    6. S. T. Jones, “Locating Safe Starting Regions for Iterative Methods: A Heuristic Algorithm” in Interval Mathematics 1980, K. Nickel, ed., Academic Press, New York, 1980, pp. 377-386.
    7. R. Krawczyk, “Newton-Algorithmen zur Bcstimmung yon Nullstellen mit Fehlerschranken’, Computing, Vol. 4, 1969, pp. 187-201.
    8. J. -r. Kajiya, “Ray Tracing Parametric Patches”, Computer Graphics, Vol. 16, No. 3, pp. 245-254.
    9. J. M. Lane, and R. F. Riesenfeld, “A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-2, No. 1, January 1980, pp. 35-46.
    10. R. E. Moore, Interval Analysis, Prentice Hall, Englewood Cliffs, N J, 1966.
    11. “A Test for Existence of Solutions to Nonlinear Systems”, SlAM J.’Numer. Anal., Vol. 14, No. 4, Sept. 1977, pp. 611- 615,
    12. “A Computational Test for Convergence of Iteratire Methods for b}onlinear Systems”, SlAM J. Numer. Anal., Vol. 15, No. 6, Dee. 1978, pp. 1 t 94-1 t 96.
    13. Methods and Applications of Interval Analysis, SlAM Studies 2, Society for Industrial and Applied Mathematics, Philadelphia, 1979.
    14. R. E. Moore, and S. T. Jones, “Safe Starting Regions for lterative Methods”, SIAM J. Numer. Anal., Vol. 14, No. 6, Dec. 1977, pp. 1051-1065.
    15. J. M. Ortega, and W. C. Reinbolt, lterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
    16. L, B. Rail, Computational Solution of Nonlinear Operator Equations, Robert E. Krieger Publishing Inc,, Huntington, New York, 1979.
    17. A. J. Schwartz, To be presented, SIAM Conference on Geometric Modeling and Robotics, July 15-18, Albany, N. Y.
    18. T. W. Sederberg, and D. C. Anderson, “Ray Tracing of Steiner Patches”, Computer Graphics, Vot. 18, No. 3, pp. 159-164.
    19. I’, Whitted, “An Improved Illumination Model for Shaded Display”, Comm. ACM, Vol. 23, No, 6, June 1980, pp. 96-102.
    20. M. A. Wolfe, “A Modification of Krawczyc’s Algorithm”, SlAM J. Numer. Anal., Vol. 17, No. 3, June 1980, pp. 376-379.

ACM Digital Library Publication: