dymokomi/luce-image
Source of release 0.45.1
0.45.1 / src / selection_sources.lucb
## Selections made from pixels read a cell at a time: a layer's transparency
## (or mask) loaded as the selection, and the magic wand. Nothing the size of
## the document is ever held. The pixels come through a `Reader` (a layer's
## tiles, the composited picture, or a test's buffer) as straight-alpha RGBA
## half floats. GPU sources are read 64 cells to a read batch on the calling
## thread (the GPU's), two batches in turn: while every processor turns one
## batch into coverage straight from the readback memory, the next is already
## on the GPU. Half floats have 65536 values, so
## each conversion is a table lookup.
##
## The wand's matching pixels become a selection of their own (`near`), cells
## wholly matching or wholly not costing nothing; a contiguous wand then
## floods through it from the seed, a cell that matches wholly being taken at
## once and only mixed cells being walked pixel by pixel.
from luce_gpu import gpu
from luce_std import math
from luce_color import transfer
import memory
from luce_canvas.tiles import tile_size
from luce_canvas.half import from_half
from selection_cells import Cells, Mode, block_bytes, each
from selection_shapes import combine_cell, combine_value
from luce_raster.errors import invalid
## Bytes of one cell's pixels as half floats, rows of 256.
let cell_halves: usize = 524288
## Cells read before they are converted together.
let batch_cells: usize = 32
## Where pixels come from, a cell at a time (`cpu_reader`, `gpu_reader`).
## A CPU source's `read(context, column, row, halves)` fills `halves` (rows of
## 256 pixels, 8 bytes each, as many rows as the cell has) and is true, or is
## false for a cell wholly transparent and leaves `halves` alone. A GPU
## source's `texture(context, column, row)` is the cell's tile (256 wide,
## rgba16f) or none where it is transparent; its cells are read in batches.
pub struct Reader:
pub var context: void*?
pub var read: func(void*?, u32, u32, u8[]) -> bool!
pub var texture: func(void*?, u32, u32) -> gpu.Texture?!
pub var device: gpu.Device
pub var batched: bool
## A reader of pixels the CPU already has.
pub func cpu_reader(context: void*?, read: func(void*?, u32, u32, u8[]) -> bool!) -> Reader:
return Reader(context = context, read = read, texture = no_texture, device = gpu.Device(), batched = false)
## A reader of tiles on `device`, read back in batches.
pub func gpu_reader(context: void*?, device: gpu.Device, texture: func(void*?, u32, u32) -> gpu.Texture?!) -> Reader:
return Reader(context = context, read = no_read, texture = texture, device = device, batched = true)
func no_texture(context: void*?, column: u32, row: u32) -> gpu.Texture?!:
_ = context
_ = column
_ = row
return none
func no_read(context: void*?, column: u32, row: u32, halves: u8[]) -> bool!:
_ = context
_ = column
_ = row
_ = halves
return false
## One cell through `reader` into `halves`: whether it is painted.
func read_one(cells: const Cells*, reader: Reader, column: u32, row: u32, halves: u8[]) -> bool!:
if not reader.batched:
return try reader.read(reader.context, column, row, halves)
let texture = (try reader.texture(reader.context, column, row)) else return false
let rows = min_u32(tile_size, cells.extent_y - row * tile_size)
try texture.read(halves[..<(usize)rows * (usize)tile_size * 8], gpu.Region(0, 0, tile_size, rows))
return true
func min_u32(a: u32, b: u32) -> u32:
return a if a < b else b
# mark: Loading =================================================================================
## Channel `channel` of every pixel as coverage, combined into `cells` by
## `mode`; a transparent cell's coverage is `blank` (a mask never painted
## shows everything).
pub func load(cells: Cells*, reader: Reader, channel: usize, blank: u8, mode: Mode) -> !:
if channel > 3:
error(invalid, "a pixel has four channels")
let table = try new u8[65536] --- in memory.heap
defer free(table) in memory.heap
for bits in 0..<(usize)65536:
table[bits] = coverage_byte(from_half((u16)bits))
var no_indices: usize[]
var no_halves: u8[]
var no_ranges: u8[]
var no_ranged: bool[]
var job = CellJob(cells = cells, table = table, channel = channel, mode = mode, low = [0, 0, 0, 0], high = [0, 0, 0, 0], limit = 0, only = none,
ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
try read_batches(cells, reader, &job, load_item, blank)
## Coverage for cell `job.indices[item]` from its halves.
func load_item(context: void*?, item: usize):
let job = (CellJob*)(context else return)
let index = job.indices[item]
let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
let shape = new u8[block_bytes] --- in memory.heap catch failure:
trap("out of memory loading a selection")
defer free(shape) in memory.heap
memory.set(shape, 0)
let width = (usize)job.cells.cell_width(index)
for y in 0..<(usize)job.cells.cell_height(index):
for x in 0..<width:
let at = (y * (usize)tile_size + x) * 8 + job.channel * 2
shape[y * (usize)tile_size + x] = job.table[(usize)((u16)halves[at] | ((u16)halves[at + 1] << 8))]
combine_cell(job.cells, index, shape, job.mode)
## Into `target` (empty to begin with): the pixels' perceptual lightness as a
## byte, 0 where transparent, for every cell `only` selects anything in, read
## a batch at a time: the guide Select and Mask's edge detection follows.
pub func luma(target: Cells*, reader: Reader, only: const Cells*) -> !:
var no_indices: usize[]
var no_halves: u8[]
var no_ranges: u8[]
var no_ranged: bool[]
var no_table: u8[]
var job = CellJob(cells = target, table = no_table, channel = 0, mode = Mode.replace, low = [0, 0, 0, 0], high = [0, 0, 0, 0], limit = 0, only = only,
ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
try read_batches(target, reader, &job, luma_item, 0)
## Lightness for cell `job.indices[item]` from its halves: straight linear
## light weighted as Rec. 709, square-rooted (about gamma 2), times alpha.
func luma_item(context: void*?, item: usize):
let job = (CellJob*)(context else return)
let index = job.indices[item]
let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
let bytes = job.cells.fresh(index)
memory.set(bytes, 0)
let width = (usize)job.cells.cell_width(index)
for y in 0..<(usize)job.cells.cell_height(index):
for x in 0..<width:
let at = (y * (usize)tile_size + x) * 8
let red = (f64)from_half((u16)halves[at] | ((u16)halves[at + 1] << 8))
let green = (f64)from_half((u16)halves[at + 2] | ((u16)halves[at + 3] << 8))
let blue = (f64)from_half((u16)halves[at + 4] | ((u16)halves[at + 5] << 8))
let alpha = math.clamp((f64)from_half((u16)halves[at + 6] | ((u16)halves[at + 7] << 8)), 0.0, 1.0)
let light = math.sqrt(math.clamp(0.2126 * red + 0.7152 * green + 0.0722 * blue, 0.0, 1.0)) * alpha
bytes[y * (usize)tile_size + x] = (u8)math.imin(255, (i64)(light * 255.0 + 0.5))
# mark: The magic wand ==========================================================================
## Into `found` (empty to begin with): the pixels within `tolerance` (0..255,
## 8-bit sRGB, alpha included) of the color at (`x`, `y`), averaged over a
## `sample` by `sample` square, only those reachable from it through such
## pixels when `contiguous`. The seed pixel is always found.
pub func wand(found: Cells*, reader: Reader, x: i64, y: i64, sample: i64, tolerance: f64, contiguous: bool) -> !:
if x < 0 or y < 0 or x >= (i64)found.extent_x or y >= (i64)found.extent_y:
error(invalid, "the wand point lies outside the document")
if not math.is_finite(tolerance) or tolerance < 0.0 or tolerance > 255.0:
error(invalid, "wand tolerance is 0..255")
if sample != 1 and sample != 3 and sample != 5:
error(invalid, "the wand samples 1, 3 or 5 pixels square")
let table = try new u8[131072] --- in memory.heap
defer free(table) in memory.heap
for bits in 0..<(usize)65536:
let value = from_half((u16)bits)
table[bits] = transfer.srgb_byte((f64)value)
table[65536 + bits] = coverage_byte(value)
var no_indices: usize[]
var no_halves: u8[]
var no_ranges: u8[]
var no_ranged: bool[]
let seed = try seed_color(found, reader, x, y, sample // 2)
var job = CellJob(cells = found, table = table, channel = 0, mode = Mode.add, low = seed, high = seed,
limit = (i64)math.floor(tolerance + 0.5), only = none, ranges = no_ranges, ranged = no_ranged, indices = no_indices, halves = no_halves)
# A transparent cell matches wholly or not at all.
let clear: u8[4] = [0, 0, 0, 0]
let blank: u8 = 255 if job.matches(clear) else 0
var near = try Cells.create(found.extent_x, found.extent_y)
defer near.destroy()
job.cells = &near
try read_batches(&near, reader, &job, match_item, blank)
# The seed itself, whatever its own color against the average.
let seed_cell = (usize)(y // (i64)tile_size) * (usize)near.columns() + (usize)(x // (i64)tile_size)
if near.uniform(seed_cell) != 255:
near.writable(seed_cell)[(usize)(y % (i64)tile_size) * (usize)tile_size + (usize)(x % (i64)tile_size)] = 255
if not contiguous:
for index in 0..<near.count():
found.share(index, &near, index)
return
try flood(&near, found, x, y)
# mark: Grow and Similar ======================================================================
## Select › Grow (`contiguous`) and Similar, into `found` (empty to begin
## with): the pixels whose color (8-bit sRGB and alpha) lies within
## `tolerance` of the range of colors `selection` covers (its pixels wholly
## selected, or any selected where none is), reachable from the
## selection through such pixels when `contiguous`. Only the cells the
## selection touches are read for the range; every cell for the matches.
pub func grow(found: Cells*, selection: const Cells*, reader: Reader, tolerance: f64, contiguous: bool) -> !:
if not math.is_finite(tolerance) or tolerance < 0.0 or tolerance > 255.0:
error(invalid, "tolerance is 0..255")
let table = try new u8[131072] --- in memory.heap
defer free(table) in memory.heap
for bits in 0..<(usize)65536:
let value = from_half((u16)bits)
table[bits] = transfer.srgb_byte((f64)value)
table[65536 + bits] = coverage_byte(value)
let count = found.count()
# Per cell: lows and highs at half coverage, then at any coverage.
let ranges = try new u8[count * 16] --- in memory.heap
defer free(ranges) in memory.heap
let ranged = try new bool[count * 2] --- in memory.heap
defer free(ranged) in memory.heap
for index in 0..<ranged.length:
ranged[index] = false
var no_indices: usize[]
var no_halves: u8[]
var job = CellJob(cells = found, table = table, channel = 0, mode = Mode.add, low = [0, 0, 0, 0], high = [255, 255, 255, 255],
limit = (i64)math.floor(tolerance + 0.5), only = selection, ranges = ranges, ranged = ranged, indices = no_indices, halves = no_halves)
# The selection over transparent cells: their color is clear.
var transparent = false
var scratch = try Cells.create(found.extent_x, found.extent_y)
defer scratch.destroy()
var range_job = job
range_job.cells = &scratch
range_job.selection = selection
# Cells the selection touches that hold no pixels come back 255 here.
try read_batches(&scratch, reader, &range_job, range_item, 255)
for index in 0..<count:
if selection.uniform(index) != 0 and scratch.uniform(index) != 0:
transparent = true
if not merge_ranges(&job, ranges, ranged, count, 0, transparent) and not merge_ranges(&job, ranges, ranged, count, 1, transparent):
return
let clear: u8[4] = [0, 0, 0, 0]
let blank: u8 = 255 if job.matches(clear) else 0
var near = try Cells.create(found.extent_x, found.extent_y)
defer near.destroy()
job.cells = &near
job.only = none
try read_batches(&near, reader, &job, match_item, blank)
if not contiguous:
for index in 0..<near.count():
found.share(index, &near, index)
return
try flood_from(&near, found, selection)
## Merge the cells' ranges at `level` (0 half coverage, 1 any) into the job's
## low and high; `transparent` adds clear. Whether any color was found.
func merge_ranges(job: CellJob*, ranges: const u8[], ranged: const bool[], count: usize, level: usize, transparent: bool) -> bool:
var found = false
var low: u8[4] = [255, 255, 255, 255]
var high: u8[4] = [0, 0, 0, 0]
if transparent:
found = true
low = [0, 0, 0, 0]
for index in 0..<count:
if not ranged[index * 2 + level]:
continue
found = true
let at = index * 16 + level * 8
for channel in 0..<(usize)4:
low[channel] = ranges[at + channel] if ranges[at + channel] < low[channel] else low[channel]
high[channel] = ranges[at + 4 + channel] if ranges[at + 4 + channel] > high[channel] else high[channel]
if found:
job.low = low
job.high = high
return found
## Grow's first pass: the range of colors under the selection in cell
## `job.indices[item]`, at half coverage and at any.
func range_item(context: void*?, item: usize):
let job = (CellJob*)(context else return)
let index = job.indices[item]
let selection = job.selection else return
let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
let value = selection.uniform(index)
let bytes = (selection.block(index) else trap("a mixed cell has a block")).bytes if value < 0 else no_bytes()
var low: u8[8] = [255, 255, 255, 255, 255, 255, 255, 255]
var high: u8[8] = [0, 0, 0, 0, 0, 0, 0, 0]
var any: bool[2] = [false, false]
var color: u8[4] = [0, 0, 0, 0]
let width = (usize)selection.cell_width(index)
for y in 0..<(usize)selection.cell_height(index):
for x in 0..<width:
let coverage = (u8)value if value >= 0 else bytes[y * (usize)tile_size + x]
if coverage == 0:
continue
let at = (y * (usize)tile_size + x) * 8
for channel in 0..<(usize)4:
let bits = (usize)((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
color[channel] = job.table[bits + (65536 if channel == 3 else 0)]
for level in 0..<(usize)2:
# The range is the selection's solid colors: an anti-aliased
# edge blends in the neighbours' colors and would let Grow
# spread into them. Partial coverage counts only when nothing
# is wholly selected.
if level == 0 and coverage < 255:
continue
any[level] = true
for channel in 0..<(usize)4:
low[level * 4 + channel] = color[channel] if color[channel] < low[level * 4 + channel] else low[level * 4 + channel]
high[level * 4 + channel] = color[channel] if color[channel] > high[level * 4 + channel] else high[level * 4 + channel]
for level in 0..<(usize)2:
job.ranged[index * 2 + level] = any[level]
for channel in 0..<(usize)4:
job.ranges[index * 16 + level * 8 + channel] = low[level * 4 + channel]
job.ranges[index * 16 + level * 8 + 4 + channel] = high[level * 4 + channel]
func no_bytes() -> u8[]:
var nothing: u8[]
return nothing
## The color the wand matches against, as 8-bit sRGB and alpha: the mean of
## the pixels within `reach` of (`x`, `y`) inside the document.
func seed_color(cells: const Cells*, reader: Reader, x: i64, y: i64, reach: i64) -> u8[4]!:
let halves = try new u8[cell_halves] --- in memory.heap
defer free(halves) in memory.heap
var sum: f64[4] = [0.0, 0.0, 0.0, 0.0]
var count = 0.0
# Row by row, as the pixels come, so the sum is the same whatever the cells.
var read_column: i64 = -1
var read_row: i64 = -1
var painted = false
for dy in -reach..<(reach + 1):
for dx in -reach..<(reach + 1):
let px = x + dx
let py = y + dy
if px < 0 or py < 0 or px >= (i64)cells.extent_x or py >= (i64)cells.extent_y:
continue
let column = px // (i64)tile_size
let row = py // (i64)tile_size
if column != read_column or row != read_row:
painted = try read_one(cells, reader, (u32)column, (u32)row, halves)
read_column = column
read_row = row
count += 1.0
if not painted:
continue
let at = ((usize)(py % (i64)tile_size) * (usize)tile_size + (usize)(px % (i64)tile_size)) * 8
for channel in 0..<(usize)4:
sum[channel] += (f64)from_half((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
var seed: u8[4] = [0, 0, 0, 0]
for channel in 0..<(usize)3:
seed[channel] = transfer.srgb_byte((f64)(f32)(sum[channel] / count))
seed[3] = coverage_byte((f32)(sum[3] / count))
return seed
## Which pixels of cell `job.indices[item]` match the seed.
func match_item(context: void*?, item: usize):
let job = (CellJob*)(context else return)
let index = job.indices[item]
let halves = job.halves[item * cell_halves..<(item + 1) * cell_halves]
let shape = new u8[block_bytes] --- in memory.heap catch failure:
trap("out of memory for the magic wand")
defer free(shape) in memory.heap
memory.set(shape, 0)
let width = (usize)job.cells.cell_width(index)
var color: u8[4] = [0, 0, 0, 0]
for y in 0..<(usize)job.cells.cell_height(index):
for x in 0..<width:
let at = (y * (usize)tile_size + x) * 8
for channel in 0..<(usize)4:
let bits = (usize)((u16)halves[at + channel * 2] | ((u16)halves[at + channel * 2 + 1] << 8))
color[channel] = job.table[bits + (65536 if channel == 3 else 0)]
if job.matches(color):
shape[y * (usize)tile_size + x] = 255
combine_cell(job.cells, index, shape, Mode.add)
# mark: Reading in batches ======================================================================
## One pass over a batch of cells: what they are turned into, and how.
struct CellJob:
var cells: Cells*
var table: const u8[]
var channel: usize
var mode: Mode
## The colors matched: each channel from `low` to `high` (the wand's
## seed for both), and how far a channel may stray past them.
var low: u8[4]
var high: u8[4]
var limit: i64
## When set, only the cells where it selects anything are read.
var only: const Cells*?
## Grow and Similar: each cell's range of selected colors, 8 bytes a cell
## (four lows then four highs), and whether it has any.
var ranges: u8[]
var ranged: bool[]
## Grow's selection, whose covered pixels give the range.
var selection: const Cells*? = none
## The batch: the cells, and their halves one after another.
var indices: usize[]
var halves: const u8[]
## Whether `color` is within the limit of the colors matched on every channel.
func matches(color: u8[4]) -> bool:
for channel in 0..<(usize)4:
let value = (i64)color[channel]
if value < (i64)self.low[channel] - self.limit or value > (i64)self.high[channel] + self.limit:
return false
return true
## Every cell of `cells` read through `reader` and handed to `work` a batch
## at a time on every processor; a transparent cell is `blank` throughout,
## combined by the job's mode here.
func read_batches(cells: Cells*, reader: Reader, job: CellJob*, work: func(void*?, usize) -> unit, blank: u8) -> !:
if reader.batched:
try read_gpu_batches(cells, reader, job, work, blank)
return
let indices = try new usize[batch_cells] --- in memory.heap
defer free(indices) in memory.heap
let halves = try new u8[batch_cells * cell_halves] --- in memory.heap
defer free(halves) in memory.heap
var filled: usize = 0
for index in 0..<cells.count():
let column = (u32)(index % (usize)cells.columns())
let row = (u32)(index // (usize)cells.columns())
if skipped(job.only, index):
if filled > 0 and index + 1 == cells.count():
job.indices = indices[..<filled]
job.halves = halves
each(filled, (void*)job, work)
filled = 0
continue
if try reader.read(reader.context, column, row, halves[filled * cell_halves..<(filled + 1) * cell_halves]):
indices[filled] = index
filled += 1
else:
combine_value(cells, index, blank, job.mode)
if filled == batch_cells or (filled > 0 and index + 1 == cells.count()):
job.indices = indices[..<filled]
job.halves = halves
each(filled, (void*)job, work)
filled = 0
## One of the two read batches a GPU source's cells go through, and which
## cells it holds (its halves one after another from offset 0).
struct CellRead:
var batch: gpu.ReadBatch
var indices: usize[]
var filled: usize
## `read_batches` for a GPU source: cells recorded into one read batch while
## the other's are worked on, straight from the readback memory.
func read_gpu_batches(cells: Cells*, reader: Reader, job: CellJob*, work: func(void*?, usize) -> unit, blank: u8) -> !:
var reads: CellRead[2] = [CellRead(batch = try gpu.ReadBatch.begin(reader.device)), CellRead(batch = gpu.ReadBatch())]
defer release_cell_read(&reads[0])
reads[1].batch = try gpu.ReadBatch.begin(reader.device)
defer release_cell_read(&reads[1])
let per_batch = reads[0].batch.capacity() // cell_halves
for index in 0..<(usize)2:
reads[index].indices = try new usize[per_batch] --- in memory.heap
var next: usize = 0
next = try fill_cell_read(cells, reader, &reads[0], next, blank, job.mode, job.only)
next = try fill_cell_read(cells, reader, &reads[1], next, blank, job.mode, job.only)
var turn: usize = 0
while reads[turn].filled > 0:
let current = &reads[turn]
try current.batch.wait()
job.indices = current.indices[..<current.filled]
job.halves = try current.batch.bytes(0, current.filled * cell_halves)
each(current.filled, (void*)job, work)
next = try fill_cell_read(cells, reader, current, next, blank, job.mode, job.only)
turn = 1 - turn
## Record cells from `next` on into `target` until it is full and submit it;
## transparent cells are combined as `blank` on the way. Where the list continues.
func fill_cell_read(cells: Cells*, reader: Reader, target: CellRead*, next: usize, blank: u8, mode: Mode, only: const Cells*?) -> usize!:
try target.batch.reset()
target.filled = 0
var index = next
while index < cells.count() and target.filled < target.indices.length:
if skipped(only, index):
index += 1
continue
let column = (u32)(index % (usize)cells.columns())
let row = (u32)(index // (usize)cells.columns())
if let texture = try reader.texture(reader.context, column, row):
# Cells of halves one after another: each offset is a whole cell on.
let offset = (try target.batch.reserve(cell_halves)) else break
let rows = min_u32(tile_size, cells.extent_y - row * tile_size)
try target.batch.copy(texture, gpu.Region(0, 0, tile_size, rows), offset)
target.indices[target.filled] = index
target.filled += 1
else:
combine_value(cells, index, blank, mode)
index += 1
if target.filled > 0:
try target.batch.submit()
return index
## Whether cell `index` is left out: `only` selects nothing there.
func skipped(only: const Cells*?, index: usize) -> bool:
let limit = only else return false
return limit.uniform(index) == 0
func release_cell_read(target: CellRead*):
target.batch.finish()
if target.indices.length > 0:
free(target.indices) in memory.heap
var none_left: usize[]
target.indices = none_left
# mark: The flood ===============================================================================
## A growing stack of places to reach: a cell and a pixel in it, packed.
struct Places:
var items: u64[]
var count: usize
func push(index: usize, x: i64, y: i64) -> !:
if self.count == self.items.length:
let grown = try new u64[(usize)math.imax(4096, (i64)self.items.length * 2)] --- in memory.heap
if self.count > 0:
memory.copy(grown, self.items, self.count)
if self.items.length > 0:
free(self.items) in memory.heap
self.items = grown
self.items[self.count] = ((u64)index << 16) | ((u64)y << 8) | (u64)x
self.count += 1
func destroy():
if self.items.length > 0:
free(self.items) in memory.heap
## Into `found`: every pixel of `near` reachable from (`x`, `y`) through
## pixels of `near`, sideways and up and down.
func flood(near: Cells*, found: Cells*, x: i64, y: i64) -> !:
var none_yet: u64[]
var places = Places(items = none_yet, count = 0)
defer places.destroy()
let queue = try new u16[65536] --- in memory.heap
defer free(queue) in memory.heap
let columns = (usize)near.columns()
try places.push((usize)(y // (i64)tile_size) * columns + (usize)(x // (i64)tile_size), x % (i64)tile_size, y % (i64)tile_size)
try drain(near, found, &places, queue)
## Into `found`: every pixel of `near` reachable from a pixel `seeds` at
## least half selects, through pixels of `near`: Select › Grow.
func flood_from(near: Cells*, found: Cells*, seeds: const Cells*) -> !:
var none_yet: u64[]
var places = Places(items = none_yet, count = 0)
defer places.destroy()
let queue = try new u16[65536] --- in memory.heap
defer free(queue) in memory.heap
for index in 0..<near.count():
let seed = seeds.uniform(index)
let kind = near.uniform(index)
if seed == 0 or kind == 0 or found.uniform(index) == 255:
continue
let seed_bytes = (seeds.block(index) else trap("a mixed cell has a block")).bytes if seed < 0 else no_bytes()
let width = seeds.cell_width(index)
let height = seeds.cell_height(index)
if kind == 255:
# Any seed in a cell matching wholly reaches all of it.
var seeded = seed >= 128
if seed < 0:
for y in 0..<height:
for x in 0..<width:
if seed_bytes[(usize)y * (usize)tile_size + (usize)x] >= 128:
seeded = true
break
if seeded:
break
if seeded:
found.fill(index, 255)
try spill(near, found, &places, index)
continue
let matching = (near.block(index) else continue).bytes
var reached: u8[] = no_bytes()
for y in 0..<height:
for x in 0..<width:
let at = (usize)y * (usize)tile_size + (usize)x
let covered = (u8)seed if seed >= 0 else seed_bytes[at]
if covered < 128 or matching[at] == 0:
continue
if reached.length == 0:
reached = found.writable(index)
if reached[at] != 255:
try walk(near, found, &places, index, matching, reached, queue, at)
try drain(near, found, &places, queue)
## Reach every place on `places`, and every place reaching them leads to.
func drain(near: Cells*, found: Cells*, places: Places*, queue: u16[]) -> !:
while places.count > 0:
places.count -= 1
let item = places.items[places.count]
let index = (usize)(item >> 16)
let px = (i64)(item & 0xff)
let py = (i64)((item >> 8) & 0xff)
if found.uniform(index) == 255:
continue
let kind = near.uniform(index)
if kind == 0:
continue
if kind == 255:
# A cell matching wholly is reached wholly; on into its neighbours.
found.fill(index, 255)
try spill(near, found, places, index)
continue
let matching = (near.block(index) else continue).bytes
let reached = found.writable(index)
let start = (usize)py * (usize)tile_size + (usize)px
if reached[start] == 255 or matching[start] == 0:
continue
try walk(near, found, places, index, matching, reached, queue, start)
## The pixels of mixed cell `index` reachable from `start` inside it; the
## places past its sides go on `places` for the cells beside.
func walk(near: const Cells*, found: const Cells*, places: Places*, index: usize, matching: const u8[], reached: u8[], queue: u16[], start: usize) -> !:
let width = near.cell_width(index)
let height = near.cell_height(index)
let column = (i64)(index % (usize)near.columns())
let row = (i64)(index // (usize)near.columns())
reached[start] = 255
queue[0] = (u16)start
var head: usize = 0
var tail: usize = 1
while head < tail:
let at = (usize)queue[head]
head += 1
let px = (i64)(at % (usize)tile_size)
let py = (i64)(at // (usize)tile_size)
for step in 0..<(usize)4:
let nx = px + (1 if step == 0 else (-1 if step == 1 else 0))
let ny = py + (1 if step == 2 else (-1 if step == 3 else 0))
if nx >= 0 and ny >= 0 and nx < width and ny < height:
let next = (usize)ny * (usize)tile_size + (usize)nx
if matching[next] != 0 and reached[next] != 255:
reached[next] = 255
queue[tail] = (u16)next
tail += 1
continue
# Past the cell's side: the cell beside, when inside the document.
let beside_column = column + (1 if nx >= width else (-1 if nx < 0 else 0))
let beside_row = row + (1 if ny >= height else (-1 if ny < 0 else 0))
if beside_column < 0 or beside_row < 0 or beside_column >= (i64)near.columns() or beside_row >= (i64)near.rows():
continue
let beside = (usize)beside_row * (usize)near.columns() + (usize)beside_column
try offer(near, found, places, beside, (nx + (i64)tile_size) % (i64)tile_size, (ny + (i64)tile_size) % (i64)tile_size)
## A place in cell `index` onto `places`, unless it plainly leads nowhere.
func offer(near: const Cells*, found: const Cells*, places: Places*, index: usize, x: i64, y: i64) -> !:
if found.uniform(index) == 255:
return
let kind = near.uniform(index)
if kind == 0:
return
if kind < 0:
let matching = (near.block(index) else return).bytes
if matching[(usize)y * (usize)tile_size + (usize)x] == 0:
return
try places.push(index, x, y)
## From cell `index`, reached wholly: every place along its sides into the
## cells beside (one place will do for a cell that matches wholly).
func spill(near: const Cells*, found: const Cells*, places: Places*, index: usize) -> !:
let columns = (i64)near.columns()
let column = (i64)index % columns
let row = (i64)index // columns
let width = near.cell_width(index)
let height = near.cell_height(index)
for side in 0..<(usize)4:
let beside_column = column + (1 if side == 0 else (-1 if side == 1 else 0))
let beside_row = row + (1 if side == 2 else (-1 if side == 3 else 0))
if beside_column < 0 or beside_row < 0 or beside_column >= columns or beside_row >= (i64)near.rows():
continue
let beside = (usize)(beside_row * columns + beside_column)
# Along the shared side: its pixels in the cell beside.
let along = height if side < 2 else width
for step in 0..<along:
let x = (0 if side == 0 else (near.cell_width(beside) - 1 if side == 1 else step))
let y = (0 if side == 2 else (near.cell_height(beside) - 1 if side == 3 else step))
try offer(near, found, places, beside, x, y)
if near.uniform(beside) == 255:
break
# mark: Conversions =============================================================================
## A sample 0..1 as coverage 0..255, rounded.
pub func coverage_byte(value: f32) -> u8:
return (u8)(math.clamp((f64)value, 0.0, 1.0) * 255.0 + 0.5)