Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-05-22
2004-12-07
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06828965
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the art of representing shapes of objects and models, and more particularly to computer implemented methods for operating on the represented shapes.
BACKGROUND OF THE INVENTION
Rivaling polygons, distance fields are well known as fundamental primitive for representing objects and models in computer graphics, see for example, U.S. Pat. No. 6,040,835 issued to Gibson on Mar. 21, 2000, and U.S. Pat. No. 6,084,593 issued to Gibson on Jul. 4, 2000.
In the prior art, a distance field is usually described with the notion that every point in space is associated with a “minimum” distance to a surface on the object or model. This notion derives both from natural experience and the classic definition in mathematics in which a distance from a point y in a metric space to a set A is given by the infimum
D
(
y,A
)=
inf
x&egr;A
D
(
x,y
),
where D(x,y) is a standard metric such as the Manhattan distance, i.e. the sum of absolute differences of components, the Euclidean distance, i.e., the square root of the sum of the squares of the components, or the infinity norm, i.e. the maximum of the absolute differences of the components; known respectively as the l
1
, l
2
and l
∞
norms.
Whatever the metric, a traditional distance field requires searching for a point on a surface of the object or model that is closest to a point in space, i.e., a point in the distance field. For example, the distance field can be determined by an intensive method that finds a nearest point on the surface to any given point in space by casting sample rays from the point in space, and then using Newton's approximation method to converge on the point on the surface. This search can be time-consuming and complicated. Furthermore, the search can be subject to many optimization pitfalls.
Unfortunately, the traditional notion of the minimum distance also excludes many useful shapes. Implicitly defined shapes, for example, do not reference a minimum distance, nor do they necessarily designate a closest point on a surface of the object to allow one to completely define the distance field.
For example, with an implicit function f(x)=20x
2
+y
2
+z
2
−1, any point x in three-dimensional space f(x) represents a very usable distance to the flattened ellipsoid defined by f(x)=0, an algebraic, i.e., non-Euclidean, distance that has no minimum or closest point in the calculation. Level sets, interpolation schemes, measured equipotential fields and procedural methods are other examples for which distance fields either fail to represent, or impose unnecessary computational burdens on the representation. In addition, repeated operations on distance field can degrade quality of the field, making further operations inaccurate, unpredictable, or worse, impossible to perform.
For example,
FIG. 1
a
shows contracting streamlines
101
of a cubic implicial test function on a test surface
102
, and
FIG. 1
b
expansion and twist of streamlines
103
on the test surface
104
. There are eight streamlines emanating from the four corners and four midpoints of the depicted square
105
. In
FIG. 1
a
, the streamlines
101
contract as they flow to the surface in a region of concavity. In
FIG. 1
b
, the streamlines
102
expand to meet a region of convexity
102
. The streamlines in
FIG. 1
a
also exhibit some twist to the flux, especially where the horizontal beginning points on the square project
105
, with a turn, onto the convex surface. It would be desirable to minimize the contraction, expansion and rotation of the streamlines.
FIG. 2
a
shows a more tortuous path of streamlines
201
when the object or model has a small amount of texture.
FIG. 2
b
shows a complete failure in the streamlines due to a lager amount of texture. This is due to the fact that the distance field has a large number of local minima that trap the streamlines.
It is desired to regularize a field surrounding shapes of objects and models so that repeated operation such Booleans, blending and texturing can be applied without deleterious effects on the field.
SUMMARY OF THE INVENTION
The invention provides a method for regularizing a distance field of a graphics model or object. The distance field includes variable scalar values and a set of fixed zero values. The zero values define a boundary or surface of the object.
The distance field is evaluated by a cost function, optimized according predetermined parameters, to determine a cost of the distance field. The variable scalar values are then randomly perturbed while holding the zero values fixed. The evaluating, determining, perturbing steps are repeated until the cost is less than a predetermined threshold.
The distance field can be in the form of a non-differentiable implicial field. A surface of the graphics model can be textured or stenciled by following streamlines along the gradients of the regularized distance field.
REFERENCES:
patent: 4912624 (1990-03-01), Harth et al.
patent: 6483518 (2002-11-01), Perry et al.
Distance Field Manipulation of Surface Models, Payne et al., Jan. 1992, IEEE, pp. 65-71.
Brinkman Dirk
Curtin Andrew J.
Mitsubishi Electric Research Labs Inc.
Wallace Scott A
Zimmerman Mark
LandOfFree
Regularization of implicial fields representing objects and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Regularization of implicial fields representing objects and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Regularization of implicial fields representing objects and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304896