Hi, What would be the best way to check if two boxes are intersection in anyway. Given this structure, struct box { float x1, y1, z1; float x2, y2, z2; } Would nice to have a function like bool IsIntersecting( box* b1, box* b2 ) Could anyone point me in the right direction? Thanks /Johan

Easy, Google for Axis-Aligned Bounding Boxes. Essentially, there is a collision if and only if the coordinates overlap for the three axes. There surely is a nice way to do these tests with ifs, but I can''t figure it out right now. Must get some sleep. Pseudo-code:

For x axis, check if the first x coordinate of the first box is between the two coordinates of the second box. Repeat for the second x coordinate of the first box. Then, repeat for second box vs first box...

Uh, check Google

Chédric

Hi,

Thanks you the quick answer.
But there could be some special cases where none of the given coordinates are in the other box, right?

Like if you have a long box going right through a big fat one.

Thanks
/Johan

Ripped from my GameObject class:


public boolean intersects(GameObject obj)
{
// Left edge
if (obj.getXCoord()+obj.getBase() < xCoord-base)
return false;

// Right edge
if (obj.getXCoord()-obj.getBase() > xCoord+base)
return false;

// Top edge
if (obj.getYCoord() < yCoord-height)
return false;

// Bottom edge
if (obj.getYCoord()-obj.getHeight() > yCoord)
return false;

// All edge tests passed, objects intersect
return true;
}


The nice thing being the early rejection. Remember to change the ordering to get the earliest rejection (eg if you''re mainly vertical scrolling etc. then switch the x and y tests).

Is there some kind of mathematical theory that can solve if a given volume is intersecting with another volume?

To check if any point possible of box1 is inside box2?

Thanks
/Johan

*GRWAHH !@^%#%&$#%!@%^!&*&$#^% Interal Server Error Ate Longer Post!*

What you need to do is test for intersection between A''s edges and B''s facets, between B''s edges and A''s facets, and between A''s and B''s edges.

http://astronomy.swin.edu.au/~pbourke/geometry/ has information on line-facet and line-line intersection tests.

"The Requested Information Is Unknown Or Classified" -Anonymous

quote:

---

Original post by JohanK
But there could be some special cases where none of the given coordinates are in the other box, right?

Like if you have a long box going right through a big fat one.

---

Not that I am aware. You are doing this one axis at a time. It doesn't matter if the box as a whole is fat or skinny, or if it can breakdance; if there is an overlap in 1D, one of the coordinates will necessarily be between the two of the other box.

Cédric

[EDIT] Extrarius, no, not if the box is axis-aligned.

[edited by - cedricl on August 23, 2002 10:42:56 AM]

What he means is this:

 _| |    ||_|    |Box going through wall really quickly.From one frame to the next:          _      |  | |      |  |_|  

Notice the wall is not in the box, yet it clearly has intersected between frames. To test, I believe you have to check if the line from one vertex of the box going from previous position to new position interesect the wall.
Would that result in too many tests?

[edited by - GBGames on August 23, 2002 10:47:31 AM]

[edited by - GBGames on August 23, 2002 10:47:57 AM]

cedricl: No, what he means is that the method you describe will fail on the case of an overlapping boxes where neither point is within the other. My method checked points against the bounding planes, and therefore for axis aligned boxes will always return the correct result.

GBGames: Thats usually the next problem that turns up. I find the best way to check that is to extend the bounding box depening on the speed and time elapsed over the last frame (therefore checking the space the object is trying to move though, not just the end result).

Your method is probably faster, but mine works too. When you check in 1D, there is no problem. There are two spans [A1...A2] and [B1...B2]

Case 1, no collision:

A1 ... A2 ... B1 ... B2

Case 2, A inside B

B1 ... A1 ... A2 ... B2

It works; A1 is in the span between B1 and B2

Case 2, one A inside B

B1 ... A1 ... B1 ... A2

It also works. As I said in my first post, there is a collision if and only if the spans of the three axes overlap.

It''s the same thing as you are doing, except that you rigthfully eliminate one of the tests because it isn''t necessary (left edge with left edge and right edge right edge).

Furthermore, in your code, may I comment that your "early rejection tests" aren''t as useful as you may think, since a good compiler shouldn''t evaluate all the expressions in an if statement if it already knows the outcome.

Cédric