This morning is a momentous occasion. I am emptying my Inbox. Often people send me messages like “… so-and-so was calling me names, please do something…” or “yo dude, give me a custom character plz…”. However, occasionally I get some interesting questions to which I send a thoughtful response. I’m going to start posting some of these. The first is from MrDoomBringer, with whom I exchange several messages a week.

MrDoomBringer writes:

Hey, I just had one of those brain zap things, an “idea”.

We keep talking about having new meshes, but, why not just allow new brick models?

As for that matter, how are the brick collisions calculated? The head mesh throws it off a bit, I know that, but how do you calculate the collision between a brick and a cylinder? If the code for the collisions could be edited to just look at the outside edges of the model, then it would be easy to make a sloped brick, or a curved one.

Of course… I have no clue how to do this, I’m speculating on other code that I have worked with…

Your question touches on two issues: parametric/custom parts and simulation efficiency.

The Roblox team has been thinking about adding additional parts to Roblox for a long time. The obvious way to do it would be to add a 3d modeler tool to Roblox Studio that would let you build your own meshes and then create parts out of them. This is probably not a great idea, since 3d modeling is very hard and writing 3d modeling software is not my idea of fun. The way we would introduce new parts would probably be to make parametric parts. For instance, we might make a Window part that you could resize however you wanted, and Roblox would automatically make a nice Window mesh for you, of any size or style that you chose.

But to answer your question more directly, we don’t do general-purpose mesh collision detection by default because it is very slow. The only shapes the Roblox physics engine has to worry about right now are boxes and spheres. That means we have to be able to detect 3 types of collisions: Sphere-Sphere, Box-Box, and Box-Sphere. All of these tests are relatively quick to compute – in particular a Sphere-Sphere test is a trivial application of the distance formula.

To do general-purpose (often called “Triangle Soup”) collision detection between two objects is very slow. Say I have two user-made meshes that both contain 1000 triangles. I basically have to do 1000^2 tests to see if the two soups are colliding. You can do a little better if you enforce the constraint that the meshes have to be “water-tight” – meaning that there is no path that can be drawn from the inside of the mesh to the outside of the mesh without passing through a face of the mesh.

The best way to test for collisions between two “water-tight” meshes is to break the meshes up into convex hulls (if the mesh is not already convex). This can be done once, at resource load time, so does not hurt performance. But then you have to do convex hull collision tests. With various gnarly optimizations you can do these in O(lg n) time against Spheres and Boxes, and O(n lg n) time against other hulls. In comparison, all current collision tests can be done in O(1) – constant time.

The bottom line is that we will need to add convex hull collision to the engine someday, but that in order to get good performance we need to be very judicious in choosing when to do the more expensive collision test and when a simple sphere will serve to approximate an object’s geometry. If we did convex hull collision by default and a user makes a pile of 100 rocket launchers, the result is not going to be good. It’s a bigger problem that it seems, which is why it was not thrown into the physics engine when BM first wrote it.

If you are interested in learning more about collision detection in games, here are two excellent sources of information:

Collision Detection Article on WikiPedia

Intro to the SAT (Separation of Axes Theorem)

– Telamon