dymokomi/luce-browser-render
Source of release 0.6.2
0.6.2 / src / gfx / sk_geometry.lucb
#==============================================================================================
#
# sk_geometry - quad and cubic Bezier math from Skia's SkGeometry
#
# DESCRIPTION:
# Port of the parts of Skia m144 src/core/SkGeometry.cpp (lines 30-200 roots and quad
# evaluation and chopping, 255-305 quad Y extrema, 390-715 cubic evaluation, chopping
# and Y extrema) and src/core/SkGeometry.h (SkQuadCoeff, SkCubicCoeff, lines 420-497)
# that the path model uses, plus SkCubicClipper::ChopMonoAtY
# (src/core/SkCubicClipper.cpp:26-105, the BISECTION variant Skia compiles). The conic
# half of SkGeometry is in sk_conic.
#
# skvx::float2 arithmetic is written out lane by lane in the same operation order; Skia
# is compiled with -ffp-contract=off, as luce-base computes, so results are bit-exact.
#
# Copyright 2006 The Android Open Source Project
# Copyright 2011+ Google Inc.
# Copyright (c) 2026 the luce-browser authors.
# SPDX-License-Identifier: BSD-3-Clause (see LICENSE-tiny-skia)
#
#==============================================================================================
# mark: Helpers =================================================================================
## Ported from src/core/SkGeometry.cpp:43 is_not_monotonic.
func sk_geometry_is_not_monotonic(a: f32, b: f32, c_: f32) -> bool:
let ab = a - b
var bc = b - c_
if ab < 0.0:
bc = -bc
return ab == 0.0 or bc < 0.0
## Ported from src/core/SkGeometry.cpp:54 valid_unit_divide: numer / denom when it is in
## (0, 1), written to `ratio`; answers 1 when written, else 0.
pub func sk_valid_unit_divide(numer0: f32, denom0: f32, ratio: f32*) -> i32:
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 0
let r = numer / denom
if sk_is_nan(r):
return 0
if r == 0.0: # catch underflow if numer <<<< denom
return 0
*ratio = r
return 1
## Ported from src/core/SkGeometry.cpp:95 SkFindUnitQuadRoots: the roots of Ax^2 + Bx + C in
## (0, 1), ascending, in `roots` (two slots); answers how many.
##
## From Numerical Recipes in C.
##
## Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C])
## x1 = Q / A
## x2 = C / Q
pub func sk_find_unit_quad_roots(a: f32, b: f32, c_: f32, roots: f32[]) -> i32:
if a == 0.0:
return sk_valid_unit_divide(-c_, b, &roots[0])
var r: usize = 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 rr = (f32)dr
if not sk_is_finite(rr):
return 0
let q = -(b - rr) / 2.0 if b < 0.0 else -(b + rr) / 2.0
r += (usize)sk_valid_unit_divide(q, a, &roots[r])
r += (usize)sk_valid_unit_divide(c_, q, &roots[r])
if r == 2:
if roots[0] > roots[1]:
let swap = roots[0]
roots[0] = roots[1]
roots[1] = swap
elif roots[0] == roots[1]: # nearly-equal?
r -= 1 # skip the double root
return (i32)r
# mark: Quads ===================================================================================
## Ported from src/core/SkGeometry.cpp:144 SkEvalQuadAt(src, t): SkQuadCoeff(src).eval(t).
pub func sk_eval_quad_at(src: const SkPoint[], t: f32) -> SkPoint:
let cx = src[0].x
let cy = src[0].y
let bx = (src[1].x - cx) + (src[1].x - cx)
let by = (src[1].y - cy) + (src[1].y - cy)
let ax = (src[2].x - (src[1].x + src[1].x)) + cx
let ay = (src[2].y - (src[1].y + src[1].y)) + cy
return SkPoint(x = (ax * t + bx) * t + cx, y = (ay * t + by) * t + cy)
## Ported from src/core/SkGeometry.cpp:148 SkEvalQuadTangentAt.
pub func sk_eval_quad_tangent_at(src: const SkPoint[], t: f32) -> SkPoint:
# 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 (t == 0.0 and sk_point_eq(src[0], src[1])) or (t == 1.0 and sk_point_eq(src[1], src[2])):
return sk_point_sub(src[2], src[0])
let bx = src[1].x - src[0].x
let by = src[1].y - src[0].y
let ax = src[2].x - src[1].x - bx
let ay = src[2].y - src[1].y - by
let tx = ax * t + bx
let ty = ay * t + by
return SkPoint(x = tx + tx, y = ty + ty)
## Ported from src/core/SkGeometry.cpp:169 interp: v0 + (v1 - v0) * t.
func sk_geometry_interp(v0: SkPoint, v1: SkPoint, t: f32) -> SkPoint:
return SkPoint(x = v0.x + (v1.x - v0.x) * t, y = v0.y + (v1.y - v0.y) * t)
## Ported from src/core/SkGeometry.cpp:175 SkChopQuadAt: splits the quad `src` (3 points) at
## `t` into `dst` (5 points).
pub func sk_chop_quad_at(src: const SkPoint[], dst: SkPoint[], t: f32):
let p0 = src[0]
let p1 = src[1]
let p2 = src[2]
let p01 = sk_geometry_interp(p0, p1, t)
let p12 = sk_geometry_interp(p1, p2, t)
dst[0] = p0
dst[1] = p01
dst[2] = sk_geometry_interp(p01, p12, t)
dst[3] = p12
dst[4] = p2
## Ported from src/core/SkGeometry.cpp:193 SkChopQuadAtHalf.
pub func sk_chop_quad_at_half(src: const SkPoint[], dst: SkPoint[]):
sk_chop_quad_at(src, dst, 0.5)
## Ported from src/core/SkGeometry.cpp:265 SkFindQuadExtrema.
pub func sk_find_quad_extrema(a: f32, b: f32, c_: f32, t_value: f32*) -> i32:
# At + B == 0
# t = -B / A
return sk_valid_unit_divide(a - b, a - b - b + c_, t_value)
## Ported from src/core/SkGeometry.cpp:279 SkChopQuadAtYExtrema: returns 0 for 1 quad, and 1
## for two quads, either way the answer is stored in dst[] (5 points). Guarantees that the
## 1/2 quads will be monotonic.
pub func sk_chop_quad_at_y_extrema(src: const SkPoint[], dst: SkPoint[]) -> i32:
let a = src[0].y
var b = src[1].y
let c_ = src[2].y
if sk_geometry_is_not_monotonic(a, b, c_):
var t_value: f32 = 0.0
if sk_valid_unit_divide(a - b, a - b - b + c_, &t_value) != 0:
sk_chop_quad_at(src, dst, t_value)
# flatten_double_quad_extrema(&dst[0].fY)
dst[1].y = dst[2].y
dst[3].y = dst[2].y
return 1
# if we get here, we need to force dst to be monotonic, even though
# we couldn't compute a unit_divide value (probably underflow).
b = a if sk_scalar_abs(a - b) < sk_scalar_abs(b - c_) else c_
dst[0] = SkPoint(x = src[0].x, y = a)
dst[1] = SkPoint(x = src[1].x, y = b)
dst[2] = SkPoint(x = src[2].x, y = c_)
return 0
# mark: Cubics ==================================================================================
## Ported from src/core/SkGeometry.cpp:394 eval_cubic_derivative.
func sk_geometry_eval_cubic_derivative(src: const SkPoint[], t: f32) -> SkPoint:
let ax = src[3].x + 3.0 * (src[1].x - src[2].x) - src[0].x
let ay = src[3].y + 3.0 * (src[1].y - src[2].y) - src[0].y
let bx0 = src[2].x - (src[1].x + src[1].x) + src[0].x
let by0 = src[2].y - (src[1].y + src[1].y) + src[0].y
let bx = bx0 + bx0
let by = by0 + by0
let cx = src[1].x - src[0].x
let cy = src[1].y - src[0].y
return SkPoint(x = (ax * t + bx) * t + cx, y = (ay * t + by) * t + cy)
## Ported from src/core/SkGeometry.cpp:418 SkEvalCubicAt: the point (SkCubicCoeff(src).eval)
## and the tangent of the cubic `src` (4 points) at `t`.
pub func sk_eval_cubic_at(src: const SkPoint[], t: f32) -> (SkPoint, SkPoint):
let ax = src[3].x + 3.0 * (src[1].x - src[2].x) - src[0].x
let ay = src[3].y + 3.0 * (src[1].y - src[2].y) - src[0].y
let bx = 3.0 * (src[2].x - (src[1].x + src[1].x) + src[0].x)
let by = 3.0 * (src[2].y - (src[1].y + src[1].y) + src[0].y)
let cx = 3.0 * (src[1].x - src[0].x)
let cy = 3.0 * (src[1].y - src[0].y)
let loc = SkPoint(x = ((ax * t + bx) * t + cx) * t + src[0].x, y = ((ay * t + by) * t + cy) * t + src[0].y)
# 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.
var tangent: SkPoint
if (t == 0.0 and sk_point_eq(src[0], src[1])) or (t == 1.0 and sk_point_eq(src[2], src[3])):
if t == 0.0:
tangent = sk_point_sub(src[2], src[0])
else:
tangent = sk_point_sub(src[3], src[1])
if tangent.x == 0.0 and tangent.y == 0.0:
tangent = sk_point_sub(src[3], src[0])
else:
tangent = sk_geometry_eval_cubic_derivative(src, t)
return (loc, tangent)
## Ported from src/core/SkGeometry.cpp:454 SkFindCubicExtrema: 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.
pub func sk_find_cubic_extrema(a: f32, b: f32, c_: f32, d: f32, t_values: f32[]) -> i32:
# 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 sk_find_unit_quad_roots(aa, bb, cc, t_values)
## Ported from src/core/SkGeometry.cpp:468 unchecked_mix: (b - a) * t + a.
func sk_geometry_mix(a: SkPoint, b: SkPoint, t: f32) -> SkPoint:
return SkPoint(x = (b.x - a.x) * t + a.x, y = (b.y - a.y) * t + a.y)
## Ported from src/core/SkGeometry.cpp:473 SkChopCubicAt: splits the cubic `src` (4 points)
## at `t` into `dst` (7 points).
pub func sk_chop_cubic_at(src: const SkPoint[], dst: SkPoint[], t: f32):
if t == 1.0:
for i in 0..<4:
dst[i] = src[i]
dst[4] = src[3]
dst[5] = src[3]
dst[6] = src[3]
return
let p0 = src[0]
let p1 = src[1]
let p2 = src[2]
let p3 = src[3]
let ab = sk_geometry_mix(p0, p1, t)
let bc = sk_geometry_mix(p1, p2, t)
let cd = sk_geometry_mix(p2, p3, t)
let abc = sk_geometry_mix(ab, bc, t)
let bcd = sk_geometry_mix(bc, cd, t)
let abcd = sk_geometry_mix(abc, bcd, t)
dst[0] = p0
dst[1] = ab
dst[2] = abc
dst[3] = abcd
dst[4] = bcd
dst[5] = cd
dst[6] = p3
## Ported from src/core/SkGeometry.cpp:504 SkChopCubicAt(src, dst, t0, t1): both chops at once
## (the two SIMD halves), `dst` holding 10 points.
pub func sk_chop_cubic_at2(src: const SkPoint[], dst: SkPoint[], t0: f32, t1: f32):
if t1 == 1.0:
sk_chop_cubic_at(src, dst, t0)
dst[7] = src[3]
dst[8] = src[3]
dst[9] = src[3]
return
# Perform both chops in parallel using 4-lane SIMD (lo = t0, hi = t1).
let ab_lo = sk_geometry_mix(src[0], src[1], t0)
let ab_hi = sk_geometry_mix(src[0], src[1], t1)
let bc_lo = sk_geometry_mix(src[1], src[2], t0)
let bc_hi = sk_geometry_mix(src[1], src[2], t1)
let cd_lo = sk_geometry_mix(src[2], src[3], t0)
let cd_hi = sk_geometry_mix(src[2], src[3], t1)
let abc_lo = sk_geometry_mix(ab_lo, bc_lo, t0)
let abc_hi = sk_geometry_mix(ab_hi, bc_hi, t1)
let bcd_lo = sk_geometry_mix(bc_lo, cd_lo, t0)
let bcd_hi = sk_geometry_mix(bc_hi, cd_hi, t1)
let abcd_lo = sk_geometry_mix(abc_lo, bcd_lo, t0)
let abcd_hi = sk_geometry_mix(abc_hi, bcd_hi, t1)
# middle = unchecked_mix(abc, bcd, shuffle<2,3,0,1>(T))
let middle_lo = sk_geometry_mix(abc_lo, bcd_lo, t1)
let middle_hi = sk_geometry_mix(abc_hi, bcd_hi, t0)
dst[0] = src[0]
dst[1] = ab_lo
dst[2] = abc_lo
dst[3] = abcd_lo
dst[4] = middle_lo
dst[5] = middle_hi
dst[6] = abcd_hi
dst[7] = bcd_hi
dst[8] = cd_hi
dst[9] = src[3]
## Ported from src/core/SkGeometry.cpp:541 SkChopCubicAt(src, dst, tValues, tCount): chops at
## every (sorted) t value; `dst` holds 3 * tCount + 4 points.
pub func sk_chop_cubic_at_values(src0: const SkPoint[], dst0: SkPoint[], t_values: const f32[]):
let t_count = t_values.length
if t_count == 0: # nothing to chop
for i in 0..<4:
dst0[i] = src0[i]
return
var src_offset: usize = 0
var use_dst_as_src = false
var i: usize = 0
while i + 1 < t_count:
# Do two chops at once.
var t0 = t_values[i]
var t1 = t_values[i + 1]
if i != 0:
let last_t = t_values[i - 1]
t0 = sk_max(0.0, sk_min((t0 - last_t) / (1.0 - last_t), 1.0))
t1 = sk_max(0.0, sk_min((t1 - last_t) / (1.0 - last_t), 1.0))
var source: SkPoint[4]
for k: usize in 0..<4:
source[k] = dst0[src_offset + k] if use_dst_as_src else src0[k]
sk_chop_cubic_at2(source[0..], dst0[src_offset..], t0, t1)
src_offset += 6
use_dst_as_src = true
i += 2
if i < t_count:
# Chop the final cubic if there was an odd number of chops.
var t = t_values[i]
if i != 0:
let last_t = t_values[i - 1]
t = sk_max(0.0, sk_min((t - last_t) / (1.0 - last_t), 1.0))
var source: SkPoint[4]
for k: usize in 0..<4:
source[k] = dst0[src_offset + k] if use_dst_as_src else src0[k]
sk_chop_cubic_at(source[0..], dst0[src_offset..], t)
## Ported from src/core/SkGeometry.cpp:575 SkChopCubicAtHalf.
pub func sk_chop_cubic_at_half(src: const SkPoint[], dst: SkPoint[]):
sk_chop_cubic_at(src, dst, 0.5)
## Ported from src/core/SkGeometry.cpp:698 SkChopCubicAtYExtrema: given 4 points on a cubic
## bezier, chop it into 1, 2, 3 beziers such that the resulting beziers are monotonic in Y.
## Depending on what is returned, dst[] (10 points) is treated as follows:
## 0 dst[0..3] is the original cubic
## 1 dst[0..3] and dst[3..6] are the two new cubics
## 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
pub func sk_chop_cubic_at_y_extrema(src: const SkPoint[], dst: SkPoint[]) -> i32:
var t_values: f32[2] = [0.0, 0.0]
let roots = sk_find_cubic_extrema(src[0].y, src[1].y, src[2].y, src[3].y, t_values[0..])
sk_chop_cubic_at_values(src, dst, t_values[..<(usize)roots])
if roots > 0:
# we do some cleanup to ensure our Y extrema are flat
# flatten_double_cubic_extrema(&dst[0].fY)
dst[2].y = dst[3].y
dst[4].y = dst[3].y
if roots == 2:
dst[5].y = dst[6].y
dst[7].y = dst[6].y
return roots
# mark: SkCubicClipper ==========================================================================
## Ported from src/core/SkCubicClipper.cpp:26 SkCubicClipper::ChopMonoAtY (the BISECTION
## variant): the t at which the Y-monotonic cubic `pts` crosses `y`.
pub func sk_cubic_clipper_chop_mono_at_y(pts: const SkPoint[], y: f32, t: f32*) -> bool:
let ycrv0 = pts[0].y - y
let ycrv1 = pts[1].y - y
let ycrv2 = pts[2].y - y
let ycrv3 = pts[3].y - y
# Check that the endpoints straddle zero.
var t_neg: f32 # Negative and positive function parameters.
var t_pos: f32
if ycrv0 < 0.0:
if ycrv3 < 0.0:
return false
t_neg = 0.0
t_pos = 1.0
elif ycrv0 > 0.0:
if ycrv3 > 0.0:
return false
t_neg = 1.0
t_pos = 0.0
else:
*t = 0.0
return true
let tol: f32 = 1.0 / 65536.0 # 1 for fixed, 1e-5 for float.
while true:
let t_mid = (t_pos + t_neg) / 2.0
let y01 = sk_scalar_interp(ycrv0, ycrv1, t_mid)
let y12 = sk_scalar_interp(ycrv1, ycrv2, t_mid)
let y23 = sk_scalar_interp(ycrv2, ycrv3, t_mid)
let y012 = sk_scalar_interp(y01, y12, t_mid)
let y123 = sk_scalar_interp(y12, y23, t_mid)
let y0123 = sk_scalar_interp(y012, y123, t_mid)
if y0123 == 0.0:
*t = t_mid
return true
if y0123 < 0.0:
t_neg = t_mid
else:
t_pos = t_mid
if sk_scalar_abs(t_pos - t_neg) <= tol: # Nan-safe
break
*t = (t_neg + t_pos) / 2.0
return true