Inside-Outside Tests Odd-Even rule( odd-Parity rule, Even-Odd rule 1. Draw a line: (the line path doesn'tintersect any line-segment endpoints) From any position P to a distant point outside the coordinate extents of the polygon 2. Counting the number of edge crossing along the line 3. If the number of polygon edges crossed by this line is odd(F) then P is an interior point exterior Else P is an exterior point P1● Interior P2 0 PM Self-intersecting Odd-Even Rule closed polyline (From Wiki) Camputer Graphics with Open GL, Third Edition, by Donald Hearn and M. Pauline Baker ISBN0-13-0-15390-70 200M Pearson Education, Inc., Upper Saddle River, NJ. All rights reserve
Odd-Even rule (Odd-Parity Rule, Even-OddRule): 1. Draw a line: (the line path doesn’t intersect anyline-segment endpoints) From any position P to a distant point outside the coordinateextents of the polygon 2. Counting the number of edge crossing along the line. 3. If the number of polygon edges crossed by this line is odd (奇) then P is an interior point. Else P is an exterior point 11 Inside-Outside Tests Self-intersecting closed polyline P1 P1 (FromWiki) P2 P2
Inside-Outside Tests Non- zeroWinding(環繞) Number rule: Counts the winding number of a point Non-zero: interior points Zero: exterior points Winding number of a closed curve around a given point The number of times the curve(polygon edges) wind counterclockwise around that point 2 Pic From Wiki)
Non-zeroWinding (環繞) Number Rule : ▪ Counts the winding number of a point ▪ Non-zero: interior points ▪ Zero: exterior points ▪ Winding number of a closed curve around a given point: ▪ The number of times the curve (polygon edges)wind counterclockwise around thatpoint. Inside-Outside Tests (Pic.FromWiki) 12
Inside-Outside Tests Non-zero Winding Number Rule(cont ) Set up vectors along the edges and initialing the winding number to o 2. Imagine a line drawn from any position p to a distant point beyond the coordinate extents of the object 3. Count the number of edges that cross the line in each direction Add 1 to the winding number a polygon edge crosses the line from right to left(2) Subtract 1 exterior An edge crosses from left to right(>) If the winding number is non-zero, then c P is defined to be an interior point Interior Else P is taken to be an exterior point Camputer Graphics with Open GL, Third Edition, by Donald Hearn and M. Pauline Baker ISBN0-13-0-15390-70 200M Pearson Education, Inc., Upper Saddle River, NJ. All rights reserve
Non-zeroWinding Number Rule (cont.): 1. Set up vectors along the edges and initialing the winding number to 0. 2. Imagine a line drawn from any position P to a distant point beyond the coordinate extents of the object. 3. Count the number of edges that cross the line in each direction. Add 1 to the winding number: A polygon edge crosses the line from right to left ( ). Subtract 1: An edge crosses from left to right ( ). 4. If the winding number is non-zero,then P is defined to be an interior point Else P is taken to be an exteriorpoint. Inside-Outside Tests 13
EXample: self-intersecting closed polyline exterior exterior G G Interior Interior B Odd- Even rule Nonzero winding- Number rule +1 Figure 4-12 Identifying interior and exterior regions of a closed polyline that contains self-intersecting segments Odd; interior: even: exterior Non-zero interior. zero exterior Camputer Graphics with Open GL, Third Edition, by Donald Hearn and M. Pauline Baker ISBN0-13-0-15390-7o 2004 Pearson Education, Inc, Upper Saddle River, NJ. All rights reserve
Odd: interior; even:exterior. Non-zero:interior;zero:exterior. Example: self-intersecting closed polyline :+1 Figure 4-12 :-1 14
Polygon Representation Polygon Tables(Fig. 4-16 e Typically, the objects in a scene are described as sets of polygon surface facets with information Coordinate, color, transparency, lighting properties e In systems, the information for polygons facets are represented by tables- polygon data tables ● GeometricTables Vertex Table: Edge Table. Surface -Facet Table Attribute Table Normal; Transparency; Reflectance; Texture Coordinates
Polygon Representation Polygon Tables (Fig.4-16) Typically, the objects in a scene are described as sets of polygon surface facets with information: Coordinate, color, transparency, lightingproperties… In systems, the information for polygons facets are representedby tables – polygon datatables: GeometricTables VertexTable;EdgeTable; Surface-FacetTable AttributeTables Normal; Transparency;Reflectance;Texture Coordinates 15