Maya and STL – Connected vertices done right

Intro

For the third and last part1)I do have an idea for an optimization related addendum to this though, so I might be lying here, there might be a part 3.5 of the whole STL thing, of which you can find the previous part here, we’re going to finally look at actually using STL instead of Maya arrays, why, and what the benefits will be.

This is probably the most practically useful part, and ironically also the shortest. The whole point being made is, after all, that using STL will save you time. Enough time that there won’t be much code to it2)fluff will therefore be added freely to inspire further reading on your side!.

 

Neighborhood cache

The first thing to look at is multi-dimensional containers.

Maya does have some containers that are actually 2D containers. MPointArray, MVectorArray and so on are actually 2D Arrays of a fixed width under the hood. What Maya doesn’t provide that STL does however is arbitrary containers of anything of arbitrary dimensions3)you can work around this by using plain arrays of pointers to Maya arrays that are manually allocated on the free store, but then you also have to take care of manually deleting them, so we won’t even bother going into it.

Enter std::vector

The simplest container, and we’ve had a look in part one, is vector. What we didn’t mention is that you can create a vector of anything; given that means vectors of vectors of vectors and so on, you get arbitrary dimensionality.

We’ve seen (at least I have, you might be taking my word for it if you haven’t tested) that the non-sequential MItMeshVertex iterator used to retrieve the neighbors of every point we visit has a certain cost to create (so we don’t want to create a new one every iteration), and while not an unreasonable one it also has a perceivable cost when you jump it around at random intervals.
It also happens to only offer the data as an MIntArray, and do so as an output argument.
Comparatively speaking a 2D table, which will be a vector of vectors of integers, is much more efficient for random access, and running the iterator sequentially to do it seems to perform respectably.

Creating one is as simple as

#include <vector>;
std::vector< std::vector<int> >;

Same as last time, if you’re unfamiliar with templates you can simply consider those <> as the equivalent of () but for objects that are generic templates.
The above basically says create a vector (rows) and for each row the entry will be another vector, but of ints. It functionally turns into a 2D array of integers, including access.

An important difference to keep in mind, however, is that unlike a bidimensional array, which is effectively a table of ints and therefore contiguous4)Maya bidimensional arrays also seem to be actual 2D C style arrays under the hood for the previously mentioned Maya arrays, this creates a vector of references that is contiguous, but those references (each row) will point to items that have their own space and small overhead each as independent objects. This means no multi dimensional pointer arithmetic.

Doing the caching thing

What we want to do is create a random access friendly container5)accessing things by index at irregular intervals is a random access  that we can store all neighbors for each point in. It works out to the following:

MItMeshVertex itrWholeMesh(dagToSelection); // we iterate the whole mesh

MIntArray instantNbrd; // temporary array as output argument
int nbrEnd = 0; // mostly for legibility
std::vector< std::vector<int> > vecNbrs(itrWholeMesh.count());
//for each point in the whole mesh
for(itrWholeMesh.reset(); !itrWholeMesh.isDone(); itrWholeMesh.next()){
    itrWholeMesh.getConnectedVertices(instantNbrd); //get neighbors
    nbrEnd = instantNbrd.length();// get the size of it which will also be the one beyond index

    // the entry at the current index in the vec of vet is set to a vector that uses
    // the maya array boundaries as begin() and end().
    vecNbrs[itrWholeMesh.index()] = std::vector<int>(&instantNbrd[0], &instantNbrd[nbrEnd]);
}

The only thing that might seem somewhat unfamiliar is the last line. The long story short about it is that it’s a constructor for a vector that takes two arguments, the beginning and end of a container of compatible type; should sound familiar from what we’ve done with insert() before and pointers to the boundaries of MIntArray.

About the cheat, and when to cache

Later on I will refer to that cache to fetch neighbors, but I won’t be including its cost in the timing. This might seem like penalizing Maya arrays in the comparison, because using those we were fetching the neighbors inside the innermost loop, but it’s not meant to be that (and we do account for reading from such cache, only storing is left out).

Also, you don’t always want to do it. Caching is only worth it when its cost is cheaper than dynamically reading the data the long way in the actual run-time case.

The cost of creating that cache is fairly linear. The more points in your mesh, the more time creating the cache will take. The thing about it is that you only need to create it once.
If you’re inside a node or something that can preserve the cache, and know the topology of the mesh won’t change (a topo change will invalidate the cache), you only pay for it once no matter how many times from there you then run the various neighbor sensitive operations.

All that said, for a large mesh and a small number of interested points, and a run-once command, I don’t recommend you create one.
I can’t give you exact numbers because the problem is of variable size due to topology and all, but I’d say if your point count is a hundred times or more the count of vertices you expect to visit, you might be better off not bothering (again, for a run-once, for a live operator like a deformer node it will most likely be worth it).

The time taken to create the cache on my Surface Pro 3 on battery for a 10,000 vertices sphere was just short of 4 milliseconds, by the way.
This operation can also be multi-threaded efficiently  for a large enough mesh.

 

Sets, the whole point, really

Ultimately in the previous examples almost all the computational resources spent were spent doing one thing: Comparing and filtering arrays.

Had we optimized that, we could have got vastly improved performance.
How do you optimize that, then? You make search operations faster, so that instead of comparing every point to all other points you find things quicker.
How do you do that? Well, there’s a number of ways, and to be honest they aren’t super-hard to implement; depending on what solution you’re looking at anywhere between later beginner mid-intermediate programming skills, and they’re not a bad exercise either if you’re inclined.

One very common search friendly optimization is using a balanced binary tree for your data structure.
While vector is a sequence that simply keeps stashing sequentially as data gets piled and popped from the pile, a tree structure has an order to it based on a rule. The same rule also allows to know where something is likely to be (or not be) in the tree and to get to it much faster than you would traversing down a linear sequence.

A binary tree is simply a set of data that is divided in two, by some rule, for every couple items. A balanced binary tree is a tree that tries to get as close as possible to having the same number of branches on the two sides of the root.
That just happens to be a rather good way to store unique values, and to retrieve them quickly.
It’s a common enough problem that in the STL there’s a container that does just that, std::set6)the c++ standard doesn’t mandate HOW set is implemented, but in most or all compilers working with Maya it’s most likely a red-black tree.

That means there is a single container that self balances, and self filters, since set only contains unique elements. Not only that cuts code down a lot, it also happens to already come with a near-ideal implementation for our case, and to be aligned to the STL standards all containers respect.

All the above fluff is in case you want to further research things on your own. In actual use I have very little to add, you strip the hell away from our previous code, you turn all your Maya arrays into sets, and you’re done.
The code from the previous article ported to sets

std::set<int> currNbrs;
std::set<int> nextNbrs;
std::set<int> visitedVertices;

MItMeshVertex itrSelVertices(dagToSelection, selectedComponents);
for(itrSelVertices.reset(); !itrSelVertices.isDone(); itrSelVertices.next()){ // for each selected vert
    currNbrs.clear();
    nextNbrs.clear();
    currNbrs.insert(itrSelVertices.index());

    unsigned int currDepth = 0;
    while(currDepth < nbrdDepth){ // for the desired depth (recursion)
        ++currDepth;
        for(auto itrSet = currNbrs.begin(); itrSet != currNbrs.end(); ++itrSet){
            nextNbrs.insert(vecNbrs[*itrSet].begin(), vecNbrs[*itrSet].end());
        }
        visitedVertices.insert(nextNbrs.begin(), nextNbrs.end());
        currNbrs = nextNbrs;
    }
}

All the functions we had to write before are gone, STL containers come with insert, and filtering to unique values is implicit to set as a type of container.

The other sets

For the sake of completeness I have to mention that for a large enough pool of data red-black trees might not be the best thing. Without going into details there is an alternative to trees for fast searching of unique keys, and that’s hash maps.
Hash maps are basically very fast searchable indices to look at organized pieces of data, sort of like the index of a book (don’t take this comparison too literally).
They aren’t free, creating the hash table itself takes time, so for small enough data they usually aren’t worth it, but when you run what amounts of to millions of searches on thousands and thousands of entries they usually turn out to be worth it (they are particularly effective with integers, our case).

Do we have one? Yes, std::unordered_set.
Thats it, take the code above, replace set with unordered_set, and see when and where performance goes up another notch.

 

Performance

These are the results of some non-exhaustive but reasonably indicative (and certainly realistic) tests with cleaned up Maya arrays 7)but no fierce optimization such as writing our own hash mapping wrapper of a MIntArray, I have better things to do with my time, and I seriously hope you do too, then with replacing them with a vector cache and sets, and lastly with unordered sets.

Sorry if it’s not a nicely formatted graph, and don’t panic if you see different visited vertices counts, I had a crash and lost the exact selection between tests, but it doesn’t change the relationship or the core samples between tests.

Maya Arrays

----------- single vertex ------------
at depth 2 on a selection of 1 points
elapsed 0 resulting in 13 visited vertices

at depth 3 on a selection of 1 points
elapsed 0 resulting in 25 visited vertices

at depth 4 on a selection of 1 points
elapsed 0 resulting in 41 visited vertices

at depth 9 on a selection of 1 points
elapsed 0.001 resulting in 181 visited vertices

at depth 16 on a selection of 1 points
elapsed 0.013009 resulting in 545 visited vertices

----------- 1000 vertices ------------
at depth 2 on a selection of 1000 points
elapsed 0.034025 resulting in 1288 visited vertices

at depth 3 on a selection of 1000 points
elapsed 0.074052 resulting in 1424 visited vertices

at depth 4 on a selection of 1000 points
elapsed 0.140119 resulting in 1564 visited vertices

at depth 9 on a selection of 1000 points
elapsed 1.34754 resulting in 2324 visited vertices

at depth 16 on a selection of 1000 points
elapsed 11.9479 resulting in 3556 visited vertices

std::set  

----------- single vertex ------------
at depth 2 on a selection of 1 points
elapsed 0 resulting in 13 visited vertices

at depth 3 on a selection of 1 points
elapsed 0 resulting in 25 visited vertices

at depth 4 on a selection of 1 points
elapsed 0 resulting in 41 visited vertices

at depth 9 on a selection of 1 points
elapsed 0.001001 resulting in 181 visited vertices

at depth 16 on a selection of 1 points
elapsed 0.003001 resulting in 545 visited vertices

----------- 1000 vertices ------------
at depth 2 on a selection of 1000 points
elapsed 0.009005 resulting in 1311 visited vertices

at depth 3 on a selection of 1000 points
elapsed 0.021011 resulting in 1452 visited vertices

at depth 4 on a selection of 1000 points
elapsed 0.035024 resulting in 1595 visited vertices

at depth 9 on a selection of 1000 points
elapsed 0.362802 resulting in 2370 visited vertices

at depth 16 on a selection of 1000 points
elapsed 2.08711 resulting in 3766 visited vertices

std::unordered_set

----------- single vertex ------------
at depth 3 on a selection of 1 points
elapsed 0.001 resulting in 25 visited vertices

at depth 4 on a selection of 1 points
elapsed 0 resulting in 41 visited vertices

at depth 9 on a selection of 1 points
elapsed 0.001 resulting in 181 visited vertices

at depth 16 on a selection of 1 points
elapsed 0.002001 resulting in 545 visited vertices

----------- 1000 vertices ------------
at depth 2 on a selection of 1000 points
elapsed 0.018012 resulting in 1311 visited vertices

at depth 3 on a selection of 1000 points
elapsed 0.030021 resulting in 1452 visited vertices

at depth 4 on a selection of 1000 points
elapsed 0.035021 resulting in 1595 visited vertices

at depth 9 on a selection of 1000 points
elapsed 0.257182 resulting in 2370 visited vertices

at depth 16 on a selection of 1000 points
elapsed 1.46506 resulting in 3766 visited vertices

You can draw your own graph, and conclude that there is practically no fathomable case to use Maya arrays here :)

 

Conclusions

I don’t have anything to add, really, other that this is still unoptimized, and could, with very little work be made even faster by taking advantage of the Standard Library and what it offers to manipulate STL containers.

The code, with all the same disclaimers of the previous article about C++11, VC and so on, can be found here.

Last time I forgot to mention that if you compile and load the plugin the command is the following:
getDeepNeighbors -dp N
With N being the int for the desired depth. But then I’d hope if you’re reading these articles you could figure that out from the source.

Yes, it was rainy outside, and I was bored again.
Thanks for reading,
Raff

Footnotes   [ + ]

1. I do have an idea for an optimization related addendum to this though, so I might be lying here, there might be a part 3.5
2. fluff will therefore be added freely to inspire further reading on your side!
3. you can work around this by using plain arrays of pointers to Maya arrays that are manually allocated on the free store, but then you also have to take care of manually deleting them, so we won’t even bother going into it
4. Maya bidimensional arrays also seem to be actual 2D C style arrays under the hood for the previously mentioned Maya arrays
5. accessing things by index at irregular intervals is a random access
6. the c++ standard doesn’t mandate HOW set is implemented, but in most or all compilers working with Maya it’s most likely a red-black tree
7. but no fierce optimization such as writing our own hash mapping wrapper of a MIntArray, I have better things to do with my time, and I seriously hope you do too

Leave a Comment