Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.0

0.45.0 / src / selection_warp.lucb

## A selection's cells taken through a warp (a backwards map, as Free
## Transform and Distort use), bilinear: Select › Transform Selection.
##
## Only the cells the moved edge crosses cost anything. A cell whose corners
## map back where the selection is one value throughout (or wholly outside
## its box) takes that value without sampling. Every other cell gathers the
## source pixels its footprint covers into a window once, whole rows of each
## source cell at a time, then walks its pixels stepping the map along each
## row: no division or cell lookup per tap, so a transform of a
## 360-megapixel selection costs its edge.
from luce_std import math
import memory
from luce_canvas.tiles import tile_size
from projective import Warp, quad_warp, affine_warp
from selection_cells import Cells, Covered, each
from selection_modify import Window, gather
from selection_refine import CellBox

## Past this many bytes a cell's footprint (a warp shrinking the selection
## hard) is sampled tap by tap instead of gathered.
let window_limit: i64 = 4194304

## `source` (whose selected pixels lie within `covered`) taken through
## `warp`, only in the cells `limit` holds; the rest are left clear (a
## preview's cells off screen). What leaves the document is dropped.
pub func warp_cells(source: const Cells*, covered: Covered, warp: Warp, limit: CellBox) -> Cells!:
    var target = try Cells.create(source.extent_x, source.extent_y)
    errdefer target.destroy()
    var job = WarpJob(source = source, covered = covered, target = &target, warp = warp, limit = limit, failed = false)
    each(target.count(), (void*)&job, warp_item)
    if job.failed:
        error(memory.exhausted, "out of memory transforming the selection")
    return target

struct WarpJob:
    var source: const Cells*
    var covered: Covered
    var target: Cells*
    var warp: Warp
    var limit: CellBox
    var failed: bool

## One cell of the warped selection.
func warp_item(context: void*?, index: usize):
    let job = (WarpJob*)(context else return)
    if not job.limit.holds(job.target, index):
        return
    let settled = settled_warp(job, index)
    if settled >= 0:
        job.target.fill(index, (u8)settled)
        return
    let origin_x = job.target.origin_x(index)
    let origin_y = job.target.origin_y(index)
    let width = job.target.cell_width(index)
    let height = job.target.cell_height(index)
    var reach = Reach()
    if not footprint(job.warp, origin_x, origin_y, width, height, &reach) or (reach.right - reach.left) * (reach.bottom - reach.top) > window_limit:
        tap_cell(job, index)
        return
    var window = Window(left = reach.left, top = reach.top, width = reach.right - reach.left, height = reach.bottom - reach.top,
                        extent_x = (i64)job.source.extent_x, extent_y = (i64)job.source.extent_y)
    let pixels = new u8[(usize)(window.width * window.height)] --- in memory.heap catch failure:
        job.failed = true
        return
    defer free(pixels) in memory.heap
    gather(job.source, &window, pixels)
    let bytes = job.target.fresh(index)
    let m = job.warp.m
    for row in 0..<height:
        # The map's numerators and denominator at the row's first pixel
        # centre, stepped a pixel along: one division a pixel, none when affine.
        let py = (f64)(origin_y + row) + 0.5
        let px = (f64)origin_x + 0.5
        var nx = m[0] * px + m[1] * py + m[2]
        var ny = m[3] * px + m[4] * py + m[5]
        var nw = m[6] * px + m[7] * py + m[8]
        let line = (usize)row * (usize)tile_size
        for column in 0..<width:
            var value: u8 = 0
            if nw > 1e-9:
                let sx = nx / nw - 0.5 - (f64)window.left
                let sy = ny / nw - 0.5 - (f64)window.top
                value = bilinear(pixels, &window, sx, sy)
            bytes[line + (usize)column] = value
            nx += m[0]
            ny += m[3]
            nw += m[6]

## Coverage at window point (`sx`, `sy`) (pixel centres at whole numbers),
## bilinear; clear past the window, which the footprint's slack keeps away.
func bilinear(pixels: const u8[], window: const Window*, sx: f64, sy: f64) -> u8:
    let x0 = (i64)math.floor(sx)
    let y0 = (i64)math.floor(sy)
    if x0 < 0 or y0 < 0 or x0 + 1 >= window.width or y0 + 1 >= window.height:
        return 0
    let fx = sx - (f64)x0
    let fy = sy - (f64)y0
    let at = (usize)(y0 * window.width + x0)
    let below = at + (usize)window.width
    let upper = (f64)pixels[at] * (1.0 - fx) + (f64)pixels[at + 1] * fx
    let lower = (f64)pixels[below] * (1.0 - fx) + (f64)pixels[below + 1] * fx
    return (u8)math.clamp(math.round(upper * (1.0 - fy) + lower * fy), 0.0, 255.0)

## A box of source pixels, one past the last.
struct Reach:
    var left: i64 = 0
    var top: i64 = 0
    var right: i64 = 0
    var bottom: i64 = 0

## The source pixels the cell at (`x`, `y`), `width` by `height`, samples:
## its corners mapped back (a projective map takes a box to a quad within
## theirs), with slack for the bilinear taps. False where a corner lies past
## the map's horizon.
func footprint(warp: Warp, x: i64, y: i64, width: i64, height: i64, reach: Reach*) -> bool:
    var low_x = 1e300
    var low_y = 1e300
    var high_x = -1e300
    var high_y = -1e300
    for corner in 0..<(usize)4:
        var mapped_x = 0.0
        var mapped_y = 0.0
        let corner_x = (f64)(x + (width if corner % 2 == 1 else 0))
        let corner_y = (f64)(y + (height if corner >= 2 else 0))
        if not warp.map(corner_x, corner_y, &mapped_x, &mapped_y):
            return false
        low_x = math.min(low_x, mapped_x)
        low_y = math.min(low_y, mapped_y)
        high_x = math.max(high_x, mapped_x)
        high_y = math.max(high_y, mapped_y)
    *reach = Reach(left = (i64)math.floor(low_x) - 2, top = (i64)math.floor(low_y) - 2, right = (i64)math.ceil(high_x) + 3, bottom = (i64)math.ceil(high_y) + 3)
    return true

## One cell sampled tap by tap: a footprint too big to gather, or one
## reaching past the map's horizon.
func tap_cell(job: WarpJob*, index: usize):
    let origin_x = job.target.origin_x(index)
    let origin_y = job.target.origin_y(index)
    let bytes = job.target.fresh(index)
    for row in 0..<job.target.cell_height(index):
        for column in 0..<job.target.cell_width(index):
            var x = 0.0
            var y = 0.0
            var value = 0.0
            if job.warp.map((f64)(origin_x + column) + 0.5, (f64)(origin_y + row) + 0.5, &x, &y):
                let sx = x - 0.5
                let sy = y - 0.5
                let x0 = (i64)math.floor(sx)
                let y0 = (i64)math.floor(sy)
                let fx = sx - (f64)x0
                let fy = sy - (f64)y0
                let upper = (f64)sample(job.source, x0, y0) * (1.0 - fx) + (f64)sample(job.source, x0 + 1, y0) * fx
                let lower = (f64)sample(job.source, x0, y0 + 1) * (1.0 - fx) + (f64)sample(job.source, x0 + 1, y0 + 1) * fx
                value = upper * (1.0 - fy) + lower * fy
            bytes[(usize)row * (usize)tile_size + (usize)column] = (u8)math.clamp(math.round(value), 0.0, 255.0)

## Coverage at a pixel, nothing past the document.
func sample(cells: const Cells*, x: i64, y: i64) -> u8:
    if x < 0 or y < 0 or x >= (i64)cells.extent_x or y >= (i64)cells.extent_y:
        return 0
    return cells.at(x, y)

## The one value cell `index` of the warped selection takes when its corners,
## mapped back through the warp, land where the selection is that value
## throughout (a pixel of slack for the bilinear taps); -1 to sample it.
func settled_warp(job: const WarpJob*, index: usize) -> i64:
    let source = job.source
    var reach = Reach()
    if not footprint(job.warp, job.target.origin_x(index), job.target.origin_y(index), job.target.cell_width(index), job.target.cell_height(index), &reach):
        return -1
    # Wholly past the selected pixels' box: nothing.
    let covered = job.covered
    if not covered.found or reach.right <= covered.left or reach.bottom <= covered.top or reach.left >= covered.right or reach.top >= covered.bottom:
        return 0
    # Past the document is clear, so a cell reaching out is only settled when clear.
    if reach.left < 0 or reach.top < 0 or reach.right > (i64)source.extent_x or reach.bottom > (i64)source.extent_y:
        return -1
    let span = (i64)tile_size
    var value: i64 = -2
    for row in (reach.top // span)..<((reach.bottom - 1) // span + 1):
        for column in (reach.left // span)..<((reach.right - 1) // span + 1):
            let found = source.uniform((usize)row * (usize)source.columns() + (usize)column)
            if found < 0 or (value != -2 and found != value):
                return -1
            value = found
    return value

# mark: Tests ===================================================================================

## Cells `width` by `height`: a hard square, a soft ramp across cells and a
## corner at the document's edge.
func shapes_cells(width: u32, height: u32) -> Cells!:
    var cells = try Cells.create(width, height)
    for index in 0..<cells.count():
        let bytes = cells.writable(index)
        for y in 0..<cells.cell_height(index):
            for x in 0..<cells.cell_width(index):
                let px = cells.origin_x(index) + x
                let py = cells.origin_y(index) + y
                var value: i64 = 0
                if px >= 100 and px < 380 and py >= 90 and py < 330:
                    value = 255
                elif py >= 380 and py < 470:
                    value = math.imin(255, math.imax(0, (px - 150) * 2))
                elif px >= 560 and py < 40:
                    value = 255
                bytes[(usize)(y * (i64)tile_size + x)] = (u8)value
    _ = try cells.settle()
    return cells

test "a gathered, stepped warp matches sampling tap by tap, and a limit leaves the rest clear":
    var cells = try shapes_cells(600, 520)
    defer cells.destroy()
    let covered = try cells.settle()
    let corners: f64[8] = [60.0, 40.0, 560.0, 90.0, 520.0, 500.0, 30.0, 430.0]
    let warps: Warp[2] = [try quad_warp(0.0, 0.0, 600.0, 520.0, corners), try affine_warp(0.5, 0.5, 0.2, 40.0, 0.0, 300.0, 260.0)]
    for warp in warps:
        var moved = try warp_cells(&cells, covered, warp, CellBox())
        defer moved.destroy()
        var tapped = try Cells.create(600, 520)
        defer tapped.destroy()
        var job = WarpJob(source = &cells, covered = covered, target = &tapped, warp = warp, limit = CellBox(), failed = false)
        for index in 0..<tapped.count():
            tap_cell(&job, index)
        for y in 0..<(i64)520:
            for x in 0..<(i64)600:
                if moved.at(x, y) != tapped.at(x, y):
                    trap(f"warp differs at {x}, {y}: {moved.at(x, y)} vs {tapped.at(x, y)}")
    var limited = try warp_cells(&cells, covered, warps[0], CellBox(everything = false, left = 0, top = 0, right = 200, bottom = 200))
    defer limited.destroy()
    var whole = try warp_cells(&cells, covered, warps[0], CellBox())
    defer whole.destroy()
    assert(limited.at(150, 150) == whole.at(150, 150) and whole.at(300, 300) == 255 and limited.at(300, 300) == 0)