From BlenderWiki

Development Documentation

This needs to be added:

• How do we detect that a componenent is connected
• What do we do to generate the seam?
• What do we calculate the Eigenvalues for?
• How are the Eigenvectors used to find a split of the mesh?

Notes about the algorithm

Getting connected component of the meshes

To do that, first of all we considered each face of the mesh as a node of a Graph. We run the Depth first search algorithm for the whole mesh until all of the faces of the mesh is visited. Each call of the depth first algorithm visited some new unvisited nodes. These nodes form a connected component of the mesh. Later on, we run our algorithm for each of the components separately.

The main approach for generating the seam

In order to generate seam, in short, we calculated connected components of each mesh. For each connected component we calculated graph laplacian matrix. We calculated eigenspace (eigenvalues, eigenvectors) for the laplacian matrix. Each eigen vector separates a component of the mesh into two parts. In one set there resides the faces having positive eigen value and in another set there reside faces with negative eigen values. Now, if the faces having positive eigen values are connected and the faces having negative values are connected we can consider the corresponding vector as a candidate for solution. Each such eigen vector separate a component into two parts if we draw a line between the connected positive eigen valued faces and negative eigen valued faces. We can call the line seam. From all candidate eigen vectors, the one that generates the seam with the maximum length is our desired seam.

The reason behind calculating eigen values

In short, we calculated eigen values of the laplacian matrix of the mesh in order to encode the semantic information of mesh into the eigenspace. By doing so, we are getting a numerical representation of the semantic information of the mesh. With this avialable, we have the scope to do operation on it to get our desired result.

How are the Eigenvectors used to find a split of the mesh?

I think this is already discussed in section 1.1.1.2

Milestones

• Write a wrapper API for Eigen3 library.
• Generate Laplacian matrix and calculate Eigenspace.
• Implement algorithm for marking seam/seams.
• Integrate the seam unwrap functionality with the added code.
• Handle some special cases and draw UI.
• Implementation of a Sparse Matrix module.
• Integration of ARPACK library to solve Eigenspace for large matrix.
• Implement a extendible eigen solver class and extend it for eigen library.

Write a wrapper API for Eigen3 library

Currently we are using Eigen3 library for eigenvalue calculation. Which can only calculate eigen values of small matrixes. We are using this for now just to implement the basic algorthm first. This library is written in C++. So, to use it's functionality we have to write a wrapper API for this library. Here, I am showing only how to use the wrapper.

To create a n*n zero valued matrix:

AUTOSEAM_Adjacency adj;
adj = autoseam_create_adjacency(n);

To set a value of the element with index (m,n):

float value = 3.0;
autoseam_set_adjacent(m, n, value);

To generate seam and get the split of face indexes in fplus and fminus array:

AUTOSEAM_Adjacency adj;
int s;
 
autoseam_generate_seam(adj);
s = autoseam_get_best_split(adj);
autoseam_get_split(adj, s, fplus, &nplus, fminus, &nminus);

Generate Laplacian matrix and calculate Eigenspace

Let, ( V, E , F ) be the V vertices, E edges and F facets sets of a structured polygonal mesh. Calculate dual graph of the mesh G( F ^* , E ^* ).

Where,

• F ^* = The vertices of the dual graph
• E ^* = The edges of the dual graph

Now, calculate martrix A which is the adjacency matrix of graph G. Compute another diagonal matrix D where,

• D_ii = i^th row sum of G.

The Laplacian matrix L is -

• L = A − D

After this, the Eigenspace of L is calculated.

The function that calculates the dual graph of the selected mesh is -

/*@main parameters:
 * adj             : AUTOSEAM_Adjacency instance
 * bm              : selected mesh
 * is_combinatorial: act as boolean, it set from the UI
 */
autoseam_create_graph(adj, bm, is_combinatorial, -1, NULL, 1);

Implement algorithm for marking seam/seams

The main functions related to algorithm of marking seams is described in this section with the top level flow of the algorithm.

• Get connected components of the mesh and call the seam generation algorithm for each component. The function signature to do this is -

/*@parameters:
 * adj             : AUTOSEAM_Adjacency instance
 * num_nodes       : number of faces in the passed component
 * bm              : instance of the mesh
 * recursion_depth : How far the recursion will go, set from UI
 * C               : bContext of the operator
 */
int handle_separate_components(AUTOSEAM_Adjacency adj, int num_nodes, BMesh *bm, int recursion_depth, bContext *C);

• Call a recursive function that will generate the seam recursively up to a given depth set by the user from the UI. The function that does this is -

/*@parameters:
 * bm              : instance of the mesh
 * adj             : adjacency matrix of the current portion of mesh
 * adj_big         : adjacency matrix of the main mesh
 * recursion_depth : How far the recursion will go, set from UI
 * C               : bContext instance of the operator
 * stretch         : stretch value for the whole mesh
 */
 
int generate_seam_recursive(BMesh *bm, AUTOSEAM_Adjacency adj, AUTOSEAM_Adjacency adj_big, int recursion_depth, bContext *C, float stretch)

Integrate the seam unwrap functionality with the added code

This portion was pretty straightforward. We just integrated the existing seam unwrapping functionalities. This integration allows the operator to unwrap the marked seams in one go. The code snippet that does this is given below -

/* add uvs if they don't exist yet */
if(!ED_uvedit_ensure_uvs(C, scene, obedit)) {
    return OPERATOR_CANCELLED;
}
 
/* remember last method for live unwrap */
scene->toolsettings->unwrapper = method;
if(fill_holes)	scene->toolsettings->uvcalc_flag |=  UVCALC_FILLHOLES;
else            scene->toolsettings->uvcalc_flag &= ~UVCALC_FILLHOLES;
 
if(correct_aspect) scene->toolsettings->uvcalc_flag&=~UVCALC_NO_ASPECT_CORRECT;
else   scene->toolsettings->uvcalc_flag |=  UVCALC_NO_ASPECT_CORRECT;
 
ED_unwrap_lscm(scene, obedit, TRUE);

Handle some special cases and draw UI

There were some special case in generating seams. For example, a mesh has some non-connected selected components. So, in case of generating seams we need to generate seams for all of the selected components. Moreover, a selected component can have hole inside it. We also handled this case in our code. While generating seams there should be some space between the generated seams to aid texturing. It's already implemented in Blender Smart UV Project and known ase 'Island Margin' feature. We have integrated this functionality with our operator. And the user interface for using the operator is drawn with the blender python API.

Implementation of a Sparse Matrix module

If we represent the meshes as matrix in most of the case they will be sparse matrixes. So, for the computational and storage efficiency it is better for us to store them in Sparse Matrix. It will also needed in efficient Matrix-Vector product calculation which is used a lot of times while calculating eigenspace with the eigen solvers. That's why we implemented a class for storing geometric representation of mesh in SparseMatrix.h. We used the Compressed Row Storage (CRS) data structure in our implementation. In short, the Compressed Row Storage (CRS) format puts the subsequent nonzeros of the matrix rows in contiguous memory locations. More information about it can be found here - http://netlib.org/linalg/html_templates/node91.html

Integration of ARPACK library to solve Eigenspace for large matrix

Done.

Implement a extendible eigen solver class and extend it for eigen library

Done.