Subscribe to The Gamer's Algorithms to Goove By        RSS Feed
-----

Terrain Collision

Icon Leave Comment
Well, I had not really intended to make this blog about generating terrains, although so far that's exactly what its become. But since I'm on a roll, I might as well go all the way with it.

Probably the primary thing we are missing at this point is collision detection with the terrain. I've seen a whole lot of terrain tutorials on the Internet that never go that extra step to make the terrain "solid". The terrain ends up being just a visual thing that you cannot interact with. You pass through it like an ethereal ghost and that's not of much use. Instead, you need to be able to detect "collision" with the terrain in order to mathematically make it "solid".

There are many different ways that you can do collision detection with a terrain. You could simply have the camera always placed at a specific height above the terrain. Or you could allow the camera to move anywhere and basically fly anywhere except disallowing it to move to a position below the terrain. Regardless, all of these options work off one key fact, and that fact is the height of the terrain at the given point, which is usually the camera position.

This algorithm takes advantage of the way that we've set things up so far with our terrain. It is highly dependent on the fact that our terrain is formed out of grid squares (square quads). And those quads must be arranged so that the two triangles that form the quad have their hypotenuse edges running from x=0,z=1 to x=1,z=0 rather than from x=0,z=0 to x=1,z=1.

There is a more simple algorithm that is still dependent on the quads being square, but not dependent on which direction the center line runs. Briefly, the idea there is to interpolate between the two height values on one side of the grid square based off of percentage distance between the two in the x dimension, then interpolate between the two heights on the other side of the quad, and then finally interpolate between those two results based on the percentage between the two side in the y dimension. I've used this method and it actually works quite well.

However, it's not "perfectly" accurate. Because you are treating the quad as a square, rather than two triangles, the terrain shape formed by the two triangles may not match the shape of the quad treated as a planer quadralateral in 3 dimensions. Or in plain english, there can be a crease that forms a hill or valley along the hypotenuse lines between the two triangles of the quad and treating it as one quad, rather than two triangles will ignore that hill or valley and result in a terrain height that does not follow the exact contours of the triangles in the grid mesh. So - for the greatest accuracy, we need to calculate the terrain height within the given triangle, within the given grid square, at the given position.

So for either method, you need to start by stripping down the grid coordinates to being between 0,0 and 1,1. So, say we want the height above position x=-12.6 and z=+4.59. Notice that I left out y. Y is what we are trying to find; y represents altitude. All of the positions of the grid must correspond to the height map array which can never have negative positions in the array. The heights stored in the array can be negative, but the elements, or positions, in the array cannot be numbered negatively. So, there's obviously a conversion to switch back and forth between the two coordinate systems. It's usually 0.5 * grid width subtracted from x and z to convert to actual positions and added to convert back to array positions. This centers the grid at x=0, z=0 and still allows the array elements to be numbered all positive.

Let's say that our grid is 100 units wide in both the x and z directions. So, half of that would be 50. So, we need to add 50 to both values and that would give us a position of x=37.4 and z=54.59 on a centered grid.

Next, the array elements are numbered as integers and so you have to convert the real number positions to integers to use them. In our example with x=-12.6 and z=+4.59, we can round the values we just converted down to get x=37 and z=54. At this point, we have the array element number that contains the height value for one corner of the quad for this terrain position.

Now, you can use this height for your terrain collision. I have and it works, albeit not that well. For example, you could just set the camera's y position to be the height of that corner of the grid square the camera is in plus about 1.67 (the average height of a man's eyes in meters). And if you do the camera will "walk" across the terrain as you move. The problem is that the results will be extremely jerky. The whole terrain is like stair steps with steep fall offs between every grid square at even a relatively shallow slope. The height values are not smoothly interpolated between grid squares and so the camera will jump all over the place between radical height differences.

You could use the method already mentions and treat the grid square as a square. Then you use the corner height we've alread determined along with the three other corner heights of the quad to interpolate as described earlier. The other corner positions can be determined by adding one (unless the grid squares are not 1 by 1 and then you have to take the square size into account). So, if one corner was x=37,z=54, then the other corners are 37,55 and 38,54 and 38,55. For the interpolation, you can use the remainder that we cut off assuming you saved the remainder. So originally 37,55 was -12.6,+4.59 and the remainders were 0.6 and 0.59. You can use those remainders as percentage values in the interpolation mentioned earlier. The given position would be 60% between the top and bottom edges of the square and 59% between the two side edges of the grid square. So you can weight your height averages with those percentages.

The more accurate method is to go a step further and determine which of the two triangles within the grid quad the position is in and interpolate between those three height values instead of the 4 height values of the overall square.

After dividing the original position by the size of a quad, adding half the grid width, and rounding down to the nearest integer, you have x and z coordinates that map to the heightmap array. From there you can add 1 to x and y values to get the array positions of the other three corner positions of the quad. At that point you have the heights of the for corners of the quad.

If you subtract the integer position of the corner from the real number position being tested, you will get the remaineder of both the x and z values. This gives a position within this grid square.

Now, if you set your grid up correctly, the hypotenuses of the two grid square triangles run from 1,0 to 0,1 and this is where this becomes important. If the position being tested (within this grid square) sum up to exactly 1 the position is on the hypotenuse line between the two triangles. If the x and y value add up to less than 1, the point is within the lower triangle. If their sum is greater than 1, then the position is in the upper triangle. (Notice that upper and lower here are somewhat dependent on what direction you look at them from and thus can get easily confused.) But this would not work if the center line running through the grid square were to go from the 0,0 position to the 1,1 position and so it's imperative that your grid is setup that way.

In fact, let's flip the grid around so that the upper and lower triangle switch position. This is highly dependent on whether you are in a left handed coordinate system or a right handed system and even then what direction you look at it from. But if you get it worked out in one, it should make sense how to flip in into the other. So, if we look at this as a horizontal grid where x grows positive to the right and z grows positive coming towards us and out of the computer monitor, then the "upper" triangle is the one furthest away and with the lowest values. The "lower" triangle is the one closest to us and has (rather unintuitavily) the higher values.

If the current position is in the upper triangle here (sum of the remainders is less than 1), the terrain height within that triangle can be determined by adding the height of the upper left corner (0,0) to the weighted average of the upper right and upper left corners. You do this by subtracting the upper left height from the upper right height and multiplying the result times the percentage across the quad in the x direction (the x value remainder is this percentage). Then you add the weighted average of the lower left and upper left corner heights. Again, this is determined by subtracting the upper left corner height from the lower left corner height and multiplying that result times the percentage across the quad in the z direction. This gives you the exact height of the triangle at that position.

HeightOfTerrain = QuadUpperLeft + (XinQuad * (QuadUpperRight - QuadUpperLeft)) + (ZinQuad * (QuadLowerLeft - QuadUpperLeft));



Where QuadUpperLeft, QuadUpperRight, and QuadUpperLeft are the height values at these corners. XinQuad and ZinQuad are the remainder value of the x and z position which is the same thing as the percentage across the quad in the x and z directions.

Now if it is the lower triangle (determined because the sum of the x and z remainders - position within the quad - add up to 1 or more [technically 1 is on the line but you need to push it to one side or the other]), then the calculation changes. Mostly, it just changes because you need a percentage across the triangle rather than position across the quad. So, you take the inverse percentage; previously the percentage was the position FROM 0,0, but for this it is percentage TO 1,1. So, you subtract both the x and z remainders from 1 to get the inverse percentage.

The inverse percentage, of course, is the opposite part of a percentage. So if the percentage is 0.73, then the inverse of that is 0.27, or 27%.

And to get the height within the lower triangle you take the height of the lower right corner and add it to the result of the inverse percentage across the quad in the x direction times the result of the lower right corner's height subtracted from the lower left corner's height. All that is added to the lower right corner's height subtracted from the upper right corner's height result multiplied times the inverse z percentage across the quad.

HeightOfTerrain = QuadLowerRight + ((1-XinQuad) * (QuadLowerLeft - QuadLowerRight)) + ((1-ZinQuad) * (QuadUpperRight - QuadLowerRight));



Once you have the height of the terrain, you can use it for more than just collision. You'll also need it when placing static objects like trees or grass.

So now you can calculate the exact height of the terrain at any point on the terrain. You can set the camera height to always be 1.67 (the height of an average man's eyes) above this height at all times and the camera will "walk" over the terrain. Or, you could reset the altitude of the camera to this height every time the camera tries to move to a position below this height and allow the camera to otherwise fly over the terrain. Knowing the altitude of the terrain at any given point between the grid square corners is the key no matter how you choose to actually do the terrain collision.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

November 2014

S M T W T F S
      1
2345678
9101112131415
16171819202122
23 242526272829
30      

Tags

    Recent Entries

    Search My Blog

    1 user(s) viewing

    1 Guests
    0 member(s)
    0 anonymous member(s)