In this lesson, we'll learn how to determine if shapes overlap in our game world, a process often called intersection testing. We'll focus on using SDL's built in functions like SDL_HasIntersection() and SDL_IntersectRect() to check if SDL_Rect and SDL_FRect objects intersect.

We'll also see how these tests are crucial for relevancy testing - optimizing our game by only updating objects that are currently important, like those near the player or visible on screen.

Relevancy Testing

As our worlds get bigger, our players will only be interacting with a small portion of the level at any given time. Because of this, objects that are not close to the player's location, or objects that are not in view of the camera, become less important.

To optimize our game and keep everything running quickly, we can "turn off" those objects (or turn off some of their behaviors) until they become relevant again. For example:

An object that is not on the screen does not need to be animated
An object that is not near any player does not need to be simulating physics or AI behaviors
In a multiplayer game, a player on one side of the map does not need to be sending network updates describing their actions to a player on the opposite end of the map who can't see them

The mechanism that checks if a specific object or behavior should currently be active is often called a relevancy test.

Intersections and Distance

In a 2D game, relevancy testing is often done by checking if two rectangles intersect. This is because objects typically have rectangular bounding boxes. Our viewport is also a rectangle, so we can determine if an object is currently visible by determining if its bounding box rectangle intersects with the viewport rectangle:

Diagram showing the intersection of bounding boxes with the viewport

We don't necessarily want to turn every behavior off just because an object isn't currently visible. For example, if we put objects to sleep when they're not on the screen, the player could escape from enemies simply by turning their camera away from them.

Equally, however, we don't want to unnecessarily calculate AI behaviors for an enemy that is nowhere near the player. So, our AI system might implement a relevancy check that uses a world space distance comparison, instead:

Diagram showing examples of world space distance comparisons

Rectangular Intersections

The way we're representing rectangles in this course is with SDL's built-in SDL_Rect and SDL_FRect structures. As we've seen, these use the $x$ , $y$ , $w$ , and $h$ convention to represent a rectangle:

Diagram showing the SDL_Rect implementation of a bounding box

As a logic puzzle, you may want to consider how we could write an algorithm to determine if two SDL_Rect objects intersect by comparing their $x$ , $y$ , $w$ , and $h$ values.

However, we don't need to, as SDL has already provided some helpful functions to do just this.

Using `SDL_HasIntersection()`

We can use the SDL_HasIntersection() function to check if two SDL_Rect objects intersect.

This function accepts two pointers to the relevant rectangles, and returns SDL_TRUE if there is any intersection, or SDL_FALSE otherwise:

1#include <iostream>
2#include <SDL.h>
3
4int main(int argc, char** argv) {
5  SDL_Rect A{100, 100, 100, 100};
6  SDL_Rect B{150, 150, 100, 100};
7  if (SDL_HasIntersection(&A, &B)) {
8    std::cout << "Those are intersecting";
9  }
10
11  return 0;
12}

1Those are intersecting

Using `SDL_IntersectRect()`

The intersection of two rectangles is, itself, a rectangle:

Diagram showing the intersection of two rectangles

For more complex interactions, rather than the simple true or false returned by SDL_HasIntersection(), it may be helpful to retrieve this rectangle so we can analyze the exact nature of the intersection.

To do this, we have the SDL_IntersectRect() function. This function works in the same way as SDL_HasIntersection(), except we can provide a third pointer:

1#include <iostream>
2#include <SDL.h>
3
4int main(int argc, char** argv) {
5  SDL_Rect A{100, 100, 100, 100};
6  SDL_Rect B{150, 150, 100, 100};
7  SDL_Rect C;
8  if (SDL_IntersectRect(&A, &B, &C)) {
9    std::cout << "Those are intersecting"
10      << "  x = " << C.x
11      << ", y = " << C.y
12      << ", w = " << C.w
13      << ", h = " << C.h;
14  }
15
16  return 0;
17}

The SDL_Rect pointed at by the third argument will be updated with the intersection rectangle:

1Those are intersecting  x = 150, y = 150, w = 50, h = 50

Note that if the third argument is a nullptr, then SDL_IntersectRect() will return SDL_FALSE, even if the first two rectangles intersect:

1#include <iostream>
2#include <SDL.h>
3
4int main(int argc, char** argv) {
5  SDL_Rect A{100, 100, 100, 100};
6  SDL_Rect B{150, 150, 100, 100};
7  if (SDL_IntersectRect(&A, &B, nullptr)) {
8    // ...
9  } else {
10    std::cout << "No intersection";
11  }
12
13  return 0;
14}

1No intersection

If we're not sure whether our third argument is a nullptr, we should proactively check and switch to SDL_HasIntersection() if it is:

1#include <iostream>
2#include <SDL.h>
3
4int main(int argc, char** argv) {
5  SDL_Rect A{100, 100, 100, 100};
6  SDL_Rect B{150, 150, 100, 100};
7  SDL_Rect* C{nullptr};
8
9  if (C && SDL_IntersectRect(&A, &B, C)) {
10    std::cout << "Those are intersecting and "
11    "I have updated C";
12  } else if (SDL_HasIntersection(&A, &B)) {
13    std::cout << "Those are intersecting";
14  }
15
16  return 0;
17}

1Those are intersecting

Using `SDL_HasIntersectionF()` and `SDL_IntersectFRect()`

Variations of SDL_HasIntersection and SDL_IntersectRect() are available to compare SDL_FRect objects.

SDL_HasIntersectionF() and SDL_IntersectFRect() work in the same way as their SDL_Rect counterparts, except all the arguments are pointers to SDL_FRect objects instead.

Distance-Based Relevancy Tests

Let's see an example of adding some relevancy testing to our scene. We'll implement a relevancy check for our physics system, and skip physics simulations for objects that are more than 20 meters away from the player character.

Let's update our Scene class with a second object, as well as a function that gets the player character. We'll just assume the first object in our scene is the player character:

1// Scene.h
2// ...
3
4class Scene {
5public:
6  Scene() {
7    Objects.emplace_back(
8      "dwarf.png", Vec2{6, 2}, 1.9, 1.7, *this);
9    Objects.emplace_back(
10      "dragon.png", Vec2{30, 2}, 4, 2, *this);
11  }
12
13  const GameObject& GetPlayerCharacter() const {
14    return Objects[0];
15  }
16
17  // ...
18};

In our GameObject class, we'll add a public getter to grant access to the object's current position:

1// GameObject.h
2// ...
3
4class GameObject {
5public:
6  const Vec2& GetPosition() const {
7    return Position;
8  }
9  // ...
10private:
11  Vec2 Position{0, 0};
12  // ...
13};

Finally, in our GameObject::Tick() function, we'll calculate how far away the object is from the player, and return early if the distance is over our 20-meter threshold:

1// GameObject.cpp
2// ...
3
4void GameObject::Tick(float DeltaTime) {
5  if (Scene.GetPlayerCharacter().GetPosition()
6           .GetDistance(Position) > 20) {
7    std::cout << "Skipping Physics\n";
8    return;
9  }
10  std::cout << "Calculating Physics\n";
11  // ...
12}

Now, each frame skips the physics calculation for our dragon because it's more than $20$ meters away from the player. The player's physics is still calculated, because the distance from the player to the player is inherently $0$ :

1Calculating Physics
2Skipping Physics
3Calculating Physics
4Skipping Physics
5Calculating Physics
6Skipping Physics
7...

Updating Class Code to use Getters

When we add a getter to a class, it is worth considering whether we should update the functions within that class to use this getter too, rather than accessing the member directly. For example:

1// GameObject.h
2// ...
3
4class GameObject {
5// ...
6private:
7  float GetFrictionCoefficient() const {
8    // Before:
9    return Position.y > 2 ? 0 : 0.5;
10    // After:
11    return GetPosition().y > 2 ? 0 : 0.5;
12  }
13  // ...
14};

Standardizing how a value is accessed means that future changes are easier, and can reduce the risk of bugs. For example, determining the Position of an object may get more complex in the future, and we might decide to implement that logic in the getter:

1// GameObject.h
2// ...
3
4class GameObject {
5public:
6  // ...  
7  const Vec2& GetPosition() const {
8    return isLoading ? LoadingPosition : Position; 
9  }
10  // ...
11};

However, code that is bypassing our getter will also bypass that logic, and we may not notice the bug.

Intersection-Based Relevancy Tests

In the following example, we implement an imaginary animation system, but the animation is only relevant if the object is on the screen. We test if an object is currently visible by comparing the screen space coordinates of its bounding box to the viewport's rectangle, which we're currently storing on the Scene object.

Let's update our BoundingBox to make its Rect accessible:

1// BoundingBox.h
2// ...
3
4class BoundingBox {
5public:
6  // ...
7  const SDL_FRect GetRect() const {
8    return Rect;
9  }
10
11private:
12  SDL_FRect Rect;
13};

We'll also update our Scene to make its Viewport accessible:

1// Scene.h
2// ...
3
4class Scene {
5public:
6  // ...
7  const SDL_Rect& GetViewport() const {
8    return Viewport;
9  }
10
11private:
12  SDL_Rect Viewport;
13  // ...
14};

We'll add a CalculateAnimation() function to our GameObject class, and call it on every Tick():

1// GameObject.h
2// ...
3
4class GameObject {
5// ...
6private:
7  void CalculateAnimation();
8  // ...
9};

1// GameObject.cpp
2// ...
3
4void GameObject::CalculateAnimation() {
5  // ....
6}
7
8void GameObject::Tick(float DeltaTime) {
9  CalculateAnimation();
10  // ...
11}
12
13// ...

Before we can check if our bounding box and viewport rectangle are intersecting, we need to address two problems:

Our bounding boxes are in world space, while the viewport is in screen space
Our bounding boxes use floating point numbers (SDL_FRect) while our viewport uses integers (SDL_Rect).

We can address these problems by using the Scene.ToScreenSpace() and BoundingBox::Round() functions we added in the previous lesson:

1// GameObject.cpp
2// ...
3
4void GameObject::CalculateAnimation() {
5  SDL_Rect BoundingBox{BoundingBox::Round(
6    Scene.ToScreenSpace(Bounds.GetRect())
7  )};
8
9  // ....
10}
11
12// ...

Finally, we can check if our object is currently visible using SDL_HasIntersection(), and skip animating if it isn't:

1// GameObject.cpp
2// ...
3
4void GameObject::CalculateAnimation() {
5  SDL_Rect BoundingBox{BoundingBox::Round(
6    Scene.ToScreenSpace(Bounds.GetRect())
7  )};
8
9  if (!SDL_HasIntersection(
10    &Scene.GetViewport(), &BoundingBox
11  )) {
12    std::cout << "Not visible - skipping\n";
13  }
14
15  std::cout << "Calculating animation\n";
16  // ....
17}
18// ...

1Calculating animation
2Not visible - skipping
3Calculating animation
4Not visible - skipping
5Calculating animation
6Not visible - skipping
7...

Tick Dependencies and Off-By-One Logic

As we progressively add more and more logic to be executed on each frame (that is, each iteration of our game loop), things can get a little complicated. This is because, at any given time within the frame, we may not be entirely clear which code has already run.

If ObjectA's Tick() function is pulling data from ObjectB, has ObjectB's Tick() function been called yet for this frame? If not, ObjectA is using the state of ObjectB from the previous frame, effectively meaning that logic is running one frame behind.

In this case, our Scene is updating its Viewport value within the Render() function. However, our Render() functions are called after our Tick() function. This means that, if the viewport has changed, our GameObject is using values from the previous frame.

In many cases, something running one frame behind is not noticeable. However, where possible, we typically want to use the latest state. This is particularly true for logic that is performed as a result of player input, as we want our game to feel as responsive as possible.

Creating a system to manage these per-frame dependencies can be quite complex to set up. It may involve adding additional tick functions, such as a PostPhysicsTick() that runs after the physics simulations. This means that if some logic depends on the latest positional data, we can put it in PostPhysicsTick() so it runs after our physics code has updated every object.

Even within tick functions, we can still have inter-object dependencies. For example, if ObjectA's frame-by-frame updates depend on the state of ObjectB, we typically want to ensure that ObjectB gets updated before ObjectA queries it.

As an example, this article explains Unreal Engine's design for dealing with dependencies in the per-frame update process.

Checking Relevancy when Rendering

The most obvious optimization we can make for an object that is not within the viewport is to not render that object. So, we may be tempted to do something like this within our Render() function:

1void GameObject::Render(SDL_Surface* Surface) {
2  if (!isInViewport()) return;
3  // ...
4}

This is a good instinct but in this case, and most cases in general, it is unnecessary. The underlying APIs we use for rendering typically already include this optimization.

In our examples, we're using SDL_BlitSurface() and SDL_BlitSurfaceScaled() for rendering. These functions already perform a very similar check internally to minimize unnecessary work if the relevant rectangles do not intersect.

World Space Intersections

SDL's built-in rectangle intersection functions like SDL_HasIntersection() and SDL_IntersectFRect() assume that the provided rectangles use the "y-down" convention. That is, they assume that increasing y values correspond to moving vertically down within the space.

That has been true of our previous examples, as we were comparing rectangles defined in screen space, or rectangles converted to screen space. However, for rectangles defined in our definition of world space, where increasing y values correspond to moving up, we need an alternative.

We can create these "y-up" intersection functions from scratch if we want, or we can adapt how we use the SDL functions.

If we wanted to use SDL's functions, we have four steps:

Start with rectangles defined using the y-up convention.
Create copies of these rectangles that have their y position reduced by their height (h)
Use an SDL function like SDL_IntersectFRect() to calculate the intersection of these rectangles within SDL's coordinate system.
If we need the intersection rectangle, increase its y value by its height to convert it to the y-up representation.

To understand why this works, we can step through the logic visually:

Diagram showing the process of converting between y-up and y-down representations

Let's add a function to our BoundingBox class that implements this procedure to calculate world-space intersections between our bounding boxes:

1// BoundingBox.h
2// ...
3
4class BoundingBox {
5public:
6  // ...
7  bool GetIntersection(
8    const BoundingBox& Other,
9    SDL_FRect* Intersection
10  ) {
11    if (!Intersection) return false;
12    
13    // Step 1
14    SDL_FRect A{GetRect()};
15    SDL_FRect B{Other.GetRect()};
16    
17    // Step 2
18    A.y -= A.h;
19    B.y -= B.h;
20    
21    // Step 3
22    SDL_IntersectFRect(&A, &B, Intersection);
23    
24    // If the intersection rectangle has no area,
25    // there was no intersection
26    if (Intersection->w <= 0 ||
27        Intersection->h <= 0) {
28      return false;
29    }
30    
31    // Step 4
32    Intersection->y += Intersection->h;
33    
34    return true;
35  }
36};

Using `SDL_RectEmpty()` and `SDL_FRectEmpty()`

Our previous example checks if a rectangle is "empty" by checking if it has no area. That is, if it has either no height (h) or no width (w).

SDL provides SDL_RectEmpty() and SDL_FRectEmpty() functions for this, which we can use if we prefer. Our previous code could be written like this:

1// BoundingBox.h
2// ...
3
4class BoundingBox {
5public:
6  // ...
7  bool GetIntersection(
8    const BoundingBox& Other,
9    SDL_FRect* Intersection
10  ) {
17    
18    if (Intersection->w <= 0 ||
19        Intersection->h <= 0) {
20      return false;
21    }
22  
23    if (SDL_FRectEmpty(Intersection)) {
24      return false;
25    }
26    
29  }
30}

Complete Code

To keep things simple, we'll remove our relevancy tests for now, but we'll keep the getters we added in this lesson.

Our updated Scene, GameObject, and BoundingBox classes are provided below, with the code we added in this lesson highlighted:

Summary

This lesson covered techniques for detecting intersections between SDL_Rect and SDL_FRect objects. We discussed the importance of these checks for implementing relevancy tests, which help make games run faster by skipping updates for non relevant objects.

We explored both distance based and intersection based relevancy and learned how to use SDL's specific functions for these tasks. Key Takeaways:

Games use intersection tests to see if objects (like bounding boxes) overlap.
SDL offers functions: SDL_HasIntersection(), SDL_IntersectRect(), SDL_HasIntersectionF(), SDL_IntersectFRect().
Relevancy testing optimizes performance by selectively updating game elements.
Common relevancy methods include checking distance to the player or intersection with the screen viewport.
Be mindful of coordinate systems (y up vs. y down) when performing intersection tests.
Third-party libraries like SDL's SDL_BlitSurface() often perform their own relevancy checks internally, so it's not always necessary for us to perform checks before using them. We can check the documentation to make sure.

Intersections and Relevancy Tests

Relevancy Testing

Intersections and Distance

Rectangular Intersections

Using `SDL_HasIntersection()`

Using `SDL_IntersectRect()`

Using `SDL_HasIntersectionF()` and `SDL_IntersectFRect()`

Distance-Based Relevancy Tests

Intersection-Based Relevancy Tests

World Space Intersections

Complete Code

Summary

Handling Object Collisions

Game Development with SDL2

Intersections and Relevancy Tests

Relevancy Testing

Intersections and Distance

Rectangular Intersections

Using SDL_HasIntersection()

Using SDL_IntersectRect()

Using SDL_HasIntersectionF() and SDL_IntersectFRect()

Distance-Based Relevancy Tests

Intersection-Based Relevancy Tests

World Space Intersections

Complete Code

Summary

Handling Object Collisions

Using `SDL_HasIntersection()`

Using `SDL_IntersectRect()`

Using `SDL_HasIntersectionF()` and `SDL_IntersectFRect()`