Report

Computer Graphics Scan Conversion Polygon Faculty of Physical and Basic Education Computer Science Dep. 2012-2013 E-mail: [email protected] [email protected] Lecturer: Azhee W. MD. Scan Conversion polygon Polygon Polygon Classifications Identifying Concave Polygons Splitting Concave Polygons Inside-Outside Tests 2 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Polygon A polyline is a chain of connected line segments. When starting point and terminal point of any polyline is same, i.e. when polyline is closed then it is called polygon. 3 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Polygon Classifications interior angle: is an angle inside the polygon boundary that is formed by two adjacent edges. convex polygon: interior angles of a polygon are less than or equal to 180° Or Convex : is a polygon in which the line segment joining any two points within the polygon lies completely inside the polygon 4 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Polygon Classifications Concave polygon: the polygon that is not convex. or Concave: is a polygon in which the line segment joining any two points within the polygon may not lie completely inside the polygon. 5 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Identifying Concave Polygons 1. At least one interior angle greater than 180° 2. The extension of some edges of a concave polygon will intersect other edges 3. Some pair of interior points will produce a line segment that intersects the polygon boundary 4. Find a cross product for adjacent edges For a convex polygon all cross products will be of the same sign (positive or negative) If some cross products yield a positive value and some a negative value, we have a concave polygon 6 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Convex or concave? Convex if no line that contains a side of the polygon contains a point in the interior of the polygon. Concave or non-convex if a line does contain a side of the polygon containing a point on the interior of the polygon. 7 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Identifying Concave Polygons(2) 8 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 Splitting Concave Polygons: Cross Product 9 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 example Q)Use cross product to find normal vector of a polygon with the following vertices: (0.2, -0.4, 0.2), (0.6, 0.7, 0.5), (-0.3, 0.4, -0.3), (-0.4, -0.3, -0.4) Answer: Ek = Vk+1 - Vk E1 = (a1, a2, a3), E2 = (b1, b2, b3) E1 x E2 = (a2b3 − a3b2, a3b1 − a1b3, a1b2 − a2b1) V1 = (0.2, -0.4, 0.2), V2 = (0.6, 0.7, 0.5), V3 = (-0.3, 0.4, -0.3) E1 = V2 – V1 = (0.6, 0.7, 0.5) - (0.2, -0.4, 0.2) = (0.4, 1.1, 0.3) E2 = V3 – V2 = (-0.3, 0.4, -0.3) - (0.6, 0.7, 0.5) = (-0.9, -0.3, -0.8) E1 x E2 = (1.1*-0.8-0.3*-0.3, 0.3*-0.9-0.4*-0.8, 0.4*-0.3-1.1*-0.9) = (-0.79, 0.05, 0.87) University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 10 Splitting Concave Polygons: Set of Triangles University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 11 Splitting Concave Polygons: Set of Triangles (2) University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 12 Inside-Outside Tests It is not clear which regions of the xy plane we should call interior and which regions we should designate as exterior for a complex polygon with intersecting regions. algorithms: odd-even rule nonzero winding-number rule University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 13 Inside-Outside Tests (2) odd-even rule Draw a reference line from any position to a distant point outside a closed polyline The line must not pass through any endpoints Count the number of line segments crossed along this line If the number is odd then the region considered to be interior Otherwise, the region is exterior University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 14 Inside-Outside Tests (2) nonzero winding-number rule Counts the number of times the boundary of an object winds around a particular point in the counterclockwise direction The count is called the winding number Initialize winding number to zero Draw a reference line from any position to a distant point The line must not pass through any endpoints Add one to the winding number if the intersected segment crosses the reference line from right to left (counterclockwise) Subtract one from the winding number if the segment crosses from left to right (clockwise) If winding number is nonzero, the region is considered to be interior Otherwise, the region is exterior University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 15 Example Q) Use nonzero winding number rule to determine the interior and exterior regions of the following polygon ? University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 16 Example University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 17 References Donald Hearn, M. Pauline Baker, Computer Graphics with OpenGL, 3rd edition, Prentice Hall, 2004 Chapter 3, 4 University of sulaimanyiah - Faculty of Physical and Basic Education - Computer Dep. 2012-2013 18