🔒 Locked

travel on surface algorithm

Started by kneeride Mar 15, 2007 at 10:35 PM 4 replies 700+ views

Original Post

Mar 15, 2007 at 10:35 PM

I'm wondering whether people can give ideas for implementing the following algorithm: I wish to travel an object across the surface of a mesh/terrain. the distance travelled is variable, say X world units. NB: The traversal must follow the gradient of the land. I must therefore need to know when the object passes from one polygon to another so that the direction vector can be projected onto the new polygon. Now this would seem to be a common request, however I have found otherwise. The following is my high level algorithm: NB: the object has already been intersected with the terrain and the intersection polygon is known. 1. project the direction vector onto the current polygon 2. travel the object along the direction vector until the object intersects an edge of the polygon 3. find the neighbouring polygon with the edge intersection 4. project the direction vector onto the new polygon 5. travel until the next intersection 6. do this until the object has travelled X units. Now implementing the above is quite complex. Does anyone have any better ideas? Has this been done before?

Cowboy Coder

Mar 15, 2007 at 11:10 PM

Based on your problem specification that sounds reasonable.

But what problem are you actually trying to solve? A unit traveling X world units in three dimensions? Why exactly?

oliii

271

oliii

Mar 16, 2007 at 3:39 AM

I think it's worth a try. As for complexity. It actually seems quited simple. Might get a tad fuzzy when you start crossing at vertices.

Rand

Mar 16, 2007 at 4:50 AM

Sounds like a good approach to me. To optimise it later you could store a list of which triangles connect to each other. 3 neighbours per triangle. That would speed it up a lot.

The only other thing, is instead of the distance to travel i would give it a target to reach, but this depends on what your trying to do with it.

kneeride

Author

kneeride

Mar 16, 2007 at 6:58 AM

Quote:
Original post by Cowboy Coder
But what problem are you actually trying to solve? A unit traveling X world units in three dimensions? Why exactly?

This alg is for travelling over terrain.

My goals:
- accuracy
- intersecting polygons that can't be travelled on. i figure this solution would be faster than testing intersections with walls in the area that define areas that can not be passed.

NB: I'm thinking that this might be too much. I might go back to the normal way of 1. projecting the vector onto the current poly, 2. move X units, and 3. intersect the object back with the mesh using a verticle vector.

For intersecting the non walkable areas I might create polygons that define the walls that divide the non walkable areas and using normal ray
casting/intersections with these areas

Quote:

Might get a tad fuzzy when you start crossing at vertices.

Yes, that is a big problem. passing over an edge is fine because the mesh will be setup to only have 1 neighbouring poly.

However passing over a vertex will be difficult because there maybe multiple neighbouring polygons.

An additional (but rare) problem would be passing over a vertex and straight down an edge...holy smokes!!

oliii

271

oliii

Mar 16, 2007 at 7:03 AM

If your terrain is some kind of heightmap, there are other solutions (bilinear interpolation). Much easier and faster.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.