dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / 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