dymokomi/luce-image
Source of release 0.45.0
#==============================================================================================
#
# mesh_map - A deformation given by a triangle mesh, read backwards a cell at a time
#
# DESCRIPTION:
# Warp and Puppet Warp move a mesh: each vertex keeps the document point it came from
# and gets the point it lands on. Drawing needs the map the other way round, from where
# a pixel lands to where it comes from, so a cell's field is made by walking the
# landed triangles over the cell's samples: a sample inside a triangle comes from the
# same barycentric mix of the triangle's source corners. Samples outside every triangle
# show nothing; the mesh's own outer edges are softened over half a sample, and the
# samples just past them borrow their neighbour's displacement, so the resampling at
# the rim reads the picture's own edge rather than smearing into the middle.
#
# Triangles are filed by the 256-pixel cells their landed boxes touch, so a cell's
# field looks only at the few triangles over it. The field is what mesh.frag reads: a
# displacement per sample as liquify's (coarse and fine half floats) and a coverage.
#
#==============================================================================================
from luce_std import math
import memory
from luce_canvas.half import to_half, from_half
from transform_window import Footprint
from liquify_grid import Reach
from luce_raster.errors import invalid
## Document pixels a bucket spans: the canvas grid's cell.
let bucket_side: f64 = 256.0
## A mesh and where its vertices land.
pub struct MeshMap:
## Four values a vertex: where it comes from (x, y) and where it lands (x, y).
var points: f64[]
## Three vertex indices a triangle, and each triangle's outer edges (bit
## e for the edge from its corner e to the next).
var corners: u32[]
var outer: u8[]
## Triangles by bucket, from bucket (`first_x`, `first_y`), `across` by `down`.
var first_x: i64
var first_y: i64
var across: i64
var down: i64
var starts: u32[]
var items: u32[]
## The box the mesh covers in the source, and the box it lands in.
pub var source: Footprint
pub var landed: Footprint
## A lattice of `columns` by `rows` quads over `source`, each split into
## two triangles; `landing` holds where each of its (columns + 1) by
## (rows + 1) points lands, x and y, row by row.
pub static func lattice(source: Footprint, columns: usize, rows: usize, landing: const f64[]) -> MeshMap!:
if columns < 1 or rows < 1 or landing.length != (columns + 1) * (rows + 1) * 2:
error(invalid, "a mesh lattice needs a point landed for each of its corners")
let count = (columns + 1) * (rows + 1)
let points = try new f64[count * 4] --- in memory.heap
errdefer free(points) in memory.heap
let width = source.right - source.left
let height = source.bottom - source.top
var landed = Footprint(left = 1.0e18, top = 1.0e18, right = -1.0e18, bottom = -1.0e18)
for r in 0..<rows + 1:
for c in 0..<columns + 1:
let at = r * (columns + 1) + c
points[at * 4] = source.left + width * (f64)c / (f64)columns
points[at * 4 + 1] = source.top + height * (f64)r / (f64)rows
let x = landing[at * 2]
let y = landing[at * 2 + 1]
if not math.is_finite(x) or not math.is_finite(y):
error(invalid, "a mesh point must land somewhere finite")
points[at * 4 + 2] = x
points[at * 4 + 3] = y
landed = Footprint(left = math.min(landed.left, x), top = math.min(landed.top, y), right = math.max(landed.right, x), bottom = math.max(landed.bottom, y))
let triangles = columns * rows * 2
let corners = try new u32[triangles * 3] --- in memory.heap
errdefer free(corners) in memory.heap
let outer = try new u8[triangles] --- in memory.heap
errdefer free(outer) in memory.heap
for r in 0..<rows:
for c in 0..<columns:
let a = (u32)(r * (columns + 1) + c)
let b = a + 1
let d = a + (u32)(columns + 1)
let e = d + 1
let t = (r * columns + c) * 2
# (a, b, e): its top edge and its right edge may be the mesh's.
corners[t * 3] = a
corners[t * 3 + 1] = b
corners[t * 3 + 2] = e
outer[t] = (1 if r == 0 else 0) | (2 if c == columns - 1 else 0)
# (a, e, d): its bottom edge and its left edge.
corners[t * 3 + 3] = a
corners[t * 3 + 4] = e
corners[t * 3 + 5] = d
outer[t + 1] = (2 if r == rows - 1 else 0) | (4 if c == 0 else 0)
var none_yet: u32[]
var mesh = MeshMap(points = points, corners = corners, outer = outer, first_x = 0, first_y = 0, across = 0, down = 0,
starts = none_yet, items = none_yet, source = source, landed = landed)
errdefer mesh.destroy()
try mesh.file()
return mesh
pub func destroy():
free(self.points) in memory.heap
free(self.corners) in memory.heap
free(self.outer) in memory.heap
if self.starts.length > 0:
free(self.starts) in memory.heap
if self.items.length > 0:
free(self.items) in memory.heap
## The triangles' count.
pub func triangles() -> usize:
return self.outer.length
## File every triangle under the buckets its landed box touches.
func file() -> !:
self.first_x = (i64)math.floor(self.landed.left / bucket_side)
self.first_y = (i64)math.floor(self.landed.top / bucket_side)
self.across = (i64)math.floor(self.landed.right / bucket_side) - self.first_x + 1
self.down = (i64)math.floor(self.landed.bottom / bucket_side) - self.first_y + 1
let buckets = (usize)(self.across * self.down)
self.starts = try new u32[buckets + 1] --- in memory.heap
for index in 0..<self.starts.length:
self.starts[index] = 0
# Count, then place: each bucket's triangles side by side.
for pass in 0..<(usize)2:
if pass == 1:
var total: u32 = 0
for index in 0..<buckets:
let here = self.starts[index]
self.starts[index] = total
total += here
self.starts[buckets] = total
self.items = try new u32[(usize)total] --- in memory.heap
let filled = try new u32[buckets] --- in memory.heap
defer free(filled) in memory.heap
for index in 0..<buckets:
filled[index] = 0
for t in 0..<self.triangles():
let box = self.triangle_box(t)
let x0 = (i64)math.floor(box.left / bucket_side) - self.first_x
let y0 = (i64)math.floor(box.top / bucket_side) - self.first_y
let x1 = (i64)math.floor(box.right / bucket_side) - self.first_x
let y1 = (i64)math.floor(box.bottom / bucket_side) - self.first_y
for by in y0..<y1 + 1:
for bx in x0..<x1 + 1:
let bucket = (usize)(by * self.across + bx)
if pass == 0:
self.starts[bucket] += 1
else:
self.items[(usize)self.starts[bucket] + (usize)filled[bucket]] = (u32)t
filled[bucket] += 1
## Where triangle `t` lands, as a box.
func triangle_box(t: usize) -> Footprint:
var box = Footprint(left = 1.0e18, top = 1.0e18, right = -1.0e18, bottom = -1.0e18)
for k in 0..<(usize)3:
let v = (usize)self.corners[t * 3 + k]
let x = self.points[v * 4 + 2]
let y = self.points[v * 4 + 3]
box = Footprint(left = math.min(box.left, x), top = math.min(box.top, y), right = math.max(box.right, x), bottom = math.max(box.bottom, y))
return box
## Whether any triangle lands over `left`..`right`, `top`..`bottom`.
pub func touches(left: f64, top: f64, right: f64, bottom: f64) -> bool:
return left < self.landed.right and right > self.landed.left and top < self.landed.bottom and bottom > self.landed.top
## The field over a cell for mesh.frag: `n` by `n` samples `spacing`
## pixels apart from pixel (`x0`, `y0`); into `bytes` (rgba16_float: each
## displacement as liquify's coarse and fine halves) and `cover` (r8,
## coverage 0..255). `rim` is how far the rim softens, in pixels. Also the
## box of pixels the covered samples come from (`moved`: any covered).
pub func field(x0: f64, y0: f64, spacing: f64, n: i64, rim: f64, bytes: u8[], cover: u8[]) -> Reach:
var reach = Reach(moved = false, left = 1.0e18, top = 1.0e18, right = -1.0e18, bottom = -1.0e18)
let count = (usize)(n * n)
let shift = new f32[count * 2] --- in memory.heap catch failure:
trap("out of memory for a mesh field")
defer free(shift) in memory.heap
for index in 0..<count:
cover[index] = 0
shift[index * 2] = 0.0
shift[index * 2 + 1] = 0.0
let x1 = x0 + (f64)(n - 1) * spacing
let y1 = y0 + (f64)(n - 1) * spacing
if self.touches(x0 - spacing, y0 - spacing, x1 + spacing, y1 + spacing):
let bx0 = math.imax(0, (i64)math.floor((x0 - spacing) / bucket_side) - self.first_x)
let by0 = math.imax(0, (i64)math.floor((y0 - spacing) / bucket_side) - self.first_y)
let bx1 = math.imin(self.across - 1, (i64)math.floor((x1 + spacing) / bucket_side) - self.first_x)
let by1 = math.imin(self.down - 1, (i64)math.floor((y1 + spacing) / bucket_side) - self.first_y)
for by in by0..<by1 + 1:
for bx in bx0..<bx1 + 1:
let bucket = (usize)(by * self.across + bx)
for item in self.starts[bucket]..<self.starts[bucket + 1]:
self.cover_triangle((usize)self.items[(usize)item], x0, y0, spacing, n, rim, shift, cover, &reach)
# Samples just past the rim borrow a covered neighbour's displacement.
for j in 0..<n:
for i in 0..<n:
let at = (usize)(j * n + i)
if cover[at] == 0:
borrow(shift, cover, n, i, j)
put_split(bytes, at * 8, (f64)shift[at * 2])
put_split(bytes, at * 8 + 2, (f64)shift[at * 2 + 1])
return reach
## Triangle `t`'s samples: where they come from, how much it covers them.
func cover_triangle(t: usize, x0: f64, y0: f64, spacing: f64, n: i64, rim: f64, shift: f32[], cover: u8[], reach: Reach*):
let a = (usize)self.corners[t * 3] * 4
let b = (usize)self.corners[t * 3 + 1] * 4
let c = (usize)self.corners[t * 3 + 2] * 4
let p = self.points
let ax = p[a + 2]
let ay = p[a + 3]
let bx = p[b + 2]
let by = p[b + 3]
let cx = p[c + 2]
let cy = p[c + 3]
let area = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
if math.abs(area) < 1e-9:
return
let box = self.triangle_box(t)
let i0 = math.imax(0, (i64)math.ceil((box.left - x0) / spacing))
let j0 = math.imax(0, (i64)math.ceil((box.top - y0) / spacing))
let i1 = math.imin(n - 1, (i64)math.floor((box.right - x0) / spacing))
let j1 = math.imin(n - 1, (i64)math.floor((box.bottom - y0) / spacing))
let edges = self.outer[t]
# Each weight is k x + m along a row: the row's samples inside are
# an interval, walked alone (a big triangle over a cell tests no more).
let kb = (cy - ay) / area
let kc = -(by - ay) / area
let ka = -(kb + kc)
let slack = 1e-7 * spacing
for j in j0..<j1 + 1:
let y = y0 + (f64)j * spacing
let mb = (-ax * (cy - ay) - (y - ay) * (cx - ax)) / area
let mc = ((bx - ax) * (y - ay) + (by - ay) * ax) / area
let ma = 1.0 - mb - mc
var low = x0 + (f64)i0 * spacing - slack
var high = x0 + (f64)i1 * spacing + slack
if not narrow(ka, ma, &low, &high) or not narrow(kb, mb, &low, &high) or not narrow(kc, mc, &low, &high):
continue
let first = math.imax(i0, (i64)math.ceil((low - slack - x0) / spacing))
let last = math.imin(i1, (i64)math.floor((high + slack - x0) / spacing))
var seen_first: i64 = -1
var seen_last: i64 = -1
for i in first..<last + 1:
let x = x0 + (f64)i * spacing
# Barycentric weights of b and c; a has what is left.
let wb = kb * x + mb
let wc = kc * x + mc
let wa = 1.0 - wb - wc
if wa < -1e-9 or wb < -1e-9 or wc < -1e-9:
continue
let at = (usize)(j * n + i)
shift[at * 2] = (f32)(wa * p[a] + wb * p[b] + wc * p[c] - x)
shift[at * 2 + 1] = (f32)(wa * p[a + 1] + wb * p[b + 1] + wc * p[c + 1] - y)
var value: u8 = 255
if edges != 0 and rim > 0.0:
let inside = edge_distance(edges, x, y, ax, ay, bx, by, cx, cy)
if inside < 0.5 * rim:
value = (u8)(math.clamp(0.5 + inside / rim, 0.5, 1.0) * 255.0 + 0.5)
if value > cover[at]:
cover[at] = value
if seen_first < 0:
seen_first = i
seen_last = i
if seen_first < 0:
continue
# Where the row's samples read is affine along it: its ends bound it.
reach.moved = true
for which in 0..<(usize)2:
let x = x0 + (f64)(seen_first if which == 0 else seen_last) * spacing
let wb = kb * x + mb
let wc = kc * x + mc
let wa = 1.0 - wb - wc
let sx = wa * p[a] + wb * p[b] + wc * p[c]
let sy = wa * p[a + 1] + wb * p[b + 1] + wc * p[c + 1]
if sx < reach.left:
reach.left = sx
if sx > reach.right:
reach.right = sx
if sy < reach.top:
reach.top = sy
if sy > reach.bottom:
reach.bottom = sy
## Narrow [`low`, `high`] to where k x + m ≥ 0 (a little under, for rounding);
## false when nothing is left.
func narrow(k: f64, m: f64, low: f64*, high: f64*) -> bool:
if k > 0.0:
let at = (-1e-9 - m) / k
if at > *low:
*low = at
elif k < 0.0:
let at = (-1e-9 - m) / k
if at < *high:
*high = at
elif m < -1e-9:
return false
return *low <= *high
## How far (`x`, `y`) lies inside the nearest of the triangle's outer edges `edges`.
func edge_distance(edges: u8, x: f64, y: f64, ax: f64, ay: f64, bx: f64, by: f64, cx: f64, cy: f64) -> f64:
var nearest = 1.0e18
if edges & 1 != 0:
nearest = math.min(nearest, line_distance(x, y, ax, ay, bx, by))
if edges & 2 != 0:
nearest = math.min(nearest, line_distance(x, y, bx, by, cx, cy))
if edges & 4 != 0:
nearest = math.min(nearest, line_distance(x, y, cx, cy, ax, ay))
return nearest
## The distance from (`x`, `y`) to the line through (`x0`, `y0`) and (`x1`, `y1`).
func line_distance(x: f64, y: f64, x0: f64, y0: f64, x1: f64, y1: f64) -> f64:
let dx = x1 - x0
let dy = y1 - y0
let length = math.sqrt(dx * dx + dy * dy)
if length < 1e-12:
return math.sqrt((x - x0) * (x - x0) + (y - y0) * (y - y0))
return math.abs((x - x0) * dy - (y - y0) * dx) / length
## An uncovered sample next to a covered one takes its displacement.
func borrow(shift: f32[], cover: const u8[], n: i64, i: i64, j: i64):
for step in 0..<(usize)4:
let ni = i + (1 if step == 0 else (-1 if step == 1 else 0))
let nj = j + (1 if step == 2 else (-1 if step == 3 else 0))
if ni < 0 or nj < 0 or ni >= n or nj >= n:
continue
let other = (usize)(nj * n + ni)
if cover[other] != 0:
let at = (usize)(j * n + i)
shift[at * 2] = shift[other * 2]
shift[at * 2 + 1] = shift[other * 2 + 1]
return
## `value` as two half floats at `at` and `at + 4` in `bytes`, as liquify's:
## a multiple of 64, exact in a half, and what is left.
func put_split(bytes: u8[], at: usize, value: f64):
if value == 0.0:
bytes[at] = 0
bytes[at + 1] = 0
bytes[at + 4] = 0
bytes[at + 5] = 0
return
let coarse = math.round(value / 64.0) * 64.0
put_half(bytes, at, coarse)
put_half(bytes, at + 4, value - coarse)
func put_half(bytes: u8[], at: usize, value: f64):
let half = to_half((f32)value)
bytes[at] = (u8)(half & 0xff)
bytes[at + 1] = (u8)(half >> 8)
## A displacement read back from `bytes` at sample `at`: x and y.
func read_shift(bytes: const u8[], at: usize, axis: usize) -> f64:
let coarse = from_half((u16)bytes[at * 8 + axis * 2] | ((u16)bytes[at * 8 + axis * 2 + 1] << 8))
let fine = from_half((u16)bytes[at * 8 + 4 + axis * 2] | ((u16)bytes[at * 8 + 4 + axis * 2 + 1] << 8))
return (f64)coarse + (f64)fine
test "a moved lattice reads back as the move, covers what it lands on and nothing past it":
let source = Footprint(left = 0.0, top = 0.0, right = 100.0, bottom = 100.0)
let landing = try new f64[25 * 2] --- in memory.heap
defer free(landing) in memory.heap
for r in 0..<(usize)5:
for c in 0..<(usize)5:
landing[(r * 5 + c) * 2] = (f64)c * 25.0 + 10.0
landing[(r * 5 + c) * 2 + 1] = (f64)r * 25.0 + 5.0
var mesh = try MeshMap.lattice(source, 4, 4, landing)
defer mesh.destroy()
assert(mesh.triangles() == 32 and mesh.landed.left == 10.0 and mesh.landed.bottom == 105.0)
let n: i64 = 129
let bytes = try new u8[(usize)(n * n) * 8] --- in memory.heap
defer free(bytes) in memory.heap
let cover = try new u8[(usize)(n * n)] --- in memory.heap
defer free(cover) in memory.heap
let reach = mesh.field(0.0, 0.0, 1.0, n, 1.0, bytes, cover)
assert(reach.moved and math.abs(reach.left) < 1e-6 and math.abs(reach.right - 100.0) < 1e-6)
let inside = (usize)(50 * n + 50)
assert(cover[inside] == 255 and math.abs(read_shift(bytes, inside, 0) + 10.0) < 0.01 and math.abs(read_shift(bytes, inside, 1) + 5.0) < 0.01)
# Left of where it lands: nothing; on its left edge: half.
assert(cover[(usize)(50 * n + 4)] == 0 and cover[(usize)(50 * n + 10)] == 128)
# Just past the rim, the displacement is the neighbour's.
assert(math.abs(read_shift(bytes, (usize)(50 * n + 9), 0) + 10.0) < 0.01)