![]() ![]() ![]() ![]() ![]() |
Experimenting with marching cubesExperimenting with marching cubes is the best way to clearly understand how it works and why it's important to use ambigous case resolution. In this way, the applet gives you the opportunity to view the algorithm running on different cases. How to use this applet?
Firsly, if your browser is not able to run the applet, please download the latest version and check if java support is enabled. ![]() ![]() Here is a description of the controls and the supported functionnalities of the applet: Modify weight of vertices
On the right panel are eight slider bars; each of them, identified by a number and a weighting, controls the corresponding vertex. For example, the slider "Vertex 4 (16)" controls the value of the vertex number 4 of the current selected cube, and, if positice, this vertex counts 16 in the case number (see algorithm section for more details on the numbering method). A great advantage of the applet is to allow visualization from any angle; to control the view, just select the mode (translation or rotation) in the transformation panel (upper-left corner), then press and drag the mouse over the viewport. If you want to change the view using the Z axis, press the shift key while draging the mouse. Build a mesh with different cubes
It is possible to have more than one cube, to see interactions between them. To add a cube, start by selecting a cube, using the current cube combo box in the upper-right corner or the space key, which cycles through all the existing cubes. Then, in the modelling panel, choose the face next to which you want to add the new cube, and finally, press the add cube button. To delete a cube, simply select it and press the del cubebutton. Note that in the two cases, the mesh will be automatically centered in the wiew.
In the bottom-right corner, the switch to complementary case button allows you to replace current cube by its complementary (number 255 - current number). The reference value is used to compute interpolation along edges; modifying this value can be done using the isovalue textfield, on the middle of the left panel, and will affect the position of the extracted surfaces. Control rendering parametersRendering parameters are used to customize the aspect of the objects. In the appropriate panel of left site of the appel, you can choose the material among some predefined values, the lighting model: lambert (without specular reflects) or phong (with specular reflects), and if you want the cube architecture to be displayed. DownloadsApplet source code - the sources of the applet (with comments)Applet classes and html file Applet javadoc - the javadoc related to the applet Lookup tables - the tables we used to draw triangles and ambiguous cases Report - the report of our project (.PS) Implementation tipsThis part explains the difficulties we encountered, and anybody else may also encounter, when implementing the marching cubes; it might provide some useful programmation advices that could speed up coding. Here is also an on-line version of the javadoc. What data structure should I use? - to implement marching cubes, it is quite obvious to create a "cube" class to modelize a single cube. What is less evident is to dissociate vertexes from the cube: if we were just considering one cube, this would not be a problem, but in a genericity point of view, when processing a gathering of cubes, we mustn't forget that one vertex may belong to more than one cube, and having data redundancies would make the algorithm more complex and heavier. It will also be a good thing to implement a "mesh" class to manipulate these gathering of cubes as single objects. Have a glance at the source code of the applet and you will see this Mesh/Cube/Vertex three level container architecture.
What triangles should I draw? - knowing the weighting of a cube, it is not really difficult to compute the interpolated values along the edges using a linear interpolation method which consists here in solving a first degree equation. Let W1 and W2 be the respective weights of the two extremities of one edge, and R the reference value; what we want is the t value which solves: (1-t)*A + t*B = R t = (R-A)/(B-A) Now that we've got all the interpolated values, we should determine which triangles to draw. We have seen that all cases could be sorted into fifteen families. Trying to make a faultless program which computes the family of a given case by applying rotations and symmetries is far from easy, that's why we use a two hundred and fifty six entries lookup table telling, for each case, the triangles that should be displayed. Note that the table we use in our applet considers ambiguity resolution by introducing the complementary cases seen in the theoretical approach (download triangles.lut.txt for more details on this table).
How can I solve problems due to ambiguity? - if you use the same kind of lookup table as us and if you do not want to be able to specify if you want or not ambiguous resolution, this is not a problem: just compute the case number of your cube by adding weights of vertexes, pick information in the table and draw the corresponding triangles. If you use the same table but don't want to use ambiguity resolution, it is necessary to be able to identify the cubes whose complementaries have been replaced to solve ambiguity. For this, we can consider another hand-made lookup table which contains all these cases: if a cube belongs to this list, do not look for the cube in the first table (it won't be the right one), instead, draw the its complementary and reverse the normal of each triangles. If a cube doesn't belong to this list, treat it as you normally do. How to easily manage weighting? - when processing models composed of more than one cube, some vertexes belong to many of them; of course, when modifying the weight of such a vertex, we want the surfaces of all the cubes it belongs to to change. The best way we found to manage this is to keep "pointer" relation between vertexes; if two cubes use pointers referencing the same object, you don't have to bother anymore: modification of the same vertex from one or the other of the two cubes will have the same effect. The problem is solved! But if you use multiple instances of one vertex for each cube, this won't be so easy... Note that in the applet source code, we do not use direct pointers on vertexes but only on their weight: this might be useful if we want to keep some data specific to each vertex. Why keep topology information? - when adding a cube to a model, it is necessary to scan other cubes and look for vertexes at the same position and, if finding any, merge them (using pointers, as explained just above). If having any information on the topology or connexity, like neighbourhood, this search can be restricted to the surrounding cubes, which results in a time consumption improvement. Depending on the expected results of the algorithm, topology might also have other uses. |
---|