scale.go

Documentation: golang.org/x/image/draw

     1  // Copyright 2015 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  
     7  package draw
     8  
     9  import (
    10  	"image"
    11  	"image/color"
    12  	"math"
    13  	"sync"
    14  
    15  	"golang.org/x/image/math/f64"
    16  )
    17  
    18  // Copy copies the part of the source image defined by src and sr and writes
    19  // the result of a Porter-Duff composition to the part of the destination image
    20  // defined by dst and the translation of sr so that sr.Min translates to dp.
    21  func Copy(dst Image, dp image.Point, src image.Image, sr image.Rectangle, op Op, opts *Options) {
    22  	var o Options
    23  	if opts != nil {
    24  		o = *opts
    25  	}
    26  	dr := sr.Add(dp.Sub(sr.Min))
    27  	if o.DstMask == nil {
    28  		DrawMask(dst, dr, src, sr.Min, o.SrcMask, o.SrcMaskP.Add(sr.Min), op)
    29  	} else {
    30  		NearestNeighbor.Scale(dst, dr, src, sr, op, opts)
    31  	}
    32  }
    33  
    34  // Scaler scales the part of the source image defined by src and sr and writes
    35  // the result of a Porter-Duff composition to the part of the destination image
    36  // defined by dst and dr.
    37  //
    38  // A Scaler is safe to use concurrently.
    39  type Scaler interface {
    40  	Scale(dst Image, dr image.Rectangle, src image.Image, sr image.Rectangle, op Op, opts *Options)
    41  }
    42  
    43  // Transformer transforms the part of the source image defined by src and sr
    44  // and writes the result of a Porter-Duff composition to the part of the
    45  // destination image defined by dst and the affine transform m applied to sr.
    46  //
    47  // For example, if m is the matrix
    48  //
    49  //	m00 m01 m02
    50  //	m10 m11 m12
    51  //
    52  // then the src-space point (sx, sy) maps to the dst-space point
    53  // (m00*sx + m01*sy + m02, m10*sx + m11*sy + m12).
    54  //
    55  // A Transformer is safe to use concurrently.
    56  type Transformer interface {
    57  	Transform(dst Image, m f64.Aff3, src image.Image, sr image.Rectangle, op Op, opts *Options)
    58  }
    59  
    60  // Options are optional parameters to Copy, Scale and Transform.
    61  //
    62  // A nil *Options means to use the default (zero) values of each field.
    63  type Options struct {
    64  	// Masks limit what parts of the dst image are drawn to and what parts of
    65  	// the src image are drawn from.
    66  	//
    67  	// A dst or src mask image having a zero alpha (transparent) pixel value in
    68  	// the respective coordinate space means that dst pixel is entirely
    69  	// unaffected or that src pixel is considered transparent black. A full
    70  	// alpha (opaque) value means that the dst pixel is maximally affected or
    71  	// the src pixel contributes maximally. The default values, nil, are
    72  	// equivalent to fully opaque, infinitely large mask images.
    73  	//
    74  	// The DstMask is otherwise known as a clip mask, and its pixels map 1:1 to
    75  	// the dst image's pixels. DstMaskP in DstMask space corresponds to
    76  	// image.Point{X:0, Y:0} in dst space. For example, when limiting
    77  	// repainting to a 'dirty rectangle', use that image.Rectangle and a zero
    78  	// image.Point as the DstMask and DstMaskP.
    79  	//
    80  	// The SrcMask's pixels map 1:1 to the src image's pixels. SrcMaskP in
    81  	// SrcMask space corresponds to image.Point{X:0, Y:0} in src space. For
    82  	// example, when drawing font glyphs in a uniform color, use an
    83  	// *image.Uniform as the src, and use the glyph atlas image and the
    84  	// per-glyph offset as SrcMask and SrcMaskP:
    85  	//	Copy(dst, dp, image.NewUniform(color), image.Rect(0, 0, glyphWidth, glyphHeight), &Options{
    86  	//		SrcMask:  glyphAtlas,
    87  	//		SrcMaskP: glyphOffset,
    88  	//	})
    89  	DstMask  image.Image
    90  	DstMaskP image.Point
    91  	SrcMask  image.Image
    92  	SrcMaskP image.Point
    93  
    94  	// TODO: a smooth vs sharp edges option, for arbitrary rotations?
    95  }
    96  
    97  // Interpolator is an interpolation algorithm, when dst and src pixels don't
    98  // have a 1:1 correspondence.
    99  //
   100  // Of the interpolators provided by this package:
   101  //   - NearestNeighbor is fast but usually looks worst.
   102  //   - CatmullRom is slow but usually looks best.
   103  //   - ApproxBiLinear has reasonable speed and quality.
   104  //
   105  // The time taken depends on the size of dr. For kernel interpolators, the
   106  // speed also depends on the size of sr, and so are often slower than
   107  // non-kernel interpolators, especially when scaling down.
   108  type Interpolator interface {
   109  	Scaler
   110  	Transformer
   111  }
   112  
   113  // Kernel is an interpolator that blends source pixels weighted by a symmetric
   114  // kernel function.
   115  type Kernel struct {
   116  	// Support is the kernel support and must be >= 0. At(t) is assumed to be
   117  	// zero when t >= Support.
   118  	Support float64
   119  	// At is the kernel function. It will only be called with t in the
   120  	// range [0, Support).
   121  	At func(t float64) float64
   122  }
   123  
   124  // Scale implements the Scaler interface.
   125  func (q *Kernel) Scale(dst Image, dr image.Rectangle, src image.Image, sr image.Rectangle, op Op, opts *Options) {
   126  	q.newScaler(dr.Dx(), dr.Dy(), sr.Dx(), sr.Dy(), false).Scale(dst, dr, src, sr, op, opts)
   127  }
   128  
   129  // NewScaler returns a Scaler that is optimized for scaling multiple times with
   130  // the same fixed destination and source width and height.
   131  func (q *Kernel) NewScaler(dw, dh, sw, sh int) Scaler {
   132  	return q.newScaler(dw, dh, sw, sh, true)
   133  }
   134  
   135  func (q *Kernel) newScaler(dw, dh, sw, sh int, usePool bool) Scaler {
   136  	z := &kernelScaler{
   137  		kernel:     q,
   138  		dw:         int32(dw),
   139  		dh:         int32(dh),
   140  		sw:         int32(sw),
   141  		sh:         int32(sh),
   142  		horizontal: newDistrib(q, int32(dw), int32(sw)),
   143  		vertical:   newDistrib(q, int32(dh), int32(sh)),
   144  	}
   145  	if usePool {
   146  		z.pool.New = func() interface{} {
   147  			tmp := z.makeTmpBuf()
   148  			return &tmp
   149  		}
   150  	}
   151  	return z
   152  }
   153  
   154  var (
   155  	// NearestNeighbor is the nearest neighbor interpolator. It is very fast,
   156  	// but usually gives very low quality results. When scaling up, the result
   157  	// will look 'blocky'.
   158  	NearestNeighbor = Interpolator(nnInterpolator{})
   159  
   160  	// ApproxBiLinear is a mixture of the nearest neighbor and bi-linear
   161  	// interpolators. It is fast, but usually gives medium quality results.
   162  	//
   163  	// It implements bi-linear interpolation when upscaling and a bi-linear
   164  	// blend of the 4 nearest neighbor pixels when downscaling. This yields
   165  	// nicer quality than nearest neighbor interpolation when upscaling, but
   166  	// the time taken is independent of the number of source pixels, unlike the
   167  	// bi-linear interpolator. When downscaling a large image, the performance
   168  	// difference can be significant.
   169  	ApproxBiLinear = Interpolator(ablInterpolator{})
   170  
   171  	// BiLinear is the tent kernel. It is slow, but usually gives high quality
   172  	// results.
   173  	BiLinear = &Kernel{1, func(t float64) float64 {
   174  		return 1 - t
   175  	}}
   176  
   177  	// CatmullRom is the Catmull-Rom kernel. It is very slow, but usually gives
   178  	// very high quality results.
   179  	//
   180  	// It is an instance of the more general cubic BC-spline kernel with parameters
   181  	// B=0 and C=0.5. See Mitchell and Netravali, "Reconstruction Filters in
   182  	// Computer Graphics", Computer Graphics, Vol. 22, No. 4, pp. 221-228.
   183  	CatmullRom = &Kernel{2, func(t float64) float64 {
   184  		if t < 1 {
   185  			return (1.5*t-2.5)*t*t + 1
   186  		}
   187  		return ((-0.5*t+2.5)*t-4)*t + 2
   188  	}}
   189  
   190  	// TODO: a Kaiser-Bessel kernel?
   191  )
   192  
   193  type nnInterpolator struct{}
   194  
   195  type ablInterpolator struct{}
   196  
   197  type kernelScaler struct {
   198  	kernel               *Kernel
   199  	dw, dh, sw, sh       int32
   200  	horizontal, vertical distrib
   201  	pool                 sync.Pool
   202  }
   203  
   204  func (z *kernelScaler) makeTmpBuf() [][4]float64 {
   205  	return make([][4]float64, z.dw*z.sh)
   206  }
   207  
   208  // source is a range of contribs, their inverse total weight, and that ITW
   209  // divided by 0xffff.
   210  type source struct {
   211  	i, j               int32
   212  	invTotalWeight     float64
   213  	invTotalWeightFFFF float64
   214  }
   215  
   216  // contrib is the weight of a column or row.
   217  type contrib struct {
   218  	coord  int32
   219  	weight float64
   220  }
   221  
   222  // distrib measures how source pixels are distributed over destination pixels.
   223  type distrib struct {
   224  	// sources are what contribs each column or row in the source image owns,
   225  	// and the total weight of those contribs.
   226  	sources []source
   227  	// contribs are the contributions indexed by sources[s].i and sources[s].j.
   228  	contribs []contrib
   229  }
   230  
   231  // newDistrib returns a distrib that distributes sw source columns (or rows)
   232  // over dw destination columns (or rows).
   233  func newDistrib(q *Kernel, dw, sw int32) distrib {
   234  	scale := float64(sw) / float64(dw)
   235  	halfWidth, kernelArgScale := q.Support, 1.0
   236  	// When shrinking, broaden the effective kernel support so that we still
   237  	// visit every source pixel.
   238  	if scale > 1 {
   239  		halfWidth *= scale
   240  		kernelArgScale = 1 / scale
   241  	}
   242  
   243  	// Make the sources slice, one source for each column or row, and temporarily
   244  	// appropriate its elements' fields so that invTotalWeight is the scaled
   245  	// coordinate of the source column or row, and i and j are the lower and
   246  	// upper bounds of the range of destination columns or rows affected by the
   247  	// source column or row.
   248  	n, sources := int32(0), make([]source, dw)
   249  	for x := range sources {
   250  		center := (float64(x)+0.5)*scale - 0.5
   251  		i := int32(math.Floor(center - halfWidth))
   252  		if i < 0 {
   253  			i = 0
   254  		}
   255  		j := int32(math.Ceil(center + halfWidth))
   256  		if j > sw {
   257  			j = sw
   258  			if j < i {
   259  				j = i
   260  			}
   261  		}
   262  		sources[x] = source{i: i, j: j, invTotalWeight: center}
   263  		n += j - i
   264  	}
   265  
   266  	contribs := make([]contrib, 0, n)
   267  	for k, b := range sources {
   268  		totalWeight := 0.0
   269  		l := int32(len(contribs))
   270  		for coord := b.i; coord < b.j; coord++ {
   271  			t := abs((b.invTotalWeight - float64(coord)) * kernelArgScale)
   272  			if t >= q.Support {
   273  				continue
   274  			}
   275  			weight := q.At(t)
   276  			if weight == 0 {
   277  				continue
   278  			}
   279  			totalWeight += weight
   280  			contribs = append(contribs, contrib{coord, weight})
   281  		}
   282  		totalWeight = 1 / totalWeight
   283  		sources[k] = source{
   284  			i:                  l,
   285  			j:                  int32(len(contribs)),
   286  			invTotalWeight:     totalWeight,
   287  			invTotalWeightFFFF: totalWeight / 0xffff,
   288  		}
   289  	}
   290  
   291  	return distrib{sources, contribs}
   292  }
   293  
   294  // abs is like math.Abs, but it doesn't care about negative zero, infinities or
   295  // NaNs.
   296  func abs(f float64) float64 {
   297  	if f < 0 {
   298  		f = -f
   299  	}
   300  	return f
   301  }
   302  
   303  // ftou converts the range [0.0, 1.0] to [0, 0xffff].
   304  func ftou(f float64) uint16 {
   305  	i := int32(0xffff*f + 0.5)
   306  	if i > 0xffff {
   307  		return 0xffff
   308  	}
   309  	if i > 0 {
   310  		return uint16(i)
   311  	}
   312  	return 0
   313  }
   314  
   315  // fffftou converts the range [0.0, 65535.0] to [0, 0xffff].
   316  func fffftou(f float64) uint16 {
   317  	i := int32(f + 0.5)
   318  	if i > 0xffff {
   319  		return 0xffff
   320  	}
   321  	if i > 0 {
   322  		return uint16(i)
   323  	}
   324  	return 0
   325  }
   326  
   327  // invert returns the inverse of m.
   328  //
   329  // TODO: move this into the f64 package, once we work out the convention for
   330  // matrix methods in that package: do they modify the receiver, take a dst
   331  // pointer argument, or return a new value?
   332  func invert(m *f64.Aff3) f64.Aff3 {
   333  	m00 := +m[3*1+1]
   334  	m01 := -m[3*0+1]
   335  	m02 := +m[3*1+2]*m[3*0+1] - m[3*1+1]*m[3*0+2]
   336  	m10 := -m[3*1+0]
   337  	m11 := +m[3*0+0]
   338  	m12 := +m[3*1+0]*m[3*0+2] - m[3*1+2]*m[3*0+0]
   339  
   340  	det := m00*m11 - m10*m01
   341  
   342  	return f64.Aff3{
   343  		m00 / det,
   344  		m01 / det,
   345  		m02 / det,
   346  		m10 / det,
   347  		m11 / det,
   348  		m12 / det,
   349  	}
   350  }
   351  
   352  func matMul(p, q *f64.Aff3) f64.Aff3 {
   353  	return f64.Aff3{
   354  		p[3*0+0]*q[3*0+0] + p[3*0+1]*q[3*1+0],
   355  		p[3*0+0]*q[3*0+1] + p[3*0+1]*q[3*1+1],
   356  		p[3*0+0]*q[3*0+2] + p[3*0+1]*q[3*1+2] + p[3*0+2],
   357  		p[3*1+0]*q[3*0+0] + p[3*1+1]*q[3*1+0],
   358  		p[3*1+0]*q[3*0+1] + p[3*1+1]*q[3*1+1],
   359  		p[3*1+0]*q[3*0+2] + p[3*1+1]*q[3*1+2] + p[3*1+2],
   360  	}
   361  }
   362  
   363  // transformRect returns a rectangle dr that contains sr transformed by s2d.
   364  func transformRect(s2d *f64.Aff3, sr *image.Rectangle) (dr image.Rectangle) {
   365  	ps := [...]image.Point{
   366  		{sr.Min.X, sr.Min.Y},
   367  		{sr.Max.X, sr.Min.Y},
   368  		{sr.Min.X, sr.Max.Y},
   369  		{sr.Max.X, sr.Max.Y},
   370  	}
   371  	for i, p := range ps {
   372  		sxf := float64(p.X)
   373  		syf := float64(p.Y)
   374  		dx := int(math.Floor(s2d[0]*sxf + s2d[1]*syf + s2d[2]))
   375  		dy := int(math.Floor(s2d[3]*sxf + s2d[4]*syf + s2d[5]))
   376  
   377  		// The +1 adjustments below are because an image.Rectangle is inclusive
   378  		// on the low end but exclusive on the high end.
   379  
   380  		if i == 0 {
   381  			dr = image.Rectangle{
   382  				Min: image.Point{dx + 0, dy + 0},
   383  				Max: image.Point{dx + 1, dy + 1},
   384  			}
   385  			continue
   386  		}
   387  
   388  		if dr.Min.X > dx {
   389  			dr.Min.X = dx
   390  		}
   391  		dx++
   392  		if dr.Max.X < dx {
   393  			dr.Max.X = dx
   394  		}
   395  
   396  		if dr.Min.Y > dy {
   397  			dr.Min.Y = dy
   398  		}
   399  		dy++
   400  		if dr.Max.Y < dy {
   401  			dr.Max.Y = dy
   402  		}
   403  	}
   404  	return dr
   405  }
   406  
   407  func clipAffectedDestRect(adr image.Rectangle, dstMask image.Image, dstMaskP image.Point) (image.Rectangle, image.Image) {
   408  	if dstMask == nil {
   409  		return adr, nil
   410  	}
   411  	if r, ok := dstMask.(image.Rectangle); ok {
   412  		return adr.Intersect(r.Sub(dstMaskP)), nil
   413  	}
   414  	// TODO: clip to dstMask.Bounds() if the color model implies that out-of-bounds means 0 alpha?
   415  	return adr, dstMask
   416  }
   417  
   418  func transform_Uniform(dst Image, dr, adr image.Rectangle, d2s *f64.Aff3, src *image.Uniform, sr image.Rectangle, bias image.Point, op Op) {
   419  	switch op {
   420  	case Over:
   421  		switch dst := dst.(type) {
   422  		case *image.RGBA:
   423  			pr, pg, pb, pa := src.C.RGBA()
   424  			pa1 := (0xffff - pa) * 0x101
   425  
   426  			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
   427  				dyf := float64(dr.Min.Y+int(dy)) + 0.5
   428  				d := dst.PixOffset(dr.Min.X+adr.Min.X, dr.Min.Y+int(dy))
   429  				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx, d = dx+1, d+4 {
   430  					dxf := float64(dr.Min.X+int(dx)) + 0.5
   431  					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
   432  					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
   433  					if !(image.Point{sx0, sy0}).In(sr) {
   434  						continue
   435  					}
   436  					dst.Pix[d+0] = uint8((uint32(dst.Pix[d+0])*pa1/0xffff + pr) >> 8)
   437  					dst.Pix[d+1] = uint8((uint32(dst.Pix[d+1])*pa1/0xffff + pg) >> 8)
   438  					dst.Pix[d+2] = uint8((uint32(dst.Pix[d+2])*pa1/0xffff + pb) >> 8)
   439  					dst.Pix[d+3] = uint8((uint32(dst.Pix[d+3])*pa1/0xffff + pa) >> 8)
   440  				}
   441  			}
   442  
   443  		default:
   444  			pr, pg, pb, pa := src.C.RGBA()
   445  			pa1 := 0xffff - pa
   446  			dstColorRGBA64 := &color.RGBA64{}
   447  			dstColor := color.Color(dstColorRGBA64)
   448  
   449  			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
   450  				dyf := float64(dr.Min.Y+int(dy)) + 0.5
   451  				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx++ {
   452  					dxf := float64(dr.Min.X+int(dx)) + 0.5
   453  					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
   454  					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
   455  					if !(image.Point{sx0, sy0}).In(sr) {
   456  						continue
   457  					}
   458  					qr, qg, qb, qa := dst.At(dr.Min.X+int(dx), dr.Min.Y+int(dy)).RGBA()
   459  					dstColorRGBA64.R = uint16(qr*pa1/0xffff + pr)
   460  					dstColorRGBA64.G = uint16(qg*pa1/0xffff + pg)
   461  					dstColorRGBA64.B = uint16(qb*pa1/0xffff + pb)
   462  					dstColorRGBA64.A = uint16(qa*pa1/0xffff + pa)
   463  					dst.Set(dr.Min.X+int(dx), dr.Min.Y+int(dy), dstColor)
   464  				}
   465  			}
   466  		}
   467  
   468  	case Src:
   469  		switch dst := dst.(type) {
   470  		case *image.RGBA:
   471  			pr, pg, pb, pa := src.C.RGBA()
   472  			pr8 := uint8(pr >> 8)
   473  			pg8 := uint8(pg >> 8)
   474  			pb8 := uint8(pb >> 8)
   475  			pa8 := uint8(pa >> 8)
   476  
   477  			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
   478  				dyf := float64(dr.Min.Y+int(dy)) + 0.5
   479  				d := dst.PixOffset(dr.Min.X+adr.Min.X, dr.Min.Y+int(dy))
   480  				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx, d = dx+1, d+4 {
   481  					dxf := float64(dr.Min.X+int(dx)) + 0.5
   482  					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
   483  					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
   484  					if !(image.Point{sx0, sy0}).In(sr) {
   485  						continue
   486  					}
   487  					dst.Pix[d+0] = pr8
   488  					dst.Pix[d+1] = pg8
   489  					dst.Pix[d+2] = pb8
   490  					dst.Pix[d+3] = pa8
   491  				}
   492  			}
   493  
   494  		default:
   495  			pr, pg, pb, pa := src.C.RGBA()
   496  			dstColorRGBA64 := &color.RGBA64{
   497  				uint16(pr),
   498  				uint16(pg),
   499  				uint16(pb),
   500  				uint16(pa),
   501  			}
   502  			dstColor := color.Color(dstColorRGBA64)
   503  
   504  			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
   505  				dyf := float64(dr.Min.Y+int(dy)) + 0.5
   506  				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx++ {
   507  					dxf := float64(dr.Min.X+int(dx)) + 0.5
   508  					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
   509  					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
   510  					if !(image.Point{sx0, sy0}).In(sr) {
   511  						continue
   512  					}
   513  					dst.Set(dr.Min.X+int(dx), dr.Min.Y+int(dy), dstColor)
   514  				}
   515  			}
   516  		}
   517  	}
   518  }
   519  
   520  func opaque(m image.Image) bool {
   521  	o, ok := m.(interface {
   522  		Opaque() bool
   523  	})
   524  	return ok && o.Opaque()
   525  }
   526
View as plain text