Issue: Volume: 23 Issue: 12 (December 2000)

A Closer Look at Distance Fields



DIANA PHILLIPS MAHONEY

A one-size-fits-all solution in computer graphics is hard to come by. If you want a nicely rendered 3D representation of an object at minimal time and computational expense, you typically have to sacrifice fine detail and interior information. If you want fine detail and comprehensive information on the object's internal structure, it will cost you in render speed, memory, and quality. This trade-off is generally the result of having to choose between various modes of data representation, typically polygonal versus volumetric approaches.

A new system under development at the Mitsubishi Electric Research Laboratory (MERL) in Cambridge, Massachusetts, may end the need to choose one form of representation over another by integrating key advantages of both, along with a broad range of associated processing operations, in a single graphical data structure.

The technique is based on an existing graphical data structure called the distance field. A distance field is a scalar field (a discrete representation of measured or simulated data) that measures the distance from a given point to an object or data volume, including information about the inside and outside of the structure. Distance-field representations, which are generally acquired by sampling the collected discrete information at regular intervals, are used as alternatives to surface representations, such as polygons or NURBS. While they can be used to effectively gather shape information, regularly sampled distance fields have drawbacks because of their size and limited resolution. For example, fine detail requires dense sampling, thus necessitating an immense amount of information to accurately represent distance fields when any fine detail is present, even if the detail only occupies a small fraction of the volume.
Smoke and mirrors. A nicotine molecule is represented by adaptively sampling the surrounding distance field. The resulting thick, translucent surfaces are enhanced with volume textures for color and transparency variation.




MERL researchers Ronald Perry and Sarah Frisken have developed a novel distance-field implementation that avoids this pitfall. Called adaptively sampled distance fields (ADFs), the system uses a unique sampling approach that automatically adapts the sampling rates based on the amount of detail in the distance field. For example, an ADF uses high sampling rates in regions where the distance field contains fine detail and low rates where the field varies smoothly.

The primary advantage of ADFs over the standard shape representations that are more commonly utilized for geometric design (such as parametric surfaces, subdivision surfaces, and implicit surfaces) is their ability to quickly and efficiently represent a wide range of graphical shapes, including artistic and organic forms, precision parts, high-order functions, and fractals.

In addition, ADFs support a broad range of important processing operations, including rendering, sculpting, level-of-detail management, surface offsetting, collision detection, Boolean operations, blending and filleting, creating offset surfaces, and morphing between shapes.

For efficient processing, ADFs store the sampled data in a spatial hierarchy that allows for level-of-detail (LOD) management by arranging sampled values based on their depth in the hierarchy.

Numerous ways to organize the adaptively sampled distance values into a spatial hierarchy have been developed by the researchers including octree-based methods. An octree-based ADF subdivides space into cells of different sizes and stores distance values at cell vertices. Distance values and surface normals within each cell are reconstructed using a trilinear interpolation technique.

With the data so organized, ADFs can be generated in a number of ways. Two examples are a bottom-up and a top-down approach. The former starts with a regularly sampled distance field of finite resolution and constructs a fully populated octree for the 3D data. In the top down approach, the distance values of the root node of the ADF hierarchy are computed, then ADF cells are recursively subdivided. For example, if the primary interest is the isosurface represented in the field, the recursive subdivision would stop if the given cell is guaranteed not to contain the surface, if the cell contains the surfaces but passes some predefined measure, or if a specified maximum level in the hierarchy is reached.

For memory and CPU efficiency, the researchers have developed methods for generating ADFs from standard forms such as CSG and triangle models. These methods have successfully produced representations of complex objects requiring a dynamic range of 1:100,000, which would re quire gigabytes of memory in a traditional volume representation.
Distance values farthest away from the zero-value isosurface of an alcohol molecule produce a colorful, haze-like effect. Adaptively sampled distance fields employ a hierarchical organization that stores sample points for both surface data and ray/surface




Among the most valuable of the ADF capabilities are precise carving and volume representation functions. Because the ADFs efficiently sample distance fields with high curvature, they can be used to represent sharp surface corners without depleting memory. Thus, says Perry, "carving is intuitive. The object is edited simply by moving a tool across the surface. It doesn't require any control-point manipulation, remeshing the surface, or trimming." By storing sample points in an octree, both localizing the surface for editing and determining ray/surface intersections for rendering are efficient.

With respect to volume rendering, the researchers have employed a raycasting technique to demonstrate some of visual effects that can be achieved. For example, offset surfaces can be used to render thick, translucent surfaces, and varying the color or transparency can be used to add volume texture within the thick surface. Although the sampled ray-caster is not optimized for speed, notes Perry, "properties of the ADF data structure can be used to increase the rendering rate." For example, he adds, "the octree allows us to quickly skip the regions of the volume that are far from the surface. Also, because distances to the closest surface are available at each sample point, we can use space-leaping methods to speed up rendering."

On the engineering side, ADFs may prove to be powerful tools for computer-aided machining. The use of a distance function allows the representation of the surface, the interior of the object, and the material that must be removed. Additionally, knowledge about the internal structure of objects as well as distances to the closest surface can be used for planning tool paths and tool sizes for the machine process, and offset surfaces can be used to plan rough cutting for designing part molds for casting. Finally, ADFs can represent fine surfaces and sharp corners efficiently, making it possible to represent unsurpassed (with traditional techniques) machining precision in the ADF model.
The ability to adaptively sample the distance fields of objects with high curvature means the technique can be used to represent sharp surface corners without the huge memory drain that usually accompanies such tasks. It also lets users easily "carve" obj




Currently, the MERL researchers are considering a number of enhancements to the ADF system, including the use of different hierarchical structures and reconstruction methods as well as efficient conversion between ADFs and standard (polygonal and NURBS) models. "We also exploring the use of ADFs in numerous artistic and entertainment applications including digital sculpting for character design and animation," says Perry.

More information on MERL's ADF research can be found at http://www.merl.com.

Diana Phillips Mahoney is chief technology editor of Computer Graphics World.