Here is the dog as an example, using 0.0015 as the Douglas-Peucker threshold. Knots are indicated by locators.

The results aren't particularly clear in this example, but further processing does occur so the threshold may change to accommodate that.

Best Fit Polynomial

In order to determine the best way to connect these knots to form components, ACD calculates a weight for each projected edge using the best fit polynomial from Andreas Hubeli and Markus Gross's 2001 Multiresolution Feature Extraction from Unstructured Meshes paper. The ACD paper was a little vague about what to do here, so I'm writing out my approach.

We know that the best fit polynomial is computed from the intersection between the plane that bisects an edge e and a subset of the model surrounding e. The following questions arise. How do we find the intersection? How big should the model subset be? What degree polynomial do we need? How does one even calculate the polynomial?

Finding the Intersection

Because the input model could be of any density or topology, there's no simple loop that we can iterate over to find appropriate nearby edges that intersect the plane.

We want to get all of the edges that intersect the plane without "skipping" one, so a traversal seems most intuitive. I considered a Dijkstra-type approach, but it was difficult to guarantee continuity. We don't care about other points, so depth-first traversal is preferable to breadth-first. We can guide the traversal by picking the neighbor that best fits a criterion. One criterion is to pick the neighbor closest to the plane, but this doesn't always work if the "best" edge is much longer than the other outgoing edges. Another criterion is to find the outgoing edge that points most towards the plane, storing the edge if it crosses the plane. This seems to work in my test cases.

If we have a strict depth-first traversal, we might not find intersecting edges the most efficient way (one side of the plane may be denser than the other, or one side may be curved). To counter this, we can pick the "best" unvisited edge (using our criteria) from the current vertex and the vertex we came from. This optimization may be unnecessary though. Then, in order to get roughly equal amounts of data on either side of the edge, we can simply restart our traversal with the best neighbor in the opposite direction. What happens if edge e is a length-wise edge on a low-poly cylinder? As such, it's probably best to alternate between the two directions to ensure an even spread.

Determining the Polynomial

In order to answer the question of "How much data?", we must first determine the method of processing the data. The best fit polynomial weight calls for a second derivative, which means that we need at least a quadratic or cubic polynomial for non-trivial results.

I don't have a lot of experience in this area, but it seems that the best general-use method for fitting a polynomial (or polynomial regression) is the least-squares method. I'm not about to implement my own linear algebra library, so I'll let Eigen do the work.

Because chances are that the knots are on C curves, even ordered polynomials would work best. It would also be very simple to check the nature of the curve and change orders accordingly. It's also worth noting here that polynomials can't handle overlapping y values, so nearly circular and related shapes need to be checked.

Model Subset Size

Although the best fit polynomial is more or less mesh-density agnostic, we still care about the mesh as a whole (for skeletonization), rather than at the detail level. However, I'll need to write some tools to find the best method for calculating mesh density. For now, I'll say that 3 points on either side of the edge are sufficient. This is because a typical animation rig limb might have around 8-24 (very rough estimate) lengthwise divisions, whereas the chest/pelvis likely has 16-32 (also rough estimate). Regardless of the estimate accuracy, 7 vertices are far more than enough to find the curvature of an 8 vertex circle, and they should also be enough to cover a feature on a high-res model.

That should be everything! Time to get to implementing.

Useful Links

• Approximate Convex Decomposition Site
• Polynomial Least Squares Fitting
• Eigen Least Squares Fitting Documentation
• Project GitHub

I have all of the work done to project the convex hull edges (i.e. the bridge edges) onto the mesh itself. The purpose of the project edges is to help determine the appropriate convex hull face (bridge) from which to calculate SL-concavity (the straight-line distance from a point on the mesh to the plane represented by the bridge). An example can be seen below:

I implemented Dijkstra's algorithm using the shortest distance between the points. For low-poly meshes like this dog, the resulting projection can deviate from an actual projection quite a bit. It would be better to have a more accurate projection than a shorter path. I was mistaken in my implementation! I changed the distance calculation to use perpendicular point-line distance instead. The green path is the new projected edge using point-line distance. The white path represents the original shortest distance projection.

Much better! Since we know the corresponding bridge faces for each projected edge, we can reduce the number of bridge faces to search through as we try to find the minimum SL-concavity. The problem lies with finding the corresponding faces for vertices that lie outside of the projected edges.

The approach I took was to iterate through each vertex with undetermined bridges and flood the area until projected edges were found. Usually, all of the projected edges share a common bridge face, which we use. Occasionally, in deeply concave areas, such as the underside of a dog, no common bridge face can be found. In such scenarios with multiple possible bridge faces, the closest bridge face by point-plane distance is used. The resulting concavity visualization:

And herein lies a potential fault of ACD (or SL-concavity). There aren't always intuitive decompositions based on concavity. For this dog model, we would expect at least one well-defined concave ring between the head and the body to separate the two body parts. Or a ring around the base of the limbs or a ring around the feet. However, they're not particularly easy to see in the visualization.

Of course, the visualization has limits and there may actually be significant points that aren't visible to the eye. There is a slight gradient around the neck that is overpowered by the range of concavities. For that purpose, ACD dedicates some time to find significant points on the body, also known as knots.

Useful Links

• Approximate Convex Decomposition Site
• Project GitHub

Iteration Flag

I've added a flag to the convex hull command so that I can limit the number of iterations that QuickHull would run. So for example, convexHullCmd -i 10 or convexHullCmd -iterations 10 would limit the algorithm to 10 iterations. I thought that this would be useful for debugging, but since the issues I faced were memory violations, I never got to use it.

Originally, the command would crash Maya. The fix was to update the registerCommand function and check for typos. getFlagArgument is very different from flagArgumentInt.

QuickHull3D / Half Edge Structure

I had been using shared pointers for ownership of my half-edges (the next variable owns the next half-edge). However, whenever I accessed them, I returned raw pointers and created new shared pointers when I wanted to transfer ownership. Little did I know that you can't transfer ownership like that. This may or may not have been the cause of my memory problems, but I resolved to replace all half-edge access with some sort of smart pointer just in case.

I kept the next variables as shared pointers and replaced the prev and opposite variables with weak pointers. It turns out that using weak pointers might have saved me a lot of headache, since it was easier to tell if a half-edge went missing.

There were a couple minor problems with the algorithm, but the biggest issue that I had was that weak opposite edge references would empty despite the corresponding shared pointer still existing. I ended up writing code to trace through the algorithm to give me some insight. Part of the struggle with tracing was receiving output via stdout or stderr. Maya redirects those streams to its Output Window, which of course is frozen when you're debugging. I ended up saving the trace to a log file.

With the log file, I was able to pinpoint where the opposite pointer reset, although it took a very long time, partly because Maya was slow to launch and partly because I was looking in all the wrong places. It turned out that my issue was in the destructor of Face, which somehow reset a variable that I didn't mean to. I thought that I had fixed this issue before. Yet if I had really looked at the code, I would've seen that I had two snippets of anti-circular-reference code that were at odds with each other.

In the future, I should rely on the debugger more. I thought that only a trace would reveal the info I needed, but looking back, I could have solved this in the debugger. Hindsight is of course 20/20, but it took so long to set up a trace log that I think it wasn't quite worth it.

Results

The code works now! Here is the dog:

Here is the rat:

For reference, you can see the original models here.

Next Steps

Now I need to implement the shape decomposition paper! I added this convex hull algorithm to get a rough "concavity" measure for each of the points. Then, you could essentially find the ridges of local maximum concavity to separate the model into parts. Hopefully I'll be done in time for the beta review of the project on 11/21.

Useful Links

• QuickHull Paper
• QuickHull3D Lecture and Implementation Notes
• John Lloyd QuickHull3D Java Implementation
• Mauricio Poppe JavaScript QuickHull3D Implementation
• Project GitHub

I do have some results though!

The dog made it to 30 iterations.

The rat crashed after around 10 iterations.

The markers indicate the positions of the simplex hull.

Useful Links

• QuickHull Paper
• QuickHull3D Lecture and Implementation Notes
• John Lloyd QuickHull3D Java Implementation
• Mauricio Poppe JavaScript QuickHull3D Implementation
• Project GitHub

Half-Edge Data Structure

The authors of the QuickHull Algorithm recommended a half-edge data structure for relatively easy manipulation of the convex hull mesh. Sometimes, faces need to be merged in case they might be coplanar, so such a data structure is needed. Maya doesn't use the half-edge format internally (it is index-based), so I had to create one that extends the Maya API myself.

I spent a long time wondering where the ownership of data would go, since there are several options (Maya, the Maya command, the QuickHull class root, or the half-edge data structure). I resorted to storing the vertex data in QuickHull and everything else in the half-edge data structure since Maya and the Maya command are too far removed. The data structure also appears to be extended to be doubly-linked on the half-edge and vertex level, which added some complicating factors to the data ownership problem. Because I saved vertex data in the QuickHull class, I was able to forgo the vertex list and pass around iterators to a vertex pointer list instead.

There are quite a few more notes to the implementation outside of the QuickHull3D lecture, so I referenced the original Java implementation as well as a JavaScript port that I found to be more readable. Unfortunately both languages don't use pointers, so figuring out what was a copy and what was a reference took some time.

However, now that the interface design for the classes is largely complete, I imagine that implementing the algorithm wouldn't take too much time.

I do want to note that I did find one Maya implementation of QuickHull, but it is not robust.

Visual Progress

So far I have been able to extend the initial plane to be 3D (which is nontrivial as described above). Here are the resulting images from Maya.

The hull mesh isn't green anymore! The polyPrimitveCmd example that Autodesk includes had some code that could add the mesh to the initial shading group. I also added locator generation to help determine which vertex was which.

Useful Links

• QuickHull Paper
• QuickHull3D Lecture and Implementation Notes
• John Lloyd QuickHull3D Java Implementation
• Mauricio Poppe JavaScript QuickHull3D Implementation
• Project GitHub

I had a misunderstanding of the simultaneous shape decomposition and skeletonization paper. It was clear that it depended on approximate shape decomposition (ACD) for the core functionality, but I didn't realize that convex hull generation has been essentially solved for a long time. I was reading through the paper trying to understand how they were able to calculate convexity with a convex hull without describing an algorithm for generating the actual convex hull.

I had a look through the Wikipedia page for convex hull algorithms, and QuickHull seemed to be a fairly popular algorithm that runs in a reasonable amount of time. So I've been dedicating resources to implementing that. So far I have the beginnings of the hull (as it starts with a triangle of the most extreme points).

The triangles are green because they aren't automatically added to the initial shading group. I'll need to look into a way to fix this next time so it's easier to see the geometry of the convex hull. It's also worth noting that the default name for a mesh is "polySurface1".

On the Overall Project

Developing a Maya plug-in has been an interesting experience. I had originally relied on the MSimple interface, which gives a simple way to create a command in Maya. However, because I'll need to depend on several different algorithms, I had to find an alternate way, which involves creating a central cpp file with initializePlugin and uninitializePlugin functions that register and deregister my commands. The polyPrimitiveCmd and pointOnMeshInfo examples that Autodesk provides have been especially helpful as well. The Maya API has an interesting approach to object manipulation to avoid memory issues, and actually going about implementing with it has been a lot more helpful than their documentation on it.

As I'm developing in Visual Studio, I've also found that it's a little difficult to use the default functionality where running the plugin involves starting up Maya and stopping involves closing Maya. Instead, I've resorted to building the plugin without running the debugger and copying the file to the appropriate plugin folder. Then, I don't have to restart Maya all the time.

I've also taken away the lesson that these research papers aren't necessarily self-contained bundles of knowledge. My previous experience with research has been with the SPH and IISPH fluid simulation. SPH is a fairly simple and novel technique at the time I believe, and IISPH was the product of a thesis which obviously contains all the details.

Taking in another look into the skeletonization paper, I've also learned that this algorithm may be insufficient for some special case scenarios. Obviously research papers try to present themselves in the best light possible, though I would have expected to see more counterexamples in the paper. As recommended by my advisor, I'll be planning to look into different algorithms to see which algorithm works best for production purposes. There's a paper by Wade that seemed to have spawned a number of derivatives that looks promising.

The goal next week is to finish the convex hull algorithm and start on the actual shape decomposition. I've included a very good link on QuickHull implementation below as well.

Useful Links

• QuickHull Lecture and Implementation Notes
• Convex Hull Algorithms
• Project GitHub

Maya requires a development kit to be downloaded. Due to certain outside restrictions I have to remain on Maya 2016 SP6, but they no longer have the development kit available on their usual channels... So I'm using a Maya 2016 SP1 devkit from their GitHub! Hopefully there weren't any important devkit changes between SP1 and SP6.

Maya 2016 also requires Visual Studio 2012 Update 4.

Writing the Plug-in

After looking through the documentation, it seems the best plan of action is to write a command for Maya that will perform the skeleton generation. I had originally thought that I would be needing a GUI, but that seems to something that scripting would be more useful for. I suppose that I could combine both scripts and plugins then!

Now just to put algorithms into code...

Quick Links

• Maya DevKit GitHub
• Maya Command Documentation
• Maya DAG Hierarchy
• Maya Poly API Classes

I had some familiarity with humanoid character rigs, and I was only just recently introduced to quadruped rigging. It was a lot more complicated than I thought! Specifically, I watched Delano Anthias's tutorial on Pluralsight. There are some things I hadn't accounted for:

• Scapulae are very important features in a quadruped rig. Imagine a tiger slowly walking towards you and how its scapula bones shift about. This is a bit of a unique scenario that needs accounting for. It was handle with a specialized scapula bone controlled by IK in a way.
• Quadruped legs are rigged different from human legs, since many quadrupeds walk on their toes. This introduces an extra joint that IK solvers don't play well with. But this is a problem for another time!

The control surfaces for the rig:

The internal skeleton:

The rig also has bendy joint chains, but that feature will have to wait. But it's worth noting how the spine consists of 2 straight chains in order to make rigging easier. As a result, the harmonic skeleton generator might not be as useful as I thought due to ease of use for the animator. I will also need to check out the wing rigging course on Pluralsight!

Maya Plugins

I started on an elementary UI for testing! First realization is that there's a difference between plugins and scripts. Scripts are inherently faster to develop, but they lack the low-level power that plugins have. In order to determine which would be necessary, we must first look at the requirements of the skeletonization algorithms.

Revisiting the Skeleton Generators

As determined earlier, we will be using a more generalized skeleton generator than the harmonic skeleton generator by [Aujay et al 2007]. One of the best methods seems to be the simultaneous shape decomposition and skeletonization by [Lien, Keyser, and Amato 2006]. It makes intuitive sense in its approach through shape decomposition, is fairly automatic, and can be tuned by a user. It might even open opportunities for manual adjustment of the decomposition. Such a feature might require a plugin to facilitate the adjustment process.

The shape composition relies on Approximate Convex Decomposition as described by [Lien and Amato 2007]. It essentially works by generating a convex hull (a nontrivial task) and scoring each vertex's concavity by its distance from the convex hull. Therefore, vertex access is required. It might be possible to achieve this through scripting, but the Maya API includes a very useful Polygon API for more direct access. There are also other procedures requiring access to connected edges also accounted for by the Polygon API.

Conclusion

Maya Plugins are clearly the best option. The question is whether to use C++ or Python. On one hand, I know C++ well, but Python is theoretically faster to develop in. Given that I have no idea what Python is capable of, I'll have to go with C++ unfortunately. I imagine that debugging and modifying data types will be a pain, but that's the price...

Next Steps

First step is to create a Maya plugin to get a sense of how the API works. Next, I'm still unfamiliar with all of the math involved in this one paper, so I'll need to read through it a few more times.

Quick URLs

• Maya 2016 API Documentation
• Maya 2016 Polygon API Documentation
• Maya 2016 Scripting Documentation

New References

• Lien, J., Amato, N.: Approximate Convex Decomposition of Polyhedra. In ACM Symposium on Solid and Physical Modeling (2007), pp. 121-131.

The abstract for the project proposal:

Character rigging is a time-consuming process in computer-generated media that is frequently left unoptimized. There are few tools for small studios and groups to use to rig non-human characters, and those that do require a hefty amount of user input. Automatic skeleton generation has been researched for quite some time, yet that have not been incorporated into production quality auto-riggers. Such generation algorithms are far from perfect, but they save time in many respects. This project aims to integrate those positive aspects of skeleton generators into a produc-tion quality auto-rigger for models of any shape, allowing non-human characters to be rigged quickly and without in-tensive training in rigging techniques.

The code will be publicly available here: https://github.com/meepzh/creature-auto-rigger

In particular, I hope to implement a shape decomposition-based algorithm and a harmonic function-based algorithm inside of a Maya plugin.

To make the algorithms usable in production, the auto-rigger will also involve control surface generation and other standard tools to ease the process of rigging for relative beginners.

The first steps will be to familiarize myself with Maya plugins and start implementing the algorithms.