Archived

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

Where's the catch?

This topic is 5779 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

OK, I''ve been thinking, I''m currently building my 3D collision detetion engine and I''ve thought about building an OBB tree... then I''ve though that when I''ll reach the end leaf in the Model-Model collision test I''ll do a Tri-Tri test for a 100% accuracy. so far so good. But... Building the OBB tree is a stinky job (with all of these Eigenvectors anf stuff I don''t realy know yet), plus, testing for intersection between two OBBs is a long operation (15 tests or something like that)... So, I''ve been thinking, instate of builiding an OBB tree, I''ll build a Bounding Spheres tree... Hello''va lot faster intersection test (Only one dot product, only one square root and only one point to transform by the world matrix)... since every triangle can be bounded by a circle, when I''ll reach the end-leaf I''ll do the Tri-Tri test (just like I''ve thought doing in my OBB tree), and again, I''ll get a 100% accuracy, with less calculations... Where''s the catch in my method? I ask this since everybody seems to be using OBB trees and not BS trees...

Share this post


Link to post
Share on other sites
Well for most shapes used in nowadays games, OBBs fit a lot tighter than spheres. But other than that, spheres are a very valid alternative.

BTW, a sphere-sphere collision test doesn''t need a square root.

Share this post


Link to post
Share on other sites
Well, since I''m finishing my coldet test with a tri-tri test, tightness doesn''t really matters right?

And to calc distance between 2 point in space you dont do:
sqrt((v1-v2)*(v1-v2))?

Share this post


Link to post
Share on other sites
the more "tightness" you have, the fewer times the computer will have to actually do those tri-tri tests, which will be faster.
and to test sphere-sphere collision, you can square the sum of the radii rather than square-root the other part:

sqrt((dX * dX) + (dY * dY) + (dZ * dZ)) <= r1 + r2
...
(dX * dX) + (dY * dY) + (dZ * dZ) <= (r1 + r2) * (r1 + r2)

the second one will be faster because sqare rooting is slow...

--- krez (krezisback@aol.com)

Share this post


Link to post
Share on other sites
but I''m only doing one tri-tri test. when I reach an end node.

plus, if the collision test between two spheres is faster then the OBB-OBB right so even if I have to make as twice as testing with a BS tree then I''ll have to do with an OBB tree, the differnce in the test time will still make the BS tree faster right? or I''m wrong?

btw, 10x for the BS-BS coldet func opt!

Share this post


Link to post
Share on other sites
Well the whole point of a tree is early rejection. If the bounding sphere/OBB surrounding the object does not collide with the bounding sphere/OBB surrounding the other object, then you stop testing, because you know that the objects are not colliding.

That tri-tri test you meantion should only get called when the object are actually colliding or are very close to colliding. The tighter the fit, the more chance on an early rejection, the less tri-tri collision detection is necessary.

But still, spheres are indeed a lot faster to test than OBBs. Maybe you could try a hybrid approach? Have one big sphere surrounding the entire object and build an OBB tree inside of this sphere.

Share this post


Link to post
Share on other sites
I''ve tought about doing so in order to speed up the coldet, but I still think that even if I''ll have to make more test with a sphere tree, the speed-up gained in the shere-sphere test will cover up the time loss in testing more shpers, and even still gain a speed-up comparing to obb trees...

The time spent on a single box-box test can be used for alot shpere-shpere tests... the speed-up is noticable even if I''ll have to make as twice as test as I have to do with a box tree...

or again, I''ve got something wrong here?

Share this post


Link to post
Share on other sites