Sweet, Sweet Matrices: Part 2

Here’s the code for the matrices problem I talked about in the previous post. This little guy is a PNG (until I find a good way to display code without you having to scroll left/right). The details and explanations for what’s going on are below as well. Check it out!

tree_leaf_code2

#16 Get The Base Shape: This section rips off the first shell in the main mesh, moves it to the origin, and resets its transforms. This new object will be the base shape that we’ll repeatedly compare to the other shells to determine their transformations, as well as be the instance shape that replaces those shells.

16 first_shell_trans, the_mesh_trans = pm.polySeparate(the_mesh_shape, sss = 0, ch = False)
17
18 pm.xform(first_shell_trans, cp = True)
19 pm.move(0,0,0, first_shell_trans, rpr = True)
20 pm.makeIdentity(first_shell_trans, apply = True)

#29 Find Its Invertible Matrix: Now that we have the base instance shape isolated, we need to pick four of its vertices to define a matrix of global vertex positions. Later, for each shell, we’ll repeat the process for those same vertex indices, then compare the two matrices to determine the shell’s translate/rotate/scale/shear values, relative to our base shape.

One hiccup though, is picking the right combination of vertices that form an invertible matrix! Because we’ll be doing some math that requires a matrix with an inverse, this can be a roadblock. The solution here is brute force! Keep picking four verts from the base mesh, at random, until an invertible matrix is found. You can see on line #29 that we start with a list of all the vert indices, then on line #32, we pick four from that list, at random.

On line #40, we’re attempting to find the inverse. If it fails, we try again with another pass through the while loop at #27. (Ignore the flipped_positions variable, I get to that later)

29 verts_all = range(instance_shape.numVertices())    
30 verts_4 = []
31 for i in range(4):
32     verts_4.append(verts_all.pop(random.randint(0, len(verts_all) -1)))
33
34 shell_id = 0
35 positions = [instance_shape.vtx[shell_id + verts_4[i]].getPosition(space = 'world').tolist() for i in range(4)]
36 flipped_positions = [[row[i] for row in positions] for i in range(3)]
37 flipped_positions.append([1,1,1,1])
38 matrix_orig = pm.datatypes.MatrixN(flipped_positions)
39
40 try:
41     matrix_orig_inverse = matrix_orig.inverse()
42     inverse_found = True        
43 except:
44     inverse_try_count = inverse_try_count + 1

#48 How Many Shells ‘N Verts? If we actually found an invertible matrix, then proceed! The first step is to find out how many shells are in the main mesh, so we can loop through them with a list of their starting vertices (0, 20, 40, 60,… last_shell’s_first_vertex).

48 the_mesh_shape = the_mesh_trans.getShape()
49 pm.select(the_mesh_shape)
50 num_shells = pm.polyEvaluate(shell = True)
51 pm.select(clear = True)
52 verts_per_shell = the_mesh_shape.numVertices() / num_shells
53 shell_ids = range(0, the_mesh_shape.numVertices(), verts_per_shell)

#59 Loop Through All The Shells: Here’s where most of the actual work is done. For each shell, grab the world positions of the four specific vertex indices we found at #32, then throw them into a matrix. There are a few details that have to be right though; the positions need to be in column vectors, not row vectors (so we reorder them on #60), and to make this a 4×4 invertible matrix, we need to append a W value of 1 to each vector. I think “homogeneous” might be a term to use here.

59 positions = [the_mesh_shape.vtx[shell_id + verts_4[i]].getPosition(space = 'world').tolist() for i in range(4)]
60 flipped_positions = [[row[i] for row in positions] for i in range(3)]
61 flipped_positions.append([1,1,1,1])
62 matrix_new = pm.datatypes.MatrixN(flipped_positions)

#64 MATH!! Ok, the REAL work is done here, in just a line or two with matrix math! This is why we found an invertible matrix earlier, to use here. We’re determining the transformation that was applied to each shell (again, relative to our base shape), solving for x in xO = N, where x is the transformation that’s applied to the (O)riginal base shape, resulting in (N)ew vertex positions. Just multiply both sides of the equation by O^-1 to find x. That O^-1 is the inverted matrix we found earlier.

(One catch in matrix math though is that you need to do this is in the correct order. Unlike regular multiplication, where xy = yx, that ISN’T the case here.)

64 transformation_matrix = matrix_new * matrix_orig_inverse

#65 Flip It, For Real: The transformation matrix we just found has the right numbers, but they need to be flipped around along the matrix’s diagonal, so they’ll play nice with how Maya’s transformation matrices are ordered.

65 transformation_matrix_transposed = transformation_matrix.transpose()

#66 Make This Whole Thing Slow: We found the answer for this shell, now store it in a list to use later on our instance objects!

66 instance_transforms.append(transformation_matrix_transposed)

#72 Create And Align The Instances! Now, let’s loop through all the transformation matrices we found, and apply them to the instance objects we’re creating.

72 for i, transform in enumerate(instance_transforms):
73     one_instance = pm.instance(instance_shape, name = 'mesh_instance_' + str(i).zfill(3))[0]
74     one_instance.setTransformation(transform)

#79 A thousand apologies:

79 else:
80     for i in range(1000):
81         print 'apology'

Conclusion:
This solution is complicated, and I’d love to see something simpler! I’d also like to increase the speed, so it can actually work on a million+ shells. I think the main culprit is accessing the main mesh, repeatedly, to query four vert positions in each shell. Maybe if I gather that data in one pass? Or declare the size of the arrays/lists involved so they don’t need to be reallocated with each loop that changes their size? There are a few options here, luckily. If those fail, switching over to OpenMaya would be the next step for a hopeful speed increase. I think there’s a function for grabbing multiple vert positions with one call in there! That may be the secret.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s