Collision detection in a voxel world?

Question

I have been working on a voxel game for a little while now, It's using a algorithm that I wrote. However, I am still stuck with collision detection; because I don't really know where to get started. The voxel engine isn't really to complicated.

I only really need to calculate the height of a heightmap.

Take this face for example: (please excuse my terrible image)

Let's say my position relative to the polygon is 0.5,0.5 (center). How would I compute the y position at this point?

Answer 1

Thanks to Ped7g, we finally arrived at the actual problem being a height map.

First I want to note that this is completely unrelated to Voxels. Your engine happens to use Voxels, but your problem is unrelated. Same goes for collision detection. While it is relevant for what you want to use something, you essentially omitted the actual problem.

Second, a triangulation like Ped7g proposed works but I see a disadvantage, it will essentially produce a surface that is composed of triangles. For your example and the triangulation

 ___        
|\  |    
| \ |    
|__\|

the lower left triangle would lie flat on the ground and only the upper right would have a slope. More sophisticated triangulations would look better but would still consist of triangular surfaces and also require you to work with several sets of barycentric coordinates.

The common way to interpolate within a square is Bilinear Interpolation, which has every corner influencing every point, with an easy formula.

Given λx and λz in 0..1 that represent your relative position in the unit square (over x and z) and heights y00, y01, y10 and y11 on the corners, the height is simply

y = (1-λx)(1-λz)y00 + (1-λx)(λz)y01 + (λx)(1-λz)y10 + (λx)(λz)y11

Note that this will create lines on the edges. The advantage of bilinear interpolation is speed. A disadvantage is that on the edges, the height will not behave smoothly, that is would not be differentiable. If you want that, you need more sophisticated methods that factor in neighbouring squares. Ped7g mentioned B-Splines, B-Splines surfaces could be used but take a while to implement and are anything but fast, wouldn't recommend those to a beginner (but if you are interested, click on this link. Chapter 8 contains what you need, but you better read the other chapters before that). A good middle ground would be Bicubic Interpolation. The link contains a visual comparison of bicubic and bilinear interpolation.

Assuming that you are a beginner, I'd recommend bilinear, though.

Answer 2

Looks to me more like "height map" from that picture, not voxel. If that's true and only one corner is "1", then you have to define how you will model the middle part.

With sharp edge triangulation you can end with two variants:

 ___        ___
|\  |      |  /|
| \ |      | / |
|__\|  vs  |/__|

In the first case the whole middle edge is Y=0, so your point at [0.5, 0.5] is at Y=0 too, in the second case the middle edge goes linearly from 0 to 1, and at [0.5, 0.5] the Y=0.5.

Or you can use even some more complex ways to define particular [x,y] height inside, like some B-spline, weighted average, etc.

But if your map has fine enough resolution, I would split it the other way, that edges between voxels are at +-0.5, +-0.5, and pick height of the "voxel" which is under ([0.5, 0.5] is on cross of 4 voxels, so hard to say which would be picked, but Y=0 or 1).

If you need more resolution than 0/1, you can calculate middle point Y as average of the four, and then each edge with middle point forms a triangle, where you can calculate [x,y] Y without ambiguity (in your case [0.5, 0.5] is right on the middle point, so Y=0.25 ((0+0+0+1)/4)). Like this:

 ___
|\ /|
| X |
|/_\|