interpolating a point on a heightmap

[JernejL]

I'd like to add some structures and random trees to my heightmap terrain, but i've got a problem, i know all 4 points of heightmap quads, but how do i interpolate a point on the quad, such as the structure edges needed - see image:



[size=9px]EDIT by Moderator: Image too big so copied over to Image Hosting and replaced with Link & Thumbnail. (I'd have resized it and added a link to that, but new version of phpBB doesn't let me:?)[/size]

[Nitrogen]

To find one of the points of the red rectangle in your drawing I would do this:

[pascal]
TargetPoint: vector; // This is the point we are looking for, we know the x and y values, but need the height.
GridSize: single; // This is the width of one of the terrain grid cells
XFrac, YFrac: single // How far into this grid cell does the target point extend.
TempH1, TempH2: single; //Temporary Height values

SX,SY,BX,BY: integer;// These are the 4 closest terrain grid point indexes
// to your target point. the small X and Y and the big X and Y..
//
// So if your terrain is a simple grid, with each grid point represented as y,x:
// 0,0 0,1 0,2 0,3 0,4 0,5
// 1,0 1,1 1,2 1,3 1,4 1,5
// 2,0 2,1 2,2 2,3 * 2,4 2,5
// 3,0 3,1 3,2 3,3 3,4 3,5
// 4,0 4,1 4,2 4,3 4,4 4,5
// 5,0 5,1 5,2 5,3 5,4 5,5

// and the target point is marked with the '*', then sx = 3, sy = 1, bx = 4, by = 2

// So first we find sx and sy:

Sx := TargetPoint.x div GridSize;
Sy := TargetPoint.y div GridSize;

//Bx and BY are simple to find:
Bx := Sx + 1;
By := Sy + 1;

//Then we already know the x, y position of the target point RIGHT?
//So now we need Xfrac and YFrac:

XFrac := (TargetPoint.x - Sx*GridSize)/GridSize;
YFrac := (TargetPoint.y - Sy*GridSize)/GridSize;

//That gives us an indication of where the Target point is inside the grid cell, as a percentage between 0.0 and 1.0 in the x and y directions.

//Here is where the actual calculation occurs:

//First we find the heights along the two borders of the gridcell:
TempH1 := Heightmap[Sx,Sy]*XFrac + Heightmap[Bx,Sy]*(1-XFrac);
TempH2 := Heightmap[Sx,By]*XFrac + Heightmap[Bx,By]*(1-XFrac);

//Then the final calculation:
TargetPoint.z := TempH1*YFrac + TempH2*(1-YFrac);

[/pascal]
And that should give you the height of a point at Targetpoint.x,y.

To try and explain here is a bad ASCII art drawing:

[sx,sy] --------TempH1------- [bx, sy]
  |                |            |
  |                             |
  |                |            |
  |                             |
  |                |            |
  |            TargetPoint      |
  |                             |
  |                |            |
  |                             |
  |                |            |
[sx,by] ---------TempH2-------- [bx,by]
  <<<<XFrac>>>>

[JernejL]

I'll see what i can do with this, thanks for the help!

[Huehnerschaender]

Keyword is "bilinear interpolation".

Greetings,
Dirk

[JernejL]

Eh? what for? linear is fine for this.

[tux]

Eh? what for? linear is fine for this.

http://en.wikipedia.org/wiki/Bilinear_interpolation

[JernejL]

I need a big viking axe, to hit my head with it for my stupidity.

thanks for the link tux

[Huehnerschaender]

// receives the terrain height(y) at point x,z
function TTerrain.GetHeight(x,z:single) : single;
var
  rx, rz : integer;
  fx, fz,
  A, B, C, D : single;

begin
   if &#40;x <0> &#40;TerrainMaxX-1&#41;&#41; or &#40;z <0> &#40;TerrainMaxZ-1&#41;&#41; then
   begin
     result &#58;= 0.0;
     exit;
   end;
   rx &#58;= trunc&#40;x&#41;;
   rz &#58;= trunc&#40;z&#41;;
   fx &#58;= x - rx;
   fz &#58;= z - rz;

   A &#58;= HeightMap&#91;rx   ,rz&#93;;
   B &#58;= HeightMap&#91;rx+1 ,rz&#93;;
   C &#58;= HeightMap&#91;rx   ,rz+1&#93;;
   D &#58;= HeightMap&#91;rx+1 ,rz+1&#93;;

   result &#58;= &#40;A + &#40;B -A&#41; * fx&#41; + &#40;&#40;C + &#40;D - C&#41; * fx&#41; - &#40;A + &#40;B - A&#41; * fx&#41;&#41; * fz;
end;

Heightmap is a 2dimensional array containing the heights at your "vertices". calling this function gives the height at any point within the terraindimensions.

Greetings,
Dirk

[JernejL]

Thank you very much, now i can add random trees