The MT Package - How to build a generic MT

HOW TO BUILD A GENERIC MT

An MT is built by:

Recording the history of a process that iteratively refines or coarsens a tesselation through local updates.
Converting such a history into an MT.

The MT building interface (class MT_BuildingInterfaceClass) provides the functions for doing that.

History recording

The user program must provide a field of type MT_INDEX associated with each vertex and each tile used in the process of refinement or coarsening. Such fields will be used as arguments in the functions of the MT building interface. The program must not manipulate the MT_INDEX fields associated with vertices and tiles in other ways different from initialization and their use in the functions of the MT building interface.

Here is a list of the operations to be added within a program for iterative refinement or coarsening of a k-dimensional tesselation embedded in d dimensions, in order to record its history.

At the beginning

Load the initial tesselation and initialize the MT_INDEX field of every vertex and tile to MT_NULL_INDEX.
Call MT_StartHistory.
For each tile of the initial tesselation:
- for each vertex of such tile, call MT_UseVertex
- immediately next, call MT_MakeTile for this tile
Before starting to refine or coarsen the initial tesselation, call MT_EndUpdate.

Operations 1 and 2 may be exchanged.

At each update operation

For each tile removed from the current tesselation, call MT_KillTile.
For each new vertex created, initialize its MT_INDEX field to MT_NULL_INDEX.
For each new tile created in the current tesselation:
- for each vertex of such tile, call MT_UseVertex
- immediately next, call MT_MakeTile for this tile
At the end of the update, call MT_EndUpdate.

Operations 1,2,3 can be executed in a mixed order, provided that:

If a vertex is new, MT_UseVertex is called on it after having initialized its MT_INDEX field to MT_NULL_INDEX.
A call to MT_MakeTile is preceded by k calls to MT_UseVertex, one for each of the k vertices of the tile.
The calls to MT_KillTile and MT_MakeTile within the same update may be interleaved. It is allowed to Make first, and then Kill the same tile within an update (these "temporary tiles" typically occur in algorithms that apply a process of local optimization within the updated area). The building interface will recognize temporary tiles and remove them from the history.

At the end

For each tile of the final tesselation, call MT_KillTile.
Then, call MT_EndUpdate.
Finally, call MT_EndHistory.

History conversion

History conversion is the operation that builds an MT from a recorded history.

It is recommended to free all data structures used by the refinement or simplification process before building the MT. In fact, there may not be enough memory to hold both such structures and the MT.

Here is a list of operations to be performed in order to convert a recorded history into an MT.

Create an MT and connect it to the building interface by calling function MT_SetTarget.
Then, call function MT_Convert.
Now, the MT has been built and it is ready to be used. The building interface is no longer needed and may be deleted.

An example

We provide here the template of a program that records a history of an iterative process of refinement of a surface mesh and builds a two-dimensional MT embedded in 3D. Recording a process of coarsening is identical, simply the parameter passed to function MT_StartHistory is MT_COARSENING instead of MT_REFINING.

We assume that, given a vertex V of the current tesselation within the user program, the MT_INDEX field associated with V is named V.index; and, given a tile T, the MT_INDEX field associated with T is named T.index.

#include "mt_build.h"

....

MT_BuildingInterface bi; /* the building interface */
MT_MultiTesselation mt;  /* the MT to be built */

/* create mt as a 2-dimensional MT (tiles=triangles) in 3D */
mt = new MT_MultiTesselationClass(3,2); 

/* create the building interface */
bi = new MT_BuildingInterfaceClass(); 

/* start a history for a 2-dimensional MT in 3D, we assume that
   our program is based on iterative refinement */
bi->MT_StartHistory(3,2, MT_REFINING);

/* initialize all MT_INDEX fields of vertices and tiles */
for (... every vertex V of the initial tesselation ...)
{  V.index = MT_NULL_INDEX;  }
for (... every tile T of the initial tesselation ...)
{  T.index = MT_NULL_INDEX;  }

/* record the update that creates the initial tesselation */
for (... every tile T of the initial tesselation ...)
{
  V1, V2, V3 =  ... the three vertices of T ...
  V1.index = bi->MT_UseVertex(V1.index, V1.coordinates);
  V2.index = bi->MT_UseVertex(V2.index, V1.coordinates);
  V3.index = bi->MT_UseVertex(V3.index, V1.coordinates);
  T.index = bi->MT_MakeTile();
}
bi->MT_EndUpdate();

/* main loop */
for (... every update performed on the current tesselation ...)
{
   /* record the current update */
   for (... every tile T deleted in this update ...)
   {  bi->MT_KillTile(T.index);  }
   for (... every new vertex V created in this update ...)
   {  V.index = MT_NULL_INDEX;  }
   for (... every new tile T created in this update ...)
   {
      V1, V2, V3 =  ... the three vertices of T ...
      V1.index = bi->MT_UseVertex(V1.index, V1.coordinates);
      V2.index = bi->MT_UseVertex(V2.index, V1.coordinates);
      V3.index = bi->MT_UseVertex(V3.index, V1.coordinates);
      T.index = bi->MT_MakeTile();
   }
   bi->MT_EndUpdate();
}

/* record an update deleting the final tesselation */
for (... every tile T of the current tesselation ...)
{  bi->MT_KillTile(T.index);  }
bi->MT_EndUpdate();

/* end history recording */
bi->MT_EndHistory();

/* ...free all memory that is no longer needed... */

/* set the description string to be associated with the resulting MT */
bi->MT_SetDescription("A 2-dimensional MT in 3D");

/* connect mt to the building interface */
bi->MT_SetTarget(mt);
   
/* build mt from the history just recorded */
bi->MT_Convert();

/* now, mt contains the MT resulting from construction */