Principles and applications of pencil tracing

ABSTRACT

Pencil tracing, a new approach to ray tracing, is introduced for faster image synthesis with more physical fidelity. The paraxial approximation theory for efficiently tracing a pencil of rays is described and analysis of its errors is conducted to insure the accuracy required for pencil tracing. The paraxial approimation is formulated from a 4x4 matrix (a system matrix) that provides the basis for pencil tracing and a variety of ray tracing techniques, such as beam tracing, ray tracing with cones, ray-object intersection tolerance, and a lighting model for reflection and refraction. In the error analysis, functions that estimate approximation errors and determine a constraint on the spread angle of a pencil are given.The theory results in the following fast ray tracing algorithms; ray tracing using a system matrix, ray interpolation, and extended 'beam tracing' using a 'generalized perspective transform'. Some experiments are described to show their advantages. A lighting model is also developed to calculate the illuminance for refracted and reflected light.

REFERENCES

• 1: 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]
• 2: Paul S. Heckbert , Pat Hanrahan, Beam tracing polygonal objects, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.119-127, July 1984
• 3: Peter Moller-Nielsen , Jorgen Staunstrup, Experiments with a fast string searching algorithm, Information Processing Letters, v.18 n.3, p.129-135, March 1984 [doi>10.1016/0020-0190(84)90015-2]
• 4: Alan H. Barr, Ray tracing deformed surfaces, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.287-296, Aug. 1986
• 5: M.Born and E.Wolf, Principles of Optics, pp.190- 196, New York: Pergamon, 1959
• 6: G.A.Deschamps, 'Ray techniques in electromagnetics', Proceedings of the IEEE, 60, No.9, pp.1022- 1035 (1972)
• 7: 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
• 8: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• 9: Tomoyuki Nishita , Eihachiro Nakamae, Continuous tone representation of three-dimensional objects taking account of shadows and interreflection, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.23-30, Jul. 1985
• 10: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.137-145, July 1984

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional 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, Experimentation, Measurement, Theory