Assigned: Thursday, February 9
Due: Thursday, March 2 by 12:00 noon
The purpose of this assignment is to implement a system for parameterizing meshes by constructing a mapping into the plane.
[15 points] Mesh Representation
Build some code to read in a mesh file and construct an appropriate data
structure to represent the mesh internally.
[25 points] Linear Parameterization
Solve the basic constrained Laplacian linear system (as outlined by
Floater and Desbrun et al) and thus flatten manifolds with boundary
into the plane. Specifically, your system should accept an input mesh,
map its boundary loop to the unit circle in the plane, and automatically
compute the embedding of the remainder of the surface. To begin with,
solve the system using uniform weights (i.e., the weight of each edge
around vertex i will be 1/deg[i]).
In addition to simply drawing the input surface, your system should also be able to:
Draw the mesh in the 2-D parametric domain.
Load an arbitrary texture (PNG is the preferred format) and map it onto the mesh.
[25 points] Better Weighting Schemes
Uniform weights fundamentally ignore the actual geometry of the surface
being flattened. We will get much better parameterizations by using
shape-sensitive weights. You should implement the following three
schemes:
Discrete Harmonic weights (DCP) — Desbrun et al, Eurographics 2002
Discrete Authalic weights (DAP) — Desbrun et al, Eurographics 2002
Mean Value weights — Floater, CAGD 2003 (Eq 2.1)
[25 points] Natural Boundaries
Enforcing the requirement that the boundary of the parametric domain can
result in excessively high distortion. It’s preferrable to allow the
boundary to find a more “natural” shape (keeping in mind that we can no
longer guarantee validity). Implement the natural boundary
formulation proposed by Desbrun et al.
[10 points] Quality Code
Your code should be efficient and well-written. It should be easy to
follow and demonstrate quality design.
You’ll probably want to browse through our collection of links, particularly the Numerical Libraries section.
My collection of sample models includes some selected manifolds-with-boundary suitable for parameterization.
If you choose to build a mesh data structure using a halfedge primitive, you might be interested in looking at the sample halfedge code that I’ve written.
You really want to use a sparse matrix solver for this project. I recommend either UMFPACK, TAUCS, or SuperLU.
You can, of course, ignore my advice and use a dense solver instead. If you’re serious about performance, you’d use LAPACK+BLAS. If you want an easy to use C++ interface, you might try TNT. There’s also newmat, but I should warn you that I’ve encountered numerical problems with newmat on my Powerbook (but not on Intel machines) when solving the DCP linear system.