Mesh - Part C

Shortcut to PartA / PartB / CS6491 project page

Abstract

After a user create a mesh using the tool made in part A, and after subdivision performed in part B, what we get is a jaggy mesh. As what we done 2D polyloop smooth in project1, we do a 3D version here: Mesh smoothing. The goal is to smooth the mesh while conserve the volume of mesh at the same time.

Links :

PartC:
WriteUp (forward and backward trick for bi-laplace)
Movie1 2D operations, smooth border and displace interior
                 vertices (4MB MP4/ Use quicktime player)
Movie2 3D operations, laplace, bi-laplace smoothing
                 (3MB MP4/ Use quicktime player)
Source code (in C++)
Excutable (interface_description)
Supporting paper (see below, I implement ALGORITHM 4 on page 11)

Other papers surveyed:
1. Xinguo Liu , Hujun Bao , Heung-Yeung Shum , Qunsheng Peng, A novel volume constrained smoothing method for meshes, Graphical Models, v.64 n.3/4, p.169-182, May/July 2002
2. Klaus Hildebrandt, Konrad Polthier and Max Wardetzky, Smooth Feature Lines on Surface Meshesin: Symposium on Geometry Processing 2005, M.
3. Shontz, Suzanne M. and Stephen A. Vavasis, A mesh wrapping algorithm based on weighted laplacian smoothing Proceedings, 12th International Meshing Roundtable, Sandia National Laboratories, pp.147-158, Sept. 2003

Goal

Break-down according to the P2 instruction

Implement a 2D relaxation scheme that uses your area-preserving smoothing (Project 1) for the border loops and uses a laplace relaxation for the interior vertices (each interior vertex moves a bit towards the average of its neighbors).
Apply it a few times after each local subdivision (not too many times, so as to ensure that the local concentration of the vertices is somewhat preserved but made more regular). Show the results in 2D.
Modify the smoothing algorithm to work in 3D by doing a 3D version of the bi-laplace smoothing (alternating forth and back smoothing adjustments).
Modify the above algorithm to first record the smoothing displacement vectors for all the vertices and then to apply them one at a time in the vicinity of the vertex selected by the user to deposit material. As you apply the smoothing, one vertex at a time, record the resulting volume change as the sum of the signed volumes of all swept tetrahedra. Then, distribute these volume changes as a low pass filter by averaging with neighbors.
Now, invent a volume recovery pass that will adjust each vertex to recover the volume change assigned to it. The vertex will move along its normal by a displacement that produces the correct swept volume. The research part here is to invent an order for moving the vertices that does not destroy the smoothing. (It may be necessary to move a vertex more than once in this volume recovery pass, recovering a fraction of its volume each time.)	see below
Explain your strategy, show results, and comment on what is good and what is bad about your approach. Suggest variations that you did not have the time to explore.	see below

I implement to have the order of area smoothing to be simply the same as it in the G-table.

Moreover, instead of inventing one algorithm other than this myself, I tried to implement to method proposed in the following paper, the method is quite different from our "two-step" scheme. It basically, take only one step, but moveing the vertex (actually two verices which share a edge at the same time) in an optimal direction which achieves smoothing but doesn't change the volume enclosed. See page 11, Algorithm 4. The result is good.

Andrew Kuprat and Ahmed Khamayseh, ``Volume Conserving Smoothing for Piecewise Linear Curves, Surfaces, and Triple Lines'', Journal of Computational Physics, vol. 172, pp. 99-118 (2001) [PDF]

(original mesh)

(top left: laplacian, top right: bi-laplacian,
bottom left, volume preserving, bottom right edge relaxtion volume preserving)

Some picture from the original paper, using the algorithm I implemented, ie. edge relaxtion volume preserving.

Last update: 2005-10-18