Getting AABB to Voxel Terrain collision working correctly

Game Mechanics
#1

So I’m implementing AABB collision detection into my voxel game (Think Minecraft, but with smaller voxels).

Right now, I check to see if the player is moving in a certain direction, and if it is, I check that face of the AABB for collisions against the voxel terrain (So if the player X velocity is > 0, I check the right side of the player’s AABB, which improves performance). I have a 3D array of bytes, which I can index at a 3D coordinate to see if that voxel is solid or not

If that face did collide, I slide the player along the colliding voxel. I obtain the normal for the colliding voxel face easily, its just the opposite of the normal of the player AABB face I was checking.

This works fine, except for 1 bug. Lets say the Front face of the player’s AABB was colliding with a wall of voxels. The corner of the front face and the left is naturally also colliding. However, that means when I check the left face for collisions, it will also check that corner, and think there is a collision on the left face! The same happens with the bottom face. Lets say I run up against a wall of voxels, and the front face of the player’s AABB is colliding, the seam where the front face meets the bottom face is colliding. Therefor, when I check the bottom face for collisions, it thinks the player is hitting the ground :-.

Here are some example images in case you need more clarification: https://www.dropbox.com/s/iq7fo1qipps6sss/Side.png?dl=0, https://www.dropbox.com/s/trbw17j9ucmov9e/Top%20Down.png?dl=0

I feel like the answer to this is probably pretty simple, and I’m just completely missing it, however I’ve been trying to work something out for days, and I just cant come up with anything.

Thanks a lot for your help. JGO is a wonderful community :wink:

#2

It seems like the difference between >= and >. If you’re using the greater/lesser or equals condition the equals may “overlap” into another side. If you could post some of your code that would help us look through and see what exactly is wrong.

#3

It may not be that simple. Although AABBs are pretty easy to work with, getting solid, robust behavior (sliding, no tunneling, etc.) can still be non-trivial.

Can you describe how your face-vs.-voxels test works? Is it continuous? Are you just testing the corners of the face?

I will say I think it’s possible you’re taking the wrong approach in testing individual faces of the box. AABB collision and response is more typically done using the separating axis test, which is quite simple and efficient in and of itself, and doesn’t deal with the box on a per-face basis. Aside from possible correctness issues, dealing with the faces individually probably isn’t necessary (or effective) as an optimization, because the full separating axis test will likely be just as efficient, if not more so.

Anyway, if you could describe in a little more detail how your AABB face test works, that would help provide some context.

#4

Sure. So first, I have a for-loop that iterates along the length of the player’s velocity vector by increments of 1 (How big a voxel is). Then, every loop I check all the points along the AABB faces to see if that point is solid or not.

This is probably a bad approach, but its the only way I could think of. Feel free to point me toward a better approach :wink:

#5

Yeah, testing the corners like that suffers from a variety of shortcomings. For example, imagine the player approaching a wall edge-on, where the wall is thinner than the player. In this scenario, the per-corner test might fail to detect any collision at all. (There are other problematic cases as well.)

Even with as simple an environment as a single axis-aligned box and a voxel grid, getting good behavior (sliding, no tunneling or other artifacts) can be tricky. One starting point would be the aforementioned separating axis test, along with the minimum translation vector for resolving collisions. An alternative (and perhaps better) formulation is to test a single moving point (the center of the box) against a representation of the environment where all surfaces are expanded by the box dimensions. (This is how a lot of games have done it in the past.)

And of course there’s always the option of using an existing physics engine (although you’d probably need to combine solid cells into larger objects to keep from overwhelming the physics system).

#6

I don’t just test the corners. I test the entire surface area of the AABB faces. Sorry if I didn’t make that clear.

I will definitely look into the the algorithms you mentioned. Could you elaborate on the approach you mentioned where you expand the terrain? Does the algorithm have a name?

Thanks.

#7

Oh, sorry about that. If you still want to try to get that working, maybe you could post some code as chrislo27 mentioned earlier. (My guess is that testing individual faces probably isn’t gaining you anything over a more typical SAT-based approach, but I could be wrong.)

[quote]Could you elaborate on the approach you mentioned where you expand the terrain? Does the algorithm have a name?
[/quote]
‘Expanded geometry’ and ‘plane shifting’ are terms that come to mind, but my attempt to search for these terms along with ‘collision detection’ seemed to return mostly academic papers that probably aren’t particularly relevant here.

The short version though is that you shrink the axis-aligned box to a point, and ‘push’ the faces of all obstacles outward to compensate. Then, you test the point against the expanded geometry. One thing worth considering is that if the extents of the axis-aligned box are integer multiples of the voxel size, then the expanded version of the environment can be represented using the voxel grid you already have. If that’s the case, I think the expanded geometry approach could actually be quite practical. (Otherwise though, it might be fairly involved to implement.)

#8

Great. I just have 2 more questions.

[quote]The short version though is that you shrink the axis-aligned box to a point, and ‘push’ the faces of all obstacles outward to compensate.
[/quote]
How would this work if my AABB was not the same size on all axises? For instance, the AABB is taller on the Y axis then the X. So if I shrink it on the X axis down to a width of 1, the AABB on the Y axis would be bigger.

[quote] One thing worth considering is that if the extents of the axis-aligned box are integer multiples of the voxel size, then the expanded version of the environment can be represented using the voxel grid you already have.
[/quote]
Right now my AABBs aren’t integer sizes, but I could make them be with slight cost to the accuracy of the AABB.

And my last question: It appears that SAT is used to test whether 2 objects are colliding. How would I use it to test against the entire voxel terrain? I’m sure there is probably a way.

Thanks for bearing with my probably noob questions ;D

#9

SAT is used for non-axis aligned shapes. If your game is completely aligned on the axis then there’s no point in using it.

#10

[quote]SAT is used for non-axis aligned shapes. If your game is completely aligned on the axis then there’s no point in using it.
[/quote]
OK. Thanks for the clarification. I think I have enough info to go on for now. I’ll give it a try :slight_smile:

#11

Not to be contrary, but that’s not true. The SAT is certainly applicable for axis-aligned shapes. (In fact, the standard AABB-vs.-AABB test that we’re all familiar with is a separating axis test.)

@The OP: In retrospect, it may not have been that helpful of me to mention these alternate approaches. I’m a little uncertain about your current method, but if it’s close to working, maybe with some tweaking it will give you the results you’re after.

#12

[quote]In retrospect, it may not have been that helpful of me to mention these alternate approaches. I’m a little uncertain about your current method, but if it’s close to working, maybe with some tweaking it will give you the results you’re after.
[/quote]
OK. I’ll mess around and see what I can get working with my current method and the ones you suggested. My only question how would I use a AABB to AABB algorithm (Such as SAT) With a whole voxel terrain?

#13

You’d check against individual obstacles (either individual solid cells, or maybe groups of cells that themselves form axis-aligned boxes), and resolve the intersections in turn. However, even this can be tricky where multiple obstacles are involved. (The expanded geometry approach would address this issue, more or less, assuming it worked as I think it would.)

#14

I felt kind of bad about suggesting the ‘expanded geometry’ technique without being able to offer anything in the way of example, so I put together a quick demonstration to show what I mean. You can find the code here. It’s a self-contained one-file program, so you should just be able to build and run if you want to check it out. Controls are arrows to move, return/enter to reset, and space bar to toggle debug graphics.

Screenshot:

And with debug graphics on, showing the expanded geometry:

This is 2D of course, but 3D would be exactly the same, just with another dimension.

Although I can’t guarantee correctness, it seems to work well. Note in particular that collisions with multiple solid cells at once are handled transparently and robustly. In any case, if I were doing something like this, this is the approach I’d probably take.

[Edit: Made a few cosmetic changes to the code.]

#15

[quote]You’d check against individual obstacles (either individual solid cells, or maybe groups of cells that themselves form axis-aligned boxes), and resolve the intersections in turn. However, even this can be tricky where multiple obstacles are involved. (The expanded geometry approach would address this issue, more or less, assuming it worked as I think it would.)
[/quote]
Great, thanks for the info.

[quote]I felt kind of bad about suggesting the ‘expanded geometry’ technique without being able to offer anything in the way of example, so I put together a quick demonstration to show what I mean.
[/quote]
Wow, thank you so much, this is excellent, much more help then I was expecting (But I’ll take it! ;)) I will defiantly use this technique in my game ;D