Maya and STL – Deep Connected Vertices

Part 2, something practical

Given the previous post might have been informative, but somewhat inconclusive in showing why you would care about STL1)the containers part of the Standard Library is referred to as simply STL this time around we move right away to a practical example of how you could do things without STL, and in a follow up we’ll look at the STL alternative.

 

Vertex Neighborhood problems

Maya offers a single straightforward way to get the neighborhood of an arbitrary point: the getConnectedVertices() method in the mesh vertex iterator.
It’s a suitable place and a reasonable layout, but it has one issue, the degree of topological connection is limited to 1; only the immediately connected points are available, if you want the points connected to the connected points you’re on your own.

Sampling data around a vertex, with around being the topological geography of it, is an incredibly common operation that a lot of important algorithms use2)I’d say Laplacian based operations like Smoothing/Relaxing geometry or vertex attributes are the most common and the most intuitive; a lot of the time the immediate neighborhood is all you need, but not infrequently you need a deeper neighborhood. Smoothing skinning weights the way Softimage does, which is infinitely superior to Maya’s, is one such case.

Conceptually the problem is simple: You have a vertex, you get its neighbors, you sample data. You iterate such neighbors, you get their neighbors, you sample the data on those. Rinse and repeat until happy with how far you got, be it depth or distance; simple recursion.
Implementation wise the problem isn’t quite that simple however if you’re limited to Maya’s arrays. Each vertex connected vertices will also include the point you are coming from, and in some topologies, or with enough depth, the other neighbors in the same step. You end up with a lot of duplicates, and you need to filter to unique entries.

Naively filtering an array from duplicates is easy, just compare it with itself and keep only the good stuff, but it’s an O( (N-1)^2 ) cost3)the cost is the Operation by one less entry than the length of the array, because the first is bound to be unique, squared.
If you have a non real-time application (a command instead of a deformer node) and do one point at a time to accumulate per point it’s not a huge deal for limited depths, but that’s a lot of restrictions.

With a guarded, frequently filtered (faster than naive), but not data optimized solution these are the times on my i5 Surface Pro 3

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.000999 resulting in 181 visited vertices

at depth 16 on a selection of 1 points
elapsed 0.010014 resulting in 841 visited vertices

You have to get to depth 16 to see it creeping into a hundredth of a second 4)incidentally the precision limit of Maya’s shoddy timer, I’m using microseconds on a steady_clock, and it’s below a microsecond until a depth of 9.
Run that on a million vertices, which these days is nothing special, and your iterator alone will have taken a considerable amount of time already at depth 9. Even at just 5 or 6 you’re likely not to be real-time for the neighbor fetching alone and you have no computational elbow room left for the actual work5)with realtime being 24fps, if you think screen V-Sync 60Hz it’s even worse.

A less frequent but not artificial case is needing to grow an island selection as one entity instead of one point at a time (expanding your vertex selection would be such a problem). In such case you are in a position similar to starting from a high depth already with a progression worse than linear, and close to squared or even worse in a very naive one6)topological operations on arbitrary topologies aren’t as easy to give an order of operations to as something like fixed size tables, the connectivity can affect the result either way greatly.

at depth 3 on a selection of 1000 points
elapsed 0.07305 resulting in 1367 visited vertices

at depth 4 on a selection of 1000 points
elapsed 0.135097 resulting in 1497 visited vertices

at depth 9 on a selection of 1000 points
elapsed 1.33495 resulting in 2207 visited vertices

For just 1000 points at depth 9 the results of a not completely naive implementation are 1336 times worse; not as bad as the worst case but already showing worse than linear time increase.

 

Some implementations

Filtering a Maya array

The first thing worth doing is writing something that can filter unique elements from an MIntArray and return one. We know we’ll need it, might as well.

MIntArray uniquesFromMIA(const MIntArray& mArr){
    unsigned int len = mArr.length();
    if(len < 2 ){ return MIntArray(mArr); }/* if there's 0 or 1 element
                                              we can simply return a copy
                                              as it's bound to be a unique element*/
    MIntArray ret(1, mArr[0]); // first element is always unique
    bool found = false;
    for(unsigned int i = 1; i < len; ++i){ // compare array with itself
        found = false;
        for(unsigned int j = 1; j < len; ++j){
            if(mArr[i] == mArr[j] && i != j){ // if identical and not the same index
                found = true;                 // we flag that it's not unique
                break;                        // and exit early
            }
        }
        if(!found){
            ret.append(mArr[i]); // if not found instead we append it to the return array
        }
    }
    return ret;
}

The code is pretty simple and the filtering better than (N-1)^2 because we’ll likely get a few early exits, unless the array is already populated of unique elements only, in which case you will pay the full cost.
Bear in mind this is pretty far from ideal, or even good, performance wise, but that’s kind of the point. Unless you are willing to spend a considerable enough amount of time working on your own data structures, at levels that would be likely challenging for a beginner, this is probably the best you could do.

Append and filter

Now, the next and most naive thing you might think of doing would be accumulating all your points, and then filtering it for duplicates all at once.
I would strongly recommend you don’t do that unless you want to see tens to hundreds or worse performance. This being a geometric progression of cost filtering frequently on small arrays is always going to be more efficient.
That means the next interesting bit is something that takes an MIntArray to append to another. E.g. the former might the new neighbors we fetched, and the latter the one we’re accumulating the current recursion level into.

A not-quite-ideal but not too shoddy function to do that, with some attention to safety, is actually not all that hard to write:

void appendUniquesToMIA(const MIntArray& toAppend, MIntArray& toExtend, bool filter = false){
    unsigned int lenSource = toAppend.length();
    unsigned int lenTarget = toExtend.length();
    if(!lenSource){ return; } // empty source means no operation
    if(!lenTarget){           // empty target means we can simply make the source unique
        toExtend = uniquesFromMIA(toAppend); // and set the target to that
        return;
    }

    /*
    the comparison below appends to the array to modify based on a
    comparison between the existing source and target at the state of passing them.
    This means that the source of additions needs to be unique,
    or the potential duplicates will make it as multiple entries into the target array.
    Filter offers the option to do it in-function if it was inconvenient to do it outside */

    MIntArray tmpA;
    if(filter){
        tmpA = uniquesFromMIA(toAppend);
        lenSource = tmpA.length();
    }

    bool found = false;
    for(unsigned int i = 0; i < lenSource; ++i){
        for(unsigned int j = 0; j < lenTarget; ++j){
            // if filter is on then the filtered array is used instead of the source
            // and whichever's entries are compared to the target's for unicity.
            if( (filter ? tmpA[i] : toAppend[i]) == toExtend[j]){
                found = true;
                break; // early exit if the item is found to be a duplicate.
            }
        }
        if(!found){
            toExtend.append(toAppend[i]);
        }
        found = false;
    }
}

Again, this isn’t ideal at all, but ideal solutions would practically circumvent Maya almost entirely, at which point we might as well use STL right away. This is already taking quite some extra work to just get non catastrophic performance but what would be the point of just telling people “use STL containers because!” if you don’t show at least part of the other option you recommend moving away from?

N.B. while the code presented here isn’t horrible, I wouldn’t suggest taking this article as a how-to guide on C++ programming. I’m favoring literate and understandable over optimal while also doing some things that beginners would generally be advised to be careful with (modifying in place, unchecked pointer arithmetic, copying memory and so on).

Deep neighborhood loop

Got this far, might as well show an implementation of the vertex iteration and the depth recursion.

/*
We'll need two iterators:
One will be used to traverse the selection,
the other will be used to get the connected vertices from each point
inspected in the current iterator's loop.
We could use one iterator only inside the depth loop to then set it back
in time for the selection iteration to advance correctly, but it seems
that jumping mesh iterators around is considerably more expensive than
running multiples and advancing them the minimum necessary amount of times
*/
MItMeshVertex itrSelVertices(dagToSelection, selectedComponents);
MItMeshVertex itrNbrVertex(dagToSelection);

MIntArray visitedVertices; // final list of vertices to be populated
MIntArray currNbrd, nextNbrd, instantNbrd; // temp arrays for the operations
                                           // we need two for a swap
                                           // then one more for getConnectedVertices() output argument

// A dummy int to satisfy Maya's output argument happy attitude
int iDump;
unsigned int nbrdDepth = 4; // the desired topological distance
for(itrSelVertices.reset(); !itrSelVertices.isDone(); itrSelVertices.next()){ // for each selected vert
    nextNbrd.clear();
    currNbrd.clear();
    // start the neighborhood from the current vetrtex
    nextNbrd.append(itrSelVertices.index());

    unsigned int currDepth = 0;
    while(currDepth < nbrdDepth){ // for the desired depth (recursion)
        ++currDepth;
        /*
        We set the current neighborhood to what was the next in the previous iteration
        but to reduce waste we make sure to reduce it to unique values first.
        The recursive nature of deep neighborhood means points you come from will
        also be seen from points you're going to in the following recursion.
        Without filtering the growth rate would be ridiculous.
        */
        appendUniquesToMIA(nextNbrd, currNbrd);

        unsigned int lenNbrd = currNbrd.length();
        for(unsigned int i = 0; i < lenNbrd; ++i){ // for each point inspected before
            itrNbrVertex.setIndex(currNbrd[i], iDump);
            itrNbrVertex.getConnectedVertices(instantNbrd); // the neighbors of each of those points
            // are put in the temp array instantNbrd

            appendUniquesToMIA(instantNbrd, nextNbrd); /* appended the above the neighborhood that will be looked
                                                       up at the next recursion */
        }
        if(nextNbrd.length() >= itrNbrVertex.count()){ break; } // a weak guard against an excessive depth.
        // very unlikely to engage in real use, unlike the one below
    }                                                           // but cheap compared to the rest of the loop operations

    appendUniquesToMIA(nextNbrd, visitedVertices);

    // if we have visited vertices == pointcount of the whole mesh there's no point doing more vertices;
    if(visitedVertices.length() >= itrNbrVertex.count()){ break; }
}

It might look like a fair chunk of code, but it’s actually not much, it’s just laid out plainly and heavily commented.

Looking at it you might also be tempted to wrap the actual depth recursion into a separate function to leave only the selection iterator in the main body, and it is actually possible and quite easy, but you would have to create most of the objects it needs outside of it and pass them in to avoid paying for their constructors and destructors every time, and that would make the function’s signature rather messy. On top of that, it’d be a touch harder to optimize it, and the compiler will usually not respond too well to it compared to the current inlined state7)A cursory test of just moving it out and signing it optimally added a considerable overhead in my test runs, and to be honest doing all of this with the API’s facilities alone is a colossal waste of time if you have an actual deadline, and there’s only that far I’m willing to go to demonstrate something :) .

 

Wrapping it up

If you want to have a look at a whole, working plugin implementing the above I’ve started using a repository for these articles so I can offer these things.

There’s a branch with all of the above implemented and working, you can find it on one of my online repositories here.
It’s pretty close to identical to what I’ve written in here, and I tested it compiles and runs inside of Maya.
The only surprise you might find is that it uses chrono for timing, and auto for chrono objects. Chrono and auto being C++11 mean they are only available (assuming you use the prescribed compilers) if you use Maya 2015 on Windows. If you’re using anything older and don’t have a C++11 compliant compiler you can simply remove the lines using it and the chrono include and it should work on any version of Maya.
Replace the timer with something that works on your platform (MTimer from Maya might do if you’re OK with the shoddy hundredth of second precision) and the logging below the end of the timer should also work.
I decided to leave the visual studio projects in as well, keep in mind two things about that: One, they are VS2013 community projects, two, I use a bunch of environment variables to be able to run multiple builds across VS and my own Make system. At least a couple of those variables are likely to be peppered in the project, the one for includes and the one for external libraries. If you use the project you will need to keep those two things in mind and modify accordingly; basically I consider the project files a small step above useless, and will probably remove them in the future as more stuff gets added to that solution or my build system changes.

As I mentioned several times this isn’t an optimal implementation. It’s not terrible, mind, a fully naive version would be literally hundreds to thousands of times slower in any case that’s even middle of the road complex, let alone in larger ones.
If you want to look at further optimizing it then you are looking at replicating what the Standard Library provides for you out of the box.
Namely you want a more efficient structure for data that needs to be unique, and accessory methods to that structure that know what do with it; most likely you’d be using a keys only, hash map based container, or possibly a balanced tree, so that searching to filter things is unique, and ideally that unicity is always granted by the object itself.

For further optimization from there context can become important, and figuring out what repeated costs can be managed to become paid once only is a common pattern and an easy enough one for beginners to look at.
E.G. if you needed this in a continuous fashion, and not as a run-once command, an iterator like MItMeshVertex jumping around to retrieve neighbors all the time is inconvenient, reading and storing the neighbors in a cache with good random access properties only once would probably improve things considerably.

Anyway, we’ll look at the above, and how it comes out of the box from STL containers in the next part, this one is already long enough as it is.

Footnotes   [ + ]

1. the containers part of the Standard Library is referred to as simply STL
2. I’d say Laplacian based operations like Smoothing/Relaxing geometry or vertex attributes are the most common and the most intuitive
3. the cost is the Operation by one less entry than the length of the array, because the first is bound to be unique, squared
4. incidentally the precision limit of Maya’s shoddy timer, I’m using microseconds on a steady_clock
5. with realtime being 24fps, if you think screen V-Sync 60Hz it’s even worse
6. topological operations on arbitrary topologies aren’t as easy to give an order of operations to as something like fixed size tables, the connectivity can affect the result either way greatly
7. A cursory test of just moving it out and signing it optimally added a considerable overhead in my test runs, and to be honest doing all of this with the API’s facilities alone is a colossal waste of time if you have an actual deadline, and there’s only that far I’m willing to go to demonstrate something :)

Leave a Comment