Computer Aided Surgery Exercise 4

Marching Cubes

Due date: 10.06.2003

In this exercise you will implement the Marching Cubes algorithm by Lorensen and Cline.
We supply you with an image class CtImage1 which is found here. Your program will input three parameters: an input file name with a serialized java Vector describing the CtImages, an output file name, and an iso value. The output will be a VRML model.

Example:
     java MarchingCubes 150 case1ImageData.obj case1.wrl

     150 - The iso-surface value.
   case1ImageData.obj - A file containing a serialized Vector containing CtImages (in this case two images).
   case1.wrl - The output file describing the triangles the marching cubes algorithm created.

We now take a look at the content of the VRML file. Marked in red are the interesting parts:
 
#VRML V2.0 utf8

Shape{ 
  appearance Appearance { material Material {
                                                           ambientIntensity 0.5
                                                           diffuseColor 0.44 0.44 0.44
                                                            specularColor 0.15 0.15 0.15
                                             }
                                         }
  geometry IndexedFaceSet {
                 coord Coordinate { point [ 10 15 20,
                                                           5 20 20,
                                                           10 20 10,
                                                           15 20 20,
                                                           10 25 20 ]
                                              }
                  normal Normal { vector  [ -0.666667 -0.666667 -0.333333,
                                                            0.666667 -0.666667 -0.333333,
                                                            0.666667 -0.666667 0.333333,
                                                           -0.666667 -0.666667 0.333333 ]
                                          }
                 normalPerVertex FALSE
                 solid FALSE
                 creaseAngle 0.5
               coordIndex [ 0, 1, 2, -1, 
                                      0, 2, 3, -1,
                                      4, 1, 2, -1, 
                                      3, 4, 2, -1 ]
                  normalIndex [ 0, 1, 2, 3 ]
   }
}

  1. point[...] - The 3D coordinates of the triangles you create.
  2. vector[...] - The triangle normals.
  3. coordIndex[...] - Indexes into the 'point' array defining a polygon. Each polygon end with a -1 index (this allows facets which are not just triangles, but does not concern us).
  4. normalIndex[...] - Indexes into the 'vector' array. The normal at entry i is for the triangle i'th triangle.
To create your own VRML models from image data you have to create a similar file with the relevant data in these four arrays.

To test your program start by running it on the above data set and see that you get a similar result. The file we provide here is similar to the above example but contains more data at the location of each pixel which is below the iso-value (150) we placed a gray sphere and at the locations of pixels above the iso-value red spheres. This approach can help you test your programs on the 15 basic cases.

Two important issues are: (a) do not create multiple appearances of the same vertex, originating from neighboring cubes, and (b) your implementation should be as time-efficient, as possible.

Technical Issues

  1. To view the image data we supply, proceed as follows: CtImages are not in the range [0,255] so you need to use a program to convert them. The program inputs a serialized Vector of CtImages and writes them to disk in viewable format.
  2. Two input files are available for you:
  3. To view the resulting VRML files, you need a VRML viewer. Two viewers that work well are cortona from ParallelGraphics which is available here, or blaxxun Contact from blaxxun interactive which is available here.
  4. Create a jar file containing the following files: MarchingCubes.java, README.
  5. Your README file should contain your identification info (login, name, student i.d.) and any relevant information about running your program.
  6. Send the jar file to yaronber@cs.huji.ac.il.
  7. If you are interested in VRML and other 3D technologies for the web, see site.
  8. Note: For basic image manipulation in java, see the java tutorial. Advanced image manipulation techniques in java can be found at java advanced imaging api.