Nonconvex polygon identifier

• US 5,347,619 A
• Filed: 04/30/1991
• Issued: 09/13/1994
• Est. Priority Date: 04/30/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Erb, David J.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): HUYNH, BA
• Application Number:
  US07/693,828
• Time in Patent Office: 1,232 Days
• Field of Search: 395/120, 395/121, 395/125, 395/126, 395/127, 395/129, 395/133, 395/118, 395/141
• US Class Current: 345/426
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A method is provided for distinguishing nonconvex polygons from complex polygons. The present invention compares the edges of a polygon for self intersection points. Initially, "base" and "compare" edges are designated and bounding boxes for each of these edges are determined. The bounding boxes are then compared and if they intersect the edges may have points in common, whereas if no intersection occurs, then there are no common points and the edges are incremented and a comparison of other edges occurs. If it is determined that bounding boxes intersect, the intersection point for the edges under consideration is determined. If this intersection point lies within both bounding boxes, then the polygon is complex and the test ends. However, if the intersection point is outside either bounding box, then the edges are incremented and processing continues until all relevant edges have been considered.

Claims

1. A computer implemented method of identifying a polygon to be displayed on a computer graphics system, said method comprising the steps of:

determining a bounding box for each of at least two non-adjacent edges of said polygon, said bounding boxes having dimensions corresponding to x and y coordinates of said at least two edges;

determining a point of intersection between lines representing said at least two non-adjacent edges;

comparing said point of intersection with each of said bounding boxes; and

utilizing the results of said comparison to determine whether said polygon is a complex polygon having self intersecting edges and multiple y scan lines for a single x value, said polygon to be scan converted by said computer graphics system.

2. A method according to claim 1 wherein said step of determining a bounding box comprises the steps of designating one of said at least two edges as a base edge and another of said edges as a compare edge.

3. A method according to claim 2 wherein said step of utilizing comprises the steps of:

determining if said point of intersection is within each of said bounding boxes; and

identifying said polygon as a complex polygon.

4. A method according to claim 3 wherein said step of identifying comprises the steps of:

invoking procedures to display said complex polygon by filling said complex polygon with color; and

displaying said complex polygon on said computer graphics system.

5. A method according to claim 2 wherein said step of utilizing comprises the steps of:

determining if said bounding boxes intersect;

determining if said point of intersection is outside at least one of said bounding boxes;

identifying said polygon as a nonconvex polygon when all of said points of intersection between said base edge and said compare edge are not within associated ones of said bounding boxes, or none of said bounding boxes intersect.

6. A method, according to claim 5 wherein said step of identifying comprises the steps of:

invoking procedures to display a nonconvex polygon by filling said nonconvex polygon with color; and

displaying said nonconvex polygon on said computer graphics system,

7. A method according to claim 5 wherein said step of identifying comprises the steps of:

incrementing said base edge and said compare edge;

determining an incremented bounding box for said incremented base edge and said incremented compare edge;

determining a point of intersection of said incremented based edge and said incremented compare edge; and

determining if said incremented point of intersection lies outside either of said incremented bounding boxes.

8. A method according to claim 7 wherein said step of incrementing comprises the step of incrementing said base edge and said compare edge by a factor of two.

9. A method according to claim 8 wherein said step of determining a point of intersection comprises the steps of:

computing the slope of said base and said compare edges; and

computing the point of intersection between said base edge and said compare edge, based upon said computed slope.

10. A system for identifying a polygon to be displayed on a computer graphics system, comprising:

means for inputting said polygon to said computer graphics system in order to display said polygon;

means for determining a bounding box for each of at least two non-adjacent edges of said input polygon, said bounding boxes having dimensions corresponding to x and y coordinates of said at least two non-adjacent edges;

means for determining a point of intersection between lines representing said at least two non-adjacent edges;

processor means for comparing said point of intersection with each of said bounding boxes; and

means for utilizing the results of said comparison to determine whether said input polygon is a complex polygon having self intersecting edges and multiple y scan lines for a single x value.

11. A system according to claim 10 wherein said means for determining a bounding box comprises means for designating one of said at least two edges as a base edge and another of said edges as a compare edge.

12. A system according to claim 11 wherein said means for utilizing comprises:

means for determining if said point of intersection is within each of said bounding boxes; and

means for identifying said polygon as a complex polygon.

13. A system according to claim 12 wherein said means for identifying, comprises:

means for invoking procedures to display said complex polygon by filling said complex polygon with color; and

means for displaying said complex polygon on said computer graphics system,

14. A system according to claim 11 wherein said means for utilizing comprises:

means for determining if said bounding boxes intersect;

means for determining if said point of intersection is outside at least one of said bounding boxes;

means for identifying said polygon as a nonconvex polygon when all of said points of intersection between said base edge and said compare edge are not within associated ones of said bounding boxes, or none of said bounding boxes intersect.

15. A system according to claim 14 wherein said means for identifying comprises:

means for invoking procedures to display a nonconvex polygon by filling said nonconvex polygon with color; and

means for displaying said nonconvex polygon on said computer graphics system.

16. A system according to claim 14 wherein said means for identifying comprises:

means for incrementing said base edge and said compare edge;

means for determining an incremented bounding box for said incremented base edge and said incremented compare edge;

means for determining a point of intersection of said incremented base edge and said incremented compare edge; and

means for determining if said incremented point of intersection lies outside either of said incremented bounding boxes.

17. A system according to claim 16 wherein said means for incrementing comprises means for incrementing said base edge and said compare edge by a factor of two.

18. A system according to claim 17 wherein said means for determining a point of intersection comprises:

means for computing the slope of said base and said compare edges; and

means for computing the point of intersection between said base edge and said compare edge, based upon said computed slope.