Implicit Surfaces and Real-Time Graphics

Kyle is a member of the Advanced Technologies Group at Advanced Visual Systems in Boston. He is also the author of POWER-3D: High-Speed 3D Graphics in Windows 95/NT (Manning/ Prentice-Hall, 1997, ISBN 0-13-841214-6). He can be contacted at [email protected].

Implicit surfaces are generally defined by an equation model that provides a logical basis for creating a closed surface in space. Implicit surfaces are useful in that they can be used in areas such as molecular modeling, animation, geophysical systems, and weather analysis.

Implicit surfaces are at the heart of Silly Space, the modeling application I'll describe in this article. Silly Space (available at http://www.inside.ch/silicon_softworks/ or http://inside.net/silicon_softworks/) lets you manipulate implicit surfaces in a real-time, click-and-drag 3-D environment under Windows 95/NT. Silly Space works by integrating an equation model, 3-D user interface, and surface tessellator into one working body. These components fit tightly together to provide an easy-to-use, robust modeling application.

Figure 1 is a function that describes the implicit surface of a two-component blob (or "meta-ball," as it is more commonly referred to). Figure 2 is the two-component blob modeled in Silly Space. By plugging in arbitrary values for x, y, and z in Figure 1, you can test where the function changes sign. It is at this point that a surface needs to be determined for visualization.

Of course, there are numerous methods for building a visualization of this surface. In raytracing, an exact evaluation of the surface is done for a displayed pixel. The surface can also be decomposed with voxels (volume pixels) to show the variations in density of the space given by the equation. In Silly Space, I decompose the surface into a set of triangles using a polygon tessellator.

Multi-Geometry Surface Model

Implicit surfaces can be generated in many different ways, the most common being to design an equation that models the desired surface, then visualize or model it. However, this is cumbersome, time-consuming, and error-prone. In the interest of simplicity and flexibility, I used a multi-geometry surface model (MGSM) -- a component-based implicit surface model. Figure 3 presents the general form of the MGSM model.

The goal of this model is to allow interactive user selection of various components and shapes and to connect this with the user interface. The quantities in the model are:

• Threshold, which specifies how tight the surface is in relation to the components of the model.
• shape(x,y,z), which provides the individual shape of a particular component. In Figure 2, I used two sphere-shaped components.
• space(x,y,z), which provides for spatial effects -- rotation, scaling, stretching, and so on -- for each component.

The MGSM model is implemented in Silly Space by taking each of these quantities and tying them together in a fast C++ implementation (see Listing OneThe exact model for the MGSM is given in Figures 4(a), 4(b), and 4(c). The first step is to perform the preliminary rotation of an individual component in the field. For instance, if you have a normal sphere component and a sphere component that has been stretched in two directions into a disc-shaped object, you could rotate the disc freely in any number of directions. This rotation is specific to the component only, and all other components will stay fixed in space.

Figure 4(a) shows the equation form for the rotation that is the first step in the MGSM. Figure 4(a) is part of the space(x,y,z) transformation. The rotation equation takes the three angles, relative to the x-, y-, and z-axes, as well as the parameters given as arguments to the MGSM call, i(x,y,z).

Now that we have performed the rotation of the given testing point with the equation in Figure 4(a), the next step is to add stretching and translation to the individual component. This transformation is also still part of the space(x,y,z) aspect of the MGSM.

The last modeling aspect of the MGSM is to apply the shape of the current component. Figure 4(c) is one example component. The shape given is the implicit equation of a sphere (meta-ball). The evaluation of this quantity is for a single component in the entire surface. The corresponding summation of many of these components is what makes a complete, artistic surface in Silly Space.

Decomposing MGSM into Triangles

Silly Space makes use of Jules Bloomenthal's implicit surface tessellator, which was presented in Graphics Gems IV, edited by Paul Heckbert (Academic Press, 1994). The tessellator works by accepting a function similar to the MGSM and searching the space to find the edge of the surface.

Bloomenthal's tessellator moves around on the surface of a geometric definition and creates a triangle-based tessellation of the model. It does this by using a collection of cubes to walk around on the surface. Each cube is used to isolate the surface along the boundaries of the cube (see Figure 5). The resultant testing of the 8 vertex locations on the cube gives 2⁸=256 possible test cases. These test cases are either positive (inside the surface) or negative (outside the surface). The test cases are mapped to bits and used in a look-up table to determine which edges need to be searched for the surface. After calculating all of these edge/surface intersection points, the algorithm then spits out the representative triangle set for that cube. The cube is then moved to the next point on the surface.

Silly Space uses a hybrid version of Bloomenthal's original tessellator. Some specific additions and modifications to it for real-time interactive use include:

Initial surface detection. The original tessellator used a random space searching method to find the starting edge of a surface. Silly Space computes the exact starting point of a surface and begins tessellation at this point. This turns out to be much faster than the random searching method if you already know where to start.

Object orientation. The tessellator was broken down into a modular object-oriented form in C++. This new modular form was ideal for finding optimization points, and code enhancements gave an overall performance increase.

Disjoint surface detection. The original tessellator did not find disjoint surfaces, or surfaces that were not attached to the currently tessellated surface. Silly Space's implementation detects and tessellates these disjoint surfaces in a nearly linear manner.

Improved memory model. The original memory allocation model was not well suited to repetitive real-time calls to the tessellator. The memory model was replaced with an allocation model that prevents memory leakage and speeds up overall memory allocation and destruction.

Component Shapes

Any given surface or set of disjoint surfaces is made up of a collection of components. These components can take many different shapes. In Figure 2, for instance, the two components were in the shape of spheres.

Other forms are possible, such as a cube, or even a toroidal-shaped component; see Figure 6. There are no real limits to the variety of individual field-based components in Silly Space. The trick is finding the ones that are computationally quick to evaluate and are actually useful as primitive modeling components.

Spatial Transformations on Components

Another significant part of the MGSM is the idea of applying various spatial effects to any given component shape. Spatial- transformation effects are applied to part of the model. All traditional spatial transformations fit well into this model.

For instance, scaling along the x-,y-,z-axes can be done by modifying the spatial-transformation part of the model so that it scales the individual component along each axis. This could be done, for instance, by multiplying the testing point by, say, 0.6 to shrink the model on the x-axis by 40 percent. Figure 7 shows five individual components--one a perfect sphere, the others stretched into the forms of disks. Each disk is created by taking the perfect sphere and stretching it along two separate axes. Additionally, each disk is rotated about different axes. The wireframe camera view on the right has lines indicating the centers of each component.

Components can also be created that subtract space from a surface. For instance, consider using a number of components in the traditional sense (each component adds to the model). If you take a single component that is among a collection of positive or additive space and invert the field, the component will subtract from the space of the model.

On the front cover of this issue, for instance, the penguin's nostrils use negative or inverse space to subtract from the main figure. Mixing and matching both positive and negative space provides a powerful way of shaping and molding the space. This combined with different component shapes and the transformations you can apply to these shapes gives the user a flexible, easy to use modeling application.

Texturing Implicit Surfaces in Real Time

Silly Space also provides a real-time texturing capability for implicit surfaces. In Figure 8, the human hand was created in about 15 minutes by stretching and shaping each finger and attaching them to a base disc. A texture that resembles skin is then attached to the surface. Note the top-right camera view. This view is inside of the hand looking down the finger spaces. The lines are the component fields that make up the hand. The texturing is done by importing and attaching a Windows bitmap (BMP), a device-independent bitmap (DIB), or a run-length encoded bitmap (RLE). Because the image file is converted to one of these formats, any image can be used.

Silly Space implements a couple of optimizations to speed texturing of the surfaces. The first step is to reduce the given texture to a power of two and scale it into a square. Computers can multiply and divide by a power of two very quickly. The multiplication or division by two operations boil down to a shifting of bits, as opposed to a multiplication call. For instance, the number three is 11 in binary, and the number six is 110. By shifting the bits left one, the number is doubled. This aids the scaling process as the bitmap size can be scaled to a good texturing size very quickly. The closer the size of the available texture to the one being drawn, the better the texture mapping. Silly Space also converts the bitmaps palette to a true color 24-bit palette. Figure 9 shows the complete hand with the texture color blended with the base color of the implicit surface, which is in this case a light orange.

The Silly Space API

Silly Space uses the traditional MFC document/view model; see Figure 10. Silly Space provides derived classes from the base CView and CDocument classes. These derived classes are called CSillyView and CSillyDocument, respectively.

The Silly Space document object, CSillyDocument, contains all of the data necessary to build the live model. This includes the surfaces, spaces, shapes, and tessellations of the model. It also includes the necessary streaming code for writing the models and surface bitmaps to disk. The object handles all of the following details:

• Streaming of objects to a CArchive object for persistent (on disk) storage.
• Collections of components with the associated parameters for computing the geometry surface of a model.
• The shapes (sphere, disk, and so on) of user-created components in the model.
• The spatial transformations (scaling, translation, and the like) of user-created components.

The Silly Space view object, CSillyView, provides the implementation details of the 3-D user interface. It also handles construction and setup of the OpenGL rendering context, or the HRC. Command handlers provide control and manipulation of the modeling surfaces. For instance, you click on one button to increase the detail level of the surface tessellation. This changes the necessary geometry and CSillyDocument parameters and recomputes the tessellation. CSillyView is responsible for:

• 3-D click-and-drag UI, which is what makes Silly Space so easy. It makes use of Geometry Object Extensions (GOEs) to handle the intersection and interactive manipulation of components in the space.
• Command handlers, which provide input and capability beyond the 3-D click-and-drag UI. Command handlers for the view change the current tool (from a node select tool to a hand tool, for instance).
• Camera view parameters. Individual views have different camera viewing parameters. Each view can be a different camera angle on the model.
• OpenGL initialization. CSillyView also provides complete initialization and setup of OpenGL for proper use in Silly Space.

Geometry Object Extensions

OpenGL provides a framework for fast and accurate graphics, but it does not do everything that is necessary to make Silly Space work. The biggest deficit is the lack of an internal method for holding and maintaining data containers and data structures for building models. This is not really a downside of OpenGL, however, as every graphics application will need a different form of container. Silly Space requires the ability to collect data and then provide user interface queries, creation and deletion of members, fast pipelining of data into OpenGL, and so on. To provide these abilities, I created Geometry Object Extensions (GOEs) to the OpenGL framework. GOE objects are what make Silly Space easy to use. They provide an abstract layer of communication between the surface tessellator, the object database (CSillyDocument), OpenGL, and the user. The objects I created include:

• LObj, a derived object from the MFC CObject. This object specifies proper virtual methods for drawing an object and for persistently storing the object.
• LVector, the fundamental 3-D math geometry object. This object provides normalization, magnitude, scaling, skewing, and other members for handling 3-D space.
• LPlane, the plane object that handles all of the intersection and collision functionality. This object is the fundamental unit for the 3-D UI.
• LCube, a cube object that can be drawn, and is used in intersection calculations with the mouse. The cube object uses a set of six LPlane objects for intersection testing.
• LSphere, which can be drawn like the others and provides a ray-to-sphere intersection capability. Stretched spheres are used for intersection of the implicit surfaces in Silly Space.
• LTriangles, which provides organization of vertex-indexed triangles and handles the drawing and modeling of collections of triangles in an API optimized manner. For instance, this object uses the shared vertex lists feature (when possible) that is new in OpenGL 1.1.
• LSurface, which encapsulates the implicit surface tessellator, intersection calculations for the user interface, different drawing modes, texturing, and the overall behavior of surfaces in Silly Space.

Spline Paths for Components

Suppose you want to move the components of the field around in space. You know those movies they make with lumps of clay? They move the clay and then take a picture, and then more the clay again, and so on. Eventually they have a complete movie. This process is slow and cumbersome.

Silly Space lets you design the complete model, and then key-frame motion in the model. You can, for instance, create three separate states for the model. Silly Space then takes the user parameters of the quantity and fits spline curves through these parameters. The result is an infinitely smooth animation of the components, even though the user only specified three frames.

Listing One

LSurface Components;    // Given Instance in Object Database// Pre-Allocated Temporaries for Calculations
static float    x1, y1, z1, x2, y2, z2, Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, 
                                                          Tmp7, Tmp8, Tmp9; 
float LSurface::MGSM(float x, float y, float z)
{
    // Initialization of Threshold and Number of Components
    float   Total=Components.GetThreshold();
    int N=Components.GetSize();
    // Loop through all components
    while(N -- ) {
        Ci=&Components[N];  // Get Pointer to Current Component
        // Check For Any Angular Rotation
        if( !((Ci->Theta_X==0) && (Ci->Theta_Y==0) && (Ci->Theta_Z==0)))
            {
            // There is Angular Rotation So Use Angular Model


</p>
            // Perform Translation of Component
            Tmp1=x+Ci->Tx;  
            Tmp2=y+Ci->Ty; 
            Tmp3=z+Ci->Tz;  
// Calculate Temporaries for Rotation
            Tmp4=Tmp2*Ci->cos_z;    
            Tmp5=Tmp1*Ci->sin_z;
            Tmp6=Ci->cos_z*Tmp1;    
            Tmp7=Ci->sin_z*Tmp2;
            Tmp8=Ci->cos_y*Tmp3;


</p>
            // Perform Rotation
            x1=(Ci->cos_y*(Tmp6-Tmp7)+Ci->sin_y*Tmp3);
            y1=(Ci->sin_x*(Ci->sin_y*Tmp6- Ci->sin_y*Tmp7-Tmp8)
                + Ci->cos_x*(Tmp5+Tmp4));
            z1=(Ci->cos_x*(-Ci->sin_y*Tmp6+Ci->sin_y*Tmp7+Tmp8)
                + Ci->sin_x*(Tmp5+Tmp4));
            // Perform Stretching
            x2=x1*Ci->Sx;       
            y2=y1*Ci->Sy;
            z2=z1*CI->Sz;
            // Calculate Divisor
            Tmp9=(x2*x2+y2*y2+z2*z2);
            Total-=( Ci->Strength / (Tmp9< 0.000001? 0.000001 : Tmp9));
        }
        else {
            // There is No Angular Rotation (x1), So Use Simple Form


</p>
            // Translate and Stretch at the Same Time
            x2=(x+Ci->Tx)*Ci->Sx;   
            y2=(y+Ci->Ty)*Ci->Sy;
            y2=(z+Ci->Tz)*Ci->Sz;


</p>
            // Calculate Divisor
            Tmp9=(x2*x2+y2*y2+z2*z2);


</p>
            // Apply to Threshold
            Total-=(Ci->Strength / (Tmp9< 0.000001? 0.000001 : Tmp9));
        };
    };
    return Total; 
}

Back to Article

DDJ