Advanced Graphics

Dr Neil Dodgson, University of Cambridge Computer Laboratory
Part II course, 1998


Lecture 3 Index
...back to lecture 2
Part A: Constructive Solid Geometry
Part B: Implicit surfaces, voxels and marching cubes
on to lecture 4...

3B) 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 does this difference have on the voxel data? What effect does it have on the marching cubes algorithm?
  5. Consider Lorenson and Cline, Section 6. This research was done about twelve 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).


Lecture 3 Index
...back to lecture 2
Part A: Constructive Solid Geometry
Part B: Implicit surfaces, voxels and marching cubes
on to lecture 4...


Neil Dodgson | Advanced Graphics | Computer Laboratory

Source file: l3b.html
Page last updated on Tue Sep 8 16:01:42 BST 1998
by Neil Dodgson (nad@cl.cam.ac.uk)