Collision Detection

[davestevens]

i've implemented a simple collision detection (commit d618c37) collision-detection-test/3d there is an object moving 1.0 (voxels are currently 1.0_1.0_1.0) per update and checking for collisions in all three planes.

a bound box is calculated for each object in the createDude function, this simply finds the max/min pairs in each plane, this is then used for checking object collisions, obviously the granularity of this is rather coarse grained, but should be less computationally expensive than checking each voxel every update.

once a collision at bounding box level is detected we can check at voxel level or even at a smaller object level.

this leads to a thought about animations and the current object (dude_t) implementation. for animations, for example legs walking, we aren't going to want to have to create a dude_t for each possible movement, so i think that a objects should also be able to contain objects, similarly to a model_t. this then would also affect collision detection as bounding boxes would alter depending on certain animations.

this is just me writing down what i was thinking while playing with the collision detection, whether or not we even do it this way i'm not sure.

[iamscottmoyers]

Yeah objects within objects sounds good.

I'm just about to stop playing around with a scenegraph for the night. In the scenegraph we could have an object with some child objects, these child objects could either be more voxel objects or represent rotations / translations. Any transformation nodes will then have more child objects that have those transformations applied to them.

An animation sequence would probably just modify the rotation and translation nodes. If there is a small number of voxels that we're transforming it may be that we just want to modify the child voxel objects directly.

[davestevens]

i was just playing with it more and it doesn't really work correctly, so i need to look into that. i think we should sort this object within object idea out sooner rather than later because it will have an impact of design.

[davestevens]

From playing with collision detection yesterday I came up with a few different approaches for calculating collisions at the voxel level.

1. Full The easiest to implement (which is the one currently implemented); Check every single voxel in a with every single voxel in b.
2. Faces Calculate the outside faces of a and b and perform a check each outside voxel of a with each outside voxel of b.
3. Direction Using direction calculate which voxels can be seen is you were looking at the dude at it was moving towards you. Each voxel seen in a would need to be checked with every voxel in b.
4. Direction and Faces Using the Direction method but only check against the outside voxels of b.
   • 2 and 3 will only be valid if we move 1.0 unit at the time.

Example:

a and b = 4 * 4 * 4 cube

1. Each dude has 64 voxels. Worst case: 64*64 = 4096 checks

2. Each dude has 56 voxels on the outside. Worst case: 56*56 = 3136 checks

3. If dude a is moving towards dude b in the z axis: dude a has 16 voxels facing dude b, dude b has 64 voxels. Worst case: 16*64 = 1024 checks

4. Case 3 but only checking outside of dude b, 16 and 56 voxels, respectively. Worst case: 16*56 = 896 checks

These are just methods I've been thinking in terms of collisions, let me know if you can see any massive failings. I'm going to attempt to implement them in the collision detection test code and see what they're like. I will also create some bigger example dudes.

[iamscottmoyers]

Your Full example can be done faster than 64*64 checks, more like 64+64 = 128.

Create a 3D array (could be a bitset if you want to be fancy) big enough to hold one of the characters (the smallest if you want to reduce memory). Draw one of the characters into the array, 1 for a voxel, 0 for empty space. Then draw the second one into the array, if you attempt to set a location that is already set to 1 you have a collision.

If characters are both of size 'n' and 'm' then your algorithms are O(n*m). But this way is O(n+m) which means it's scalable to bigger characters, but who knows if it's actually faster for small ones.

We'll also have the problem that we will have 'x' characters on the screen and we need to check collisions between them all. That problem is always worst case O(x^2) but we can do a lot to ensure that most of the time we're not worst case. Like splitting the scene in half and any characters that are in separate halves of the screen don't have to be checked against each other because they can't possibly collide.

We could have a 3 layer thing (octree binning, bounding box, voxel)...although we're probably over optimising at this point. Bounding box, then a voxel one is good.

On 17 Jul 2012, at 16:32, petercrumb wrote:

From playing with collision detection yesterday I came up with a few different approaches for calculating collisions at the voxel level.

1. Full The easiest to implement (which is the one currently implemented); Check every single voxel in a with every single voxel in b.
2. Faces Calculate the outside faces of a and b and perform a check each outside voxel of a with each outside voxel of b.
3. Direction Using direction calculate which voxels can be seen is you were looking at the dude at it was moving towards you. Each voxel seen in a would need to be checked with every voxel in b.
4. Direction and Faces Using the Direction method but only check against the outside voxels of b.
   • 2 and 3 will only be valid if we move 1.0 unit at the time.

Example:

a and b = 4 * 4 * 4 cube

1. Each dude has 64 voxels. Worst case: 64*64 = 4096 checks

2. Each dude has 56 voxels on the outside. Worst case: 56*56 = 3136 checks

3. If dude a is moving towards dude b in the z axis: dude a has 16 voxels facing dude b, dude b has 64 voxels. Worst case: 16*64 = 1024 checks

4. Case 3 but only checking outside of dude b, 16 and 56 voxels, respectively. Worst case: 16*56 = 896 checks

These are just methods I've been thinking in terms of collisions, let me know if you can see any massive failings. I'm going to attempt to implement them in the collision detection test code and see what they're like. I will also create some bigger example dudes.

---

Reply to this email directly or view it on GitHub: https://github.com/iamscottmoyers/cambhaxx-gles/issues/12#issuecomment-7038873

[davestevens]

Ah ok, i will alter the full example to do it the way you suggested. So you think just optimise it if it needs optimising.

[iamscottmoyers]

If you want to write a clever multiple layer collision detection algorithm I won't try and stop you :).

If the bounding box + full check works for the number of objects we want then we don't have to do something about it. All the binning stuff will probably take longer for small numbers of objects anyway so it might not even be an optimisation. We'll have to see how many objects we have...which is why I thought it'd be over optimising at the moment.