Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-07-19
2004-03-16
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S421000, C345S581000, C345S606000
Reexamination Certificate
active
06707452
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computer graphics, and, more specifically, to graphical rendering of surfaces.
2. Background Art
In computer graphics, images are often created from three-dimensional objects modeled within a computer. The process of transforming the three-dimensional object data within the computer into viewable images is referred to as rendering. Typically, objects are modeled as one or more surfaces. Ideally, these surfaces comprise continuous curves for best visual realism. However, in practice, these surfaces are approximated with a mesh of less complex surface components, such as parametric surfaces or patches, to reduce the computational complexity of the rendering process. These patches are further subdivided or “diced” into triangles or polygons for rendering purposes. For example, bicubic patches are often rendered by subdividing their parameter space into rectangular grid of quadrilaterals, which are then further subdivided into triangles for rendering. A higher dicing rate provides greater modeling resolution and a better surface approximation. The dicing rate of a given patch may depend on factors such as the distance of the patch from the viewing plane and the local feature complexity of the patch.
An undesirable phenomenon known as “cracking” occurs when surfaces are split into multiple patches that are rendered independently. The shared boundaries between patches are tessellated and displaced by each side independently, which often creates narrow gaps or “cracks” between the two sides. Adjacent patches can compute different positions for their shared boundary curve for several reasons:
Two adjacent patches may dice at different rates, generating different numbers of vertices along a shared edge.
The adjacent patches may compute different positions for a vertex at the same parametric location, due to numerical errors. For example, this can occur if one patch has split into two pieces along the adjacent edge while the other patch has not.
Vertices along a shared edge may have different positions in the two patches due to displacement mapping (a technique whereby the diced vertex positions are modified according to a given formula, such as a texture map lookup, in order to add geometric detail to a smooth underlying surface). For example, this can happen when finite difference techniques are used in the displacement calculations (to estimate surface normals, derivatives, or texture filtering information). This is because finite difference techniques cause the position of a vertex to depend on the position of its neighbors, which are different in the two patch tessellations.
An example of crack formation is illustrated in
FIGS. 1A and 1B
.
FIG. 1A
depicts an idealized surface comprising regions
100
and
101
, having a continuous seam
102
between the regions.
FIG. 1B
depicts an approximation of the surface of
FIG. 1A
, wherein region
100
is now
100
A comprising several parametric surfaces with piecewise linear edge
102
A corresponding to seam
102
. Similarly, region
101
A comprises several parametric surfaces having piecewise linear edge
102
B corresponding to seam
102
. Edge
102
A models seam
102
with a higher dicing rate than edge
102
B. As shown, edge
102
A contains four vertices within the same span in which edge
102
B has three vertices. The mismatch in dicing rates as well as the displacement differences between vertices in edges
102
A and
102
B form a crack
103
between regions
100
A and
101
A. Crack
103
represents a rendering error that may be visually apparent in the final rendered image, particularly where there is high contrast between the color value associated with regions
100
B and
101
B and the color value associated with the background visible through the crack.
Previous techniques for eliminating cracks fall into several categories. First there are methods that render parametric surfaces as a restricted quad-tree. That is, tessellation is limited to a pattern of quadrilaterals wherein the variation in dicing rates between patches is strictly constrained. These techniques store the entire tessellated surface in memory and do not support surfaces of arbitrary topology.
A second set of techniques are based on the idea that the tessellation of a boundary should be based only on the boundary curve itself. However, these methods do not eliminate all sources of cracking. In particular, if the patches on one side of a shared boundary have split more often than those on the other, then there is no single dicing rate for the unsplit patch that can match the multiple rates on the other side. Furthermore these techniques cannot handle the problems caused by displacement mapping, in which case the two sides can have different vertex positions even if the dicing rates match.
In another variation, the boundary curves are tessellated before patches are split. This technique has several drawbacks. It generates highly irregular tessellations that cannot be evaluated efficiently; it requires a substantial amount of time and memory to split patches that may eventually be occluded (and discarded) anyway; and, furthermore, this technique cannot render patches whose boundaries are simple (e.g. flat) but have complex features in their interiors.
Finally, some prior art techniques are based on the idea of splitting all patches and determining dicing rates in a preprocessing phase. For each portion of a shared boundary edge, one of the two adjacent patches is arbitrarily chosen to be associated with that edge. The main drawback to this approach is that the entire surface must be tessellated (or at least all dicing rates must be determined) in advance, which has significant time and memory expenses.
SUMMARY OF THE INVENTION
A method and apparatus for surface approximation without cracks are described. Embodiments of the invention may be applied to surfaces of arbitrary topology. In one or more embodiments, a surface to be rendered is split into multiple adjacent regions (e.g., subdivision surfaces or patches). A data structure is associated with each boundary edge between two regions for storage of adjacency information in the form of a sequence of tessellation vertices. Adjacency information for a given edge is written into the data structure when an adjacent region is first tessellated. When the remaining adjacent region is tessellated, the adjacency information is read from the data structure and used to achieve tessellation without cracks. In one embodiment, visible cracks due to T-vertices are prevented by forming an overlap of adjacent regions at the location of each T-vertex. This technique allows regions to be tessellated and rendered without any advance knowledge of how the adjacent regions will be split. The regions may be tessellated and rendered separately and in any order, reducing time and memory requirements for rendering.
In one embodiment, the data structure is implemented as a binary tree having a root node created when a new edge is created through a splitting operation. Splitting of an existing edge results in the creation of two child nodes corresponding to the new edge segments. Nodes may be freed from memory when no longer referenced by either of the associated adjacent regions.
REFERENCES:
patent: 5278949 (1994-01-01), Thayer
patent: 5377320 (1994-12-01), Abi-Ezzi et al.
patent: 6313837 (2001-11-01), Assa et al.
patent: 6373489 (2002-04-01), Lu et al.
Nguyen Kimbinh T.
Pixar
Zimmerman Mark
LandOfFree
Method and apparatus for surface approximation without cracks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for surface approximation without cracks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for surface approximation without cracks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3238220