Polygon edge clipping

• US 4,958,305 A
• Filed: 11/04/1987
• Issued: 09/18/1990
• Est. Priority Date: 11/04/1987
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Piazza, Thomas A.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/116,708
• Time in Patent Office: 1,049 Days
• Field of Search: 364/521, 364/522, 340/724, 340/729, 340/734
• US Class Current: 345/427
• CPC Class Codes: G06T 15/30 Clipping

Abstract

A method for clipping a source polygon to a view window permits the valid (i.e. potentially visible) edges or portions of edges of the source polygon and of the view window boundary edges to be sequentially output for further processing, while determining the valid parts in a predetermined direction around the perimeter of the source polygon, without having to store (other than for a first entry point) the value of exit points from or entry points to the view window. Only an end point of an edge of the source polygon is considered at a time so that a maximum of two intersection point determinations between the source polygon edge and view window boundary planes outside of which the source polygon edge lies are required to ascertain if a portion of the source polygon edge is valid.

Claims

1. A method for clipping a convex source polygon to a view-window defined by boundary edges for forming a clipped figure, wherein a respective boundary edge plane coinciding with each boundary edge of the view window is predeterminedly defined, comprising:

determining intersection points between edges of the source polygon and boundary edges of the view window while proceeding from a randomly selected vertex of the source polygon in a predetermined direction around the perimeter of the source polygon;

assigning each intersection point determined as either an entry point to, or an exit point from, the view window in response to the predetermined direction along the edge of the source polygon forming the respective intersection point;

sequentially supplying as encountered in the predetermined direction around the perimeter of the source polygon;

source polygon edges that lie entirely within the view window, valid portions of source polygon edges that include an exit point and/or an entry point, and a valid portion of the boundary edges of the view window from an exit point to the next determined entry point before supplying the valid portion of the source polygon edge that includes the next determined entry point; and

substituting the value of the first entry point determined for the value of the next determined entry point when a last exit point assigned does not include a corresponding next determined entry point after the step of determining has returned to the randomly selected vertex,

wherein the step of sequentially supplying is performed while the edges of the clipped figure are being determined without having to recall the valid portion of the edge of the source polygon and the portion of the boundary edges of the view window from the first determined exit point to the entry point next determined.

2. The method as in claim 1, wherein the source polygon is defined in three dimensions and further including the step of projecting the source polygon into two dimensions before the step of determining is performed.

3. The method as in claim 1, further including substituting the value of the entry point for the value of the first end point of the edge of the source polygon forming the respective entry point and substituting the value of the exit point for the value of the second end point of the edge of the source polygon forming the respective exit point.

4. The method as in claim 1, further including disregarding from further consideration any edge of the source polygon for which both end points of the any edge lie outside the same boundary edge plane.

5. The method as in claim 1, wherein, for each edge of the source polygon, the step of determining further includes:

determining an alpha intersection point of an edge of the source polygon with a first boundary edge plane the edge crosses when the first end point and second end point of the edge lie on opposite sides of the first boundary edge plane;

assigning an appropriate exit or entry code to the alpha intersection point and replacing the value of the first end point of the edge with the value of the alpha intersection point when the alpha intersection point lies on a boundary edge;

disregarding the edge from further consideration when the second end point of the edge lies outside the first boundary plane;

determining a beta intersection point of the edge with the second boundary edge plane that the edge crosses when the alpha intersection point and the second end point of the edge lie on opposite sides of the second boundary edge plane when the alpha intersection point does not lie on a boundary edge;

assigning an appropriate entry or exit code to the beta intersection point and replacing the value of the alpha intersection point with the value of the beta intersection point when the beta intersection point lies on a boundary edge; and

disregarding the edge from further consideration when the beta intersection point does not lie on a boundary edge.

6. The method as in claim 1, further including providing the boundary edges of the view window in a connected order for defining the perimeter of the clipped figure when the source polygon encircles the view window.

7. The method as in claim 6, wherein the view window is rectangular and further wherein the step of providing further includes outputting the boundary edges of the view window in a sequential connected order when a first edge of the source polygon intersects a predetermined first boundary plane from outside to inside the first boundary plane when proceeding in the predetermined direction along the first edge, the first edge intersecting the first boundary plane outside a predetermined second boundary plane that intersects the first boundary plane and when a second edge of the source polygon intersects the first boundary plane from inside to outside the first boundary plane when proceeding in the predetermined direction along the second edge, the second edge intersecting the first boundary plane outside a predetermined third boundary plane that intersects the first boundary plane unless a third edge of the source polygon intersects a boundary edge of the view window or a fourth edge of the source polygon intersects the first boundary plane outside the second boundary plane from inside to outside the first boundary plane when proceeding in the predetermined direction along the fourth edge, or a fifth edge of the source polygon intersects the first boundary plane outside the third boundary plane from outside to inside the first boundary plane when proceeding in the predetermined direction along the fifth edge.

8. A method for forming a clipped figure from the interaction between a convex source polygon and a view window defined by boundary edges, wherein a respective boundary plane corresponding to each boundary edge so that the window lies inside each boundary plane, comprising:

determining a valid portion of edges of the source polygon in a predetermined direction around the perimeter of the source polygon that form a part of the perimeter of the clipped figure;

identifying in response to the valid portion of edges of the source polygon a derived portion of the boundary edges that forms another part of the perimeter of the clipped figure; and

providing the valid portion and the derived portion so that the perimeter of the clipped figure may be sequentially defined in a predetermined direction along the perimeter of the clipped figure by adjoining valid and derived portions such that the derived portion lying between an exit intersection point of the valid portion and a next determined entry intersection point of the valid portion may be provided before determining the valid portion following the next determined entry intersection point.

9. The method as in claim 8, where for each successive edge of the source polygon in a predetermined direction around the perimeter of the source polygon the step of determining includes:

disregarding a source polygon edge and proceeding to consider the next successive source polygon edge when both end points of the source polygon edge lie outside the same boundary plane;

determining a first intersection point of the source polygon edge with a first boundary plane outside of which the first end point of the source polygon edge lies;

coding the first intersection point as an entry point and replacing the value of the first intersection point by the value of the first end point of the source polygon edge when the first intersection point lies on a boundary edge of the view window;

disregarding the source polygon edge when the first intersection point and the second end point of the source polygon edge lie outside the same boundary plane;

determining a second intersection point of the source polygon edge with a second boundary plane outside of which the first intersection point lies;

coding the second intersection point as an entry point and replacing the value of the first intersection point by the value of the second intersection point when the second intersection point lies on a boundary edge of the view window;

disregarding the source polygon edge and proceeding to consider the next succeeding source polygon edge when the second intersection point does not lie on a boundary edge of the view window;

identifying the source polygon edge as a valid edge when the first and second end points of the polygon edge lie within the view window.

10. A method for clipping a convex source polygon to a view window for forming a clipped figure, wherein the view window is defined by boundary edges and a respective boundary edge plane coinciding with each boundary edge, each boundary edge plane dividing space into an inside region and an outside region disposed on opposite sides of each boundary plane and the view window further disposed in the inside region of each boundary edge plane, for each consecutive edge encountered in a predetermined direction around the perimeter of the source polygon from a predetermined vertex of the source polygon wherein each edge of the source polygon includes a first end point (V₁) and a second end point (V₂), the method comprising:

(a) disregarding the source polygon edge from further consideration when the points V₁ and V₂ lie in the outside region of the same boundary plane;

(b) determining an alpha intersection point of the source polygon edge with the first boundary plane encountered outside of which V₁ lies when proceeding from V₁ to V₂ ;

(c) coding the alpha intersection point as an entry point and replacing the value of V₁ with the value of the alpha intersection point when the alpha intersection point lies on a boundary edge of the view window;

(d) disregarding the source polygon edge from further consideration when the alpha intersection point and V₂ lie in the outside region of the same boundary plane;

(e) determining a beta intersection point of the source polygon edge with the second boundary plane encountered outside of which the alpha intersection point lies when proceeding from the alpha intersection point to V₂ whenever the alpha intersection point and V₂ do not lie in the outside region of the same boundary plane and the alpha intersection point does not lie on a boundary edge of the view window;

(f) disregarding the source polygon edge from further consideration when the beta intersection point does not lie on a boundary edge of the view window;

(g) coding the beta intersection point as an entry point and replacing the value of the alpha intersection point with the value of the beta intersection point when the beta intersection point lies on a boundary edge of the view window;

(h) coding a gamma intersection point of the source polygon edge with the first boundary plane encountered when proceeding from V₁ to V₂ as an exit point and replacing the value of V₂ with the value of the gamma intersection point whenever V₁, the alpha intersection point or the beta intersection point lies within the view window and V₂ lies outside a boundary plane;

(i) deriving the valid portion of the boundary edges of the view window that form a portion of the perimeter of the clipped figure from a gamma intersection point and the next determined alpha or beta intersection point coded as an entry point; and

(j) sequentially providing the valid portion of the source polygon edges and the valid portion of the boundary edges of the view window for forming contiguous portions of the perimeter of the clipped figure while the alpha, beta and gamma intersections are being determined.

11. The method as in claim 10, further including providing the boundary edges of the view window in a connected order for defining the perimeter of the clipped figure when the source polygon encircles the view window.

12. The method as in claim 11, wherein the view window is rectangular and further wherein the step of providing further includes outputting the boundary edges of the view window in a sequential connected order when a first edge of the source polygon intersects a predetermined first boundary plane from outside to inside the first boundary plane when proceeding in the predetermined direction along the first edge, the first edge intersecting the first boundary plane outside a predetermined second boundary plane that intersects the first boundary plane and when a second edge of the source polygon intersects the first boundary plane from inside to outside the first boundary plane when proceeding in the predetermined direction along the second edge, the second edge intersecting the first boundary plane outside a predetermined third boundary plane that intersects the first boundary plane unless a third edge of the source polygon intersects a boundary edge of the view window or a fourth edge of the source polygon intersects the first boundary plane outside the second boundary plane from inside to outside the first boundary plane when proceeding in the predetermined direction along the fourth edge, or a fifth edge of the source polygon intersects the first boundary plane outside the third boundary plane from outside to inside the first boundary plane when proceeding in the predetermined direction along the fifth edge.