Optimise rect intersection

SDL Development
1

Hi,

I was just looking at the rect intersection test and thought it seemed
like it was doing a bit too much work.

Can somebody check the patch I’ve attached, I believe it does the same
thing and is more efficient.

The theory is that if (A.topleft < B.bottomright and A.bottomright >
B.topleft) then they must be overlapping. This needs less tests than the
current version.

The #define lines are to provide a similar readability to the old
version without the overhead of variables (as each thing is referenced
only once).

Thanks,
Sam Bull–
E-Mail sent with anti-spam site TrashMail.net!
Free disposable email addresses: http://www.trashmail.net
-------------- next part --------------
A non-text attachment was scrubbed…
Name: intersection.patch
Type: application/octet-stream
Size: 1483 bytes
Desc: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121021/5f3bcef2/attachment.obj

2

It looks as though the patch only tests for one case of intersection (where A is
“northwest” of B), but misses all other cases (A contains B, A and B share a
colinear edge, A and B are identical, A is southeast of B, etc.), plus it won’t
pass this quick test:

SDL_HasIntersection(A,B) == SDL_HasIntersection(B,A)

right?On 10/21/2012 03:35 PM, fox_oodmlo wrote:

Hi,

I was just looking at the rect intersection test and thought it seemed
like it was doing a bit too much work.

Can somebody check the patch I’ve attached, I believe it does the same
thing and is more efficient.

The theory is that if (A.topleft < B.bottomright and A.bottomright >
B.topleft) then they must be overlapping. This needs less tests than the
current version.

The #define lines are to provide a similar readability to the old
version without the overhead of variables (as each thing is referenced
only once).

Thanks,
Sam Bull

SDL mailing list
SDL at lists.libsdl.org
http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

3

Hi, shouldn’t be the “Seperating Axis Theorem” the best solution for
this, since SDL_Rects are AABBs?

CheersAm 22.10.2012 00:06, schrieb John:

It looks as though the patch only tests for one case of intersection
(where A is “northwest” of B), but misses all other cases (A contains
B, A and B share a colinear edge, A and B are identical, A is
southeast of B, etc.), plus it won’t pass this quick test:

SDL_HasIntersection(A,B) == SDL_HasIntersection(B,A)

right?

On 10/21/2012 03:35 PM, fox_oodmlo wrote:

Hi,

I was just looking at the rect intersection test and thought it seemed
like it was doing a bit too much work.

Can somebody check the patch I’ve attached, I believe it does the same
thing and is more efficient.

The theory is that if (A.topleft < B.bottomright and A.bottomright >
B.topleft) then they must be overlapping. This needs less tests than the
current version.

The #define lines are to provide a similar readability to the old
version without the overhead of variables (as each thing is referenced
only once).

Thanks,
Sam Bull

SDL mailing list
SDL at lists.libsdl.org
http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

SDL mailing list
SDL at lists.libsdl.org
http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

4

It looks as though the patch only tests for one case of intersection (where A is
“northwest” of B), but misses all other cases (A contains B, A and B share a
colinear edge, A and B are identical, A is southeast of B, etc.),

It should pass all these tests. If A contains B, then A.topleft <
B.bottomright and A.bottomright > B.topleft. The same is true with the
other conditions.

plus it won’t
pass this quick test:

SDL_HasIntersection(A,B) == SDL_HasIntersection(B,A)

right?

No, it makes no difference which way round you test. It will succeed in
that test.

I’ve attached an image to demonstrate the test. Given the black
rectangle, A, testing against any of the red rectangles, B.

“If A.topleft < B.bottomright” translates to any of the black corners
labelled ‘1’ being anywhere in the blue quadrant.
“and A.bottomright > B.topleft” translates to any of the black corners
labelled ‘2’ being anywhere in the green quadrant.

If these two tests are true, then they must be intersecting. If they are
not both true, then there is no way they are intersecting.On Sun, 2012-10-21 at 18:06 -0400, John wrote:

On Mon, 2012-10-22 at 09:38 +0200, Tobias Leich wrote:

Hi, shouldn’t be the “Seperating Axis Theorem” the best solution for
this, since SDL_Rects are AABBs?

That seems like an overly complex method for simple AABB to AABB
collision detection. SAT is there for collision between more complex
shapes.

-------------- next part --------------
A non-text attachment was scrubbed…
Name: collide.png
Type: image/png
Size: 4526 bytes
Desc: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121022/6ae56746/attachment-0001.png
-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121022/6ae56746/attachment-0001.pgp

5

What if the two rects have the same dimensions and position? Your test
would fail.

For SAT, I am thinking of the following:

/////////////////////////////////////////////////
If( rect1.bottom < rect2.top ) {
return NO_COLLISION;
}
elseif( rect1.top > rect2.bottom ) {
return NO_COLLISION;
}
elseif( rect1.right < rect2.left ) {
return NO_COLLISION;
}
elseif( rect1.left > rect2.right ) {
return NO_COLLISION;
}

return COLLISION;
/////////////////////////////////////////////////

Thats not that heavy, isnt it?

Of course for the .bottom and .right you have to do a calculation, but
really, worst case is to have 4 additions and 4 condition checks.

Cheers.

It looks as though the patch only tests for one case of intersection
(where A is
“northwest” of B), but misses all other cases (A contains B, A and B
share aAm 22.10.2012 18:36, schrieb Sam Bull:
On Sun, 2012-10-21 at 18:06 -0400, John wrote:
colinear edge, A and B are identical, A is southeast of B, etc.),

It should pass all these tests. If A contains B, then A.topleft <
B.bottomright and A.bottomright > B.topleft. The same is true with the
other conditions.

plus it won’t
pass this quick test:

SDL_HasIntersection(A,B) == SDL_HasIntersection(B,A)

right?

No, it makes no difference which way round you test. It will succeed in
that test.

I’ve attached an image to demonstrate the test. Given the black
rectangle, A, testing against any of the red rectangles, B.

“If A.topleft < B.bottomright” translates to any of the black corners
labelled ‘1’ being anywhere in the blue quadrant.
“and A.bottomright > B.topleft” translates to any of the black corners
labelled ‘2’ being anywhere in the green quadrant.

If these two tests are true, then they must be intersecting. If they are
not both true, then there is no way they are intersecting.

On Mon, 2012-10-22 at 09:38 +0200, Tobias Leich wrote:

Hi, shouldn’t be the “Seperating Axis Theorem” the best solution for
this, since SDL_Rects are AABBs?

That seems like an overly complex method for simple AABB to AABB
collision detection. SAT is there for collision between more complex
shapes.

6

No, it wouldn’t. The opposite corner is still in the appropriate
quadrant. A.topleft < B.bottomright, if they are the same size and
position, then that is the same as saying: A.topleft < A.bottomright. If
the bottomright corner is not greater than the topleft corner, then it’s
not a valid rectangle.

Thanks,
Sam Bull

-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121022/8b876c50/attachment.pgpOn Mon, 2012-10-22 at 19:00 +0200, Tobias Leich wrote:

What if the two rects have the same dimensions and position? Your test
would fail.

7

For SAT, I am thinking of the following:

/////////////////////////////////////////////////
If( rect1.bottom < rect2.top ) {
return NO_COLLISION;
}

In fact, what you have just proposed, is exactly what my patch does.
You’ve just reversed it to return not colliding. It will do the same
number of tests due to the way &&'s are evaluated.

Twitter/Identi.ca: @sambull

-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121022/ae7c348c/attachment.pgpOn Mon, 2012-10-22 at 19:00 +0200, Tobias Leich wrote:

8

Ya, think you are right…Am 22.10.2012 20:23, schrieb Sam Bull:

On Mon, 2012-10-22 at 19:00 +0200, Tobias Leich wrote:

For SAT, I am thinking of the following:

/////////////////////////////////////////////////
If( rect1.bottom < rect2.top ) {
return NO_COLLISION;
}

In fact, what you have just proposed, is exactly what my patch does.
You’ve just reversed it to return not colliding. It will do the same
number of tests due to the way &&'s are evaluated.

Twitter/Identi.ca: @sambull

9

What’s the optimization? It looks like the patch adds two jumps, correct?
(GCC 4.7.2 x86_64)On 10/22/2012 02:31 PM, Tobias Leich wrote:

Ya, think you are right…

Am 22.10.2012 20:23, schrieb Sam Bull:

On Mon, 2012-10-22 at 19:00 +0200, Tobias Leich wrote:

For SAT, I am thinking of the following:

/////////////////////////////////////////////////
If( rect1.bottom < rect2.top ) {
return NO_COLLISION;
}

In fact, what you have just proposed, is exactly what my patch does.
You’ve just reversed it to return not colliding. It will do the same
number of tests due to the way &&'s are evaluated.

Twitter/Identi.ca: @sambull

10

The original uses 3 or 6 comparisons before returning. The patch uses
1-4 comparisons and loses the variable overhead.

-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20121023/872e9b87/attachment.pgpOn Mon, 2012-10-22 at 16:45 -0400, John wrote:

What’s the optimization? It looks like the patch adds two jumps, correct?
(GCC 4.7.2 x86_64)