3D convex hull SAT face clipping implementation question

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
BeRo
Posts: 8
Joined: Fri Apr 17, 2015 5:50 am
Location: Moenchengladbach, Germany

3D convex hull SAT face clipping implementation question

Post by BeRo »

Hello guys,

i'm rewriting my old 3D physics engine PAPPE in the moment, which I wrote in anno 2007, because it was buggy as hell. The rewrite is almost complete now (except continuous collision detection), but I've some open questions yet, so the first question here (the other second open "which CCD&CP solution is the best for discrete->CCD&CP code upgrade case" question will be a own forum topic later).

Is it the (or also a) correct way, that the reference face for 3D convexhull(HullA)<->convexhull(HullB) SAT clipping in my implementation is always on HullA, and the clipping incident face always on HullB? At least, in this case the contact points are always directly automatically coherence and consistent/ without plane reprojection (among other things for warm starting for the nearest new->old feature-ID-key-free contact point search between last and current frame). It seems, that Bullet does also in this way. At least this way implementation works pretty well so far for me, and I saw no failure cases at my tests so far.

The alternative way should be that a face from HullB could also the clip reference face (rg. when face B SAT seperation > face A SAT seperation), where the contact points would be projected to the HullA in-this-case-now incident face then, but will be it the more correct way? It seems, that the most other open source physics engines and collision detection libraries, which I could find (but not Bullet), does it in this way.

Or in other words, what are the pros&cons of the two possible face-face-clipping implementation ways?

My code of my 3D convex-hull-vs-convex-hull collision detection => http://pastebin.com/J0yjHMh6

A physics engine test youtube capture video of my physics engine => test https://www.youtube.com/watch?v=QGO5Bk1JdbM
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: 3D convex hull SAT face clipping implementation question

Post by RandyGaul »

In Erin Catto's code he starts out detecting collision against colliderA vs colliderB. Once the axis of minimum penetration is found he renames the collider's face it came from as the reference face. Then then most anti-normal face on the other collider is named the incident face. The incident face is clipped against the side planes of the reference face, and all resulting clipped points are culled by a plane test against the reference face (keep points that are penetrating). This gives you clip points that contribute to the manifold in an intelligent way, without generating too many unnecessary clip points.

Since features could have come from either colliderA or colliderB, Catto uses an if statement near the end of his collision routines to make any necessary bookkeeping swaps.

Another thing that Catto suggested (and Dirk in his recent GDC presentation on contact creation) is to bias which collider contributes to the reference face, to prevent excessive feature flip-flops (which makes the final if-statement prefer one code path over the other).

As far as I know this kind of technique is what is used for modern SAT implementations. To me the face naming mostly seems to be a code abstraction, and not much more. As long as your clip points contribute to the manifold in an intelligent way, it probably won't matter how you obtain them (aside from memory/performance).
BeRo
Posts: 8
Joined: Fri Apr 17, 2015 5:50 am
Location: Moenchengladbach, Germany

Re: 3D convex hull SAT face clipping implementation question

Post by BeRo »

Okay, thanks, so as I have now implemented it in my physics engine, where I'm pushing now the respective clipped vertices (of shapr A or B) to reference plane of shape A, regardless of which shape (A or B) is the reference convex hull and which (A or B) is the incident convex hull, so that feature flip-flops are prevented.
Post Reply