Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / scan_hairline.lucb

#==============================================================================================
#
#   scan_hairline - hairline (zero-width) stroking, and its non-AA line rasterizer
#
#   DESCRIPTION:
#       Port of tiny-skia scan/hairline.rs (SkScan_Hairline.cpp): stroke_path, the non-AA
#       hair_line_rgn, and the shared stroke_path_impl that caps hairlines, subdivides quads
#       and cubics into lines and hands them to a LineProc (hair_line_rgn here,
#       anti_hair_line_rgn in scan_hairline_aa.lucb).
#
#==============================================================================================

type LineProc = func(const Point[], const ScreenIntRect*?, Blitter) -> unit

let max_cubic_subdivide_level: u8 = 9
let max_quad_subdivide_level: u8 = 5

func hairline_stroke_path(path: const Path*, line_cap: LineCap, clip: ScreenIntRect, blitter: Blitter):
    stroke_path_impl(path, line_cap, clip, hair_line_rgn, blitter)

func hair_line_rgn(points: const Point[], clip: const ScreenIntRect*?, blitter0: Blitter):
    var blitter = blitter0
    let max: f32 = 32767.0
    let fixed_bounds = Rect.from_ltrb(-max, -max, max, max) else trap("unreachable")

    var clip_bounds: Rect? = none
    if let c = clip:
        clip_bounds = c.to_rect()

    for i in 0..<points.length - 1:
        var pts: Point[2]

        # We have to pre-clip the line to fit in a Fixed, so we just chop the line.
        if not line_clipper_intersect([points[i], points[i + 1]], fixed_bounds, pts):
            continue

        if let cb = clip_bounds:
            let tmp = pts
            # Perform a clip in scalar space, so we catch huge values which might be missed
            # after we convert to FDot6 (overflow).
            if not line_clipper_intersect(tmp, cb, pts):
                continue

        var x0 = fdot6_from_f32(pts[0].x)
        var y0 = fdot6_from_f32(pts[0].y)
        var x1 = fdot6_from_f32(pts[1].x)
        var y1 = fdot6_from_f32(pts[1].y)

        let dx = x1 - x0
        let dy = y1 - y0

        if math.iabs((i64)dx) > math.iabs((i64)dy):
            # mostly horizontal

            if x0 > x1:
                # we want to go left-to-right
                var t = x0
                x0 = x1
                x1 = t
                t = y0
                y0 = y1
                y1 = t

            var ix0 = fdot6_round(x0)
            let ix1 = fdot6_round(x1)
            if ix0 == ix1:
                # too short to draw
                continue

            let slope = fdot16_div(dy, dx)
            var start_y = fdot6_to_fdot16(y0) + ((slope * ((32 - x0) & 63)) >> 6)

            # In some cases, probably due to precision/rounding issues, `start_y` can become
            # equal to the image height, which will lead to panic, because we would be
            # accessing pixels outside the current memory buffer. This is tiny-skia specific
            # issue. Skia handles this part differently.
            var max_y = i32_max
            if let cb = clip_bounds:
                max_y = fdot16_from_f32(cb.bottom())

            while true:
                if ix0 >= 0 and start_y >= 0 and start_y < max_y:
                    blitter.blit_h(ix0, start_y >> 16, 1)

                start_y += slope
                ix0 += 1
                if ix0 >= ix1:
                    break
        else:
            # mostly vertical

            if y0 > y1:
                # we want to go top-to-bottom
                var t = x0
                x0 = x1
                x1 = t
                t = y0
                y0 = y1
                y1 = t

            var iy0 = fdot6_round(y0)
            let iy1 = fdot6_round(y1)
            if iy0 == iy1:
                # too short to draw
                continue

            let slope = fdot16_div(dx, dy)
            var start_x = fdot6_to_fdot16(x0) + ((slope * ((32 - y0) & 63)) >> 6)

            while true:
                if start_x >= 0 and iy0 >= 0:
                    blitter.blit_h(start_x >> 16, iy0, 1)

                start_x += slope
                iy0 += 1
                if iy0 >= iy1:
                    break

func stroke_path_impl(path: const Path*, line_cap: LineCap, clip: ScreenIntRect, line_proc: LineProc, blitter: Blitter):
    var inset_clip: IntRect? = none
    var outset_clip: IntRect? = none

    let cap_out: f32 = 1.0 if line_cap == .butt else 2.0
    let outset = path.bounds().outset(cap_out, cap_out) else return
    let ibounds = outset.round_out() else return
    if clip.to_int_rect().intersect(ibounds) == none:
        return

    if not clip.to_int_rect().contains(ibounds):
        # We now cache two scalar rects, to use for culling per-segment (e.g. cubic). Since
        # we're hairlining, the "bounds" of the control points isn't necessarily the limit of
        # where a segment can draw (it might draw up to 1 pixel beyond in aa-hairs).
        #
        # Compute the pt-bounds per segment is easy, so we do that, and then inversely adjust
        # the culling bounds so we can just do a straight compare per segment.
        #
        # insetClip is use for quick-accept (i.e. the segment is not clipped), so we inset it
        # from the clip-bounds (since segment bounds can be off by 1).
        #
        # outsetClip is used for quick-reject (i.e. the segment is entirely outside), so we
        # outset it from the clip-bounds.
        outset_clip = clip.to_int_rect().make_outset(1, 1)
        if outset_clip == none:
            return
        inset_clip = clip.to_int_rect().inset(1, 1)
        if inset_clip == none:
            return

    let clip_ptr: const ScreenIntRect*? = &clip
    var prev_verb = PathVerb.move
    var first_pt = Point.zero()
    var last_pt = Point.zero()

    var iter = path.segments()
    while true:
        # A segment starts at the path's previous point (Skia's srcPts[0]), not at last_pt,
        # which a cap may have moved.
        let start = iter.last_point
        let segment = iter.next() else break
        let verb = iter.curr_verb()
        let next_verb = iter.next_verb()
        var moved_start = start
        match segment:
            .move_to(p):
                first_pt = p
                last_pt = p
                moved_start = p
            .line_to(p):
                var points: Point[2] = [start, p]
                if line_cap != .butt:
                    extend_pts(line_cap, prev_verb, next_verb, points)

                line_proc(points, clip_ptr, blitter)
                last_pt = points[1]
                moved_start = points[0]
            .quad_to(p0, p1):
                var points: Point[3] = [start, p0, p1]
                if line_cap != .butt:
                    extend_pts(line_cap, prev_verb, next_verb, points)

                hair_quad(points, clip_ptr, inset_clip, outset_clip, compute_quad_level(points), line_proc, blitter)

                last_pt = points[2]
                moved_start = points[0]
            .conic_to(p0, p1, weight):
                var points: Point[3] = [start, p0, p1]
                if line_cap != .butt:
                    extend_pts(line_cap, prev_verb, next_verb, points)

                # how close should the quads be to the original conic?
                let quads = AutoConicToQuads.compute(points[0], points[1], points[2], weight, 0.25)
                for q in 0..<quads.len:
                    let quad = quads.quad(q)
                    hair_quad(quad, clip_ptr, inset_clip, outset_clip, compute_quad_level(quad), line_proc, blitter)

                last_pt = points[2]
                moved_start = points[0]
            .cubic_to(p0, p1, p2):
                var points: Point[4] = [start, p0, p1, p2]
                if line_cap != .butt:
                    extend_pts(line_cap, prev_verb, next_verb, points)

                hair_cubic(points, clip_ptr, inset_clip, outset_clip, line_proc, blitter)

                last_pt = points[3]
                moved_start = points[0]
            .close:
                var points: Point[2] = [last_pt, first_pt]
                if line_cap != .butt and prev_verb == .move:
                    # cap moveTo/close to match svg expectations for degenerate segments
                    extend_pts(line_cap, prev_verb, next_verb, points)
                line_proc(points, clip_ptr, blitter)
                moved_start = points[0]

        if line_cap != .butt:
            if prev_verb == .move and (verb == .line or verb == .quad or verb == .conic or verb == .cubic):
                first_pt = moved_start  # the curve moved the initial point, so close to it instead

            prev_verb = verb

func extend_pts(line_cap: LineCap, prev_verb: PathVerb, next_verb: PathVerb?, points: Point[]):
    # The area of a circle is PI*R*R. For a unit circle, R=1/2, and the cap covers half of
    # that.
    let cap_outset: f32 = 0.5 if line_cap == .square else float_pi / 8.0
    if prev_verb == .move:
        let first = points[0]
        var offset: usize = 0
        var controls = points.length - 1
        var tangent: Point
        while true:
            offset += 1
            tangent = first.sub(points[offset])

            if not tangent.is_zero():
                break

            controls -= 1
            if controls == 0:
                break

        if tangent.is_zero():
            tangent = Point.from_xy(1.0, 0.0)
            controls = points.length - 1  # If all points are equal, move all but one.
        else:
            _ = tangent.normalize()

        offset = 0
        while true:
            # If the end point and control points are equal, loop to move them in tandem.
            points[offset].x += tangent.x * cap_outset
            points[offset].y += tangent.y * cap_outset

            offset += 1
            controls += 1
            if controls >= points.length:
                break

    var at_end = true
    if let nv = next_verb:
        at_end = nv == .move or nv == .close
    if at_end:
        let last = points[points.length - 1]
        var offset = points.length - 1
        var controls = points.length - 1
        var tangent: Point
        while true:
            offset -= 1
            tangent = last.sub(points[offset])

            if not tangent.is_zero():
                break

            controls -= 1
            if controls == 0:
                break

        if tangent.is_zero():
            tangent = Point.from_xy(-1.0, 0.0)
            controls = points.length - 1
        else:
            _ = tangent.normalize()

        offset = points.length - 1
        while true:
            points[offset].x += tangent.x * cap_outset
            points[offset].y += tangent.y * cap_outset

            offset -%= 1
            controls += 1
            if controls >= points.length:
                break

func hair_quad(points: const Point[], clip0: const ScreenIntRect*?, inset_clip: IntRect?, outset_clip: IntRect?, level: u8, line_proc: LineProc, blitter: Blitter):
    var clip = clip0
    if let inset = inset_clip:
        let inset_rect = inset.to_rect()
        let outset = outset_clip else return
        let outset_rect = outset.to_rect()

        let bounds = compute_nocheck_quad_bounds(points) else return
        if not geometric_overlap(outset_rect, bounds):
            return  # nothing to do
        elif geometric_contains(inset_rect, bounds):
            clip = none

    hair_quad2(points, clip, level, line_proc, blitter)

func compute_nocheck_quad_bounds(points: const Point[]) -> Rect?:
    var min = points[0].to_f32x2()
    var max = min
    for i: usize in 1..<3:
        let pair = points[i].to_f32x2()
        min = f32x2_min(min, pair)
        max = f32x2_max(max, pair)

    return Rect.from_ltrb(min[0], min[1], max[0], max[1])

func geometric_overlap(a: Rect, b: Rect) -> bool:
    return a.left() < b.right() and b.left() < a.right() and a.top() < b.bottom() and b.top() < a.bottom()

func geometric_contains(outer: Rect, inner: Rect) -> bool:
    return inner.right() <= outer.right() and inner.left() >= outer.left() and inner.bottom() <= outer.bottom() and inner.top() >= outer.top()

func hair_quad2(points: const Point[], clip: const ScreenIntRect*?, level: u8, line_proc: LineProc, blitter: Blitter):
    let coeff = QuadCoeff.from_points(points)

    let lines: usize = (usize)1 << (usize)level

    var tmp: Point[33]
    tmp[0] = points[0]

    var t = f32x2_splat(0.0)
    let dt = f32x2_splat(1.0 / (f32)lines)
    for i in 1..<lines:
        t = t + dt
        let v = (coeff.a * t + coeff.b) * t + coeff.c
        tmp[i] = Point.from_xy(v[0], v[1])

    tmp[lines] = points[2]
    line_proc(tmp[..<lines + 1], clip, blitter)

func compute_quad_level(points: const Point[]) -> u8:
    let d = compute_int_quad_dist(points)
    # Quadratics approach the line connecting their start and end points 4x closer with each
    # subdivision, so we compute the number of subdivisions to be the minimum need to get
    # that distance to be less than a pixel.
    var level = (33 - leading_zeros(d)) >> 1
    # sanity check on level (from the previous version)
    if level > (u32)max_quad_subdivide_level:
        level = (u32)max_quad_subdivide_level

    return (u8)level

func compute_int_quad_dist(points: const Point[]) -> u32:
    # compute the vector between the control point ([1]) and the middle of the line
    # connecting the start and end ([0] and [2])
    let dx = math32.abs(half(points[0].x + points[2].x) - points[1].x)
    let dy = math32.abs(half(points[0].y + points[2].y) - points[1].y)

    # convert to whole pixel values (use ceiling to be conservative). assign to unsigned so
    # we can safely add 1/2 of the smaller and still fit in u32, since T::saturate_from()
    # returns 31 bits at most.
    let idx = (u32)saturate_from(math32.ceil(dx))
    let idy = (u32)saturate_from(math32.ceil(dy))

    # use the cheap approx for distance
    if idx > idy:
        return idx + (idy >> 1)
    return idy + (idx >> 1)

func hair_cubic(points: const Point[], clip0: const ScreenIntRect*?, inset_clip: IntRect?, outset_clip: IntRect?, line_proc: LineProc, blitter: Blitter):
    var clip = clip0
    if let inset = inset_clip:
        let inset_rect = inset.to_rect()
        let outset = outset_clip else return
        let outset_rect = outset.to_rect()

        let bounds = compute_nocheck_cubic_bounds(points) else return
        if not geometric_overlap(outset_rect, bounds):
            return  # noting to do
        elif geometric_contains(inset_rect, bounds):
            clip = none

    if quick_cubic_niceness_check(points):
        hair_cubic2(points, clip, line_proc, blitter)
    else:
        var tmp: Point[13]
        var t_values = new_t_values()

        let count = chop_cubic_at_max_curvature(points, t_values, tmp)
        for i in 0..<count:
            let offset = i * 3
            let new_points: Point[4] = [tmp[offset], tmp[offset + 1], tmp[offset + 2], tmp[offset + 3]]
            hair_cubic2(new_points, clip, line_proc, blitter)

func compute_nocheck_cubic_bounds(points: const Point[]) -> Rect?:
    var min = points[0].to_f32x2()
    var max = min
    for i: usize in 1..<4:
        let pair = points[i].to_f32x2()
        min = f32x2_min(min, pair)
        max = f32x2_max(max, pair)

    return Rect.from_ltrb(min[0], min[1], max[0], max[1])

# The off-curve points are "inside" the limits of the on-curve points.
func quick_cubic_niceness_check(points: const Point[]) -> bool:
    return lt_90(points[1], points[0], points[3]) and lt_90(points[2], points[0], points[3]) and lt_90(points[1], points[3], points[0]) and lt_90(points[2], points[3], points[0])

func lt_90(p0: Point, pivot: Point, p2: Point) -> bool:
    return p0.sub(pivot).dot(p2.sub(pivot)) >= 0.0

func hair_cubic2(points: const Point[], clip: const ScreenIntRect*?, line_proc: LineProc, blitter: Blitter):
    let lines = compute_cubic_segments(points)
    if lines == 1:
        line_proc([points[0], points[3]], clip, blitter)
        return

    let coeff = CubicCoeff.from_points(points)

    var tmp: Point[513]

    let dt = f32x2_splat(1.0 / (f32)lines)
    var t = f32x2_splat(0.0)

    tmp[0] = points[0]
    for i in 1..<lines:
        t = t + dt
        tmp[i] = Point.from_f32x2(((coeff.a * t + coeff.b) * t + coeff.c) * t + coeff.d)

    var all_finite = true
    for p in tmp:
        if not p.is_finite():
            all_finite = false
            break
    if all_finite:
        tmp[lines] = points[3]
        line_proc(tmp[..<lines + 1], clip, blitter)

# else some point(s) are non-finite, so don't draw

func compute_cubic_segments(points: const Point[]) -> usize:
    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 one_third = f32x2_splat(1.0 / 3.0)
    let two_third = f32x2_splat(2.0 / 3.0)

    let p13 = one_third * p3 + two_third * p0
    let p23 = one_third * p0 + two_third * p3

    let diff = f32x2_max_component(f32x2_max(f32x2_abs(p1 - p13), f32x2_abs(p2 - p23)))
    var tol: f32 = 1.0 / 8.0

    for i in 0..<max_cubic_subdivide_level:
        if diff < tol:
            return (usize)1 << (usize)i

        tol *= 4.0

    return (usize)1 << (usize)max_cubic_subdivide_level