Mesh as Graph

The approach I have chosen for mesh segmentation involves representing the mesh as a graph. This graph will allow for algorithms such as Dijkstra’s shortest path and Floyd-Warshall all-pair-shortest-path to be calculated.

slide00_01_graphheory

What is a graph?
A graph is a set of nodes (depending on your convention you can call them nodes or vertices) connected by pairwise relations. You can have as many lines as you want coming in and out of a node, but each line can only be connected to two nodes, creating a pair. These lines are called edges (or arcs) and can have an weighting associated with them, and it is this weighting makes graph such a powerful concept.

Representing a graph!
A graph may be represented either as an adjacency list or and adjacency matrix. Some graph calculations require adjacency lists and others require adjacency matrices, neither of which are difficult concepts or difficult to implement.

An adjacency lists will conceptually show us the node Id and what nodes it is connected to. Lets say that London is a node, and from London you can travel to Oslo, Berlin and Paris. This would be written as:

London = Oslo, Berlin, Paris

We have now described the edges between our node (London), but we can also associate a weighting for the edges, represented as flight time from our node to the connected nodes:

London = (Oslo, 2h), (Berlin, 1h), (Paris, 1.5h)

Adjacency lists are commonly represented as dictionaries in python, as shown here:

# Initialize our adjacency list graph.
graph = {}

# Add a node and its edges to the adjacency list.
graph['London'] = ('Oslo', 'Berlin', 'Paris')

# Update the node to associate weightings with its edges.
graph['London'] = (('Oslo', 2), ('Berlin', 1), ('Paris', 1.5))

print graph
# {'London': (('Oslo', 2), ('Berlin', 1), ('Paris', 1.5))}

Matrix!

You better have a basic understanding of matrices, if not, they can be explained as a grid of size ij. That is i wide and j high, correct terms would be i rows and j columns( a matrix is denoted Mij). An adjacency matrix is always square because it represents all the nodes in i and in j, so i and j = number of nodes on the graph. When you view an adjacency matrix it will remind you a bit of a identity matrix where all diagonal elements are 1, just that in adjacency matrix all diagonal elements are 0. If we have an graph, represented by text as:

1. London = Oslo, Berlin, Paris

2. Oslo = London

3. Berlin = London

4. Paris = London, Berlin, Oslo

We can see that we have 4 nodes (London, Oslo, Berlin, Paris), so we would have an adjacency matrix of size i = 4 and j =4 (Mij = M44).

   1  2  3  4
1  0, 0, 0, 0
2  0, 0, 0, 0
3  0, 0, 0, 0
4  0, 0, 0, 0

If we put our data into the matrix we would receive:

   1  2  3  4
1  0, 1, 1, 1
2  1, 0, 0, 1
3  1, 0, 0, 1
4  1, 1, 1, 0

To represent a mesh as a graph in adjacency list form and adjacency matrix form we loop all the faces of the mesh. Check which faces faceN is connected to, this would be the edges our current node has. Calculate the distance between faceN and its edges. apply this to a adjacency list and a adjacency matrix.

import maya.OpenMaya as om
import maya.cmds as cmds

def selectObj():
    ####### Querying a selected object
    cmds.FreezeTransformations()
    # Turns on the option for maya to track what order you selected things in
    om.MGlobal.setTrackSelectionOrderEnabled(True)

    # 1 # Initialize a selectionList object
    selectionLs = om.MSelectionList()
    # 2 # Populate the selectionList with current selected objects
    om.MGlobal.getActiveSelectionList(selectionLs)
    # 3 # create an iterator from our queried selection list, and give it an filter to only iterate kmesh
    iterSel = om.MItSelectionList(selectionLs, om.MFn.kMesh)
    # 4 # initialize a dagObject object
    dagObject = om.MdagObject()
    # 5 # populate the dag path object
    iterSel.getdagObject(dagObject)
    return dagObject

####################################

def objToGraph(dagObject):
    """
    Returns an adjacency list representing the inputed dagObject
    Creates a node for each face and calculates weightings
    between nodes based on distance from the center of
    faceN1 to center of edgeN to the canter of faceN2

    weighting = |-----------------|-----------------|
                f1.center -> edge.center <- f2.center

    """
    # initialize iterators
    mitFace = om.MItMeshPolygon(dagObject)
    mitEdge = om.MItMeshEdge(dagObject)

    ####################################

    #### Faces
    # iterate over all the faces

    faceFace = om.MIntArray()
    faceId = om.MIntArray()

    faceRel = []    # keep a list of which faces are connected to face N.
    facePos = []    # hold the centroid position of each face.

    mitFace.reset()
    while not mitFace.isDone():

        # get the connected faces of the current face
        mitFace.getConnectedFaces(faceFace)
        faceRel.append(list(faceFace))

        # get the center of the face
        fcenter = mitFace.center()
        facePos.append(fcenter)

        mitFace.next()

    # iterate over all the edges
    mitEdge.reset()
    while not mitEdge.isDone():

        # get the faces connected to the edge
        mitEdge.getConnectedFaces(faceId)

        # check if the edge is valid i.e. must have two faces connected to it
        if faceId.length() == 2:

            # get the center of the current edge
            edgeCenter =  mitEdge.center()

            # holder variables for the two faces in question
            f1 = faceId[0]
            f2 = faceId[1]

            #### Length weighting Calculation

            # retrieve the center of the face from our queried list
            p1 = facePos[f2]
            p2 = facePos[f1]

            # calculate the face-to-edge length
            fe1 = p1 - edgeCenter
            fe2 = p2 - edgeCenter

            # the total length for the weighting from one node to the other
            fLength = fe1.length() + fe2.length()

            # adding the weighting to the adjacency list structure
            ind1 = faceRel[f1].index(f2)
            val1 = faceRel[f1][ind1]

            ind2 = faceRel[f2].index(f1)
            val2 = faceRel[f2][ind2]

            faceRel[f1][ind1] = [fLength, val1]
            faceRel[f2][ind2] = [fLength, val2]

        mitEdge.next()
    return faceRel