vector.go

Documentation: golang.org/x/image/vector

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:generate go run gen.go
     6  //go:generate asmfmt -w acc_amd64.s
     7  
     8  // asmfmt is https://github.com/klauspost/asmfmt
     9  
    10  // Package vector provides a rasterizer for 2-D vector graphics.
    11  package vector // import "golang.org/x/image/vector"
    12  
    13  // The rasterizer's design follows
    14  // https://medium.com/@raphlinus/inside-the-fastest-font-renderer-in-the-world-75ae5270c445
    15  //
    16  // Proof of concept code is in
    17  // https://github.com/google/font-go
    18  //
    19  // See also:
    20  // http://nothings.org/gamedev/rasterize/
    21  // http://projects.tuxee.net/cl-vectors/section-the-cl-aa-algorithm
    22  // https://people.gnome.org/~mathieu/libart/internals.html#INTERNALS-SCANLINE
    23  
    24  import (
    25  	"image"
    26  	"image/color"
    27  	"image/draw"
    28  	"math"
    29  )
    30  
    31  // floatingPointMathThreshold is the width or height above which the rasterizer
    32  // chooses to used floating point math instead of fixed point math.
    33  //
    34  // Both implementations of line segmentation rasterization (see raster_fixed.go
    35  // and raster_floating.go) implement the same algorithm (in ideal, infinite
    36  // precision math) but they perform differently in practice. The fixed point
    37  // math version is roughtly 1.25x faster (on GOARCH=amd64) on the benchmarks,
    38  // but at sufficiently large scales, the computations will overflow and hence
    39  // show rendering artifacts. The floating point math version has more
    40  // consistent quality over larger scales, but it is significantly slower.
    41  //
    42  // This constant determines when to use the faster implementation and when to
    43  // use the better quality implementation.
    44  //
    45  // The rationale for this particular value is that TestRasterizePolygon in
    46  // vector_test.go checks the rendering quality of polygon edges at various
    47  // angles, inscribed in a circle of diameter 512. It may be that a higher value
    48  // would still produce acceptable quality, but 512 seems to work.
    49  const floatingPointMathThreshold = 512
    50  
    51  func lerp(t, px, py, qx, qy float32) (x, y float32) {
    52  	return px + t*(qx-px), py + t*(qy-py)
    53  }
    54  
    55  func clamp(i, width int32) uint {
    56  	if i < 0 {
    57  		return 0
    58  	}
    59  	if i < width {
    60  		return uint(i)
    61  	}
    62  	return uint(width)
    63  }
    64  
    65  // NewRasterizer returns a new Rasterizer whose rendered mask image is bounded
    66  // by the given width and height.
    67  func NewRasterizer(w, h int) *Rasterizer {
    68  	z := &Rasterizer{}
    69  	z.Reset(w, h)
    70  	return z
    71  }
    72  
    73  // Raster is a 2-D vector graphics rasterizer.
    74  //
    75  // The zero value is usable, in that it is a Rasterizer whose rendered mask
    76  // image has zero width and zero height. Call Reset to change its bounds.
    77  type Rasterizer struct {
    78  	// bufXxx are buffers of float32 or uint32 values, holding either the
    79  	// individual or cumulative area values.
    80  	//
    81  	// We don't actually need both values at any given time, and to conserve
    82  	// memory, the integration of the individual to the cumulative could modify
    83  	// the buffer in place. In other words, we could use a single buffer, say
    84  	// of type []uint32, and add some math.Float32bits and math.Float32frombits
    85  	// calls to satisfy the compiler's type checking. As of Go 1.7, though,
    86  	// there is a performance penalty between:
    87  	//	bufF32[i] += x
    88  	// and
    89  	//	bufU32[i] = math.Float32bits(x + math.Float32frombits(bufU32[i]))
    90  	//
    91  	// See golang.org/issue/17220 for some discussion.
    92  	bufF32 []float32
    93  	bufU32 []uint32
    94  
    95  	useFloatingPointMath bool
    96  
    97  	size   image.Point
    98  	firstX float32
    99  	firstY float32
   100  	penX   float32
   101  	penY   float32
   102  
   103  	// DrawOp is the operator used for the Draw method.
   104  	//
   105  	// The zero value is draw.Over.
   106  	DrawOp draw.Op
   107  
   108  	// TODO: an exported field equivalent to the mask point in the
   109  	// draw.DrawMask function in the stdlib image/draw package?
   110  }
   111  
   112  // Reset resets a Rasterizer as if it was just returned by NewRasterizer.
   113  //
   114  // This includes setting z.DrawOp to draw.Over.
   115  func (z *Rasterizer) Reset(w, h int) {
   116  	z.size = image.Point{w, h}
   117  	z.firstX = 0
   118  	z.firstY = 0
   119  	z.penX = 0
   120  	z.penY = 0
   121  	z.DrawOp = draw.Over
   122  
   123  	z.setUseFloatingPointMath(w > floatingPointMathThreshold || h > floatingPointMathThreshold)
   124  }
   125  
   126  func (z *Rasterizer) setUseFloatingPointMath(b bool) {
   127  	z.useFloatingPointMath = b
   128  
   129  	// Make z.bufF32 or z.bufU32 large enough to hold width * height samples.
   130  	if z.useFloatingPointMath {
   131  		if n := z.size.X * z.size.Y; n > cap(z.bufF32) {
   132  			z.bufF32 = make([]float32, n)
   133  		} else {
   134  			z.bufF32 = z.bufF32[:n]
   135  			for i := range z.bufF32 {
   136  				z.bufF32[i] = 0
   137  			}
   138  		}
   139  	} else {
   140  		if n := z.size.X * z.size.Y; n > cap(z.bufU32) {
   141  			z.bufU32 = make([]uint32, n)
   142  		} else {
   143  			z.bufU32 = z.bufU32[:n]
   144  			for i := range z.bufU32 {
   145  				z.bufU32[i] = 0
   146  			}
   147  		}
   148  	}
   149  }
   150  
   151  // Size returns the width and height passed to NewRasterizer or Reset.
   152  func (z *Rasterizer) Size() image.Point {
   153  	return z.size
   154  }
   155  
   156  // Bounds returns the rectangle from (0, 0) to the width and height passed to
   157  // NewRasterizer or Reset.
   158  func (z *Rasterizer) Bounds() image.Rectangle {
   159  	return image.Rectangle{Max: z.size}
   160  }
   161  
   162  // Pen returns the location of the path-drawing pen: the last argument to the
   163  // most recent XxxTo call.
   164  func (z *Rasterizer) Pen() (x, y float32) {
   165  	return z.penX, z.penY
   166  }
   167  
   168  // ClosePath closes the current path.
   169  func (z *Rasterizer) ClosePath() {
   170  	z.LineTo(z.firstX, z.firstY)
   171  }
   172  
   173  // MoveTo starts a new path and moves the pen to (ax, ay).
   174  //
   175  // The coordinates are allowed to be out of the Rasterizer's bounds.
   176  func (z *Rasterizer) MoveTo(ax, ay float32) {
   177  	z.firstX = ax
   178  	z.firstY = ay
   179  	z.penX = ax
   180  	z.penY = ay
   181  }
   182  
   183  // LineTo adds a line segment, from the pen to (bx, by), and moves the pen to
   184  // (bx, by).
   185  //
   186  // The coordinates are allowed to be out of the Rasterizer's bounds.
   187  func (z *Rasterizer) LineTo(bx, by float32) {
   188  	if z.useFloatingPointMath {
   189  		z.floatingLineTo(bx, by)
   190  	} else {
   191  		z.fixedLineTo(bx, by)
   192  	}
   193  }
   194  
   195  // QuadTo adds a quadratic Bézier segment, from the pen via (bx, by) to (cx,
   196  // cy), and moves the pen to (cx, cy).
   197  //
   198  // The coordinates are allowed to be out of the Rasterizer's bounds.
   199  func (z *Rasterizer) QuadTo(bx, by, cx, cy float32) {
   200  	ax, ay := z.penX, z.penY
   201  	devsq := devSquared(ax, ay, bx, by, cx, cy)
   202  	if devsq >= 0.333 {
   203  		const tol = 3
   204  		n := 1 + int(math.Sqrt(math.Sqrt(tol*float64(devsq))))
   205  		t, nInv := float32(0), 1/float32(n)
   206  		for i := 0; i < n-1; i++ {
   207  			t += nInv
   208  			abx, aby := lerp(t, ax, ay, bx, by)
   209  			bcx, bcy := lerp(t, bx, by, cx, cy)
   210  			z.LineTo(lerp(t, abx, aby, bcx, bcy))
   211  		}
   212  	}
   213  	z.LineTo(cx, cy)
   214  }
   215  
   216  // CubeTo adds a cubic Bézier segment, from the pen via (bx, by) and (cx, cy)
   217  // to (dx, dy), and moves the pen to (dx, dy).
   218  //
   219  // The coordinates are allowed to be out of the Rasterizer's bounds.
   220  func (z *Rasterizer) CubeTo(bx, by, cx, cy, dx, dy float32) {
   221  	ax, ay := z.penX, z.penY
   222  	devsq := devSquared(ax, ay, bx, by, dx, dy)
   223  	if devsqAlt := devSquared(ax, ay, cx, cy, dx, dy); devsq < devsqAlt {
   224  		devsq = devsqAlt
   225  	}
   226  	if devsq >= 0.333 {
   227  		const tol = 3
   228  		n := 1 + int(math.Sqrt(math.Sqrt(tol*float64(devsq))))
   229  		t, nInv := float32(0), 1/float32(n)
   230  		for i := 0; i < n-1; i++ {
   231  			t += nInv
   232  			abx, aby := lerp(t, ax, ay, bx, by)
   233  			bcx, bcy := lerp(t, bx, by, cx, cy)
   234  			cdx, cdy := lerp(t, cx, cy, dx, dy)
   235  			abcx, abcy := lerp(t, abx, aby, bcx, bcy)
   236  			bcdx, bcdy := lerp(t, bcx, bcy, cdx, cdy)
   237  			z.LineTo(lerp(t, abcx, abcy, bcdx, bcdy))
   238  		}
   239  	}
   240  	z.LineTo(dx, dy)
   241  }
   242  
   243  // devSquared returns a measure of how curvy the sequence (ax, ay) to (bx, by)
   244  // to (cx, cy) is. It determines how many line segments will approximate a
   245  // Bézier curve segment.
   246  //
   247  // http://lists.nongnu.org/archive/html/freetype-devel/2016-08/msg00080.html
   248  // gives the rationale for this evenly spaced heuristic instead of a recursive
   249  // de Casteljau approach:
   250  //
   251  // The reason for the subdivision by n is that I expect the "flatness"
   252  // computation to be semi-expensive (it's done once rather than on each
   253  // potential subdivision) and also because you'll often get fewer subdivisions.
   254  // Taking a circular arc as a simplifying assumption (ie a spherical cow),
   255  // where I get n, a recursive approach would get 2^⌈lg n⌉, which, if I haven't
   256  // made any horrible mistakes, is expected to be 33% more in the limit.
   257  func devSquared(ax, ay, bx, by, cx, cy float32) float32 {
   258  	devx := ax - 2*bx + cx
   259  	devy := ay - 2*by + cy
   260  	return devx*devx + devy*devy
   261  }
   262  
   263  // Draw implements the Drawer interface from the standard library's image/draw
   264  // package.
   265  //
   266  // The vector paths previously added via the XxxTo calls become the mask for
   267  // drawing src onto dst.
   268  func (z *Rasterizer) Draw(dst draw.Image, r image.Rectangle, src image.Image, sp image.Point) {
   269  	// TODO: adjust r and sp (and mp?) if src.Bounds() doesn't contain
   270  	// r.Add(sp.Sub(r.Min)).
   271  
   272  	if src, ok := src.(*image.Uniform); ok {
   273  		srcR, srcG, srcB, srcA := src.RGBA()
   274  		switch dst := dst.(type) {
   275  		case *image.Alpha:
   276  			// Fast path for glyph rendering.
   277  			if srcA == 0xffff {
   278  				if z.DrawOp == draw.Over {
   279  					z.rasterizeDstAlphaSrcOpaqueOpOver(dst, r)
   280  				} else {
   281  					z.rasterizeDstAlphaSrcOpaqueOpSrc(dst, r)
   282  				}
   283  				return
   284  			}
   285  		case *image.RGBA:
   286  			if z.DrawOp == draw.Over {
   287  				z.rasterizeDstRGBASrcUniformOpOver(dst, r, srcR, srcG, srcB, srcA)
   288  			} else {
   289  				z.rasterizeDstRGBASrcUniformOpSrc(dst, r, srcR, srcG, srcB, srcA)
   290  			}
   291  			return
   292  		}
   293  	}
   294  
   295  	if z.DrawOp == draw.Over {
   296  		z.rasterizeOpOver(dst, r, src, sp)
   297  	} else {
   298  		z.rasterizeOpSrc(dst, r, src, sp)
   299  	}
   300  }
   301  
   302  func (z *Rasterizer) accumulateMask() {
   303  	if z.useFloatingPointMath {
   304  		if n := z.size.X * z.size.Y; n > cap(z.bufU32) {
   305  			z.bufU32 = make([]uint32, n)
   306  		} else {
   307  			z.bufU32 = z.bufU32[:n]
   308  		}
   309  		if haveAccumulateSIMD {
   310  			floatingAccumulateMaskSIMD(z.bufU32, z.bufF32)
   311  		} else {
   312  			floatingAccumulateMask(z.bufU32, z.bufF32)
   313  		}
   314  	} else {
   315  		if haveAccumulateSIMD {
   316  			fixedAccumulateMaskSIMD(z.bufU32)
   317  		} else {
   318  			fixedAccumulateMask(z.bufU32)
   319  		}
   320  	}
   321  }
   322  
   323  func (z *Rasterizer) rasterizeDstAlphaSrcOpaqueOpOver(dst *image.Alpha, r image.Rectangle) {
   324  	// TODO: non-zero vs even-odd winding?
   325  	if r == dst.Bounds() && r == z.Bounds() {
   326  		// We bypass the z.accumulateMask step and convert straight from
   327  		// z.bufF32 or z.bufU32 to dst.Pix.
   328  		if z.useFloatingPointMath {
   329  			if haveAccumulateSIMD {
   330  				floatingAccumulateOpOverSIMD(dst.Pix, z.bufF32)
   331  			} else {
   332  				floatingAccumulateOpOver(dst.Pix, z.bufF32)
   333  			}
   334  		} else {
   335  			if haveAccumulateSIMD {
   336  				fixedAccumulateOpOverSIMD(dst.Pix, z.bufU32)
   337  			} else {
   338  				fixedAccumulateOpOver(dst.Pix, z.bufU32)
   339  			}
   340  		}
   341  		return
   342  	}
   343  
   344  	z.accumulateMask()
   345  	pix := dst.Pix[dst.PixOffset(r.Min.X, r.Min.Y):]
   346  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   347  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   348  			ma := z.bufU32[y*z.size.X+x]
   349  			i := y*dst.Stride + x
   350  
   351  			// This formula is like rasterizeOpOver's, simplified for the
   352  			// concrete dst type and opaque src assumption.
   353  			a := 0xffff - ma
   354  			pix[i] = uint8((uint32(pix[i])*0x101*a/0xffff + ma) >> 8)
   355  		}
   356  	}
   357  }
   358  
   359  func (z *Rasterizer) rasterizeDstAlphaSrcOpaqueOpSrc(dst *image.Alpha, r image.Rectangle) {
   360  	// TODO: non-zero vs even-odd winding?
   361  	if r == dst.Bounds() && r == z.Bounds() {
   362  		// We bypass the z.accumulateMask step and convert straight from
   363  		// z.bufF32 or z.bufU32 to dst.Pix.
   364  		if z.useFloatingPointMath {
   365  			if haveAccumulateSIMD {
   366  				floatingAccumulateOpSrcSIMD(dst.Pix, z.bufF32)
   367  			} else {
   368  				floatingAccumulateOpSrc(dst.Pix, z.bufF32)
   369  			}
   370  		} else {
   371  			if haveAccumulateSIMD {
   372  				fixedAccumulateOpSrcSIMD(dst.Pix, z.bufU32)
   373  			} else {
   374  				fixedAccumulateOpSrc(dst.Pix, z.bufU32)
   375  			}
   376  		}
   377  		return
   378  	}
   379  
   380  	z.accumulateMask()
   381  	pix := dst.Pix[dst.PixOffset(r.Min.X, r.Min.Y):]
   382  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   383  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   384  			ma := z.bufU32[y*z.size.X+x]
   385  
   386  			// This formula is like rasterizeOpSrc's, simplified for the
   387  			// concrete dst type and opaque src assumption.
   388  			pix[y*dst.Stride+x] = uint8(ma >> 8)
   389  		}
   390  	}
   391  }
   392  
   393  func (z *Rasterizer) rasterizeDstRGBASrcUniformOpOver(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) {
   394  	z.accumulateMask()
   395  	pix := dst.Pix[dst.PixOffset(r.Min.X, r.Min.Y):]
   396  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   397  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   398  			ma := z.bufU32[y*z.size.X+x]
   399  
   400  			// This formula is like rasterizeOpOver's, simplified for the
   401  			// concrete dst type and uniform src assumption.
   402  			a := 0xffff - (sa * ma / 0xffff)
   403  			i := y*dst.Stride + 4*x
   404  			pix[i+0] = uint8(((uint32(pix[i+0])*0x101*a + sr*ma) / 0xffff) >> 8)
   405  			pix[i+1] = uint8(((uint32(pix[i+1])*0x101*a + sg*ma) / 0xffff) >> 8)
   406  			pix[i+2] = uint8(((uint32(pix[i+2])*0x101*a + sb*ma) / 0xffff) >> 8)
   407  			pix[i+3] = uint8(((uint32(pix[i+3])*0x101*a + sa*ma) / 0xffff) >> 8)
   408  		}
   409  	}
   410  }
   411  
   412  func (z *Rasterizer) rasterizeDstRGBASrcUniformOpSrc(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) {
   413  	z.accumulateMask()
   414  	pix := dst.Pix[dst.PixOffset(r.Min.X, r.Min.Y):]
   415  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   416  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   417  			ma := z.bufU32[y*z.size.X+x]
   418  
   419  			// This formula is like rasterizeOpSrc's, simplified for the
   420  			// concrete dst type and uniform src assumption.
   421  			i := y*dst.Stride + 4*x
   422  			pix[i+0] = uint8((sr * ma / 0xffff) >> 8)
   423  			pix[i+1] = uint8((sg * ma / 0xffff) >> 8)
   424  			pix[i+2] = uint8((sb * ma / 0xffff) >> 8)
   425  			pix[i+3] = uint8((sa * ma / 0xffff) >> 8)
   426  		}
   427  	}
   428  }
   429  
   430  func (z *Rasterizer) rasterizeOpOver(dst draw.Image, r image.Rectangle, src image.Image, sp image.Point) {
   431  	z.accumulateMask()
   432  	out := color.RGBA64{}
   433  	outc := color.Color(&out)
   434  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   435  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   436  			sr, sg, sb, sa := src.At(sp.X+x, sp.Y+y).RGBA()
   437  			ma := z.bufU32[y*z.size.X+x]
   438  
   439  			// This algorithm comes from the standard library's image/draw
   440  			// package.
   441  			dr, dg, db, da := dst.At(r.Min.X+x, r.Min.Y+y).RGBA()
   442  			a := 0xffff - (sa * ma / 0xffff)
   443  			out.R = uint16((dr*a + sr*ma) / 0xffff)
   444  			out.G = uint16((dg*a + sg*ma) / 0xffff)
   445  			out.B = uint16((db*a + sb*ma) / 0xffff)
   446  			out.A = uint16((da*a + sa*ma) / 0xffff)
   447  
   448  			dst.Set(r.Min.X+x, r.Min.Y+y, outc)
   449  		}
   450  	}
   451  }
   452  
   453  func (z *Rasterizer) rasterizeOpSrc(dst draw.Image, r image.Rectangle, src image.Image, sp image.Point) {
   454  	z.accumulateMask()
   455  	out := color.RGBA64{}
   456  	outc := color.Color(&out)
   457  	for y, y1 := 0, r.Max.Y-r.Min.Y; y < y1; y++ {
   458  		for x, x1 := 0, r.Max.X-r.Min.X; x < x1; x++ {
   459  			sr, sg, sb, sa := src.At(sp.X+x, sp.Y+y).RGBA()
   460  			ma := z.bufU32[y*z.size.X+x]
   461  
   462  			// This algorithm comes from the standard library's image/draw
   463  			// package.
   464  			out.R = uint16(sr * ma / 0xffff)
   465  			out.G = uint16(sg * ma / 0xffff)
   466  			out.B = uint16(sb * ma / 0xffff)
   467  			out.A = uint16(sa * ma / 0xffff)
   468  
   469  			dst.Set(r.Min.X+x, r.Min.Y+y, outc)
   470  		}
   471  	}
   472  }
   473
View as plain text