Collision Against Uniform Grid (Voxel) Without Creating Mesh

[Layla]

I thought I'd get a conversation going about ways to tackle this problem seeing as this forum seems to be quite active and helpful.

My game level is made up of a simple uniform grid, there's either a block there or there isn't, super simple. So because the environment is so simple, surely the collision detection can be super simple too. The first thing people try is to just pass the triangle mesh of the level to the physics engine, this works but it's not ideal as the collision mesh needs to be updated constantly when editing the level. The level can be split up into many triangle meshes but I still think we can be much smarter about it.

My thinking is to just work out the collision from the block data array only, why is a triangle collision mesh needed when you can represent the level with a simple array of block values. It would be great if we can get some discussion going on how to best handle this or even have a special shape in newton to handle it because I'm sure many games would benefit from it.

[Julio Jerez]

Is the level a voxel space represented by an octree, when you have convened large voxels, or are they all just simple uniform size boxes?
It seems voxel worlds are becoming very popular these days, maybe I should add a native support for that.

you are right, the voxel space can be specialized with box shapes instead of collision shapes.

The one thing you can do is this, make a scene collision and add all the boxes that make you voxel model, as boxes.
The tree will because of Newton instantly caching,

To change the collisions you just nee to save the handle return by the scene collision, and you can add and remove handle at will.
I thing it will represent you voxel world exactly.

try that first see how it goes. The we can think of different representation

[Layla]

No octrees, just a flat array of block types, zero for air. All blocks are uniform size. I've thought about just creating many boxes but I felt like it would be just as bad as a triangle mesh because of how how many blocks are needed. A typical level can easily have upto a million blocks. I can try it but I don't think it will be ideal.

Native support that relied just on an array of blocks would be amazing, not just for my game, I've seen many games like this that just throw a triangle mesh at the physics engine when there's really no need to.

I'm new to Newton so I only just found out what a scene collision is. I assumed you meant a rigid body for every block. I'll try and get a scene collision up and running then we can go from there

[Layla]

Just got a scene collision setup. Speed doesn't seem to be an issue at all. I can setup many boxes and FPS is fine, it just uses up a crazy amount of memory. Still, I'm impressed with the results.

This is my quick code to test the scene collision, I hope I'm using it correctly.

Code: Select all

   m_physicsWorldNewton = new PhysicsWorldNewton();
   m_physicsWorldNewton->SetAccuracy(PHYSICS_ACCURACY_MEDIUM);
   m_physicsWorldNewton->SetGravity(Vector3f(0.0f, -20.0f, 0.0f));

   NewtonCollision* sceneCollision = NewtonCreateSceneCollision(m_physicsWorldNewton->GetNewtonWorld(), 0);
   NewtonSceneCollisionBeginAddRemove(sceneCollision);

   NewtonCollision* boxCollision = NewtonCreateBox(m_physicsWorldNewton->GetNewtonWorld(), 1.0f, 1.0f, 1.0f, 0, NULL);

   for (int x = -512; x < 512; ++x)
   {
      for (int z = -512; z < 512; ++z)
      {
         Vector3i blockPosition(x, 0, z);

         void* collisionNode = NewtonSceneCollisionAddSubCollision(sceneCollision, boxCollision);
         NewtonSceneCollisionSetSubCollisionMatrix(sceneCollision, collisionNode, Matrix4x4::Translation(Vector3f(blockPosition)).Base());
      }
   }

   NewtonSceneCollisionEndAddRemove(sceneCollision);

   NewtonDestroyCollision(boxCollision); // is this needed anymore?

   PhysicsBodyNewton* physicsBodyBlocks = new PhysicsBodyNewton(*m_physicsWorldNewton, sceneCollision);
   physicsBodyBlocks->SetMass(0.0f);

[Julio Jerez]

does is use too much memory?
The shape reused be reused, since they are all boxed and many will be of equal size.
This is unless w\you are making the boxes global space

The rest is that each node will have the overhead of a collision instance, plus the node inrmation, since are collision instance

Code: Select all

class dgCollisionInstance
{
   dgMatrix m_globalMatrix;
   dgMatrix m_localMatrix;
   dgMatrix m_aligmentMatrix;
   dgVector m_scale;
   dgVector m_invScale;
   dgVector m_maxScale;
   dgUnsigned32 m_userDataID;
   dgInt32 m_refCount;
   
   void* m_userData;
   const dgWorld* m_world;
   const dgCollision* m_childShape;
   dgInt32 m_collisionMode;
   dgScaleType m_scaleType;

   static dgVector m_padding;
};

an specialized voxel collision tree will not need the overhead of the collision instance per node, because they do no scale and do not rotate or move, with is about 300 bytes.
however it Is my experience that when I do these specialization, few month after that some user come back asking for a generalization of the same thing.
Performance wise should be faster that a collision tree.

scne collsion can also be use for any king of work mad of convex spaces like quake maps.

[Julio Jerez]

Code: Select all

 for (int x = -512; x < 512; ++x)
   {
      for (int z = -512; z < 512; ++z)
      {
         Vector3i blockPosition(x, 0, z);

         void* collisionNode = NewtonSceneCollisionAddSubCollision(sceneCollision, boxCollision);
         NewtonSceneCollisionSetSubCollisionMatrix(sceneCollision, collisionNode, Matrix4x4::Translation(Vector3f(blockPosition)).Base());
      }
   }

this subject that you made a world of one million cells. is that correct?
But that will be one solid world, hopefully a real world will have lot of hollow space so the memory will not be as much as that test.

for example on a voxel representation the code above will convert all those boxes to a singe large box, or am I getting this wrong?

[Layla]

With the code i posted, creating 128 ^ 3 sub shapes uses over 2gigs of memory. Yeah you're right, a real level probably wouldn't need that many blocks, maybe I can just add blocks that are exposed but I still really think working directly off the block array would be worth while.

[Julio Jerez]

yes, by what I am saying is that, you are passing single cells, but my understanding of a voxel algorithm is that solid area are decomposed spatially,
so clusters of voxes that are together and represented by one single large voxel. Only detail surfaces is represented in detail

yes the data can be compressed and synthesized from the box array, how do you represent detail from the box array?
don't you need an octree representation for that?

in an octree representation a box of 128 x 128 x 128 will be represented by a single node, if it was centered, 8 at most.

[Layla]

I guess it depends on the game. In my game I can afford to just have a byte per cell and create 2 triangles for every cell face that is exposed.

I guess I could work out the volumes and add big box shapes when needed but it isn't that easy and would slow down the editing I think.

[Julio Jerez]

you sure has to have some spatial representation, because otherwise, building the mesh by visiting every single cell to see if is fill or empty will bring your engine down to a crawl, even if it is just a point
I mean an array of (128 x 128 x 128) of Booleans is actually very small but that's over 2 million points, that's too many to traverse each frame

[Layla]

There's no octrees or any spatial structure for the level. The mesh is built and rendered, I'm not building the mesh every frame.

I could use octrees to place the minimal amount of sub shapes to the scene collision but I will try and push for another way because I think it will slow down the editing of a level. I can place huge volumes and arrangements of blocks really fast, messing with octrees and the scene collision will slow that down. If the collision is worked out by just the array of block values then nothing needs to be edited and no additional memory is needed (apart from what newton needs to solve the collision)

[Julio Jerez]

when you edit the mesh, don't you have to regenerate the mesh?

The second question is, if you have a triangular mesh, why don you just use a collision tree, I wan under the impression that you where changing the world dynamically.

[Layla]

I do but I don't need to rebuild the whole thing. I can insert triangles in places in the buffer that are removed and other tricks to speed that up.

Even if editing a triangle collision mesh was very fast, i still think it's unnecessary to have a whole collision mesh for a level that you know the exact shape of from just an array of bytes. Maybe I'm expecting something that can't be done but either way a scene collision I think will do the job if used right, giving the physics engine the array of bytes would just be 100 times easier, if it's even possible.

[Julio Jerez]

I could use octrees to place the minimal amount of sub shapes to the scene collision but I will try and push for another way because I think it will slow down the editing of a level. I can place huge volumes and arrangements of blocks really fast, messing with octrees and the scene collision will slow that down. If the collision is worked out by just the array of block values then nothing needs to be edited and no additional memory is needed (apart from what newton needs to solve the collision)

hwoo can you deal with a world of 4000 x 4000 x 4000, which for today's games is actual quiet small and yet that more memory that any desktop PC can has

[Layla]

If I was doing a world that large I certainly wouldn't be doing it the way I'm doing, I'd stream in the geometry in chunks and merge all adjacent faces. My game has a fixed map limit so I can get away with just a flat array.