A parallel algorithm for polygon rasterization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel algorithm for polygon rasterization

Full text

Pdf (529 KB)

Source

International Conference on Computer Graphics and Interactive Techniques archive
Proceedings of the 15th annual conference on Computer graphics and interactive techniques table of contents

Pages: 17 - 20

Year of Publication: 1988

ISBN:0-89791-275-6

Also published in ...

Author

Juan Pineda

Apollo Computer Inc., Chelmsford, MA

Sponsor

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 219, Citation Count: 28

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/54852.378457 What is a DOI?

ABSTRACT

A parallel algorithm for the rasterization of polygons is presented that is particularly well suited for 3D Z-buffered graphics implementations. The algorithm represents each edge of a polygon by a linear edge function that has a value greater than zero on one side of the edge and less than zero on the opposite side. The value of the function can be interpolated with hardware similar to hardware required to interpolate color and Z pixel values. In addition, the edge function of adjacent pixels may be easily computed in parallel. The coefficients of the "Edge function" can be computed from floating point endpoints in such a way that sub-pixel precision of the endpoints can be retained in an elegant way.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bresenham, J. Algorithm for Computer Control of Digital Plotter. IBM Systems Journal 4,1 (1965), 25-30.
	2	James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	3	Fuchs, H. and Poulton J. PIXEL-PLANES: A VLSI-Oriented Design for a Raster Graphics Engine. VLSI DESIGN (Third Quarter 1981), 20-28.
	4	Fujimoto, A. and Iwata, K. Jag-Free Images on Raster Displays. IEEE Computer Graphics and Applications 3,9 (December 1983), 26-34.
	5	Whitton, M. Memory Design for Raster Graphics Displays. iEEE Computer Graphics and Applications 4,3 (March 1984), 48-65.

CITED BY 28

	Donghyun Kim , Lee-Sup Kim, Technical Section: Area-efficient pixel rasterization and texture coordinate interpolation, Computers and Graphics, v.32 n.6, p.669-681, December, 2008
	Larry Seller, Quadratic interpolation for near-Phong quality shading, ACM SIGGRAPH 98 Conference abstracts and applications, p.268, July 19-24, 1998, Orlando, Florida, United States
	Joel McCormack , Robert McNamara , Christopher Gianos , Norman P. Jouppi , Todd Dutton , John Zurawski , Larry Seiler , Ken Correll, Implementing Neon: A 256-Bit Graphics Accelerator, IEEE Micro, v.19 n.2, p.58-69, March 1999
	Bruce D'Amora , Fausto Bernardini, Pervasive 3D Viewing for Product Data Management, IEEE Computer Graphics and Applications, v.23 n.2, p.14-19, March 2003
	Graham J. Dunnett , Martin White , Paul F. Lister , Richard L. Grimsdale, The Image Chip for High Performance 3D Rendering, IEEE Computer Graphics and Applications, v.12 n.6, p.41-52, November 1992
	Scott Whitman, A load balanced SIMD polygon renderer, Proceedings of the IEEE symposium on Parallel rendering, p.63-69, October 30-31, 1995, Atlanta, Georgia, United States
	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
	Marcus D. Waller , Jon P. Ewins , Martin White , Paul F. Lister, Efficient Coverage Mask Generation for Antialiasing, IEEE Computer Graphics and Applications, v.20 n.6, p.86-93, November 2000
	Jon P. Ewins , Phil L. Watten , Martin White , Michael D. J. McNeill , Paul F. Lister, Codesign of graphics hardware accelerators, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.103-110, August 03-04, 1997, Los Angeles, California, United States
	Kurt Akeley, Reality Engine graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.109-116, September 1993
	Kai Hormann , Marco Tarini, A quadrilateral rendering primitive, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France
	Robert McNamara , Joel McCormack , Norman P. Jouppi, Prefiltered antialiased lines using half-plane distance functions, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.77-85, August 21-22, 2000, Interlaken, Switzerland
	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
	Andreas Schilling, A new simple and efficient antialiasing with subpixel masks, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.133-141, July 1991
	Michael D. McCool , Chris Wales , Kevin Moule, Incremental and hierarchical Hilbert order edge equation polygon rasterizatione, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.65-72, August 2001, Los Angeles, California, United States
	Tomas Akenine-Möller , Ulf Assarsson, Approximate soft shadows on arbitrary surfaces using penumbra wedges, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
	Tomas Akenine-Möller , Jacob Ström, Graphics for the masses: a hardware rasterization architecture for mobile phones, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	Bengt-Olaf Schneider , Jim van Welzen, Efficient Polygon Clipping for an SIMD Graphics Pipeline, IEEE Transactions on Visualization and Computer Graphics, v.4 n.3, p.272-285, July 1998
	Jon P. Ewins , Marcus D. Waller , Martin White , Paul F. Lister, MIP-Map Level Selection for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.4 n.4, p.317-329, October 1998
	Joel McCormack , Robert McNamara , Christopher Gianos , Larry Seiler , Norman P. Jouppi , Ken Correll, Neon: a single-chip 3D workstation graphics accelerator, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.123-132, August 31-September 01, 1998, Lisbon, Portugal
	D. Brandon Lloyd , Naga K. Govindaraju , Steven E. Molnar , Dinesh Manocha, Practical logarithmic rasterization for low-error shadow maps, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
	Gregory S. Johnson , Juhyun Lee , Christopher A. Burns , William R. Mark, The irregular Z-buffer: Hardware acceleration for irregular data structures, ACM Transactions on Graphics (TOG), v.24 n.4, p.1462-1482, October 2005
	Tulika Mitra , Tzi-cker Chiueh, Dynamic 3D graphics workload characterization and the architectural implications, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.62-71, November 16-18, 1999, Haifa, Israel
	Tomas Akenine-Möller , Jacob Munkberg , Jon Hasselgren, Stochastic rasterization using time-continuous triangles, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
	Voicu Popescu , Paul Rosen, Forward rasterization, ACM Transactions on Graphics (TOG), v.25 n.2, p.375-411, April 2006
	Larry Seiler , Doug Carmean , Eric Sprangle , Tom Forsyth , Michael Abrash , Pradeep Dubey , Stephen Junkins , Adam Lake , Jeremy Sugerman , Robert Cavin , Roger Espasa , Ed Grochowski , Toni Juan , Pat Hanrahan, Larrabee: a many-core x86 architecture for visual computing, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Peter Shirley, Data structures for graphics, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Frederick M. Weinhaus , Venkat Devarajan, Texture mapping 3D models of real-world scenes, ACM Computing Surveys (CSUR), v.29 n.4, p.325-365, Dec. 1997