Modeling of surfaces employing polygon strips

• US 5,561,749 A
• Filed: 12/02/1994
• Issued: 10/01/1996
• Est. Priority Date: 12/02/1994
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Schroeder, William J.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/348,407
• Time in Patent Office: 669 Days
• Field of Search: 395/120, 395/123, 395/119, 395/124, 395/133, 395/141, 395/161
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A graphic workstation converts a polygonal model generated with computer aided design (CAD) software or volumetric data into a more compact polygon strip list having multiple strip sublists. The strip list, in addition to being more compactly stored, is displayed much more rapidly than conventional polygonal models since much of the redundant redrawing is eliminated. Shared point of adjacent polygons are eliminated. The strip list consists of a number of strip lists, each list having vertices of a first, or initial, polygon and subsequent vertices defining remaining portions of polygons to be `built onto` the polygon strip in the strip direction. Since this method of model storage and display is much more efficient, less powerful graphic workstation could be implemented in place of more powerful graphics workstations; or alternatively, existing graphics workstation would become faster and have more free memory available for other functions.

Claims

1. A method of storing a set of polygons of a polygon model having a plurality of vertices in compact triangle strip lists comprising the steps of:

a) selecting an initial polygon of said polygonal model;

b) identifying said vertices of the initial polygon;

c) adding these vertices to the strip list;

d) selecting a strip direction;

e) selecting a polygon in the strip direction which has not yet been selected, that shares at least two of the vertices the previously selected polygon;

f) storing in the strip list, vertices of the selected polygon, other than vertices already stored in the strip list;

g) repeating steps "e"-"f" until all polygons in the strip direction have been selected; and

h) repeating steps "a"-"g" for a plurality of different strip lists having different selected strip directions and initial polygons until all of polygons of a desired portion of said model has been selected.

2. A method of displaying a triangle strip list comprising the steps of:

a) reading an initial polygon, and strip direction from the strip list;

b) drawing the initial polygon;

c) reading subsequent vertices from the strip list

d) drawing the vertices read from the strip list in the strip direction thereby adding to the strip;

e) repeating steps "c"-"d" for remaining vertices in the strip list to result in a rapidly displayed surface.

3. A method of identifying a surface comprising the steps of:

a) selecting an initial polygon having a plurality of vertices on said surface;

b) storing the vertices of the initial polygon in a strip list;

c) a strip direction;

d) selecting a polygon along the strip direction having a plurality of vertices on said surface and sharing at least two vertices of the previously computed polygon;

e) storing the, vertices of the computed polygon in the strip list, except for those already stored in the strip list; and

f) repeating steps "d" length in the strip direction to result in a strip list identifying said surface; and

g) repeating steps "a"-"f" for a plurality of different strip lists having different selected strip directions and initial polygons until all of polygons of a desired portion of said surface been selected.

4. The method of identifying a surface of claim 3 further comprising, after the step "f" the step of displaying the strip list as a surface.

5. The method of identifying a surface of claim 3 further comprising, after the step "f" the steps of:

a) reading an initial polygon from the strip list;

b) drawing the initial polygon;

c) reading subsequent vertices from the strip list

d) drawing the vertices read from the strip list in the strip direction thereby adding to the strip;

e) repeating steps "c"-"d" for remaining vertices in the strip list to result in a rapidly displayed surface.

6. A graphics workstation for manipulating polygonal models comprising:

a) a polygonal model memory for storing a set of polygons from the polygonal models;

b) a polygon strip list memory for polygon strip lists;

c) a strip generator for converting a set of polygons in said polygonal model memory into a plurality of variable length polygon strip lists each pertaining to a different selected direction and for storing the strip lists in the polygon strip list memory;

d) a strip display circuit for reading the polygon strip lists and forming an image from the polygon strip list.