Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-04
2001-07-17
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06262738
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to computer graphics, and more particularly to estimating 3D distance maps from 2D depth images.
BACKGROUND OF THE INVENTION
Distance maps are typically 2D or 3D discrete arrays of sampled values. The sampled values represent distances to the closest points on the surface of an object that is modeled in a computer. One can apply discrete interpolation methods, such as tri-linear interpolation, on distance maps to estimate the distance from any non-grid point within the sampled volume to the surface of the object.
The zero-value iso-surface of a signed distance map represents the surface of the object. In addition, the gradient vector of the distance map points in the direction of the closest surface point, and hence, for points near object surfaces, the gradient of the distance map is a good approximation of the surface normal of the object.
Many applications in the fields of computer graphics and robotics can make use of distance maps in visualization, planning or modeling. For example, in “Towards the Automatic Control of Robot Assembly Tasks Via Potential Functions: The Case of 2-D Sphere Assemblies” by Koditschek et al., mobile robots use distance maps of the local environment to determine an obstacle-free path. Sramek uses distance maps in “Fast Surface Rendering from Raster Data by Voxel Traversal Using Chessboard Distance” Proceedings IEEE Visualization, 1994, to increase the speed of volume rendering by allowing the renderer to quickly skip empty regions in the volume.
Yagel et al. use distance maps in “Volume-based Re-zoning and Visualization of Diecasting,” in Proceedings IEEE Visualization, 1994, for locating problematic regions in computer models of mechanical structures where part thickness may be too large for the manufacturing process. Gibson uses distance maps to accurately reconstruct surface normals for use in shaded volume rendering, as described in “Using Distance Maps for Accurate Surface Representation in Sampled Volumes” Proceedings IEEE Visualization, 1998. In addition, “Linked Volumetric Objects for Physical-based Modeling,” MERL Technical Report TR97-20 by Gibson, discusses the use of both distance values and the gradient of the distance map for calculating impact force vectors between colliding graphical objects as the calculation of interaction forces between a haptic force feedback device and a virtual object model.
Object scanning is the process of acquiring a computer model of a real-world object from image or range data. Scanning is done with many techniques. Most methods generate a “cloud,” or grid, of 3D points that lie on the object's surface. A model of the object is constructed by fitting surfaces to these points. However, as was discussed in Gibson's “Using Distance Maps for Accurate Surface Representation in Sampled Volumes,” distance maps provide a much more robust representation of object surfaces than sampled object points. Hence, if the range images were used to generate 3D distance maps, rather than clouds of surface points, then better scanned models can be obtained.
In the prior art, a number of methods for generating distance maps from object models are known. When the object model is an analytic function, the distance map can be generated procedurally. For example, for a spherical object centered at (x
0
, y
0
, z
0
) with radius R, the signed distance map value can be calculated at a grid point (i, j, k) as:
d=R−sqrt
((
i−x
0
)
2
+(
j−y
0
)
2
+(
k−z
0
)
2
).
In this example, the signed distance is positive inside the object and negative outside the object. Unfortunately, only a limited number of objects have simple procedural definitions for the distance map.
When the object is represented by a binary volume, where elements in the volume are either on or off, there are a number of methods that can be used for estimating the distance map. Some of these methods are described for the 2D case in “The Image Processing Handbook”, by J. Russ. Extensions to 3D are discussed, for example, in “Local Distances for Distance Transformations in Two and Three Dimensions,” a Ph.D. thesis from Delft University by B. Verwer, 1991.
However, as discussed in “Calculating Distance Maps from Binary Segmented Data,” by Gibson in MERL Technical Report WP98-01, these methods only approximate the distance to the true surface of the binary object and the resultant distance map does not generate smooth surface normals. In “Constrained Elastic Surface Nets: Generating Smooth Surfaces from Binary Segmented Data,” Proceedings Medical Image Computation and Computer Assisted Interventions, 1998, Gibson presented a method for creating smooth polygonal surfaces from binary data and generating the corresponding distance maps from this polygonal model.
When the object is represented by a polygonal model, the distance map is determined by finding the closest polygon, edge, or vertex in the model, and calculating the distance to that feature. One straightforward method for doing this is to consider each grid point in the distance map individually, find the closest polygon in the model by searching the list of polygons, and then calculating the distance from the grid point to that closest polygon. A second straightforward method is to consider each polygon in the object model one at a time, calculate the distance from the polygon to each grid point within a limited distance from the polygon, and replace each grid value in the distance map if the new distance has a smaller magnitude than the existing value.
Both of these methods for calculating distance maps from a polygonal model are adequate, when the distance map is calculated for a static object in a pre-processing step. However, both of these methods are unsuitable for time constrained interactive applications in which the shape or topology of the polygon model is changing.
For example, in complex models with as many 100,000 or more triangles, it may take minutes to calculate the distance map using either of these two methods. When the object model is deforming, or its shape is interactively changing, interactive systems require new distance maps within seconds for path planning, within 10's of milliseconds for rendering and most physics-based modeling systems, and within milliseconds for haptics. Even with algorithms for adaptive updating of distance maps, these two techniques for generating distance maps are computationally intensive, and require a significant portion of available processing power.
Therefore, there is a need for a method that can rapidly estimate distance maps from depth images.
SUMMARY OF THE INVENTION
The present invention approximates 3D distance maps from range images of real-world objects or from triangulated object models using single or multiple projected 2D depth images. The invention can be used in systems where 2D depth images of real-world objects are obtained with range sensing devices, or in systems where the 2D depth images of virtual object models are obtained by calculating the projected distance from each point in the depth image to the object model. These systems can include means for performing the projection particularly fast using polygon rendering hardware and a graphics z-buffer.
As stated above, distance maps are a discrete representation of the distance from grid points in the volume to the closest point on the object surface. Using an interpolation function, such as tri-linear interpolation, distances at grid points can be used to estimate the closest distance from any point within the volume to the surface. In addition, near the surface, the gradient of the distance map can be used to estimate the surface normal.
Distances to object surfaces can be used in a number of applications. For example, the distance maps can be used to determine a path that stays a minimum distance away from objects or an obstacle-free path with minimum length for a mobile robot. As a second example, distance maps can be used in volume rendering to detect surfaces and surface normals
Gibson Sarah F. F.
Perry Ronald N.
LandOfFree
Method for estimating volumetric distance maps from 2D depth... 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 for estimating volumetric distance maps from 2D depth..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for estimating volumetric distance maps from 2D depth... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2559397