Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / 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