sci.math.num-analysis
SUNA58, Marching Cubes & Group Theory
=====================================
Reference (again) is "Marching Cubes: a high resolution 3d surface construction
algorithm" by William E. Lorenzen and Harvey E. Cline, Computer Graphics volume
21, number 4, July 1987. Quoted without permission: "Using the second symmetry
property, rotational symmetry, we reduced the problem to 14 [well, I think 15 ]
patterns by inspection. Figure 3 shows the triangulation for the 14 patterns."
Does "by inspection" mean that they did it by hand? Allow me some nitpicking if
this is indeed the case.
I once made a little program, which uses a bit of group theory. It checks out
all possible symmetries of a cube. Reading again the Marching Cubes article, I
wondered if the above result could be reproduced with my program, thus avoiding
human "inspection". The program is called "suna58.for". The results of it are
compared below with those of Lorenzen and Cline:
Output suna58 Figure 3
------------- --------
1 <<<<<<<< 0
2 <<<<<<<> 1
4 <<<<<<>> 2
7 <<<<<>>< 3
8 <<<<<>>> 5
16 <<<<>>>> 8
23 <<<><>>< 7
24 <<<><>>> 9
25 <<<>><<< 5
26 <<<>><<> 6
28 <<<>><>> 11
* 30 <<<>>><> 14
31 <<<>>>>< 12
61 <<>>>><< 10
106 <>><><<> 13
Number of cases: 15 , if case (0) is also counted (: why not, huh?)
The case (14) marked with (*) is not found if transformations with non-positive
determinant (mirroring) are also allowed. (BTW, it does no harm if they are !)
Ambiguities are introduced if equalities are involved. What shall we do in that
case: identify them with < or with > ? A rigourous way out is to check out
the essentially different cases with = as an extra relationship. Statements
in our program corresponding with this are commented out. I gave up because the
list of cases to be implemented becomes LONG: more than 147 items are found !
(I only checked it out for general transformations, not rotations exclusively).
Administration of all possible cases is done by the same kind of SETUP routine
which has been employed successfully in SUNA55. But there are minor differences:
eight vertices instead of four, (default) binary instead of ternary number base
and the transformations are rotations instead of permutations. It is here that
a small piece of Group Theory was employed.
The group theory used is encoded in subroutine "groepen". The unit cube that we
start with is spanned by the unit vectors in 3-space, which are of course the
columns of the unit transformation matrix:
| 1 0 0 |
| 0 1 0 |
| 0 0 1 |
As a first step, the columns of this matrix are permutated. This can be done in
six different ways. But transformed unit vectors can also point in the opposite
direction. This enlarges the number of possibilities with a factor 8, resulting
in the well known 6 x 8 = 48 symmetry elements of the cube. Finding next the
transformed vertices and the corresponding numbering is a matter of routine and
a bit of ingenuity (too ;-).
At a certain point in the agorithm, we may decide that only the transformations
with a positive determinant, the rotations, must be kept. This place is clearly
indicated in the program. If you wish to decide otherwise (as I did), then look
for the statement "if(det.eq.0) goto" , and comment it out. Don't forget then
to enlarge several dimensions again to 48 instead of 24 : there are as many
transformations with positive as there exist with negative determinant. It was
seen already that the net effect on the endresult is minimal: 15 cases instead
of 14, if we are (always) including the null case too.
That's all for today, folks! I don't feel the desire to reinvent more intricate
details of this wheel. It was fun, anyway ...
-
* Han de Bruijn; Applications&Graphics | "A little bit of Physics * No
* TUD Computing Centre; P.O. Box 354 | would be NO idleness in * Oil
* 2600 AJ Delft; The Netherlands. | Mathematics" (HdB). * for
* E-mail: Han.deBruijn@RC.TUDelft.NL --| Fax: +31 15 78 37 87 ----* Blood