Narrow Phase (SAT)

Task 1 - A Box That Spins, Drifts and Bounces

Create a new Console App (C++) project in Visual Studio the same way as in the Environment Setup lab, naming it NarrowPhase. Use Add > New Item to add a new header file named OBB.h, and write the class shown below. An OBB (oriented bounding box) is a rotated rectangle stored as a centre, half-extents, and a rotation angle in radians, together with an angular and linear velocity so it can spin and drift on its own. update advances the rotation and position for one frame and bounces off the window's edges using the box's half-diagonal as a simple circular bound, so the box never visibly pokes through a wall no matter its rotation. getCorners returns the four true, rotated corners in world space, and draw renders exactly that same corner data as an outlined polygon, so the shape on screen always matches the shape any later test will examine.

Success condition: the project compiles with OBB fully defined in OBB.h. There is no window yet, that is added in the next task.

#pragma once
#include <SFML/Graphics.hpp>
#include <algorithm>
#include <array>
#include <cmath>

class OBB {
public:
    OBB(sf::Vector2f centerPos, sf::Vector2f halfExtents, float rotationRadians,
        float angularVelocityRadPerSec, sf::Vector2f linearVelocity, sf::Color colour)
        : center(centerPos), halfExtents(halfExtents), rotation(rotationRadians),
          angularVelocity(angularVelocityRadPerSec), velocity(linearVelocity), colour(colour) {}

    void update(float deltaTime, float worldWidth, float worldHeight) {
        rotation += angularVelocity * deltaTime;
        center += velocity * deltaTime;

        float boundRadius = boundingRadius();

        if (center.x - boundRadius < 0.0f) {
            center.x = boundRadius;
            velocity.x = -velocity.x;
        } else if (center.x + boundRadius > worldWidth) {
            center.x = worldWidth - boundRadius;
            velocity.x = -velocity.x;
        }

        if (center.y - boundRadius < 0.0f) {
            center.y = boundRadius;
            velocity.y = -velocity.y;
        } else if (center.y + boundRadius > worldHeight) {
            center.y = worldHeight - boundRadius;
            velocity.y = -velocity.y;
        }
    }

    std::array<sf::Vector2f, 4> getCorners() const {
        float cosR = std::cos(rotation);
        float sinR = std::sin(rotation);

        std::array<sf::Vector2f, 4> localSigns = {
            sf::Vector2f(-halfExtents.x, -halfExtents.y),
            sf::Vector2f(halfExtents.x, -halfExtents.y),
            sf::Vector2f(halfExtents.x, halfExtents.y),
            sf::Vector2f(-halfExtents.x, halfExtents.y)
        };

        std::array<sf::Vector2f, 4> corners;
        for (std::size_t i = 0; i < 4; ++i) {
            float localX = localSigns[i].x;
            float localY = localSigns[i].y;
            corners[i] = sf::Vector2f(
                center.x + localX * cosR - localY * sinR,
                center.y + localX * sinR + localY * cosR);
        }
        return corners;
    }

    std::array<sf::Vector2f, 2> getAxes() const {
        float cosR = std::cos(rotation);
        float sinR = std::sin(rotation);
        return { sf::Vector2f(cosR, sinR), sf::Vector2f(-sinR, cosR) };
    }

    sf::FloatRect getAABB() const {
        auto corners = getCorners();
        float minX = corners[0].x, maxX = corners[0].x;
        float minY = corners[0].y, maxY = corners[0].y;
        for (std::size_t i = 1; i < 4; ++i) {
            minX = std::min(minX, corners[i].x);
            maxX = std::max(maxX, corners[i].x);
            minY = std::min(minY, corners[i].y);
            maxY = std::max(maxY, corners[i].y);
        }
        return sf::FloatRect(sf::Vector2f(minX, minY), sf::Vector2f(maxX - minX, maxY - minY));
    }

    float boundingRadius() const {
        return std::sqrt(halfExtents.x * halfExtents.x + halfExtents.y * halfExtents.y);
    }

    void draw(sf::RenderWindow& window, sf::Color outlineColour, float outlineThickness = 2.0f) const {
        auto corners = getCorners();
        sf::ConvexShape shape(4);
        for (std::size_t i = 0; i < 4; ++i) {
            shape.setPoint(i, corners[i]);
        }
        shape.setFillColor(sf::Color::Transparent);
        shape.setOutlineColor(outlineColour);
        shape.setOutlineThickness(outlineThickness);
        window.draw(shape);
    }

    void drawAABB(sf::RenderWindow& window, sf::Color colour) const {
        sf::FloatRect bounds = getAABB();
        sf::RectangleShape box(bounds.size);
        box.setPosition(bounds.position);
        box.setFillColor(sf::Color::Transparent);
        box.setOutlineColor(colour);
        box.setOutlineThickness(1.0f);
        window.draw(box);
    }

    sf::Vector2f center;
    sf::Vector2f halfExtents;
    float rotation;
    float angularVelocity;
    sf::Vector2f velocity;
    sf::Color colour;
};

Task 2 - A Window With One Box You Control

Use Add > New Item to add a new C++ source file named NarrowPhaseDemo.cpp, and write the main function shown below. It opens a window and creates a single green OBB in the centre, moved with the arrow keys or WASD and rotated with Q and E, using continuous key state rather than key-press events so holding a key moves or rotates it smoothly frame to frame.

Success condition: a window opens showing one green box in the centre. Arrow keys or WASD move it, Q and E rotate it, and it stays fully on screen.

#include <SFML/Graphics.hpp>
#include <algorithm>
#include <optional>
#include "OBB.h"

namespace {
    constexpr unsigned int WORLD_WIDTH = 900;
    constexpr unsigned int WORLD_HEIGHT = 800;
    constexpr float MOVE_SPEED = 220.0f;
    constexpr float ROTATE_SPEED = 1.6f;
}

int main() {
    sf::VideoMode videoMode(sf::Vector2u(WORLD_WIDTH, WORLD_HEIGHT));
    sf::RenderWindow window(videoMode, "Narrow Phase - SAT on Rotating Boxes");
    window.setFramerateLimit(60);

    OBB userBox(
        sf::Vector2f(WORLD_WIDTH * 0.5f, WORLD_HEIGHT * 0.5f),
        sf::Vector2f(35.0f, 35.0f),
        0.0f, 0.0f,
        sf::Vector2f(0.0f, 0.0f),
        sf::Color(80, 220, 140));

    sf::Clock clock;

    while (window.isOpen()) {
        float deltaTime = clock.restart().asSeconds();

        while (const std::optional event = window.pollEvent()) {
            if (event->is<sf::Event::Closed>()) {
                window.close();
            }
        }

        sf::Vector2f move(0.0f, 0.0f);
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::Left) || sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::A)) {
            move.x -= 1.0f;
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::Right) || sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::D)) {
            move.x += 1.0f;
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::Up) || sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::W)) {
            move.y -= 1.0f;
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::Down) || sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::S)) {
            move.y += 1.0f;
        }
        userBox.center += move * MOVE_SPEED * deltaTime;
        userBox.center.x = std::clamp(userBox.center.x, 0.0f, static_cast<float>(WORLD_WIDTH));
        userBox.center.y = std::clamp(userBox.center.y, 0.0f, static_cast<float>(WORLD_HEIGHT));

        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::Q)) {
            userBox.rotation -= ROTATE_SPEED * deltaTime;
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Scancode::E)) {
            userBox.rotation += ROTATE_SPEED * deltaTime;
        }

        window.clear(sf::Color(12, 12, 18));
        userBox.draw(window, userBox.colour, 3.0f);
        window.display();
    }

    return 0;
}

Task 3 - Filling the Scene With Auto-Rotating Boxes

Open NarrowPhaseDemo.cpp. Add a helper that builds a randomly placed, randomly spinning box, and use it to fill the scene with several boxes alongside the user's green one.

1. In the anonymous namespace, add a std::mt19937 rng(std::random_device{}()) and a makeRandomBox(float worldWidth, float worldHeight) function returning an OBB with a random position, a half-extent between 20.0f and 45.0f, a random starting rotation, a random angular velocity between 0.25f and 1.6f radians per second (positive or negative), a random colour, and a linear velocity that is (0, 0) for roughly half the boxes and a small random drift for the rest.
2. In main, declare a std::vector<OBB> boxes, push userBox onto it first so it stays index 0, then push seven more boxes built from makeRandomBox.
3. Replace the single userBox.center += move * ... block so it only ever touches boxes[0], and add a loop calling update on every box from index 1 onward.
4. Replace the single userBox.draw(...) call with a loop drawing every box in boxes, each with box.draw(window, box.colour, 2.0f).

Success condition: the window shows the green user box plus several other boxes spinning and drifting independently, all bouncing off the window's edges.

namespace {
    constexpr unsigned int WORLD_WIDTH = 900;
    constexpr unsigned int WORLD_HEIGHT = 800;
    constexpr std::size_t BOX_COUNT = 8; // includes the user-controlled box

    constexpr float MOVE_SPEED = 220.0f;
    constexpr float ROTATE_SPEED = 1.6f;

    // TODO: declare std::mt19937 rng(std::random_device{}())

    // TODO: sf::Color randomColour() using a std::uniform_int_distribution<int> c(100, 255)

    // TODO: OBB makeRandomBox(float worldWidth, float worldHeight), returning an
    // OBB with a random position (60 px margin from the edges), a random
    // half-extent between 20.0f and 45.0f, a random rotation, a random
    // angular velocity between 0.25f and 1.6f rad/s (flip its sign with a
    // std::bernoulli_distribution), a random colour, and velocity (0, 0)
    // for roughly half the boxes and a small random drift for the rest
}

// In main(): declare std::vector<OBB> boxes, push userBox first, then push
// seven more from makeRandomBox. Update boxes[1] onward each frame and draw
// every box in the vector.

Task 4 - Watching the Bounding Box Swell and Shrink

Open NarrowPhaseDemo.cpp. Add a toggle so every box's tight bounding box can be shown alongside its true rotated outline, making the problem this lab exists to solve visible directly.

1. Declare bool showAABB = true; before the main loop.
2. Inside the event-polling loop, check for an sf::Event::KeyPressed event with event->getIf<sf::Event::KeyPressed>(), and flip showAABB when keyPressed->scancode is sf::Keyboard::Scancode::G.
3. Just before drawing the boxes themselves, if showAABB is true, loop over every box and call box.drawAABB(window, sf::Color(90, 90, 110, 130)).

Success condition: pressing G toggles a translucent rectangle around every box showing its tight axis-aligned bounds. Watch one spinning box closely: its bounding box visibly grows as the box rotates toward 45 degrees and shrinks back down as it continues rotating toward 90.

// Before the main loop:
bool showAABB = true;

// Inside the event-polling loop, alongside the existing sf::Event::Closed check:
if (const auto* keyPressed = event->getIf<sf::Event::KeyPressed>()) {
    switch (keyPressed->scancode) {
        // TODO: on sf::Keyboard::Scancode::G, flip showAABB
        default:
            break;
    }
}

// Just before the loop that draws every box:
// TODO: if showAABB, loop over every box and call
// box.drawAABB(window, sf::Color(90, 90, 110, 130))

Task 5 - Declaring the SAT Module

In Solution Explorer, use Add > New Item to add a new header file named SAT.h, and write the declarations shown below. A Result struct carries everything a caller needs back from one test: whether the pair collides, the unit-length push direction, and how far apart they overlap along that direction. The two free functions inside the SAT namespace are declared here but not yet defined, that happens over the next two tasks.

Success condition: the project still compiles, nothing calls these functions yet.

#pragma once
#include <SFML/Graphics.hpp>
#include "OBB.h"

namespace SAT {
    struct Result {
        bool colliding = false;
        sf::Vector2f normal{ 0.f, 0.f }; // unit MTV direction, points from A's centre toward B's
        float penetration = 0.f;          // MTV magnitude along normal; 0 if not colliding
    };

    // Precise narrow-phase test between two oriented boxes.
    Result test(const OBB& a, const OBB& b);

    // Cheap broad-phase pre-check: tight AABB vs tight AABB.
    bool aabbOverlap(const OBB& a, const OBB& b);
}

Task 6 - Implementing the Broad-Phase Pre-Check

Use Add > New Item to add a new C++ source file named SAT.cpp, and implement aabbOverlap shown below. This is a cheap first pass, exactly the tight AABB drawn by the G toggle in the previous task, used here to decide whether a pair is even worth testing precisely.

1. Include "SAT.h".
2. Define SAT::aabbOverlap to return a.getAABB().findIntersection(b.getAABB()).has_value().

Success condition: the project compiles with aabbOverlap defined. SAT::test is declared in SAT.h but still has no definition, that is fine as long as nothing calls it yet.

#include "SAT.h"

// TODO: define bool SAT::aabbOverlap(const OBB& a, const OBB& b), returning
// a.getAABB().findIntersection(b.getAABB()).has_value()

Task 7 - Finding and Drawing Candidate Pairs

Open NarrowPhaseDemo.cpp. Each frame, build the list of candidate pairs using the same brute-force, every-pair-once approach as the Brute-Force Broad Phase lab, this time filtering with SAT::aabbOverlap instead of a circle overlap test, then draw a thin line between the centres of every candidate pair so the broad-phase result is visible on screen before any precise test runs.

1. Include "SAT.h" alongside the existing includes.
2. Each frame, after updating every box, declare std::vector<std::pair<std::size_t, std::size_t>> candidatePairs, and fill it with a nested loop over every i < boxes.size() and j from i + 1 to boxes.size() - 1, pushing (i, j) whenever SAT::aabbOverlap(boxes[i], boxes[j]) is true.
3. After drawing the AABB overlay and before drawing the boxes themselves, loop over candidatePairs and draw a line between boxes[pair.first].center and boxes[pair.second].center using two sf::Vertex entries coloured sf::Color(255, 220, 60, 140) and sf::PrimitiveType::Lines.
4. Build an sf::Text reporting boxes.size() and candidatePairs.size(), and draw it in the top-left corner.

Success condition: a yellow line connects every pair of boxes whose bounding boxes overlap. Toggle G on and watch closely: some yellow lines connect boxes whose true rotated outlines are clearly not touching, only their swollen bounding boxes are overlapping. That gap is exactly what the next task closes.

// After updating every box, before clearing the window:
// TODO: declare std::vector<std::pair<std::size_t, std::size_t>> candidatePairs
// and fill it with a nested loop (i from 0, j from i + 1) pushing (i, j)
// whenever SAT::aabbOverlap(boxes[i], boxes[j]) is true

// After drawing the AABB overlay, before drawing the boxes:
// TODO: loop over candidatePairs and draw a line between
// boxes[pair.first].center and boxes[pair.second].center using two
// sf::Vertex entries coloured sf::Color(255, 220, 60, 140) and
// sf::PrimitiveType::Lines

// TODO: build and draw an sf::Text in the top-left corner reporting
// boxes.size() and candidatePairs.size()

Task 8 - Projecting a Box Onto an Axis

Open SAT.cpp and add the two small helpers shown below, in an anonymous namespace above aabbOverlap. Every later step of the SAT test relies on these to turn a box's four corners into a single range along one axis.

1. Add a struct Projection { float min; float max; }.
2. Add float dot(sf::Vector2f a, sf::Vector2f b) returning a.x * b.x + a.y * b.y.
3. Add Projection project(const std::array<sf::Vector2f, 4>& corners, sf::Vector2f axis). Start mn and mx both at dot(corners[0], axis), then loop i from 1 to 3, computing p = dot(corners[i], axis) and updating mn and mx with std::min and std::max. Return { mn, mx }.

Success condition: the project compiles. Neither helper is called from outside this file yet, that starts in the next task.

#include "SAT.h"
#include <algorithm>
#include <array>
#include <limits>

namespace {
    struct Projection {
        float min;
        float max;
    };

    float dot(sf::Vector2f a, sf::Vector2f b) {
        // TODO: return a.x * b.x + a.y * b.y
        return 0.0f;
    }

    Projection project(const std::array<sf::Vector2f, 4>& corners, sf::Vector2f axis) {
        // TODO: start mn and mx both at dot(corners[0], axis), then loop i
        // from 1 to 3 updating mn with std::min and mx with std::max against
        // dot(corners[i], axis), then return { mn, mx }
        return { 0.0f, 0.0f };
    }
}

bool SAT::aabbOverlap(const OBB& a, const OBB& b) {
    return a.getAABB().findIntersection(b.getAABB()).has_value();
}

Task 9 - Testing All Four Axes

Open SAT.cpp and add SAT::test below aabbOverlap. This is the precise narrow-phase test itself: check the two boxes' projections against each of the four candidate axes, exiting the moment one axis proves they cannot be touching.

1. Get both boxes' corners with a.getCorners() and b.getCorners(), and combine both boxes' axes from a.getAxes() and b.getAxes() into one std::array<sf::Vector2f, 4> axes.
2. Declare float bestOverlap = std::numeric_limits<float>::max() and sf::Vector2f bestAxis(0.f, 0.f) to track the smallest overlap seen so far.
3. For each axis in axes, project both boxes' corners onto it, then compute overlap = std::min(projA.max, projB.max) - std::max(projA.min, projB.min).
4. If overlap <= 0.f, this axis alone proves separation, return Result{ false, sf::Vector2f(0.f, 0.f), 0.f } immediately without checking the remaining axes.
5. Otherwise, if overlap < bestOverlap, update bestOverlap and bestAxis.

Success condition: the project compiles with a working test, but it is not called from main yet, so nothing changes on screen. That is the next task.

SAT::Result SAT::test(const OBB& a, const OBB& b) {
    std::array<sf::Vector2f, 4> cornersA = a.getCorners();
    std::array<sf::Vector2f, 4> cornersB = b.getCorners();

    // TODO: combine axesA and axesB (from a.getAxes() and b.getAxes()) into
    // one std::array<sf::Vector2f, 4> axes

    float bestOverlap = std::numeric_limits<float>::max();
    sf::Vector2f bestAxis(0.f, 0.f);

    // TODO: for each axis in axes, project cornersA and cornersB onto it,
    // compute overlap = std::min(projA.max, projB.max) - std::max(projA.min, projB.min).
    // If overlap <= 0.f, return Result{ false, sf::Vector2f(0.f, 0.f), 0.f }
    // immediately. Otherwise, if overlap < bestOverlap, update bestOverlap
    // and bestAxis.

    return Result{ false, sf::Vector2f(0.f, 0.f), 0.f };
}

Task 10 - Orienting the Push Direction

Open SAT.cpp and finish SAT::test. Reaching the end of the axis loop without an early return means every axis showed overlap, so the boxes are colliding. bestAxis already holds the smallest overlap direction, but it could point either way, this step makes sure the returned normal always points from a toward b.

1. Below the axis loop, compute sf::Vector2f direction = b.center - a.center.
2. If dot(direction, bestAxis) < 0.f, negate bestAxis so it points toward b.
3. Return Result{ true, bestAxis, bestOverlap }.

Success condition: the project compiles with a complete SAT::test. It still is not called from main yet, that is the next task.

// At the end of SAT::test, after the axis loop finds no separating axis:

// TODO: compute sf::Vector2f direction = b.center - a.center. If
// dot(direction, bestAxis) < 0.f, negate bestAxis so the normal points from
// a's centre toward b's. Then return Result{ true, bestAxis, bestOverlap }

Task 11 - Confirming Collisions on Screen

Open NarrowPhaseDemo.cpp and replace the flat yellow-line drawing from Task 7 with a real narrow-phase pass, so a candidate pair only stays yellow if SAT rejects it, and turns red once SAT confirms it.

1. Right after building candidatePairs, declare std::vector<SAT::Result> results(candidatePairs.size()), then loop over every candidate pair calling SAT::test(boxes[pair.first], boxes[pair.second]) and storing the result.
2. Count how many results have colliding == true into a confirmedCount.
3. Replace the single-colour line loop from Task 7: for each candidate pair, if its result is colliding, draw a thick line (use a rectangle-shaped line, 4 pixels wide, in sf::Color(255, 60, 60)) between the two centres. Otherwise, draw the thin yellow line exactly as before.
4. Update the stats text to also report confirmedCount and candidatePairs.size() - confirmedCount as the false-positive count.

Success condition: drive the green box into a spinning neighbour. The connecting line turns red only once their true rotated outlines actually touch, staying yellow the whole time only their bounding boxes overlap.

// Right after building candidatePairs:
// TODO: declare std::vector<SAT::Result> results(candidatePairs.size()),
// then fill it by calling SAT::test(boxes[pair.first], boxes[pair.second])
// for each entry in candidatePairs

// TODO: count how many results have colliding == true into confirmedCount

// Replacing the Task 7 line-drawing loop:
for (const auto& pair : candidatePairs) {
    sf::Vector2f centerA = boxes[pair.first].center;
    sf::Vector2f centerB = boxes[pair.second].center;

    // TODO: if this pair's SAT result is colliding, draw a thick
    // (4 pixel) sf::Color(255, 60, 60) line between centerA and centerB.
    // Otherwise, draw the thin sf::Color(255, 220, 60, 140) line from
    // Task 7 using sf::Vertex and sf::PrimitiveType::Lines.
}

// TODO: extend the stats text to also report confirmedCount and
// (candidatePairs.size() - confirmedCount) as the false-positive count

Task 12 - Drawing the Push-Apart Arrow

Open NarrowPhaseDemo.cpp. Add a small arrow-drawing helper and call it for every confirmed collision, so the direction and (scaled up for visibility) size of the minimum push needed to separate a pair is visible directly, not just implied by the red line.

1. In the anonymous namespace, add the drawThickLine and drawArrow helpers shown below. drawArrow draws a shaft from a start point along a direction for a given length, plus a small two-stroke arrowhead at the tip.
2. Add bool showMTV = true; before the main loop, and toggle it on sf::Keyboard::Scancode::M alongside the existing G handler.
3. Where a confirmed pair's thick red line is drawn, if showMTV is true, call drawArrow starting at the midpoint between the two centres, using the result's normal as the direction and result.penetration * 4.0f as the length (the multiplier exaggerates small penetrations so they stay visible), coloured sf::Color(255, 160, 30).

Success condition: pressing M toggles an orange arrow on every confirmed collision, pointing away from the overlap in the direction SAT::test reported as the cheapest separating push.

void drawThickLine(sf::RenderWindow& window, sf::Vector2f from, sf::Vector2f to, float thickness, sf::Color colour) {
    sf::Vector2f delta = to - from;
    float length = std::sqrt(delta.x * delta.x + delta.y * delta.y);
    if (length < 0.0001f) {
        return;
    }

    sf::RectangleShape line(sf::Vector2f(length, thickness));
    line.setOrigin(sf::Vector2f(0.0f, thickness * 0.5f));
    line.setPosition(from);
    float angleDeg = std::atan2(delta.y, delta.x) * 180.0f / 3.14159265f;
    line.setRotation(sf::degrees(angleDeg));
    line.setFillColor(colour);
    window.draw(line);
}

void drawArrow(sf::RenderWindow& window, sf::Vector2f from, sf::Vector2f direction, float length, sf::Color colour) {
    if (length < 0.0001f) {
        return;
    }
    sf::Vector2f tip = from + direction * length;
    drawThickLine(window, from, tip, 3.0f, colour);

    float angle = std::atan2(direction.y, direction.x);
    float headLength = std::min(12.0f, length * 0.4f);
    constexpr float headSpreadRadians = 2.6f;
    sf::Vector2f left(std::cos(angle + headSpreadRadians), std::sin(angle + headSpreadRadians));
    sf::Vector2f right(std::cos(angle - headSpreadRadians), std::sin(angle - headSpreadRadians));
    drawThickLine(window, tip, tip + left * headLength, 3.0f, colour);
    drawThickLine(window, tip, tip + right * headLength, 3.0f, colour);
}

// bool showMTV = true; before the main loop, toggled on sf::Keyboard::Scancode::M

// Where a confirmed pair's thick red line is drawn:
// if (showMTV) {
//     sf::Vector2f midpoint = (centerA + centerB) * 0.5f;
//     drawArrow(window, midpoint, result.normal, result.penetration * 4.0f, sf::Color(255, 160, 30));
// }