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.

[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