In our Siggraph ’03 paper we introduced a general framework for mesh decomposition.
In this page we elaborate on some options within this general framework.
Fuzzy Clustering (section 3.3 in the paper)
In the
third phase of our decomposition algorithm, our goal is to achieve a fuzzy
clustering of the mesh. One way to achieve this is using fuzzy k-means using a
single representative. The benefit of this method is that connected components
are always guaranteed. Another benefit is that each iteration is linear in the
number of faces of the mesh and thus is very fast. The drawback of this
approach is the high dependency of the clustering on the exact position of the
representatives. An alternative use the average distance. The latter can be
done in one various ways. We describe two options below.
(1) This iterative process (fuzzy k-means) is initialized by choosing initial representatives and associating every face with one of the representatives by the minimal distance. Then, in each iteration use the results from the previous iteration to calculate the new refined fuzzy clustering. This is done by associating each face a probability to belong to each patch by using its average distance from the patch, where the patches are the clusters from the previous iteration. During the iterations the representatives are recalculated to have the minimal weighted sum of distances from all the other faces in their patches. These representatives are used only as a stopping condition since they mark when the center of the patches are stabilized and the iterative process may be stopped. This stopping condition might be calculated in different and more efficient ways. One suggestion is to check when the centers of mass of the patches are more or less stabilized (although this might require a threshold parameter).
(2) Assign probabilities or belonging values only after the iterative process is terminated. During the iterative process a strict assignment of the faces is applied and in each stage the probabilities (as defined in the paper) have binary values. The probability assignment is then applied only when the rough decomposition is already calculated. To calculate the probabilities we apply eq. 2 from our paper but here REPA is changed the average distance of the face to all the faces contained in A and REPB is changed the average distance of the face to all the faces contained in B.
This way of calculating the fuzzy clustering also solves problems of symmetry. However, it does not have the overhead of recalculating the probabilities in each iteration.
There are many different ways that this fuzzy clustering may be achieved. The
important thing to remember is that the following stage makes up for
inaccuracies and therefore in this stage we may trade accuracy for time of
computation. For example, in our implementation the distance is calculated
using a regular Dijkstra algorithm. This may be easily traded for another
algorithm which approximates the distances without compensating the quality of
the results.
Minimum Cuts and Capacity Definitions (section 3.4 in the paper)
In the final stage of decomposition the cuts are found using a minimum cut algorithm. The capacity function definition is crucial here and directly affects the final decomposition. However, there are many ways in which the capacity function may be defined.
(1) In our paper we defined the capacity function in equation 5. It is defined as a function of the angular distance between adjacent faces so that faces having a large angle between their normals will be the bottle-neck of the flow network and the cut is likely to pass between them. The reason for dividing in equation 5 by the average angular distance is precision problems that we encountered when this factor was not used. A flaw of this capacity function definition is that when sometimes longer cuts are preferred rather than the shorter ones that cut between more faces
(2) Obviously
it is possible to use other capacity functions. One option is to use (1) and
include also arc lengths. Using arc lengths, some cases where the minimum cut
prefers large faces with smaller angular distance rather then many small faces
with larger angular distance, may be avoided. One problem with using also arc
lengths, is that there is a need to add an additional parameter to weigh the arc
lengths against the angular distance. Another problem is that if shorter cuts
are preferred when using the arc lengths, this may cause the algorithm to prefer shorter and straight
cuts which might not fit the model. However, in some applications this behavior
may be desired.
Applications
In our paper we demonstrated the application of automatic skeleton extraction using decomposition. However, there are many other applications that may be thought of. Below we briefly describe some of the applications of mesh decomposition:
(2) Texture mapping – under construction
(3) 3D puzzles
