Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / gfx / sk_path_contains.lucb

#==============================================================================================
#
#   sk_path_contains - SkPath::contains: point-in-path by winding numbers
#
#   DESCRIPTION:
#       Port of Skia m144 src/core/SkPathPriv.cpp lines 884-1370 (poly_eval, between,
#       eval_cubic_pts, find_minmax, checkOnCurve, the winding_* counters for lines, quads,
#       conics and cubics, the tangent_* collectors and SkPathPriv::Contains) and
#       src/core/SkPath.cpp:547 (SkPath::contains, which needs a finite path). Points on the
#       path's edges count as inside, with coincident edges cancelled by their tangents.
#
#       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/SkPathPriv.cpp:884 poly_eval(A, B, C, t).
func sk_contains_poly_eval3(a: f32, b: f32, c_: f32, t: f32) -> f32:
    return (a * t + b) * t + c_

## Ported from src/core/SkPathPriv.cpp:888 poly_eval(A, B, C, D, t).
func sk_contains_poly_eval4(a: f32, b: f32, c_: f32, d: f32, t: f32) -> f32:
    return ((a * t + b) * t + c_) * t + d

## Ported from src/core/SkPathPriv.cpp:893 between: (a <= b <= c) || (a >= b >= c).
func sk_contains_between(a: f32, b: f32, c_: f32) -> bool:
    return (a - b) * (c_ - b) <= 0.0

## Ported from src/core/SkPathPriv.cpp:899 eval_cubic_pts.
func sk_contains_eval_cubic_pts(c0: f32, c1: f32, c2: f32, c3: f32, t: f32) -> f32:
    let a = c3 + 3.0 * (c1 - c2) - c0
    let b = 3.0 * (c2 - c1 - c1 + c0)
    let c_ = 3.0 * (c1 - c0)
    let d = c0
    return sk_contains_poly_eval4(a, b, c_, d, t)

## Ported from src/core/SkPathPriv.cpp:908 find_minmax<N> (over the x coordinates).
func sk_contains_find_minmax(pts: const SkPoint[]) -> (f32, f32):
    var min = pts[0].x
    var max = pts[0].x
    for i in 1..<pts.length:
        min = sk_min(min, pts[i].x)
        max = sk_max(max, pts[i].x)
    return (min, max)

## Ported from src/core/SkPathPriv.cpp:920 checkOnCurve.
func sk_contains_check_on_curve(x: f32, y: f32, start: SkPoint, end: SkPoint) -> bool:
    if start.y == end.y:
        return sk_contains_between(start.x, x, end.x) and x != end.x
    return x == start.x and y == start.y

# mark: Winding =================================================================================

## Ported from src/core/SkPathPriv.cpp:928 winding_mono_cubic.
func sk_contains_winding_mono_cubic(pts: const SkPoint[], x: f32, y: f32, on_curve_count: i32*) -> i32:
    var y0 = pts[0].y
    var y3 = pts[3].y

    var dir: i32 = 1
    if y0 > y3:
        let swap = y0
        y0 = y3
        y3 = swap
        dir = -1
    if y < y0 or y > y3:
        return 0
    if sk_contains_check_on_curve(x, y, pts[0], pts[3]):
        *on_curve_count += 1
        return 0
    if y == y3:
        return 0

    # quickreject or quickaccept
    let (min, max) = sk_contains_find_minmax(pts[..<4])
    if x < min:
        return 0
    if x > max:
        return dir

    # compute the actual x(t) value
    var t: f32 = 0.0
    if not sk_cubic_clipper_chop_mono_at_y(pts, y, &t):
        return 0
    let xt = sk_contains_eval_cubic_pts(pts[0].x, pts[1].x, pts[2].x, pts[3].x, t)
    if sk_scalar_nearly_equal(xt, x):
        if x != pts[3].x or y != pts[3].y:  # don't test end points; they're start points
            *on_curve_count += 1
            return 0
    return dir if xt < x else 0

## Ported from src/core/SkPathPriv.cpp:974 winding_cubic.
func sk_contains_winding_cubic(pts: const SkPoint[], x: f32, y: f32, on_curve_count: i32*) -> i32:
    var dst: SkPoint[10]
    let n = sk_chop_cubic_at_y_extrema(pts, dst[0..])
    var w: i32 = 0
    for i in 0..=(usize)n:
        w += sk_contains_winding_mono_cubic(dst[i * 3..], x, y, on_curve_count)
    return w

## Ported from src/core/SkPathPriv.cpp:984 conic_eval_numerator (`offset` 0 for x, 1 for y).
func sk_contains_conic_eval_numerator(pts: const SkPoint[], offset: usize, w: f32, t: f32) -> f64:
    let s0 = pts[0].x if offset == 0 else pts[0].y
    let s2 = pts[1].x if offset == 0 else pts[1].y
    let s4 = pts[2].x if offset == 0 else pts[2].y
    let src2w = s2 * w
    let c_ = s0
    let a = s4 - 2.0 * src2w + c_
    let b = 2.0 * (src2w - c_)
    return (f64)sk_contains_poly_eval3(a, b, c_, t)

## Ported from src/core/SkPathPriv.cpp:995 conic_eval_denominator.
func sk_contains_conic_eval_denominator(w: f32, t: f32) -> f64:
    let b = 2.0 * (w - 1.0)
    let c_: f32 = 1.0
    let a = -b
    return (f64)sk_contains_poly_eval3(a, b, c_, t)

## Ported from src/core/SkPathPriv.cpp:1002 winding_mono_conic.
func sk_contains_winding_mono_conic(conic: const SkConic*, x: f32, y: f32, on_curve_count: i32*) -> i32:
    let pts: const SkPoint[] = conic.pts
    var y0 = pts[0].y
    var y2 = pts[2].y

    var dir: i32 = 1
    if y0 > y2:
        let swap = y0
        y0 = y2
        y2 = swap
        dir = -1
    if y < y0 or y > y2:
        return 0
    if sk_contains_check_on_curve(x, y, pts[0], pts[2]):
        *on_curve_count += 1
        return 0
    if y == y2:
        return 0

    var roots: f32[2] = [0.0, 0.0]
    var a = pts[2].y
    var b = pts[1].y * conic.w - y * conic.w + y
    var c_ = pts[0].y
    a += c_ - 2.0 * b  # A = a + c - 2*(b*w - yCept*w + yCept)
    b -= c_  # B = b*w - w * yCept + yCept - a
    c_ -= y
    let n = sk_find_unit_quad_roots(a, 2.0 * b, c_, roots[0..])
    var xt: f32
    if 0 == n:
        # zero roots are returned only when y0 == y
        # Need [0] if dir == 1
        # and  [2] if dir == -1
        xt = pts[(usize)(1 - dir)].x
    else:
        let t = roots[0]
        xt = (f32)(sk_contains_conic_eval_numerator(pts, 0, conic.w, t) / sk_contains_conic_eval_denominator(conic.w, t))
    if sk_scalar_nearly_equal(xt, x):
        if x != pts[2].x or y != pts[2].y:  # don't test end points; they're start points
            *on_curve_count += 1
            return 0
    return dir if xt < x else 0

## Ported from src/core/SkPathPriv.cpp:1052 is_mono_quad.
func sk_contains_is_mono_quad(y0: f32, y1: f32, y2: f32) -> bool:
    #    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
    if y0 == y1:
        return true
    if y0 < y1:
        return y1 <= y2
    return y1 >= y2

## Ported from src/core/SkPathPriv.cpp:1064 winding_conic.
func sk_contains_winding_conic(pts: const SkPoint[], x: f32, y: f32, weight: f32, on_curve_count: i32*) -> i32:
    let conic = sk_conic_from_points(pts, weight)
    var chopped: SkConic[2]
    # If the data points are very large, the conic may not be monotonic but may also
    # fail to chop. Then, the chopper does not split the original conic in two.
    let is_mono = sk_contains_is_mono_quad(pts[0].y, pts[1].y, pts[2].y) or not sk_conic_chop_at_y_extrema(&conic, chopped[0..])
    if is_mono:
        return sk_contains_winding_mono_conic(&conic, x, y, on_curve_count)
    var w = sk_contains_winding_mono_conic(&chopped[0], x, y, on_curve_count)
    if not is_mono:
        w += sk_contains_winding_mono_conic(&chopped[1], x, y, on_curve_count)
    return w

## Ported from src/core/SkPathPriv.cpp:1078 winding_mono_quad.
func sk_contains_winding_mono_quad(pts: const SkPoint[], x: f32, y: f32, on_curve_count: i32*) -> i32:
    var y0 = pts[0].y
    var y2 = pts[2].y

    var dir: i32 = 1
    if y0 > y2:
        let swap = y0
        y0 = y2
        y2 = swap
        dir = -1
    if y < y0 or y > y2:
        return 0
    if sk_contains_check_on_curve(x, y, pts[0], pts[2]):
        *on_curve_count += 1
        return 0
    if y == y2:
        return 0

    var roots: f32[2] = [0.0, 0.0]
    let n = sk_find_unit_quad_roots(pts[0].y - 2.0 * pts[1].y + pts[2].y,
                                    2.0 * (pts[1].y - pts[0].y),
                                    pts[0].y - y,
                                    roots[0..])
    var xt: f32
    if 0 == n:
        # zero roots are returned only when y0 == y
        # Need [0] if dir == 1
        # and  [2] if dir == -1
        xt = pts[(usize)(1 - dir)].x
    else:
        let t = roots[0]
        let c_ = pts[0].x
        let a = pts[2].x - 2.0 * pts[1].x + c_
        let b = 2.0 * (pts[1].x - c_)
        xt = sk_contains_poly_eval3(a, b, c_, t)
    if sk_scalar_nearly_equal(xt, x):
        if x != pts[2].x or y != pts[2].y:  # don't test end points; they're start points
            *on_curve_count += 1
            return 0
    return dir if xt < x else 0

## Ported from src/core/SkPathPriv.cpp:1133 winding_quad.
func sk_contains_winding_quad(pts: const SkPoint[], x: f32, y: f32, on_curve_count: i32*) -> i32:
    var span_storage: SkPoint[5]
    var n: i32 = 0

    var span = pts
    if not sk_contains_is_mono_quad(pts[0].y, pts[1].y, pts[2].y):
        n = sk_chop_quad_at_y_extrema(pts, span_storage[0..])
        span = span_storage[0..]
    var w = sk_contains_winding_mono_quad(span, x, y, on_curve_count)
    if n > 0:
        w += sk_contains_winding_mono_quad(span[2..], x, y, on_curve_count)
    return w

## Ported from src/core/SkPathPriv.cpp:1149 winding_line.
func sk_contains_winding_line(pts: const SkPoint[], x: f32, y: f32, on_curve_count: i32*) -> i32:
    let x0 = pts[0].x
    var y0 = pts[0].y
    let x1 = pts[1].x
    var y1 = pts[1].y

    let dy = y1 - y0

    var dir: i32 = 1
    if y0 > y1:
        let swap = y0
        y0 = y1
        y1 = swap
        dir = -1
    if y < y0 or y > y1:
        return 0
    if sk_contains_check_on_curve(x, y, pts[0], pts[1]):
        *on_curve_count += 1
        return 0
    if y == y1:
        return 0
    let cross = (x1 - x0) * (y - pts[0].y) - dy * (x - x0)

    if cross == 0.0:
        # zero cross means the point is on the line, and since the case where
        # y of the query point is at the end point is handled above, we can be
        # sure that we're on the line (excluding the end point) here
        if x != x1 or y != pts[1].y:
            *on_curve_count += 1
        dir = 0
    elif sk_scalar_sign_as_int(cross) == dir:
        dir = 0
    return dir

# mark: Tangents ================================================================================

## Ported from src/core/SkPathPriv.cpp:1189 tangent_cubic.
func sk_contains_tangent_cubic(pts: const SkPoint[], x: f32, y: f32, tangents: ak.Vector[SkPoint]*):
    if not sk_contains_between(pts[0].y, y, pts[1].y) and not sk_contains_between(pts[1].y, y, pts[2].y) and not sk_contains_between(pts[2].y, y, pts[3].y):
        return
    if not sk_contains_between(pts[0].x, x, pts[1].x) and not sk_contains_between(pts[1].x, x, pts[2].x) and not sk_contains_between(pts[2].x, x, pts[3].x):
        return
    var dst: SkPoint[10]
    let n = sk_chop_cubic_at_y_extrema(pts, dst[0..])
    for i in 0..=(usize)n:
        let c_ = dst[i * 3..]
        var t: f32 = 0.0
        if not sk_cubic_clipper_chop_mono_at_y(c_, y, &t):
            continue
        let xt = sk_contains_eval_cubic_pts(c_[0].x, c_[1].x, c_[2].x, c_[3].x, t)
        if not sk_scalar_nearly_equal(x, xt):
            continue
        let (_loc, tangent) = sk_eval_cubic_at(c_, t)
        ak.vector_append_t(tangents, tangent)

## Ported from src/core/SkPathPriv.cpp:1217 tangent_conic.
func sk_contains_tangent_conic(pts: const SkPoint[], x: f32, y: f32, w: f32, tangents: ak.Vector[SkPoint]*):
    if not sk_contains_between(pts[0].y, y, pts[1].y) and not sk_contains_between(pts[1].y, y, pts[2].y):
        return
    if not sk_contains_between(pts[0].x, x, pts[1].x) and not sk_contains_between(pts[1].x, x, pts[2].x):
        return
    var roots: f32[2] = [0.0, 0.0]
    var a = pts[2].y
    var b = pts[1].y * w - y * w + y
    var c_ = pts[0].y
    a += c_ - 2.0 * b  # A = a + c - 2*(b*w - yCept*w + yCept)
    b -= c_  # B = b*w - w * yCept + yCept - a
    c_ -= y
    let n = sk_find_unit_quad_roots(a, 2.0 * b, c_, roots[0..])
    for index in 0..<(usize)n:
        let t = roots[index]
        let xt = (f32)(sk_contains_conic_eval_numerator(pts, 0, w, t) / sk_contains_conic_eval_denominator(w, t))
        if not sk_scalar_nearly_equal(x, xt):
            continue
        let conic = sk_conic_from_points(pts, w)
        ak.vector_append_t(tangents, sk_conic_eval_tangent_at(&conic, t))

## Ported from src/core/SkPathPriv.cpp:1244 tangent_quad.
func sk_contains_tangent_quad(pts: const SkPoint[], x: f32, y: f32, tangents: ak.Vector[SkPoint]*):
    if not sk_contains_between(pts[0].y, y, pts[1].y) and not sk_contains_between(pts[1].y, y, pts[2].y):
        return
    if not sk_contains_between(pts[0].x, x, pts[1].x) and not sk_contains_between(pts[1].x, x, pts[2].x):
        return
    var roots: f32[2] = [0.0, 0.0]
    let n = sk_find_unit_quad_roots(pts[0].y - 2.0 * pts[1].y + pts[2].y,
                                    2.0 * (pts[1].y - pts[0].y),
                                    pts[0].y - y,
                                    roots[0..])
    for index in 0..<(usize)n:
        let t = roots[index]
        let c_ = pts[0].x
        let a = pts[2].x - 2.0 * pts[1].x + c_
        let b = 2.0 * (pts[1].x - c_)
        let xt = sk_contains_poly_eval3(a, b, c_, t)
        if not sk_scalar_nearly_equal(x, xt):
            continue
        ak.vector_append_t(tangents, sk_eval_quad_tangent_at(pts, t))

## Ported from src/core/SkPathPriv.cpp:1270 tangent_line.
func sk_contains_tangent_line(pts: const SkPoint[], x: f32, y: f32, tangents: ak.Vector[SkPoint]*):
    let y0 = pts[0].y
    let y1 = pts[1].y
    if not sk_contains_between(y0, y, y1):
        return
    let x0 = pts[0].x
    let x1 = pts[1].x
    if not sk_contains_between(x0, x, x1):
        return
    let dx = x1 - x0
    let dy = y1 - y0
    if not sk_scalar_nearly_equal((x - x0) * dy, dx * (y - y0)):
        return
    ak.vector_append_t(tangents, SkPoint(x = dx, y = dy))

## Ported from src/core/SkPathPriv.cpp:1292 contains_inclusive.
func sk_contains_inclusive(r: SkRect, x: f32, y: f32) -> bool:
    return r.left <= x and x <= r.right and r.top <= y and y <= r.bottom

# mark: Contains ================================================================================

## Ported from src/core/SkPath.cpp:547 SkPath::contains and src/core/SkPathPriv.cpp:1296
## SkPathPriv::Contains: whether (x, y) is inside the path under its fill type. A path with a
## non-finite point contains nothing.
pub func sk_path_contains(this: const SkPath*, x: f32, y: f32) -> bool:
    # SkPathPriv::Raw answers none for a path that is not finite.
    var bounds: SkRect
    if not sk_rect_set_bounds_check(&bounds, sk_path_points(this)):
        return false

    let ft = this.m_fill_type
    let is_inverse = ft == SkPathFillType.inverse_winding or ft == SkPathFillType.inverse_even_odd
    if sk_path_is_empty(this):
        return is_inverse

    if not sk_contains_inclusive(bounds, x, y):
        return is_inverse

    var w: i32 = 0
    var on_curve_count: i32 = 0

    var iter = sk_path_edge_iter(this)
    while let rec = sk_path_edge_iter_next(&iter):
        match rec.edge:
            .line:
                w += sk_contains_winding_line(rec.pts[..<2], x, y, &on_curve_count)
            .quad:
                w += sk_contains_winding_quad(rec.pts[..<3], x, y, &on_curve_count)
            .conic:
                w += sk_contains_winding_conic(rec.pts[..<3], x, y, sk_path_edge_iter_conic_weight(&iter), &on_curve_count)
            .cubic:
                w += sk_contains_winding_cubic(rec.pts[..<4], x, y, &on_curve_count)
            _:
                trap("VERIFY_NOT_REACHED")
    let even_odd_fill = SkPathFillType.even_odd == ft or SkPathFillType.inverse_even_odd == ft
    if even_odd_fill:
        w &= 1
    if w != 0:
        return not is_inverse
    if on_curve_count <= 1:
        return (on_curve_count != 0) != is_inverse
    if (on_curve_count & 1) != 0 or even_odd_fill:
        return ((on_curve_count & 1) != 0) != is_inverse
    # If the point touches an even number of curves, and the fill is winding, check for
    # coincidence. Count coincidence as places where the on curve points have identical tangents.
    var tangents = ak.vector_create_atomic[SkPoint]()
    var tangent_iter = sk_path_edge_iter(this)
    while let rec = sk_path_edge_iter_next(&tangent_iter):
        let old_count = ak.vector_size(&tangents)
        match rec.edge:
            .line:
                sk_contains_tangent_line(rec.pts[..<2], x, y, &tangents)
            .quad:
                sk_contains_tangent_quad(rec.pts[..<3], x, y, &tangents)
            .conic:
                sk_contains_tangent_conic(rec.pts[..<3], x, y, sk_path_edge_iter_conic_weight(&tangent_iter), &tangents)
            .cubic:
                sk_contains_tangent_cubic(rec.pts[..<4], x, y, &tangents)
            _:
                trap("VERIFY_NOT_REACHED")
        if ak.vector_size(&tangents) > old_count:
            let last = ak.vector_size(&tangents) - 1
            let tangent = *ak.vector_at(&tangents, last)
            if sk_scalar_nearly_zero_tol(sk_point_length_sqd(tangent)):
                ak.vector_remove(&tangents, last)
            else:
                for index in 0..<last:
                    let probe = *ak.vector_at(&tangents, index)
                    if sk_scalar_nearly_zero_tol(sk_point_cross(probe, tangent)) and sk_scalar_sign_as_int(tangent.x * probe.x) <= 0 and sk_scalar_sign_as_int(tangent.y * probe.y) <= 0:
                        ak.vector_remove(&tangents, last)
                        # removeShuffle: the last element moves into the removed slot
                        let size = ak.vector_size(&tangents)
                        if index != size - 1:
                            *ak.vector_at(&tangents, index) = *ak.vector_at(&tangents, size - 1)
                        ak.vector_remove(&tangents, size - 1)
                        break
    return (ak.vector_size(&tangents) != 0) != is_inverse