font/opentype: implement Glyph and GlyphBounds

This CL is based on Joe Blubaugh's work (golang.org/cl/240897).
Thank you.

Fixes golang/go#22451

Change-Id: I02e194b9e0a227128ff111cf9f40d6a569dfbd2c
Reviewed-on: https://go-review.googlesource.com/c/image/+/255237
Run-TryBot: Hajime Hoshi <hajimehoshi@gmail.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Nigel Tao <nigeltao@golang.org>
Trust: David Symonds <dsymonds@golang.org>
diff --git a/font/opentype/face.go b/font/opentype/face.go
index 88c28da..1478582 100644
--- a/font/opentype/face.go
+++ b/font/opentype/face.go
@@ -6,10 +6,12 @@
 
 import (
 	"image"
+	"image/draw"
 
 	"golang.org/x/image/font"
 	"golang.org/x/image/font/sfnt"
 	"golang.org/x/image/math/fixed"
+	"golang.org/x/image/vector"
 )
 
 // FaceOptions describes the possible options given to NewFace when
@@ -34,7 +36,12 @@
 	hinting font.Hinting
 	scale   fixed.Int26_6
 
-	buf sfnt.Buffer
+	metrics    font.Metrics
+	metricsSet bool
+
+	buf  sfnt.Buffer
+	rast vector.Rasterizer
+	mask image.Alpha
 }
 
 // NewFace returns a new font.Face for the given sfnt.Font.
@@ -58,11 +65,15 @@
 
 // Metrics satisfies the font.Face interface.
 func (f *Face) Metrics() font.Metrics {
-	m, err := f.f.Metrics(&f.buf, f.scale, f.hinting)
-	if err != nil {
-		return font.Metrics{}
+	if !f.metricsSet {
+		var err error
+		f.metrics, err = f.f.Metrics(&f.buf, f.scale, f.hinting)
+		if err != nil {
+			f.metrics = font.Metrics{}
+		}
+		f.metricsSet = true
 	}
-	return m
+	return f.metrics
 }
 
 // Kern satisfies the font.Face interface.
@@ -78,22 +89,120 @@
 
 // Glyph satisfies the font.Face interface.
 func (f *Face) Glyph(dot fixed.Point26_6, r rune) (dr image.Rectangle, mask image.Image, maskp image.Point, advance fixed.Int26_6, ok bool) {
-	panic("not implemented")
+	x, err := f.f.GlyphIndex(&f.buf, r)
+	if err != nil {
+		return image.Rectangle{}, nil, image.Point{}, 0, false
+	}
+
+	segments, err := f.f.LoadGlyph(&f.buf, x, f.scale, nil)
+	if err != nil {
+		return image.Rectangle{}, nil, image.Point{}, 0, false
+	}
+
+	bounds, advance, err := f.f.GlyphBounds(&f.buf, x, f.scale, f.hinting)
+	if err != nil {
+		return image.Rectangle{}, nil, image.Point{}, 0, false
+	}
+
+	// Numerical notation used below:
+	//  - 2    is an integer, "two"
+	//  - 2:16 is a 26.6 fixed point number, "two and a quarter"
+	//  - 2.5  is a float32 number, "two and a half"
+	// Using 26.6 fixed point numbers means that there are 64 sub-pixel units
+	// in 1 integer pixel unit.
+	// Translate the sub-pixel bounding box from glyph space (where the glyph
+	// origin is at (0:00, 0:00)) to dst space (where the glyph origin is at
+	// the dot). dst space is the coordinate space that contains both the dot
+	// (a sub-pixel position) and dr (a pixel rectangle).
+	dBounds := bounds.Add(dot)
+
+	// Quantize the sub-pixel bounds (dBounds) to integer-pixel bounds (dr).
+	dr.Min.X = dBounds.Min.X.Floor()
+	dr.Min.Y = dBounds.Min.Y.Floor()
+	dr.Max.X = dBounds.Max.X.Ceil()
+	dr.Max.Y = dBounds.Max.Y.Ceil()
+	width := dr.Dx()
+	height := dr.Dy()
+	if width < 0 || height < 0 {
+		return image.Rectangle{}, nil, image.Point{}, 0, false
+	}
+
+	// Calculate the sub-pixel bias to convert from glyph space to rasterizer
+	// space. In glyph space, the segments may be to the left or right and
+	// above or below the glyph origin. In rasterizer space, the segments
+	// should only be right and below (or equal to) the top-left corner (0.0,
+	// 0.0). They should also be left and above (or equal to) the bottom-right
+	// corner (width, height), as the rasterizer should enclose the glyph
+	// bounding box.
+	//
+	// For example, suppose that dot.X was at the sub-pixel position 25:48,
+	// three quarters of the way into the 26th pixel, and that bounds.Min.X was
+	// 1:20. We then have dBounds.Min.X = 1:20 + 25:48 = 27:04, dr.Min.X = 27
+	// and biasX = 25:48 - 27:00 = -1:16. A vertical stroke at 1:20 in glyph
+	// space becomes (1:20 + -1:16) = 0:04 in rasterizer space. 0:04 as a
+	// fixed.Int26_6 value is float32(4)/64.0 = 0.0625 as a float32 value.
+	biasX := dot.X - fixed.Int26_6(dr.Min.X<<6)
+	biasY := dot.Y - fixed.Int26_6(dr.Min.Y<<6)
+
+	// Configure the mask image, re-allocating its buffer if necessary.
+	nPixels := width * height
+	if cap(f.mask.Pix) < nPixels {
+		f.mask.Pix = make([]uint8, 2*nPixels)
+	}
+	f.mask.Pix = f.mask.Pix[:nPixels]
+	f.mask.Stride = width
+	f.mask.Rect.Min.X = 0
+	f.mask.Rect.Min.Y = 0
+	f.mask.Rect.Max.X = width
+	f.mask.Rect.Max.Y = height
+
+	// Rasterize the biased segments, converting from fixed.Int26_6 to float32.
+	f.rast.Reset(width, height)
+	f.rast.DrawOp = draw.Src
+	for _, seg := range segments {
+		switch seg.Op {
+		case sfnt.SegmentOpMoveTo:
+			f.rast.MoveTo(
+				float32(seg.Args[0].X+biasX)/64,
+				float32(seg.Args[0].Y+biasY)/64,
+			)
+		case sfnt.SegmentOpLineTo:
+			f.rast.LineTo(
+				float32(seg.Args[0].X+biasX)/64,
+				float32(seg.Args[0].Y+biasY)/64,
+			)
+		case sfnt.SegmentOpQuadTo:
+			f.rast.QuadTo(
+				float32(seg.Args[0].X+biasX)/64,
+				float32(seg.Args[0].Y+biasY)/64,
+				float32(seg.Args[1].X+biasX)/64,
+				float32(seg.Args[1].Y+biasY)/64,
+			)
+		case sfnt.SegmentOpCubeTo:
+			f.rast.CubeTo(
+				float32(seg.Args[0].X+biasX)/64,
+				float32(seg.Args[0].Y+biasY)/64,
+				float32(seg.Args[1].X+biasX)/64,
+				float32(seg.Args[1].Y+biasY)/64,
+				float32(seg.Args[2].X+biasX)/64,
+				float32(seg.Args[2].Y+biasY)/64,
+			)
+		}
+	}
+	f.rast.Draw(&f.mask, f.mask.Bounds(), image.Opaque, image.Point{})
+
+	return dr, &f.mask, f.mask.Rect.Min, advance, true
 }
 
 // GlyphBounds satisfies the font.Face interface.
 func (f *Face) GlyphBounds(r rune) (bounds fixed.Rectangle26_6, advance fixed.Int26_6, ok bool) {
-	advance, ok = f.GlyphAdvance(r)
-	if !ok {
-		return bounds, advance, ok
-	}
-	panic("not implemented")
+	bounds, advance, err := f.f.GlyphBounds(&f.buf, f.index(r), f.scale, f.hinting)
+	return bounds, advance, err == nil
 }
 
 // GlyphAdvance satisfies the font.Face interface.
 func (f *Face) GlyphAdvance(r rune) (advance fixed.Int26_6, ok bool) {
-	idx := f.index(r)
-	advance, err := f.f.GlyphAdvance(&f.buf, idx, f.scale, f.hinting)
+	advance, err := f.f.GlyphAdvance(&f.buf, f.index(r), f.scale, f.hinting)
 	return advance, err == nil
 }
 
diff --git a/font/opentype/face_test.go b/font/opentype/face_test.go
index c8b7054..6f720da 100644
--- a/font/opentype/face_test.go
+++ b/font/opentype/face_test.go
@@ -30,31 +30,99 @@
 	}
 }
 
+var runeTests = []struct {
+	r       rune
+	advance fixed.Int26_6
+	dr      image.Rectangle
+}{
+	{' ', 213, image.Rect(0, 0, 0, 0)},
+	{'A', 512, image.Rect(0, -9, 8, 0)},
+	{'Á', 512, image.Rect(0, -12, 8, 0)},
+	{'Æ', 768, image.Rect(0, -9, 12, 0)},
+	{'i', 189, image.Rect(0, -9, 3, 0)},
+	{'x', 384, image.Rect(0, -7, 6, 0)},
+}
+
 func TestFaceGlyphAdvance(t *testing.T) {
-	for _, test := range []struct {
-		r    rune
-		want fixed.Int26_6
-	}{
-		{' ', 213},
-		{'A', 512},
-		{'Á', 512},
-		{'Æ', 768},
-		{'i', 189},
-		{'x', 384},
-	} {
+	for _, test := range runeTests {
 		got, ok := regular.GlyphAdvance(test.r)
 		if !ok {
 			t.Errorf("could not get glyph advance width for %q", test.r)
 			continue
 		}
 
-		if got != test.want {
-			t.Errorf("%q: glyph advance width=%d. want=%d", test.r, got, test.want)
+		if got != test.advance {
+			t.Errorf("%q: glyph advance width=%d. want=%d", test.r, got, test.advance)
 			continue
 		}
 	}
 }
 
+func TestFaceGlyphBounds(t *testing.T) {
+	for _, test := range runeTests {
+		bounds, advance, ok := regular.GlyphBounds(test.r)
+		if !ok {
+			t.Errorf("could not get glyph bounds for %q", test.r)
+			continue
+		}
+
+		// bounds must fit inside the draw rect.
+		testFixedBounds := fixed.R(test.dr.Min.X, test.dr.Min.Y,
+			test.dr.Max.X, test.dr.Max.Y)
+		if !bounds.In(testFixedBounds) {
+			t.Errorf("%q: glyph bounds %v must be inside %v", test.r, bounds, testFixedBounds)
+			continue
+		}
+		if advance != test.advance {
+			t.Errorf("%q: glyph advance width=%d. want=%d", test.r, advance, test.advance)
+			continue
+		}
+	}
+}
+
+func TestFaceGlyph(t *testing.T) {
+	dot := image.Pt(200, 500)
+	fixedDot := fixed.P(dot.X, dot.Y)
+
+	for _, test := range runeTests {
+		dr, mask, maskp, advance, ok := regular.Glyph(fixedDot, test.r)
+		if !ok {
+			t.Errorf("could not get glyph for %q", test.r)
+			continue
+		}
+		if got, want := dr, test.dr.Add(dot); got != want {
+			t.Errorf("%q: glyph draw rectangle=%d. want=%d", test.r, got, want)
+			continue
+		}
+		if got, want := mask.Bounds(), image.Rect(0, 0, dr.Dx(), dr.Dy()); got != want {
+			t.Errorf("%q: glyph mask rectangle=%d. want=%d", test.r, got, want)
+			continue
+		}
+		if maskp != (image.Point{}) {
+			t.Errorf("%q: glyph maskp=%d. want=%d", test.r, maskp, image.Point{})
+			continue
+		}
+		if advance != test.advance {
+			t.Errorf("%q: glyph advance width=%d. want=%d", test.r, advance, test.advance)
+			continue
+		}
+	}
+}
+
+func BenchmarkFaceGlyph(b *testing.B) {
+	fixedDot := fixed.P(200, 500)
+	r := 'A'
+
+	b.ReportAllocs()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		_, _, _, _, ok := regular.Glyph(fixedDot, r)
+		if !ok {
+			b.Fatalf("could not get glyph for %q", r)
+		}
+	}
+}
+
 func TestFaceKern(t *testing.T) {
 	// FIXME(sbinet) there is no kerning with gofont/goregular
 	for _, test := range []struct {