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.

**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