Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Rectangular Boundary Collision  (Read 9671 times)

0 Members and 1 Guest are viewing this topic.

Hapax

  • Hero Member
  • *****
  • Posts: 3043
  • My number of posts is shown in hexadecimal.
    • View Profile
Rectangular Boundary Collision
« on: July 11, 2017, 08:08:46 pm »
Rectangular Boundary Collision

SFML's sprites and shapes can provide you with their axis-aligned boundary boxes (getGlobalBounds) and you can easily use these rectangles to test if they intersect. Unfortunately, this only allows axis-aligned collision detection.

Rectangular Boundary Collision allows testing collision based on their original rectangular boundary box (getLocalBounds). It tests to see if an object's rectangular boundary collides with another object's rectangular boundary. This method, however, allows transformations to be taken into account - most notably, rotation.

Rectangular Boundary Collision is a single, templated free-function contained within the "collision" namespace:
const bool spritesAreColliding = collision::areColliding(sprite1, sprite2);

You only need the header, which is approximately 100 lines of code...

The collision is performed in three stages:
  • Level 0 - AABB (axis-aligned boundaries boxes):
    tests the axis-aligned boundaries boxes (equivalent to getGlobalBounds) of the objects to see if they intersect.
  • Level 1 - Corner inside opposite object:
    tests to see if any of either object's corner is inside the other object.
  • Level 2 - SAT (Separating Axis Theorem):
    tests using a simplified version (for rectangles) of SAT to catch other cases.
If, at any time, the result is certain, the following stages are not calculated. This allows easier detections to be done without resorting to the more involved calculations.

The collision level represents after which stage to leave the function, regardless of if a result is certain.


(red = collision, green = no collision)

Wiki page:
https://github.com/SFML/SFML/wiki/Source%3A-Rectangular-Boundary-Collision

GitHub repository (it's a part of SfmlSnippets):
https://github.com/Hapaxia/SfmlSnippets/tree/master/RectangularBoundaryCollision

Example used to create the above screenshots is included in the repository and also on the wiki page.
« Last Edit: June 08, 2019, 10:48:00 pm by Hapax »
Selba Ward - SFML drawables
Kairos - Timing Library
Rectangular Boundary Collision - Rectangular SAT Collision

@Hapaxiation - Hapaxia on Twitter

Jove

  • Full Member
  • ***
  • Posts: 114
    • View Profile
    • http://www.jestofevekites.com/
Re: Rectangular Boundary Collision
« Reply #1 on: March 14, 2021, 09:00:15 pm »
This is really interesting.

I've been eyeballing this code for a few weeks as a means of solving my off-screen culling which isn't perfect due to scale and rotation combined with a zooming and rotating view. What I have is working alright based on a cull-radius, but this could help make it very accurate!

I'm supposing I could make one object a 'screen-rectangle' and the other one whichever entity instance I'm checking.

Thanks.


*EDIT
Worked as expected!
Increased CPU usage a bit more than I'd like, but I can filter-out a lot of that with a radius check, leaving only the outer entities to test with this code.

Thanks HAPAX!!  ;D
« Last Edit: March 15, 2021, 11:15:51 pm by Jove »
{much better code}

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6259
  • Thor Developer
    • View Profile
    • Bromeon
Re: Rectangular Boundary Collision
« Reply #2 on: March 19, 2021, 11:12:34 am »
Nice, thanks a lot for yet another contribution! Very nicely documented too :)
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

KRS

  • Newbie
  • *
  • Posts: 19
  • The burning you feel?
    • View Profile
    • Email
Re: Rectangular Boundary Collision
« Reply #3 on: March 21, 2021, 01:43:53 pm »
That is cool. ;D Did something like that time ago. But i did so that shapes are made of triangles, so that you can check if any point is inside of a triangle using something like that
float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}
And so you can construct any shapes out of these triangles, and make complex hitboxes. Will be sweet if you will add such a feauture. ;)
« Last Edit: March 21, 2021, 01:45:33 pm by KRS »

Hapax

  • Hero Member
  • *****
  • Posts: 3043
  • My number of posts is shown in hexadecimal.
    • View Profile
Re: Rectangular Boundary Collision
« Reply #4 on: March 28, 2021, 07:00:56 pm »
Ah, thanks!

Glad you found some use of this. It's been here for years  ;D

Yes, I'd say it would be best to filter out tests before using it; it's not the best idea to test collision between all objects if they aren't near each other.

One thing to note, however, is that this should be just doing the standard rectangle intersection test unless it's not completely sure of the result so the more complex tests should only be happening if they really need it.
Selba Ward - SFML drawables
Kairos - Timing Library
Rectangular Boundary Collision - Rectangular SAT Collision

@Hapaxiation - Hapaxia on Twitter