(2)
The goal of this project is to automatically produce a "nice" picture of a given two-dimensional cellular complex, a purely topological description of a graph drawn on a surface.
This work was motivated by the need to debug the topology of solid models used in computer graphics and engineering. In the boundary representation technique, commonly used by such applications, a solid object is defined indirectly by its bounding surface; and the latter is described as the union of a finite number of faces (simply connected patches, flat or curved), edges (open arcs, straight or curved) and vertices (single points).
When manipulating such models, it is advisable to handle separately its topological properties (the contacts between faces, edges, and vertices) from its geometrical properties (vertex coordinates, face equations, etc.) This separation greatly improves the modularity and versatility of geometric algorithms.
The topological aspects of such a boundary model can be formalized as a combinatrial structure known as a two-dimensional cellular complex. The complex specifies only the number of edges, vertices, and faces, and their incidence relationships, freed from all geometrical data.
The topology of a cellular complex, even a small one, may be hard to understand intuitively, which makes it hard to debug programs that deal with boundary representations. Since topology and geometry are handled by separate procedures, one cannot rely on the visual appearance of the object to verify the correctness of its topology. Faces that may look adjacent on the screen may not be adjacent in the topological data structure, and vice-versa.
Motivated by these difficulties, we set ou to develop a graphical tool for the automatically visualizing the topology of a cellular complex: a program which, given only the incidence relations among the elements of a complex, will choose a "nice" surface in three-space, and partition it into points, arcs, and disks, so as to clearly display those incidence relations.
The input to our tool is a quad-edge data structure that describes the incidence relationships between the faces, edges and vertices of the complex.
To realize the complex, we use a polyhedral surface, consisting of a mesh of flat triangles. its shape is completely determined by the coordinates of its vertices $\CV T = \set{v_1,\dd v_n}$; we say that these $n$ points pf $\BR^3$ are a configuration of the mesh.
In order to make the topological atructure easy to understand, the geometric representation must be "nice" and "clear". We must try to avoid artifacts such as creases and self-intersections, which attract the eye but do not have a topological significance; and the elements of the complex must be well-separated, in space if not on the image plane.
The "ugliness" of the surface is quantified by some function from $(\BR^{3})^n$ to $\BR$, called (for historical reasons) the energy function. Thus, we seek a geometric realization with minimum energy.
The energy functions we have tried were convex combinations of several partial energies, each measuring one particular kind of "ugliness." Some terms are concerned with smoothness of the surface, as measured by the dihedral angles between adjacent triangles. Other terms measure the "crowding" of edges of the complex on the surface, the variance of their lengths, and so forth.
Note that the "nicest" realization of the complex is not necessarily the "nicest" shape for the underlying surface. In order to keep the edges of the complex uniform and well-separated, it may be ncessary to use a surface that is elongated, flattened, or twisted out of its "nicest" shape.
Finding the surface of minimum energy is a nontrivial optimization problem, since even for a small complex the energy function will have hundreds of independent variables. We use a combination os specially developed heuristics, general-purpose non-linear optimization routines, and random search. We have tried several general purpose numerical optimization techniques, but there is still considerable room for improvement here.
It should be possible to use combinatorial heuristics, such as simulated annealing, to extend the search beyond the nearest local minimum; but we haven't been able to get such methods to work fast enough.
Besides these general-purpose optimization algorithms, we have also used specialized heuristic smoothing methods. These are local smoothing and straightening operations, applied to each vertex $v$ of the mesh in turn, cyclically, up to a prescribed number of passes.These heuristics are not sensisitive to the energy functions or their weights. Therefore, they are useful only as a preprocessing step.
The following pictures show the smoothing of a complex having four faces with 4 sides each, and two faces with 2 sides, connected so as to form a "sausage" balloon. This complex was modeled by a mesh of 360 triangles, as explained in the papers (see below).
(1)
(2)
(3)
(4)
In the starting configuration, figure (1) above, each vertex of the mesh is given a random position inside the unit sphere. Fifteen passes of the heuristic smoothing algorithm produced configuration (2). After 100 such passes, we had a smooth surface with the correct overall shape (3). The general-purpose minimizer was then used, resulting in figure (4) after some 2000 function evaluations. (Note the bend, which implies that this configuration is still not optimal.)
Below are a few other examples: the simplest complex whose surface is a Klein bottle (5), and a 12-face complex whose surface is a tritorus (6).
(5)
(6)
The following pictures illustrate an unplanned test of the Toposcope tool as a debugging aid. The original intention was to run the tool on a "star shaped" complex, a five-armed version of the "sausage" complex of figure (4). Instead, we got the strange shape shown in figure (7). This picture revealed quite effectively that there was a bug in the program that generated the test data. We fixed that bug, but re-running the Toposcope still returned a wrong image (8). This image led us to a second bug in the program. After fixing it, we finally got what we had expected (9).
(7)
(8)
(9)
Note that two of the arms in figure (9) are turned inside-out. It so happens that this particular configuration is only a loal minimum of the energy function. The tendency for the optimizer to get stuck in such local minima is the main obstacle we are facing. Currently, our only strategy to get rid of such crossings is to run the heuristic smoothing step some 10-20 times, with random starting points, and select the best oututt for further optimization. Surely there must be a better way...
There are plenty of loose ends that need to be tied up, for instance:
On a higher level, it may pay off to use higher-order polynomial patches (e.g. Bézier or NURBS) to model the surface.