Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-develop

Source of release 0.1.0

0.1.0 / src / geometry.lucb

## Geometry: perspective correction, rotation, aspect and scale, and the guides
## that solve for them. The correction is the camera turned back: a roll
## (Rotate), a tilt (Vertical) and a pan (Horizontal) about the image's middle,
## H = K·R·K⁻¹ with K a 28 mm equivalent lens, so converging verticals from a
## camera tilted up straighten exactly as they would had it been level. Aspect
## stretches the result, and the frame is the largest rectangle of the photo's
## shape inside the corrected image ("crop to fit"), or the rectangle holding all
## of it, divided by Scale.
##
## Guides are lines drawn on the uncorrected photo that should be vertical or
## horizontal; `solve` finds the roll, tilt and pan that make them so, by
## Nelder–Mead over the rotations the guides constrain, and writes them into the
## settings. darktable's ashift does the same job with a lens-shift model; this is
## its approach, not its code.
##
## Crop then takes a rectangle of that frame (`crop_*`, fractions of it), and the
## output is that rectangle at its own size (`output_size`).
##
## Everything else reads one 3×3 matrix, `frame_map`: from output coordinates
## (0..1 of the output) to source coordinates (0..1 of the photo), homogeneous.
from luce_std import math
import interop
from settings import Settings, Guide, Look, defaults

## The largest tilt or pan the Vertical and Horizontal sliders reach, in degrees.
pub let reach_degrees: f64 = 30.0

pub type Matrix = f64[9]

func multiply(a: Matrix, b: Matrix) -> Matrix:
    var out: Matrix
    for row in 0..<(usize)3:
        for column in 0..<(usize)3:
            out[row * 3 + column] = a[row * 3] * b[column] + a[row * 3 + 1] * b[3 + column] + a[row * 3 + 2] * b[6 + column]
    return out

func invert(m: Matrix) -> Matrix:
    let a = m[4] * m[8] - m[5] * m[7]
    let b = m[5] * m[6] - m[3] * m[8]
    let c = m[3] * m[7] - m[4] * m[6]
    let determinant = m[0] * a + m[1] * b + m[2] * c
    if math.abs(determinant) < 1.0e-300:
        return [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]
    let d = 1.0 / determinant
    return [a * d, (m[2] * m[7] - m[1] * m[8]) * d, (m[1] * m[5] - m[2] * m[4]) * d,
            b * d, (m[0] * m[8] - m[2] * m[6]) * d, (m[2] * m[3] - m[0] * m[5]) * d,
            c * d, (m[1] * m[6] - m[0] * m[7]) * d, (m[0] * m[4] - m[1] * m[3]) * d]

## `m` applied to the point (`x`, `y`), divided through.
pub func project(m: Matrix, x: f64, y: f64) -> (f64, f64):
    let w = m[6] * x + m[7] * y + m[8]
    let scale = 1.0 / w if math.abs(w) > 1.0e-12 else 1.0e12
    return ((m[0] * x + m[1] * y + m[2]) * scale, (m[3] * x + m[4] * y + m[5]) * scale)

## The turn (radians) of each axis: roll about the view, tilt about the
## horizontal, pan about the vertical.
pub struct Turn:
    pub var roll: f64
    pub var tilt: f64
    pub var pan: f64

## The settings' turn.
pub func turn_of(settings: const Settings*) -> Turn:
    let degrees = math.pi / 180.0
    return Turn(roll = settings.get(.geometry_rotate) * degrees,
                tilt = settings.get(.geometry_vertical) / 100.0 * reach_degrees * degrees,
                pan = settings.get(.geometry_horizontal) / 100.0 * reach_degrees * degrees)

## The correction of a `width` × `height` photo turned by `turn` and stretched by
## `aspect` (-1..1), in pixels: source to corrected.
pub func correction(turn: Turn, aspect: f64, width: f64, height: f64) -> Matrix:
    let focal = math.sqrt(width * width + height * height) * 28.0 / 43.27
    let camera: Matrix = [focal, 0.0, width * 0.5, 0.0, focal, height * 0.5, 0.0, 0.0, 1.0]
    let cr = math.cos(turn.roll)
    let sr = math.sin(turn.roll)
    let ct = math.cos(turn.tilt)
    let st = math.sin(turn.tilt)
    let cp = math.cos(turn.pan)
    let sp = math.sin(turn.pan)
    let roll: Matrix = [cr, -sr, 0.0, sr, cr, 0.0, 0.0, 0.0, 1.0]
    let tilt: Matrix = [1.0, 0.0, 0.0, 0.0, ct, -st, 0.0, st, ct]
    let pan: Matrix = [cp, 0.0, sp, 0.0, 1.0, 0.0, -sp, 0.0, cp]
    let rotation = multiply(roll, multiply(tilt, pan))
    let turned = multiply(camera, multiply(rotation, invert(camera)))
    # Aspect stretches about the middle.
    let stretch = math.exp2(aspect * 0.5)
    let aspect_matrix: Matrix = [stretch, 0.0, width * 0.5 * (1.0 - stretch), 0.0, 1.0 / stretch, height * 0.5 * (1.0 - 1.0 / stretch), 0.0, 0.0, 1.0]
    return multiply(aspect_matrix, turned)

## Whether every corner of the `half_width` × `half_height` rectangle about
## (`cx`, `cy`) lies inside the convex quadrilateral `quad` (four corners in order).
func rectangle_inside(quad: f64[8], cx: f64, cy: f64, half_width: f64, half_height: f64) -> bool:
    let corners: f64[8] = [cx - half_width, cy - half_height, cx + half_width, cy - half_height, cx + half_width, cy + half_height, cx - half_width, cy + half_height]
    var sign = 0.0
    for edge in 0..<(usize)4:
        let ax = quad[edge * 2]
        let ay = quad[edge * 2 + 1]
        let bx = quad[((edge + 1) % 4) * 2]
        let by = quad[((edge + 1) % 4) * 2 + 1]
        for corner in 0..<(usize)4:
            let cross = (bx - ax) * (corners[corner * 2 + 1] - ay) - (by - ay) * (corners[corner * 2] - ax)
            if sign == 0.0:
                sign = 1.0 if cross >= 0.0 else -1.0
            elif cross * sign < 0.0:
                return false
    return true

## The crop rectangle of the frame: left, top, right, bottom (0..1), at least a
## hundredth wide and high.
pub func crop_of(settings: const Settings*) -> (f64, f64, f64, f64):
    let left = settings.get(.crop_left)
    let top = settings.get(.crop_top)
    let right = math.max(settings.get(.crop_right), left + 0.01)
    let bottom = math.max(settings.get(.crop_bottom), top + 0.01)
    return (left, top, math.min(right, 1.0), math.min(bottom, 1.0))

## The output's size for `settings` on a `width` × `height` photo: the crop's
## share of the frame, which has the photo's size.
pub func output_size(settings: const Settings*, width: f64, height: f64) -> (f64, f64):
    let (left, top, right, bottom) = crop_of(settings)
    return (math.max(1.0, math.round(width * (right - left))), math.max(1.0, math.round(height * (bottom - top))))

## The map from output coordinates (0..1) to source coordinates (0..1) for
## `settings` on a `width` × `height` photo, cropped unless `cropped` is false
## (the crop tool shows the whole frame): the identity when untouched.
pub func frame_map(settings: const Settings*, width: f64, height: f64, cropped: bool = true) -> Matrix:
    let framed = frame_without_crop(settings, width, height)
    if not cropped:
        return framed
    let (left, top, right, bottom) = crop_of(settings)
    if left == 0.0 and top == 0.0 and right == 1.0 and bottom == 1.0:
        return framed
    let crop: Matrix = [right - left, 0.0, left, 0.0, bottom - top, top, 0.0, 0.0, 1.0]
    return multiply(framed, crop)

func frame_without_crop(settings: const Settings*, width: f64, height: f64) -> Matrix:
    let identity: Matrix = [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]
    let turn = turn_of(settings)
    let aspect = settings.get(.geometry_aspect) / 100.0
    let scale = settings.get(.geometry_scale) / 100.0
    if turn.roll == 0.0 and turn.tilt == 0.0 and turn.pan == 0.0 and aspect == 0.0 and scale == 1.0:
        return identity
    let forward = correction(turn, aspect, width, height)
    var quad: f64[8]
    var low_x = 1.0e300
    var low_y = 1.0e300
    var high_x = -1.0e300
    var high_y = -1.0e300
    let source_corners: f64[8] = [0.0, 0.0, width, 0.0, width, height, 0.0, height]
    for corner in 0..<(usize)4:
        let (x, y) = project(forward, source_corners[corner * 2], source_corners[corner * 2 + 1])
        quad[corner * 2] = x
        quad[corner * 2 + 1] = y
        low_x = math.min(low_x, x)
        low_y = math.min(low_y, y)
        high_x = math.max(high_x, x)
        high_y = math.max(high_y, y)
    let (cx, cy) = project(forward, width * 0.5, height * 0.5)
    # How much of the photo's size the frame spans in corrected pixels.
    var span = 1.0
    if settings.get(.geometry_autocrop) > 0.5:
        var low = 0.01
        var high = 4.0
        for _step in 0..<(usize)50:
            let middle = (low + high) * 0.5
            if rectangle_inside(quad, cx, cy, width * 0.5 * middle, height * 0.5 * middle):
                low = middle
            else:
                high = middle
        span = low
    else:
        span = math.max(math.max(high_x - cx, cx - low_x) / (width * 0.5), math.max(high_y - cy, cy - low_y) / (height * 0.5))
    span /= scale
    # Output (u, v) to corrected pixels, back through the correction, to source (u, v).
    let place: Matrix = [width * span, 0.0, cx - width * span * 0.5, 0.0, height * span, cy - height * span * 0.5, 0.0, 0.0, 1.0]
    let normalize: Matrix = [1.0 / width, 0.0, 0.0, 0.0, 1.0 / height, 0.0, 0.0, 0.0, 1.0]
    return multiply(normalize, multiply(invert(forward), place))

# mark: solving =============================================================================

## How far the guides are from vertical and horizontal under `turn`, plus a
## little of the turn itself, so a guide that leaves a rotation free does not
## let it wander.
func misfit(guides: const Guide[], turn: Turn, width: f64, height: f64) -> f64:
    let forward = correction(turn, 0.0, width, height)
    var total = 0.0
    for guide in guides:
        let (x1, y1) = project(forward, guide.x1 * width, guide.y1 * height)
        let (x2, y2) = project(forward, guide.x2 * width, guide.y2 * height)
        let dx = x2 - x1
        let dy = y2 - y1
        let length = dx * dx + dy * dy
        if length <= 1.0e-18:
            continue
        # The off-axis share of the direction, squared: 0 when the guide is true.
        total += (dx * dx if guide.vertical() else dy * dy) / length
    return total + 0.0005 * (turn.roll * turn.roll + turn.tilt * turn.tilt + turn.pan * turn.pan)

## Which turns the guides decide: roll with any guide, tilt with two verticals,
## pan with two horizontals.
func freed(guides: const Guide[]) -> (bool, bool, bool):
    var verticals = 0
    var horizontals = 0
    for guide in guides:
        if guide.vertical():
            verticals += 1
        else:
            horizontals += 1
    return (verticals + horizontals > 0, verticals >= 2, horizontals >= 2)

func turn_from(base: Turn, values: const f64[], axes: (bool, bool, bool)) -> Turn:
    var out = base
    var at: usize = 0
    if axes.0:
        out.roll = values[at]
        at += 1
    if axes.1:
        out.tilt = values[at]
        at += 1
    if axes.2:
        out.pan = values[at]
    return out

## The turn that makes `guides` vertical and horizontal on a `width` × `height`
## photo; the turns no guide decides stay zero.
pub func solve_turn(guides: const Guide[], width: f64, height: f64) -> Turn:
    let axes = freed(guides)
    var count: usize = 0
    for on in [axes.0, axes.1, axes.2]:
        if on:
            count += 1
    let start = Turn()
    if count == 0:
        return start
    # Nelder–Mead over the free turns, from no turn, with steps of 3°.
    var simplex: f64[12]
    var scores: f64[4]
    for vertex in 0..=count:
        for axis in 0..<count:
            simplex[vertex * 3 + axis] = 0.05 if vertex == axis + 1 else 0.0
        scores[vertex] = misfit(guides, turn_from(start, simplex[vertex * 3..<vertex * 3 + count], axes), width, height)
    for _iteration in 0..<(usize)400:
        # Order the vertices best first.
        for i in 0..=count:
            for j in i + 1..=count:
                if scores[j] < scores[i]:
                    let held = scores[i]
                    scores[i] = scores[j]
                    scores[j] = held
                    for axis in 0..<(usize)3:
                        let value = simplex[i * 3 + axis]
                        simplex[i * 3 + axis] = simplex[j * 3 + axis]
                        simplex[j * 3 + axis] = value
        if scores[count] - scores[0] < 1.0e-14:
            break
        var centroid: f64[3]
        for vertex in 0..<count:
            for axis in 0..<count:
                centroid[axis] += simplex[vertex * 3 + axis] / (f64)count
        let worst = count * 3
        var reflected: f64[3]
        for axis in 0..<count:
            reflected[axis] = centroid[axis] + (centroid[axis] - simplex[worst + axis])
        let reflected_score = misfit(guides, turn_from(start, reflected[..<count], axes), width, height)
        if reflected_score < scores[0]:
            var expanded: f64[3]
            for axis in 0..<count:
                expanded[axis] = centroid[axis] + 2.0 * (centroid[axis] - simplex[worst + axis])
            let expanded_score = misfit(guides, turn_from(start, expanded[..<count], axes), width, height)
            let take_expanded = expanded_score < reflected_score
            for axis in 0..<count:
                simplex[worst + axis] = expanded[axis] if take_expanded else reflected[axis]
            scores[count] = expanded_score if take_expanded else reflected_score
        elif reflected_score < scores[count - 1]:
            for axis in 0..<count:
                simplex[worst + axis] = reflected[axis]
            scores[count] = reflected_score
        else:
            var contracted: f64[3]
            for axis in 0..<count:
                contracted[axis] = centroid[axis] + 0.5 * (simplex[worst + axis] - centroid[axis])
            let contracted_score = misfit(guides, turn_from(start, contracted[..<count], axes), width, height)
            if contracted_score < scores[count]:
                for axis in 0..<count:
                    simplex[worst + axis] = contracted[axis]
                scores[count] = contracted_score
            else:
                # Shrink toward the best.
                for vertex in 1..=count:
                    for axis in 0..<count:
                        simplex[vertex * 3 + axis] = simplex[axis] + 0.5 * (simplex[vertex * 3 + axis] - simplex[axis])
                    scores[vertex] = misfit(guides, turn_from(start, simplex[vertex * 3..<vertex * 3 + count], axes), width, height)
    return turn_from(start, simplex[..<count], axes)

## Solve `settings`' guides on a `width` × `height` photo and set Rotate,
## Vertical and Horizontal to the answer; without guides they are left alone.
pub func solve(settings: Settings*, width: f64, height: f64):
    if settings.guides().length == 0:
        return
    let turn = solve_turn(settings.guides(), width, height)
    let degrees = 180.0 / math.pi
    settings.set(.geometry_rotate, turn.roll * degrees)
    settings.set(.geometry_vertical, turn.tilt * degrees / reach_degrees * 100.0)
    settings.set(.geometry_horizontal, turn.pan * degrees / reach_degrees * 100.0)

## Solve `look`'s guides for a `width` × `height` photo (any size of its
## shape), setting its Rotate, Vertical and Horizontal: for Luce.
pub func solve_look(look: interop.Reference[Look], width: f64, height: f64) -> !:
    let held = try look.get()
    var settings = held.value()
    solve(&settings, width, height)
    held.replace(settings)

test "untouched geometry maps the frame to itself":
    let settings = defaults()
    let map = frame_map(&settings, 6000.0, 4000.0)
    let (x, y) = project(map, 0.25, 0.75)
    assert(math.abs(x - 0.25) < 1.0e-12 and math.abs(y - 0.75) < 1.0e-12)

test "guides on a tilted photo solve back to the tilt":
    # A building's verticals as a camera tilted up by 12° sees them.
    let width = 6000.0
    let height = 4000.0
    let tilted = correction(Turn(tilt = -12.0 * math.pi / 180.0), 0.0, width, height)
    var guides: Guide[2]
    for (at, x) in [1500.0, 4500.0].indexed():
        let (x1, y1) = project(tilted, x, 500.0)
        let (x2, y2) = project(tilted, x, 3500.0)
        guides[at] = Guide(x1 / width, y1 / height, x2 / width, y2 / height)
    let turn = solve_turn(guides, width, height)
    assert(math.abs(turn.tilt * 180.0 / math.pi - 12.0) < 0.3, "the tilt was not recovered")
    assert(math.abs(turn.roll) < 0.01 and turn.pan == 0.0)

test "a crop maps the output onto its rectangle of the frame":
    var settings = defaults()
    settings.set(.crop_left, 0.25)
    settings.set(.crop_right, 0.75)
    settings.set(.crop_top, 0.5)
    let map = frame_map(&settings, 6000.0, 4000.0)
    let (x, y) = project(map, 0.0, 0.0)
    assert(math.abs(x - 0.25) < 1.0e-12 and math.abs(y - 0.5) < 1.0e-12)
    let (x2, y2) = project(map, 1.0, 1.0)
    assert(math.abs(x2 - 0.75) < 1.0e-12 and math.abs(y2 - 1.0) < 1.0e-12)
    let (w, h) = output_size(&settings, 6000.0, 4000.0)
    assert(w == 3000.0 and h == 2000.0)

test "crop to fit keeps the frame inside the corrected photo":
    var settings = defaults()
    settings.set(.geometry_vertical, 40.0)
    settings.set(.geometry_rotate, 5.0)
    let map = frame_map(&settings, 6000.0, 4000.0)
    for (u, v) in [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0), (0.5, 0.0)]:
        let (x, y) = project(map, u, v)
        assert(x >= -1.0e-6 and x <= 1.0 + 1.0e-6 and y >= -1.0e-6 and y <= 1.0 + 1.0e-6, "a corner of the frame left the photo")