i have created a 3d terrain mesh and render it using OpenGL, im trying to write a routine that will give the height of any coordinate on my mesh, so if the mesh is 1.0f spaced and i want the height of the terrain at X: 10.6f and Z: 6.3f how do i acomplish this? i have been trying various method using 2d trigonometry but i am unable to make this work in 3d. Obviosuly the data we have at our disposal is the heights of all 4 neighbouring absoule points in the case of this example 10,6 11,6 11,6 and 11,7 Can anyone offer help? a simple method? im sure many are intrested in this Thanks

hehe that makes no sense to me (nothing new there), i actualy do not know the Y value of the object (the player) over the terrain, im after using the x,z coordinates to find the y height of the terrain at the x,z postion.

This is tricky indeed. Your biggest problem is that you have a square grid of points, where each square of points defines the corners of a square. Now I''m sure you''ve already forseen this, but you realize that the four points will not always form a flat polygon. The only way to guarantee a flat polygon is to be limited to three points, thus forming a triangle. A little bit of preprocessing on the terrain could break each "square" up into two triangles, cut across one of the diagonals. There are only three possible cases. Either the square is flat (and doesn''t really need to be cut in the first place), the square needs to be cut upper-left to lower-right, or the square needs to be cut upper-right to lower-left. Clearly, once you have a set of triangles instead of a set of woggly squares, you can use trig to find the altitude at any x/z position on a given triangle. Which way do you cut? This is an ambiguous question which you must answer for yourself. For example, assuming two high points diagonally across from each other and two low points on the remaining two corners. You can form two flat triangles by cutting diagonally in either direction. One way produces a ridge, the other way produces a valley. Every square can be cut arbitrarily, so you will have to decide how you want to do this. The easiest (if not necessarily smoothest and prettiest) way is to just cut all squares the same way, say upper-left to lower right.

There is a completely different alternative you can consider. If you do not like the inherant ambguity of the above solution, You can "morph" your square grid into a triangular grid by putting a new point at the center of every square. The height of this point would be the average of the four corner heights. Now every square is cut into four triangles, not two, but there is no ambiguity, since you already have the three points of each triangle concretely nailed down.

The third alternative is to encode your mesh as a series of triangles instead of squares in the first place. Do this by offsetting every other row of terrain heights by half the point-spacing, so:

* * * *
* * * *
* * * *
* * * *

becomes:

* * * *
* * * *
* * * *
* * * *

Clearly, once you have your terrain broken down into triangles, you can find the terrain height of any x/z coord in a particular triangle with a little simple trig.

Well, the stupid text formatting ruined my pictures at the bottom, and this buggy message system won''t let me edit my original message. The second picture should have the second and fourth rows of asterisks offset by half the horizontal asterisk spacing. Oh well.

Try linear interpolation. Mesh vertices v1...v4 have coordinates (x1,y1,z1)...(x4,y4,z4) and lay on retangular grid. Player has coordinates (xp,zp).
Choose two vertices who have same x - coordinate. (e.g. v1 and v2) Find equation of line coming through points (z1,y1) and (z2,y2) (Since x1=x2 this is 2D problem).
Next insert into this equation zp. You will get y value - yp1.
Do same thing for other two vertices (v3 and v4), find line equation for points (z3,y3), (z4,y4), insert zp and you have yp2.
Then find equation of line coming through points (x1,yp1) and (x3,yp2).
Finally insert into this equation xp and you will get yp, i.e. interpolated mesh
height at (xp,zp).

line equation for two points looks like that:
y-y1 = ( (y2-y1) / (x2 - x1) )*(x-x1) where (x1,y1), (x2, y2) - points line
is coming through.

Of course you can start with points with same z - coordinate. Method is the same.
Just change x to z and z to x. And it should give same result
(I hope :D).
Hope it helps you.

K.

That''s interesting. I wonder what kind of a curvilinear surface that would define. I might code that up just to see what it looks like.

oki ive found a fairly simple way to work out the height on any given point within a triangle, basicaly split in into another triangle thru the point you need to know the height of, as finding the height at the edge of a triangle is easy.

ONE problem tho

How can i easily find out x,y of where two lines intersect? the only informastion availible in the start and end of one of the lines, and the start of the second line and a point somewhere along the line. hope this makes sense..

/me tries ascii art

........./
......../
C ----X---------- D
....../
.....B
..../
.../
..A

bad art i know as this sily bbs ignores whitespace or somin :/

need to find x,y of the intersection at X, but we only know the x,y of points A,B,C,D :o)

help!


Edited by - Marvin on September 23, 2001 2:12:32 PM

Edited by - Marvin on September 23, 2001 2:14:20 PM

If I understand correctly, you have two lines, each defined by two points. To find their intersection, find their equations. For this use the formula: line coming through two points (x1,y1) and (x2,y2) has exuation
y-y1 = ( (y2-y1)/(x2-x1) )*(x-x1). Transform it to form y= a*x+b (a=(y2-y1)/(x2-x1), b=y1-a*x1).
So, you have two exuations (for two lines):
y=a*x+b
y=c*x+d
After solving them you have x=(b-d)/(c-a) and y=a*((b-d)/(c-a))+b (or y=c*((b-d)/(c-a))+d it gives same result)
Then, point (x,y) is intersection point you are looking for.

K.

quote:Original post by Grudzio

y-y1 = ( (y2-y1)/(x2-x1) )*(x-x1). Transform it to form y= a*x+b (a=(y2-y1)/(x2-x1), b=y1-a*x1).
So, you have two exuations (for two lines):
y=a*x+b
y=c*x+d
After solving them you have x=(b-d)/(c-a) and y=a*((b-d)/(c-a))+b (or y=c*((b-d)/(c-a))+d it gives same result)
Then, point (x,y) is intersection point you are looking for.

ok sounds like what i need but you completely lost me at thr forumla bit :/ can you break it down anymore or explain more?What do you mean by transform it? im scared

hehe or should i just slap that as it is into my code and hope for the best?

Thanks