Method and apparatus for clipping non-planar polygons

• US 5,767,859 A
• Filed: 09/28/1995
• Issued: 06/16/1998
• Est. Priority Date: 09/28/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Rossin, Theodore G., Krech, Alan S. Jr.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/535,499
• Time in Patent Office: 992 Days
• Field of Search: 395/134, 395/123, 395/130
• US Class Current: 345/620
• CPC Class Codes: G06T 15/30 Clipping

Abstract

A hardware graphics accelerator accepts lists of polygon vertices from an application environment running application and systems graphics software. After a polygon is rotated and translated as needed, it is checked for trivial accept/reject against the clip limits of the viewing volume, but is not otherwise clipped. Polygons that are not rejected are decomposed into triangles before any other operations on them are performed. After decomposition the triangles are illuminated by light sources, if desired and then clipped by a triangle clipper, rasterized, and the results sent to a frame buffer for display. The triangle clipper incorporates trivial accept/reject operation, and is capable of operating on non-planar quadrilaterals. It avoids ugly artifacts during certain clip operations when the diagonal used to decompose a quadrilateral into triangles intersects a clip plane not parallel to the viewing axis. It does this by replacing the point of intersection along that diagonal that the clipper would ordinarily find with a point that is the projection of that diagonal onto a line between two adjacent points of intersection of the actual edges of the quadrilateral with the clip plane.

Claims

1. A method of clipping a non-planar polygon with a clipper that obeys rules for clipping triangles, the method comprising the steps of:

(a) selecting a clip plane;

(b) traversing the edges of the non-planar polygon and finding any points of intersection between the edges of the non-planar polygon and the selected clip plane;

(c) decomposing the non-planar polygon into a plurality of adjoining triangles, each of which share with another as a common edge a diagonal of the non-planar polygon;

(d) selecting a triangle to clip;

(e) finding, if it exists, the intersection of a projection of the diagonal associated with the selected triangle with a line segment between two adjacent points found in step (b); and

(f) clipping the selected triangle with a clipper obeying rules for clipping triangles, except that if there is an intersection between the diagonal associated with the selected triangle and the selected clip plane, then the intersection found in step (e) is used in place of that aforesaid intersection within an output list of vertices produced by the clipper.

2. A method as in claim 1 wherein the non-planar polygon is a quadrilateral.

3. A method as in claim 1 wherein the non-planar polygon is a convex polygon having at least five edges.

4. Apparatus for clipping a non-planar quadrilateral described by an original list of vertices stored in a memory, the apparatus comprising:

first circuitry, coupled to operate on the original list of vertices, that finds intersections between a clip plane and edges of the non-planar quadrilateral;

second circuitry that decomposes the non-planar quadrilateral into triangles separated by a diagonal and described by respective first and second lists of vertices;

third circuitry, coupled to the first and second circuitry, that finds an intersection-by-projection of the diagonal and a line between the intersections found by the first circuitry; and

a triangle clipper, coupled to the first and second lists of vertices and to the intersection-by-projection, that clips in accordance with rules for a triangle clipper except that it substitutes the point found by intersection-by-projection for any point of intersection between the diagonal and the clipping plane.

5. Apparatus as in claim 4 wherein the first, second and third circuitry and the triangle clipper comprise at least one state machine, an associated collection of registers and fourth circuitry that performs arithmetic computation.