CS 284: CAGD
Lecture #14 -- Wed 10/14, 2009.

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

Warm-up:
What data structure do you need
for diadic triangle subdivision?

-- Discuss this with your neighbors.

Preparation: Interpolatory Root-3 Subdivision by Labsik and Greiner

Paper Discussion:

What are the key ideas ?
Some specific facts you should have gleaned from this paper:

What is the formula for placing the new face vertex ?
How many vertices are involved in computing the new point ?

in the regular case ?
in the irregular cases ?

Treatment of boundary edges ?

Is there anything of relevance to your current assignment ?

Topic: Subdivision Data Structures (cont.)

Tailored to 2-manifolds. Goals: efficiency, robustness.
(The goal is to take a look "under the hood" to find out what it takes to make mesh representations and subdivision algorithms work)

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.

A lean triangle hierarchy: just enough to do the dyadic triangle subdivision for your homework

-- 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 genus-4 shape into your data structure and onto a display

-- Design the geometry of ONE fundamental domain, 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.
-- 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 different 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).

Fancy texturing on arbitrary surfaces (next)

Craig Kaplan posed the question nicely...
and also gave nice answers (image), (SIGGRAPH'07 sketch).
Useful in this context: "Globally Smooth Parametrizations..."

Paper Presentations start on Monday with Alexei Baboulevitch

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.

Reading Assignments:

Read: "Semiregular patterns on surfaces" by Craig S. Kaplan, SIGGRAPH'07 sketch

Study: SS'98: Subdivision Surfaces in Character Animation (Sharp Features)
As you study the paper, try to find the answers the following questions:

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 ?

New Homework Assignments:

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

Use the data structure discussed in class.
Assume that you start from a complete, hierarchically flat mesh (you may get this out of SLIDE; save as SIF).
Test your program on your designs of a smooth genus-4 surface.
(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 MON, Oct. 19, have the whole thing running; send me a brief description of your encoding scheme and your data structures.
If you get far enough, send me also an image of your genus-4 shape after a couple of subdivisions.

COURSE PROJECTS:
Before MON, Oct. 19, e-mail me a couple of ideas (a few sentences) of what you would like to do.
By MON, Oct. 26, the final more detailed, written proposal will be due.
On MON, Nov. 2, you will make a formal 5-minute presentation in class.

Previous CS284 projects

Paper Presentation Assignments (WITH A TENTATIVE ORDERING OF PRESENTATION SEQUENCE)