Archived

This topic is now archived and is closed to further replies.

DC_Tsunami

linear interpolation with weighted average

Recommended Posts

DC_Tsunami    122
I''m trying out 2D Perlin noise to generate a heightfield, and part of the algorithm requires me to use bilinear interpolation to get the value of a point in between four other points. I''ve thought about this for a while, and I can''t come up with anything. I could only find one thread in the search, and the algorithms either didn''t make sense or were seriously flawed. I figure I have to do some sort of weighted average based on the y-values of the four corners and the distances to each point. How can I use the distances as a weight? I am using a function in the form: float BilinearInterpolate( float topleft, float topright, float bottomleft, float bottomright, float x, float y ); where the first four arguments are the y-values of the corners, and the last two are distances to the top left corner clamped between 0 and 1. If anyone has a working function that does this, please share it with me and explain how it works. Thanks in advance.

Share this post


Link to post
Share on other sites
LilBudyWizer    491
You can''t really do a bilinear interpolation between four values. It is v1+(v2-v1)*s+(v3-v1)*t. When s and t are both one you get v2+(v3-v1) which may or may not be your fourth value. With terrain if the four corners all lie in the same plane then you can use the same bilinear interpolation across the entire quad. If not then you have to split the quad into two triangles. You then use the three corners for the triangle the point is on.

Share this post


Link to post
Share on other sites
DC_Tsunami    122
Thanks for the reply Zipster. That works quite well. I guess I forgot that you don''t actually divide by anything in a weighted average (I should just slap myself right now =] ), and I never thought of just multiplying the fractional values like that.

LilBudyWizer, you''re right, it does not create co-planar points, but I don''t actually want co-planar points. A curvy surface is perfectly acceptable. I''ll definitely use your method though when I have to move a vehicle or something across the terrain and it has to be coplanar with each triangle.

One question though: are v1, v2, and v3 arbitrary vertices of the triangle? I''m guessing not because of s and t. Which vertices are they?

Share this post


Link to post
Share on other sites
LilBudyWizer    491
They are not arbitrary, but they can pretty well be any of the vertices. A square can be split into two triangles two ways. You can then be on either one of those triangles. V1 is one of the two vertices not on the split. Which one depends on which triangle you are on. Just to make matters more confusing (s,t) is relative to that corner. Say you have the following:


    
+----+
|\ * |
| \ |
| \ |
| \|
+----+


The '*' is the point you want the height for. So V1 is the upper right corner, V2 is the upper left, V3 is the lower right and (s,t)=(.4,.2).

I took the time to look at the article Zipster posted. I suppose that is the correct usage of the term bilinear interpolation. I've seen and used it before, but I never really examined it. It does make an interesting surface. Each trace is a straight line from one edge to the other though the surface isn't a plane.

[edited by - LilBudyWizer on March 17, 2003 2:03:44 AM]

[edited by - LilBudyWizer on March 17, 2003 3:05:19 AM]

Share this post


Link to post
Share on other sites