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