Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-12-14
2003-02-04
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000, C345S428000
Reexamination Certificate
active
06515660
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer graphics. In particular, the present Invention relates to dynamically triangle stripping a multi-resolution mesh (“MRM”) representation of a three-dimensional (“3-D”) triangulated model.
BACKGROUND
Prior art approaches to increase the speed of rendering and displaying three dimensional objects have started with the properties of the polygons used to render an object. A common polygon used in rendering three dimensional objects is a triangle. A triangle has many helpful properties that make it ideal for use in rendering three dimensional surfaces. For example, a triangle is completely defined by three vertices and each triangle also uniquely defines a plane. Thus, many systems will use a plurality of triangles to render a three dimensional surface. If each triangle is passed separately to the graphic subsystem that renders the three dimensional object, then three vertices for each triangle must be passed and processed by the graphic subsystem. However, the number of vertices that must be passed and processed by the graphic subsystem can be reduced through “vertex sharing.” Vertex sharing relies on a property of shared sides among triangles. Although it takes three vertices to define one triangle, it only takes four vertices to define two triangles if they share a common side. In order to take advantage of vertex sharing to reduce the number of vertices needed to render an object, pipelined systems have been developed that divide a three dimensional object into triangle strips that can then be processed and displayed efficiently In order to present a three-dimensional (“3-D”) object on a display screen, typical computer graphics systems decompose the object into a plurality of graphics primitives. These primitives are the basic components of a graphics picture and may include points, lines, polylines, vectors and polygons, such as triangles or quadrilaterals. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent the view of one or more objects being represented on the screen.
In general, the primitives that define a 3-D graphic object are provided from a host computer, which defines each primitive in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitive in terms of the x, y, z coordinates of its vertices, as well as the R, G, B color values of each vertex. Rendering hardware interpolates the primitive data to compute the display screen pixels that are turned on to represent each primitive, and the R, G, B values for each pixel.
A triangle strip (tri-strip) is a basic primitive that very efficiently represents the triangles (faces) of a mesh. A “mesh,” as used in the present invention, is a representation of the surface area of an object by subdividing the surface area into triangle or quadrilateral shapes. For example, if there are ten triangles in a row, it would take thirty vertices (3 vertices per triangle*ten triangles) to represent these triangles as discrete elements within the 3-D object.
Triangle strips have been typically pre-computed for each mesh because current triangle stripping processes are too slow to be computed each time the mesh is rendered. As a result, this pre-computing technique does not work with Multi-Resolution Meshes (“MRMs”) because the triangle strips have to be computed and stored for every possible resolution of the MRM, thus using far too much memory.
In a triangle mesh a “neighboring triangle” is any triangle that shares an edge with an adjacent triangle. Similarly, a “far corner” of a triangle is the corner in the neighboring triangle that is not on the edge that joins a triangle to its neighboring triangles. A “far vertex” is the vertex that defines the far corner.
Previous triangle mesh data structures were variable in size or limited to manifold meshes. In a “manifold” mesh each shared edge can only be shared between two triangles. These previous triangle mesh data structures also comprised triangle records that included individual pointers to the neighboring triangles and location information for each of the three corners/vertices of the triangle. As a consequence of these structures, all of the vertices in the triangle must be searched to find the far vertex, the size of the data structures is variable and usually larger which results in slower performance, and variable-sized sets of pointers were used to store the pointers to multiple neighbors in non-manifold meshes that shared an edge. In a “non-manifold mesh” at least one edge is shared by more than two triangles. While variable-sized sets of pointers are relatively easy to implement in software, they do not easily lend themselves to being implemented in hardware.
FIG. 7
illustrates an exemplary prior art triangle mesh data structure. In
FIG. 7
, an exemplary three triangle mesh
700
which is made up of triangles T
1
, T
2
and T
3
701
,
702
and
703
, respectively, is shown with the comers of each triangle labeled as C
0
, C
1
and C
2
. A triangle mesh data structure
705
illustrates the interrelationships between triangle records
710
,
720
and
730
which represent triangles T
1
701
, T
2
702
and T
3
703
, respectively, of triangle mesh
700
. Triangle record T
1
710
is comprised of a triangle number field
711
, a corner
0
field
712
, a corner
1
field
713
, a corner
2
field
714
, a record header
715
, a first neighboring triangle pointer
716
, a second neighboring triangle pointer
717
and a third neighboring triangle pointer
718
. Each of the pointers
716
,
717
and
718
are used to point to the header record of a different neighboring triangle. For example, in
FIG. 7
, since triangle T
1
701
and triangle T
2
702
are neighbors, first neighboring triangle pointer
716
of triangle record T
1
710
points to the record header
725
for triangle record T
2
720
. Similarly, first neighboring triangle pointer
726
of triangle record T
2
720
points to the record header
715
for triangle record T
1
710
. Continuing, second neighboring triangle pointer
727
of triangle record T
2
720
points to the record header
735
for triangle record T
3
730
and first neighboring triangle pointer
736
of triangle record T
3
730
points to the record header
725
for triangle record T
2
720
, since triangle T
2
702
and triangle T
3
703
are neighbors. The second and third neighboring triangle pointers
717
and
718
, respectively, in triangle record T
1
710
are null pointers since only one side of triangle T
1
701
has a neighbor triangle, triangle B
702
.
Selective refinement of an arbitrary progressive mesh according to changing view parameters is introduced by Hughes Hoppe in “View-Dependent Refinement of Progressive Meshes,” SIGGRAPH 97.
A general representation of a pipeline system processing a triangle strip is described in U.S. Pat. No. 5,818,136 to Keondjian. This discussion highlights two hallmarks of prior art pipelined systems. First, the pipelined process always works on one vertex at a time, and for each vertex processed, after the first two vertices, a new triangle is drawn. Second, to maintain maximum performance, the pipeline must be provided with a steady stream of vertices and any breaks in the steady flow of vertices reduces system performance.
Therefore, it can be appreciated that a substantial need exists to provide an improved method and system for dynamic triangle stripping a MRM at run-time at rates at least as fast as standard computer display rates of 60 Hz.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide a method for creating a neighbor mesh from a multi-resolution mesh. The method includes computing neighbor data for the neighbor mesh at a highest resolution of the multi-resolution mesh. The method further includes changing the resolution of the multi-resolution mesh and re-computing the neighbor data for the neighbor mesh at the changed resolution of the multi-resolution mesh, and comp
MacPherson Michael S.
Marshall Carl S.
Intel Corporation
Kenyon & Kenyon
Wiley Sam A.
Zimmerman Mark
LandOfFree
Apparatus and method for dynamic triangle stripping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for dynamic triangle stripping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for dynamic triangle stripping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121302