Polygon Fill Areas Polygon a plane figure specified by a set of three or more vertices. thatare connected in sequence by straight-line segments(edges) The interior angle is the angle inside the polygon boundary that Here refer only to those without is formed by two adjacent edges crossing edges: simple(standard) DORgon Polygon classifications <180° Convex Polygon(口) >180° All interior angles are less than or equal to 180 degrees Concave Polygon(凹) A convex polygon(a)and a concave on Otherwise
Polygon Fill Areas A convex polygon (a) and a concave polygon (b) The interior angle is the angle inside the polygon boundary that is formed by two adjacent edges. Polygon A plane figure specified by a set of three or more vertices, thatare connected in sequence by straight-line segments (edges). Here refer only to those without crossing edges: simple (standard) polygon Polygon Classifications Convex Polygon (凸) All interior angles are less thanor equal to 180odegrees Concave Polygon (凹) Otherwise 6
Polygon Fill Areas Implementation consideration Some graphics packages including OpenGL, only support convex polygon for the fill algorithms. Generate a line segment For degenerate(退化) polygogerlapping edges. or edges with o. leng A set of vertices that are collinear(or that have repeated vertex positions To identify these cases, graphics systems usually leave these to the ● For concave polygons Implementation of fill algorithms and other graphics routines aremore complicated for concave polygons olit a concave polygon into a set of convex polygons
Polygon Fill Areas Implementation consideration Some graphics packages including OpenGL, only support convex polygon for the fillalgorithms. For degenerate (退化)polygons -- A set of vertices that are collinear (or that have repeated vertexpositions) --To identify these cases, graphics systems usually leave these to the programmer For concave polygons -- Implementation of fill algorithms and other graphics routines aremore complicated for concave polygons --To split a concave polygon into a set of convex polygons Generate a line segment Overlapping edges, or edges with 0 length 7
Identifying Concave Polygons Characteristics e At least one interior angle >1800 >180° Extension of some edges intersect other o Line segment of some pair of interior points intersects the be Doundary Mathematically The cross products of adjacent edges Convex: the same sign (E1XE2)>0 Concave: some are positive and (E2×E3)2>0 (E3×E4)2<0 some are negative (E4×E5)2>0 (next slide for the detail) (E3×E)2>0 (E6×E1)2>0
Identifying ConcavePolygons Characteristics At least one interior angle>180o ; Extension of some edges intersect other; Line segment of some pair of interior points intersects the boundary. Mathematically The cross products of adjacent edges Convex: the same sign Concave: some are positive and some are negative (next slide for the detail ) 8
Splitting Concave Polygons a concave polygon with six edges Edge vectors for this polygon E1=(100)E2=( E E E3=(1,-10)E4=(030 E3=(3.00)E=(0-30) E2 E The cross product for two adjacent E dge vectors 0 E1XE2=(001)!E2×E3=(0,0,-2) Splitting a concave polygon using E E4=E4×E3=(009) the vector method (03)E5×E。E6×E1=(00.3) Determinant form i j k Spl(t, the polygon along the line of ax b= det al a2 a3 vector E2. The two new polygons b, b2 b3 9)ia2ba+jab1+ka1b2-iaab2-jay b,. are both convex
E2E3 = (0,0,−2) E4 E5 = (0,0,9) E6E1= (0,0,3) E1 E2 = (0,0,1) E3 E4 = (0,0,3) E5 E6 Split the =(0,0,9) polygon along the line of vector E2 .The two new polygons A concave polygon with six edges. Edge vectors for this polygon: E1 = (1,0,0) E2 = (1,1,0) E3 = (1,−1,0) E4 = (0,3,0) E5 = (− 3,0,0) E6 = (0,−3,0) The cross product for two adjacent edge vectors: Splitting ConcavePolygons Splitting a concave polygon using the vectormethod Determinant form are both convex. 9
Inside-Outside Tests ● Inside- Outside test rea-filling algorithms and other graphics processes often need to identify interior regions of objects For simple object, it is a straightforward process For complex objects, graphics packages normally use either 1.Odd-Even(a f-5)rule(Odd-Parity rule or Even-Oddrule) 2. Non-zero winding(環繞) number rule
Inside-Outside Tests Inside-Outside test ▪ Area-filling algorithms and other graphics processes often need to identify interior regions of objects. ▪ For simple object, it is a straightforward process. ▪ For complex objects, graphics packages normally use either: 1. Odd-Even (奇偶) rule (Odd-Parity rule or Even-Odd rule) 2. Non-zero winding (環繞) number rule 10