From 84d2482ddbff9564c9ad75b2d30af66e3ddfd44d Mon Sep 17 00:00:00 2001 From: Christopher Speller Date: Thu, 12 May 2016 15:08:58 -0400 Subject: Updating go depencancies. Switching to go1.6 vendoring (#2949) --- .../src/github.com/golang/freetype/raster/geom.go | 245 --------- .../src/github.com/golang/freetype/raster/paint.go | 287 ---------- .../github.com/golang/freetype/raster/raster.go | 601 --------------------- .../github.com/golang/freetype/raster/stroke.go | 483 ----------------- 4 files changed, 1616 deletions(-) delete mode 100644 Godeps/_workspace/src/github.com/golang/freetype/raster/geom.go delete mode 100644 Godeps/_workspace/src/github.com/golang/freetype/raster/paint.go delete mode 100644 Godeps/_workspace/src/github.com/golang/freetype/raster/raster.go delete mode 100644 Godeps/_workspace/src/github.com/golang/freetype/raster/stroke.go (limited to 'Godeps/_workspace/src/github.com/golang/freetype/raster') diff --git a/Godeps/_workspace/src/github.com/golang/freetype/raster/geom.go b/Godeps/_workspace/src/github.com/golang/freetype/raster/geom.go deleted file mode 100644 index f3696ea98..000000000 --- a/Godeps/_workspace/src/github.com/golang/freetype/raster/geom.go +++ /dev/null @@ -1,245 +0,0 @@ -// Copyright 2010 The Freetype-Go Authors. All rights reserved. -// Use of this source code is governed by your choice of either the -// FreeType License or the GNU General Public License version 2 (or -// any later version), both of which can be found in the LICENSE file. - -package raster - -import ( - "fmt" - "math" - - "golang.org/x/image/math/fixed" -) - -// maxAbs returns the maximum of abs(a) and abs(b). -func maxAbs(a, b fixed.Int26_6) fixed.Int26_6 { - if a < 0 { - a = -a - } - if b < 0 { - b = -b - } - if a < b { - return b - } - return a -} - -// pNeg returns the vector -p, or equivalently p rotated by 180 degrees. -func pNeg(p fixed.Point26_6) fixed.Point26_6 { - return fixed.Point26_6{-p.X, -p.Y} -} - -// pDot returns the dot product p·q. -func pDot(p fixed.Point26_6, q fixed.Point26_6) fixed.Int52_12 { - px, py := int64(p.X), int64(p.Y) - qx, qy := int64(q.X), int64(q.Y) - return fixed.Int52_12(px*qx + py*qy) -} - -// pLen returns the length of the vector p. -func pLen(p fixed.Point26_6) fixed.Int26_6 { - // TODO(nigeltao): use fixed point math. - x := float64(p.X) - y := float64(p.Y) - return fixed.Int26_6(math.Sqrt(x*x + y*y)) -} - -// pNorm returns the vector p normalized to the given length, or zero if p is -// degenerate. -func pNorm(p fixed.Point26_6, length fixed.Int26_6) fixed.Point26_6 { - d := pLen(p) - if d == 0 { - return fixed.Point26_6{} - } - s, t := int64(length), int64(d) - x := int64(p.X) * s / t - y := int64(p.Y) * s / t - return fixed.Point26_6{fixed.Int26_6(x), fixed.Int26_6(y)} -} - -// pRot45CW returns the vector p rotated clockwise by 45 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot45CW is {1/√2, 1/√2}. -func pRot45CW(p fixed.Point26_6) fixed.Point26_6 { - // 181/256 is approximately 1/√2, or sin(π/4). - px, py := int64(p.X), int64(p.Y) - qx := (+px - py) * 181 / 256 - qy := (+px + py) * 181 / 256 - return fixed.Point26_6{fixed.Int26_6(qx), fixed.Int26_6(qy)} -} - -// pRot90CW returns the vector p rotated clockwise by 90 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot90CW is {0, 1}. -func pRot90CW(p fixed.Point26_6) fixed.Point26_6 { - return fixed.Point26_6{-p.Y, p.X} -} - -// pRot135CW returns the vector p rotated clockwise by 135 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot135CW is {-1/√2, 1/√2}. -func pRot135CW(p fixed.Point26_6) fixed.Point26_6 { - // 181/256 is approximately 1/√2, or sin(π/4). - px, py := int64(p.X), int64(p.Y) - qx := (-px - py) * 181 / 256 - qy := (+px - py) * 181 / 256 - return fixed.Point26_6{fixed.Int26_6(qx), fixed.Int26_6(qy)} -} - -// pRot45CCW returns the vector p rotated counter-clockwise by 45 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot45CCW is {1/√2, -1/√2}. -func pRot45CCW(p fixed.Point26_6) fixed.Point26_6 { - // 181/256 is approximately 1/√2, or sin(π/4). - px, py := int64(p.X), int64(p.Y) - qx := (+px + py) * 181 / 256 - qy := (-px + py) * 181 / 256 - return fixed.Point26_6{fixed.Int26_6(qx), fixed.Int26_6(qy)} -} - -// pRot90CCW returns the vector p rotated counter-clockwise by 90 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot90CCW is {0, -1}. -func pRot90CCW(p fixed.Point26_6) fixed.Point26_6 { - return fixed.Point26_6{p.Y, -p.X} -} - -// pRot135CCW returns the vector p rotated counter-clockwise by 135 degrees. -// -// Note that the Y-axis grows downwards, so {1, 0}.Rot135CCW is {-1/√2, -1/√2}. -func pRot135CCW(p fixed.Point26_6) fixed.Point26_6 { - // 181/256 is approximately 1/√2, or sin(π/4). - px, py := int64(p.X), int64(p.Y) - qx := (-px + py) * 181 / 256 - qy := (-px - py) * 181 / 256 - return fixed.Point26_6{fixed.Int26_6(qx), fixed.Int26_6(qy)} -} - -// An Adder accumulates points on a curve. -type Adder interface { - // Start starts a new curve at the given point. - Start(a fixed.Point26_6) - // Add1 adds a linear segment to the current curve. - Add1(b fixed.Point26_6) - // Add2 adds a quadratic segment to the current curve. - Add2(b, c fixed.Point26_6) - // Add3 adds a cubic segment to the current curve. - Add3(b, c, d fixed.Point26_6) -} - -// A Path is a sequence of curves, and a curve is a start point followed by a -// sequence of linear, quadratic or cubic segments. -type Path []fixed.Int26_6 - -// String returns a human-readable representation of a Path. -func (p Path) String() string { - s := "" - for i := 0; i < len(p); { - if i != 0 { - s += " " - } - switch p[i] { - case 0: - s += "S0" + fmt.Sprint([]fixed.Int26_6(p[i+1:i+3])) - i += 4 - case 1: - s += "A1" + fmt.Sprint([]fixed.Int26_6(p[i+1:i+3])) - i += 4 - case 2: - s += "A2" + fmt.Sprint([]fixed.Int26_6(p[i+1:i+5])) - i += 6 - case 3: - s += "A3" + fmt.Sprint([]fixed.Int26_6(p[i+1:i+7])) - i += 8 - default: - panic("freetype/raster: bad path") - } - } - return s -} - -// Clear cancels any previous calls to p.Start or p.AddXxx. -func (p *Path) Clear() { - *p = (*p)[:0] -} - -// Start starts a new curve at the given point. -func (p *Path) Start(a fixed.Point26_6) { - *p = append(*p, 0, a.X, a.Y, 0) -} - -// Add1 adds a linear segment to the current curve. -func (p *Path) Add1(b fixed.Point26_6) { - *p = append(*p, 1, b.X, b.Y, 1) -} - -// Add2 adds a quadratic segment to the current curve. -func (p *Path) Add2(b, c fixed.Point26_6) { - *p = append(*p, 2, b.X, b.Y, c.X, c.Y, 2) -} - -// Add3 adds a cubic segment to the current curve. -func (p *Path) Add3(b, c, d fixed.Point26_6) { - *p = append(*p, 3, b.X, b.Y, c.X, c.Y, d.X, d.Y, 3) -} - -// AddPath adds the Path q to p. -func (p *Path) AddPath(q Path) { - *p = append(*p, q...) -} - -// AddStroke adds a stroked Path. -func (p *Path) AddStroke(q Path, width fixed.Int26_6, cr Capper, jr Joiner) { - Stroke(p, q, width, cr, jr) -} - -// firstPoint returns the first point in a non-empty Path. -func (p Path) firstPoint() fixed.Point26_6 { - return fixed.Point26_6{p[1], p[2]} -} - -// lastPoint returns the last point in a non-empty Path. -func (p Path) lastPoint() fixed.Point26_6 { - return fixed.Point26_6{p[len(p)-3], p[len(p)-2]} -} - -// addPathReversed adds q reversed to p. -// For example, if q consists of a linear segment from A to B followed by a -// quadratic segment from B to C to D, then the values of q looks like: -// index: 01234567890123 -// value: 0AA01BB12CCDD2 -// So, when adding q backwards to p, we want to Add2(C, B) followed by Add1(A). -func addPathReversed(p Adder, q Path) { - if len(q) == 0 { - return - } - i := len(q) - 1 - for { - switch q[i] { - case 0: - return - case 1: - i -= 4 - p.Add1( - fixed.Point26_6{q[i-2], q[i-1]}, - ) - case 2: - i -= 6 - p.Add2( - fixed.Point26_6{q[i+2], q[i+3]}, - fixed.Point26_6{q[i-2], q[i-1]}, - ) - case 3: - i -= 8 - p.Add3( - fixed.Point26_6{q[i+4], q[i+5]}, - fixed.Point26_6{q[i+2], q[i+3]}, - fixed.Point26_6{q[i-2], q[i-1]}, - ) - default: - panic("freetype/raster: bad path") - } - } -} diff --git a/Godeps/_workspace/src/github.com/golang/freetype/raster/paint.go b/Godeps/_workspace/src/github.com/golang/freetype/raster/paint.go deleted file mode 100644 index 185d36a8e..000000000 --- a/Godeps/_workspace/src/github.com/golang/freetype/raster/paint.go +++ /dev/null @@ -1,287 +0,0 @@ -// Copyright 2010 The Freetype-Go Authors. All rights reserved. -// Use of this source code is governed by your choice of either the -// FreeType License or the GNU General Public License version 2 (or -// any later version), both of which can be found in the LICENSE file. - -package raster - -import ( - "image" - "image/color" - "image/draw" - "math" -) - -// A Span is a horizontal segment of pixels with constant alpha. X0 is an -// inclusive bound and X1 is exclusive, the same as for slices. A fully opaque -// Span has Alpha == 0xffff. -type Span struct { - Y, X0, X1 int - Alpha uint32 -} - -// A Painter knows how to paint a batch of Spans. Rasterization may involve -// Painting multiple batches, and done will be true for the final batch. The -// Spans' Y values are monotonically increasing during a rasterization. Paint -// may use all of ss as scratch space during the call. -type Painter interface { - Paint(ss []Span, done bool) -} - -// The PainterFunc type adapts an ordinary function to the Painter interface. -type PainterFunc func(ss []Span, done bool) - -// Paint just delegates the call to f. -func (f PainterFunc) Paint(ss []Span, done bool) { f(ss, done) } - -// An AlphaOverPainter is a Painter that paints Spans onto a *image.Alpha using -// the Over Porter-Duff composition operator. -type AlphaOverPainter struct { - Image *image.Alpha -} - -// Paint satisfies the Painter interface. -func (r AlphaOverPainter) Paint(ss []Span, done bool) { - b := r.Image.Bounds() - for _, s := range ss { - if s.Y < b.Min.Y { - continue - } - if s.Y >= b.Max.Y { - return - } - if s.X0 < b.Min.X { - s.X0 = b.Min.X - } - if s.X1 > b.Max.X { - s.X1 = b.Max.X - } - if s.X0 >= s.X1 { - continue - } - base := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride - r.Image.Rect.Min.X - p := r.Image.Pix[base+s.X0 : base+s.X1] - a := int(s.Alpha >> 8) - for i, c := range p { - v := int(c) - p[i] = uint8((v*255 + (255-v)*a) / 255) - } - } -} - -// NewAlphaOverPainter creates a new AlphaOverPainter for the given image. -func NewAlphaOverPainter(m *image.Alpha) AlphaOverPainter { - return AlphaOverPainter{m} -} - -// An AlphaSrcPainter is a Painter that paints Spans onto a *image.Alpha using -// the Src Porter-Duff composition operator. -type AlphaSrcPainter struct { - Image *image.Alpha -} - -// Paint satisfies the Painter interface. -func (r AlphaSrcPainter) Paint(ss []Span, done bool) { - b := r.Image.Bounds() - for _, s := range ss { - if s.Y < b.Min.Y { - continue - } - if s.Y >= b.Max.Y { - return - } - if s.X0 < b.Min.X { - s.X0 = b.Min.X - } - if s.X1 > b.Max.X { - s.X1 = b.Max.X - } - if s.X0 >= s.X1 { - continue - } - base := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride - r.Image.Rect.Min.X - p := r.Image.Pix[base+s.X0 : base+s.X1] - color := uint8(s.Alpha >> 8) - for i := range p { - p[i] = color - } - } -} - -// NewAlphaSrcPainter creates a new AlphaSrcPainter for the given image. -func NewAlphaSrcPainter(m *image.Alpha) AlphaSrcPainter { - return AlphaSrcPainter{m} -} - -// An RGBAPainter is a Painter that paints Spans onto a *image.RGBA. -type RGBAPainter struct { - // Image is the image to compose onto. - Image *image.RGBA - // Op is the Porter-Duff composition operator. - Op draw.Op - // cr, cg, cb and ca are the 16-bit color to paint the spans. - cr, cg, cb, ca uint32 -} - -// Paint satisfies the Painter interface. -func (r *RGBAPainter) Paint(ss []Span, done bool) { - b := r.Image.Bounds() - for _, s := range ss { - if s.Y < b.Min.Y { - continue - } - if s.Y >= b.Max.Y { - return - } - if s.X0 < b.Min.X { - s.X0 = b.Min.X - } - if s.X1 > b.Max.X { - s.X1 = b.Max.X - } - if s.X0 >= s.X1 { - continue - } - // This code mimics drawGlyphOver in $GOROOT/src/image/draw/draw.go. - ma := s.Alpha - const m = 1<<16 - 1 - i0 := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride + (s.X0-r.Image.Rect.Min.X)*4 - i1 := i0 + (s.X1-s.X0)*4 - if r.Op == draw.Over { - for i := i0; i < i1; i += 4 { - dr := uint32(r.Image.Pix[i+0]) - dg := uint32(r.Image.Pix[i+1]) - db := uint32(r.Image.Pix[i+2]) - da := uint32(r.Image.Pix[i+3]) - a := (m - (r.ca * ma / m)) * 0x101 - r.Image.Pix[i+0] = uint8((dr*a + r.cr*ma) / m >> 8) - r.Image.Pix[i+1] = uint8((dg*a + r.cg*ma) / m >> 8) - r.Image.Pix[i+2] = uint8((db*a + r.cb*ma) / m >> 8) - r.Image.Pix[i+3] = uint8((da*a + r.ca*ma) / m >> 8) - } - } else { - for i := i0; i < i1; i += 4 { - r.Image.Pix[i+0] = uint8(r.cr * ma / m >> 8) - r.Image.Pix[i+1] = uint8(r.cg * ma / m >> 8) - r.Image.Pix[i+2] = uint8(r.cb * ma / m >> 8) - r.Image.Pix[i+3] = uint8(r.ca * ma / m >> 8) - } - } - } -} - -// SetColor sets the color to paint the spans. -func (r *RGBAPainter) SetColor(c color.Color) { - r.cr, r.cg, r.cb, r.ca = c.RGBA() -} - -// NewRGBAPainter creates a new RGBAPainter for the given image. -func NewRGBAPainter(m *image.RGBA) *RGBAPainter { - return &RGBAPainter{Image: m} -} - -// A MonochromePainter wraps another Painter, quantizing each Span's alpha to -// be either fully opaque or fully transparent. -type MonochromePainter struct { - Painter Painter - y, x0, x1 int -} - -// Paint delegates to the wrapped Painter after quantizing each Span's alpha -// value and merging adjacent fully opaque Spans. -func (m *MonochromePainter) Paint(ss []Span, done bool) { - // We compact the ss slice, discarding any Spans whose alpha quantizes to zero. - j := 0 - for _, s := range ss { - if s.Alpha >= 0x8000 { - if m.y == s.Y && m.x1 == s.X0 { - m.x1 = s.X1 - } else { - ss[j] = Span{m.y, m.x0, m.x1, 1<<32 - 1} - j++ - m.y, m.x0, m.x1 = s.Y, s.X0, s.X1 - } - } - } - if done { - // Flush the accumulated Span. - finalSpan := Span{m.y, m.x0, m.x1, 1<<32 - 1} - if j < len(ss) { - ss[j] = finalSpan - j++ - m.Painter.Paint(ss[:j], true) - } else if j == len(ss) { - m.Painter.Paint(ss, false) - if cap(ss) > 0 { - ss = ss[:1] - } else { - ss = make([]Span, 1) - } - ss[0] = finalSpan - m.Painter.Paint(ss, true) - } else { - panic("unreachable") - } - // Reset the accumulator, so that this Painter can be re-used. - m.y, m.x0, m.x1 = 0, 0, 0 - } else { - m.Painter.Paint(ss[:j], false) - } -} - -// NewMonochromePainter creates a new MonochromePainter that wraps the given -// Painter. -func NewMonochromePainter(p Painter) *MonochromePainter { - return &MonochromePainter{Painter: p} -} - -// A GammaCorrectionPainter wraps another Painter, performing gamma-correction -// on each Span's alpha value. -type GammaCorrectionPainter struct { - // Painter is the wrapped Painter. - Painter Painter - // a is the precomputed alpha values for linear interpolation, with fully - // opaque == 0xffff. - a [256]uint16 - // gammaIsOne is whether gamma correction is a no-op. - gammaIsOne bool -} - -// Paint delegates to the wrapped Painter after performing gamma-correction on -// each Span. -func (g *GammaCorrectionPainter) Paint(ss []Span, done bool) { - if !g.gammaIsOne { - const n = 0x101 - for i, s := range ss { - if s.Alpha == 0 || s.Alpha == 0xffff { - continue - } - p, q := s.Alpha/n, s.Alpha%n - // The resultant alpha is a linear interpolation of g.a[p] and g.a[p+1]. - a := uint32(g.a[p])*(n-q) + uint32(g.a[p+1])*q - ss[i].Alpha = (a + n/2) / n - } - } - g.Painter.Paint(ss, done) -} - -// SetGamma sets the gamma value. -func (g *GammaCorrectionPainter) SetGamma(gamma float64) { - g.gammaIsOne = gamma == 1 - if g.gammaIsOne { - return - } - for i := 0; i < 256; i++ { - a := float64(i) / 0xff - a = math.Pow(a, gamma) - g.a[i] = uint16(0xffff * a) - } -} - -// NewGammaCorrectionPainter creates a new GammaCorrectionPainter that wraps -// the given Painter. -func NewGammaCorrectionPainter(p Painter, gamma float64) *GammaCorrectionPainter { - g := &GammaCorrectionPainter{Painter: p} - g.SetGamma(gamma) - return g -} diff --git a/Godeps/_workspace/src/github.com/golang/freetype/raster/raster.go b/Godeps/_workspace/src/github.com/golang/freetype/raster/raster.go deleted file mode 100644 index 995925e2a..000000000 --- a/Godeps/_workspace/src/github.com/golang/freetype/raster/raster.go +++ /dev/null @@ -1,601 +0,0 @@ -// Copyright 2010 The Freetype-Go Authors. All rights reserved. -// Use of this source code is governed by your choice of either the -// FreeType License or the GNU General Public License version 2 (or -// any later version), both of which can be found in the LICENSE file. - -// Package raster provides an anti-aliasing 2-D rasterizer. -// -// It is part of the larger Freetype suite of font-related packages, but the -// raster package is not specific to font rasterization, and can be used -// standalone without any other Freetype package. -// -// Rasterization is done by the same area/coverage accumulation algorithm as -// the Freetype "smooth" module, and the Anti-Grain Geometry library. A -// description of the area/coverage algorithm is at -// http://projects.tuxee.net/cl-vectors/section-the-cl-aa-algorithm -package raster - -import ( - "strconv" - - "golang.org/x/image/math/fixed" -) - -// A cell is part of a linked list (for a given yi co-ordinate) of accumulated -// area/coverage for the pixel at (xi, yi). -type cell struct { - xi int - area, cover int - next int -} - -type Rasterizer struct { - // If false, the default behavior is to use the even-odd winding fill - // rule during Rasterize. - UseNonZeroWinding bool - // An offset (in pixels) to the painted spans. - Dx, Dy int - - // The width of the Rasterizer. The height is implicit in len(cellIndex). - width int - // splitScaleN is the scaling factor used to determine how many times - // to decompose a quadratic or cubic segment into a linear approximation. - splitScale2, splitScale3 int - - // The current pen position. - a fixed.Point26_6 - // The current cell and its area/coverage being accumulated. - xi, yi int - area, cover int - - // Saved cells. - cell []cell - // Linked list of cells, one per row. - cellIndex []int - // Buffers. - cellBuf [256]cell - cellIndexBuf [64]int - spanBuf [64]Span -} - -// findCell returns the index in r.cell for the cell corresponding to -// (r.xi, r.yi). The cell is created if necessary. -func (r *Rasterizer) findCell() int { - if r.yi < 0 || r.yi >= len(r.cellIndex) { - return -1 - } - xi := r.xi - if xi < 0 { - xi = -1 - } else if xi > r.width { - xi = r.width - } - i, prev := r.cellIndex[r.yi], -1 - for i != -1 && r.cell[i].xi <= xi { - if r.cell[i].xi == xi { - return i - } - i, prev = r.cell[i].next, i - } - c := len(r.cell) - if c == cap(r.cell) { - buf := make([]cell, c, 4*c) - copy(buf, r.cell) - r.cell = buf[0 : c+1] - } else { - r.cell = r.cell[0 : c+1] - } - r.cell[c] = cell{xi, 0, 0, i} - if prev == -1 { - r.cellIndex[r.yi] = c - } else { - r.cell[prev].next = c - } - return c -} - -// saveCell saves any accumulated r.area/r.cover for (r.xi, r.yi). -func (r *Rasterizer) saveCell() { - if r.area != 0 || r.cover != 0 { - i := r.findCell() - if i != -1 { - r.cell[i].area += r.area - r.cell[i].cover += r.cover - } - r.area = 0 - r.cover = 0 - } -} - -// setCell sets the (xi, yi) cell that r is accumulating area/coverage for. -func (r *Rasterizer) setCell(xi, yi int) { - if r.xi != xi || r.yi != yi { - r.saveCell() - r.xi, r.yi = xi, yi - } -} - -// scan accumulates area/coverage for the yi'th scanline, going from -// x0 to x1 in the horizontal direction (in 26.6 fixed point co-ordinates) -// and from y0f to y1f fractional vertical units within that scanline. -func (r *Rasterizer) scan(yi int, x0, y0f, x1, y1f fixed.Int26_6) { - // Break the 26.6 fixed point X co-ordinates into integral and fractional parts. - x0i := int(x0) / 64 - x0f := x0 - fixed.Int26_6(64*x0i) - x1i := int(x1) / 64 - x1f := x1 - fixed.Int26_6(64*x1i) - - // A perfectly horizontal scan. - if y0f == y1f { - r.setCell(x1i, yi) - return - } - dx, dy := x1-x0, y1f-y0f - // A single cell scan. - if x0i == x1i { - r.area += int((x0f + x1f) * dy) - r.cover += int(dy) - return - } - // There are at least two cells. Apart from the first and last cells, - // all intermediate cells go through the full width of the cell, - // or 64 units in 26.6 fixed point format. - var ( - p, q, edge0, edge1 fixed.Int26_6 - xiDelta int - ) - if dx > 0 { - p, q = (64-x0f)*dy, dx - edge0, edge1, xiDelta = 0, 64, 1 - } else { - p, q = x0f*dy, -dx - edge0, edge1, xiDelta = 64, 0, -1 - } - yDelta, yRem := p/q, p%q - if yRem < 0 { - yDelta -= 1 - yRem += q - } - // Do the first cell. - xi, y := x0i, y0f - r.area += int((x0f + edge1) * yDelta) - r.cover += int(yDelta) - xi, y = xi+xiDelta, y+yDelta - r.setCell(xi, yi) - if xi != x1i { - // Do all the intermediate cells. - p = 64 * (y1f - y + yDelta) - fullDelta, fullRem := p/q, p%q - if fullRem < 0 { - fullDelta -= 1 - fullRem += q - } - yRem -= q - for xi != x1i { - yDelta = fullDelta - yRem += fullRem - if yRem >= 0 { - yDelta += 1 - yRem -= q - } - r.area += int(64 * yDelta) - r.cover += int(yDelta) - xi, y = xi+xiDelta, y+yDelta - r.setCell(xi, yi) - } - } - // Do the last cell. - yDelta = y1f - y - r.area += int((edge0 + x1f) * yDelta) - r.cover += int(yDelta) -} - -// Start starts a new curve at the given point. -func (r *Rasterizer) Start(a fixed.Point26_6) { - r.setCell(int(a.X/64), int(a.Y/64)) - r.a = a -} - -// Add1 adds a linear segment to the current curve. -func (r *Rasterizer) Add1(b fixed.Point26_6) { - x0, y0 := r.a.X, r.a.Y - x1, y1 := b.X, b.Y - dx, dy := x1-x0, y1-y0 - // Break the 26.6 fixed point Y co-ordinates into integral and fractional - // parts. - y0i := int(y0) / 64 - y0f := y0 - fixed.Int26_6(64*y0i) - y1i := int(y1) / 64 - y1f := y1 - fixed.Int26_6(64*y1i) - - if y0i == y1i { - // There is only one scanline. - r.scan(y0i, x0, y0f, x1, y1f) - - } else if dx == 0 { - // This is a vertical line segment. We avoid calling r.scan and instead - // manipulate r.area and r.cover directly. - var ( - edge0, edge1 fixed.Int26_6 - yiDelta int - ) - if dy > 0 { - edge0, edge1, yiDelta = 0, 64, 1 - } else { - edge0, edge1, yiDelta = 64, 0, -1 - } - x0i, yi := int(x0)/64, y0i - x0fTimes2 := (int(x0) - (64 * x0i)) * 2 - // Do the first pixel. - dcover := int(edge1 - y0f) - darea := int(x0fTimes2 * dcover) - r.area += darea - r.cover += dcover - yi += yiDelta - r.setCell(x0i, yi) - // Do all the intermediate pixels. - dcover = int(edge1 - edge0) - darea = int(x0fTimes2 * dcover) - for yi != y1i { - r.area += darea - r.cover += dcover - yi += yiDelta - r.setCell(x0i, yi) - } - // Do the last pixel. - dcover = int(y1f - edge0) - darea = int(x0fTimes2 * dcover) - r.area += darea - r.cover += dcover - - } else { - // There are at least two scanlines. Apart from the first and last - // scanlines, all intermediate scanlines go through the full height of - // the row, or 64 units in 26.6 fixed point format. - var ( - p, q, edge0, edge1 fixed.Int26_6 - yiDelta int - ) - if dy > 0 { - p, q = (64-y0f)*dx, dy - edge0, edge1, yiDelta = 0, 64, 1 - } else { - p, q = y0f*dx, -dy - edge0, edge1, yiDelta = 64, 0, -1 - } - xDelta, xRem := p/q, p%q - if xRem < 0 { - xDelta -= 1 - xRem += q - } - // Do the first scanline. - x, yi := x0, y0i - r.scan(yi, x, y0f, x+xDelta, edge1) - x, yi = x+xDelta, yi+yiDelta - r.setCell(int(x)/64, yi) - if yi != y1i { - // Do all the intermediate scanlines. - p = 64 * dx - fullDelta, fullRem := p/q, p%q - if fullRem < 0 { - fullDelta -= 1 - fullRem += q - } - xRem -= q - for yi != y1i { - xDelta = fullDelta - xRem += fullRem - if xRem >= 0 { - xDelta += 1 - xRem -= q - } - r.scan(yi, x, edge0, x+xDelta, edge1) - x, yi = x+xDelta, yi+yiDelta - r.setCell(int(x)/64, yi) - } - } - // Do the last scanline. - r.scan(yi, x, edge0, x1, y1f) - } - // The next lineTo starts from b. - r.a = b -} - -// Add2 adds a quadratic segment to the current curve. -func (r *Rasterizer) Add2(b, c fixed.Point26_6) { - // Calculate nSplit (the number of recursive decompositions) based on how - // 'curvy' it is. Specifically, how much the middle point b deviates from - // (a+c)/2. - dev := maxAbs(r.a.X-2*b.X+c.X, r.a.Y-2*b.Y+c.Y) / fixed.Int26_6(r.splitScale2) - nsplit := 0 - for dev > 0 { - dev /= 4 - nsplit++ - } - // dev is 32-bit, and nsplit++ every time we shift off 2 bits, so maxNsplit - // is 16. - const maxNsplit = 16 - if nsplit > maxNsplit { - panic("freetype/raster: Add2 nsplit too large: " + strconv.Itoa(nsplit)) - } - // Recursively decompose the curve nSplit levels deep. - var ( - pStack [2*maxNsplit + 3]fixed.Point26_6 - sStack [maxNsplit + 1]int - i int - ) - sStack[0] = nsplit - pStack[0] = c - pStack[1] = b - pStack[2] = r.a - for i >= 0 { - s := sStack[i] - p := pStack[2*i:] - if s > 0 { - // Split the quadratic curve p[:3] into an equivalent set of two - // shorter curves: p[:3] and p[2:5]. The new p[4] is the old p[2], - // and p[0] is unchanged. - mx := p[1].X - p[4].X = p[2].X - p[3].X = (p[4].X + mx) / 2 - p[1].X = (p[0].X + mx) / 2 - p[2].X = (p[1].X + p[3].X) / 2 - my := p[1].Y - p[4].Y = p[2].Y - p[3].Y = (p[4].Y + my) / 2 - p[1].Y = (p[0].Y + my) / 2 - p[2].Y = (p[1].Y + p[3].Y) / 2 - // The two shorter curves have one less split to do. - sStack[i] = s - 1 - sStack[i+1] = s - 1 - i++ - } else { - // Replace the level-0 quadratic with a two-linear-piece - // approximation. - midx := (p[0].X + 2*p[1].X + p[2].X) / 4 - midy := (p[0].Y + 2*p[1].Y + p[2].Y) / 4 - r.Add1(fixed.Point26_6{midx, midy}) - r.Add1(p[0]) - i-- - } - } -} - -// Add3 adds a cubic segment to the current curve. -func (r *Rasterizer) Add3(b, c, d fixed.Point26_6) { - // Calculate nSplit (the number of recursive decompositions) based on how - // 'curvy' it is. - dev2 := maxAbs(r.a.X-3*(b.X+c.X)+d.X, r.a.Y-3*(b.Y+c.Y)+d.Y) / fixed.Int26_6(r.splitScale2) - dev3 := maxAbs(r.a.X-2*b.X+d.X, r.a.Y-2*b.Y+d.Y) / fixed.Int26_6(r.splitScale3) - nsplit := 0 - for dev2 > 0 || dev3 > 0 { - dev2 /= 8 - dev3 /= 4 - nsplit++ - } - // devN is 32-bit, and nsplit++ every time we shift off 2 bits, so - // maxNsplit is 16. - const maxNsplit = 16 - if nsplit > maxNsplit { - panic("freetype/raster: Add3 nsplit too large: " + strconv.Itoa(nsplit)) - } - // Recursively decompose the curve nSplit levels deep. - var ( - pStack [3*maxNsplit + 4]fixed.Point26_6 - sStack [maxNsplit + 1]int - i int - ) - sStack[0] = nsplit - pStack[0] = d - pStack[1] = c - pStack[2] = b - pStack[3] = r.a - for i >= 0 { - s := sStack[i] - p := pStack[3*i:] - if s > 0 { - // Split the cubic curve p[:4] into an equivalent set of two - // shorter curves: p[:4] and p[3:7]. The new p[6] is the old p[3], - // and p[0] is unchanged. - m01x := (p[0].X + p[1].X) / 2 - m12x := (p[1].X + p[2].X) / 2 - m23x := (p[2].X + p[3].X) / 2 - p[6].X = p[3].X - p[5].X = m23x - p[1].X = m01x - p[2].X = (m01x + m12x) / 2 - p[4].X = (m12x + m23x) / 2 - p[3].X = (p[2].X + p[4].X) / 2 - m01y := (p[0].Y + p[1].Y) / 2 - m12y := (p[1].Y + p[2].Y) / 2 - m23y := (p[2].Y + p[3].Y) / 2 - p[6].Y = p[3].Y - p[5].Y = m23y - p[1].Y = m01y - p[2].Y = (m01y + m12y) / 2 - p[4].Y = (m12y + m23y) / 2 - p[3].Y = (p[2].Y + p[4].Y) / 2 - // The two shorter curves have one less split to do. - sStack[i] = s - 1 - sStack[i+1] = s - 1 - i++ - } else { - // Replace the level-0 cubic with a two-linear-piece approximation. - midx := (p[0].X + 3*(p[1].X+p[2].X) + p[3].X) / 8 - midy := (p[0].Y + 3*(p[1].Y+p[2].Y) + p[3].Y) / 8 - r.Add1(fixed.Point26_6{midx, midy}) - r.Add1(p[0]) - i-- - } - } -} - -// AddPath adds the given Path. -func (r *Rasterizer) AddPath(p Path) { - for i := 0; i < len(p); { - switch p[i] { - case 0: - r.Start( - fixed.Point26_6{p[i+1], p[i+2]}, - ) - i += 4 - case 1: - r.Add1( - fixed.Point26_6{p[i+1], p[i+2]}, - ) - i += 4 - case 2: - r.Add2( - fixed.Point26_6{p[i+1], p[i+2]}, - fixed.Point26_6{p[i+3], p[i+4]}, - ) - i += 6 - case 3: - r.Add3( - fixed.Point26_6{p[i+1], p[i+2]}, - fixed.Point26_6{p[i+3], p[i+4]}, - fixed.Point26_6{p[i+5], p[i+6]}, - ) - i += 8 - default: - panic("freetype/raster: bad path") - } - } -} - -// AddStroke adds a stroked Path. -func (r *Rasterizer) AddStroke(q Path, width fixed.Int26_6, cr Capper, jr Joiner) { - Stroke(r, q, width, cr, jr) -} - -// areaToAlpha converts an area value to a uint32 alpha value. A completely -// filled pixel corresponds to an area of 64*64*2, and an alpha of 0xffff. The -// conversion of area values greater than this depends on the winding rule: -// even-odd or non-zero. -func (r *Rasterizer) areaToAlpha(area int) uint32 { - // The C Freetype implementation (version 2.3.12) does "alpha := area>>1" - // without the +1. Round-to-nearest gives a more symmetric result than - // round-down. The C implementation also returns 8-bit alpha, not 16-bit - // alpha. - a := (area + 1) >> 1 - if a < 0 { - a = -a - } - alpha := uint32(a) - if r.UseNonZeroWinding { - if alpha > 0x0fff { - alpha = 0x0fff - } - } else { - alpha &= 0x1fff - if alpha > 0x1000 { - alpha = 0x2000 - alpha - } else if alpha == 0x1000 { - alpha = 0x0fff - } - } - // alpha is now in the range [0x0000, 0x0fff]. Convert that 12-bit alpha to - // 16-bit alpha. - return alpha<<4 | alpha>>8 -} - -// Rasterize converts r's accumulated curves into Spans for p. The Spans passed -// to p are non-overlapping, and sorted by Y and then X. They all have non-zero -// width (and 0 <= X0 < X1 <= r.width) and non-zero A, except for the final -// Span, which has Y, X0, X1 and A all equal to zero. -func (r *Rasterizer) Rasterize(p Painter) { - r.saveCell() - s := 0 - for yi := 0; yi < len(r.cellIndex); yi++ { - xi, cover := 0, 0 - for c := r.cellIndex[yi]; c != -1; c = r.cell[c].next { - if cover != 0 && r.cell[c].xi > xi { - alpha := r.areaToAlpha(cover * 64 * 2) - if alpha != 0 { - xi0, xi1 := xi, r.cell[c].xi - if xi0 < 0 { - xi0 = 0 - } - if xi1 >= r.width { - xi1 = r.width - } - if xi0 < xi1 { - r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha} - s++ - } - } - } - cover += r.cell[c].cover - alpha := r.areaToAlpha(cover*64*2 - r.cell[c].area) - xi = r.cell[c].xi + 1 - if alpha != 0 { - xi0, xi1 := r.cell[c].xi, xi - if xi0 < 0 { - xi0 = 0 - } - if xi1 >= r.width { - xi1 = r.width - } - if xi0 < xi1 { - r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha} - s++ - } - } - if s > len(r.spanBuf)-2 { - p.Paint(r.spanBuf[:s], false) - s = 0 - } - } - } - p.Paint(r.spanBuf[:s], true) -} - -// Clear cancels any previous calls to r.Start or r.AddXxx. -func (r *Rasterizer) Clear() { - r.a = fixed.Point26_6{} - r.xi = 0 - r.yi = 0 - r.area = 0 - r.cover = 0 - r.cell = r.cell[:0] - for i := 0; i < len(r.cellIndex); i++ { - r.cellIndex[i] = -1 - } -} - -// SetBounds sets the maximum width and height of the rasterized image and -// calls Clear. The width and height are in pixels, not fixed.Int26_6 units. -func (r *Rasterizer) SetBounds(width, height int) { - if width < 0 { - width = 0 - } - if height < 0 { - height = 0 - } - // Use the same ssN heuristic as the C Freetype (version 2.4.0) - // implementation. - ss2, ss3 := 32, 16 - if width > 24 || height > 24 { - ss2, ss3 = 2*ss2, 2*ss3 - if width > 120 || height > 120 { - ss2, ss3 = 2*ss2, 2*ss3 - } - } - r.width = width - r.splitScale2 = ss2 - r.splitScale3 = ss3 - r.cell = r.cellBuf[:0] - if height > len(r.cellIndexBuf) { - r.cellIndex = make([]int, height) - } else { - r.cellIndex = r.cellIndexBuf[:height] - } - r.Clear() -} - -// NewRasterizer creates a new Rasterizer with the given bounds. -func NewRasterizer(width, height int) *Rasterizer { - r := new(Rasterizer) - r.SetBounds(width, height) - return r -} diff --git a/Godeps/_workspace/src/github.com/golang/freetype/raster/stroke.go b/Godeps/_workspace/src/github.com/golang/freetype/raster/stroke.go deleted file mode 100644 index 8d4379757..000000000 --- a/Godeps/_workspace/src/github.com/golang/freetype/raster/stroke.go +++ /dev/null @@ -1,483 +0,0 @@ -// Copyright 2010 The Freetype-Go Authors. All rights reserved. -// Use of this source code is governed by your choice of either the -// FreeType License or the GNU General Public License version 2 (or -// any later version), both of which can be found in the LICENSE file. - -package raster - -import ( - "golang.org/x/image/math/fixed" -) - -// Two points are considered practically equal if the square of the distance -// between them is less than one quarter (i.e. 1024 / 4096). -const epsilon = fixed.Int52_12(1024) - -// A Capper signifies how to begin or end a stroked path. -type Capper interface { - // Cap adds a cap to p given a pivot point and the normal vector of a - // terminal segment. The normal's length is half of the stroke width. - Cap(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) -} - -// The CapperFunc type adapts an ordinary function to be a Capper. -type CapperFunc func(Adder, fixed.Int26_6, fixed.Point26_6, fixed.Point26_6) - -func (f CapperFunc) Cap(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) { - f(p, halfWidth, pivot, n1) -} - -// A Joiner signifies how to join interior nodes of a stroked path. -type Joiner interface { - // Join adds a join to the two sides of a stroked path given a pivot - // point and the normal vectors of the trailing and leading segments. - // Both normals have length equal to half of the stroke width. - Join(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) -} - -// The JoinerFunc type adapts an ordinary function to be a Joiner. -type JoinerFunc func(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) - -func (f JoinerFunc) Join(lhs, rhs Adder, halfWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) { - f(lhs, rhs, halfWidth, pivot, n0, n1) -} - -// RoundCapper adds round caps to a stroked path. -var RoundCapper Capper = CapperFunc(roundCapper) - -func roundCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) { - // The cubic Bézier approximation to a circle involves the magic number - // (√2 - 1) * 4/3, which is approximately 141/256. - const k = 141 - e := pRot90CCW(n1) - side := pivot.Add(e) - start, end := pivot.Sub(n1), pivot.Add(n1) - d, e := n1.Mul(k), e.Mul(k) - p.Add3(start.Add(e), side.Sub(d), side) - p.Add3(side.Add(d), end.Add(e), end) -} - -// ButtCapper adds butt caps to a stroked path. -var ButtCapper Capper = CapperFunc(buttCapper) - -func buttCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) { - p.Add1(pivot.Add(n1)) -} - -// SquareCapper adds square caps to a stroked path. -var SquareCapper Capper = CapperFunc(squareCapper) - -func squareCapper(p Adder, halfWidth fixed.Int26_6, pivot, n1 fixed.Point26_6) { - e := pRot90CCW(n1) - side := pivot.Add(e) - p.Add1(side.Sub(n1)) - p.Add1(side.Add(n1)) - p.Add1(pivot.Add(n1)) -} - -// RoundJoiner adds round joins to a stroked path. -var RoundJoiner Joiner = JoinerFunc(roundJoiner) - -func roundJoiner(lhs, rhs Adder, haflWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) { - dot := pDot(pRot90CW(n0), n1) - if dot >= 0 { - addArc(lhs, pivot, n0, n1) - rhs.Add1(pivot.Sub(n1)) - } else { - lhs.Add1(pivot.Add(n1)) - addArc(rhs, pivot, pNeg(n0), pNeg(n1)) - } -} - -// BevelJoiner adds bevel joins to a stroked path. -var BevelJoiner Joiner = JoinerFunc(bevelJoiner) - -func bevelJoiner(lhs, rhs Adder, haflWidth fixed.Int26_6, pivot, n0, n1 fixed.Point26_6) { - lhs.Add1(pivot.Add(n1)) - rhs.Add1(pivot.Sub(n1)) -} - -// addArc adds a circular arc from pivot+n0 to pivot+n1 to p. The shorter of -// the two possible arcs is taken, i.e. the one spanning <= 180 degrees. The -// two vectors n0 and n1 must be of equal length. -func addArc(p Adder, pivot, n0, n1 fixed.Point26_6) { - // r2 is the square of the length of n0. - r2 := pDot(n0, n0) - if r2 < epsilon { - // The arc radius is so small that we collapse to a straight line. - p.Add1(pivot.Add(n1)) - return - } - // We approximate the arc by 0, 1, 2 or 3 45-degree quadratic segments plus - // a final quadratic segment from s to n1. Each 45-degree segment has - // control points {1, 0}, {1, tan(π/8)} and {1/√2, 1/√2} suitably scaled, - // rotated and translated. tan(π/8) is approximately 106/256. - const tpo8 = 106 - var s fixed.Point26_6 - // We determine which octant the angle between n0 and n1 is in via three - // dot products. m0, m1 and m2 are n0 rotated clockwise by 45, 90 and 135 - // degrees. - m0 := pRot45CW(n0) - m1 := pRot90CW(n0) - m2 := pRot90CW(m0) - if pDot(m1, n1) >= 0 { - if pDot(n0, n1) >= 0 { - if pDot(m2, n1) <= 0 { - // n1 is between 0 and 45 degrees clockwise of n0. - s = n0 - } else { - // n1 is between 45 and 90 degrees clockwise of n0. - p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0)) - s = m0 - } - } else { - pm1, n0t := pivot.Add(m1), n0.Mul(tpo8) - p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0)) - p.Add2(pm1.Add(n0t), pm1) - if pDot(m0, n1) >= 0 { - // n1 is between 90 and 135 degrees clockwise of n0. - s = m1 - } else { - // n1 is between 135 and 180 degrees clockwise of n0. - p.Add2(pm1.Sub(n0t), pivot.Add(m2)) - s = m2 - } - } - } else { - if pDot(n0, n1) >= 0 { - if pDot(m0, n1) >= 0 { - // n1 is between 0 and 45 degrees counter-clockwise of n0. - s = n0 - } else { - // n1 is between 45 and 90 degrees counter-clockwise of n0. - p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2)) - s = pNeg(m2) - } - } else { - pm1, n0t := pivot.Sub(m1), n0.Mul(tpo8) - p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2)) - p.Add2(pm1.Add(n0t), pm1) - if pDot(m2, n1) <= 0 { - // n1 is between 90 and 135 degrees counter-clockwise of n0. - s = pNeg(m1) - } else { - // n1 is between 135 and 180 degrees counter-clockwise of n0. - p.Add2(pm1.Sub(n0t), pivot.Sub(m0)) - s = pNeg(m0) - } - } - } - // The final quadratic segment has two endpoints s and n1 and the middle - // control point is a multiple of s.Add(n1), i.e. it is on the angle - // bisector of those two points. The multiple ranges between 128/256 and - // 150/256 as the angle between s and n1 ranges between 0 and 45 degrees. - // - // When the angle is 0 degrees (i.e. s and n1 are coincident) then - // s.Add(n1) is twice s and so the middle control point of the degenerate - // quadratic segment should be half s.Add(n1), and half = 128/256. - // - // When the angle is 45 degrees then 150/256 is the ratio of the lengths of - // the two vectors {1, tan(π/8)} and {1 + 1/√2, 1/√2}. - // - // d is the normalized dot product between s and n1. Since the angle ranges - // between 0 and 45 degrees then d ranges between 256/256 and 181/256. - d := 256 * pDot(s, n1) / r2 - multiple := fixed.Int26_6(150-(150-128)*(d-181)/(256-181)) >> 2 - p.Add2(pivot.Add(s.Add(n1).Mul(multiple)), pivot.Add(n1)) -} - -// midpoint returns the midpoint of two Points. -func midpoint(a, b fixed.Point26_6) fixed.Point26_6 { - return fixed.Point26_6{(a.X + b.X) / 2, (a.Y + b.Y) / 2} -} - -// angleGreaterThan45 returns whether the angle between two vectors is more -// than 45 degrees. -func angleGreaterThan45(v0, v1 fixed.Point26_6) bool { - v := pRot45CCW(v0) - return pDot(v, v1) < 0 || pDot(pRot90CW(v), v1) < 0 -} - -// interpolate returns the point (1-t)*a + t*b. -func interpolate(a, b fixed.Point26_6, t fixed.Int52_12) fixed.Point26_6 { - s := 1<<12 - t - x := s*fixed.Int52_12(a.X) + t*fixed.Int52_12(b.X) - y := s*fixed.Int52_12(a.Y) + t*fixed.Int52_12(b.Y) - return fixed.Point26_6{fixed.Int26_6(x >> 12), fixed.Int26_6(y >> 12)} -} - -// curviest2 returns the value of t for which the quadratic parametric curve -// (1-t)²*a + 2*t*(1-t).b + t²*c has maximum curvature. -// -// The curvature of the parametric curve f(t) = (x(t), y(t)) is -// |x′y″-y′x″| / (x′²+y′²)^(3/2). -// -// Let d = b-a and e = c-2*b+a, so that f′(t) = 2*d+2*e*t and f″(t) = 2*e. -// The curvature's numerator is (2*dx+2*ex*t)*(2*ey)-(2*dy+2*ey*t)*(2*ex), -// which simplifies to 4*dx*ey-4*dy*ex, which is constant with respect to t. -// -// Thus, curvature is extreme where the denominator is extreme, i.e. where -// (x′²+y′²) is extreme. The first order condition is that -// 2*x′*x″+2*y′*y″ = 0, or (dx+ex*t)*ex + (dy+ey*t)*ey = 0. -// Solving for t gives t = -(dx*ex+dy*ey) / (ex*ex+ey*ey). -func curviest2(a, b, c fixed.Point26_6) fixed.Int52_12 { - dx := int64(b.X - a.X) - dy := int64(b.Y - a.Y) - ex := int64(c.X - 2*b.X + a.X) - ey := int64(c.Y - 2*b.Y + a.Y) - if ex == 0 && ey == 0 { - return 2048 - } - return fixed.Int52_12(-4096 * (dx*ex + dy*ey) / (ex*ex + ey*ey)) -} - -// A stroker holds state for stroking a path. -type stroker struct { - // p is the destination that records the stroked path. - p Adder - // u is the half-width of the stroke. - u fixed.Int26_6 - // cr and jr specify how to end and connect path segments. - cr Capper - jr Joiner - // r is the reverse path. Stroking a path involves constructing two - // parallel paths 2*u apart. The first path is added immediately to p, - // the second path is accumulated in r and eventually added in reverse. - r Path - // a is the most recent segment point. anorm is the segment normal of - // length u at that point. - a, anorm fixed.Point26_6 -} - -// addNonCurvy2 adds a quadratic segment to the stroker, where the segment -// defined by (k.a, b, c) achieves maximum curvature at either k.a or c. -func (k *stroker) addNonCurvy2(b, c fixed.Point26_6) { - // We repeatedly divide the segment at its middle until it is straight - // enough to approximate the stroke by just translating the control points. - // ds and ps are stacks of depths and points. t is the top of the stack. - const maxDepth = 5 - var ( - ds [maxDepth + 1]int - ps [2*maxDepth + 3]fixed.Point26_6 - t int - ) - // Initially the ps stack has one quadratic segment of depth zero. - ds[0] = 0 - ps[2] = k.a - ps[1] = b - ps[0] = c - anorm := k.anorm - var cnorm fixed.Point26_6 - - for { - depth := ds[t] - a := ps[2*t+2] - b := ps[2*t+1] - c := ps[2*t+0] - ab := b.Sub(a) - bc := c.Sub(b) - abIsSmall := pDot(ab, ab) < fixed.Int52_12(1<<12) - bcIsSmall := pDot(bc, bc) < fixed.Int52_12(1<<12) - if abIsSmall && bcIsSmall { - // Approximate the segment by a circular arc. - cnorm = pRot90CCW(pNorm(bc, k.u)) - mac := midpoint(a, c) - addArc(k.p, mac, anorm, cnorm) - addArc(&k.r, mac, pNeg(anorm), pNeg(cnorm)) - } else if depth < maxDepth && angleGreaterThan45(ab, bc) { - // Divide the segment in two and push both halves on the stack. - mab := midpoint(a, b) - mbc := midpoint(b, c) - t++ - ds[t+0] = depth + 1 - ds[t-1] = depth + 1 - ps[2*t+2] = a - ps[2*t+1] = mab - ps[2*t+0] = midpoint(mab, mbc) - ps[2*t-1] = mbc - continue - } else { - // Translate the control points. - bnorm := pRot90CCW(pNorm(c.Sub(a), k.u)) - cnorm = pRot90CCW(pNorm(bc, k.u)) - k.p.Add2(b.Add(bnorm), c.Add(cnorm)) - k.r.Add2(b.Sub(bnorm), c.Sub(cnorm)) - } - if t == 0 { - k.a, k.anorm = c, cnorm - return - } - t-- - anorm = cnorm - } - panic("unreachable") -} - -// Add1 adds a linear segment to the stroker. -func (k *stroker) Add1(b fixed.Point26_6) { - bnorm := pRot90CCW(pNorm(b.Sub(k.a), k.u)) - if len(k.r) == 0 { - k.p.Start(k.a.Add(bnorm)) - k.r.Start(k.a.Sub(bnorm)) - } else { - k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, bnorm) - } - k.p.Add1(b.Add(bnorm)) - k.r.Add1(b.Sub(bnorm)) - k.a, k.anorm = b, bnorm -} - -// Add2 adds a quadratic segment to the stroker. -func (k *stroker) Add2(b, c fixed.Point26_6) { - ab := b.Sub(k.a) - bc := c.Sub(b) - abnorm := pRot90CCW(pNorm(ab, k.u)) - if len(k.r) == 0 { - k.p.Start(k.a.Add(abnorm)) - k.r.Start(k.a.Sub(abnorm)) - } else { - k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, abnorm) - } - - // Approximate nearly-degenerate quadratics by linear segments. - abIsSmall := pDot(ab, ab) < epsilon - bcIsSmall := pDot(bc, bc) < epsilon - if abIsSmall || bcIsSmall { - acnorm := pRot90CCW(pNorm(c.Sub(k.a), k.u)) - k.p.Add1(c.Add(acnorm)) - k.r.Add1(c.Sub(acnorm)) - k.a, k.anorm = c, acnorm - return - } - - // The quadratic segment (k.a, b, c) has a point of maximum curvature. - // If this occurs at an end point, we process the segment as a whole. - t := curviest2(k.a, b, c) - if t <= 0 || 4096 <= t { - k.addNonCurvy2(b, c) - return - } - - // Otherwise, we perform a de Casteljau decomposition at the point of - // maximum curvature and process the two straighter parts. - mab := interpolate(k.a, b, t) - mbc := interpolate(b, c, t) - mabc := interpolate(mab, mbc, t) - - // If the vectors ab and bc are close to being in opposite directions, - // then the decomposition can become unstable, so we approximate the - // quadratic segment by two linear segments joined by an arc. - bcnorm := pRot90CCW(pNorm(bc, k.u)) - if pDot(abnorm, bcnorm) < -fixed.Int52_12(k.u)*fixed.Int52_12(k.u)*2047/2048 { - pArc := pDot(abnorm, bc) < 0 - - k.p.Add1(mabc.Add(abnorm)) - if pArc { - z := pRot90CW(abnorm) - addArc(k.p, mabc, abnorm, z) - addArc(k.p, mabc, z, bcnorm) - } - k.p.Add1(mabc.Add(bcnorm)) - k.p.Add1(c.Add(bcnorm)) - - k.r.Add1(mabc.Sub(abnorm)) - if !pArc { - z := pRot90CW(abnorm) - addArc(&k.r, mabc, pNeg(abnorm), z) - addArc(&k.r, mabc, z, pNeg(bcnorm)) - } - k.r.Add1(mabc.Sub(bcnorm)) - k.r.Add1(c.Sub(bcnorm)) - - k.a, k.anorm = c, bcnorm - return - } - - // Process the decomposed parts. - k.addNonCurvy2(mab, mabc) - k.addNonCurvy2(mbc, c) -} - -// Add3 adds a cubic segment to the stroker. -func (k *stroker) Add3(b, c, d fixed.Point26_6) { - panic("freetype/raster: stroke unimplemented for cubic segments") -} - -// stroke adds the stroked Path q to p, where q consists of exactly one curve. -func (k *stroker) stroke(q Path) { - // Stroking is implemented by deriving two paths each k.u apart from q. - // The left-hand-side path is added immediately to k.p; the right-hand-side - // path is accumulated in k.r. Once we've finished adding the LHS to k.p, - // we add the RHS in reverse order. - k.r = make(Path, 0, len(q)) - k.a = fixed.Point26_6{q[1], q[2]} - for i := 4; i < len(q); { - switch q[i] { - case 1: - k.Add1( - fixed.Point26_6{q[i+1], q[i+2]}, - ) - i += 4 - case 2: - k.Add2( - fixed.Point26_6{q[i+1], q[i+2]}, - fixed.Point26_6{q[i+3], q[i+4]}, - ) - i += 6 - case 3: - k.Add3( - fixed.Point26_6{q[i+1], q[i+2]}, - fixed.Point26_6{q[i+3], q[i+4]}, - fixed.Point26_6{q[i+5], q[i+6]}, - ) - i += 8 - default: - panic("freetype/raster: bad path") - } - } - if len(k.r) == 0 { - return - } - // TODO(nigeltao): if q is a closed curve then we should join the first and - // last segments instead of capping them. - k.cr.Cap(k.p, k.u, q.lastPoint(), pNeg(k.anorm)) - addPathReversed(k.p, k.r) - pivot := q.firstPoint() - k.cr.Cap(k.p, k.u, pivot, pivot.Sub(fixed.Point26_6{k.r[1], k.r[2]})) -} - -// Stroke adds q stroked with the given width to p. The result is typically -// self-intersecting and should be rasterized with UseNonZeroWinding. -// cr and jr may be nil, which defaults to a RoundCapper or RoundJoiner. -func Stroke(p Adder, q Path, width fixed.Int26_6, cr Capper, jr Joiner) { - if len(q) == 0 { - return - } - if cr == nil { - cr = RoundCapper - } - if jr == nil { - jr = RoundJoiner - } - if q[0] != 0 { - panic("freetype/raster: bad path") - } - s := stroker{p: p, u: width / 2, cr: cr, jr: jr} - i := 0 - for j := 4; j < len(q); { - switch q[j] { - case 0: - s.stroke(q[i:j]) - i, j = j, j+4 - case 1: - j += 4 - case 2: - j += 6 - case 3: - j += 8 - default: - panic("freetype/raster: bad path") - } - } - s.stroke(q[i:]) -} -- cgit v1.2.3-1-g7c22