Collision Detection 0.7 – Further Improvements
Patrick Lam | 13 March, 2009 | 20:38
After cutting back on unnecessary calculations such as the triangle-triangle tests on back-side triangles, I’ve decided to look at other places to cut back other unnecessary processes.
Inside my triangle-triangle test, for each test, I call the ray-triangle test 3 times, and then I see if any of them pass. Each test was for an edge on triangle A and test for intersection with triangle B. So instead of calling them all at once and check if any of them pass, I decided to call each of them one at a time and only call the others if the previous test failed.
So before, it was something like this
if (Test1 or Test2 or Test3) pass triangle-triangle test;
And now it’s
if (Test1) {pass triangle-triangle test;}
if (Not Pass tri-tri test) {if (Test2) {pass triangle-triangle test;}}
if (Not Pass tri-tri test) {if (Test3) {pass triangle-triangle test;}}
So if lucky enough, I could cut the processing for each triangle-triangle test up to about 2/3 of the time.
Including the previous improvement, only testing triangles that are in the front of the object, in theory, or at least what I believe, the triangle-triangle test can now perform up to 1/6 of the time it used to (in a very lucky situation that is).
Before, it would need the time to go through all the triangles in both objects, and then for each of those triangles, it would need to run all 3 ray-triangle test. Now, it’s half the triangles in both objects, and if lucky, 1 ray-triangle test. Unfortunately, most of the time the triangle-triangle test of both objects will fail since we are trying to find 1 triangle of object A which intersects 1 triangle of object B.
The next part of the improvement is to try and divide the whole 3D space into sections, and then group objects into each section. And when testing for collisions, we can narrow down the test to only objects in each section, instead of running through all the objects in the 3D space. But before implementing that, I will still try to improve the efficiency of the currently existing code. I’m pretty sure I have some pretty time consuming processes hidden somewhere in the code.
Looking forward to get this collision detection flying soon.
Referred blog: http://pplam3.blogspot.com/2009/03/more-blogs-and-release-07.html
Inside my triangle-triangle test, for each test, I call the ray-triangle test 3 times, and then I see if any of them pass. Each test was for an edge on triangle A and test for intersection with triangle B. So instead of calling them all at once and check if any of them pass, I decided to call each of them one at a time and only call the others if the previous test failed.
So before, it was something like this
if (Test1 or Test2 or Test3) pass triangle-triangle test;
And now it’s
if (Test1) {pass triangle-triangle test;}
if (Not Pass tri-tri test) {if (Test2) {pass triangle-triangle test;}}
if (Not Pass tri-tri test) {if (Test3) {pass triangle-triangle test;}}
So if lucky enough, I could cut the processing for each triangle-triangle test up to about 2/3 of the time.
Including the previous improvement, only testing triangles that are in the front of the object, in theory, or at least what I believe, the triangle-triangle test can now perform up to 1/6 of the time it used to (in a very lucky situation that is).
Before, it would need the time to go through all the triangles in both objects, and then for each of those triangles, it would need to run all 3 ray-triangle test. Now, it’s half the triangles in both objects, and if lucky, 1 ray-triangle test. Unfortunately, most of the time the triangle-triangle test of both objects will fail since we are trying to find 1 triangle of object A which intersects 1 triangle of object B.
The next part of the improvement is to try and divide the whole 3D space into sections, and then group objects into each section. And when testing for collisions, we can narrow down the test to only objects in each section, instead of running through all the objects in the 3D space. But before implementing that, I will still try to improve the efficiency of the currently existing code. I’m pretty sure I have some pretty time consuming processes hidden somewhere in the code.
Looking forward to get this collision detection flying soon.
Referred blog: http://pplam3.blogspot.com/2009/03/more-blogs-and-release-07.html
