dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / src / raster / edge.lucb
#==============================================================================================
#
# edge - scan converter edges: lines, and forward-differenced quads and cubics
#
# DESCRIPTION:
# Port of tiny-skia edge.rs: LineEdge, QuadraticEdge, CubicEdge and Edge. Rust's
# `enum Edge` whose variants all deref to their LineEdge is a tagged union here: the
# three payloads begin with their LineEdge, so `edge.data.line` is the line of every
# kind (Rust's Deref). The linked-list indices `prev`/`next` (Rust's Option<u32>) use
# `edge_none` for None.
#
#==============================================================================================
let max_coeff_shift: i32 = 6
## Rust's `None` for an edge index.
let edge_none: u32 = 0xFFFFFFFF
enum EdgeKind as u8:
line = 0
quadratic = 1
cubic = 2
union EdgeData:
line: LineEdge
quad: QuadraticEdge
cubic: CubicEdge
struct Edge:
var kind: EdgeKind
var data: EdgeData
static func from_line(line: LineEdge) -> Edge:
var e = Edge(kind = .line)
e.data.line = line
return e
static func from_quad(quad: QuadraticEdge) -> Edge:
var e = Edge(kind = .quadratic)
e.data.quad = quad
return e
static func from_cubic(cubic: CubicEdge) -> Edge:
var e = Edge(kind = .cubic)
e.data.cubic = cubic
return e
struct LineEdge:
# Imitate a linked list.
var prev: u32
var next: u32
var x: FDot16
var dx: FDot16
var first_y: i32
var last_y: i32
var winding: i8 # 1 or -1
static func new_(p0: Point, p1: Point, shift: i32) -> LineEdge?:
let scale = (f32)(1 << (shift + 6))
var x0 = (i32)(p0.x * scale)
var y0 = (i32)(p0.y * scale)
var x1 = (i32)(p1.x * scale)
var y1 = (i32)(p1.y * scale)
var winding: i8 = 1
if y0 > y1:
let tx = x0
x0 = x1
x1 = tx
let ty = y0
y0 = y1
y1 = ty
winding = -1
let top = fdot6_round(y0)
let bottom = fdot6_round(y1)
# are we a zero-height line?
if top == bottom:
return none
let slope = fdot6_div(x1 - x0, y1 - y0)
let dy = compute_dy(top, y0)
return LineEdge(next = edge_none, prev = edge_none, x = fdot6_to_fdot16(x0 + fdot16_mul(slope, dy)), dx = slope, first_y = top, last_y = bottom - 1, winding = winding)
func is_vertical() -> bool:
return self.dx == 0
func update(x00: FDot16, y00: FDot16, x10: FDot16, y10: FDot16) -> bool:
let y0 = y00 >> 10
let y1 = y10 >> 10
let top = fdot6_round(y0)
let bottom = fdot6_round(y1)
# are we a zero-height line?
if top == bottom:
return false
let x0 = x00 >> 10
let x1 = x10 >> 10
let slope = fdot6_div(x1 - x0, y1 - y0)
let dy = compute_dy(top, y0)
self.x = fdot6_to_fdot16(x0 + fdot16_mul(slope, dy))
self.dx = slope
self.first_y = top
self.last_y = bottom - 1
return true
struct QuadraticEdge:
var line: LineEdge
var curve_count: i8
var curve_shift: u8 # applied to all dx/ddx/dddx
var qx: FDot16
var qy: FDot16
var qdx: FDot16
var qdy: FDot16
var qddx: FDot16
var qddy: FDot16
var q_last_x: FDot16
var q_last_y: FDot16
static func new_(points: const Point[], shift: i32) -> QuadraticEdge?:
var quad = QuadraticEdge.new2(points, shift) else return none
if quad.update():
return quad
return none
static func new2(points: const Point[], shift0: i32) -> QuadraticEdge?:
var shift = shift0
let scale = (f32)(1 << (shift + 6))
var x0 = (i32)(points[0].x * scale)
var y0 = (i32)(points[0].y * scale)
let x1 = (i32)(points[1].x * scale)
let y1 = (i32)(points[1].y * scale)
var x2 = (i32)(points[2].x * scale)
var y2 = (i32)(points[2].y * scale)
var winding: i8 = 1
if y0 > y2:
let tx = x0
x0 = x2
x2 = tx
let ty = y0
y0 = y2
y2 = ty
winding = -1
let top = fdot6_round(y0)
let bottom = fdot6_round(y2)
# are we a zero-height quad (line)?
if top == bottom:
return none
# compute number of steps needed (1 << shift)
let dx = (left_shift(x1, 1) - x0 - x2) >> 2
let dy = (left_shift(y1, 1) - y0 - y2) >> 2
# This is a little confusing: before this line, shift is the scale up factor for AA;
# after this line, shift is the fCurveShift.
shift = diff_to_shift(dx, dy, shift)
# need at least 1 subdivision for our bias trick
if shift == 0:
shift = 1
elif shift > max_coeff_shift:
shift = max_coeff_shift
let curve_count = (i8)(1 << shift)
# We want to reformulate into polynomial form, to make it clear how we should
# forward-difference.
#
# p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
#
# A = p0 - 2p1 + p2
# B = 2(p1 - p0)
# C = p0
#
# Our caller must have constrained our inputs (p0..p2) to all fit into 16.16.
# However, as seen above, we sometimes compute values that can be larger (e.g.
# B = 2*(p1 - p0)). To guard against overflow, we will store A and B at 1/2 of their
# actual value, and just apply a 2x scale during application in updateQuadratic().
# Hence we store (shift - 1) in curve_shift.
let curve_shift = (u8)(shift - 1)
var a = fdot6_to_fixed_div2(x0 - x1 - x1 + x2) # 1/2 the real value
var b = fdot6_to_fdot16(x1 - x0) # 1/2 the real value
let qx = fdot6_to_fdot16(x0)
let qdx = b + (a >> shift) # biased by shift
let qddx = a >> (shift - 1) # biased by shift
a = fdot6_to_fixed_div2(y0 - y1 - y1 + y2) # 1/2 the real value
b = fdot6_to_fdot16(y1 - y0) # 1/2 the real value
let qy = fdot6_to_fdot16(y0)
let qdy = b + (a >> shift) # biased by shift
let qddy = a >> (shift - 1) # biased by shift
let q_last_x = fdot6_to_fdot16(x2)
let q_last_y = fdot6_to_fdot16(y2)
return QuadraticEdge(
line = LineEdge(next = edge_none, prev = edge_none, x = 0, dx = 0, first_y = 0, last_y = 0, winding = winding),
curve_count = curve_count,
curve_shift = curve_shift,
qx = qx,
qy = qy,
qdx = qdx,
qdy = qdy,
qddx = qddx,
qddy = qddy,
q_last_x = q_last_x,
q_last_y = q_last_y,
)
func update() -> bool:
var success: bool
var count = self.curve_count
var oldx = self.qx
var oldy = self.qy
var dx = self.qdx
var dy = self.qdy
var newx: FDot16
var newy: FDot16
let shift = (i32)self.curve_shift
while true:
count -= 1
if count > 0:
newx = oldx + (dx >> shift)
dx += self.qddx
newy = oldy + (dy >> shift)
dy += self.qddy
else:
# last segment
newx = self.q_last_x
newy = self.q_last_y
success = self.line.update(oldx, oldy, newx, newy)
oldx = newx
oldy = newy
if count == 0 or success:
break
self.qx = newx
self.qy = newy
self.qdx = dx
self.qdy = dy
self.curve_count = count
return success
struct CubicEdge:
var line: LineEdge
var curve_count: i8
var curve_shift: u8 # applied to all dx/ddx/dddx except for dshift exception
var dshift: u8 # applied to cdx and cdy
var cx: FDot16
var cy: FDot16
var cdx: FDot16
var cdy: FDot16
var cddx: FDot16
var cddy: FDot16
var cdddx: FDot16
var cdddy: FDot16
var c_last_x: FDot16
var c_last_y: FDot16
static func new_(points: const Point[], shift: i32) -> CubicEdge?:
var cubic = CubicEdge.new2(points, shift, true) else return none
if cubic.update():
return cubic
return none
static func new2(points: const Point[], shift0: i32, sort_y: bool) -> CubicEdge?:
var shift = shift0
let scale = (f32)(1 << (shift + 6))
var x0 = (i32)(points[0].x * scale)
var y0 = (i32)(points[0].y * scale)
var x1 = (i32)(points[1].x * scale)
var y1 = (i32)(points[1].y * scale)
var x2 = (i32)(points[2].x * scale)
var y2 = (i32)(points[2].y * scale)
var x3 = (i32)(points[3].x * scale)
var y3 = (i32)(points[3].y * scale)
var winding: i8 = 1
if sort_y and y0 > y3:
var t = x0
x0 = x3
x3 = t
t = x1
x1 = x2
x2 = t
t = y0
y0 = y3
y3 = t
t = y1
y1 = y2
y2 = t
winding = -1
let top = fdot6_round(y0)
let bot = fdot6_round(y3)
# are we a zero-height cubic (line)?
if sort_y and top == bot:
return none
# compute number of steps needed (1 << shift)
# Can't use (center of curve - center of baseline), since center-of-curve need not
# be the max delta from the baseline (it could even be coincident) so we try just
# looking at the two off-curve points
let dx = cubic_delta_from_line(x0, x1, x2, x3)
let dy = cubic_delta_from_line(y0, y1, y2, y3)
# add 1 (by observation)
shift = diff_to_shift(dx, dy, 2) + 1
# need at least 1 subdivision for our bias trick
if shift > max_coeff_shift:
shift = max_coeff_shift
# Since our in coming data is initially shifted down by 10 (or 8 in antialias). That
# means the most we can shift up is 8. However, we compute coefficients with a 3*, so
# the safest upshift is really 6
var up_shift: i32 = 6 # largest safe value
var down_shift = shift + up_shift - 10
if down_shift < 0:
down_shift = 0
up_shift = 10 - shift
let curve_count = (i8)left_shift(-1, shift)
let curve_shift = (u8)shift
let dshift = (u8)down_shift
var b = fdot6_up_shift(3 * (x1 - x0), up_shift)
var c = fdot6_up_shift(3 * (x0 - x1 - x1 + x2), up_shift)
var d = fdot6_up_shift(x3 + 3 * (x1 - x2) - x0, up_shift)
let cx = fdot6_to_fdot16(x0)
let cdx = b + (c >> shift) + (d >> (2 * shift)) # biased by shift
let cddx = 2 * c + ((3 * d) >> (shift - 1)) # biased by 2*shift
let cdddx = (3 * d) >> (shift - 1) # biased by 2*shift
b = fdot6_up_shift(3 * (y1 - y0), up_shift)
c = fdot6_up_shift(3 * (y0 - y1 - y1 + y2), up_shift)
d = fdot6_up_shift(y3 + 3 * (y1 - y2) - y0, up_shift)
let cy = fdot6_to_fdot16(y0)
let cdy = b + (c >> shift) + (d >> (2 * shift)) # biased by shift
let cddy = 2 * c + ((3 * d) >> (shift - 1)) # biased by 2*shift
let cdddy = (3 * d) >> (shift - 1) # biased by 2*shift
let c_last_x = fdot6_to_fdot16(x3)
let c_last_y = fdot6_to_fdot16(y3)
return CubicEdge(
line = LineEdge(next = edge_none, prev = edge_none, x = 0, dx = 0, first_y = 0, last_y = 0, winding = winding),
curve_count = curve_count,
curve_shift = curve_shift,
dshift = dshift,
cx = cx,
cy = cy,
cdx = cdx,
cdy = cdy,
cddx = cddx,
cddy = cddy,
cdddx = cdddx,
cdddy = cdddy,
c_last_x = c_last_x,
c_last_y = c_last_y,
)
func update() -> bool:
var success: bool
var count = self.curve_count
var oldx = self.cx
var oldy = self.cy
var newx: FDot16
var newy: FDot16
let ddshift = (i32)self.curve_shift
let dshift = (i32)self.dshift
while true:
count += 1
if count < 0:
newx = oldx + (self.cdx >> dshift)
self.cdx += self.cddx >> ddshift
self.cddx += self.cdddx
newy = oldy + (self.cdy >> dshift)
self.cdy += self.cddy >> ddshift
self.cddy += self.cdddy
else:
# last segment
newx = self.c_last_x
newy = self.c_last_y
# we want to say debug_assert(oldy <= newy), but our finite fixedpoint doesn't
# always achieve that, so we have to explicitly pin it here.
if newy < oldy:
newy = oldy
success = self.line.update(oldx, oldy, newx, newy)
oldx = newx
oldy = newy
if count == 0 or success:
break
self.cx = newx
self.cy = newy
self.curve_count = count
return success
# This correctly favors the lower-pixel when y0 is on a 1/2 pixel boundary
func compute_dy(top: FDot6, y0: FDot6) -> FDot6:
return left_shift(top, 6) + 32 - y0
func diff_to_shift(dx: FDot6, dy: FDot6, shift_aa: i32) -> i32:
# cheap calc of distance from center of p0-p2 to the center of the curve
var dist = cheap_distance(dx, dy)
# shift down dist (it is currently in dot6)
# down by 3 should give us 1/8 pixel accuracy (assuming our dist is accurate...)
# this is chosen by heuristic: make it as big as possible (to minimize segments)
# ... but small enough so that our curves still look smooth
# When shift > 0, we're using AA and everything is scaled up so we can lower the
# accuracy.
dist = (dist + (1 << (2 + shift_aa))) >> (3 + shift_aa)
# each subdivision (shift value) cuts this dist (error) by 1/4
return (32 - (i32)leading_zeros((u32)dist)) >> 1
func cheap_distance(dx0: FDot6, dy0: FDot6) -> FDot6:
let dx = (i32)math.iabs((i64)dx0)
let dy = (i32)math.iabs((i64)dy0)
# return max + min/2
if dx > dy:
return dx + (dy >> 1)
return dy + (dx >> 1)
# In LineEdge::new, QuadraticEdge::new, CubicEdge::new, the first thing we do is to convert
# the points into FDot6. This is modulated by the shift parameter, which will either be 0,
# or something like 2 for antialiasing.
#
# In the float case, we want to turn the float into .6 by saying pt * 64, or pt * 256 for
# antialiasing. This is implemented as 1 << (shift + 6).
#
# In the fixed case, we want to turn the fixed into .6 by saying pt >> 10, or pt >> 8 for
# antialiasing. This is implemented as pt >> (10 - shift).
func fdot6_to_fixed_div2(value: FDot6) -> FDot16:
# we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw away data in
# value, so just perform a modify up-shift
return left_shift(value, 16 - 6 - 1)
func fdot6_up_shift(x: FDot6, up_shift: i32) -> i32:
return left_shift(x, up_shift)
# f(1/3) = (8a + 12b + 6c + d) / 27
# f(2/3) = (a + 6b + 12c + 8d) / 27
#
# f(1/3)-b = (8a - 15b + 6c + d) / 27
# f(2/3)-c = (a + 6b - 15c + 8d) / 27
#
# use 16/512 to approximate 1/27
func cubic_delta_from_line(a: FDot6, b: FDot6, c: FDot6, d: FDot6) -> FDot6:
# since our parameters may be negative, we don't use <<
let one_third = ((a * 8 - b * 15 + 6 * c + d) * 19) >> 9
let two_third = ((a + 6 * b - c * 15 + d * 8) * 19) >> 9
let x = (i32)math.iabs((i64)one_third)
let y = (i32)math.iabs((i64)two_third)
return x if x > y else y