1// Package basemap draws a city's ground from the city's own vector data.2//3// A bundle owes its reader a surface to stand on, and the offline invariant4// (issue #5 ยง2) means no tile service may be reached for one. A city has no5// tile server of its own either: what it publishes is geometry -- limits,6// zoning, water, streets, trails -- so the picture is drawn here, from that7// geometry, into the deepest level of the lens's pyramid. Every shallower level8// then folds down from it exactly as any other pyramid's does, which is why9// this package draws one level and knows nothing about pyramids.10//11// # Determinism12//13// The drawing is a pure function of the shapes handed to it. Roles draw in a14// fixed order; within a role, shapes are unioned rather than painted over, so15// the order they arrive in cannot be read off the result; the arithmetic is16// float64 down to the rasterizer's own float32 edge; and the encoder runs with17// fixed settings. The same shapes make the same bytes, which is what lets a18// derivation be compared against the capture that witnessed it.19//20// The one thing outside this package's control is the toolchain: a change to21// the standard library's DEFLATE would re-spell the PNG bytes once without22// moving a pixel. That is why the deriver compares content hashes and the23// fixtures carry decoded-pixel digests beside them -- the two together tell a24// re-encoding from a picture that actually moved.25package basemap2627import (28 "bytes"29 "image"30 "image/color"31 "image/draw"32 "image/png"33 "math"3435 "golang.org/x/image/vector"36)3738// The grid the drawing is cut on: the corpus's tile edge, and the world square39// every source's picture is measured in. They are repeated rather than imported40// so this package stands alone as the thing that draws a tile.41const (42 TileSize = 25643 WorldSize = 819244)4546// Bleed is how far past its own edge a tile draws, in tile pixels: wide enough47// for the widest stroke's half plus its antialiasing, so a cut never lands on a48// pixel the tile keeps and two neighbours continue each other exactly.49const Bleed = 85051// Feature is one thing to draw, in world pixels of the square: ground as rings52// -- the first the outline, the rest holes -- and linework as polylines.53// Emphasis scales the role's stroke width for this one shape, an arterial54// against a lane; zero means the role's own width, unremarkable.55type Feature struct {56 Role Role57 Rings [][][2]float6458 Lines [][][2]float6459 Emphasis float6460}6162// Renderer draws the tiles of one level of one city. Build it once per level63// and ask it for tiles: it normalizes the shapes' winding once and indexes them64// by the tile they touch, so drawing a tile visits only the shapes that reach65// it rather than the whole city.66type Renderer struct {67 features []Feature68 zoom int69 touching map[[2]int][]int70}7172// NewRenderer prepares a level's shapes for drawing. It takes ownership of the73// slice: ring winding is normalized in place, once, rather than on every tile.74func NewRenderer(features []Feature, zoom int) *Renderer {75 r := &Renderer{features: features, zoom: zoom, touching: make(map[[2]int][]int)}76 across := 1 << zoom77 worldTile := float64(WorldSize) / float64(across)7879 for at := range r.features {80 feature := &r.features[at]81 normalizeWinding(feature.Rings)82 reach := span(feature.Rings).join(span(feature.Lines))83 if reach.empty() {84 continue85 }86 // A stroke reaches past its own centreline, so the reach is widened by87 // the bleed before it is indexed: a wide boundary has to be found by88 // the neighbouring tile it spills into, not only by the tiles its89 // centreline crosses.90 margin := Bleed * worldTile / TileSize91 firstX := tileOf(reach.minX-margin, worldTile, across)92 lastX := tileOf(reach.maxX+margin, worldTile, across)93 firstY := tileOf(reach.minY-margin, worldTile, across)94 lastY := tileOf(reach.maxY+margin, worldTile, across)95 for x := firstX; x <= lastX; x++ {96 for y := firstY; y <= lastY; y++ {97 key := [2]int{x, y}98 r.touching[key] = append(r.touching[key], at)99 }100 }101 }102 return r103}104105// tileOf is which tile a world coordinate falls in, held inside the level.106func tileOf(world, worldTile float64, across int) int {107 tile := int(math.Floor(world / worldTile))108 return min(max(tile, 0), across-1)109}110111// Tile draws one tile of the level the renderer was built for. Every tile of112// the level exists: one nothing touches is the flat background, and the deriver113// wants the level complete so it has something to fold down from. Empty tiles114// cost almost nothing, and the deriver omits the one they all share anyway.115func (r *Renderer) Tile(x, y int) *image.NRGBA {116 img := image.NewNRGBA(image.Rect(0, 0, TileSize, TileSize))117 draw.Draw(img, img.Bounds(), image.NewUniform(Background), image.Point{}, draw.Src)118119 worldTile := float64(WorldSize) / float64(int(1)<<r.zoom)120 scale := TileSize / worldTile121 originX, originY := float64(x)*worldTile, float64(y)*worldTile122 // The window the geometry is cut to, bled past the tile on every side.123 window := box{124 minX: originX - Bleed/scale,125 minY: originY - Bleed/scale,126 maxX: originX + worldTile + Bleed/scale,127 maxY: originY + worldTile + Bleed/scale,128 }129 // Widths are spelled at the reference zoom, so a level deeper draws them130 // twice as wide -- which, folded back down, is one constant width on the131 // ground.132 widthScale := math.Pow(2, float64(r.zoom-ReferenceZoom))133134 local := func(p [2]float64) [2]float64 {135 return [2]float64{(p[0] - originX) * scale, (p[1] - originY) * scale}136 }137 // How many tile pixels one world pixel spans, measured through the very138 // transform the geometry crosses, so the dash rhythm is counted in the139 // units it is drawn in.140 pixels := math.Abs(local([2]float64{1, 0})[0] - local([2]float64{0, 0})[0])141142 for _, role := range zOrder {143 style := styles[role]144 // One rasterizer per role for the ground and one for the linework, made145 // only if the role has anything on this tile. Every shape of a role146 // accumulates into the same path, and the rasterizer saturates, so a147 // role's shapes are unioned and their order cannot be seen.148 var ground, lines *vector.Rasterizer149150 for _, at := range r.candidates(x, y) {151 feature := &r.features[at]152 if feature.Role != role {153 continue154 }155 if style.Fill.A > 0 && len(feature.Rings) > 0 {156 if ground == nil {157 ground = vector.NewRasterizer(TileSize, TileSize)158 }159 for _, ring := range feature.Rings {160 clipped := clipRing(ring, window)161 if clipped == nil {162 continue163 }164 head := local(clipped[0])165 moveTo(ground, head[0], head[1])166 for _, corner := range clipped[1:] {167 corner := local(corner)168 lineTo(ground, corner[0], corner[1])169 }170 ground.ClosePath()171 }172 }173 if style.Stroke.A == 0 || style.StrokeWidth <= 0 {174 continue175 }176 width := style.StrokeWidth * widthScale177 if feature.Emphasis > 0 {178 width *= feature.Emphasis179 }180 if lines == nil {181 lines = vector.NewRasterizer(TileSize, TileSize)182 }183 stroke(lines, feature.Lines, window, local, pixels, width, style.Dash, widthScale)184 // A filled role that also carries a stroke wears it as a rim around185 // its own ground -- but only when the shape brought no linework of186 // its own to spend it on.187 if len(feature.Lines) == 0 && len(feature.Rings) > 0 {188 stroke(lines, closed(feature.Rings), window, local, pixels, width, style.Dash, widthScale)189 }190 }191192 if ground != nil {193 ground.Draw(img, img.Bounds(), image.NewUniform(style.Fill), image.Point{})194 }195 if lines != nil {196 lines.Draw(img, img.Bounds(), image.NewUniform(style.Stroke), image.Point{})197 }198 }199 return img200}201202// candidates is the shapes that reach one tile, in the order they were given.203func (r *Renderer) candidates(x, y int) []int { return r.touching[[2]int{x, y}] }204205// stroke lays every polyline of one shape into the path: each is clipped206// segment by segment, and what survives is stroked as capsules.207//208// Clipping a segment at a time rather than the polyline as a whole is what209// keeps a dashed line's rhythm agreeing across a tile seam. The phase advances210// by the whole of every segment, drawn or not, and a segment whose head was cut211// off starts at the phase its lost lead had already carried -- so the dash a212// neighbouring tile draws lands in exactly the same place.213func stroke(214 into *vector.Rasterizer,215 paths [][][2]float64,216 window box,217 local func([2]float64) [2]float64,218 pixels, width float64,219 dash [2]float64,220 widthScale float64,221) {222 scaled := [2]float64{dash[0] * widthScale, dash[1] * widthScale}223 period := scaled[0] + scaled[1]224225 for _, path := range paths {226 phase := 0.0227 for at := 0; at+1 < len(path); at++ {228 from, to, kept := clipSegment(path[at], path[at+1], window)229 if kept {230 a, b := local(from), local(to)231 if dash[0] > 0 {232 lead := math.Hypot(from[0]-path[at][0], from[1]-path[at][1]) * pixels233 dashedCapsules(into, a, b, width, scaled, math.Mod(phase+lead, max(period, 1)))234 } else {235 capsule(into, a, b, width)236 }237 }238 if period > 0 {239 length := math.Hypot(path[at+1][0]-path[at][0], path[at+1][1]-path[at][1]) * pixels240 phase = math.Mod(phase+length, period)241 }242 }243 }244}245246// closed spells rings as polylines that return to where they began, which is247// what stroking a shape's rim means.248func closed(rings [][][2]float64) [][][2]float64 {249 out := make([][][2]float64, 0, len(rings))250 for _, ring := range rings {251 if len(ring) < 3 {252 continue253 }254 path := make([][2]float64, 0, len(ring)+1)255 path = append(path, ring...)256 if ring[0] != ring[len(ring)-1] {257 path = append(path, ring[0])258 }259 out = append(out, path)260 }261 return out262}263264// EncodePNG spells a tile with the settings the archive is written under:265// slowest and smallest, because a tile is encoded once and read forever, and266// fixed, because a settings knob left to a caller is a way for two runs of the267// same pipeline to disagree.268func EncodePNG(img *image.NRGBA) ([]byte, error) {269 var out bytes.Buffer270 encoder := png.Encoder{CompressionLevel: png.BestCompression}271 if err := encoder.Encode(&out, img); err != nil {272 return nil, err273 }274 return out.Bytes(), nil275}276277// BackgroundColor reports the flat ground, so the deriver's placeholder278// detection and this drawing cannot disagree about what empty looks like.279func BackgroundColor() color.NRGBA { return Background }