Camera collision with heightmaps?

Engines, Libraries and Tools Java 3D
#1

Hi!

I started with my first attempt to reder heightfields with LWJGL.
The heightmap is rendered using triangle strips (flat filled at the moment or wireframe)
with NO optimizations - each frame all polys are rendered.
I can fly over the terrain, but now I want to implement collision detection
so that the camera always stays at a fixed height above the ground.
Now, how do I know on which triangle I am standing?

My camera holds a vector (x,y,z) for the position in space
and 2 angles for orientation (y-, and x-rotation to look left/right and up/down).

The terrain is scaled by a constant factor in x-, and z-direction and also translated,
so that the origin is in the middle of the map.

I do the following:

a = (int) camera.x / scale + mapsize/2
b = (int) camera.z / scale + mapsize/2

This gives me the square (a,b) on which I stay, right?
But how do I know on which one of the two triangles I am standing?
Btw. , is this the right way to handle collision on terrains?

I hope my explanation is clear enough since I’m very tired :wink:

Thanks in advance, Adam.

#2

Handling collision on heightmap is easy. Look at the “41th GameTutorials.com” tutorial on my website (http://chman.tuxfamily.org/gt/GT41.ZIP), in the render method, you will see something like that :


        // Get the current position of the camera
      CCamera.CVector3 vPos = g_Camera.Position();
      CCamera.CVector3 vNewPos = g_Camera.Position();

        // Check if the camera is below the height of the terrain at x and z,
        // but we add 10 to make it so the camera isn't on the floor.
      if(vPos.y < terrain.Height(g_HeightMap, (int)vPos.x, (int)vPos.z ) + 10)
      {
              // Set the new position of the camera so it's above the terrain + 10
            vNewPos.y = (float)terrain.Height(g_HeightMap, (int)vPos.x, (int)vPos.z ) + 10;

              // Get the difference of the y that the camera was pushed back up
            float temp = vNewPos.y - vPos.y;

              //  Get the current view and increase it by the different the position was moved
            CCamera.CVector3 vView = g_Camera.View();
            vView.y += temp;

              // Set the new camera position.
            g_Camera.PositionCamera(vNewPos.x,  vNewPos.y,  vNewPos.z, vView.x,      vView.y,      vView.z,      0, 1, 0);                                                
      }

Hope it helps !

++
Chman

#3

[quote]Handling collision on heightmap is easy.
[/quote]
Very clever!

I’m sure he asked for how terrain.Height(g_HeightMap, (int)vPos.x, (int)vPos.z ) is done!

#4

oh… sorry, i hadn’t paid attention to that !

anyway, look in the source code of GT41, you will surely find something intereting.

#5

Assuming a coord of (1,3) coverts to an array height of [1][3], then something like this:


xMin = Math.floor(xCoord);
xMax = Math.ceil(xCoord);
// repeat for y..

// Find weights:
xWeight = xCoord - xMin;
yWeight = yCoord - yMin;

// Perform weighted average
xHeight = xMin*xWeight + xMax*(1-xWeight);
// repeat for y..

This may not be 100% accurate, you may have to take into account which way the 4 heights are joined with triangles, but its a good starting point…

#6

Your code is more accurate than mine, thanks for that Orangy Tang.
And yes, Herkules is right, that was what I was looking forward.
Right now I take the four vertices of the grid the camera is standing
in and average the four y-values.
This is very ugly, because it looks like going stairs up instead of
walking on a terrain.
I’ve read something about creating a bounding sphere around
the camera and check for collision on all triangles.
But isn’t it easier to calculate the planes equation of the triangle
under the camera and calculate the height with this?
That was my idea I but don’t know where to start.

#7

You can also use simple trigonometry… set your cameras origo somewhere behind the screen, or the same pos where the came is, and now calculate the distance between every vertex that is directly ahead.

I’ve seen this in use, and I think Tribes2 uses it aswell… So basically you have right angle triangle going downwards of your camera. and if the hypothenuse/intersects with a triangle then it raises it up. Of course this doesn’t work when going downwards, but that is quite easy to do with physics.

#8

[quote]But isn’t it easier to calculate the planes equation of the triangle
under the camera and calculate the height with this?
That was my idea I but don’t know where to start.
[/quote]
Ah yes, now there might be a better solution - you’ll have to bear with me, by a strange coincidence I was just starting to experiment with plane equations a few days ago…

Plane equation:
point.normal + d = 0

Or, more generally, ax + by + cz + d = 0. So, er, assuming you know the heights of the 3 points of the triangle, a bit of vector addition and subtraction should get you the normal at a point. Then you can use one of the point and the normal to find the constant, d. Like:
constant = -normal.point

Then you should be able to feed in the current x and y into the plane equation and calculate the z height for the point. I think this should be totally accurate, if a tad slower. On the other hand, if this is for a camera then you’re possibly more interested in smooth movement than accuracy, so perhaps you could average the normals for the points or something. Or just smooth out the camera movement over time (weighted averages I find work rather well :smiley: ).

#9

Lets say that player A is climing up the hill B which is made out of triengle strip C. Now checking all the triangles in the mountain would be an overkill to the computer and sometimes the triangle under you doesn’t work since you sort of want to be one step ahead.

The side of the triangle going downwards of the triangle is the height you want the camera to stay when it moves. Say that it is 10 whatever units you are using. Now the other side of the triangle that gos forward of the camera, perpendicular to the line pointing downwards. Here you have the hypothenuse. Let’s you are checking over distance of 10 units as well. The lenght of hypo should be about 14.1 or so. The longer the hypo the smoother the climbing, the lenght of hypo doesn’t matter since all you need is the beginning and the end of hypo.

Now this triangle works exactly the same way as in frustum culling, except that it is a megaton of faster. You can put this in the frustum equation so it really, really fast. When any of the triangles has intersected with the collision triangle the test is canceled and turned into false and now frustum culling continues with the rest view frustum without testing for the triangle. Now logically the right angle position of the triangle gets elevated by the delta as well as the camera position, and now you can do the same check again.

I’m pretty sure there was some algorithm to test it only with the triangles under the line going forward of the camera, but I can’t figure it out now. I’m pretty sure you can figure it out in an hour or two on paper. Damn tests…

:frowning: