geom

import geom from "geom";
import math3d from "math3d";

let wall = geom.aabb2(math3d.vec2(4.0, 0.0), math3d.vec2(5.0, 3.0));
let ray = geom.ray2(math3d.vec2(0.0, 1.0), math3d.vec2(1.0, 0.0));
let hit = ray.cast_aabb(wall);              // ?Hit2: t 4, point (4, 1), normal (-1, 0)
let at: f32 = hit!.t;                       // 4

geom answers the questions a game asks of its shapes: do these touch, where does this ray hit, how far do I push this out, what is near this box. It works on math3d’s f32 vectors Vec2 and Vec3. It is pure (t1): only the polygon functions and the spatial structures allocate.

Coordinates are right-handed with y up, angles in radians. A polygon is a []const Vec2; counter-clockwise means a positive signed area with y up (on a y-down screen the same polygon looks clockwise).

Touching counts. Every overlap and containment test is inclusive: boxes sharing an edge overlap, a point on a circle is inside it. The one exception is the swept box (below).

Shapes

let box = geom.aabb2_around(math3d.vec2(0.0, 0.0), math3d.vec2(1.0, 1.0));   // -1..1
let tilted = geom.obb2(math3d.vec2(3.0, 0.0), math3d.vec2(1.0, 0.5), 0.5);
let floor = geom.plane(math3d.vec3(0.0, 1.0, 0.0), math3d.vec3(0.0, 0.0, 0.0));

plane makes the normal unit length (a zero normal traps); plane_from_points gives null for three points on a line.

Results

A test that can miss returns an optional:

A ray’s t is in units of dir: with a unit dir it is the distance. A ray that starts inside a shape hits it at t = 0, at its origin, with a zero normal.

Boxes

let player = geom.aabb2(math3d.vec2(0.0, 0.0), math3d.vec2(2.0, 2.0));
let crate = geom.aabb2(math3d.vec2(1.5, 0.5), math3d.vec2(4.0, 1.5));
let m = player.mtv(crate)!;           // normal (-1, 0), depth 0.5: push left by 0.5

mtv pushes along the axis of least overlap (on a tie, x).

Swept boxes

sweep gives the time of impact (t in 0..1 of vel), the normal of the face it meets, and the moving box’s centre at that moment:

let feet = geom.aabb2(math3d.vec2(0.0, 0.0), math3d.vec2(1.0, 1.0));
let wall = geom.aabb2(math3d.vec2(3.0, 0.0), math3d.vec2(4.0, 1.0));
let h = feet.sweep(math3d.vec2(4.0, 0.0), wall)!;    // t 0.5, normal (-1, 0)
let pos = h.point;                                   // the centre at impact: (2.5, 0.5)

It reports when the boxes would start to overlap with area. Boxes that only touch, or slide along each other, never hit, so a box standing on a floor can walk along it; pushing into the floor hits at t = 0 with the floor’s normal. Boxes already overlapping hit at t = 0 with a zero normal: separate them with mtv. Hitting a corner exactly takes the x face; only grazing a corner is no hit.

Circles and spheres

A circle whose centre is inside a box is pushed out through the nearest face. Spheres have the same methods without the MTVs.

Turned boxes and convex polygons

These use separating axes (each polygon’s edge normals). A polygon must be convex and have at least 3 points; fewer never overlap anything, and a concave one gives a wrong answer.

let tri = [math3d.vec2(0.0, 0.0), math3d.vec2(2.0, 0.0), math3d.vec2(0.0, 2.0)];
let sq = [math3d.vec2(0.75, 0.75), math3d.vec2(2.0, 0.75), math3d.vec2(2.0, 2.0), math3d.vec2(0.75, 2.0)];
let m = geom.convex_mtv(tri[0..3], sq[0..4])!;   // normal (-0.707, -0.707), depth 0.354

Rays and segments

let ground = geom.triangle(math3d.vec3(0.0, 0.0, 0.0), math3d.vec3(1.0, 0.0, 0.0), math3d.vec3(0.0, 1.0, 0.0));
let down = geom.ray3(math3d.vec3(0.25, 0.25, 1.0), math3d.vec3(0.0, 0.0, -1.0));
let h = down.cast_triangle(ground)!;     // t 1, point (0.25, 0.25, 0), normal (0, 0, 1)

• Planes and triangles are hit from either side; the normal faces the ray. Triangle edges and corners count (Möller–Trumbore).
• A ray hitting a box’s corner takes the earlier axis’s face (x, y, z).
• Parallel in 2D means exactly parallel: a ray along a segment, or two segments on one line, miss even when they overlap. In 3D a ray within EPSILON (1e-6, the sine of the angle) of a plane’s or triangle’s direction misses; the test doesn’t depend on scale.
• A zero-length segment is never crossed; a ray with a zero direction hits only a shape it starts in.

Closest points

Polygons

// an L: 2 x 1 below, 1 x 1 above on the left
let l = [math3d.vec2(0.0, 0.0), math3d.vec2(2.0, 0.0), math3d.vec2(2.0, 1.0),
         math3d.vec2(1.0, 1.0), math3d.vec2(1.0, 2.0), math3d.vec2(0.0, 2.0)];
let area = geom.polygon_area(l[0..6]);                      // 3
let inside = geom.polygon_contains(l[0..6], math3d.vec2(1.5, 1.5));   // false: the notch
let tris = geom.triangulate(l[0..6]);                       // 0 1 2, 0 2 3, 0 3 4, 0 4 5

• convex_hull starts at the leftmost point (the lowest of those), leaves out points on an edge, and keeps the lowest index of repeated points. A single point gives one index, points on one line the two ends.
• triangulate clips ears from any simple polygon, concave included, either winding. Every triangle comes out counter-clockwise, and none has zero area: a point on the line through its neighbours, or a repeated point, may be dropped, so you get at most n - 2 triangles. A polygon that crosses itself still gets triangles, but they may overlap.

Spatial structures

Two generators make a broadphase for your item type (an entity id, an index, a struct). The i64 ones are ready: geom.GridHash_i64 and geom.Quadtree_i64. For another type, call the generator once:

@tape { geom.gen_grid_hash(Entity); }      // GridHash_Entity, grid_hash_Entity_new

Both store copies of the items (strings and other managed values too), and a query is a loop over the items whose boxes overlap the query box:

for (id in grid.query(box)) { ... }

Queries don’t change the structure, so loops can nest; insert, remove or clear only after the loop.

Grid hash

For many moving objects: every frame, clear it, insert every object, then query.

var grid = geom.grid_hash_i64_new(32.0);      // cells 32 x 32
// each frame:
grid.clear();
for (e in entities) { grid.insert(e.id, e.box); }
for (other in grid.query(player.box.expand(4.0))) { ... }

For a broadphase, pairs() hands every overlapping pair to the narrow phase once, however many cells the two share; touching boxes count, as in overlaps. It is a loop like query, allocates nothing, and the indices are only good until the next insert or clear:

for (p in grid.pairs()) {
    collide(grid.get(p.a), grid.get(p.b));
}

Pick a cell about the size of a typical object. The grid has no bounds: cells are hashed. A box covering more than GRID_MAX_CELLS (64) cells, such as a level-wide trigger, goes into one list every query reads.

Quadtree

For objects that mostly stay put or move a little: insert once, move when they move.

var tree = geom.quadtree_i64_new(geom.aabb2(math3d.vec2(0.0, 0.0), math3d.vec2(4096.0, 4096.0)), 8, 4);
let h = tree.insert(42, coin_box);
tree.move(h, coin_box_next);
for (id in tree.query(view)) { draw(id); }
let gone = tree.remove(h);                   // 42

A handle stays valid until its item is removed (then it may be reused); using a handle that isn’t live traps. Items outside bounds still work: they live at the top and every query looks at them. A subtree that falls to capacity items merges back, so a tree that empties shrinks.

Last modified: 2026-11-04 15:49:19 UTC