I''m just starting to implement collision detection into my terrain engine. The problem is, all the tutorials I''ve seen only show collision with a plane. Can anyone explain to me, or have any other tutorials that demonstrate this? Another question is I''ve seen that you need to determine where your destination point is relative to the plane you''re headed towrds. My camera only moves say 1 unit forward each time, so am I supposed to do this check each time, or is there a way to ''sum up'' the moves? Thanks //------------------------------------------------------------------------------------------------------ The great logician Bertrand Russell once claimed that he could prove anything if given that 1+1=1. So one day, some fool asked him, "Ok. Prove that you''re the Pope." He thought for a while and proclaimed, "I am one. The Pope is one. Therefore, the Pope and I are one."

bit of a long post, but the problem is that not straight forward, although not difficult.

The first stage of a terrain/camera collision would be to extract the planes/triangles that can potentially collide with the camera. I do this by calculating the bounding box of the camera relative to the heitghmap pixels, which gives me a patch of pixels, then I reconstruct the triangles from that.

//-----------------------------------------------------------// bounding box around terrain vertices.//-----------------------------------------------------------Vector3 xTerrainMin; // min coordinate of the terrain in the worldVector3 xTerrainMax; // max coordinate of the terrain in the worldint iNumRowsOfPixels;     // number of pixels along the x axis of the heightmapint iNumColumnsOfPixels; // number of pixels along the y axis of the heightmapVector xCamMin; // min coordinate of the cameraVector xCamMax; // max coordinate of the camerafloat fMapRatioMinX = (xCamMin.x - xTerrainMin.x) / (xTerrainMax.x - xTerrainMin.x);float fMapRatioMinZ = (xCamMin.z - xTerrainMin.z) / (xTerrainMax.z - xTerrainMin.z);float fMapRatioMaxX = (xCamMax.x - xTerrainMin.x) / (xTerrainMax.x - xTerrainMin.x);float fMapRatioMaxZ = (xCamMax.z - xTerrainMin.z) / (xTerrainMax.z - xTerrainMin.z);int iMinU = RoundDown(fMapRatioMinX * (float) iNumRowsOfPixels);int iMinV = RoundDown(fMapRatioMinZ * (float) iNumColumnsOfPixels);int iMaxU = RoundUp(fMapRatioMaxX * (float) iNumRowsOfPixels);int iMaxV = RoundUp(fMapRatioMaxZ * (float) iNumColumnsOfPixels);iMinU = ClampInRange(iMinU, 0, iNumRowsOfPixels-1);iMinV = ClampInRange(iMinV, 0, iNumColumnsOfPixels-1);iMaxU = ClampInRange(iMaxU, 0, iNumRowsOfPixels-1);iMaxV = ClampInRange(iMaxV, 0, iNumColumnsOfPixels-1);

RoundDown() rounds a float to the nearest smaller integer
RoundUp () rounds a float to the nearest larget integer
ClampInRange() makes sure that the pixel coordinates fit on the map

So there you go, you now have the patch of pixels underneath the camera. The bounding box of the camera should contain the camera''s bounding volume, and if you do a swept volume collision detection, also the displacement of the camera.

from that patch, you reconstruct the triangles, as you would do for your terrain rendering.

When you have the patch of triangles computed, you do a collision detection with the camera''s sphere/Axis Aligned box / Oriented bounding box and all the triangles in the patch. This is like any other collision detection routine, nothing special about it. See the terrain as another way to partition a bunch of triangles, like an octree would do. So you can plug in this algo into a collision solver, which would take a list of triangles and detect collisions and apply a collision response to your camera.

to make the matters much simpler, you can approximate the camera to a single point. You find the triangle underneath the camera like in the algo above (the algo above should only return 4 pixel coordinates, thus two triangles to calculate).

Then you cast a ray from your camera position down the Y axis, find the point of intersection with one of the two triangles, and push the camera up from the point of intersection by an altitude value.

//-----------------------------------------------------------// bounding box around terrain vertices.//-----------------------------------------------------------Vector3 xTerrainMin; // min coordinate of the terrain in the worldVector3 xTerrainMax; // max coordinate of the terrain in the worldint iNumRowsOfPixels;     // number of pixels along the x axis of the heightmapint iNumColumnsOfPixels; // number of pixels along the y axis of the heightmapVector xCamPos; // Camera positionfloat fMapRatioX = (xCamPos.x - xTerrainMin.x) / (xTerrainMax.x - xTerrainMin.x);float fMapRatioZ = (xCamPos.z - xTerrainMin.z) / (xTerrainMax.z - xTerrainMin.z);int iMinU = RoundDown(fMapRatioX * (float) iNumRowsOfPixels);int iMinV = RoundDown(fMapRatioZ * (float) iNumColumnsOfPixels);int iMaxU = iMinU+1;int iMaxV = iMinV+1;iMinU = ClampInRange(iMinU, 0, iNumRowsOfPixels-1);iMinV = ClampInRange(iMinV, 0, iNumColumnsOfPixels-1);iMaxU = ClampInRange(iMaxU, 0, iNumRowsOfPixels-1);iMaxV = ClampInRange(iMaxV, 0, iNumColumnsOfPixels-1);Vector Triangles[2 * 3];int iNumTris = ComputeTerrainTriangles(iMinU, iMinV, iMaxU, iMaxV, Triangles);float fCameraAltitude = 10.0f; // hovers 10 meters above the groundVector *pxVertices = Triangles;Vector xPointOfIntersection;float  fDistanceToIntersection;Vector xNormalAtIntersection;Vector xCamRayDir(0, -1, 0);for (int i = 0; i < iNumTris; i ++, pxVertices += 3){    if (RayTriangleIntersect(pxVertices, xCamPos, xCamRayDir, xPointOfIntersection, fDistanceToIntersection, xNormalAtIntersection))    {        xCamPos = xPointOfIntersection + xCamRayDir * fCameraAltitude;    }}

The problem with that, is that your camera could clip through triangles on the terrain if there is a sharp slope near the camera on the terrain. But in 99% of the cases, it should give good results, and the algo is simple.

you can find a ray/triangle intersection routine easily on the net.

http://www.ce.chalmers.se/staff/tomasm/code/
http://www.realtimerendering.com/int/


To avoid that clipping, what you can try is use the algorithm at the top of the post, find all the triangles underneath the bounding box of the camera, and find the distance of your camera position to all those triangles. If the distance to a triangle is too small, then push your camera away(the distance algoritm should give you the point on the triangle that is the closest to your camera, so you push it away along the vector (ClosestPoint - CamPos).UnitVector()). By doing that, you could be pushing your camera towards another triangle, so you need to do the distance check several times, until the camera is far enough from all the triangles.

Ok, I think I basically get it, but I''m a little confused on some of the variables.
Vector3 xTerrainMin; // min coordinate of the terrain world
Vector3 xTerrainMax; // max coordinate of the terrain world
My initial supposition for these variables would be the smallest and largest coordinate in my map, but that seems to be taken care of by RoswPixels and ColsPixels. In my case the map goes from (0,0), to (256, 256).

Vector xCamMin; // min coordinate of the camera
Vector xCamMax; // max coordinate of the camera
My camera is represented by a single vector. I guess I could add and subtract something to the x and z coord to ''create'' an encompassing area. Am I on the right track here?

if you have one unit spacing per vertex, then yes,
xTerrainMin.x = 0.0f
xTerrainMin.z = 0.0f
xTerrainMax.x = 256.0f
xTerrainMax.z = 256.0f

but most of the time, the terrains are scales and probably centered at (0, 0, 0)

if you terrain goes from 0->256 with 256 pixels, then the conversion is easy, and the camera is a single point

int MinU = RoundDown(CameraPos.x);
int MinV = RoundDown(CameraPos.z);

MaxU = MinU+1;
MaxV = MinV+1;

but as I say, you might experience some clipping with your camera (the near plane of your camera should not be at 0.0f, usually, the near plane is set at 0.5f or something).

so there, calculate the triangles from minU, MinV, MaxU, MaxV, raytrace verticaly to find the point of intersection, and push the camera up from that point.

if you want to stop clipping, build an area around your camera to capture the nearby triangles, and do the distance check & push.


MinU = RoundDown(CameraPos.x - fCameraRadius);
MinV = RoundDown(CameraPos.z - fCameraRadius);

MaxU = RoundUp(CameraPos.x + fCameraRadius);
MaxV = RoundUp(CameraPos.z + fCameraRadius);

ect....