TRI is considering investing in FCL development about fcl

[florent-lamiraux]

My team and myself use fcl for path planning. A while ago we forked our own branch (https://github.com/humanoid-path-planner/hpp-fcl) to develop features that require to modify many interfaces. As the project was not very active at that time, we did not submit any pull request.

The main modifications are the following

• 1. computation of a distance lower bound when checking collision and when the objects are not colliding (on demand)
• 2. computation of closest points in the global frame: in the current version, the frames in which points are expressed are not the same for all pairs of primitives,
• 3. repackaging using standardized cmake rules.

Point 1 is required for dynamic collision checking along paths and costs a negligible overhead in terms of computation, compared to computing exact distance.

I think it is a good idea to take fcl as a basis for an open-source project supported by TRI. It could be an opportunity for us to merge our modifications. However, I would start the TODO list by

• selecting which part should be developed and which part should be removed. For instance "articulated_model" does not seem to be really implemented and should be handled outside fcl (in my opinion).
• documenting exiting code.

[mamoll]

Not sure if I count as an fcl leader, but these sound like very useful additions.

[stonneau]

Hello,
Hello everyone,
I hope I'm not delving into too much details, but would like to mention two others features
of the fcl fork mentionned by @florent-lamiraux, which may answers issues expressed by @jslee02 .

Regarding the contact point computation, we found the same issue to occur when colliding objects of different types, which results from the fact that methods are found in a diagonal look up table, which sometimes require inverting parameters (though the Collision results do not take this inversion into account). Our quick and dirty fix is here (our objective was to have a minimal impact of the code,
but this is not satisfactory):
humanoid-path-planner/hpp-fcl@177fb1f

Similarly the triangle ids resulting from a collision with an octree were wrong:
humanoid-path-planner/hpp-fcl@fdd6d8d

[sherm1]

One might hope that Gonthier's 2007 mathematical formulation has already been instantiated for simple analytical shapes into a library

Yeah, one could hope! But when I asked about it I was told by McPhee lab ex-pats that it is an extremely difficult calculation except for the simplest of shapes. There is apparently a Canadian company that offers a GPU-implemented numerical method for calculating the necessary volumes but they are doing it by sampling so probably can't deliver smooth derivatives. @edrumwri, how are you able to do it?

[arocchi]

@stonneau

in the end did you backport any of the modifications you previously mentioned from hpp-fcl back to fcl, and if no, are you still planning on doing so?

Thanks!
Alessio

@sherm1
I created a pull request for the second issue.
#114

and raised an issue for the first one.
#115

Three others modifications of fcl were performed in hpp-fcl, as mentionned by @florent-lamiraux:

1. computation of a distance lower bound when checking collision and when the objects are not colliding (on demand)
2. computation of closest points in the global frame: in the current version, the frames in which points are expressed are not the same for all pairs of primitives,
3. repackaging using standardized cmake rules.

These modifications are less trivial that the previous one, because they required a significant modification of the code.

We would like to integrate them to fcl (at least the first 2 points), which would allow us to use fcl in our projects rather than our fork. However, since this require significant work from us, we need confirmation that the fcl leaders are actually interested in those, and that they will be indeed included.

Thanks

Steve

[isucan]

This is excellent news!
For your questions:
1: I believe FCL is the best place for this, yes.
2: This is a longer discussion, but I think we can build a list of TODOs by inspecting / trying to add extra docs & unit tests. An e-mail to moveit-users / ros-users would be a good idea to see what features people use or would like to have. Benchmarking more of the algorithms is also a good idea.
3: I just made the teams publicly visible.
4: I guess trying to address some of the points in 2?

[jslee02]

Yeah, it's great news! I'm glad to hear that FCL is going to have more development support.

2: This is a longer discussion, but I think we can build a list of TODOs by inspecting / trying to add extra docs & unit tests.

I agree. Here is a short list from my experience and other's feedback:

• Incorrect contact point. The binary check whether the objects are in contact seems to work fine, but the computation of the contact point are not always correct. #106
• Multiple contact points (or contact manifold) for primitive shape collision. In dynamics simulation, multiple contact points are important when it's not a point contact (e.g., line/face contact) to put an object on the other object.
• Lack of consistent general fcl-philosophy for calculating contact point, depth, and normal. This was brought by @gdbaldw and @gdbaldw might have more idea on this. The mid-point of the intersection volume for the contact point seems the implicit rule, but the definition of the mid-point is not consistent across the individual shape-shape collision algorithms.
• Slow performance for mesh-halfspace collision check (compare to mesh-plane collision check).
• Detecting an object that is fully inside of another object (mesh) reported by @olzhas and #78.
• Benchmarking with other well-known libraries like ode and bullet.
• heightfield support.

There would be more items I can't come up with at this moment. I can help writing unit tests that reproduce the issues.

[mamoll]

Excellent news indeed! I am more of a user than a developer of FCL. On the motion planning front, sampling-based planners could probably do more with the information that FCL can provide (such as penetration depth / separation distance or vector to closest point). It might also be good to send emails to key researchers (Jia Pan @panjia1983, Dinesh Manocha, others?) who were/are involved in developing the algorithms behind FCL to make sure that FCL continues to be a library of state-of-the-art collision detection algorithms.

[sherm1]

@isucan: 3: I just made the teams publicly visible

Hmmm ... I still can't see teams. Could be a delay, or maybe I have to be a member of the organization? Would you mind adding me to a team?

[isucan]

That's odd, it should be visible (I checked again just now). In any case, I
added you as well.

On Fri, Mar 18, 2016 at 10:16 PM, Michael Sherman [email protected]
wrote:

@isucan https://github.com/isucan: 3: I just made the teams publicly
visible

Hmmm ... I still can't see teams. Could be a delay, or maybe I have to be
a member of the organization? Would you mind adding me to a team?

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#97 (comment)

[sherm1]

Thanks, Ioan -- that worked.

[j-rivero]

Thanks Michael for asking. I can not speak from the perspective of an user or developer. From my perspective as the Debian/Ubuntu maintainer would be nice:

• Improve the test coverage
• Have a clear policy about ABI changes and versioning
• Implement an ABI checker and add it to the CI pipeline

Ubuntu has recently change the policy to introduce changes in already released distributions, it is called microreleases. The changes I'm proposing above will help to maintain libccd fcl during the life cycle of Ubuntu releases.

If the software is designed to be multi-platform, it would be good to implement CI also in Windows and Mac.

[sherm1]

@j-rivero, did you mean fcl or libccd above?

[j-rivero]

@j-rivero, did you mean fcl or libccd above?

Sorry I meant fcl, yes. Although the comments can be applied for both.

[isucan]

+1 for merging changes from https://github.com/humanoid-path-planner/hpp-fcl and for removing the articulated model part.

[gdbaldw]

@sherm1 I agree FCL is an excellent base, and have also found that its contact location and vectors are inconsistent for various shape pairs. A general contact solution is needed, in my opinion, for robust simulation. My thought is to define the contact location to be the centroid of the overlaping shape, the orientation to be the plane normal to its major and minor axes, and the length to be proportional to the overlap volume. A fast general solution may be possible using this library, https://www.math.ucdavis.edu/~latte/ , which "has the ability to directly compute integrals of polynomial functions over polytopes and in particular to do exact volume computations"; in plain language, given a faceted 3-D shape, the library may efficiently calculate its centroid, axes, and volume. Analytic shapes could be even faster, and offer an interesting research project to develop formulas for each pair of shapes. cc/ @jslee02 , @stonneau

[sherm1]

@gdbadw -- characterization of the overlap volume would be great and would allow use of volumetric contact models like those from John McPhee's group at Waterloo. I'm not sure that can be done practically though. Latte looks cool but I don't think it could work here -- the limitation to convex polytopes might be solvable by decomposition but the viral GPL license is a fatal flaw!

I'll add in Evan Drumwright @edrumwri in case he has a comment about this.

[edrumwri]

@sherm1, I've been using a volumetric description of the intersecting geometries in Moby for convex polyhedra. One nice thing about this is that the volume is also convex, so point samples represent the intersection completely. I can show at least one compelling example where characterizing the volume is useful (perhaps necessary) for constraint stabilization between convex polyhedra in multi-body simulations.

For generic shapes, even defining an API will be challenging. And I'm unaware of an example where such a volumetric representation is useful for two spheres contacting in multi-body simulations. I'll claim that the determination of whether a volumetric intersection for specific pairs of geometries is useful for such simulations is an open problem.

[gdbaldw]

@sherm1 - Interesting research you reference.
http://real.uwaterloo.ca/~mboos/wp-content/uploads/2011/05/BoosMcPhee_imsd2010.pdf

In accordance with McPhee's method, each localized contact is characterized as one vector with position. A generalized approach to this characterization, while only partially supported by his limited experiments, would facilitate robust simulation independent of object shape. However, Bullet Collision and FCL [ and Moby ?] often represent localized impacts as multiple vectors (box on box for example). Localized impact forces of course resolve into a single differentiable vector, so why shouldn't this resolution originate with a single differentiable collision vector based on a reasonable general geometric theory? cc/ @edrumwri

[edrumwri]

The answer to the question I think you're asking, @gdbaldw, is that a single point of contact is generally insufficient to prevent interpenetration even though equipollent forces/impulses at the two centers of mass can be found that correspond to forces/impulses applied at multiple contact points. The exception is that if the objects are contacting at their centers-of-mass.

[gdbaldw]

@edrumwri - Interpenetration is fundamental to McPhee's method, with each impact force "expressed in terms of the volume of interference between the undeformed geometries", independent of mass distribution and for each interference/interpenetration. At the instant two objects touch and share just one point, the calculated impact force is zero. As an extension, I ask if it reasonable that the direction and location for each of McPhee's impact forces also be expressed in terms of its interpenetration geometry, perhaps characterized as centroid and major and minor axes. Ideally we'd have a generalized approach to calculate a differentiable collision vector with position for each interpenetration, useful for calculating each differentiable impact vector, resulting in robust simulation.

[sherm1]

@gdbaldw, the volumetric contact model from McPhee's lab does make use of the volume, centroid, and geometric inertia of the overlap volume although that might not be clear from the Boos 2010 reference which was mostly about validation I think. Gonthier's 2007 thesis is probably a better place to look. Here's a quote from pg 53:

This new modelling method is based on a compliant contact model approach but uses information related
to the volume of inter-penetration of the colliding bodies. This volume is defined as the volume
spanned by the intersection of the two undeformed geometries of the colliding bodies and will be
called hereafter the volume of interference. In contrast to most other compliant modelling methods,
which are commonly based on the point of deepest penetration, the proposed method yields
a contact force proportional to the volume of interference, specifies that the force should be applied
at the centroid of this volume and that the rolling resistance and spinning friction torques are
proportional to the geometric inertia tensor of the volume of interference.

[gdbaldw]

@sherm1 - Excellent! One might hope that Gonthier's 2007 mathematical formulation has already been instantiated for simple analytical shapes into a library useful to FCL, which could then be validated against/correlated with experiments using a general multibody solver, followed by validation of a faceted model implementation (e.g. ico-sphere vs analytic sphere).

[michaelaeriksen]

Any plans to fix Question: mesh and box collision check? #78?

[michaelaeriksen]

Have you guys looked at the Bullet collision implementation? I switched to that instead of FCL since I have the issue with ignored collision when an object is within a mesh,

[sherm1]

Have you guys looked at the Bullet collision implementation? I switched to that instead of FCL since I have the issue with ignored collision when an object is within a mesh

What does Bullet do in that case? Are you looking for just yes/no collision info or penetration depth?

[sherm1]

@stonneau, you mentioned what sound like some important bug fixes in the hpp fork:

Regarding the contact point computation, we found the same issue to occur when colliding objects of different types, which results from the fact that methods are found in a diagonal look up table, which sometimes require inverting parameters (though the Collision results do not take this inversion into account). Our quick and dirty fix is here (our objective was to have a minimal impact of the code,
but this is not satisfactory):
humanoid-path-planner/hpp-fcl@177fb1f

Similarly the triangle ids resulting from a collision with an octree were wrong:
humanoid-path-planner/hpp-fcl@fdd6d8d

Are there issues describing these problems, and if not do you want to open some? You said you're not satisfied with the first fix but how about the second one? If that's good do you want to submit a PR for it? Is there a test case that you could add that would show the problem and verify the fix?

[sherm1]

Adding Dinesh Manocha to this thread in case he wants to add anything. Sorry, there has already been a lot going on here, Dinesh!

/cc @manocha1

[manocha1]

Thanks for all the feedback on FCL. The input provided by different folks is very useful and we should all work together to extend the capabilities of FCL in terms of contact point computations, penetration depth (esp. global PD computations) and supporting higher order analytic shape representations.

[michaelaeriksen]

I'm currently just looking for yes/no collision and bullet reports that.

Cheers,

Michael

On Mar 27, 2016, at 12:23 PM, Michael Sherman [email protected] wrote:

Have you guys looked at the Bullet collision implementation? I switched to that instead of FCL since I have the issue with ignored collision when an object is within a mesh

What does Bullet do in that case? Are you looking for just yes/no collision info or penetration depth?

—
You are receiving this because you commented.
Reply to this email directly or view it on GitHub

[stonneau]

@sherm1
I created a pull request for the second issue.
#114

and raised an issue for the first one.
#115

Three others modifications of fcl were performed in hpp-fcl, as mentionned by @florent-lamiraux:
1. computation of a distance lower bound when checking collision and when the objects are not colliding (on demand)
2. computation of closest points in the global frame: in the current version, the frames in which points are expressed are not the same for all pairs of primitives,
3. repackaging using standardized cmake rules.

These modifications are less trivial that the previous one, because they required a significant modification of the code.

We would like to integrate them to fcl (at least the first 2 points), which would allow us to use fcl in our projects rather than our fork. However, since this require significant work from us, we need confirmation that the fcl leaders are actually interested in those, and that they will be indeed included.

Thanks

Steve

[mirsking]

Hi @sherm1 , do you have any information about the progress of the high-performance open source collision library by TRI. Thank you!

[sherm1]

@mirsking: we have just recently added staff for computational geometry so are really just getting started on this now. We have been working on FCL integration but not yet on new code for it except for some minor build things. Adding @SeanCurtis-TRI to this thread -- Sean is our main go-to person for computational geometry.

[adamconkey]

Hello @sherm1, @SeanCurtis-TRI, I'm curious to know about the status of the development interest now that we're a couple years down the line. Has much development happened and are there plans for further development? Thanks!

[SeanCurtis-TRI]

Best laid plans of mice and men... Lots of distractions.

The intent is very much to do so. And we've got a couple of patches that need vetting to release into the wild. Things should begin to accelerate in the next few months.

[florent-lamiraux]

in the end did you backport any of the modifications you previously mentioned from hpp-fcl back to fcl, and if no, are you still planning on doing so?

@arocchi
No, and the complete refactoring of fcl since then makes the task more difficult. Moreover, we still need to support older standards of C++ than C++11. Besides, we have added in hpp-fcl some features that introduced other API changes: we have added a security margin in collision tests in such a way that two objects are considered in collision if the distance between each other is below a threshold.