Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-render

Source of release 0.6.1

0.6.1 / src / raster / conic.lucb

#==============================================================================================
#
#   conic - conics: arcs as weighted quads, and their subdivision into quads
#
#   DESCRIPTION:
#       Port of tiny-skia-path path_geometry.rs from `struct Conic` to the end (Conic,
#       build_unit_arc, subdivide, between), with the conversion to quads brought up to Skia
#       m144's SkGeometry.cpp: computeQuadPOW2 (up to 32 quads), chopIntoQuadsPOW2 and the
#       non-legacy SkConic::chop, and SkAutoConicToQuads. Paths keep their conics; they
#       become quads (within 1/4 pixel) where Skia converts them, in device space.
#
#==============================================================================================

struct Conic:
    var points: Point[3]
    var weight: f32

    static func new_(pt0: Point, pt1: Point, pt2: Point, weight: f32) -> Conic:
        return Conic(points = [pt0, pt1, pt2], weight = weight)

    static func from_points(points: const Point[], weight: f32) -> Conic:
        return Conic(points = [points[0], points[1], points[2]], weight = weight)

    static func zero() -> Conic:
        return Conic(points = [Point.zero(), Point.zero(), Point.zero()], weight = 0.0)

    ## SkConic::computeQuadPOW2: how many times (as a power of 2) the conic must be halved
    ## for its quads to be within `tolerance` ("High order approximation of conic sections
    ## by quadratic splines", Michael Floater, 1993).
    func compute_quad_pow2(tolerance: f32) -> u32:
        if tolerance < 0.0 or not math32.is_finite(tolerance) or not self.points[0].is_finite() or not self.points[1].is_finite() or not self.points[2].is_finite() or bad_conic_w(self.weight):
            return 0

        let a = self.weight - 1.0
        let k = a / (4.0 * (2.0 + a))
        let x = k * (self.points[0].x - 2.0 * self.points[1].x + self.points[2].x)
        let y = k * (self.points[0].y - 2.0 * self.points[1].y + self.points[2].y)

        var err = math32.sqrt(x * x + y * y)
        var pow2: u32 = 0
        while pow2 < max_conic_to_quad_pow2:
            if err <= tolerance:
                break
            err *= 0.25
            pow2 += 1
        return pow2

    ## SkConic::chopIntoQuadsPOW2: chops this conic into N = 1 << pow2 quads, stored
    ## continuously in points[] (1 + 2 * N of them). Answers N.
    func chop_into_quads_pow2(pow20: u32, points: Point[]) -> usize:
        var pow2 = pow20
        if bad_conic_w(self.weight):
            pow2 = 0

        points[0] = self.points[0]
        var done = false
        if pow2 == max_conic_to_quad_pow2:  # If an extreme weight generates many quads ...
            let pair = self.chop()
            let d0 = pair.0
            let d1 = pair.1
            # check to see if the first chop generates a pair of lines
            if equals_within_tolerance(d0.points[1], d0.points[2]) and equals_within_tolerance(d1.points[0], d1.points[1]):
                points[1] = d0.points[1]  # set ctrl == end to make lines
                points[2] = d0.points[1]
                points[3] = d0.points[1]
                points[4] = d1.points[2]
                pow2 = 1
                done = true
        if not done:
            _ = subdivide(&self, points[1..], (u8)pow2)

        let quad_count: usize = (usize)1 << (usize)pow2
        let pt_count = 2 * quad_count + 1
        var any_non_finite = false
        for p in points[..<pt_count]:
            if not p.is_finite():
                any_non_finite = true
        if any_non_finite:
            # if we generated a non-finite, pin ourselves to the middle of the hull, as our
            # first and last are already on the first/last pts of the hull.
            for i in 1..<pt_count - 1:
                points[i] = self.points[1]
        return quad_count

    ## SkConic::chop (Skia m144's, not SK_SUPPORT_LEGACY_CONIC_CHOP): halves the conic.
    func chop() -> (Conic, Conic):
        # Observe that scale will always be smaller than 1 because weight > 0.
        let scale = invert(1.0 + self.weight)

        # The subdivided control points below are the sums of the following three terms.
        # Because the terms are multiplied by something <1, and the resulting control points
        # lie within the control points of the original then the terms and the sums below
        # will not overflow. Note that weight * scale approaches 1 as weight becomes very
        # large.
        let t0 = self.points[0].to_f32x2() * f32x2_splat(scale)
        let t1 = self.points[1].to_f32x2() * f32x2_splat(self.weight * scale)
        let t2 = self.points[2].to_f32x2() * f32x2_splat(scale)

        # Calculate the subdivided control points
        let p1 = Point.from_f32x2(t0 + t1)
        let p3 = Point.from_f32x2(t1 + t2)

        # p2 = (t0 + 2*t1 + t2) / 2. Divide the terms by 2 before the sum to keep the sum for
        # p2 from overflowing.
        let p2 = Point.from_f32x2(f32x2_splat(0.5) * t0 + t1 + f32x2_splat(0.5) * t2)

        let w = subdivide_weight_value(self.weight)
        return (Conic(points = [self.points[0], p1, p2], weight = w), Conic(points = [p2, p3, self.points[2]], weight = w))

    ## SkConic::evalAt: the point at `t` (SkConicCoeff: the rational quad's numerator over
    ## its denominator).
    func eval_at(t: f32) -> Point:
        let p0 = self.points[0].to_f32x2()
        let p1 = self.points[1].to_f32x2()
        let p2 = self.points[2].to_f32x2()
        let ww = f32x2_splat(self.weight)

        let p1w = p1 * ww
        let numer = QuadCoeff(a = p2 - times_2(p1w) + p0, b = times_2(p1w - p0), c = p0)
        let one = f32x2_splat(1.0)
        let denom_b = times_2(ww - one)
        let denom = QuadCoeff(a = f32x2_splat(0.0) - denom_b, b = denom_b, c = one)
        let tt = f32x2_splat(t)
        return Point.from_f32x2(numer.eval(tt) / denom.eval(tt))

    ## SkConic::evalTangentAt.
    func eval_tangent_at(t: f32) -> Point:
        # The derivative equation returns a zero tangent vector when t is 0 or 1, and the
        # control point is equal to the end point. In this case, use the conic endpoints to
        # compute the tangent.
        if (t == 0.0 and points_equal(self.points[0], self.points[1])) or (t == 1.0 and points_equal(self.points[1], self.points[2])):
            return Point.from_xy(self.points[2].x - self.points[0].x, self.points[2].y - self.points[0].y)
        let p0 = self.points[0].to_f32x2()
        let p1 = self.points[1].to_f32x2()
        let p2 = self.points[2].to_f32x2()
        let ww = f32x2_splat(self.weight)

        let p20 = p2 - p0
        let p10 = p1 - p0

        let c = ww * p10
        let a = ww * p20 - p20
        let b = p20 - c - c

        return Point.from_f32x2(QuadCoeff(a = a, b = b, c = c).eval(f32x2_splat(t)))

    ## SkConic::chopAt(t, dst): the conic split at `t`, none if that is not finite.
    func chop_at(t: f32) -> (Conic, Conic)?:
        # ratquad_mapTo3D, p3d_interp and project_down
        let w = self.weight
        let x: f32[3] = [self.points[0].x * 1.0, self.points[1].x * w, self.points[2].x * 1.0]
        let y: f32[3] = [self.points[0].y * 1.0, self.points[1].y * w, self.points[2].y * 1.0]
        let z: f32[3] = [1.0, w, 1.0]
        let x2 = p3d_interp(x, t)
        let y2 = p3d_interp(y, t)
        let z2 = p3d_interp(z, t)

        let m = Point.from_xy(x2[1] / z2[1], y2[1] / z2[1])
        # to put in "standard form", where w0 and w2 are both 1, we compute the new w1 as
        # sqrt(w1*w1/w0*w2), or w1 /= sqrt(w0*w2). However, in our case, we know that for
        # dst[0]: w0 == 1, and for dst[1], w2 == 1
        let root = math32.sqrt(z2[1])
        let d0 = Conic(points = [self.points[0], Point.from_xy(x2[0] / z2[0], y2[0] / z2[0]), m], weight = z2[0] / root)
        let d1 = Conic(points = [m, Point.from_xy(x2[2] / z2[2], y2[2] / z2[2]), self.points[2]], weight = z2[2] / root)
        for c in [d0, d1]:
            for p in c.points:
                if not p.is_finite():
                    return none
            if not math32.is_finite(c.weight):
                return none
        return (d0, d1)

    ## SkConic::chopAt(t1, t2, dst): the part of the conic between t1 and t2.
    func chop_between(t1: f32, t2: f32) -> Conic:
        if t1 == 0.0 or t2 == 1.0:
            if t1 == 0.0 and t2 == 1.0:
                return self
            if let pair = self.chop_at(t1 if t1 != 0.0 else t2):
                return pair.1 if t1 != 0.0 else pair.0
        # SkConicCoeff: the numerator and denominator quads.
        let p0 = self.points[0].to_f32x2()
        let p1 = self.points[1].to_f32x2()
        let p2 = self.points[2].to_f32x2()
        let ww = f32x2_splat(self.weight)
        let p1w = p1 * ww
        let numer = QuadCoeff(a = p2 - times_2(p1w) + p0, b = times_2(p1w - p0), c = p0)
        let one = f32x2_splat(1.0)
        let denom_b = times_2(ww - one)
        let denom = QuadCoeff(a = f32x2_splat(0.0) - denom_b, b = denom_b, c = one)

        let tt1 = f32x2_splat(t1)
        let a_xy = numer.eval(tt1)
        let a_zz = denom.eval(tt1)
        let mid_tt = f32x2_splat((t1 + t2) / 2.0)
        let d_xy = numer.eval(mid_tt)
        let d_zz = denom.eval(mid_tt)
        let tt2 = f32x2_splat(t2)
        let c_xy = numer.eval(tt2)
        let c_zz = denom.eval(tt2)
        let half_v = f32x2_splat(0.5)
        let b_xy = times_2(d_xy) - (a_xy + c_xy) * half_v
        let b_zz = times_2(d_zz) - (a_zz + c_zz) * half_v
        let ww2 = b_zz / f32x2_sqrt(a_zz * c_zz)
        return Conic(points = [Point.from_f32x2(a_xy / a_zz), Point.from_f32x2(b_xy / b_zz), Point.from_f32x2(c_xy / c_zz)], weight = ww2[0])

    ## Writes the conics of the unit arc from `u_start` to `u_stop` into `dst` (5 slots) and
    ## answers how many (0 is Rust's `None`).
    static func build_unit_arc(u_start: Point, u_stop: Point, dir: PathDirection, user_transform: Transform, dst: Conic[]) -> usize:
        # rotate by x,y so that u_start is (1.0)
        let x = u_start.dot(u_stop)
        var y = u_start.cross(u_stop)

        let abs_y = math32.abs(y)

        # check for (effectively) coincident vectors
        # this can happen if our angle is nearly 0 or nearly 180 (y == 0)
        # ... we use the dot-prod to distinguish between 0 and 180 (x > 0)
        if abs_y <= scalar_nearly_zero and x > 0.0 and ((y >= 0.0 and dir == .cw) or (y <= 0.0 and dir == .ccw)):
            return 0

        if dir == .ccw:
            y = -y

        # We decide to use 1-conic per quadrant of a circle. What quadrant does [xy] lie in?
        #      0 == [0  .. 90)
        #      1 == [90 ..180)
        #      2 == [180..270)
        #      3 == [270..360)
        #
        var quadrant: usize = 0
        if y == 0.0:
            quadrant = 2  # 180
        elif x == 0.0:
            quadrant = 1 if y > 0.0 else 3  # 90 / 270
        else:
            if y < 0.0:
                quadrant += 2
            if (x < 0.0) != (y < 0.0):
                quadrant += 1

        let quadrant_points: Point[8] = [
            Point.from_xy(1.0, 0.0),
            Point.from_xy(1.0, 1.0),
            Point.from_xy(0.0, 1.0),
            Point.from_xy(-1.0, 1.0),
            Point.from_xy(-1.0, 0.0),
            Point.from_xy(-1.0, -1.0),
            Point.from_xy(0.0, -1.0),
            Point.from_xy(1.0, -1.0),
        ]

        let quadrant_weight = scalar_root_2_over_2

        var conic_count = quadrant
        for i in 0..<conic_count:
            dst[i] = Conic.from_points(quadrant_points[i * 2..], quadrant_weight)

        # Now compute any remaining (sub-90-degree) arc for the last conic
        let final_pt = Point.from_xy(x, y)
        let last_q = quadrant_points[quadrant * 2]  # will already be a unit-vector
        let dot = last_q.dot(final_pt)

        if dot < 1.0:
            var off_curve = Point.from_xy(last_q.x + x, last_q.y + y)
            # compute the bisector vector, and then rescale to be the off-curve point. we
            # compute its length from cos(theta/2) = length / 1, using half-angle identity we
            # get length = sqrt(2 / (1 + cos(theta)). We already have cos() when to computed
            # the dot. This is nice, since our computed weight is cos(theta/2) as well!
            let cos_theta_over_2 = math32.sqrt((1.0 + dot) / 2.0)
            _ = off_curve.set_length(invert(cos_theta_over_2))
            if not last_q.almost_equal(off_curve):
                dst[conic_count] = Conic.new_(last_q, off_curve, final_pt, cos_theta_over_2)
                conic_count += 1

        # now handle counter-clockwise and the initial unitStart rotation
        var transform = Transform.from_sin_cos(u_start.y, u_start.x)
        if dir == .ccw:
            transform = transform.pre_scale(1.0, -1.0)

        transform = transform.post_concat(user_transform)

        for i in 0..<conic_count:
            transform.map_points(dst[i].points)

        return conic_count

func subdivide_weight_value(w: f32) -> f32:
    return math32.sqrt(0.5 + w * 0.5)

func subdivide(src: const Conic*, points0: Point[], level0: u8) -> Point[]:
    var points = points0
    var level = level0
    if level == 0:
        points[0] = src.points[1]
        points[1] = src.points[2]
        return points[2..]

    let pair = src.chop()
    var d0 = pair.0
    var d1 = pair.1

    let start_y = src.points[0].y
    let end_y = src.points[2].y
    if between(start_y, src.points[1].y, end_y):
        # If the input is monotonic and the output is not, the scan converter hangs.
        # Ensure that the chopped conics maintain their y-order.
        let mid_y = d0.points[2].y
        if not between(start_y, mid_y, end_y):
            # If the computed midpoint is outside the ends, move it to the closer one.
            let closer_y = start_y if math32.abs(mid_y - start_y) < math32.abs(mid_y - end_y) else end_y
            d0.points[2].y = closer_y
            d1.points[0].y = closer_y

        if not between(start_y, d0.points[1].y, d0.points[2].y):
            # If the 1st control is not between the start and end, put it at the start.
            # This also reduces the quad to a line.
            d0.points[1].y = start_y

        if not between(d1.points[0].y, d1.points[1].y, end_y):
            # If the 2nd control is not between the start and end, put it at the end.
            # This also reduces the quad to a line.
            d1.points[1].y = end_y

    level -= 1
    points = subdivide(&d0, points, level)
    return subdivide(&d1, points, level)

# This was originally developed and tested for pathops: see SkOpTypes.h
# returns true if (a <= b <= c) || (a >= b >= c)
func between(a: f32, b: f32, c: f32) -> bool:
    return (a - b) * (c - b) <= 0.0

## p3d_interp for one coordinate of the three homogeneous points.
func p3d_interp(src: f32[3], t: f32) -> f32[3]:
    let ab = src[0] + (src[1] - src[0]) * t
    let bc = src[1] + (src[2] - src[1]) * t
    return [ab, ab + (bc - ab) * t, bc]

func f32x2_sqrt(v: F32x2) -> F32x2:
    return [math32.sqrt(v[0]), math32.sqrt(v[1])]

## conic_find_extrema: the t of the extremum of one coordinate (x or y, as src0..src2) of a
## conic, if it has one.
func conic_find_extrema(src0: f32, src1: f32, src2: f32, w: f32) -> f32?:
    # conic_deriv_coeff
    let p20 = src2 - src0
    let p10 = src1 - src0
    let wp10 = w * p10
    let coeff0 = w * p20 - p20
    let coeff1 = p20 - 2.0 * wp10
    let coeff2 = wp10

    var t_values: f32[3] = [0.0, 0.0, 0.0]
    let roots = find_unit_quad_roots(coeff0, coeff1, coeff2, t_values)
    if roots == 1:
        return t_values[0]
    return none

## The most quads (as a power of 2) a conic is split into.
let max_conic_to_quad_pow2: u32 = 5

func bad_conic_w(w: f32) -> bool:
    return w < 0.0 or not math32.is_finite(w)

## SkPointPriv::EqualsWithinTolerance: the difference cannot be normalized.
func equals_within_tolerance(p1: Point, p2: Point) -> bool:
    let dx = p1.x - p2.x
    let dy = p1.y - p2.y
    return not (math32.is_finite(dx) and math32.is_finite(dy) and (dx != 0.0 or dy != 0.0))

## SkAutoConicToQuads: the quads approximating a conic within a tolerance. Quad i is
## points[2 * i ..= 2 * i + 2].
struct AutoConicToQuads:
    var points: Point[65]
    ## The number of quads.
    var len: usize

    static func compute(pt0: Point, pt1: Point, pt2: Point, weight: f32, tolerance: f32) -> AutoConicToQuads:
        let conic = Conic.new_(pt0, pt1, pt2, weight)
        let pow2 = conic.compute_quad_pow2(tolerance)
        var result: AutoConicToQuads = ---
        result.len = conic.chop_into_quads_pow2(pow2, result.points)
        return result

    ## Quad i's three points.
    func quad(i: usize) -> const Point[]:
        return self.points[2 * i..<2 * i + 3]