Sorry it took me a while to reply. It took some time to read all that and implementing it.
oliii, thank you very much, that second link and your explanation were great . I implemented the code from that powerpoint and part of it works great, another part not so great.
The problem seems to be the edge SATs, everytime the check gets past the face normal checks, it automatically returns a collision even if there isn't any.
What's strange is that my edge directions and face normals are correct, I'm drawing them in my scene and they are where they're supposed to be.
Pics, blue lines means no collision, red cubes means collision is detected.
Purple lines are the edge directions, the yellow lines the face normals.
Still good: it doesn't check the edges here
Collision detected: it goes through the full test here
This is my code:
Intersect test: straight from the powerpoint presentation, just ported to C#/XNA
Updating my edge directions: I keep an EdgeList, which holds edges by storing the vertex indexes they have in the vertex array. So basically, I look for the 3 edges that have vertex 0 as a point and calculate the direction from there, then add that direction to an array which is the one I use in the TestIntersection function.
Is there something I did wrong? Is there an error in the intersect function? Because my directions and normals seem correct judging from drawing them in the scene.
General OBB question
I must say, I fail to see a problem there. I'm not too sure about the edge calculations, but looking at the pictures, they look all right.
As for the edge directions, for a box, the edge directions are basically the same as the face directions. So you can try and replace the edges with faces in the cross product.
You also have to consider the case of degenerate edges, i.e. edges that are parallel to each other. That means the cross product is close to zero, and you can run into floating point imprecisions that lead to a test always failing or always returning true.
you can use a tolerance to make sure that doesn't happen.
const float tolerance = 1.0E-6f;
if (max1 < min2 - tolerance || max2 < min1 - tolerance) return false;
another thing to test is to use unit tests. Have the box configured in a predictable way, and check the results. I'd start with two unit box, axis aligned, then rotate one around the y axis 45 degrees, and so on.
EDIT : hmmm the pictures don't make sense. Wether you check the edges or not, the test should return false as the boxes are clearly separated along the face normal going along the negative X axis. Unless it's a perspective effect.
As for the edge directions, for a box, the edge directions are basically the same as the face directions. So you can try and replace the edges with faces in the cross product.
You also have to consider the case of degenerate edges, i.e. edges that are parallel to each other. That means the cross product is close to zero, and you can run into floating point imprecisions that lead to a test always failing or always returning true.
you can use a tolerance to make sure that doesn't happen.
const float tolerance = 1.0E-6f;
if (max1 < min2 - tolerance || max2 < min1 - tolerance) return false;
another thing to test is to use unit tests. Have the box configured in a predictable way, and check the results. I'd start with two unit box, axis aligned, then rotate one around the y axis 45 degrees, and so on.
EDIT : hmmm the pictures don't make sense. Wether you check the edges or not, the test should return false as the boxes are clearly separated along the face normal going along the negative X axis. Unless it's a perspective effect.
Author
It's not a perspective effect.
I tried to add tolerance but it didn't change anything. I also tried to do a 12 + 12 + 12x12 check for all edges and normals but again, nothing changed.
I tried replacing the edgedirections in the calculation by the face normals, all edge checks, all normals checks, combinations with that, and it all gives the same result.
When both are axis alligned, it works. When 1 is rotated around the Y axis, it works. When both are rotated around the Y axis, it's inaccurate but the gap between them has to be pretty small. When 1 is rotated around the X and Y axis, it's terribly inaccurate and there can be a huge gap between them and it still detects collision.
1 rotated around Y
1 rotated around Y, collision
1 rotated around both X and Y
1 rotated around both X and Y, collision
Both rotated around Y
Both rotated around Y, collision
I tried to add tolerance but it didn't change anything. I also tried to do a 12 + 12 + 12x12 check for all edges and normals but again, nothing changed.
I tried replacing the edgedirections in the calculation by the face normals, all edge checks, all normals checks, combinations with that, and it all gives the same result.
When both are axis alligned, it works. When 1 is rotated around the Y axis, it works. When both are rotated around the Y axis, it's inaccurate but the gap between them has to be pretty small. When 1 is rotated around the X and Y axis, it's terribly inaccurate and there can be a huge gap between them and it still detects collision.
1 rotated around Y
1 rotated around Y, collision
1 rotated around both X and Y
1 rotated around both X and Y, collision
Both rotated around Y
Both rotated around Y, collision
this is mad. I can't find anything wrong in the code example. The last example should return no collision even before doing the edge-edge tests.
Clutching at straws here, but did you clear the boxes' collided flag before calling the routine.
Basically, you need to check the numbers, single stepping through the code... Because that is the SAT, and the SAT works!
Clutching at straws here, but did you clear the boxes' collided flag before calling the routine.
Basically, you need to check the numbers, single stepping through the code... Because that is the SAT, and the SAT works!
Try normalizing the axis in TestIntersection for the edge code before the call to GetInterval.
Edit: Actually I think that shouldn't matter unless you want an accurate penetration depth, but shouldn't hurt to try.
Edit: Actually I think that shouldn't matter unless you want an accurate penetration depth, but shouldn't hurt to try.
Author
I'm an idiot...
I found the problem. I'm storing the 3 normals and 3 edge directions in a struct that contains 2 arrays. When it has to update the normals and directions, it adds the updated values to that struct, but if the arrays are already filled, it doesn't do anything. So basically, the calculation was correct, it draws them correctly but they didn't get stored so the checks kept using the original normals and directions with the updated vertex intervals.
Now I just need to expand it a bit so it returns the difference and I can push one back.
But first I think I'm gonna go hate myself for a while.
Thank you so much everyone, I couldn't have done it without your excellent links and explanations.
I found the problem. I'm storing the 3 normals and 3 edge directions in a struct that contains 2 arrays. When it has to update the normals and directions, it adds the updated values to that struct, but if the arrays are already filled, it doesn't do anything. So basically, the calculation was correct, it draws them correctly but they didn't get stored so the checks kept using the original normals and directions with the updated vertex intervals.
Now I just need to expand it a bit so it returns the difference and I can push one back.
But first I think I'm gonna go hate myself for a while.
Thank you so much everyone, I couldn't have done it without your excellent links and explanations.
no worries. Calculating the separation vector (aka MTD, push vector...) can be extracted from the SAT as well, without normalisations.
Author
I really hate bothering you even more than I already have but you seem so experienced in this.
I can barely find any info on getting the push vector. The one I did find requires the distance between the 2 centerpoints, which I don't have.
I tried doing an extra check using my movement direction axis and getting those intervals but the results weren't accurate at all.
Any chance you have some wisdom to share on this?
Thanks in advance.
I can barely find any info on getting the push vector. The one I did find requires the distance between the 2 centerpoints, which I don't have.
I tried doing an extra check using my movement direction axis and getting those intervals but the results weren't accurate at all.
Any chance you have some wisdom to share on this?
Thanks in advance.
for each axis you check, you have
- axis direction
- min, max of box1
- min, max of box2
the min-max values will tell you how much the objects intersect along the axis.
examples :
among all the 15 push vectors for each axes, you take the one that gives you the smallest length (the minimum translation distance, or MTD).
[Edited by - oliii on June 4, 2009 11:24:38 AM]
- axis direction
- min, max of box1
- min, max of box2
the min-max values will tell you how much the objects intersect along the axis.
examples :
Quote:mina maxa---------|--------------------|------------------ minb maxb----------------------|--------------------|-------- push |-------> mina maxa--------------------|--------------------|------------------ minb maxb----|--------------------|------------------ push <----| mina maxa---------|---------------------------|------------------ minb maxb-------------------|------------|------------------ push |----------------->
among all the 15 push vectors for each axes, you take the one that gives you the smallest length (the minimum translation distance, or MTD).
Quote:bool TestAxisIntersection(const Vector& axis, const CollisionBox& a, const CollisionBox& b, Vector& mtd, float& mtd2){ // compute intervals float mina, maxa; float minb, maxb; GetInterval(a, axis, mina, maxa); GetInterval(b, axis, minb, maxb); // compute the two possible interval intersections float tolerance = 1.0E-8f; float d0 = maxb - mina; float d1 = maxa - minb; // intervals don't intersect // therefore the box dont intersect if(d0 < tolerance || d1 < tolerance) return false; // minimum intersection between the two intervals float d = (d0 < d1)? -d0 : d1; // length of axis, squared float axis2 = axis.DotProduct(axis); // push vector along axis (normalised). Vector push = axis * (d / axis2); float push2 = push.DotProduct(push); // length squared // in the push vector along axis the minimum among all push vectors // or we haven't computed a push vector yet, use this // as our best candidate. if(mtd2 < 0.0f || push2 < mtd2) { mtd = push; mtd2 = push2; } // boxes intersected along axis. return true;}bool TestIntersection(const CollisionBox& a, const CollisionBox& b, Vector& mtd){ // length of mtd (push vector), squared. initialised to impossible value. float mtd2 = -1.0f; // reset push vector to zero. mtd = Vector(0, 0, 0); for(int i = 0; i < 3; i ++) { if(!TestAxisIntersection(a.QuadDir,a, b, mtd, mtd2)) return false; } //...... // ect //......}
[Edited by - oliii on June 4, 2009 11:24:38 AM]
Author
Thank you so much, it works great.
Although, when a collision is detected, it looks for the shortest vector to get out of the overlap. I want it so that it gets pushed back in the oposite direction as my initial movement.
I tried this:
It works most of the time but not always so I'm guessing this probably isn't the right method.
Although, when a collision is detected, it looks for the shortest vector to get out of the overlap. I want it so that it gets pushed back in the oposite direction as my initial movement.
I tried this:
public bool TestIntersection(CollisionBox cbox1, CollisionBox cbox2, ref Vector3 mtd) { // length of mtd (push vector), squared. initialised to impossible value. float mtd2 = -1.0f; // reset push vector to zero. mtd = new Vector3(0, 0, 0); // example of te movement of box1 Vector3 dir = new Vector3(1,0,0); Vector3 x; if (!TestAxisIntersection(ref dir,ref cbox1, ref cbox2,ref mtd, ref mtd2)) return false; x = mtd; //... all the checks float length = (x.X + x.Y + x.Z) / 3; x = Vector3.Multiply(dir, length); mtd = x; cbox1.Collides = true; cbox2.Collides = true; return true;It works most of the time but not always so I'm guessing this probably isn't the right method.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
