# Board index » delphi » Heightfield interpolation

## Heightfield interpolation

2004-07-12 08:56:24 AM
delphi163
Hey all,
I'm writing a little 3D game. The main display is a terrain made up of a
huge array of height values. The terrain renderer I am using imposes a
restriction of at least 8*8 points per "Tile". The problem is, I only want
the height of a tile to be stored as a single byte. So I devised a little
system whereby the heights of 4 surrounding "tiles" and the height of the
current tile are used in a weighted average to calculate each of the 8*8
points that make up the tile. But I have only got this to working when it
interpolates in one direction only... ie. smooth terrain from left to right
or top to bottom, but not both, and I have no idea how to get the tiles to
flow diagonally as well. Can someone help me out? How can I interpolate
values in a heightfield?
Cheers,
Nicholas Sherlock

## Re:Heightfield interpolation

Nicholas Sherlock writes:
##### Quote
I'm writing a little 3D game. The main display is a terrain made up of a
huge array of height values. The terrain renderer I am using imposes a
restriction of at least 8*8 points per "Tile". The problem is, I only want
the height of a tile to be stored as a single byte. So I devised a little
system whereby the heights of 4 surrounding "tiles" and the height of the
current tile are used in a weighted average to calculate each of the 8*8
points that make up the tile. But I have only got this to working when it
interpolates in one direction only... ie. smooth terrain from left to right
or top to bottom, but not both, and I have no idea how to get the tiles to
flow diagonally as well. Can someone help me out? How can I interpolate
values in a heightfield?
First you need to consider how much continuity you really want.
You are not really confined to nearest neighbours only if you choose.
You can choose a function with a number of parameters, and then fit it
to the number of points equal to (or greater than, if you do a best fit)
the number or parameters.
For instance, if you take a kwadratic interpolation, you have 7
parameters (a..g):
z = a.x^2 + b.y^2 + c.z^2 + d.yz + e.xz + f.xy + g
That doesn't fit nicely with either 5 points (without diagonals) or 9
points (with diagonals), although you could do a least square fit with
the 9 points.
A natural would seem to be a fourier expansion:
z = a + b.sin(x) + c.sin(y) + d.cos(x) + e.cos(y) + f.sin(x + y) +
g.cos(x + y) + h.sin(x - y) + i.cos(x - y)
(well, scale x and y such that a tile has a side of pi)
Now you can calculate matrices such that you can relate the [a..i] to
the values at the 9 (x,y) values of your 9 points.
And you can calculate the coefficients for your 8 by 8 points in your tile.
(This requires some calculations, but nothing rocketscience).
--
Erik Springelkamp
springelkamp.nl/

## Re:Heightfield interpolation

Erik Springelkamp writes:
##### Quote
A natural would seem to be a fourier expansion:

z = a + b.sin(x) + c.sin(y) + d.cos(x) + e.cos(y) + f.sin(x + y) +
g.cos(x + y) + h.sin(x - y) + i.cos(x - y)
Matrices? Coefficients? Sorry, I am lost :). Does anyone have a link to a
website that deals with this kind of thing? I couldn't find anything with a
quick google, but I don't know what to look for.
Cheers,
Nicholas Shrelock

## Re:Heightfield interpolation

Nicholas Sherlock writes:
##### Quote
Erik Springelkamp writes:
>A natural would seem to be a fourier expansion:
>
>z = a + b.sin(x) + c.sin(y) + d.cos(x) + e.cos(y) + f.sin(x + y) +
>g.cos(x + y) + h.sin(x - y) + i.cos(x - y)

Matrices? Coefficients? Sorry, I am lost :). Does anyone have a link
to a website that deals with this kind of thing? I couldn't find
anything with a quick google, but I don't know what to look for.
When doing 3D you rather get the math required quick.
There are books such as "me, analysis and linear algebra"
At university, they are 2 years at 4 hours per week each.
To start with, I would recommend not to use mean values, but
spend the couple megabytes required for the terrain.
BTW, better than fourier transform are wavelets,
as fourier transform is bounded to an area, wheras wavelets
are localized.
Rene
--
Ing.Buro R.Tschaggelar www.ibrtses.com

## Re:Heightfield interpolation

Rene Tschaggelar writes:
##### Quote
BTW, better than fourier transform are wavelets,
as fourier transform is bounded to an area, wheras wavelets
are localized.
You are right.
The formula I gave will give you an interpolation that fits the given
neighbouring points, but wouldn't garantee continuity across the tile
boundaries unless you would do one integrated interpolation of the whole
map area. But then the number of coefficients would become unpractically
large.
--
Erik Springelkamp
springelkamp.nl/

## Re:Heightfield interpolation

Erik Springelkamp writes:
##### Quote
Rene Tschaggelar writes:

>BTW, better than fourier transform are wavelets,
>as fourier transform is bounded to an area, wheras wavelets
>are localized.

You are right.

The formula I gave will give you an interpolation that fits the given
neighbouring points, but wouldn't garantee continuity across the tile
boundaries unless you would do one integrated interpolation of the
whole map area. But then the number of coefficients would become
unpractically large.
One could also think of 3D splines or nurbs.
One major difficulty is that terrain tends to change the
derivative and the density of derivative sign changes.
It is questionable whether a terrain shall be stored as
multiple series with whatever almost global parameters or
whether is shall be stored as multitude of local bounded
shapes. Real terrain tends to have a fractal nature,
even when the lower scale is truncated at fistsize structures.
A mixture of global and local description might be optimal.
Rene
--
Ing.Buro R.Tschaggelar www.ibrtses.com