Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / scan_path.lucb

#==============================================================================================
#
#   scan_path - the non-AA path scan converter
#
#   DESCRIPTION:
#       Port of tiny-skia scan/path.rs (conservative rounding, fill_path_impl, and the
#       active edge list walk of SkScan_Path.cpp: walk_edges, insert/remove/backward-insert
#       of edges), brought up to Skia m144's sk_fill_path: edges sorted with SkTQSort,
#       edges culled to the right only for concave paths, and walk_simple_edges for convex
#       ones. The entry point with a clip is raster_fill_path (scan_raster_clip.lucb).
#
#==============================================================================================

# mark: scan/path.rs ==========================================================================

# Conservative rounding function, which effectively nudges the int-rect to be slightly
# larger than Rect::round() might have produced. This is a safety-net for the scan-converter,
# which inspects the returned int-rect, and may disable clipping (for speed) if it thinks all
# of the edges will fit inside the clip's bounds. The scan-converter introduces slight
# numeric errors due to accumulated += of the slope, so this function is used to return a
# conservatively large int-bounds, and thus we will only disable clipping if we're sure the
# edges will stay in-bounds.
func conservative_round_to_int(src: Rect) -> IntRect?:
    # We must use `from_ltrb`, otherwise rounding will be incorrect.
    return IntRect.from_ltrb(round_down_to_int(src.left()), round_down_to_int(src.top()), round_up_to_int(src.right()), round_up_to_int(src.bottom()))

# Bias used for conservative rounding of float rects to int rects, to nudge the irects a
# little larger, so we don't "think" a path's bounds are inside a clip, when (due to numeric
# drift in the scan-converter) we might walk beyond the predicted limits.
#
# This value has been determined trial and error: pick the smallest value (after the 0.5)
# that fixes any problematic cases (e.g. crbug.com/844457)
# NOTE: cubics appear to be the main reason for needing this slop. If we could (perhaps)
# have a more accurate walker for cubics, we may be able to reduce this fudge factor.
let conservative_round_bias: f64 = 0.5 + 1.5 / 64.0

# Round the value down. This is used to round the top and left of a rectangle, and
# corresponds to the way the scan converter treats the top and left edges. It has a slight
# bias to make the "rounded" int smaller than a normal round, to create a more conservative
# int-bounds (larger) from a float rect.
func round_down_to_int(x: f32) -> i32:
    var xx = (f64)x
    xx -= conservative_round_bias
    return saturate_from64(math.ceil(xx))

# Round the value up. This is used to round the right and bottom of a rectangle. It has a
# slight bias to make the "rounded" int smaller than a normal round, to create a more
# conservative int-bounds (larger) from a float rect.
func round_up_to_int(x: f32) -> i32:
    var xx = (f64)x
    xx += conservative_round_bias
    return saturate_from64(math.floor(xx))

## compare_edges of SkScan_Path.cpp, on an edge's sort key.
func basic_edge_key_less(a: const EdgeSortKey*, b: const EdgeSortKey*) -> bool:
    if a.upper_y != b.upper_y:
        return a.upper_y < b.upper_y
    return a.x < b.x

## sk_fill_path: fills `path` between rows `start_y0` and `stop_y0`, clipped to `clip_rect`
## unless the path is contained in it.
func scan_fill_path_impl(path: const Path*, fill_rule: FillRule, clip_rect: ScreenIntRect, start_y0: i32, stop_y0: i32, path_contained_in_clip: bool, blitter: Blitter):
    var start_y = start_y0
    var stop_y = stop_y0
    let shifted_clip = ShiftedIntRect.new_(clip_rect, 0) else return
    let convex = path_is_convex(path)

    let clip: const ShiftedIntRect*? = none if path_contained_in_clip else &shifted_clip
    var built = BasicEdgeBuilder.build_edges(path, clip, 0, not convex) else return  # no edges to render, just return
    defer built.release()
    let count = built.len

    # SkTQSort, as Skia sorts its edge list (the sort is not stable).
    let keys = (new EdgeSortKey[count] --- in memory.heap) else trap("raster: out of memory")
    defer free(keys) in memory.heap
    for i in 0..<count:
        keys[i] = EdgeSortKey(upper_y = built.data[i].data.line.first_y, x = built.data[i].data.line.x, dx = 0, index = (u32)i)
    sk_tqsort(keys, basic_edge_key_less)

    # The sorted edges with a head (index 0) and a tail (index count + 1).
    var edges: Vec[Edge]
    defer edges.release()
    edges.reserve(count + 2)
    var head_line: LineEdge
    head_line.prev = edge_none
    head_line.next = 1
    head_line.x = i32_min
    head_line.first_y = i32_min
    edges.push(Edge.from_line(head_line))
    for i in 0..<count:
        var e = built.data[(usize)keys[i].index]
        e.data.line.prev = (u32)i
        e.data.line.next = (u32)i + 2
        edges.push(e)
    var tail_line: LineEdge
    tail_line.prev = (u32)count
    tail_line.next = edge_none
    tail_line.first_y = i32_max
    edges.push(Edge.from_line(tail_line))

    let top = (i32)clip_rect.y()
    if not path_contained_in_clip and start_y < top:
        start_y = top

    let bottom = (i32)clip_rect.bottom()
    if not path_contained_in_clip and stop_y > bottom:
        stop_y = bottom

    if start_y < 0 or stop_y < 0:
        return

    # count >= 2 is required as the convex walker does not handle missing right edges
    if convex and count >= 2:
        walk_simple_edges(edges.view(), blitter, start_y, stop_y)
    else:
        walk_edges(fill_rule, (u32)start_y, (u32)stop_y, clip_rect.right(), edges.view(), blitter)

## update_edge: returns true if we're NOT done with this edge.
func update_edge(edge: Edge*, last_y: i32) -> bool:
    if last_y != edge.data.line.last_y:
        return true
    match edge.kind:
        .quadratic:
            return edge.data.quad.curve_count > 0 and edge.data.quad.update()
        .cubic:
            return edge.data.cubic.curve_count < 0 and edge.data.cubic.update()
        _:
            return false

## walk_simple_edges: needs Y to only change once (looser than convex in X).
func walk_simple_edges(edges: Edge[], blitter0: Blitter, start_y: i32, stop_y: i32):
    var blitter = blitter0
    var left_e = (usize)edges[0].data.line.next
    var rite_e = (usize)edges[left_e].data.line.next
    var curr_e = (usize)edges[rite_e].data.line.next

    # our edge choppers for curves can result in the initial edges not lining up, so we
    # take the max.
    let lt = edges[left_e].data.line.first_y
    let rt = edges[rite_e].data.line.first_y
    var local_top = lt if lt > rt else rt
    if local_top < start_y:
        return

    while local_top < stop_y:
        let lb = edges[left_e].data.line.last_y
        let rb = edges[rite_e].data.line.last_y
        var local_bot = lb if lb < rb else rb
        if local_bot > stop_y - 1:
            local_bot = stop_y - 1
        if local_top > local_bot:
            return

        var left = edges[left_e].data.line.x
        let d_left = edges[left_e].data.line.dx
        var rite = edges[rite_e].data.line.x
        let d_rite = edges[rite_e].data.line.dx
        var count = local_bot - local_top

        if d_left == 0 and d_rite == 0:
            var l = fdot16_round_to_i32(left)
            var r = fdot16_round_to_i32(rite)
            if l > r:
                let t = l
                l = r
                r = t
            if l < r:
                count += 1
                blitter.blit_rect(l, local_top, r - l, count)
            local_top = local_bot + 1
        else:
            while true:
                var l = fdot16_round_to_i32(left)
                var r = fdot16_round_to_i32(rite)
                if l > r:
                    let t = l
                    l = r
                    r = t
                if l < r:
                    blitter.blit_h(l, local_top, r - l)
                # Either/both of these might overflow, since we perform this step even if
                # (later) we determine that we are done with the edge, and so the computed
                # left or rite edge will not be used (see update_edge).
                left = left +% d_left
                rite = rite +% d_rite
                local_top += 1
                count -= 1
                if count < 0:
                    break

        edges[left_e].data.line.x = left
        edges[rite_e].data.line.x = rite

        if not update_edge(&edges[left_e], local_bot):
            if edges[curr_e].data.line.first_y >= stop_y:
                return  # we're done
            left_e = curr_e
            curr_e = (usize)edges[curr_e].data.line.next
            if edges[left_e].data.line.first_y != local_top:
                return
        if not update_edge(&edges[rite_e], local_bot):
            if edges[curr_e].data.line.first_y >= stop_y:
                return  # we're done
            rite_e = curr_e
            curr_e = (usize)edges[curr_e].data.line.next
            if edges[rite_e].data.line.first_y != local_top:
                return

# TODO: simplify!
func walk_edges(fill_rule: FillRule, start_y: u32, stop_y: u32, right_clip: u32, edges: Edge[], blitter0: Blitter):
    var blitter = blitter0
    var curr_y = start_y
    let winding_mask: i32 = 1 if fill_rule == .even_odd else -1

    while true:
        var w: i32 = 0
        var left: u32 = 0
        var prev_x = edges[0].data.line.x

        var curr_idx = (usize)edges[0].data.line.next
        while edges[curr_idx].data.line.first_y <= (i32)curr_y:
            let x = (u32)fdot16_round_to_i32(edges[curr_idx].data.line.x)  # TODO: check

            if (w & winding_mask) == 0:
                # we're starting interval
                left = x

            w += (i32)edges[curr_idx].data.line.winding

            if (w & winding_mask) == 0:
                # we finished an interval
                let width = x - left
                if width != 0:
                    blitter.blit_h((i32)left, (i32)curr_y, (i32)width)

            let next_idx = edges[curr_idx].data.line.next
            var new_x: FDot16

            if edges[curr_idx].data.line.last_y == (i32)curr_y:
                # are we done with this edge?
                match edges[curr_idx].kind:
                    .line:
                        remove_edge(curr_idx, edges)
                    .quadratic:
                        if edges[curr_idx].data.quad.curve_count > 0 and edges[curr_idx].data.quad.update():
                            new_x = edges[curr_idx].data.quad.line.x

                            if new_x < prev_x:
                                # ripple current edge backwards until it is x-sorted
                                backward_insert_edge_based_on_x(curr_idx, edges)
                            else:
                                prev_x = new_x
                        else:
                            remove_edge(curr_idx, edges)
                    .cubic:
                        if edges[curr_idx].data.cubic.curve_count < 0 and edges[curr_idx].data.cubic.update():
                            new_x = edges[curr_idx].data.cubic.line.x

                            if new_x < prev_x:
                                # ripple current edge backwards until it is x-sorted
                                backward_insert_edge_based_on_x(curr_idx, edges)
                            else:
                                prev_x = new_x
                        else:
                            remove_edge(curr_idx, edges)
                    _:
                        trap("unreachable")
            else:
                new_x = edges[curr_idx].data.line.x + edges[curr_idx].data.line.dx
                edges[curr_idx].data.line.x = new_x

                if new_x < prev_x:
                    # ripple current edge backwards until it is x-sorted
                    backward_insert_edge_based_on_x(curr_idx, edges)
                else:
                    prev_x = new_x

            curr_idx = (usize)next_idx

        if (w & winding_mask) != 0:
            # was our right-edge culled away?
            let width = right_clip - left
            if width != 0:
                blitter.blit_h((i32)left, (i32)curr_y, (i32)width)

        curr_y += 1
        if curr_y >= stop_y:
            break

        # now current edge points to the first edge with a Yint larger than curr_y
        insert_new_edges(curr_idx, (i32)curr_y, edges)

func remove_edge(curr_idx: usize, edges: Edge[]):
    let prev = edges[curr_idx].data.line.prev
    let next = edges[curr_idx].data.line.next

    edges[(usize)prev].data.line.next = next
    edges[(usize)next].data.line.prev = prev

func backward_insert_edge_based_on_x(curr_idx: usize, edges: Edge[]):
    let x = edges[curr_idx].data.line.x
    var prev_idx = (usize)edges[curr_idx].data.line.prev
    while prev_idx != 0:
        if edges[prev_idx].data.line.x > x:
            prev_idx = (usize)edges[prev_idx].data.line.prev
        else:
            break

    let next_idx = (usize)edges[prev_idx].data.line.next
    if next_idx != curr_idx:
        remove_edge(curr_idx, edges)
        insert_edge_after(curr_idx, prev_idx, edges)

func insert_edge_after(curr_idx: usize, after_idx: usize, edges: Edge[]):
    edges[curr_idx].data.line.prev = (u32)after_idx
    edges[curr_idx].data.line.next = edges[after_idx].data.line.next

    let after_next_idx = (usize)edges[after_idx].data.line.next
    edges[after_next_idx].data.line.prev = (u32)curr_idx
    edges[after_idx].data.line.next = (u32)curr_idx

# Start from the right side, searching backwards for the point to begin the new edge list
# insertion, marching forwards from here. The implementation could have started from the
# left of the prior insertion, and search to the right, or with some additional caching,
# binary search the starting point. More work could be done to determine optimal new edge
# insertion.
func backward_insert_start(prev_idx0: usize, x: FDot16, edges: const Edge[]) -> usize:
    var prev_idx = prev_idx0
    while edges[prev_idx].data.line.prev != edge_none:
        prev_idx = (usize)edges[prev_idx].data.line.prev
        if edges[prev_idx].data.line.x <= x:
            break

    return prev_idx

func insert_new_edges(new_idx0: usize, curr_y: i32, edges: Edge[]):
    var new_idx = new_idx0
    if edges[new_idx].data.line.first_y != curr_y:
        return

    let prev_idx = (usize)edges[new_idx].data.line.prev
    if edges[prev_idx].data.line.x <= edges[new_idx].data.line.x:
        return

    # find first x pos to insert
    var start_idx = backward_insert_start(prev_idx, edges[new_idx].data.line.x, edges)
    # insert the lot, fixing up the links as we go
    while true:
        let next_idx = (usize)edges[new_idx].data.line.next
        var keep_edge = false
        while true:
            let after_idx = (usize)edges[start_idx].data.line.next
            if after_idx == new_idx:
                keep_edge = true
                break

            if edges[after_idx].data.line.x >= edges[new_idx].data.line.x:
                break

            start_idx = after_idx

        if not keep_edge:
            remove_edge(new_idx, edges)
            insert_edge_after(new_idx, start_idx, edges)

        start_idx = new_idx
        new_idx = next_idx

        if edges[new_idx].data.line.first_y != curr_y:
            break