dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / src / raster / scan_aaa_path.lucb
#==============================================================================================
#
# scan_aaa_path - the analytic anti-aliasing path filler
#
# DESCRIPTION:
# Port of the last part of Skia m144 src/core/SkScan_AAAPath.cpp: the edge list
# (sorted with SkTQSort, linked through indices with a head and a tail sentinel),
# aaa_walk_convex_edges (the fast walk for convex paths, with its "smooth jump" to
# integer y), aaa_walk_edges (the general walk over non-uniform scan lines at the
# edges' ends and intersections), aaa_fill_path and SkScan::AAAFillPath, which picks
# the additive blitter. Skia's default anti-aliased path filler; Skia m144 no longer
# has the 4x4 supersampling one tiny-skia ports.
#
# Copyright (c) 2016 The Android Open Source Project
# Copyright (c) 2026 the luce-browser authors.
# SPDX-License-Identifier: BSD-3-Clause (see LICENSE-skia)
#
#==============================================================================================
# mark: The edge list =========================================================================
## An edge's sort key (compare_edges) and its index.
struct EdgeSortKey:
var upper_y: i32
var x: i32
var dx: i32
var index: u32
func edge_key_less(a: const EdgeSortKey*, b: const EdgeSortKey*) -> bool:
if a.upper_y != b.upper_y:
return a.upper_y < b.upper_y
if a.x != b.x:
return a.x < b.x
return a.dx < b.dx
func aaa_remove_edge(edges: AnalyticEdge[], edge: u32):
let prev = edges[edge].prev
let next = edges[edge].next
edges[prev].next = next
edges[next].prev = prev
func aaa_insert_edge_after(edges: AnalyticEdge[], edge: u32, after_me: u32):
edges[edge].prev = after_me
edges[edge].next = edges[after_me].next
edges[edges[after_me].next].prev = edge
edges[after_me].next = edge
func aaa_backward_insert_edge_based_on_x(edges: AnalyticEdge[], edge: u32):
let x = edges[edge].x
var prev = edges[edge].prev
while edges[prev].prev != edge_nil and edges[prev].x > x:
prev = edges[prev].prev
if edges[prev].next != edge:
aaa_remove_edge(edges, edge)
aaa_insert_edge_after(edges, edge, prev)
## Start from the right side, searching backwards for the point to begin the new edge list
## insertion, marching forwards from here.
func aaa_backward_insert_start(edges: AnalyticEdge[], prev0: u32, x: i32) -> u32:
var prev = prev0
while edges[prev].prev != edge_nil and edges[prev].x > x:
prev = edges[prev].prev
return prev
func update_next_next_y(y: i32, next_y: i32, next_next_y: i32*):
if y > next_y and y < *next_next_y:
*next_next_y = y
func check_intersection(edges: AnalyticEdge[], edge: u32, next_y: i32, next_next_y: i32*):
let prev = edges[edge].prev
if edges[prev].prev != edge_nil and edges[prev].x +% edges[prev].dx > edges[edge].x +% edges[edge].dx:
*next_next_y = next_y + (fixed_one >> analytic_default_accuracy)
func check_intersection_fwd(edges: AnalyticEdge[], edge: u32, next_y: i32, next_next_y: i32*):
let next = edges[edge].next
if edges[next].next != edge_nil and edges[edge].x +% edges[edge].dx > edges[next].x +% edges[next].dx:
*next_next_y = next_y + (fixed_one >> analytic_default_accuracy)
func aaa_insert_new_edges(edges: AnalyticEdge[], new_edge0: u32, y: i32, next_next_y: i32*):
var new_edge = new_edge0
if edges[new_edge].upper_y > y:
update_next_next_y(edges[new_edge].upper_y, y, next_next_y)
return
let prev = edges[new_edge].prev
if edges[prev].x <= edges[new_edge].x:
while edges[new_edge].upper_y <= y:
check_intersection(edges, new_edge, y, next_next_y)
update_next_next_y(edges[new_edge].lower_y, y, next_next_y)
new_edge = edges[new_edge].next
update_next_next_y(edges[new_edge].upper_y, y, next_next_y)
return
# find first x pos to insert
var start = aaa_backward_insert_start(edges, prev, edges[new_edge].x)
# insert the lot, fixing up the links as we go
while true:
let next = edges[new_edge].next
var already_linked = false
while true:
if edges[start].next == new_edge:
already_linked = true
break
let after = edges[start].next
if edges[after].x >= edges[new_edge].x:
break
start = after
if not already_linked:
aaa_remove_edge(edges, new_edge)
aaa_insert_edge_after(edges, new_edge, start)
check_intersection(edges, new_edge, y, next_next_y)
check_intersection_fwd(edges, new_edge, y, next_next_y)
update_next_next_y(edges[new_edge].lower_y, y, next_next_y)
start = new_edge
new_edge = next
if not (edges[new_edge].upper_y <= y):
break
update_next_next_y(edges[new_edge].upper_y, y, next_next_y)
## Return true if prev.x, next.x are too close in the current pixel row.
func edges_too_close(edges: AnalyticEdge[], prev: u32, next: u32, lower_y: i32) -> bool:
# When next.dx == 0, prev.x >= next.x - abs(next.dx) would be false even if prev.x and
# next.x are close and within one pixel (e.g., prev.x == 0.1, next.x == 0.9). Adding
# SLACK = 1 to the formula would guarantee it to be true if two edges prev and next are
# within one pixel.
let slack = fixed_one
# Note that even if the following test failed, the edges might still be very close to
# each other at some point within the current pixel row because of prev.dx and next.dx.
# However, to handle that case, we have to sacrafice more performance.
return next != edge_nil and prev != edge_nil and edges[next].upper_y < lower_y and edges[prev].x +% slack >= edges[next].x -% abs32(edges[next].dx)
## This function exists for the case where the previous rite edge is removed because its
## lower_y <= next_y.
func edges_too_close_rite(prev_rite: i32, ul: i32, ll: i32) -> bool:
return prev_rite > fixed_floor_to_int(ul) or prev_rite > fixed_floor_to_int(ll)
# mark: Smoothness ============================================================================
## For an edge, we consider it smooth if the Dx doesn't change much, and Dy is large enough.
## For curves that are updating, the Dx is not changing much if fQDx/fCDx and fQDy/fCDy are
## relatively large compared to fQDDx/QCDDx and fQDDy/fCDDy.
func is_smooth_enough_edge(edges: AnalyticEdge[], this_edge: u32, next_edge: u32) -> bool:
let e = &edges[this_edge]
if e.curve_count < 0:
let ddshift = e.curve_shift
return abs32(e.cdx) >> 1 >= abs32(e.cddx) >> ddshift and abs32(e.cdy) >> 1 >= abs32(e.cddy) >> ddshift and (e.cdy - (e.cddy >> ddshift)) >> e.cubic_dshift >= fixed_one # current Dy is (fCDy - (fCDDy >> ddshift)) >> dshift
elif e.curve_count > 0:
return abs32(e.qdx) >> 1 >= abs32(e.qddx) and abs32(e.qdy) >> 1 >= abs32(e.qddy) and (e.qdy - e.qddy) >> e.curve_shift >= fixed_one # current Dy is (fQDy - fQDDy) >> shift
# DDx should be small and Dy should be large
let n = &edges[next_edge]
return abs32(sat_sub32(n.dx, e.dx)) <= fixed_one and n.lower_y - n.upper_y >= fixed_one
## Check if the left_e and rite_e are changing smoothly in terms of dx. If yes, we can later
## skip the fractional y and directly jump to integer y.
func is_smooth_enough(edges: AnalyticEdge[], left_e: u32, rite_e: u32, curr_e0: u32, stop_y: i32) -> bool:
var curr_e = curr_e0
if edges[curr_e].upper_y >= left_shift(stop_y, 16):
return false # We're at the end so we won't skip anything
if edges[left_e].lower_y + fixed_one < edges[rite_e].lower_y:
return is_smooth_enough_edge(edges, left_e, curr_e) # Only left_e is changing
elif edges[left_e].lower_y > edges[rite_e].lower_y + fixed_one:
return is_smooth_enough_edge(edges, rite_e, curr_e) # Only rite_e is changing
# Now both edges are changing, find the second next edge
var next_curr_e = edges[curr_e].next
if edges[next_curr_e].upper_y >= stop_y << 16: # Check if we're at the end
return false
# Ensure that curr_e is the next left edge and next_curr_e is the next right edge. Swap
# if not.
if edges[next_curr_e].upper_x < edges[curr_e].upper_x:
let t = curr_e
curr_e = next_curr_e
next_curr_e = t
return is_smooth_enough_edge(edges, left_e, curr_e) and is_smooth_enough_edge(edges, rite_e, next_curr_e)
# mark: aaa_fill_path =========================================================================
func aaa_fill_path(path: const Path*, convex: bool, clip_rect: IRect, blitter: AdditiveBlitter*, start_y0: i32, stop_y0: i32, path_contained_in_clip: bool, is_using_mask: bool, force_rle: bool, is_inverse: bool, fill_rule: FillRule):
var start_y = start_y0
var stop_y = stop_y0
var clip: IRect? = clip_rect
if path_contained_in_clip:
clip = none
var list = build_analytic_edges(path, clip, convex) else return
defer list.release()
let count = list.len
var rect = clip_rect
if count == 0:
if is_inverse:
# Since we are in inverse-fill, our caller has already drawn above our top
# (start_y) and will draw below our bottom (stop_y). Thus we need to restrict our
# drawing to the intersection of the clip and those two limits.
if rect.top < start_y:
rect.top = start_y
if rect.bottom > stop_y:
rect.bottom = stop_y
if not rect.is_empty():
blitter.real_blit_rect(rect.left, rect.top, rect.width(), rect.height())
return
# this returns the first and last edge after they're sorted into a dlink list
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:
let e = &list.data[i]
keys[i] = EdgeSortKey(upper_y = e.upper_y, x = e.x, dx = e.dx, index = (u32)i)
sk_tqsort(keys, edge_key_less)
let head = (u32)count
let tail = (u32)count + 1
list.push(new_analytic_edge())
list.push(new_analytic_edge())
let edges = list.view()
for i in 1..<count:
edges[keys[i - 1].index].next = keys[i].index
edges[keys[i].index].prev = keys[i - 1].index
let first = keys[0].index
let last = keys[count - 1].index
edges[head].prev = edge_nil
edges[head].next = first
edges[head].upper_y = fixed_min
edges[head].lower_y = fixed_min
edges[head].x = fixed_min
edges[head].dx = 0
edges[head].dy = fixed_max
edges[head].upper_x = fixed_min
edges[first].prev = head
edges[tail].prev = last
edges[tail].next = edge_nil
edges[tail].upper_y = fixed_max
edges[tail].lower_y = fixed_max
edges[tail].x = fixed_max
edges[tail].dx = 0
edges[tail].dy = fixed_max
edges[tail].upper_x = fixed_max
edges[last].next = tail
# now edge is the head of the sorted linklist
if not path_contained_in_clip and start_y < clip_rect.top:
start_y = clip_rect.top
if not path_contained_in_clip and stop_y > clip_rect.bottom:
stop_y = clip_rect.bottom
var left_bound = int_to_fixed(rect.left)
var right_bound = int_to_fixed(rect.right)
if is_using_mask:
# If we're using mask, then we have to limit the bound within the path bounds.
# Otherwise, the edge drift may access an invalid address inside the mask.
let ir = irect_round_out(path.bounds())
left_bound = left_bound if left_bound > int_to_fixed(ir.left) else int_to_fixed(ir.left)
right_bound = right_bound if right_bound < int_to_fixed(ir.right) else int_to_fixed(ir.right)
if not is_inverse and convex and count >= 2:
aaa_walk_convex_edges(edges, head, blitter, start_y, stop_y, left_bound, right_bound, is_using_mask)
else:
# We skip intersection computation if there are many points which probably already
# give us enough fractional scan lines.
let skip_intersect = (i64)path.points.len > (i64)((stop_y - start_y) * 2)
aaa_walk_edges(edges, head, tail, fill_rule, is_inverse, blitter, start_y, stop_y, left_bound, right_bound, is_using_mask, force_rle, skip_intersect)
## SkScan::AAAFillPath: fills `path` (with its bounds rounded out, `ir`) through `blitter`,
## clipped to `clip_bounds`. `force_rle` is set when an anti-aliased clip is involved.
func aaa_fill_path_entry(path: const Path*, fill_rule: FillRule, is_inverse: bool, blitter: Blitter, ir: IRect, clip_bounds: IRect, force_rle: bool):
let contained_in_clip = clip_bounds.contains(ir)
let convex = not is_inverse and path_is_convex(path)
# The mask blitter (where we store intermediate alpha values directly in a mask, and
# then call the real blitter once in the end to blit the whole mask) is faster than the
# RLE blitter when the blit region is small enough (i.e., CanHandleRect(ir)). When
# is_inverse is true, the blit region is no longer the rectangle ir so we won't use the
# mask blitter. The caller may also use the force_rle flag to force not using the mask
# blitter. Also, when the path is a simple rect, preparing a mask and blitting it might
# have too much overhead. Hence we'll use blitFatAntiRect to avoid the mask and its
# overhead.
if AdditiveBlitter.can_handle_rect(ir) and not is_inverse and not force_rle:
# blitFatAntiRect is slower than the normal AAA flow without MaskAdditiveBlitter.
# Hence only tryBlitFatAntiRect when MaskAdditiveBlitter would have been used.
if not try_blit_fat_anti_rect(blitter, path, clip_bounds):
var additive = AdditiveBlitter.new_mask(blitter, ir, clip_bounds)
aaa_fill_path(path, convex, clip_bounds, &additive, ir.top, ir.bottom, contained_in_clip, true, force_rle, is_inverse, fill_rule)
additive.finish()
elif not is_inverse and convex:
# If the filling area is convex (i.e., path.isConvex && !isInverse), our simpler
# aaa_walk_convex_edges won't generate alphas above 255. Hence we don't need
# SafeRLEAdditiveBlitter (which is slow due to clamping). The basic RLE blitter
# RunBasedAdditiveBlitter would suffice.
var additive = AdditiveBlitter.new_rle(.run_based, blitter, ir, clip_bounds, is_inverse)
aaa_fill_path(path, convex, clip_bounds, &additive, ir.top, ir.bottom, contained_in_clip, false, force_rle, is_inverse, fill_rule)
additive.finish()
else:
# If the filling area might not be convex, the more involved aaa_walk_edges would be
# called and we have to clamp the alpha downto 255. The SafeRLEAdditiveBlitter does
# that at a cost of performance.
var additive = AdditiveBlitter.new_rle(.safe_rle, blitter, ir, clip_bounds, is_inverse)
aaa_fill_path(path, convex, clip_bounds, &additive, ir.top, ir.bottom, contained_in_clip, false, force_rle, is_inverse, fill_rule)
additive.finish()
## Check if the path is a rect and fat enough after clipping; if so, blit it.
func try_blit_fat_anti_rect(blitter: Blitter, path: const Path*, clip: IRect) -> bool:
let contour = path_is_rect_contour(path) else return false
let rect = contour.rect.intersect(clip.to_rect()) else return true # The intersection is empty. Hence consider it done.
let bounds = irect_round_out(rect)
if bounds.width() < 3:
return false # not fat
blit_fat_anti_rect(blitter, rect)
return true