raster.go

Documentation: github.com/golang/freetype/raster

     1  // Copyright 2010 The Freetype-Go Authors. All rights reserved.
     2  // Use of this source code is governed by your choice of either the
     3  // FreeType License or the GNU General Public License version 2 (or
     4  // any later version), both of which can be found in the LICENSE file.
     5  
     6  // Package raster provides an anti-aliasing 2-D rasterizer.
     7  //
     8  // It is part of the larger Freetype suite of font-related packages, but the
     9  // raster package is not specific to font rasterization, and can be used
    10  // standalone without any other Freetype package.
    11  //
    12  // Rasterization is done by the same area/coverage accumulation algorithm as
    13  // the Freetype "smooth" module, and the Anti-Grain Geometry library. A
    14  // description of the area/coverage algorithm is at
    15  // http://projects.tuxee.net/cl-vectors/section-the-cl-aa-algorithm
    16  package raster // import "github.com/golang/freetype/raster"
    17  
    18  import (
    19  	"strconv"
    20  
    21  	"golang.org/x/image/math/fixed"
    22  )
    23  
    24  // A cell is part of a linked list (for a given yi co-ordinate) of accumulated
    25  // area/coverage for the pixel at (xi, yi).
    26  type cell struct {
    27  	xi          int
    28  	area, cover int
    29  	next        int
    30  }
    31  
    32  type Rasterizer struct {
    33  	// If false, the default behavior is to use the even-odd winding fill
    34  	// rule during Rasterize.
    35  	UseNonZeroWinding bool
    36  	// An offset (in pixels) to the painted spans.
    37  	Dx, Dy int
    38  
    39  	// The width of the Rasterizer. The height is implicit in len(cellIndex).
    40  	width int
    41  	// splitScaleN is the scaling factor used to determine how many times
    42  	// to decompose a quadratic or cubic segment into a linear approximation.
    43  	splitScale2, splitScale3 int
    44  
    45  	// The current pen position.
    46  	a fixed.Point26_6
    47  	// The current cell and its area/coverage being accumulated.
    48  	xi, yi      int
    49  	area, cover int
    50  
    51  	// Saved cells.
    52  	cell []cell
    53  	// Linked list of cells, one per row.
    54  	cellIndex []int
    55  	// Buffers.
    56  	cellBuf      [256]cell
    57  	cellIndexBuf [64]int
    58  	spanBuf      [64]Span
    59  }
    60  
    61  // findCell returns the index in r.cell for the cell corresponding to
    62  // (r.xi, r.yi). The cell is created if necessary.
    63  func (r *Rasterizer) findCell() int {
    64  	if r.yi < 0 || r.yi >= len(r.cellIndex) {
    65  		return -1
    66  	}
    67  	xi := r.xi
    68  	if xi < 0 {
    69  		xi = -1
    70  	} else if xi > r.width {
    71  		xi = r.width
    72  	}
    73  	i, prev := r.cellIndex[r.yi], -1
    74  	for i != -1 && r.cell[i].xi <= xi {
    75  		if r.cell[i].xi == xi {
    76  			return i
    77  		}
    78  		i, prev = r.cell[i].next, i
    79  	}
    80  	c := len(r.cell)
    81  	if c == cap(r.cell) {
    82  		buf := make([]cell, c, 4*c)
    83  		copy(buf, r.cell)
    84  		r.cell = buf[0 : c+1]
    85  	} else {
    86  		r.cell = r.cell[0 : c+1]
    87  	}
    88  	r.cell[c] = cell{xi, 0, 0, i}
    89  	if prev == -1 {
    90  		r.cellIndex[r.yi] = c
    91  	} else {
    92  		r.cell[prev].next = c
    93  	}
    94  	return c
    95  }
    96  
    97  // saveCell saves any accumulated r.area/r.cover for (r.xi, r.yi).
    98  func (r *Rasterizer) saveCell() {
    99  	if r.area != 0 || r.cover != 0 {
   100  		i := r.findCell()
   101  		if i != -1 {
   102  			r.cell[i].area += r.area
   103  			r.cell[i].cover += r.cover
   104  		}
   105  		r.area = 0
   106  		r.cover = 0
   107  	}
   108  }
   109  
   110  // setCell sets the (xi, yi) cell that r is accumulating area/coverage for.
   111  func (r *Rasterizer) setCell(xi, yi int) {
   112  	if r.xi != xi || r.yi != yi {
   113  		r.saveCell()
   114  		r.xi, r.yi = xi, yi
   115  	}
   116  }
   117  
   118  // scan accumulates area/coverage for the yi'th scanline, going from
   119  // x0 to x1 in the horizontal direction (in 26.6 fixed point co-ordinates)
   120  // and from y0f to y1f fractional vertical units within that scanline.
   121  func (r *Rasterizer) scan(yi int, x0, y0f, x1, y1f fixed.Int26_6) {
   122  	// Break the 26.6 fixed point X co-ordinates into integral and fractional parts.
   123  	x0i := int(x0) / 64
   124  	x0f := x0 - fixed.Int26_6(64*x0i)
   125  	x1i := int(x1) / 64
   126  	x1f := x1 - fixed.Int26_6(64*x1i)
   127  
   128  	// A perfectly horizontal scan.
   129  	if y0f == y1f {
   130  		r.setCell(x1i, yi)
   131  		return
   132  	}
   133  	dx, dy := x1-x0, y1f-y0f
   134  	// A single cell scan.
   135  	if x0i == x1i {
   136  		r.area += int((x0f + x1f) * dy)
   137  		r.cover += int(dy)
   138  		return
   139  	}
   140  	// There are at least two cells. Apart from the first and last cells,
   141  	// all intermediate cells go through the full width of the cell,
   142  	// or 64 units in 26.6 fixed point format.
   143  	var (
   144  		p, q, edge0, edge1 fixed.Int26_6
   145  		xiDelta            int
   146  	)
   147  	if dx > 0 {
   148  		p, q = (64-x0f)*dy, dx
   149  		edge0, edge1, xiDelta = 0, 64, 1
   150  	} else {
   151  		p, q = x0f*dy, -dx
   152  		edge0, edge1, xiDelta = 64, 0, -1
   153  	}
   154  	yDelta, yRem := p/q, p%q
   155  	if yRem < 0 {
   156  		yDelta -= 1
   157  		yRem += q
   158  	}
   159  	// Do the first cell.
   160  	xi, y := x0i, y0f
   161  	r.area += int((x0f + edge1) * yDelta)
   162  	r.cover += int(yDelta)
   163  	xi, y = xi+xiDelta, y+yDelta
   164  	r.setCell(xi, yi)
   165  	if xi != x1i {
   166  		// Do all the intermediate cells.
   167  		p = 64 * (y1f - y + yDelta)
   168  		fullDelta, fullRem := p/q, p%q
   169  		if fullRem < 0 {
   170  			fullDelta -= 1
   171  			fullRem += q
   172  		}
   173  		yRem -= q
   174  		for xi != x1i {
   175  			yDelta = fullDelta
   176  			yRem += fullRem
   177  			if yRem >= 0 {
   178  				yDelta += 1
   179  				yRem -= q
   180  			}
   181  			r.area += int(64 * yDelta)
   182  			r.cover += int(yDelta)
   183  			xi, y = xi+xiDelta, y+yDelta
   184  			r.setCell(xi, yi)
   185  		}
   186  	}
   187  	// Do the last cell.
   188  	yDelta = y1f - y
   189  	r.area += int((edge0 + x1f) * yDelta)
   190  	r.cover += int(yDelta)
   191  }
   192  
   193  // Start starts a new curve at the given point.
   194  func (r *Rasterizer) Start(a fixed.Point26_6) {
   195  	r.setCell(int(a.X/64), int(a.Y/64))
   196  	r.a = a
   197  }
   198  
   199  // Add1 adds a linear segment to the current curve.
   200  func (r *Rasterizer) Add1(b fixed.Point26_6) {
   201  	x0, y0 := r.a.X, r.a.Y
   202  	x1, y1 := b.X, b.Y
   203  	dx, dy := x1-x0, y1-y0
   204  	// Break the 26.6 fixed point Y co-ordinates into integral and fractional
   205  	// parts.
   206  	y0i := int(y0) / 64
   207  	y0f := y0 - fixed.Int26_6(64*y0i)
   208  	y1i := int(y1) / 64
   209  	y1f := y1 - fixed.Int26_6(64*y1i)
   210  
   211  	if y0i == y1i {
   212  		// There is only one scanline.
   213  		r.scan(y0i, x0, y0f, x1, y1f)
   214  
   215  	} else if dx == 0 {
   216  		// This is a vertical line segment. We avoid calling r.scan and instead
   217  		// manipulate r.area and r.cover directly.
   218  		var (
   219  			edge0, edge1 fixed.Int26_6
   220  			yiDelta      int
   221  		)
   222  		if dy > 0 {
   223  			edge0, edge1, yiDelta = 0, 64, 1
   224  		} else {
   225  			edge0, edge1, yiDelta = 64, 0, -1
   226  		}
   227  		x0i, yi := int(x0)/64, y0i
   228  		x0fTimes2 := (int(x0) - (64 * x0i)) * 2
   229  		// Do the first pixel.
   230  		dcover := int(edge1 - y0f)
   231  		darea := int(x0fTimes2 * dcover)
   232  		r.area += darea
   233  		r.cover += dcover
   234  		yi += yiDelta
   235  		r.setCell(x0i, yi)
   236  		// Do all the intermediate pixels.
   237  		dcover = int(edge1 - edge0)
   238  		darea = int(x0fTimes2 * dcover)
   239  		for yi != y1i {
   240  			r.area += darea
   241  			r.cover += dcover
   242  			yi += yiDelta
   243  			r.setCell(x0i, yi)
   244  		}
   245  		// Do the last pixel.
   246  		dcover = int(y1f - edge0)
   247  		darea = int(x0fTimes2 * dcover)
   248  		r.area += darea
   249  		r.cover += dcover
   250  
   251  	} else {
   252  		// There are at least two scanlines. Apart from the first and last
   253  		// scanlines, all intermediate scanlines go through the full height of
   254  		// the row, or 64 units in 26.6 fixed point format.
   255  		var (
   256  			p, q, edge0, edge1 fixed.Int26_6
   257  			yiDelta            int
   258  		)
   259  		if dy > 0 {
   260  			p, q = (64-y0f)*dx, dy
   261  			edge0, edge1, yiDelta = 0, 64, 1
   262  		} else {
   263  			p, q = y0f*dx, -dy
   264  			edge0, edge1, yiDelta = 64, 0, -1
   265  		}
   266  		xDelta, xRem := p/q, p%q
   267  		if xRem < 0 {
   268  			xDelta -= 1
   269  			xRem += q
   270  		}
   271  		// Do the first scanline.
   272  		x, yi := x0, y0i
   273  		r.scan(yi, x, y0f, x+xDelta, edge1)
   274  		x, yi = x+xDelta, yi+yiDelta
   275  		r.setCell(int(x)/64, yi)
   276  		if yi != y1i {
   277  			// Do all the intermediate scanlines.
   278  			p = 64 * dx
   279  			fullDelta, fullRem := p/q, p%q
   280  			if fullRem < 0 {
   281  				fullDelta -= 1
   282  				fullRem += q
   283  			}
   284  			xRem -= q
   285  			for yi != y1i {
   286  				xDelta = fullDelta
   287  				xRem += fullRem
   288  				if xRem >= 0 {
   289  					xDelta += 1
   290  					xRem -= q
   291  				}
   292  				r.scan(yi, x, edge0, x+xDelta, edge1)
   293  				x, yi = x+xDelta, yi+yiDelta
   294  				r.setCell(int(x)/64, yi)
   295  			}
   296  		}
   297  		// Do the last scanline.
   298  		r.scan(yi, x, edge0, x1, y1f)
   299  	}
   300  	// The next lineTo starts from b.
   301  	r.a = b
   302  }
   303  
   304  // Add2 adds a quadratic segment to the current curve.
   305  func (r *Rasterizer) Add2(b, c fixed.Point26_6) {
   306  	// Calculate nSplit (the number of recursive decompositions) based on how
   307  	// 'curvy' it is. Specifically, how much the middle point b deviates from
   308  	// (a+c)/2.
   309  	dev := maxAbs(r.a.X-2*b.X+c.X, r.a.Y-2*b.Y+c.Y) / fixed.Int26_6(r.splitScale2)
   310  	nsplit := 0
   311  	for dev > 0 {
   312  		dev /= 4
   313  		nsplit++
   314  	}
   315  	// dev is 32-bit, and nsplit++ every time we shift off 2 bits, so maxNsplit
   316  	// is 16.
   317  	const maxNsplit = 16
   318  	if nsplit > maxNsplit {
   319  		panic("freetype/raster: Add2 nsplit too large: " + strconv.Itoa(nsplit))
   320  	}
   321  	// Recursively decompose the curve nSplit levels deep.
   322  	var (
   323  		pStack [2*maxNsplit + 3]fixed.Point26_6
   324  		sStack [maxNsplit + 1]int
   325  		i      int
   326  	)
   327  	sStack[0] = nsplit
   328  	pStack[0] = c
   329  	pStack[1] = b
   330  	pStack[2] = r.a
   331  	for i >= 0 {
   332  		s := sStack[i]
   333  		p := pStack[2*i:]
   334  		if s > 0 {
   335  			// Split the quadratic curve p[:3] into an equivalent set of two
   336  			// shorter curves: p[:3] and p[2:5]. The new p[4] is the old p[2],
   337  			// and p[0] is unchanged.
   338  			mx := p[1].X
   339  			p[4].X = p[2].X
   340  			p[3].X = (p[4].X + mx) / 2
   341  			p[1].X = (p[0].X + mx) / 2
   342  			p[2].X = (p[1].X + p[3].X) / 2
   343  			my := p[1].Y
   344  			p[4].Y = p[2].Y
   345  			p[3].Y = (p[4].Y + my) / 2
   346  			p[1].Y = (p[0].Y + my) / 2
   347  			p[2].Y = (p[1].Y + p[3].Y) / 2
   348  			// The two shorter curves have one less split to do.
   349  			sStack[i] = s - 1
   350  			sStack[i+1] = s - 1
   351  			i++
   352  		} else {
   353  			// Replace the level-0 quadratic with a two-linear-piece
   354  			// approximation.
   355  			midx := (p[0].X + 2*p[1].X + p[2].X) / 4
   356  			midy := (p[0].Y + 2*p[1].Y + p[2].Y) / 4
   357  			r.Add1(fixed.Point26_6{midx, midy})
   358  			r.Add1(p[0])
   359  			i--
   360  		}
   361  	}
   362  }
   363  
   364  // Add3 adds a cubic segment to the current curve.
   365  func (r *Rasterizer) Add3(b, c, d fixed.Point26_6) {
   366  	// Calculate nSplit (the number of recursive decompositions) based on how
   367  	// 'curvy' it is.
   368  	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)
   369  	dev3 := maxAbs(r.a.X-2*b.X+d.X, r.a.Y-2*b.Y+d.Y) / fixed.Int26_6(r.splitScale3)
   370  	nsplit := 0
   371  	for dev2 > 0 || dev3 > 0 {
   372  		dev2 /= 8
   373  		dev3 /= 4
   374  		nsplit++
   375  	}
   376  	// devN is 32-bit, and nsplit++ every time we shift off 2 bits, so
   377  	// maxNsplit is 16.
   378  	const maxNsplit = 16
   379  	if nsplit > maxNsplit {
   380  		panic("freetype/raster: Add3 nsplit too large: " + strconv.Itoa(nsplit))
   381  	}
   382  	// Recursively decompose the curve nSplit levels deep.
   383  	var (
   384  		pStack [3*maxNsplit + 4]fixed.Point26_6
   385  		sStack [maxNsplit + 1]int
   386  		i      int
   387  	)
   388  	sStack[0] = nsplit
   389  	pStack[0] = d
   390  	pStack[1] = c
   391  	pStack[2] = b
   392  	pStack[3] = r.a
   393  	for i >= 0 {
   394  		s := sStack[i]
   395  		p := pStack[3*i:]
   396  		if s > 0 {
   397  			// Split the cubic curve p[:4] into an equivalent set of two
   398  			// shorter curves: p[:4] and p[3:7]. The new p[6] is the old p[3],
   399  			// and p[0] is unchanged.
   400  			m01x := (p[0].X + p[1].X) / 2
   401  			m12x := (p[1].X + p[2].X) / 2
   402  			m23x := (p[2].X + p[3].X) / 2
   403  			p[6].X = p[3].X
   404  			p[5].X = m23x
   405  			p[1].X = m01x
   406  			p[2].X = (m01x + m12x) / 2
   407  			p[4].X = (m12x + m23x) / 2
   408  			p[3].X = (p[2].X + p[4].X) / 2
   409  			m01y := (p[0].Y + p[1].Y) / 2
   410  			m12y := (p[1].Y + p[2].Y) / 2
   411  			m23y := (p[2].Y + p[3].Y) / 2
   412  			p[6].Y = p[3].Y
   413  			p[5].Y = m23y
   414  			p[1].Y = m01y
   415  			p[2].Y = (m01y + m12y) / 2
   416  			p[4].Y = (m12y + m23y) / 2
   417  			p[3].Y = (p[2].Y + p[4].Y) / 2
   418  			// The two shorter curves have one less split to do.
   419  			sStack[i] = s - 1
   420  			sStack[i+1] = s - 1
   421  			i++
   422  		} else {
   423  			// Replace the level-0 cubic with a two-linear-piece approximation.
   424  			midx := (p[0].X + 3*(p[1].X+p[2].X) + p[3].X) / 8
   425  			midy := (p[0].Y + 3*(p[1].Y+p[2].Y) + p[3].Y) / 8
   426  			r.Add1(fixed.Point26_6{midx, midy})
   427  			r.Add1(p[0])
   428  			i--
   429  		}
   430  	}
   431  }
   432  
   433  // AddPath adds the given Path.
   434  func (r *Rasterizer) AddPath(p Path) {
   435  	for i := 0; i < len(p); {
   436  		switch p[i] {
   437  		case 0:
   438  			r.Start(
   439  				fixed.Point26_6{p[i+1], p[i+2]},
   440  			)
   441  			i += 4
   442  		case 1:
   443  			r.Add1(
   444  				fixed.Point26_6{p[i+1], p[i+2]},
   445  			)
   446  			i += 4
   447  		case 2:
   448  			r.Add2(
   449  				fixed.Point26_6{p[i+1], p[i+2]},
   450  				fixed.Point26_6{p[i+3], p[i+4]},
   451  			)
   452  			i += 6
   453  		case 3:
   454  			r.Add3(
   455  				fixed.Point26_6{p[i+1], p[i+2]},
   456  				fixed.Point26_6{p[i+3], p[i+4]},
   457  				fixed.Point26_6{p[i+5], p[i+6]},
   458  			)
   459  			i += 8
   460  		default:
   461  			panic("freetype/raster: bad path")
   462  		}
   463  	}
   464  }
   465  
   466  // AddStroke adds a stroked Path.
   467  func (r *Rasterizer) AddStroke(q Path, width fixed.Int26_6, cr Capper, jr Joiner) {
   468  	Stroke(r, q, width, cr, jr)
   469  }
   470  
   471  // areaToAlpha converts an area value to a uint32 alpha value. A completely
   472  // filled pixel corresponds to an area of 64*64*2, and an alpha of 0xffff. The
   473  // conversion of area values greater than this depends on the winding rule:
   474  // even-odd or non-zero.
   475  func (r *Rasterizer) areaToAlpha(area int) uint32 {
   476  	// The C Freetype implementation (version 2.3.12) does "alpha := area>>1"
   477  	// without the +1. Round-to-nearest gives a more symmetric result than
   478  	// round-down. The C implementation also returns 8-bit alpha, not 16-bit
   479  	// alpha.
   480  	a := (area + 1) >> 1
   481  	if a < 0 {
   482  		a = -a
   483  	}
   484  	alpha := uint32(a)
   485  	if r.UseNonZeroWinding {
   486  		if alpha > 0x0fff {
   487  			alpha = 0x0fff
   488  		}
   489  	} else {
   490  		alpha &= 0x1fff
   491  		if alpha > 0x1000 {
   492  			alpha = 0x2000 - alpha
   493  		} else if alpha == 0x1000 {
   494  			alpha = 0x0fff
   495  		}
   496  	}
   497  	// alpha is now in the range [0x0000, 0x0fff]. Convert that 12-bit alpha to
   498  	// 16-bit alpha.
   499  	return alpha<<4 | alpha>>8
   500  }
   501  
   502  // Rasterize converts r's accumulated curves into Spans for p. The Spans passed
   503  // to p are non-overlapping, and sorted by Y and then X. They all have non-zero
   504  // width (and 0 <= X0 < X1 <= r.width) and non-zero A, except for the final
   505  // Span, which has Y, X0, X1 and A all equal to zero.
   506  func (r *Rasterizer) Rasterize(p Painter) {
   507  	r.saveCell()
   508  	s := 0
   509  	for yi := 0; yi < len(r.cellIndex); yi++ {
   510  		xi, cover := 0, 0
   511  		for c := r.cellIndex[yi]; c != -1; c = r.cell[c].next {
   512  			if cover != 0 && r.cell[c].xi > xi {
   513  				alpha := r.areaToAlpha(cover * 64 * 2)
   514  				if alpha != 0 {
   515  					xi0, xi1 := xi, r.cell[c].xi
   516  					if xi0 < 0 {
   517  						xi0 = 0
   518  					}
   519  					if xi1 >= r.width {
   520  						xi1 = r.width
   521  					}
   522  					if xi0 < xi1 {
   523  						r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha}
   524  						s++
   525  					}
   526  				}
   527  			}
   528  			cover += r.cell[c].cover
   529  			alpha := r.areaToAlpha(cover*64*2 - r.cell[c].area)
   530  			xi = r.cell[c].xi + 1
   531  			if alpha != 0 {
   532  				xi0, xi1 := r.cell[c].xi, xi
   533  				if xi0 < 0 {
   534  					xi0 = 0
   535  				}
   536  				if xi1 >= r.width {
   537  					xi1 = r.width
   538  				}
   539  				if xi0 < xi1 {
   540  					r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha}
   541  					s++
   542  				}
   543  			}
   544  			if s > len(r.spanBuf)-2 {
   545  				p.Paint(r.spanBuf[:s], false)
   546  				s = 0
   547  			}
   548  		}
   549  	}
   550  	p.Paint(r.spanBuf[:s], true)
   551  }
   552  
   553  // Clear cancels any previous calls to r.Start or r.AddXxx.
   554  func (r *Rasterizer) Clear() {
   555  	r.a = fixed.Point26_6{}
   556  	r.xi = 0
   557  	r.yi = 0
   558  	r.area = 0
   559  	r.cover = 0
   560  	r.cell = r.cell[:0]
   561  	for i := 0; i < len(r.cellIndex); i++ {
   562  		r.cellIndex[i] = -1
   563  	}
   564  }
   565  
   566  // SetBounds sets the maximum width and height of the rasterized image and
   567  // calls Clear. The width and height are in pixels, not fixed.Int26_6 units.
   568  func (r *Rasterizer) SetBounds(width, height int) {
   569  	if width < 0 {
   570  		width = 0
   571  	}
   572  	if height < 0 {
   573  		height = 0
   574  	}
   575  	// Use the same ssN heuristic as the C Freetype (version 2.4.0)
   576  	// implementation.
   577  	ss2, ss3 := 32, 16
   578  	if width > 24 || height > 24 {
   579  		ss2, ss3 = 2*ss2, 2*ss3
   580  		if width > 120 || height > 120 {
   581  			ss2, ss3 = 2*ss2, 2*ss3
   582  		}
   583  	}
   584  	r.width = width
   585  	r.splitScale2 = ss2
   586  	r.splitScale3 = ss3
   587  	r.cell = r.cellBuf[:0]
   588  	if height > len(r.cellIndexBuf) {
   589  		r.cellIndex = make([]int, height)
   590  	} else {
   591  		r.cellIndex = r.cellIndexBuf[:height]
   592  	}
   593  	r.Clear()
   594  }
   595  
   596  // NewRasterizer creates a new Rasterizer with the given bounds.
   597  func NewRasterizer(width, height int) *Rasterizer {
   598  	r := new(Rasterizer)
   599  	r.SetBounds(width, height)
   600  	return r
   601  }
   602
View as plain text