scale.go

// Copyright 2015 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.

//go:generate go run gen.go

package draw

import (
	"image"
	"image/color"
	"math"
	"sync"

	"golang.org/x/image/math/f64"
)

// Copy copies the part of the source image defined by src and sr and writes
// the result of a Porter-Duff composition to the part of the destination image
// defined by dst and the translation of sr so that sr.Min translates to dp.
func Copy(dst Image, dp image.Point, src image.Image, sr image.Rectangle, op Op, opts *Options) {
	var o Options
	if opts != nil {
		o = *opts
	}
	dr := sr.Add(dp.Sub(sr.Min))
	if o.DstMask == nil {
		DrawMask(dst, dr, src, sr.Min, o.SrcMask, o.SrcMaskP.Add(sr.Min), op)
	} else {
		NearestNeighbor.Scale(dst, dr, src, sr, op, opts)
	}
}

// Scaler scales the part of the source image defined by src and sr and writes
// the result of a Porter-Duff composition to the part of the destination image
// defined by dst and dr.
//
// A Scaler is safe to use concurrently.
type Scaler interface {
	Scale(dst Image, dr image.Rectangle, src image.Image, sr image.Rectangle, op Op, opts *Options)
}

// Transformer transforms the part of the source image defined by src and sr
// and writes the result of a Porter-Duff composition to the part of the
// destination image defined by dst and the affine transform m applied to sr.
//
// For example, if m is the matrix
//
// m00 m01 m02
// m10 m11 m12
//
// then the src-space point (sx, sy) maps to the dst-space point
// (m00*sx + m01*sy + m02, m10*sx + m11*sy + m12).
//
// A Transformer is safe to use concurrently.
type Transformer interface {
	Transform(dst Image, m f64.Aff3, src image.Image, sr image.Rectangle, op Op, opts *Options)
}

// Options are optional parameters to Copy, Scale and Transform.
//
// A nil *Options means to use the default (zero) values of each field.
type Options struct {
	// Masks limit what parts of the dst image are drawn to and what parts of
	// the src image are drawn from.
	//
	// A dst or src mask image having a zero alpha (transparent) pixel value in
	// the respective coordinate space means that that dst pixel is entirely
	// unaffected or that src pixel is considered transparent black. A full
	// alpha (opaque) value means that the dst pixel is maximally affected or
	// the src pixel contributes maximally. The default values, nil, are
	// equivalent to fully opaque, infinitely large mask images.
	//
	// The DstMask is otherwise known as a clip mask, and its pixels map 1:1 to
	// the dst image's pixels. DstMaskP in DstMask space corresponds to
	// image.Point{X:0, Y:0} in dst space. For example, when limiting
	// repainting to a 'dirty rectangle', use that image.Rectangle and a zero
	// image.Point as the DstMask and DstMaskP.
	//
	// The SrcMask's pixels map 1:1 to the src image's pixels. SrcMaskP in
	// SrcMask space corresponds to image.Point{X:0, Y:0} in src space. For
	// example, when drawing font glyphs in a uniform color, use an
	// *image.Uniform as the src, and use the glyph atlas image and the
	// per-glyph offset as SrcMask and SrcMaskP:
	//	Copy(dst, dp, image.NewUniform(color), image.Rect(0, 0, glyphWidth, glyphHeight), &Options{
	//		SrcMask:  glyphAtlas,
	//		SrcMaskP: glyphOffset,
	//	})
	DstMask  image.Image
	DstMaskP image.Point
	SrcMask  image.Image
	SrcMaskP image.Point

	// TODO: a smooth vs sharp edges option, for arbitrary rotations?
}

// Interpolator is an interpolation algorithm, when dst and src pixels don't
// have a 1:1 correspondence.
//
// Of the interpolators provided by this package:
//	- NearestNeighbor is fast but usually looks worst.
//	- CatmullRom is slow but usually looks best.
//	- ApproxBiLinear has reasonable speed and quality.
//
// The time taken depends on the size of dr. For kernel interpolators, the
// speed also depends on the size of sr, and so are often slower than
// non-kernel interpolators, especially when scaling down.
type Interpolator interface {
	Scaler
	Transformer
}

// Kernel is an interpolator that blends source pixels weighted by a symmetric
// kernel function.
type Kernel struct {
	// Support is the kernel support and must be >= 0. At(t) is assumed to be
	// zero when t >= Support.
	Support float64
	// At is the kernel function. It will only be called with t in the
	// range [0, Support).
	At func(t float64) float64
}

// Scale implements the Scaler interface.
func (q *Kernel) Scale(dst Image, dr image.Rectangle, src image.Image, sr image.Rectangle, op Op, opts *Options) {
	q.newScaler(dr.Dx(), dr.Dy(), sr.Dx(), sr.Dy(), false).Scale(dst, dr, src, sr, op, opts)
}

// NewScaler returns a Scaler that is optimized for scaling multiple times with
// the same fixed destination and source width and height.
func (q *Kernel) NewScaler(dw, dh, sw, sh int) Scaler {
	return q.newScaler(dw, dh, sw, sh, true)
}

func (q *Kernel) newScaler(dw, dh, sw, sh int, usePool bool) Scaler {
	z := &kernelScaler{
		kernel:     q,
		dw:         int32(dw),
		dh:         int32(dh),
		sw:         int32(sw),
		sh:         int32(sh),
		horizontal: newDistrib(q, int32(dw), int32(sw)),
		vertical:   newDistrib(q, int32(dh), int32(sh)),
	}
	if usePool {
		z.pool.New = func() interface{} {
			tmp := z.makeTmpBuf()
			return &tmp
		}
	}
	return z
}

var (
	// NearestNeighbor is the nearest neighbor interpolator. It is very fast,
	// but usually gives very low quality results. When scaling up, the result
	// will look 'blocky'.
	NearestNeighbor = Interpolator(nnInterpolator{})

	// ApproxBiLinear is a mixture of the nearest neighbor and bi-linear
	// interpolators. It is fast, but usually gives medium quality results.
	//
	// It implements bi-linear interpolation when upscaling and a bi-linear
	// blend of the 4 nearest neighbor pixels when downscaling. This yields
	// nicer quality than nearest neighbor interpolation when upscaling, but
	// the time taken is independent of the number of source pixels, unlike the
	// bi-linear interpolator. When downscaling a large image, the performance
	// difference can be significant.
	ApproxBiLinear = Interpolator(ablInterpolator{})

	// BiLinear is the tent kernel. It is slow, but usually gives high quality
	// results.
	BiLinear = &Kernel{1, func(t float64) float64 {
		return 1 - t
	}}

	// CatmullRom is the Catmull-Rom kernel. It is very slow, but usually gives
	// very high quality results.
	//
	// It is an instance of the more general cubic BC-spline kernel with parameters
	// B=0 and C=0.5. See Mitchell and Netravali, "Reconstruction Filters in
	// Computer Graphics", Computer Graphics, Vol. 22, No. 4, pp. 221-228.
	CatmullRom = &Kernel{2, func(t float64) float64 {
		if t < 1 {
			return (1.5*t-2.5)*t*t + 1
		}
		return ((-0.5*t+2.5)*t-4)*t + 2
	}}

	// TODO: a Kaiser-Bessel kernel?
)

type nnInterpolator struct{}

type ablInterpolator struct{}

type kernelScaler struct {
	kernel               *Kernel
	dw, dh, sw, sh       int32
	horizontal, vertical distrib
	pool                 sync.Pool
}

func (z *kernelScaler) makeTmpBuf() [][4]float64 {
	return make([][4]float64, z.dw*z.sh)
}

// source is a range of contribs, their inverse total weight, and that ITW
// divided by 0xffff.
type source struct {
	i, j               int32
	invTotalWeight     float64
	invTotalWeightFFFF float64
}

// contrib is the weight of a column or row.
type contrib struct {
	coord  int32
	weight float64
}

// distrib measures how source pixels are distributed over destination pixels.
type distrib struct {
	// sources are what contribs each column or row in the source image owns,
	// and the total weight of those contribs.
	sources []source
	// contribs are the contributions indexed by sources[s].i and sources[s].j.
	contribs []contrib
}

// newDistrib returns a distrib that distributes sw source columns (or rows)
// over dw destination columns (or rows).
func newDistrib(q *Kernel, dw, sw int32) distrib {
	scale := float64(sw) / float64(dw)
	halfWidth, kernelArgScale := q.Support, 1.0
	// When shrinking, broaden the effective kernel support so that we still
	// visit every source pixel.
	if scale > 1 {
		halfWidth *= scale
		kernelArgScale = 1 / scale
	}

	// Make the sources slice, one source for each column or row, and temporarily
	// appropriate its elements' fields so that invTotalWeight is the scaled
	// coordinate of the source column or row, and i and j are the lower and
	// upper bounds of the range of destination columns or rows affected by the
	// source column or row.
	n, sources := int32(0), make([]source, dw)
	for x := range sources {
		center := (float64(x)+0.5)*scale - 0.5
		i := int32(math.Floor(center - halfWidth))
		if i < 0 {
			i = 0
		}
		j := int32(math.Ceil(center + halfWidth))
		if j > sw {
			j = sw
			if j < i {
				j = i
			}
		}
		sources[x] = source{i: i, j: j, invTotalWeight: center}
		n += j - i
	}

	contribs := make([]contrib, 0, n)
	for k, b := range sources {
		totalWeight := 0.0
		l := int32(len(contribs))
		for coord := b.i; coord < b.j; coord++ {
			t := abs((b.invTotalWeight - float64(coord)) * kernelArgScale)
			if t >= q.Support {
				continue
			}
			weight := q.At(t)
			if weight == 0 {
				continue
			}
			totalWeight += weight
			contribs = append(contribs, contrib{coord, weight})
		}
		totalWeight = 1 / totalWeight
		sources[k] = source{
			i:                  l,
			j:                  int32(len(contribs)),
			invTotalWeight:     totalWeight,
			invTotalWeightFFFF: totalWeight / 0xffff,
		}
	}

	return distrib{sources, contribs}
}

// abs is like math.Abs, but it doesn't care about negative zero, infinities or
// NaNs.
func abs(f float64) float64 {
	if f < 0 {
		f = -f
	}
	return f
}

// ftou converts the range [0.0, 1.0] to [0, 0xffff].
func ftou(f float64) uint16 {
	i := int32(0xffff*f + 0.5)
	if i > 0xffff {
		return 0xffff
	}
	if i > 0 {
		return uint16(i)
	}
	return 0
}

// fffftou converts the range [0.0, 65535.0] to [0, 0xffff].
func fffftou(f float64) uint16 {
	i := int32(f + 0.5)
	if i > 0xffff {
		return 0xffff
	}
	if i > 0 {
		return uint16(i)
	}
	return 0
}

// invert returns the inverse of m.
//
// TODO: move this into the f64 package, once we work out the convention for
// matrix methods in that package: do they modify the receiver, take a dst
// pointer argument, or return a new value?
func invert(m *f64.Aff3) f64.Aff3 {
	m00 := +m[3*1+1]
	m01 := -m[3*0+1]
	m02 := +m[3*1+2]*m[3*0+1] - m[3*1+1]*m[3*0+2]
	m10 := -m[3*1+0]
	m11 := +m[3*0+0]
	m12 := +m[3*1+0]*m[3*0+2] - m[3*1+2]*m[3*0+0]

	det := m00*m11 - m10*m01

	return f64.Aff3{
		m00 / det,
		m01 / det,
		m02 / det,
		m10 / det,
		m11 / det,
		m12 / det,
	}
}

func matMul(p, q *f64.Aff3) f64.Aff3 {
	return f64.Aff3{
		p[3*0+0]*q[3*0+0] + p[3*0+1]*q[3*1+0],
		p[3*0+0]*q[3*0+1] + p[3*0+1]*q[3*1+1],
		p[3*0+0]*q[3*0+2] + p[3*0+1]*q[3*1+2] + p[3*0+2],
		p[3*1+0]*q[3*0+0] + p[3*1+1]*q[3*1+0],
		p[3*1+0]*q[3*0+1] + p[3*1+1]*q[3*1+1],
		p[3*1+0]*q[3*0+2] + p[3*1+1]*q[3*1+2] + p[3*1+2],
	}
}

// transformRect returns a rectangle dr that contains sr transformed by s2d.
func transformRect(s2d *f64.Aff3, sr *image.Rectangle) (dr image.Rectangle) {
	ps := [...]image.Point{
		{sr.Min.X, sr.Min.Y},
		{sr.Max.X, sr.Min.Y},
		{sr.Min.X, sr.Max.Y},
		{sr.Max.X, sr.Max.Y},
	}
	for i, p := range ps {
		sxf := float64(p.X)
		syf := float64(p.Y)
		dx := int(math.Floor(s2d[0]*sxf + s2d[1]*syf + s2d[2]))
		dy := int(math.Floor(s2d[3]*sxf + s2d[4]*syf + s2d[5]))

		// The +1 adjustments below are because an image.Rectangle is inclusive
		// on the low end but exclusive on the high end.

		if i == 0 {
			dr = image.Rectangle{
				Min: image.Point{dx + 0, dy + 0},
				Max: image.Point{dx + 1, dy + 1},
			}
			continue
		}

		if dr.Min.X > dx {
			dr.Min.X = dx
		}
		dx++
		if dr.Max.X < dx {
			dr.Max.X = dx
		}

		if dr.Min.Y > dy {
			dr.Min.Y = dy
		}
		dy++
		if dr.Max.Y < dy {
			dr.Max.Y = dy
		}
	}
	return dr
}

func clipAffectedDestRect(adr image.Rectangle, dstMask image.Image, dstMaskP image.Point) (image.Rectangle, image.Image) {
	if dstMask == nil {
		return adr, nil
	}
	// TODO: enable this fast path once Go 1.5 is released, where an
	// image.Rectangle implements image.Image.
	// if r, ok := dstMask.(image.Rectangle); ok {
	// 	return adr.Intersect(r.Sub(dstMaskP)), nil
	// }
	// TODO: clip to dstMask.Bounds() if the color model implies that out-of-bounds means 0 alpha?
	return adr, dstMask
}

func transform_Uniform(dst Image, dr, adr image.Rectangle, d2s *f64.Aff3, src *image.Uniform, sr image.Rectangle, bias image.Point, op Op) {
	switch op {
	case Over:
		switch dst := dst.(type) {
		case *image.RGBA:
			pr, pg, pb, pa := src.C.RGBA()
			pa1 := (0xffff - pa) * 0x101

			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
				dyf := float64(dr.Min.Y+int(dy)) + 0.5
				d := dst.PixOffset(dr.Min.X+adr.Min.X, dr.Min.Y+int(dy))
				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx, d = dx+1, d+4 {
					dxf := float64(dr.Min.X+int(dx)) + 0.5
					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
					if !(image.Point{sx0, sy0}).In(sr) {
						continue
					}
					dst.Pix[d+0] = uint8((uint32(dst.Pix[d+0])*pa1/0xffff + pr) >> 8)
					dst.Pix[d+1] = uint8((uint32(dst.Pix[d+1])*pa1/0xffff + pg) >> 8)
					dst.Pix[d+2] = uint8((uint32(dst.Pix[d+2])*pa1/0xffff + pb) >> 8)
					dst.Pix[d+3] = uint8((uint32(dst.Pix[d+3])*pa1/0xffff + pa) >> 8)
				}
			}

		default:
			pr, pg, pb, pa := src.C.RGBA()
			pa1 := 0xffff - pa
			dstColorRGBA64 := &color.RGBA64{}
			dstColor := color.Color(dstColorRGBA64)

			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
				dyf := float64(dr.Min.Y+int(dy)) + 0.5
				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx++ {
					dxf := float64(dr.Min.X+int(dx)) + 0.5
					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
					if !(image.Point{sx0, sy0}).In(sr) {
						continue
					}
					qr, qg, qb, qa := dst.At(dr.Min.X+int(dx), dr.Min.Y+int(dy)).RGBA()
					dstColorRGBA64.R = uint16(qr*pa1/0xffff + pr)
					dstColorRGBA64.G = uint16(qg*pa1/0xffff + pg)
					dstColorRGBA64.B = uint16(qb*pa1/0xffff + pb)
					dstColorRGBA64.A = uint16(qa*pa1/0xffff + pa)
					dst.Set(dr.Min.X+int(dx), dr.Min.Y+int(dy), dstColor)
				}
			}
		}

	case Src:
		switch dst := dst.(type) {
		case *image.RGBA:
			pr, pg, pb, pa := src.C.RGBA()
			pr8 := uint8(pr >> 8)
			pg8 := uint8(pg >> 8)
			pb8 := uint8(pb >> 8)
			pa8 := uint8(pa >> 8)

			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
				dyf := float64(dr.Min.Y+int(dy)) + 0.5
				d := dst.PixOffset(dr.Min.X+adr.Min.X, dr.Min.Y+int(dy))
				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx, d = dx+1, d+4 {
					dxf := float64(dr.Min.X+int(dx)) + 0.5
					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
					if !(image.Point{sx0, sy0}).In(sr) {
						continue
					}
					dst.Pix[d+0] = pr8
					dst.Pix[d+1] = pg8
					dst.Pix[d+2] = pb8
					dst.Pix[d+3] = pa8
				}
			}

		default:
			pr, pg, pb, pa := src.C.RGBA()
			dstColorRGBA64 := &color.RGBA64{
				uint16(pr),
				uint16(pg),
				uint16(pb),
				uint16(pa),
			}
			dstColor := color.Color(dstColorRGBA64)

			for dy := int32(adr.Min.Y); dy < int32(adr.Max.Y); dy++ {
				dyf := float64(dr.Min.Y+int(dy)) + 0.5
				for dx := int32(adr.Min.X); dx < int32(adr.Max.X); dx++ {
					dxf := float64(dr.Min.X+int(dx)) + 0.5
					sx0 := int(d2s[0]*dxf+d2s[1]*dyf+d2s[2]) + bias.X
					sy0 := int(d2s[3]*dxf+d2s[4]*dyf+d2s[5]) + bias.Y
					if !(image.Point{sx0, sy0}).In(sr) {
						continue
					}
					dst.Set(dr.Min.X+int(dx), dr.Min.Y+int(dy), dstColor)
				}
			}
		}
	}
}

func opaque(m image.Image) bool {
	o, ok := m.(interface {
		Opaque() bool
	})
	return ok && o.Opaque()
}