interpolating a point on a heightmap [Archive]

JernejL

01-12-2006, 01:35 PM

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:

http://upload4.postimage.org/1802231/addingstructures.jpg (http://upload4.postimage.org/1802231/photo_hosting.html)

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:?)

Nitrogen

01-12-2006, 03:12 PM

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

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);

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

01-12-2006, 04:40 PM

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

Huehnerschaender

01-12-2006, 06:57 PM

Keyword is "bilinear interpolation".

Greetings,
Dirk

JernejL

01-12-2006, 07:22 PM

Eh? what for? linear is fine for this.

tux

01-12-2006, 07:48 PM

Eh? what for? linear is fine for this.

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

JernejL

01-12-2006, 11:11 PM

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

thanks for the link tux :)

Huehnerschaender

01-12-2006, 11:31 PM

// 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 (x <0> (TerrainMaxX-1)) or (z <0> (TerrainMaxZ-1)) then
begin
result := 0.0;
exit;
end;
rx := trunc(x);
rz := trunc(z);
fx := x - rx;
fz := z - rz;

A := HeightMap[rx ,rz];
B := HeightMap[rx+1 ,rz];
C := HeightMap[rx ,rz+1];
D := HeightMap[rx+1 ,rz+1];

result := (A + (B -A) * fx) + ((C + (D - C) * fx) - (A + (B - A) * fx)) * 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

02-12-2006, 08:07 AM

Thank you very much, now i can add random trees :D