Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.\


share|improve this question
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 ?

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.