# Walking over a 3d mesh

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

Posted 20 September 2001 - 07:38 AM

###
#2
Members - Reputation: **1323**

Posted 20 September 2001 - 11:13 PM

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

Trent (ShiningKnight)

E-mail me

ShiningKnight Games

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

Posted 21 September 2001 - 11:16 AM

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

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

Posted 21 September 2001 - 12:14 PM

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

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

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

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