Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1996-01-24
2001-01-09
Au, Amelia (Department: 2723)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S440000
Reexamination Certificate
active
06172682
ABSTRACT:
TECHNICAL FIELD
This invention relates to a method for processing image data and more particularly, to a method to determine if a rectangle is inside, outside, or intersects, a polygon.
BACKGROUND OF THE INVENTION
Clipping is the process of modifying a subject figure by retaining the part disposed inside the given clip boundary and removing the part disposed outside the clip boundary. The subject figure may be a graphic image or a primitive element thereof, such as a line, polygon, circle, raster image or bitmapped character. The clip boundary is a polygon ranging from a simple rectangle to any arbitrary shape. Clipping is extensively employed in computer graphics and image processing, in computer operating systems that display windows, and in printers such as laser printers.
There are two well-known polygon clipping algorithms, the Sutherland-Hodgman and the Liang-Barsky algorithms (See Ivan E. Sutherland and Gary W. Hodgroan, Reentrant polygon clipping, Communications of the ACM, volume 17 (1974), no. 1, page 32-42 and You-Dong Liang and Brian A. Barsky, An analysis and algorithm for polygon clipping Communications of the ACM, volume 26 (1983), no. 11 page 868-877). They will be discussed briefly in this section.
The Sutherland-Hodgman algorithm clips the polygon through a pipeline with a different boundary line in each stage of the pipeline. Suppose the boundary lines are ordered in this manner: the left, right, bottom and then the top boundary lines. The algorithm first clips the polygon against the left boundary line. The result of this stage is then fed to be clipped against the right boundary line in the second stage. Similarly, the results of the second, and the third stages are fed to be clipped against the bottom and top boundary lines respectively. The resultant polygon of the fourth stage is the resultant polygon of the clipping process.
In each stage, each of the edges of the input polygon is handled separately into four cases.
1) Both endpoints are inside the boundary line. The second endpoint is sent to the outside
2) Both endpoints are outside the boundary line. Both are discarded.
3) The first endpoint is inside the boundary line and the second endpoint is outside the boundary line. Compute the intersection point the edge makes with the boundary line and output it.
4) The first endpoint is outside the boundary line and the second endpoint is inside the boundary line. Compute the intersection point the edge makes with the boundary line, output it, and then output the second endpoint.
The Liang-Barsky algorithm also handles each edge separately. Each edge is parameterized and clipped against the window. When processing an edge, the edge is extended to infinity at both ends. There are two cases.
1) The extended edge originates from a corner region; intersects a boundary line to enter an edge region; intersects another boundary line to enter the window; intersects a boundary line to exit to an edge region; and finally intersects the last boundary line to enter a corner region. If the edge overlaps the first portion of the extended edge, then output the corner of the corner region it originates from. If the edge overlaps the portion of the extended edge that enters the window, then compute the intersection point and output it. If the first endpoint of the edge is inside the window, output it. If the second endpoint of the edge is inside the window, output it as well. If the edge overlaps the portion of the extended edge that exits the window, compute the intersection point on the window boundary and output the intersection point.
2) The extended edge originates from a corner region; intersects a boundary line to enter an edge region; intersects another boundary line to enter another corner region on the same invisible side as the originating corner region; intersects a boundary line to enter an edge region; and finally intersects a boundary line to enter another corner region. If the edge overlaps the first portion of the extended edge, then output the corner of the originating corner region. If the edge overlaps the portion of the extended edge that exits the second corner region, then the corner of that corner region is also sent to the output.
One problem with the prior art clipping algorithms is their unsatisfactory performance in handling irregular polygon clip boundaries. To increase the performance of any clipping algorithm, a first pass should determine if a clipping algorithm needs to be used at all. For example, if the subject figure is entirely inside or outside the clip boundary no clipping is necessary. Only if the subject figure intersects with the clip boundary is the complicated clipping algorithm needed. Therefore, a quick “insideness” test can determine if the clipping algorithm needs to be used.
There are known methods that test whether a point lies inside a polygon. By definition, filling the polygon causes all points inside to be painted. Thus, known insideness methods use a filling algorithm.
Generally, all of the filling algorithms disclosed in the prior art are based on defining the interior of a polygon by a winding number. The winding number for a point is the number of times that point is circled in tracing the polygon boundary. There are two well known winding number methods: odd/even and non-zero.
Under the odd/even winding approach, defining a point as interior if an odd number of boundaries are crossed to reach it is equivalent to defining interior points as having an odd winding number. The non-zero winding number involves giving each edge a direction number −1 or +1, based on whether one moves up or down along the edge as one traces the polygon boundary counter-clockwise. As one steps along a scan line and notes intersections with the boundary, the direction numbers of the edges crossed are added.
For a simple path, it is intuitively clear what region lies “inside.” However, for a more complex path—for example, a path that intersects itself or has one or more subpaths that enclose another—the interpretation of “inside” is not so obvious.
The non-zero winding number rule determines whether a given point is inside a path by conceptually drawing a ray from that point to infinity in any direction and then examining the places where a segment of the path crosses the ray. Here's how it works:
Starting with a count of zero, add one each time a path segment crosses the ray from left to right and subtract one each time a path segment crosses the ray from right to left. After counting all the crossings, if the result is zero then the point is outside the path. Otherwise it is inside.
Note, the rule does not specify what to do if a path segment coincides with or is tangent to the ray. Since any ray will do, one may simply choose a different ray that does not encounter such problem intersections.
With the non-zero winding number rule, a simple convex path yields inside and outside as you would expect. Now consider a five-pointed star, drawn with five connected straight line segments intersecting each other as shown in FIG.
1
A. The entire area enclosed by the star, including the pentagon in the center, is considered inside by the non-zero winding number rule. For a path composed of two concentric circles, if they are both drawn in the same direction as in
FIG. 1B
, the areas enclosed by both circles are inside, according to the rule. If they are drawn in opposite directions as in
FIG. 1C
, only the “doughnut” shape between the two circles is inside, according to the rule; the “doughnut hole” is outside.
An alternative to the non-zero winding number rule is the even-odd rule. This rule determines the “insideness” of a point by drawing a ray from that point in any direction and counting the number of path segments that the ray crosses. If this number is odd, the point is inside; if even, the point is outside.
The even-odd rule yields the same results as the non-zero winding number rule for paths with simple shapes, but yields different results for more complex shapes. For the five-pointed star drawn with five intersecting line
Claiborne Steven J.
Papke Jeff H.
Au Amelia
Baca Anthony J
Hewlett-Packard Co.
Miller Martin
LandOfFree
Detecting insideness of a rectangle to an arbitrary polygon does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detecting insideness of a rectangle to an arbitrary polygon, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting insideness of a rectangle to an arbitrary polygon will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476715