# How to get the height at a position in a triangle

I have a heightmap, and I store the heights in a giant array. However, when I move, it's quite choppy on the Y-axis, so I need a way to get the height at a certain point in a triangle.

I currently am picking a triangle based on the player's position, but I'm stuck on finding the intermediate height at the point. At the moment, I'm using similar triangles on each axis to calculate the height, but this method seems slow, and someone mentioned using a weighted average to find the height, which would probably be faster.

I know that DirectX has a "D3DXIntersectTri" function, but I couldn't find one in XNA.

Basically, I just want to know how the height is interpolated with a weighted average.\

Thanks!

• Have you looked for heightmap interpolation methods on Google? – sam hocevar Jan 18 '13 at 8:24

I believe you can use bilinear interpolation on the heightmap data. (I suppose, you have your heightmap as 2D raster of heights)

1. Get floating point position fX, fY in your height map. This is something like:

float fX, fY;
float fHeightMapWorldSizeX, fHeightMapWorldSizeY;
float fHeightMapWorldOffsetX, fHeightMapWorldOffsetY;
int   iDimHeightMapX, iDimHeightMapY;
float fPlayerX, fPlayerY;

fX = (fPlayerX + fHeightMapWorldOffsetX) / fHeightMapWorldSizeX * iDimHeightMapX;
fY = (fPlayerY + fHeightMapWorldOffsetY) / fHeightMapWorldSizeY * iDimHeightMapY;

2. Bilinear interpolation

float fTX, fTY;
float fSampleH1, fSampleH2, fSampleH3, fSampleH4;
int x,y;
float fFinalHeight;
x = floor(fX);
y = floor(fY);
fTX = fX - x;
fTY = fY - y;
fSampleH1 = arrHeightMap2D[x][y];
fSampleH2 = arrHeightMap2D[x+1][y];
fSampleH3 = arrHeightMap2D[x][y+1];
fSampleH4 = arrHeightMap2D[x+1][y+1];
fFinalHeight = (fSampleH1 * (1.0-fTX) + fSampleH2 * fTX)*(1.0-fTY) + (fSampleH3 * (1.0-fTX) + fSampleH4 * fTX)*(fTY);


Easy, isn't it ?

One approach is to use a generic ray-triangle intersection algorithm.

If you have a ray from [player.x,MAX_Y,player.z] straight down (direction [0,MAX_Y-MIN_Y,0]) and fire this at both triangles that form the grid-square, you'll find the y at the player's position.