System and method for triangulation of non-simple, multiply-connected, multi-styled shapes

摘要

Disclosed is a system and method for triangulating vector graphics data having non-simple multi-styled and multi-connected shapes. The method provides for geometry flattening and more efficient processing of horizontal edges. The method involves computing a plurality of monotone chains corresponding to each of the plurality of shapes; computing a plurality of scan beams corresponding to the plurality of monotone chains; computing a plurality of monotone polygons corresponding to the monotone chains; computing a plurality of triangles from the plurality of monotone polygons; and displaying the plurality of triangles on the computer display.

主权项

1. A computer-implemented method for displaying an image having a plurality of multi-styled shapes on a computer display, comprising:
creating a plurality of monotone chains corresponding to each of the plurality of multi-styled shapes; creating, via a microprocessor, a monotone chain table populated with the plurality of monotone chains; assigning a plurality of scan beams corresponding to the plurality of monotone chains; identifying a left style and a right style corresponding to each of the plurality of monotone chains between two adjacent scan beams; computing a plurality of monotone polygons corresponding to the monotone chains, wherein each edge included in each monotone polygon is part of a monotone chain having a left style and a right style; and computing a plurality of triangles from the plurality of monotone polygons.