Bepu gets very slow, when there are lot of collisions

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
kapsl
Posts: 6
Joined: Thu Jun 16, 2016 8:00 am

Bepu gets very slow, when there are lot of collisions

Post by kapsl »

Hi,
we currently have the following problem. We have two industrial robots, and check collisions for them. We have situations where we have to test positions where the are a lot "inside" each other = colliding. When the objects overlapp a lot, the collision checking gets very very slow. I guess this is, because every collision check has to go to very detail then. For us it would be completely fair to just know if there's a collision or not. Not exactly what objects or where exactly...

Is there a way to speed the situation up? Most of the robot objects are convex hulls.

lg Manu and thanks a lot!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Bepu gets very slow, when there are lot of collisions

Post by Norbo »

While using boolean-only tests could theoretically speed up collision by around 2-4 for deep contact convex hull collisions, the engine doesn't have a top-level boolean-only pipeline. That is, you would have to trigger the boolean tests yourself for each overlapping pair generated by the broad phase. This is doable, but would be a little bit annoying.

There may be easier options. How many overlaps are there, and how many vertices does each convex hull have on average, and how long does it take (on what hardware)?

My guess is that the convex hulls have a large number of vertices each. The cost of collision detection with convex hulls is proportional to the number of vertices in the hull, so if there are hundreds of vertices, it will run an order of magnitude slower than shapes with a couple dozen vertices.
kapsl
Posts: 6
Joined: Thu Jun 16, 2016 8:00 am

Re: Bepu gets very slow, when there are lot of collisions

Post by kapsl »

Hi Norbo,
each Robot consists of 9 Elements and each Robot has a tool consisting of 9 Elements (one of this is a Mobile Mesh). + 1 Element the object, they carry = ~ 35 Convex Hulls + 2 Mobile Meshes
There are other obstacles in the world, but it is also slow if only the two robots are involved in the collision.

When there is deep contact, it seems like a collision check takes about 1 second, roughly on an Intel Xeon E5620 with 12GB Ram. I can measure more detailed if this helps...

How exactly can I find out the nr. of vertices? When I look at the outcome of ConvexHullHelper.RemoveRedundantPoints(points), the points have
1069, 1080, 7059, 1701, 1346, ...

And when we created the convexhullshape with new ConvexHullShape() we have Vertices
271, 219, 146, 89, 108, ...

The GeometryModel3D is imported with Helix ModelImporter from a .stl object file.

Thanks a lot!
lg Manu
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Bepu gets very slow, when there are lot of collisions

Post by Norbo »

The number of vertices in the final ConvexHullShape- where you measured 271, 219, 146, 89, 108- is the relevant metric for convex hull performance. For a real time game-like application, I would recommend those numbers being closer to 6-30.

However, a full second for collision detection is very high, even taking into account the high vertex count.

For reference, I set up a quick demo in the BEPUphysics demos to test. I created 30 ballish convex hulls all near each other, each with 250 surface vertices. The result is 435 collision pairs with mostly deep contacts. After disabling the solver for the involved pairs, the single threaded time is ~49ms on my 3770K@4.5ghz. The E5620 is about half as fast in terms of single threaded performance, so I'd expect the same simulation to take ~100ms on it. Here's the simulation if you want to try it out:

Code: Select all

            var points = new List<Vector3>();
            Space.ForceUpdater.Gravity = new Vector3();
            var random = new Random(0);
            for (int shapeIndex = 0; shapeIndex < 30; ++shapeIndex)
            {
                var center = new Vector3(2 * (float) random.NextDouble(), 2 * (float) random.NextDouble(), 2 * (float) random.NextDouble());
                for (int k = 0; k < 250; k++)
                {
                    var direction = Vector3.Normalize(new Vector3(-1 + 2 * (float)random.NextDouble(), -1 + 2 * (float)random.NextDouble(), -1 + 2 * (float)random.NextDouble()));
                    points.Add(center + direction);
                }
                var convexHull = new ConvexHull(points, 10);
                convexHull.CollisionInformation.CollisionRules.Personal = BEPUphysics.CollisionRuleManagement.CollisionRule.NoSolver;
                convexHull.ActivityInformation.IsAlwaysActive = true;
                Console.WriteLine("Convex hull point count: " + convexHull.CollisionInformation.Shape.Vertices.Count);

                Space.Add(convexHull);
            }
So even assuming your simulation is single threaded and has as many overlaps as this (which would basically require both robots being compressed together into a tiny box), there's still a factor of 10 performance difference to figure out.

Are you using the Space.Update(dt) overload where dt is the time since the previous frame? Using that overload will make the engine take multiple timesteps in an attempt to catch up with the accumulated time. It gives up after Space.TimeStepSettings.MaximumTimeStepsPerFrame, which defaults to 3. So, if the simulation is complicated enough to take longer than a frame's duration consistently, it could end up entering a vicious cycle where it just can't keep up. In that case, just using one time step per frame via Space.Update() with no parameter could help responsiveness by just letting the simulation run slower than real time.

But even that alone doesn't explain the full performance difference. How complicated are the MobileMeshes? A mesh with a thousand triangles deeply intersecting another mesh would hurt pretty bad. It would be roughly as expensive as a thousand simple primitives being queried against a static mesh. It gets even worse if the MobileMesh has interior solidity enabled. For any nontrivial mesh, I would strongly recommend decomposing the mesh into multiple convex hulls instead. There exist some handy automated tools that can do a good job of this, like V-HACD. Combined with some form of mesh simplification prepass, 100x faster collision detection is very possible.

It would probably be a good idea to run some form of profiler to get a better idea about what systems are actually taking up the time before jumping into anything work intensive.
kapsl
Posts: 6
Joined: Thu Jun 16, 2016 8:00 am

Re: Bepu gets very slow, when there are lot of collisions

Post by kapsl »

Thanks for your reply!!!

I tried to change the mobile mesh back to a convex hull and it seems, that this speeds up the process a lot. I think this was the reason, why it was so slow...

Thank you very much!
Post Reply