Walking along the surface of another object

You will want to store the edge connectivity of each triangle. Store an index to the neighbouring triangle with each edge. Make sure that you never lose track of which polygon your origin is projected down onto. Every time you cross an edge search for where you have arrived at. You need to do this iteratively in case you cross at a vertex. Remember that moves can also cross multiple triangles in one go. Don't get in an endless loop checking for the neighbours (ie remember where you have already checked).

that was me BTW :) What's wrong with the GDnet profiles?!?

If you construct your surface so that it can be expressed analytically, for example using bezier surfaces, then motion across the surface can be calculated both quickly and accurately using Lagrange dynamics. If you're interested I recommend picking up 'Classical Dynamics of Particles and Systems' by Marion Thornton or 'Game Physics' by David Eberly. Also so far no-ones mentioned that feature walking only works for convex meshes rather than arbitrary meshes.

The neighbouring polygon method works with arbitrary meshes that don't have more than 2 polygons adjoining a single edge. I used this technique in a game and you could drive across arbitrary surfaces. Some test meshes were the openGL teapot (concave), mobius strip, torus, sphere, etc.

A (plane based) height map is obviously a no-no for a sphere.

EDIT: To make it easy to start with, do point collision where the point is in the plane of its current polygon. Highlight the polygon you are currently on and have rotate, forwards and backwards controls.

Quote:

Original post by Paradigm Shifter The neighbouring polygon method works with arbitrary meshes that don't have more than 2 polygons adjoining a single edge.

I was more refering to Oliii's suggestion of finding closest point on the mesh to the target using feature walking. Such a method would depend on Voronoi regions which can become degenerate for non-convex meshes. The thing about 2 polys adjoining a single edge would probably mess up a convex mesh as well. I'm wondering though how your method copes with objects which encounter crevices in the mesh due to it being non-convex. If the object is larger than the crevice width but smaller than the crevice depth won't your method try to push it down into the crevice even though it doesn't fit?? Sorry, I'm not trying to split hairs, I'm just curious if you've come across this as a problem?

I wasn't saying that, but nevermind. the walking stuff only works with convex objects obviously. Well, you can walk on non-convex surface, but you are not converging towards a kind of unique solution, like with convexes, so you need some method to stop searching. I was just suggesting to grab a few polys around the target point, and find the closest point to that target point on those polys. Of course, you can filter a few, like the ones facing down, ect...

about holes, spiders do that. they probe around to see if they will fit or not, and they can fit through pretty small holes. If there is a gaping hole, they'll try to bridge it.

Well I don't know, I don't spend my time looking at how spiders commute, however fun it might be :)

Quote:

Original post by oliii I wasn't saying that, but nevermind.

Sorry for the confusion. My bad. I don't suppose what I mention is much of a problem for spiders since they're very small but if you plan on using larger objects it could be. I've drawn a little piccy to explain better:



I bet Van Gogh is sweating now :). Anyway, if the ball is moving from left to right then using a feature walking algo it will stick to the tri I've pointed at and get pushed into the crevice even though it doesn't fit. See what I mean? You'd have to scan ahead or collide with the surrounding tris each time, and if you're in a situation like above then switch to another method or compensate in some way. The only way to garauntee this doesn't happen is to restrict yourself to convex meshes.

Quote:

Original post by oliii Well I don't know, I don't spend my time looking at how spiders commute, however fun it might be :)

Spiders are funny, especially when high. Check out what these buzzing spiders have made...Clicky.....They really dig caffene :).

I agree that if the object has size (i.e. not a point in the polygon) there will be a problem with convex meshes.
What we did was to project the point upwards and do sphere collision based on the point projected upwards (wrt the polygons normal, i.e. up changes depending on which poly you are on). You can be between convex edges in this case, I think we solved that by averaging the polygon face normals of polygons you were straddling while you were between edges.
It was pretty complicated to get right though, I remember a couple of months (2+) of late nights fixing bugs.
Our game had you in a floaty ship though (bit like wipeout) so a bit of bouncing didn't seem too bad. We also only did collision on the "floor" mesh and the rest of the world ("walls") was just decoration with no collision. There was no gravity.
The OP could probably do point collision of just the spider legs though, and then use some method to position the spiders body based on foot position. The point collision version was easy.

I didn't know spiders commute. Are they associative too?

Thanks for all the replies.

I'm using Ogre as the graphics engine.

I think the first step I will take is to create a very simple 'plane' surface in 3DS and then convert it into the OGRE mesh format.

I *think* this (xml) format lists how the faces join together :

Quote:

- <faces count="512"> <face v1="1" v2="2" v3="3" /> <face v1="3" v2="4" v3="1" /> <face v1="2" v2="5" v3="6" /> <face v1="6" v2="3" v3="2" /> ... ...

And the vertex themselves :

Quote:

- <geometry vertexcount="290">- <vertexbuffer positions="true" normals="true" colours_diffuse="false" texture_coords="1" texture_coord_dimensions_0="2">- <vertex> <position x="-117.507" y="26.6164" z="119.078" /> <normal x="0.0" y="1.0" z="-3.56533e-007" /> <texcoord u="0.0" v="1.0" /> </vertex>- <vertex> <position x="-117.507" y="26.6164" z="119.078" /> <normal x="0.0" y="1.0" z="-3.56533e-007" /> <texcoord u="0.0" v="1.0" /> </vertex> ... ...

Atleast I think that's what it does (feel free to correct me, as I said, I have very little experience with mesh data structures.

There are the usual functions to build stuff like an edge list too.


The spiders will (hopefully) eventually be able to walk across arbitary surfaces, but for the moment I am not perticularly concerned with moving their legs. As I said, the spiders will be represented by a simple object like a sphere (just a beacon to show where they are on the surface really).

So going back to the simple 'plane' object (although it must be stated that I will still want to treat it as an arbitary surface)...

I've got this plane object converted from a 3DS object into OGRE's native OgreMesh format.

I've created a 'creature' object and I want to place it on a random polygon on the surface. This is how I think I could do it :

---

(Movement of the creature updated via simple Euler Integration)

1. Pick a random polygon from the object mesh
2. Place the creature at the centre of this polygon (the average position of the three vertices that make up the polygon?).
3. Set the UP vector of the creature's orientation matrix to be equal to the normal of the polygon.

So as it stands I have a simple surface, and the creature is orientated on it so that its parallel with it. If the creature was represented by a static spider mesh, it would look like its standing on the surface at this point.

4. Increase the velocity of the creature, causing it to move in the direction of its FORWARD vector.

(This is where it gets a bit hazy, if it hasn't already! [wink])

5. OK, so the creature is moving. A ray is cast downwards which finds out which polygon the creature's origin is currently intersecting.

6. When its detected that the creature is on a different polygon, it looks at the normal of this polygon and updates its UP vector.

---

Am I thinking about this correctly? Or to put it another way, exactly how wrong am I? [grin]

Cheers for all the help guys, I need it!

SFA.

[Edited by - SFA on October 21, 2004 12:56:20 PM]

that's a way to do it. find the polygon underneath the creature, use the normal and forward vector to generate an orientation matrix (you need to re-orthogonolise the matrix afterwards, thus giving you a new forward vector parallel to the plane surface).

THat's as simple as it gets :)

SFA has the right idea, but don't forget the distance to the intersection so you can offset your spiders distance to the polygon.

Quote:

Original post by iosys SFA has the right idea, but don't forget the distance to the intersection so you can offset your spiders distance to the polygon.

Can you explain what you mean by this (and why its necessary)? Thanks!

If you're walking along a flat surface and come to a downward slope, how is your model going to move along that sloped surface? Orienting it to the surface by using the surfaces normal is perfect, but the model will still be floating at the level it was when it was on the flat surface.

Assuming +Y is up, you should take the models Y coordinate in worldspace, add it to the distance to the intersection (the distance should be negative since it is projected downward on the -Y). That should position the model's origin right onto the point of intersection. Then you offset the model to be a little above or below the surface, depending on where your models origin actually is.

If that doesn't work, I'll peek at my code when I get home.

Hey there again.

I'm at a stage now where I can load in a landscape, and place a creature on the surface. The creature has access to all the information it will ever need about the landscape (a sphere at the moment) including the polygon/face array, edge list and vertex/face normal arrays.

I'm having a bit of difficulty getting the creature to move across the surface.

What I want to do first is :

1. The creature is initalised at the centre of a random polygon on the surface. (DONE)
2. I press a key and the agent moves in a random direction parallel to the surface, and continues through space after that (for the time being).

Now my creature's target position is a 'carrot on a stick' which is a point in front of its nose that it heads towards every frame. In Craig Raynold's Steering Behaviours he calls this 'wondering'. As the creature moves, so does the target point in front of it. The target point lies on an invisible circle, and every frame a small offset is added to its position which causes the agent to randomly steer left and right as the target position changes.

At the moment, no offset is added, so the target point is directly in front of the agent (i.e it will head in a straight line).

Quote:

V_wonderTarget = (V_polygonNormal * cos(angle) + V_Up * sin(angle)) * radius;

Where:

V_wonderTarget = vector position of target point
V_polygonNormal = vector normal of polygon the agent is currently standing on
V_Up = Creature's Up vector
radius = Radius of (invisible) wonder circle
angle = Current angle difference from directly in front of agent (set to 0 here).


What this causes the agent to do is move directly upwards from a surface, as if it was a rocket pointed towards space. What I want it to do is move across the surface, i.e perpendicular to the surface normal! [depressed]

Craig Raynolds describes the way you'd go about creating a surface hugging vehicle as follows :

Quote:

For a Òsurface hugging (wheeled, sliding, or legged) vehicle, we want to both constrain the vehicle's position to the surface and to align the vehicle's up axis to the surface normal. In addition the velocity should be constrained to be purely tangential to the surface. These requirements can be easily met if the surface manifold is represented in such a way that an arbitrary point in space (corresponding to the old vehicle position) can be mapped to: (1) the nearest point on the surface, and (2) the surface normal at that point. The velocity can be made tangent by subtracting off the portion normal to the surface. The vehicle's position is set to the point on the surface, and the surface normal becomes its up axis.

Can anyone explain to me what exactly he means by the bold text?

Thanks guys. I would be very grateful for any help! [smile]

What he's saying is that if you remove all components of the velocity which are normal to the surface (ie. aligned with the surface plane/tri normal) then what is left of the velocity must be completely tangetial to the surface and so will move the object along the surface like it is stuck to said surface. You do this by projecting the velocity vector onto the surface normal vector (using the dot product) to find the magnitude with which the velocity vector lies in the surface normal direction. Then subtract the surface normal vector scaled by the above magnitude from the velocity vector (your surface normals must be unit length for this to work correctly). What you'll be left with is the component of the velocity vector which is tangetial to the surface.

Thanks Motorherp, that works perfectly! [wink]

no problem [wink]

Helo, me again! [wink]

I've managed to get my creature to move across the surface of any arbitary mesh.



Above you can see my program running in debug mode.

green sphere : The creature (currently floating just above the landscape its moving across)
light blue sphere : The creature's target point (carrot on a stick style).
red polygon : Current polygon the creature is 'on'.
dark blue spheres : Vertices of current polygon the creature is 'on'.
red, green and blue lines : Creature's orientation vectors (forward, up and side).
yellow line : Ray projected from the agent's origin downwards (negative up vector)
yellow sphere : Position on polygon where the ray intersects (when creature is not elevated, this is its exact point on the current polygon).

Now what I do is test (every x number of steps) if the creature is under a different polygon. When this happens, I re-orientate the creature so that its up vector is equal to the polygon normal and its velocity is tangent to the new surface.

The problem is, when the agent moves from one polygon to the next, it 'jumps' from one orientation to another. It also changes direction (although perhaps that's because of the orientation change).

Would it be better to do something like interpolate/smooth between the old orientation and the new one to get smoother movement/transition between the polygons? Or am I doing something incorrectly / thinking about this the wrong way?

Another problem I've come across (and anticipated) is that the agent won't move across angles of more than 90 degrees. Obviously the reason for this is that the 90 degree angle polygon isn't 'under' the agent at any time, and therefore the ray never intersects with the polygon. Is there a method of dealing with this? Perhaps I could do some kind of scan? (scanning the ray forwards and backwards or something).

[Edited by - SFA on November 26, 2004 7:35:48 AM]

Perhaps Interpolation between the two orientations would work?