Archived

This topic is now archived and is closed to further replies.

Collision detection on NON-UNIFORM terrain meshes

This topic is 5149 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi Everybody! I am not sure what is the proper way of performing collision detection on non-uniform terrain mesh. Non-uniform I mean not regular grid mesh. In every collision detection I think before we determine if a point collides with the terrain surface (triangle) we first must determine which triangle we should test for. Obviously we wouldnt go through each triangle in the whole terrain database in order to test if a point collides with every triangle or not. This is my question HOW TO SELECT the correct terrain triangle on non-uniform mesh in order to check if a point touches the selected triangle or not which is the second step that I already know. I'll describe first my method which works quite well but is not enough for me as it works purely for regular grid meshes. So, I want to select which triangle the point "p" i above so that later I can tell if it touches the triangle surface or not. Say I have a simple terrain grid eg. 10 by 10 triangle stripes (grid cells). so we have 100 grid cells and 200 triangles in total (each cell contains 2 triangles). Each grid cell is 2 meters wide. So my terrain is 20 meters square. Now. if I the point is hanging in the air about the centre of the terrain (say X = 11 Z = 11) above the surface I can easily tell which terrain grid cell the point lies above. I simply take the curr position of the point P (X=11 Z=11) and divide X by cell width (2meters) so I get 11/2=5.5 (ceiling = 6). So now I know it is above grid cell 6. The same applies for Z axis. In the end I know tha my point is above terrain grid cel X=6 & Z=6. Then it is quite easy for me to calculate which triangle exactly teh point lies above. As you can see this is very simple way and fast of selecting terrain triangle for collision. But what happens when there are triangles each of a differnt size? I cant apply this simple formula ie. divide X point position by vertex spacing (2 meteres) because in some places vertices may be very close to each other and in some they may be very far from each other. How do you solve this problem of selecting the correct triangle for collision. You cant just go through each triangle in the entire database. Please let me know. I am very curious!!!! Thank you very much!! [edited by - robert_s on November 5, 2003 10:13:35 PM]

Share this post


Link to post
Share on other sites
Hello,

I think there are more than one way to approach the problem. Most of the methods I know involves partation. This is what I did in my engine. First, divided your terrain into different blocks. Then, built up an AABB trees for all those blocks. When you do the collision detection, you can first go through the AABB tree and find the block that you are "in". After that, you can do a detail collision with each triangle inside that block to determine the collision point.

Actually, I think there is no easy way to solve this problem. If anyone know a faster way to do it, please let me know too!

Thanks!!

Nachi

Share this post


Link to post
Share on other sites
Split your mesh into some recursive, log-n structure (loose AABB trees, BSP trees, whatever). Keep splitting until each bin is about 20 triangles or less, or the bins become smaller than twice the size of your typical collider.

When testing, sweep your collider (or bounding volume of collider) through this tree, accumulating all triangles that are in the volumes which your collider intersects.

Test all the triangles you accumulate this way against the actual collision volume, using a primitive-primitive test.

There are some advanced ways of accelerating this a little more, like doing per-axis sweep-and-prune, but the above strategy should get you pretty far.

If you want a pre-made collision library which kicks butt, try OPCODE.

Share this post


Link to post
Share on other sites