How to activate entities around a physics change

[diabloqfdb]

Hi!

I am trying to make entities react to semi-static physics entities change. This is almost always terrain, but sometimes some other static can disappear or move.

This is a quite difficult task, so I decided to start fresh and easy, using raycast to determine the terrain intersection, updating the terrain and the computing a bounding box around the intersection point. For every entity intersecting the box, I would like to activate it. A more advanced solution will be needed, but first let's see how BEPU reacts to this. Suspended objects should fall and objects that are deep inside another object will either slowly rise up, of fall through.

But I am having problems with activating the entities. More precisely, I don't know how to get the entity. Bellow I'll list a pseudocode which obviously doesn't compile with my approach:

Code: Select all

                 if (RayCastFromCamera(out rcr, World.TERRAIN)) {
                    EditTerrain.EpdateHeightsAtAP(terrain, rcr.HitData.Location, gameTime, HF, chunkAlloc);

                    BoundingBox box = new BoundingBox();
                    box.Min = rcr.HitData.Location - new Vector3(30, 50, 30);
                    box.Max = rcr.HitData.Location + new Vector3(30, 150, 30);

                    List<BroadPhaseEntry> overlaps = new List<BroadPhaseEntry>();
                    Space.BroadPhase.QueryAccelerator.GetEntries(box, overlaps);

                    foreach (BroadPhaseEntry b in overlaps) {
                        if (b is ConvexCollidable<CylinderShape>) {
                            Cylinder c = (Cylinder)b;
                            c.ActivityInformation.Activate();                      
                        }
                    }
                }

Which is the proper way of getting the entity that intersected the box?

Thank you!

[Norbo]

ConvexCollidables and other EntityCollidables are indeed subclasses of BroadPhaseEntry, but Entity does not inherit from BroadPhaseEntry. Instead, an Entity owns a collidable that acts as its collision proxy, referred to by its CollisionInformation property.

All Collidables which can be used by Entity objects inherit from EntityCollidable. So, to get the entity associated with a broad phase entry, you can either try to cast the BroadPhaseEntry to an EntityCollidable and check its Entity property if it succeeds, or you can store some information in the Tag of the BroadPhaseEntry that you can cast and check.

[diabloqfdb]

Thank you!

Raising terrain level seems to work absolutely flawlessly as long as the terrain raise speed is not very high. In some limited testing it seemed to work very well with a bunch of object on on top of the other, both active and inactive entities.

But lowering the terrain does not always work. The entity gets activated, but sometimes it remains floating. After a time it will settle and deactivate, but it will keep floating. I tried applying a linear velocity, but the object sometimes remains afloat. I also tried activating the simulation island.

[Norbo]

Raising terrain level seems to work absolutely flawlessly as long as the terrain raise speed is not very high. In some limited testing it seemed to work very well with a bunch of object on on top of the other, both active and inactive entities.

You may be able to make it even better by using a nonzero Terrain.Thickness value. If any objects end up below the ground, they will be pulled back up so long as they are within the extruded volume defined by the thickness.

But lowering the terrain does not always work. The entity gets activated, but sometimes it remains floating. After a time it will settle and deactivate, but it will keep floating. I tried applying a linear velocity, but the object sometimes remains afloat. I also tried activating the simulation island.

This is probably caused by old cached contacts (similar to viewtopic.php?f=4&t=2017). Ensuring that floating objects' contacts are cleared should fix it:

Code: Select all

foreach (var pair in Body.CollisionInformation.Pairs)
       pair.ClearContacts();

[diabloqfdb]

Thanks for the reply! Clearing contacts worked great.

I already have thickness assigned to my terrain. Can you make it really large? I have it around 2 meters right now.

I'm back full time developing this project after a short break trying to port it to DirectX with C++. While I am more comfortable working with C++ and performance sensitive stuff, the main reason I returned to the XNA version is BEPU. It is hard to tweak physics to behave consistently and I didn't want to tweak a whole new physics engine. After I would have found a replacement, that is. Especially character controller. It still needs a lot of improvement and I'm going to probably need some help with that, but it works fairly well and I couldn't find a good replacement. Out of the opensource candidates, Bullet looked quite promising. I might have to try it when they finish their GPU accelerated implementation (http://www.youtube.com/watch?v=ZkF4yMmP0R8).

But back to BEPU. Now that terrain deformation response is pretty good and I added static world and physics persistence, I need to add it to mobile entities. I would like to implement quick-save/quick-load. It would be great if quick load would be 100% deterministic, as in loading a scene with objects in collision resulted from player interaction before scene would yield the same result, no matter how many time you load it. My idea was to save the movement related properties of all active entities and just the transforms for inactive ones. At load, inactive ones are placed inactive into their position and active ones get their movement properties restored. Would something like this work? Could you tell me what properties I should store for entities so I can restore them?

Another thing that I'll need to do is speed up level loading, which means speeding up StaticGroup creation. I think this can't be done without modifying BEPU, so I'll start using a self compiled version .Should I switch to the dev branch? How is 1.3 coming along? What are the new features?

I will consider the level made up out off several static "islands", each a static group. I want o go over this group and store all data, structure and relations raw on disk. Then at load, I want to restore it without doing any calculations, thus loading taking as much time as needed to read from disk plus allocating memory and filling in some data. Would something like this work? I need to speed up loading by at least an order of magnitude.

And finally, I'm going to need a way of removing a single static mesh from an already filled in StaticGroup. This is related to terrain deformation. A lot of the clutter on top of the terrain is static, so you can collide with it but no other interactions are available. But when you modify the height of the terrain, you need to adjust the position of some of the clutter objects. My idea was to remove them from the group and add them separately to the space. Further down the line, once in a while a piece of code could run during a low CPU use period that would pick up close isolated statics and recombine them, so during execution eventually one single static group would probably be split into multiple smaller groups. On a level load, these subgroups would be merged back again to avoid broad phase pollution.

[Norbo]

I already have thickness assigned to my terrain. Can you make it really large? I have it around 2 meters right now.

Yup, it would work fine so long as there's nothing beneath the terrain which would care about the fact that it's now inside a terrain

I would like to implement quick-save/quick-load. It would be great if quick load would be 100% deterministic, as in loading a scene with objects in collision resulted from player interaction before scene would yield the same result, no matter how many time you load it. My idea was to save the movement related properties of all active entities and just the transforms for inactive ones. At load, inactive ones are placed inactive into their position and active ones get their movement properties restored. Would something like this work? Could you tell me what properties I should store for entities so I can restore them?

Position, orientation, linear velocity, angular velocity, and activity would be the primary properties. You could indeed omit velocity for inactive objects. Those five would likely produce a roughly reproducible simulation in many cases.

Unfortunately, perfect determinism is going to be extremely difficult to maintain. In fact, for the sake of development time, it might be a good idea to treat it as impossible:
-Objects must be added to the space in the same order.
-Cached data must be identical. To proceed deterministically from a previous simulation, it must be replicated down to the level of individual contacts, warm-starting impulse magnitudes, and contact manifold state.
-The pair generation order must be the same, which means the broad phase was constructed in exactly the same way.
-The solving order must be the same, which means the solver's permutation index must be controlled (easy enough).
-Multithreading must be disabled for a variety of performance sensitive stages (the biggest one being the solver).

And even if all of that is dealt with, it still isn't guaranteed to be deterministic across different platforms due to subtle differences in floating point behavior that can't all be controlled from C#. The JIT has some freedom. It might happen to work on two platforms, but relying on it to always be true would be extremely dangerous.

Other than 'don't bother', the most common solutions for this problem are usually replacing floating point with fixed point math, or implementing floating point operations in software. For a real time physics engine, this could be problematic.

Should I switch to the dev branch? How is 1.3 coming along? What are the new features?

Yes, it would definitely be a good idea to update (though the 'dev' branch was deleted, and the main branch is the updated version of the former dependency free branch.). You can see the changes in v1.3.0 on the XNA fork (they're in the main dependency free fork too, but codeplex seems to hide the pre-merge changesets.)

The largest single new feature would be the inverse kinematics system. It's the same system that I ported to C++ for use with the BEPUik blender plugin. I haven't given it a formal spot in the API yet, but I'll probably put it into its own library soon.

The most noticeable behavioral change is likely the new collision softness support via CollisionResponseSettings.Softness. It's an extremely small change in terms of code, but stacks and other difficult collision-related configurations should behave a lot better now. It's not quite done, though; allowed penetration margins cause odd behavior in some cases. The old behavior is equivalent to setting CollisionResponseSettings.Softness = 0.

Other than that, there have been quite a few bug fixes, behavior improvements, and organizational changes. Most significantly for the purposes of porting is the existence of a separate BEPUutilities project which BEPUphysics depends upon. It contains all the general helpers that are used by BEPUphysics but are not specific to physics.

Another thing that I'll need to do is speed up level loading, which means speeding up StaticGroup creation. I think this can't be done without modifying BEPU, so I'll start using a self compiled version ...

I will consider the level made up out off several static "islands", each a static group. I want o go over this group and store all data, structure and relations raw on disk. Then at load, I want to restore it without doing any calculations, thus loading taking as much time as needed to read from disk plus allocating memory and filling in some data. Would something like this work? I need to speed up loading by at least an order of magnitude.

Persisting the internal hierarchies would indeed require some custom modifications. Careful management of persistence could probably get you the needed boost.

However, the hierarchies are in for a significant overhaul in the not-hugely-distant future. In addition to some new mutable hierarchies and better memory access behavior/performance in general, part of that overhaul will probably introduce high performance hierarchies designed for offline building. They will require some amount of built-in persistence management since they'd take too long to build at runtime. It may not be wise to wait on me to get that done, but keep it in mind.

And finally, I'm going to need a way of removing a single static mesh from an already filled in StaticGroup. This is related to terrain deformation. A lot of the clutter on top of the terrain is static, so you can collide with it but no other interactions are available. But when you modify the height of the terrain, you need to adjust the position of some of the clutter objects. My idea was to remove them from the group and add them separately to the space. Further down the line, once in a while a piece of code could run during a low CPU use period that would pick up close isolated statics and recombine them, so during execution eventually one single static group would probably be split into multiple smaller groups. On a level load, these subgroups would be merged back again to avoid broad phase pollution.

StaticGroups were built with mutability in mind for the future, but they do not yet support it. That would come along with the previously mentioned hierarchy overhauls. For now, removes and topology changes in general would require a hierarchy reconstruction.

It sounds like you might not need to modify topology, though. If an object is merely moving a little bit, you could scoot it while keeping it in the StaticGroup, and then call the StaticGroupShape.CollidableTree.Refit function. It's extremely fast compared to a full reconstruction. After lots of significant displacements, it might be a good idea to eventually call a Reconstruct just to improve performance, but that will be rare.

[diabloqfdb]

Wow, a lot to think about.

I'll go ahead and and try first mobile entities persistence. Hopefully I can get it to work and is reasonably deterministic. If not, I might make it so that saving advances in game time by 5 minutes, so that in real time I can call update repeatedly and hope that the most mobile entities have settled.

And for static persistence, maybe I'll start with something simple. Would there be anything to gain by caching on disk Terrain internals? I am currently loading at most 256 MiB of terrain height data.

[Norbo]

Would there be anything to gain by caching on disk Terrain internals? I am currently loading at most 256 MiB of terrain height data.

Not particularly; it doesn't need any acceleration structure. The heightmap array is all there is.

[diabloqfdb]

Loading a 64 square kilometer map with 4096 chunks used to take over 2.7 + 2.5 seconds, with 2.7 being the disk read speed and 2.5 the time it takes BEPU to populate the space. This is without any clutter. Loading a full map with clutter can take around 2-3 minutes. I figured out that C# is very slow at reading floats from a stream, so now I load byte arrays and use BlockCopy, so my load time from disk is down to 0.5 seconds.

The 4096 are perfectly aligned in a grid. Do you have any idea what kind of performance on load I could gain by persisting the internal structure of the space like I mentioned before? What volume would the data have. I am trying to figure out where and how much effort to invest.

[Norbo]

If the simulation is actually able to run in real time, the set up of the space itself should not be significant. The BroadPhase is the largest single initialization expense but it should still only take a matter of milliseconds. It is unlikely that persisting the space itself would be useful.

My guess would be that the time is spent in the reconstruction of hierarchies for every mesh. This is more likely if the clutter is a bunch of StaticMeshes instead of shared-shape InstancedMeshes.

Fortunately, no guessing is required! I would recommend grabbing a profiler or otherwise instrumenting your code to isolate where the load time is being spent. With that, you'll have all the information you need to choose which areas to focus on.

[diabloqfdb]

I have traces surround key areas of code with execution time and other info recorded.

Maybe I'm doing something wrong, but just adding 4096 terrain objects takes 2.5 seconds. This is just the terrain. If I add clutter which uses InstancedMeshShape, the time easily goes up to over 2 minutes. It takes 4 minutes maximum with extremely dense clutter. I add the collidables to a list, and add them to space with groups:

Code: Select all

chunk.container = new StaticGroup(chunk.Collidables);
Space.Add(chunk.container);

But first, I'd like to make sure that loading just the terrain is as fast as possible. It takes 0.5 seconds to load all the floats from disk, so I would like space creation to be faster than that, since disk read is a major bottleneck.

[Norbo]

I would recommend performing much narrower profiling to verify which very specific part of the loading is taking the time. Run a proper profiling application like ANTS, SlimTune, EQATEC, etc. These will help identify what areas you should pay attention to, or they might just immediately reveal the problem directly. Once you have more information you can drill down to the level of instrumenting individual chunks and portions of the chunk initialization process. Incrementally refining this would tell you what code and what data is responsible if the profiler's results do not. (The profiler should be able to tell you the code path that is taking the time, but it may be difficult to notice details, e.g. one chunk is taking 40x longer than others, without breaking it down further. Some profilers make this easier than others.)

Drilling down to that level of detail or lower would quickly eliminate any ambiguity about the source by showing what code is responsible and if any data has an abnormally high cost.

[diabloqfdb]

I am testing and optimizing and measuring. This will take same time since I need to work on the real features.

Meanwhile I created as system of logical coordinates and sizes. Now everything is expressed in meters, but the real floating point value for one meter can be changed for each execution. When I first started out with BEPU, I had problems with object tunneling and you said that my scale was too big. I reduced it back then, but now I wanted to reduce it again so I came up with this system.

And it works just fine, but the simulation has changed in subtle ways. Things are floaty again, so I need to adjust g again. Traction has more of an acceleration tot it, like when trying to run up fast a slope that is too steep. You'll come to a stop. If you slowly move the camera in order to to reduce the slope, by looking left or right, you may start to advance slowly and as soon as you have enough traction you will be semi-violently accelerated forwards, like in a car when suddenly pressing down on acceleration and being pushed back into the seat. This was not present before the scale reduction.

Also, things are easier to move and push. It must be g again. I figured out dimensions, but what about weight. I am trying to achieve a realistic physics simulation where one meter is 1.0f. So g should be -9.8? And how do I scale this? I have formulas for transforming from local coordinates to absolutes and back, but how do I scale g? If my new meter m' = m X f, should my new g be g' = g x f? And in this system what units should I consider mass to be in? What If I want to give an object a weight of 1 kg? What mass should I give it.

Sorry for the basic questions, but it has been a long time since I last touched a physics book .

In the meantime I am also working on a character movement system with stats and behaviors, so I am heavily using and modifying CharacterController. I need to make judgements based on current speed, maximal achieved speed, how long did you go over a given speed and the most difficult parts: are you jumping, from how high did you jump, what is the impact force and what is in general the impact force when running and smashing into something. I need to reduce character HP and stamina accordingly and maybe add some pushback or tip over to the controller. I'm thinking that it would be best to deactivate the controller for the tip over animation and take away control until you stand up.

[Norbo]

I am trying to achieve a realistic physics simulation where one meter is 1.0f. So g should be -9.8?

In order to make things appear to respond Earthily to gravity, the gravity should be ~9.8 times greater than however many units it takes to represent a meter.

Note that this is distinct from just saying 'if one meter is 1.0, gravity should be -9.8 for Earthlike behavior'; while that's one special case, it is not the only possibility. For example, if your objects are all on the scale of 10 kilometers long and gravity is 9.8, you could represent the same simulation with 10km = 1.0f and gravity = -0.00098f. The best choice depends on numerical concerns. Generally, sticking within the default of 0.5 to 10 units for an objects' dimensions is simplest.

If the simulation scale falls outside of the default 0.5 to 10 units for object dimensions, you could make use of the ConfigurationHelper.ApplyScale method. A good heuristic for choosing the scale value is to figure out what gravity value you need for your current simulation size, and divide it by 10. (This works out because 0.5-10 unit dimensions and ~10 gravity is what the default values were built for. If your gravity needs to be 100 instead of 10 for things to look right, it usually (but not always) implies that everything is about 10 times larger than the default configuration assumed.)

Make sure you use the v1.3.0 version of ConfigurationHelper.ApplyScale. It includes additional tuning factors compared to earlier versions. Also, note that the ApplyScale method has limits; if you go too far up or too far down, numerical issues will start to creep in.

but how do I scale g?

Multiply it by exactly the same factor as all the other distances and velocities.

And in this system what units should I consider mass to be in?

Whatever you want, so long as it's numerically kind. It's easiest to stay near the 0.1 to 100 range for masses (100 being really heavy, and 0.1 being really light) because that plays nice with the default settings for constraint rigidity and the solver short circuiting. All of those values can be tweaked, of course, but it's easier not to do anything.

Mass does not need to be scaled with distance/velocity/acceleration.


Once you get the above scaling issues controlled, then you can go back and tune things like character controller speed and force.

[diabloqfdb]

I would recommend performing much narrower profiling to verify which very specific part of the loading is taking the time. Run a proper profiling application like ANTS, SlimTune, EQATEC, etc. These will help identify what areas you should pay attention to, or they might just immediately reveal the problem directly. Once you have more information you can drill down to the level of instrumenting individual chunks and portions of the chunk initialization process. Incrementally refining this would tell you what code and what data is responsible if the profiler's results do not. (The profiler should be able to tell you the code path that is taking the time, but it may be difficult to notice details, e.g. one chunk is taking 40x longer than others, without breaking it down further. Some profilers make this easier than others.)

Drilling down to that level of detail or lower would quickly eliminate any ambiguity about the source by showing what code is responsible and if any data has an abnormally high cost.

Sorry to bring up this again, but I did manage to find time and do some extra testing. I now have detailed logs of all the stages of the loading process:

Terrain loaded in 0,491490210570191 seconds
Generating 5329 physics chunks...
One physics chunk time 0,0205506251331826 seconds
One physics chunk time 0,00379370992959593 seconds
One physics chunk time 0,000918521029234398 seconds
One physics chunk time 0,00048491752386326 seconds
One physics chunk time 0,000508650260599097 seconds
One physics chunk time 0,000494538904604269 seconds
One physics chunk time 0,000482031111459946 seconds
One physics chunk time 0,000506084561493481 seconds
One physics chunk time 0,00049550104449736 seconds
One physics chunk time 0,000539438678970328 seconds
...
// 5000+ entries later
Average chunk physics load time: 0,000504841490453611
Terrain collision data generation finished in 2,71854610693117 seconds
Grass loaded in 0,000548739342775662 seconds
Total terrain generation finished in 2,80941169754442 seconds

Almost tree seconds is not that much, but since this is at the heart of a streaming engine for really large terrain, I am wondering if I could improve this. Loading the 5329 chunks form disk takes around 0.5 seconds and adding one to the space takes on average 0.0005 seconds, but since I have so many chunks, the time adds up. And terrain is the easy part.

Since terrain is a simple grid of Terrain objects that are perfectly aligned and touching and I know without computing the bounding box for it, I was wondering if there would be a way to speed up just this stage of the space population.

Thank you!