From 58019288176e751299eabcaf4677f3b3425a4b36 Mon Sep 17 00:00:00 2001 From: Nigel Tao Date: Fri, 10 Sep 2010 20:09:56 +1000 Subject: [PATCH] exp/draw: fast path for drawing overlapping image.RGBAs. R=r, nigeltao CC=golang-dev https://golang.org/cl/2145045 --- src/pkg/exp/draw/draw.go | 90 ++++++++++++++++++++++++----------- src/pkg/exp/draw/draw_test.go | 77 ++++++++++++++++++++++++++---- 2 files changed, 130 insertions(+), 37 deletions(-) diff --git a/src/pkg/exp/draw/draw.go b/src/pkg/exp/draw/draw.go index d76f7aa550..eabd88ed1b 100644 --- a/src/pkg/exp/draw/draw.go +++ b/src/pkg/exp/draw/draw.go @@ -74,12 +74,8 @@ func DrawMask(dst Image, r image.Rectangle, src image.Image, sp image.Point, mas return } if src0, ok := src.(*image.RGBA); ok { - if dst0 == src0 && r.Overlaps(r.Add(sp.Sub(r.Min))) { - // TODO(nigeltao): Implement a fast path for the overlapping case. - } else { - drawCopyOver(dst0, r, src0, sp) - return - } + drawCopyOver(dst0, r, src0, sp) + return } } else if mask0, ok := mask.(*image.Alpha); ok { if src0, ok := src.(image.ColorImage); ok { @@ -94,12 +90,8 @@ func DrawMask(dst Image, r image.Rectangle, src image.Image, sp image.Point, mas return } if src0, ok := src.(*image.RGBA); ok { - if dst0 == src0 && r.Overlaps(r.Add(sp.Sub(r.Min))) { - // TODO(nigeltao): Implement a fast path for the overlapping case. - } else { - drawCopySrc(dst0, r, src0, sp) - return - } + drawCopySrc(dst0, r, src0, sp) + return } } } @@ -181,18 +173,42 @@ func drawFillOver(dst *image.RGBA, r image.Rectangle, src image.ColorImage) { } func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { - x0, x1 := r.Min.X, r.Max.X - y0, y1 := r.Min.Y, r.Max.Y - for y, sy := y0, sp.Y; y != y1; y, sy = y+1, sy+1 { - dbase := y * dst.Stride - dpix := dst.Pix[dbase+x0 : dbase+x1] - sbase := sy * src.Stride - spix := src.Pix[sbase+sp.X:] - for i, rgba := range dpix { + dx0, dx1 := r.Min.X, r.Max.X + dy0, dy1 := r.Min.Y, r.Max.Y + nrows := dy1 - dy0 + sx0, sx1 := sp.X, sp.X+dx1-dx0 + d0 := dy0*dst.Stride + dx0 + d1 := dy0*dst.Stride + dx1 + s0 := sp.Y*src.Stride + sx0 + s1 := sp.Y*src.Stride + sx1 + var ( + ddelta, sdelta int + i0, i1, idelta int + ) + if r.Min.Y < sp.Y || r.Min.Y == sp.Y && r.Min.X <= sp.X { + ddelta = dst.Stride + sdelta = src.Stride + i0, i1, idelta = 0, d1-d0, +1 + } else { + // If the source start point is higher than the destination start point, or equal height but to the left, + // then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down. + d0 += (nrows - 1) * dst.Stride + d1 += (nrows - 1) * dst.Stride + s0 += (nrows - 1) * src.Stride + s1 += (nrows - 1) * src.Stride + ddelta = -dst.Stride + sdelta = -src.Stride + i0, i1, idelta = d1-d0-1, -1, -1 + } + for ; nrows > 0; nrows-- { + dpix := dst.Pix[d0:d1] + spix := src.Pix[s0:s1] + for i := i0; i != i1; i += idelta { // For unknown reasons, even though both dpix[i] and spix[i] are // image.RGBAColors, on an x86 CPU it seems fastest to call RGBA // for the source but to do it manually for the destination. sr, sg, sb, sa := spix[i].RGBA() + rgba := dpix[i] dr := uint32(rgba.R) dg := uint32(rgba.G) db := uint32(rgba.B) @@ -205,6 +221,10 @@ func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image. da = (da*a)/m + sa dpix[i] = image.RGBAColor{uint8(dr >> 8), uint8(dg >> 8), uint8(db >> 8), uint8(da >> 8)} } + d0 += ddelta + d1 += ddelta + s0 += sdelta + s1 += sdelta } } @@ -265,17 +285,33 @@ func drawFillSrc(dst *image.RGBA, r image.Rectangle, src image.ColorImage) { func drawCopySrc(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { dx0, dx1 := r.Min.X, r.Max.X dy0, dy1 := r.Min.Y, r.Max.Y + nrows := dy1 - dy0 sx0, sx1 := sp.X, sp.X+dx1-dx0 d0 := dy0*dst.Stride + dx0 d1 := dy0*dst.Stride + dx1 - s0 := sp.Y*dst.Stride + sx0 - s1 := sp.Y*dst.Stride + sx1 - for y := dy0; y < dy1; y++ { + s0 := sp.Y*src.Stride + sx0 + s1 := sp.Y*src.Stride + sx1 + var ddelta, sdelta int + if r.Min.Y <= sp.Y { + ddelta = dst.Stride + sdelta = src.Stride + } else { + // If the source start point is higher than the destination start point, then we compose the rows + // in bottom-up order instead of top-down. Unlike the drawCopyOver function, we don't have to + // check the x co-ordinates because the built-in copy function can handle overlapping slices. + d0 += (nrows - 1) * dst.Stride + d1 += (nrows - 1) * dst.Stride + s0 += (nrows - 1) * src.Stride + s1 += (nrows - 1) * src.Stride + ddelta = -dst.Stride + sdelta = -src.Stride + } + for ; nrows > 0; nrows-- { copy(dst.Pix[d0:d1], src.Pix[s0:s1]) - d0 += dst.Stride - d1 += dst.Stride - s0 += src.Stride - s1 += src.Stride + d0 += ddelta + d1 += ddelta + s0 += sdelta + s1 += sdelta } } diff --git a/src/pkg/exp/draw/draw_test.go b/src/pkg/exp/draw/draw_test.go index 03a4b018ef..30b856b709 100644 --- a/src/pkg/exp/draw/draw_test.go +++ b/src/pkg/exp/draw/draw_test.go @@ -53,6 +53,16 @@ func hgradRed(alpha int) Image { return m } +func gradYellow(alpha int) Image { + m := image.NewRGBA(16, 16) + for y := 0; y < 16; y++ { + for x := 0; x < 16; x++ { + m.Set(x, y, image.RGBAColor{uint8(x * alpha / 15), uint8(y * alpha / 15), 0, uint8(alpha)}) + } + } + return m +} + type drawTest struct { desc string src image.Image @@ -94,24 +104,31 @@ var drawTests = []drawTest{ drawTest{"genericSrc", fillBlue(255), vgradAlpha(192), Src, image.RGBAColor{0, 0, 102, 102}}, } -func makeGolden(dst image.Image, t drawTest) image.Image { +func makeGolden(dst, src, mask image.Image, op Op) image.Image { // Since golden is a newly allocated image, we don't have to check if the // input source and mask images and the output golden image overlap. b := dst.Bounds() - golden := image.NewRGBA(b.Dx(), b.Dy()) + sx0 := src.Bounds().Min.X - b.Min.X + sy0 := src.Bounds().Min.Y - b.Min.Y + var mx0, my0 int + if mask != nil { + mx0 = mask.Bounds().Min.X - b.Min.X + my0 = mask.Bounds().Min.Y - b.Min.Y + } + golden := image.NewRGBA(b.Max.X, b.Max.Y) for y := b.Min.Y; y < b.Max.Y; y++ { - my, sy := y, y + my, sy := my0+y, sy0+y for x := b.Min.X; x < b.Max.X; x++ { - mx, sx := x, x + mx, sx := mx0+x, sx0+x const M = 1<<16 - 1 var dr, dg, db, da uint32 - if t.op == Over { + if op == Over { dr, dg, db, da = dst.At(x, y).RGBA() } - sr, sg, sb, sa := t.src.At(sx, sy).RGBA() + sr, sg, sb, sa := src.At(sx, sy).RGBA() ma := uint32(M) - if t.mask != nil { - _, _, _, ma = t.mask.At(mx, my).RGBA() + if mask != nil { + _, _, _, ma = mask.At(mx, my).RGBA() } a := M - (sa * ma / M) golden.Set(x, y, image.RGBA64Color{ @@ -122,6 +139,7 @@ func makeGolden(dst image.Image, t drawTest) image.Image { }) } } + golden.Rect = b return golden } @@ -130,14 +148,14 @@ loop: for _, test := range drawTests { dst := hgradRed(255) // Draw the (src, mask, op) onto a copy of dst using a slow but obviously correct implementation. + golden := makeGolden(dst, test.src, test.mask, test.op) b := dst.Bounds() - golden := makeGolden(dst, test) if !b.Eq(golden.Bounds()) { t.Errorf("draw %s: bounds %v versus %v", test.desc, dst.Bounds(), golden.Bounds()) continue } // Draw the same combination onto the actual dst using the optimized DrawMask implementation. - DrawMask(dst, image.Rect(b.Min.X, b.Min.Y, b.Max.X, b.Max.Y), test.src, image.ZP, test.mask, image.ZP, test.op) + DrawMask(dst, b, test.src, image.ZP, test.mask, image.ZP, test.op) // Check that the resultant pixel at (8, 8) matches what we expect // (the expected value can be verified by hand). if !eq(dst.At(8, 8), test.expected) { @@ -156,6 +174,45 @@ loop: } } +func TestDrawOverlap(t *testing.T) { + for _, op := range []Op{Over, Src} { + for yoff := -2; yoff <= 2; yoff++ { + loop: + for xoff := -2; xoff <= 2; xoff++ { + m := gradYellow(127).(*image.RGBA) + dst := &image.RGBA{ + Pix: m.Pix, + Stride: m.Stride, + Rect: image.Rect(5, 5, 10, 10), + } + src := &image.RGBA{ + Pix: m.Pix, + Stride: m.Stride, + Rect: image.Rect(5+xoff, 5+yoff, 10+xoff, 10+yoff), + } + // Draw the (src, mask, op) onto a copy of dst using a slow but obviously correct implementation. + golden := makeGolden(dst, src, nil, op) + b := dst.Bounds() + if !b.Eq(golden.Bounds()) { + t.Errorf("drawOverlap xoff=%d,yoff=%d: bounds %v versus %v", xoff, yoff, dst.Bounds(), golden.Bounds()) + continue + } + // Draw the same combination onto the actual dst using the optimized DrawMask implementation. + DrawMask(dst, b, src, src.Bounds().Min, nil, image.ZP, op) + // Check that the resultant dst image matches the golden output. + for y := b.Min.Y; y < b.Max.Y; y++ { + for x := b.Min.X; x < b.Max.X; x++ { + if !eq(dst.At(x, y), golden.At(x, y)) { + t.Errorf("drawOverlap xoff=%d,yoff=%d: at (%d, %d), %v versus golden %v", xoff, yoff, x, y, dst.At(x, y), golden.At(x, y)) + continue loop + } + } + } + } + } + } +} + // TestIssue836 verifies http://code.google.com/p/go/issues/detail?id=836. func TestIssue836(t *testing.T) { a := image.NewRGBA(1, 1) -- 2.50.0