dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / src / raster / path_geometry.lucb
#==============================================================================================
#
# path_geometry - Bezier math: evaluation, chopping, extrema, roots, curvature
#
# DESCRIPTION:
# Port of tiny-skia-path path_geometry.rs up to the conics (QuadCoeff, CubicCoeff,
# chop_quad_at, find_unit_quad_roots, chop_cubic_at2, the extrema, max-curvature,
# inflection and cusp finders). NormalizedF32 and NormalizedF32Exclusive values are
# f32 in [0, 1] and (0, 1); a "t values" array is `f32[3]`. Functions taking Rust's
# `&[Point; N]` take a `const Point[]` of at least N points.
#
#==============================================================================================
# mark: Coefficients ==========================================================================
## use for : eval(t) == A * t^2 + B * t + C
struct QuadCoeff:
var a: F32x2
var b: F32x2
var c: F32x2
static func from_points(points: const Point[]) -> QuadCoeff:
let c = points[0].to_f32x2()
let p1 = points[1].to_f32x2()
let p2 = points[2].to_f32x2()
let b = times_2(p1 - c)
let a = p2 - times_2(p1) + c
return QuadCoeff(a = a, b = b, c = c)
func eval(t: F32x2) -> F32x2:
return (self.a * t + self.b) * t + self.c
struct CubicCoeff:
var a: F32x2
var b: F32x2
var c: F32x2
var d: F32x2
static func from_points(points: const Point[]) -> CubicCoeff:
let p0 = points[0].to_f32x2()
let p1 = points[1].to_f32x2()
let p2 = points[2].to_f32x2()
let p3 = points[3].to_f32x2()
let three = f32x2_splat(3.0)
return CubicCoeff(a = p3 + three * (p1 - p2) - p0, b = three * (p2 - times_2(p1) + p0), c = three * (p1 - p0), d = p0)
func eval(t: F32x2) -> F32x2:
return ((self.a * t + self.b) * t + self.c) * t + self.d
# mark: Quads =================================================================================
# TODO: to a custom type?
func new_t_values() -> f32[3]:
return [normalized_exclusive_half, normalized_exclusive_half, normalized_exclusive_half]
func chop_quad_at(src: const Point[], t: f32, dst: Point[]):
let p0 = src[0].to_f32x2()
let p1 = src[1].to_f32x2()
let p2 = src[2].to_f32x2()
let tt = f32x2_splat(t)
let p01 = interp_f32x2(p0, p1, tt)
let p12 = interp_f32x2(p1, p2, tt)
dst[0] = Point.from_f32x2(p0)
dst[1] = Point.from_f32x2(p01)
dst[2] = Point.from_f32x2(interp_f32x2(p01, p12, tt))
dst[3] = Point.from_f32x2(p12)
dst[4] = Point.from_f32x2(p2)
# From Numerical Recipes in C.
#
# Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C])
# x1 = Q / A
# x2 = C / Q
func find_unit_quad_roots(a: f32, b: f32, c: f32, roots: f32[]) -> usize:
if a == 0.0:
if let r = valid_unit_divide(-c, b):
roots[0] = r
return 1
return 0
# use doubles so we don't overflow temporarily trying to compute R
var dr = (f64)b * (f64)b - 4.0 * (f64)a * (f64)c
if dr < 0.0:
return 0
dr = math.sqrt(dr)
let r = (f32)dr
if not math32.is_finite(r):
return 0
let q = -(b - r) / 2.0 if b < 0.0 else -(b + r) / 2.0
var roots_offset: usize = 0
if let r0 = valid_unit_divide(q, a):
roots[roots_offset] = r0
roots_offset += 1
if let r1 = valid_unit_divide(c, q):
roots[roots_offset] = r1
roots_offset += 1
if roots_offset == 2:
if roots[0] > roots[1]:
let tmp = roots[0]
roots[0] = roots[1]
roots[1] = tmp
elif roots[0] == roots[1]:
# nearly-equal?
roots_offset -= 1 # skip the double root
return roots_offset
func chop_cubic_at2(src: const Point[], t: f32, dst: Point[]):
if t == 1.0:
for i: usize in 0..<4:
dst[i] = src[i]
dst[4] = src[3]
dst[5] = src[3]
dst[6] = src[3]
return
let p0 = src[0].to_f32x2()
let p1 = src[1].to_f32x2()
let p2 = src[2].to_f32x2()
let p3 = src[3].to_f32x2()
let tt = f32x2_splat(t)
let ab = interp_f32x2(p0, p1, tt)
let bc = interp_f32x2(p1, p2, tt)
let cd = interp_f32x2(p2, p3, tt)
let abc = interp_f32x2(ab, bc, tt)
let bcd = interp_f32x2(bc, cd, tt)
let abcd = interp_f32x2(abc, bcd, tt)
dst[0] = Point.from_f32x2(p0)
dst[1] = Point.from_f32x2(ab)
dst[2] = Point.from_f32x2(abc)
dst[3] = Point.from_f32x2(abcd)
dst[4] = Point.from_f32x2(bcd)
dst[5] = Point.from_f32x2(cd)
dst[6] = Point.from_f32x2(p3)
# Quad'(t) = At + B, where
# A = 2(a - 2b + c)
# B = 2(b - a)
# Solve for t, only if it fits between 0 < t < 1
func find_quad_extrema(a: f32, b: f32, c: f32) -> f32?:
# At + B == 0
# t = -B / A
return valid_unit_divide(a - b, a - b - b + c)
func valid_unit_divide(numer0: f32, denom0: f32) -> f32?:
var numer = numer0
var denom = denom0
if numer < 0.0:
numer = -numer
denom = -denom
if denom == 0.0 or numer == 0.0 or numer >= denom:
return none
let r = numer / denom
return normalized_exclusive_new(r)
func interp_f32x2(v0: F32x2, v1: F32x2, t: F32x2) -> F32x2:
return v0 + (v1 - v0) * t
func times_2(value: F32x2) -> F32x2:
return value + value
# F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2
# F'(t) = 2 (b - a) + 2 (a - 2b + c) t
# F''(t) = 2 (a - 2b + c)
#
# A = 2 (b - a)
# B = 2 (a - 2b + c)
#
# Maximum curvature for a quadratic means solving
# Fx' Fx'' + Fy' Fy'' = 0
#
# t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2)
func find_quad_max_curvature(src: const Point[]) -> f32:
let ax = src[1].x - src[0].x
let ay = src[1].y - src[0].y
let bx = src[0].x - src[1].x - src[1].x + src[2].x
let by = src[0].y - src[1].y - src[1].y + src[2].y
var numer = -(ax * bx + ay * by)
var denom = bx * bx + by * by
if denom < 0.0:
numer = -numer
denom = -denom
if numer <= 0.0:
return 0.0
if numer >= denom:
# Also catches denom=0
return 1.0
let t = numer / denom
return normalized_new(t) else trap("unreachable")
func eval_quad_at(src: const Point[], t: f32) -> Point:
return Point.from_f32x2(QuadCoeff.from_points(src).eval(f32x2_splat(t)))
func eval_quad_tangent_at(src: const Point[], tol: f32) -> Point:
# The derivative equation is 2(b - a +(a - 2b +c)t). This returns a zero tangent vector
# when t is 0 or 1, and the control point is equal to the end point. In this case, use
# the quad end points to compute the tangent.
if (tol == 0.0 and points_equal(src[0], src[1])) or (tol == 1.0 and points_equal(src[1], src[2])):
return src[2].sub(src[0])
let p0 = src[0].to_f32x2()
let p1 = src[1].to_f32x2()
let p2 = src[2].to_f32x2()
let b = p1 - p0
let a = p2 - p1 - b
let t = a * f32x2_splat(tol) + b
return Point.from_f32x2(t + t)
# mark: Cubics ================================================================================
# Looking for F' dot F'' == 0
#
# A = b - a
# B = c - 2b + a
# C = d - 3c + 3b - a
#
# F' = 3Ct^2 + 6Bt + 3A
# F'' = 6Ct + 6B
#
# F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
func find_cubic_max_curvature(src: const Point[], t_values: f32[]) -> usize:
var coeff_x = formulate_f1_dot_f2([src[0].x, src[1].x, src[2].x, src[3].x])
let coeff_y = formulate_f1_dot_f2([src[0].y, src[1].y, src[2].y, src[3].y])
for i: usize in 0..<4:
coeff_x[i] += coeff_y[i]
return solve_cubic_poly(coeff_x, t_values)
func formulate_f1_dot_f2(src: f32[4]) -> f32[4]:
let a = src[1] - src[0]
let b = src[2] - 2.0 * src[1] + src[0]
let c = src[3] + 3.0 * (src[1] - src[2]) - src[0]
return [c * c, 3.0 * b * c, 2.0 * b * b + c * a, a * b]
func solve_cubic_poly(coeff: f32[4], t_values: f32[]) -> usize:
if is_nearly_zero(coeff[0]):
# we're just a quadratic
var tmp_t = new_t_values()
let count = find_unit_quad_roots(coeff[1], coeff[2], coeff[3], tmp_t)
for i in 0..<count:
t_values[i] = tmp_t[i]
return count
let inva = invert(coeff[0])
let a = coeff[1] * inva
let b = coeff[2] * inva
let c = coeff[3] * inva
let q = (a * a - b * 3.0) / 9.0
let r = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0
let q3 = q * q * q
let r2_minus_q3 = r * r - q3
let adiv3 = a / 3.0
if r2_minus_q3 < 0.0:
# we have 3 real roots
# the divide/root can, due to finite precisions, be slightly outside of -1...1
let theta = math32.acos(bound(r / math32.sqrt(q3), -1.0, 1.0))
let neg2_root_q = -2.0 * math32.sqrt(q)
t_values[0] = normalized_clamped(neg2_root_q * math32.cos(theta / 3.0) - adiv3)
t_values[1] = normalized_clamped(neg2_root_q * math32.cos((theta + 2.0 * float_pi) / 3.0) - adiv3)
t_values[2] = normalized_clamped(neg2_root_q * math32.cos((theta - 2.0 * float_pi) / 3.0) - adiv3)
# now sort the roots
sort_array3(t_values)
return collapse_duplicates3(t_values)
# we have 1 real root
var aa = math32.abs(r) + math32.sqrt(r2_minus_q3)
aa = scalar_cube_root(aa)
if r > 0.0:
aa = -aa
if aa != 0.0:
aa += q / aa
t_values[0] = normalized_clamped(aa - adiv3)
return 1
func sort_array3(array: f32[]):
if array[0] > array[1]:
let t = array[0]
array[0] = array[1]
array[1] = t
if array[1] > array[2]:
let t = array[1]
array[1] = array[2]
array[2] = t
if array[0] > array[1]:
let t = array[0]
array[0] = array[1]
array[1] = t
func collapse_duplicates3(array: const f32[]) -> usize:
var len: usize = 3
if array[1] == array[2]:
len = 2
if array[0] == array[1]:
len = 1
return len
func scalar_cube_root(x: f32) -> f32:
return math32.pow(x, 0.3333333)
# This is SkEvalCubicAt split into three functions.
func eval_cubic_pos_at(src: const Point[], t: f32) -> Point:
return Point.from_f32x2(CubicCoeff.from_points(src).eval(f32x2_splat(t)))
# This is SkEvalCubicAt split into three functions.
func eval_cubic_tangent_at(src: const Point[], t: f32) -> Point:
# The derivative equation returns a zero tangent vector when t is 0 or 1, and the
# adjacent control point is equal to the end point. In this case, use the next control
# point or the end points to compute the tangent.
if (t == 0.0 and points_equal(src[0], src[1])) or (t == 1.0 and points_equal(src[2], src[3])):
var tangent = src[2].sub(src[0]) if t == 0.0 else src[3].sub(src[1])
if tangent.x == 0.0 and tangent.y == 0.0:
tangent = src[3].sub(src[0])
return tangent
return eval_cubic_derivative(src, t)
func eval_cubic_derivative(src: const Point[], t: f32) -> Point:
let p0 = src[0].to_f32x2()
let p1 = src[1].to_f32x2()
let p2 = src[2].to_f32x2()
let p3 = src[3].to_f32x2()
let coeff = QuadCoeff(a = p3 + f32x2_splat(3.0) * (p1 - p2) - p0, b = times_2(p2 - times_2(p1) + p0), c = p1 - p0)
return Point.from_f32x2(coeff.eval(f32x2_splat(t)))
# Cubic'(t) = At^2 + Bt + C, where
# A = 3(-a + 3(b - c) + d)
# B = 6(a - 2b + c)
# C = 3(b - a)
# Solve for t, keeping only those that fit between 0 < t < 1
func find_cubic_extrema(a: f32, b: f32, c: f32, d: f32, t_values: f32[]) -> usize:
# we divide A,B,C by 3 to simplify
let aa = d - a + 3.0 * (b - c)
let bb = 2.0 * (a - b - b + c)
let cc = b - a
return find_unit_quad_roots(aa, bb, cc, t_values)
# http://www.faculty.idc.ac.il/arik/quality/appendixA.html
#
# Inflection means that curvature is zero.
# Curvature is [F' x F''] / [F'^3]
# So we solve F'x X F''y - F'y X F''y == 0
# After some canceling of the cubic term, we get
# A = b - a
# B = c - 2b + a
# C = d - 3c + 3b - a
# (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0
func find_cubic_inflections(src: const Point[], t_values: f32[]) -> usize:
let ax = src[1].x - src[0].x
let ay = src[1].y - src[0].y
let bx = src[2].x - 2.0 * src[1].x + src[0].x
let by = src[2].y - 2.0 * src[1].y + src[0].y
let cx = src[3].x + 3.0 * (src[1].x - src[2].x) - src[0].x
let cy = src[3].y + 3.0 * (src[1].y - src[2].y) - src[0].y
return find_unit_quad_roots(bx * cy - by * cx, ax * cy - ay * cx, ax * by - ay * bx, t_values)
# Return location (in t) of cubic cusp, if there is one.
# Note that classify cubic code does not reliably return all cusp'd cubics, so
# it is not called here.
func find_cubic_cusp(src: const Point[]) -> f32?:
# When the adjacent control point matches the end point, it behaves as if the cubic has a
# cusp: there's a point of max curvature where the derivative goes to zero. Ideally, this
# would be where t is zero or one, but math error makes not so. It is not uncommon to
# create cubics this way; skip them.
if points_equal(src[0], src[1]):
return none
if points_equal(src[2], src[3]):
return none
# Cubics only have a cusp if the line segments formed by the control and end points
# cross. Detect crossing if line ends are on opposite sides of plane formed by the other
# line.
if on_same_side(src, 0, 2) or on_same_side(src, 2, 0):
return none
# Cubics may have multiple points of maximum curvature, although at most only one is a
# cusp.
var t_values: f32[3] = [0.0, 0.0, 0.0]
let count = find_cubic_max_curvature(src, t_values)
for test_t in t_values[..<count]:
if 0.0 >= test_t or test_t >= 1.0:
# no need to consider max curvature on the end
continue
# A cusp is at the max curvature, and also has a derivative close to zero. Choose
# the 'close to zero' meaning by comparing the derivative length with the overall
# cubic size.
let d_pt = eval_cubic_derivative(src, test_t)
let d_pt_magnitude = d_pt.length_sqd()
let precision = calc_cubic_precision(src)
if d_pt_magnitude < precision:
# All three max curvature t values may be close to the cusp; return the first
# one.
return normalized_exclusive_new_bounded(test_t)
return none
# Returns true if both points src[testIndex], src[testIndex+1] are in the same half plane
# defined by the line segment src[lineIndex], src[lineIndex+1].
func on_same_side(src: const Point[], test_index: usize, line_index: usize) -> bool:
let origin = src[line_index]
let line = src[line_index + 1].sub(origin)
var crosses: f32[2] = [0.0, 0.0]
for index: usize in 0..<2:
let test_line = src[test_index + index].sub(origin)
crosses[index] = line.cross(test_line)
return crosses[0] * crosses[1] >= 0.0
# Returns a constant proportional to the dimensions of the cubic.
# Constant found through experimentation -- maybe there's a better way....
func calc_cubic_precision(src: const Point[]) -> f32:
return (src[1].distance_to_sqd(src[0]) + src[2].distance_to_sqd(src[1]) + src[3].distance_to_sqd(src[2])) * 1e-8