Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-08-06
2003-08-05
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S420000
Reexamination Certificate
active
06603484
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to sculpting graphical objects, and in particular to sculpting graphical objects represented as distance fields.
BACKGROUND OF THE INVENTION
Surface Representations
A representation of “shape” of an object or model is required in many fields such as computer-aided design and manufacturing, computational physics, physical modeling, and computer graphics. Three common representations for shape are parametric surface models, implicit surfaces, and sampled volume data.
Parametric Surface Models
Parametric surface models define the surfaces of an object as a collection of primitives such as polygons, spline patches, or subdivision surfaces that are defined parametrically. Most graphics systems use a parametric representation. As stated by Alyn Rockwood in “The displacement method for implicit blending surfaces in solid models,” ACM Transactions on Graphics, Vol. 8, No. 4, 1989, “parametric surfaces are usually easier to draw, tessellate, subdivide, and bound, or to perform any operation on that requires a knowledge of ‘where’ on the surface.” However, parametric surface models are difficult to combine, sculpt, or deform. Moreover, parametric surface models cannot be used for solid objects because they do not represents the interior of objects.
Implicit Surfaces
Implicit surfaces are represented by an implicit function, f(x). The function is defined over the space including the surface. The surface of the object is expressed as an iso-surface of an implicit function: i.e.,f(x)=c. Implicit surfaces can represent object interiors, can easily blend together, can morph between object shapes, and can perform constructive solid geometry (CSG) operations on objects. Implicit surfaces can also detect inside versus outside of objects. However, as stated by Bloomenthal in
Introduction to Implicit Surfaces
, Morgan Kaufman Publishers, 1997, while the “natural conversion from the parametric (2D) space of a surface to the geometric (3D) space of an object is a fundamental convenience, and partially accounts for the popularity of parametric surfaces . . . there is no comparable mechanism for implicit surfaces.” In other words, given the equation defining an implicit surface it is hard to locate points on the surface in object space. In addition, it can be difficult to find implicit functions for some arbitrary objects.
Sampled Volume Data
Sampled volume data represent objects and models in an array of sampled intensity values on a regular or irregular grid. Volume data are usually generated from 3D image data or from numerical simulation. Like implicit surfaces, sampled volume data represent object interiors, and the sampled volume data can be used in many of the same ways that implicit surfaces are used. However, the accuracy of the object representation is limited by the resolution of the sampling. Sampled data are usually intensity-based so that an object is distinguished from the background and from other objects by the sampled intensity values. In general, this means that the sampled intensities change abruptly at object surfaces to introduce high spatial frequencies into the data. High sampling rates are required to avoid aliasing artifacts and jagged edges in rendered images. Because high sampling rates increase memory requirements and rendering times, the quality of the represented surface must be traded-off with memory requirements and rendering speed.
Distance Fields and Distance Maps
A scalar field is a single-valued N-dimensional function that is defined over a given region. A distance field is a scalar field that represents the “distance” to a surface, &dgr;S, of an object, S. A “distance” is defined for each p contained in the domain of the field by D(p, S)=minabs{∥p−q∥}, for all points q on the surface &dgr;S, where minabs{A} determines the signed element of a set A with the minimum absolute magnitude, and ∥~∥ represents a distance metric with the following characteristics: the distance metric has a value of zero everywhere on &dgr;S and the metric is signed to permit the distinction between the inside and the outside of S. A surface at a non-zero iso-surface of the distance field can be easily specified by adding a scalar offset to the distance field.
A sampled distance field is a set of values sampled from the distance field along with either an implicit or explicit representation of the sampling location. The sampled values can include distance values and associated distance computations such as the gradient of the distance field and/or other partial derivatives of the distance field.
One example of a distance metric is the Euclidean distance in which the distance field at any point p becomes the signed Euclidean distance from p to the closest point on the object surface. A distance map is defined to be the sampled Euclidean distance field where the sample locations lie on a regular grid. Distance maps have been used in several applications.
For example, Lengyel et al. used distance maps for robotic path planning in “Real-time robot motion planning using rasterizing computer graphics hardware,” SIGGRAPH, pp. 327-335, 1990. Others have used distance maps for morphing between two objects. See “Distance field manipulation of surface models,” Payne et al. in IEEE Computer Graphics and Applications, January, 1992 for an example. Distance maps have also been used for generating offset surfaces as discussed by Breen et al. in “3D scan conversion of CSG models into distance volumes,” Proceedings of the IEEE Volume Visualization Symposium, 1998. Gibson used distance maps to represent precision surfaces for volume rendering in “Using distance maps for smooth surface representation in sampled volumes,” Proceedings of the IEEE Volume Visualization Symposium, 1998. Four methods for generating distance maps from binary sampled volume data are compared by Gibson in “Calculating distance maps from binary segmented data,” MERL Technical Report TR99-26, April, 1999.
Because the Euclidean distance field varies slowly across surfaces, distance maps do not suffer from the aliasing problems of sampled intensity volumes. Smooth surfaces can accurately be reconstructed from relatively coarse distance maps as long as the surface has low curvature. However, because distance maps are regularly sampled, they suffer from some of the same problems as sampled volumes. For example, the size of the distance map is determined by a combination of the volume of the object and the finest detail that must be represented. Hence, volumes that have some fine detail surfaces require large distance maps, even when only a small fraction of the volume is occupied by the fine-detail surfaces. In addition, distance maps are typically rendered by using volume rendering techniques. Volume rendering techniques can be very slow, and may require many seconds or minutes per frame for high quality rendering of reasonably sized volumes.
Spatial Data Structures for Hierarchical Object Representation
A number of methods are known for hierarchically organizing spatial data for efficient memory usage, rendering, or physics modeling. Examples of spatial data structures are presented in two books by Samet, “The Design and Analysis of Spatial Data Structures,” and “Applications of Spatial Data Structures,” both published by Addison-Wesley in 1989.
Octrees recursively decompose three-dimensional space into eight equal-sized octants or nodes in order to organize data hierarchically. Region octrees divide data into nodes corresponding to uniform regions of the volume image. When the image data is binary, the resultant tree has two types of nodes, interior nodes and exterior nodes. Three-color octrees classify nodes as being interior, exterior or boundary nodes, where boundary nodes intersect object surfaces. Boundary nodes are subdivided recursively to the highest resolution of the volume data. Object surfaces are rendered by drawing the boundary leaf nodes.
Three-color octrees have been applied to volume data to reduce the amount
Frisken Sarah F.
Jones Thouis R.
Perry Ronald N.
Bella Matthew C.
Blackman Anthony
Brinkman Dirk
Curtin Andrew
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Sculpting objects using detail-directed hierarchical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sculpting objects using detail-directed hierarchical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sculpting objects using detail-directed hierarchical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3119186