Rectangles First, Then Lines

// internal/render/draw.go
package render

// Rect is a half-open rectangle of pixels: it holds every pixel with
// X0 <= x < X1 and Y0 <= y < Y1, so its width is X1-X0 and its height
// is Y1-Y0.
type Rect struct {
	X0, Y0, X1, Y1 int
}

// Empty reports whether the rectangle holds no pixels at all.
func (r Rect) Empty() bool { return r.X1 <= r.X0 || r.Y1 <= r.Y0 }

// Contains reports whether one pixel lies inside the rectangle.
func (r Rect) Contains(x, y int) bool {
	return x >= r.X0 && x < r.X1 && y >= r.Y0 && y < r.Y1
}

// Intersect returns the pixels the two rectangles share, which is
// empty if they overlap nowhere.
func (r Rect) Intersect(s Rect) Rect {
	if s.X0 > r.X0 {
		r.X0 = s.X0
	}
	if s.Y0 > r.Y0 {
		r.Y0 = s.Y0
	}
	if s.X1 < r.X1 {
		r.X1 = s.X1
	}
	if s.Y1 < r.Y1 {
		r.Y1 = s.Y1
	}
	if r.X1 < r.X0 {
		r.X1 = r.X0
	}
	if r.Y1 < r.Y0 {
		r.Y1 = r.Y0
	}
	return r
}

// internal/render/buffer.go — the buffer carries its wall
type Buffer struct {
	W, H int
	Pix  []Color

	clip Rect
}

// NewBuffer allocates a w-by-h buffer in a single allocation. Every
// pixel starts at the zero value, Clear, and drawing may write
// anywhere on it until somebody narrows the clip rectangle.
func NewBuffer(w, h int) *Buffer {
	b := &Buffer{W: w, H: h, Pix: make([]Color, w*h)}
	b.clip = b.Bounds()
	return b
}

// Set writes one pixel, if the clip rectangle allows it.
func (b *Buffer) Set(x, y int, c Color) {
	if !b.clip.Contains(x, y) {
		return
	}
	b.Pix[b.index(x, y)] = c
}

// internal/render/draw.go — the wall's controls, and the first user of it

// Bounds is every pixel the buffer owns: the widest the clip can be.
func (b *Buffer) Bounds() Rect { return Rect{0, 0, b.W, b.H} }

// Clip is the rectangle drawing is currently allowed to write inside.
func (b *Buffer) Clip() Rect { return b.clip }

// SetClip narrows the writable area, and can only ever narrow it: the
// requested rectangle is intersected with the buffer's own bounds.
func (b *Buffer) SetClip(r Rect) { b.clip = r.Intersect(b.Bounds()) }

// FillRect paints every pixel of r that the clip rectangle allows.
func (b *Buffer) FillRect(r Rect, c Color) {
	r = r.Intersect(b.clip)
	if r.Empty() {
		return
	}
	for y := r.Y0; y < r.Y1; y++ {
		row := b.Pix[b.index(r.X0, y):b.index(r.X1, y)]
		for i := range row {
			row[i] = c
		}
	}
}

// cmd/worldc/main.go — three rectangles: one inside, one hanging off, one nowhere near
	b := render.NewBuffer(24, 12)
	b.Fill(render.Soil)

	pond := render.Rect{X0: 3, Y0: 2, X1: 9, Y1: 6}
	scree := render.Rect{X0: -4, Y0: 7, X1: 4, Y1: 15}

	fmt.Println("clip:  ", b.Clip())
	fmt.Println("pond:  ", pond, "->", pond.Intersect(b.Clip()))
	fmt.Println("scree: ", scree, "->", scree.Intersect(b.Clip()))

	b.FillRect(pond, render.Water)
	b.FillRect(scree, render.Rock)
	b.FillRect(render.Rect{X0: 30, Y0: 2, X1: 40, Y1: 4}, render.Rock)
	fmt.Print(b.Preview())

$ go run ./cmd/worldc
clip:   {0 0 24 12}
pond:   {3 2 9 6} -> {3 2 9 6}
scree:  {-4 7 4 15} -> {0 7 4 12}
........................
........................
...~~~~~~...............
...~~~~~~...............
...~~~~~~...............
...~~~~~~...............
........................
####....................
####....................
####....................
####....................
####....................

The scree is the one to study. It was asked for at {-4 7 4 15}, four columns west of the buffer and three rows below it, and Intersect turned it into {0 7 4 12} before a single pixel moved: four comparisons, one per side, each keeping whichever edge is further in. The clamps underneath handle the case where that leaves nothing, which is what the third call hit. {30 2 40 4} against a 24-wide buffer comes back as {30 2 30 4}, zero pixels wide, and Empty sends FillRect home before the loop starts. Nothing drawn, nothing said, because a rectangle entirely off the buffer is routine: in a scrolling map most of the world is off-screen every frame.

Look at what the fill loop does not do: it never calls Set. It takes a row slice, b.Pix[b.index(r.X0, y):b.index(r.X1, y)], and writes straight through it. Both ends of that slice are checked once, when the slice is made, and the for i := range row that follows writes through an index the compiler can prove is inside it. That is chapter 12's promise collected: 24 pixels of pond cost one intersection and four bounds checks instead of 24 coordinate tests, and the saving grows with the rectangle. A row is also contiguous in memory, so the fill walks forward instead of hopping.

Two smaller decisions carry weight across the drawing package. Set now asks clip instead of In, so every per-pixel write inherits the movable wall, and because NewBuffer starts the clip at Bounds(), nothing chapter 12 wrote behaves differently today. At keeps asking In: reading a pixel outside the clip is sensible, and the clip governs writing only.

// cmd/worldc/main.go — a throwaway: lines that only run east and south

// lineShallow draws a line running left to right whose rise is no
// greater than its run, keeping the error as a whole number.
func lineShallow(b *render.Buffer, x0, y0, x1, y1 int, c render.Color) {
	dx, dy := x1-x0, y1-y0
	e, y := 0, y0
	for x := x0; x <= x1; x++ {
		b.Set(x, y, c)
		e += dy
		if 2*e >= dx {
			y++
			e -= dx
		}
	}
}

$ go run ./cmd/worldc   (the walk printed, then the pixels it chose)
  x     e    2e  2e >= 7   y
  2     0     0    false   2
  3     3     6    false   2
  4     6    12     true   3
  5     2     4    false   3
  6     5    10     true   4
  7     1     2    false   4
  8     4     8     true   5
  9     0     0    false   5
........................
........................
..~~....................
....~~..................
......~~................
........~~..............
........................
........................
........................
........................
........................
........................

Eight columns, eight pixels, and the staircase steps down exactly where the pencil said it would. Per pixel the method costs one addition, one comparison and occasionally one subtraction, and the division that would have produced 0.428571… never happens: it was replaced by the decision to count in sevenths. That trick is much older than graphics and turns up wherever a rate must be tracked without drift, from audio resampling to scheduling. Multiply the units up until the fractions disappear, then stay in whole numbers.

// cmd/worldc/main.go — add the slope, cut the result down to a pixel

func lineFloat(b *render.Buffer, x0, y0, x1, y1 int, c render.Color) {
	slope := float64(y1-y0) / float64(x1-x0)
	y := float64(y0)
	for x := x0; x <= x1; x++ {
		b.Set(x, int(y), c)
		y += slope
	}
}

func main() {
	b := render.NewBuffer(24, 12)
	b.Fill(render.Soil)
	lineFloat(b, 2, 2, 9, 5, render.Water)
	lineFloat(b, 2, 8, 12, 9, render.Water)
	fmt.Print(b.Preview())

	slope := 1.0 / 10.0
	y := 8.0
	for x := 2; x < 12; x++ {
		y += slope
	}
	fmt.Printf("asked for   (12,9)\n")
	fmt.Printf("y ends at   %.17f\n", y)
	fmt.Printf("as a pixel  %d\n", int(y))
	fmt.Printf("exact?      %v\n", y == 9.0)
}

$ go run ./cmd/worldc
........................
........................
..~~~...................
.....~~.................
.......~~...............
.........~..............
........................
........................
..~~~~~~~~~~~...........
........................
........................
........................
asked for   (12,9)
y ends at   8.99999999999999645
as a pixel  8
exact?      false

Two failures, one of them fatal. The first stream sags: its runs are three pixels, then two, two, one, where the integer walk laid down an even two, two, two, two. That is int(y) cutting the fraction off, which discards up to a whole pixel of rise every column and always in the same direction, so the line rides low and its final column arrives alone.

The second stream never arrives at all. It was told to run from {2 8} to {12 9}, a slope of exactly one tenth, and the preview shows it flat along row 8 with row 9 untouched. The printed arithmetic says why: one tenth has no exact form in binary, ten additions of it land on 8.99999999999999645 instead of 9, and cutting the fraction off reads that as row 8. The line missed its own endpoint by a pixel. Rounding to nearest would rescue this particular line, at the price of an extra operation per pixel and a patch laid over a method that is approximate by construction. The integer walk needs no rescue: its error is a whole number that provably returns to zero.

// internal/render/draw.go

// Line draws the pixels nearest the straight line from (x0,y0) to
// (x1,y1), in integers only.
func (b *Buffer) Line(x0, y0, x1, y1 int, c Color) {
	dx, sx := x1-x0, 1
	if dx < 0 {
		dx, sx = -dx, -1
	}
	dy, sy := y1-y0, 1
	if dy < 0 {
		dy, sy = -dy, -1
	}
	dy = -dy
	err := dx + dy
	for {
		b.Pix[b.index(x0, y0)] = c // straight into the slice, like FillRect
		if x0 == x1 && y0 == y1 {
			return
		}
		e2 := 2 * err
		if e2 >= dy {
			err += dy
			x0 += sx
		}
		if e2 <= dx {
			err += dx
			y0 += sy
		}
	}
}

// cmd/worldc/main.go — the hand-walked line, then a fan of twelve
	b.Line(2, 2, 9, 5, render.Water)
	fmt.Print(b.Preview())

	f := render.NewBuffer(24, 12)
	f.Fill(render.Soil)
	cx, cy := 11, 5
	for _, d := range [][2]int{{9, 0}, {9, 4}, {4, 5}, {0, 5}, {-4, 5}, {-9, 4},
		{-9, 0}, {-9, -4}, {-4, -5}, {0, -5}, {4, -5}, {9, -4}} {
		f.Line(cx, cy, cx+d[0], cy+d[1], render.Water)
	}
	fmt.Print(f.Preview())

$ go run ./cmd/worldc
........................
........................
..~~....................
....~~..................
......~~................
........~~..............
........................
........................
........................
........................
........................
........................
.......~...~...~........
..~~....~..~..~....~~...
....~~...~.~.~...~~.....
......~~.~.~.~.~~.......
........~~~~~~~.........
..~~~~~~~~~~~~~~~~~~~...
........~~~~~~~.........
......~~.~.~.~.~~.......
....~~...~.~.~...~~.....
..~~....~..~..~....~~...
.......~...~...~........
........................

Check the first preview first: those are the same eight pixels the pencil chose and lineShallow drew, produced by a loop that never heard of octants. The fan is the general case, twelve spokes shallow and steep across all four quadrants, every one of them ending on the pixel it was aimed at.

The signs come off at the top: dx and dy are made positive with their directions kept in sx and sy, so the arithmetic is about magnitudes and the direction of travel is a separate fact. Negating dy afterwards is what lets one error term serve both axes. err carries the x-error and the y-error against each other, and e2, its double, plays the part 2*e played in the interlude, asking each axis in turn whether the true line has moved far enough to justify a step. On a shallow line the x test passes every iteration and the y test occasionally; on a steep line it is the other way round; at 45 degrees both pass every time and the walk goes diagonally. The loop stops on the coordinate test and not on a counter, so both endpoints are drawn exactly.

This method is Bresenham's line algorithm, worked out at IBM in 1962 to drive a plotter. It survived into every framebuffer renderer since for the reasons that fan demonstrates. Integers only, a couple of adds and compares per pixel, endpoints exact, and the same answer everywhere.

// internal/render/draw.go — Line's loop, one line different
	for {
		b.Set(x0, y0, c)
		if x0 == x1 && y0 == y1 {
			return
		}

$ go run ./cmd/worldc
........................
........................
........................
........................
................~~~~~...
........~~~~~~~~........
~~~~~~~~................
........................
........................
........................
........................
........................
still drawing

Same two calls, same coordinates, and the stream now stops dead at column 0 with the east side of rows 5 and 6 untouched. The row 0 line draws its four on-map pixels and returns, and the client is still running to say so. The fix does not shorten the walk or leave the loop early. The error term keeps stepping through coordinates nobody will ever see, out to {-6 7}, and Set throws each one away. That matters for correctness, because the pixels a clipped line draws must be the pixels it would have drawn unclipped. A line that changed its staircase depending on where the window edge fell would shift by a pixel every time the camera moved.

// cmd/worldc/main.go — draw far too much, inside a small window

// border draws the four sides of a rectangle, one pixel wide.
func border(b *render.Buffer, r render.Rect, c render.Color) {
	b.Line(r.X0, r.Y0, r.X1-1, r.Y0, c)
	b.Line(r.X0, r.Y1-1, r.X1-1, r.Y1-1, c)
	b.Line(r.X0, r.Y0, r.X0, r.Y1-1, c)
	b.Line(r.X1-1, r.Y0, r.X1-1, r.Y1-1, c)
}

func main() {
	b := render.NewBuffer(24, 12)
	b.Fill(render.Soil)

	view := render.Rect{X0: 6, Y0: 3, X1: 18, Y1: 10}
	full := b.Clip()

	b.SetClip(view)
	b.FillRect(render.Rect{X0: 2, Y0: 6, X1: 22, Y1: 8}, render.Water)
	b.Line(-4, 1, 27, 12, render.Rock)
	b.SetClip(full)

	border(b, view, render.Rock)
	fmt.Print(b.Preview())

	wide := render.Rect{X0: -100, Y0: -100, X1: 900, Y1: 900}
	b.SetClip(wide)
	fmt.Println("asked to clip to", wide)
	fmt.Println("clip is        ", b.Clip())
}

$ go run ./cmd/worldc
........................
........................
........................
......############......
......#..........#......
......###........#......
......#~~###~~~~~#......
......#~~~~~###~~#......
......#........###......
......############......
........................
........................
asked to clip to {-100 -100 900 900}
clip is         {0 0 24 12}

The pond was asked for at columns 2 through 21 and appears only between 7 and 16. The rock line was told to run from {-4 1}, off the buffer entirely, to {27 12}, off the other side, and only its middle survives, entering and leaving the window on the pixels it would have used anyway: clipping removed pixels without moving any. The border exists because it is drawn afterwards with the clip restored, four calls to Line, each using X1-1 because half-open means the last pixel is one short of the edge number.

The last two printed lines are what makes this a wall and not a suggestion. Asked to open the clip to a thousand pixels in every direction, the buffer reports {0 0 24 12}. Because SetClip intersects with Bounds(), the writable area can be cut down by any caller and widened by none, and that guarantee holds no matter what a camera or a panel layout computes.