vector: new package for rasterizing 2-D graphics.
Updates golang/go#16904
Change-Id: I4e11e4e859c007c3444655a227ac935c27f3f784
Reviewed-on: https://go-review.googlesource.com/28347
Reviewed-by: David Crawshaw <crawshaw@golang.org>
diff --git a/vector/raster_floating.go b/vector/raster_floating.go
new file mode 100644
index 0000000..d03936a
--- /dev/null
+++ b/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/vector/vector.go b/vector/vector.go
new file mode 100644
index 0000000..3723a84
--- /dev/null
+++ b/vector/vector.go
@@ -0,0 +1,196 @@
+// 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) {
+ // We make a linear approximation to the curve.
+ // 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.
+ a := z.pen
+ devx := a[0] - 2*b[0] + c[0]
+ devy := a[1] - 2*b[1] + c[1]
+ devsq := devx*devx + devy*devy
+ 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
+ z.LineTo(lerp(t, lerp(t, a, b), lerp(t, b, c)))
+ }
+ }
+ z.LineTo(c)
+}
+
+// TODO: CubeTo for cubic Béziers.
+
+// 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/vector/vector_test.go b/vector/vector_test.go
new file mode 100644
index 0000000..9b8b642
--- /dev/null
+++ b/vector/vector_test.go
@@ -0,0 +1,59 @@
+// 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"
+ "testing"
+
+ "golang.org/x/image/math/f32"
+)
+
+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, 0xd4, 0xdd, 0xc5, 0xab, 0x63, 0x12, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x9f, 0xff, 0xff, 0xff, 0xff, 0xfb, 0xb3, 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x60, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf1, 0x5b, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x1f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x5b, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0xdf, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf1, 0x20, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x9f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xb3, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x5f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfb, 0x12, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x1f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x63, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0xdf, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xab, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x9f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc5, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x5f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xdd, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x1f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf4, 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.QuadTo(f32.Vec2{14, 2}, f32.Vec2{14, 14})
+ z.LineTo(f32.Vec2{5, 14})
+ 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])
+ }
+ }
+}
