History: Malheiro's Mestrado Thesis

Prototype Implicit Modeler

Introduction

The idea used here is inspired on the paper by Desbrun, Tsingos, and Gascuel [1].

The implicit model used is a classic skeleton-based one, using ellipsoidal primitives. In fact, the primitives are spheric on their local coordinate system, which relates to the global system by an affine transformation [2].

Each primitive has an associated triangular mesh. In this particular case, the mesh is a triangulation of level 2 of an icosahedron. To each mesh vertex is assigned a "particle", which moves restricted to a radial axis. Throughout the interactions, these particles flow to the boundary of the implicit surface. When a particle stops at some point of the surface, we have a valid position.

Not all particles move into a correct position. Some particles move too far from their primitives, where the influence of some other primitive if greater than of its owner. Such particles are dubbed invalid. Regions of the mesh that contain invalid vertices should not be drawn, because such regions do not accurately approximate the implicit surface.

The boundaries between valid and invalid regions are determined for each primitive. Then, all such strips are matched against each other to create surface joints. Those joints provide a better approximation of the surface, because they follow the underlying topology of the implicit object.

The matches are done based on the relationship between strips, that is, a strip of A created by the influence of B is combined with a strip of B influenced by A. The estimated normal of the strips are also used to quantify the correctness of the joint: if two strips are not facing each other, the joint is not done.

However, there are times when some strips could not be matched against others. This occurs when:

  • there are singular points on the scalar field nearby and
  • the discretization of the mesh does not give enough precision for accurately describing parts of the implicit surface.
This situation is handled by closing each invalid region with approximations of the surface of the primitive alone. That is, the vertices belonging to a invalid region get positioned regarding only their primitive.

Requirements

The modeler needs a Solaris 2.5.x or 2.6 environment to be run. UltraSparc 1 or a better machine is highly recommended. The modeler was compiled using Solaris SunPRO C++ 4.1, and most of the libraries were compiled statically. In particular, the program uses the Mesa library for the rendering. The required shared libraries are:

    libdl.so.1 =>    /usr/lib/libdl.so.1
    libm.so.1 =>     /usr/lib/libm.so.1
    libC.so.5 =>     /usr/lib/libC.so.5
    libw.so.1 =>     /usr/lib/libw.so.1
    libc.so.1 =>     /usr/lib/libc.so.1
I hope these dependencies should pose no problem for any Solaris environment. If there are any problems, please contact me.

Here is the modeler binary, compressed with gzip (780 KB).

Interface

The interface has been trimmed down to the minimum. Most of the operations can be done interactively with the mouse. The following keys are available:

  • ESC quits
  • SPACE toggles between red and green modes; see below
  • i toggles invalid faces display (green)
  • j toggles joints display (yellow)
  • n toggles normals display (white lines)
  • v toggles valid faces display (blue)
  • r toggles rendering mode (flat shaded/wireframe)
To select a primitive to modify, simply click on its valid faces. A bounding box should then appear. Click again on the background to dismiss the bounding box. Click in the other primitive to place the bounding box on that primitive. Click maintaining the CTRL key pressed to individually select each primitive, thus making possible to select both primitives at the same time.

Mouse operations on the bounding box are interpreted as follows:

For the "red" mode, any pointer drag started on a (invisible) box face is interpreted as a translation, restricted to the plane that contains that face. Picking and moving points on the edges is interpreted as rotations around an axis parallel to the picked edge and passing through the box center. Movement on the red corners is interpreted as an uniform scaling, in relation to the box center.

In the "green" mode, picking on the faces has no effect. Dragging points on the edges is interpreted as scaling in the direction of the picked edge, having the midpoint fixed. Motion of the green vertices is interpreted as a free rotation around the box center, where the corners lie on the surface of a sphere.

Finally, there's a trivial menu available when pressing the right mouse button.

Comments

Currently only two primitives are fully supported. The case with three or more primitives is still in development.

The code is not much efficient, being not optimized at all. But this is planned to happen soon. A lot of things can be enhanced, mainly using the temporal coherence of the interactive manipulation and by caching intermediate results.

The performance bottleneck seems to be the root solving for particle placement on the implicit surface. Because all vertices are evaluated for each frame, this accounts for most of the time spent. The strip identification and matching are computationally cheap in comparison.

Authors

The modeler was designed by me, Marcelo de Gomensoro Malheiros, and my advisor, Prof. Dr.-Ing. Wu, Shin-Ting.

The direct manipulation interface and semantics are given by the MTK toolkit [3], which was developed on top of OpenGL by Flávio Navarro Fernandes, Prof. Ting, and myself.

The modeler also depends on a topological structure management library, TDM [4], written by Prof. Ting.

References

[1] Mathieu Desbrun, Nicolas Tsingos, and Marie-Paule Gascuel, Adaptive Sampling of Implicit Surfaces for Interactive Modeling and Animation, in Implicit Surfaces 95, Grenoble, France, Eurographics Association, April 1995.

[2] Marcelo de G. Malheiros and Wu, Shin-Ting, A Hierachical Skeleton-based Implicit Model, in SIBGRAPI'97, Campos de Jordão, Brazil, IEEE Computer Society, October 1997.

[3] Marcelo de G. Malheiros, Flávio N. Fernandes, and Wu, Shin-Ting, MTK: A Direct 3D Manipulation Toolkit, in SCCG'98, Bratislava, Slovak Republic, February 1998.

[4] Wu, Shin-Ting, Topologie von Hybriden Objekten, Technische Hochschule Darmstadt, Darmstadt, Germany, February 1991, Phd Thesis.