Ming's
Note

**Some experiments on Discrete Harmonic
Map**

Discrete Harmonic Map (DHM) [1] parameterizes
disk-like surfaces by minimizing the Dirichlet energy of the (piece-wise
linear) mapping functions. It is *super*
easy to implement (if you are familiar with cotangent-weight Laplacian and have
a linear solver at hand, it should take no more than a few hours) and generally
gives good results. If you never heard about it, Misha's class note [2] might
be helpful.

Below are some fun, mini projects I have done with
DHM. The ideas were not that interesting for serious publications, so I just
wanted to post some results here. If you have any decent thoughts about how to
extend them, let me know and let's see if we can figure something out together.

**Mesh
segmentation**

When I first looked at the results produced from many
conformal/harmonic parameterization techniques, one thing that was
eye-catching, especially in articulated models, was that stretching and
contraction phenomena seemed pretty *part-aware*.
Individual mesh components tend to crowd into individual regions within which
area distortion varies smoothly. For example, let's cut open the Armadillo model
and parameterize it by DHM:

Pay attention to those red/green ellipses that mark
joints. If there is a function (defined on the parameter domain) describing
area distortion, I will expect it changes quickly around those joints.

This made me wonder: can I leverage this observation
to segment meshes?

So I proceeded to do the following. After computing
DHM, I performed a naïve Gaussian Mixture Model fitting by EM on vertices,
weighted by their associated surface area, in the parameter domain. Then I
grouped those insignificant clusters (# vertices < some threshold) into a
single one. And finally, I used eventual clusters to assign membership to
patches on the input mesh.

As a result, I got something like below, which was not
so bad:

If we want, we can continue to (hierarchically)
cluster points in those obtained clusters. It looked like this:

or this:

Note that I did *not*
perform any boundary optimization here. To make boundaries better aligned local
features, one can consider the graph-cut optimization scheme described in the
state-of-the-art approach of Shape Diameter Function [3].

**Some Remarks**

Obviously, there are a couple of issues in our
proposal. Apart from the need of parameter tweaking in cluster analysis, the
biggest concern is how to generate the initial convex-boundary properly (as
required by DHM to guarantee a one-to-one map). And I don't have a good answer
for that (except the manual method).

There was a time I was talking to Patricio about this general idea of
leveraging metric contraction/expansion in parameterization. I showed him the
result and he was interested in it. After discussions, we agreed then that the
problem can be made more tractable if we focus on genus-0 closed surfaces. In
that case, we can try to find a canonical *spherical
parameterization* (no cutting-open thing whatsoever anymore) and work on the
spherical domain instead.

This thought of spherical parameterization turned out
to be quite inspiring. Let's assume we are given the so-called density-map (yeah..we
kind of liked this name for some reason) function F:S^2->R
describing area change after parameterization. One can hope to make such F invariant
to translation, rotation, and even (quasi-)isometric deformation of
(articulated) models. This would be great if we want to extract some intrinsic
properties! Having that in mind, Patricio proposed several interesting ideas of
applications beyond mesh segmentation. In particular, he suggested *symmetry detection* and *shape matching*. Since we are living in
S^2 now, one immediately obvious way to do so is spherical harmonics analysis
(See [4] and [5]), though other techniques are possible too.

(To be continued. . .)

**Real-time
Parameterization Editing/Tweaking**

(To appear)

[1] M. Eck, T. D. DeRose, T.
Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. *Multiresolution analysis of arbitrary meshes*.
In Proceedings of SIGGRAPH 1995, pages 173-182.

[2] http://www.cs.jhu.edu/~misha/Fall09/6-harmonic.pdf

[3] SHAPIRA, L., SHAMIR, A.,
AND COHEN-OR, D. 2008. *Consistent
mesh partitioning and skeletonisation using the shape diameter function*.
Visual Computer. 24, 4, 249-259