A hybrid modeling technique being developed by re searchers in Canada could help propel implicit surfaces into the computer graphics mainstream.
Unlike most computer-based 3D geometric modeling techniques, which are based on polygonal models or parametric surfaces generated from sets of carefully constructed control points, implicit surfaces consist of contours (isosurfaces) through some scalar field in 3D. The resulting implicit models are defined by finding a field value for a large number of points in space to calculate the 3D contour.
Primitive shapes, or skeletons, such as spheres, planes, and cylinders may be combined using various operations. These include adding, subtracting, and blending multiple skeletons to describe smooth, intricate, deformable shapes that are difficult or inefficient to represent with conventional polygonal or parametric building blocks, even if primitives such as spheres or Bezier-spline surfaces are used.
Unfortunately, implicit surface techniques are hampered by the lack of efficient methods for producing polygonal meshes from the skeletal descriptions, which is necessary for visualizing the implicit models. Current graphics hardware is not fast enough to enable existing polygon conversion techniques (such as particle, voxel-based, and adaptive methods) to be used for the interactive modeling of complex implicit forms. Consequently, computer graphics researchers have been searching for new algorithms that will enable them to fully exploit the advantages of implicit surfaces.
 |
| Blended spheres, which are well suited to modeling with implicit surfaces, are shown at various initial grid sizes and levels of subdivision. A conventional polygonization technique is enhanced by the application of subdivision surfaces as a post process |
Toward this end, Brian Wyvill and Pauline Jepp of the University of Calgary, together with colleagues Kees van Overveld of Philips Research and Geoff Wyvill of the University of Otago, have developed a system that combines an existing, voxel-based implicit polygonization method with a subdivision surface technique to quickly approximate and smooth an implicit mesh.
A subdivision surface is a method of generating curving surfaces by taking a mesh of polygons, and refining those polygons by replacing them with smaller polygons according to a set formula. The resulting polygon mesh, over successive generations, approaches a smooth curve. In this application, subdivision surfaces are applied as a post process to smooth the mesh that has been generated using an implicit surface polygonization algorithm.
The polygonization algorithm the system employs divides the object space into cubic voxels, then tests selected vertices for edges and intersections, and marks them accordingly. Although this technique produces a consistent mesh, on its own it doesn't meet the interactive modeling needs of most applications. The algorithm is slowed by the multitude of implicit function evaluations it requires, says Wyvill. "An implicit surface tiler has to make many function evaluations to find a point on the implicit surface. Once a voxel edge is found to intersect the surface, then some kind of root-finding algorithm must be applied to iterate to the intersection point, which involves several implicit function evaluations [for each intersection]."
Subdivision surfaces have no such baggage, since each iteration automatically produces a new, smoother mesh, thus the visualization technique is much faster than implicit surface polygonization.
 |
| A polygonization algorithm provides the initial polygon mesh for implicitly modeled spheres. The mesh is then repeatedly smoothed at various levels with a subdivision algorithm. With simple shapes, the time it takes to generate the initial mesh and its su |
The hybrid technique developed by the researchers takes advantage of this, while retaining the flexibility of implicit models, by enabling the smooth mesh points created using subdivision surfaces to migrate to the implicit surface. The migration transpires in idle moments when the user is not interacting with the model. The result is a significantly faster visualization process. "The time for subdivision plus the time taken to find the initial polygonization is considerably smaller than the time to generate an equivalent number of polygons by polygonization alone," says Wyvill.
The new algorithm is still in its early stages of development. The researchers have tested it on simple implicit models and are satisfied that it saves significant processing time. Complex implicit models are more challenging. For example, says Wyvill, "we have some very complex shapes consisting of hundreds of primitives described by a tree-like implicit modeling structure we developed called the Blob Tree. Polygonizing these models can take 20 minutes on our fastest machine." The researchers' goal, he says, is to further develop the hybrid polygonization algorithm "so we can reduce this time, and eventually produce images at interactive rates."
In addition, the researchers are looking at ways the technique can be further enhanced by providing tools for the user to indicate specific areas of interest that can be preferentially smoothed.
Diana Phillips Mahoney is chief technology editor of Computer Graphics World.