dymokomi/luce-svg
Source of release 0.9.2
#==============================================================================================
#
# svg/path - Paths: building, path data, bounds and transforms
#
# DESCRIPTION:
# A Path is a sequence of move, line, cubic and close verbs over points, the form
# every SVG shape becomes. Quadratic curves are raised to cubics and elliptical arcs
# are split into cubics of at most a quarter turn, so later stages see two kinds of
# segment. `parse_path_data` reads SVG path data with resvg's rules: relative
# commands, implicit line-tos after a move-to, reflected control points for S and
# T, an implicit move-to after a close, repeated closes dropped, and on an error
# everything up to it kept, as the specification asks. Bounds are tight: a curve
# counts its extrema, not its control points.
#
#==============================================================================================
## What a path does next: start a subpath at one point, draw a line to one point, draw a
## cubic curve through two control points to a third, or close the subpath.
pub enum Verb:
move
line
cubic
close
## A path: verbs and the points they use (move and line one each, cubic three, close
## none). It owns its storage; `release` frees it.
pub struct Path:
var verbs: List[Verb] = List[Verb]()
var points: List[Point] = List[Point]()
## Where the last move started its subpath, and whether a subpath is open.
var start: Point = Point()
var open: bool = false
## Free the path's storage; it is empty afterwards.
pub func release():
self.verbs.release()
self.points.release()
self.open = false
## How many verbs the path has.
pub func verb_count() -> usize:
return self.verbs.used
## Verb `index`.
pub func verb(index: usize) -> Verb:
return self.verbs.items[index]
## How many points the path has.
pub func point_count() -> usize:
return self.points.used
## Point `index` (in verb order).
pub func point(index: usize) -> Point:
return self.points.items[index]
## The current point: where the last verb ended.
pub func last_point() -> Point?:
if self.verbs.used == 0:
return none
if self.verbs.items[self.verbs.used - 1] == Verb.close:
return self.start
return self.points.items[self.points.used - 1]
## Start a subpath at (`x`, `y`). A move right after a move replaces it.
pub func move_to(x: f64, y: f64) -> !:
if self.verbs.used > 0 and self.verbs.items[self.verbs.used - 1] == Verb.move:
self.points.items[self.points.used - 1] = Point(x, y)
else:
try self.verbs.push(Verb.move)
try self.points.push(Point(x, y))
self.start = Point(x, y)
self.open = true
## Make sure a subpath is open, starting one where the last ended.
func ensure_open() -> !:
if not self.open:
let at = self.last_point() else Point()
try self.move_to(at.x, at.y)
## A line to (`x`, `y`).
pub func line_to(x: f64, y: f64) -> !:
try self.ensure_open()
try self.verbs.push(Verb.line)
try self.points.push(Point(x, y))
## A cubic curve through (`x1`, `y1`) and (`x2`, `y2`) to (`x`, `y`).
pub func cubic_to(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> !:
try self.ensure_open()
try self.verbs.push(Verb.cubic)
try self.points.push(Point(x1, y1))
try self.points.push(Point(x2, y2))
try self.points.push(Point(x, y))
## A quadratic curve through (`x1`, `y1`) to (`x`, `y`), stored as the same cubic.
pub func quad_to(x1: f64, y1: f64, x: f64, y: f64) -> !:
try self.ensure_open()
let origin = self.last_point() else Point()
try self.cubic_to(origin.x + (x1 - origin.x) * 2.0 / 3.0, origin.y + (y1 - origin.y) * 2.0 / 3.0,
x + (x1 - x) * 2.0 / 3.0, y + (y1 - y) * 2.0 / 3.0, x, y)
## An SVG elliptical arc from the current point to (`x`, `y`): radii `rx` and `ry`, the
## x axis turned `rotation` degrees, the large or small arc, swept positively or not.
## Radii too small to reach are scaled up; zero radii or coincident ends draw a line.
pub func arc_to(rx: f64, ry: f64, rotation: f64, large: bool, sweep: bool, x: f64, y: f64) -> !:
let origin = self.last_point() else return
try arc_segments(&self, origin, rx, ry, rotation, large, sweep, x, y)
## Close the current subpath; a close right after a close is dropped.
pub func close() -> !:
if self.verbs.used == 0 or self.verbs.items[self.verbs.used - 1] == Verb.close:
return
try self.verbs.push(Verb.close)
self.open = false
## A rectangle as one closed subpath.
pub func rect(x: f64, y: f64, width: f64, height: f64) -> !:
try self.move_to(x, y)
try self.line_to(x + width, y)
try self.line_to(x + width, y + height)
try self.line_to(x, y + height)
try self.close()
## The tight bounds of the path, or none when it has no points.
pub func bounds() -> Rect?:
return self.bounds_through(Matrix())
## The tight bounds of the path mapped through `transform`.
pub func bounds_through(transform: Matrix) -> Rect?:
if self.points.used == 0:
return none
var box = Box()
var at: usize = 0
var current = Point()
for verb in self.verbs.view():
match verb:
.move, .line:
current = apply(transform, self.points.items[at].x, self.points.items[at].y)
box.add(current)
at += 1
.cubic:
let p1 = apply(transform, self.points.items[at].x, self.points.items[at].y)
let p2 = apply(transform, self.points.items[at + 1].x, self.points.items[at + 1].y)
let p3 = apply(transform, self.points.items[at + 2].x, self.points.items[at + 2].y)
cubic_extrema(&box, current, p1, p2, p3)
current = p3
at += 3
.close:
continue
return box.rect()
## A copy of the path with every point mapped through `transform`.
pub func transformed(transform: Matrix) -> Path!:
var copy = Path()
errdefer copy.release()
for verb in self.verbs.view():
try copy.verbs.push(verb)
for p in self.points.view():
try copy.points.push(apply(transform, p.x, p.y))
copy.start = apply(transform, self.start.x, self.start.y)
copy.open = self.open
return copy
## A copy of the path.
pub func copy() -> Path!:
return try self.transformed(Matrix())
## A bounding box being grown point by point.
struct Box:
var low: Point = Point(math.infinity, math.infinity)
var high: Point = Point(-math.infinity, -math.infinity)
func add(p: Point):
self.low = Point(math.min(self.low.x, p.x), math.min(self.low.y, p.y))
self.high = Point(math.max(self.high.x, p.x), math.max(self.high.y, p.y))
func add_rect(r: Rect):
self.add(Point(r.x, r.y))
self.add(Point(r.x + r.w, r.y + r.h))
func empty() -> bool:
return self.low.x > self.high.x
func rect() -> Rect?:
if self.empty():
return none
return Rect(x = self.low.x, y = self.low.y, w = self.high.x - self.low.x, h = self.high.y - self.low.y)
## Grow `box` by the cubic from `p0` through `p1` and `p2` to `p3`: its ends and the
## points where it turns back on either axis.
func cubic_extrema(box: Box*, p0: Point, p1: Point, p2: Point, p3: Point):
box.add(p0)
box.add(p3)
for axis in 0..<(usize)2:
let a0 = p0.x if axis == 0 else p0.y
let a1 = p1.x if axis == 0 else p1.y
let a2 = p2.x if axis == 0 else p2.y
let a3 = p3.x if axis == 0 else p3.y
# The derivative's coefficients: a·t² + b·t + c.
let a = 3.0 * (-a0 + 3.0 * a1 - 3.0 * a2 + a3)
let b = 6.0 * (a0 - 2.0 * a1 + a2)
let c = 3.0 * (a1 - a0)
var roots: f64[2] = [-1.0, -1.0]
if math.abs(a) < 1e-12:
if math.abs(b) > 1e-12:
roots[0] = -c / b
else:
let discriminant = b * b - 4.0 * a * c
if discriminant >= 0.0:
let root = math.sqrt(discriminant)
roots[0] = (-b + root) / (2.0 * a)
roots[1] = (-b - root) / (2.0 * a)
for t in roots:
if t > 0.0 and t < 1.0:
box.add(cubic_point(p0, p1, p2, p3, t))
## The point at `t` along a cubic.
func cubic_point(p0: Point, p1: Point, p2: Point, p3: Point, t: f64) -> Point:
let u = 1.0 - t
let a = u * u * u
let b = 3.0 * u * u * t
let c = 3.0 * u * t * t
let d = t * t * t
return Point(a * p0.x + b * p1.x + c * p2.x + d * p3.x, a * p0.y + b * p1.y + c * p2.y + d * p3.y)
# mark: Arcs ==================================================================================
## Append the cubics of an SVG arc from `origin` to (`x`, `y`) to `path`.
func arc_segments(path: Path*, origin: Point, rx_in: f64, ry_in: f64, rotation: f64, large: bool, sweep: bool, x: f64, y: f64) -> !:
var rx = math.abs(rx_in)
var ry = math.abs(ry_in)
if rx < 1e-12 or ry < 1e-12 or (origin.x == x and origin.y == y):
try path.line_to(x, y)
return
let phi = rotation * math.pi / 180.0
let cos_phi = math.cos(phi)
let sin_phi = math.sin(phi)
let dx = (origin.x - x) * 0.5
let dy = (origin.y - y) * 0.5
let x1p = cos_phi * dx + sin_phi * dy
let y1p = -sin_phi * dx + cos_phi * dy
let lambda = x1p * x1p / (rx * rx) + y1p * y1p / (ry * ry)
if lambda > 1.0:
let scale = math.sqrt(lambda)
rx *= scale
ry *= scale
let numerator = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p
let denominator = rx * rx * y1p * y1p + ry * ry * x1p * x1p
var factor = math.sqrt(numerator / denominator) if numerator > 0.0 and denominator > 0.0 else 0.0
if large == sweep:
factor = -factor
let cxp = factor * rx * y1p / ry
let cyp = -factor * ry * x1p / rx
let cx = cos_phi * cxp - sin_phi * cyp + (origin.x + x) * 0.5
let cy = sin_phi * cxp + cos_phi * cyp + (origin.y + y) * 0.5
let start = math.atan2((y1p - cyp) / ry, (x1p - cxp) / rx)
var delta = math.atan2((-y1p - cyp) / ry, (-x1p - cxp) / rx) - start
if sweep and delta < 0.0:
delta += math.tau
elif not sweep and delta > 0.0:
delta -= math.tau
# As many pieces as kurbo cuts for a tenth of a unit's tolerance (at least four a turn),
# so marker vertices fall where resvg puts them.
let per_turn = math.max(3.999999, math.pow(1.1163 * math.max(rx, ry) / 0.1, 1.0 / 6.0))
# (Held to a thousand pieces for arcs of wild size, NaN as one.)
let wanted = math.ceil(per_turn * math.abs(delta) / math.tau)
let pieces = (i64)math.clamp(wanted, 1.0, 1000.0) if wanted == wanted else 1
let step = delta / (f64)pieces
let k = 4.0 / 3.0 * math.tan(step / 4.0)
var angle = start
for piece in 0..<pieces:
let a0 = angle
let a1 = angle + step
let c0 = math.cos(a0)
let s0 = math.sin(a0)
let c1 = math.cos(a1)
let s1 = math.sin(a1)
# The unit-circle control points, then the ellipse's scale, rotation and centre.
let q1 = arc_point(cx, cy, rx, ry, cos_phi, sin_phi, c0 - k * s0, s0 + k * c0)
let q2 = arc_point(cx, cy, rx, ry, cos_phi, sin_phi, c1 + k * s1, s1 - k * c1)
var q3 = arc_point(cx, cy, rx, ry, cos_phi, sin_phi, c1, s1)
if piece == pieces - 1:
q3 = Point(x, y)
try path.cubic_to(q1.x, q1.y, q2.x, q2.y, q3.x, q3.y)
angle = a1
func arc_point(cx: f64, cy: f64, rx: f64, ry: f64, cos_phi: f64, sin_phi: f64, u: f64, v: f64) -> Point:
let ex = rx * u
let ey = ry * v
return Point(cx + cos_phi * ex - sin_phi * ey, cy + sin_phi * ex + cos_phi * ey)
# mark: Path data =============================================================================
## Read SVG path data `text` into `path`. Data after an error is ignored, as SVG asks;
## answers whether the whole text was read.
pub func parse_path_data(text: str, path: Path*) -> bool!:
var scanner = Scanner(data = text.bytes)
var command: u8 = 0
# Where the current point and the subpath start are, and the last segment's control
# point for S and T (with which kind of segment it came origin).
var current = Point()
var subpath = Point()
var control = Point()
var control_kind: u8 = 0
var closed = false
var first = true
while true:
scanner.skip_spaces()
if scanner.at_end():
return true
let byte = scanner.peek()
var implicit = false
if is_alpha(byte):
command = byte
scanner.pos += 1
elif (is_digit(byte) or byte == '-' or byte == '+' or byte == '.') and command != 0:
if command == 'Z' or command == 'z':
return false
implicit = true
else:
return false
if first and command != 'M' and command != 'm':
return false
first = false
if implicit and (command == 'M' or command == 'm'):
command = 'L' if command == 'M' else 'l'
let relative = command >= 'a' and command <= 'z'
let lower = command + 32 if command >= 'A' and command <= 'Z' else command
# After a close, any command but a move starts again where the subpath began.
if closed and lower != 'm' and lower != 'z':
try path.move_to(subpath.x, subpath.y)
let base = current
var kind: u8 = 0
if lower == 'm':
var x = scanner.list_number() else return false
var y = scanner.list_number() else return false
if relative:
x += base.x
y += base.y
try path.move_to(x, y)
current = Point(x, y)
subpath = current
elif lower == 'l' or lower == 'h' or lower == 'v':
var x = current.x
var y = current.y
if lower == 'l':
x = scanner.list_number() else return false
y = scanner.list_number() else return false
if relative:
x += base.x
y += base.y
elif lower == 'h':
x = scanner.list_number() else return false
if relative:
x += base.x
else:
y = scanner.list_number() else return false
if relative:
y += base.y
try path.line_to(x, y)
current = Point(x, y)
elif lower == 'c' or lower == 's':
var p1 = current
if lower == 'c':
p1.x = scanner.list_number() else return false
p1.y = scanner.list_number() else return false
if relative:
p1 = Point(p1.x + base.x, p1.y + base.y)
elif control_kind == 'c':
p1 = Point(2.0 * current.x - control.x, 2.0 * current.y - control.y)
var p2 = Point()
p2.x = scanner.list_number() else return false
p2.y = scanner.list_number() else return false
var p3 = Point()
p3.x = scanner.list_number() else return false
p3.y = scanner.list_number() else return false
if relative:
p2 = Point(p2.x + base.x, p2.y + base.y)
p3 = Point(p3.x + base.x, p3.y + base.y)
try path.cubic_to(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)
control = p2
kind = 'c'
current = p3
elif lower == 'q' or lower == 't':
var p1 = current
if lower == 'q':
p1.x = scanner.list_number() else return false
p1.y = scanner.list_number() else return false
if relative:
p1 = Point(p1.x + base.x, p1.y + base.y)
elif control_kind == 'q':
p1 = Point(2.0 * current.x - control.x, 2.0 * current.y - control.y)
var p2 = Point()
p2.x = scanner.list_number() else return false
p2.y = scanner.list_number() else return false
if relative:
p2 = Point(p2.x + base.x, p2.y + base.y)
try path.quad_to(p1.x, p1.y, p2.x, p2.y)
control = p1
kind = 'q'
current = p2
elif lower == 'a':
let rx = scanner.list_number() else return false
let ry = scanner.list_number() else return false
let rotation = scanner.list_number() else return false
let large = arc_flag(&scanner) else return false
let sweep = arc_flag(&scanner) else return false
var x = scanner.list_number() else return false
var y = scanner.list_number() else return false
if relative:
x += base.x
y += base.y
try path.arc_to(rx, ry, rotation, large, sweep, x, y)
current = Point(x, y)
elif lower == 'z':
try path.close()
current = subpath
else:
return false
control_kind = kind
closed = lower == 'z'
## An arc flag: a single `0` or `1`, which needs no separator after it.
func arc_flag(scanner: Scanner*) -> bool?:
scanner.skip_spaces()
let byte = scanner.peek()
if byte != '0' and byte != '1':
return none
scanner.pos += 1
scanner.skip_separator()
return byte == '1'
## The points of a `points` attribute as a path: a move, then lines; an odd last number
## is ignored and reading stops at the first error. None with fewer than two points.
pub func parse_points(text: str, close: bool) -> Path?!:
var path = Path()
errdefer path.release()
var scanner = Scanner(data = text.bytes)
var count: usize = 0
while true:
scanner.skip_spaces()
if scanner.at_end():
break
let x = scanner.list_number() else break
let y = scanner.list_number() else break
if count == 0:
try path.move_to(x, y)
else:
try path.line_to(x, y)
count += 1
if count < 2:
path.release()
return none
if close:
try path.close()
return path