Intersections and Relevancy Tests

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:

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:

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:

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.

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

SDL_IntersectRect()

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

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

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...

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};

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

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:

1. Our bounding boxes are in world space, while the viewport is in screen space
2. 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...

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

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:

1. Start with rectangles defined using the y-up convention.
2. Create copies of these rectangles that have their y position reduced by their height (h)
3. Use an SDL function like SDL_IntersectFRect() to calculate the intersection of these rectangles within SDL's coordinate system.
4. 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:

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};

1// BoundingBox.h
2// ...
3
4class BoundingBox {
5public:
6  // ...
7  bool GetIntersection(
8    const BoundingBox& Other,
9    SDL_FRect* Intersection
10  ) {
Previous Code Unchanged|Show
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    
Previous Code Unchanged|Show
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:

1#pragma once
2#include <SDL.h>
3#include <vector>
4#include "GameObject.h"
5
6class Scene {
7public:
8  Scene() {
9    Objects.emplace_back(
10      "dwarf.png", Vec2{6, 2}, 1.9, 1.7, *this);
11  }
12
13  const GameObject& GetPlayerCharacter() const {
14    return Objects[0];
15  }
16  
17  const SDL_Rect& GetViewport() const {
18    return Viewport;
19  }
20
21  Vec2 ToScreenSpace(const Vec2& Pos) const {
22    auto [vx, vy, vw, vh]{Viewport};
23    float HorizontalScaling{vw / WorldSpaceWidth};
24    float VerticalScaling{vh / WorldSpaceHeight};
25
26    return {
27      vx + Pos.x * HorizontalScaling,
28      vy + (WorldSpaceHeight - Pos.y)
29      * VerticalScaling
30    };
31  }
32
33  SDL_FRect ToScreenSpace(
34    const SDL_FRect& Rect) const {
35    Vec2 ScreenPos{
36      ToScreenSpace(Vec2{Rect.x, Rect.y})};
37    float HorizontalScaling{
38      Viewport.w / WorldSpaceWidth};
39    float VerticalScaling{
40      Viewport.h / WorldSpaceHeight};
41
42    return {
43      ScreenPos.x,
44      ScreenPos.y,
45      Rect.w * HorizontalScaling,
46      Rect.h * VerticalScaling
47    };
48  }
49
50  Vec2 ToWorldSpace(const Vec2& Pos) const {
51    auto [vx, vy, vw, vh]{Viewport};
52    float HorizontalScaling{
53      WorldSpaceWidth / vw};
54    float VerticalScaling{
55      WorldSpaceHeight / vh};
56
57    return {
58      (Pos.x - vx) * HorizontalScaling,
59      WorldSpaceHeight - (Pos.y - vy)
60      * VerticalScaling
61    };
62  }
63
64  void HandleEvent(SDL_Event& E) {
65    for (GameObject& Object : Objects) {
66      Object.HandleEvent(E);
67    }
68  }
69
70  void Tick(float DeltaTime) {
71    for (GameObject& Object : Objects) {
72      Object.Tick(DeltaTime);
73    }
74  }
75
76  void Render(SDL_Surface* Surface) {
77    SDL_GetClipRect(Surface, &Viewport);
78    for (GameObject& Object : Objects) {
79      Object.Render(Surface);
80    }
81  }
82
83private:
84  SDL_Rect Viewport;
85  std::vector<GameObject> Objects;
86  float WorldSpaceWidth{14}; // meters
87  float WorldSpaceHeight{6}; // meters
88};

1// GameObject.h
2#pragma once
3#include <SDL.h>
4
5#include "BoundingBox.h"
6#include "Vec2.h"
7#include "Image.h"
8
9class Scene;
10
11class GameObject {
12public:
13  GameObject(
14    const std::string& ImagePath,
15    const Vec2& InitialPosition,
16    float Width,
17    float Height,
18    const Scene& Scene
19  ) : Image{ImagePath},
20      Position{InitialPosition},
21      Scene{Scene},
22      Bounds{
23        SDL_FRect{
24          InitialPosition.x, InitialPosition.y,
25          Width, Height
26        }
27      } {}
28
29  void HandleEvent(const SDL_Event& E);
30
31  const Vec2& GetPosition() const {
32    return Position;
33  }
34
35  void Tick(float DeltaTime);
36
37  void Render(SDL_Surface* Surface);
38
39  void ApplyForce(const Vec2& Force) {
40    Acceleration += Force / Mass;
41  }
42
43private:
44  Image Image;
45  const Scene& Scene;
46
47  Vec2 Position{0, 0};
48  Vec2 Velocity{0, 0};
49  Vec2 Acceleration{0, -9.8};
50  float Mass{70};
51  BoundingBox Bounds;
52
53  float DragCoefficient{0.2};
54
55  Vec2 DragForce() const {
56    return -Velocity * DragCoefficient
57      * Velocity.GetLength();
58  }
59
60  float GetFrictionCoefficient() const {
61    if (Position.y > 2) { return 0; }
62
63    return 0.5;
64  }
65
66  Vec2 FrictionForce(float DeltaTime) const {
67    float MaxMagnitude{
68      GetFrictionCoefficient()
69      * Mass * -Acceleration.y};
70    if (MaxMagnitude <= 0) return Vec2(0, 0);
71
72    float StoppingMagnitude{
73      Mass *
74      Velocity.GetLength() / DeltaTime};
75
76    return -Velocity.Normalize() * std::min(
77      MaxMagnitude, StoppingMagnitude);
78  }
79
80  void Clamp(Vec2& V) const {
81    V.x = std::abs(V.x) > 0.01 ? V.x : 0;
82    V.y = std::abs(V.y) > 0.01 ? V.y : 0;
83  }
84
85  void ApplyImpulse(const Vec2& Impulse) {
86    Velocity += Impulse / Mass;
87  }
88
89  void ApplyPositionalImpulse(
90    const Vec2& Origin, float Magnitude
91  ) {
92    Vec2 Displacement{Position - Origin};
93    Vec2 Direction{Displacement.Normalize()};
94    float Distance{Displacement.GetLength()};
95    float AdjustedMagnitude{
96      Magnitude /
97      ((Distance + 0.1f) * (Distance + 0.1f))};
98
99    ApplyImpulse(Direction * AdjustedMagnitude);
100  }
101};

1#pragma once
2#include <SDL.h>
3#include "Vec2.h"
4
5class Scene;
6
7class BoundingBox {
8public:
9  BoundingBox(const SDL_FRect& InitialRect)
10    : Rect{InitialRect} {}
11
12  void SetPosition(const Vec2& Position) {
13    Rect.x = Position.x;
14    Rect.y = Position.y;
15  }
16
17  static SDL_Rect Round(const SDL_FRect& Rect) {
18    return {
19      static_cast<int>(std::round(Rect.x)),
20      static_cast<int>(std::round(Rect.y)),
21      static_cast<int>(std::round(Rect.w)),
22      static_cast<int>(std::round(Rect.h))
23    };
24  }
25  
26  bool GetIntersection(
27    const BoundingBox& Other,
28    SDL_FRect* Intersection
29  ) {
30    if (!Intersection) return false;
31    SDL_FRect A{GetRect()};
32    A.y -= A.h;
33    SDL_FRect B{Other.GetRect()};
34    B.y -= B.h;
35    SDL_IntersectFRect(&A, &B, Intersection);
36
37    if (SDL_FRectEmpty(Intersection)) {
38      return false;
39    }
40
41    Intersection->y += Intersection->h;
42    return true;
43  }
44
45  const SDL_FRect GetRect() const {
46    return Rect;
47  }
48
49  void Render(SDL_Surface* Surface,
50              const Scene& Scene);
51
52private:
53  SDL_FRect Rect;
54};

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.

Free and Unlimited Access

Professional C++

Unlock the true power of C++ by mastering complex features, optimizing performance, and learning expert workflows used in professional development

View Course