Data structure for polyhedra

flexible-collision-library / fcl

Flexible Collision Library

https://flexible-collision-library.github.io/

Other

1.39k stars 417 forks source link

Data structure for polyhedra #235

Open edrumwri opened 6 years ago

edrumwri commented 6 years ago

Existing data structures in FCL do not seem to support boundary representations of polytopic solids (i.e., polyhedra in 3D). Are there any plans to incorporate such a representation? If not, how receptive would the FCL community be to such a representation? TRI is specifically interested in such a data structure that supports:

extremal point queries
volume calculations
intersection constructions between pairs of convex polyhedra
inertia matrix calculations (i.e., for a polyhedron that represents a rigid body)
signed distance calculations between pairs of polyhedra
closest features between pairs of polyhedra

JenniferBuehler commented 6 years ago

Absolutely interested, need that as well for volume/intersection calculations. More specifically when meshes are not a sufficient representation because they are no solids, e.g. to find intersecting objects (i.e. if one object is a mesh and the other lies completely inside it, but it doesn't intersect its surface, no intersection is found). I think especially because of this shortcoming of surface representations in general, polytopic solids would be a very useful addition to FCL!

I'd be happy to contribute to the work needed to integrate this in FCL.

edrumwri commented 6 years ago

Excellent, thanks! We're still evaluating data structures but will start working on this shortly.

JenniferBuehler commented 6 years ago

Quick question on this as I'm just thinking about this again, are you considering to support concave objects, or should it be just convex polyhedra?

edrumwri commented 6 years ago

My recollection of the literature is that typical algorithms are predicated on the polyhedra being convex, and that non-convex polyhedra can be processed after decomposition into convex pieces.

Evan Drumwright Senior Research Scientist http://positronicslab.github.io Toyota Research Institute Palo Alto, CA

On Wed, Nov 29, 2017 at 12:15 PM, Jennifer Buehler <notifications@github.com

wrote:

Quick question on this as I'm just thinking about this again, are you considering to support concave objects, or should it be just convex polyhedra?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/flexible-collision-library/fcl/issues/235#issuecomment-347982689, or mute the thread https://github.com/notifications/unsubscribe-auth/ACHwz7v2wyLotX-7HTpEpxsncE2vjHO4ks5s7btMgaJpZM4QDoG1 .

JenniferBuehler commented 6 years ago

Yes, so that anwers my question I think.. you want to use GJK or other standard methods and leave it to the user to decompose it if they have concave shapes. Right?

edrumwri commented 6 years ago

Exactly.

Evan Drumwright Senior Research Scientist http://positronicslab.github.io Toyota Research Institute Palo Alto, CA

On Fri, Dec 1, 2017 at 9:10 AM, Jennifer Buehler notifications@github.com wrote:

Yes, so that anwers my question I think.. you want to use GJK or other standard methods and leave it to the user to decompose it if they have concave shapes. Right?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/flexible-collision-library/fcl/issues/235#issuecomment-348552143, or mute the thread https://github.com/notifications/unsubscribe-auth/ACHwz2A5yx2PMvoiT9rkhVpnBHDGJn-oks5s8DMHgaJpZM4QDoG1 .

JenniferBuehler commented 6 years ago

Ok that makes sense :)