Principal Component Analysis, Collision Volumes and You

It's been a loooong time between posts, and I guess a lot of distance as well.  This whole AAA business really takes it out of you :P

One of the last major coding projects I did before the awesomeness of asset wrangling hit me was an idea I had about auto collision volume creation.  My dream is to automate everything, leaving artist to worry about the big stuff, and collision volumes isn't something they should worry about.  So I started searching for a solution to my plan:

1. Find a way to automate the creation of best fit Bounding Box, Bounding Cylinder and Bounding Sphere collision primitives, mainly for environment art/props but could work for characters.
2. Find a way to automatically partition an arbitrary mesh into smaller parts to create bounding volumes.

This post will be addressing part 1.


First lets talk about bounding volumes, specifically bounding boxes.  There are 3 main types of bounding boxes:

1. World Space BBox:

This is where a bounding box is generated from the model's verts translated into world space.

2. Local Space BBox:

This is where the axises of the bound box are translated into the same local space as the model before being computed.

3. Oriented BBox (OBB):

This is the trickiest BBox to compute and the one mostly created by hand/eye by artists.  It's hard to compute because we're looking at an arbitrary cloud of vertex data with no reference orientation.  Sure we could use World or Local BBoxes but they don't really get the job done when you want a tightly fitting BBox.  Another advantage to Oriented BBoxes is that, well they're oriented.  This means that they not only fit the model very well, but they are also transformed correctly, this is very handy later on when you want to compute oriented bounding cylinders and capsules:

 

How the hell do we calculate an Oriented BBox you might ask?

The first solution I discovered wasn't very pretty.  Basically you just rotate a bounding box around the model (well really rotate the model around world space) and calculate the world space BBox for each rotation.  Repeat this A LOT and take note of the volume of each BBox and pick the BBox with the least volume.  Problems here are this can take a long time and it's not very accurate.  This might be ok for packing algorithms but not for our purposes.

Next I found out about PCA.


 PCA stands for Principal Component Analysis.
Here's the obligatory wiki entry for it:
http://en.wikipedia.org/wiki/Principal_component_analysis

Basically, given a random collection of points, ie mesh verts, PCA picks out the "best fit" vectors.  PCA is traditionally used in a lot of statistics maths but like most algorithms it's found a place in 3D.

Here's the pic from Wikipedia:

If you want to know how this works, PLEASE go and read this excellent tutorial by Lindsay I Smith:
www.cs.otago.ac.nz/cosc453/student_​tutorials/​principal_​components.pdf

It helped me no end to break down how to actually implement this.  It's been a while since I did this so I'm not going through the exact process here.  I basically made sure I had what Standard Deviation,Variance, Covariance and Covariance Matrix meant in my head, and wrote code to calc these values from a set of verts.

There's always a dirty word with these projects, and this time it's "Eigen"!  Well Eigenvectors and Eigenvalues to be exact:
http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

In true coding by numberz style I reached for the closest open source library I could find to calc Eigenvectors and Eigenvalue: Eigen!
http://eigen.tuxfamily.org/index.php?title=Main_Page


From Lindsay's article, here are the main steps:
Step 1: Get some data
Step 2: Subtract the mean
Step 3: Calculate the covariance matrix
Step 4: Calculate the eigenvectors and eigenvalues of the covariance matrix
Step 5: Choosing components and forming a feature vector

Steps 1 to 3 I implemented in Maxscript.  They're all pretty simple stats stuff.  Step 4 is a bit more tricky and this is where the Eigen library steps in.

I integrated the library into the 3DS Max SDK and exposed several functions to Maxscript.  Sorry peeps, I don't own any of the code so I can't post it here.

Here's a vid of the final tool in action with "Simple Arse"TM UI:



play video



 So that's got the automation of individual parts done.  Now for the big question:

How the hell do we automatically split up a model into primitive shapes?

Did somebody say "Approximate Convex Decomposition of Polyhedra"?  I hope so because that's where I'm going with this.  I've done A LOT of study on this sort of thing over the years and was quite chuffed when I wrote my first convex hull generator in the 3DS Max SDK.

Here's a link to mad SIGGRAPH scientist who came up with this concept:
http://masc.cs.gmu.edu/wiki/ACD

I've read through the paper and it's not that difficult, just very involved and I haven't been able to justify the time cost in developing a product.  The basic idea would be:

1. Preprocess the models mesh to identify any non contiguous mesh, open edges etc.  Either treat these separately or create a shrink-wrap mesh around the original mesh.
2. Decompose all resultant mesh elements into approximate convex parts.
3. Generate best fitting bounding volumes or convex hulls from approximate convex parts.
4. Run some quick tests to optimize volumes.  If for example a part of the mesh was very pointy you could reduce the size of the volumes so they were slightly inside the mesh, giving a more realistic physics volume.

That's the plan anyway.  Peace out.