scale.go

// Copyright 2014 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 draw

import (
	"image"
	"image/color"
	"math"
)

// Scale scales the part of the source image defined by src and sr and writes
// to the part of the destination image defined by dst and dr.
func Scale(dst Image, dr image.Rectangle, src image.Image, sr image.Rectangle, q Interpolator) {
	NewScaler(dr.Size(), sr.Size(), q).Scale(dst, dr.Min, src, sr.Min)
}

// Scaler scales part of a source image, starting from sp, and writes to a
// destination image, starting from dp. The destination and source width and
// heights are pre-determined, as part of the Scaler.
//
// A Scaler is safe to use concurrently.
type Scaler interface {
	Scale(dst Image, dp image.Point, src image.Image, sp image.Point)
}

// TODO: should Scale and NewScaler also take an Op argument?

// NewScaler returns a Scaler that scales a source image of the given size to a
// destination image of the given size.
func NewScaler(dstSize, srcSize image.Point, q Interpolator) Scaler {
	dw := int32(dstSize.X)
	dh := int32(dstSize.Y)
	sw := int32(srcSize.X)
	sh := int32(srcSize.Y)
	if dw <= 0 || dh <= 0 || sw <= 0 || sh <= 0 {
		return nopScaler{}
	}
	switch q.(type) {
	case nearest:
		return &nnScaler{
			dw: dw,
			dh: dh,
			sw: sw,
			sh: sh,
		}

	default:
		return &scaler{
			dw:         dw,
			dh:         dh,
			sw:         sw,
			sh:         sh,
			horizontal: newDistrib(dw, sw, q),
			vertical:   newDistrib(dh, sh, q),
		}
	}
}

type nopScaler struct{}

func (nopScaler) Scale(dst Image, dp image.Point, src image.Image, sp image.Point) {}

// nnScaler implements a nearest-neighbor image scaler.
type nnScaler struct {
	dw, dh, sw, sh int32
}

func (z *nnScaler) Scale(dst Image, dp image.Point, src image.Image, sp image.Point) {
	dstColorRGBA64 := &color.RGBA64{}
	dstColor := color.Color(dstColorRGBA64)
	for dy := int32(0); dy < z.dh; dy++ {
		sy := (2*uint64(dy) + 1) * uint64(z.sh) / (2 * uint64(z.dh))
		for dx := int32(0); dx < z.dw; dx++ {
			sx := (2*uint64(dx) + 1) * uint64(z.sw) / (2 * uint64(z.dw))
			pr, pg, pb, pa := src.At(sp.X+int(sx), sp.Y+int(sy)).RGBA()
			dstColorRGBA64.R = uint16(pr)
			dstColorRGBA64.G = uint16(pg)
			dstColorRGBA64.B = uint16(pb)
			dstColorRGBA64.A = uint16(pa)
			dst.Set(dp.X+int(dx), dp.Y+int(dy), dstColor)
		}
	}
}

// scaler implements a Catmull-Rom image scaler.
type scaler struct {
	dw, dh, sw, sh       int32
	horizontal, vertical distrib
}

func (z *scaler) Scale(dst Image, dp image.Point, src image.Image, sp image.Point) {
	// TODO: is it worth having a sync.Pool for this temporary buffer?
	tmp := make([][4]float64, z.dw*z.sh)
	z.scaleX(tmp, src, sp)
	z.scaleY(dst, dp, tmp)
}

// 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(dw, sw int32, f Interpolator) distrib {
	scale := float64(sw) / float64(dw)
	halfWidth, kernelArgScale := float64(f.Support()), 1.0
	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
	// co-ordinate 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 - 1
			if j < i {
				j = i
			}
		}
		sources[x] = source{i: i, j: j, invTotalWeight: center}
		n += j - i + 1
	}

	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++ {
			weight := f.F((b.invTotalWeight - float64(coord)) * kernelArgScale)
			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}
}

// scaleX distributes the source image's columns over the temporary image.
func (z *scaler) scaleX(tmp [][4]float64, src image.Image, sp image.Point) {
	t := 0
	for y := int32(0); y < z.sh; y++ {
		for _, s := range z.horizontal.sources {
			var r, g, b, a float64
			for _, c := range z.horizontal.contribs[s.i:s.j] {
				rr, gg, bb, aa := src.At(sp.X+int(c.coord), sp.Y+int(y)).RGBA()
				r += float64(rr) * c.weight
				g += float64(gg) * c.weight
				b += float64(bb) * c.weight
				a += float64(aa) * c.weight
			}
			tmp[t] = [4]float64{
				r * s.invTotalWeightFFFF,
				g * s.invTotalWeightFFFF,
				b * s.invTotalWeightFFFF,
				a * s.invTotalWeightFFFF,
			}
			t++
		}
	}
}

// scaleY distributes the temporary image's rows over the destination image.
func (z *scaler) scaleY(dst Image, dp image.Point, tmp [][4]float64) {
	dstColorRGBA64 := &color.RGBA64{}
	dstColor := color.Color(dstColorRGBA64)
	for x := int32(0); x < z.dw; x++ {
		for y, s := range z.vertical.sources {
			var r, g, b, a float64
			for _, c := range z.vertical.contribs[s.i:s.j] {
				p := &tmp[c.coord*z.dw+x]
				r += p[0] * c.weight
				g += p[1] * c.weight
				b += p[2] * c.weight
				a += p[3] * c.weight
			}
			dstColorRGBA64.R = ftou(r * s.invTotalWeight)
			dstColorRGBA64.G = ftou(g * s.invTotalWeight)
			dstColorRGBA64.B = ftou(b * s.invTotalWeight)
			dstColorRGBA64.A = ftou(a * s.invTotalWeight)
			dst.Set(dp.X+int(x), dp.Y+y, dstColor)
		}
	}
}

// The Interpolator defines the quality and speed of the resize operation.
//
// There are built-in types that have different speed/quality tradeoffs.
// In order from fastest to slowest are:
//
//	* NearestNeighbor
// 	* Linear
// 	* CatmullRom
// 	* Lanczos
type Interpolator interface {
	F(float64) float64
	Support() uint
}

// Fastest resample filter, no antialiasing at all.
// This should only be used if speed is essential.
func NearestNeighbor() Interpolator {
	return nearest{}
}

// Nearest is a special case, so only satisfy the interface.
type nearest struct{}

func (f nearest) F(t float64) float64 { return 0 }
func (f nearest) Support() uint       { return 0 }

// Bilinear interpolation filter, produces reasonably good, smooth output. It's faster than cubic filters.
func Linear() Interpolator {
	return linear{}
}

type linear struct{}

func (f linear) F(x float64) float64 {
	x = math.Abs(x)
	if x < 1.0 {
		return 1.0 - x
	}
	return 0

}
func (f linear) Support() uint {
	return 1
}

// CatmullRom is the Catmull-Rom kernel.
//
// 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.
func CatmullRom() Interpolator {
	return catmullRom{}
}

type catmullRom struct{}

func (f catmullRom) F(t float64) float64 {
	if t < 0 {
		t = -t
	}
	if t < 1 {
		return (1.5*t-2.5)*t*t + 1
	}
	if t < 2 {
		return ((-0.5*t+2.5)*t-4)*t + 2
	}
	return 0
}

func (f catmullRom) Support() uint {
	return 2
}

// Lanczos Interpolator
//
// Probably the best resampling filter for photographic images yielding sharp results,
// but it's slower than cubic filters.
func Lanczos() Interpolator {
	var lobes uint = 3
	return lanczos{Lobes: lobes, FloatLobes: float64(lobes), InvLobes: 1.0 / float64(lobes)}
}

// Lanczos Interpolator with custom number of lobes
//
// It is recommended to use between 3 and 7 lobes.
func LanczosLobes(lobes uint) Interpolator {
	return lanczos{Lobes: lobes, FloatLobes: float64(lobes), InvLobes: 1.0 / float64(lobes)}
}

type lanczos struct {
	Lobes      uint
	FloatLobes float64
	InvLobes   float64
}

func (f lanczos) F(x float64) float64 {
	x = math.Abs(x)
	if x < f.FloatLobes {
		return sinc(x) * sinc(x*f.InvLobes)
	}
	return 0

}

func (f lanczos) Support() uint {
	return f.Lobes
}

func sinc(x float64) float64 {
	if x == 0.0 {
		return 1.0
	}
	return math.Sin(math.Pi*x) / (math.Pi * x)
}

func ftou(f float64) uint16 {
	i := int32(0xffff*f + 0.5)
	if i > 0xffff {
		return 0xffff
	} else if i > 0 {
		return uint16(i)
	}
	return 0
}