CS 284: CAGD
Lecture #13 -- Thu 10/04, 2012.

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

Preparation: Subdivision Surfaces in Character Animation (Sharp Features)

Warm-up:
What is a minimal mesh data structure
needed for dyadic triangle subdivision?
-- Discuss this with your neighbors.

Mesh Data Structures for Subdivision

Tailored to 2-manifolds. Goals: efficiency, robustness.
Last time we discussed two generice mesh data structures:

Winged-edge data structure for orientable 2-manifolds (Baumgart)
-- describes a non-hierarchical boundary representation.
-- every edge connects to exactly two polygons, one on each side.

Half-edge data structure (e.g. http://www.flipcode.com/articles/article_halfedge.shtml)
-- a lean and regular variant for 2-manifolds.
-- can use fixed-size data structures, even if valences and number of sides in meshes are not all the same!
-- in the triangle subdivision process, every half-edge gets subdivided, and new pairs of half-edges get introduced for the new central triangle.

Now we focus on the special case of a lean triangle hierarchy for dyadic triangle subdivision:

-- Probably best to keep all subsequent generations of the subdivision process side by side.
-- Vertex list, carrying the geometrical coordinates.
-- Triangle list (referencing the vertex list); each triangle also carries: surface pointer (material,color), 3 pairs of texture coordinates.
-- Connectivity information to find all vertices needed for the smoothing or interpolation step.
(Do you need a full half-edge data structure -- or can you get away with less, perhaps exploiting regularity?)

Indexing Schemes for Regular Arrays

Within each triangle, we encounter a completely regular array of triangles.
One can use a properly designed indexing scheme to find vertices in a local neighbor hood.
-- 1D: Use a binary encoding of the address as an index for the vertex; or use a binary tree directly as the adressing structure.
-- 2D square array: Combine two of the above schemes; or use a quad tree to find the 4 next-generation quads in each quad.
-- Triangle array: Can be seen as just one half (below the diagonal) of a square array;
or use a special quad tree to find the 4 next-generation triangles in each triangle.

How to get your mug design into your data structure and onto a display:

-- Design the geometry for each unique geometrical domain (e.g. half a handle; one sector of the bowl of your mug),
    then replicate it using the symmetry of your design, merge the coinciding vertices into one.
-- In SLIDE you can save your design as SIF, which will then produce hierarchically flat vertex lists and face lists;
    cut and paste those into a textfile that you can easily parse.
    (Your own CAD environment should have similar capabilities).
-- At the top level, you should build a winged-edge or half-edge data structure for your basic control mesh.
-- Within each base triangles you may do something more efficient that exploits the regularity of the subdivision process (see above).

-- After a suitable number of subdivision, you should have a hierarchically flat triangle file, which you would like to display.
-- Choose your preferred graphics/CAD/video-game... environment and write out your triangle list in a compatible format.
-- If you choose to use SLIDE, you would have to write out your vertex and face lists in the mesh-format
    (i.e., a list of "vertex" constructs followed by a list of "facets" constructs.)
-- Another option is to download MESHLAB; in this case I would recommend that you write out your shape in the OBJ format.
-- Ideally you work in an environment where you can make OpenGL or Java_3D calls and display your mesh interactively.

I keep this deliberately open ended, so that you can build something that may be useful to you in your own study/research environment.
I want you to build something that really works. (Deadline extentions can be negotiated).

Discussion: Subdivision Surfaces in Character Animation (Sharp Features)

What subdivision scheme are they using ?
What are the key additions to the basic scheme that they have made ?
Why do they prefer quadrilaterals ?
What is the basic approach to creating semi-sharp edges ?
What is the underlying model for cloth simulation ?
How is excessive wrinkling of the cloth avoided ?
What are virtual threads ? -- and what is their purpose ?
What is the data structure to make collision detection efficient ?
How is it made possible to apply texture maps and procedural shaders ?
What was one of the general implementation requirements for the Pixar production environment ?

Guidelines for Paper Presentations

starting on Tuesday with Soham and Brandon discussing: Marching Cubes
and with Laura and Eric discussing: Structure Preserving CAD Model Repair.

The whole, uninterrupted presentation for one paper should last between 20 and 25 minutes.

there may be interruptions due to questions, but "the clock will be stopped.".

Everybody in the class should read the papers carefully before the day that they are presented in class.
The class should be prepared to help the presenters with constructive and insightful questions and comments.
The presenters should be prepared to answer such questions.
The presentations will be judged for:

Organization of the material
Clarity of explanations
Quality of visual materials
Forcefulness and enthusiasm of oral presentation
(This will account for about 20% of your course grade)

For some papers I will ask everybody to answer some questions on-line about the paper before coming to class.
I may start a class with a short pop quiz about the paper(s) for that day.

Assignments for Tue. Oct. 9, 2012:

Read: Marching Cubes

Read: Structure Preserving CAD Model Repair

Programming: Implement a simple data structure for dyadic triangle subdivision, useful for either the Loop or Zorin scheme.

Use your preferred programming environment; start from the data structure discussed in class.
Your input or starting file should be a closed, hierarchically flat mesh (e.g. an OBJ file).
Test your program on a simple cube surface (12 triangles) and on your "mug-file".
(In the next phase of the assignment we will add texturing to it).
For display use what is most convenient for you (open GL, Java 3D, SLIDE?)

By Tue, Oct. 9, you should have the mesh structure running -- at least with trivial mid-edge subdivision (without smoothing).
E-mail me a brief description of your encoding scheme and your data structures, with a picture of your cube subdivision.
If you get far enough, send me also an image of your mug shape after a couple of subdivisions.

Continue thinking about possible course projects.