Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.2

0.6.2 / src / raster / path_perspective.lucb

#==============================================================================================
#
#   path_perspective - transforming a path by a matrix with perspective
#
#   DESCRIPTION:
#       Port of the perspective branch of Skia m144's path transforms: SkPath::transform
#       (src/core/SkPath_pathref.cpp) and SkPathBuilder::transform (src/core/SkPathBuilder.cpp),
#       SkPathPriv::PerspectiveClip with SkHalfPlane and its `clip` (src/core/SkPath.cpp), and
#       SkConic::TransformW (src/core/SkGeometry.cpp). The path is first cut to the half-plane
#       where w >= kW0PlaneDistance (SkEdgeClipper::ClipPath on the path rotated so that the
#       plane is y = 0), then rebuilt with quads and conics as conics whose weight carries the
#       projection and cubics split in four, and its points are mapped with the divide by w.
#
#       SkPath::transform walks the path with SkPath::Iter, which turns a close into a line
#       back to the contour's start when the contour is open and drops a trailing move;
#       SkPathBuilder::transform (drawPath's fills, mapRect) walks the raw verbs.
#
#       Copyright 2006 The Android Open Source Project
#       Copyright (c) 2026 the luce-browser authors.
#       SPDX-License-Identifier: BSD-3-Clause (see LICENSE-skia)
#
#==============================================================================================

## SkPathPriv::kW0PlaneDistance: how far in front of the w = 0 plane points are kept.
let w0_plane_distance: f32 = 1.0 / 16384.0

## How SkPath::transform walks the path: SkPath::Iter (closes as lines, no trailing move) or
## the raw verbs (SkPathBuilder::transform).
pub enum PerspectiveIteration as u8:
    path_iter = 0
    raw = 1

# mark: SkHalfPlane ===========================================================================

## What SkPathPriv::PerspectiveClip leaves of a path.
enum PerspectiveClipResult:
    ## The whole path is in front of the plane: nothing to cut.
    unclipped
    ## The part of the path in front of the plane.
    clipped(path: Path)
    ## Nothing is in front of the plane (or the clip failed).
    nothing

## SkHalfPlane::Result.
enum HalfPlaneResult as u8:
    all_negative = 0
    all_positive = 1
    mixed = 2

## SkHalfPlane: the points where a * x + b * y + c >= 0.
struct HalfPlane:
    var a: f32
    var b: f32
    var c: f32

    func eval(x: f32, y: f32) -> f32:
        return self.a * x + self.b * y + self.c

    ## SkHalfPlane::normalize: the normal made unit length (in f64). False when it cannot be
    ## (the plane then contains everything).
    func normalize() -> bool:
        var a = (f64)self.a
        var b = (f64)self.b
        var c = (f64)self.c
        let dmag = math.sqrt(a * a + b * b)
        # length of initial plane normal is zero
        if dmag == 0.0:
            self.a = 0.0
            self.b = 0.0
            self.c = 1.0
            return true
        let dscale = 1.0 / dmag
        a *= dscale
        b *= dscale
        c *= dscale
        # check if we're not finite, or normal is zero-length
        if not math.is_finite(a) or not math.is_finite(b) or not math.is_finite(c) or (a == 0.0 and b == 0.0):
            self.a = 0.0
            self.b = 0.0
            self.c = 1.0
            return false
        self.a = (f32)a
        self.b = (f32)b
        self.c = (f32)c
        return true

    ## SkHalfPlane::test: whether `bounds` is all on one side of the plane, by the diagonal
    ## aligned with the normal.
    func test_bounds(bounds: Rect) -> HalfPlaneResult:
        var min_x = bounds.left()
        var max_x = bounds.right()
        if not (self.a >= 0.0):
            min_x = bounds.right()
            max_x = bounds.left()
        var min_y = bounds.top()
        var max_y = bounds.bottom()
        if not (self.b >= 0.0):
            min_y = bounds.bottom()
            max_y = bounds.top()
        let near = self.eval(min_x, min_y)
        let sign = near * self.eval(max_x, max_y)
        if sign > 0.0:
            # the path is either all on one side of the half-plane or the other
            if near < 0.0:
                return .all_negative
            return .all_positive
        return .mixed

# mark: PerspectiveClip =======================================================================

## SkPath.cpp's `clip`: `path` cut to the (normalized) half-plane, or none when nothing is
## left or the result is not finite.
func perspective_clip_path(path: const Path*, plane: HalfPlane) -> Path?:
    # The matrix that maps y = 0 onto the plane (and y > 0 onto its positive side).
    let p0 = Point.from_xy(-plane.a * plane.c, -plane.b * plane.c)
    let mx = Transform.from_all(plane.b, plane.a, p0.x, -plane.a, plane.b, p0.y, 0.0, 0.0, 1.0)
    let inv = mx.invert() else return none

    var rotated = path.clone()
    defer rotated.release()
    if not rotated.transform(inv):
        return none

    # SkRect {-big, 0, big, big}, whose width does not fit a float (no Rect.from_ltrb).
    let big = scalar_max
    let clip = Rect(left_ = -big, top_ = 0.0, right_ = big, bottom_ = big)

    # SkEdgeClipper::ClipPath with the callback that rebuilds the path.
    var result = PathBuilder.new_()
    var prev = Point.zero()
    var iter = edge_iter(&rotated)
    while let edge = iter.next():
        let new_contour = iter.is_new_contour
        var clipper = EdgeClipper.new_(clip, false)
        match edge:
            .line_to(e0, e1):
                if let edges = clipper.clip_line(e0, e1):
                    perspective_clip_consume(&result, &prev, &edges, new_contour)
            .quad_to(e0, e1, e2):
                if let edges = clipper.clip_quad(e0, e1, e2):
                    perspective_clip_consume(&result, &prev, &edges, new_contour)
            .cubic_to(e0, e1, e2, e3):
                if let edges = clipper.clip_cubic(e0, e1, e2, e3):
                    perspective_clip_consume(&result, &prev, &edges, new_contour)
            .conic_to(e0, e1, e2, weight):
                let quads = AutoConicToQuads.compute(e0, e1, e2, weight, 0.25)
                for i in 0..<quads.len:
                    let q = quads.quad(i)
                    var quad_clipper = EdgeClipper.new_(clip, false)
                    if let edges = quad_clipper.clip_quad(q[0], q[1], q[2]):
                        perspective_clip_consume(&result, &prev, &edges, new_contour)

    var clipped = result.finish() else return none
    if not clipped.transform(mx):
        clipped.release()
        return none
    return clipped

## The ClipPath callback of `clip`: the clipped pieces of one edge appended to `result`, a
## new contour started when the edge starts one, and a line joining pieces that do not meet.
func perspective_clip_consume(result: PathBuilder*, prev: Point*, edges: const ClippedEdges*, new_contour0: bool):
    var new_contour = new_contour0
    var add_line_to = false
    for i in 0..<edges.len:
        let edge = edges.edges[i]
        let start = perspective_edge_start(edge)
        if new_contour:
            result.move_to(start.x, start.y)
            *prev = start
            new_contour = false
        if add_line_to or not points_equal(start, *prev):
            result.line_to(start.x, start.y)
        match edge:
            .line_to(_, e1):
                result.line_to(e1.x, e1.y)
                *prev = e1
            .quad_to(_, e1, e2):
                result.quad_to(e1.x, e1.y, e2.x, e2.y)
                *prev = e2
            .cubic_to(_, e1, e2, e3):
                result.cubic_to(e1.x, e1.y, e2.x, e2.y, e3.x, e3.y)
                *prev = e3
            _:
                _ = 0
        add_line_to = true

## The first point of a clipped edge.
func perspective_edge_start(edge: PathEdge) -> Point:
    var start = Point.zero()
    match edge:
        .line_to(e0, _): start = e0
        .quad_to(e0, _, _): start = e0
        .cubic_to(e0, _, _, _): start = e0
        .conic_to(e0, _, _, _): start = e0
    return start

## SkPathPriv::PerspectiveClip: what is left of `path` in front of the w = kW0PlaneDistance
## plane of `matrix`.
func perspective_clip(path: const Path*, matrix: Transform) -> PerspectiveClipResult:
    var plane = HalfPlane(a = matrix.persp0, b = matrix.persp1, c = matrix.persp2 - w0_plane_distance)
    if plane.normalize():
        match plane.test_bounds(path.bounds()):
            .all_positive:
                return .unclipped
            .mixed:
                if let clipped = perspective_clip_path(path, plane):
                    return .clipped(path = clipped)
                return .nothing
            _:
                _ = 0
    # clipped out (or failed)
    return .nothing

# mark: The transform =========================================================================

## SkConic::TransformW: the weight of the conic (pts, w) once mapped by `matrix`.
func conic_transform_w(p0: Point, p1: Point, p2: Point, w: f32, matrix: Transform) -> f32:
    if not matrix.has_perspective():
        return w
    # ratquad_mapTo3D, then mapHomogeneousPoints: only the mapped z of each point is needed.
    let w0 = (f64)(p0.x * 1.0 * matrix.persp0 + p0.y * 1.0 * matrix.persp1 + 1.0 * matrix.persp2)
    let w1 = (f64)(p1.x * w * matrix.persp0 + p1.y * w * matrix.persp1 + w * matrix.persp2)
    let w2 = (f64)(p2.x * 1.0 * matrix.persp0 + p2.y * 1.0 * matrix.persp1 + 1.0 * matrix.persp2)
    # w' = sqrt(w1*w1/w0*w2); doubles handle small numerators and denominators
    return (f32)math.sqrt((w1 * w1) / (w0 * w2))

## subdivide_cubic_to: the cubic halved twice (four cubics), so that each piece maps close
## to its projection.
func subdivide_cubic_to(builder: PathBuilder*, pts: const Point[], level0: i32):
    let level = level0 - 1
    if level >= 0:
        var tmp: Point[7] = ---
        chop_cubic_at2(pts, 0.5, tmp)
        subdivide_cubic_to(builder, tmp[0..<4], level)
        subdivide_cubic_to(builder, tmp[3..<7], level)
    else:
        builder.cubic_to(pts[1].x, pts[1].y, pts[2].x, pts[2].y, pts[3].x, pts[3].y)

## The perspective branch of SkPath::transform / SkPathBuilder::transform: `path` clipped to
## w > 0, rebuilt for the projection and mapped. None when nothing is left.
pub func path_transform_perspective(path: const Path*, matrix: Transform, iteration: PerspectiveIteration) -> Path?:
    match perspective_clip(path, matrix):
        .unclipped:
            return path_transform_perspective_unclipped(path, matrix, iteration)
        .clipped(clipped):
            var owned = clipped
            let result = path_transform_perspective_unclipped(&owned, matrix, iteration)
            owned.release()
            return result
        .nothing:
            return none

## The rest of the perspective branch, once the path is in front of the plane.
func path_transform_perspective_unclipped(source: const Path*, matrix: Transform, iteration: PerspectiveIteration) -> Path?:
    var builder = PathBuilder.new_()
    var iter = source.segments()
    iter.set_auto_close(iteration == .path_iter)
    var last = Point.zero()
    while let segment = iter.next():
        match segment:
            .move_to(p):
                # SkPath::Iter drops a trailing move.
                if iteration == .raw or iter.next_verb() != none:
                    builder.move_to(p.x, p.y)
            .line_to(p):
                builder.line_to(p.x, p.y)
            .quad_to(p1, p):
                # promote the quad to a conic
                builder.conic_to(p1.x, p1.y, p.x, p.y, conic_transform_w(last, p1, p, 1.0, matrix))
            .conic_to(p1, p, weight):
                builder.conic_to(p1.x, p1.y, p.x, p.y, conic_transform_w(last, p1, p, weight, matrix))
            .cubic_to(p1, p2, p):
                let pts: Point[4] = [last, p1, p2, p]
                subdivide_cubic_to(&builder, pts, 2)
            .close:
                builder.close()
        last = iter.last_point

    var result = builder.finish() else return none
    matrix.map_points(result.points.view())
    if let bounds = Rect.from_points(result.points.view()):
        result.bounds_ = bounds
        return result
    result.release()
    return none