UnrealPrototyping/Tools/Terrain/internal/template/classify.go

package template

import (
	"fmt"
	"math"

	"salty/terrain/internal/field"
)

// Raster is a class index per pixel, row-major. X wraps; Y does not.
type Raster struct {
	W, H  int
	Class []uint8
}

// At reads a pixel, wrapping X and clamping Y, which is the convention every cylindrical map in this
// tree follows: the left and right edges are the same meridian, the top and bottom are the poles.
func (r *Raster) At(x, y int) uint8 {
	x = ((x % r.W) + r.W) % r.W
	if y < 0 {
		y = 0
	} else if y >= r.H {
		y = r.H - 1
	}
	return r.Class[y*r.W+x]
}

// Match is what the classifier saw, and it is the first thing to read when a template comes out wrong.
//
// Every pixel is assigned to its nearest class, so a colour the legend has never heard of does not fail
// the run - it quietly becomes whatever it happens to be closest to. Far and MaxDist are what make that
// visible.
type Match struct {
	Total   int
	Counts  []int // per class
	Far     int   // pixels further than the legend's WarnDistance from every class
	MaxDist float64
	MaxAt   [2]int // where the worst one was

	// The wrap: how well the painting's left and right edges agree. They are the same meridian, so a
	// template that does not wrap produces a real discontinuity down one line of the world and there is no
	// way to see it by looking at the picture - the two edges are as far apart on screen as they can be.
	WrapRows    int // rows compared
	WrapDiffer  int // rows where the two edges classify differently
	WrapLandSea int // rows where one edge is land and the other water: the visible kind
	WrapFarEdge int // pixels in the first or last two columns that no class is near
}

func (m Match) String() string {
	return fmt.Sprintf("%d px, %d further than the warn distance from any class (worst %.0f at %d,%d)",
		m.Total, m.Far, m.MaxDist, m.MaxAt[0], m.MaxAt[1])
}

// WrapReport is the one-line verdict on whether the painting is a cylinder.
func (m Match) WrapReport() string {
	if m.WrapRows == 0 {
		return "wrap not measured"
	}
	return fmt.Sprintf("the edges disagree on %d of %d rows (%.1f%%), %d of them land against water; "+
		"%d px in the outermost columns match no class",
		m.WrapDiffer, m.WrapRows, 100*float64(m.WrapDiffer)/float64(m.WrapRows), m.WrapLandSea, m.WrapFarEdge)
}

// measureWrap compares the first and last columns, which are the same meridian.
func (l *Legend) measureWrap(px []uint8, w, h int, r *Raster, m *Match) {
	if w < 2 {
		return
	}
	m.WrapRows = h
	warn2 := l.WarnDistance * l.WarnDistance
	for y := 0; y < h; y++ {
		a := r.Class[y*w]
		b := r.Class[y*w+w-1]
		if a != b {
			m.WrapDiffer++
			if l.Classes[a].Sea != l.Classes[b].Sea {
				m.WrapLandSea++
			}
		}
		// The outermost columns are where a lossy encoder leaves its halo, and a halo on the seam is a
		// stripe of the wrong class down the one line of the world where it cannot be hidden.
		for _, x := range [4]int{0, 1, w - 2, w - 1} {
			o := (y*w + x) * 3
			if float64(l.nearestDist2(int(px[o]), int(px[o+1]), int(px[o+2]))) > warn2 {
				m.WrapFarEdge++
			}
		}
	}
}

// nearestDist2 is the squared RGB distance to the closest painted class.
func (l *Legend) nearestDist2(r, g, b int) int {
	best := 1 << 30
	for ci := range l.Classes {
		c := &l.Classes[ci]
		if c.Derived {
			continue
		}
		dr, dg, db := r-c.RGB[0], g-c.RGB[1], b-c.RGB[2]
		if d := dr*dr + dg*dg + db*db; d < best {
			best = d
		}
	}
	return best
}

// Classify assigns every pixel to the nearest class in RGB.
//
// Nearest rather than within-a-tolerance, so the result is total: there is no unclassified pixel to
// decide what to do with later, and a stray artefact - a JPEG ringing overshoot, the one black pixel in
// the left column of the template this was written for - lands on something sensible instead of
// punching a hole in the world. The Match report is what says it happened.
func (l *Legend) Classify(px []uint8, w, h int) (*Raster, Match) {
	r := &Raster{W: w, H: h, Class: make([]uint8, w*h)}

	// Reduction into pre-allocated indexed slots, never a channel drain: the result must not depend on
	// which goroutine finished first (cross-cutting rule 12).
	partial := make([]Match, field.BandCount(h))
	for i := range partial {
		partial[i].Counts = make([]int, len(l.Classes))
	}
	warn2 := l.WarnDistance * l.WarnDistance

	field.RowsIndexed(h, func(band, y0, y1 int) {
		p := &partial[band]
		for y := y0; y < y1; y++ {
			for x := 0; x < w; x++ {
				o := (y*w + x) * 3
				cr, cg, cb := int(px[o]), int(px[o+1]), int(px[o+2])
				best, bestD := -1, 1<<30
				for ci := range l.Classes {
					c := &l.Classes[ci]
					if c.Derived {
						continue // never painted, so never matched
					}
					dr := cr - c.RGB[0]
					dg := cg - c.RGB[1]
					db := cb - c.RGB[2]
					d := dr*dr + dg*dg + db*db
					if d < bestD {
						bestD, best = d, ci
					}
				}
				r.Class[y*w+x] = uint8(best)
				p.Total++
				p.Counts[best]++
				if float64(bestD) > warn2 {
					p.Far++
				}
				if float64(bestD) > p.MaxDist {
					p.MaxDist = float64(bestD)
					p.MaxAt = [2]int{x, y}
				}
			}
		}
	})

	out := Match{Counts: make([]int, len(l.Classes))}
	out.MaxAt = [2]int{-1, -1}
	for i := range partial {
		p := &partial[i]
		out.Total += p.Total
		out.Far += p.Far
		for c, n := range p.Counts {
			out.Counts[c] += n
		}
		// The tie-break keeps the report itself independent of GOMAXPROCS, which changes how many bands
		// there are: without it two pixels at the same distance could be reported in either order.
		if p.Total > 0 && (p.MaxDist > out.MaxDist ||
			(p.MaxDist == out.MaxDist && earlier(p.MaxAt, out.MaxAt))) {
			out.MaxDist = p.MaxDist
			out.MaxAt = p.MaxAt
		}
	}
	out.MaxDist = math.Sqrt(out.MaxDist) // kept squared through the loops; reported as a distance
	l.measureWrap(px, w, h, r, &out)
	return r, out
}

func earlier(a, b [2]int) bool {
	if b[1] < 0 {
		return true
	}
	if a[1] != b[1] {
		return a[1] < b[1]
	}
	return a[0] < b[0]
}

// DissolveStrokes removes the decoration an artist drew and leaves only classes that mean something.
//
// Two rules, in this order:
//
//  1. A stroke region that touches the top or bottom row of the map is not a stroke. It becomes the
//     class its edge_class names. This is what tells a polar ice cap from the white outline drawn
//     around every island when both are painted the same white, and it is the whole reason the rule
//     exists.
//  2. Every remaining stroke pixel takes the class of the nearest pixel that is not a stroke, measured
//     outwards from all of them at once. A ring sitting between land and water is therefore split down
//     its middle rather than given wholly to one side, which is the only answer that does not move the
//     coastline by the width of the artist's brush.
//
// Returns how many pixels each rule rewrote.
func (r *Raster) DissolveStrokes(l *Legend) (edge, dissolved int) {
	stroke := make([]bool, len(l.Classes))
	any := false
	for i := range l.Classes {
		stroke[i] = l.Classes[i].Stroke
		any = any || stroke[i]
	}
	if !any {
		return 0, 0
	}

	edge = r.rewriteEdgeStrokes(l, stroke)

	// Rule 2. Seed from every non-stroke pixel that touches a stroke pixel, then walk outwards through
	// stroke pixels only. Seeds are pushed in raster order and the queue is FIFO, so the result does not
	// depend on anything but the image.
	queue := make([]int32, 0, 1<<16)
	filled := make([]bool, len(r.Class))
	for y := 0; y < r.H; y++ {
		for x := 0; x < r.W; x++ {
			i := y*r.W + x
			if stroke[r.Class[i]] {
				continue
			}
			if r.hasStrokeNeighbour(x, y, stroke) {
				queue = append(queue, int32(i))
				filled[i] = true
			}
		}
	}
	for head := 0; head < len(queue); head++ {
		i := int(queue[head])
		c := r.Class[i]
		x, y := i%r.W, i/r.W
		for _, n := range r.neighbours(x, y) {
			if n < 0 || filled[n] || !stroke[r.Class[n]] {
				continue
			}
			r.Class[n] = c
			filled[n] = true
			dissolved++
			queue = append(queue, int32(n))
		}
	}
	return edge, dissolved
}

// rewriteEdgeStrokes applies rule 1: flood each stroke class inwards from the poles.
func (r *Raster) rewriteEdgeStrokes(l *Legend, stroke []bool) int {
	n := 0
	stack := make([]int32, 0, 1<<16)
	for ci := range l.Classes {
		if !stroke[ci] {
			continue
		}
		to := l.EdgeIndex(ci)
		if to < 0 {
			continue
		}
		want := uint8(ci)
		become := uint8(to)
		stack = stack[:0]
		push := func(x, y int) {
			i := y*r.W + x
			if r.Class[i] == want {
				r.Class[i] = become
				n++
				stack = append(stack, int32(i))
			}
		}
		for x := 0; x < r.W; x++ {
			push(x, 0)
			push(x, r.H-1)
		}
		for len(stack) > 0 {
			i := int(stack[len(stack)-1])
			stack = stack[:len(stack)-1]
			x, y := i%r.W, i/r.W
			for _, m := range r.neighbours(x, y) {
				if m >= 0 && r.Class[m] == want {
					r.Class[m] = become
					n++
					stack = append(stack, int32(m))
				}
			}
		}
	}
	return n
}

// neighbours is the eight-connected neighbourhood with X wrapped and Y bounded. -1 means off the map,
// which only ever happens past a pole.
func (r *Raster) neighbours(x, y int) [8]int {
	var out [8]int
	k := 0
	for dy := -1; dy <= 1; dy++ {
		ny := y + dy
		for dx := -1; dx <= 1; dx++ {
			if dx == 0 && dy == 0 {
				continue
			}
			if ny < 0 || ny >= r.H {
				out[k] = -1
				k++
				continue
			}
			nx := x + dx
			if nx < 0 {
				nx += r.W
			} else if nx >= r.W {
				nx -= r.W
			}
			out[k] = ny*r.W + nx
			k++
		}
	}
	return out
}

func (r *Raster) hasStrokeNeighbour(x, y int, stroke []bool) bool {
	for _, n := range r.neighbours(x, y) {
		if n >= 0 && stroke[r.Class[n]] {
			return true
		}
	}
	return false
}