Collision Detection in Terrain Engine

OpenGL OpenGL: Basic Coding
1

I am building a flight simulator for a school project, and one of my hurdles is putting in good collision detection… I have a 2 dimentional array of heights, and the players xpos, ypos, zpos and the relative velocities for each axis… What is an efficient way to find if the players destination point (xpos + xvelocity…) will collide with the terrain. I can always employ the traditional ray-polygon intersection routine but that is costly and im sure there is a better way if your dealing with a terrain engine… Any suggestions?

2

If I undestand You well, then:

1.You have a regular heightfield terrain. Let`s suppose that your terrain X-axis goes normal OpenGL way (from left to right) and your terrain Z-axis is down the negative Z-axis. Y-axis represents the height of actual point in terrain grid.

  1. You have destination point`s (Dest) X and Z coordinate and You need to calculate the Y-coordinate (Dest.Y).

  2. Since you know the Dest.X and Dest.Z you can easily find in your grid array the square that contains your Dest point. Let`s name the Square points P1,P2,P3,P4. This square has two triangles :P1P2P3 and P1P3P4. If your grid is regular you can simply find out which triangle is yours.

  3. Since you know all coordinates for P1,P2,P3,P4 and you also know Dest.X and Dest.Z, finding Dest.Y (height) is easy.
    Try to draw it on a paper and youll see it immediately. There are just several Multiplies and Divisions which isnt that bad.

  4. Of course you could do the same with plane equation but this approach has several other advantages particulary in my engine so thats why I use it. Yours may be different and if you dont have the usage of counted temporary points other than the Dest.Y it might not be faster than plane equation.

3

you might also want to do a simple height test first, so that you only calculate all this stuff if the plane’s height is under the maximum height value of the terrain…

just a simple suggestion…

4

Actually, line/poly tests are ulmost certainly going to be used at some stage.
Collision detectin for terrains can be greatly speed up compared to arbitary collision detection by using some assumptions.

  1. The landscape does not move.
  2. Your lanscape is not concave (manditory for height fields)

Under these conditions the following steps help greatly.

  1. divide your lanscape into a regular grid(s) greater than the maximum size of your line. This means at worst case you have to check the polys in three grids (buckets). This allows you to quickly zome into the polys which MIGHT collide. If you remember which grid you tested for last, you can get fabulous improvements in speed, as long as you are carefull to check that it hasn’t changed.
  2. consider using a heirachacal version of 1.
  3. consider producing a seperate collision geomety for each bucket. e.g. A BSP style description. Try Watt&Watt for description of BSP. This should allow quick rejection within the buckets. Although quick this solution can be memory intensive, so it depends on what hardware you have.

I hate to contridict the last message but always spend most of your effort of the earliest stage, and avoid the impulse to optimise for best case (e.g. using height). Otherwise you can end with a fast system, until you get near the ground. This is incredably annoying to play, as the last thing you want is for the system to frame out, as you are required to have most skill.

Nigel

5

So the replies above, will those suggestions work for walking on the terrain. I have been looking for info on this topic for a while.