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