dymokomi/luce-browser-render
Source of release 0.6.2
0.6.2 / src / raster / scan_aaa_rows.lucb
#==============================================================================================
#
# scan_aaa_rows - the coverage of one trapezoid row of the analytic AA scan converter
#
# DESCRIPTION:
# Port of the second part of Skia m144 src/core/SkScan_AAAPath.cpp: the alpha of
# trapezoids and triangles, compute_alpha_above_line/below_line, blit_single_alpha,
# blit_two_alphas, blit_full_alpha, blit_aaa_trapezoid_row and blit_trapezoid_row,
# which blit the coverage of the strip between two scan lines bounded by a left and a
# right edge.
#
# Our algorithm is based on horizontal scan lines (y = c_i) as the previous
# sampling-based algorithm did, but it uses non-equal-spaced scan lines: c_i is an
# integer, the y value of a line segment endpoint, or the y value of an intersection
# of two line segments. For two consecutive scan lines we analytically compute the
# coverage of this horizontal strip of our path on each pixel, which is easy because
# the strip consists of trapezoids whose top and bottom edges are the scan lines. The
# coverage of a pixel is the area of the trapezoid minus the excluded areas, which
# are triangles (or their complements): it is ground-truth coverage, and there are
# far fewer scan lines than with 16x supersampling.
#
# 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: Alphas ================================================================================
## The alpha of a trapezoid whose height is 1.
func trapezoid_to_alpha(l1: i32, l2: i32) -> AlphaU8:
let area = (l1 + l2) // 2
return (u8)(area >> 8)
## The alpha of right-triangle (a, a*b).
func partial_triangle_to_alpha(a: i32, b: i32) -> AlphaU8:
# Approximating...
# SkFixed area = SkFixedMul(a, SkFixedMul(a,b)) / 2;
let area = (a >> 11) *% (a >> 11) *% (b >> 11)
return (u8)((area >> 8) & 0xFF)
func get_partial_alpha(alpha: AlphaU8, partial_height: i32) -> AlphaU8:
return (u8)fixed_round_to_int((i32)alpha * partial_height)
func get_partial_alpha_a(alpha: AlphaU8, full_alpha: AlphaU8) -> AlphaU8:
return (u8)(((u32)alpha * (u32)full_alpha) >> 8)
## For SkFixed that's close to SK_Fixed1, we can't convert it to alpha by just shifting right.
## For example, when f = SK_Fixed1, right shifting 8 will get 256, but we need 255. This is
## rarely the problem so we'll only use this for blitting rectangles.
func fixed_to_alpha(f: i32) -> AlphaU8:
return get_partial_alpha(0xFF, f)
## Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1), approximate (very
## coarsely) the x coordinate of the intersection.
func approximate_intersection(l10: i32, r10: i32, l20: i32, r20: i32) -> i32:
var l1 = l10
var r1 = r10
var l2 = l20
var r2 = r20
if l1 > r1:
let t = l1
l1 = r1
r1 = t
if l2 > r2:
let t = l2
l2 = r2
r2 = t
let a = l1 if l1 > l2 else l2
let b = r1 if r1 < r2 else r2
return (a + b) // 2
## Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0].
func compute_alpha_above_line(alphas: AlphaU8[], l: i32, r: i32, dy: i32, full_alpha: AlphaU8):
let rr = fixed_ceil_to_int(r)
if rr == 0:
return
elif rr == 1:
alphas[0] = get_partial_alpha_a((u8)(((rr << 17) - l - r) >> 9), full_alpha)
else:
let first = fixed_one - l # horizontal edge length of the left-most triangle
let last = r - ((rr - 1) << 16) # horizontal edge length of the right-most triangle
let first_h = fixed_mul(first, dy) # vertical edge of the left-most triangle
alphas[0] = (u8)(fixed_mul(first, first_h) >> 9) # triangle alpha
var alpha16 = sat_add32(first_h, dy >> 1) # rectangle plus triangle
for i in 1..<(usize)(rr - 1):
alphas[i] = (u8)(alpha16 >> 8)
alpha16 = sat_add32(alpha16, dy)
alphas[(usize)(rr - 1)] = full_alpha -% partial_triangle_to_alpha(last, dy)
## Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0].
func compute_alpha_below_line(alphas: AlphaU8[], l: i32, r: i32, dy: i32, full_alpha: AlphaU8):
let rr = fixed_ceil_to_int(r)
if rr == 0:
return
elif rr == 1:
alphas[0] = get_partial_alpha_a(trapezoid_to_alpha(l, r), full_alpha)
else:
let first = fixed_one - l # horizontal edge length of the left-most triangle
let last = r - ((rr - 1) << 16) # horizontal edge length of the right-most triangle
let last_h = fixed_mul(last, dy) # vertical edge of the right-most triangle
alphas[(usize)(rr - 1)] = (u8)(fixed_mul(last, last_h) >> 9) # triangle alpha
var alpha16 = sat_add32(last_h, dy >> 1) # rectangle plus triangle
var i = rr - 2
while i > 0:
alphas[(usize)i] = (u8)((alpha16 >> 8) & 0xFF)
alpha16 = sat_add32(alpha16, dy)
i -= 1
alphas[0] = full_alpha -% partial_triangle_to_alpha(first, dy)
# mark: Blits =================================================================================
## Note that if full_alpha != 0xFF, we'll multiply alpha by full_alpha.
func blit_single_alpha(blitter: AdditiveBlitter*, y: i32, x: i32, alpha: AlphaU8, full_alpha: AlphaU8, mask_row: i32?, no_real_blitter: bool):
if let row = mask_row:
if full_alpha == 0xFF and not no_real_blitter: # no_real_blitter is needed for concave paths
*blitter.mask_at(row, x) = alpha
else:
safely_add_alpha(blitter.mask_at(row, x), get_partial_alpha_a(alpha, full_alpha))
else:
if full_alpha == 0xFF and not no_real_blitter:
blitter.real_blit_v(x, y, 1, alpha)
else:
blitter.blit_anti_h1(x, y, get_partial_alpha_a(alpha, full_alpha))
func blit_two_alphas(blitter: AdditiveBlitter*, y: i32, x: i32, a1: AlphaU8, a2: AlphaU8, full_alpha: AlphaU8, mask_row: i32?, no_real_blitter: bool):
if let row = mask_row:
safely_add_alpha(blitter.mask_at(row, x), a1)
safely_add_alpha(blitter.mask_at(row, x + 1), a2)
else:
if full_alpha == 0xFF and not no_real_blitter:
blitter.real_blit_anti_h2(x, y, a1, a2)
else:
blitter.blit_anti_h1(x, y, a1)
blitter.blit_anti_h1(x + 1, y, a2)
func blit_full_alpha(blitter: AdditiveBlitter*, y: i32, x: i32, len: i32, full_alpha: AlphaU8, mask_row: i32?, no_real_blitter: bool):
if let row = mask_row:
for i in 0..<len:
safely_add_alpha(blitter.mask_at(row, x + i), full_alpha)
else:
if full_alpha == 0xFF and not no_real_blitter:
blitter.real_blit_h(x, y, len)
else:
blitter.blit_anti_hw(x, y, len, full_alpha)
func blit_aaa_trapezoid_row(blitter: AdditiveBlitter*, y: i32, ul: i32, ur: i32, ll: i32, lr: i32, l_dy: i32, r_dy: i32, full_alpha: AlphaU8, mask_row: i32?, no_real_blitter: bool):
let ll_int = fixed_floor_to_int(ul)
let rr_int = fixed_ceil_to_int(lr)
let len = rr_int - ll_int
if len == 1:
let alpha = trapezoid_to_alpha(ur - ul, lr - ll)
blit_single_alpha(blitter, y, ll_int, alpha, full_alpha, mask_row, no_real_blitter)
return
let quick_len: i32 = 31
var quick_alphas: u8[64] = ---
var quick_temp: u8[64] = ---
var quick_runs: AlphaRun[64] = ---
var alphas: AlphaU8[] = quick_alphas
var temp_alphas: AlphaU8[] = quick_temp
var runs: AlphaRun[] = quick_runs
var heap = false
if len > quick_len:
alphas = (new AlphaU8[(usize)len + 1] --- in memory.heap) else trap("raster: out of memory")
temp_alphas = (new AlphaU8[(usize)len + 1] --- in memory.heap) else trap("raster: out of memory")
runs = (new AlphaRun[(usize)len + 1] --- in memory.heap) else trap("raster: out of memory")
heap = true
for i in 0..<(usize)len:
runs[i] = 1
alphas[i] = full_alpha
runs[(usize)len] = 0
let u_l = fixed_floor_to_int(ul)
let l_l = fixed_ceil_to_int(ll)
if u_l + 2 == l_l: # We only need to compute two triangles, accelerate this special case
let first = int_to_fixed(u_l) + fixed_one - ul
let second = ll - ul - first
let a1 = full_alpha -% partial_triangle_to_alpha(first, l_dy)
let a2 = partial_triangle_to_alpha(second, l_dy)
alphas[0] = alphas[0] - a1 if alphas[0] > a1 else 0
alphas[1] = alphas[1] - a2 if alphas[1] > a2 else 0
else:
compute_alpha_below_line(temp_alphas[(usize)(u_l - ll_int)..], ul - int_to_fixed(u_l), ll - int_to_fixed(u_l), l_dy, full_alpha)
for i in u_l..<l_l:
let k = (usize)(i - ll_int)
if alphas[k] > temp_alphas[k]:
alphas[k] -= temp_alphas[k]
else:
alphas[k] = 0
let u_r = fixed_floor_to_int(ur)
let l_r = fixed_ceil_to_int(lr)
if u_r + 2 == l_r: # We only need to compute two triangles, accelerate this special case
let first = int_to_fixed(u_r) + fixed_one - ur
let second = lr - ur - first
let a1 = partial_triangle_to_alpha(first, r_dy)
let a2 = full_alpha -% partial_triangle_to_alpha(second, r_dy)
let n = (usize)len
alphas[n - 2] = alphas[n - 2] - a1 if alphas[n - 2] > a1 else 0
alphas[n - 1] = alphas[n - 1] - a2 if alphas[n - 1] > a2 else 0
else:
compute_alpha_above_line(temp_alphas[(usize)(u_r - ll_int)..], ur - int_to_fixed(u_r), lr - int_to_fixed(u_r), r_dy, full_alpha)
for i in u_r..<l_r:
let k = (usize)(i - ll_int)
if alphas[k] > temp_alphas[k]:
alphas[k] -= temp_alphas[k]
else:
alphas[k] = 0
if let row = mask_row:
for i in 0..<len:
safely_add_alpha(blitter.mask_at(row, ll_int + i), alphas[(usize)i])
else:
if full_alpha == 0xFF and not no_real_blitter:
# Real blitter is faster than RunBasedAdditiveBlitter
blitter.real_blit_anti_h(ll_int, y, alphas, runs)
else:
blitter.blit_anti_h_row(ll_int, y, alphas, len)
if heap:
free(alphas) in memory.heap
free(temp_alphas) in memory.heap
free(runs) in memory.heap
func blit_trapezoid_row(blitter: AdditiveBlitter*, y: i32, ul0: i32, ur0: i32, ll0: i32, lr0: i32, l_dy: i32, r_dy: i32, full_alpha: AlphaU8, mask_row: i32?, no_real_blitter: bool):
var ul = ul0
var ur = ur0
var ll = ll0
var lr = lr0
if ul > ur:
return
# Edge crosses. Approximate it. This should only happend due to precision limit, so the
# approximation could be very coarse.
if ll > lr:
ll = approximate_intersection(ul, ll, ur, lr)
lr = ll
if ul == ur and ll == lr:
return # empty trapzoid
# We're going to use the left line ul-ll and the rite line ur-lr to exclude the area
# that's not covered by the path. Swapping (ul, ll) or (ur, lr) won't affect that
# exclusion so we'll do that for simplicity.
if ul > ll:
let t = ul
ul = ll
ll = t
if ur > lr:
let t = ur
ur = lr
lr = t
let join_left = fixed_ceil_to_fixed(ll)
let join_rite = fixed_floor_to_fixed(ur)
if join_left <= join_rite: # There's a rect from join_left to join_rite that we can blit
if ul < join_left:
let len = fixed_ceil_to_int(join_left - ul)
if len == 1:
let alpha = trapezoid_to_alpha(join_left - ul, join_left - ll)
blit_single_alpha(blitter, y, ul >> 16, alpha, full_alpha, mask_row, no_real_blitter)
elif len == 2:
let first = join_left - fixed_one - ul
let second = ll - ul - first
let a1 = partial_triangle_to_alpha(first, l_dy)
let a2 = full_alpha -% partial_triangle_to_alpha(second, l_dy)
blit_two_alphas(blitter, y, ul >> 16, a1, a2, full_alpha, mask_row, no_real_blitter)
else:
blit_aaa_trapezoid_row(blitter, y, ul, join_left, ll, join_left, l_dy, fixed_max, full_alpha, mask_row, no_real_blitter)
# SkAAClip requires that we blit from left to right. Hence we must blit
# [ul, join_left] before blitting [join_left, join_rite]
if join_left < join_rite:
blit_full_alpha(blitter, y, fixed_floor_to_int(join_left), fixed_floor_to_int(join_rite - join_left), full_alpha, mask_row, no_real_blitter)
if lr > join_rite:
let len = fixed_ceil_to_int(lr - join_rite)
if len == 1:
let alpha = trapezoid_to_alpha(ur - join_rite, lr - join_rite)
blit_single_alpha(blitter, y, join_rite >> 16, alpha, full_alpha, mask_row, no_real_blitter)
elif len == 2:
let first = join_rite + fixed_one - ur
let second = lr - ur - first
let a1 = full_alpha -% partial_triangle_to_alpha(first, r_dy)
let a2 = partial_triangle_to_alpha(second, r_dy)
blit_two_alphas(blitter, y, join_rite >> 16, a1, a2, full_alpha, mask_row, no_real_blitter)
else:
blit_aaa_trapezoid_row(blitter, y, join_rite, ur, join_rite, lr, fixed_max, r_dy, full_alpha, mask_row, no_real_blitter)
else:
blit_aaa_trapezoid_row(blitter, y, ul, ur, ll, lr, l_dy, r_dy, full_alpha, mask_row, no_real_blitter)