3. Length, Distance and Normalization

In chapter 2 we learned that a vector is both a list of numbers and an arrow.
An arrow has two properties you can see immediately: how long it is, and which way it points.
In this chapter we learn how to measure the first one, and how to separate the two from each other.

This sounds like a small thing, but a graphics programmer does it constantly.
How far is the enemy from the player?
Which direction is the light coming from?
Why does my character run faster when I walk diagonally?
All of these questions are answered with three small functions: length, distance and normalize.

3.1 The idea: how long is an arrow?

Imagine you walk 3 meters east and then 4 meters north.
You have walked 7 meters in total, but how far are you from where you started, in a straight line?
That straight line is the arrow 𝐯=(3,4), and its length is what we want.

The vector v = 3, 4 as the hypotenuse of a right triangle

Look at the picture.
The arrow, the horizontal step and the vertical step form a right triangle.
The arrow is the long side (the hypotenuse), so we can use the Pythagorean theorem from chapter 1.

3.2 What the formula is

The length of a vector is written with double vertical bars: ‖𝐯‖.
I read it as "the length of v" (other names you will see: magnitude, norm).
We use double bars so it doesn't get mixed up with the absolute value |s| of a single number, which we will also need in this chapter.

For a 2D vector 𝐯=(vx,vy):

‖𝐯‖=vx2+vy2

For a 3D vector 𝐯=(vx,vy,vz):

‖𝐯‖=vx2+vy2+vz2

And in general, for a vector with n components, using the sigma notation from chapter 1:

‖𝐯‖=v12+v22+⋯+vn2=∑i=1nvi2

In words: square every component, add the squares up, take the square root.
That's it.
Since squares are never negative, the length is never negative either, and it is zero only for the zero vector.

The distance between two points 𝐚 and 𝐛 is the length of the arrow from one to the other:

d(𝐚,𝐛)=‖𝐛−𝐚‖

A unit vector is a vector of length exactly 1.
We mark unit vectors with a little hat: 𝐯^ (read "v hat").
Turning any non-zero vector into a unit vector pointing the same way is called normalization:

𝐯^=𝐯‖𝐯‖=1‖𝐯‖𝐯

Those are all the formulas of this chapter.
Now let's see why they work.

3.3 How it works

3.3.1 Length in 2D

For 𝐯=(3,4) the right triangle in the picture has legs 3 and 4.
Pythagoras says the square of the hypotenuse equals the sum of the squares of the legs:

‖𝐯‖2=32+42=9+16=25‖𝐯‖=25=5

So you are exactly 5 meters from where you started.
Negative components work the same way, because squaring removes the sign: (−3,4) also has length 9+16=5.
That makes sense, since walking 3 meters west instead of east doesn't change how far you end up.

3.3.2 Length in 3D: Pythagoras twice

In 3D the arrow doesn't lie in a flat triangle anymore, but we can split the problem in two.
Take 𝐯=(2,3,6) and picture a box that is 2 wide (x), 3 high (y) and 6 deep (z).
The arrow goes from one bottom corner O to the opposite top corner P.

A 2 by 3 by 6 box: O to Q across the floor, Q to P straight up, O to P is v

Step 1: walk across the floor from O to Q.
The floor is a flat rectangle, 2 by 6, so Pythagoras gives the floor diagonal f:

f2=22+62=4+36=40

Step 2: from Q, go straight up 3 to reach P.
The floor diagonal and the vertical edge are at a right angle, so we have another right triangle with legs f and 3:

‖𝐯‖2=f2+32=40+9=49‖𝐯‖=49=7

Notice that we never needed f itself (it's 40≈6.3246, an ugly number).
We only needed f2=22+62, and then we added 32.
So the total is simply 22+32+62, which is the 3D formula.

3.3.3 More dimensions

The same trick keeps working.
Each extra component adds one more right angle and one more square under the root.
We can't draw 4D, but we can calculate it: for 𝐮=(1,2,2,4),

‖𝐮‖=12+22+22+42=1+4+4+16=25=5

In graphics we rarely need the length of a 4D vector (we'll meet 4D vectors properly in chapter 9), but in data science vectors with hundreds of components are normal, and the formula doesn't change.

3.3.4 Distance between two points

In chapter 2 we saw that 𝐛−𝐚 is the arrow that starts at point 𝐚 and ends at point 𝐛.
The distance between the points is just the length of that arrow.

Let 𝐚=(1,2,3) and 𝐛=(4,6,15).

𝐛−𝐚=(4−1,6−2,15−3)=(3,4,12)‖𝐛−𝐚‖=32+42+122=9+16+144=169=13

It doesn't matter which point you subtract from which.
𝐚−𝐛=(−3,−4,−12) points the other way, but the squares are the same, so the distance is still 13.

3.3.5 Squared length and squared distance

A square root is noticeably slower to compute than an addition or a multiplication.
One square root doesn't matter, but a game might compare distances millions of times per frame.

Here is the trick: if two lengths are both non-negative, then the bigger one also has the bigger square.
So if you only want to compare distances, you can compare the squares and skip the root completely.

Example: is an enemy within 10 units of the player at the origin?
Instead of checking d<10, check d2<102=100.

Enemy d2 Compare with 100 Result
(6,0,7) 36+0+49=85 85<100 inside
(9,0,5) 81+0+25=106 106>100 outside

No square root anywhere.
Just remember to square the radius too; comparing d2 with 10 instead of 100 is a classic bug.

3.3.6 Scaling a vector scales its length

What happens to the length if we multiply a vector by a number s (scalar multiplication from chapter 2)?

Take 𝐯=(2,3,6), which has length 7, and multiply by 3:

‖3𝐯‖=‖(6,9,18)‖=36+81+324=441=21=3×7

Now take 𝐰=(3,4), length 5, and multiply by −2:

‖−2𝐰‖=‖(−6,−8)‖=36+64=100=10=2×5

The length got multiplied by 2, not by −2.
The minus sign flipped the arrow around, but a flipped arrow is just as long.
This is where the absolute value comes in: |s| means "s without its minus sign", so |−2|=2 and |3|=3.
The rule is:

‖s𝐯‖=|s|‖𝐯‖

Why it works: every component gets multiplied by s, so every square gets multiplied by s2.
We can pull s2 out of the sum, and s2=|s|.

3.3.7 Normalization

The rule above is the key to normalization.
If a vector has length L and we multiply it by 1L, its new length is 1L×L=1.
And since 1L is positive, the direction doesn't change.

Example with 𝐰=(3,4), length 5:

𝐰^=15(3,4)=(0.6,0.8)

Check: 0.62+0.82=0.36+0.64=1=1.

Example with 𝐯=(2,3,6), length 7:

𝐯^=17(2,3,6)=(27,37,67)≈(0.2857,0.4286,0.8571)

Check: (27)2+(37)2+(67)2=4+9+3649=4949=1.

w = 3, 4 and its unit vector ŵ = 0.6, 0.8

3.3.8 Length times direction

Normalization lets us split any non-zero vector into two independent pieces of information:

𝐯=‖𝐯‖𝐯^

The length says "how much", the unit vector says "which way".
For a velocity, that's speed times direction.
Example: a ball moving with velocity (6,0,8) meters per second.
Its speed is 36+0+64=10 m/s, its direction is (0.6,0,0.8), and indeed 10×(0.6,0,0.8)=(6,0,8).

This split is extremely useful in games, because you usually want to control the two parts separately.
The AI decides where to go (a direction), the character stats decide how fast (a speed), and you multiply them at the end.

3.3.9 The zero-vector problem

There is one vector we can't normalize: the zero vector 𝟎=(0,0,0).
Its length is 0, and the formula asks us to divide by 0.
In floating-point math, 0/0 doesn't crash; it produces a special value called NaN ("not a number").
NaN is poisonous: any calculation that touches it also becomes NaN.
One NaN in a position and your model vanishes from the screen, or your physics object teleports to nowhere.

And it's not a rare case.
The player stands exactly on top of the target, the input stick is centered, two vertices of a broken mesh are in the same place.
The zero vector simply has no direction, so there is no correct answer.

Our linalg.hh handles it the simple way: normalize of the zero vector returns the zero vector.
That's safe (no NaN), but it means you should be aware that "normalized" vectors can still be zero in that case.
Shader normalize functions do NOT protect you: in GLSL, Slang and HLSL, normalizing a zero vector gives an undefined result, which usually means NaN.

3.4 Use in graphics programming

3.4.1 The diagonal-movement bug

This is the most famous bug in this chapter, and almost every beginner game has it.
The player presses D to move right and W to move forward.
In our right-handed system, right is +X and forward is −Z, so the code builds an input vector like this:

 W only: ( 0, 0, -1)   length 1
 D only: ( 1, 0,  0)   length 1
 W + D : ( 1, 0, -1)   length 1.4142  <- too long!

The input vector 1, 0, −1 for W + D is longer than 1

Then it does position = position + speed * input * dt.
With a speed of 5, moving straight gives 5 units per second, but diagonally:

‖5×(1,0,−1)‖=512+02+(−1)2=52≈7.0711

The player is about 41% faster when moving diagonally.
Speedrunners love this bug; game designers don't.

The fix is to normalize the input direction before multiplying by the speed:

𝐝^=(1,0,−1)2≈(0.7071,0,−0.7071)

Now ‖5𝐝^‖=5 in every direction.
Note that the zero-vector rule matters here: if no key is pressed, the input is (0,0,0), and our normalize returns zero instead of NaN, so the player simply stands still.

With an analog stick, normalizing would make a slight tilt as fast as a full tilt. There you usually only normalize if the length is greater than 1, so small tilts still mean walking slowly.

3.4.2 Direction from A to B

"Make this thing move towards that thing" is the bread and butter of game code: enemies chasing the player, homing missiles, bullets fired at a target, a camera following a character.
The recipe is always the same:

  1. Subtract: 𝐛−𝐚 is the arrow from A to B.
  2. Normalize: divide it by its length to get the direction 𝐝^, length 1.
  3. Multiply by speed and time, and add to the position.

Worked example: an enemy at 𝐞=(2,0,1) chases a player at 𝐩=(5,0,5) with speed 2 units per second, and this frame lasts Δt=0.5 seconds.

𝐩−𝐞=(3,0,4),‖𝐩−𝐞‖=9+0+16=5𝐝^=15(3,0,4)=(0.6,0,0.8)𝐞new=𝐞+2×0.5×𝐝^=(2,0,1)+(0.6,0,0.8)=(2.6,0,1.8)

The enemy moved exactly 1 unit towards the player, no matter how far away the player is.
Without the normalization, it would move faster when the player is far away and crawl when the player is close, which is sometimes what you want (a smooth follow camera that slows down as it arrives), but usually not.

3.4.3 Light directions and normals

Lighting needs two directions at every point of a surface:

  • the light direction 𝐥: from the surface point towards the light, normalize(lightPos - worldPos);
  • the normal 𝐧: the direction the surface is facing (perpendicular to it).

In the next chapter we will compute brightness from these two vectors with the dot product.
That calculation only works if both vectors have length 1.
If they are longer, the surface gets brighter for no reason; if shorter, darker.

There is a trap here.
Normals are stored per vertex, and the GPU blends (interpolates) them across the triangle with exactly the lerp from chapter 2.
Halfway between two unit normals (1,0,0) and (0,1,0) the blended normal is:

12(1,0,0)+12(0,1,0)=(0.5,0.5,0),‖(0.5,0.5,0)‖=0.5≈0.7071

That is no longer a unit vector.
So the very first thing almost every lighting fragment shader does is normalize the normal again.

3.4.4 Distance-based effects

Many effects fade with distance.
In shaders, length, distance and normalize are built in, in Slang, GLSL and HLSL alike:

// 1 near the light, 0 at radius and beyond
float attenuation(float3 lightPos, float3 worldPos, float radius) {
  float d = distance(lightPos, worldPos);
  float a = saturate(1.0 - d / radius);
  return a * a;
}

// 1 = no fog, 0 = completely fogged
float fogFactor(float3 cameraPos, float3 worldPos, float fogStart, float fogEnd) {
  float d = distance(cameraPos, worldPos);
  return saturate((fogEnd - d) / (fogEnd - fogStart));
}
// 1 near the light, 0 at radius and beyond
float attenuation(vec3 lightPos, vec3 worldPos, float radius) {
  float d = distance(lightPos, worldPos);
  float a = clamp(1.0 - d / radius, 0.0, 1.0);
  return a * a;
}

// 1 = no fog, 0 = completely fogged
float fogFactor(vec3 cameraPos, vec3 worldPos, float fogStart, float fogEnd) {
  float d = distance(cameraPos, worldPos);
  return clamp((fogEnd - d) / (fogEnd - fogStart), 0.0, 1.0);
}
// 1 near the light, 0 at radius and beyond
float attenuation(float3 lightPos, float3 worldPos, float radius) {
  float d = distance(lightPos, worldPos);
  float a = saturate(1.0 - d / radius);
  return a * a;
}

// 1 = no fog, 0 = completely fogged
float fogFactor(float3 cameraPos, float3 worldPos, float fogStart, float fogEnd) {
  float d = distance(cameraPos, worldPos);
  return saturate((fogEnd - d) / (fogEnd - fogStart));
}

saturate(x) in Slang and HLSL and clamp(x, 0.0, 1.0) in GLSL both squeeze a number into the range 0 to 1.

Let's check them with numbers.
A light at (0,4,0) with radius 10 shines on the point (3,0,0):

d=‖(3,−4,0)‖=5,a=1−510=0.5,a2=0.25

So the point gets a quarter of the light's full brightness.
Squaring makes the falloff gentle at the edge, which looks closer to real light than a straight line.
(Real light falls off with 1d2, the inverse-square law, but that never quite reaches zero, so games often use a windowed version like this one that ends at a fixed radius.)

For fog with start 10 and end 50, a point 30 units from the camera gets 50−3050−10=2040=0.5, so we mix half fog color and half object color with lerp/mix from chapter 2.

Level of detail (LOD) uses distance on the CPU side: close objects get the detailed mesh, far ones get a cheaper mesh.
Since we only compare against thresholds, this is a perfect place for squared distances: compare d2 with 202=400, 502=2500 and so on.

3.4.5 A circle and a vignette in a fragment shader

Texture coordinates (UVs) go from 0 to 1 across the screen, so the center of the screen is (0.5,0.5).
The distance from the center is length(uv - 0.5): 0 at the center, 0.5 at the middle of each edge, and 0.52+0.52≈0.7071 in the corners.
Every pixel with the same distance lies on a circle, so with this one number we can draw circles, rings, spotlights or a vignette (a darkening towards the edges).

struct Params {
  float2 resolution; // window size in pixels
};
ConstantBuffer<Params> params;

[shader("fragment")]
float4 fragmentMain(float2 uv : TEXCOORD0) : SV_Target {
  float2 p = uv - 0.5;
  p.x *= params.resolution.x / params.resolution.y; // keep the circle round
  float d = length(p);
  float vignette = 1.0 - smoothstep(0.3, 0.7, d);
  float3 color = float3(1.0, 0.8, 0.6) * vignette;
  return float4(color, 1.0);
}
#version 450

layout(location = 0) in vec2 uv;
layout(location = 0) out vec4 outColor;

layout(set = 0, binding = 0) uniform Params {
  vec2 resolution; // window size in pixels
};

void main() {
  vec2 p = uv - 0.5;
  p.x *= resolution.x / resolution.y; // keep the circle round
  float d = length(p);
  float vignette = 1.0 - smoothstep(0.3, 0.7, d);
  vec3 color = vec3(1.0, 0.8, 0.6) * vignette;
  outColor = vec4(color, 1.0);
}
struct Params {
  float2 resolution; // window size in pixels
};
ConstantBuffer<Params> params;

float4 fragmentMain(float2 uv : TEXCOORD0) : SV_Target {
  float2 p = uv - 0.5;
  p.x *= params.resolution.x / params.resolution.y; // keep the circle round
  float d = length(p);
  float vignette = 1.0 - smoothstep(0.3, 0.7, d);
  float3 color = float3(1.0, 0.8, 0.6) * vignette;
  return float4(color, 1.0);
}

smoothstep(a, b, x) returns 0 when x is below a, 1 when x is above b, and a smooth S-shaped curve in between.
So pixels closer than 0.3 to the center keep their full color, pixels further than 0.7 become black, and at d=0.5 we get exactly half: 1−0.5=0.5.
The line with the resolution is important on a non-square window: UVs are 0 to 1 in both directions, so without it the "circle" would be stretched into an ellipse on a 16:9 screen.

3.5 Other uses

Length and distance are everywhere outside graphics too.

  • Maps and GPS: the straight-line ("as the crow flies") distance between two places on a local, flat map is exactly our distance formula. For long distances the Earth's curvature matters and you need spherical formulas instead.
  • k-nearest neighbors: a simple machine-learning method that classifies a new data point by looking at the k closest known points, where "closest" is our distance formula in many dimensions.
  • Normalizing feature vectors: in data science, vectors (for example word counts of a document) are often normalized so that a long document and a short document about the same topic look similar. We will use this in chapter 4 for cosine similarity.
  • Signal strength (RMS): in audio, the loudness of a block of samples is often measured as the RMS (root mean square): the length of the sample vector divided by n. For the samples (1,7,−1,−7) the length is 1+49+1+49=10 and the RMS is 10/4=5.
  • Physics: speed is the length of the velocity vector, and the strength of a force is the length of the force vector.
  • Error measurement: "how far is my prediction from the real answer" is often the distance between two vectors.

3.6 Code

Now let's add the functions to linalg.hh.
Put them below the vector operators from chapter 2:

// 長さ・距離・正規化 / length, distance, normalization (chapter 3)
inline float length(Vec2 v) { return std::sqrt(v.x * v.x + v.y * v.y); }
inline float length(Vec3 v) { return std::sqrt(v.x * v.x + v.y * v.y + v.z * v.z); }
inline float distance(Vec3 a, Vec3 b) { return length(b - a); }

inline Vec3 normalize(Vec3 v) {
  float len = length(v);
  if (len == 0.0f) return {0.0f, 0.0f, 0.0f}; // ゼロベクトルは正規化出来ない / cannot normalize zero
  return (1.0f / len) * v;
}

A few remarks:

  • std::sqrt comes from <cmath>, which the header already includes since chapter 1.
  • distance is literally the definition: the length of b - a, using the subtraction operator from chapter 2.
  • normalize checks for the zero vector before dividing. Instead of dividing each component by len, it computes 1.0f / len once and multiplies, using the scalar multiplication from chapter 2.
  • The exact comparison len == 0.0f only catches the true zero vector. A vector like (1e-30, 0, 0) still gets normalized; that's fine for this tutorial.

Here is a small test program, main.cc.
It also defines a distanceSquared helper for the comparison trick (it is not part of the header):

#include "linalg.hh"
#include <cstdio>

// Squared distance: no square root needed for comparisons.
float distanceSquared(Vec3 a, Vec3 b) {
  Vec3 d = b - a;
  return d.x * d.x + d.y * d.y + d.z * d.z;
}

int main() {
  Vec2 a{3.0f, 4.0f};
  Vec3 v{2.0f, 3.0f, 6.0f};
  printf("length(a)      = %g\n", length(a));
  printf("length(v)      = %g\n", length(v));

  Vec3 p{1.0f, 2.0f, 3.0f};
  Vec3 q{4.0f, 6.0f, 15.0f};
  printf("distance(p, q) = %g\n", distance(p, q));

  Vec3 n = normalize(v);
  printf("normalize(v)   = (%.4f, %.4f, %.4f)\n", n.x, n.y, n.z);
  printf("length of that = %.4f\n", length(n));

  // W + D pressed: right (+X) and forward (-Z) at the same time
  Vec3 input{1.0f, 0.0f, -1.0f};
  float speed = 5.0f;
  printf("raw speed      = %.4f\n", length(speed * input));
  printf("fixed speed    = %.4f\n", length(speed * normalize(input)));

  // An enemy chases the player
  Vec3 enemy{2.0f, 0.0f, 1.0f};
  Vec3 player{5.0f, 0.0f, 5.0f};
  Vec3 dir = normalize(player - enemy);
  enemy = enemy + (2.0f * 0.5f) * dir; // speed 2, dt 0.5
  printf("enemy moved to = (%g, %g, %g)\n", enemy.x, enemy.y, enemy.z);

  // Is it within 10 units? Compare squares: 10 * 10 = 100
  Vec3 origin{};
  Vec3 e1{6.0f, 0.0f, 7.0f};
  Vec3 e2{9.0f, 0.0f, 5.0f};
  float d1 = distanceSquared(origin, e1);
  float d2 = distanceSquared(origin, e2);
  printf("e1: %g -> %s\n", d1, d1 < 100.0f ? "inside" : "outside");
  printf("e2: %g -> %s\n", d2, d2 < 100.0f ? "inside" : "outside");

  Vec3 zero = normalize(Vec3{});
  printf("normalize(0)   = (%g, %g, %g)\n", zero.x, zero.y, zero.z);
  return 0;
}

Expected output:

length(a)      = 5
length(v)      = 7
distance(p, q) = 13
normalize(v)   = (0.2857, 0.4286, 0.8571)
length of that = 1.0000
raw speed      = 7.0711
fixed speed    = 5.0000
enemy moved to = (2.6, 0, 1.8)
e1: 85 -> inside
e2: 106 -> outside
normalize(0)   = (0, 0, 0)

Every line matches a worked example from this chapter.
If you want to see a NaN with your own eyes, try printf("%f\n", 0.0f / 0.0f); (some systems print nan, others -nan).

3.7 Summary

  • The length ‖𝐯‖ is the square root of the sum of the squared components. It comes straight from Pythagoras, applied once per extra dimension.
  • The distance between two points is ‖𝐛−𝐚‖.
  • To compare distances, compare squared distances and skip the square root (and square the threshold too).
  • Scaling a vector by s scales its length by |s|.
  • A unit vector has length 1. Normalizing means dividing by the length: 𝐯^=𝐯/‖𝐯‖.
  • Every non-zero vector is length times direction: 𝐯=‖𝐯‖𝐯^.
  • The zero vector can't be normalized. Our header returns zero; shaders give garbage (usually NaN).
  • Normalize movement input (diagonal bug), directions to targets, light directions and interpolated normals.

3.8 Challenges

  1. ★ Compute the length of (5,12), (−8,6) and (1,4,8).
  2. ★ Compute the distance between the points (2,−1,3) and (4,5,6).
  3. ★ Normalize (0,−3,4) and check that the result has length 1.
  4. ★ A vector has length 4. What is the length of −3 times that vector? What is the length of 14 times it?
  5. ★★ Add float length(Vec4 v) and Vec2 versions of distance and normalize to your header (the header already has length(Vec2) and float * Vec2). Check that length(Vec4{1, 2, 2, 4}) prints 5 and that normalizing Vec2{3, 4} prints (0.6, 0.8).
  6. ★★ Write a function Vec3 moveTowards(Vec3 from, Vec3 to, float maxStep) that moves at most maxStep towards to and never overshoots it (if the target is closer than maxStep, return to). Starting at {0, 0, 0} with target {3, 0, 4} and maxStep = 2, calling it repeatedly should print (1.2, 0, 1.6), (2.4, 0, 3.2), (3, 0, 4), (3, 0, 4).
  7. ★★★ An analog stick returns values from −1 to 1 on each axis, so pushing it into a corner can return (1,1). Design input handling that keeps small tilts slow, never lets the diagonal be faster than straight movement, and never produces NaN. What should happen for a stick input of (0.3,0.4)? And for (1,1)?


コメント(0)

まだコメントはありません。