Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / stroker_curves.lucb

#==============================================================================================
#
#   stroker_curves - approximating the offset of quads and cubics with quads
#
#   DESCRIPTION:
#       Port of tiny-skia-path stroker.rs, part 2 (PathStroker's curve methods, lines
#       460-1010): cubic_stroke, quad_stroke, the perpendicular rays, compare_quad_cubic /
#       compare_quad_quad, stroke_close_enough, intersect_ray and QuadConstruct. The methods
#       are free functions over `s: PathStroker*` to keep PathStroker's body in one fragment
#       of reasonable size; their names and bodies are tiny-skia's.
#
#==============================================================================================

func cubic_stroke(s: PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> bool:
    if not s.found_tangents:
        let result_type = tangents_meet(s, cubic, quad_points)
        if result_type != .quad:
            let ok = points_within_dist(quad_points.quad[0], quad_points.quad[2], s.inv_res_scale)
            if (result_type == .degenerate or ok) and cubic_mid_on_line(s, cubic, quad_points):
                add_degenerate_line(s, quad_points)
                return true
        else:
            s.found_tangents = true

    if s.found_tangents:
        let result_type = compare_quad_cubic(s, cubic, quad_points)
        if result_type == .quad:
            let stroke = quad_points.quad
            if s.stroke_type == .outer:
                s.outer.quad_to(stroke[1].x, stroke[1].y, stroke[2].x, stroke[2].y)
            else:
                s.inner.quad_to(stroke[1].x, stroke[1].y, stroke[2].x, stroke[2].y)
            return true

        if result_type == .degenerate:
            if not quad_points.opposite_tangents:
                add_degenerate_line(s, quad_points)
                return true

    if not math32.is_finite(quad_points.quad[2].x) or not math32.is_finite(quad_points.quad[2].x):
        return false  # just abort if projected quad isn't representable

    s.recursion_depth += 1
    if s.recursion_depth > recursive_limits[(usize)s.found_tangents]:
        return false  # just abort if projected quad isn't representable

    var half_quad = QuadConstruct.default()
    if not half_quad.init_with_start(quad_points):
        add_degenerate_line(s, quad_points)
        s.recursion_depth -= 1
        return true

    if not cubic_stroke(s, cubic, &half_quad):
        return false

    if not half_quad.init_with_end(quad_points):
        add_degenerate_line(s, quad_points)
        s.recursion_depth -= 1
        return true

    if not cubic_stroke(s, cubic, &half_quad):
        return false

    s.recursion_depth -= 1
    return true

func cubic_mid_on_line(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> bool:
    var stroke_mid = Point.zero()
    cubic_quad_mid(s, cubic, quad_points, &stroke_mid)
    let dist = pt_to_line(stroke_mid, quad_points.quad[0], quad_points.quad[2])
    return dist < s.inv_res_scale_squared

func cubic_quad_mid(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*, mid: Point*):
    var cubic_mid_pt = Point.zero()
    cubic_perp_ray(s, cubic, quad_points.mid_t, &cubic_mid_pt, mid, none)

# Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular
# tangent.
func cubic_perp_ray(s: const PathStroker*, cubic: const Point[], t: f32, t_pt: Point*, on_pt: Point*, tangent: Point*?):
    *t_pt = eval_cubic_pos_at(cubic, t)
    var dxy = eval_cubic_tangent_at(cubic, t)

    var chopped: Point[7] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
    if dxy.x == 0.0 and dxy.y == 0.0:
        var c_points = cubic
        if is_nearly_zero(t):
            dxy = cubic[2].sub(cubic[0])
        elif is_nearly_zero(1.0 - t):
            dxy = cubic[3].sub(cubic[1])
        else:
            # If the cubic inflection falls on the cusp, subdivide the cubic to find the
            # tangent at that point.
            #
            # Unwrap never fails, because we already checked that `t` is not 0/1,
            let tt = normalized_exclusive_new(t) else trap("unreachable")
            chop_cubic_at2(cubic, tt, chopped)
            dxy = chopped[3].sub(chopped[2])
            if dxy.x == 0.0 and dxy.y == 0.0:
                dxy = chopped[3].sub(chopped[1])
                c_points = chopped

        if dxy.x == 0.0 and dxy.y == 0.0:
            dxy = c_points[3].sub(c_points[0])

    set_ray_points(s, *t_pt, &dxy, on_pt, tangent)

func set_cubic_end_normal(s: const PathStroker*, cubic: const Point[], normal_ab: Point, unit_normal_ab: Point, normal_cd: Point*, unit_normal_cd: Point*):
    var ab = cubic[1].sub(cubic[0])
    var cd = cubic[3].sub(cubic[2])

    var degenerate_ab = degenerate_vector(ab)
    var degenerate_cb = degenerate_vector(cd)

    if degenerate_ab and degenerate_cb:
        *normal_cd = normal_ab
        *unit_normal_cd = unit_normal_ab
        return

    if degenerate_ab:
        ab = cubic[2].sub(cubic[0])
        degenerate_ab = degenerate_vector(ab)

    if degenerate_cb:
        cd = cubic[3].sub(cubic[1])
        degenerate_cb = degenerate_vector(cd)

    if degenerate_ab or degenerate_cb:
        *normal_cd = normal_ab
        *unit_normal_cd = unit_normal_ab
        return

    _ = set_normal_unit_normal2(cd, s.radius, normal_cd, unit_normal_cd)

func compare_quad_cubic(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> ResultType:
    # get the quadratic approximation of the stroke
    cubic_quad_ends(s, cubic, quad_points)
    let result_type = intersect_ray(s, .ctrl_pt, quad_points)
    if result_type != .quad:
        return result_type

    # project a ray from the curve to the stroke
    # points near midpoint on quad, midpoint on cubic
    var ray0 = Point.zero()
    var ray1 = Point.zero()
    cubic_perp_ray(s, cubic, quad_points.mid_t, &ray1, &ray0, none)
    let stroke = quad_points.quad
    return stroke_close_enough(s, stroke, [ray0, ray1], quad_points)

# Given a cubic and a t range, find the start and end if they haven't been found already.
func cubic_quad_ends(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*):
    if not quad_points.start_set:
        var cubic_start_pt = Point.zero()
        cubic_perp_ray(s, cubic, quad_points.start_t, &cubic_start_pt, &quad_points.quad[0], &quad_points.tangent_start)
        quad_points.start_set = true

    if not quad_points.end_set:
        var cubic_end_pt = Point.zero()
        cubic_perp_ray(s, cubic, quad_points.end_t, &cubic_end_pt, &quad_points.quad[2], &quad_points.tangent_end)
        quad_points.end_set = true

func init_quad(s: PathStroker*, stroke_type: StrokeType, start: f32, end: f32, quad_points: QuadConstruct*):
    s.stroke_type = stroke_type
    s.found_tangents = false
    _ = quad_points.init_(start, end)

func quad_stroke(s: PathStroker*, quad: const Point[], quad_points: QuadConstruct*) -> bool:
    let result_type = compare_quad_quad(s, quad, quad_points)
    if result_type == .quad:
        let path: PathBuilder* = &s.outer if s.stroke_type == .outer else &s.inner
        path.quad_to(quad_points.quad[1].x, quad_points.quad[1].y, quad_points.quad[2].x, quad_points.quad[2].y)
        return true

    if result_type == .degenerate:
        add_degenerate_line(s, quad_points)
        return true

    s.recursion_depth += 1
    if s.recursion_depth > recursive_limits[quad_recursive_limit]:
        # If we stop making progress, just emit a line and move on
        add_degenerate_line(s, quad_points)
        return true

    var half_quad = QuadConstruct.default()
    _ = half_quad.init_with_start(quad_points)
    if not quad_stroke(s, quad, &half_quad):
        return false

    _ = half_quad.init_with_end(quad_points)
    if not quad_stroke(s, quad, &half_quad):
        return false

    s.recursion_depth -= 1
    return true

func compare_quad_quad(s: PathStroker*, quad: const Point[], quad_points: QuadConstruct*) -> ResultType:
    # get the quadratic approximation of the stroke
    if not quad_points.start_set:
        var quad_start_pt = Point.zero()
        quad_perp_ray(s, quad, quad_points.start_t, &quad_start_pt, &quad_points.quad[0], &quad_points.tangent_start)
        quad_points.start_set = true

    if not quad_points.end_set:
        var quad_end_pt = Point.zero()
        quad_perp_ray(s, quad, quad_points.end_t, &quad_end_pt, &quad_points.quad[2], &quad_points.tangent_end)
        quad_points.end_set = true

    let result_type = intersect_ray(s, .ctrl_pt, quad_points)
    if result_type != .quad:
        return result_type

    # project a ray from the curve to the stroke
    var ray0 = Point.zero()
    var ray1 = Point.zero()
    quad_perp_ray(s, quad, quad_points.mid_t, &ray1, &ray0, none)
    let stroke = quad_points.quad
    return stroke_close_enough(s, stroke, [ray0, ray1], quad_points)

# Given a point on the curve and its derivative, scale the derivative by the radius, and
# compute the perpendicular point and its tangent.
func set_ray_points(s: const PathStroker*, tp: Point, dxy: Point*, on_p: Point*, tangent: Point*?):
    if not dxy.set_length(s.radius):
        *dxy = Point.from_xy(s.radius, 0.0)

    let axis_flip = (f32)(i32)(i8)s.stroke_type  # go opposite ways for outer, inner
    on_p.x = tp.x + axis_flip * dxy.y
    on_p.y = tp.y - axis_flip * dxy.x

    if let t = tangent:
        *t = *dxy

# Given a quad and t, return the point on curve, its perpendicular, and the perpendicular
# tangent.
func quad_perp_ray(s: const PathStroker*, quad: const Point[], t: f32, tp: Point*, on_p: Point*, tangent: Point*?):
    *tp = eval_quad_at(quad, t)
    var dxy = eval_quad_tangent_at(quad, t)

    if dxy.is_zero():
        dxy = quad[2].sub(quad[0])

    set_ray_points(s, *tp, &dxy, on_p, tangent)

func add_degenerate_line(s: PathStroker*, quad_points: const QuadConstruct*):
    if s.stroke_type == .outer:
        s.outer.line_to(quad_points.quad[2].x, quad_points.quad[2].y)
    else:
        s.inner.line_to(quad_points.quad[2].x, quad_points.quad[2].y)

func stroke_close_enough(s: const PathStroker*, stroke: Point[3], ray: Point[2], quad_points: QuadConstruct*) -> ResultType:
    let half_t = normalized_clamped(0.5)
    let stroke_mid = eval_quad_at(stroke, half_t)
    # measure the distance from the curve to the quad-stroke midpoint, compare to radius
    if points_within_dist(ray[0], stroke_mid, s.inv_res_scale):
        # if the difference is small
        if sharp_angle(quad_points.quad):
            return .split
        return .quad

    # measure the distance to quad's bounds (quick reject)
    # an alternative : look for point in triangle
    if not pt_in_quad_bounds(stroke, ray[0], s.inv_res_scale):
        # if far, subdivide
        return .split

    # measure the curve ray distance to the quad-stroke
    var roots = new_t_values()
    let roots_len = intersect_quad_ray(ray, stroke, roots)
    if roots_len != 1:
        return .split

    let quad_pt = eval_quad_at(stroke, roots[0])
    let err = s.inv_res_scale * (1.0 - math32.abs(roots[0] - 0.5) * 2.0)
    if points_within_dist(ray[0], quad_pt, err):
        # if the difference is small, we're done
        if sharp_angle(quad_points.quad):
            return .split
        return .quad

    # otherwise, subdivide
    return .split

# Find the intersection of the stroke tangents to construct a stroke quad. Return whether the
# stroke is a degenerate (a line), a quad, or must be split. Optionally compute the quad's
# control point.
func intersect_ray(s: const PathStroker*, intersect_ray_type: IntersectRayType, quad_points: QuadConstruct*) -> ResultType:
    let start = quad_points.quad[0]
    let end = quad_points.quad[2]
    let a_len = quad_points.tangent_start
    let b_len = quad_points.tangent_end

    # Slopes match when denom goes to zero:
    #                   axLen / ayLen ==                   bxLen / byLen
    # (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
    #          byLen  * axLen         ==  ayLen          * bxLen
    #          byLen  * axLen         -   ayLen          * bxLen         ( == denom )
    let denom = a_len.cross(b_len)
    if denom == 0.0 or not math32.is_finite(denom):
        quad_points.opposite_tangents = a_len.dot(b_len) < 0.0
        return .degenerate

    quad_points.opposite_tangents = false
    let ab0 = start.sub(end)
    var numer_a = b_len.cross(ab0)
    let numer_b = a_len.cross(ab0)
    if (numer_a >= 0.0) == (numer_b >= 0.0):
        # if the control point is outside the quad ends

        # if the perpendicular distances from the quad points to the opposite tangent line
        # are small, a straight line is good enough
        let dist1 = pt_to_tangent_line(start, end, quad_points.tangent_end)
        let dist2 = pt_to_tangent_line(end, start, quad_points.tangent_start)
        if fmax(dist1, dist2) <= s.inv_res_scale_squared:
            return .degenerate

        return .split

    # check to see if the denominator is teeny relative to the numerator
    # if the offset by one will be lost, the ratio is too large
    numer_a /= denom
    let valid_divide = numer_a > numer_a - 1.0
    if valid_divide:
        if intersect_ray_type == .ctrl_pt:
            # the intersection of the tangents need not be on the tangent segment
            # so 0 <= numer_a <= 1 is not necessarily true
            quad_points.quad[1] = Point.from_xy(start.x + quad_points.tangent_start.x * numer_a, start.y + quad_points.tangent_start.y * numer_a)

        return .quad

    quad_points.opposite_tangents = a_len.dot(b_len) < 0.0

    # if the lines are parallel, straight line is good enough
    return .degenerate

# Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
func tangents_meet(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> ResultType:
    cubic_quad_ends(s, cubic, quad_points)
    return intersect_ray(s, .result_type, quad_points)

# mark: QuadConstruct =========================================================================

struct QuadConstruct:
    # The state of the quad stroke under construction.
    var quad: Point[3]  # the stroked quad parallel to the original curve
    var tangent_start: Point  # the tangent vector at quad[0]
    var tangent_end: Point  # the tangent vector at quad[2]
    var start_t: f32  # a segment of the original curve
    var mid_t: f32
    var end_t: f32
    var start_set: bool  # state to share common points across structs
    var end_set: bool
    var opposite_tangents: bool  # set if coincident tangents have opposite directions

    static func default() -> QuadConstruct:
        var q: QuadConstruct
        return q

    # return false if start and end are too close to have a unique middle
    func init_(start: f32, end: f32) -> bool:
        self.start_t = start
        self.mid_t = normalized_clamped(half(start + end))
        self.end_t = end
        self.start_set = false
        self.end_set = false
        return self.start_t < self.mid_t and self.mid_t < self.end_t

    func init_with_start(parent: const QuadConstruct*) -> bool:
        if not self.init_(parent.start_t, parent.mid_t):
            return false

        self.quad[0] = parent.quad[0]
        self.tangent_start = parent.tangent_start
        self.start_set = true
        return true

    func init_with_end(parent: const QuadConstruct*) -> bool:
        if not self.init_(parent.mid_t, parent.end_t):
            return false

        self.quad[2] = parent.quad[2]
        self.tangent_end = parent.tangent_end
        self.end_set = true
        return true