How to get the height at a position in a triangle

Question

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!

Answer 1

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 ?

Answer 2

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.