From 2ca0e8f9a0f9863555a26e984cde15efff9ef8f8 Mon Sep 17 00:00:00 2001 From: Christopher Speller Date: Fri, 23 Sep 2016 10:17:51 -0400 Subject: Updating golang dependancies (#4075) --- .../golang.org/x/image/vector/raster_floating.go | 153 ++++++++++++++ vendor/golang.org/x/image/vector/vector.go | 228 +++++++++++++++++++++ vendor/golang.org/x/image/vector/vector_test.go | 76 +++++++ 3 files changed, 457 insertions(+) create mode 100644 vendor/golang.org/x/image/vector/raster_floating.go create mode 100644 vendor/golang.org/x/image/vector/vector.go create mode 100644 vendor/golang.org/x/image/vector/vector_test.go (limited to 'vendor/golang.org/x/image/vector') diff --git a/vendor/golang.org/x/image/vector/raster_floating.go b/vendor/golang.org/x/image/vector/raster_floating.go new file mode 100644 index 000000000..d03936a1e --- /dev/null +++ b/vendor/golang.org/x/image/vector/raster_floating.go @@ -0,0 +1,153 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package vector + +// This file contains a floating point math implementation of the vector +// graphics rasterizer. + +import ( + "math" + + "golang.org/x/image/math/f32" +) + +func floatingMax(x, y float32) float32 { + if x > y { + return x + } + return y +} + +func floatingMin(x, y float32) float32 { + if x < y { + return x + } + return y +} + +func floatingFloor(x float32) int32 { return int32(math.Floor(float64(x))) } +func floatingCeil(x float32) int32 { return int32(math.Ceil(float64(x))) } + +func (z *Rasterizer) floatingLineTo(b f32.Vec2) { + a := z.pen + z.pen = b + dir := float32(1) + if a[1] > b[1] { + dir, a, b = -1, b, a + } + // Horizontal line segments yield no change in coverage. Almost horizontal + // segments would yield some change, in ideal math, but the computation + // further below, involving 1 / (b[1] - a[1]), is unstable in floating + // point math, so we treat the segment as if it was perfectly horizontal. + if b[1]-a[1] <= 0.000001 { + return + } + dxdy := (b[0] - a[0]) / (b[1] - a[1]) + + x := a[0] + y := floatingFloor(a[1]) + yMax := floatingCeil(b[1]) + if yMax > int32(z.size.Y) { + yMax = int32(z.size.Y) + } + width := int32(z.size.X) + + for ; y < yMax; y++ { + dy := floatingMin(float32(y+1), b[1]) - floatingMax(float32(y), a[1]) + xNext := x + dy*dxdy + if y < 0 { + x = xNext + continue + } + buf := z.area[y*width:] + d := dy * dir + x0, x1 := x, xNext + if x > xNext { + x0, x1 = x1, x0 + } + x0i := floatingFloor(x0) + x0Floor := float32(x0i) + x1i := floatingCeil(x1) + x1Ceil := float32(x1i) + + if x1i <= x0i+1 { + xmf := 0.5*(x+xNext) - x0Floor + if i := clamp(x0i+0, width); i < uint(len(buf)) { + buf[i] += d - d*xmf + } + if i := clamp(x0i+1, width); i < uint(len(buf)) { + buf[i] += d * xmf + } + } else { + s := 1 / (x1 - x0) + x0f := x0 - x0Floor + oneMinusX0f := 1 - x0f + a0 := 0.5 * s * oneMinusX0f * oneMinusX0f + x1f := x1 - x1Ceil + 1 + am := 0.5 * s * x1f * x1f + + if i := clamp(x0i, width); i < uint(len(buf)) { + buf[i] += d * a0 + } + + if x1i == x0i+2 { + if i := clamp(x0i+1, width); i < uint(len(buf)) { + buf[i] += d * (1 - a0 - am) + } + } else { + a1 := s * (1.5 - x0f) + if i := clamp(x0i+1, width); i < uint(len(buf)) { + buf[i] += d * (a1 - a0) + } + dTimesS := d * s + for xi := x0i + 2; xi < x1i-1; xi++ { + if i := clamp(xi, width); i < uint(len(buf)) { + buf[i] += dTimesS + } + } + a2 := a1 + s*float32(x1i-x0i-3) + if i := clamp(x1i-1, width); i < uint(len(buf)) { + buf[i] += d * (1 - a2 - am) + } + } + + if i := clamp(x1i, width); i < uint(len(buf)) { + buf[i] += d * am + } + } + + x = xNext + } +} + +func floatingAccumulate(dst []uint8, src []float32) { + // almost256 scales a floating point value in the range [0, 1] to a uint8 + // value in the range [0x00, 0xff]. + // + // 255 is too small. Floating point math accumulates rounding errors, so a + // fully covered src value that would in ideal math be float32(1) might be + // float32(1-ε), and uint8(255 * (1-ε)) would be 0xfe instead of 0xff. The + // uint8 conversion rounds to zero, not to nearest. + // + // 256 is too big. If we multiplied by 256, below, then a fully covered src + // value of float32(1) would translate to uint8(256 * 1), which can be 0x00 + // instead of the maximal value 0xff. + // + // math.Float32bits(almost256) is 0x437fffff. + const almost256 = 255.99998 + + acc := float32(0) + for i, v := range src { + acc += v + a := acc + if a < 0 { + a = -a + } + if a > 1 { + a = 1 + } + dst[i] = uint8(almost256 * a) + } +} diff --git a/vendor/golang.org/x/image/vector/vector.go b/vendor/golang.org/x/image/vector/vector.go new file mode 100644 index 000000000..218e76489 --- /dev/null +++ b/vendor/golang.org/x/image/vector/vector.go @@ -0,0 +1,228 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package vector provides a rasterizer for 2-D vector graphics. +package vector // import "golang.org/x/image/vector" + +// The rasterizer's design follows +// https://medium.com/@raphlinus/inside-the-fastest-font-renderer-in-the-world-75ae5270c445 +// +// Proof of concept code is in +// https://github.com/google/font-go +// +// See also: +// http://nothings.org/gamedev/rasterize/ +// http://projects.tuxee.net/cl-vectors/section-the-cl-aa-algorithm +// https://people.gnome.org/~mathieu/libart/internals.html#INTERNALS-SCANLINE + +import ( + "image" + "image/draw" + "math" + + "golang.org/x/image/math/f32" +) + +func midPoint(p, q f32.Vec2) f32.Vec2 { + return f32.Vec2{ + (p[0] + q[0]) * 0.5, + (p[1] + q[1]) * 0.5, + } +} + +func lerp(t float32, p, q f32.Vec2) f32.Vec2 { + return f32.Vec2{ + p[0] + t*(q[0]-p[0]), + p[1] + t*(q[1]-p[1]), + } +} + +func clamp(i, width int32) uint { + if i < 0 { + return 0 + } + if i < width { + return uint(i) + } + return uint(width) +} + +// NewRasterizer returns a new Rasterizer whose rendered mask image is bounded +// by the given width and height. +func NewRasterizer(w, h int) *Rasterizer { + return &Rasterizer{ + area: make([]float32, w*h), + size: image.Point{w, h}, + } +} + +// Raster is a 2-D vector graphics rasterizer. +type Rasterizer struct { + area []float32 + size image.Point + first f32.Vec2 + pen f32.Vec2 + + // DrawOp is the operator used for the Draw method. + // + // The zero value is draw.Over. + DrawOp draw.Op + + // TODO: an exported field equivalent to the mask point in the + // draw.DrawMask function in the stdlib image/draw package? +} + +// Reset resets a Rasterizer as if it was just returned by NewRasterizer. +// +// This includes setting z.DrawOp to draw.Over. +func (z *Rasterizer) Reset(w, h int) { + if n := w * h; n > cap(z.area) { + z.area = make([]float32, n) + } else { + z.area = z.area[:n] + for i := range z.area { + z.area[i] = 0 + } + } + z.size = image.Point{w, h} + z.first = f32.Vec2{} + z.pen = f32.Vec2{} + z.DrawOp = draw.Over +} + +// Size returns the width and height passed to NewRasterizer or Reset. +func (z *Rasterizer) Size() image.Point { + return z.size +} + +// Bounds returns the rectangle from (0, 0) to the width and height passed to +// NewRasterizer or Reset. +func (z *Rasterizer) Bounds() image.Rectangle { + return image.Rectangle{Max: z.size} +} + +// Pen returns the location of the path-drawing pen: the last argument to the +// most recent XxxTo call. +func (z *Rasterizer) Pen() f32.Vec2 { + return z.pen +} + +// ClosePath closes the current path. +func (z *Rasterizer) ClosePath() { + z.LineTo(z.first) +} + +// MoveTo starts a new path and moves the pen to a. +// +// The coordinates are allowed to be out of the Rasterizer's bounds. +func (z *Rasterizer) MoveTo(a f32.Vec2) { + z.first = a + z.pen = a +} + +// LineTo adds a line segment, from the pen to b, and moves the pen to b. +// +// The coordinates are allowed to be out of the Rasterizer's bounds. +func (z *Rasterizer) LineTo(b f32.Vec2) { + // TODO: add a fixed point math implementation. + z.floatingLineTo(b) +} + +// QuadTo adds a quadratic Bézier segment, from the pen via b to c, and moves +// the pen to c. +// +// The coordinates are allowed to be out of the Rasterizer's bounds. +func (z *Rasterizer) QuadTo(b, c f32.Vec2) { + a := z.pen + devsq := devSquared(a, b, c) + if devsq >= 0.333 { + const tol = 3 + n := 1 + int(math.Sqrt(math.Sqrt(tol*float64(devsq)))) + t, nInv := float32(0), 1/float32(n) + for i := 0; i < n-1; i++ { + t += nInv + ab := lerp(t, a, b) + bc := lerp(t, b, c) + z.LineTo(lerp(t, ab, bc)) + } + } + z.LineTo(c) +} + +// CubeTo adds a cubic Bézier segment, from the pen via b and c to d, and moves +// the pen to d. +// +// The coordinates are allowed to be out of the Rasterizer's bounds. +func (z *Rasterizer) CubeTo(b, c, d f32.Vec2) { + a := z.pen + devsq := devSquared(a, b, d) + if devsqAlt := devSquared(a, c, d); devsq < devsqAlt { + devsq = devsqAlt + } + if devsq >= 0.333 { + const tol = 3 + n := 1 + int(math.Sqrt(math.Sqrt(tol*float64(devsq)))) + t, nInv := float32(0), 1/float32(n) + for i := 0; i < n-1; i++ { + t += nInv + ab := lerp(t, a, b) + bc := lerp(t, b, c) + cd := lerp(t, c, d) + abc := lerp(t, ab, bc) + bcd := lerp(t, bc, cd) + z.LineTo(lerp(t, abc, bcd)) + } + } + z.LineTo(d) +} + +// devSquared returns a measure of how curvy the sequnce a to b to c is. It +// determines how many line segments will approximate a Bézier curve segment. +// +// http://lists.nongnu.org/archive/html/freetype-devel/2016-08/msg00080.html +// gives the rationale for this evenly spaced heuristic instead of a recursive +// de Casteljau approach: +// +// The reason for the subdivision by n is that I expect the "flatness" +// computation to be semi-expensive (it's done once rather than on each +// potential subdivision) and also because you'll often get fewer subdivisions. +// Taking a circular arc as a simplifying assumption (ie a spherical cow), +// where I get n, a recursive approach would get 2^⌈lg n⌉, which, if I haven't +// made any horrible mistakes, is expected to be 33% more in the limit. +func devSquared(a, b, c f32.Vec2) float32 { + devx := a[0] - 2*b[0] + c[0] + devy := a[1] - 2*b[1] + c[1] + return devx*devx + devy*devy +} + +// Draw implements the Drawer interface from the standard library's image/draw +// package. +// +// The vector paths previously added via the XxxTo calls become the mask for +// drawing src onto dst. +func (z *Rasterizer) Draw(dst draw.Image, r image.Rectangle, src image.Image, sp image.Point) { + if src, ok := src.(*image.Uniform); ok { + _, _, _, srcA := src.RGBA() + switch dst := dst.(type) { + case *image.Alpha: + // Fast path for glyph rendering. + if srcA == 0xffff && z.DrawOp == draw.Src { + z.rasterizeDstAlphaSrcOpaqueOpSrc(dst, r) + return + } + } + } + println("TODO: the general case") +} + +func (z *Rasterizer) rasterizeDstAlphaSrcOpaqueOpSrc(dst *image.Alpha, r image.Rectangle) { + // TODO: add SIMD implementations. + // TODO: add a fixed point math implementation. + // TODO: non-zero vs even-odd winding? + if r == dst.Bounds() && r == z.Bounds() { + floatingAccumulate(dst.Pix, z.area) + return + } + println("TODO: the general case") +} diff --git a/vendor/golang.org/x/image/vector/vector_test.go b/vendor/golang.org/x/image/vector/vector_test.go new file mode 100644 index 000000000..3aa8c192f --- /dev/null +++ b/vendor/golang.org/x/image/vector/vector_test.go @@ -0,0 +1,76 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package vector + +// TODO: add tests for NaN and Inf coordinates. + +import ( + "image" + "image/draw" + "image/png" + "os" + "testing" + + "golang.org/x/image/math/f32" +) + +// encodePNG is useful for manually debugging the tests. +func encodePNG(dstFilename string, src image.Image) error { + f, err := os.Create(dstFilename) + if err != nil { + return err + } + encErr := png.Encode(f, src) + closeErr := f.Close() + if encErr != nil { + return encErr + } + return closeErr +} + +func TestBasicPath(t *testing.T) { + want := []byte{ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe3, 0xaa, 0x3e, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa, 0x5f, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x24, 0x00, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xa1, 0x00, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x14, 0x00, 0x00, + 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x4a, 0x00, 0x00, + 0x00, 0x00, 0xcc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x81, 0x00, 0x00, + 0x00, 0x00, 0x66, 0xff, 0xff, 0xff, 0xff, 0xff, 0xef, 0xe4, 0xff, 0xff, 0xff, 0xb6, 0x00, 0x00, + 0x00, 0x00, 0x0c, 0xf2, 0xff, 0xff, 0xfe, 0x9e, 0x15, 0x00, 0x15, 0x96, 0xff, 0xce, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x88, 0xfc, 0xe3, 0x43, 0x00, 0x00, 0x00, 0x00, 0x06, 0xcd, 0xdc, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x10, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x25, 0xde, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x56, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + } + + z := NewRasterizer(16, 16) + z.MoveTo(f32.Vec2{2, 2}) + z.LineTo(f32.Vec2{8, 2}) + z.QuadTo(f32.Vec2{14, 2}, f32.Vec2{14, 14}) + z.CubeTo(f32.Vec2{8, 2}, f32.Vec2{5, 20}, f32.Vec2{2, 8}) + z.ClosePath() + + dst := image.NewAlpha(z.Bounds()) + z.DrawOp = draw.Src + z.Draw(dst, dst.Bounds(), image.Opaque, image.Point{}) + + got := dst.Pix + if len(got) != len(want) { + t.Fatalf("len(got)=%d and len(want)=%d differ", len(got), len(want)) + } + for i := range got { + delta := int(got[i]) - int(want[i]) + // The +/- 2 allows different implementations to give different + // rounding errors. + if delta < -2 || +2 < delta { + t.Errorf("i=%d: got %#02x, want %#02x", i, got[i], want[i]) + } + } +} -- cgit v1.2.3-1-g7c22