# Walking over a 3d mesh

Started by Marvin, Sep 20 2001 07:38 AM

14 replies to this topic

###
#1
Members - Reputation: **127**

Posted 20 September 2001 - 07:38 AM

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

###
#2
Moderators - Reputation: **1323**

Posted 20 September 2001 - 11:13 PM

I''m working on that right now actually. As far as I see it, you already know where the person is in location (the thing you want to test a collision with) with an (x, y, z) value, and you can use the x/y or x/z location to find the height of the spot they are currently at. Just my idea, I just woke up though, so this explanation may sound a bit funny.

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

Trent (ShiningKnight)

E-mail me

ShiningKnight Games

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

Trent (ShiningKnight)

E-mail me

ShiningKnight Games

###
#4
Anonymous Poster_Anonymous Poster_*
Guests - Reputation:

Posted 21 September 2001 - 11:16 AM

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.

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.

###
#5
Members - Reputation: **122**

Posted 21 September 2001 - 11:20 AM

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.

###
#6
Members - Reputation: **122**

Posted 21 September 2001 - 12:14 PM

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.

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.

###
#8
Members - Reputation: **127**

Posted 23 September 2001 - 07:05 AM

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

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

###
#9
Members - Reputation: **122**

Posted 23 September 2001 - 08:43 AM

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.

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.

###
#10
Members - Reputation: **127**

Posted 23 September 2001 - 09:23 AM

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

###
#11
Anonymous Poster_Anonymous Poster_*
Guests - Reputation:

Posted 23 September 2001 - 01:16 PM

Sorry for confusing you. I will try to explain it more. Here it goes. First. How to make line out of two points (x1,y1) and (x2,y2). The solution is this big awfull formula:

(y-y1) = ( (y2-y1)/(x2-x1) )*(x-x1)

Second, this y=a*x+b. I want to use a and b to have less typing.

(a and b are kind of temporary variables to store partial results). So I have to find out how a and b corresponds to x1,y1,x2,y2. This is what I meant by transforming equations.

I calculated that a = (y2-y1)/(x2-x1)

and b = y1 - (y2-y1)/(x2-x1)*x1

As a result we have an equation y=a*x+b which is easy to write (cause it is short ).

Now, do same trick with second line. If we have points (x3,y3) and (x4,y4) then equation is

(y-y3)= ( (y4-y3)/(x4-x3) )*(x-x3)

Then, change it to form y=c*x+d. It is the same as previous one so c = (y4-y3)/(x4-x3)

and d = y3 - (y4-y3)/(x4-x3)*x3

Now, to the intersection point. We have set of two equations

y=a*x+b

y=c*x+d

The point (x0,y0) which fullfils both these equation is intersetion point. In other words we are looking for such x) and y) that when you put x0 in first equation you will get y0 AND if you put same x0 to second equation you will get y0 again. Here are solutions for x0 and y0:

x0 = (b-d)/(c-a), y0 = c*( (b-d)/(c-a) ) + d

Procedure which finds intersection point has to do two steps.

First. Calculate a,b,c,d from x1,y1,.......,x4,y4

Second. Calculate x0,y0 from a,b,c,d

Well, I hope it clears things a bit (And I didnt bore you to death).

K.

(y-y1) = ( (y2-y1)/(x2-x1) )*(x-x1)

Second, this y=a*x+b. I want to use a and b to have less typing.

(a and b are kind of temporary variables to store partial results). So I have to find out how a and b corresponds to x1,y1,x2,y2. This is what I meant by transforming equations.

I calculated that a = (y2-y1)/(x2-x1)

and b = y1 - (y2-y1)/(x2-x1)*x1

As a result we have an equation y=a*x+b which is easy to write (cause it is short ).

Now, do same trick with second line. If we have points (x3,y3) and (x4,y4) then equation is

(y-y3)= ( (y4-y3)/(x4-x3) )*(x-x3)

Then, change it to form y=c*x+d. It is the same as previous one so c = (y4-y3)/(x4-x3)

and d = y3 - (y4-y3)/(x4-x3)*x3

Now, to the intersection point. We have set of two equations

y=a*x+b

y=c*x+d

The point (x0,y0) which fullfils both these equation is intersetion point. In other words we are looking for such x) and y) that when you put x0 in first equation you will get y0 AND if you put same x0 to second equation you will get y0 again. Here are solutions for x0 and y0:

x0 = (b-d)/(c-a), y0 = c*( (b-d)/(c-a) ) + d

Procedure which finds intersection point has to do two steps.

First. Calculate a,b,c,d from x1,y1,.......,x4,y4

Second. Calculate x0,y0 from a,b,c,d

Well, I hope it clears things a bit (And I didnt bore you to death).

K.