8000 go-stuff/curve/bezpath.go at main · dominikh/go-stuff · GitHub
[go: up one dir, main page]
Skip to content

bezpath.go

Latest commit

 

History

History
1079 lines (985 loc) · 28.4 KB

bezpath.go

File metadata and controls

1079 lines (985 loc) · 28.4 KB
Raw
// SPDX-FileCopyrightText: 2018 Raph Levien
// SPDX-FileCopyrightText: 2024 Dominik Honnef and contributors
//
// SPDX-License-Identifier: MIT
// SPDX-FileAttributionText: https://github.com/linebender/kurbo
package curve
import (
"fmt"
"io"
"iter"
"math"
"honnef.co/go/stuff/container/maybe"
"honnef.co/go/stuff/math/polyroot"
)
//go:generate go tool stringer -type=PathElementKind
type PathElementKind int
const (
// Move directly to the point without drawing anything, starting a new
// subpath.
MoveToKind PathElementKind = iota + 1
// Draw a line from the current location to the point.
LineToKind
// Draw a quadratic bezier using the current location and the two points.
QuadToKind
// Draw a cubic bezier using the current location and the three points.
CubicToKind
// Close off the path.
ClosePathKind
)
// PathElement describes an element of a Bézier path. Different kinds of path
// elements use different numbers of points.
type PathElement struct {
Kind PathElementKind
P0 Point
P1 Point
P2 Point
}
func (el PathElement) String() string {
switch el.Kind {
case MoveToKind:
return fmt.Sprintf("MoveTo(%s)", el.P0)
case LineToKind:
return fmt.Sprintf("LineTo(%s)", el.P0)
case QuadToKind:
return fmt.Sprintf("QuadTo(%s, %s)", el.P0, el.P1)
case CubicToKind:
return fmt.Sprintf("CubicTo(%s, %s, %s)", el.P0, el.P1, el.P2)
case ClosePathKind:
return "ClosePath()"
default:
return fmt.Sprintf("InvalidPathElement(%s, %s, %s)", el.P0, el.P1, el.P2)
}
}
func (el PathElement) Transform(aff Affine) PathElement {
switch el.Kind {
case MoveToKind:
return MoveTo(el.P0.Transform(aff))
case LineToKind:
return LineTo(el.P0.Transform(aff))
case QuadToKind:
return QuadTo(el.P0.Transform(aff), el.P1.Transform(aff))
case CubicToKind:
return CubicTo(el.P0.Transform(aff), el.P1.Transform(aff), el.P2.Transform(aff))
case ClosePathKind:
return ClosePath()
default:
return PathElement{}
}
}
func (el PathElement) IsInf() bool {
return el.P0.IsInf() ||
el.P1.IsInf() ||
el.P2.IsInf()
}
func (el PathElement) IsNaN() bool {
return el.P0.IsNaN() ||
el.P1.IsNaN() ||
el.P2.IsNaN()
}
func MoveTo(pt Point) PathElement {
return PathElement{Kind: MoveToKind, P0: pt}
}
func LineTo(pt Point) PathElement {
return PathElement{Kind: LineToKind, P0: pt}
}
func QuadTo(p0, p1 Point) PathElement {
return PathElement{Kind: QuadToKind, P0: p0, P1: p1}
}
func CubicTo(p0, p1, p2 Point) PathElement {
return PathElement{Kind: CubicToKind, P0: p0, P1: p1, P2: p2}
}
func ClosePath() PathElement {
return PathElement{Kind: ClosePathKind}
}
type PathSegmentKind int
const (
// A line segment.
LineKind PathSegmentKind = iota + 1
// A quadratic Bézier segment.
QuadKind
// A cubic Bézier segment.
CubicKind
)
// PathSegment represents a segment of a Bézier path. This type acts as a sort of tagged
// union representing all possible path segments ([Path], [QuadBez], and [CubicBez]).
type PathSegment struct {
// We don't use an interface for PathSegment because we want {Line, Quad,
// Cubic}.Transform to return their respective types, not PathSegment. But we cannot
// encode that in Go interfaces.
//
// This also avoids having to allocate for path segments.
Kind PathSegmentKind
P0 Point
P1 Point
P2 Point
P3 Point
}
// BoundingBox implements Shape.
func (seg PathSegment) BoundingBox() Rect {
switch seg.Kind {
case LineKind:
return seg.Line().BoundingBox()
case QuadKind:
return seg.Quad().BoundingBox()
case CubicKind:
return seg.Cubic().BoundingBox()
default:
return Rect{}
}
}
// Path implements Shape.
func (seg PathSegment) Path(tolerance float64, out BezPath) BezPath {
out.MoveTo(seg.P0)
switch seg.Kind {
case LineKind:
out.LineTo(seg.P1)
case QuadKind:
out.QuadTo(seg.P1, seg.P2)
case CubicKind:
out.CubicTo(seg.P1, seg.P2, seg.P3)
}
return out
}
var _ Shape = PathSegment{}
var _ ParametricCurve = PathSegment{}
// Line returns the line represented by this segment. This is only valid when Kind ==
// LineKind.
func (seg PathSegment) Line() Line { return Line{seg.P0, seg.P1} }
// Quad returns the quadratic Bézier represented by this segment. This is only valid when Kind ==
// QuadKind.
func (seg PathSegment) Quad() QuadBez { return QuadBez{seg.P0, seg.P1, seg.P2} }
// Cubic converts seg to a cubic Bézier. This is valid for any Kind.
func (seg PathSegment) Cubic() CubicBez {
switch seg.Kind {
case LineKind:
p0 := seg.P0
p1 := seg.P1
return CubicBez{p0, p0, p1, p1}
case QuadKind:
return seg.Quad().Raise()
case CubicKind:
return CubicBez{seg.P0, seg.P1, seg.P2, seg.P3}
default:
return CubicBez{}
}
}
func (seg PathSegment) Transform(aff Affine) PathSegment {
return PathSegment{
Kind: seg.Kind,
P0: seg.P0.Transform(aff),
P1: seg.P0.Transform(aff),
P2: seg.P0.Transform(aff),
P3: seg.P0.Transform(aff),
}
}
func (seg PathSegment) IsInf() bool {
return seg.P0.IsInf() || seg.P1.IsInf() || seg.P2.IsInf() || seg.P3.IsInf()
}
func (seg PathSegment) IsNaN() bool {
return seg.P0.IsNaN() || seg.P1.IsNaN() || seg.P2.IsNaN() || seg.P3.IsNaN()
}
func (seg PathSegment) Eval(t float64) Point {
switch seg.Kind {
case LineKind:
return seg.Line().Eval(t)
case QuadKind:
return seg.Quad().Eval(t)
case CubicKind:
return seg.Cubic().Eval(t)
default:
return Point{}
}
}
func (seg PathSegment) Subsegment(start, end float64) PathSegment {
switch seg.Kind {
case LineKind:
return seg.Line().Subsegment(start, end).Seg()
case QuadKind:
return seg.Quad().Subsegment(start, end).Seg()
case CubicKind:
return seg.Cubic().Subsegment(start, end).Seg()
default:
return PathSegment{}
}
}
func (seg PathSegment) Start() Point {
return seg.Eval(0)
}
func (seg PathSegment) End() Point {
return seg.Eval(1)
}
func (seg PathSegment) SubsegmentCurve(start, end float64) ParametricCurve {
return seg.Subsegment(start, end)
}
func (seg PathSegment) Subdivide() (PathSegment, PathSegment) {
return seg.Subsegment(0.0, 0.5), seg.Subsegment(0.5, 1.0)
}
func (seg PathSegment) SubdivideCurve() (ParametricCurve, ParametricCurve) {
return seg.Subdivide()
}
func (seg PathSegment) PathLength(accuracy float64) float64 {
switch seg.Kind {
case LineKind:
return seg.Line().PathLength(accuracy)
case QuadKind:
return seg.Quad().PathLength(accuracy)
case CubicKind:
return seg.Cubic().PathLength(accuracy)
default:
return 0
}
}
func (seg PathSegment) SolveForPathLength(arclen, accuracy float64) float64 {
switch seg.Kind {
case LineKind:
return SolveForPathLength(seg.Line(), arclen, accuracy)
case QuadKind:
return SolveForPathLength(seg.Quad(), arclen, accuracy)
case CubicKind:
return SolveForPathLength(seg.Cubic(), arclen, accuracy)
default:
return 0
}
}
func (seg PathSegment) Area() float64 {
switch seg.Kind {
case LineKind:
return seg.Line().Area()
case QuadKind:
return seg.Quad().Area()
case CubicKind:
return seg.Cubic().Area()
default:
return 0
}
}
func (seg PathSegment) Nearest(pt Point, accuracy float64) (distSq, t float64) {
switch seg.Kind {
case LineKind:
return seg.Line().Nearest(pt, accuracy)
case QuadKind:
return seg.Quad().Nearest(pt, accuracy)
case CubicKind:
return seg.Cubic().Nearest(pt, accuracy)
default:
return 0, 0
}
}
func (seg PathSegment) Extrema() ([MaxExtrema]float64, int) {
switch seg.Kind {
case LineKind:
return seg.Line().Extrema()
case QuadKind:
return seg.Quad().Extrema()
case CubicKind:
return seg.Cubic().Extrema()
default:
return [MaxExtrema]float64{}, 0
}
}
// PathElement returns the PathElement corresponding to the segment, discarding the
// segment's starting point.
func (seg PathSegment) PathElement() PathElement {
switch seg.Kind {
case LineKind:
return LineTo(seg.Line().P1)
case QuadKind:
return QuadTo(seg.Quad().P1, seg.Quad().P2)
case CubicKind:
return CubicTo(seg.Cubic().P1, seg.Cubic().P2, seg.Cubic().P3)
default:
return PathElement{}
}
}
// Reverse returns a new PathSegment describing the same path as this one, but with the
// points reversed.
func (seg PathSegment) Reverse() PathSegment {
switch seg.Kind {
case LineKind:
seg.P0, seg.P1 = seg.P1, seg.P0
return seg
case QuadKind:
seg.P0, seg.P2 = seg.P2, seg.P0
return seg
case CubicKind:
seg.P0, seg.P1, seg.P2, seg.P3 = seg.P3, seg.P2, seg.P1, seg.P0
return seg
default:
return PathSegment{}
}
}
// Assumes split at extrema.
func (seg PathSegment) windingInner(pt Point) int {
start := seg.Eval(0)
end := seg.Eval(1)
var sign int
if end.Y > start.Y {
if pt.Y < start.Y || pt.Y >= end.Y {
return 0
}
sign = -1
} else if end.Y < start.Y {
if pt.Y < end.Y || pt.Y >= start.Y {
return 0
}
sign = 1
} else {
return 0
}
switch seg.Kind {
case LineKind:
if pt.X < min(start.X, end.X) {
return 0
}
if pt.X >= max(start.X, end.X) {
return sign
}
// line equation ax + by = c
a := end.Y - start.Y
b := start.X - end.X
c := a*start.X + b*start.Y
if (a*pt.X+b*pt.Y-c)*float64(sign) <= 0.0 {
return sign
} else {
return 0
}
case QuadKind:
quad := seg.Quad()
p1 := quad.P1
if pt.X < min(start.X, end.X, p1.X) {
return 0
}
if pt.X >= max(start.X, end.X, p1.X) {
return sign
}
a := end.Y - 2.0*p1.Y + start.Y
b := 2.0 * (p1.Y - start.Y)
c := start.Y - pt.Y
solution := polyroot.NewPolynomial(c, b, a).Roots(0, 1, 0, nil)
for _, t := range solution {
x := quad.Eval(t).X
if pt.X >= x {
return sign
} else {
return 0
}
}
return 0
case CubicKind:
cubic := seg.Cubic()
p1 := cubic.P1
p2 := cubic.P2
if pt.X < min(start.X, end.X, p1.X, p2.X) {
return 0
}
if pt.X >= max(start.X, end.X, p1.X, p2.X) {
return sign
}
a := end.Y - 3.0*p2.Y + 3.0*p1.Y - start.Y
b := 3.0 * (p2.Y - 2.0*p1.Y + start.Y)
c := 3.0 * (p1.Y - start.Y)
d := start.Y - pt.Y
solution := polyroot.NewPolynomial(d, c, b, a).Roots(0, 1, 0, nil)
for _, t := range solution {
x := cubic.Eval(t).X
if pt.X >= x {
return sign
} else {
return 0
}
}
return 0
default:
return 0
}
}
// Winding computes the winding number contribution of a single segment.
//
// It casts a ray to the left and counts intersections.
func (seg PathSegment) Winding(pt Point) int {
exs, n := ExtremaRanges(seg)
var w int
for _, ex := range exs[:n] {
w += seg.Subsegment(ex[0], ex[1]).windingInner(pt)
}
return w
}
// LineIntersection describes the intersection of a [Line] and a [PathSegment].
//
// This can be generated with [PathSegment.IntersectLine].
type LineIntersection struct {
// The "time" that the intersection occurs, on the line.
//
// This value is in the range [0, 1].
LineT float64
// The "time" that the intersection occurs, on the path segment.
//
// This value is nominally in the range [0, 1], although it may slightly exceed
// that range at the boundaries of segments.
SegmentT float64
}
func (li LineIntersection) IsInf() bool {
return math.IsInf(li.LineT, 0) || math.IsInf(li.SegmentT, 0)
}
func (li LineIntersection) IsNaN() bool {
return math.IsNaN(li.LineT) || math.IsNaN(li.SegmentT)
}
// IntersectLine computes intersections against a line.
//
// It returns up to three intersections and the number of intersections. For
// each intersection, the t value of the segment and line are given.
//
// Note: This test is designed to be inclusive of points near the endpoints
// of the segment. This is so that testing a line against multiple
// contiguous segments of a path will be guaranteed to catch at least one
// of them. In such cases, use higher level logic to coalesce the hits
// (the t value may be slightly outside the range of [0, 1]).
func (seg PathSegment) IntersectLine(line Line) ([3]LineIntersection, int) {
switch seg.Kind {
case LineKind:
return seg.Line().IntersectLine(line)
case QuadKind:
return seg.Quad().IntersectLine(line)
case CubicKind:
return seg.Cubic().IntersectLine(line)
default:
return [3]LineIntersection{}, 0
}
}
// MinDistance encodes the minimum distance between two Bézier curves, as returned by
// [PathSegment.MinDist].
type MinDistance struct {
// The shortest distance between any two points on the two curves.
Distance float64
// The position of the nearest point on the first curve, as a parameter.
T1 float64
// The position of the nearest point on the second curve, as a parameter.
T2 float64
}
func (seg PathSegment) vec2s() ([4]Vec2, int) {
switch seg.Kind {
case LineKind:
return [4]Vec2{
Vec2(seg.P0),
Vec2(seg.P1),
}, 2
case QuadKind:
return [4]Vec2{
Vec2(seg.P0),
Vec2(seg.P1),
Vec2(seg.P2),
}, 3
case CubicKind:
return [4]Vec2{
Vec2(seg.P0),
Vec2(seg.P1),
Vec2(seg.P2),
Vec2(seg.P3),
}, 4
default:
return [4]Vec2{}, 0
}
}
// MinDist returns the minimum distance between two path segments.
func (seg PathSegment) MinDist(other PathSegment, accuracy float64) MinDistance {
vecs1, n1 := seg.vec2s()
vecs2, n2 := other.vec2s()
ret := minDistParam(
vecs1[:n1],
vecs2[:n2],
[2]float64{0.0, 1.0},
[2]float64{0.0, 1.0},
accuracy,
math.Inf(1),
)
distance, t1, t2 := ret[0], ret[1], ret[2]
return MinDistance{
Distance: math.Sqrt(distance),
T1: t1,
T2: t2,
}
}
// Tangents returns the endpoint tangents of a path segment.
//
// This version is robust to the path segment not being a regular curve.
func (seg PathSegment) Tangents() (Vec2, Vec2) {
switch seg.Kind {
case LineKind:
return seg.Line().Tangents()
case QuadKind:
return seg.Quad().Tangents()
case CubicKind:
return seg.Cubic().Tangents()
default:
panic(fmt.Sprintf("invalid PathSegment kind %v", seg.Kind))
}
}
// BezPath describes a Bézier path.
//
// These docs assume basic familiarity with Bézier curves; for an introduction,
// see Pomax's wonderful [A Primer on Bézier Curves].
//
// This path can contain lines, quadratics ([QuadBez]) and cubics
// ([CubicBez]), and may contain multiple subpaths.
//
// # Elements and Segments
//
// A Bézier path can be represented in terms of either elements ([PathElement])
// or segments ([PathSegment]). Elements map closely to how Béziers are
// generally used in PostScript-style drawing APIs; they can be thought of as
// instructions for drawing the path. Segments more directly describe the
// path itself, with each segment being an independent line or curve.
//
// These different representations are useful in different contexts.
// For tasks like drawing, elements are a natural fit, but when doing
// hit-testing or subdividing, we need to have access to the segments.
//
// Conceptually, a BezPath contains zero or more subpaths. Each subpath
// always begins with a MoveTo, then has zero or more LineTo, QuadTo,
// and CurveTo elements, and optionally ends with a ClosePath.
//
// [A Primer on Bézier Curves]: https://pomax.github.io/bezierinfo/
type BezPath []PathElement
var _ Shape = BezPath{}
func (p BezPath) Path(tolerance float64, out BezPath) BezPath { return append(out, p...) }
// Transform returns a new path with an affine transformation to the path. See
// [BezPath.ApplyTransform] for a version that modifies the path in-place.
func (p BezPath) Transform(aff Affine) BezPath {
els := make([]PathElement, len(p))
for i := range p {
els[i] = p[i].Transform(aff)
}
return els
}
// Pop removes and returns the last element in the path. If the path contains no more
// elements, false is returned.
func (p *BezPath) Pop() (PathElement, bool) {
if len(*p) == 0 {
return PathElement{}, false
}
el := (*p)[len(*p)-1]
*p = (*p)[:len(*p)-1]
return el, true
}
// Push adds an element to the path.
func (p *BezPath) Push(el PathElement) {
*p = append(*p, el)
}
// MoveTo adds a "move to" element to the path.
func (p *BezPath) MoveTo(pt Point) { p.Push(MoveTo(pt)) }
// LineTo adds a "line to" element to the path.
//
// If called immediately after [BezPath.ClosePath] then the current
// subpath starts at the initial point of the previous subpath.
func (p *BezPath) LineTo(pt Point) { p.Push(LineTo(pt)) }
// QuadTo adds a "quad to" element to the path.
//
// If called immediately after [BezPath.ClosePath] then the current
// subpath starts at the initial point of the previous subpath.
func (p *BezPath) QuadTo(p1, p2 Point) { p.Push(QuadTo(p1, p2)) }
// Push a "curve to" element onto the path.
//
// If called immediately after [BezPath.ClosePath] then the current
// subpath starts at the initial point of the previous subpath.
func (p *BezPath) CubicTo(p1, p2, p3 Point) { p.Push(CubicTo(p1, p2, p3)) }
// Push a "close path" element onto the path.
func (p *BezPath) ClosePath() { p.Push(ClosePath()) }
// Truncate truncates the path, keeping the first n elements.
func (p *BezPath) Truncate(n int) {
if n >= len(*p) {
return
}
*p = (*p)[:n]
}
func (p BezPath) Area() float64 {
return SegmentsArea(p.Segments())
}
func (p BezPath) PathLength(accuracy float64) float64 {
return SegmentsPerimeter(p.Segments(), accuracy)
}
func (p BezPath) Winding(pt Point) int {
return SegmentsWinding(p.Segments(), pt)
}
func (p BezPath) BoundingBox() Rect {
return SegmentsBoundingBox(p.Segments())
}
// Segment returns the segment at the given element index, if any.
//
// If you need to access all segments, [BezPath.Segments] provides a better
// API. This function is intended for random access of specific elements, for clients
// that require this specifically.
//
// This returns the segment that ends at the provided element
// index. In effect this means it is 1-indexed: since no segment ends at
// the first element (which is presumed to be a [MoveTo]) Segment(0) will
// always return false.
func (p BezPath) Segment(idx int) (PathSegment, bool) {
if idx == 0 || idx >= len(p) {
return PathSegment{}, false
}
var last Point
switch prev := p[idx-1]; prev.Kind {
case MoveToKind:
last = prev.P0
case LineToKind:
last = prev.P0
case QuadToKind:
last = prev.P1
case CubicToKind:
last = prev.P2
default:
return PathSegment{}, false
}
switch el := p[idx]; el.Kind {
case LineToKind:
return Line{last, el.P0}.Seg(), true
case QuadToKind:
return QuadBez{last, el.P0, el.P1}.Seg(), true
case CubicToKind:
return CubicBez{last, el.P0, el.P1, el.P2}.Seg(), true
case ClosePathKind:
for i := idx - 1; i >= 0; i-- {
el := p[i]
if el.Kind == MoveToKind && el.P0 != last {
return Line{last, el.P0}.Seg(), true
}
}
return PathSegment{}, false
default:
return PathSegment{}, false
}
}
// HasSegments reports whether the path contains any segments. A path that consists only
// of MoveTo and ClosePath elements has no segments.
func (p BezPath) HasSegments() bool {
for i := range p {
el := p[i]
if el.Kind != MoveToKind && el.Kind != ClosePathKind {
return true
}
}
return false
}
// ApplyTransform destructively applies an affine transformation to the path. See
// [BezPath.Transform] for a version that returns a new path instead.
func (p *BezPath) ApplyTransform(aff Affine) {
for i := range *p {
(*p)[i] = (*p)[i].Transform(aff)
}
}
func (p BezPath) IsInf() bool {
for i := range p {
if p[i].IsInf() {
return true
}
}
return false
}
func (p BezPath) IsNaN() bool {
for i := range p {
if p[i].IsNaN() {
return true
}
}
return false
}
// ControlBox returns a rectangle that conservatively encloses the path.
//
// Unlike [BezPath.BoundingBox], this uses control points directly rather than computing
// tight bounds for curve elements.
func (p BezPath) ControlBox() Rect {
cbox := Rect{1, 1, 0, 0}
for i := range p {
el := p[i]
switch el.Kind {
case MoveToKind, LineToKind:
cbox = cbox.UnionPoint(el.P0)
case QuadToKind:
cbox = cbox.UnionPoint(el.P0)
cbox = cbox.UnionPoint(el.P1)
case CubicToKind:
cbox = cbox.UnionPoint(el.P0)
cbox = cbox.UnionPoint(el.P1)
cbox = cbox.UnionPoint(el.P2)
case ClosePathKind:
}
}
return cbox
}
// SVG converts the path to an SVG path string representation.
//
// The current implementation doesn't take any special care to produce a
// short string (reducing precision, using relative movement).
func (p BezPath) SVG(opts SVGOptions) string {
return SVG(p, opts)
}
func (p BezPath) WriteSVG(w io.Writer, opts SVGOptions) error {
return WriteSVG(w, p, opts)
}
// ReverseSubpaths returns a new path with the winding direction of all subpaths
// reversed.
func (p BezPath) ReverseSubpaths(out BezPath) BezPath {
elements := p
startIdx := 1
startPt := Point{}
reversed := out
// Pending move is used to capture degenerate subpaths that should
// remain in the reversed output.
pendingMove := false
for ix, el := range elements {
switch el.Kind {
case MoveToKind:
pt := el.P0
if pendingMove {
reversed.Push(MoveTo(startPt))
}
if startIdx < ix {
reverseSubpath(startPt, elements[startIdx:ix], &reversed)
}
pendingMove = true
startPt = pt
startIdx = ix + 1
case ClosePathKind:
if startIdx <= ix {
reverseSubpath(startPt, elements[startIdx:ix], &reversed)
}
reversed.Push(ClosePath())
startIdx = ix + 1
pendingMove = false
default:
pendingMove = false
}
}
if startIdx < len(elements) {
reverseSubpath(startPt, elements[startIdx:], &reversed)
} else if pendingMove {
reversed.Push(MoveTo(startPt))
}
return reversed
}
// EndPoint returns the end point of the path element, or false if none exists. It exists
// for all kinds except for [ClosePathKind].
func (el PathElement) EndPoint() (Point, bool) {
switch el.Kind {
case MoveToKind:
return el.P0, true
case LineToKind:
return el.P0, true
case QuadToKind:
return el.P1, true
case CubicToKind:
return el.P2, true
default:
return Point{}, false
}
}
// Helper for reversing a subpath.
//
// The els parameter must not contain any MoveTo or ClosePath elements.
func reverseSubpath(startPt Point, els []PathElement, reversed *BezPath) {
var endPt Point
if len(els) > 0 {
endPt, _ = els[len(els)-1].EndPoint()
} else {
endPt = startPt
}
reversed.Push(MoveTo(endPt))
for ix := len(els) - 1; ix >= 0; ix-- {
el := &els[ix]
var endPt Point
if ix > 0 {
endPt, _ = els[ix-1].EndPoint()
} else {
endPt = startPt
}
switch el.Kind {
case LineToKind:
reversed.Push(LineTo(endPt))
case QuadToKind:
reversed.Push(QuadTo(el.P0, endPt))
case CubicToKind:
reversed.Push(CubicTo(el.P1, el.P0, endPt))
default:
panic("reverseSubpath expects MoveTo and ClosePath to be removed")
}
}
}
// Flatten flattens a sequence of arbitrary path elements to a sequence of lines that
// approximate the original curve.
//
// The tolerance value controls the maximum distance between the curved input
// segments and their polyline approximations. (In technical terms, this is the
// [Hausdorff distance]). The algorithm attempts to bound this distance
// by tolerance but this is not absolutely guaranteed. The appropriate value
// depends on the use, but for antialiased rendering, a value of 0.25 has been
// determined to give good results. The number of segments tends to scale as the
// inverse square root of tolerance.
//
// This algorithm is based on the blog post [Flattening quadratic Béziers],
// but with some refinements. For one, there is a more careful approximation at cusps. For
// two, the algorithm is extended to work with cubic Béziers as well, by first subdividing
// into quadratics and then computing the subdivision of each quadratic. However, as a
// clever trick, these quadratics are subdivided fractionally, and their endpoints are not
// included.
//
// [Flattening quadratic Béziers]: https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html
// [Hausdorff distance]: https://en.wikipedia.org/wiki/Hausdorff_distance
func (p BezPath) Flatten(tolerance float64, out BezPath) BezPath {
// Proportion of tolerance budget that goes to cubic to quadratic conversion.
const toQuadTol = 0.1
sqrtTol := math.Sqrt(tolerance)
var lastPt maybe.Option[Point]
// The sum variable is technically local to some nested scope, but
// because of the heavy use of iterators and closures, it escapes.
// Declaring it up here means it only produces one allocation per call
// to Flatten, instead of one per cubic bezier in the path.
var sum float64
for _, el := range p {
switch el.Kind {
case MoveToKind:
lastPt = maybe.Some(el.P0)
out.Push(el)
case LineToKind:
lastPt = maybe.Some(el.P0)
out.Push(el)
case QuadToKind:
p1, p2 := el.P0, el.P1
if p0, ok := lastPt.Get(); ok {
// An upper bound on the shortest distance of any point on the quadratic Bezier
// curve to the line segment [p0, p2] is 1/2 of the control-point-to-line-segment
// distance.
//
// The derivation is similar to that for the cubic Bez 6CE9 ier (see below). In
// short:
//
// q(t) = B0(t) p0 + B1(t) p1 + B2(t) p2
// dist(q(t), [p0, p1]) <= B1(t) dist(p1, [p0, p1])
// = 2 (1-t)t dist(p1, [p0, p1]).
//
// The maximum occurs at t=1/2, hence
// max(dist(q(t), [p0, p1] <= 1/2 dist(p1, [p0, p1])).
//
// The following takes the square to elide the square root of the Euclidean
// distance.
line := Line{p0, p2}
if distSq, _ := line.Nearest(p1, 0); distSq <= 4*tolerance*tolerance {
out.LineTo(p2)
} else {
q := QuadBez{p0, p1, p2}
params := q.estimateSubdiv(sqrtTol)
n := max(int(math.Ceil(0.5*params.val/sqrtTol)), 1)
step := 1.0 / float64(n)
for i := 1; i < n; i++ {
u := float64(i) * step
t := q.determineSubdivT(&params, u)
p := q.Eval(t)
out.LineTo(p)
}
out.LineTo(p2)
}
}
lastPt = maybe.Some(p2)
case CubicToKind:
p1, p2, p3 := el.P0, el.P1, el.P2
if p0, ok := lastPt.Get(); ok {
// An upper bound on the shortest distance of any point on the cubic Bezier
// curve to the line segment [p0, p3] is 3/4 of the maximum of the
// control-point-to-line-segment distances.
//
// With Bernstein weights Bi(t), we have
// c(t) = B0(t) p0 + B1(t) p1 + B2(t) p2 + B3(t) p3
// with t from 0 to 1 (inclusive).
//
// Through convexivity of the Euclidean distance function and the line segment,
// we have
// dist(c(t), [p0, p3]) <= B1(t) dist(p1, [p0, p3]) + B2(t) dist(p2, [p0, p3])
// <= (B1(t) + B2(t)) max(dist(p1, [p0, p3]), dist(p2, [p0, p3]))
// = 3 ((1-t)t^2 + (1-t)^2t) max(dist(p1, [p0, p3]), dist(p2, [p0, p3])).
//
// The inner polynomial has its maximum of 1/4 at t=1/2, hence
// max(dist(c(t), [p0, p3])) <= 3/4 max(dist(p1, [p0, p3]), dist(p2, [p0, p3])).
//
// The following takes the square to elide the square root of the Euclidean
// distance.
line := Line{p0, p3}
distSq1, _ := line.Nearest(p1, 0)
distSq2, _ := line.Nearest(p2, 0)
if max(distSq1, distSq2) <= 16.0/9.0*(tolerance*tolerance) {
out.LineTo(p3)
} else {
c := CubicBez{p0, p1, p2, p3}
// Subdivide into quadratics, and estimate the number of
// subdivisions required for each, summing to arrive at an
View remainder of file in raw view
0