Overview

In this assignment you will create a simple mesh processing program. The operations that you implement will mostly be filters that take an input mesh, process the mesh, and produce an output mesh.

Getting Started

You should use the following skeleton code (COS426_assignment2.zip) as a starting point for your assignment. We provide you with several files, but you should mainly change R3Mesh.cpp.

• meshpro.cpp: Parses the command line arguments, and calls the appropriate mesh processing functions.
• meshview.cpp: Interactive program for viewing meshes.
• R3Mesh.[cpp,h]: Defines the mesh data structure and implements the mesh processing operations.
• R2: code to support operations on 2D points, vectors, lines, segments, and images
• R3: code to support operations on 3D points, vectors, lines, segments, and planes
• jpeg: code to read/write JPEG files
• meshpro.[vcproj/sln]: Project file for Visual Studio .NET 2005 on Windows.
• Makefile: Make file for Mac OS X.

After you copy the provided files to your directory, the first thing to do is compile the program. If you are developing on a Windows machine and have Visual Studio .NET 2005 installed, use the provided project files to build the program. If you are developing on a Mac OS X machine, type make in the assignment2 directory. In either case, two executables will be created: meshpro and meshview (or meshpro.exe and meshview.exe). meshpro is the program that processes mesh (just like imgpro from assignment #1), while meshview provides a way for you to visualize meshes interactively.

Aside: Visual Studio bug: On multiprocessor machines, Visual Studio will lock object files while building in a way that causes the build to fail. To fix this, use Tools -> Options -> Projects and Solutions -> Build and Run and set the maximum number of parallel project builds to 1.

The skeleton R3Mesh class is able to read meshes in three simple mesh file formats. The first is the COS426 file format, which is indicated by the .ray file extention. This format was created to provide the features required by this course -- it will be extended to handle materials, lights, etc. in Assignments 3 and 4. The others are the Object File Format (.off) and the Wavefront file format (.obj), which are commonly used for interchange between mesh processing programs. We provide several sample meshes that you can use to test your program. However, you are not limited to these files. You should be able to find .off and .obj files on the web -- in particular, there is a large repository of 3D meshes in .off format in the Princeton Shape Benchmark.

Optionally, you can also try the Google 3D Warehouse, which contains SketchUp models, and use an OFF exporter plugin from SketchUp (place the script in the PlugIns directory of Sketchup, then use Plugins -> Export OFF in the SketchUp application). This allows you to obtain more OFF files for your mesh processing needs. We don't provide debugging support for the Sketchup approach, however, so try it at your own risk!

How the Program Works

The user interface for this assignment was kept as simple as possible, so you can concentrate on the mesh processing issues. The program runs on the command line. It reads a mesh from a file (the first program argument) and writes a mesh to a file (the second program argument). In between, it processes the mesh using the filters specified by subsequent command line arguments. For example, to scale a mesh in.ray by a factor of 1.1, and save the result in the mesh out.ray, you would type:

% meshpro in.ray out.ray -scale 1.1 1.1 1.1

For each available mesh filter there may be one or more optional parameters -- e.g., -scale takes three factors (sx sy sz). To see the complete list of filters and their parameters, type:

% meshpro -help

If you specify more than one filter on the command line, they are applied in the order that they are found. For example,

% meshpro in.ray out.ray -scale 0.8 0.8 0.8 -rotate 0.5 0 0 0 0 0 1

would first scale the mesh by 0.8 in all three dimensions and then rotate the mesh by 0.5 radians around a line through the point (0,0,0) and with direction vector (0,0,1) -- i.e., the z-axis. Of course, you are welcome to create your own filters and add program arguments for them by editing meshpro.cpp. However, please do not change the program arguments for the filters already provided.

How to use meshview

Use meshview filename.ext to open a mesh. Use F to toggle drawing faces, E to toggle drawing edges, V to toggle vertices, I to toggle vertex IDs, S to save a screenshot. You can display the position on a mesh (and the active face index) under the mouse cursor by moving the mouse over the mesh and pressing spacebar.

What You Have to Do

The assignment is worth 20 points. The following is a list of features that you may implement (listed roughly from easiest to hardest within each group). The number in front of the feature corresponds to how many points the feature is worth. The features in bold face are required. The other ones are optional. Refer to the examples web page to see images of inputs and outputs for several of these filters.

• Warps
  • (1) Random noise: Add noise of a random amount and direction to the position of every vertex.
  • (1) Translate: Translate the mesh by adding a vector (dx,dy,dz) to every vertex.
  • (1) Scale: Scale the mesh by increasing the distance from every vertex to the origin by a factor given for each dimension (sx, sy, sz).
  • (1) Rotate: Rotate the mesh counter-clockwise by an angle (in radians) around a line specified by a point (x,y,z) and a direction vector (dx,dy,dz).
  • (1) Inflate: Move every vertex by a given offset along its normal direction (offsets can be negative). (If a mesh doesn't have per-vertex normals, you can use the "compute normals" feature later in the assignment to find the normals.)
  • (2) Fun: Warp a mesh using a non-linear mapping of your choice (examples are sine, bulge, swirl).
  • (3) Deform according to point correspondences: Warp the mesh by a deformation defined by point correspondences provided in an ascii file with six numbers on each line: x y z x' y' z'. The position of every vertex in the output mesh should be offset by a Gaussian weighted average of the offsets implied by the point correspondences (x,y,z) -> (x',y',z'). The t parameter should control the "amount" of offset, so that t = 0 gives the original mesh, t = 1 gives the deformed mesh, and other t values interpolate or extrapolate. Use a reasonable heuristic to choose sigma for the Gaussian.
• Filters
  • (2) Smooth: Smooth the mesh by moving every vertex to a position determined by a weighted average of its immediate neighbors (with weights determined by a Gaussian function of distance).
  • (2) Sharpen: Accentuate details in the mesh by moving every vertex away from the position determined by a weighted average of its neighbors (with weights determined by a Gaussian function of distance). This filter moves vertices in the direction opposite from smoothing.
  • (3) Truncate: For every vertex, create a new vertex a parameter t [0-0.5] of the way along each of its attached edges, and then "chop off" the pyramid whose base is formed by the new vertices and whose apex is the original vertex, creating a set of faces to triangulate the hole.
  • (3) Bevel: For every edge, create a new face whose vertices are t [0-1] of the way along each of its attached edges. This requires first truncating all vertices by t, creating new vertices t [0-1] of the way along each of new edges, and then "chopping off" a prism for each of the original edges, creating a pair of faces to triangulate the hole. Alternatively, you can truncate the edges of the mesh in a manner of your choosing, so long as the created bevels behave in a reasonable way where they intersect at the vertices of the original mesh.
  • (4) Bilateral smoothing: Smooth the mesh using a bilateral filter as in [Jones et al, Siggraph 2003] or [Fleishman et al., Siggraph 2003].
• Remeshing
  • (2) Subdivide faces: Replace every triangle by four new ones according to the Loop subdivision scheme. This requires creating a new vertex at the midpoint of every edge, removing the original triangles, and creating four new triangles to replace each of the original ones. An extra point will be given if the positions of all vertices are updated according to the Loop subdivision weights.
  • (2) Split long edges: Iteratively split edges longer than a given threshold. Note that every edge split produces a new vertex at the edge midpoint and replaces the two adjacent faces with four. Edges should be split repeatedly until there is none longer than the given threshold. An extra point will be given if longer edges are split first (with produces better shaped triangles).
  • (3) Vertex cluster: Simplify the mesh by clustering vertices residing in the same cell of a grid defined by the x, y, and z spacing parameter. All vertices within the same grid cell should be merged into a single vertex, that vertex should be placed at the centroid of the cluster vertices, and all edges and faces that collapse as a result of the vertex merging should be removed.
  • (4) Uniform resampling: Generate a new mesh whose vertices are evenly spaced (i.e., all edges are the same length). One way to accomplish this is to iteratively adjust vertices so that they are at the position on the surface closest to the centroid of its neighbors.
  • (4) Regular resampling: Generate a new mesh whose vertices are on regularly spaced intervals in x, y, and z. One way to accomplish this is to rasterize the interior of the mesh into a voxel grid with negative values inside and positive values outside and then compute the zero-set isosurface from the grid.
• Analysis
  • (2) Compute normals: Compute the surface normal at every vertex by taking a weighted average of the normals for the attached faces, where the weights are determined by the areas of the faces.
  • (3) Compute curvatures: Compute the minimum and maximum curvatures of the surface at every vertex using the method described in [Rusinkiewicz, 3DPVT 2004]. Store the resulting two curvatures values in the texture coordinates for every vertex.
• Geometry Construction
  • (2) Surface of revolution: Create new vertices and faces by sweeping a profile curve around an axis of revolution. The vertices representing the profile curve are provided in a mesh file (take the vertices of the mesh in order and ignore the faces). The rotation axis and rotation step size are provided in command line arguments. New vertices should be created by successively rotating the original vertices around the axis by the step size and new faces should be constructed by connecting adjacent vertices to create a surface of revolution.
  • (2) Surface sweep: Create new vertices and faces by sweeping a polygon along a curve. The vertices representing a cross-section polygon are provided in one input mesh file, and the vertices representing the sweep centerline curve are provided in a second mesh file (for both, take the vertices of the meshes in order and ignore the faces). New vertices should be created by successively translating and rotating the vertices of the cross-section polygon to match the position and orientation of vertices/edges in the centerline, and new faces should be constructed by connecting adjacent vertices created during the sweep. An extra 3 points will be awarded if your implementation avoids self-intersecting polygons in all cases.
  • (2) Fractalize: Create fractal detail by recursively subdividing every triangle of an input mesh into four (as in the Subdivide feature above) and moving every new vertex by a random offset vector (as in the Random Noise feature above) with magnitude proportional to the original edge length. Note that the output mesh may resemble a mountain if the input is planar.
  • (2) Bezier: Create a smooth mesh using cubic Bezier patches. The input file should have M*N vertices representing control points arranged in a M by N array (M and N can be inferred from the topology of the input file or read from program arguments). The output file should contain a fine triangular mesh rerpresenting the cubic Bezier surface implied by the control points. Points at regular intervals of u and v on the surface should be generated using the tensor product Bezier surface construction and connnected into triangles to form a polygonal approximation of the smooth Bezier surface.
  • (2) B-Spline: Create a smooth mesh using cubic B-Spline patches. The input file should have M*N vertices representing control points arranged in a M by N array (M and N can be inferred from the topology of the input file or read from program arguments). The output file should contain a fine triangular mesh rerpresenting the cubic B-Spline surface implied by the control points. Points at regular intervals of u and v on the surface should be generated using the tensor product B-Spline surface construction and connnected into triangles to form a polygonal approximation of the smooth B-Spline surface.
• Topological Fixup
  • (2) Fill holes: Create triangles covering the holes of a mesh by connecting vertices on the boundary of every hole. You should completely cover the hole, while doing your best to produce well-shaped triangles (e.g., by connecting closer vertices first). However, do not worry about triangles intersecting other parts of the mesh in your implementation.
  • (3) Fix cracks: Merge boundary vertices and edges within a specified distance (epsilon) of one another.
  • (4) Fix self-intersections: Insert edges at face-face intersections and discard the smaller part of the mesh "pinched" off by new edge loops. Note: this is hard.
• Boolean Operations (note: these are very hard)
  • (4) Intersect: Compute the mesh enclosing the intersection of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the exterior of the solid object implied by either of the two meshes.
  • (4) Difference: compute the mesh enclosing the difference of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the interior of the solid object implied by the second mesh.
  • (4) Union: compute the mesh enclosing the union of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the interior of the solid object implied by both of the two meshes.
  • (3) Implement any of the boolean operations by rasterizing the meshes onto two voxel grids, then using max(), min(), or subtraction elementwise to compute the boolean operation, then extract the isosurface to produce the final mesh. You cannot get more than 3 points for this section if you use the voxel approach.
• Miscellaneous
  • (2) Create a mesh from an image: Create a mesh by reading an image file, constructing vertices at (x,y,luminance), and connecting adjacent pixels into triangles. For this feature, the image is interpretted as a height field, where the luminance of each pixel provides its z-coordinate.
  • (2) Crop: Given a plane equation (a,b,c,d), crop the input mesh to the positive side of the plane. This feature requires clipping each polygon crossing the plane, and discarding any part of any face on the negative side of the plane.
  • (up to 3) Anything else: Implement any non-trivial mesh processing algorithm of your own choosing, and we will give you points according to the difficulty.

By implementing all the required features, you get 10 points. There are many ways to get more points:

• implementing the optional features listed above;
• (1) submitting one or more images for the art contest,
• (1) submitting a .mpeg or .avi movie showing images generated while animating the results of one or more filters with continuously varying parameters,
• (2) winning the art contest.

For images or movies that you submit, you also have to submit the sequence of commands used to created them, otherwise they will not be considered valid.

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. If your raw score is 19, your final score will be 19. If the raw score is 23, you'll get 21.25. For a raw score of 26, you'll get 22.

Extra credit points cannot replace the required features (bold items). Your final score will be calculated by adding 10 to the number of extra credit points you achieve, applying the above formula for diminishing returns, and then subtracting the number of required points that you missed.

What to Submit

You should submit one archive (zip file) containing:

• the complete source code required to build your project, along with your Visual Studio project file or makefile;
• the .mpeg or .avi movie for the movie feature (optional);
• the meshes for the art contest (optional); and
• a writeup.

The .zip file's name should be your Princeton OIT LDAP username.

The writeup should be a HTML document called assignment2.html which may include other documents or pictures. It should be brief, describing what you have implemented, how you created the art contest images, and instructions on how to run the fun filters you have implemented. It should also include screenshots of example output meshes for each of the filters you implemented, with the corresponding command-line. (Points will be deducted if the screenshots are not included). Finally, the writeup should list the points you think you deserve for each section, and the total, as if your assignment were correct.

NOTE: Please convert your art contest and writeup images to JPEG format before submitting them (to save space).

Should you choose to create a video, there are many options for video encoders available, however we have found that FFMPEG works well and runs on both Windows and linux. MEncoder is another option.

Always remember the late policy and the collaboration policy.

Hints

A few hints:

• Do the simplest filters first!
• There are functions to manipulate 3D geometric primitives in R3.
• Send mail to the cos426 mailing list.
• The code should compile and link as-is (make sure to try it out before adding your own code!). If you have problems linking to libjpeg, you can simply remove the -DUSE_JPEG flag from the makefile (or #undef USE_JPEG in your code) to disable JPEG support.
• If you should happen stumble upon anything that you suspect is a bug in the framework code (we're not perfect either!) please mail the preceptor as soon as possible so that it can be corrected.