Defining collision w.r.t. osculating surfaces

[SeanCurtis-TRI]

Fundamental question

If two surfaces are perfectly touching (i.e. zero distance and zero penetration), are they "colliding"?

Example

There is a unit test which places a sphere and box in perfect osculation. The sphere is centered at the origin and the box is displaced along the x-axis a distance equal to the sphere's radius plus 1/2 the box's size (in the x-direction). Mathematically, they are perfectly touching. This uses the GJKSolver_indep to determine collision and, historically, this has been considered a collision.

Problem

Historically, GJKSolver_indep has used 1e-6 for the gjk_tolerance. With this tolerance, the test passes. As the tolerance gets "tighter" (i.e., smaller) the behavior is preserved. Until we cross from a tolerance of 1e-10 to 1e-11 (and smaller). With this tighter tolerance, the solver converges to deciding that the sphere and box do not collide. One would expect as the tolerance decreases, we're converging to the "true answer".

Arguments

It's worth noting that the solver only considers a collision to exist iff the GJK solver classifies the origin as being inside the minkowski difference. It's worth noting that that's a necessary but not sufficient condition -- the EPA solver must also report successful (aka Non-Failed) status. So, if the GJK status of "inside" is to be taken at face value, one would assume that osculating surfaces should fail this test.

So, the question is, should two surfaces with a distance of zero between them be considered a collision?

Votes and comments please?

P.S. For the unit test in question, it should explicitly set the solver tolerances which distinguish between collision and non-collision.

[sherm1]

Argument for why "kissing" contact (exactly 0 penetration) should be considered a "collision":

• A common use for FCL geometry is to track contact in simulation
• Contact is often modeled as fully-rigid objects constrained not to interpenetrate
• When that constraint is enforced perfectly, the penetration is held exactly at zero
• Thus the contact model needs to generate non-zero forces at zero penetration, which it can only do if that is considered a contact.

When contact is instead modeled using compliant (soft) surfaces (also common) the contact force is a function of the penetration depth. A 0-depth contact thus produces 0 contact force, which is not very interesting but is still correct. So saying "yes, contact" at 0 depth works for both kinds of models but saying "no" means the rigid ones can't generate forces then.

[SeanCurtis-TRI]

So, the question is, does the distance query serve that role for rigid contact? And if distance queries do, should collide also be constrained to provide the same functionality?

Big "if" there. I don't know that the distance query does serve that role. It presumes that distance is signed distance implicitly reporting separation and penetration. If it also breaks down at distance == 0, then having collision handle this makes sense. In which case, the code would be considered incorrect.

[jmirabel]

To put in my two cents: your question is case-dependent. Instead of a binary answer, couldn't it return an enum like one of (COLLISION, CONTACT, SEPARABLE) ? Maybe with thresholds tunable by users ?

[SeanCurtis-TRI]

@jmirabel I like your suggestion. It should give us a basis to reasonably expect results based on thresholds and configuration. That gets my vote as well.

[sherm1]

I would want to make sure we're not just punting a hard decision from people who have thought about it a lot to people who haven't! It would certainly be useful to be able to specify a non-zero margin to make collision query report on near objects as well as contacting ones. That's not a tolerance in the algorithmic sense though. And the margin would have to be known to the broad phase as well to prevent early weed-outs.

[SeanCurtis-TRI]

One thought to consider -- if the algorithm converges to defining osculation as not colliding (as the tolerance levels get tighter), then, at the very least, we should consider that the current implementation implies that osculation != collision and it should be documented and supported in tests.

The next question being whether that behavior is correct can then be dealt with in a subsequent endeavor (and a much more painful one to get the code to agree).

[SeanCurtis-TRI]

@jmirabel in retrospect, I'm taking my vote back.

Ultimately, FCL should provide a signed distance value φ between two geometries (to within some user-specified tolerance). The interpretation of that distance should be left as a user function on φ.

The definition of two objects "colliding" is simply syntactic sugar on top of that. We've taken the domain of φ and said this function, collide() will tell you about object pairs for which φ < 0 (as current implementation seems to suggest) or φ <= 0 (if we choose to define and support this definition).

If we wanted to add a user parameter such that collide() becomes φ - d < 0 as the definition of collision, we'd have to modify the entire infrastructure. The broadphase algorithm tightly bounds the geometry and seeks to ignore all cases where BV-overlap tests conservatively detect φ > 0. We'd have to push the padding into the broadphase algorithm.

[jmirabel]

The definition of two objects "colliding" is simply syntactic sugar on top of that.

From a theoretical point of view, yes. From a computer scientist point of view, the difference can be up to 8 times faster... The question is to know whether you can have a richer answer than a boolean for the same cost.

Will φ <= 0 or φ < 0 make much difference with floating-point number ? I would say that in case φ==0, collide is sufficiently bad conditioned to be avoided and distance should be used instead.

We'd have to push the padding into the broadphase algorithm.

Yes, I agree. It is not simple to implement. This is related to #276 .

Anyway, my suggestion was a mere thought with no deep

[SeanCurtis-TRI]

I completely agree with what you're saying.

The collide() method is all about exploiting the fact that we're cutting down the domain of φ to our computational benefit.

So, my final proposal is that we document and have supporting tests for the current behavior: that collisions are defined as φ < 0. If we deem later that we want the missing equals sign, then we dig through the internal implementation (and possibly libccd) to determine what it would take to have it converge to that new reality as tolerances go to zero.