How to calculate the slope of a point on a terrain data (e.g. Digital Elevation Matrix)

Question

I want to implement a 3D car racing game and I need to approximate the magnitude and the direction of the slope of any arbitrary point on a terrain.

Terrain Data Format:
- heights[ ][ ]: 2D array of floats (representing heights in meters)
- unit: horizontal unit distance between (i, j) - (i, j+1) and between (i, j) - (i+1, j) in meters

Ex:

3|1311
2|2542 <-- 2D array of heights in meters
1|2231   (unit distance between two cell is, say, 1 meters)
0|1121   (so the highest point of the terrain (x = 1.5 meters, y = 2.5 meters)
  ----      is 5 meters high)
  0123

What is the value and direction of the slope at point, say, (x = 1.75 meters, y = 2.25 meters)?

What would your interpolation algorithm be?

Answer 1

You could of course linearly interpolate along both the x and y axis, ie first interpolate the y value for the x coordinates that are lower and higher than your actual x value two times - one time for the y coordinate lower than your actual y value and one time for the y value higher than your actual y value. This gives you two y values that you can linearly interpolate between to get the height.

In order to find the slope you need to find the normal at that point. To find the normal you could then do an interpolation in the same way. Given one of the patches (determined by four points A:(x1,y1), B:(x2, y1), C:(x2,y2) and D:(x1,y2), x1 < x2, y1 < y2 and each point also includes the height) you can say that the normal at one of the points, say A, is determined by the cross product of the vectors AB and AD. The normal at B is BC x BA in the same way.

Linearly interpolate the normal in the same way as for the height. I don't know in what format you want the slope, but if you want a vector pointing in the direction of the slope, that would then be calculated by S = N - Up, where Up is simply the up vector (in this example (0,0,1) since you are using Z as up.

Another approach would be to tesselate the squares into triangles, ABD and BCD for instance. The normal for the entire triangle would then be AB x AD and BC x BD respectively. In that case, take a look at http://www.cc.gatech.edu/classes/AY2007/cs3451_spring/lininter.pdf for instance on how to interpolate the height on the triangle. This approach gives you smooth triangles, but there is notable differences in the slope between adjacent triangles.