Analysis of primary extent algorithms for ray tracing

ABSTRACT

Ray tracing renders realistic images of scenes but requires a relatively large amount of time. Ray tracing is so named because it traces backward along the rays of light reaching an observer's eye, through each pixel of the computer screen, to determine which object in a scene is the source of the light for that ray. To do this, a minimum intersection time, if any, for the ray and each object in the scene is found to determine which object is intersected first. To reduce the calculation time, extents are formed around the objects in the scene; these are bounding rectangles determined in screen coordinates. A ray-extent intersection calculation is fast when compared with that of a ray and a more complex object, such as a sphere, cylinder, cone, or torus. An analysis suggested by earlier work in hidden-surface elimination is carried out here with respect to extent algorithms. The intent is to methodically characterize different methods and orderings in which extents can be used and determine which, if any, performs well consistently. One of the algorithms arrived at will be shown to be particularly effective.

REFERENCES

• 1: Borland Languages Publications Group. Turbo C++ Version 3.0 User's Guide. Scotts Valley, CA: Borland International, Inc., 1991.
• 2: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 3: Andrew S. Glassner, Graphics Gems, Academic Press, Inc., Orlando, FL, 1990
• 4: Francis S. Hill , John Griffin, Computer Graphics, Simon & Schuster, 1990
• 5: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]