Luce packages
LuceLuce BaseLuciaOS

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