Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-svg

Source of release 0.9.2

0.9.2 / src / svg / text_path_walk.lucb

#==============================================================================================
#
#   svg/text_path_walk - Text along a path
#
#   DESCRIPTION:
#       A text path's glyphs sit centred on points along the path's length: each glyph
#       at the start offset (plus the chunk's x and its anchor shift) plus the advances
#       and dx before it, turned with the path's tangent there, shifted across it by the
#       running dy and its baseline. A glyph past either end of the path is not drawn.
#       Lengths and positions along a segment are found as kurbo (and so resvg) finds
#       them, to the same accuracy, so glyphs land where resvg puts them.
#
#==============================================================================================

## Legendre-Gauss quadrature weights and abscissae (the positive halves), as kurbo
## measures cubic arc lengths with them.
let gauss_8: f64[8] = [0.3626837833783620, 0.1834346424956498, 0.3137066458778873, 0.5255324099163290, 0.2223810344533745, 0.7966664774136267,
                       0.1012285362903763, 0.9602898564975363]
let gauss_8_full: f64[16] = [0.3626837833783620, -0.1834346424956498, 0.3626837833783620, 0.1834346424956498, 0.3137066458778873, -0.5255324099163290,
                             0.3137066458778873, 0.5255324099163290, 0.2223810344533745, -0.7966664774136267, 0.2223810344533745, 0.7966664774136267,
                             0.1012285362903763, -0.9602898564975363, 0.1012285362903763, 0.9602898564975363]
let gauss_16: f64[16] = [0.1894506104550685, 0.0950125098376374, 0.1826034150449236, 0.2816035507792589, 0.1691565193950025, 0.4580167776572274,
                         0.1495959888165767, 0.6178762444026438, 0.1246289712555339, 0.7554044083550030, 0.0951585116824928, 0.8656312023878318,
                         0.0622535239386479, 0.9445750230732326, 0.0271524594117541, 0.9894009349916499]
let gauss_24: f64[24] = [0.1279381953467522, 0.0640568928626056, 0.1258374563468283, 0.1911188674736163, 0.1216704729278034, 0.3150426796961634,
                         0.1155056680537256, 0.4337935076260451, 0.1074442701159656, 0.5454214713888396, 0.0976186521041139, 0.6480936519369755,
                         0.0861901615319533, 0.7401241915785544, 0.0733464814110803, 0.8200019859739029, 0.0592985849154368, 0.8864155270044011,
                         0.0442774388174198, 0.9382745520027328, 0.0285313886289337, 0.9747285559713095, 0.0123412297999872, 0.9951872199970213]

## A path segment as a cubic (lines and closes as straight cubics).
struct Bezier:
    var p0: Point = Point()
    var p1: Point = Point()
    var p2: Point = Point()
    var p3: Point = Point()

    func at(t: f64) -> Point:
        return cubic_point(self.p0, self.p1, self.p2, self.p3, t)

    ## The derivative at `t`.
    func tangent(t: f64) -> Point:
        let u = 1.0 - t
        let ax = 3.0 * u * u * (self.p1.x - self.p0.x) + 6.0 * u * t * (self.p2.x - self.p1.x) + 3.0 * t * t * (self.p3.x - self.p2.x)
        let ay = 3.0 * u * u * (self.p1.y - self.p0.y) + 6.0 * u * t * (self.p2.y - self.p1.y) + 3.0 * t * t * (self.p3.y - self.p2.y)
        return Point(ax, ay)

    ## The length of the control polygon, which the curve is no longer than.
    func rough_length() -> f64:
        let first = math.hypot(self.p1.x - self.p0.x, self.p1.y - self.p0.y)
        let second = math.hypot(self.p2.x - self.p1.x, self.p2.y - self.p1.y)
        return first + second + math.hypot(self.p3.x - self.p2.x, self.p3.y - self.p2.y)

    ## The part of the curve from `t0` to `t1`.
    func part(t0: f64, t1: f64) -> Bezier:
        let a = self.at(t0)
        let b = self.at(t1)
        let scale = (t1 - t0) * (1.0 / 3.0)
        let da = self.tangent(t0)
        let db = self.tangent(t1)
        return Bezier(p0 = a, p1 = Point(a.x + scale * da.x, a.y + scale * da.y), p2 = Point(b.x - scale * db.x, b.y - scale * db.y), p3 = b)

    ## The arc length, within `accuracy`, as kurbo measures it: Gauss-Legendre
    ## quadrature of 8, 16 or 24 points by an error estimate, halving the curve when
    ## none is close enough.
    func length(accuracy: f64, depth: usize = 0) -> f64:
        if depth == 0:
            # Curves of wild size are measured relative to their size, not to half a unit.
            let rough = self.rough_length()
            if not math.is_finite(rough):
                return rough
            if rough * 1e-9 > accuracy:
                return self.length(rough * 1e-9, 1)
        let d03 = Point(self.p3.x - self.p0.x, self.p3.y - self.p0.y)
        let d01 = Point(self.p1.x - self.p0.x, self.p1.y - self.p0.y)
        let d12 = Point(self.p2.x - self.p1.x, self.p2.y - self.p1.y)
        let d23 = Point(self.p3.x - self.p2.x, self.p3.y - self.p2.y)
        let polygon_excess = math.hypot(d01.x, d01.y) + math.hypot(d12.x, d12.y) + math.hypot(d23.x, d23.y) - math.hypot(d03.x, d03.y)
        let dd1 = Point(d12.x - d01.x, d12.y - d01.y)
        let dd2 = Point(d23.x - d12.x, d23.y - d12.y)
        let dm = Point(0.25 * (d01.x + d23.x) + 0.5 * d12.x, 0.25 * (d01.y + d23.y) + 0.5 * d12.y)
        let dm1 = Point(0.5 * (dd2.x + dd1.x), 0.5 * (dd2.y + dd1.y))
        let dm2 = Point(0.25 * (dd2.x - dd1.x), 0.25 * (dd2.y - dd1.y))
        var estimate = 0.0
        for i in 0..<(usize)8:
            let weight = gauss_8_full[i * 2]
            let x = gauss_8_full[i * 2 + 1]
            let dx = dm.x + dm1.x * x + dm2.x * x * x
            let dy = dm.y + dm1.y * x + dm2.y * x * x
            let ddx = dm1.x + dm2.x * 2.0 * x
            let ddy = dm1.y + dm2.y * 2.0 * x
            estimate += weight * ((ddx * ddx + ddy * ddy) / (dx * dx + dy * dy))
        let cube = estimate * estimate * estimate
        if math.min(cube * 2.5e-6, 3e-2) * polygon_excess < accuracy:
            return quadrature(gauss_8[0..<8], dm, dm1, dm2)
        if math.min(cube * cube * 1.5e-11, 9e-3) * polygon_excess < accuracy:
            return quadrature(gauss_16[0..<16], dm, dm1, dm2)
        if math.min(cube * cube * cube * 3.5e-16, 3.5e-3) * polygon_excess < accuracy or depth >= 20:
            return quadrature(gauss_24[0..<24], dm, dm1, dm2)
        let first = self.part(0.0, 0.5)
        let second = self.part(0.5, 1.0)
        return first.length(accuracy * 0.5, depth + 1) + second.length(accuracy * 0.5, depth + 1)

    ## The parameter `distance` along the curve falls at, as kurbo's inv_arclen finds
    ## it: an ITP root search on the length so far, to `accuracy`.
    func parameter(distance: f64, wanted: f64) -> f64:
        if distance <= 0.0:
            return 0.0
        let accuracy = math.max(wanted, self.rough_length() * 1e-9)
        let total = self.length(accuracy)
        if not math.is_finite(total):
            return 0.0
        if distance >= total:
            return 1.0
        var t_last = 0.0
        var length_last = 0.0
        let epsilon = accuracy / total
        let pieces = 1.0 - math.min(math.ceil(math.log2(epsilon)), 0.0)
        let inner = accuracy / pieces
        var a = 0.0
        var b = 1.0
        var ya = -distance
        var yb = total - distance
        let n_half = (usize)math.max(math.ceil(math.log2((b - a) / epsilon)) - 1.0, 0.0)
        var scaled = epsilon * math.pow(2.0, (f64)(1 + n_half))
        while b - a > 2.0 * epsilon:
            let middle = 0.5 * (a + b)
            let r = scaled - 0.5 * (b - a)
            let xf = (yb * a - ya * b) / (yb - ya)
            let sigma = middle - xf
            let delta = 0.2 * (b - a) * (b - a)
            let xt = xf + math.copysign(delta, sigma) if delta <= math.abs(middle - xf) else middle
            let x = xt if math.abs(xt - middle) <= r else middle - math.copysign(r, sigma)
            # The length to `x`, walked on from the last parameter measured.
            if x > t_last:
                length_last += self.part(t_last, x).length(inner)
            else:
                length_last -= self.part(x, t_last).length(inner)
            t_last = x
            let y = length_last - distance
            if y > 0.0:
                b = x
                yb = y
            elif y < 0.0:
                a = x
                ya = y
            else:
                return x
            scaled *= 0.5
        return 0.5 * (a + b)

## A quadrature of the curve whose derivative at its middle is `dm`, second
## derivative `dm1` and half third derivative `dm2`.
func quadrature(table: const f64[], dm: Point, dm1: Point, dm2: Point) -> f64:
    var total = 0.0
    for i in 0..<table.length // 2:
        let weight = table[i * 2]
        let x = table[i * 2 + 1]
        let cx = dm.x + dm2.x * x * x
        let cy = dm.y + dm2.y * x * x
        total += 1.5 * weight * (math.hypot(cx + dm1.x * x, cy + dm1.y * x) + math.hypot(cx - dm1.x * x, cy - dm1.y * x))
    return total

func straight(a: Point, b: Point) -> Bezier:
    return Bezier(p0 = a, p1 = Point(a.x + (b.x - a.x) * 0.33, a.y + (b.y - a.y) * 0.33), p2 = Point(a.x + (b.x - a.x) * 0.66, a.y + (b.y - a.y) * 0.66), p3 = b)

## The segments of `path` as cubics, into `out`.
func path_beziers(path: const Path*, out: List[Bezier]*) -> !:
    var at: usize = 0
    var start = Point()
    var current = Point()
    for verb in path.verbs.view():
        match verb:
            .move:
                start = path.points.items[at]
                current = start
                at += 1
            .line:
                try out.push(straight(current, path.points.items[at]))
                current = path.points.items[at]
                at += 1
            .cubic:
                try out.push(Bezier(p0 = current, p1 = path.points.items[at], p2 = path.points.items[at + 1], p3 = path.points.items[at + 2]))
                current = path.points.items[at + 2]
                at += 3
            .close:
                try out.push(straight(current, start))
                current = start

## The arc length of `path`, measured to half a unit.
func path_length(path: const Path*, accuracy: f64 = 0.5) -> f64:
    var beziers = List[Bezier]()
    defer beziers.release()
    path_beziers(path, &beziers) catch _:
        return 0.0
    var total = 0.0
    for b in beziers.view():
        total += b.length(accuracy)
    return total

## Place `clusters` along `path`; answer where the pen ends.
func place_on_path(content: const TextContent*, chunk: const TextChunk*, path: const Path*, clusters: Cluster[], fonts: GlyphSource) -> Point:
    # Lengths are measured to half a unit, finer where the text is scaled up.
    let accuracy = 0.5 / math.max(content.scale, 1.0)
    var source = fonts
    var beziers = List[Bezier]()
    defer beziers.release()
    path_beziers(path, &beziers) catch _:
        return Point()
    var lengths = List[f64]()
    defer lengths.release()
    for b in beziers.view():
        lengths.push(b.length(accuracy)) catch _:
            return Point()
    var width = 0.0
    for cluster in clusters:
        width += cluster.advance
    var advance = (chunk.x else 0.0) + chunk.start_offset + anchor_shift(chunk.anchor, width)
    var dy = 0.0
    var end = Point()
    for at in 0..<clusters.length:
        let position = content.positions.items[clusters[at].order]
        advance += position.dx
        let half = clusters[at].width * 0.5
        let offset = advance + half
        advance += clusters[at].advance
        # Find the segment the offset lies on.
        var found = false
        var walked = 0.0
        var point = Point()
        var angle = 0.0
        if offset >= 0.0:
            for segment in 0..<beziers.used:
                let length = lengths.items[segment]
                if offset >= walked and offset <= walked + length:
                    let b = beziers.items[segment]
                    let t = math.clamp(b.parameter(offset - walked, accuracy), 0.0, 1.0)
                    point = b.at(t)
                    let d = b.tangent(t)
                    angle = math.atan2(d.y, d.x) * 180.0 / math.pi
                    found = true
                    break
                walked += length
        if not found:
            clusters[at].visible = false
            continue
        clusters[at].shifted = true
        let original = clusters[at].transform
        var t = Matrix(e = point.x - half, f = point.y)
        t = multiply(t, multiply(multiply(Matrix(e = half), rotation_matrix(angle)), Matrix(e = -half)))
        dy += position.dy
        let span = content.spans.items[clusters[at].span]
        var shift = 0.0
        if let face = span.face:
            let metrics = source.face_metrics(face)
            shift = baseline_offset(&span, metrics, span.size / math.max(metrics.units_per_em, 1.0))
        if dy != 0.0 or shift != 0.0:
            t = multiply(t, Matrix(f = dy + shift))
        if position.rotate != 0.0:
            t = multiply(t, rotation_matrix(position.rotate))
        clusters[at].transform = multiply(t, original)
        end = Point(point.x + clusters[at].advance, point.y)
    return end