Triangle strip length maximization

Details Triangle strip length maximization Triangle strip length maximization

1999-05-06

2002-08-06

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S423000

Reexamination Certificate

active

06429865

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to three-dimensional (3D) models represented as triangle meshes, and more particularly to representing a triangle mesh as a series of triangle strips.
BACKGROUND OF THE INVENTION
As computers become increasingly more powerful, they have been increasingly used to run computer programs that utilize three-dimensional (3D) models, or objects. Such programs include game programs where a game player views his or her surroundings in three dimensions, computer-aided-drafting (CAD) programs allowing architects, engineers and designers to construct plans for real-world objects in three dimensions, as well as other programs. The three-dimensional objects used by these and other computer programs have generally become increasingly complex.
One manner by which three-dimensional models are represented within a computer is known as a triangle mesh. A triangle mesh includes a number of differently sized triangles, such that at least one edge of each triangle within the mesh is shared with another triangle, and each vertex of each triangle within the mesh is shared with at least one other triangle. Complex three-dimensional objects can be constructed utilizing triangle meshes. For example, small numbers of triangles can be used for flat surfaces of an object, while large numbers can be used to mold curved surfaces of the object, similar to the way a geodesic dome is constructed.
As triangle meshes have gained popularity to represent three-dimensional models within computers, and as these triangle meshes have become more complex to represent increasingly complex three-dimensional models, the issue of representing a triangle mesh in a sequential manner has become important. A triangle mesh is generally a non-sequential representation: it usually does not have a set beginning nor a set end. Representing the triangle mesh sequentially, however, is important to save the triangle mesh to a sequential file for storage on a storage device such as a hard disk drive, for instance, or for sending to another computer over a network such as the Internet, for example. Furthermore, it is also important in sending triangles to a graphics card via a graphics application programming interface (API).
One manner by which triangle meshes are represented in a sequential manner is through the use of triangle strips. A triangle strip defines a connected group of triangles in a sequential fashion, having a set beginning and a set end. In one representation of a triangle strip, the strip is represented as a series of vertices. A new triangle is typically defined for each vertex presented after the first two vertices. In this particular representation, N=2 triangles are defined, where N is the number of vertices in the representation.
Once triangle strips are selected as a desired manner by which to represent triangle meshes in a sequential manner, an important issue becomes the manner in which a triangle mesh is converted to a series of one or more triangle strips. The series of triangle strips must as a whole represent all of the plurality of triangles within the mesh. For a compact representation, desirably no triangles within the mesh are repeated within the triangle strips—that is, each single triangle within the mesh is represented only once within the triangle strips. Furthermore, longer triangle strips are generally better, because they usually lend themselves to easier storage and transmission as a file. For these and other reasons, there is a need for the present invention.
SUMMARY OF THE INVENTION
Embodiments of the present invention relate to triangle strip length maximization. In one embodiment, a computer-implemented method first includes determining an area of each of a plurality of triangles of a triangle mesh. A list of the plurality of triangles is generated. A distance from the smallest area triangle to every other triangle on the list is determined. An available triangle on the list closest to the smallest area triangle is added to a triangle strip that begins with the smallest area triangle. The process of creating triangle strips continues until all of the triangles are represented in the strips.


REFERENCES:
patent: 5448687 (1995-09-01), Hoogerhyde et al.
patent: 5862252 (1999-01-01), Yamamoto et al.
patent: 5945996 (1999-08-01), Migdal et al.
patent: 6137492 (2000-10-01), Hoppe
patent: 6208347 (2001-03-01), Migdal et al.
Arkin, E.M., et al., “Hamiltonian Triangulations for Fast Rendering”, Second Annual European Symposium on Algorithms, 855, Springer-Verlag Lecture Notes in Computer Science, pp. 1-17, (1994).
Evans, F., et al., “Efficiently Generating Triangle Strips for Fast Rendering”, SIGGRAPH Presentation, pp. 1-25, (Dec. 1996).
Evans, F., et al., “Optimizing Triangle Strips for Fast Rendering”, IEEE Visualization Presentation Seminar, San Francisco, CA, 8 p., (Oct. 27-Nov. 1, 19).

Affiliated with

Also associated with

Rating

Triangle strip length maximization does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2912478