search

humanoid-path-planner / hpp-fcl

An extension of the Flexible Collision Library
Other
272 stars 80 forks source link

Question About Specific Narrowphase Collision Algorithm #567

Closed Cfather closed 3 months ago

Cfather commented 3 months ago

Hi, I have a few questions about the collision-checking algorithm between boxes and spheres, since I noticed that there's one specific algorithm implemented in src/narrowphase/details.h:

  1. Is the algorithm in src/narrowphase/details.h faster than a general GJK algorithm applied on boxes and spheres?
  2. When I setup a box collision object and a sphere collision object and use hpp::fcl::collide or hpp::fcl::distance, will it call the specific algorithm in src/narrowphase/details.h, or still call the general GJK algorithm?

I would appreciate it very much if anyone could help me with this.

lmontaut commented 3 months ago

Hi @Cfather, For box-sphere, both hpp::fcl::collide and hpp::fcl::distance will call the specialized function in src/narrowphase/details.h. This specialized function is faster than running GJK+EPA on box-sphere, notably due to the fact that a sphere is strictly convex. This means that in this case GJK and EPA will do more iterations compared to a polytope-polytope collision pair, because these algos will try to "fit" the sphere with polytopes, which is costly.

At the moment, box-sphere takes about 40 nano-seconds with the current specialized function. If you instead use a box-ellipsoid (with radii = (r, r, r), r being the sphere radius) collision pair, which will use GJK+EPA behind the scene, you will be in the range of 0.5 to 1 micro-second (depending on whether or not the shapes are in collision).

Cfather commented 3 months ago

Thanks for the comments. This is very clear.