dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / src / raster / cubics.lucb
#==============================================================================================
#
# cubics - chopping a monotonic cubic where it crosses a clip line
#
# DESCRIPTION:
# Port of Skia m144's double-precision root finders and the code that uses them to chop
# a cubic exactly at a clip edge: src/base/SkFloatingPoint.cpp (sk_double_nearly_zero,
# sk_doubles_nearly_equal_ulps), src/base/SkQuads.cpp (Discriminant, Roots, RootsReal),
# src/base/SkCubics.cpp (RootsReal, RootsValidT, BinarySearchRootsValidT, EvalAt),
# src/base/SkBezierCurves.cpp (SkBezierCubic::ConvertToPolynomial, Subdivide) and
# src/core/SkGeometry.cpp (first_axis_intersection, SkChopMonoCubicAtX/Y). tiny-skia
# ports the older SkPathOps intersection instead, which picks slightly different t values.
#
# Copyright (c) 2023 Google LLC
# Copyright (c) 2026 the luce-browser authors.
# SPDX-License-Identifier: BSD-3-Clause (see LICENSE-skia)
#
#==============================================================================================
# mark: SkFloatingPoint ========================================================================
## FLT_EPSILON as a double.
let sk_flt_epsilon_f64: f64 = (f64)1.1920929e-7f32
## The positive magnitude of a double: 2^e for a normal number, 0 for a subnormal one and
## infinity for NaN or infinity.
func double_magnitude(a: f64) -> f64:
return f64.bits(a.bits() & (u64)0x7FF0000000000000)
## sk_double_nearly_zero.
func sk_double_nearly_zero(a: f64) -> bool:
return a == 0.0 or math.abs(a) < sk_flt_epsilon_f64
## sk_doubles_nearly_equal_ulps with the default of 16 ulps.
func sk_doubles_nearly_equal_ulps(a: f64, b: f64) -> bool:
let min_magnitude: f64 = 2.2250738585072014e-308 # DBL_MIN
let max_magnitude = std_max64(std_max64(double_magnitude(a), min_magnitude), double_magnitude(b))
let ulp_factor: f64 = 2.220446049250313e-16 # DBL_EPSILON
let tolerance = max_magnitude * (ulp_factor * 17.0)
return a == b or math.abs(b - a) < tolerance
## std::max for doubles (unlike fmax64, NaN is not ignored): `a` unless a < b.
func std_max64(a: f64, b: f64) -> f64:
return b if a < b else a
## std::min for doubles: `a` unless b < a.
func std_min64(a: f64, b: f64) -> f64:
return b if b < a else a
# mark: SkQuads ================================================================================
func quads_solve_linear(m: f64, b: f64, solution: f64[]) -> usize:
if sk_double_nearly_zero(m):
solution[0] = 0.0
if sk_double_nearly_zero(b):
return 1
return 0
solution[0] = -b / m
if not math.is_finite(solution[0]):
return 0
return 1
func quads_close_to_linear(a: f64, b: f64) -> bool:
if a != 0.0:
# Return if B is much bigger than A.
return math.abs(b / a) >= 1.0e+16
# Otherwise A is zero, and the quadratic is linear.
return true
## SkQuads::Discriminant: b² - ac, with the rounding errors of both products added back in
## when they cancel.
func quads_discriminant(a: f64, b: f64, c: f64) -> f64:
let b2 = b * b
let ac = a * c
let rough_discriminant = b2 - ac
if 3.0 * math.abs(rough_discriminant) >= b2 + ac:
return rough_discriminant
let b2_rounding_error = math.fma(b, b, -b2)
let ac_rounding_error = math.fma(a, c, -ac)
return (b2 - ac) + (b2_rounding_error - ac_rounding_error)
## SkQuads::Roots for Ax² - 2Bx + C: (discriminant, root0, root1).
func quads_roots(a: f64, b: f64, c: f64) -> (f64, f64, f64):
let discriminant = quads_discriminant(a, b, c)
if a == 0.0:
var root: f64
if b == 0.0:
root = f64.bits((u64)0x7FF0000000000000) if c == 0.0 else f64.bits((u64)0x7FF8000000000000)
else:
root = c / (2.0 * b)
return (discriminant, root, root)
if discriminant == 0.0:
return (discriminant, b / a, b / a)
if discriminant > 0.0:
let d = math.sqrt(discriminant)
let r = b + d if b > 0.0 else b - d
return (discriminant, r / a, c / r)
return (discriminant, f64.bits((u64)0x7FF8000000000000), f64.bits((u64)0x7FF8000000000000))
func zero_if_tiny(x: f64) -> f64:
return 0.0 if sk_double_nearly_zero(x) else x
## SkQuads::RootsReal: the real roots of Ax² + Bx + C.
func quads_roots_real(a: f64, b: f64, c: f64, solution: f64[]) -> usize:
if quads_close_to_linear(a, b):
return quads_solve_linear(b, c, solution)
let (discriminant, root0, root1) = quads_roots(a, -0.5 * b, c)
if not math.is_finite(discriminant) or discriminant < 0.0:
return 0
var roots: usize = 0
let r0 = zero_if_tiny(root0)
if math.is_finite(r0):
solution[roots] = r0
roots += 1
let r1 = zero_if_tiny(root1)
if math.is_finite(r1):
solution[roots] = r1
roots += 1
if roots == 2 and sk_doubles_nearly_equal_ulps(solution[0], solution[1]):
roots = 1
return roots
# mark: SkCubics ===============================================================================
## SkCubics::EvalAt: At³ + Bt² + Ct + D with fused multiply-adds.
func cubics_eval_at(a: f64, b: f64, c: f64, d: f64, t: f64) -> f64:
return math.fma(t, math.fma(t, math.fma(t, a, b), c), d)
func cubics_nearly_equal(x: f64, y: f64) -> bool:
if sk_double_nearly_zero(x):
return sk_double_nearly_zero(y)
return sk_doubles_nearly_equal_ulps(x, y)
func close_to_a_quadratic(a: f64, b: f64) -> bool:
if sk_double_nearly_zero(b):
return sk_double_nearly_zero(a)
return math.abs(a / b) < 1.0e-7
## SkTPin(x, lo, hi): std::max(lo, std::min(x, hi)).
func pin64(x: f64, lo: f64, hi: f64) -> f64:
return std_max64(lo, std_min64(x, hi))
## SkCubics::RootsReal: the real roots of At³ + Bt² + Ct + D.
func cubics_roots_real(a0: f64, b0: f64, c0: f64, d0: f64, solution: f64[]) -> usize:
if close_to_a_quadratic(a0, b0):
return quads_roots_real(b0, c0, d0, solution)
if sk_double_nearly_zero(d0): # 0 is one root
var num = quads_roots_real(a0, b0, c0, solution)
for i: usize in 0..<num:
if sk_double_nearly_zero(solution[i]):
return num
solution[num] = 0.0
num += 1
return num
if sk_double_nearly_zero(a0 + b0 + c0 + d0): # 1 is one root
var num = quads_roots_real(a0, a0 + b0, -d0, solution)
for i: usize in 0..<num:
if sk_doubles_nearly_equal_ulps(solution[i], 1.0):
return num
solution[num] = 1.0
num += 1
return num
let inv_a = 1.0 / a0
let a = b0 * inv_a
let b = c0 * inv_a
let c = d0 * inv_a
let a2 = a * a
let q = (a2 - b * 3.0) / 9.0
let r = (2.0 * a2 * a - 9.0 * a * b + 27.0 * c) / 54.0
let r2 = r * r
let q3 = q * q * q
let r2_minus_q3 = r2 - q3
if not math.is_finite(r2_minus_q3):
return 0
let adiv3 = a / 3.0
let pi: f64 = 3.14159265358979323846264338327950288
var count: usize = 0
if r2_minus_q3 < 0.0: # we have 3 real roots
let theta = math.acos(pin64(r / math.sqrt(q3), -1.0, 1.0))
let neg2_root_q = -2.0 * math.sqrt(q)
solution[0] = neg2_root_q * math.cos(theta / 3.0) - adiv3
count = 1
let root1 = neg2_root_q * math.cos((theta + 2.0 * pi) / 3.0) - adiv3
if not cubics_nearly_equal(solution[0], root1):
solution[count] = root1
count += 1
let root2 = neg2_root_q * math.cos((theta - 2.0 * pi) / 3.0) - adiv3
if not cubics_nearly_equal(solution[0], root2) and (count == 1 or not cubics_nearly_equal(solution[1], root2)):
solution[count] = root2
count += 1
# we have 1 real root
else:
let sqrt_r2_minus_q3 = math.sqrt(r2_minus_q3)
var big_a = math.cbrt(math.abs(r) + sqrt_r2_minus_q3)
if r > 0.0:
big_a = -big_a
if not sk_double_nearly_zero(big_a):
big_a += q / big_a
solution[0] = big_a - adiv3
count = 1
if not sk_double_nearly_zero(r2) and sk_doubles_nearly_equal_ulps(r2, q3):
let root1 = -big_a / 2.0 - adiv3
if not cubics_nearly_equal(solution[0], root1):
solution[count] = root1
count += 1
return count
## SkCubics::RootsValidT: the roots in [0, 1], snapping those within 0.00005 of an end to it.
func cubics_roots_valid_t(a: f64, b: f64, c: f64, d: f64, solution: f64[]) -> usize:
var all_roots: f64[3] = [0.0, 0.0, 0.0]
let real_roots = cubics_roots_real(a, b, c, d, all_roots)
var found: usize = 0
for index: usize in 0..<real_roots:
let t = all_roots[index]
if t <= 1.00005 and (t >= 1.0 or sk_doubles_nearly_equal_ulps(t, 1.0)):
if (found < 1 or not sk_doubles_nearly_equal_ulps(solution[0], 1.0)) and (found < 2 or not sk_doubles_nearly_equal_ulps(solution[1], 1.0)):
solution[found] = 1.0
found += 1
elif t >= -0.00005 and (t <= 0.0 or sk_double_nearly_zero(t)):
if (found < 1 or not sk_double_nearly_zero(solution[0])) and (found < 2 or not sk_double_nearly_zero(solution[1])):
solution[found] = 0.0
found += 1
elif t > 0.0 and t < 1.0:
solution[found] = t
found += 1
return found
func cubics_approximately_zero(x: f64) -> bool:
return math.abs(x) < 0.00000001
func find_extrema_valid_t(a: f64, b: f64, c: f64, t: f64[]) -> usize:
var roots: f64[2] = [0.0, 0.0]
let num_roots = quads_roots_real(3.0 * a, 2.0 * b, c, roots)
var valid: usize = 0
for i: usize in 0..<num_roots:
let t_value = roots[i]
if t_value >= 0.0 and t_value <= 1.0:
t[valid] = t_value
valid += 1
return valid
## A root of the cubic in [start, stop] by bisection, or -1.
func cubics_binary_search(a: f64, b: f64, c: f64, d: f64, start0: f64, stop0: f64) -> f64:
var start = start0
var stop = stop0
let left = cubics_eval_at(a, b, c, d, start)
if cubics_approximately_zero(left):
return start
let right = cubics_eval_at(a, b, c, d, stop)
if not math.is_finite(left) or not math.is_finite(right):
return -1.0
if (left > 0.0 and right > 0.0) or (left < 0.0 and right < 0.0):
return -1.0
for iteration: i32 in 0..<1000: # prevent infinite loop
let step = (start + stop) / 2.0
let curr = cubics_eval_at(a, b, c, d, step)
if cubics_approximately_zero(curr):
return step
if (curr < 0.0 and left < 0.0) or (curr > 0.0 and left > 0.0):
start = step
else:
stop = step
return -1.0
## SkCubics::BinarySearchRootsValidT: the roots in [0, 1] found by bisecting between extrema.
func cubics_binary_search_roots_valid_t(a: f64, b: f64, c: f64, d: f64, solution: f64[]) -> usize:
if not math.is_finite(a) or not math.is_finite(b) or not math.is_finite(c) or not math.is_finite(d):
return 0
var regions: f64[4] = [0.0, 0.0, 0.0, 1.0]
var min_max: f64[2] = [0.0, 0.0]
let extrema_count = find_extrema_valid_t(a, b, c, min_max)
var start_index = 2 - extrema_count
if extrema_count == 1:
regions[start_index + 1] = min_max[0]
if extrema_count == 2:
regions[start_index + 1] = std_min64(min_max[0], min_max[1])
regions[start_index + 2] = std_max64(min_max[0], min_max[1])
var found: usize = 0
while start_index < 3:
let root = cubics_binary_search(a, b, c, d, regions[start_index], regions[start_index + 1])
if root >= 0.0:
if (found < 1 or not cubics_approximately_zero(solution[0] - root)) and (found < 2 or not cubics_approximately_zero(solution[1] - root)):
solution[found] = root
found += 1
start_index += 1
return found
# mark: SkBezierCubic ==========================================================================
## SkBezierCubic::ConvertToPolynomial for one axis of the control values `p`.
func bezier_cubic_polynomial(p: const f64[]) -> (f64, f64, f64, f64):
let a = -p[0] + 3.0 * p[1] - 3.0 * p[2] + p[3]
let b = 3.0 * p[0] - 6.0 * p[1] + 3.0 * p[2]
let c = -3.0 * p[0] + 3.0 * p[1]
return (a, b, c, p[0])
func interpolate64(a: f64, b: f64, t: f64) -> f64:
return a + (b - a) * t
## SkBezierCubic::Subdivide for one axis: `v` holds the 4 control values, `out` receives 7.
func bezier_cubic_subdivide(v: const f64[], t: f64, out: f64[]):
out[0] = v[0]
out[6] = v[3]
let v01 = interpolate64(v[0], v[1], t)
let v12 = interpolate64(v[1], v[2], t)
let v23 = interpolate64(v[2], v[3], t)
out[1] = v01
out[5] = v23
out[2] = interpolate64(v01, v12, t)
out[4] = interpolate64(v12, v23, t)
out[3] = interpolate64(out[2], out[4], t)
# mark: SkChopMonoCubicAt ======================================================================
func close_enough_to_zero(x: f64) -> bool:
return math.abs(x) < 0.00001
## first_axis_intersection: the first accurate t where the axis values `p` reach `intercept`.
func first_axis_intersection(p: const f64[], intercept: f64) -> f64?:
var (a, b, c, d) = bezier_cubic_polynomial(p)
d -= intercept
var roots: f64[3] = [0.0, 0.0, 0.0]
var count = cubics_roots_valid_t(a, b, c, d, roots)
if count == 0:
return none
# Verify that at least one of the roots is accurate.
for i: usize in 0..<count:
if close_enough_to_zero(cubics_eval_at(a, b, c, d, roots[i])):
return roots[i]
# None of the roots returned by our normal cubic solver were correct enough, so fall back
# to a more accurate solution.
count = cubics_binary_search_roots_valid_t(a, b, c, d, roots)
for i: usize in 0..<count:
if close_enough_to_zero(cubics_eval_at(a, b, c, d, roots[i])):
return roots[i]
return none
## SkChopMonoCubicAtX/Y: chop `src` where its x (or y, when `y_axis`) equals `intercept`.
func chop_mono_cubic_at_axis(src: const Point[], intercept: f32, y_axis: bool, dst: Point[]) -> bool:
var xs: f64[4] = [(f64)src[0].x, (f64)src[1].x, (f64)src[2].x, (f64)src[3].x]
var ys: f64[4] = [(f64)src[0].y, (f64)src[1].y, (f64)src[2].y, (f64)src[3].y]
if let t = first_axis_intersection(ys if y_axis else xs, (f64)intercept):
var out_x: f64[7] = ---
var out_y: f64[7] = ---
bezier_cubic_subdivide(xs, t, out_x)
bezier_cubic_subdivide(ys, t, out_y)
for i: usize in 0..<7:
dst[i] = Point.from_xy((f32)out_x[i], (f32)out_y[i])
return true
return false
## SkChopMonoCubicAtX.
func chop_mono_cubic_at_x(src: const Point[], x: f32, dst: Point[]) -> bool:
return chop_mono_cubic_at_axis(src, x, false, dst)
## SkChopMonoCubicAtY.
func chop_mono_cubic_at_y(src: const Point[], y: f32, dst: Point[]) -> bool:
return chop_mono_cubic_at_axis(src, y, true, dst)