dymokomi/luce-image
Source of release 0.45.1
0.45.1 / src / projective.lucb
## The maps free transform and distort resample through: 3×3 projective
## matrices on document pixels, row-major, mapping (x, y) to
## ((m0 x + m1 y + m2) / w, (m3 x + m4 y + m5) / w) with w = m6 x + m7 y + m8.
## A `Warp` runs backwards — from where a pixel lands to where it comes from —
## which is what resampling needs; `forward` turns it round.
from luce_std import math
from luce_raster.errors import invalid
pub struct Warp:
pub var m: f64[9]
## Where document point (`x`, `y`) maps to: false when it lies on or
## behind the map's horizon.
pub func map(x: f64, y: f64, out_x: f64*, out_y: f64*) -> bool:
let w = self.m[6] * x + self.m[7] * y + self.m[8]
if w <= 1e-9:
return false
*out_x = (self.m[0] * x + self.m[1] * y + self.m[2]) / w
*out_y = (self.m[3] * x + self.m[4] * y + self.m[5]) / w
return true
## The map the other way round, defined at document point (`x`, `y`).
pub func forward(x: f64, y: f64) -> Warp!:
return try invert(self, x, y)
## The same map written with `w` positive at document point (`x`, `y`),
## which lies where the map is defined.
func normalized(x: f64, y: f64) -> Warp:
var result = self
if result.m[6] * x + result.m[7] * y + result.m[8] < 0.0:
for index in 0..<(usize)9:
result.m[index] = -result.m[index]
return result
## Free transform: pixels scaled by (`scale_x`, `scale_y`) — negative flips —
## and turned `angle` radians about (`pivot_x`, `pivot_y`), then moved by
## (`dx`, `dy`). Forward p' = R S (p - c) + c + d, so backwards
## p = S⁻¹ R⁻¹ (p' - c - d) + c.
pub func affine_warp(scale_x: f64, scale_y: f64, angle: f64, dx: f64, dy: f64, pivot_x: f64, pivot_y: f64) -> Warp!:
for value in [scale_x, scale_y, angle, dx, dy, pivot_x, pivot_y]:
if not math.is_finite(value):
error(invalid, "transform parameters must be finite")
if math.abs(scale_x) < 0.001 or math.abs(scale_y) < 0.001 or math.abs(scale_x) > 1000.0 or math.abs(scale_y) > 1000.0:
error(invalid, "transform scales are 0.001..1000")
let cos = math.cos(angle)
let sin = math.sin(angle)
let a = cos / scale_x
let b = sin / scale_x
let d = -sin / scale_y
let e = cos / scale_y
let ox = pivot_x + dx
let oy = pivot_y + dy
return Warp(m = [a, b, pivot_x - a * ox - b * oy, d, e, pivot_y - d * ox - e * oy, 0.0, 0.0, 1.0])
## Distort: the box at (`left`, `top`), `width` by `height`, its corners
## taken to `corners` (x, y pairs: top-left, top-right, bottom-right,
## bottom-left) in perspective. The corners must make a convex shape.
pub func quad_warp(left: f64, top: f64, width: f64, height: f64, corners: const f64[]) -> Warp!:
if corners.length != 8 or not (width > 0.0) or not (height > 0.0):
error(invalid, "a distortion takes a box with area and four corners")
for value in corners:
if not math.is_finite(value) or math.abs(value) > 1000000.0:
error(invalid, "distortion corners must be finite")
if not convex(corners):
error(invalid, "the corners must make a convex shape")
# The unit square onto the corners (Heckbert's square-to-quad).
let sx = corners[0] - corners[2] + corners[4] - corners[6]
let sy = corners[1] - corners[3] + corners[5] - corners[7]
var g = 0.0
var h = 0.0
if math.abs(sx) > 1e-9 or math.abs(sy) > 1e-9:
let dx1 = corners[2] - corners[4]
let dx2 = corners[6] - corners[4]
let dy1 = corners[3] - corners[5]
let dy2 = corners[7] - corners[5]
let den = dx1 * dy2 - dx2 * dy1
if math.abs(den) > 1e-12:
g = (sx * dy2 - dx2 * sy) / den
h = (dx1 * sy - sx * dy1) / den
let square = Warp(m = [corners[2] - corners[0] + g * corners[2], corners[6] - corners[0] + h * corners[6], corners[0],
corners[3] - corners[1] + g * corners[3], corners[7] - corners[1] + h * corners[7], corners[1], g, h, 1.0])
# Backwards: from the shape to the unit square, then out to the box;
# defined over the shape, whose middle is inside it as it is convex.
let middle_x = (corners[0] + corners[2] + corners[4] + corners[6]) * 0.25
let middle_y = (corners[1] + corners[3] + corners[5] + corners[7]) * 0.25
let back = try invert(square, middle_x, middle_y)
let box = Warp(m = [width, 0.0, left, 0.0, height, top, 0.0, 0.0, 1.0])
return multiply(box, back).normalized(middle_x, middle_y)
## Whether four corners (x, y pairs) wind one way round with area at each turn.
pub func convex(corners: const f64[]) -> bool:
var sign = 0.0
for index in 0..<(usize)4:
let a = index * 2
let b = ((index + 1) % 4) * 2
let c = ((index + 2) % 4) * 2
let cross = (corners[b] - corners[a]) * (corners[c + 1] - corners[b + 1]) - (corners[b + 1] - corners[a + 1]) * (corners[c] - corners[b])
if math.abs(cross) <= 0.01:
return false
if sign == 0.0:
sign = -1.0 if cross < 0.0 else 1.0
elif (cross < 0.0) != (sign < 0.0):
return false
return true
## `first` after `second`: p ↦ first(second(p)).
pub func multiply(first: Warp, second: Warp) -> Warp:
var result = Warp(m = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
for row in 0..<(usize)3:
for column in 0..<(usize)3:
var sum = 0.0
for k in 0..<(usize)3:
sum += first.m[row * 3 + k] * second.m[k * 3 + column]
result.m[row * 3 + column] = sum
return result
## The inverse map, written to be defined at document point (`x`, `y`); an
## error for one that flattens the plane.
pub func invert(warp: Warp, x: f64, y: f64) -> Warp!:
let m = warp.m
let c0 = m[4] * m[8] - m[5] * m[7]
let c1 = m[5] * m[6] - m[3] * m[8]
let c2 = m[3] * m[7] - m[4] * m[6]
let det = m[0] * c0 + m[1] * c1 + m[2] * c2
if math.abs(det) < 1e-15:
error(invalid, "the map flattens the picture")
let r = 1.0 / det
let inverse = Warp(m = [c0 * r, (m[2] * m[7] - m[1] * m[8]) * r, (m[1] * m[5] - m[2] * m[4]) * r,
c1 * r, (m[0] * m[8] - m[2] * m[6]) * r, (m[2] * m[3] - m[0] * m[5]) * r,
c2 * r, (m[1] * m[6] - m[0] * m[7]) * r, (m[0] * m[4] - m[1] * m[3]) * r])
return inverse.normalized(x, y)
test "free transforms and distortions map points both ways":
let turn = try affine_warp(2.0, 2.0, 0.0, 10.0, 0.0, 50.0, 50.0)
var x = 0.0
var y = 0.0
# (60, 50) is where the pivot lands, so it comes from the pivot (50, 50).
assert(turn.map(60.0, 50.0, &x, &y) and math.abs(x - 50.0) < 1e-9 and math.abs(y - 50.0) < 1e-9)
let ahead = try turn.forward(50.0, 50.0)
assert(ahead.map(40.0, 50.0, &x, &y) and math.abs(x - 40.0) < 1e-9)
# A box taken to a trapezoid: each corner comes from the box's corner.
let corners: f64[8] = [10.0, 0.0, 90.0, 0.0, 120.0, 100.0, -20.0, 100.0]
let distort = try quad_warp(0.0, 0.0, 100.0, 50.0, corners[..<8])
assert(distort.map(90.0, 0.0, &x, &y) and math.abs(x - 100.0) < 1e-6 and math.abs(y) < 1e-6)
assert(distort.map(-20.0, 100.0, &x, &y) and math.abs(x) < 1e-6 and math.abs(y - 50.0) < 1e-6)
let folded: f64[8] = [0.0, 0.0, 100.0, 0.0, 0.0, 100.0, 100.0, 100.0]
assert(not convex(folded[..<8]))
test "skew keeps the sides parallel, and perspective keeps the box's middle on its axis":
var x = 0.0
var y = 0.0
# Skewed: the top slid right by 20, the bottom left by 20 — a parallelogram,
# so the map is affine (no w) and a row keeps its width.
let skewed: f64[8] = [20.0, 0.0, 120.0, 0.0, 80.0, 50.0, -20.0, 50.0]
let skew = try quad_warp(0.0, 0.0, 100.0, 50.0, skewed[..<8])
assert(math.abs(skew.m[6]) < 1e-12 and math.abs(skew.m[7]) < 1e-12)
assert(skew.map(50.0, 25.0, &x, &y) and math.abs(x - 50.0) < 1e-9 and math.abs(y - 25.0) < 1e-9)
assert(skew.map(60.0, 10.0, &x, &y) and math.abs(x - 48.0) < 1e-9 and math.abs(y - 10.0) < 1e-9)
# Perspective: the top narrowed symmetrically. The middle column stays put,
# and a row comes from a row: w changes with y only.
let narrowed: f64[8] = [30.0, 0.0, 70.0, 0.0, 100.0, 50.0, 0.0, 50.0]
let perspective = try quad_warp(0.0, 0.0, 100.0, 50.0, narrowed[..<8])
assert(math.abs(perspective.m[6]) < 1e-12 and math.abs(perspective.m[7]) > 1e-6)
assert(perspective.map(50.0, 20.0, &x, &y) and math.abs(x - 50.0) < 1e-9)
assert(perspective.map(70.0, 0.0, &x, &y) and math.abs(x - 100.0) < 1e-6 and math.abs(y) < 1e-6)
# Nearer the narrow top, a pixel covers more of the source.
var near_top = 0.0
var near_bottom = 0.0
var unused = 0.0
assert(perspective.map(51.0, 5.0, &near_top, &unused) and perspective.map(51.0, 45.0, &near_bottom, &unused))
assert(near_top - 50.0 > near_bottom - 50.0)