COMPUTER GRAPHICS CLIPPING SYSTEM FOR POLYGONS

• US 3,816,726 A
• Filed: 10/16/1972
• Issued: 06/11/1974
• Est. Priority Date: 10/16/1972
• Status: Expired due to Term

• Current Assignee: Gary W. Hodgman, Sutherland, Ivan E.
• Original Assignee: Gary W. Hodgman, Sutherland, Ivan E.
• Inventors: Sutherland, Ivan E., Hodgman, Gary W.
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Malzahn, David H.
• Application Number:
  US05/298,084
• Time in Patent Office: 603 Days
• Field of Search: 235/151,152 340/324.1,172.5 33/1K 444/1
• US Class Current: 345/623
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G09G 1/06 using single beam tubes G09G1/26, G09G1/28 take precedence, e.g. three-dimensional or perspective representation, rotation or translation of display pattern, hidden lines, shadows G09G1/28 takes precedence; stereoscopic TV-systems, details thereof H04N13/00; oscilloscopes for three-dimensional representation G01R13/206; vectorscopes G01R13/208

Abstract

A system is disclosed for clipping three-dimensional polygons for use in a computer-graphics display. The system removes from each polygon all parts that lie outside an arbitrary, planefaced, convex polyhedron, e.g. a truncated pyramid defining a viewing volume. The polygon is defined by data representing a group of vertices and is clipped separately in its entirety against each clipping plane (of the polyhedron). In a multiplestage structure as disclosed, each stage clips the polygon against a single plane and requires storage for only two vertex values. A time-sharing embodiment of the system is also disclosed. The disclosed system also incorporates the use of a perspective transformation matrix which provides for arbitrary field-of-view angles and depth-of-field distances while utilizing simple, fixed clipping planes.

Claims

1. A clipping method for defining select data, as for a perspective display comprising the steps of:

representing data in the form of electrical signals manifesting coordinate locations;

defining a polyhedron for containing select data;

testing said electrical signals to generate those signals defining data within sAid polyhedron as said select data.

2. A clipping method according to claim 1 wherein said electrical signals represent vertices in three-dimensional space by four-dimensional coordinates.

3. A method according to claim 1 wherein said electrical signals represent vertex locations defining a polygon, whereby said select data defines the portion of said polygon that lies within said polyhedron.

4. A method according to claim 3 wherein said testing step includes testing said vertex locations in relation to sides of said polyhedron in sequence.

5. A clipping method according to claim 3 wherein said testing step includes a step of computing data representative of intersections between represented data and a plane of said polyhedron to thereby define other vertex locations.

6. A method according to claim 3 wherein said polyhedron comprises a pyramidal vision projection.

7. A method according to claim 6 wherein said pyramid is truncated.

8. A method according to claim 6 wherein said testing step includes testing said vertex locations sequentially in relation to each side of said pyramidal vision projection.

9. A system according to claim 6 further including a preliminary step of processing said electrical signals to produce matrix-multiplied signals whereby to translate said pyramidal vision projection.

10. A clipping method for processing data that is representative of a polygon and is manifest by electrical signals specifying vertex locations of such polygon, comprising the steps of:

defining a pyramidal field of vision by at least four defined surfaces;

testing said electrical signals representing said vertex locations in relation to said defined surfaces to identify selected vertex locations as are within said field of vision;

determining intersection locations of said polygon with said pyramidal field of vision to define a portion of said polygon within said field of vision in combination with said selected vertex locations.

11. A system for clipping a polygon comprising:

means for providing vertex electrical signals representative of vertex locations specifying said polygon;

means for registering a pyramidal projection figure including a plurality of planes;

means for receiving said electrical signals representative of vertex locations, and coupled to said means for registering, to identify certain of said vertex electrical signals as representative of vertex locations internal of said figure; and

means for receiving said electrical signals representative of vertex locations, and coupled to said means for registering, to provide intersection electrical signals representative of intersections between said polygon and said figure to specify, in combination with said certain vertex electrical signals, the portion of said polygon within said figure.

12. A system according to claim 11 wherein said means for providing vertex electrical signals comprises means for providing signals representative of homogeneous coordinates to define vertices in three-dimensional space.

13. A system according to claim 12 further including a matrix multiplier for acting on said vertex electrical signals for translating said signals in relation to said pyramidal projection.

14. A system according to claim 11 wherein said means for registering a figure includes means for registering data to specify six planes definitive of a truncated pyramid.

15. A system according to claim 11 wherein said means for registering a figure includes means for registering data to specify a plurality of planes definitive of a field of vision.

16. A system according to claim 15 wherein said means for providing vertex electrical signals provides coordinate signals representative of coordinate values dimensionally related to said planes definitive of said field of vision and wherein said means for identifying includes means for identifying vertex signals in relation to said planes.

17. A system according to claim 16 wherein said means for identifYing vertex signals in relation to said planes includes a plurality of registers for said vertex signals and means for sequentially testing said coordinate signals in relation to each of said planes.

18. A system according to claim 17 wherein said means for sequentially testing includes an arithmetic unit and means for time sharing said unit in relation to said plurality of registers.

19. A system according to claim 17 wherein said means for sequentially testing includes a plurality of individual processing units.