Wrong assumption about planes of a ConvexMesh in case padding is used

[peci1]

In ConvexMesh::useDimensions(), there is this code that processes planes (halfspaces) generated by qhull:

https://github.com/ros-planning/geometric_shapes/blob/07a5254b698ecc89e511dc5b3182ecb6c7d2258e/src/bodies.cpp#L903-L904

It checks if the plane for the currently processed triangle/facet isn't too similar to the plane for the previous triangle. If it is, it merges these planes into one and makes both triangles reference the same plane.

However, according to the definition of padding for convex meshes in this library, this optimization goes wrong when non-zero padding is used.

I made some visualizations to make this argument clearly visible:

Here, the red line is original (unscaled) "mesh" (well...). The cyan one is the line after applying only scaling. And the green one is after padding is applied. You can see that the line stops being a line and any planes that would be optimized by the previous algorithm would no longer be parallel.

Maybe even more obvious.

This has also consequences for more code paths. It seems to me that two things are required.

1. Get rid of the "if" in the above code excerpt and just add one plane per each triangle.
2. Take a broader look around the code, and e.g. add mesh_data_->scaled_planes_ which would contain the correctly scaled and padded planes which could be used for collision checking. For example this code tries to subtract padding from the data, but fails to do it correctly (a part of it is fixed in Fixed computation of intersectsRay() for Cylinder, Box and ConvexMesh #109):

https://github.com/ros-planning/geometric_shapes/blob/07a5254b698ecc89e511dc5b3182ecb6c7d2258e/src/bodies.cpp#L1091-L1100

If there were an already precomputed field containing the scaled planes, all computations of this kind could be done both efficiently and without fear if everything is correctly accounted for. My approach to recomputing the scaled planes would be to just take the scaled vertices and reconstruct the scaled planes from them. It has just one drawback - so far, mesh_data_ are not touched in updateInternalData(), however if we wanted to keep a set of scaled planes, these would obviously need to be updated in updateInternalData(). But this function anyways has a loop over all vertices to recompute the scaled vertices, so I think another loop for scaled planes is not a problem. It might well be compensated by the possible speedups from #126.

[v4hn]

Reading this, my first impression was: What a weird kind of padding...
Do we actually want to have/keep this definition of padding?
Would, e.g., padding only convex vertices, be a reasonable alternative definition?

Does the "optimization" you mention above achieve such an alternative definition consistently?

[peci1]

What do you mean by padding only convex vertices? You mean only those that are not in the middle of a larger plane? That would probably be more of what one expects, but the computations would be even more complicated...

The optimization I suggested would follow the current "weird" padding definition. Maybe the current behavior e.g. in isPointInPlanes() is closer to your alternative definition (if I understood it correctly) in the fact that it doesn't change normals of the scaled planes. However, it is then not true that the scaled vertices lie on their scaled plane, which is kind of weird. So if you'd want to change the meaning of padding, it would need a more thorough debate on what would be all the consequences and how to compute it.

[v4hn]

What do you mean by padding only convex vertices? You mean only those that are not in the middle of a larger plane?

This is what I had in mind, yes.

The optimization I suggested would follow the current "weird" padding definition

That is why I wanted to raise the question of whether the current definition is even what we want.
I guess the decision boils down to:

• Currently all vertices of convex meshes are padded, which leads to the unintuitive behavior illustrated above when meshes are not minimal.
  To achieve consistency in this case, we should remove some input optimizations and should probably restructure internal overhead.
• Alternatively, all planes could be padded, to retain the planes' normals. This however, would likely incur more computational complexity, as vertices cannot be computed from line projections anymore.
• Lastly, It seems a rather obvious alternative to simply leave everything as is and require ConvexMesh objects to be constructed from minimal convex meshes only (i.e., no vertex can be dropped without changing the convex hull).

Do you have time to join the MoveIt maintainer meeting tomorrow to discuss this (and your other issues) in person?

[peci1]

Okay, let't talk about it tomorrow, I'll join.

[peci1]

Here's a wrap-up from the WG meeting.

Any changes we make, we should want their behavior to be synchronized between shapes and bodies. I only see a problem that shapes have a (general) Mesh, while bodies have ConvexMesh.

There are multiple alternative ways of implementing padding:

1. Apply padding along triangle normals. Reconstruct vertices by re-intersecting the planes. Points in the middle of a planar area should just be pushed with the surrounding triangles.
2. Apply padding along triangle normals, but keep dimensions of the triangles. Add new faces to the vertices that got "torn apart".
3. There's an already reported issue which implements another solution based on applying the padding along vertex normals, which are computed as weighted average of the normals of the surrounding triangles.
4. Keep the current behavior and just make sure the library always works with minimal convex hulls.

Pros and cons:

1. Close to what one might "visually" expect. The amount of applied padding is invariant to isometries (relative to mesh center). In sharp angles, it might increase the size of the mesh a lot. Keeps planes as planes.
2. Also close to the visual expectations. It needs adding new faces and splitting vertices. Keeps planes as planes. The amount of applied padding is invariant to isometries (relative to mesh center).
3. Another approach, visually also satisfying. It doesn't keep planes as planes. It was shown to work even on non-convex meshes (getting weird results if too much padding is added to non-convex meshes, but that'd probably be a problem for any algorithm). The amount of applied padding is invariant to isometries (relative to mesh center).
4. Maybe the current implementation in bodies which is actually using qhull goes this way. But the shapes library definitely allows any kind of meshes, and for those, this approach would not be usable. The amount of applied padding depends on the angle between the ray to mesh center and axes.

One of the comments was that we should keep runtime overhead as low as possible. This can be tested e.g. on PR2 robot meshes.

Another comment was that generally change of the current behavior is okay as long as we can provide some guarantees on the relationship between the old approach and the new one (i.e. all points contained by the old behavior would be contained by the new one, or so...).

[peci1]

This might already be resolved by #238?

[rhaschke]

Planes are still "bent" by the padding. But I don't see a solution to the problem either. We cannot easily keep planes planar with padding.

[peci1]

Ah, you're right.