Constructive Solid Geometry Support

[Abuzer]

Hi,

I've been thinking about this for a while now, and it seems like CSG support for defining complex shapes based on primites would be a relatively easy thing to add to a physics engine such as BEPU.

While I could perhaps do it as a layer on top of what BEPU does internally, obviously it wouldn't be as fast as doing it natively inside BEPU.
Of course I'm probably simplifying things a good deal here, but for example, when doing subtractive CSG, the collision result would flip the normals if it's colliding the subtracted primitive and only processed if it is colliding the additive primitive(s) as well. Intersection would simply only evaluate the collision if the contact point is inside both (or all intersected) primitives etc.

This really hit me when I started to realize how painful it'd be without CSG to try to generate a relatively accurate dome shaped primitive using only the only available "union" method.

It'd be cool to hear if anyone has attempted this, or if there are some inherent problems with trying to implement such a system in BEPU.

Cheers

[Norbo]

The collision detection system wouldn't be particularly helpful for creating CSG built directly from primitives.

For example, imagine a small box subtracts out a hole in a larger box. Now toss a cylinder in there. Relying only on the existing convex-convex tests could give us a contact from each box. Each contact would be somewhere in the intersection volume of the cylinder and the collided box. The collision normal would point in the direction of minimum penetration depth for that convex pair. That's simply not enough information/the wrong information to create a contact manifold with the concave interior of the CSG shape. (A proper contact manifold would include contact points representing either the closest points of approach between the CSG object and the collider or contact points which represent a point in an intersection volume between the CSG object and the collider which have a normal pointing in the direction of minimum penetration depth.)

While you could attempt to implement this, it would be a lot of work and the existing engine components would not help you very much.

If a compound shape representing the desired volume is too complicated, there's always the option of a MobileMeshShape. Approximations are preferred over the mobile mesh where they can work for performance reasons, but mobile meshes do have their purposes.

[Abuzer]

I see your point about the subtractive operations. In a sense, perhaps one would need to evaluate a 3D distance field and extract the direction of minimum penetration depths along the CSG surface. Though are you saying that incorrect direction of minimum penetration could result in completely unresolvable or broken looking situations? I mean if an object is simply pushed out in a slightly offset matter, hoping that the simulation is running fast enough, would it even be noticeable?

How about intersections? Same deal? I'd imagine, most of the time, one could check the penetration depth on both primitives in the intersection, and weight the "new penetration depth" based on how small each penetration depth is (i.e. use the inverse of the penetration depth as the weight for the final penetration depth). This however is just me attempting to solve perhaps just one of the potentially many other intricacies that I don't know about in the depths of BEPU

My thinking is that every physics engine has its limitations that are within reason. If something doesn't work quite the way the developers had hoped for, they need to recognize that and work around it. So if such an engine returned OK looking results with most of the CSG primitive setups, then it's "good" in my book, but perhaps (and I wouldn't be surprised to hear that) you're seeing issues that are deal breakers with this idea.

[Norbo]

Though are you saying that incorrect direction of minimum penetration could result in completely unresolvable or broken looking situations? I mean if an object is simply pushed out in a slightly offset matter, hoping that the simulation is running fast enough, would it even be noticeable?

Approximations are possible. Technically, the general convex-convex deep intersection case is an approximation now, though it does usually converge to the true minimum.

However, the contacts need to be consistent (for a particular definition of consistent). If it generates a different approximation under similar circumstances every single update, the simulation will fall apart in a very bad way. Guaranteeing such consistency is not trivial; right now, all the tests I can think of which leverage only what already exists in the engine would result in significant problems for CSG.

For example, if a whole bunch of tests were applied between two objects, consistent contact data should be able to conceptually reconstruct a reasonable representation of the geometry of those objects. Inconsistent tests would make this representation a fuzzy, glitchy blob. Fuzzy, glitchy blobs do not work well

How about intersections? Same deal? I'd imagine, most of the time, one could check the penetration depth on both primitives in the intersection, and weight the "new penetration depth" based on how small each penetration depth is (i.e. use the inverse of the penetration depth as the weight for the final penetration depth). This however is just me attempting to solve perhaps just one of the potentially many other intricacies that I don't know about in the depths of BEPU

Since the intersection of two convex objects is still convex, I'd guess that it would be more feasible to get it 'working' this way than subtraction. Attempting to use per-body tests will still be difficult since they don't directly provide the needed information.

For example:

moreproblems.jpg (30.55 KiB) Viewed 29812 times

While you could do some blending to get a not-terrible approximation of the normal here, the location of the contact is unknown. The sphere-box contact tests would give you a contact location somewhere in the intersection between the box and the sphere collider, most likely in the middle of the arrow. In order to have any chance of decent collision response, the contact has to be put somewhere in the intersection of the sphere and the CSG intersection volume. Sadly, the tests did not tell us anything at all about where that might be.

If you could define a support mapping representing the intersection volume, that would allow you to most directly make use of the existing tests. At that point it would just be another ConvexShape type, like the MinkowskiSumShape or WrappedShape. However, defining such a support mapping is not trivial. It is also not immediately clear how such an approach would mesh together with subtractive geometry.

My thinking is that every physics engine has its limitations that are within reason. If something doesn't work quite the way the developers had hoped for, they need to recognize that and work around it. So if such an engine returned OK looking results with most of the CSG primitive setups, then it's "good" in my book, but perhaps (and I wouldn't be surprised to hear that) you're seeing issues that are deal breakers with this idea.

Unfortunately, the built-in tests just don't support general CSG by themselves. The information content their sampling provides is fundamentally different. The problem is less 'this has a few behavior quirks' and more 'this does not work' in general. Solving individual pieces of the overall problem with tricks is possible, but a usable solution requires a single general approach which works consistently.

Now, it is likely possible to create a form of CSG which incidentally leverages some of these built-in tests, but the primary logic of the process will be quite separate.

And despite all of this negativity, implementing a CSG shape is definitely possible, it's just not easy and I personally do not have the time to do it

[Abuzer]

Thanks Norbo. I appreciate the detailed explanations and imagery.