The marching cubes algorithm is defined on regular three dimentional grids. Therefor this engine can only work on data type below the Volume tree in this project. The algorithm is threshold based and tries to calculate an exact surface defined by this threshold.
The algorytm visites every cube in the volume. A cube is defined by eight neighboured data values which form the edges of the cube. The edges are numbered in a defined way.
In the first step each edge is tested against the threshold and for every edge that is inside the object, i.e the data value of the edge is higher than the threshold, a corresponding bit in an edge type integer is set to zero. All other bits are set to one. The result of this step is a number which defines the cube type. According to the fact that a cube has eight edges the type integer is eight bit long and therefore there can only exist 256 different types of cubes. If symetry and rotation is taken into account the number of different cubes can be reduced to XXX. For each of these XXX cube types a triangle setup can be defined. These triangle setups with their rotated and mirrored relatives can now be and written to a lookup table of the size 256 (see MarchingCubesBase::_marchingCubesTable). Depending on the actual type the corresponding triangles are written to a triangle list and this list is then drawn.
In order to speed up the surface calculation a mechanism is included in the marching cubes algorithm to reuse already calculated triangle vertices. This mechanism also has several other benefits. First this mechanism can be used to calculate triangle strips which in turn speed up the rendering (in this project OpenGL is used for rendering). Second this information can be used to calculate correct normal vectors and third smoothing algorithms can also take advantage of the additional information of this mechanism.
o-------------o-------------o /| /| /| / | / | / | / | / | / | / | / | / | o-------------o-------------o | /| | /: | /| | / | | / : | / | | / |(x,y,z-1)-/--:(x+1,y,z+1/--|----o / | / /1=5=3=7/ / | / o-------------o-------------o | / | | / | : / | | / | |/ | :/ | |/ | (x,y,z)-----|(x+1,y,z)----|----o | / | / | / y | / | / | / | | / | / | / o-- x |/ |/ |/ / o-------------o-------------o z
The idea behind this mechanism is to try to map corresponding edges. One such edge ist drawn in dots in the above image. This edge has the number 1 in the cube at the left front, it has the number 7 in the left backward cube and so on. This mapping is done by a mapping table (MarchingCubesBase::_edgeMapping). This table is described in detail in Edge mapping table.
But this mapping table is not the only part of the mechanism. There also exists a bunch of classes which saves the vertices in such way that they can serve more than one purpose. First the vertices should be saved so that they can be found fast and easily. Another requirement is to provide data structures that can directly be accessed by OpenGL. Other purposes have already been mentioned above. The classes also provide connectivity information between vertices. For more information about this data structure see Marching Cubes Data.
The marching cubes engine consists of three components. Its design is derived from the model-view-controller pattern. How this designe is realized can be seen in the following image.
Implementation of the MVC
To be more specific, vuMarchingCubes implements all the code to view and to controll the creation of the object. It also provides a user interface to the marching cubes browser, a little tool which shows all possible cube configurations. The widget classes are implemented to work mostly autonomyouse and give their feedback through so called callback classes which are described later. The view and controller classes are collected in the files vuMarchingCubes.h and vuMarchingCubes.cpp.
MarchingCubesBase holds the data array and implements all the algorithms neccessary for the marching cubes engine itself. All the data specific classes as for example vu112211 are derived from MarchingCubesBase. In this way I could avoid to implement the algorithms several times and can provide a uniqe interface to the controller independent from the data type. MarchingCubesBase resides in the files MarchingCubesBase.h and MarchingCubesBase.cpp. All the spezial files can be found in the Volume subtree of this project.
Marching cubes widgets are parts of the GUI which serve spezial needs. There is for example a widget that shows a key value pair. All widgets are derived from vuMCWidget which holds a wxSizer and is itself derived from wxPanel. All widgets are designed also to hold data they present and therefore provide an interface to access this data from the parent (which is in most cases vuMarchingCubes). For more information on the marching cubes widgets idea see the class vuMCWidget.
Callbacks in the marching cubes engine are realized trough the decorator pattern, This pattern decorates a class with a defined interface provided to the caller. In this engine we have a unique interface defined in vuMCDecorator which is at the one hand a abstract base class to this mechanism and on the other hand defined as a function object. So all derived classes should also be callback classes. Each widget that want's to send a message back to it's parent can do this only if the parent object has provided widge with a callback object of the type vuMCDecorator and when the parent should be informed about anything, it executes the function object.
This mechanism is very flexibe. If the action that should take place, when the callback occures, should be changed, the widget has to simply be given a callback object of another type.
A Callback object should hold a reference to the object that should be called. The callback object is only a decorator to this referenced object and therefor the callback object is not and can not be responsible for deleting the referenced object.
For the caller this looks different. With retreaving a callback object it also retreaves response for this object and therefor has to delete it at the end of it's live cycle.
In this design I follow the rule: a class want's an object, it takes also it's controll. What does that mean. Let's take as an example the above described callback mechanism. A widget want's to call back it's parent so it requests a callback object. The parent creates the object and present's it to the widget. By taking the object from the parent, the widget has also takes over it's controll and hase therefore to destroy it at the end of the widgets live cycle. wxWidgets also fallows this rule and therefore non of the widgets is destroyed in vuMarchingCubes.
The only problem is to define when an object is given to another class. My definition of this situation is when the given object isn't interfaced (i.e. none of it's member functions is called) in class which gives the object away. In all other cases the object remains in the controll of the class which created it and this class has to destroy it.