dymokomi/luce-image
Source of release 0.45.0
0.45.0 / src / selection_shapes.lucb
## Shapes drawn into a selection's cells (selection_cells.lucb), a cell at a
## time and on every processor: rectangles, ellipses, polygons, and coverage
## from elsewhere (another selection, or a byte a pixel).
## A cell the shape covers wholly or misses wholly is combined as one value,
## so only the cells along a shape's edge ever hold bytes.
##
## Modes here are add, subtract and intersect; replace is add onto cells
## cleared first, which the callers do.
from luce_std import math
import memory
from luce_canvas.tiles import tile_size
from selection_cells import Cells, Mode, block_bytes, each
## One pixel's coverage `current` combined with a shape's `value` by `mode`.
pub func mix(current: u8, value: u8, mode: Mode) -> u8:
if mode == Mode.subtract:
return current - (value if value < current else current)
if mode == Mode.intersect:
return value if value < current else current
return value if value > current else current
## A shape `value` throughout cell `index`, combined by `mode`.
pub func combine_value(cells: Cells*, index: usize, value: u8, mode: Mode):
let current = cells.uniform(index)
if current >= 0:
cells.fill(index, mix((u8)current, value, mode))
return
# Nothing changes: adding nothing, taking nothing away, or keeping all.
if (value == 0 and mode != Mode.intersect) or (value == 255 and mode == Mode.intersect):
return
if (value == 255 and mode == Mode.add) or (value == 255 and mode == Mode.subtract) or (value == 0 and mode == Mode.intersect):
cells.fill(index, 255 if mode == Mode.add else 0)
return
let bytes = cells.writable(index)
let width = (usize)cells.cell_width(index)
for y in 0..<(usize)cells.cell_height(index):
for x in 0..<width:
let at = y * (usize)tile_size + x
bytes[at] = mix(bytes[at], value, mode)
## A cell's worth of shape coverage (`shape`, rows of 256) combined into cell
## `index` by `mode`.
pub func combine_cell(cells: Cells*, index: usize, shape: const u8[], mode: Mode):
let width = (usize)cells.cell_width(index)
let height = (usize)cells.cell_height(index)
# One value throughout is combined as one.
let first = shape[0]
var same = true
for y in 0..<height:
let line = y * (usize)tile_size
for x in 0..<width:
if shape[line + x] != first:
same = false
break
if not same:
break
if same:
combine_value(cells, index, first, mode)
return
let current = cells.uniform(index)
if (current == 0 and mode != Mode.add) or (current == 255 and mode == Mode.add):
return
let bytes = cells.writable(index)
if current == 0 or (current == 255 and mode == Mode.intersect):
# Onto nothing, or cut from everything: the shape itself.
memory.copy(bytes, shape, block_bytes)
return
for y in 0..<height:
let line = y * (usize)tile_size
for x in 0..<width:
bytes[line + x] = mix(bytes[line + x], shape[line + x], mode)
## The cells a box of document pixels reaches: first and last-plus-one column and row.
struct Reach:
var left: usize
var top: usize
var right: usize
var bottom: usize
func reach(cells: const Cells*, left: i64, top: i64, right: i64, bottom: i64) -> Reach:
let span = (i64)tile_size
return Reach(left = (usize)(left // span), top = (usize)(top // span), right = (usize)((right + span - 1) // span), bottom = (usize)((bottom + span - 1) // span))
## A rectangle of document pixels (inside the document, not empty), combined by `mode`.
pub func rectangle(cells: Cells*, left: i64, top: i64, right: i64, bottom: i64, mode: Mode):
if mode == Mode.intersect:
# All of the rectangle is selected: intersecting keeps what is inside.
outside(cells, left, top, right, bottom)
return
let cover = reach(cells, left, top, right, bottom)
let value: u8 = 0 if mode == Mode.subtract else 255
for row in cover.top..<cover.bottom:
for column in cover.left..<cover.right:
let index = row * (usize)cells.columns() + column
let x = cells.origin_x(index)
let y = cells.origin_y(index)
let x0 = math.imax(left, x) - x
let y0 = math.imax(top, y) - y
let x1 = math.imin(right, x + cells.cell_width(index)) - x
let y1 = math.imin(bottom, y + cells.cell_height(index)) - y
if x0 == 0 and y0 == 0 and x1 == cells.cell_width(index) and y1 == cells.cell_height(index):
cells.fill(index, value)
continue
if cells.uniform(index) == (i64)value:
continue
let bytes = cells.writable(index)
for line in y0..<y1:
let start = (usize)line * (usize)tile_size
memory.set(bytes[start + (usize)x0..<start + (usize)x1], value)
## Clear everything outside a box of document pixels (intersecting with a shape inside it).
pub func outside(cells: Cells*, left: i64, top: i64, right: i64, bottom: i64):
for index in 0..<cells.count():
let x = cells.origin_x(index)
let y = cells.origin_y(index)
let width = cells.cell_width(index)
let height = cells.cell_height(index)
let x0 = math.imax(left, x) - x
let y0 = math.imax(top, y) - y
let x1 = math.imin(right, x + width) - x
let y1 = math.imin(bottom, y + height) - y
if x1 <= x0 or y1 <= y0:
cells.fill(index, 0)
continue
if (x0 == 0 and y0 == 0 and x1 == width and y1 == height) or cells.uniform(index) == 0:
continue
let bytes = cells.writable(index)
for line in 0..<height:
let start = (usize)line * (usize)tile_size
if line < y0 or line >= y1:
memory.set(bytes[start..<start + (usize)width], 0)
continue
if x0 > 0:
memory.set(bytes[start..<start + (usize)x0], 0)
if x1 < width:
memory.set(bytes[start + (usize)x1..<start + (usize)width], 0)
# mark: Ellipses ==============================================================================
## An ellipse inscribed in the box `x`, `y`, `width`, `height`, antialiased over a pixel.
pub struct Ellipse:
var cx: f64
var cy: f64
var rx: f64
var ry: f64
var edge: f64
pub static func inscribed(x: i64, y: i64, width: i64, height: i64) -> Ellipse:
let rx = math.max(0.5, (f64)width * 0.5)
let ry = math.max(0.5, (f64)height * 0.5)
return Ellipse(cx = (f64)x + (f64)width * 0.5, cy = (f64)y + (f64)height * 0.5, rx = rx, ry = ry, edge = math.min(rx, ry))
## Coverage at the pixel whose centre is (`px`, `py`).
pub func value(px: f64, py: f64) -> u8:
let dx = (px - self.cx) / self.rx
let dy = (py - self.cy) / self.ry
let d = math.sqrt(dx * dx + dy * dy)
let coverage = math.clamp((1.0 - d) * self.edge + 0.5, 0.0, 1.0)
return (u8)(coverage * 255.0 + 0.5)
struct EllipseJob:
var cells: Cells*
var shape: Ellipse
var cover: Reach
var mode: Mode
## The ellipse into the cells of the box `left`..`bottom` (inside the document) by `mode`.
pub func ellipse(cells: Cells*, shape: Ellipse, left: i64, top: i64, right: i64, bottom: i64, mode: Mode):
var job = EllipseJob(cells = cells, shape = shape, cover = reach(cells, left, top, right, bottom), mode = mode)
let count = (job.cover.right - job.cover.left) * (job.cover.bottom - job.cover.top)
each(count, (void*)&job, ellipse_item)
if mode == Mode.intersect:
outside(cells, left, top, right, bottom)
## One cell of the ellipse. Its coverage only falls away from the centre, so a
## cell whose nearest pixel is outside is wholly outside, and one whose four
## corner pixels are inside is wholly inside (an ellipse is convex).
func ellipse_item(context: void*?, item: usize):
let job = (EllipseJob*)(context else return)
let across = job.cover.right - job.cover.left
let index = (job.cover.top + item // across) * (usize)job.cells.columns() + job.cover.left + item % across
let x = (f64)job.cells.origin_x(index)
let y = (f64)job.cells.origin_y(index)
let width = job.cells.cell_width(index)
let height = job.cells.cell_height(index)
let last_x = x + (f64)width - 0.5
let last_y = y + (f64)height - 0.5
let near_x = math.clamp(job.shape.cx, x + 0.5, last_x)
let near_y = math.clamp(job.shape.cy, y + 0.5, last_y)
if job.shape.value(near_x, near_y) == 0:
combine_value(job.cells, index, 0, job.mode)
return
if job.shape.value(x + 0.5, y + 0.5) == 255 and job.shape.value(last_x, y + 0.5) == 255 and job.shape.value(x + 0.5, last_y) == 255 and job.shape.value(last_x, last_y) == 255:
combine_value(job.cells, index, 255, job.mode)
return
let shape = new u8[block_bytes] --- in memory.heap catch failure:
trap("out of memory drawing a selection")
defer free(shape) in memory.heap
memory.set(shape, 0)
for row in 0..<(usize)height:
for column in 0..<(usize)width:
shape[row * (usize)tile_size + column] = job.shape.value(x + (f64)column + 0.5, y + (f64)row + 0.5)
combine_cell(job.cells, index, shape, job.mode)
# mark: Polygons ==============================================================================
struct PolygonJob:
var cells: Cells*
var points: const f64[]
var cover: Reach
var mode: Mode
## The polygon of `points` (x, y pairs), even-odd filled, into the cells of its
## box `left`..`bottom` (inside the document) by `mode`: a row of cells a thread.
pub func polygon(cells: Cells*, points: const f64[], left: i64, top: i64, right: i64, bottom: i64, mode: Mode):
var job = PolygonJob(cells = cells, points = points, cover = reach(cells, left, top, right, bottom), mode = mode)
each(job.cover.bottom - job.cover.top, (void*)&job, polygon_row)
if mode == Mode.intersect:
outside(cells, left, top, right, bottom)
## One row of cells of the polygon: each pixel row's coverage from scanline
## crossings at four heights (a little antialiasing along near-horizontal
## edges), spans summed through a running difference, into a strip of cells.
func polygon_row(context: void*?, item: usize):
let job = (PolygonJob*)(context else return)
let cells = job.cells
let row = job.cover.top + item
let across = job.cover.right - job.cover.left
let first_index = row * (usize)cells.columns() + job.cover.left
let xa = cells.origin_x(first_index)
let xb = math.imin((i64)cells.extent_x, (i64)(job.cover.right * (usize)tile_size))
let span = (usize)(xb - xa)
let count = job.points.length // 2
let strip = new u8[across * block_bytes] --- in memory.heap catch failure:
trap("out of memory drawing a selection")
defer free(strip) in memory.heap
let delta = new i32[span + 1] --- in memory.heap catch failure:
trap("out of memory drawing a selection")
defer free(delta) in memory.heap
let crossings = new f64[count] --- in memory.heap catch failure:
trap("out of memory drawing a selection")
defer free(crossings) in memory.heap
memory.set(strip, 0)
let y0 = cells.origin_y(first_index)
for line in 0..<(usize)cells.cell_height(first_index):
for x in 0..<delta.length:
delta[x] = 0
var touched = false
for sample in 0..<(usize)4:
let y = (f64)y0 + (f64)line + ((f64)sample + 0.5) * 0.25
var found: usize = 0
for edge in 0..<count:
let ax = job.points[edge * 2]
let ay = job.points[edge * 2 + 1]
let bx = job.points[((edge + 1) % count) * 2]
let by = job.points[((edge + 1) % count) * 2 + 1]
if (ay <= y and by > y) or (by <= y and ay > y):
crossings[found] = ax + (y - ay) * (bx - ax) / (by - ay)
found += 1
# Sorted, the crossings pair up into the spans inside.
for i in 1..<found:
let value = crossings[i]
var at = i
while at > 0 and crossings[at - 1] > value:
crossings[at] = crossings[at - 1]
at -= 1
crossings[at] = value
var pair: usize = 0
while pair + 1 < found:
let start = math.imin(math.imax((i64)math.floor(crossings[pair] + 0.5), xa), xb)
let stop = math.imin(math.imax((i64)math.floor(crossings[pair + 1] + 0.5), xa), xb)
if stop > start:
delta[(usize)(start - xa)] += 64
delta[(usize)(stop - xa)] -= 64
touched = true
pair += 2
if not touched:
continue
var running: i32 = 0
for x in 0..<span:
running += delta[x]
if running > 0:
let value: u8 = 255 if running >= 256 else (u8)running
strip[(x // (usize)tile_size) * block_bytes + line * (usize)tile_size + x % (usize)tile_size] = value
for column in 0..<across:
combine_cell(cells, first_index + column, strip[column * block_bytes..<(column + 1) * block_bytes], job.mode)
# mark: Coverage from elsewhere =================================================================
## Where `from_source` takes its coverage: another selection's cells, a byte
## a document pixel (times `scale`).
pub struct Source:
pub var other: const Cells*? = none
pub var bytes: const u8[]
pub var scale: u8 = 1
struct SourceJob:
var cells: Cells*
var source: Source
var mode: Mode
## Every cell combined with `source` by `mode`.
pub func from_source(cells: Cells*, source: Source, mode: Mode):
var job = SourceJob(cells = cells, source = source, mode = mode)
each(cells.count(), (void*)&job, source_item)
func source_item(context: void*?, index: usize):
let job = (SourceJob*)(context else return)
if let other = job.source.other:
let value = other.uniform(index)
if value >= 0:
combine_value(job.cells, index, (u8)value, job.mode)
elif let block = other.block(index):
combine_cell(job.cells, index, block.bytes, job.mode)
return
let shape = new u8[block_bytes] --- in memory.heap catch failure:
trap("out of memory reading a selection")
defer free(shape) in memory.heap
memory.set(shape, 0)
let width = (usize)job.cells.cell_width(index)
let stride = (usize)job.cells.extent_x
let x = (usize)job.cells.origin_x(index)
let y = (usize)job.cells.origin_y(index)
for row in 0..<(usize)job.cells.cell_height(index):
let line = (y + row) * stride + x
for column in 0..<width:
shape[row * (usize)tile_size + column] = job.source.bytes[line + column] * job.source.scale
combine_cell(job.cells, index, shape, job.mode)