Coder Corner

There is a new flag in PhysX 3.4 that tells the system to use tight bounds for convexes: PxConvexMeshGeometryFlag::eTIGHT_BOUNDS.

Use it.

Until now PhysX used a fast O(1) piece of code to update the AABB of a convex mesh, from its precomputed local AABB and the current world transform. That one’s a classic from the GD-Algorithms days, and I remember also spotting it in Charles Bloom’s public code years and years ago. If you want the details, see for example this file in the PEEL distro:

.\PEEL\Physics\Ice\APIs\Ice\IceMaths\IceAABB.h

And then look up the “Rotate” function, implemented there both for min/max and center/extents AABBs. This stuff is from 2000 or before, nothing new here.

There is no problem with this “Rotate” function: it’s great, we’ve been using it for more than a decade, and we’re still using it.

However, it obviously does not create the tightest possible AABB, since it only knows about the local un-transformed bounds, and it doesn’t know anything about the object contained within these bounds. That’s why for simple shapes like boxes or capsules we don’t use it: instead we directly recompute the sphere or capsule’s bounds from its data and current pose. This is just as fast, but also provides tighter bounds.

For convexes though, we never tried that, because computing tight bounds for them was more tedious. You either need to use brute-force and iterate over all vertices (which is a potentially expensive O(N) approach), or you need to do something more complex like maybe hill-climbing, etc: basically the same stuff as for GJK really, which has pros and cons I won’t go into right now.

Long story short: in PhysX 3.4 we tried the brute-force approach, and found that it significantly improves both performance and memory usage in scenes with piles of convex objects. The number of vertices in a convex is limited to 256 in PhysX, so there’s a limit to how expensive the computation can be, and we found it reasonable (iterating over vertices in a linear array is cache & SIMD friendly, so the worst case isn’t that bad).

Here are some results using PEEL’s “ConvexGalore2″ test scene. It’s a giant pile of convex objects falling, and it looks like this:

Here are the performance results with and without tight bounds. Blue is with the default PhysX settings, red is with PxConvexMeshGeometryFlag::eTIGHT_BOUNDS. There’s a pretty clear winner here:

It also improves memory usage, since the tighter bounds mean less candidate pairs are generated from the  broadphase, etc. This is again a clear win:

Granted: computing the bounds becomes more expensive, and if you have convex objects that don’t ever go close to other convex objects, using the flag might reduce performance overall. But I’d say that all things considered it’s one of these easy flags that you should just use all the time. It’s a small price to pay for potentially big gains. Visually the difference between the regular and tight bounds can be quite dramatic, as you can see for example here:

PhysX does not support native, implicit cylinder shapes.

The initial technical reason behind this is clear, and goes back all the way to NovodeX 2.0 around 2003. I was the first NovodeX employee and my job was to implement everything related to collision detection in this engine: broad phase, narrow phase, contact generation, raycasts, etc. We didn’t have a lot of time for research or experimentation, so I only briefly tried GJK / EPA and quickly ran into a wall: these algorithms were just constantly failing for me. Accuracy issues, infinite loops, etc. At the time I was able to reproduce some of these issues in SOLID 3.5 itself, which made me give up: even the reference version was failing and I just had no time to spend on productizing my “research code” (you know… works in the lab, fails in the field).

So instead I went with what I was familiar with, and implemented contact generation using a mixture of SAT and distance tests, with a dedicated function for each possible pairs of shapes. So for example box-vs-box would use a dedicated function to generate box-vs-box contacts, sphere-vs-box would use another function, and so on. With this design the cost of adding a new shape type, such as a cylinder, is high. To support cylinder shapes, one needs to write and add several new contact generation functions: cylinder-vs-box, cylinder-vs-sphere, cylinder-vs-mesh, etc. And none of these functions are trivial, since a cylinder is not the most friendly shape to generate contacts for. On top of that, the same problem exists for “scene queries”, i.e. one needs to write explicit raycast, overlap and sweep queries for cylinders. It’s a lot of non-trivial work.

This basic design (the same as in the old ODE library for example) survived until PhysX 3, for which we finally got the time to pause, sit down and revisit everything (not just collision detection: everything). We started playing with GJK / EPA again, mainly because Havok had been using it since the beginning, and it seemed to give them an edge in performance. New people joined, new code got written. It took a while to iron everything out, but in PhysX 3.4 we were happy enough with the results and finally switched to the new implementation, “PCM” (for Persistent Contact Manifolds), as the default contact generation method. Which means that in theory adding support for cylinders should now be as easy as adding a “support function” for cylinders (a trivial task), and that would be it.

However in practice, as usual, it is not that easy. Because under the hood, our PCM codepath still relies on the previous non-PCM contact generation routines to create the initial contacts, when two shapes initially touch. We do this to avoid issues and artifacts traditionally coming with the PCM territory. There are other ways to deal with those, as explained in the past IIRC by Erwin (from Bullet) and Gino (from SOLID), but that’s again something that always felt a bit experimental / fragile to me. And in any case that’s more code that we currently don’t have and have no time to research at this point.

That isn’t the main problem though. Beyond these implementation details, adding a new shape type still increases the support burden, the amount of code and classes, the potential for bugs, the testing & maintenance cost, etc. The only way to justify that now would be to instead add a generic “user-defined” shape where users would simply define their own support function, and this could be reused not only for cylinders but also for most existing shapes, or new ones like cones, etc - any convex shape. That’s what several other engines do, so that’s a viable option, and that way at least we would get some more gains & benefit for the price we’d pay. But it would still introduce an inconsistency in the API, since these new shapes would only be supported in the PCM codepath. And it could come with a performance cost if we use virtual calls into users’ code to compute a supporting vertex. And we still wouldn’t have a great way to generate the initial contacts for these shapes. And… and… and this is starting to sound a lot like analysis paralysis, which might explain why user-defined shapes are still an item on our TODO list rather than an actual, current feature.

—

The final nail in the coffin though is simply that we already have a perfectly fine workaround: just use a convex mesh instead.

People often don’t like this suggestion: they object that a convex shape is not going to be smooth enough to roll convincingly, and/or that a convex mesh tessellated enough to roll nicely would create performance problems.

As far as I can tell, both of these claims are incorrect.

I created a few test scenes in PEEL 1.1 to investigate.

—

The first scene features a single cylinder starting on an inclined slope and rolling away. The test is configurable and users can select the amount of tessellation for the cylinder. At the same time, since it’s PEEL, you can run the same scene with an engine that features “proper” cylinders (like Bullet or Newton - the Havok case is more questionable, see e.g. here). That way you can directly compare the motions and see if the cylinder that uses a convex mesh rolls more or less convincingly than the real thing. For me, with about 60 vertices in the cylinder’s base circle, I cannot tell the difference. But download PEEL 1.1 and see for yourself. (Use “RollingCylinder”, test 27).

Rolling cylinder

Another way to test this is to try one of the vehicle scenes, for example “ArticulatedVehicle” (test 76). In this test the wheels use convex meshes instead of “real” cylinders. You can change the tessellation level in the test’s UI, and see the effect on the motion. You have to pull the vehicle around with the mouse, as you cannot drive it in this test.

Articulated vehicle

If you want to drive, try the “VehicleTest” scene (number 245). Here again the cylindrical wheels are convex meshes. Use the arrow keys to drive the car around. Do you feel that the tessellation produces a bumpy ride? I don’t.

—

Now, the performance issue. Yes, certainly, using a highly tessellated convex mesh is more expensive than using an implicit shape. But this is only visible within the same engine. Beyond that, in practice, a tessellated convex mesh in PhysX can be just as fast, or faster, than a “real” implicit cylinder in another engine. Again, don’t take my word for it: download PEEL and see for yourself. (for example with “CylinderStack”, test 28). There is no performance problem using a highly tessellated convex mesh for cylinders, because generally speaking there is no performance problem using highly tessellated convex meshes in PhysX.

Cylinder stack

Besides, even if there would be a performance issue with cylinders, it still would remain isolated and only affecting cylinders. Unless your game features cylinders exclusively, it would be unlikely to make a dent in the framerate. In an actual game, the extra cost would be lost in the noise. Remember that there’s a lot more than physics going on in a game. Physics may have maybe a CPU budget of 20% of the frame. And then only a limited part of the physics budget is eaten up by contact generation (there’s also the broad phase, the solver, scene queries, etc). And then only a limited part of that contact generation time will be dedicated to cylinders. So even if the support function for a convex mesh is 10 times slower than the support function for an implicit cylinder, at the end of the day it doesn’t make the whole game 10 times slower. The way it is now, the overall performance impact should be quite small.

So in theory, yeah, you have a point. In practice, no, this is just not an issue.