Decomposition of arbitrary polygons into trapezoids

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.

What I claim is: 
     
       1. A device for rendering a plurality of polygons representing an image to a display device, each polygon having an arbitrary number of vertices and a corresponding number of edges having edge data associated therewith, said device comprising: means for providing data including coordinate values of said arbitrary number of vertices and said edge data for said corresponding number of edges for each input polygon of said image;   means for sorting said vertices by increasing coordinate values in a direction perpendicular to a scan direction;   a polygon processor for breaking each input polygon into scanning regions parallel to said scan direction of said display device, said scanning regions being bounded in a direction perpendicular to said scan direction by scan lines through respective sorted vertices, said polygon processor further determining whether any edges in each scanning region intersect and then subdividing a scanning region having intersecting edges into subregions bounded on opposite ends in said direction perpendicular to said scan direction by said scan lines through said respective sorted vertices and on common ends in said direction perpendicular to said scan direction by a scan line through an intersection point of said intersecting edges; and   means for sending the edge data for each scanning region and subregion of each input polygon to said display device for display.   
     
     
       2. A device as in claim 1, wherein said providing means provides each vertex of each input polygon to said polygon processor in a sequence of vertices such that adjacent vertices in the sequence of vertices define respective edges of each input polygon. 
     
     
       3. A device as in claim 1, wherein said sorting means sorts the edges in each scanning region by increasing coordinate values in the scan direction at points where each edge crosses a scan line through a one of said respective sorted vertices having a lesser coordinate value in said direction perpendicular to the scan direction and stores edge pairs of the sorted edges as respective odd and even entries in an edge array, and said polygon processor forms said subregions for scanning regions containing intersecting edges except when an edge of an edge pair stored as an odd entry in said edge array crosses a subsequent edge of said edge pair stored as an even entry in said edge array. 
     
     
       4. A device as in claim 3, wherein when at least two edges in each scanning region cross said scan line through the one of said respective sorted vertices having a lesser coordinate value in said direction perpendicular to the scan direction at a common point, said sorting means sorts said at least two edges by increasing slope in the scan lines direction. 
     
     
       5. A device as in claim 1, wherein said sending means does not send to said display device scanning regions and subregions having less than a predetermined thickness in said direction perpendicular to the scan direction. 
     
     
       6. A device as in claim 5, wherein said predetermined thickness is one scan line. 
     
     
       7. A method of rendering a plurality of polygons representing an image to a display device, each polygon having an arbitrary number of vertices and a corresponding number of edges having edge data associated therewith, comprising the steps of: providing data including coordinate values of said arbitrary number of vertices and said edge data for said corresponding number of edges for each input polygon of said image;   sorting said vertices by increasing coordinate values in a direction perpendicular to a scan direction;   breaking each input polygon into scanning regions parallel to said scan direction of said display device, said scanning regions being bounded in a direction perpendicular to said scan direction by scan lines through respective sorted vertices, including the steps of determining whether any edges in each scanning region intersect and subdividing a scanning region having intersecting edges into subregions bounded on opposite ends in said direction perpendicular to said scan direction by said said lines through said respective sorted vertices and on common ends in said direction perpendicular to said scan direction by a scan line through an intersection point of said intersecting edges; and   sending the edge data for each scanning region and subregion of each input polygon to said display device for display.   
     
     
       8. A method as in claim 7, wherein said providing step includes the step of providing each vertex of each input polygon in a sequence of vertices such that adjacent vertices in the sequence of vertices define respective edges of each input polygon. 
     
     
       9. A method as in claim 7, wherein said sorting step includes the steps of sorting the edges in each scanning region by increasing coordinate values in the scan direction at points where each edge crosses a scan line through a one of said respective sorted vertices having a lesser coordinate value in said direction perpendicular to the scan direction and storing edge pairs of the sorted edges as respective odd and even entries in an edge array, and said polygon breaking step includes the step of forming said subregions for scanning regions containing intersecting edges except when an edge of an edge pair stored as an odd entry in said edge array crosses a subsequent edge of said edge pair stored as an even entry in said edge array. 
     
     
       10. A method as in claim 9, wherein said sorting step includes the further step of sorting, by increasing slope in the scan line direction, those edges in each scanning region which cross each other and said scan line through the one of said respective sorted vertices having a lesser coordinate value in said direction perpendicular to the scan direction at a common point. 
     
     
       11. A method as in claim 7, including the step of discarding those scanning regions and subregions having less than a predetermined thickness in said direction perpendicular to the scan direction before sending in said sending step. 
     
     
       12. A method as in claim 11, wherein said predetermined thickness is one scan line.