Geometry Primitives

// internal/vec/shapes.go — create
package vec

import "math"

// Cross is the two-dimensional cross product, a.X·b.Y − a.Y·b.X: the
// signed area of the parallelogram the two vectors span. It is zero when
// they are parallel, and its sign says which side of a the vector b is on.
func (a Vec2) Cross(b Vec2) float64 {
	return a.X*b.Y - a.Y*b.X
}

// AABB is an axis-aligned box: its least corner and its greatest.
type AABB struct {
	Min, Max Vec2
}

// Circle is a centre and a radius.
type Circle struct {
	Centre Vec2
	R      float64
}

// Segment is the straight piece between two points.
type Segment struct {
	A, B Vec2
}

// Hit is what an overlap test reports when two shapes overlap: how far the
// first reaches into the second along the shortest way out, and that way,
// a unit vector pointing from the second toward the first, which is the
// direction to push the first to separate them.
type Hit struct {
	Depth  float64
	Normal Vec2
}

// OverlapAABB tests two boxes: four comparisons, and boxes that only touch
// along an edge do not overlap. The depth is the smallest of the four
// overlaps and the normal is along that axis, away from b.
func OverlapAABB(a, b AABB) (Hit, bool) {
	if a.Max.X <= b.Min.X || b.Max.X <= a.Min.X || a.Max.Y <= b.Min.Y || b.Max.Y <= a.Min.Y {
		return Hit{}, false
	}
	// The four overlaps: how far a's right edge is past b's left, and so on.
	left, right := a.Max.X-b.Min.X, b.Max.X-a.Min.X
	top, bottom := a.Max.Y-b.Min.Y, b.Max.Y-a.Min.Y
	h := Hit{Depth: left, Normal: Vec2{X: -1}}
	if right < h.Depth {
		h = Hit{Depth: right, Normal: Vec2{X: 1}}
	}
	if top < h.Depth {
		h = Hit{Depth: top, Normal: Vec2{Y: -1}}
	}
	if bottom < h.Depth {
		h = Hit{Depth: bottom, Normal: Vec2{Y: 1}}
	}
	return h, true
}

// OverlapCircles tests two circles by comparing the squared distance
// between their centres with the square of the radii's sum, so that no
// square root is taken unless they do overlap. Circles that only touch do
// not overlap. Two circles on one centre have no direction between them,
// and the normal is taken along x.
func OverlapCircles(a, b Circle) (Hit, bool) {
	d := a.Centre.Sub(b.Centre)
	reach := a.R + b.R
	d2 := d.Dot(d)
	if d2 >= reach*reach {
		return Hit{}, false
	}
	if d2 == 0 {
		return Hit{Depth: reach, Normal: Vec2{X: 1}}, true
	}
	dist := math.Sqrt(d2)
	return Hit{Depth: reach - dist, Normal: d.Scale(1 / dist)}, true
}

// Closest is the point of the box nearest to p: p itself when p is inside,
// otherwise p with each coordinate held to the box's range.
func (b AABB) Closest(p Vec2) Vec2 {
	return Vec2{
		X: math.Max(b.Min.X, math.Min(p.X, b.Max.X)),
		Y: math.Max(b.Min.Y, math.Min(p.Y, b.Max.Y)),
	}
}

// OverlapCircleAABB tests a circle against a box: the circle overlaps the
// box exactly when it overlaps the point of the box nearest its centre.
// When the centre is inside the box the nearest point is the centre and
// there is no direction to it, so the push is out through the nearest
// face, by the radius plus the distance to that face.
func OverlapCircleAABB(c Circle, b AABB) (Hit, bool) {
	p := b.Closest(c.Centre)
	if p == c.Centre {
		toLeft, toRight := c.Centre.X-b.Min.X, b.Max.X-c.Centre.X
		toTop, toBottom := c.Centre.Y-b.Min.Y, b.Max.Y-c.Centre.Y
		h := Hit{Depth: c.R + toLeft, Normal: Vec2{X: -1}}
		if toRight < toLeft && toRight <= toTop && toRight <= toBottom {
			h = Hit{Depth: c.R + toRight, Normal: Vec2{X: 1}}
		} else if toTop < toLeft && toTop <= toBottom {
			h = Hit{Depth: c.R + toTop, Normal: Vec2{Y: -1}}
		} else if toBottom < toLeft {
			h = Hit{Depth: c.R + toBottom, Normal: Vec2{Y: 1}}
		}
		return h, true
	}
	return OverlapCircles(c, Circle{Centre: p})
}

// Meet says how two segments lie: they cross at one point, they are
// parallel and apart, they lie on one line, or their lines cross somewhere
// off one segment or both.
type Meet uint8

const (
	Apart Meet = iota
	Crossing
	Parallel
	Collinear
)

// String names the way two segments meet.
func (m Meet) String() string {
	return [...]string{"apart", "crossing", "parallel", "collinear"}[m]
}

// Intersect finds where two segments cross. With d = B − A and e = D − C,
// the point A + t·d is on the second line when (C − A) × e = t·(d × e), and
// C + u·e is on the first when (C − A) × d = u·(d × e); the segments cross
// when both t and u are within [0, 1]. A zero d × e means the lines are
// parallel, and then a zero (C − A) × d means they are the same line.
func Intersect(s, o Segment) (Vec2, Meet) {
	d, e := s.B.Sub(s.A), o.B.Sub(o.A)
	ca := o.A.Sub(s.A)
	denom := d.Cross(e)
	if denom == 0 {
		if ca.Cross(d) == 0 {
			return Vec2{}, Collinear
		}
		return Vec2{}, Parallel
	}
	t := ca.Cross(e) / denom
	u := ca.Cross(d) / denom
	if t < 0 || t > 1 || u < 0 || u > 1 {
		return Vec2{}, Apart
	}
	return s.A.Add(d.Scale(t)), Crossing
}

go vet ./...

Each overlap test returns a Hit and a boolean. The boolean says whether the shapes overlap. The Hit only matters when the boolean is true.

OverlapAABB uses <= when it checks for separation, so touching boxes do not overlap. OverlapCircles uses the matching >= rule for touching rims.

OverlapCircleAABB reduces the box test to the nearest point on the box. Intersect checks for a zero cross product before it divides, so parallel and collinear segments get named instead of crashing the formula.

// cmd/motion/shapes.go — create
package main

import (
	"fmt"

	"github.com/hajimehoshi/ebiten/v2"
	"github.com/hajimehoshi/ebiten/v2/vector"

	"gez/internal/vec"
)

// The shapes lab keeps three fixed things, a box, a circle and a segment,
// and a probe under the arrow keys: a circle, the box that bounds it, and
// a segment from its centre. Every tick it runs the four overlap tests
// between probe and fixture and draws what each reports.
const probeR = 12.0

var (
	fixedBox     = vec.AABB{Min: vec.Vec2{X: 40, Y: 60}, Max: vec.Vec2{X: 120, Y: 120}}
	fixedCircle  = vec.Circle{Centre: vec.Vec2{X: 220, Y: 90}, R: 28}
	fixedSegment = vec.Segment{A: vec.Vec2{X: 130, Y: 160}, B: vec.Vec2{X: 300, Y: 40}}
	probeStart   = vec.Vec2{X: 160, Y: 100}
	probeArm     = vec.Vec2{X: 30, Y: -50} // the probe's segment, from its centre
)

// shapesLab keeps the probe's centre and nothing else; the probe's three
// shapes are built from it on every tick.
type shapesLab struct {
	probe vec.Vec2
}

func newShapesLab() *shapesLab {
	return &shapesLab{probe: probeStart}
}

// step moves the probe a pixel a tick. Space prints the four tests.
func (l *shapesLab) step(k keys) {
	var d vec.Vec2
	if k.left {
		d.X--
	}
	if k.right {
		d.X++
	}
	if k.up {
		d.Y--
	}
	if k.down {
		d.Y++
	}
	l.probe = l.probe.Add(d)
	if k.space {
		bb, cc, cb, okB, okC, okCB, cross, meet := l.hits()
		fmt.Printf("probe %v: box %s  circle %s  circle-box %s\n", l.probe, hitText(bb, okB), hitText(cc, okC), hitText(cb, okCB))
		if meet == vec.Crossing {
			fmt.Printf("segments %v at %v\n", meet, cross)
		} else {
			fmt.Printf("segments %v\n", meet)
		}
	}
}

// The probe's three shapes.
func (l *shapesLab) circle() vec.Circle {
	return vec.Circle{Centre: l.probe, R: probeR}
}

func (l *shapesLab) box() vec.AABB {
	r := vec.Vec2{X: probeR, Y: probeR}
	return vec.AABB{Min: l.probe.Sub(r), Max: l.probe.Add(r)}
}

func (l *shapesLab) segment() vec.Segment {
	return vec.Segment{A: l.probe, B: l.probe.Add(probeArm)}
}

// hits runs the four tests: probe box against the fixed box, probe circle
// against the fixed circle, probe circle against the fixed box, and probe
// segment against the fixed segment.
func (l *shapesLab) hits() (bb, cc, cb vec.Hit, okB, okC, okCB bool, cross vec.Vec2, meet vec.Meet) {
	bb, okB = vec.OverlapAABB(l.box(), fixedBox)
	cc, okC = vec.OverlapCircles(l.circle(), fixedCircle)
	cb, okCB = vec.OverlapCircleAABB(l.circle(), fixedBox)
	cross, meet = vec.Intersect(l.segment(), fixedSegment)
	return
}

// hitText is a hit as the printed line shows it: the depth and the way
// out, or a dash for no overlap.
func hitText(h vec.Hit, ok bool) string {
	if !ok {
		return "-"
	}
	return fmt.Sprintf("%.4f %v", h.Depth, h.Normal)
}

// depthText is a hit as the HUD shows it: the depth alone, since the
// picture draws the way out.
func depthText(h vec.Hit, ok bool) string {
	if !ok {
		return "-"
	}
	return fmt.Sprintf("%.4f", h.Depth)
}

func (l *shapesLab) draw(screen *ebiten.Image, h *hud) {
	bb, cc, cb, okB, okC, okCB, cross, meet := l.hits()
	// The fixtures, dim.
	vector.StrokeRect(screen, float32(fixedBox.Min.X), float32(fixedBox.Min.Y), float32(fixedBox.Max.X-fixedBox.Min.X), float32(fixedBox.Max.Y-fixedBox.Min.Y), 1, dimColor, false)
	vector.StrokeCircle(screen, float32(fixedCircle.Centre.X), float32(fixedCircle.Centre.Y), float32(fixedCircle.R), 1, dimColor, false)
	vector.StrokeLine(screen, float32(fixedSegment.A.X), float32(fixedSegment.A.Y), float32(fixedSegment.B.X), float32(fixedSegment.B.Y), 1, dimColor, false)
	// The probe, lit.
	b, s := l.box(), l.segment()
	vector.StrokeRect(screen, float32(b.Min.X), float32(b.Min.Y), float32(2*probeR), float32(2*probeR), 1, xColor, false)
	vector.StrokeCircle(screen, float32(l.probe.X), float32(l.probe.Y), probeR, 1, lineColor, false)
	vector.StrokeLine(screen, float32(s.A.X), float32(s.A.Y), float32(s.B.X), float32(s.B.Y), 1, lineColor, false)
	// What the tests found: each push drawn from the probe's centre, the
	// crossing as a small cross.
	for _, hit := range []struct {
		hit vec.Hit
		ok  bool
	}{{bb, okB}, {cc, okC}, {cb, okCB}} {
		if hit.ok {
			arrow(screen, h, l.probe, hit.hit.Normal.Scale(hit.hit.Depth), yColor, "")
		}
	}
	if meet == vec.Crossing {
		vector.StrokeLine(screen, float32(cross.X-3), float32(cross.Y-3), float32(cross.X+3), float32(cross.Y+3), 1, yColor, false)
		vector.StrokeLine(screen, float32(cross.X-3), float32(cross.Y+3), float32(cross.X+3), float32(cross.Y-3), 1, yColor, false)
	}
}

func (l *shapesLab) lines() (top, bottom string) {
	bb, cc, cb, okB, okC, okCB, _, meet := l.hits()
	return fmt.Sprintf("probe %v  box %s  circle %s", l.probe, depthText(bb, okB), depthText(cc, okC)),
		fmt.Sprintf("circle-box %s  segments %v", depthText(cb, okCB), meet)
}

// cmd/motion/main.go — extend
// newLab builds the lab named, from the seed: the one place a name
// becomes a lab. Labs that draw no random numbers ignore the seed.
func newLab(name string, seed uint64) (lab, error) {
	switch name {
	case "circle":
		return newCircleLab(), nil
	case "arrows":
		return newArrowsLab(), nil
	case "ship":
		return newShipLab(), nil
	case "ball":
		return newBallLab(), nil
	case "ease":
		return newEaseLab(), nil
	case "dots":
		return newDotsLab(seed), nil
	case "shapes":
		return newShapesLab(), nil
	}
	return nil, fmt.Errorf("no lab called %q", name)
}

go vet ./...
go run ./cmd/motion -lab shapes

The window when the lab opens: the probe clear of everything, and every test answering no.

Press Space where the probe starts, hold Left for fifty ticks and press it again, hold Right for eighty and press it again, then Down for forty and once more:

$ go run ./cmd/motion -lab shapes
probe (160.0000, 100.0000): box -  circle -  circle-box -
segments apart
probe (110.0000, 100.0000): box 22.0000 (1.0000, 0.0000)  circle -  circle-box 22.0000 (1.0000, 0.0000)
segments apart
probe (190.0000, 100.0000): box -  circle 8.3772 (-0.9487, 0.3162)  circle-box -
segments apart
probe (190.0000, 140.0000): box -  circle -  circle-box -
segments crossing at (213.2653, 101.2245)

Fifty ticks of Left: the probe's box 22 pixels inside the fixed box's right edge, and the circle's centre inside it too, both pushed out to the right by 22.

At (110, 100), the probe's box runs from x = 98 to x = 122. The fixed box ends at x = 120. The four overlaps are 82, 22, 52 and 32. The smallest is 22, so the push goes right along (1, 0).

The circle-against-box test agrees by a different route. The centre is inside the box, ten pixels from the right face, and ten plus the radius of twelve gives 22. The fixed circle is too far away, and the probe segment misses the fixed segment.

Eighty ticks of Right: the probe 31.6 pixels from the fixed circle's centre, against a reach of 40, and pushed 8.38 pixels back along the line between the two centres.

At (190, 100), the centres are (−30, 10) apart. The squared distance is 1000, and the squared reach is 1600, so the circles overlap. The distance is 31.6228, and the depth is 40 − 31.6228 = 8.3772.

The normal is (−30, 10) normalised, or (−0.9487, 0.3162). Forty ticks of Down moves the probe segment across the fixed segment, and the lab marks the crossing at (213.27, 101.22).

Forty ticks of Down: the arm across the fixed segment, and the crossing marked where two cross products put it.

The lab stores one point and builds three shapes from it every tick, so the probe shapes can't disagree about their centre. hits runs all four tests. draw and lines both call it, so the picture and HUD use the same answers.

// cmd/motion/shapes.go — extend
import (
	"flag"
	"fmt"
	"math"

	"github.com/hajimehoshi/ebiten/v2"
	"github.com/hajimehoshi/ebiten/v2/vector"

	"gez/internal/vec"
)

// newShapesLab prints how many square roots the circle test takes for a
// field of circles, with the package's test and with one that takes the
// root on every pair.
func newShapesLab() *shapesLab {
	for _, n := range []int{10, 100, 1000} {
		s := vec.NewSource(1)
		cs := make([]vec.Circle, n)
		for i := range cs {
			cs[i] = vec.Circle{Centre: vec.Vec2{X: s.Uniform(0, screenW), Y: s.Uniform(14, screenH-14)}, R: 5}
		}
		pairs, overlaps := 0, 0
		for i := range cs {
			for j := i + 1; j < n; j++ {
				pairs++
				if _, ok := circles(cs[i], cs[j]); ok {
					overlaps++
				}
			}
		}
		roots := overlaps
		if *sqrtEvery {
			roots = pairs
		}
		fmt.Printf("%4d circles of radius 5: %6d pairs a tick, %4d overlapping; square roots a tick %6d, a second %8d\n", n, pairs, overlaps, roots, roots*60)
	}
	return &shapesLab{probe: probeStart}
}

// circles is the circle test the lab uses: the package's, or, under -sqrt,
// one that takes the square root of the distance on every test before
// comparing, which is the cost this chapter measures.
func circles(a, b vec.Circle) (vec.Hit, bool) {
	if !*sqrtEvery {
		return vec.OverlapCircles(a, b)
	}
	d := a.Centre.Sub(b.Centre)
	dist := math.Sqrt(d.Dot(d))
	if dist >= a.R+b.R {
		return vec.Hit{}, false
	}
	if dist == 0 {
		return vec.Hit{Depth: a.R + b.R, Normal: vec.Vec2{X: 1}}, true
	}
	return vec.Hit{Depth: a.R + b.R - dist, Normal: d.Scale(1 / dist)}, true
}

// hits runs the four tests: probe box against the fixed box, probe circle
// against the fixed circle, probe circle against the fixed box, and probe
// segment against the fixed segment.
func (l *shapesLab) hits() (bb, cc, cb vec.Hit, okB, okC, okCB bool, cross vec.Vec2, meet vec.Meet) {
	bb, okB = vec.OverlapAABB(l.box(), fixedBox)
	cc, okC = circles(l.circle(), fixedCircle)
	cb, okCB = vec.OverlapCircleAABB(l.circle(), fixedBox)
	cross, meet = vec.Intersect(l.segment(), fixedSegment)
	return
}

var sqrtEvery = flag.Bool("sqrt", false, "take the square root on every circle test instead of comparing squares: the cost this chapter measures, kept so it can be run")

go vet ./...
go run ./cmd/motion -lab shapes

$ go run ./cmd/motion -lab shapes
  10 circles of radius 5:     45 pairs a tick,    0 overlapping; square roots a tick      0, a second        0
 100 circles of radius 5:   4950 pairs a tick,   33 overlapping; square roots a tick     33, a second     1980
1000 circles of radius 5: 499500 pairs a tick, 3084 overlapping; square roots a tick   3084, a second   185040

A thousand circles make 499,500 pairs. In this field, 3,084 pairs overlap. The package test takes 3,084 square roots, one for each overlap, and none for the other 496,416 pairs.

The number of pairs is n(n − 1)/2. Real collision systems avoid testing every pair when they can. This lab tests every pair so the square-root count stays visible.