Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-painting

Source of release 0.5.1

0.5.1 / src / heal.lucb

## Spot healing, as Compositor's (Rendering/HealPixels.c): the painted hole is
## filled from one shifted copy of the picture near it — the shift whose ring
## around the hole best matches the hole's own ring — with the difference
## between the two rings spread smoothly across the hole (a Laplace membrane,
## solved by over-relaxation), so the patch brings its texture and takes the
## surrounding tone: Poisson cloning. When no shift fits, the hole is filled
## with the ring's harmonic interpolation. On the CPU, once per stroke.
from luce_std import math
import memory
from luce_raster.errors import invalid

## Pixel roles in the work box.
let outside: u8 = 0
let ring: u8 = 1
let hole: u8 = 2

## The distances tried, in work-box sizes, and the directions.
let angle_count: usize = 24

## Heal `pixels` (premultiplied RGBA, 4 samples a pixel, `width` × `height`)
## where `painted` is non-zero, in place. Returns false when nothing was
## painted.
pub func heal(pixels: f32[], width: usize, height: usize, painted: const u8[]) -> bool!:
    if pixels.length != width * height * 4 or painted.length != width * height:
        error(invalid, "healing needs RGBA pixels and one mask byte each")
    # The hole's bounding box.
    var left = width
    var top = height
    var right: usize = 0
    var bottom: usize = 0
    for y in 0..<height:
        for x in 0..<width:
            if painted[y * width + x] != 0:
                left = left if left < x else x
                top = top if top < y else y
                right = right if right > x + 1 else x + 1
                bottom = bottom if bottom > y + 1 else y + 1
    if right <= left:
        return false
    let size = (right - left) if right - left > bottom - top else (bottom - top)
    let band = clamp_usize(size // 8, 2, 16)
    # The work box: the hole and its ring, inside the picture.
    let box_left = left - (band if left >= band else left)
    let box_top = top - (band if top >= band else top)
    let box_right = min_usize(width, right + band)
    let box_bottom = min_usize(height, bottom + band)
    let box_width = box_right - box_left
    let box_height = box_bottom - box_top
    let roles = try new u8[box_width * box_height] --- in memory.heap
    defer free(roles) in memory.heap
    try mark_roles(roles, painted, width, box_left, box_top, box_width, box_height, band)
    # The best shift of the ring onto itself, then refined.
    var best_x: i64 = 0
    var best_y: i64 = 0
    var best_score = 1.0e30
    var found = false
    let span = (f64)(box_width if box_width > box_height else box_height)
    let factors: f64[5] = [1.05, 1.35, 1.75, 2.25, 2.8]
    for factor in factors:
        for step in 0..<angle_count:
            let angle = (f64)step * 2.0 * math.pi / (f64)angle_count
            let dx = (i64)math.round(math.cos(angle) * span * factor)
            let dy = (i64)math.round(math.sin(angle) * span * factor)
            let score = shift_score(pixels, width, height, roles, box_left, box_top, box_width, box_height, dx, dy) * (1.0 + 0.1 * factor)
            if score < best_score:
                best_score = score
                best_x = dx
                best_y = dy
                found = true
    if found:
        let center_x = best_x
        let center_y = best_y
        for ry in -3..<(i64)4:
            for rx in -3..<(i64)4:
                let score = shift_score(pixels, width, height, roles, box_left, box_top, box_width, box_height, center_x + rx, center_y + ry) * (1.0 + 0.1 * 1.05)
                if score < best_score:
                    best_score = score
                    best_x = center_x + rx
                    best_y = center_y + ry
    # The membrane: on the ring, target minus source; solved over the hole.
    let values = try new f32[box_width * box_height * 4] --- in memory.heap
    defer free(values) in memory.heap
    var sum: f64[4] = [0.0, 0.0, 0.0, 0.0]
    var ring_count = 0.0
    for y in 0..<box_height:
        for x in 0..<box_width:
            let at = y * box_width + x
            if roles[at] != ring:
                continue
            let target = ((box_top + y) * width + box_left + x) * 4
            for channel in 0..<(usize)4:
                let source = sample(pixels, width, height, (i64)(box_left + x) + best_x, (i64)(box_top + y) + best_y, channel) if found else 0.0
                let value = (f64)pixels[target + channel] - source
                values[at * 4 + channel] = (f32)value
                sum[channel] += value
            ring_count += 1.0
    for y in 0..<box_height:
        for x in 0..<box_width:
            let at = y * box_width + x
            if roles[at] == hole:
                for channel in 0..<(usize)4:
                    values[at * 4 + channel] = (f32)(sum[channel] / math.max(ring_count, 1.0))
    solve(values, roles, box_width, box_height)
    # Healed: the shifted source plus the membrane.
    for y in 0..<box_height:
        for x in 0..<box_width:
            let at = y * box_width + x
            if roles[at] != hole:
                continue
            let target = ((box_top + y) * width + box_left + x) * 4
            var alpha = 0.0
            for channel in 0..<(usize)4:
                let source = sample(pixels, width, height, (i64)(box_left + x) + best_x, (i64)(box_top + y) + best_y, channel) if found else 0.0
                let value = math.clamp(source + (f64)values[at * 4 + channel], 0.0, 1.0)
                pixels[target + channel] = (f32)value
                if channel == 3:
                    alpha = value
            # Premultiplied: no channel above the alpha.
            for channel in 0..<(usize)3:
                pixels[target + channel] = (f32)math.min((f64)pixels[target + channel], alpha)
    return true

## Mark each pixel of the work box: in the hole, in the ring around it (a
## square dilation `band` wide, by prefix sums), or outside both.
func mark_roles(roles: u8[], painted: const u8[], width: usize, left: usize, top: usize, box_width: usize, box_height: usize, band: usize) -> !:
    let stride = box_width + 1
    let sums = try new u32[stride * (box_height + 1)] --- in memory.heap
    defer free(sums) in memory.heap
    for index in 0..<sums.length:
        sums[index] = 0
    for y in 0..<box_height:
        for x in 0..<box_width:
            let inside: u32 = 1 if painted[(top + y) * width + left + x] != 0 else 0
            sums[(y + 1) * stride + x + 1] = inside + sums[y * stride + x + 1] + sums[(y + 1) * stride + x] - sums[y * stride + x]
    for y in 0..<box_height:
        for x in 0..<box_width:
            let at = y * box_width + x
            if painted[(top + y) * width + left + x] != 0:
                roles[at] = hole
                continue
            let x0 = x - (band if x >= band else x)
            let y0 = y - (band if y >= band else y)
            let x1 = min_usize(box_width, x + band + 1)
            let y1 = min_usize(box_height, y + band + 1)
            # Added before subtracting: the partial sums are unsigned.
            let near = (sums[y1 * stride + x1] + sums[y0 * stride + x0]) - (sums[y0 * stride + x1] + sums[y1 * stride + x0])
            roles[at] = ring if near > 0 else outside

## How badly the ring shifted by (`dx`, `dy`) matches the ring in place: the
## mean squared difference; unusable shifts (off the picture, or landing on
## the hole) score as large.
func shift_score(pixels: const f32[], width: usize, height: usize, roles: const u8[], left: usize, top: usize, box_width: usize, box_height: usize, dx: i64, dy: i64) -> f64:
    let x0 = (i64)left + dx
    let y0 = (i64)top + dy
    if x0 < 0 or y0 < 0 or x0 + (i64)box_width > (i64)width or y0 + (i64)box_height > (i64)height:
        return 1.0e30
    # The shifted box must not cover the hole's box.
    if math.iabs(dx) < (i64)box_width and math.iabs(dy) < (i64)box_height:
        return 1.0e30
    var total = 0.0
    var count = 0.0
    for y in 0..<box_height:
        for x in 0..<box_width:
            if roles[y * box_width + x] != ring:
                continue
            let here = ((top + y) * width + left + x) * 4
            let there = ((usize)(y0 + (i64)y) * width + (usize)(x0 + (i64)x)) * 4
            for channel in 0..<(usize)4:
                let difference = (f64)pixels[here + channel] - (f64)pixels[there + channel]
                total += difference * difference
            count += 1.0
    return total / math.max(count, 1.0)

func sample(pixels: const f32[], width: usize, height: usize, x: i64, y: i64, channel: usize) -> f64:
    if x < 0 or y < 0 or x >= (i64)width or y >= (i64)height:
        return 0.0
    return (f64)pixels[((usize)y * width + (usize)x) * 4 + channel]

## Laplace's equation over the hole by successive over-relaxation (ω 1.8),
## the ring's values held: each hole value moves toward its four neighbours'
## mean.
func solve(values: f32[], roles: const u8[], width: usize, height: usize):
    for _ in 0..<(usize)300:
        for y in 0..<height:
            for x in 0..<width:
                let at = y * width + x
                if roles[at] != hole:
                    continue
                for channel in 0..<(usize)4:
                    var total = 0.0
                    var count = 0.0
                    if x > 0:
                        total += (f64)values[(at - 1) * 4 + channel]
                        count += 1.0
                    if x + 1 < width:
                        total += (f64)values[(at + 1) * 4 + channel]
                        count += 1.0
                    if y > 0:
                        total += (f64)values[(at - width) * 4 + channel]
                        count += 1.0
                    if y + 1 < height:
                        total += (f64)values[(at + width) * 4 + channel]
                        count += 1.0
                    let current = (f64)values[at * 4 + channel]
                    values[at * 4 + channel] = (f32)(current + 1.8 * (total / math.max(count, 1.0) - current))

func min_usize(a: usize, b: usize) -> usize:
    return a if a < b else b

func clamp_usize(value: usize, low: usize, high: usize) -> usize:
    return low if value < low else (high if value > high else value)

test "a spot on a gradient heals to the gradient, texture from beside it":
    let width: usize = 96
    let height: usize = 64
    let pixels = try new f32[width * height * 4] --- in memory.heap
    defer free(pixels) in memory.heap
    let painted = try new u8[width * height] --- in memory.heap
    defer free(painted) in memory.heap
    # A horizontal gray ramp, opaque, with a black blotch in the middle painted over.
    for y in 0..<height:
        for x in 0..<width:
            let at = (y * width + x) * 4
            let gray = (f32)x / (f32)width
            pixels[at] = gray
            pixels[at + 1] = gray
            pixels[at + 2] = gray
            pixels[at + 3] = 1.0
            let blotch = x >= 44 and x < 52 and y >= 28 and y < 36
            painted[y * width + x] = 1 if blotch else 0
            if blotch:
                pixels[at] = 0.0
                pixels[at + 1] = 0.0
                pixels[at + 2] = 0.0
    assert(try heal(pixels, width, height, painted))
    # Healed, the middle is the ramp's gray there again, give or take.
    let middle = (32 * width + 48) * 4
    assert(math.abs((f64)pixels[middle] - 48.0 / 96.0) < 0.03 and pixels[middle + 3] > 0.99)
    # Nothing outside the hole moved.
    assert(math.abs((f64)pixels[(5 * width + 5) * 4] - 5.0 / 96.0) < 0.0001)
    for index in 0..<painted.length:
        painted[index] = 0
    assert(not (try heal(pixels, width, height, painted)))