Convex tools

Been a while since I've made one of these, but there has been a lot of moving around town over the past couple of months. Now that things have settled down, I figure I would talk about something a bit more objective that I've been exposed to over the past couple of weeks.

Why is it that there are no good convex mesh generators for 3dsmax? Since almost every game engine out there uses convex collision meshes I would have thought that there would be at least some robust tool from many versions ago that works well enough is has now become an old defacto like Crazy Bump for normal maps. But there isn't anything like that, not that I found anyways.

Maybe a lot of the new game engines have started incorporating such a tool internally and creating whatever collision mesh they need straight from the imported asset, which is good. But what about all those engines that don't have that capability, or if they do, don't generate accurate enough results?

Necessity being the mother of all invention, I decided to write my own convex mesh generator based on the implementation seen in Unreal; a box sliced at 45 degree angles to fit the source object. The process from start to finish took roughly 4 days with a complete rewrite from scratch at one point.

The original implementation had me looking at all the verticies of the source object, finding the min and max XYZ, and then use that information to create a 26 polygon "sphere" around the object. The problem with this implementation is that it didn't always create a purely convex object and it wasn't all that tightly wrapped either. So I looked closer at what Unreal did and it seemed to me that the collision mesh was being cut only on 45 degree angles, and stopping when it hit the closest vert along any edge.

Ok, sounds simple enough: create a bounding box, bevel each edge at a 45 degree angle until it intersects a vertex, repeat for all edges until the object looks like some weird abstract art. Normally this would be a simple tast for an experienced programmer who has vast knowledge in 3d math and world space, etc. But for an artist working in 3dsmax with max script, the problem was a bit more complicated. Sure there were a lot of helpful functions available for figuring stuff out, but there wasn't anything like "vertex intersects plane" which is what I really needed.

I reused the code for generating that sphere and simplified it into a box, hence starting with the bounding box that I needed. Now that I had the box I was ready to slice it along all of it's edges at 45 degree angles. I placed my slicer objects in the middle of each edge and rotated so it faced 45 degrees out. But the problem remained of how to move the slicer to the closest vertex?

I could use a length or distance function to get the distance to the closest vertex, but because the origin was in the middle of the edge, I only had one point of reference, and usually the closest vertex wasn't the one closest to the middle of the edge. Sure I could subdivide the slicer and give me a lot more sample points, but that seemed like overkill, and not guaranteed to give the most accurate results. Maybe I could calculate the vector to each vertex and find the one with the lowest angle? Hmm, that could work. So I asked one of the render programmers about his thoughts, and he gave me the most ideal solution: find the distance from the plane to the vertex. Heh, well yes, of course. But how to do that?

Calculating the distance from a plane (considering it was infinite in size) to a point in space is a simple matter when it's aligned to on the major axis's. You simply move the sample point right under, or over, the point in question and calculate the distance. The problem with this is that it gets much more complex when the plane is rotated. So I was almost there, I just had math standing in my way :)

One of the things I had forgotten about max is that it allows you to select a different coordinate space! But would a different coordinate space always give me the necessary measurements in THAT coordinate space? Or would it still be all in the world coordinate space? Well, as it turns out, it did! Problem solved!

Finally I had my bounding box, I had my aligned slicers, and now the final piece of the puzzle was solved too. Since I was in the slicer's coordinate system, figuring out the distance to the closest vertex was a snap since now everything acted as though it was aligned to a major axis. With that out of the way, the slicers got moved in, the bounding box cut, and there we have it, a purely convex and simple mesh surrounding the arbitrary source object.

Now while the might seem like a very round about way to going about creating this convex mesh.. and not very quickly I might add, it works every time. Save for the rare instances when the boolean operation messes up and produces artifacts. But the principal is sound. Surprisingly I'm not sure how I could optimize this script other than maybe use a function for a couple repetitive calculations. It makes me appreciate just how slow scripting languages can be compared to compiled, and even interpreted languages. But it also gives me a great satisfaction to know I've just created a script that can save hours, maybe days of manual work for artists all around the industry. And I've proven to myself that stuff like this can be taken on by artists too, not just programmers :)

If you're interested in check the script out, visit my website (www.renalicious.com) and see the Tools Portfolio section for the max tools.