Use FCL's broad phase

[tobiaskunz]

FCL includes functionality to smartly organize objects/link into a data structure such that not all pairs of them need to be checked for collision. We are currently not making use of that functionality and instead check all pairs for collision.

[scpeters]

I've been running some benchmark tests with a variable number of rigid bodies in a scene. Even without contact, the computational time scales superlinearly with the number of bodies for dart with FCL, while the other physics engines had roughly linear scaling.

[mxgrey]

Are the bodies in your test primitives or meshes? Or are they a mixture?

(I ask because speed differences could also be related to issue #19)

[jslee02]

Boxes are all converted to meshes for FCL, and each box mesh has 12 triangles. So they are all meshes.

[mxgrey]

I worded my last comment poorly. I've revised it.

[jslee02]

It's partially related to #19, but unfortunately, FCL is not ready to use primitives for DART because of these issues (flexible-collision-library/fcl#15, flexible-collision-library/fcl#8).

I'm planning to make some changes for the issues and create pull requests. The major changes would be:

• supporting multiple contact points for primitive shape collision
• making sure consistent normal directions

[tobiaskunz]

While fixing #19 could improve performance in general, the issue raised by Steven has nothing to do with #19 and fixing #19 would not improve it. He did not compare absolute computation time, but the change in computation time with increasing number of bodies. Making use of FCL's broad phase could potentially improve this.

[jslee02]

@tobiaskunz is right. That's why I added "partially" but Tobias's explanation is more precise.

[edit]
This is my understanding. Fixing #19 will improve performance in general, and using broad phase algorithm will improve the nonlinear increase of computation time as increasing collision objects.

[jslee02]

Addressed by #631