System of polygon sorting by dissection

• US 3,889,107 A
• Filed: 09/27/1973
• Issued: 06/10/1975
• Est. Priority Date: 10/16/1972
• Status: Expired due to Term

• Current Assignee: Sutherland, Ivan E.
• Original Assignee: Sutherland, Ivan E.
• Inventors: Sutherland, Ivan E.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US05/401,479
• Time in Patent Office: 621 Days
• Field of Search: 235/152,151 340/324A,324R,172.5
• 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 polygon-dissection structure is disclosed incorporated in a system for processing geometric data, e.g. data representing three-dimensional polygons, as by subdividing such polygons to accomplish sorting of the data. The system operates to divide a working volume, e.g. a perspective pyramid, into successivelysmaller subvolumes. The separating planes are placed at arbitrary angles to coincide with the edges and surfaces of polygons that define objects to be represented. Polygons which straddle separating planes are dissected into two parts which are thereafter treated separately. Dissection by the system results in simplification in accounting for the polygons in relation to specific subvolumes. The system can be applied to the detection of those polygons which hide others thereby enabling a solution to the hidden-surface problem. Additionally, the system affords a simple mechanism for resolving shadowed portions of polygons as well as portions of polygons obstructed by semi-transparent surfaces and for explicitly computing and displaying implied lines of intersections existing between two inter-penetrating polygons. Alternatively, the system provides an efficient way of detecting if any or a multiplicity of polyhedra solids interpenetrate.

Claims

1. A method for processing data in relation to a volume of space comprising the steps of:

representing data in the form of electrical signals manifesting objects and positional relationships of said objects in said volume of space;

defining a selected viewpoint in relation to said volume of space;

selectively definiNg a specific plane in terms of electrical signals, from various possible planes lying in said volume of space, said specific plane being related to one of said objects, said possible planes including planes extending transverse to the axis of said selected viewpoint; and

testing said electrical signals manifesting objects and positional relationships of said objects in said volume of space in relation to said specific plane to generate signals that are definitive of data representing said objects on each side of said specific plane.

2. A method wherein each of the steps of claim 1 is progressively repeated in sequence to provide display electrical signals defining select portions of said objects.

3. A method according to claim 1 wherein said electrical signals represent vertex locations defining polygons.

4. A method according to claim 1 wherein said plane in said volume of space is defined coincident with an edge of one of said objects.

5. A method according to claim 4 further including the steps of:

representing the opacity of said objects with opacity electrical signals and modifying said signals definitive of data representing said objects on each side of said specific plane in accordance with said opacity electrical signals.

6. A data processing system comprising:

means for providing sets of electrical signals representative of positional vertices definitive of polygons in space;

first means for registering one set of said sets of electrical signals;

second means for registering representations definitive of a plane in said space;

processing means connected to receive signals from;

said means for providing signals definitive of polygons in space, said first register means and said second register means, for processing said one set of electrical signals with another set of said sets of electrical signals provided from said means for providing, subsequent to said one set, to provide separate developed sets of electrical signals representative of vertices sorted with respect to said plane in said space, said processing means including a pair of output means for individually receiving said signals representative of vertices sorted with respect to said plane.

7. A system according to claim 6 and further including selection means to specify a series of said representations definitive of planes to define progressively smaller volumes for said positional vertices.

8. A system according to claim 7 further including means for detecting coincidence of a boundary of one of said volumes and one of said polygons for controlling said selection means.

9. A system according to claim 8 wherein said first register means includes means to register signals indicating that one of said polygons is definitive of a silhouette of an object.