Processing polygon strips

Details Processing polygon strips Processing polygon strips

1999-02-24

2001-11-20

Jankus, Almis R. (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

Reexamination Certificate

active

06320596

ABSTRACT:

BACKGROUND
The invention relates to processing polygon strips, such as triangle strips, for example.
There are many ways for a computer system to represent three-dimensional (3-D) objects. For example, the computer system may use polygon meshes to represent the surfaces of the 3-D objects. One type of polygon mesh may include at least one triangle strip
8
(see
FIG. 1
) that is a collection of connected triangles
12
that are organized in a manner to minimize the number of vertices
9
that are used to describe the triangles
12
. More particularly, a triangle may be described by three vertices, and thus, n triangles may be described by n*3 vertices. However, for the triangle strip
8
, each triangle
12
shares a common edge with another triangle
12
, an arrangement that permits n triangles to be described by n+2 vertices. In this manner, the triangle strip
8
(having sixteen triangles
12
) may be described by the following vertex list (having 18 vertices):
{
9
a
,
9
b
,
9
c
,
9
d
,
9
e
,
9
f
,
9
g
,
9
h
,
9
i
,
9
j
,
9
k
,
9
l
,
9
m
,
9
n
,
9
o
,
9
p
9
q
,
9
r
}
The triangle strip
8
may have a winding order (i.e., the triangle strip
8
may be “ordered”), a designation that implies that the vertices of each triangle
12
appear in a sequence (in the vertex list) that indicates the direction of the surface normal of the triangle
12
. In this manner, the triangle strip
8
typically is not planar (as depicted in
FIG. 1
for purposes of simplicity), but rather, the triangle strip
8
may follow a non-planar path in 3-D space. As an example, a surface of a particular triangle
12
may form part of an object's exterior surface and as a result, may have a surface normal that points in a direction away from the exterior surface. Thus, the order in which the vertices associated with a particular triangle
12
appear in the vertex list may govern which surface of the triangle
12
forms part of the object's exterior surface.
More particularly, when the computer system processes the above-described vertex list to render an image of the triangle strip
8
, the computer system may initially draw a triangle
12
a
that has the vertices
9
a
,
9
b
and
9
c
and is bounded by a conceptual piecewise parametric curve
5
that extends through the vertices
9
a
,
9
b
, and
9
c
. The direction (clockwise or counterclockwise) of a parametric curve (such as the parametric curve
5
) may be determined by the order in which the vertices are connected to form the curve, and the direction of the curve may govern which surface of the triangle is an exterior surface, as described below.
The winding order of the triangle strip
8
effectively alternates the applications of the right hand and left hand rules to the parametric curves (that bound the triangles
12
) to determine the directions of the surface normals. For example, to form the leftmost triangle
12
a
of the strip
8
, the computer system may connect the first three vertices {
9
a
,
9
b
,
9
c
} together in the order (a left-to-right order, for example) that is defined by the sequence in which the vertices appear in the vertex list described above: vertex
9
a
to vertex
9
b
to vertex
9
c
to vertex
9
a
(to close the curve). Thus, the resultant parametric curve
5
has a counterclockwise orientation (as depicted in FIG.
1
). Applying the right hand rule, the surface normal of the triangle
12
a
points out of the page, for example. It is noted that if the leftmost triangle is alternatively defined by the vertex sublist {
9
a
,
9
c
,
9
b
}, then the resultant parametric curve (given the drawing order described above) has a clockwise (instead of a counterclockwise) orientation, and thus, applying the right hand rule, the surface normal of the triangle points into the page.
As another example, the next triangle
12
b
to the right of the triangle
12
a
is defined by one additional vertice
9
d
that, when combined with the vertex sublist {
9
b
,
9
c
} (i.e., the two prior vertices of the vertex list), causes the computer system to form a conceptual parametric curve
6
in the following manner: vertex
9
b
to vertex
9
c
to vertex.
9
d
to vertex
9
b
. Thus, the parametric curve
6
has a clockwise orientation, and the winding order ensures that the left hand rule applies (because of the alternating applications of the left hand and right hand rules) to determine the direction of the surface normal. Thus, applying the left hand rule to the parametric curve
6
, the surface normal of the triangle
12
b
points out of the page.
Three dimensional objects may be defined in an object space by a mesh of multiple triangle strips that are oriented in various directions, and the computer system may process the vertex lists that define the triangle strips to transform the vertices into a two-dimensional (2-D) screen space for display. As an example, the computer system may represent a portion of an exterior surface of a sphere
9
(in an object space) by a triangle strip
8
a
, as depicted in FIG.
2
. When transformed into screen coordinates as seen through a viewing window
7
, a portion
8
aa
of the strip
8
a
may be visible, and another portion
8
ab
of the strip
8
a
may be invisible. Unfortunately, the computer system may consume a considerable amount of time processing triangles, such as the triangles that form the portion
8
ab
, that do not ultimately appear in the 2-D screen space. These additional computations (e.g., transformations of the vertices from one coordinate space to another coordinate space), in turn, may degrade performance of the computer system.
Thus, there is a continuing need for an arrangement that reduces the number of polygons that are processed by a computer system but do not appear in the final image that is rendered by the computer system.
SUMMARY
In one embodiment, a method for forming an image of an object on a display of a computer includes representing at least a portion of the object with a first strip of polygons that is described by a first set of points of a first coordinate space. One or moret polygons of the first strip that will be invisible in the image are selected, and these polygons are culled from the first strip to form a second strip of polygons. The second strip of polygons is described by a second set of points of the first coordinate space. The culling is performed before the points of the second set are transformed into another coordinate space that is associated with the image.


REFERENCES:
patent: 4870599 (1989-09-01), Hempel et al.
patent: 5363475 (1994-11-01), Baker et al.
patent: 5574835 (1996-11-01), Duluk, Jr. et al.
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5596686 (1997-01-01), Duluk, Jr.
patent: 5898437 (1999-04-01), Deolaliker
patent: 5903272 (1999-05-01), Otto
patent: 5999187 (1999-12-01), Dehmlow et al.
patent: 6088035 (2000-07-01), Sudarsky et al.
patent: 6115050 (2000-09-01), Laudau et al.
Patent application Ser. No. 09/252,396 Dated Feb. 18, 1999 Entitled “Processing Polygon Strips”.

Affiliated with

Also associated with

Rating

Processing polygon strips does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing polygon strips, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing polygon strips will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2592839