collision detection with SAT and OBB
Author
I'm finishing up my collision detection system using OBB and SAT. Now it's time to start thinking about some optimizing, so I have som questions.
First, since these are polys are always boxes, can you skip the edge check? It seems to me that a plane orthogonal to an edge would always contain another face in this case.
Second, what's fastest, to multiply the transformation matrix of one box with the inverse of the other's and apply to the first box only or to apply each transformation matrix to each box? I guess what I'm really asking is wether multiplying matrices together is faster than transorming vertices.
Third, I'm wondering if it's worth the trouble to make some temporary vectors and such static or global to prevent them from being reallocated each function call?
Fourth, do you have any other tips? I bet there's a much more effective and simple algorithm out there that I haven't found :).
EDIT: It occured to me that perhaps this one should be in the math forum...
should be :)
ok, by SAT, you mean Separation Axis Theorem? So why are you using vertices? There should be no vertices involved, and no transformations.
Also, sometimes it's always not as efficient to do
if (this is true)
then
{ do simple maths; }
else
{ do more complicated maths; }
than to do
{ always do the complicated maths; }
since you have some branching, and some maths operations can be actually free (done concurrently). That's what the RAPID collision detection library do, just brute-force maths, and the code is clean and very fast. There's no need to complicate things for special cases if there is no need to (except for two coplanar triangles, where the test becomes totally different than from non-coplanar triangles).
to improve the SAT algorithm from it's raw state is basically going through each separation axis, see how it's constructed, and weed out the maths operations one by one.
Then you can gain a substantial amount, but it's quite tiresome, and it's been already done. If you look at the RAPID collision detection library, the code doing tri-box intersection tests and the code doing box-box intersection test is pretty much optimum. Optimising further from that would be a waste of time really.
When you allocate something on the stack, you don't actually allocate anything at all. It's all free. The stack pointer just gets pushed, and it's much faster to play with the cache than with some global data store on the heap. The only concern about allocating data on the stack is the amount you need.
There is no advantage of using data on the heap (global variables). This is usually done for hacks, large amount of data that won't fit on the stack (which should be dynamially allocated anyway), and sharing stuff around (which should be done other ways).
About the transforms, you can transform a box into the other box's object space, which can give some neat improvements since one box will be axis aligned and at the origin. Inverse transforms like that can be very fast indeed. I guess you can do that if you are prepared to take the OBB SAT to the next level. Someone like Charles B. would probably advocate such things, but he is an inflinching optimisation hardcore. Anything less than 110% efficiency won't do :)
So, here are my arguments anyway.
ok, by SAT, you mean Separation Axis Theorem? So why are you using vertices? There should be no vertices involved, and no transformations.
Also, sometimes it's always not as efficient to do
if (this is true)
then
{ do simple maths; }
else
{ do more complicated maths; }
than to do
{ always do the complicated maths; }
since you have some branching, and some maths operations can be actually free (done concurrently). That's what the RAPID collision detection library do, just brute-force maths, and the code is clean and very fast. There's no need to complicate things for special cases if there is no need to (except for two coplanar triangles, where the test becomes totally different than from non-coplanar triangles).
to improve the SAT algorithm from it's raw state is basically going through each separation axis, see how it's constructed, and weed out the maths operations one by one.
Then you can gain a substantial amount, but it's quite tiresome, and it's been already done. If you look at the RAPID collision detection library, the code doing tri-box intersection tests and the code doing box-box intersection test is pretty much optimum. Optimising further from that would be a waste of time really.
When you allocate something on the stack, you don't actually allocate anything at all. It's all free. The stack pointer just gets pushed, and it's much faster to play with the cache than with some global data store on the heap. The only concern about allocating data on the stack is the amount you need.
There is no advantage of using data on the heap (global variables). This is usually done for hacks, large amount of data that won't fit on the stack (which should be dynamially allocated anyway), and sharing stuff around (which should be done other ways).
About the transforms, you can transform a box into the other box's object space, which can give some neat improvements since one box will be axis aligned and at the origin. Inverse transforms like that can be very fast indeed. I guess you can do that if you are prepared to take the OBB SAT to the next level. Someone like Charles B. would probably advocate such things, but he is an inflinching optimisation hardcore. Anything less than 110% efficiency won't do :)
So, here are my arguments anyway.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
