GetConvexHull not completing in some cases

[iemfi]

Hi, I have a problem with making convex hulls. I use the pruning method in ConvexHullHelper first then ensure that there are more than 5 vertices. It works fine most of the time with thousands of different convex hulls. The problem is that every once in awhile it gets stuck in the main loop of ConvexHullHelper.GetConvexHull() and never exits.

while (outsidePoints.Count > 0)

I think the problem is that outsidePoints never reaches 0 for some edge cases. Is there a way to check if the vertice data is valid first? If not is there a way I can make GetConvexHull terminate gracefully instead of getting stuck? Thank you!

[Norbo]

The convex huller should be able to handle invalid geometry, though that handling can be in the form of an exception. If it's hitting an infinite loop, then something snuck through that isn't already protected against. I'm not sure what that would be off the top of my head; probably just some sneaky numerical issue.

If you could share the vertex data of a reproducing model, that would help me track down and fix the source.

[iemfi]

+ [0] {X:-0.8577047 Y:14.19758 Z:-4.866044} Microsoft.Xna.Framework.Vector3
+ [1] {X:-0.07056456 Y:14.0434 Z:-5.165401} Microsoft.Xna.Framework.Vector3
+ [2] {X:-0.09851751 Y:14.08656 Z:-5.261027} Microsoft.Xna.Framework.Vector3
+ [3] {X:-0.05788735 Y:14.14983 Z:-5.182701} Microsoft.Xna.Framework.Vector3
+ [4] {X:-0.8197466 Y:14.26284 Z:-4.811094} Microsoft.Xna.Framework.Vector3
+ [5] {X:-0.8200286 Y:14.17346 Z:-4.784081} Microsoft.Xna.Framework.Vector3

Here are a set of points which causes it to get stuck in the loop (I'm using the latest dev version).

Also this is probably a very silly question but is there any way to get CompoundHelper.SplitCompound() to produce 2 CompoundBody's instead of a Entity<CompoundCollidable>?

[Norbo]

Here are a set of points which causes it to get stuck in the loop (I'm using the latest dev version).

That's disconcerting- I am unable to reproduce the infinite loop; it works as expected.

Perhaps it's related to some contextual subtlety; could you try reproducing it in one of the BEPUphysicsDemos and then posting the whole demo setup?

Also this is probably a very silly question but is there any way to get CompoundHelper.SplitCompound() to produce 2 CompoundBody's instead of a Entity<CompoundCollidable>?

Unfortunately, not directly, no. The CompoundHelper is a little experimental and was intended to be an interim solution until proper mutable compounds were added. I've been dragging my feet on that

You can recreate CompoundBody objects from the data in the Entity<CompoundCollidable> objects, but that would be a little gross. A marginally less gross option would be to toss in a CompoundCollidable-consuming constructor on the CompoundBody and use the overload of SplitCompound which outputs CompoundCollidables directly.

[iemfi]

I've been unable to reproduce the problem in the demo but I think I've narrowed down the issue. If I do not add the list of created CompoundShapeEntrys into a new compound body, it proceeds smoothly. If I create the CompoundBodys it gets stuck.

I've uploaded the whole source, it should go straight to the stuck loop when you run it. Commenting out line 160 "var newBody = new CompoundBody(cbeList,totalWeight);" in Tree.cs fixes the problem. I've commented out all other uses of BEPU. If you change the random seed used it works correctly with most seeds.

http://www.mediafire.com/?6mh542chv7ird20

[Norbo]

It appears to be a numerical disagreement between the RemoveInsidePoints function and the convex hull expansion tests. While a few epsilons could be tossed in here and there on the dot product comparisons, I'm going to poke around trying to find a more elegant approach tomorrow.

[iemfi]

Thank you! Nice to know I wasn't just slowly losing my mind. I'm curious though, why does the creation of the compound body affect it? Is it something to do with the data structures?

[Norbo]

A fix has been uploaded to the development version.

Turns out it was a numerical issue, but not quite where I thought. Sometimes, the initial tetrahedron vertices were included in the 'outside' points incorrectly.

I'm curious though, why does the creation of the compound body affect it? Is it something to do with the data structures?

Creating a compound body requires some information about mass distribution and so forth which results in some GetConvexHull operations when ConvexHullShapes are involved (ConvexHullShapes do not cache all the compound-required information automatically). Even the slightest difference in input can cause this error to occur or not occur. The order of vertices, 'mathematically' equivalent but not 'numerically' equivalent vertex processing, or even a particular processor's implementation of floating point operations can all result in different behavior.

In this case, since the convex hulls were likely already processed once, the compound body's processing worked on the already-processed list and took a different path (off a cliff and into an infinite loop).

[iemfi]

Wow, if only every company's support was like yours! The trees work great now after some refactoring of my code.

One thing I noticed while testing was that sometimes when a compound body is created overlapping a static mesh it blows up and generates NaN values. Is this expected? Not really an issue but was curious if it was a bug.

Also, how would you handle penetration of one object with another? For example an arrow getting embedded in the ground. I was thinking of disabling collision checking between both objects on collision then creating a weld joint and manually calculating and controlling the joint offsets to adjust the object locations. Is there a better way to do it?

[Norbo]

One thing I noticed while testing was that sometimes when a compound body is created overlapping a static mesh it blows up and generates NaN values. Is this expected? Not really an issue but was curious if it was a bug.

No, that is not quite expected behavior

The most frequent cause of such crashes in the past have been degenerate triangles of one form or another. Usually the crash can be resolved by fixing the mesh, but I also try to stop the engine from crashing and burning even in the presence of suboptimal input data. If you want to set up another reproduction case, I'll take a look and see if I can protect against it.

Also, how would you handle penetration of one object with another? For example an arrow getting embedded in the ground. I was thinking of disabling collision checking between both objects on collision then creating a weld joint and manually calculating and controlling the joint offsets to adjust the object locations. Is there a better way to do it?

If you want it to remain as a dynamic object in the world, that's the usual approach.

You could also turn it into a kinematic entity upon impact. That would avoid the need for a constraint. However, kinematic entities have infinite mass; making such a thing follow a dynamic object essentially gives the dynamic object unstoppable force. (For example: get an arrow stuck on your character, walk up to a truck and push the truck around effortlessly with the arrow parented to your body).

The simplest/speediest approach is to just remove the collidable representation of the object from the world entirely, leaving a graphical proxy. If you want to be able to pick up the arrow later, you could keep a kinematic entity at the impact spot but with collision response disabled. Then, use a broadphase query around the character or check the pairs list of the character to find any collectibles nearby.

[iemfi]

Hmm, I can't seem to reproduce it any more. I think it was because I was actually using the stable version when I thought I downloaded the dev version .