Level Depth

Theres been two big questions on my mind for a long time now about game dev and the time is going to come very soon where im going to need how to do this, because i've thought long and hard about it but i just can't fathom of any way to do it.


Say you have a level or a terrain, it could be for a shooter, or a racer just about anything and its not flat it has angles and hills infact it was as far from flat as anything could possibly be (well actually if it were a racer u'd want some kind of flatness) how could done calculate the depth of the tarrain at any giving location so you would not fall through the floor when you have a mash with what is most likely going to to be 500,000+ polygons.
And how would one calculate it if say you had two floors in a building that could be accessed how would you know when to fall and when to stop.

This seems to me like a fundemental in any givin 3d game, but i wouldn't even know where to begin

As I understand it, you're talking about basic collision detection. There are many ways to optimize it: look into bounding boxes, bounding spheres, BSP and octree's. Simply google for them, maybe in relation to collision detection, and maybe just for collision detection on itself. There are plenty of resources on the web, though I have yet to find a really good one. But at least it's enough to fit the pieces together and understand how to do it.

Yea I have delt with some collision detection with basic 2d games when i was using allegro a while back im just not sure how to implement it when using it on a complex object

Well you are talking about 2 different types of collision here. Granted you can use swept sphere or some other swept type of algo for terrain but it is much easier to use bi-linear interpolation. With bi-linear interpolation you calcuate how far into the terrain quad you are and given you know the heights of the four corners you can compute the height at any point within the quad. But it is even easier than that. You can then compute which triangle the object is in based on it's world coords and you can then interpolate based on the 3 heights or Y values of the triangle vertices.

Swept sphere is much more involved and is done by sweeping a sphere through world space near the player to see what is hit. The system will return a new vector which is the path the object should follow to move around or slide around the object. Usually worlds are composed of several static meshes all placed together to give the illusion of one seamless cavern or tunnel or building. But, in reality, the building is composed of many separate meshes that all have a local scenegraph that tells the system how to draw them. The root of each model's scenegraph is transformed to world position and thus you get the illusion you are walking through some huge perfectly lit and arranged building. You would send these static meshes to the collision system to compute the new vector to follow...if there was a collision.

Collision is usually parametric in that it computes if anything was hit between time T1 and time T2. Once it has been determined a collision occurred now the collision point can be calculated in order to classify the collision or you could fire a ray towards the object that was hit and do a simple ray-triangle intersection test to see where the hit occurred. Normally objects have what are known as collision hulls which are greatly simplified versions of the object. You would not want to test collision against the actual mesh drawn to the back buffer since this mesh is for eye-candy only and would slow the system down b/c it has far more triangles than is needed for accurate enough collision to occur.

Note than on NVidia cards this type of collision testing can be given to the PhysX subsystem. It will do the sweeping in world space automatically and notify the code what exactly happened...if anything.