Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-05-06
2003-04-22
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06552724
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 another 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.
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 added to the strip 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. In addition, the generation of longer triangle strips generally means that less strips are necessary to represent a particular triangle mesh. 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 merging for length maximization of a plurality of triangle strips representing a triangle mesh. In one embodiment, a computer-implemented method, for each triangle strip, first includes determining whether a defining face of the strip has a neighboring face that is a defining face of another strip. A defining face of a particular strip is either a front face, an end face, or an orphan face of the particular strip. Upon determining that a defining face of the strip has a neighboring face that is a defining face of another strip, it is determined whether the strip and the another strip are joinable. If they are joinable, then the two strips are joined to create a new, larger strip in place of the strip and the another strip.
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: 5982385 (1999-11-01), Fish et al.
patent: 6137492 (2000-10-01), Hoppe
patent: 6208347 (2001-03-01), Migdal et al.
Cao Hue Dung X
Zimmerman Mark
LandOfFree
Triangle strip merging for 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 merging for length maximization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Triangle strip merging for length maximization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078199