Best way to handle physics for voxel based terrain?

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
MitchellKrenz
Posts: 6
Joined: Thu Jul 02, 2015 2:26 pm

Best way to handle physics for voxel based terrain?

Post by MitchellKrenz »

Hi,

It's me again (I asked a question a few days ago about the ModelDrawer). You were so helpful with my other question I thought I'd bother you again :)

So a recap, my friend and I are writing a voxel based game like minecraft much much more so like an RPG. We have decided that most terrain will not be changeable though, just the area a users "home" is and "Cave instances"

Here is what I tried so far:
Had a one layer thick 40x40 square of cubes, even have a nice texture loaded on all of them. Used the fantastic BEPU CharacterController for movement and collision handling, wrote a basic nice camera and all of the cubes for the floor were kinematic entities of the Box type in the prefabEntites namespace. this worked fine for 40x40=1600 cubes. However I noticed that up scaling to 80x80=6400 started to lag seriously bad.

Second I re looked over all of the tutorials to see if i could find a better way since they all had lots of objects with collision and rendered just fine. I thought my problem might be because even though the boxes are kinematic since they are all touching if I step on one it has to do collisions for all of them. I also figured when looking at the code in Space.Add() that the Box prefab implemented way more functionality then I needed for terrain, since all I really need is collision detection so the entities don't fall though. I saw the collision filtering demo and thought about setting it up so none of the boxes did Broad Phase collision with any other terrain boxes but after looking at the code implementation this seemed unfeasible since every box would have to have a collision rule pair for every other box, or maybe just the ones directly next to it? But still this didn't solve the issue of each call to Space.Update doing way more things then it needed to for an entity that never moves and basically is just a floor. I'm not sure which if any of my assumptions were correct but either way it seemed like the prefab box was the wrong way to go.

Then I saw the tutorial for Compound entities and I was inspired. basically I could just create all of my grass blocks and for each one create a corresponding CompoundShapeEntry and the create a parent CompoundShape. This worked fairly well but I immediately noticed that the children collection seems to be immutable. So for the areas that users can place and remove blocks Id need to either not use CompoundShapes at all or destroy and recreate the parent compound with every change, which sounds expensive.

I know almost nothing about static meshes but the use of the word static makes it sound like it is optimized for this type of purpose. and then I would use that for the non changing areas and a different solution for the areas that can be changed.
I figured that it had gotten to the point where I should probably ask you how you would handle each situation if you were the one writing this application. In code all of my blocks are in a large array currently and then my blocks basically inherit from the base physics types I need, not sure if that's correct either or if I should just instantiate the type and keep it as a property. To summarize I basically have a static terrain built out of boxes that could some time later become a dynamic terrain but not often and then some randomly generated caves that are built completely out of boxes that can be added and removed. So should I be using the prefab Box, the BoxShape in a CompoundShape, a StaticMesh, or is there some other even better way? especially if all of the default terrain will be pre-designed by me before the launch of the game.

Sorry I got so verbose, and again thanks for any help and for the great engine!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Best way to handle physics for voxel based terrain?

Post by Norbo »

I saw the collision filtering demo and thought about setting it up so none of the boxes did Broad Phase collision with any other terrain boxes but after looking at the code implementation this seemed unfeasible since every box would have to have a collision rule pair for every other box, or maybe just the ones directly next to it?
Objects can be assigned to collision groups, and rules can be created between collision groups. In fact, the engine puts kinematic entities into their own collision group that doesn't collide with other kinematic or static objects by default, since they can't respond to collisions anyway. (More information can be found in the collision groups documentation.)

The reason why you're seeing a slowdown is probably because the broadphase is forced to consider every single touching pair as a potential collision pair, causing deep traversals and collision rule computations. In a tight voxel grid, every box is near 26 other boxes. A solid box of 50x50x50 boxes would cause many millions of unnecessary operations. Ideally, the broad phase would be smart enough to realize that it never needs to do these traversals and collision rule computations in the first place. That's on the roadmap for v2.0.

The other stuff entities do would also slow things down a little bit too, but not as much.
I figured that it had gotten to the point where I should probably ask you how you would handle each situation if you were the one writing this application.
If I was the one doing it, I would probably build a custom collidable that uses the unique guarantees of a voxel grid as an implicit acceleration structure. Unfortunately, that requires a good deal of effort and familiarity with the engine's internals.

So, if not a custom collidable, I would probably use a StaticGroup. They recently gained support for mutability via StaticGroup.Shape.Add/Remove. Note that the order of adds and removes can affect the quality of the tree. If a pathological series of operations occurs, you may have to reconstruct the tree to improve the quality. Generally, random-ish operations are best for maintaining quality.

Another common approach is to use a StaticMesh. This is indeed much more expensive to change, but it has two advantages over StaticGroups:
1) It can represent non-box geometry, which is important if the voxels are ever smoothed.
2) Triangle meshes have special boundary smoothing logic to stop bumps between triangles connected by the index list.

Due to the expense of rebuilding StaticMeshes, the work is usually thrown onto a background thread. This introduces latency on every modification, but it's usually acceptable.
In code all of my blocks are in a large array currently and then my blocks basically inherit from the base physics types I need, not sure if that's correct either or if I should just instantiate the type and keep it as a property.
I recommend against inheriting from any of the physics types usually. It isn't a big problem, but it usually leads to architectural awkwardness down the road. It's usually easier when a gameplay logic object has a physics representation, rather than a gameplay object is a physics object.
MitchellKrenz
Posts: 6
Joined: Thu Jul 02, 2015 2:26 pm

Re: Best way to handle physics for voxel based terrain?

Post by MitchellKrenz »

Thanks Norbo,

I'll try out your recommendations and let you know how it goes. Thanks again for your feedback and help!

Mitch.
mcmonkey
Posts: 92
Joined: Fri Apr 17, 2015 11:42 pm

Re: Best way to handle physics for voxel based terrain?

Post by mcmonkey »

Hello there! I'm working on a similar project (in that it's a Voxel based world at least) and have an answer and a question.

First, the answer:

A StaticMesh, in my experience so far, is a fantastic solution for building Voxel terrain into BEPU - at least it is after you get it constructing off-thread. If you're relatively new, I would recommend researching that as the solution for you - I've used to to great success, and you should be able to copy/paste a fair bit of code off your rendering code (You render triangles, right? StaticMesh is just a structure of the exact same triangles!)

Now then, onto the question that will possibly help OP if he feels like getting advanced, but is mostly for my own sake...
If I was the one doing it, I would probably build a custom collidable that uses the unique guarantees of a voxel grid as an implicit acceleration structure. Unfortunately, that requires a good deal of effort and familiarity with the engine's internals.
So... a staticmesh is indeed fantastic as I said above, yet it's not /perfect/ enough for my obsessive tastes. It eats RAM on both server and client that it doesn't need to, and it runs slower than it can.

In standard Voxel (pure cubic) setups, it's super-duper easy to collide anything against Voxels.
In my case, I don't have a pure cubic setup, I'm still using voxels but they can have datavalues that give them angles or shapes or whatever... this makes it harder to just collide things against the Voxels... but it still leaves room for a massively capable acceleration structure!

So, my question is... how should I go about starting to write my own static collision shape.

My ideal vision at the moment of it is:
Use the laws of voxels to find the small number of blocks that are relevant at all to the collision (in 90% of convex or ray traces, this'll be like... 10 blocks max) and then from there use the triangle-vs-whatever collision code to collide those few blocks in roughly the same way as if I had a staticmesh (except it would only go through the relevant blocks on exposed faces, and not anything else).

My BACKUP plan is to build a static mesh of all NON-cubic blocks, to collide as I already have them functioning, and then for cubic blocks, instead of that, have a static VoxelChunk type collider that uses the AABB-vs-whatever collision code for anything incoming

So, which of these two plans sounds better to you and how would I go about starting to do whichever one that is?

I realize this will likely be pretty complex to set up... but I believe I'm ready for the challenge.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Best way to handle physics for voxel based terrain?

Post by Norbo »

So, my question is... how should I go about starting to write my own static collision shape.
There are three main conceptual parts:
1) Create the StaticCollidable subtype itself and its shape. Cloning the Terrain and its TerrainShape to begin with may be a good idea. They have an implicit structure that's used for collision. You can get rid of the complexity associated with affine transforms most likely.
2) Create the necessary queries using the voxel grid. (The fun and easy part!)
3) Create collision pair handlers for every supported collision type that use the midphase and register them with the narrow phase. For examples of these pair handlers, check out the TerrainConvexPairHandler and its TerrainConvexContactManifold, the TerrainSpherePairHandler and its TerrainSphereContactManifold (a special case for spheres) the CompoundPairTerrainHandler, and the MobileMeshTerrainPairHandler. Register your pair handler types with the NarrowPhaseHelper.CollisionManagers dictionary.

If you wanted to support different shape types as children of the voxel grid, you may want to do something closer to the StaticGroupPairHandler.

A few notes:
1) A lot of functionality is held in the base classes of these listed types. If something seems to come out of nowhere, it's probably stuffed higher in the inheritance hierarchy.
2) Be very careful about initializing and cleaning up the pair handlers correctly. It's possible to create extremely difficult to debug problems...
3) You may notice the Terrain and other mesh collision types have a lot of logic dedicated to boundary smoothing. This does not trivially generalize to voxels. I'd recommend ignoring it and not implementing smoothing if at all possible. It tends to be very hard to make that sort of thing 100% robust.
4) You're going to be trudging around in the grossest parts of the engine. Expect most of the structure to completely change once v2.0 rolls around, possibly invalidating a lot of effort.
Post Reply