voxel object vs voxel object collision

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
Nablabla
Posts: 14
Joined: Wed Mar 18, 2015 12:36 am

voxel object vs voxel object collision

Post by Nablabla »

hi everybody (me newbe), I have tested three other physics enignes and I found bepu ist best for c# . (congratulations and big thx!!)

I want to create a game which contains multiple big voxel objects (like star made, blockade runner or space engineers),
which behave physically correct. A major challange i face is to provide a collision handling.
The "blockade runner"-guys use the jitter engine, but I dont see any support of that in any sense.This guy:
https://www.youtube.com/watch?v=7h_hObw ... be&t=2m26s
does have some objects separating and having collisions, but I think he is using the compound shapes.

I think just using compound shaps does not suite my purpose, since my objects should be very very big and "in-convex", like planets or terrains and
star ships or space stations.

I have looked at a lot of the bepu code the last days (and three other engines.. :shock: )
I have several ideas, but some may not be possible (or I do not know how to implement them into bepu, but again it has a very good architecture in my eyes)

#1 I do not know how it would perform using one of those mass-mesh-bodies (MobileMeshShape?), but I assume that at least for the terrain, its not possible or would you say, that it is sufficient for realizing my dreams?

#2 My fav Idea is to add a new type of Entity<...> or shape which queries recursively over my voxel object(s)(which is oct-tree based)
and returns contact points and merges them (as the engine is alredy capable of).
I assumed that the shape is in some way telling the narrow phase if it collides with another obect and I would distinguish only between other voxel object and everything else. Where for other voxel objects I would go down the hierachy simultaneously and for other objects I would use some ghost boxes to get the contact points return them and the parent node does the merging of the contact points.
This is my favorite idea, but I do not see how I can put this into the engine.
I do not know where to put algorithms and so on.
What I need: A way to define a new type of collision shape and how (or where) its collisions will be computed. Meaning what happens in the narrow phase.
I must get the two candidates and return the contact points.
I tried to inherit from the narrow phase and punch that in, but where the actual collision detection is happening ... I dont understand that


#3 Another idea is to use (inherit from) a compound shape and only fill it with the next 8 nodes in the oct tree, and replacing them ad-hoc - when they collide - by new this kind of (inherited) compound shapes which act similarly. And if the contact of the two objects dissappear they go back to the original 8 boxes. (or I somehow start with one).
This is an idea which might be easer to implement with compareble performance, but CompoundBodies can only consist of CompoundShapeEntry which can not be CompoundBodies on their own. So I think ... dunno

#4 Overriding the broad phase or just returning false/no collison/disposing the contact in some way if it does not really collide after the regular narrow phase of the bounding boxes would not suffice since I need new contact points if so. Or can I just change those somehow? I assume this would break a lot


I would be really grateful for some suggestions or links to anything which is related to this kind of problem.
Or some Ideas or way how I can do that in the bepu engine.
And I am sorry in case I did not make myself very clear, I think this idea is very strange :mrgreen:
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: voxel object vs voxel object collision

Post by Norbo »

want to create a game which contains multiple big voxel objects (like star made, blockade runner or space engineers),
which behave physically correct. A major challange i face is to provide a collision handling.
The "blockade runner"-guys use the jitter engine, but I dont see any support of that in any sense.This guy:
https://www.youtube.com/watch?v=7h_hObw ... be&t=2m26s
does have some objects separating and having collisions, but I think he is using the compound shapes. I think just using compound shaps does not suite my purpose, since my objects should be very very big and "in-convex", like planets or terrains and
star ships or space stations.
I think Blockade Runner actually uses BEPUphysics these days. Not sure about that, but I thought I saw a development update about it.

For anything that can reasonably be a dynamic object in the first place, compound shapes do tend to be a good choice. They support concavity and have a reasonably speedy acceleration structure built in.

In addition to the other games using it for similar purposes, I made a prototype destructible spaceship a couple of years ago based on compounds. It scaled from hundreds of small ships of a couple dozen pieces to large ships composed of hundreds or thousands of pieces. I've never released it, but it was a decent proof that it can work.

That said, CompoundShapes aren't great for things with truly enormous numbers of subshapes, like a planet composed of millions of pieces. This is mostly because they refit their acceleration structure in world space every frame. For such things, a MobileMeshShape will actually be a better option since its acceleration hierarchy is local and does not need to be updated as the object moves.

If the object doesn't move, then using StaticMesh, InstancedMesh, Terrain, and StaticGroup is recommended.
#2 My fav Idea is to add a new type of Entity<...> or shape which queries recursively over my voxel object(s)(which is oct-tree based)
and returns contact points and merges them (as the engine is alredy capable of).
While creating a shape that uses voxel structures directly rather than creating a compound shape would work, creating custom collision detection routines is not easy. I would avoid doing this unless you truly need the extra performance that might be gained by a specialized data structure.

To do this, you would need to create a custom collidable and shape (similar to the CompoundCollidable and CompoundShape), the CollidablePairHandlers for all of the supported collision type pairs, and then register them in the NarrowPhaseHelper.CollisionManagers dictionary. The custom CollidablePairHandlers would need to collect contacts and report them to the solver. Generally, pair handlers have a contact manifold object in them which is actually responsible for doing the contact generation (as in all StandardPairHandlers), or the pair handler may manage sub-pair handlers (as in all GroupPairHandlers). The CompoundConvexPairHandler is a decent starting point- beware, it's extremely easy to get lost in the byzantine inheritance hierarchy.

The above is a very high level overview. The devil is in the details, and there are a lot of ways to screw up the fiddly bits as you may notice when trying to traverse the implementation details of CleanUp. In addition, there is a high probability going forward that I will make sweeping breaking changes to the architecture of the CollidablePairHandler as a part of a nearly-entire-engine-rewrite sometime this year.
#3 Another idea is to use (inherit from) a compound shape and only fill it with the next 8 nodes in the oct tree, and replacing them ad-hoc - when they collide - by new this kind of (inherited) compound shapes which act similarly. And if the contact of the two objects dissappear they go back to the original 8 boxes. (or I somehow start with one).
This is an idea which might be easer to implement with compareble performance, but CompoundBodies can only consist of CompoundShapeEntry which can not be CompoundBodies on their own. So I think ... dunno
CompoundShapes can have child CompoundShapes. Check out the EntityConstructionDemo in the BEPUphysicsDemos. I wouldn't recommend trying to use this fact to accelerate collision detection though. The compound's acceleration structure already takes care of that.
Nablabla
Posts: 14
Joined: Wed Mar 18, 2015 12:36 am

Re: voxel object vs voxel object collision

Post by Nablabla »

wow! Thanks so much for your answer, you are great!
I think Blockade Runner actually uses BEPUphysics these days.
Pah, so the jitter guys should stop advertising their engine with it :x
The bepu engine IS the best engine for c# or not?, but it took me three days to get to know that. I dont want to discredit anybodys hard work, but there should be more evaluations/comparisons out there in the internet. The only thing I found was that: https://www.youtube.com/watch?v=3kX8zfBokW4 And thats just fraud.

Anyways, your answer is very helpful. I will try going with the compound shapes at first and maybe later try to implement my idea #3 to add the parts only when needen. Because I later want that it is possible, that parts of the voxel object are not even in memory :D
And use the static meshes for terrain. But your prototype does interrest me ;)

But you also answered my other question, that's so neat :)
I will come back to that later.

Nablabla
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: voxel object vs voxel object collision

Post by Norbo »

Pah, so the jitter guys should stop advertising their engine with it :x
The bepu engine IS the best engine for c# or not?, but it took me three days to get to know that. I dont want to discredit anybodys hard work, but there should be more evaluations/comparisons out there in the internet. The only thing I found was that: https://www.youtube.com/watch?v=3kX8zfBokW4 And thats just fraud.
To be fair, these are indie-ish free open source projects. It's a little time consuming to keep track of a base of developers who aren't obligated to tell you anything. I tried once and gave up before posting any sort of gallery :P

I can also understand the lack of evaluations. Besides just feeling kinda gross to do a bunch of benchmarks and poopoo on someone who isn't making any money on it, it's also tricky to do it right without being really familiar with every engine (as that video shows).
Nablabla
Posts: 14
Joined: Wed Mar 18, 2015 12:36 am

Re: voxel object vs voxel object collision

Post by Nablabla »

It has been a long time and I have been advancing quite a bit, thank you for your help so far and sorry for my frustration statement :oops:

Okey, I have used compound shapes as you recommended and it indeed works good :)
The performace is quite good as you stated, it starts to get slower with 15.000 box shapes in a compound
I am constructing a hierarchy of compound objects, so if a single block gets changed, it does not need to compute the whole structure again, but only
the leaf, its parent, its parent's parent, ..., its parent's parent's ... parent and the root node. So for each of these levels I construct a new compound shape of the 0-7 ones I already have and the new one. It is O(log(n))-kind-ish. I saw that this computes the inertia and mass distribution which is ok, if it is done that way.
And finally I do this: _morphableRigidBody.SetCollisionInformation(Shape.GetCollidableInstance(), Mass);
I think it constructs the whole hierarchy again, am I right? If so, is there a way hat it does not construct the whole hierarchy again? Or whatever it does, which takes time, not do it all from scratch?
And as you say, the compound shapes refit their acceleration structure every step, hmm, so I will switch to MobileMeshShape or to implementing my own custom collidable.

But until that, I have another concern: When I do a ConvexCast (for getting everythin in visible range) It takes very much computation time, I think it does it exactly.

Code: Select all

PhysicSpace.ConvexCast(
                new BEPUphysics.CollisionShapes.ConvexShapes.SphereShape(vieRadius),
                ref trans,
                ref zero,
                result);
Is there a way to get broadcast results, like getting everything who's broadcast shape is colliding with my view sphere?

Thx in advance
Nablabla
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: voxel object vs voxel object collision

Post by Norbo »

I think it constructs the whole hierarchy again, am I right? If so, is there a way hat it does not construct the whole hierarchy again? Or whatever it does, which takes time, not do it all from scratch?
Yes, the acceleration hierarchy is constructed when the collidable is created, and using shape.GetCollidableInstance will create all the CompoundCollidables from scratch.

For now, the easiest approach to improving this is to just plop the construction work onto another thread and check if it's done each frame. This will introduce a frame of latency or two to modifications.

Another possible modification would be to add a CompoundCollidable constructor that takes a set of existing collidables rather than shapes. You could then reuse other CompoundCollidables so that only a tiny fraction of the whole hierarchy gets changed.

(The solution that will eventually get implemented is a dynamic hierarchy, like the one currently used for broad phase collision detection (except with a significantly better implementation). This would permit topological changes in the hierarchy without reconstruction, plus the option to run refinement iterations on demand to improve the quality of the tree incrementally without any single huge monolithic step.)
I have another concern: When I do a ConvexCast (for getting everythin in visible range) It takes very much computation time, I think it does it exactly.
ConvexCast does indeed perform an exact test between shapes. Further, since it is a cast, it's often forced to use slower tests than discrete collision would.

Using the Space.BroadPhase.QueryAccelerator.GetEntries overload that takes a BoundingSphere would be a lot faster. Depending on the scene, though, it may be even faster to just check the squared distances between object positions and the view position; querying the broad phase structure with an enormous shape will end up descending most of the hierarchy.
Nablabla
Posts: 14
Joined: Wed Mar 18, 2015 12:36 am

Re: voxel object vs voxel object collision

Post by Nablabla »

Yes, the acceleration hierarchy is constructed when the collidable is created, and using shape.GetCollidableInstance will create all the CompoundCollidables from scratch.
So, when I use a mobile mesh and change it a bit, lets say remove 4 and add 4 out of several million, does it also recreate the hierarchy? Because changing a compound shape does take too long now. (I mean the shape.GetCollidableInstance takes a lot of time)
That said, CompoundShapes aren't great for things with truly enormous numbers of subshapes, like a planet composed of millions of pieces. This is mostly because they refit their acceleration structure in world space every frame. For such things, a MobileMeshShape will actually be a better option since its acceleration hierarchy is local and does not need to be updated as the object moves.
You mean for a big moving thing the mobile mesh is better, but changing it is slow, and for big things not moving like planets (I mean, planets do not move :lol: ) there is no optimal choice right now.
(The solution that will eventually get implemented is a dynamic hierarchy, like the one currently used for broad phase collision detection (except with a significantly better implementation). This would permit topological changes in the hierarchy without reconstruction, plus the option to run refinement iterations on demand to improve the quality of the tree incrementally without any single huge monolithic step.)
when? I mean, about when?
Sounds like the best option, I think I will wait for that

Another concern: Is there any chance to combine multiple spaces?
I want to have a very big space combined of multiple BEPUphysics.Spaces, linear grid like, to overcome the inaccuracy of floats or load only parts of the universe. Or for moving spaces (for moving planets).
Is there any way to let objects of different BEPUphysics.Spaces physically interact with each other, and say the objects of one space are 1000.0f to the left of the other?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: voxel object vs voxel object collision

Post by Norbo »

So, when I use a mobile mesh and change it a bit, lets say remove 4 and add 4 out of several million, does it also recreate the hierarchy? Because changing a compound shape does take too long now. (I mean the shape.GetCollidableInstance takes a lot of time)
Yes, changes to the topology of the mesh would require a reconstruction of the hierarchy right now. The only value of the local space structures is in avoiding refit operations every frame.
You mean for a big moving thing the mobile mesh is better, but changing it is slow, and for big things not moving like planets (I mean, planets do not move :lol: ) there is no optimal choice right now.
For large unmoving objects that need to be modified at runtime, the usual recommendation today is to chunk it into smaller pieces. Any changes end up affecting a small part of the whole, so the reconstruction overhead is much reduced. Chunked StaticMeshes like this have been used quite a few times in voxel world games using BEPUphysics, often combined with asynchronous modifications.

Technically, this approach would also work for moving kinematic objects. The individual chunks would have their positions, orientations, and velocities set every frame to keep them in line with the whole.

But for enormous complicated dynamically moving objects which change at runtime, there's no silver bullet today. Chunking is difficult for dynamic objects, because the chunks need to interact to propagate physical effects. This could be doable with constraints, but it won't be perfectly rigid without further hacking at the position level. Doing the work asynchronously and waiting on the result to avoid stalling the game is the current easiest workaround, as mentioned.
when? I mean, about when?
Sounds like the best option, I think I will wait for that
Hard to say. I'm jumping around to a lot of things in development, and BEPUphysics is only one part of it. I expect to package up BEPUphysics v1.4.0 as a packaged release in the next couple of months. It won't include any major features over the current development branch, probably just a few bug fixes. That will give people a stable baseline to work with while I rip up the foundations of the engine for v2.0.0 over the coming year.

One of the earlier changes in v2.0.0 is probably going to be changes to continuous collision detection, which will require some changes to pair management. After that comes deactivation-broadphase-narrowphase-solver pipeline architectural optimizations, which will include a ground up rewrite of the broad phase. Then there's rewriting the solver with a focus on improving cache behavior and vectorization under RyuJIT. After that comes the miscellaneous changes that didn't get hit by the rest of it; I expect things like events and interpolation buffers will show up in this phase, and maybe improvements to some of the low level collision routines.

So the question is where the 'auxiliary' hierarchies used by collision shapes fit into this roadmap. There are two likely places: either alongside the broadphase revamp (since the algorithms are virtually identical), or near the end when the low level collision routines get refined. If it's a part of the broad phase revamp, you're looking at some point in the next 6 months (assuming I don't get distracted rewriting a graphics engine or something in the interim). If it ends up being done as part of the final phase, it could be well into 2016. At this point, I can't say for sure which it will be.
Another concern: Is there any chance to combine multiple spaces?
I want to have a very big space combined of multiple BEPUphysics.Spaces, linear grid like, to overcome the inaccuracy of floats or load only parts of the universe. Or for moving spaces (for moving planets).
Is there any way to let objects of different BEPUphysics.Spaces physically interact with each other, and say the objects of one space are 1000.0f to the left of the other?
There is no prebuilt helper for this sort of thing. It's doable, but it gets nasty at the border between spaces, since objects in different spaces cannot interact by default. You could create proxy objects in the other space and try to bind the proxy to the original to propagate physical effects between them.

I've considered a few approaches to support 'big world' scenarios as they are very relevant to the other things I'm working on. For example, the broad phase could be modified to compare not only against itself but also against adjacent broad phase structures, while taking into account their different origins. I have no plans to actually implement such a thing, though. Unfortunately, the needs of such a locally segmented simulation are quite different from a fully network-distributed simulation, and while the distributed solution could work for the local case, it is way out of scope for a physics engine as it includes all sorts of application specific logic.
Post Reply