Lines, Rays, and Distances

Chapter 11 gave us shapes to store. This chapter starts asking questions of them, beginning with the two simplest, the line and the ray, since almost everything harder is built on them. How far is a point from a line? Which side of it is the point on? And where, exactly, does a ray cross a wall? Answer those, and you have the tools for lines of sight, laser beams, sliding along walls, and much of Part 4's collision work.

The payoff is a laser that fires from a point, sweeps with your mouse, and stops dead at the first wall it meets. That's a ray cast, the most useful single question in this whole subject. It's how a game asks what the first thing between here and there is: what a bullet hits, what a guard can see, whether there's a clear line to the player. And all of it comes from the cross product, which we've had since Chapter 4, with a little algebra that this chapter works through in full.

In this chapter, we will:

• Meet the three ways to write a line, and the two this book uses
• Find a point's distance from a line, with a sign that says which side it's on
• Drop a perpendicular from a point to a line
• Work out where a ray crosses a segment, and check the answer with numbers
• Use the same test for lines and for segments, and handle its edge cases
• Cast a ray to find the nearest wall it hits
• Build Laser, a beam you aim with the mouse

We'll start with how to write a line down.

The Three Forms of a Line

A line is such a simple thing that there are three common ways to describe one, and each suits different jobs.

The slope-intercept form is the one from school: y = mx + b, where m is the slope, and b is where the line crosses the y axis. It's familiar, but it has a fatal flaw for games. A vertical line has an infinite slope, which no number can hold, and a wall can easily be vertical. This book doesn't use it.

The parametric form is the one we've been using all along. The line through A and B is every point A + t × (B - A), for some number t. At a t of 0, it's A, and at 1, it's B. At 0.5, it's halfway between, which is Chapter 8's lerp. Allow only the t values from 0 to 1, and you have the segment from A to B. Allow every t of 0 or more, and you have a ray from A through B. Allow any t at all, and you have the whole line. Vertical lines are no trouble, and this form slides straight into the algebra of where things cross.

The implicit form describes a line by a test that its points pass. Take a normal to the line: a vector at right angles to it, such as (B - A).perp(), a quarter turn of its direction. A point P is on the line exactly when the vector from A to P is at right angles to the normal, so that their dot product is zero:

n · (P - A) = 0

For a point off the line, the dot product isn't zero. It's positive on the side the normal points to, and negative on the other. So the parametric form is for making points along a line, and the implicit form is for testing points against one. The next image shows a line with its t values, and its normal.

Between them, the parametric and implicit forms cover everything this chapter needs.

Distance From a Point to a Line

How far is a point P from the infinite line through A and B? The distance is the length of the perpendicular from P to the line, and there are two ways to find it. They give the same number, and seeing why is worth the detour.

Area Over Base

Chapter 4 found that the cross product (B - A).cross(P - A) is the area of the parallelogram that the two vectors make, with a sign. But a parallelogram's area is also its base times its height. Take B - A as the base, and the height is exactly the perpendicular distance from P to the line. So the distance is the area divided by the base's length:

distance = |(B - A) × (P - A)| / |B - A|

Here's a worked example. With A at (0, 0), B at (3, 4) and P at (5, 0), the cross product is 3 × 0 − 4 × 5, which is −20. The base's length is 5, so P is 20 / 5, or 4, from the line. The sign of −20 says which side of the line P is on.

From the Normal

Now take the implicit form's dot product, with the normal (B - A).perp(). Write B - A as (x, y). Its quarter turn is (-y, x), and the dot product of that with P - A, written as (p, q), is -y × p + x × q. That's x × q - y × p, which is exactly the cross product of (x, y) and (p, q):

(B - A).perp().dot(P - A) = (B - A).cross(P - A)

So Chapter 4's side test was the implicit form all along. And dividing by |B - A| is the same as using a unit normal, so the dot product with the unit normal is the distance itself, with its sign:

// How far a point is from the infinite line through A and B: the dot
// product with the line's unit normal, A to B turned a quarter turn. It's
// positive on the right of A to B, as the screen shows it, and negative on
// the left.
float signedDistance(Vec2 P, Vec2 A, Vec2 B)
{
    Vec2 normal = (B - A).perp().normalized();
    return normal.dot(P - A);
}

For the worked example, the unit normal is (3, 4).perp(), which is (-4, 3), divided by 5: (-0.8, 0.6). Its dot product with P - A, (5, 0), is −4: P is 4 from the line, on the negative side. That's the signed distance, and it's the most useful number this chapter makes. Its size is the distance, and its sign is the side.

If A and B are the same point, there's no line. Then normalized turns the zero normal into the zero vector, so the distance comes out as 0, rather than dividing by 0. Code that can be handed such a line should check for it first.

Which Side Is Positive

On the screen, with y pointing down, the normal (B - A).perp() points to the right of the line, as you look along it from A toward B. Chapter 4 found that a quarter turn is clockwise on the screen, and a clockwise quarter turn from facing along the line is facing to its right. So a positive signed distance means the point is on the right of A to B, and a negative one means it's on the left.

The worked example's line runs from (0, 0) toward (3, 4): down and to the right on the screen. The point (5, 0) is up and to the right of it, which, looking along the line from A, is on its left. The negative distance agrees.

The Foot of the Perpendicular

The point on the line nearest to P is the foot of the perpendicular. Since the signed distance is how far P is from the line along the unit normal, stepping back that far along the normal lands on the line:

foot = P - n × distance

For the worked example, that's (5, 0) - (-0.8, 0.6) × (-4), which is (5, 0) + (-3.2, 2.4), or (1.8, 2.4). It's on the line, since it's 0.6 times (3, 4). The next image shows the parallelogram, its height, and the foot.

This is the distance to the infinite line. The distance to a segment is different when the foot falls beyond one of its ends, since then the nearest point is the end itself. That's Chapter 13's subject.

Ray Against Segment

Now the central question. A ray starts at O, and heads along the unit vector d. A wall is the segment from A to B. Where, if anywhere, does the ray cross the wall, and how far along the ray is that?

Setting It Up

Write both in parametric form. A point on the ray is O + t × d, and since d is a unit vector, t is the distance from O in pixels. A point on the wall is A + u × s, where s is B - A, and u runs from 0 at A to 1 at B. The ray meets the wall's line where the two are the same point:

O + t × d = A + u × s

There are two unknowns, t and u. The equation is between vectors, so it's really two equations, one for x and one for y, which is enough to find both. Move the unknowns to one side:

t × d - u × s = A - O

The right side, A - O, is the vector from the ray's start to the wall's first end. Everything in it is known, which leaves just t and u to find.

Solving It

The cross product makes short work of this. The cross product of any vector with itself is zero, since a vector and itself make a parallelogram with no area. So crossing both sides with s gets rid of u, because its term becomes u × (s × s), which is zero:

t × (d × s) - u × (s × s) = (A - O) × s
t × (d × s)               = (A - O) × s
t = ((A - O) × s) / (d × s)

Crossing both sides with d instead gets rid of t, the same way. That leaves -u × (s × d), and since swapping a cross product's two vectors flips its sign, s × d is -(d × s):

t × (d × d) - u × (s × d) = (A - O) × d
u × (d × s)               = (A - O) × d
u = ((A - O) × d) / (d × s)

Both answers share the denominator d × s. It's zero when d and s point the same way, or exactly opposite: when the ray and the wall are parallel, and never cross at a single point.

A Worked Example

Put a ray at O (0, 0), heading along d (1, 0), to the right. A wall runs from A (5, -2) to B (5, 2), a vertical line at x = 5. Then s is (0, 4). The denominator, d × s, is 1 × 4 − 0 × 0, or 4. And the vector A - O is (5, -2):

t = ((5, -2) × (0, 4)) / 4 = (5 × 4 - (-2) × 0) / 4 = 20 / 4 = 5
u = ((5, -2) × (1, 0)) / 4 = (5 × 0 - (-2) × 1) / 4 =  2 / 4 = 0.5

The ray hits the wall 5 pixels out, at (5, 0), exactly halfway along the wall. Both answers are what a sketch would tell you.

Now aim the ray along (0.6, 0.8) instead, down and to the right. The denominator is 0.6 × 4 − 0.8 × 0, or 2.4, and t is 20 / 2.4, or 8.33. But u is (5 × 0.8 − (−2) × 0.6) / 2.4, which is 5.2 / 2.4, or 2.17. That's more than 1, so the crossing is beyond B: the ray reaches the wall's line at (5, 6.67), below the wall's end at (5, 2). It misses. The next image shows both rays.

The algebra finds where the ray meets the wall's whole line. The ranges of t and u decide whether that's a real hit.

In Code

Laser's version returns whether the ray hits, and fills in t and u through references:

// Where a ray, from O along the unit vector d, crosses the segment from A
// to B. It's true for a hit, and then t is the distance along the ray,
// and u the fraction of the way from A to B. Lines that are parallel, to
// within a tiny angle, never cross at a single point, so they miss.
bool raySegment(Vec2 O, Vec2 d, Vec2 A, Vec2 B, float& t, float& u)
{
    Vec2 s = B - A;
    float denom = d.cross(s);
    if (std::fabs(denom) < 0.00001f * s.length()) return false;
    Vec2 toA = A - O;
    t = toA.cross(s) / denom;
    u = toA.cross(d) / denom;
    return t >= 0.0f && u >= 0.0f && u <= 1.0f;
}

It works out s and the denominator, and returns false for a ray parallel to the wall. Otherwise, it finds t and u, as Solving It did, with toA for A - O. The crossing is a hit when t is 0 or more, so that it's ahead of the ray, not behind it. It also needs a u from 0 to 1, so that it's on the wall, not off one of its ends.

Lines and Segments

The algebra never changes. What changes is which values of t and u count. A ray against a segment needs t of 0 or more, and u from 0 to 1. Two infinite lines always cross, if they aren't parallel, so any t and u will do. And two segments cross when both t and u run from 0 to 1.

There's a catch with that last one. For t to run from 0 to 1 along the first segment, d must be the first segment's whole vector, from its first end to its second, not a unit vector. Then t is a fraction of that segment, as u is of the other, not a distance in pixels. With Laser's unit d, a limit of t up to 1 would only accept walls within a pixel of the origin.

The Edge Cases

Four cases deserve a thought before they surprise you.

The first is parallel lines. A zero denominator covers two situations: a ray beside a wall, which never meets it, and a ray running exactly along a wall, which touches it all the way. The function calls both a miss. For a laser, that's fine. A game where things slide along walls may need its own rule for the second.

The second is the size of the test. The denominator, d × s, is the two vectors' lengths multiplied together, times the sine of the angle between them. Since d is a unit vector, that's the length of s times the sine. So comparing it with a fixed number would treat a long wall and a short one differently. Comparing it with 0.00001 times the length of s, as the code does, compares the sine with 0.00001 instead. It's an angle test, the same for every wall.

The third is the wall's ends. A u of exactly 0 or 1 counts as a hit. So a ray aimed straight at a corner that two walls share should hit both, at the same t. Rounding can spoil that, as the FAQ explains.

The fourth is a ray that starts on a wall. Its t for that wall is 0, give or take a rounding error, so raySegment may well report a hit right at the start. A ray cast has to deal with that, as the next section shows.

Casting a Ray

One ray against one segment answers whether the ray hits that wall. A ray cast asks the more useful question: of all the walls, which does the ray hit first? That's the test in a loop, keeping the nearest hit:

// The ray cast: test every wall, and keep the nearest hit. Hits
// closer than a hundredth of a pixel don't count, so that a beam
// can start on a wall without hitting it.
float nearest = 1e9f;
float hitU = 0.0f;
int hitWall = -1;
for (int i = 0; i < (int)walls.size(); ++i)
{
    float t = 0.0f, u = 0.0f;
    if (raySegment(origin, dir, walls[i].a, walls[i].b, t, u) &&
        t > 0.01f && t < nearest)
    {
        nearest = t;
        hitU = u;
        hitWall = i;
    }
}
Vec2 beamEnd = origin + dir * (hitWall >= 0 ? nearest : 2000.0f);

In the preceding code, every wall is tested, and the smallest t so far is kept, with its u and the wall's number. Since t is a distance in pixels, comparing them finds the nearest hit with no extra work. After the loop, hitWall is the wall the beam hits first, or −1 for a clear shot, and beamEnd is where the beam stops. That's the origin plus the direction times the distance: the ray's own parametric form, at the hit. A miss runs the beam 2,000 pixels, off the screen.

Notice that the loop ignores any hit at a t of 0.01 or less, a hundredth of a pixel. Laser's beam never starts on a wall, but a reflected one would, on the wall it bounced off. Its t for that wall would be 0, give or take a rounding error. Without the minimum, it could hit that wall again at once, and never leave it.

Building Laser

Laser fires a beam from a fixed point toward the mouse. It stops at the first wall it meets. That wall lights up, drawn as an arrow from its first end, a, to its second, b. The wall's line is carried on past its ends, faintly, with the perpendicular from the origin to that line, and its foot. The readout gives the beam's t and u, and the origin's signed distance from the wall's line.

Get the code. The complete project is in the Laser folder of the book's repository.

Laser starts from the skeleton, without the timing, since nothing moves by itself. It reuses drawGrid, fillCircle, drawArrow, drawDashed, fmt2 and setColor. Its Vec2.h is Shape Gallery's, since this chapter adds nothing to it. Here are its includes and colors, and Chapter 11's Segment:

#include <cmath>
#include <string>
#include <vector>
#include "Vec2.h"

constexpr int WINDOW_WIDTH  = 1000;
constexpr int WINDOW_HEIGHT = 700;

constexpr SDL_Color TEXT = { 235, 238, 242, 255 };
constexpr SDL_Color GREY = { 90, 100, 112, 255 };
constexpr SDL_Color BLUE = { 47, 111, 235, 255 };
constexpr SDL_Color AMBER = { 232, 89, 12, 255 };
constexpr SDL_Color GREEN = { 47, 158, 68, 255 };
constexpr SDL_Color FAINT = { 70, 78, 90, 255 };
constexpr SDL_Color SILVER = { 150, 158, 170, 255 };

// A segment: its two ends.
struct Segment
{
    Vec2 a;
    Vec2 b;
};

The two functions this chapter built come next. The rest of the demo comes in three parts: the walls and the aim, the ray cast, and the drawing.

The Walls and the Aim

The origin, the aim and the walls go after the font is loaded:

// The laser's origin, and the way it's aimed, as a unit vector.
const Vec2 origin = { 140.0f, 350.0f };
Vec2 dir = { 1.0f, 0.0f };

// The walls. The second and the third meet at a corner.
const std::vector<Segment> walls = {
    { { 400, 200 }, { 400, 60 } },
    { { 540, 250 }, { 760, 250 } },
    { { 760, 250 }, { 760, 420 } },
    { { 620, 500 }, { 880, 620 } },
    { { 300, 560 }, { 520, 610 } },
    { { 720, 110 }, { 900, 300 } },
};

The walls are a std::vector of segments. The second and the third meet at (760, 250), so you can aim at a corner. After the mouse is read, the laser aims at it:

// Aim at the mouse, unless it's on the origin, where there's no
// direction to aim in, and the last aim stays.
Vec2 mouse = { mx, my };
if ((mouse - origin).lengthSquared() > 1.0f)
    dir = (mouse - origin).normalized();

The direction is the vector from the origin to the mouse, normalized to a unit vector, so that t comes out in pixels. When the mouse is on the origin, there's no direction to normalize, so the last aim stays, the same caution with tiny vectors that the book has kept since Chapter 3. Then the ray cast runs, as Casting a Ray printed it.

Drawing

After the grid come the walls that weren't hit:

// The walls that weren't hit.
setColor(renderer, SILVER);
for (int i = 0; i < (int)walls.size(); ++i)
{
    if (i == hitWall) continue;
    SDL_RenderLine(renderer, walls[i].a.x, walls[i].a.y,
                   walls[i].b.x, walls[i].b.y);
}

The continue skips the hit wall, which is drawn next, with everything that goes with it:

// The hit wall: its line carried on past its ends, faintly, then
// the wall as an arrow from a to b, and the perpendicular from the
// origin to the line, with its foot.
float side = 0.0f;
if (hitWall >= 0)
{
    const Segment& w = walls[hitWall];
    Vec2 along = (w.b - w.a).normalized();
    drawDashed(renderer, w.a - along * 1500.0f, w.b + along * 1500.0f,
               FAINT);
    drawArrow(renderer, w.a, w.b, GREEN);
    side = signedDistance(origin, w.a, w.b);
    Vec2 foot = origin - along.perp() * side;
    drawDashed(renderer, origin, foot, AMBER);
    setColor(renderer, AMBER);
    fillCircle(renderer, foot, 4.0f);
}

In the preceding code, along is the wall's unit direction. The faint dashes run 1,500 pixels past each end, which is far enough to cross the window at any angle, so you can see the wall's whole line. The wall itself is a green arrow, from a to b, so that its right and left are clear. Then the signed distance from the origin to the line is worked out, and the foot is the origin, stepped back along the unit normal by that distance, as The Foot of the Perpendicular found. Here, the unit normal is along.perp(), the same vector signedDistance uses. An amber dashed line runs from the origin to the foot.

Then the beam, the origin, and the hit:

// The beam, the origin, and where the beam hit.
setColor(renderer, BLUE);
SDL_RenderLine(renderer, origin.x, origin.y, beamEnd.x, beamEnd.y);
fillCircle(renderer, origin, 6.0f);
if (hitWall >= 0)
{
    setColor(renderer, GREEN);
    fillCircle(renderer, beamEnd, 6.0f);
}

Last come the readout and the controls:

// The readout: where the beam hit, and the origin's side of that
// wall's line, and its distance from it.
if (hitWall >= 0)
{
    drawText(renderer, font,
             "wall " + std::to_string(hitWall) + " hit: t = " +
             std::to_string(std::lround(nearest)) + " px, u = " +
             fmt2(hitU), 12, 10, TEXT);
    drawText(renderer, font,
             "the origin is " +
             std::to_string(std::lround(std::fabs(side))) +
             " px from the wall's line, on its " +
             (side > 0.0f ? "right" : "left"), 12, 30, SILVER);
}
else
{
    drawText(renderer, font, "no hit: the beam leaves the window",
             12, 10, TEXT);
}
drawText(renderer, font, "[Move the mouse] aim   [Esc] quit",
         12, WINDOW_HEIGHT - 26, GREY);

The readout names the wall by its place in the vector, from 0, and gives t in whole pixels and u to two places. The second line gives the distance without its sign, by std::fabs, and says right or left from the sign.

Trying It Out

Run the demo, and sweep the mouse around the room. The next image shows Laser aimed at the wall at the bottom left.

The beam hits wall 4 at a t of 367 pixels, and a u of 0.55, just past halfway along it. The foot of the perpendicular from the origin isn't on the wall at all: it's on the wall's line, carried on past the wall's first end. That's the difference between a line and a segment, which Chapter 13 takes up. The origin is 169 pixels from the line, on its left, as you look along the green arrow.

Some things to try:

• Sweep the beam across the corner where walls 1 and 2 meet. The wall's number changes, and u jumps from 1 to 0, but t hardly moves.
• Sweep the beam along a wall's length, and watch u run from 0 to 1.
• Aim between two walls, at the edge of one, and watch u reach 0 or 1 just as the beam slips past.

Then aim at each wall in turn, and watch the side change. Walls 0 and 4 have the origin on their left, and the rest have it on their right. Each wall's arrow shows which way it runs, and so which side is which.

FAQ

Q) Why does my beam sometimes slip through where two walls meet?

A) Because of rounding. Aimed exactly at a shared corner, the beam's u for one wall should be exactly 1, and for the other exactly 0. A float can land a hair outside both, so that each wall reports a miss. The usual cure is to accept a u a tiny amount past each end: u >= -0.0001f && u <= 1.0001f. The walls then overlap at the corner by a fraction of a pixel, and nothing slips through.

Q) What if I use the vector to the target as the direction, instead of a unit vector?

A) Then t measures in lengths of that vector, and that's a neat trick. Use the vector from a guard to the player as d, and the player is at a t of exactly 1. Any wall with a t from 0 to 1 is in the way. That's a line-of-sight test, which is how many games decide whether a guard can see the player.

Q) How do games cast rays against thousands of walls?

A) By not testing most of them. A game first finds the walls that could possibly be hit, the ones in the cells of a grid that the ray passes through, or whose bounding boxes it crosses, and only tests those properly. Chapter 19 builds that kind of grid. The ray-against-segment test itself stays the same.

Q) Can a ray hit a circle, or a box?

A) Yes, and Chapter 17 works out both. A ray against a circle comes from putting the ray's parametric form into the circle's equation, which gives a quadratic in t. A ray against a box tests the box's sides, or uses a quicker trick with its slabs. Both answer the same question as this chapter: how far along the ray is the first hit.

Exercises

The first three exercises need only a pencil. The others change Laser.

1. Line and segment (paper). Find the distance from P (4, 1) to the line through A (0, 0) and B (0, 5), and where its foot is. Then do the same for P (4, 7). For which point is the foot on the segment from A to B?
2. Signed distance (paper). For A (0, 0), B (4, 3) and P (0, 5), find the signed distance from P to the line, which side P is on, and the foot of the perpendicular.
3. A ray by hand (paper). A ray starts at (0, 0), heading along (0.6, 0.8). A wall runs from (0, 10) to (10, 0). Find the denominator, t and u. Does it hit, and where?
4. Mirrors (code). Make every wall a mirror. At each hit, bounce the beam with Chapter 10's reflect, using the wall's unit normal. Then cast again from the hit point, for up to five bounces. What goes wrong if you take out the loop's minimum t?
5. Line of sight (code). Add a target that the mouse can drag. Draw it green when no wall blocks the line from the origin to it, and red when one does, using the trick from the FAQ.

For the code exercises, work on a copy of the demo's folder, so that the original stays as the chapter describes it.

AI Exercise (Optional)

A ray cast is the heart of one of the prettiest effects in 2D games: lights that cast shadows. Shine a light from a point, and the area it reaches is a polygon whose edges are where its rays stop. With an AI's help, you can turn Laser into a lamp. Open your AI chatbot of choice, and try a prompt like this:

"I have a C++ demo using SDL3, with a struct Segment of two Vec2 ends, a vector of wall segments, and a function raySegment(O, d, A, B, t, u) that returns true when a ray from O along the unit vector d hits the segment from A to B, filling in t, the distance along the ray, and u, the fraction along the wall. Please make the mouse a light. Add the window's four edges as walls. For every wall end, cast three rays from the mouse, toward the end and toward it turned by plus and minus 0.0001 radians, and keep each ray's nearest hit. Sort the hits by their angle around the mouse, and fill the triangles between the mouse and each pair of neighboring hits with a soft yellow, using SDL_RenderGeometry. Explain why the rays need the two tiny extra angles."

That prompt describes your walls and your ray test, so the AI builds the lighting from them, instead of a library of its own. It asks for the light's edges from the walls' ends, since that's where shadows begin and end, which is the whole trick. And it asks about the tiny extra angles, which are the part people find hardest to see.

Then move the light around, and watch the shadows swing. If the lit area has gaps or spikes, check the sorting: the angles come from atan2, from Chapter 5, and two hits at the same angle must be in the right order. Then try two lights, and draw both areas, faintly, on top of each other.

Summary

A line can be written three ways. Parametric form, A + t × (B - A), makes points along it, and the range of t decides between segment, ray and line. Implicit form, n · (P - A) = 0, tests points against it. The cross product (B - A) × (P - A) is the implicit form's dot product with the normal (B - A).perp(). Divided by the base's length, it's the signed distance from P to the line, and on the screen, a positive one means P is on the right of A to B. Stepping back along the unit normal by that distance gives the foot of the perpendicular. A ray meets a segment where O + t × d = A + u × s, and crossing with s and with d solves for t and u, over the shared denominator d × s, which is zero for parallel lines. A ray cast keeps the nearest hit over all the walls, ignoring any too close to its start to count. Laser drew it all. In Chapter 13, the question turns around: not where a line goes, but which point of a shape is nearest to a given point.