BEPUphysics

Hi,

Most of the objects in my game use a convex hull, and I'm using a heightmap terrain. When I add a considerable number of turret emplacements to the level, I get a lot of slowdown. I've profiled my application, and the most intensive part of the code is the physics.

My current terrain is 128^2 in dimensions. My plan is to use a sparse grid of blocks of approximately this size for the whole level. I've got 64 turret emplacements on the level, just as a test, and each of these uses 4 convex hulls. These hulls are all kinematic, as the emplacement is an articulated object; im not using joints, im just directly placing each hull on each logic step; the physics step comes after the logic step.

I cant really tell from my profiler results which part of the physics scene is the more intensive, but I suspect its testing the hulls against the heightmap. What things can I do to optimise this system?

Try giving it motivation. Tell it that if it doesn't run more efficiently it will be sold into slavery to do off-world mining.

Fe_Yoshi's suggestion may work, but there may be some alternatives.

By default, kinematic objects will not generate contacts with other kinematic or static objects. Unless you've changed the collision rules, it's not the narrow phase testing.

If they were changed so that contacts are being generated, how complicated are the convex hulls? Convex hull narrow phase cost rises roughly linearly with the number of vertices within a hull. Keeping them simple is important.

If the hulls had the collision rules changed to detect other kinematic impacts, consider refining the rules with collision groups such that the terrain-turret interaction does not attempt to generate any contacts. NoBroadPhase is the fastest option.

I would recommend grabbing the source and profiling everything together so that the culprit can be found more precisely.

I never thought of disabling turret vs. terrain contacts - although it seems obvious now.

You need to take the results of a deep profiling with a pinch of salt. Some things take orders of magnitude longer with an intrusive profiler than without.

I have done some deep profiling of my test level, using the equatec profiler, and a few things are proving to be very expensive to profile due to the large number of calls to the same methods - intrusive profilers create a horrible amount of overhead unless you inline these sorts of things. I wait about 2-3 minutes for the application to start up in a profiler, and the most expensive thing during startup is the computation of convex hulls; for example, a call to Toolbox.GetConvexHull takes 21,223ms when run in the profiler, and i call it 7 times, for a total of 148,563ms. Using the Stopwatch class I can tell that without the intrusive profiling, this totals about 6 seconds. Without profiling, the whole application takes 7 seconds from clicking Play on the main menu to dumping the player tank into the world.

With that in mind, I ran the application for a short amount of time, during which there were 2141 timesteps. In total, calls to DoTimeStep took 77577 milliseconds. Here is a breakdown of the most expensive parts, which I doubt comes of any surprise to the developer as it seems fairly predictable, but anyway, here it is.

Figures are in the format: [num calls, average time in ms, total time in ms]

Within Space.Update, the most expensive call was MultithreadedProcessingStage.Update [23551, 3.3, 77524]. ( Roughly 90% must be a no-op, judging by the average time spent )
Within that method, the most expensive is NarrowPhase.UpdateSingleThreaded [ 2141, 31, 65520]

Within that method, NarrowPhase.UpdateBroadPhaseOverlap is the most expensive [188567, 0.3, 65215]

And within that, the most expensive is StandardPairHandler.UpdateCollision. This is mostly passthrough though. If I dig down I eventually reach
CollisionAlgorithms.MPRToolbox.GetContact [149503, 0.4, 61501] which spends the majority of its time calling two methods:
MPRToolbox.LocalSurfaceCast [299006, 0.1, 30886]
MPRToolbox.RefinePenetration [149503, 0.2, 25583]

Does any of this come as a surprise? The total and average times are most likely skewed by the same thing which is skewing the results of the convex hull creation, but what of the call counts?

Assuming those results are representative, it sounds like there's a lot of objects in persistent deep penetration. This could happen easily if collision response is disabled but contacts between intersecting objects are still being generated. In addition to disabling collision detection between the terrain and the turrets, it would be good to ensure the turret is not colliding with itself either.

There's some tuning which can be used to speed up deep contact (at the cost of accuracy), but it's best to get rid of the unnecessary tests first.

That particular routine is one of the areas where the number of vertices in the convex hull will play a big role.

You might want to check with a different, lighter profile to see if those results are representative as well (if equatec supports such a thing). I use ANTS most of the time; I believe it has a trial. It has a 'light' option which has much higher speed (only about a 2x slowdown) and accuracy (though it sacrifices line-level timings). It's not computationally free or absolutely accurate, of course, but it's quite a bit better. SlimTune might support some faster profiling types too, though I haven't fiddled with it much.

How would I use collision rules to prevent bodies from contacting each other? What i've done is to create a single collision group for all static scenery objects (my height map, walls, trees, etc) and to create a collision group for individual entities. I've read the PDF on collision rules, but it doesn't help me work out how to actually use them. Are there some code samples somewhere?

There's a CollisionFilteringDemo in the BEPUphysicsDemos.

Every collidable has CollisionRules which contain the Specific relationships, Personal collision rule, and Group to which it belongs. For entities, it's accessible in entity.CollisionInformation.CollisionRules. StaticMeshes, Terrains, and InstancedMeshes are Collidables themselves so they have a CollisionRules property directly. Usually, that property is used to set the Personal collision rule and the Group and then other static helper methods are used to conveniently define the collision rules between specific objects and between groups.

The two most common helper methods are the CollisionRules.AddRule and CollisionGroup.DefineCollisionRule methods.

CollisionRules.AddRule specifies two CollisionRules instances or owners of collision rule instances and adds the latter instance to the first object's Specific list with the given collision rule. For example: CollisionGroup.DefineCollisionRule works between two groups, like so: You can pass the same group in for both parameters to define a rule for a group and itself: There's other ways to set and modify collision rules; the CollisionGroup class has other static methods related to CollisionGroups and CollisionRules contains all the raw dictionaries and some other non-group helper methods. The above are just the most used.

Also, if you find yourself getting into some sort of combinatorial explosion of collision groups, it's usually a sign that collision groups aren't really what should be used in that specific situation. It may be better in some scenarios to define a bunch of specfic relationships within a structure. And, if all else fails and you can't quite get what you want, the collision rules calculation system can always be changed to take into account whatever data you want. It's easiest to find a working solution in the existing system, though.

From my remote perspective, it sounds like turrets probably won't need to collide with other turrets, so all turrets and similar kinematic objects could be in a single collision group that doesn't collide (NoBroadPhase) with itself or the environment. Projectiles or perhaps vehicles would have another (set of) group(s) that have their own relationships with the environment, turrets, and so on.

I've tried a couple of things, and I still find that convex hulls on a height map are very slow. I have a test scene, with 128 turret emplacements (3 convex hulls each) and one vehicle. My height map is 128x128.

I've set all my convex hulls to kinematic, except for a single hull on the vehicle; the vehicle turret, and the turrets on top of the emplacements, are all kinematic. I have created a collision group specifically for scenery objects, of which right now the only one is the terrain. This group has the collision rule of NoBroadPhase.

I then did a couple of different things, and found that the intersection tests were still the main bottleneck.

First, I tried giving every entity its own collision group; then, in my emplacement entity, I set it to use the NoBroadPhase collision rule with the Scenery collision group. Here is my code for the emplacement entity:
The enterWorld methods for the turret and body shape all contain calls to Space.Add. I also used an assert to test that the terrain object had the correct collision group set on it:
This produced the same kind of performance as before, so it seems that no difference has been made. I tried removing the Turret.addToWorld and Body.AddToWorld calls, and this gave me back my performance, indicating that the convex hulls are still the problem.

I also tried a more brute force method, by setting the collision groups of everything to the same group as the Scenery group, bearing in mind that the Scenery group has the rule of NoBroadPhase set on itself. My performance was the same.

In the short term, getting this to work with turrets would be useful, but in the long term I plan to have up to 100 vehicles in the scene, and having such slow convex hull vs. terrain casts will be a serious problem. Even if I make my turrets fast, I will find later that the vehicles are too slow. In the long term, what can I do to make convex hulls faster against the scenery?

[update]

A bit more information: By putting breakpoints in the method NarrowPhase.UpdateSingleThreaded I have determined that there are 529 broadphase contacts at the point of this method being called, when I was expecting only 1 contact (between the rigid body of the vehicle hull and the terrain).

I wasn't able to work out where the broadphase pairs are generated from, however, or else I would poke around a bit.

I found the problem, after a bit of trickery. Rather than trying to work out where the collision rules were calculated from a top down perspective, i worked bottom up, adding breakpoints in CollisionRules, and added a get/set wrapper around CollisionRules.specific (which was being accessed directly) and I eventually found that it was calculating NoSolver for the barrel and rotating bit of the turret on top of each emplacement. The result of this was that they were in deep pentration with full tests being performed on them, even though the three main parts of an emplacement are supposed to intersect each other.

It seems that for some reason (I guess by design but I would like to check this), if we set the CollisionRules.Personal to NoSolver, this overrides the effects of any groups. Removing that from the setup code resolves the issue. My convex hulls no longer collide with the terrain.

But this presents another problem, that I have to have the solver on for objects if I want to exclude them from colliding with any arbitrary collision groups. Am I wrong in thinking that there might be some possible use cases for this?

It seems that for some reason (I guess by design but I would like to check this), if we set the CollisionRules.Personal to NoSolver, this overrides the effects of any groups.

This is indeed by design. CollisionRules priorities are based on specificity (Specific first, Personal second, Group third). There's more information in the collision rules documentation: http://bepuphysics.codeplex.com/wikipag ... umentation

Personal rules can act as 'exceptions' to the general-purpose group rules. Specific rules act as overriding exceptions to all other rules.

But this presents another problem, that I have to have the solver on for objects if I want to exclude them from colliding with any arbitrary collision groups. Am I wrong in thinking that there might be some possible use cases for this?

To clarify, the solver does not operate on individual entities or collidables. It operates on constraints. A colliding pair of objects creates a constraint. The collision rule created from the involved collidables determines whether or not the solver solves the constraint. If the group rules do not let the solver solve (because it results in NoSolver or more restrictive), the Personal rule does not also need to be NoSolver because solving is already blocked.

There are indeed some cases where you may be able to get more direct results through a slightly different system. Rather than make a system that is guaranteed to work for every possible situation with the minimum amount of rule-setting (which is very nearly impossible), the engine has a generally good starting point and allows the rule evaluation to be configured. The CollisionRules.CollisionRuleCalculator delegate can be set and the various stages of calculation are available in static helper methods to ease the creation of custom calculators (CollisionRules.GetSpecific/Group/PersonalRuleDefault).