Thoughts about (Narrowphase) Collision Detection Approaches!

[MShonoda]

Hello,

I don't have much knowledge about the field (I am a beginner) ... so I have some -random- thoughts and I will highly appreciate to hear feedbacks/comments. (I am trying to build a big-picture in my mind)

-> The most well known algorithms for the narrowphase CD are: V-clip, GJK, Lin-Canny (I heard about SWIFT, I did not read about it though) ..... well, most of these algorithms are 'old'! (they back to ~~ 15 years back -- Please, don't get me wrong here, kinda there is no out-dated thing in our field, but.. during the last 15 years, what happened? just enhancements or.. ?)

My questions:
- What are the current methods/approaches that are considered to be the "state-of-the-art-methods" for CD? - (it depends, but generally.. ?)
- What are the -best- known enhancements to the mentioned ones?

- These algorithms are categorized by: feature based or simplex based approach -> Is there any other approach(es)?

Thanks!

[Dirk Gregorius]

I think the methods you mention above only work for *disjoint* shapes. In the penetrating case you need a different algorithm like e.g. EPA or XenoCollide. From the three algorithms you mention I would argue GJK is the most popular. Note that these algorithms give you either closest points (in the disjoint case) or the smallest direction to resolve the penetration. Building contact points on top of these algorithms is something else. E.g. you can build incremental manifolds collecting individual points over several frames or you can use a clipping approach to find the full manifold. I recommend looking at Bullet, ODE and Box2D for implementation ideas.

There is also a library called LibCCD which implemented a bunch of colliders in the ODE recently. I haven't looked at it, but it might be worth to investigate.


HTH,
-Dirk

[MShonoda]

Thank, Dirk, for your information/thoughts.

V-clip works in the penetration case, but yes, building contact points on top of these algorithms is something else since they don't return all the points of contact, and the other two doesn't handle the penetration case.

I will look through all the information you mentioned! :)