Decomposition of arbitrary polygons into trapezoids
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
12 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification