Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / gfx / sk_path_measure.lucb

#==============================================================================================
#
#   sk_path_measure - SkPathMeasure: lengths along a path, and points and tangents at them
#
#   DESCRIPTION:
#       Port of Skia m144 src/core/SkPathMeasure.cpp (lines 22-60) and
#       src/core/SkContourMeasure.cpp (lines 27-40 t values, 137-495 building a contour's
#       segments, 460-500 compute_pos_tan, 500-630 the iterator, SkTKSearch,
#       distanceToSegment and getPosTan), with SkPoint::Length, ::Distance and
#       set_point_length from src/core/SkPoint.cpp:22-92. Gfx::Path::place_text_along measures
#       the first contour of a path this way. getSegment and getMatrix are not ported (the
#       port has no caller for them).
#
#       Copyright 2008 The Android Open Source Project
#       Copyright 2018 Google Inc.
#       Copyright (c) 2026 the luce-browser authors.
#       SPDX-License-Identifier: BSD-3-Clause (see LICENSE-tiny-skia)
#
#==============================================================================================

# mark: SkPoint lengths =========================================================================

## Ported from src/core/SkPoint.cpp:79 SkPoint::Length.
pub func sk_point_length(dx: f32, dy: f32) -> f32:
    let mag2 = dx * dx + dy * dy
    if sk_is_finite(mag2):
        return math32.sqrt(mag2)
    let xx = (f64)dx
    let yy = (f64)dy
    return (f32)math.sqrt(xx * xx + yy * yy)

## Ported from include/private/base/SkPoint_impl.h:508 SkPoint::Distance.
pub func sk_point_distance(a: SkPoint, b: SkPoint) -> f32:
    return sk_point_length(a.x - b.x, a.y - b.y)

## Ported from src/core/SkPoint.cpp:42 set_point_length<false> (SkPoint::setLength(x, y,
## length)): (x, y) scaled to `length` in double; (0, 0) and false when that is not finite or
## zero.
pub func sk_point_set_length(pt: SkPoint*, x0: f32, y0: f32, length: f32) -> bool:
    # our mag2 step overflowed to infinity, so use doubles instead.
    # much slower, but needed when x or y are very large, other wise we
    # divide by inf. and return (0,0) vector.
    let xx = (f64)x0
    let yy = (f64)y0
    let dmag = math.sqrt(xx * xx + yy * yy)
    let dscale = (f64)length / dmag
    let x = (f32)((f64)x0 * dscale)
    let y = (f32)((f64)y0 * dscale)
    # check if we're not finite, or we're zero-length
    if not sk_is_finite2(x, y) or (x == 0.0 and y == 0.0):
        *pt = SkPoint(x = 0.0, y = 0.0)
        return false
    *pt = SkPoint(x = x, y = y)
    return true

# mark: Segments ================================================================================

# kMaxTValue: t values are 30-bit fixed point.
let sk_max_t_value: i32 = 0x3FFFFFFF

# The segment types (src/core/SkPathMeasurePriv.h:18).
let sk_seg_line: u8 = 0
let sk_seg_quad: u8 = 1
let sk_seg_cubic: u8 = 2
let sk_seg_conic: u8 = 3

## Ported from src/core/SkContourMeasure.cpp:29 tValue2Scalar.
func sk_t_value_to_scalar(t: i32) -> f32:
    # 1/kMaxTValue can't be represented as a float, but it's close and the limits work fine.
    let max_t_reciprocal: f32 = 1.0 / (f32)sk_max_t_value
    return (f32)t * max_t_reciprocal

## SkContourMeasure::Segment: the distance at its end, the index of its first point, its t
## value at the end and its type.
pub struct SkContourMeasureSegment:
    pub var distance: f32
    pub var pt_index: u32
    pub var t_value: i32
    pub var kind: u8

## Ported from src/core/SkContourMeasure.cpp:137 tspan_big_enough.
func sk_measure_tspan_big_enough(tspan: i32) -> i32:
    return tspan >> 10

# CHEAP_DIST_LIMIT: just made this value up.
let sk_cheap_dist_limit: f32 = 0.5

## Ported from src/core/SkContourMeasure.cpp:148 quad_too_curvy.
func sk_measure_quad_too_curvy(pts: const SkPoint[], tolerance: f32) -> bool:
    # diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
    # diff = -a/4 + b/2 - c/4
    let dx = pts[1].x * 0.5 - ((pts[0].x + pts[2].x) * 0.5) * 0.5
    let dy = pts[1].y * 0.5 - ((pts[0].y + pts[2].y) * 0.5) * 0.5

    let dist = sk_max(sk_scalar_abs(dx), sk_scalar_abs(dy))
    return dist > tolerance

## Ported from src/core/SkContourMeasure.cpp:161 conic_too_curvy.
func sk_measure_conic_too_curvy(first_pt: SkPoint, mid_t_pt: SkPoint, last_pt: SkPoint, tolerance: f32) -> bool:
    var mid_ends = sk_point_add(first_pt, last_pt)
    mid_ends = sk_point_scale(mid_ends, 0.5)
    let dxy = sk_point_sub(mid_t_pt, mid_ends)
    let dist = sk_max(sk_scalar_abs(dxy.x), sk_scalar_abs(dxy.y))
    return dist > tolerance

## Ported from src/core/SkContourMeasure.cpp:170 cheap_dist_exceeds_limit.
func sk_measure_cheap_dist_exceeds_limit(pt: SkPoint, x: f32, y: f32, tolerance: f32) -> bool:
    let dist = sk_max(sk_scalar_abs(x - pt.x), sk_scalar_abs(y - pt.y))
    # just made up the 1/2
    return dist > tolerance

## Ported from src/core/SkContourMeasure.cpp:177 cubic_too_curvy.
func sk_measure_cubic_too_curvy(pts: const SkPoint[], tolerance: f32) -> bool:
    let third: f32 = 1.0 / 3.0
    let two_thirds: f32 = 1.0 * 2.0 / 3.0
    return (sk_measure_cheap_dist_exceeds_limit(pts[1], sk_scalar_interp(pts[0].x, pts[3].x, third),
                                                sk_scalar_interp(pts[0].y, pts[3].y, third), tolerance) or sk_measure_cheap_dist_exceeds_limit(pts[2], sk_scalar_interp(pts[0].x, pts[3].x, two_thirds),
                                                                                                                                               sk_scalar_interp(pts[0].y, pts[3].y, two_thirds), tolerance))

# puts a cap on the total size of our output, since the client can pass in
# arbitrarily large values for resScale.
let sk_measure_max_recursion_depth: i32 = 8

# mark: Building a contour ======================================================================

## SkContourMeasure: one contour's segments, the points they use, its length and whether it
## is closed.
pub struct SkContourMeasure:
    pub var segments: ak.Vector[SkContourMeasureSegment]
    pub var pts: ak.Vector[SkPoint]
    pub var length: f32
    pub var is_closed: bool

## SkContourMeasureIter::Impl: the path (a copy), the position in it, the tolerance and
## whether contours are closed by force.
pub struct SkContourMeasureIter:
    var m_path: SkPath
    var m_iter_verb: usize
    var m_iter_point: usize
    var m_iter_weight: usize
    var m_tolerance: f32
    var m_force_closed: bool
    var m_valid: bool
    # temporary
    var m_segments: ak.Vector[SkContourMeasureSegment]
    var m_pts: ak.Vector[SkPoint]  # Points used to define the segments

# Appends a segment.
func sk_measure_append_segment(this: SkContourMeasureIter*, distance: f32, pt_index: u32, kind: u8, t_value: i32):
    ak.vector_append_t(&this.m_segments, SkContourMeasureSegment(distance = distance, pt_index = pt_index,
                                                                 t_value = t_value, kind = kind))

## Ported from src/core/SkContourMeasure.cpp:229 SkContourMeasureIter::Impl::compute_quad_segs.
func sk_measure_compute_quad_segs(this: SkContourMeasureIter*, pts: const SkPoint[], distance0: f32, mint: i32,
                                  maxt: i32, pt_index: u32, recursion_depth0: i32) -> f32:
    var distance = distance0
    var recursion_depth = recursion_depth0
    if recursion_depth < sk_measure_max_recursion_depth and sk_measure_tspan_big_enough(maxt - mint) != 0 and sk_measure_quad_too_curvy(pts, this.m_tolerance):
        var tmp: SkPoint[5]
        let halft = (mint + maxt) >> 1

        sk_chop_quad_at_half(pts, tmp[0..])
        recursion_depth += 1
        distance = sk_measure_compute_quad_segs(this, tmp[0..], distance, mint, halft, pt_index, recursion_depth)
        distance = sk_measure_compute_quad_segs(this, tmp[2..], distance, halft, maxt, pt_index, recursion_depth)
    else:
        let d = sk_point_distance(pts[0], pts[2])
        let prev_d = distance
        distance += d
        if distance > prev_d:
            sk_measure_append_segment(this, distance, pt_index, sk_seg_quad, maxt)
    return distance

## Ported from src/core/SkContourMeasure.cpp:255 SkContourMeasureIter::Impl::compute_conic_segs.
func sk_measure_compute_conic_segs(this: SkContourMeasureIter*, conic: const SkConic*, distance0: f32, mint: i32,
                                   min_pt: SkPoint, maxt: i32, max_pt: SkPoint, pt_index: u32, recursion_depth0: i32) -> f32:
    var distance = distance0
    var recursion_depth = recursion_depth0
    let halft = (mint + maxt) >> 1
    let half_pt = sk_conic_eval_at(conic, sk_t_value_to_scalar(halft))
    if not sk_point_is_finite(half_pt):
        return distance
    if recursion_depth < sk_measure_max_recursion_depth and sk_measure_tspan_big_enough(maxt - mint) != 0 and sk_measure_conic_too_curvy(min_pt, half_pt, max_pt, this.m_tolerance):
        recursion_depth += 1
        distance = sk_measure_compute_conic_segs(this, conic, distance, mint, min_pt, halft, half_pt, pt_index, recursion_depth)
        distance = sk_measure_compute_conic_segs(this, conic, distance, halft, half_pt, maxt, max_pt, pt_index, recursion_depth)
    else:
        let d = sk_point_distance(min_pt, max_pt)
        let prev_d = distance
        distance += d
        if distance > prev_d:
            sk_measure_append_segment(this, distance, pt_index, sk_seg_conic, maxt)
    return distance

## Ported from src/core/SkContourMeasure.cpp:284 SkContourMeasureIter::Impl::compute_cubic_segs.
func sk_measure_compute_cubic_segs(this: SkContourMeasureIter*, pts: const SkPoint[], distance0: f32, mint: i32,
                                   maxt: i32, pt_index: u32, recursion_depth0: i32) -> f32:
    var distance = distance0
    var recursion_depth = recursion_depth0
    if recursion_depth < sk_measure_max_recursion_depth and sk_measure_tspan_big_enough(maxt - mint) != 0 and sk_measure_cubic_too_curvy(pts, this.m_tolerance):
        var tmp: SkPoint[7]
        let halft = (mint + maxt) >> 1

        sk_chop_cubic_at_half(pts, tmp[0..])
        recursion_depth += 1
        distance = sk_measure_compute_cubic_segs(this, tmp[0..], distance, mint, halft, pt_index, recursion_depth)
        distance = sk_measure_compute_cubic_segs(this, tmp[3..], distance, halft, maxt, pt_index, recursion_depth)
    else:
        let d = sk_point_distance(pts[0], pts[3])
        let prev_d = distance
        distance += d
        if distance > prev_d:
            sk_measure_append_segment(this, distance, pt_index, sk_seg_cubic, maxt)
    return distance

## Ported from src/core/SkContourMeasure.cpp:312 SkContourMeasureIter::Impl::compute_line_seg.
func sk_measure_compute_line_seg(this: SkContourMeasureIter*, p0: SkPoint, p1: SkPoint, distance0: f32, pt_index: u32) -> f32:
    var distance = distance0
    let d = sk_point_distance(p0, p1)
    let prev_d = distance
    distance += d
    if distance > prev_d:
        sk_measure_append_segment(this, distance, pt_index, sk_seg_line, sk_max_t_value)
    return distance

## Ported from src/core/SkContourMeasure.cpp:357 SkContourMeasureIter::Impl::buildSegments:
## the next contour's measure, none when it has no length or is not finite.
func sk_measure_build_segments(this: SkContourMeasureIter*) -> SkContourMeasure?:
    var pt_index: i32 = -1
    var distance: f32 = 0.0
    var have_seen_close = this.m_force_closed
    var have_seen_move_to = false

    #  Note:
    #  as we accumulate distance, we have to check that the result of +=
    #  actually made it larger, since a very small delta might be > 0, but
    #  still have no effect on distance (if distance >>> delta).
    #
    #  We do this check below, and in compute_quad_segs and compute_cubic_segs

    this.m_segments = ak.vector_create_atomic[SkContourMeasureSegment]()
    this.m_pts = ak.vector_create_atomic[SkPoint]()

    var iter = sk_path_raw_iter(&this.m_path)
    iter.m_verb_index = this.m_iter_verb
    iter.m_pt_index = this.m_iter_point
    iter.m_weight_index = this.m_iter_weight
    while iter.m_verb_index < iter.m_verbs.length:
        # the verb at fIter, without advancing past a following contour's move
        if have_seen_move_to and iter.m_verbs[iter.m_verb_index] == SkPathVerb.move:
            break
        let rec = sk_path_raw_iter_next(&iter) else break
        let pts: const SkPoint[] = rec.pts
        match rec.verb:
            .move:
                pt_index += 1
                ak.vector_append_t(&this.m_pts, pts[0])
                have_seen_move_to = true
            .line:
                let prev_d = distance
                distance = sk_measure_compute_line_seg(this, pts[0], pts[1], distance, (u32)pt_index)
                if distance > prev_d:
                    ak.vector_append_t(&this.m_pts, pts[1])
                    pt_index += 1
            .quad:
                let prev_d = distance
                distance = sk_measure_compute_quad_segs(this, pts[..<3], distance, 0, sk_max_t_value, (u32)pt_index, 0)
                if distance > prev_d:
                    ak.vector_append_t(&this.m_pts, pts[1])
                    ak.vector_append_t(&this.m_pts, pts[2])
                    pt_index += 2
            .conic:
                let conic = sk_conic_from_points(pts[..<3], rec.conic_weight)
                let prev_d = distance
                distance = sk_measure_compute_conic_segs(this, &conic, distance, 0, conic.pts[0], sk_max_t_value, conic.pts[2], (u32)pt_index, 0)
                if distance > prev_d:
                    # we store the conic weight in our next point, followed by the last 2 pts
                    # thus to reconstitue a conic, you'd need to say
                    # SkConic(pts[0], pts[2], pts[3], weight = pts[1].fX)
                    ak.vector_append_t(&this.m_pts, SkPoint(x = conic.w, y = 0.0))
                    ak.vector_append_t(&this.m_pts, pts[1])
                    ak.vector_append_t(&this.m_pts, pts[2])
                    pt_index += 3
            .cubic:
                let prev_d = distance
                distance = sk_measure_compute_cubic_segs(this, pts[..<4], distance, 0, sk_max_t_value, (u32)pt_index, 0)
                if distance > prev_d:
                    ak.vector_append_t(&this.m_pts, pts[1])
                    ak.vector_append_t(&this.m_pts, pts[2])
                    ak.vector_append_t(&this.m_pts, pts[3])
                    pt_index += 3
            .close:
                have_seen_close = true
            _:
                trap("VERIFY_NOT_REACHED")
    this.m_iter_verb = iter.m_verb_index
    this.m_iter_point = iter.m_pt_index
    this.m_iter_weight = iter.m_weight_index

    if not sk_is_finite(distance):
        return none
    if ak.vector_is_empty(&this.m_segments):
        return none

    if have_seen_close:
        let prev_d = distance
        let first_pt = *ak.vector_at(&this.m_pts, 0)
        distance = sk_measure_compute_line_seg(this, *ak.vector_at(&this.m_pts, (usize)pt_index), first_pt, distance, (u32)pt_index)
        if distance > prev_d:
            ak.vector_append_t(&this.m_pts, first_pt)

    return SkContourMeasure(segments = this.m_segments, pts = this.m_pts, length = distance, is_closed = have_seen_close)

## Ported from src/core/SkContourMeasure.cpp:505 SkContourMeasureIter::SkContourMeasureIter
## (reset): measures the contours of a copy of `path`; a path that is not finite has none.
pub func sk_contour_measure_iter(path: const SkPath*, force_closed: bool, res_scale: f32 = 1.0) -> SkContourMeasureIter:
    return SkContourMeasureIter(m_path = sk_path_clone(path), m_iter_verb = 0, m_iter_point = 0,
                                m_iter_weight = 0, m_tolerance = sk_cheap_dist_limit * (1.0 / res_scale),
                                m_force_closed = force_closed, m_valid = sk_path_is_finite(path),
                                m_segments = ak.vector_create_atomic[SkContourMeasureSegment](), m_pts = ak.vector_create_atomic[SkPoint]())

## Ported from src/core/SkContourMeasure.cpp:525 SkContourMeasureIter::next: the next contour
## with a length, none when there are no more.
pub func sk_contour_measure_iter_next(this: SkContourMeasureIter*) -> SkContourMeasure?:
    if not this.m_valid:
        return none
    while this.m_iter_verb < ak.vector_size(&this.m_path.m_verbs):
        if let cm = sk_measure_build_segments(this):
            return cm
    return none

# mark: Positions and tangents ==================================================================

## Ported from src/core/SkContourMeasure.cpp:458 compute_pos_tan: the position and the
## normalized tangent at `t` of the segment of type `seg_type` starting at `pts`.
func sk_measure_compute_pos_tan(pts: const SkPoint[], seg_type: u8, t: f32) -> (SkPoint, SkPoint):
    var pos = SkPoint(x = 0.0, y = 0.0)
    var tangent = SkPoint(x = 0.0, y = 0.0)
    if seg_type == sk_seg_line:
        pos = SkPoint(x = sk_scalar_interp(pts[0].x, pts[1].x, t), y = sk_scalar_interp(pts[0].y, pts[1].y, t))
        _ = sk_point_set_length(&tangent, pts[1].x - pts[0].x, pts[1].y - pts[0].y, 1.0)
    elif seg_type == sk_seg_quad:
        pos = sk_eval_quad_at(pts, t)
        let raw = sk_eval_quad_tangent_at(pts, t)
        _ = sk_point_set_length(&tangent, raw.x, raw.y, 1.0)
    elif seg_type == sk_seg_conic:
        let conic = sk_conic(pts[0], pts[2], pts[3], pts[1].x)
        pos = sk_conic_eval_at(&conic, t)
        let raw = sk_conic_eval_tangent_at(&conic, t)
        _ = sk_point_set_length(&tangent, raw.x, raw.y, 1.0)
    elif seg_type == sk_seg_cubic:
        let (loc, raw) = sk_eval_cubic_at(pts, t)
        pos = loc
        _ = sk_point_set_length(&tangent, raw.x, raw.y, 1.0)
    else:
        trap("unknown segType")
    return (pos, tangent)

## Ported from src/core/SkContourMeasure.cpp:552 SkTKSearch over the segments' distances.
func sk_measure_tk_search(base: const SkContourMeasureSegment[], key: f32) -> i32:
    let count = base.length
    if count == 0:
        return ~0

    var lo: u32 = 0
    var hi = (u32)(count - 1)

    while lo < hi:
        let mid = (hi + lo) >> 1
        if base[mid].distance < key:
            lo = mid + 1
        else:
            hi = mid

    if base[hi].distance < key:
        hi += 1
        return ~(i32)hi
    elif key < base[hi].distance:
        return ~(i32)hi
    return (i32)hi

## Ported from src/core/SkContourMeasure.cpp:579 SkContourMeasure::distanceToSegment: the
## index of the segment at `distance` and the t there.
func sk_contour_measure_distance_to_segment(this: const SkContourMeasure*, distance: f32) -> (usize, f32):
    let segments = ak.vector_span_const(&this.segments)

    var index = sk_measure_tk_search(segments, distance)
    # don't care if we hit an exact match or not, so we xor index if it is negative
    index = index ^ (index >> 31)
    let seg = segments[(usize)index]

    # now interpolate t-values with the prev segment (if possible)
    var start_t: f32 = 0.0
    var start_d: f32 = 0.0
    # check if the prev segment is legal, and references the same set of points
    if index > 0:
        let prev = segments[(usize)index - 1]
        start_d = prev.distance
        if prev.pt_index == seg.pt_index:
            start_t = sk_t_value_to_scalar(prev.t_value)

    let t = start_t + (sk_t_value_to_scalar(seg.t_value) - start_t) * (distance - start_d) / (seg.distance - start_d)
    return ((usize)index, t)

## Ported from src/core/SkContourMeasure.cpp:609 SkContourMeasure::getPosTan: the position and
## unit tangent at `distance` (pinned to the contour), none for a NaN distance or t.
pub func sk_contour_measure_get_pos_tan(this: const SkContourMeasure*, distance0: f32) -> (SkPoint, SkPoint)?:
    var distance = distance0
    if sk_is_nan(distance):
        return none

    let length = this.length

    # pin the distance to a legal range
    if distance < 0.0:
        distance = 0.0
    elif distance > length:
        distance = length

    let (index, t) = sk_contour_measure_distance_to_segment(this, distance)
    if sk_is_nan(t):
        return none

    let seg = *ak.vector_at_const(&this.segments, index)
    let pts = ak.vector_span_const(&this.pts)
    return sk_measure_compute_pos_tan(pts[(usize)seg.pt_index..], seg.kind, t)

# mark: SkPathMeasure ===========================================================================

## SkPathMeasure (include/core/SkPathMeasure.h): the current contour of a path.
pub struct SkPathMeasure:
    var m_iter: SkContourMeasureIter
    var m_contour: SkContourMeasure?

## Ported from src/core/SkPathMeasure.cpp:24 SkPathMeasure::SkPathMeasure(path, forceClosed,
## resScale): measures the first contour.
pub func sk_path_measure(path: const SkPath*, force_closed: bool = false, res_scale: f32 = 1.0) -> SkPathMeasure:
    var measure = SkPathMeasure(m_iter = sk_contour_measure_iter(path, force_closed, res_scale), m_contour = none)
    measure.m_contour = sk_contour_measure_iter_next(&measure.m_iter)
    return measure

## Ported from src/core/SkPathMeasure.cpp:37 SkPathMeasure::getLength.
pub func sk_path_measure_get_length(this: const SkPathMeasure*) -> f32:
    if let contour = this.m_contour:
        return contour.length
    return 0.0

## Ported from src/core/SkPathMeasure.cpp:41 SkPathMeasure::getPosTan: the position and unit
## tangent at `distance` along the current contour.
pub func sk_path_measure_get_pos_tan(this: const SkPathMeasure*, distance: f32) -> (SkPoint, SkPoint)?:
    if let contour = this.m_contour:
        return sk_contour_measure_get_pos_tan(&contour, distance)
    return none

## Ported from src/core/SkPathMeasure.cpp:53 SkPathMeasure::isClosed.
pub func sk_path_measure_is_closed(this: const SkPathMeasure*) -> bool:
    if let contour = this.m_contour:
        return contour.is_closed
    return false

## Ported from src/core/SkPathMeasure.cpp:57 SkPathMeasure::nextContour.
pub func sk_path_measure_next_contour(this: SkPathMeasure*) -> bool:
    this.m_contour = sk_contour_measure_iter_next(&this.m_iter)
    if let _contour = this.m_contour:
        return true
    return false