diff options
Diffstat (limited to 'Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster')
4 files changed, 1617 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go new file mode 100644 index 000000000..63c86e6ab --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go @@ -0,0 +1,280 @@ +// 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" +) + +// A Fix32 is a 24.8 fixed point number. +type Fix32 int32 + +// A Fix64 is a 48.16 fixed point number. +type Fix64 int64 + +// String returns a human-readable representation of a 24.8 fixed point number. +// For example, the number one-and-a-quarter becomes "1:064". +func (x Fix32) String() string { + if x < 0 { + x = -x + return fmt.Sprintf("-%d:%03d", int32(x/256), int32(x%256)) + } + return fmt.Sprintf("%d:%03d", int32(x/256), int32(x%256)) +} + +// String returns a human-readable representation of a 48.16 fixed point number. +// For example, the number one-and-a-quarter becomes "1:16384". +func (x Fix64) String() string { + if x < 0 { + x = -x + return fmt.Sprintf("-%d:%05d", int64(x/65536), int64(x%65536)) + } + return fmt.Sprintf("%d:%05d", int64(x/65536), int64(x%65536)) +} + +// maxAbs returns the maximum of abs(a) and abs(b). +func maxAbs(a, b Fix32) Fix32 { + if a < 0 { + a = -a + } + if b < 0 { + b = -b + } + if a < b { + return b + } + return a +} + +// A Point represents a two-dimensional point or vector, in 24.8 fixed point +// format. +type Point struct { + X, Y Fix32 +} + +// String returns a human-readable representation of a Point. +func (p Point) String() string { + return "(" + p.X.String() + ", " + p.Y.String() + ")" +} + +// Add returns the vector p + q. +func (p Point) Add(q Point) Point { + return Point{p.X + q.X, p.Y + q.Y} +} + +// Sub returns the vector p - q. +func (p Point) Sub(q Point) Point { + return Point{p.X - q.X, p.Y - q.Y} +} + +// Mul returns the vector k * p. +func (p Point) Mul(k Fix32) Point { + return Point{p.X * k / 256, p.Y * k / 256} +} + +// Neg returns the vector -p, or equivalently p rotated by 180 degrees. +func (p Point) Neg() Point { + return Point{-p.X, -p.Y} +} + +// Dot returns the dot product p·q. +func (p Point) Dot(q Point) Fix64 { + px, py := int64(p.X), int64(p.Y) + qx, qy := int64(q.X), int64(q.Y) + return Fix64(px*qx + py*qy) +} + +// Len returns the length of the vector p. +func (p Point) Len() Fix32 { + // TODO(nigeltao): use fixed point math. + x := float64(p.X) + y := float64(p.Y) + return Fix32(math.Sqrt(x*x + y*y)) +} + +// Norm returns the vector p normalized to the given length, or the zero Point +// if p is degenerate. +func (p Point) Norm(length Fix32) Point { + d := p.Len() + if d == 0 { + return Point{} + } + s, t := int64(length), int64(d) + x := int64(p.X) * s / t + y := int64(p.Y) * s / t + return Point{Fix32(x), Fix32(y)} +} + +// Rot45CW 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 (p Point) Rot45CW() Point { + // 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 Point{Fix32(qx), Fix32(qy)} +} + +// Rot90CW returns the vector p rotated clockwise by 90 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot90CW is {0, 1}. +func (p Point) Rot90CW() Point { + return Point{-p.Y, p.X} +} + +// Rot135CW 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 (p Point) Rot135CW() Point { + // 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 Point{Fix32(qx), Fix32(qy)} +} + +// Rot45CCW 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 (p Point) Rot45CCW() Point { + // 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 Point{Fix32(qx), Fix32(qy)} +} + +// Rot90CCW 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 (p Point) Rot90CCW() Point { + return Point{p.Y, -p.X} +} + +// Rot135CCW 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 (p Point) Rot135CCW() Point { + // 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 Point{Fix32(qx), Fix32(qy)} +} + +// An Adder accumulates points on a curve. +type Adder interface { + // Start starts a new curve at the given point. + Start(a Point) + // Add1 adds a linear segment to the current curve. + Add1(b Point) + // Add2 adds a quadratic segment to the current curve. + Add2(b, c Point) + // Add3 adds a cubic segment to the current curve. + Add3(b, c, d Point) +} + +// 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 []Fix32 + +// 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([]Fix32(p[i+1:i+3])) + i += 4 + case 1: + s += "A1" + fmt.Sprint([]Fix32(p[i+1:i+3])) + i += 4 + case 2: + s += "A2" + fmt.Sprint([]Fix32(p[i+1:i+5])) + i += 6 + case 3: + s += "A3" + fmt.Sprint([]Fix32(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 Point) { + *p = append(*p, 0, a.X, a.Y, 0) +} + +// Add1 adds a linear segment to the current curve. +func (p *Path) Add1(b Point) { + *p = append(*p, 1, b.X, b.Y, 1) +} + +// Add2 adds a quadratic segment to the current curve. +func (p *Path) Add2(b, c Point) { + *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 Point) { + *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 Fix32, cr Capper, jr Joiner) { + Stroke(p, q, width, cr, jr) +} + +// firstPoint returns the first point in a non-empty Path. +func (p Path) firstPoint() Point { + return Point{p[1], p[2]} +} + +// lastPoint returns the last point in a non-empty Path. +func (p Path) lastPoint() Point { + return Point{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(Point{q[i-2], q[i-1]}) + case 2: + i -= 6 + p.Add2(Point{q[i+2], q[i+3]}, Point{q[i-2], q[i-1]}) + case 3: + i -= 8 + p.Add3(Point{q[i+4], q[i+5]}, Point{q[i+2], q[i+3]}, Point{q[i-2], q[i-1]}) + default: + panic("freetype/raster: bad path") + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go new file mode 100644 index 000000000..13cccc192 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go @@ -0,0 +1,292 @@ +// 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 A == 1<<32 - 1. +type Span struct { + Y, X0, X1 int + A 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 an image.Alpha +// using the Over Porter-Duff composition operator. +type AlphaOverPainter struct { + Image *image.Alpha +} + +// Paint satisfies the Painter interface by painting ss onto an image.Alpha. +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.A >> 24) + 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 an image.Alpha +// using the Src Porter-Duff composition operator. +type AlphaSrcPainter struct { + Image *image.Alpha +} + +// Paint satisfies the Painter interface by painting ss onto an image.Alpha. +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.A >> 24) + 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} +} + +type RGBAPainter struct { + // The image to compose onto. + Image *image.RGBA + // The Porter-Duff composition operator. + Op draw.Op + // The 16-bit color to paint the spans. + cr, cg, cb, ca uint32 +} + +// Paint satisfies the Painter interface by painting ss onto an image.RGBA. +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 is similar to drawGlyphOver in $GOROOT/src/pkg/image/draw/draw.go. + ma := s.A >> 16 + 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.A >= 1<<31 { + 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 { + // The wrapped Painter. + Painter Painter + // Precomputed alpha values for linear interpolation, with fully opaque == 1<<16-1. + a [256]uint16 + // 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 ( + M = 0x1010101 // 255*M == 1<<32-1 + N = 0x8080 // N = M>>9, and N < 1<<16-1 + ) + for i, s := range ss { + if s.A == 0 || s.A == 1<<32-1 { + continue + } + p, q := s.A/M, (s.A%M)>>9 + // 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 + a = (a + N/2) / N + // Convert the alpha from 16-bit (which is g.a's range) to 32-bit. + a |= a << 16 + ss[i].A = a + } + } + g.Painter.Paint(ss, done) +} + +// SetGamma sets the gamma value. +func (g *GammaCorrectionPainter) SetGamma(gamma float64) { + if gamma == 1.0 { + g.gammaIsOne = true + return + } + g.gammaIsOne = false + 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/code.google.com/p/freetype-go/freetype/raster/raster.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/raster.go new file mode 100644 index 000000000..45af7eaa2 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/raster.go @@ -0,0 +1,579 @@ +// 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. + +// The raster package provides an anti-aliasing 2-D rasterizer. +// +// It is part of the larger Freetype-Go suite of font-related packages, +// but the raster package is not specific to font rasterization, and can +// be used standalone without any other Freetype-Go 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" +) + +// 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 Point + // 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 24.8 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 Fix32) { + // Break the 24.8 fixed point X co-ordinates into integral and fractional parts. + x0i := int(x0) / 256 + x0f := x0 - Fix32(256*x0i) + x1i := int(x1) / 256 + x1f := x1 - Fix32(256*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 256 units in 24.8 fixed point format. + var ( + p, q, edge0, edge1 Fix32 + xiDelta int + ) + if dx > 0 { + p, q = (256-x0f)*dy, dx + edge0, edge1, xiDelta = 0, 256, 1 + } else { + p, q = x0f*dy, -dx + edge0, edge1, xiDelta = 256, 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 = 256 * (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(256 * 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 Point) { + r.setCell(int(a.X/256), int(a.Y/256)) + r.a = a +} + +// Add1 adds a linear segment to the current curve. +func (r *Rasterizer) Add1(b Point) { + x0, y0 := r.a.X, r.a.Y + x1, y1 := b.X, b.Y + dx, dy := x1-x0, y1-y0 + // Break the 24.8 fixed point Y co-ordinates into integral and fractional parts. + y0i := int(y0) / 256 + y0f := y0 - Fix32(256*y0i) + y1i := int(y1) / 256 + y1f := y1 - Fix32(256*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 Fix32 + yiDelta int + ) + if dy > 0 { + edge0, edge1, yiDelta = 0, 256, 1 + } else { + edge0, edge1, yiDelta = 256, 0, -1 + } + x0i, yi := int(x0)/256, y0i + x0fTimes2 := (int(x0) - (256 * 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 256 + // units in 24.8 fixed point format. + var ( + p, q, edge0, edge1 Fix32 + yiDelta int + ) + if dy > 0 { + p, q = (256-y0f)*dx, dy + edge0, edge1, yiDelta = 0, 256, 1 + } else { + p, q = y0f*dx, -dy + edge0, edge1, yiDelta = 256, 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)/256, yi) + if yi != y1i { + // Do all the intermediate scanlines. + p = 256 * 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)/256, 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 Point) { + // 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) / Fix32(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]Point + 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(Point{midx, midy}) + r.Add1(p[0]) + i-- + } + } +} + +// Add3 adds a cubic segment to the current curve. +func (r *Rasterizer) Add3(b, c, d Point) { + // 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) / Fix32(r.splitScale2) + dev3 := maxAbs(r.a.X-2*b.X+d.X, r.a.Y-2*b.Y+d.Y) / Fix32(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]Point + 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(Point{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(Point{p[i+1], p[i+2]}) + i += 4 + case 1: + r.Add1(Point{p[i+1], p[i+2]}) + i += 4 + case 2: + r.Add2(Point{p[i+1], p[i+2]}, Point{p[i+3], p[i+4]}) + i += 6 + case 3: + r.Add3(Point{p[i+1], p[i+2]}, Point{p[i+3], p[i+4]}, Point{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 Fix32, cr Capper, jr Joiner) { + Stroke(r, q, width, cr, jr) +} + +// Converts an area value to a uint32 alpha value. A completely filled pixel +// corresponds to an area of 256*256*2, and an alpha of 1<<32-1. 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 32-bit alpha. + a := (area + 1) >> 1 + if a < 0 { + a = -a + } + alpha := uint32(a) + if r.UseNonZeroWinding { + if alpha > 0xffff { + alpha = 0xffff + } + } else { + alpha &= 0x1ffff + if alpha > 0x10000 { + alpha = 0x20000 - alpha + } else if alpha == 0x10000 { + alpha = 0x0ffff + } + } + alpha |= alpha << 16 + return alpha +} + +// 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 * 256 * 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*256*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 = Point{} + 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 Fix32 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 implementation. + // The C implementation uses the values 32, 16, but those are in + // 26.6 fixed point units, and we use 24.8 fixed point everywhere. + ss2, ss3 := 128, 64 + 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/code.google.com/p/freetype-go/freetype/raster/stroke.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/stroke.go new file mode 100644 index 000000000..d49b1cee9 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/stroke.go @@ -0,0 +1,466 @@ +// 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 + +// Two points are considered practically equal if the square of the distance +// between them is less than one quarter (i.e. 16384 / 65536 in Fix64). +const epsilon = 16384 + +// 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 Fix32, pivot, n1 Point) +} + +// The CapperFunc type adapts an ordinary function to be a Capper. +type CapperFunc func(Adder, Fix32, Point, Point) + +func (f CapperFunc) Cap(p Adder, halfWidth Fix32, pivot, n1 Point) { + 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 Fix32, pivot, n0, n1 Point) +} + +// The JoinerFunc type adapts an ordinary function to be a Joiner. +type JoinerFunc func(lhs, rhs Adder, halfWidth Fix32, pivot, n0, n1 Point) + +func (f JoinerFunc) Join(lhs, rhs Adder, halfWidth Fix32, pivot, n0, n1 Point) { + 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 Fix32, pivot, n1 Point) { + // 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 := n1.Rot90CCW() + 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 Fix32, pivot, n1 Point) { + p.Add1(pivot.Add(n1)) +} + +// SquareCapper adds square caps to a stroked path. +var SquareCapper Capper = CapperFunc(squareCapper) + +func squareCapper(p Adder, halfWidth Fix32, pivot, n1 Point) { + e := n1.Rot90CCW() + 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 Fix32, pivot, n0, n1 Point) { + dot := n0.Rot90CW().Dot(n1) + if dot >= 0 { + addArc(lhs, pivot, n0, n1) + rhs.Add1(pivot.Sub(n1)) + } else { + lhs.Add1(pivot.Add(n1)) + addArc(rhs, pivot, n0.Neg(), n1.Neg()) + } +} + +// BevelJoiner adds bevel joins to a stroked path. +var BevelJoiner Joiner = JoinerFunc(bevelJoiner) + +func bevelJoiner(lhs, rhs Adder, haflWidth Fix32, pivot, n0, n1 Point) { + 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 Point) { + // r2 is the square of the length of n0. + r2 := n0.Dot(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 Point + // 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 := n0.Rot45CW() + m1 := n0.Rot90CW() + m2 := m0.Rot90CW() + if m1.Dot(n1) >= 0 { + if n0.Dot(n1) >= 0 { + if m2.Dot(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 m0.Dot(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 n0.Dot(n1) >= 0 { + if m0.Dot(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 = m2.Neg() + } + } 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 m2.Dot(n1) <= 0 { + // n1 is between 90 and 135 degrees counter-clockwise of n0. + s = m1.Neg() + } else { + // n1 is between 135 and 180 degrees counter-clockwise of n0. + p.Add2(pm1.Sub(n0t), pivot.Sub(m0)) + s = m0.Neg() + } + } + } + // 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 * s.Dot(n1) / r2 + multiple := Fix32(150 - 22*(d-181)/(256-181)) + p.Add2(pivot.Add(s.Add(n1).Mul(multiple)), pivot.Add(n1)) +} + +// midpoint returns the midpoint of two Points. +func midpoint(a, b Point) Point { + return Point{(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 Point) bool { + v := v0.Rot45CCW() + return v.Dot(v1) < 0 || v.Rot90CW().Dot(v1) < 0 +} + +// interpolate returns the point (1-t)*a + t*b. +func interpolate(a, b Point, t Fix64) Point { + s := 65536 - t + x := s*Fix64(a.X) + t*Fix64(b.X) + y := s*Fix64(a.Y) + t*Fix64(b.Y) + return Point{Fix32(x >> 16), Fix32(y >> 16)} +} + +// 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 Point) Fix64 { + 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 32768 + } + return Fix64(-65536 * (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 Fix32 + // 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 Point +} + +// 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 Point) { + // 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]Point + 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 Point + + 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 := ab.Dot(ab) < Fix64(1<<16) + bcIsSmall := bc.Dot(bc) < Fix64(1<<16) + if abIsSmall && bcIsSmall { + // Approximate the segment by a circular arc. + cnorm = bc.Norm(k.u).Rot90CCW() + mac := midpoint(a, c) + addArc(k.p, mac, anorm, cnorm) + addArc(&k.r, mac, anorm.Neg(), cnorm.Neg()) + } 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 := c.Sub(a).Norm(k.u).Rot90CCW() + cnorm = bc.Norm(k.u).Rot90CCW() + 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 Point) { + bnorm := b.Sub(k.a).Norm(k.u).Rot90CCW() + 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 Point) { + ab := b.Sub(k.a) + bc := c.Sub(b) + abnorm := ab.Norm(k.u).Rot90CCW() + 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 := ab.Dot(ab) < epsilon + bcIsSmall := bc.Dot(bc) < epsilon + if abIsSmall || bcIsSmall { + acnorm := c.Sub(k.a).Norm(k.u).Rot90CCW() + 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 || t >= 65536 { + 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 := bc.Norm(k.u).Rot90CCW() + if abnorm.Dot(bcnorm) < -Fix64(k.u)*Fix64(k.u)*2047/2048 { + pArc := abnorm.Dot(bc) < 0 + + k.p.Add1(mabc.Add(abnorm)) + if pArc { + z := abnorm.Rot90CW() + 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 := abnorm.Rot90CW() + addArc(&k.r, mabc, abnorm.Neg(), z) + addArc(&k.r, mabc, z, bcnorm.Neg()) + } + 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 Point) { + 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 = Point{q[1], q[2]} + for i := 4; i < len(q); { + switch q[i] { + case 1: + k.Add1(Point{q[i+1], q[i+2]}) + i += 4 + case 2: + k.Add2(Point{q[i+1], q[i+2]}, Point{q[i+3], q[i+4]}) + i += 6 + case 3: + k.Add3(Point{q[i+1], q[i+2]}, Point{q[i+3], q[i+4]}, Point{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(), k.anorm.Neg()) + addPathReversed(k.p, k.r) + pivot := q.firstPoint() + k.cr.Cap(k.p, k.u, pivot, pivot.Sub(Point{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 Fix32, 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:]) +} |