PDA

View Full Version : Getting Height Between Two Points



Swiftless
10-07-2005, 09:36 PM
Hi,
In my application I have a heightfield. This is read in from a RAW file as a series of points that are then displayed. I am setting the height of my viewpoint according to its height from the RAW file. But the problem then is that it does not calculate the height I am at between a set of points. I can get the current position on a 2D plane with the old y=mx+c. But have no idea how I would go about this on a 3D plane.

(Should this be in Maths?)

john
10-08-2005, 03:03 AM
Hello,

your post seems a little confusing since I'd argue you're out by one-dimenion in your descrption: y=mx+c is a line and hence you're tyring to find a 1D solution (ie. y), not a 2D solution.

From my undestanding of your problem, you're trying to find a suitable height given a 2D position along a height-field, and that you're unsure what to do when you're between point samples, right?

What you need is some kind of interpolation to 'tween' a synthetic (or interpolated) point between known data. The type of solutions you're after are identical to image filtering: it's just you're interpolating a scalar representing a height rather than a three-vector representing colour.

Check out http://astronomy.swin.edu.au/~pbourke/colour/bicubic/

Yes, it's image scaling, but its the same idea since both aim to resample a point-sampled function.

cheers,
John

10-08-2005, 08:50 PM
Hi !

Not sure if this is what you want, but....

To get 'intermediate' points between a pair of points, you can try this :
-------------------------------
struct XYZ
{
GLfloat x;
GLfloat y;
GLfloat z;
};
-------------------------------
XYZ LinearInterpolate(XYZ pt_01, XYZ pt_02, double mu); // syntax

// PS : mu goes from 0.0 to 1.0;
// if mu = 0.0, you have 'intermediate' point
// completely at pt_01,
// if mu = 1.0, you have 'intermedaite' completely
// at pt_02.
-------------------------------
So, the function

XYZ LinearInterpolate(XYZ pt_01, XYZ pt_02, double mu)
{
XYZ new_pt;

new_pt.x = (float)((pt_01.x * (1-mu)) + (pt_02.x * (mu)));
new_pt.y = (float)((pt_01.y * (1-mu)) + (pt_02.y * (mu)));
new_pt.z = (float)((pt_01.z * (1-mu)) + (pt_02.z * (mu)));

return new_pt;
}

----------------------------------------

If you want it to be more smooth, please try with "Cubic Spline".

Hope that helps.... ?

Swiftless
10-09-2005, 06:39 AM
Thanks for the replies.

You are both on the right track but I must not have explained it correctly.

I can set my position on the X and Z axis fine, but the problem is with the Y axis.
If I am on point [X][Z] then I get Y.
Same goes for [X+1][Z+1] then I get a new value for Y.

But I want to get a height between [X+1] and [Z+1] no matter what X and Z are.

That is why I was looking for something along the lines of Y=MX+C. Because it works with the basic X and Y. And of course the slope. But I don't know any formulas like this for 3D that also find the slope according to the Z axis.

I need the slope between my previous [X][Z] position and my next [X][Z] position.

Another thing that I got stuck on was, what if I am facing the opposite direction? I would need a different way to find the slope so I can work out my position on the Y axis.

If you don't understand fully, I will come up with a diagram, but I will try your suggestions tomorrow when I get some time.

john
10-09-2005, 04:45 PM
Hello,



But I want to get a height between [X+1] and [Z+1] no matter what X and Z are.
that's exactly what I thought you were talking about. What you want to do is interpolate data: that is, generate new data based on your observations, and that link to Paul Bourke's site is EXACTLY what you want. His description, though, is in the context of generating new intensities, but it's the same idea: you just need to apply it to generating heights rather than a three vector for RGB.

The second post also generates new data based on given observations, but it doesn't explain how the bias is computed. His approach is linear interpolation---which is good, but not as good as the bicubic interpolation described in that link.

The idea behind linear interpolation (its easier to explain;-) is that you have four known points surrounding the point you really want to sample:


[3] [2]

[p]

[0] [1] here, [0]..[3] are the known points (they have fixed height) and [p] is the point inbetween your knwon points. If you ignore one dimension for now and just consider the following case


[0] [p] [1] then you can solve the height for [p] based on your linear interpolation of y=mx+c since the line equation (ie. unknowns m and c) can be readily solved from the two known points.

That's all well and good. But what happens when you want to linearly interpolate in TWO dimensions? Well, all you need to do is come up with "new" [0] and [1] and interpolate from there. The two cases, then, is to find (m,c) for the line defined by pts [0] and [3], and find a new set of (m,c) for the line defined by [2], [1]. From these two lines you can find the two heights [a] and [B] by using the y-coordinate (in this example) of [p], like so:


[3] [2]

[a] [p] [B]


[0] [1] ie. [a] is the linear interpolated point from (m,c) generated by [3] and [0], where the line parameter is p.y, and similarly point [B] for (m,c) generated from [2], [1]. Now you have a new linear problem to solve, this time solving y=mx+c from the line formed by [a] and [B]. this time, your line parameter is p.x and the solution is your linearly interpolated height at [p]!

does this make sense?

cheers,
John

Swiftless
10-09-2005, 11:29 PM
That makes perfect sense. Thanks a bunch.

Now I just gotta put it into my app. I'll do a test app to see if I can get it working and if I have any problems I will come back. But it doesn't seem difficult now that I know what I have to do.

Thanks again. :) :D

john
10-10-2005, 02:31 AM
Hello,

no worries. I'm glad I could help out. Actually, I was so keen, I worked out the analytical solution. Here, [a]..[d] are your known heights and yuo want to compute h, the height at point [x,y] where x,y in the range [0, 1]. Provided my maths is right, the solution is:


[d] [c]

[u][x,y] [v] < [3]

[a] [B]

^ ^
[1] [2]

we seek h=f(x,y)

from [1],
u=m'y+c', where
a=m'.0+c' ie. c'=a
d=m'.1+c' ie. m'=d-a (since c'=a)

therefore,
u=(d-a)y+a

similarly, from [2]
since v=m''y+c'', then
c''=b, and
m''=c-b

therefore,
v=(c-b)y+b

therefore, [3] becomes

h=mx+c, where
u=m.0+c, ie. c=u
v=m.1+c, ie. m=v-u (since c=u)

therefore,
h=(v-u)x+u
=vx-(x-1)u

ie. h=x((c-b)y+b)-(x-1)((d-a)y+a)good luck!

cheers
John

Swiftless
10-10-2005, 04:38 AM
Sorry John, I couldn't get it working. It is getting alot of weird results.

From what I could gather from your last post. I came up with this for [a]..[d]:


int ha = HeightMap[posX][posZ];
int hb = HeightMap[posX + 1][posZ];
int hc = HeightMap[posX + 1][posZ + 1];
int hd = HeightMap[posX][posZ + 1];
Then you came up with your final equation for h and I substituted my numbers into it and it came out like:


h = xpos * ((hc-hb) * zpos+hb) - ((xpos-1) * ((hd-ha) * zpos+ha));
Where xpos is your x and zpos is your y. I then set the Y of my 'camera' to the result of h.

But I am not sure whether you are using [a]..[d] as the height data themselves, or as just the points, eg: [a]=(x,y).

I'll take a closer look (currently school holidays and haven't done much maths recently). Hopefully I will get it. But I believe I get what you are on about.

*Just tried it the long way and am getting the exact same results. I must be doing something wrong in the [a]..[d] section. Really not sure at this stage...

**Just tested it in 2D, I have narrowed the problem down to how it is displaying the height. When it does a downward slope (m is a -ive value), the point where the camera is going to be is inverted. So instead of a positive number, it becomes a negative, like a reflection. Also, when I have a slope of 1, everything works fine going up hill, but when it gets higher, the point moves too hight above the needed point. Here is the code I am using for this:


float h1;
float h2;
int posX = xpos;
float m;
float c;
h1 = Map[posX];
h2 = Map[posX+1];
m = (h2-h1);
c = h1;
newypos = (m * xpos) + c;
Where the Map positions are randomly generated on startup, xpos starts at 0 and is increased at 0.1 intervals.

Then to display it I am using:


camera();

enable();

glColor3f(0,1,0);
HeightMap();

glPushMatrix();
glPointSize(3);
glColor3f(1,0,0);
glBegin(GL_POINTS);
glVertex3f(xpos,newypos,0);
glEnd();
glPopMatrix();
Where 'camera' sets up the newypos.

I am thinking maybe I need a variable that ranges between maybe 0 and 1, that resets everytime I hit a new 'key height' to count how far along the selected slope I am.

Swiftless
10-10-2005, 07:45 AM
I did what I said above and added a controller that varies between 0 and 1 to determine where I am along the current slope and it is almost perfect on a 2D perspective. But Every now and the the point I have going over the other points, jumps up, then back down. I have a feeling it is reaching it's highest value of 1 before getting to the end of the current line. How would I go about fixing this. I have tried getting the Length of the current line but after I have that I am not sure what to do with my counter.

Should I set it's new maximum to the current length of the line? I have tried it and it just seems to cause more problems.

The equation I am using for this is:
lLength = sqrt(1 + (h2-h1)^2);
(right angled triangle)
Where h2 is my next height and h1 is my current height (or previous, depends on position). And 1 is the length between the current point and the next along the x axis.

In theory it sounds to me like it should work. But it won't for some reason.

I am so close :(

john
10-10-2005, 03:30 PM
I am thinking maybe I need a variable that ranges between maybe 0 and 1, that resets everytime I hit a new 'key height' to count how far along the selected slope I am.Hi,

ok, I think I know what the problem is. The point [p] (which you denote {xpos,ypos}) is _always_ in the range [0,1] because it represents the ratio of the point _between_ 'key' points. In this case, for example


5 4 3
.

0 1 2then you'd use a=[1], b=[2], c=[3], d=[4] for the above equations, but xpos might be 0.25 since the point '.' is 25% across from the line '4::1' and the line '3::2'.

So, check to make sure your xpos and ypos is in the range [0,1], and make sure you're using floating point numbers where appropriate. (I see that you're using ints for the height, which is fine, but make sure you DON'T cast your xpos and ypos to an int:-)

good work on trying out your code in 2D to inspect what's going on. That is an excellent debugging strategy.

good luck

cheers,
John

Swiftless
10-10-2005, 09:10 PM
I am using floats for the final results. And am seeing no problem with them.

Althought my ypos and xpos are not stuck between 0 and 1.

My ypos is any height along the selected line, and xpos is a number that I can either increase or decrease in intervals of 0.1 to whatever number I want. But to work out my final ypos, I am taking a counter called cxpos and wacking that into my y=mx+c equation as the x.

And cxpos is the number that ranges between 0 and 1. So it is taking my current point and my next point. Getting the slope. Timesing the slope with cxpos and adding the height I previously had.

The only problem is that when cxpos gets above 1 and jumps back to 0 (i then am left with y=m*0+c), it still keeps the previous height as c, so it jumps back up to the previous height.

I have tried setting it so that when cxpos = 0, it used height2 (h2) as c. But then I get 1 error when cxpos first = 0, but from then on it works fine until I start going in reverse, then I get the same errors I got at the start.

The code to get the height, is now:


int h1;
int h2;

int posX = xpos;
float m;
float c;
h1 = Map[posX];
h2 = Map[posX+1];
m = (h2-h1);
if (cxpos == 0) {
c = h2;
}
if (cxpos != 0)
{
c = h1;
}
ypos = (m * cxpos) + c;
The code to display it is:


glTranslatef(-4,0,-10);
camera();

glColor3f(0,1,0);
HeightMap();

glPushMatrix();
glPointSize(4);
glColor3f(1,0,0);
glBegin(GL_POINTS);
glVertex3f(xpos,ypos,0);
glEnd();
glPopMatrix();
And finally, the code to set cxpos and xpos is:


if (key=='d')
{
xpos += 0.1;
cxpos += 0.1;
if (cxpos > 1) {
cxpos = 0;
}
}

if (key=='a')
{
xpos -= 0.1;
cxpos -= 0.1;
if (cxpos < 0) {
cxpos = 1;
}
}
I have a feeling, I am also going to have to set a variable to determine which direction I am headed. Eg: forwards, backwards
and in the 3d field:
forwards, backwards, left, right
Would there be an easier way?

john
10-10-2005, 10:03 PM
Hi,

I wrote a programme to test it out:


{
const unsigned int res=5; /* resolution of the height field */
const unsigned int ssres=512; /* sampling frequency (for rendering) */
float hf[res][res]; /* the heightfield itself */

/* generate the random height field */
for(unsigned int t=0; t<5; t++)
for(unsigned int j=0; j<5; j++)
hf[j][t]=(float)rand()/(float)RAND_MAX;

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, res-1, 0, res-1, -1, 1);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glClear(GL_COLOR_BUFFER_BIT);

/* supersample the heightfield and render it */
glBegin(GL_POINTS);
for(unsigned int t=0; t<ssres; t++) {
for(unsigned int j=0; j<ssres; j++) {
float p[2]={ /* both dimensions of p are in the range [0,res-1) */
(res-1)*(float)j/(float)ssres,
(res-1)*(float)t/(float)ssres
};

/* compute the height at p */
float h;
{
int cell[2]={ /* the 'cell' that contains p */
(int)p[0], (int)p[1]
};

float offset[2]={ /* compute the offset within the cell (in [0,1]) */
p[0]-cell[0], p[1]-cell[1]
};

/* height mnemonics */
float a=hf[cell[0]][cell[1]];
float b=hf[cell[0]+1][cell[1]];
float c=hf[cell[0]+1][cell[1]+1];
float d=hf[cell[0]][cell[1]+1];

/* linearly interpolate the height */
h=offset[0]*((c-b)*offset[1]+b)-(offset[0]-1)*((d-a)*offset[1]+a);

glColor3f(h, h, h);
glVertex2f(p[0], p[1]);
}
}
}
glEnd();
}that fragment is self-contained so you'll be able to see what's going on. It works, too, insofar as it's a straightforward linear interpolation with random heights...

check it out and see how it works...?

cheers
John

Swiftless
10-11-2005, 03:37 AM
Ok, I placed that into an app and have it up and running. I see what it is doing, but am still having trouble implementing the same thing into what I want.

I am understanding it more as I go at least...
I will probably go and have a little scribble on some paper to get it mastered before I try again.

I will have a closer look at it later, my brain is currently hurting :(

Thanks, you have been a huge help.

Oh, and if I may ask, how did you come up with:
h=x((c-b)y+b)-(x-1)((d-a)y+a)
In the one equation?
I see how you got:
(d-a)y+a
and
(c-b)y+b
But can't see how you wacked the two different equations into one. (something else I might have to have a scribble with)

john
10-11-2005, 02:28 PM
Hi,

the equations for u and v were subsituted into the equation for h. If you look up in the work-through, u and v were defined as

u=(d-a)y+a .. [1]
v=(c-b)y+b .. [2]

which are based entirely on known values. The equation for h in terms of u, v and x is

h=(v-u)x+u .. [3]

so so substiting [1] for u and [2] for v into [3] gives

h=((c-b)y+b-(d-a)y+a)x+(d-a)y+a

which, again, is all based on known values and not 'intermediate' processing. A simple rearrangment to factor out (d-a)y+a (which is u) gives the equation I gave you.

I'm glad this is helping out

cheers,
John

john
10-11-2005, 03:54 PM
Hi,

another thing: I'm not convinced by this code


if (key=='d')
{
xpos += 0.1;
cxpos += 0.1;
if (cxpos > 1) {
cxpos = 0;
}
}

if (key=='a')
{
xpos -= 0.1;
cxpos -= 0.1;
if (cxpos < 0) {
cxpos = 1;
}
}Your 'cxpos' looks like your index INTO the cell, but the problem is that it's going to get confused when you wrap around. For example, if cxpos=xpos=1.0, then when you next increase x, you'll start with cxpos=xpos=1.1, but then you'll set cxpos to 0.0 (since it's greater than 1), but it should REALLY be 0.1 because you're 10% into the next cell.

Your two options are;

1. change the cxpos=0.0 to cxpos-=1.0, or
2. compute cxpos from xpos when you need it, rather than tracking two different but _dependent_ counters.

I vote for method [2]: that's how I did it in the source I posted earlier where it computes offset[] from the given position. (That way you only need to track ONE point, the p[] in my example, and everything else falls out nicely.)

cheers,
John