Decomposition of arbitrary polygons into trapezoids

Details Decomposition of arbitrary polygons into trapezoids Decomposition of arbitrary polygons into trapezoids

1990-03-16

1992-07-07

Harkcom, Gary V.

395134, 395141, G06F 1562

Patent

active

051290510

ABSTRACT:
A technique for decomposing any simple or complex arbitrary polygon into a trapezoid having at least one edge parallel to the scan direction for more efficient scan conversion by rasterization circuitry. An input polygon is split into "slabs", which are adjacent regions bounded by lines parallel to the scan direction. Initially the polygon is split at the y coordinate of every vertex to define the slabs. Then, for each slab, it is determined which edges are present in the slab and whether there are any unacceptable edge intersections. If an unacceptable edge intersection is found in a slab, that slab is broken into two or more slabs at the y coordinates of the intersection points of the edges. Each of the slabs is then processed independently. Once no unacceptable intersections are found in any slab, trapezoids are rendered from adjacent pairs of edges and sent to the rasterization circuitry. Since edge intersections may be accounted for in accordance with the invention, any input polygon, no matter how complex, may be correctly rendered in an efficient manner.

REFERENCES:
patent: 4725831 (1988-02-01), Coleman
patent: 4791582 (1988-12-01), Ueda et al.
patent: 5020002 (1991-05-01), Malachowsky
Fuchs et al., "Pixel-Planes 5: A Heterogeneous Multiprocessor Graphics System Using Processor-Enhanced Memories," Computer Graphics, vol. 23, No. 3, Jul. 1989, pp. 79-88.
D. T. Lee, "Shading of Regions on Vector Display Devises," Computer Graphics, vol. 15, No. 3, Aug. 1981, pp. 37-44.
Rhoden et al., "Hardware Acceleration for Window Systems," Computer Graphics, vol. 23, No. 3, Jul. 1989, pp. 61-67.

Affiliated with

Also associated with

Rating

Decomposition of arbitrary polygons into trapezoids does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Decomposition of arbitrary polygons into trapezoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposition of arbitrary polygons into trapezoids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1836323