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/