The piece of code you posted above looks like the old SAT code you used because it is taken from the old SAT code you used. xD
Everything else was written by me, though.
It would be very nice of you to tell me what could be improved. :D
SAT Trouble
First off, it would be nice to split the code into function blocks.
in the function interval_overlap() the signs of d1 and d2 can be used directly, thus avoiding the problems I pointed out in my previous post.
pushing it further, you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end.
there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length.
You can also track the push vector as you go along.
void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){ min = vec_dot_product(axis, a.edge[0].world); max = min; for(j = 1; j < a.edge_num; j++) { temp = vec_dot_product(axis, a.edge[j].world); if(temp < min) { min = temp; } if(temp > max) { max = temp; } }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){ if(min0 > max1 || min1 > max0) return FALSE; // Found a separating axis. Bodies can't intersecting. d0 = max0 - min1; d1 = max1 - min0; if(d0 < d1) depth = d0; else depth = d1; return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, float& depth){ float mina, maxa; float minb, maxb; body_interval_on_axis(axis, a, mina, maxa); body_interval_on_axis(axis, b, minb, maxb); return interval_overlap(mina, maxa, minb, maxb, depth);}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, float depth[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; vec_t offset; temp = depth[0]; j = 0; for(i = 1; i < total_edge_num; i++) if(depth < temp) { temp = depth; j = i; } if(j < a.edge_num) { push.x = depth[j] * a.normal[j].x; push.y = depth[j] * a.normal[j].y; } else { k = j - a.edge_num; push.x = depth[j] * b.normal[k].x; push.y = depth[j] * b.normal[k].y; } vec_set(offset, a.pos.x - b.pos.x, a.pos.y - b.pos.y); // Check if the push vector is pointing in the right direction: if(vec_dot_product(offset, push) >= 0.0) vec_scale(push, -1.0, -1.0); // It actually made it through all the tests, the bodies must be intersecting. return TRUE;}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, k, total_edge_num = a.edge_num + b.edge_num; vec_t axis; float depth[total_edge_num]; if(a.validity != 1 || b.validity != 1) return 2; k = 0; // Project A and B on the axes of A: for(i = 0; i < a.edge_num; i++) { axis = a.normal; if (!body_intersection_test_on_axis(axis, a, b, depth[k])) return FALSE; k++; } // Project A and B on the axes of B: for(i = 0; i < b.edge_num; i++) { axis = b.normal; if (!body_intersection_test_on_axis(axis, a, b, depth[k])) return FALSE; k++; } return body_intersection_push_vector(a, b, push, depth);}in the function interval_overlap() the signs of d1 and d2 can be used directly, thus avoiding the problems I pointed out in my previous post.
bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){ if(min0 > max1 || min1 > max0) return FALSE; // Found a separating axis. Bodies can't intersecting. d0 = max0 - min1; d1 = max1 - min0; if(d0 < d1) depth = -d0; // sign! else depth = d1; return TRUE;}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, float depth[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; temp = depth[0]; j = 0; for(i = 1; i < total_edge_num; i++) if(fabs(depth) < fabs(temp)) // depth values aren't always positive! { temp = depth; j = i; } if(j < a.edge_num) { push.x = depth[j] * a.normal[j].x; push.y = depth[j] * a.normal[j].y; } else { k = j - a.edge_num; push.x = depth[j] * b.normal[k].x; push.y = depth[j] * b.normal[k].y; } // It actually made it through all the tests, the bodies must be intersecting. return TRUE;}pushing it further, you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end.
void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){ min = vec_dot_product(axis, a.edge[0].world); max = min; for(j = 1; j < a.edge_num; j++) { temp = vec_dot_product(axis, a.edge[j].world); if(temp < min) { min = temp; } if(temp > max) { max = temp; } }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){ if(min0 > max1 || min1 > max0) return FALSE; // Found a separating axis. Bodies can't intersecting. d0 = max0 - min1; d1 = max1 - min0; if(d0 < d1) depth = -d0; else depth = d1; return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, vec_t& axis_push){ float depth; float mina, maxa; float minb, maxb; body_interval_on_axis(axis, a, mina, maxa); body_interval_on_axis(axis, b, minb, maxb); if (!interval_overlap(mina, maxa, minb, maxb, depth)) return FALSE; vec_mul(axis_push, axis, depth); return TRUE;}bool body_intersection_push_vector(body_t a, body_t b, vec_t &push, vec_t axis_push[]){ int i, j, total_edge_num = a.edge_num + b.edge_num; float push_length_squared; push = axis_push[0]; push_length_squared = vec_dot(push, push); for(i = 1; i < total_edge_num; i++) { float axis_push_length_squared; axis_push_length_squared = vec_dot(axis_push, axis_push); if(axis_push_length_squared < push_length_squared) { push = axis_push; push_length_squared = vec_dot(push, push); } // It actually made it through all the tests, the bodies must be intersecting. return TRUE;}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, k, total_edge_num = a.edge_num + b.edge_num; vec_t axis; vec_t axis_push[total_edge_num]; if(a.validity != 1 || b.validity != 1) return 2; k = 0; // Project A and B on the axes of A: for(i = 0; i < a.edge_num; i++) { axis = a.normal; if (!body_intersection_test_on_axis(axis, a, b, axis_push[k])) return FALSE; k++; } // Project A and B on the axes of B: for(i = 0; i < b.edge_num; i++) { axis = b.normal; if (!body_intersection_test_on_axis(axis, a, b, axis_push[k])) return FALSE; k++; } return body_intersection_push_vector(a, b, push, axis_push);}there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length.
You can also track the push vector as you go along.
void body_interval_on_axis(vec_t axis, body_t a, float& min, float max){ min = vec_dot_product(axis, a.edge[0].world); max = min; for(j = 1; j < a.edge_num; j++) { temp = vec_dot_product(axis, a.edge[j].world); if(temp < min) { min = temp; } if(temp > max) { max = temp; } }}bool interval_overlap(float min0, float max0, float min1, float max1, float& depth){ if(min0 > max1 || min1 > max0) return FALSE; // Found a separating axis. Bodies can't intersecting. d0 = max0 - min1; d1 = max1 - min0; if(d0 < d1) depth = -d0; else depth = d1; return TRUE;}bool body_intersection_test_update_push(vec_t axis, float depth, vec_t& push, float& push_length_squared){ vec_t axis_push; float axis_push_length_squared; float axis_length_squared; axis_length_squared = vec_dot(axis, axis); vec_mul(axis_push, axis, depth / axis_length_squared); axis_push_length_squared = vec_dot(axis_push, axis_push); if (axis_push_length_squared < push_length_squared || push_length_squared < 0.0f) { push_length_squared = axis_push_length_squared; push = axis_push; } return TRUE;}bool body_intersection_test_on_axis(vec_t axis, body_t a, body_t b, vec_t& push, float& push_length_squared){ float depth; float mina, maxa; float minb, maxb; body_interval_on_axis(axis, a, mina, maxa); body_interval_on_axis(axis, b, minb, maxb); if (!interval_overlap(mina, maxa, minb, maxb, depth)) return FALSE; return body_intersection_test_update_push(axis, depth, push, push_length_squared);}bool body_intersection_test(body_t a, body_t b, vec_t &push){ int i, ip1; vec_t edge; vec_t axis; float push_length_squared = -1.0f; // initiaise to impossible value if(a.validity != 1 || b.validity != 1) return 2; // Project A and B on the axes of A: i = a.edge_num-1; for(ip1 = 0; ip1 < a.edge_num; i = ip1, ip1++) { vec_sub(edge, a.edge[ip1], a.edge); axis = vec_t(-edge.y, edge.x); if (!body_intersection_test_on_axis(axis, a, b, push, push_length_squared)) return FALSE; } i = b.edge_num-1; for(ip1 = 0; ip1 < b.edge_num; i = ip1, ip1++) { vec_sub(edge, b.edge[ip1], b.edge); axis = vec_t(-edge.y, edge.x); if (!body_intersection_test_on_axis(axis, a, b, push, push_length_squared)) return FALSE; } return TRUE;}
Author
"in the function interval_overlap() the signs of d1 and d2 can be used directly"
So no need to do the dot product to check the direction of the MTD?
Ok, i'll fix that.
"you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end."
So no need to calculate and save all those depth values?
Sounds pretty good but I don't really get it...
"there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length."
But if i'll do so, i'll have to take square roots in every MTD and rebound calculation, right?
In that case, I rather waste a few bytes on the normals and rotate them along with the object using precalculated sines and cosines.
After all, 3D computer games store thousands of them for the model illumination and it works fine.
So no need to do the dot product to check the direction of the MTD?
Ok, i'll fix that.
"you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end."
So no need to calculate and save all those depth values?
Sounds pretty good but I don't really get it...
"there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length."
But if i'll do so, i'll have to take square roots in every MTD and rebound calculation, right?
In that case, I rather waste a few bytes on the normals and rotate them along with the object using precalculated sines and cosines.
After all, 3D computer games store thousands of them for the model illumination and it works fine.
Quote:Original post by mrbig
"in the function interval_overlap() the signs of d1 and d2 can be used directly"
So no need to do the dot product to check the direction of the MTD?
Ok, i'll fix that.
but when doing comparisons of numbers to get the smallest, remember to use fabs().
Quote:Original post by mrbig
"you don't have to use depth values, you can use push vectors for each axis, and compare their length sqaured at the end."
So no need to calculate and save all those depth values?
Sounds pretty good but I don't really get it...
The depth you get for each separation axis, really is a way to tell by how much the intervals overlap, and by how much you should push an object so the intervals along that axis stop overlapping. In the end, it is equivalent to pushing the objects by (axis * depth), for a given separation axis.
so, instead of storing depth values for each axis, you store (depth * axis) as a vector. And when you try to find the smallest of the push vectors, you take the one which as the smallest length squared (which is a simple dot product).
Why do that? Well, it would have prevented you having your particular bug in the first place. Secondly, it has to do with improving the algo and avoiding allocating a cache to store the vectors. OK, not big deal, but that's the way I'd improve things, since you asked. This becomes particularly handy when moving to swept tests, then you'd have to cache more data, and it gets messy. First, the algo has to be simple and working. Then after that, if you need full optimisations, you can think of doing that caching and comparisons at the end. If the algo works and it's nice and tidy first, it's a lot easier to debug (by for example, comparing values between optimised and non-optimised).
Quote:Original post by mrbig
"there is no need to keep normals of polygon edges. You can use polygon edges directly, unormalised (moot point). Although if you do that, you have to remember that depth values are all scaled by the corresponding axis length."
But if i'll do so, i'll have to take square roots in every MTD and rebound calculation, right?
In that case, I rather waste a few bytes on the normals and rotate them along with the object using precalculated sines and cosines.
After all, 3D computer games store thousands of them for the model illumination and it works fine.
you dont compare lengths, but squared lengths, which is just a dot product (where the length is a square root of a dot product). Again, it's not necessary, but it is neater in my opinion, and don't require precalculations and preconceptions for objects (the less the better in my experience, if you can avoid them). It's nice to know the algorithm can work efficiently that way too (so it can be extended to 3D for example).
Author
I'm not trying to argue with you, really, but I just don't get it...
You said:
"instead of storing depth values for each axis, you store (depth * axis) as a vector. And when you try to find the smallest of the push vectors, you take the one which as the smallest length squared (which is a simple dot product). "
So instead of doing two subtractions for every axis, saving the result in a float array with [total_edge_num] elements and comparing them, I can calculate depth * axis for every axis, store it in a vector array with [total_edge_num] elements, (which is 2x bigger 'cause vec_t consists of two floats) and than compare their squared lenghts, which is another dot product per axis.
Am I missing something?
I hope i'm not starting to be annoying...
I could just copy-paste all that optimized code you wrote there, but that's not my style. I don't like using something I don't understand.
[OFF TOPIC]
Hey, take a look!
Somebody rated me one point up!
Wow, I must have been very helpful... [rolleyes]
You said:
"instead of storing depth values for each axis, you store (depth * axis) as a vector. And when you try to find the smallest of the push vectors, you take the one which as the smallest length squared (which is a simple dot product). "
So instead of doing two subtractions for every axis, saving the result in a float array with [total_edge_num] elements and comparing them, I can calculate depth * axis for every axis, store it in a vector array with [total_edge_num] elements, (which is 2x bigger 'cause vec_t consists of two floats) and than compare their squared lenghts, which is another dot product per axis.
Am I missing something?
I hope i'm not starting to be annoying...
I could just copy-paste all that optimized code you wrote there, but that's not my style. I don't like using something I don't understand.
[OFF TOPIC]
Hey, take a look!
Somebody rated me one point up!
Wow, I must have been very helpful... [rolleyes]
It's not a problem with the code, or efficiency, it's the way I work. OK, the code here is not as efficient, but, if you get curious about expanding the algo further, caching would make it harder to explain, because there will be so many other things to track, and it will turn into a mess.
first of, the memory requirement here is irrelevant. It's all allocated in the stack, and freed after the algo exits. This part of the program is only a step towards freeing you from having to cache stuff in the first place. Instead, you do just-in-time calculations. That also frees you from allocating stuff at run time, either on the heap (very bad), of on the stack (not so bad).
Again, I do not want to use normals, because of the preprocessing and extra dependencies involved in that case (i.e. a need to keep normals for edges, extra data, extra things to worry about). I prefer low level stuff, which works with the minimum amount of inputs (just a loop of vertices). That forces you to use extra dot products, but the cost is negligeable. The most costly thing on processors aren't ops, but jumps and dereferencing / cache misses.
Anyway, I don't care so much about efficiency when presenting stuff. Of course it's gonna be slower than caching data at the end of the algo, but that kind of methodology is more about optimisations than linked to the algorithm, and I'm not interested in optimisations. I want to present a complete thing, which may be slower, but that you can shape into something fast in your own time (like add normals to edges, add large caches, dont do just-in-time, but process the data only when a collision occurs, ect...). There are better pre-processing to be done anyway (like becuase edges are sometimes parallel to each other, you don't need to test all edges).
Don't worry about it then, ignore the posts if it confuses you. I should have never written the code with cached values in the first place anyway.
As long as you understand the process (minimise the MTD using just-in-time calculations, compare squared lengths, no cache), that's enough, even if you thing it's irrelevant and useless, then if you decide to jump into time-based algos ansd read that stuff, you'll see where this is going.
Quote:
"So instead of doing two subtractions for every axis, saving the result in a float array with [total_edge_num] elements and comparing them, I can calculate depth * axis for every axis, store it in a vector array with [total_edge_num] elements, (which is 2x bigger 'cause vec_t consists of two floats) and than compare their squared lenghts, which is another dot product per axis."
first of, the memory requirement here is irrelevant. It's all allocated in the stack, and freed after the algo exits. This part of the program is only a step towards freeing you from having to cache stuff in the first place. Instead, you do just-in-time calculations. That also frees you from allocating stuff at run time, either on the heap (very bad), of on the stack (not so bad).
Again, I do not want to use normals, because of the preprocessing and extra dependencies involved in that case (i.e. a need to keep normals for edges, extra data, extra things to worry about). I prefer low level stuff, which works with the minimum amount of inputs (just a loop of vertices). That forces you to use extra dot products, but the cost is negligeable. The most costly thing on processors aren't ops, but jumps and dereferencing / cache misses.
Anyway, I don't care so much about efficiency when presenting stuff. Of course it's gonna be slower than caching data at the end of the algo, but that kind of methodology is more about optimisations than linked to the algorithm, and I'm not interested in optimisations. I want to present a complete thing, which may be slower, but that you can shape into something fast in your own time (like add normals to edges, add large caches, dont do just-in-time, but process the data only when a collision occurs, ect...). There are better pre-processing to be done anyway (like becuase edges are sometimes parallel to each other, you don't need to test all edges).
Don't worry about it then, ignore the posts if it confuses you. I should have never written the code with cached values in the first place anyway.
As long as you understand the process (minimise the MTD using just-in-time calculations, compare squared lengths, no cache), that's enough, even if you thing it's irrelevant and useless, then if you decide to jump into time-based algos ansd read that stuff, you'll see where this is going.
Author
Ok.
Just one more thing:
Can you please post an example code for me on how to find the contact point of two polygons?
I know you already wrote about it in your tutorial, but if you're not too busy, can you please rewrite it in a way it would fit the rest of my SAT code?
I would figure it out myself, but i've wasted so much time figuring out collision detection and response, and I got so many other things to add to my engine and I could really use some more help.
Thanks for all your help. :)
Just one more thing:
Can you please post an example code for me on how to find the contact point of two polygons?
I know you already wrote about it in your tutorial, but if you're not too busy, can you please rewrite it in a way it would fit the rest of my SAT code?
I would figure it out myself, but i've wasted so much time figuring out collision detection and response, and I got so many other things to add to my engine and I could really use some more help.
Thanks for all your help. :)
findint contact points is separate from the SAT.
You basically take the MTD vector (Push vector) as your collision normal, and find the support features (edge or vertex, for 2D polygons) along that normal on both polys.
depending on edge-edge, point-edge pairs, you just work out the intersection point quite easily.
finding the pairs (p0, p1) and (q0, q1) is easy, and it's just careful coding.
[Edited by - oliii on October 26, 2005 7:16:35 PM]
You basically take the MTD vector (Push vector) as your collision normal, and find the support features (edge or vertex, for 2D polygons) along that normal on both polys.
depending on edge-edge, point-edge pairs, you just work out the intersection point quite easily.
\ p0 / ^ +---------*-----------+ | | \ | / | | PUSH | \|/ | | | * | | | p1 | | | | p0 q0 | +------+-----------------+ | \ | / | \ | p1 / q1 | \ +---------------/-+-------+ \ / \ / \ / finding the pairs (p0, p1) and (q0, q1) is easy, and it's just careful coding.
[Edited by - oliii on October 26, 2005 7:16:35 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
