Ray tracing generalized cylinders

ABSTRACT

An algorithm is presented for ray tracing generalized cylinders, that is, objects defined by sweeping a two-dimensional contour along a three-dimensional trajectory. The contour can be any 'well-behaved' curve in the sense that it is continuous, and that the points where the tangent is horizontal or vertical can be determined, the trajectory can be any spline curve. First a definition is given of generalized cylinders in terms of the Frenet frame of the trajectory. Then the main problem in ray tracing these objects, the computation of the intersection points with a ray, is reduced to the problem of intersecting two two-dimensional curves. This problem is solved by a subdivision algorithm. The three-dimensional normal at the intersection point closest to the eye point, necessary to perform shading, is obtained by transforming the two-dimensional normal at the corresponding intersection point of the two two-dimensional curves. In this way it is possible to obtain highly realistic images for a very broad class of objects.

REFERENCES

• 1: Dana Harry Ballard , Christopher M. Brown, Computer Vision, Prentice Hall Professional Technical Reference, 1982
• 2: DO CARMO, M. P. Differential Geometry of Curves and Surfaces. Prentice Hall, Englewood Cliffs, N.J., 1976, pp. 16-22.
• 3: 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]
• 4: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 5: GOLDSTEIN, 1~. A. AND NAGEL, R. 3D visual simulation. Simulation 16, 1 (Jan. 1971), 25-31.
• 6: Pat Hanrahan, Ray tracing algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.83-90, July 1983
• 7: James T. Kajiya, Ray tracing parametric patches, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.245-254, July 1982
• 8: 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]
• 9: KOPARKAR, P. A. AND MUDUR, S.P. A new class of algorithms for the processing of parametric curves. Comput.-Aided Des. 15, 1 (Jan, 1983), 41-45.
• 10: ROTH, S.D. Ray casting for modeling solids. Comput. Graph. Image Proc. 18, 2 (Feb. 1982), 109-144.
• 11: 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]
• 12: Jarke J. van Wijk, Ray tracing objects defined by sweeping planar cubic splines, ACM Transactions on Graphics (TOG), v.3 n.3, p.223-237, July 1984 [doi>10.1145/3870.3875]
• 13: WrJK, J. J. VAN. Ray tracing objects defined by sweeping a sphere. In Proceedings of the Eurographics "84 Conference (Copenhagen, Sept. 12-14), North-Holland, Amsterdam, 1984, pp. 73-82.

INDEX TERMS

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; Geometric algorithms, languages, and systems; Modeling packages
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms; Color, shading, shadowing, and texture

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Human Factors, Theory