Advanced Graphics Study Guide

Advanced Graphics, Dr Neil Dodgson, University of Cambridge Computer Laboratory
Part II course, 2000


Part 4: Other 3D modelling mechanisms
A: Generative models
B: Converting swept objects to polygons
C: Constructive Solid Geometry
D: Implicit surfaces, voxels and marching cubes
E: Subdivision surfaces
...back to part 3 | on to part 5...

4D) Implicit surfaces, voxels and the marching cubes algorithm

Implicit surfaces

These are covered in Brian Wyvill's article "A Computer Animation Tutorial" in Computer Graphics Techniques: Theory and Practice, Rogers and Earnshaw (editors), Springer-Verlag, 1990, ISBN 0-387-97237-4.

Voxels and the marching cubes algorithm

Voxels are the three dimensional analogue of pixels. Rather than storing a colour in a voxel, you will generally store a density value. Voxels and the marching cubes algorithm are both covered in Lorenson and Cline's 1987 SIGGRAPH paper "Marching cubes: a high resolution 3D surface construction algorithm", Proc SIGGRAPH 87, pages 163-169.

Exercises
  1. Give a definition of an implicit surface and give three examples of where such things might be useful.
  2. The marching cubes algorithm, as it applies to implicit surfaces, is described in the Wyvill article; while Lorenson and Cline concentrate on the algorithm as applied to voxel data. It is useful that the same algorithm works for both types of data. Explain how voxel data can be thought of a defining an implicit surface (or surfaces). Explain, conversely, how the Wyvill algorithm can be thought of as converting implicit surface data into voxel data before producing the final surface.
  3. Following Section 4 of Lorenson and Cline's paper, sketch an implementation of the two-dimensional `marching squares' algorithm -- where you generate line segments in 2D rather than triangles in 3D. An appliation of this algorithm would be the drawing of isobars on a weather map, given pressure values at a regular (2D) grid of points.
  4. Medical data is captured in slices. Each slice is a 2D image of density data. The distance between slices may be different to the distance between the pixels within a slice (for example, see Lorenson and Cline, Section 7.1, p. 167). What effect, if any, does this difference have on the voxel data? What effect, if any, does it have on the marching cubes algorithm?
  5. Consider Lorenson and Cline, Section 6. This research was done about fourteen years ago. Given your knowledge of processor performance, what differences in performance would you expect to see between then and now?
  6. Lorenson and Cline is an example of a graphics research paper. Critically evaluate Lorenson and Cline. How good is this piece of research?
  7. Research papers at the SIGGRAPH conference are limited in their length. Evaluate Lorenson and Cline in terms of the following questions. What has been left out that would have been useful? What has been included that could have been left out? Where could the explanation have been better? Are any of the figures extraneous? Where would an extra figure have been helpful? List any grammatical or spelling errors (there is at least one of each).


Part 4: Other 3D modelling mechanisms
A: Generative models
B: Converting swept objects to polygons
C: Constructive Solid Geometry
D: Implicit surfaces, voxels and marching cubes
E: Subdivision surfaces
...back to part 3 | on to part 5...


Neil Dodgson | Advanced Graphics | Computer Laboratory

Source file: p4d.html
Page last updated on Thu Sep 14 16:58:09 BST 2000
by Neil Dodgson (nad@cl.cam.ac.uk)