Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / edge_clipper.lucb

#==============================================================================================
#
#   edge_clipper - clipping path edges against the clip rectangle
#
#   DESCRIPTION:
#       Port of tiny-skia edge_clipper.rs: EdgeClipper (clip_line, clip_quad and
#       clip_mono_quad, clip_cubic and clip_mono_cubic, with vertical lines along the clip's
#       left/right edges), EdgeClipperIter, and the monotonic chopping helpers. Rust's
#       ArrayVec<PathEdge, 18> is ClippedEdges: a fixed array and a length.
#
#==============================================================================================

let max_verbs: usize = 18

struct ClippedEdges:
    var edges: PathEdge[18]
    var len: usize

    static func empty() -> ClippedEdges:
        var c: ClippedEdges = ---
        c.len = 0
        return c

    func push(edge: PathEdge):
        if self.len == max_verbs:
            trap("raster: too many clipped edges")
        self.edges[self.len] = edge
        self.len += 1

struct EdgeClipper:
    var clip: Rect
    var can_cull_to_the_right: bool
    var edges: ClippedEdges

    static func new_(clip: Rect, can_cull_to_the_right: bool) -> EdgeClipper:
        return EdgeClipper(clip = clip, can_cull_to_the_right = can_cull_to_the_right, edges = ClippedEdges.empty())

    func clip_line(p0: Point, p1: Point) -> ClippedEdges?:
        var points: Point[4]
        let count = line_clipper_clip([p0, p1], self.clip, self.can_cull_to_the_right, points)
        if count != 0:
            for i in 0..<count - 1:
                self.push_line(points[i], points[i + 1])

        if self.edges.len == 0:
            return none
        return self.edges

    func push_line(p0: Point, p1: Point):
        self.edges.push(.line_to(p0 = p0, p1 = p1))

    func push_vline(x: f32, y00: f32, y10: f32, reverse: bool):
        var y0 = y00
        var y1 = y10
        if reverse:
            let t = y0
            y0 = y1
            y1 = t
        self.edges.push(.line_to(p0 = Point.from_xy(x, y0), p1 = Point.from_xy(x, y1)))

    func clip_quad(p0: Point, p1: Point, p2: Point) -> ClippedEdges?:
        let pts: Point[3] = [p0, p1, p2]
        let bounds = Rect.from_points(pts) else return none

        if not quick_reject(bounds, self.clip):
            var mono_y: Point[5]
            let count_y = chop_quad_at_y_extrema(pts, mono_y)
            for y in 0..=count_y:
                var mono_x: Point[5]
                let y_points: Point[3] = [mono_y[y * 2], mono_y[y * 2 + 1], mono_y[y * 2 + 2]]
                let count_x = chop_quad_at_x_extrema(y_points, mono_x)
                for x in 0..=count_x:
                    let x_points: Point[3] = [mono_x[x * 2], mono_x[x * 2 + 1], mono_x[x * 2 + 2]]
                    self.clip_mono_quad(x_points)

        if self.edges.len == 0:
            return none
        return self.edges

    # src[] must be monotonic in X and Y
    func clip_mono_quad(src: const Point[]):
        var pts: Point[3]
        var reverse = sort_increasing_y(src, pts)

        # are we completely above or below
        if pts[2].y <= self.clip.top() or pts[0].y >= self.clip.bottom():
            return

        # Now chop so that pts is contained within clip in Y
        chop_quad_in_y(self.clip, pts)

        if pts[0].x > pts[2].x:
            let t = pts[0]
            pts[0] = pts[2]
            pts[2] = t
            reverse = not reverse

        # Now chop in X has needed, and record the segments

        if pts[2].x <= self.clip.left():
            # wholly to the left
            self.push_vline(self.clip.left(), pts[0].y, pts[2].y, reverse)
            return

        if pts[0].x >= self.clip.right():
            # wholly to the right
            if not self.can_cull_to_the_right:
                self.push_vline(self.clip.right(), pts[0].y, pts[2].y, reverse)
            return

        var t: f32 = normalized_exclusive_half
        var tmp: Point[5]

        # are we partially to the left
        if pts[0].x < self.clip.left():
            if chop_mono_quad_at_x(pts, self.clip.left(), &t):
                chop_quad_at(pts, t, tmp)
                self.push_vline(self.clip.left(), tmp[0].y, tmp[2].y, reverse)
                # clamp to clean up imprecise numerics in the chop
                tmp[2].x = self.clip.left()
                tmp[3].x = fmax(tmp[3].x, self.clip.left())

                pts[0] = tmp[2]
                pts[1] = tmp[3]
            else:
                # if chopMonoQuadAtY failed, then we may have hit inexact numerics so we just
                # clamp against the left
                self.push_vline(self.clip.left(), pts[0].y, pts[2].y, reverse)
                return

        # are we partially to the right
        if pts[2].x > self.clip.right():
            if chop_mono_quad_at_x(pts, self.clip.right(), &t):
                chop_quad_at(pts, t, tmp)
                # clamp to clean up imprecise numerics in the chop
                tmp[1].x = fmin(tmp[1].x, self.clip.right())
                tmp[2].x = self.clip.right()

                self.push_quad([tmp[0], tmp[1], tmp[2]], reverse)
                self.push_vline(self.clip.right(), tmp[2].y, tmp[4].y, reverse)
            else:
                # if chopMonoQuadAtY failed, then we may have hit inexact numerics so we just
                # clamp against the right
                pts[1].x = fmin(pts[1].x, self.clip.right())
                pts[2].x = fmin(pts[2].x, self.clip.right())
                self.push_quad(pts, reverse)
        else:
            # wholly inside the clip
            self.push_quad(pts, reverse)

    func push_quad(pts: const Point[], reverse: bool):
        if reverse:
            self.edges.push(.quad_to(p0 = pts[2], p1 = pts[1], p2 = pts[0]))
        else:
            self.edges.push(.quad_to(p0 = pts[0], p1 = pts[1], p2 = pts[2]))

    func clip_cubic(p0: Point, p1: Point, p2: Point, p3: Point) -> ClippedEdges?:
        let pts: Point[4] = [p0, p1, p2, p3]
        let bounds = Rect.from_points(pts) else return none

        # check if we're clipped out vertically
        if bounds.bottom() > self.clip.top() and bounds.top() < self.clip.bottom():
            if too_big_for_reliable_float_math(bounds):
                # can't safely clip the cubic, so we give up and draw a line (which we can
                # safely clip)
                #
                # If we rewrote chopcubicat*extrema and chopmonocubic using doubles, we could
                # very likely always handle the cubic safely, but (it seems) at a big loss in
                # speed, so we'd only want to take that alternate impl if needed.
                return self.clip_line(p0, p3)
            var mono_y: Point[10]
            let count_y = chop_cubic_at_y_extrema(pts, mono_y)
            for y in 0..=count_y:
                var mono_x: Point[10]
                let y_points: Point[4] = [mono_y[y * 3], mono_y[y * 3 + 1], mono_y[y * 3 + 2], mono_y[y * 3 + 3]]
                let count_x = chop_cubic_at_x_extrema(y_points, mono_x)
                for x in 0..=count_x:
                    let x_points: Point[4] = [mono_x[x * 3], mono_x[x * 3 + 1], mono_x[x * 3 + 2], mono_x[x * 3 + 3]]
                    self.clip_mono_cubic(x_points)

        if self.edges.len == 0:
            return none
        return self.edges

    # src[] must be monotonic in X and Y
    func clip_mono_cubic(src: const Point[]):
        var pts: Point[4]
        var reverse = sort_increasing_y(src, pts)

        # are we completely above or below
        if pts[3].y <= self.clip.top() or pts[0].y >= self.clip.bottom():
            return

        # Now chop so that pts is contained within clip in Y
        chop_cubic_in_y(self.clip, pts)

        if pts[0].x > pts[3].x:
            var t = pts[0]
            pts[0] = pts[3]
            pts[3] = t
            t = pts[1]
            pts[1] = pts[2]
            pts[2] = t
            reverse = not reverse

        # Now chop in X has needed, and record the segments

        if pts[3].x <= self.clip.left():
            # wholly to the left
            self.push_vline(self.clip.left(), pts[0].y, pts[3].y, reverse)
            return

        if pts[0].x >= self.clip.right():
            # wholly to the right
            if not self.can_cull_to_the_right:
                self.push_vline(self.clip.right(), pts[0].y, pts[3].y, reverse)
            return

        # are we partially to the left
        if pts[0].x < self.clip.left():
            var tmp: Point[7]
            chop_mono_cubic_at_x_clamped(pts, self.clip.left(), tmp)
            self.push_vline(self.clip.left(), tmp[0].y, tmp[3].y, reverse)

            # tmp[3, 4].fX should all be to the right of clip.left(). Since we can't trust
            # the numerics of the chopper, we force those conditions now
            tmp[3].x = self.clip.left()
            tmp[4].x = fmax(tmp[4].x, self.clip.left())

            pts[0] = tmp[3]
            pts[1] = tmp[4]
            pts[2] = tmp[5]

        # are we partially to the right
        if pts[3].x > self.clip.right():
            var tmp: Point[7]
            chop_mono_cubic_at_x_clamped(pts, self.clip.right(), tmp)
            tmp[3].x = self.clip.right()
            tmp[2].x = fmin(tmp[2].x, self.clip.right())

            self.push_cubic([tmp[0], tmp[1], tmp[2], tmp[3]], reverse)
            self.push_vline(self.clip.right(), tmp[3].y, tmp[6].y, reverse)
        else:
            # wholly inside the clip
            self.push_cubic(pts, reverse)

    func push_cubic(pts: const Point[], reverse: bool):
        if reverse:
            self.edges.push(.cubic_to(p0 = pts[3], p1 = pts[2], p2 = pts[1], p3 = pts[0]))
        else:
            self.edges.push(.cubic_to(p0 = pts[0], p1 = pts[1], p2 = pts[2], p3 = pts[3]))

## SkEdgeClipper::ClipPath as an iterator: the clipped edges of each path edge in turn (a
## conic's quads, within 1/4 pixel, one at a time).
struct EdgeClipperIter:
    var edge_iter: PathEdgeIter
    var clip: Rect
    var can_cull_to_the_right: bool
    var conic_quads: AutoConicToQuads
    ## The next quad of `conic_quads` to clip (conic_quads.len when none is pending).
    var conic_index: usize

    static func new_(path: const Path*, clip: Rect, can_cull_to_the_right: bool) -> EdgeClipperIter:
        var iter: EdgeClipperIter = ---
        iter.edge_iter = edge_iter(path)
        iter.clip = clip
        iter.can_cull_to_the_right = can_cull_to_the_right
        iter.conic_quads.len = 0
        iter.conic_index = 0
        return iter

    func next() -> ClippedEdges?:
        while true:
            while self.conic_index < self.conic_quads.len:
                let q = self.conic_quads.quad(self.conic_index)
                self.conic_index += 1
                var clipper = EdgeClipper.new_(self.clip, self.can_cull_to_the_right)
                if let edges = clipper.clip_quad(q[0], q[1], q[2]):
                    return edges
            let edge = self.edge_iter.next() else return none
            var clipper = EdgeClipper.new_(self.clip, self.can_cull_to_the_right)

            match edge:
                .line_to(p0, p1):
                    if let edges = clipper.clip_line(p0, p1):
                        return edges
                .quad_to(p0, p1, p2):
                    if let edges = clipper.clip_quad(p0, p1, p2):
                        return edges
                .cubic_to(p0, p1, p2, p3):
                    if let edges = clipper.clip_cubic(p0, p1, p2, p3):
                        return edges
                .conic_to(p0, p1, p2, weight):
                    self.conic_quads = AutoConicToQuads.compute(p0, p1, p2, weight, 0.25)
                    self.conic_index = 0

func quick_reject(bounds: Rect, clip: Rect) -> bool:
    return bounds.top() >= clip.bottom() or bounds.bottom() <= clip.top()

# src[] must be monotonic in Y. This routine copies src into dst, and sorts it to be
# increasing in Y. If it had to reverse the order of the points, it returns true, otherwise
# it returns false
func sort_increasing_y(src: const Point[], dst: Point[]) -> bool:
    # We need the data to be monotonically increasing in Y.
    # Never fails, because src is always non-empty.
    if src[0].y > src[src.length - 1].y:
        for i in 0..<src.length:
            dst[i] = src[src.length - 1 - i]
        return true
    for i in 0..<src.length:
        dst[i] = src[i]
    return false

func chop_quad_in_y(clip: Rect, pts: Point[]):
    var t: f32 = normalized_exclusive_half
    var tmp: Point[5]

    # are we partially above
    if pts[0].y < clip.top():
        if chop_mono_quad_at_y(pts, clip.top(), &t):
            # take the 2nd chopped quad
            chop_quad_at(pts, t, tmp)
            # clamp to clean up imprecise numerics in the chop
            tmp[2].y = clip.top()
            tmp[3].y = fmax(tmp[3].y, clip.top())

            pts[0] = tmp[2]
            pts[1] = tmp[3]
        else:
            # if chop_mono_quad_at_y failed, then we may have hit inexact numerics so we just
            # clamp against the top
            for p in &pts:
                if p.y < clip.top():
                    p.y = clip.top()

    # are we partially below
    if pts[2].y > clip.bottom():
        if chop_mono_quad_at_y(pts, clip.bottom(), &t):
            chop_quad_at(pts, t, tmp)
            # clamp to clean up imprecise numerics in the chop
            tmp[1].y = fmin(tmp[1].y, clip.bottom())
            tmp[2].y = clip.bottom()

            pts[1] = tmp[1]
            pts[2] = tmp[2]
        else:
            # if chop_mono_quad_at_y failed, then we may have hit inexact numerics so we just
            # clamp against the bottom
            for p in &pts:
                if p.y > clip.bottom():
                    p.y = clip.bottom()

func chop_mono_quad_at_x(pts: const Point[], x: f32, t: f32*) -> bool:
    return chop_mono_quad_at(pts[0].x, pts[1].x, pts[2].x, x, t)

func chop_mono_quad_at_y(pts: const Point[], y: f32, t: f32*) -> bool:
    return chop_mono_quad_at(pts[0].y, pts[1].y, pts[2].y, y, t)

func chop_mono_quad_at(c0: f32, c1: f32, c2: f32, target: f32, t: f32*) -> bool:
    # Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
    # We solve for t, using quadratic equation, hence we have to rearrange
    # our coefficients to look like At^2 + Bt + C
    let a = c0 - c1 - c1 + c2
    let b = 2.0 * (c1 - c0)
    let c = c0 - target

    var roots = new_t_values()
    let count = find_unit_quad_roots(a, b, c, roots)
    if count != 0:
        *t = roots[0]
        return true
    return false

func too_big_for_reliable_float_math(r: Rect) -> bool:
    # limit set as the largest float value for which we can still reliably compute things
    # like
    # - chopping at XY extrema
    # - chopping at Y or X values for clipping
    #
    # Current value chosen just by experiment. Larger (and still succeeds) is always better.

    let limit: f32 = 4194304.0
    return r.left() < -limit or r.top() < -limit or r.right() > limit or r.bottom() > limit

func chop_cubic_in_y(clip: Rect, pts: Point[]):
    # are we partially above
    if pts[0].y < clip.top():
        var tmp: Point[7]
        chop_mono_cubic_at_y_clamped(pts, clip.top(), tmp)

        # For a large range in the points, we can do a poor job of chopping, such that the t
        # we computed resulted in the lower cubic still being partly above the clip.
        #
        # If just the first or first 2 Y values are above the fTop, we can just smash them
        # down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really
        # distort the cubic. In this case, we take the first output (tmp[3..6] and treat it
        # as a guess, and re-chop against fTop. Then we fall through to checking if we need
        # to smash the first 1 or 2 Y values.
        if tmp[3].y < clip.top() and tmp[4].y < clip.top() and tmp[5].y < clip.top():
            let tmp2: Point[4] = [tmp[3], tmp[4], tmp[5], tmp[6]]
            chop_mono_cubic_at_y_clamped(tmp2, clip.top(), tmp)

        # tmp[3, 4].y should all be to the below clip.fTop. Since we can't trust the numerics
        # of the chopper, we force those conditions now
        tmp[3].y = clip.top()
        tmp[4].y = fmax(tmp[4].y, clip.top())

        pts[0] = tmp[3]
        pts[1] = tmp[4]
        pts[2] = tmp[5]

    # are we partially below
    if pts[3].y > clip.bottom():
        var tmp: Point[7]
        chop_mono_cubic_at_y_clamped(pts, clip.bottom(), tmp)
        tmp[3].y = clip.bottom()
        tmp[2].y = fmin(tmp[2].y, clip.bottom())

        pts[1] = tmp[1]
        pts[2] = tmp[2]
        pts[3] = tmp[3]

# edge_clipper.rs chop_mono_cubic_at_x: path64 first, then the closest-t fallback.
func chop_mono_cubic_at_x_clamped(src: const Point[], x: f32, dst: Point[]):
    if chop_mono_cubic_at_x(src, x, dst):
        return

    let src_values: f32[4] = [src[0].x, src[1].x, src[2].x, src[3].x]
    chop_cubic_at2(src, mono_cubic_closest_t(src_values, x), dst)

# edge_clipper.rs chop_mono_cubic_at_y: path64 first, then the closest-t fallback.
func chop_mono_cubic_at_y_clamped(src: const Point[], y: f32, dst: Point[]):
    if chop_mono_cubic_at_y(src, y, dst):
        return

    let src_values: f32[4] = [src[0].y, src[1].y, src[2].y, src[3].y]
    chop_cubic_at2(src, mono_cubic_closest_t(src_values, y), dst)

func mono_cubic_closest_t(src: f32[4], x0: f32) -> f32:
    var x = x0
    var t: f32 = 0.5
    var last_t: f32
    var best_t = t
    var step: f32 = 0.25
    let d = src[0]
    let a = src[3] + 3.0 * (src[1] - src[2]) - d
    let b = 3.0 * (src[2] - src[1] - src[1] + d)
    let c = 3.0 * (src[1] - d)
    x -= d
    var closest = scalar_max
    while true:
        let loc = ((a * t + b) * t + c) * t
        let dist = math32.abs(loc - x)
        if closest > dist:
            closest = dist
            best_t = t

        last_t = t
        t += step if loc < x else -step
        step *= 0.5

        if not (closest > 0.25 and last_t != t):
            break

    return normalized_exclusive_new(best_t) else trap("unreachable")