# Thread: Interpolation algorithm

1. ## Interpolation algorithm

I'm trying to create an accurate height map from existing z values I already have. From what I have read when generating a terrain model its is easier to use values in a grid format.

Is there a way/algorithm to take my existing zvalues and interpolate them to a grid in order to generate my height map?

Any help would be greatly appreciated.

Cheers

Shaun

2. ## Re: Interpolation algorithm

Wild guess, not sure exactly how suitable, try bicubic interpolation :-)

3. ## Re: Interpolation algorithm

I couldn't seem to find much on it. And what I did read didn't seem to be that helpful.

Any other suggestions from anyone?

4. ## Re: Interpolation algorithm

Originally posted by eskimo:
...Is there a way/algorithm to take my existing zvalues and interpolate them to a grid in order to generate my height map?...
I am not really aware of what you mean here. You got the values, why do you need to interpolate?
If you really want to interpolate between the height values for some reason, there are different kinds of interpolation.

Linear interpolation is the fastest but produces ugly results.

A pretty nice interpolation used by most Perlin Noise implementation is t * t * t * (t * (t * 6 - 15) + 10). This produces an S-shaped curve. Just linearly interpolate using this weight and you're done. Very cool.
There's also cosine interpolation (don't remember it right now), cubic interpolation and "old-noise" interpolation as I call it.
I'll try to post something more on this but I don't know how much I will take (probably someone other will already answer you).

5. ## Re: Interpolation algorithm

Let's say you have three points with z values
P1 = (x1, y1, z1)
P2 = (x2, y2, z2)
P3 = (x3, y3, z3)
So, you have 3D points.

You want to interpolate the values of z in a grid, so you will have (x.y) position and you need to find the z.

Let's say your grid is made of 9 points with coordinates

G1 = (0,0)
G2 = (.5,0)
G3 = (1,0)
G4 = (0,.5)
G5 = (.5,.5)
G6 = (1,.5)
G7 = (0,1)
G8 = (.5,1)
G9 = (1,1)

If you want to find the z value in G5 (for example) you need to select a K number of points you find closer (for x and y distance) to your G5 and interpolate the z values weighting the distance.

Is this your problem?
I'm not sure to understan it, but do your 3D points have some kind of structure? I mean, they are a mesh or what?

If you have a triangular mesh of 3D points, your problem is easyer, because you can find the triangle that contain the grid point and interpolate the z values of its vertexes.

If you have only the z values, without a defined structure, I think your bigger problem is to find a certain numer of closer points to your "grid position".

6. ## Re: Interpolation algorithm

Yes- What I have is collection of random (x,y,z) values and I want to create a height map. I'm very new to Open GL - and from what I've been reading the simplest way to create the height map in from a grid with specific Z-values. That is where my interpolation problem comes into effect.

Unless there is an easier way to create my height map that I'm unaware of.

7. ## Re: Interpolation algorithm

Just wild guessing, but if you have the mesh, why would you want to make a height-map out of it? There surely is an octree or whatever partitioning approach for normal meshes...
If you try to display a free mesh through a height-map you will almost surely loose precision and add senseless geometry detail. Heightmaps are so cool, because you can easily use algorithms to fill them or manually edit them to get a terrain or whatever. And i think the easy stripping of heightmap-based terrain is useless because of the faces added.

8. ## Re: Interpolation algorithm

I'm making the height map - because I've been asked to create a 3d model of an area. Interpolation is required because the data I've been given has been pretty thin.

9. ## Re: Interpolation algorithm

I still don't get it.
If you have your xyz vals, can't you just use them as a mesh?
For me an height map is an array of single-component values. It looks silly to do mesh->heightmap->mesh.
Where interpolation comes in play?

If the problem is that your xyz points are taken at random positions then I can see the light but this is going to be somewhat more complicated than expected.
What I fear is that if that's the case, than and arbitrary grid point p[x,y] can have up to n-1 neightbours (n = number of points) in a worse case condition (interpolating correctly all those values could get tricky - provided you choose them correctly).

Is that the point?

10. ## Re: Interpolation algorithm

Hello,

For refining a mesh structure (or in particular a regulary sampled height values), you can use an interpolation subdivision scheme, such as the Butterfly subdivion scheme.
http://portal.acm.org/citation.cfm?i...CM&coll=portal

Code implementing this scheme probably can be found by Google.

Regards
Martin

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•