Convex geometry clean up

[SeanCurtis-TRI]

Perusing the Convex geometry implementation, several issues jump out:

• (Clean up Convex geometry (including fixing AABB computation error) #325) The class has several unused members. They aren't used in the class's internal implementation and, it likewise appears, are not directly referenced (as public members). They should be removed from the class API.
  • plane_normals
  • plane_dis
  • edges
• The class does no validation on the inputs. It can either validate by default at construction or be available as a user-callable a method such that the user can choose to validate.
• The operations that calculate volume, center of mass, and moment of inertia tensor all have duplicated functionality (they all rely on the volume-weighted combination of smaller tetrahedra). To iterate through the tetrahedra and compute volume is duplicated across all methods. Refactor so it's only defined once.
• Currently, the smaller tetrahedra are defined generally (every face is divided into tetrahedra based on the face's "center" point and a fan of triangles including all other vertices). If the face is actually a triangle, this leads to volume for three tetrahedra being computed instead of just the one. The decomposition of the geometry into tetrahedra should, at least, handle triangular faces more intelligently. And perhaps also 4-sided faces.
• There are no (until Clean up Convex geometry (including fixing AABB computation error) #325 and then limited) unit tests for the geometry.
  • Need more unit tests -- particularly for the inertia tensor. See notes in current tests.
• (Added after initial post) Resolve data ownership. Currently, the Convex class doesn't own the vertices and polygons, it only takes pointers to them. The reasoning behind this design isn't clear and needs to be captured in the code.
• (Added after initial post) There are two primitive algorithm implementations involving Convex convexHalfspaceIntersect and convexPlaneIntersect. These functions, however, are not connected into the two solvers. In fact, the ascii tables that indicate primitive algorithms don't even have a row/column for Convex.

[SeanCurtis-TRI]

@jslee02 Do you know any reason why I can't pull the trigger on modifying the API of the Convex type?

[jslee02]

@SeanCurtis-TRI Nope. I think your points are all valid. Looking at the history, Convex class was added in the very beginning of FCL (7 years ago), and there hasn't been any significant improvement made. It's time to move on!

As a note, one of my personal reasons I haven't taken a look at this class is that I believed there is no performance advantage of using Convex over the BVH representation even for convex meshes. This is because FCL uses the convexity-based algorithms for Convex, and the specific algorithm frequently requires iteration over all the vertices. This conclusion is made without a comprehensive benchmark so it could be wrong. However, the current algorithm can be replaced by a more efficient algorithm anytime so I think this modification worth enough.

[SeanCurtis-TRI]

Hi @jslee02 Thanks for weighing in.

I know what you mean about the support function for Convex. In its current incarnation, it does a linear pass over all vertices, period. However, that can be sped up and, I believe, probably should be. Here are the things to consider.

1. The one thing the Convex class gives us (in conjunction with GJK/MPR) is that it will detect if one convex shape is completely contained within another. Pushing it into a BVH as a mesh will only detect collision if there's actual intersection at the surface.
2. The support function can be made a lot faster by making use of the topology (i.e., the edges). Rather than a linear search, the code can basically walk along the surface of the mesh based on edge directions. That would certainly reduce the linear component. I suspect that was probably the motivation for the edges in the first place. (Or, at the very least, I'm hard-pressed thinking up an alternative motivation.)

But that's for the future. In the short-term, we'll go ahead and clean it up so it's, at least, a fully participatory member of FCL.

[SeanCurtis-TRI]

@jslee02 Quick question, I've added one more point above (about data ownership). The Convex class doesn't own the data it is provided; it's simply given pointers. Do you have any insight into that design decision? While I can imagine a case where the Convex class could simply be an abstraction on top of some other data, I would imagine the default case is that it is a stand-alone entity with its own memory and self-contained lifespan. Yes?

[jslee02]

@SeanCurtis-TRI I agree that this design is prone to errors in terms of memory management. As you mentioned, it should be self-contained by default I think. if needed, we could consider sharing the mesh data over multiple Convex or other objects, which I cannot think of any use case on top of my head. Even in this case, we might want to use a smart pointer instead of a raw pointer.

There are two primitive algorithm implementations involving Convex convexHalfspaceIntersect and convexPlaneIntersect.

Good catch! I think it's worth to utilize the two functions.

In fact, the ascii tables that indicate primitive algorithms don't even have a row/column for Convex.

This is simply an oversight. 😅 Feel free to update the table.

[SeanCurtis-TRI]

Great. A shared_ptr for the data would definitely resolve those issues. That would make it so that no external entity has to keep track of the Convex's geometry but would allow the same geometry to be used by multiple Convex instances. And I was thinking of a std::shared_ptr<std::vector<Thing>> just to modernize things a bit.

[Levi-Armstrong]

Great. A shared_ptr for the data would definitely resolve those issues. That would make it so that no external entity has to keep track of the Convex's geometry but would allow the same geometry to be used by multiple Convex instances. And I was thinking of a std::shared_ptr<std::vector> just to modernize things a bit.

I finally got back to working with FLC and I upgraded to the latest version and ran into this where I assume it was taking ownership of the pointer but after looking into it further found it was not. +1 for using shared pointers.

I have been doing a lot of testing of different shapes to convex hull and comparing FCL to Bullet and it turns out that they produce very similar results but both are off around 12cm for the case of checking a convex hull (Meshed Sphere) to convex hull (Meshed Sphere). Although when I run it in debug it does fail on one of the newly added asserts which suspect may be part of the issues with the error in distance. If useful I can create a test that demonstrates the assert failures if desirable?

Also I have a piece of code written that uses qhull to take a vector of point and returns the necessary data for the current constructor of Convex shape type. Would the maintainers be interested in adding this utility function to FCL (adds a dependency on qhull) and if so where would you like it added?

[MengeCrowdSim]

If you've got an example that exposes some of the new asserts, we would love to get that into a unit test. We've had some issues reported in the past, but have been unable to reproduce the issues (which makes debugging nigh on to impossible). So, if you can do that as a PR, that'd be brilliant. And the sooner the better -- I'd love if we can get that in before the next release.

We'll have a chat about qhull dependency. Clearly the FCL API was designed with minimal dependencies -- clearly they didn't want to have to compute a convex hull and relied on one being pre-computed. A method that facilitates that would definitely be a huge improvement in the usability of the API. The only question in my mind comes down to making sure the dependency "makes sense" (whatever vague concepts that simple phrase captures). We've discussed it in the past and bringing qhull probably makes sense. If we pull the trigger on that, it'd make sense to defer that until after we release the next public release.

As for the error you're finding in your hulls, when you say the answer is off, can you elaborate? What are the radii of the spheres? Are the tesselations polar or geodesic? What are the sizes of the triangles/faces? Is that error compared to the idealized spheres or the known tesselation? There had been an earlier issue related to that, and the answers that were being produced were exact, to the resolution of the mesh. I want to make sure this isn't another instance of that (although 12 cm is pretty large -- unless, of course, the spheres are much, much larger).

[SeanCurtis-TRI]

Oops -- that last comment was mine. That's what happens when I respond at home -- I forget I'm not logged in as myself. :-)

[Levi-Armstrong]

I will create a few unit tests that cause the assert failures. Also for these tests instead of relying on qhull I will write the data to a simple text file which gets parsed by the unit test.

[SeanCurtis-TRI]

You rock! That'll be great. One of the things I'm hoping is that the test will still fail if we take your tesselated sphere and throw out most of the faces away from the contact. (the fewer faces there are, the easier it is to debug -- but with GJK/EPA algorithms, the path you take through the code is sensitive to the actual feature set you have.) So, we'll start with the data that actually reproduces the problem and only try simplifying it to the extent that it still works. So, you don't have to waste your time tinkering with "simpler" geometry.

[Levi-Armstrong]

@SeanCurtis-TRI I have created the first of three tests.

Also distance error was not as bad as I thought. As you suggested, I pulled the meshes into Blender and fiscally measured the correct distance. When not in collision the distance is correct but when in collision it is off ~0.005 for two spheres with a 0.25 radius.