Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / stroker.lucb

#==============================================================================================
#
#   stroker - path stroking (SkStroke): the stroke description and the contour walk
#
#   DESCRIPTION:
#       Port of tiny-skia-path stroker.rs, part 1 (lines 1-620): Stroke, LineCap, LineJoin,
#       the cap/join procedure types, SwappableBuilders, PathStroker and its per-segment
#       entry points (move_to, line_to, quad_to, cubic_to). Based on SkStroke.cpp, and
#       checked against Skia m144's SkStroke::strokePath (a closed rectangle goes through
#       strokeRect, stroker_rect.lucb; a zero-length line before a segment with length is
#       skipped, has_valid_tangent). The curve approximation is in stroker_curves.lucb, the
#       caps and joins in stroker_joins.lucb.
#
#==============================================================================================

# Skia swaps pointers to inner and outer builders during joining, but not builders itself.
struct SwappableBuilders:
    var inner: PathBuilder*
    var outer: PathBuilder*

    func swap():
        let tmp = self.inner
        self.inner = self.outer
        self.outer = tmp

## Stroke properties.
pub struct Stroke:
    ## A stroke thickness. Must be >= 0. When set to 0, a hairline stroking will be used.
    ## Default: 1.0
    pub var width: f32 = 1.0

    ## The limit at which a sharp corner is drawn beveled. Default: 4.0
    pub var miter_limit: f32 = 4.0

    ## A stroke line cap. Default: Butt
    pub var line_cap: LineCap = .butt

    ## A stroke line join. Default: Miter
    pub var line_join: LineJoin = .miter

    ## A stroke dashing properties. Default: none
    pub var dash: StrokeDash?

## Draws at the beginning and end of an open path contour.
pub enum LineCap as u8:
    ## No stroke extension.
    butt = 0
    ## Adds circle.
    round = 1
    ## Adds square.
    square = 2

## Specifies how corners are drawn when a shape is stroked. Join affects the four corners of
## a stroked rectangle, and the connected segments in a stroked path. Choose miter join to
## draw sharp corners. Choose round join to draw a circle with a radius equal to the stroke
## width on top of the corner. Choose bevel join to minimally connect the thick strokes.
## The fill path constructed to describe the stroked path respects the join setting but may
## not contain the actual join. For instance, a fill path constructed with round joins does
## not necessarily include circles at each connected segment.
pub enum LineJoin as u8:
    ## Extends to miter limit, then switches to bevel.
    miter = 0
    ## Extends to miter limit, then clips the corner.
    miter_clip = 1
    ## Adds circle.
    round = 2
    ## Connects outside edges.
    bevel = 3

let quad_recursive_limit: usize = 3

# quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
# largest seen for normal cubics: 5, 26
# largest seen for normal quads: 11
let recursive_limits: i32[4] = [5 * 3, 26 * 3, 11 * 3, 11 * 3]  # 3x limits seen in practice

type CapProc = func(Point, Point, Point, const PathBuilder*?, PathBuilder*) -> unit

type JoinProc = func(Point, Point, Point, f32, f32, bool, bool, SwappableBuilders) -> unit

enum ReductionType as u8:
    point = 0  # all curve points are practically identical
    line = 1  # the control point is on the line between the ends
    quad = 2  # the control point is outside the line between the ends
    degenerate = 3  # the control point is on the line but outside the ends
    degenerate2 = 4  # two control points are on the line but outside ends (cubic)
    degenerate3 = 5  # three areas of max curvature found (for cubic)

enum StrokeType as i8:
    outer = 1  # use sign-opposite values later to flip perpendicular axis
    inner = -1

enum ResultType as u8:
    split = 0  # the caller should split the quad stroke in two
    degenerate = 1  # the caller should add a line
    quad = 2  # the caller should (continue to try to) add a quad stroke

enum IntersectRayType as u8:
    ctrl_pt = 0
    result_type = 1

## A path stroker.
pub struct PathStroker:
    var radius: f32
    var inv_miter_limit: f32
    var res_scale: f32
    var inv_res_scale: f32
    var inv_res_scale_squared: f32

    var first_normal: Point
    var prev_normal: Point
    var first_unit_normal: Point
    var prev_unit_normal: Point

    # on original path
    var first_pt: Point
    var prev_pt: Point

    var first_outer_pt: Point
    var first_outer_pt_index_in_contour: usize
    var segment_count: i32
    var prev_is_line: bool

    var capper: CapProc
    var joiner: JoinProc

    # outer is our working answer, inner is temp
    var inner: PathBuilder
    var outer: PathBuilder
    var cusper: PathBuilder

    var stroke_type: StrokeType

    var recursion_depth: i32  # track stack depth to abort if numerics run amok
    var found_tangents: bool  # do less work until tangents meet (cubic)
    var join_completed: bool  # previous join was not degenerate

    ## Creates a new PathStroker.
    pub static func new_() -> PathStroker:
        return PathStroker(
            radius = 0.0,
            inv_miter_limit = 0.0,
            res_scale = 1.0,
            inv_res_scale = 1.0,
            inv_res_scale_squared = 1.0,
            first_normal = Point.zero(),
            prev_normal = Point.zero(),
            first_unit_normal = Point.zero(),
            prev_unit_normal = Point.zero(),
            first_pt = Point.zero(),
            prev_pt = Point.zero(),
            first_outer_pt = Point.zero(),
            first_outer_pt_index_in_contour = 0,
            segment_count = -1,
            prev_is_line = false,
            capper = butt_capper,
            joiner = miter_joiner,
            inner = PathBuilder(),
            outer = PathBuilder(),
            cusper = PathBuilder(),
            stroke_type = .outer,
            recursion_depth = 0,
            found_tangents = false,
            join_completed = false,
        )

    ## Computes a resolution scale. Resolution scale is the "intended" resolution for the
    ## output. Default is 1.0. Larger values (res > 1) indicate that the result should be
    ## more precise, since it will be zoomed up, and small errors will be magnified. Smaller
    ## values (0 < res < 1) indicate that the result can be less precise, since it will be
    ## zoomed down, and small errors may be invisible.
    pub static func compute_resolution_scale(ts: Transform) -> f32:
        let sx = Point.from_xy(ts.sx, ts.kx).length()
        let sy = Point.from_xy(ts.ky, ts.sy).length()
        if math32.is_finite(sx) and math32.is_finite(sy):
            let scale = fmax(sx, sy)
            if scale > 0.0:
                return scale
        return 1.0

    ## Stroke the path. Can be none when: `width` <= 0 or Nan/inf, `miter_limit` < 4 or
    ## NaN/inf (only when LineJoin::Miter is used). Unlike `Path.stroke`, allows to reuse
    ## internal allocations.
    pub func stroke(path: const Path*, stroke: const Stroke*, resolution_scale: f32) -> Path?:
        let width = stroke.width
        if not (math32.is_finite(width) and width > 0.0):
            return none
        # SkStroke::strokePath: a closed rectangle goes through strokeRect (Skia has no
        # miter-clip join, which keeps the general walk).
        if stroke.line_join != .miter_clip:
            if let contour = path_is_rect_contour(path):
                if contour.is_closed:
                    return stroke_rect(contour.rect, contour.clockwise, width, stroke.miter_limit, stroke.line_join)
        return self.stroke_inner(path, width, stroke.miter_limit, stroke.line_cap, stroke.line_join, resolution_scale)

    ## Frees the stroker's working storage.
    pub func release():
        self.inner.release()
        self.outer.release()
        self.cusper.release()

    func stroke_inner(path: const Path*, width: f32, miter_limit: f32, line_cap: LineCap, line_join0: LineJoin, res_scale: f32) -> Path?:
        var line_join = line_join0
        var inv_miter_limit: f32 = 0.0

        if line_join == .miter:
            if miter_limit <= 1.0:
                line_join = .bevel
            else:
                inv_miter_limit = invert(miter_limit)

        if line_join == .miter_clip:
            inv_miter_limit = invert(miter_limit)

        self.res_scale = res_scale
        # The '4' below matches the fill scan converter's error term.
        self.inv_res_scale = invert(res_scale * 4.0)
        self.inv_res_scale_squared = sqr(self.inv_res_scale)

        self.radius = half(width)
        self.inv_miter_limit = inv_miter_limit

        self.first_normal = Point.zero()
        self.prev_normal = Point.zero()
        self.first_unit_normal = Point.zero()
        self.prev_unit_normal = Point.zero()

        self.first_pt = Point.zero()
        self.prev_pt = Point.zero()

        self.first_outer_pt = Point.zero()
        self.first_outer_pt_index_in_contour = 0
        self.segment_count = -1
        self.prev_is_line = false

        self.capper = cap_factory(line_cap)
        self.joiner = join_factory(line_join)

        # Need some estimate of how large our final result (fOuter) and our per-contour temp
        # (fInner) will be, so we don't spend extra time repeatedly growing these arrays.
        #
        # 1x for inner == 'wag' (worst contour length would be better guess)
        self.inner.clear()
        self.inner.reserve(path.verbs.len, path.points.len)

        # 3x for result == inner + outer + join (swag)
        self.outer.clear()
        self.outer.reserve(path.verbs.len * 3, path.points.len * 3)

        self.cusper.clear()

        self.stroke_type = .outer

        self.recursion_depth = 0
        self.found_tangents = false
        self.join_completed = false

        var last_segment_is_line = false
        var iter = path.segments()
        iter.set_auto_close(true)
        while let segment = iter.next():
            match segment:
                .move_to(p):
                    self.move_to(p)
                .line_to(p):
                    self.line_to(p, &iter)
                    last_segment_is_line = true
                .quad_to(p1, p2):
                    self.quad_to(p1, p2)
                    last_segment_is_line = false
                .cubic_to(p1, p2, p3):
                    self.cubic_to(p1, p2, p3)
                    last_segment_is_line = false
                .conic_to(p1, p2, weight):
                    stroker_conic_to(&self, p1, p2, weight)
                    last_segment_is_line = false
                .close:
                    if line_cap != .butt:
                        # If the stroke consists of a moveTo followed by a close, treat it as
                        # if it were followed by a zero-length line. Lines without length can
                        # have square and round end caps.
                        if self.has_only_move_to():
                            self.line_to(self.move_to_pt(), none)
                            last_segment_is_line = true
                            continue

                        # If the stroke consists of a moveTo followed by one or more
                        # zero-length verbs, then followed by a close, treat is as if it were
                        # followed by a zero-length line. Lines without length can have
                        # square & round end caps.
                        if self.is_current_contour_empty():
                            last_segment_is_line = true
                            continue

                    self.close(last_segment_is_line)

        return self.finish(last_segment_is_line)

    func builders() -> SwappableBuilders:
        return SwappableBuilders(inner = &self.inner, outer = &self.outer)

    func move_to_pt() -> Point:
        return self.first_pt

    func move_to(p: Point):
        if self.segment_count > 0:
            self.finish_contour(false, false)

        self.segment_count = 0
        self.first_pt = p
        self.prev_pt = p
        self.join_completed = false

    func line_to(p: Point, iter: const PathSegmentsIter*?):
        let teeny_line = self.prev_pt.equals_within_tolerance(p, scalar_nearly_zero * self.inv_res_scale)
        if fn_ptr_eq(self.capper, butt_capper) and teeny_line:
            return

        if teeny_line:
            if self.join_completed:
                return
            if let it = iter:
                if it.has_valid_tangent():
                    return

        var normal = Point.zero()
        var unit_normal = Point.zero()
        if not self.pre_join_to(p, true, &normal, &unit_normal):
            return

        self.outer.line_to(p.x + normal.x, p.y + normal.y)
        self.inner.line_to(p.x - normal.x, p.y - normal.y)

        self.post_join_to(p, normal, unit_normal)

    func quad_to(p1: Point, p2: Point):
        let quad: Point[3] = [self.prev_pt, p1, p2]
        let (reduction, reduction_type) = check_quad_linear(quad)
        if reduction_type == .point:
            # If the stroke consists of a moveTo followed by a degenerate curve, treat it as
            # if it were followed by a zero-length line. Lines without length can have square
            # and round end caps.
            self.line_to(p2, none)
            return

        if reduction_type == .line:
            self.line_to(p2, none)
            return

        if reduction_type == .degenerate:
            self.line_to(reduction, none)
            let save_joiner = self.joiner
            self.joiner = round_joiner
            self.line_to(p2, none)
            self.joiner = save_joiner
            return

        var normal_ab = Point.zero()
        var unit_ab = Point.zero()
        var normal_bc = Point.zero()
        var unit_bc = Point.zero()
        if not self.pre_join_to(p1, false, &normal_ab, &unit_ab):
            self.line_to(p2, none)
            return

        var quad_points = QuadConstruct.default()
        init_quad(&self, .outer, 0.0, 1.0, &quad_points)
        _ = quad_stroke(&self, quad, &quad_points)
        init_quad(&self, .inner, 0.0, 1.0, &quad_points)
        _ = quad_stroke(&self, quad, &quad_points)

        let ok = set_normal_unit_normal(quad[1], quad[2], self.res_scale, self.radius, &normal_bc, &unit_bc)
        if not ok:
            normal_bc = normal_ab
            unit_bc = unit_ab

        self.post_join_to(p2, normal_bc, unit_bc)

    func cubic_to(pt1: Point, pt2: Point, pt3: Point):
        let cubic: Point[4] = [self.prev_pt, pt1, pt2, pt3]
        var reduction: Point[3] = [Point.zero(), Point.zero(), Point.zero()]
        var tangent_pt = Point.zero()
        let reduction_type = check_cubic_linear(cubic, reduction, &tangent_pt)
        if reduction_type == .point:
            # If the stroke consists of a moveTo followed by a degenerate curve, treat it as
            # if it were followed by a zero-length line. Lines without length can have square
            # and round end caps.
            self.line_to(pt3, none)
            return

        if reduction_type == .line:
            self.line_to(pt3, none)
            return

        if (u8)ReductionType.degenerate <= (u8)reduction_type and (u8)ReductionType.degenerate3 >= (u8)reduction_type:
            self.line_to(reduction[0], none)
            let save_joiner = self.joiner
            self.joiner = round_joiner
            if (u8)ReductionType.degenerate2 <= (u8)reduction_type:
                self.line_to(reduction[1], none)

            if reduction_type == .degenerate3:
                self.line_to(reduction[2], none)

            self.line_to(pt3, none)
            self.joiner = save_joiner
            return

        var normal_ab = Point.zero()
        var unit_ab = Point.zero()
        var normal_cd = Point.zero()
        var unit_cd = Point.zero()
        if not self.pre_join_to(tangent_pt, false, &normal_ab, &unit_ab):
            self.line_to(pt3, none)
            return

        var t_values = new_t_values()
        let t_count = find_cubic_inflections(cubic, t_values)
        var last_t: f32 = 0.0
        for index in 0..=t_count:
            let next_t = t_values[index] if index < t_count else 1.0

            var quad_points = QuadConstruct.default()
            init_quad(&self, .outer, last_t, next_t, &quad_points)
            _ = cubic_stroke(&self, cubic, &quad_points)
            init_quad(&self, .inner, last_t, next_t, &quad_points)
            _ = cubic_stroke(&self, cubic, &quad_points)
            last_t = next_t

        if let cusp = find_cubic_cusp(cubic):
            let cusp_loc = eval_cubic_pos_at(cubic, cusp)
            push_sk_circle(&self.cusper, cusp_loc.x, cusp_loc.y, self.radius)

        # emit the join even if one stroke succeeded but the last one failed
        # this avoids reversing an inner stroke with a partial path followed by another moveto
        set_cubic_end_normal(&self, cubic, normal_ab, unit_ab, &normal_cd, &unit_cd)

        self.post_join_to(pt3, normal_cd, unit_cd)

    func close(is_line: bool):
        self.finish_contour(true, is_line)

    func finish_contour(close: bool, curr_is_line: bool):
        if self.segment_count > 0:
            if close:
                self.joiner(self.prev_unit_normal, self.prev_pt, self.first_unit_normal, self.radius, self.inv_miter_limit, self.prev_is_line, curr_is_line, self.builders())
                self.outer.close()

                # now add inner as its own contour
                let pt = self.inner.last_point() else Point.zero()
                self.outer.move_to(pt.x, pt.y)
                self.outer.reverse_path_to(&self.inner)
                self.outer.close()
            else:
                # add caps to start and end

                # cap the end
                let pt = self.inner.last_point() else Point.zero()
                let end_other: const PathBuilder*? = &self.inner if curr_is_line else none
                self.capper(self.prev_pt, self.prev_normal, pt, end_other, &self.outer)
                self.outer.reverse_path_to(&self.inner)

                # cap the start
                let start_other: const PathBuilder*? = &self.inner if self.prev_is_line else none
                self.capper(self.first_pt, self.first_normal.neg(), self.first_outer_pt, start_other, &self.outer)
                self.outer.close()

            if not self.cusper.is_empty():
                self.outer.push_path_builder(&self.cusper)
                self.cusper.clear()

        # since we may re-use `inner`, we rewind instead of reset, to save on reallocating its
        # internal storage.
        self.inner.clear()
        self.segment_count = -1
        self.first_outer_pt_index_in_contour = self.outer.points.len

    func pre_join_to(p: Point, curr_is_line: bool, normal: Point*, unit_normal: Point*) -> bool:
        let prev_x = self.prev_pt.x
        let prev_y = self.prev_pt.y

        let normal_set = set_normal_unit_normal(self.prev_pt, p, self.res_scale, self.radius, normal, unit_normal)
        if not normal_set:
            if fn_ptr_eq(self.capper, butt_capper):
                return false

            # Square caps and round caps draw even if the segment length is zero. Since the
            # zero length segment has no direction, set the orientation to upright as the
            # default orientation.
            *normal = Point.from_xy(self.radius, 0.0)
            *unit_normal = Point.from_xy(1.0, 0.0)

        if self.segment_count == 0:
            self.first_normal = *normal
            self.first_unit_normal = *unit_normal
            self.first_outer_pt = Point.from_xy(prev_x + normal.x, prev_y + normal.y)

            self.outer.move_to(self.first_outer_pt.x, self.first_outer_pt.y)
            self.inner.move_to(prev_x - normal.x, prev_y - normal.y)
        else:
            # we have a previous segment
            self.joiner(self.prev_unit_normal, self.prev_pt, *unit_normal, self.radius, self.inv_miter_limit, self.prev_is_line, curr_is_line, self.builders())
        self.prev_is_line = curr_is_line
        return true

    func post_join_to(p: Point, normal: Point, unit_normal: Point):
        self.join_completed = true
        self.prev_pt = p
        self.prev_unit_normal = unit_normal
        self.prev_normal = normal
        self.segment_count += 1

    func finish(is_line: bool) -> Path?:
        self.finish_contour(false, is_line)

        # Swap out the outer builder.
        var buf = self.outer
        self.outer = PathBuilder()
        return buf.finish()

    func has_only_move_to() -> bool:
        return self.segment_count == 0

    func is_current_contour_empty() -> bool:
        return self.inner.is_zero_length_since_point(0) and self.outer.is_zero_length_since_point(self.first_outer_pt_index_in_contour)