The goal of this assigment is to introduce you to mesh representation, curve/surface smoothing, and modeling. You will be creating a basic interactive modeling program for generating smooth surfaces that allows a user to drag vertices of a coarse control mesh in 3D while displaying an associated smooth surface. You will be asked to implement aspects of both the user interface and the subdivision algorithm, and finally use your program to construct several models.
Specifically, you will write a program that reads a set of triangle from a .ray file, builds a "control" mesh from these triangles (shown in green above), and displays it in a window using OpenGL. As the program executes, a user can subdivide the control mesh (each press of the `S' key subdivides one level further) to produce a smooth subdivision surface for display (shown in gray above). The user may also drag vertices of the control mesh with the mouse while the corresponding finest level of the subdivision surface is updated continuously in the display. To create the smooth surface, we will be implementing the Loop subdivision scheme.
You will construct the topology of the subdivided meshes only once, and after that update the geometry of these surfaces using the subdivision rules. At the highest level, your program will juggle the following meshes:
- level 0: coarse mesh (displayed and the user is allowed to move vertices)
- level 1: intermediate mesh (not displayed)
- level 2: intermediate mesh (not displayed)
- ...
- level n: final fine mesh (displayed)
Much work has been done on the properties and applications of subdivision surfaces, and below are some references for the curious. Everything you need to know to implement subdivision should be in the course notes, however.
- E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10(6):350-355, 1978.
- Smooth Subdivision Surfaces Based on Triangles, Charles Teorell Loop, Department of Mathematics, University of Utah, August 1987. (15mb pdf, download - don't view in browser).
- SIGGRAPH 2000 Course Notes: Subdivision for Modeling and Animation. (30mb pdf, download - don't view in browser; Relevant pages are 47-50, 70.)
Implement an interactive subdivision surface modeling program, which reads a model file, subdivides it, displays it, lets you interactively move the original mesh around while updating the subdivided surface, and outputs the final coarse and fine mesh. The inputs to the program will be a coarse mesh in the .ray file format (vertices and triangles only). The output of the program will also be a .ray file.
The assignment is worth 20 points. The following is a list of features that you may implement. The number in parentheses corresponds to how many points it is worth. Options in bold are mandatory.
User interface:
- (1) finer control: Let the user turn the subdivided mesh into the coarse mesh. (see the examples page)
- (2) normal dragging: Let the user drag control points of the original control mesh. Mouse movements should translate into movements in the normal direction of the surface.
- (1) orthogonal dragging: Let the user drag control points of the original control mesh. Mouse movements should translate into movements orthogonal to the viewing direction.
- (4) neighborhood dragging: Let the user move a whole neighborhood of control points around with one mouse stroke. The user should select a single control point, and its vertex neighborhood should move with the mouse. The neighbors should move less than the control point selected.
- (1) detail elision: Draw mesh with intermediate detail while it is being translated, rotated, scaled during interactive viewing.
- (2) multiple vertex dragging: Allow selection of multiple vertices (e.g., by clicking with shift down) and move them all with the same dragging motion.
- (3) creases: Allow a method for interactively specifying creases in the model.
- (?) Some other user interface enhancement that you can argue is useful in creating a model.
Mesh subdivision:
- (9) subdivision: Implement the Loop subdivision algorithm. Assume the original mesh contains only triangles. You will need separate rules for boundary and interior nodes. When a user moves a vertex, it's ok to recompute the entire subdivision surface at each level, but you should only compute the topology once. Verify that your subdivision scheme works on the included models. For the plane, cylinders, pawn, torus, moebius strip, and vase, move the control mesh noticably, subdivide it two or three times, and output the finest resolution mesh as a new .ray file (see the examples page).
- (1) rules: Change the subdivision rules and show what effect this has on the fine mesh.
- (1) smooth shading: Calculate normals at all vertex points and feed this information into OpenGL when drawing the smooth mesh.
- (3) finite support: When a vertex moves, only recompute the vertices that need to be recomputed. This should allow you to move vertices of large base meshes and still have interactive updates.
- (2) textures: Instead of just subdividing vertex positions, subdivide texture coordinates as well. Assume the input file provides texture coordinates (one texture map for the entire mesh) for each vertex. Display the subdivided textured mesh.
- (4+) multiresolution: Let the user move vertices at all levels of the subdivision hierarchy. At each level, store offsets from the previous level in a local frame. This is difficult.
Create some models:
- (2) Original model: Create a new coarse mesh with your program and subdivide it to produce an interesting object, such as a fish, mountain terrain, machine part, human, horse, bunny, rabbit, squirrel, or an impression of a famous roman statue.
- (2) Original model with Blender: Download blender and create an interesting model with it.
- (?) Impress us with something beautiful...
You should try to create the coarse model yourself, using whatever tools you want. For each of model, you need to submit a coarse mesh that, when subdivided without modification, results in your final model.
By implementing all the required features, you get 14 points. There are several ways to get more points:
- Implement optional features (as listed above).
- (1) include a one page-section in your writeup commenting on your interactive modeling experience. Here are some ideas: What features would you need to create a complicated model? Which of these features fit inside the subdivision framework? How did you create the initial coarse mesh? How could you use subdivision for animation? (Around a page, double spaced, size 12 font, 1 inch margins.)
- (1) Submit a picture of a model for the art contest.
- (2) Win the art contest.
- (?) Implement something original.
It is possible to get more than 20 points. However, after 20 points, each point is divided by 2, and after 22 points, each point is divided by 4.
You should use the code available here (3.tar.gz, 3.zip) as a starting point.
The code we give you is able to load a .ray file and display it. It also sets up basic menus (click the right mouse button) and several keyboard shortcuts. This is just a starting point for the project, so feel free to change anything you want, but you will mainly need to modify the following files:
main.cpp: manages meshes and sets up user interface framework.Face.[cpp/h]: class representing faces.Mesh.[cpp/h]: Mesh class, containing Vertices and Faces.Vertex.[cpp/h]: class representing vertices.There are several support classes which you shouldn't need to touch:
ArcBall.[cpp/h]: Arcball rotation user interface.Quaternion.[cpp/h]: Quaternion support class. Quaternions are used for rotations in the arcball user interface.Color.[cpp/h]: Color support class.Vector.[h]: 3D vector support class.Misc.h: Basic routines.
You should submit one archive (zip or tar file) containing:
- the complete source code with a makefile or Visual C project file;
- any base meshes you used, and everything you had to use to create models;
- a writeup.
The writeup should be a HTML document called assignment3.html which may include other documents or pictures. It should be brief, describing what you have implemented, and how you created your models. Note if your writeup is very large you can just instead include a pointer to it.
Make sure the code compiles under Visual C++ or Linux.
Always remember the late policy and the collaboration policy.
- The input is given as a "triangle soup". Can I compute the actual topology by brute force, in O(n2) time?
No, that's too inefficient. It isn't hard to come up with an implementation that takes O(n log n) (where n is the input size). You may need to do more than one pass over the input data. The topology can even be built in linear time, though an extra log factor is acceptable.- How can I get Blender to export a file in some text-based format? The
.blendfile is binary.
Use "Save as videoscape".
