CS 284: CAGD 
Lecture #14 -- Tue 10/09, 2012.

PREVIOUS < - - - - > CS 284 HOME < - - - - > CURRENT < - - - - > NEXT

Preparation: Marching Cubes  and   Structure Preserving CAD Model Repair.

Warm-up Questions:

What representations do you know for describing the shape of a physical object ?

How do you convert these representations into one another ?

How does this apply to today's papers ?

Discuss these questions with your neighbors.

Paper Presentations:  

Soham and Brandon discussing:

Lorensen and Klein: "Marching Cubes: A High-Resolution 3D Surface Construction Algorithm", SIGGRAPH 1987

WHAT: Converts an octree/voxel representation into a relatively smooth triangulated B-Rep.
WHY: Easier interpretation of medical scans from CT, MRI, SPECT, Ultrasound ...
HOW: For each leaf-node voxel through which the surface passes, construct one or more triangles
               that approximate the most likely shape of the surface in that voxel.
           Determine the most likely position where a surface may cross one of the edges of the voxel
               using linear interpolation between voxel corners.
           Also calculate the most likely normalized surface normal for each surface vertex constructed
               by interpolating the gradient values at the sample points.
How are these gradients calculated?
What can be done to enhance the efficiency of the algorithm?
What can be done to enhance the functionality of the algorithm?
What do you make of the results?

Test-questions:

In what form is the original data coming in ?

How many different voxel vertex-occupancy patterns are there,
       if we only exclude the redundancies due to rotations and mirroring ?

Under what circumstances will a very large planar face, positioned obliquely in 3D space,
       be recovered as a perfectly flat collection of facets by the marching-cube algorithm ?

What are the pro's and con's of using marching  TETRAHEDRA  instead of  CUBES ?


A nice Tutorial:  -- algorithm


Laura and Eric discussing: 

Bischoff and Kobbelt: "Structure Preserving CAD Model Repair", Eurographics 2005

Main benefit:

Pros and Cons of volumetric conversion:

Key steps in the algorithm:

Test-questions:

Why do they double up (mirror) all patches ?

What is an "ambiguous" vertex ?

What happens if the input patches have self-intersections ?
What happens if the input mesh is a hierarchically flat triangle mesh ?
What happens if the input mesh describes an open cylinder, a Moebius band, or a Klein bottle ?
   (How is the "inside" determined ?).


A Current Modeling Research Problem

How to smoothly undo a Klein bottle mouth of the "Inverted Double-Sock" type into a twisted tube with a figure-8 profile?

Some pictures to explain the problem ...

Keep this problem in mind next week when we discuss surface "optimization" (deformation while minimizing some functional).

Assignments for Thu. Oct. 11, 2012:

Read: SB'10:  An intuitive explanation of third-order surface behavior.

Programming:  Continue implementation of your data structure for dyadic triangle subdivision.

Enter your own coarse mug design and subject it to a smoothing subdivision process (about 3 levels is sufficient!).
E-mail me a picture of the result.

Continue thinking about possible course projects.

PREVIOUS < - - - - > CS 284 HOME < - - - - > CURRENT < - - - - > NEXT
Page Editor: Carlo H. Séquin