• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

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

Marvin

Walking over a 3d mesh

14 posts in this topic

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
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
I''m just curious, does this method produce a bezier curve, or is it just some other sort of nonspecific an unspecial curve?
0

Share this post


Link to post
Share on other sites
KeithW: If you refer to my method (from my first post), I dont know what type of curve it creates/defines or if it even creates any curve.
Or I just dont understand your question .

K.
0

Share this post


Link to post
Share on other sites
Hey Marvin, could you please give me your email address ? I gatta ask you something !!

Please.... (or you can send ME an email @ VanKurt@gmx.de)

Thx, VanKurt
0

Share this post


Link to post
Share on other sites