# 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

Wild guess, not sure exactly how suitable, try bicubic interpolation

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?

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

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.

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.

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”.

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.

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.

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.

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?

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?id=78958&dl=ACM&coll=portal

Code implementing this scheme probably can be found by Google.

Regards
Martin

Now I am confused. Here’s a breakdown of what I’m trying to do - bear in mind that I’m pretty new to OpenGL so this is a bit of a minefield for me.

I have a collection of points that have been extracted from Ordinance survey data and are stored in a text file, like so:

“xvalue”,“yvalue”,"zvalue
,336415.50,390170.75,60.78
,336210.30,390373.05,53.03
,336280.20,390472.90,58.20
,336567.80,390080.15,63.34
,336873.75,390013.15,58.08
,336935.65,390170.10,56.96
,336637.85,390280.40,64.78
,336506.40,390372.90,66.85
,336572.75,390371.15,67.79
,336539.45,390455.00,68.73
,336638.20,390467.00,66.57
,336200.95,390873.85,61.60
,336384.50,390728.20,66.32
,336129.55,390805.10,59.06
,336658.25,390595.90,66.34
,336948.10,390527.00,61.30
,336741.30,390655.25,64.47

etc

Anyway from thes points I wish to generate a height map of the area. Thats all I want to do. The reason I had asked about interpolation is because I had read that a simple way of generate a height map was to use a grid and simply read in z values, but that could be wrong, like I said I’m new to this. I’m not entirely sure what you meen about mesh either. Sorry - my apologies if I’m stating the obvious. Hope this helps you to see what I’m tryin to do.

Shaun

Just to loosely define some terms, in the context that they’re generally used in:

A height map is a regular (usually square, could also be triangular, hexagonal, radial) arrangement of height values.

A mesh is a continuous surface made of linked points, generally in some kind of regular arrangment.

If the x and y values are regularly spaced, and in a regular formation, like a square grid, or a equilaterally triangular grid, then you already have a heightmap, more or less.

In that case, you just need to sort you data into the appropropriate order by x and y value, and then use it to render some kind of regular mesh.

From a quick visual inspection of your sample data, it doesn’t seem to be regularly spaced (assuming, of course, that you didn’t just make it up as an example), which means that you don’t have a grid, and that making a heightmap is a non-trivial problem - you’d need to make some kind of vector based contour map first, and then perhaps render that to a heightmap - try voronoi diagrams on that count.

I believe most people did not understood that Eskimo wants to use a cloud of xyz points as a surface, so there is no connectivity information in the original data.
As it was said previously, a height field is not appropriate in this case.
The only (!) problem is to determine connectivity between the vertices. I have already faced the same problem with terrains, but I solved it by creating all the triangles by hand, carefully creating the edges where needed.

Some Voronoi based algorithm may give good results too.
Or something like creating edges between the 2 nearest vertices (and no edge crossing an existing edge in xy space) until each vertex has at least 3 adjacent edges and all the polygons formed are triangles ? (untested)

Thats exactly it. I essentially need to create the mesh from my random collection of points.

Any Ideas on how to do it?

cheers

Here’s my canned response to terrain related questions: Check out vterrain .

I think what you’re looking for here is generating a TIN (triangulated irregular network) from a set of possibly random points. The best kind of TIN to work with is a delaunay TIN usually, as it forms the best triangulation for any given set of points (laymans term).

To convert a TIN to a heightmap, it would simply be calculating the height above terrain for every point in your heightmap.

Here are a few starter links, but this is a widely studied computational geometry algorithm so google will be your best friend.

http://cs.smith.edu/~orourke/ (great book, has source for basic algorithm)

In my opinion, the best way to approach this problem is to project the 3D points on a 2D plane perpendicular to the height-axes. Then use this collection of 2D points as input to an algorithm called ‘Delauney Triangulation’. This algorithm automatically creates ‘optimal’ edges between the collection of 2D points. Finally just use the same edges for the corresponding 3D points.

C++ code for Delauney triangulation shouldn’t be to hard to find on the internet.