Incremental and hierarchical Hilbert order edge equation polygon rasterizatione

ABSTRACT

A rasterization algorithm must efficiently generate pixel fragments from geometric descriptions of primitives. In order to accomplish per-pixel shading, shading parameters must also be interpolated across the primitive in a perspective-correct manner. If some of these parameters are to be interpreted in later stages of the pipeline directly or indirectly as texture coordinates, then translating spatial and parametric coherence into temporal coherence will improve texture cache performance. Finally, if framebuffer access is also organized around cached blocks, then organizing rasterization so fragments are generated in block-sequential order will maximize framebuffer cache performance. Hilbert-order rasterization accomplishes these goals, and also permits efficient incremental evaluation of edge and interpolation equations.

REFERENCES

• 1: T. Bially. Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory, 15:658-664, November 1969.
• 2: Arthur R. Butz. Convergence with Hilbert's Space-Filling Curve. Journal of Computer and System Sciences, 3:128-146, 1969.
• 3: Arthur R. Butz. Alternative Algorithm for Hilbert's Space- Filling Curve. IEEE Transactions on Computers, 20:424-426, April 1971.
• 4: Henry Fuchs , Jack Goldfeather , Jeff P. Hultquist , Susan Spach , John D. Austin , Frederick P. Brooks, Jr. , John G. Eyles , John Poulton, Fast spheres, shadows, textures, transparencies, and imgage enhancements in pixel-planes, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.111-120, July 1985
• 5: Ned Greene, Hierarchical polygon tiling with coverage masks, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.65-74, August 1996 [doi>10.1145/237170.237207]
• 6: John C. Hart, The object instancing paradigm for linear fractal modeling, Proceedings of the conference on Graphics interface '92, p.224-231, September 1992, Vancouver, British Columbia, Canada
• 7: Michael D. McCool. SMASH: A Next-Generation API for Programmable Graphics Accelerators. Technical Report CS- 2000-14, Department of Computer Science, University of Waterloo, April 2001. Published as part of the SIGGRAPH 2001 Course Notes.
• 8: Joel McCormack , Robert McNamara, Tiled polygon traversal using half-plane edge functions, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.15-21, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346882]
• 9: Marc Olano , Trey Greer, Triangle scan conversion using 2D homogeneous coordinates, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.89-95, August 03-04, 1997, Los Angeles, California, United States [doi>10.1145/258694.258723]
• 10: I. Page and R. Dettmer. Software to Silicon. IEE Review, 46(5):15-19, September 2000.
• 11: Juan Pineda, A parallel algorithm for polygon rasterization, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.17-20, June 1988
• 12: I. J. Schoenberg. On the Peano Curve of Lebesgue. Bull. Am. Math. Soc., 44:519, 1938.
• 13: Douglas Voorhies. Space-Filling Curves and a Measure of Coherence. In James Arvo, editor, Graphics Gems, volume II, pages 26-30. Academic Press, 1991.
• 14: I. H. Witten and R. M. Neal. Using peano curves for bilevel display of continuous-tone images. IEEE Computer Graphics & Applications, 2:47-52, May 1982.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Design, Performance, Theory

Keywords:
hardware accelerated image synthesis and shading