Back to General and Gameplay Programming

Walking on a terrain in a FPS?

General and Gameplay Programming Programming

Started by mikenovemberoscar March 20, 2010 11:40 AM

30 comments, last by mikenovemberoscar 14 years ago

mikenovemberoscar

215

Author

March 27, 2010 01:15 PM

Right, so is this OK:

(pseudo-code)
SetupLevel()

sort triangles into XZ grid cells

GetFloor()

1.Get player's position2.Get player's cell3.Loop through triangles casting a ray downwards and getting the distance to each ray collision4.Get the triangle with the smallest distance 5.Interpolate heights from three points

If this is OK, there is one main area of problem:
1. Step Three in Getfloor : how do I cast a ray? Can anyone help with a point in triangle function?

http://www.sites.google.com/site/michaelssoftwaresite/

bzroom

648

March 27, 2010 09:00 PM

You'll need to check each triangle, as you said. But the ray vs triangle intersection starts first as a ray vs plane intersection to get the point on the ray, then checks are done to check that the point lies within the triangle.

mikenovemberoscar

215

Author

March 28, 2010 07:14 AM

Thanks, but I tried to get a point in triangle (and ray-plane for that matter) function but couldn't find any guides. Anyone know of any tutorials/guides/examples?
Another problem was sorting the triangles into grid cells at the start of the program. How can I do a triangle - square test?

http://www.sites.google.com/site/michaelssoftwaresite/

Dave Eberly

1,182

March 28, 2010 11:52 AM

Quote:Original post by bzroom
If the ray does not intersect something, the character has left the ground and enters a physics based falling mode.

...such as when you get (un)lucky and the cast ray happens to intersect (near) the edge shared by two triangles and neither triangle "reports" an intersection (due to numerical round-off errors). To avoid this might require having collision geometry in addition to the geometry you need for visualizing.

Quote:
Lastly, ray cast against everything. Often physics engines are highly optimized ray casting machines, but ideally that would happen at the graphics detail level. It doesn't make sense when bullets or characters are hovering over the graphics because they're colliding with the physics primitive.

Ray casting everything can be expensive. Moreover, you are not guaranteed to avoid a collision. You hope is that the probability of missing a collision when there is one is small.

As I said, there is more to this than geometry and simple ray-triangle tests.

Dave Eberly

1,182

March 28, 2010 11:55 AM

Quote:Original post by bzroom
The ray casting should accept a world space ray (origin and extent) and return the first intersection point along that ray.

This depends. For example, you might want your character to walk into a shallow pond of water. If you store only the first intersection along the ray, you'll have your character walking on water. Well, maybe that is what your game is about.

mikenovemberoscar

215

Author

March 29, 2010 09:55 AM

Well, there would be no way to check the water, what's the geometrical difference between that and a roof with a ceiling underneath?

http://www.sites.google.com/site/michaelssoftwaresite/

tpascal

120

March 29, 2010 10:20 AM

This article called Terrain Fallow will help you: http://www.toymaker.info/Games/html/terrain_follow.html

However, take note that seem you pretend to load *ANY* OBJ file and make your character wallk on in. Just throwing a triangle soup to your engine is not really realistic, you need to implement any kind of scene management like a bsp tree, octree, grid system, etc,

bzroom

648

March 29, 2010 03:53 PM

Quote:Original post by Dave Eberly
Quote:Original post by bzroom
The ray casting should accept a world space ray (origin and extent) and return the first intersection point along that ray.

This depends. For example, you might want your character to walk into a shallow pond of water. If you store only the first intersection along the ray, you'll have your character walking on water. Well, maybe that is what your game is about.

Flags. The water is not tagged as "ground" and therefore is early rejected in the ray test.

A small epsilon will eliminate the neighboring triangles issue.

Quote:
Ray casting everything can be expensive.

Somewhat, but not really. Not if you have spatial partitioning and dont search models that you did not remotely intersect.

Quote:
Moreover, you are not guaranteed to avoid a collision. You hope is that the probability of missing a collision when there is one is small.

I have no idea what you mean by this.

You're making things way too complicated.

mikenovemberoscar

215

Author

March 30, 2010 10:21 AM

Well, thanks for the replies.
As for the ground flagging, I might include another file specifying the different types of faces in the OBJ, structured like the faces in an OBJ file. That's quite trivial though.

As for partitioning, one of my methods (I did mention this in the first post) was to divide the map into a grid at the start, then sort each triangle into the corresponding grid cells. When I need to check, I find the player's grid cell, then check all of the triangles in that cell. Hopefully there should only be one or two, but it depends on the size of the map and grid.

That is why I need a triangle-square collision detection function.

http://www.sites.google.com/site/michaelssoftwaresite/

bzroom

648

March 30, 2010 03:50 PM

You should just store your meshes in a quad or oct tree by their bounding box.

So when you ray cast, you first find the cells of the quad tree that intersect the ray, then you check the ray against the total model bounds for each model in those cells, and for each model bounds that you hit you check it's sub mesh bounds, and for each sub mesh bounds that you hit you check every triangle.

There are other partitioning methods designed for flat shapes like triangles that you could use once you got to the sub mesh level, such as bsp.

Walking on a terrain in a FPS?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Walking on a terrain in a FPS?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines