More info

Sunday, 2 March 2014

Computer Graphics Notes - Lab 15 - INSIDE -OUTSIDE TESTS

Area- filling algorithm and other graphics processes often need to identify interior regions of objects. So far, we have discussed area filling only in terms of standard polygon shapes. In elementary geometry, a polygon is usually defined as having no self intersections. Examples of standard polygons include triangles, rectangles, octagons and decagons. The component edges of these objects are joined only at the vertices, and otherwise the edges have no common points in the plane. Identifying the interior regions of standard polygons is generally a straightforward process.

Determining the inclusion of a point in a 2D planar polygon is a geometric problem that results in interesting algorithms. Two commonly used methods are:

1.     The Crossing Number (cn) method: It is also called odd-even rule or odd parity rule or odd rule. We apply this method by conceptually drawing a line from any position P to a distant point outside the coordinate extents of the object and counting the number of edge crossings along the line. If the number of polygon edges crossed by this line is odd, then P is an interior point. Otherwise, P is an exterior point. To obtain an accurate edge count, we must be sure that the line path we choose does not intersect any polygon vertices.

The Winding Number (wn)/ nonzero winding number rule method: This method counts the number of times the polygon edges wind around a particular point in the counterclockwise direction. This count is called the winding number. Here instead of just counting the intersections, we have to give directions to each boundary line crossed and we have to sum these direction numbers. The direction number indicates the direction the polygon was drawn relative to the line segment we have constructed for the test. Let a point (xa, ya) is a test point and line y = ya is a horizontal line runs from outside the polygon to point (xa, ya). The polygon edges crossed by this line could be drawn in two ways. If the edge crosses the positive ray from below to above, the crossing is positive (+1); but if it crosses from above to below, the crossing is negative (-1). One then simply adds all crossing values to get wn. For polygons or two dimensional objects, the point is said to be inside when the value of winding number is nonzero.

If a polygon is simple (i.e. it has no self intersections), then both methods give the same result for all points. But for non-simple polygons, the two methods can give different answers for some points.


In generally, scan-line fill of regions with curved boundaries more work than polygon filling, since intersection calculations now involve nonlinear boundaries. For simple curves such as circles or ellipses, performing a scan-line fill is a straightforward process. We only need to calculate the two scan-line intersections on opposite sides of the curve. This is the same as generating pixel positions along the curve boundary, and we can do that with the midpoint method. Then we simply fill in the horizontal pixel spans between the boundary points on opposite side of the curve. Symmetries between quadrants are used to reduce the boundary calculations.

Scan Filling Curved Objects

No comments:

Post a Comment