Скачать или смотреть 12. Graphics and Visual Computing – Fill Algorithms.

Polygon surfaces are a simple form of representation used in most applications. It is used in all Real-Time displays as fast to process. Other descriptions such as Splines might be used in some applications but are generally reduced to polygons for processing.
We had discussed a layered link list structure. The most important link-list are the vertices/The Vertices Table; which is linked to the Edge Link-List/The Edge Table; which in turn links the edges to form the polygon/surface link-list /The Polygon/Surface Table. This lecture deals with the Fill Algorithms of these polygons. Polygons could be classified as Convex and Concave. A polygon is convex if: for all edges, all other vertices lie on the same side of the edge; otherwise it is concave. Concave polygons often difficult to process /algorithms get stuck or miss bits. We discuss different algorithms to determine if a polygon is convex or concave. We see that no interior angle of a convex polygon is greater the PI. Which imply that the cross product of the vectors formed by the connected edges will have the same sign. We discuss 3 fill algorithms. We begin with scan fill algorithm and discuss the link list data structure. Knowing a point inside a polygon the recursive Boundary Fill and Flood Fill Algorithms are discussed. We also show that it is extremely difficult to determine a point is inside or outside an intersected polygon/concave polygon. It is therefore preferred to represent each polygon by Triangles. Triangles are always convex. Mathematically, uses simple linear equations. Three points guaranteed co-planar by definition. Any polygon can be decomposed into triangles. Triangles can approximate arbitrary shapes. For any orientation on screen, a scan line will intersect only a single segment /scan. We also make a comparison of the Inside-Outside Test for a self-intersecting polygon; with the Odd-Even Rule Algorithm and the Nonzero Winding Number Rule Algorithm. Some application of polygons are also discussed.