Traversal of a 3D Triangle Plane
Author
Hi guys,
I am stuck!
Traversing terrain in old 2d games was easy. The old straight-line formula worked wonders, with a unit following the line.
How would one go about traversing a 3D Triangle terrain?? I have my exact starting point (xs,ys,zs) on the terrain and the exact destination point (xd,yd,zd).
Don't know if you require any more information on the problem?
Any ideas or a shove to the right algortihm would be appreciated!
Best regards,
Riaan.
Let's look at a simple technique for moving around on a terrain made of triangles. If there is some direction that is defined as generally "down" (e.g., the direction gravity would act), and if you have some AI or user control that indicates the desire direction of movement (say, walking), then a conceptually easy way to move around is:
Here, the first 4 steps really represent 2D movement, in the xy plane, horizontally.
The 5th/6th steps do the terrain following. Here it is very, very simple...just lookup the terrain height by ray tracing using a vertical ray, then assign the found terrain height to the position....the player or object will snap to the terrain.
The reason for the "+ 5.0" in step 5 is so that the ray trace will be slightly above the terrain even if the terrain in the movement direction is going up a hill. This basically enables the object to move up a hill, walk up stairs/steps, follow rocks, etc., that might be represented in the terrain. If you don't include this, and you try to walk up a hill, you will either walk into the terrain instead of on top, or you will fall through, or you will simply disallow movement in any direction where the ray trace does not intersect the terrain.
This isn't a foolproof system. It's very simple. It works, and is easy to code.
The hardest part of this is the ray tracing. It is easy, and you should be able to find posts here (many many posts in the archive) on finding the intersection of a line and a triangle. That's the basic ray tracing algorithm. But to do a fast ray trace against many triangles...the trick here is that you need to do spatial partitioning, and that is what you search should help you with. A spatial partitioning scheme that works well for triangle models is called the Kd-tree. "Ray tracing using a Kd-tree" would probably be a good search phrase.
You can go more complex from here, e.g., adjust speed based on some physical properties of the terrain and object (harder to walk up muddy hill), etc.
I know that was a ramble. I hope it helps.
1) Assume +Z is up2) Assume desired movement direction is dir(x,y) ---- given by AI or player control. Must be a unit-length vector.3) Current position is pos(x,y,z)4) Given a movement speed, compute the new (x,y) location: pos = pos + speed*dir*time_step; Here, time_step is the amount of time since the last update. For example, this could be the frame time. Make sure units are consistent, e.g., if you represent speed in meters/second, then the time step should be in seconds so that speed * time_step is in meters.5) Ray trace the terrain triangle list using a vertical ray to find the terrain height: ray_start_pt = vec(pos.x, pos.y, pos.z + 5.0); ray_dir = vec(0.0, 0.0, -1.0); // look down towards terrain terrain_height = ray_trace_terrain_triangles(ray_start_pt, ray_dir);6) Assign terrain height to new pos: pos.z = terrain_height7) repeat 1-6 for every frameHere, the first 4 steps really represent 2D movement, in the xy plane, horizontally.
The 5th/6th steps do the terrain following. Here it is very, very simple...just lookup the terrain height by ray tracing using a vertical ray, then assign the found terrain height to the position....the player or object will snap to the terrain.
The reason for the "+ 5.0" in step 5 is so that the ray trace will be slightly above the terrain even if the terrain in the movement direction is going up a hill. This basically enables the object to move up a hill, walk up stairs/steps, follow rocks, etc., that might be represented in the terrain. If you don't include this, and you try to walk up a hill, you will either walk into the terrain instead of on top, or you will fall through, or you will simply disallow movement in any direction where the ray trace does not intersect the terrain.
This isn't a foolproof system. It's very simple. It works, and is easy to code.
The hardest part of this is the ray tracing. It is easy, and you should be able to find posts here (many many posts in the archive) on finding the intersection of a line and a triangle. That's the basic ray tracing algorithm. But to do a fast ray trace against many triangles...the trick here is that you need to do spatial partitioning, and that is what you search should help you with. A spatial partitioning scheme that works well for triangle models is called the Kd-tree. "Ray tracing using a Kd-tree" would probably be a good search phrase.
You can go more complex from here, e.g., adjust speed based on some physical properties of the terrain and object (harder to walk up muddy hill), etc.
I know that was a ramble. I hope it helps.
Author
Thank you Graham!
I will implement it like this and get back to you if I run into problems.
Best regards,
Riaan.
I will implement it like this and get back to you if I run into problems.
Best regards,
Riaan.
Author
Hi Graham,
I have not implemented your algorithm, but have thought it through thoroughly. I think there is a pitfall. Allow me to explain, and please shred my argument if it is not sound.
You said "Here, the first 4 steps really represent 2D movement, in the xy plane, horizontally.", and this is my problem.
Imagine you have a terrain grid with each increment in the X and Y direction being 1. But some rectangles are raised with Z to, say, 4.
If you traverse with this algorithm, the heightened "stretched" triangles will be traversed 'quicker' (the triangle is longer, but its X,Y is the same as other triangles), because the Z is ignored during movement, and Z traced as an afterthought.
Is this wrong??
Riaan.
I have not implemented your algorithm, but have thought it through thoroughly. I think there is a pitfall. Allow me to explain, and please shred my argument if it is not sound.
You said "Here, the first 4 steps really represent 2D movement, in the xy plane, horizontally.", and this is my problem.
Imagine you have a terrain grid with each increment in the X and Y direction being 1. But some rectangles are raised with Z to, say, 4.
If you traverse with this algorithm, the heightened "stretched" triangles will be traversed 'quicker' (the triangle is longer, but its X,Y is the same as other triangles), because the Z is ignored during movement, and Z traced as an afterthought.
Is this wrong??
Riaan.
Author
Hi guys,
Let me clarify my last post with an image: Worth a thousand words I guess ;)
<br/>
As you can see from the image, the triangle circled in Green and the one circled in Red, have exactly the same dimensions in the XY plane, but, the Green triangle has two of its Vertices lifted (in the Zdirection) relatively high.
Now, if you traverse this terrain in only the XY plane (and pick the value of Z later on), and these two triangles are the same size in XY, then you would traverse both triangles equally fast (time wise). In other words, the larger rectangle will be traversed "quicker" (a larger distance will be covered on the large rectangle in the same time that a smaller distance was covered on the smaller rectangle [blue dotted line]).
Does this make sense to anyone else, or am I missing something?
If my argument is correct, how can I traverse the terrain in 3 dimensions, not only in XY and pick Z later??
Best regards,
Riaan.
Let me clarify my last post with an image: Worth a thousand words I guess ;)
<br/>
As you can see from the image, the triangle circled in Green and the one circled in Red, have exactly the same dimensions in the XY plane, but, the Green triangle has two of its Vertices lifted (in the Zdirection) relatively high.
Now, if you traverse this terrain in only the XY plane (and pick the value of Z later on), and these two triangles are the same size in XY, then you would traverse both triangles equally fast (time wise). In other words, the larger rectangle will be traversed "quicker" (a larger distance will be covered on the large rectangle in the same time that a smaller distance was covered on the smaller rectangle [blue dotted line]).
Does this make sense to anyone else, or am I missing something?
If my argument is correct, how can I traverse the terrain in 3 dimensions, not only in XY and pick Z later??
Best regards,
Riaan.
You're absolutely correct, given the same X and Y values, different terrain heights will produce different Z values which will increase or decrease the speed of the traversal. The trick is to normalize the vector [X,Y,Z], which makes it unit length, and then multiply it by your desired travel speed. This way you always cancel out the length variation created by sampling different Z values from the height-map.
However, there's still the issue of moving across triangle boundaries. For instance, if XY is 10 units long, but each terrain cell is only 1x1, then you will pass through multiple triangles in the middle. Unless you take into account all the triangles in-between, your can possibly move through the terrain itself, for instance if you skipped a tall mountain without detecting it. In cases like this you'd have to actually trace the XY vector across the terrain, detect all the triangles it intersects, clip it along those boundaries, and then have multiple traversals that accurately follows the surface of the terrain.
However, there's still the issue of moving across triangle boundaries. For instance, if XY is 10 units long, but each terrain cell is only 1x1, then you will pass through multiple triangles in the middle. Unless you take into account all the triangles in-between, your can possibly move through the terrain itself, for instance if you skipped a tall mountain without detecting it. In cases like this you'd have to actually trace the XY vector across the terrain, detect all the triangles it intersects, clip it along those boundaries, and then have multiple traversals that accurately follows the surface of the terrain.
Author
Quote:Original post by Zipster
In cases like this you'd have to actually trace the XY vector across the terrain, detect all the triangles it intersects, clip it along those boundaries, and then have multiple traversals that accurately follows the surface of the terrain.
I thought about doing this, but how do I detect where the taversal line leaves the current triangle?
I have the current position and the destination, so I have a line to work with. As well as the current triangle's dimensions and all angles inside the triangle. But how do I get the line exit point from here?
Soz, my maths is a bit shoddy.
Riaan.
Good discussion! I'm on travel, with slow Internet access and a million things to do, so my reply will be brief.
As Riaan observed, the simple approach I presented is based on the idea that the speed of motion is the xy component only, regardless of terrain shape, which will effectively mean the agent/player will accelerate or decelerate depending on the slope of the triangles being traversed.
To be strictly correct about maintaining a constant 3D speed, the piecewise traversal of each triangle crossed in a time step seems necessary; however, a simple compromise might be suitable:
1) Compute the new position based on my algorithm, based on speed being a horizontal constant speed.
2) With the new Z value at the position computed above, you will have a vector from the old 3D position to the new
3) As Zipster suggested, normalize this vector...and assume it'll be your *actual* direction of motion
4) Multiple the result of step 3 times your speed...this'll give you a 3D position that is adjusted for an approximate slope variation between the start and end points.
5) Do a second ray trace to find the actual terrain height, given the adjusted (x,y) coordinate from step 4, and take the step 4 (x,y) + this updated Z to be your final position.
I didn't say that very elegantly. This too isn't perfect, in the way a full piecewise movement across multiple triangles would be. But for time steps that aren't too large and for terrain that doesn't have high frequency variations in height, it might get you close enough to true constant speed to be acceptable. And it'd be less expensive than the full piecewise movement implementation.
As Riaan observed, the simple approach I presented is based on the idea that the speed of motion is the xy component only, regardless of terrain shape, which will effectively mean the agent/player will accelerate or decelerate depending on the slope of the triangles being traversed.
To be strictly correct about maintaining a constant 3D speed, the piecewise traversal of each triangle crossed in a time step seems necessary; however, a simple compromise might be suitable:
1) Compute the new position based on my algorithm, based on speed being a horizontal constant speed.
2) With the new Z value at the position computed above, you will have a vector from the old 3D position to the new
3) As Zipster suggested, normalize this vector...and assume it'll be your *actual* direction of motion
4) Multiple the result of step 3 times your speed...this'll give you a 3D position that is adjusted for an approximate slope variation between the start and end points.
5) Do a second ray trace to find the actual terrain height, given the adjusted (x,y) coordinate from step 4, and take the step 4 (x,y) + this updated Z to be your final position.
I didn't say that very elegantly. This too isn't perfect, in the way a full piecewise movement across multiple triangles would be. But for time steps that aren't too large and for terrain that doesn't have high frequency variations in height, it might get you close enough to true constant speed to be acceptable. And it'd be less expensive than the full piecewise movement implementation.
Author
Haha,
This is getting much closer to what I think I need (might even be exactly what I need!)
Coding it today, and will post the success of the algorithm.
Best regards and thank you for the help.
Riaan.
This is getting much closer to what I think I need (might even be exactly what I need!)
Coding it today, and will post the success of the algorithm.
Best regards and thank you for the help.
Riaan.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
