1package tiles23import (4 "fmt"5 "image"6 "image/color"7 "math"8 "strconv"910 "github.com/FelineStateMachine/atlas/internal/generate/doc"11)1213// Warping keeps the lesser picture.14//15// When two sources picture one ground, one raster is usually the finer -- a16// publisher's own map beside a wiki's rasterized in-game rendering -- and a17// registry that simply served the finer one would throw the other away. Instead18// the lesser raster is resampled into the finer one's world and offered as one19// more picture of the same ground: nothing is discarded, both rasters answer to20// one grid, and every feature lands on either.21//22// # What this file does not decide23//24// It does not fit the alignment. Deciding that two readings picture one ground,25// and how, stands on the names they share, and that is alignment work the enrich26// lane owns (issue #5 ยง5.3) -- the same machinery cross-source merge stands on,27// written once. What arrives here is the fitted transformation as six numbers,28// an input to the derivation exactly as the donor's tiles are. That is why the29// stamp carries it: the same donor through a different transformation is a30// different picture, and a pyramid that quietly kept serving the old alignment31// would be wrong in a way nothing could see.32//33// The seam that fits an affine and hands it here is cmd/atlas, which is the one34// place both lanes are in scope. Neither lane imports the other.3536// PlanWarp decides the pyramid a donor picture becomes once it is resampled37// into a base picture's world.38//39// Two of its judgements are worth naming. The variant renders at the base-frame40// zoom nearest the donor's real resolution after the alignment's own scaling --41// deep enough to keep everything the donor drew, never so deep as to invent42// detail that was never there. And the plan lists exactly one captured level,43// the donor's deepest complete one, because that is what the warp samples: a44// stamp that named the donor's other levels would rebuild for a change that45// could not reach these tiles.46func PlanWarp(base, donor Plan, affine Affine, lensName string) Plan {47 effective := float64(WorldDepth(donor)) * affine.Scale()48 targetZoom := int(math.Round(math.Log2(effective / TileSize)))49 targetZoom = max(0, min(targetZoom, base.MaxFullZoom-base.Frame.BaseZoom))5051 return Plan{52 TileSet: donor.TileSet + "=>" + base.TileSet,53 Name: base.Name + "__aligned-" + doc.Slugify(donor.TileSet),54 // The variant is cut from the base picture's window, which is what55 // lets a reader switch between the two without the ground moving.56 Frame: base.Frame,57 Levels: map[int][]Tile{donor.MaxFullZoom: donor.Levels[donor.MaxFullZoom]},58 MaxFullZoom: targetZoom + base.Frame.BaseZoom,59 MaxSourceZoom: targetZoom + base.Frame.BaseZoom,60 // A resample is a new picture rather than a copy of an old one, so it61 // is written afresh as a photograph: smoothed when magnified, and62 // encoded the way every level this deriver writes is encoded.63 Format: "jpg",64 Interpolate: true,65 LensName: lensName,66 AlignedWith: base.TileSet,67 Warp: &Warp{68 Donor: &donor,69 Base: &base,70 Affine: affine,71 TargetZoom: targetZoom,72 },73 }74}7576// WorldDepth is the finest resolution a plan draws its world at, in pixels77// across the world square. It is what decides which of two readings is the78// picture worth aligning the other onto.79func WorldDepth(p Plan) int {80 return TileSize * (1 << (p.MaxFullZoom - p.Frame.BaseZoom))81}8283// Settle takes the collisions out of a set of planned names.84//85// Two sources capturing one volume name the same ground the same thing, so86// their pyramids would land in one directory. Every colliding plan -- all of87// them, never just the later one -- takes its publisher's own path into its88// name, so which pyramid is called what does not depend on the order an archive89// happened to list its captures in.90//91// It runs before anything is stamped, because a pyramid's name is part of what92// it is derived as, and before any warp is planned, because a warped variant is93// named after the picture it aligns onto.94func Settle(plans []Plan) {95 byName := make(map[string][]int, len(plans))96 for index := range plans {97 byName[plans[index].Name] = append(byName[plans[index].Name], index)98 }99 for _, colliders := range byName {100 if len(colliders) < 2 {101 continue102 }103 for _, at := range colliders {104 plans[at].Name += "__" + doc.Slugify(plans[at].TileSet)105 }106 }107}108109// deriveWarp renders the donor through the alignment into the base frame at the110// target zoom, then folds the shallower levels down exactly as every other111// pyramid is folded.112func deriveWarp(root string, plan Plan) (Pyramid, error) {113 warp := plan.Warp114 donor := warp.Donor115 captured := donor.Levels[donor.MaxFullZoom]116117 // Wherever the donor never drew, the donor's own background stands in: a118 // warped tile is opaque, and painting it black would put a hole in a119 // picture that simply ends there.120 backgroundHex, err := placeholderColor(captured, placeholder(captured))121 if err != nil {122 return Pyramid{}, err123 }124 background := parseHex(backgroundHex)125126 sampler, err := newSampler(donor, background)127 if err != nil {128 return Pyramid{}, err129 }130 inverse, ok := warp.Affine.Invert()131 if !ok {132 return Pyramid{}, fmt.Errorf("pyramid %s: the alignment is singular", plan.Name)133 }134135 // Where the donor's content lands in the base world, and the tiles that136 // covers at the zoom the variant renders at.137 bounds := warpedBounds(donor.Bounds, warp.Affine)138 first, last := warpedWindow(bounds, warp.TargetZoom)139140 targetZoom := warp.TargetZoom141 levelPixels := TileSize * (1 << targetZoom)142 span := float64(WorldSize) / float64(levelPixels)143 formats := make([]string, targetZoom+1)144 coverage := make(map[string]*Coverage)145 mask := &coverageMask{total: (1 << targetZoom) * (1 << targetZoom)}146147 for tileY := first[1]; tileY <= last[1]; tileY++ {148 for tileX := first[0]; tileX <= last[0]; tileX++ {149 raster := image.NewNRGBA(image.Rect(0, 0, TileSize, TileSize))150 drew := false151 for y := range TileSize {152 for x := range TileSize {153 baseX := (float64(tileX*TileSize+x) + 0.5) * span154 baseY := (float64(tileY*TileSize+y) + 0.5) * span155 donorX, donorY := inverse.Apply(baseX, baseY)156 sampled, drawn := sampler.at(donorX, donorY)157 if drawn {158 drew = true159 }160 raster.SetNRGBA(x, y, sampled)161 }162 }163 // A tile the donor never reached is not written at all: coverage164 // says nothing about it, and a reader falls back to the parent.165 if !drew {166 continue167 }168 if err := encode(tilePath(root, plan.Name, targetZoom, tileX, tileY, "jpg"),169 raster, "jpg"); err != nil {170 return Pyramid{}, err171 }172 mask.mark(tileX, tileY)173 }174 }175 formats[targetZoom] = "jpg"176 if built := mask.build(); built != nil {177 coverage[strconv.Itoa(targetZoom)] = built178 }179180 for localZoom := targetZoom - 1; localZoom >= 0; localZoom-- {181 built, err := deriveLevel(root, plan.Name, localZoom, formats[localZoom+1], "jpg", false, background)182 if err != nil {183 return Pyramid{}, err184 }185 formats[localZoom] = "jpg"186 if built != nil {187 coverage[strconv.Itoa(localZoom)] = built188 }189 }190 if len(coverage) == 0 {191 coverage = nil192 }193194 sourceZoom, firstTile := plan.Frame.Window()195 return Pyramid{196 TileSet: plan.TileSet,197 Name: plan.Name,198 MinZoom: 0,199 MaxZoom: targetZoom,200 FullZoom: targetZoom,201 SourceZoom: targetZoom + plan.Frame.BaseZoom,202 Window: Window{SourceZoom: sourceZoom, FirstTile: firstTile},203 Formats: formats,204 // The bounds are the warped content's, as measured, whether or not205 // that comes to the whole square: what the alignment reached is a fact206 // about this picture rather than a default that can be left out.207 Bounds: bounds,208 Interpolate: true,209 Background: backgroundHex,210 Coverage: coverage,211 LensName: plan.LensName,212 AlignedWith: plan.AlignedWith,213 }, nil214}215216// warpedBounds sends the donor's content box through the alignment and clips it217// to the base world.218func warpedBounds(box *Box, affine Affine) *Box {219 if box == nil {220 box = &Box{Width: WorldSize, Height: WorldSize}221 }222 minX, minY := math.Inf(1), math.Inf(1)223 maxX, maxY := math.Inf(-1), math.Inf(-1)224 for _, corner := range [4][2]float64{225 {float64(box.X), float64(box.Y)},226 {float64(box.X + box.Width), float64(box.Y)},227 {float64(box.X), float64(box.Y + box.Height)},228 {float64(box.X + box.Width), float64(box.Y + box.Height)},229 } {230 x, y := affine.Apply(corner[0], corner[1])231 minX, maxX = math.Min(minX, x), math.Max(maxX, x)232 minY, maxY = math.Min(minY, y), math.Max(maxY, y)233 }234 minX, minY = math.Max(minX, 0), math.Max(minY, 0)235 maxX, maxY = math.Min(maxX, WorldSize), math.Min(maxY, WorldSize)236 if maxX <= minX || maxY <= minY {237 return &Box{}238 }239 return &Box{240 X: int(minX),241 Y: int(minY),242 Width: int(math.Ceil(maxX)) - int(minX),243 Height: int(math.Ceil(maxY)) - int(minY),244 }245}246247// warpedWindow is the tile window one level covers a box with, clipped to the248// level.249func warpedWindow(box *Box, zoom int) (first, last [2]int) {250 levelPixels := TileSize * (1 << zoom)251 span := float64(WorldSize) / float64(levelPixels)252 edge := (1 << zoom) - 1253 return [2]int{254 max(0, int(float64(box.X)/span/TileSize)),255 max(0, int(float64(box.Y)/span/TileSize)),256 }, [2]int{257 min(edge, int(float64(box.X+box.Width)/span/TileSize)),258 min(edge, int(float64(box.Y+box.Height)/span/TileSize)),259 }260}261262// sampler reads a donor's deepest complete level as one continuous picture,263// decoding tiles as the warp first touches them and holding a bounded number of264// them decoded. A whole level is far larger than the warp of it.265type sampler struct {266 files map[[2]int]string267 decoded map[[2]int]*image.NRGBA268 order [][2]int269 origin int270 pixelScale float64 // level pixels per world pixel271 levelSpan int // level pixels across the level272 background color.NRGBA273}274275// sampled is how many decoded tiles the sampler holds at once.276const sampled = 256277278func newSampler(donor *Plan, background color.Color) (*sampler, error) {279 files := make(map[[2]int]string)280 for _, tile := range donor.Levels[donor.MaxFullZoom] {281 files[[2]int{tile.Ref.X, tile.Ref.Y}] = tile.Path282 }283 if len(files) == 0 {284 return nil, fmt.Errorf("donor %s holds no complete level to resample", donor.TileSet)285 }286 r, g, b, _ := background.RGBA()287 return &sampler{288 files: files,289 decoded: make(map[[2]int]*image.NRGBA),290 origin: donor.Frame.Origin(donor.MaxFullZoom),291 pixelScale: math.Pow(2, float64(donor.MaxFullZoom-donor.Frame.BaseZoom-worldZoomLevels)),292 levelSpan: TileSize * (1 << (donor.MaxFullZoom - donor.Frame.BaseZoom)),293 background: color.NRGBA{R: uint8(r >> 8), G: uint8(g >> 8), B: uint8(b >> 8), A: 0xff},294 }, nil295}296297// at reads the donor at a world coordinate, bilinearly, clamped within the tile298// that holds it. The second result says whether the donor drew here at all:299// outside the level, or over a tile the capture never held, it did not, and the300// background stands in.301func (s *sampler) at(worldX, worldY float64) (color.NRGBA, bool) {302 pixelX, pixelY := worldX*s.pixelScale, worldY*s.pixelScale303 if pixelX < 0 || pixelY < 0 ||304 pixelX >= float64(s.levelSpan) || pixelY >= float64(s.levelSpan) {305 return s.background, false306 }307 tileX, tileY := int(pixelX)/TileSize, int(pixelY)/TileSize308 raster, held := s.tile(tileX, tileY)309 if !held {310 return s.background, false311 }312 // Sampling is clamped inside the tile rather than reaching into its313 // neighbour: a seam a pixel wide is invisible, and a decoder held open for314 // every neighbour of every sample is not.315 localX := pixelX - float64(tileX*TileSize) - 0.5316 localY := pixelY - float64(tileY*TileSize) - 0.5317 x0 := clamp(int(math.Floor(localX)), 0, TileSize-1)318 y0 := clamp(int(math.Floor(localY)), 0, TileSize-1)319 x1, y1 := clamp(x0+1, 0, TileSize-1), clamp(y0+1, 0, TileSize-1)320 fx := math.Max(0, math.Min(1, localX-float64(x0)))321 fy := math.Max(0, math.Min(1, localY-float64(y0)))322323 blend := func(c00, c10, c01, c11 uint8) uint8 {324 top := float64(c00)*(1-fx) + float64(c10)*fx325 bottom := float64(c01)*(1-fx) + float64(c11)*fx326 return uint8(top*(1-fy) + bottom*fy + 0.5)327 }328 p00, p10 := raster.NRGBAAt(x0, y0), raster.NRGBAAt(x1, y0)329 p01, p11 := raster.NRGBAAt(x0, y1), raster.NRGBAAt(x1, y1)330 return color.NRGBA{331 R: blend(p00.R, p10.R, p01.R, p11.R),332 G: blend(p00.G, p10.G, p01.G, p11.G),333 B: blend(p00.B, p10.B, p01.B, p11.B),334 A: 0xff,335 }, true336}337338func (s *sampler) tile(x, y int) (*image.NRGBA, bool) {339 key := [2]int{x + s.origin, y + s.origin}340 if raster, seen := s.decoded[key]; seen {341 return raster, raster != nil342 }343 path, exists := s.files[key]344 if !exists {345 s.hold(key, nil)346 return nil, false347 }348 value, err := decode(path)349 if err != nil {350 // A tile that will not decode is a tile the donor did not draw. The351 // warp is a picture, and one unreadable capture must not stop it.352 s.hold(key, nil)353 return nil, false354 }355 raster := nrgba(value)356 s.hold(key, raster)357 return raster, true358}359360func (s *sampler) hold(key [2]int, raster *image.NRGBA) {361 if len(s.order) >= sampled {362 delete(s.decoded, s.order[0])363 s.order = s.order[1:]364 }365 s.decoded[key] = raster366 s.order = append(s.order, key)367}368369// nrgba is an image as straight-alpha bytes, copied only where it is not one370// already.371func nrgba(value image.Image) *image.NRGBA {372 if typed, ok := value.(*image.NRGBA); ok {373 return typed374 }375 bounds := value.Bounds()376 out := image.NewNRGBA(image.Rect(0, 0, bounds.Dx(), bounds.Dy()))377 for y := bounds.Min.Y; y < bounds.Max.Y; y++ {378 for x := bounds.Min.X; x < bounds.Max.X; x++ {379 r, g, b, _ := value.At(x, y).RGBA()380 out.SetNRGBA(x-bounds.Min.X, y-bounds.Min.Y, color.NRGBA{381 R: uint8(r >> 8), G: uint8(g >> 8), B: uint8(b >> 8), A: 0xff,382 })383 }384 }385 return out386}387388func clamp(value, low, high int) int { return max(low, min(high, value)) }