Simple Heightmap Physics Simplification

Here's one way, although I don't know how efficient it is...It's a matter of computing the distance of the line to the center of each square. If the distance is small enough, then the line is in the square.

(xc,yc) = center of grid square

y = mx + b is the equation of the line


then

distance from line to square center is

d(x) = sqrt( (xc-x)^2 + (yc - (mx + b))^2 )

The square of the distance is quadratic in x, so it has a minimum, which is what you want, and we can find it with a little bit of work. we get

d(minimum) = sqrt( (b + m xc - yc)^2 / (1 + m^2) )


Then if d < half the length of the diagonal of a grid square, then the line runs through that square. You would have to do this calculation on the rectangular subregion of which the two endpoints form opposite corners.

c

You could use Bresenham's algorithm, but modify it to be 2 blocks wide at every point, instead of just 1. that will be slightly wasteful, especially in the case of a perfectly vertical or horizontal line (2x the blocks needed). However if speed of determining the blocks is more important than the number of blocks tested, this should work out fine.

a tighter approach is to use raycasting, just like in the old Wolfenstein. you move along the ray, stopping each time you hit the boundary between blocks. flag the new block, update your initial starting point and repeat till you reach your target block. I like this one, but the logic is tougher. I think there is an article about this here on GameDev.

[edit]
like the 1st half of this article
[/edit]

hmm... besenham is usually done with integer maths. I dunnno how it would work with FP maths.

I've upgraded an old rasteriser engine of mine, that I used precisely to cast rays on heightmaps. This one is working in 3D as well (doing voxels basically).

you can get it here.

I think that demo is two demos in one. the voxel trace is demo #2 (press '2'). 'r' to reset and start a new example.

it's quite complete. It first does a clipping, to make sure the ray stays in the voxel grid, then it converts the ray into the voxel grid space (where each voxel is sized to (1, 1, 1)), then does the walking along the voxel map.

It uses a callback function called everytime a voxel is reached.

the logic is very simple, with little branching, which is good. [grin]

Thanks for the sugestions guys, i thought of besenham's algerithm earlyer today, as well as the checking the distance from the center of the square, to the vector. the problem with checking the distance to the center is i wopuld have to check every square for every object i need to hit test and even with a grid of only 128x128 thats 18384 checks and everyone includes a squareroot or 2, also if the line was vertical i would get still get 2x as many results as i need, so i guess that one is out. Besenhams algerithm might just work, since i would just use array indices (integers) to work it out and i can deal with the posable worst case of 2x the checks since a square will probably be a few meters in size and delta Time (hopefully) will be very small (<1/30sec) so to get more than one square the object would have to traveling at 300+ m/s. i think i may just have found my solution.
Thanks guys, i wasnt expecting such a quick responce.