1package tiles23import (4 "errors"5 "fmt"6 "math"7 "os"89 "github.com/FelineStateMachine/atlas/internal/generate/archive"10 "github.com/FelineStateMachine/atlas/internal/generate/doc"11)1213// Deriving a pyramid begins by deciding what is there, which is what a plan is.14// Nothing is read out of a raster to make one: the archive says which tiles15// answered and what their bytes hash to, the source says which tiles a level was16// supposed to hold, and between the two the whole shape of the pyramid is17// settled -- how deep it goes, which level is the one to trust, what encoding18// each level carries, and the ground it actually draws.19//20// That is also why a plan can be stamped without touching a tile. See stamp.go.2122// worldZoomLevels is how far the world square sits above the level that holds a23// picture in one tile: 8192 units of world across, 256 to a tile, so five24// halvings. It is what makes one unit of world one pixel of the reference level,25// whichever level that turns out to be.26const worldZoomLevels = 52728// Frame is where a picture sits in its publisher's tile grid.29//30// Publishers do not agree on it. The maps captured most recently are cut from a31// 32-tile square at zoom 13; one older game is cut from a square at the origin32// whose deepest level is 43 tiles across and whose shallowest is 3. Both are the33// same kind of pyramid seen from a different height, so no one height is34// assumed: each picture is measured, and the zoom whose window collapses into a35// single tile is the floor its local zooms are counted from.36type Frame struct {37 // BaseZoom is the publisher's zoom that holds the whole window in one tile,38 // and BaseTile is that tile. Local zoom 0 is this level, so a picture's39 // local zooms are its publisher zooms less BaseZoom.40 BaseZoom int41 BaseTile int42}4344// Origin is the first tile of a publisher's level: the base tile, doubled back45// up the pyramid the same way the window was halved down it.46func (f Frame) Origin(zoom int) int { return f.BaseTile << (zoom - f.BaseZoom) }4748// Window is where this picture's world space sits in the publisher's grid, in49// the terms a reader needs to place a feature: the zoom whose pixels are the50// world's units, and the first tile of the window at that zoom. A picture in the51// corpus's shared window lands back on zoom 13 and tile 4064.52func (f Frame) Window() (sourceZoom, firstTile int) {53 reference := f.BaseZoom + worldZoomLevels54 return reference, f.Origin(reference)55}5657// Tile is one captured raster in a plan: where the publisher put it, what its58// bytes hash to, where they sit, and how they are encoded.59type Tile struct {60 Ref archive.TileRef61 Path string62 Format string63}6465// Plan is one pyramid, decided but not yet built.66type Plan struct {67 // TileSet is the publisher's path for the picture, and Name is the68 // directory the derived pyramid lands in.69 TileSet string70 Name string71 // Frame is where the picture sits in the publisher's grid.72 Frame Frame73 // Levels is every usable captured level, by the publisher's zoom. Levels at74 // or below MaxFullZoom cover the picture completely; deeper ones may be75 // partial and are carried as extra detail on top of the complete pyramid.76 Levels map[int][]Tile77 // MaxFullZoom is the deepest level whose expected tiles are all present --78 // the one level the pyramid is folded down from. MaxSourceZoom is the79 // deepest usable level of any kind.80 MaxFullZoom int81 MaxSourceZoom int82 // Format is the encoding the publisher serves, and Interpolate says whether83 // the raster is smoothed when magnified: false is pixel art, which is84 // reduced nearest-neighbour and normalized to lossless PNG.85 Format string86 Interpolate bool87 // Bounds is the part of the world square the picture actually draws, or nil88 // where it draws all of it.89 Bounds *Box90 // Drawing, when set, says the deepest level is drawn rather than copied:91 // its pixels come from the source's own vectors and not from a capture. The92 // plan still lists the level's captured tiles, because a drawn level was93 // archived when it was first drawn and those hashes are what the derivation94 // is held to -- see Derive, which refuses a tile that disagrees with them.95 Drawing *doc.Drawing96 // LensName and AlignedWith mark a warped variant. An ordinary plan leaves97 // both empty.98 LensName string99 AlignedWith string100 // Warp, when set, makes this a derived plan: a donor picture resampled into101 // another picture's world so both rasters answer to one grid.102 Warp *Warp103}104105// Warp says how a donor picture lands in a base picture's world.106//107// Two sources picturing one ground publish two rasters in two spaces. A warp is108// the second one resampled into the first's, so a reader can switch between them109// without the ground moving: the alignment is fitted from the names the two110// sources share, and the fit is as much an input to the derivation as the tiles111// are -- the same donor through a different transformation is a different112// picture, which is why the stamp carries it.113type Warp struct {114 Donor *Plan115 Base *Plan116 // Affine sends donor world pixels onto base world pixels.117 Affine Affine118 // TargetZoom is the local zoom in the base frame the warp renders at.119 TargetZoom int120}121122// Affine is the transformation a warp resamples through: x' = AX*x + BX*y + CX,123// y' = AY*x + BY*y + CY.124//125// Fitting one is not this lane's work -- it stands on the names two readings126// share, which is the enrich lane's alignment (issue #5 ยง5.3), and a warp127// receives the fitted six numbers as an input. What lives here is only the128// arithmetic of using one, which a resampler cannot do without and which is not129// alignment: applying it, inverting it, and asking how far it stretches.130type Affine struct {131 AX, BX, CX float64132 AY, BY, CY float64133}134135// Apply sends a donor-space point into the base picture's space.136func (a Affine) Apply(x, y float64) (float64, float64) {137 return a.AX*x + a.BX*y + a.CX, a.AY*x + a.BY*y + a.CY138}139140// Invert solves the transformation the other way, which is the direction a141// resampler reads in: every base pixel asks where in the donor it came from.142// The false result is a degenerate transformation, through which nothing may be143// resampled.144func (a Affine) Invert() (Affine, bool) {145 determinant := a.AX*a.BY - a.BX*a.AY146 if math.Abs(determinant) < 1e-12 {147 return Affine{}, false148 }149 out := Affine{150 AX: a.BY / determinant, BX: -a.BX / determinant,151 AY: -a.AY / determinant, BY: a.AX / determinant,152 }153 out.CX = -(out.AX*a.CX + out.BX*a.CY)154 out.CY = -(out.AY*a.CX + out.BY*a.CY)155 return out, true156}157158// Scale reports how many base pixels one donor pixel spans, averaged over the159// axes. It is what decides how deep a warp is worth rendering.160func (a Affine) Scale() float64 {161 return (math.Hypot(a.AX, a.AY) + math.Hypot(a.BX, a.BY)) / 2162}163164// ErrNoFrame marks a lens the deriver cannot plan: one whose source declared no165// frame, or whose frame has no square window. It is a refusal rather than a166// guess, because a picture measured against the wrong window derives a pyramid167// that draws a map in one place and its features in another.168var ErrNoFrame = errors.New("this picture declares no frame the deriver can measure")169170// PlanLens decides what a lens's pyramid will be, from what the source declared171// and what the archive actually holds.172//173// The complete-level rule is the whole judgement. The deepest level whose174// expected tiles are all present is the one the pyramid is folded down from;175// every shallower level is derived from it rather than taken from whatever176// intermediate levels the capture happens to hold, because those are separately177// encoded pictures of varying completeness and a reduction of the level we178// already trust is both more consistent and never leaves a level empty. Partial179// levels above it are carried while they stay contiguous: a reader falls back to180// the parent tile wherever coverage says nothing, but it cannot jump across a181// missing resolution.182func PlanLens(183 a *archive.Archive,184 world archive.WorldRef,185 name string,186 lens doc.Lens,187 captured map[int][]archive.TileRef,188 interpolate bool,189) (Plan, error) {190 if lens.Frame == nil {191 return Plan{}, fmt.Errorf("%w: %s", ErrNoFrame, lens.TileSet)192 }193 frame, ok := frameOf(*lens.Frame)194 if !ok {195 return Plan{}, fmt.Errorf("%w: %s has no square window", ErrNoFrame, lens.TileSet)196 }197198 levels := make(map[int][]Tile)199 maxFullZoom, maxSourceZoom := -1, -1200 for zoom, refs := range captured {201 if zoom < frame.BaseZoom || zoom > lens.Frame.MaxZoom {202 continue203 }204 tiles, full, err := readLevel(a, world, *lens.Frame, zoom, refs)205 if err != nil {206 return Plan{}, err207 }208 if len(tiles) == 0 {209 continue210 }211 levels[zoom] = tiles212 maxSourceZoom = max(maxSourceZoom, zoom)213 if full {214 maxFullZoom = max(maxFullZoom, zoom)215 }216 }217 if maxFullZoom < frame.BaseZoom {218 return Plan{}, fmt.Errorf("%w: %s has no complete captured level", ErrNoFrame, lens.TileSet)219 }220 // A partial level is only usable if every level beneath it is there;221 // otherwise a reader would jump across a missing resolution.222 for zoom := maxFullZoom + 1; zoom <= maxSourceZoom; zoom++ {223 if len(levels[zoom]) == 0 {224 maxSourceZoom = zoom - 1225 break226 }227 }228229 return Plan{230 TileSet: lens.TileSet,231 Name: name,232 Frame: frame,233 Levels: levels,234 MaxFullZoom: maxFullZoom,235 MaxSourceZoom: maxSourceZoom,236 Format: archive.NormalizeFormat(lens.Frame.Format),237 Interpolate: interpolate,238 Bounds: boundsOf(levels[maxFullZoom], maxFullZoom, frame),239 Drawing: lens.Drawing,240 }, nil241}242243// frameOf halves a declared window until it is a single tile.244func frameOf(declared doc.Frame) (Frame, bool) {245 window := expected(declared, declared.MaxZoom)246 for shift := 0; shift <= declared.MaxZoom; shift++ {247 x, y := window.MinX>>shift, window.MinY>>shift248 if x != window.MaxX>>shift || y != window.MaxY>>shift {249 continue250 }251 // A reader places a feature from one origin for both axes, so a window252 // whose axes come to rest on different tiles would draw the picture in253 // one place and its features in another. Nothing in the archive is254 // shaped that way; a picture that is says so rather than being silently255 // a tile out.256 if x != y {257 return Frame{}, false258 }259 return Frame{BaseZoom: declared.MaxZoom - shift, BaseTile: x}, true260 }261 return Frame{}, false262}263264// expected is the tile window one level was supposed to hold. A level the source265// says nothing about is measured against the corpus's shared square, which is266// where every picture cut from a 32-tile square at zoom 13 lands.267func expected(declared doc.Frame, zoom int) doc.TileWindow {268 if window, ok := declared.Windows[decimal(zoom)]; ok {269 return window270 }271 minimum, maximum := sharedWindow(zoom)272 return doc.TileWindow{MinX: minimum, MinY: minimum, MaxX: maximum, MaxY: maximum}273}274275// The corpus's shared window, and the reference zoom it is measured at. They276// live here rather than in curation because they are what an *undeclared* window277// falls back to during derivation -- the same numbers curation names, read at a278// different moment.279const (280 sharedZoom = 13281 sharedFirstTile = 4064282 sharedTiles = WorldSize / TileSize283)284285// The corpus's grid: 256-pixel tiles and an 8192-pixel world square.286const (287 TileSize = 256288 WorldSize = 8192289)290291func sharedWindow(zoom int) (first, last int) {292 if zoom <= sharedZoom {293 shift := sharedZoom - zoom294 return sharedFirstTile >> shift, ((sharedFirstTile + sharedTiles) >> shift) - 1295 }296 shift := zoom - sharedZoom297 return sharedFirstTile << shift, ((sharedFirstTile + sharedTiles) << shift) - 1298}299300// readLevel collects every captured tile of one publisher level that is inside301// the window the level was supposed to fill, and reports whether the level fills302// it completely. Partial levels are still returned so they can be carried as303// extra detail above the complete pyramid.304func readLevel(305 a *archive.Archive,306 world archive.WorldRef,307 declared doc.Frame,308 zoom int,309 refs []archive.TileRef,310) ([]Tile, bool, error) {311 window := expected(declared, zoom)312 want := (window.MaxX - window.MinX + 1) * (window.MaxY - window.MinY + 1)313314 seen := make(map[[2]int]bool, len(refs))315 out := make([]Tile, 0, len(refs))316 for _, ref := range refs {317 key := [2]int{ref.X, ref.Y}318 if seen[key] || ref.X < window.MinX || ref.X > window.MaxX ||319 ref.Y < window.MinY || ref.Y > window.MaxY {320 continue321 }322 path, format, err := a.Raster(world, ref)323 if errors.Is(err, os.ErrNotExist) {324 continue325 }326 if err != nil {327 return nil, false, err328 }329 seen[key] = true330 out = append(out, Tile{Ref: ref, Path: path, Format: format})331 }332 return out, want > 0 && len(out) == want, nil333}334335// boundsOf is the part of the world square a level actually draws, measured from336// the tiles that are not the level's own background filler.337//338// The window a raster is cut from is not the ground a picture is about. Several339// sheets are drawn inside a printed border or a wide margin of nothing, and340// dividing that whole window up spends most of it on blank paper. Only an341// unambiguous filler tile -- one that is more than half the level -- is treated342// as empty space, so a picture whose real content happens to repeat is never343// punched full of holes.344func boundsOf(tiles []Tile, zoom int, frame Frame) *Box {345 filler := placeholder(tiles)346 minX, minY := math.MaxInt, math.MaxInt347 maxX, maxY := -1, -1348 for _, tile := range tiles {349 if filler != "" && tile.Ref.ContentHash == filler {350 continue351 }352 minX, minY = min(minX, tile.Ref.X), min(minY, tile.Ref.Y)353 maxX, maxY = max(maxX, tile.Ref.X), max(maxY, tile.Ref.Y)354 }355 if maxX < minX || maxY < minY {356 return nil357 }358 // Bounds are reported in world space, which is sized at this picture's own359 // reference zoom -- the level whose pixels are its units. A shallower level360 // covers more world per tile and a deeper one covers less, so the tile pitch361 // scales both ways.362 reference := frame.BaseZoom + worldZoomLevels363 origin := frame.Origin(zoom)364 pitch, divisor := TileSize, 1365 if zoom < reference {366 pitch = TileSize << (reference - zoom)367 } else if zoom > reference {368 divisor = 1 << (zoom - reference)369 }370 box := &Box{371 X: (minX - origin) * pitch / divisor,372 Y: (minY - origin) * pitch / divisor,373 Width: (maxX - minX + 1) * pitch / divisor,374 Height: (maxY - minY + 1) * pitch / divisor,375 }376 if box.X == 0 && box.Y == 0 && box.Width == WorldSize && box.Height == WorldSize {377 return nil378 }379 return box380}381382// placeholder is the content hash of a level's background tile, or "" when no383// single tile holds a majority. A level with no clear filler is drawn whole.384func placeholder(tiles []Tile) string {385 counts := make(map[string]int, len(tiles))386 var dominant string387 for _, tile := range tiles {388 counts[tile.Ref.ContentHash]++389 if counts[tile.Ref.ContentHash] > counts[dominant] {390 dominant = tile.Ref.ContentHash391 }392 }393 if dominant == "" || counts[dominant] <= len(tiles)/2 {394 return ""395 }396 return dominant397}398399func decimal(zoom int) string {400 if zoom < 0 {401 return fmt.Sprint(zoom)402 }403 // Small, hot, and always a plain decimal: the zooms in play are 0..25.404 const digits = "0123456789"405 if zoom < 10 {406 return digits[zoom : zoom+1]407 }408 return fmt.Sprint(zoom)409}