Collision detection on NON-UNIFORM terrain meshes
Author
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]
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
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
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.
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.
Cool. What technique did you end up using?
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
