Tiled polygon traversal using half-plane edge functions

ABSTRACT

Existing techniques for traversing a polygon generate fragments one (or more) rows or columns at a time. (A fragment is all the information needed to paint one pixel of the polygon.) This order is non-optimal for many operations. For example, most frame buffers are tiled into rectangular pages, and there is a cost associated with accessing a different page. Pixel processing is more efficient if all fragments of a polygon on one page are generated before any fragments on a different page. Similarly, texture caches have reduced miss rates if fragments are generated in tiles (and even tiles of tiles) whose size depends upon the cache organization. We describe a polygon traversal algorithm that generates fragments in a tiled fashion. That is, it generates all fragments of a polygon within a rectangle (tile) before generating any fragments in another rectangle. For a single level of tiling, our algorithm requires one additional saved context (the values of all interpolator accumulators, such as Z depth, Red, Green, Blue, etc.) over a traditional traversal algorithm based upon half-plane edge functions. An additional level of tiling requires another saved context for the special case of rectangle copies, or three more for the general case. We describe how to use this algorithm to generate fragments in an optimal order for several common scenarios.

REFERENCES

• 1: Kurt Akeley, Reality Engine graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.109-116, September 1993 [doi>10.1145/166117.166131]
• 2: Michael F. Deering , Stephen A. Schlapp , Michael G. Lavelle, FBRAM: a new form of memory optimized for 3D graphics, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.167-174, July 1994 [doi>10.1145/192161.192194]
• 3: 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
• 4: Ziyad S. Hakura , Anoop Gupta, The design and analysis of a cache architecture for texture mapping, Proceedings of the 24th annual international symposium on Computer architecture, p.108-120, June 01-04, 1997, Denver, Colorado, United States
• 5: Homan Igehy , Matthew Eldridge , Kekoa Proudfoot, Prefetching in a texture cache architecture, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.133-ff., August 31-September 01, 1998, Lisbon, Portugal [doi>10.1145/285305.285321]
• 6: Homan Igehy , Matthew Eldridge , Pat Hanrahan, Parallel texture caching, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.95-106, August 08-09, 1999, Los Angeles, California, United States [doi>10.1145/311534.311583]
• 7: Brian Kelleher. PixelVision Architecture, Technical Note 1998-013, System Research Center, Compaq Computer Corporation, October 1998, available at http:// www.research.digital.com/SRC/publications/src-tn.html.
• 8: Joel McCormack, Robert McNamara, Chris Gianos, Larry Seiler, Norman Jouppi, Ken Correll, Todd Dutton & John Zurawski. Neon: A (Big) (Fast) Single-Chip 3D Workstation Graphics Accelerator. Research Report 98/1, Western Research Laboratory, Compaq Computer Corporation, Revised July 1999, available at http:// www.research.compaq.com/wrl/techreports/pubslist.html.
• 9: Joel McCormack & Robert McNamara. Efficient and Tiled Polygon Traversal Using Half-Plane Edge Functions. Research Report 2000/4, Western Research Laboratory, Compaq Computer Corporation, August 2000, available at http://www.research.compaq.com/wrl/techreports/ pubslist.html.
• 10: John S. Montrym , Daniel R. Baum , David L. Dignam , Christopher J. Migdal, InfiniteReality: a real-time graphics system, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.293-302, August 1997 [doi>10.1145/258734.258871]
• 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
graphics accelerators, rasterization, tiling