stroke.go

Documentation: github.com/golang/freetype/raster

     1  // Copyright 2010 The Freetype-Go Authors. All rights reserved.
     2  // Use of this source code is governed by your choice of either the
     3  // FreeType License or the GNU General Public License version 2 (or
     4  // any later version), both of which can be found in the LICENSE file.
     5  
     6  package raster
     7  
     8  import (
     9  	"golang.org/x/image/math/fixed"
    10  )
    11  
    12  // Two points are considered practically equal if the square of the distance
    13  // between them is less than one quarter (i.e. 1024 / 4096).
    14  const epsilon = fixed.Int52_12(1024)
    15  
    16  // A Capper signifies how to begin or end a stroked path.
    17  type Capper interface {
    18  	// Cap adds a cap to p given a pivot point and the normal vector of a
    19  	// terminal segment. The normal's length is half of the stroke width.
    20  	Cap(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6)
    21  }
    22  
    23  // The CapperFunc type adapts an ordinary function to be a Capper.
    24  type CapperFunc func(Adder, fixed.Int26_6, fixed.Point26_6, fixed.Point26_6)
    25  
    26  func (f CapperFunc) Cap(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) {
    27  	f(p, halfWidth, pivot, n1)
    28  }
    29  
    30  // A Joiner signifies how to join interior nodes of a stroked path.
    31  type Joiner interface {
    32  	// Join adds a join to the two sides of a stroked path given a pivot
    33  	// point and the normal vectors of the trailing and leading segments.
    34  	// Both normals have length equal to half of the stroke width.
    35  	Join(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6)
    36  }
    37  
    38  // The JoinerFunc type adapts an ordinary function to be a Joiner.
    39  type JoinerFunc func(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6)
    40  
    41  func (f JoinerFunc) Join(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) {
    42  	f(lhs, rhs, halfWidth, pivot, n0, n1)
    43  }
    44  
    45  // RoundCapper adds round caps to a stroked path.
    46  var RoundCapper Capper = CapperFunc(roundCapper)
    47  
    48  func roundCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) {
    49  	// The cubic Bézier approximation to a circle involves the magic number
    50  	// (√2 - 1) * 4/3, which is approximately 35/64.
    51  	const k = 35
    52  	e := pRot90CCW(n1)
    53  	side := pivot.Add(e)
    54  	start, end := pivot.Sub(n1), pivot.Add(n1)
    55  	d, e := n1.Mul(k), e.Mul(k)
    56  	p.Add3(start.Add(e), side.Sub(d), side)
    57  	p.Add3(side.Add(d), end.Add(e), end)
    58  }
    59  
    60  // ButtCapper adds butt caps to a stroked path.
    61  var ButtCapper Capper = CapperFunc(buttCapper)
    62  
    63  func buttCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) {
    64  	p.Add1(pivot.Add(n1))
    65  }
    66  
    67  // SquareCapper adds square caps to a stroked path.
    68  var SquareCapper Capper = CapperFunc(squareCapper)
    69  
    70  func squareCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) {
    71  	e := pRot90CCW(n1)
    72  	side := pivot.Add(e)
    73  	p.Add1(side.Sub(n1))
    74  	p.Add1(side.Add(n1))
    75  	p.Add1(pivot.Add(n1))
    76  }
    77  
    78  // RoundJoiner adds round joins to a stroked path.
    79  var RoundJoiner Joiner = JoinerFunc(roundJoiner)
    80  
    81  func roundJoiner(lhs, rhs Adder, haflWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) {
    82  	dot := pDot(pRot90CW(n0), n1)
    83  	if dot >= 0 {
    84  		addArc(lhs, pivot, n0, n1)
    85  		rhs.Add1(pivot.Sub(n1))
    86  	} else {
    87  		lhs.Add1(pivot.Add(n1))
    88  		addArc(rhs, pivot, pNeg(n0), pNeg(n1))
    89  	}
    90  }
    91  
    92  // BevelJoiner adds bevel joins to a stroked path.
    93  var BevelJoiner Joiner = JoinerFunc(bevelJoiner)
    94  
    95  func bevelJoiner(lhs, rhs Adder, haflWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) {
    96  	lhs.Add1(pivot.Add(n1))
    97  	rhs.Add1(pivot.Sub(n1))
    98  }
    99  
   100  // addArc adds a circular arc from pivot+n0 to pivot+n1 to p. The shorter of
   101  // the two possible arcs is taken, i.e. the one spanning <= 180 degrees. The
   102  // two vectors n0 and n1 must be of equal length.
   103  func addArc(p Adder, pivot, n0, n1 fixed.Point26_6) {
   104  	// r2 is the square of the length of n0.
   105  	r2 := pDot(n0, n0)
   106  	if r2 < epsilon {
   107  		// The arc radius is so small that we collapse to a straight line.
   108  		p.Add1(pivot.Add(n1))
   109  		return
   110  	}
   111  	// We approximate the arc by 0, 1, 2 or 3 45-degree quadratic segments plus
   112  	// a final quadratic segment from s to n1. Each 45-degree segment has
   113  	// control points {1, 0}, {1, tan(π/8)} and {1/√2, 1/√2} suitably scaled,
   114  	// rotated and translated. tan(π/8) is approximately 27/64.
   115  	const tpo8 = 27
   116  	var s fixed.Point26_6
   117  	// We determine which octant the angle between n0 and n1 is in via three
   118  	// dot products. m0, m1 and m2 are n0 rotated clockwise by 45, 90 and 135
   119  	// degrees.
   120  	m0 := pRot45CW(n0)
   121  	m1 := pRot90CW(n0)
   122  	m2 := pRot90CW(m0)
   123  	if pDot(m1, n1) >= 0 {
   124  		if pDot(n0, n1) >= 0 {
   125  			if pDot(m2, n1) <= 0 {
   126  				// n1 is between 0 and 45 degrees clockwise of n0.
   127  				s = n0
   128  			} else {
   129  				// n1 is between 45 and 90 degrees clockwise of n0.
   130  				p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0))
   131  				s = m0
   132  			}
   133  		} else {
   134  			pm1, n0t := pivot.Add(m1), n0.Mul(tpo8)
   135  			p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0))
   136  			p.Add2(pm1.Add(n0t), pm1)
   137  			if pDot(m0, n1) >= 0 {
   138  				// n1 is between 90 and 135 degrees clockwise of n0.
   139  				s = m1
   140  			} else {
   141  				// n1 is between 135 and 180 degrees clockwise of n0.
   142  				p.Add2(pm1.Sub(n0t), pivot.Add(m2))
   143  				s = m2
   144  			}
   145  		}
   146  	} else {
   147  		if pDot(n0, n1) >= 0 {
   148  			if pDot(m0, n1) >= 0 {
   149  				// n1 is between 0 and 45 degrees counter-clockwise of n0.
   150  				s = n0
   151  			} else {
   152  				// n1 is between 45 and 90 degrees counter-clockwise of n0.
   153  				p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2))
   154  				s = pNeg(m2)
   155  			}
   156  		} else {
   157  			pm1, n0t := pivot.Sub(m1), n0.Mul(tpo8)
   158  			p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2))
   159  			p.Add2(pm1.Add(n0t), pm1)
   160  			if pDot(m2, n1) <= 0 {
   161  				// n1 is between 90 and 135 degrees counter-clockwise of n0.
   162  				s = pNeg(m1)
   163  			} else {
   164  				// n1 is between 135 and 180 degrees counter-clockwise of n0.
   165  				p.Add2(pm1.Sub(n0t), pivot.Sub(m0))
   166  				s = pNeg(m0)
   167  			}
   168  		}
   169  	}
   170  	// The final quadratic segment has two endpoints s and n1 and the middle
   171  	// control point is a multiple of s.Add(n1), i.e. it is on the angle
   172  	// bisector of those two points. The multiple ranges between 128/256 and
   173  	// 150/256 as the angle between s and n1 ranges between 0 and 45 degrees.
   174  	//
   175  	// When the angle is 0 degrees (i.e. s and n1 are coincident) then
   176  	// s.Add(n1) is twice s and so the middle control point of the degenerate
   177  	// quadratic segment should be half s.Add(n1), and half = 128/256.
   178  	//
   179  	// When the angle is 45 degrees then 150/256 is the ratio of the lengths of
   180  	// the two vectors {1, tan(π/8)} and {1 + 1/√2, 1/√2}.
   181  	//
   182  	// d is the normalized dot product between s and n1. Since the angle ranges
   183  	// between 0 and 45 degrees then d ranges between 256/256 and 181/256.
   184  	d := 256 * pDot(s, n1) / r2
   185  	multiple := fixed.Int26_6(150-(150-128)*(d-181)/(256-181)) >> 2
   186  	p.Add2(pivot.Add(s.Add(n1).Mul(multiple)), pivot.Add(n1))
   187  }
   188  
   189  // midpoint returns the midpoint of two Points.
   190  func midpoint(a, b fixed.Point26_6) fixed.Point26_6 {
   191  	return fixed.Point26_6{(a.X + b.X) / 2, (a.Y + b.Y) / 2}
   192  }
   193  
   194  // angleGreaterThan45 returns whether the angle between two vectors is more
   195  // than 45 degrees.
   196  func angleGreaterThan45(v0, v1 fixed.Point26_6) bool {
   197  	v := pRot45CCW(v0)
   198  	return pDot(v, v1) < 0 || pDot(pRot90CW(v), v1) < 0
   199  }
   200  
   201  // interpolate returns the point (1-t)*a + t*b.
   202  func interpolate(a, b fixed.Point26_6, t fixed.Int52_12) fixed.Point26_6 {
   203  	s := 1<<12 - t
   204  	x := s*fixed.Int52_12(a.X) + t*fixed.Int52_12(b.X)
   205  	y := s*fixed.Int52_12(a.Y) + t*fixed.Int52_12(b.Y)
   206  	return fixed.Point26_6{fixed.Int26_6(x >> 12), fixed.Int26_6(y >> 12)}
   207  }
   208  
   209  // curviest2 returns the value of t for which the quadratic parametric curve
   210  // (1-t)²*a + 2*t*(1-t).b + t²*c has maximum curvature.
   211  //
   212  // The curvature of the parametric curve f(t) = (x(t), y(t)) is
   213  // |x′y″-y′x″| / (x′²+y′²)^(3/2).
   214  //
   215  // Let d = b-a and e = c-2*b+a, so that f′(t) = 2*d+2*e*t and f″(t) = 2*e.
   216  // The curvature's numerator is (2*dx+2*ex*t)*(2*ey)-(2*dy+2*ey*t)*(2*ex),
   217  // which simplifies to 4*dx*ey-4*dy*ex, which is constant with respect to t.
   218  //
   219  // Thus, curvature is extreme where the denominator is extreme, i.e. where
   220  // (x′²+y′²) is extreme. The first order condition is that
   221  // 2*x′*x″+2*y′*y″ = 0, or (dx+ex*t)*ex + (dy+ey*t)*ey = 0.
   222  // Solving for t gives t = -(dx*ex+dy*ey) / (ex*ex+ey*ey).
   223  func curviest2(a, b, c fixed.Point26_6) fixed.Int52_12 {
   224  	dx := int64(b.X - a.X)
   225  	dy := int64(b.Y - a.Y)
   226  	ex := int64(c.X - 2*b.X + a.X)
   227  	ey := int64(c.Y - 2*b.Y + a.Y)
   228  	if ex == 0 && ey == 0 {
   229  		return 2048
   230  	}
   231  	return fixed.Int52_12(-4096 * (dx*ex + dy*ey) / (ex*ex + ey*ey))
   232  }
   233  
   234  // A stroker holds state for stroking a path.
   235  type stroker struct {
   236  	// p is the destination that records the stroked path.
   237  	p Adder
   238  	// u is the half-width of the stroke.
   239  	u fixed.Int26_6
   240  	// cr and jr specify how to end and connect path segments.
   241  	cr Capper
   242  	jr Joiner
   243  	// r is the reverse path. Stroking a path involves constructing two
   244  	// parallel paths 2*u apart. The first path is added immediately to p,
   245  	// the second path is accumulated in r and eventually added in reverse.
   246  	r Path
   247  	// a is the most recent segment point. anorm is the segment normal of
   248  	// length u at that point.
   249  	a, anorm fixed.Point26_6
   250  }
   251  
   252  // addNonCurvy2 adds a quadratic segment to the stroker, where the segment
   253  // defined by (k.a, b, c) achieves maximum curvature at either k.a or c.
   254  func (k *stroker) addNonCurvy2(b, c fixed.Point26_6) {
   255  	// We repeatedly divide the segment at its middle until it is straight
   256  	// enough to approximate the stroke by just translating the control points.
   257  	// ds and ps are stacks of depths and points. t is the top of the stack.
   258  	const maxDepth = 5
   259  	var (
   260  		ds [maxDepth + 1]int
   261  		ps [2*maxDepth + 3]fixed.Point26_6
   262  		t  int
   263  	)
   264  	// Initially the ps stack has one quadratic segment of depth zero.
   265  	ds[0] = 0
   266  	ps[2] = k.a
   267  	ps[1] = b
   268  	ps[0] = c
   269  	anorm := k.anorm
   270  	var cnorm fixed.Point26_6
   271  
   272  	for {
   273  		depth := ds[t]
   274  		a := ps[2*t+2]
   275  		b := ps[2*t+1]
   276  		c := ps[2*t+0]
   277  		ab := b.Sub(a)
   278  		bc := c.Sub(b)
   279  		abIsSmall := pDot(ab, ab) < fixed.Int52_12(1<<12)
   280  		bcIsSmall := pDot(bc, bc) < fixed.Int52_12(1<<12)
   281  		if abIsSmall && bcIsSmall {
   282  			// Approximate the segment by a circular arc.
   283  			cnorm = pRot90CCW(pNorm(bc, k.u))
   284  			mac := midpoint(a, c)
   285  			addArc(k.p, mac, anorm, cnorm)
   286  			addArc(&k.r, mac, pNeg(anorm), pNeg(cnorm))
   287  		} else if depth < maxDepth && angleGreaterThan45(ab, bc) {
   288  			// Divide the segment in two and push both halves on the stack.
   289  			mab := midpoint(a, b)
   290  			mbc := midpoint(b, c)
   291  			t++
   292  			ds[t+0] = depth + 1
   293  			ds[t-1] = depth + 1
   294  			ps[2*t+2] = a
   295  			ps[2*t+1] = mab
   296  			ps[2*t+0] = midpoint(mab, mbc)
   297  			ps[2*t-1] = mbc
   298  			continue
   299  		} else {
   300  			// Translate the control points.
   301  			bnorm := pRot90CCW(pNorm(c.Sub(a), k.u))
   302  			cnorm = pRot90CCW(pNorm(bc, k.u))
   303  			k.p.Add2(b.Add(bnorm), c.Add(cnorm))
   304  			k.r.Add2(b.Sub(bnorm), c.Sub(cnorm))
   305  		}
   306  		if t == 0 {
   307  			k.a, k.anorm = c, cnorm
   308  			return
   309  		}
   310  		t--
   311  		anorm = cnorm
   312  	}
   313  	panic("unreachable")
   314  }
   315  
   316  // Add1 adds a linear segment to the stroker.
   317  func (k *stroker) Add1(b fixed.Point26_6) {
   318  	bnorm := pRot90CCW(pNorm(b.Sub(k.a), k.u))
   319  	if len(k.r) == 0 {
   320  		k.p.Start(k.a.Add(bnorm))
   321  		k.r.Start(k.a.Sub(bnorm))
   322  	} else {
   323  		k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, bnorm)
   324  	}
   325  	k.p.Add1(b.Add(bnorm))
   326  	k.r.Add1(b.Sub(bnorm))
   327  	k.a, k.anorm = b, bnorm
   328  }
   329  
   330  // Add2 adds a quadratic segment to the stroker.
   331  func (k *stroker) Add2(b, c fixed.Point26_6) {
   332  	ab := b.Sub(k.a)
   333  	bc := c.Sub(b)
   334  	abnorm := pRot90CCW(pNorm(ab, k.u))
   335  	if len(k.r) == 0 {
   336  		k.p.Start(k.a.Add(abnorm))
   337  		k.r.Start(k.a.Sub(abnorm))
   338  	} else {
   339  		k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, abnorm)
   340  	}
   341  
   342  	// Approximate nearly-degenerate quadratics by linear segments.
   343  	abIsSmall := pDot(ab, ab) < epsilon
   344  	bcIsSmall := pDot(bc, bc) < epsilon
   345  	if abIsSmall || bcIsSmall {
   346  		acnorm := pRot90CCW(pNorm(c.Sub(k.a), k.u))
   347  		k.p.Add1(c.Add(acnorm))
   348  		k.r.Add1(c.Sub(acnorm))
   349  		k.a, k.anorm = c, acnorm
   350  		return
   351  	}
   352  
   353  	// The quadratic segment (k.a, b, c) has a point of maximum curvature.
   354  	// If this occurs at an end point, we process the segment as a whole.
   355  	t := curviest2(k.a, b, c)
   356  	if t <= 0 || 4096 <= t {
   357  		k.addNonCurvy2(b, c)
   358  		return
   359  	}
   360  
   361  	// Otherwise, we perform a de Casteljau decomposition at the point of
   362  	// maximum curvature and process the two straighter parts.
   363  	mab := interpolate(k.a, b, t)
   364  	mbc := interpolate(b, c, t)
   365  	mabc := interpolate(mab, mbc, t)
   366  
   367  	// If the vectors ab and bc are close to being in opposite directions,
   368  	// then the decomposition can become unstable, so we approximate the
   369  	// quadratic segment by two linear segments joined by an arc.
   370  	bcnorm := pRot90CCW(pNorm(bc, k.u))
   371  	if pDot(abnorm, bcnorm) < -fixed.Int52_12(k.u)*fixed.Int52_12(k.u)*2047/2048 {
   372  		pArc := pDot(abnorm, bc) < 0
   373  
   374  		k.p.Add1(mabc.Add(abnorm))
   375  		if pArc {
   376  			z := pRot90CW(abnorm)
   377  			addArc(k.p, mabc, abnorm, z)
   378  			addArc(k.p, mabc, z, bcnorm)
   379  		}
   380  		k.p.Add1(mabc.Add(bcnorm))
   381  		k.p.Add1(c.Add(bcnorm))
   382  
   383  		k.r.Add1(mabc.Sub(abnorm))
   384  		if !pArc {
   385  			z := pRot90CW(abnorm)
   386  			addArc(&k.r, mabc, pNeg(abnorm), z)
   387  			addArc(&k.r, mabc, z, pNeg(bcnorm))
   388  		}
   389  		k.r.Add1(mabc.Sub(bcnorm))
   390  		k.r.Add1(c.Sub(bcnorm))
   391  
   392  		k.a, k.anorm = c, bcnorm
   393  		return
   394  	}
   395  
   396  	// Process the decomposed parts.
   397  	k.addNonCurvy2(mab, mabc)
   398  	k.addNonCurvy2(mbc, c)
   399  }
   400  
   401  // Add3 adds a cubic segment to the stroker.
   402  func (k *stroker) Add3(b, c, d fixed.Point26_6) {
   403  	panic("freetype/raster: stroke unimplemented for cubic segments")
   404  }
   405  
   406  // stroke adds the stroked Path q to p, where q consists of exactly one curve.
   407  func (k *stroker) stroke(q Path) {
   408  	// Stroking is implemented by deriving two paths each k.u apart from q.
   409  	// The left-hand-side path is added immediately to k.p; the right-hand-side
   410  	// path is accumulated in k.r. Once we've finished adding the LHS to k.p,
   411  	// we add the RHS in reverse order.
   412  	k.r = make(Path, 0, len(q))
   413  	k.a = fixed.Point26_6{q[1], q[2]}
   414  	for i := 4; i < len(q); {
   415  		switch q[i] {
   416  		case 1:
   417  			k.Add1(
   418  				fixed.Point26_6{q[i+1], q[i+2]},
   419  			)
   420  			i += 4
   421  		case 2:
   422  			k.Add2(
   423  				fixed.Point26_6{q[i+1], q[i+2]},
   424  				fixed.Point26_6{q[i+3], q[i+4]},
   425  			)
   426  			i += 6
   427  		case 3:
   428  			k.Add3(
   429  				fixed.Point26_6{q[i+1], q[i+2]},
   430  				fixed.Point26_6{q[i+3], q[i+4]},
   431  				fixed.Point26_6{q[i+5], q[i+6]},
   432  			)
   433  			i += 8
   434  		default:
   435  			panic("freetype/raster: bad path")
   436  		}
   437  	}
   438  	if len(k.r) == 0 {
   439  		return
   440  	}
   441  	// TODO(nigeltao): if q is a closed curve then we should join the first and
   442  	// last segments instead of capping them.
   443  	k.cr.Cap(k.p, k.u, q.lastPoint(), pNeg(k.anorm))
   444  	addPathReversed(k.p, k.r)
   445  	pivot := q.firstPoint()
   446  	k.cr.Cap(k.p, k.u, pivot, pivot.Sub(fixed.Point26_6{k.r[1], k.r[2]}))
   447  }
   448  
   449  // Stroke adds q stroked with the given width to p. The result is typically
   450  // self-intersecting and should be rasterized with UseNonZeroWinding.
   451  // cr and jr may be nil, which defaults to a RoundCapper or RoundJoiner.
   452  func Stroke(p Adder, q Path, width fixed.Int26_6, cr Capper, jr Joiner) {
   453  	if len(q) == 0 {
   454  		return
   455  	}
   456  	if cr == nil {
   457  		cr = RoundCapper
   458  	}
   459  	if jr == nil {
   460  		jr = RoundJoiner
   461  	}
   462  	if q[0] != 0 {
   463  		panic("freetype/raster: bad path")
   464  	}
   465  	s := stroker{p: p, u: width / 2, cr: cr, jr: jr}
   466  	i := 0
   467  	for j := 4; j < len(q); {
   468  		switch q[j] {
   469  		case 0:
   470  			s.stroke(q[i:j])
   471  			i, j = j, j+4
   472  		case 1:
   473  			j += 4
   474  		case 2:
   475  			j += 6
   476  		case 3:
   477  			j += 8
   478  		default:
   479  			panic("freetype/raster: bad path")
   480  		}
   481  	}
   482  	s.stroke(q[i:])
   483  }
   484
View as plain text