diff options
Diffstat (limited to 'Godeps/_workspace/src/code.google.com/p/draw2d')
34 files changed, 5618 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/advanced_path.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/advanced_path.go new file mode 100644 index 000000000..68f1d782b --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/advanced_path.go @@ -0,0 +1,42 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +import ( + "math" +) + +//high level path creation + +func Rect(path Path, x1, y1, x2, y2 float64) { + path.MoveTo(x1, y1) + path.LineTo(x2, y1) + path.LineTo(x2, y2) + path.LineTo(x1, y2) + path.Close() +} + +func RoundRect(path Path, x1, y1, x2, y2, arcWidth, arcHeight float64) { + arcWidth = arcWidth / 2 + arcHeight = arcHeight / 2 + path.MoveTo(x1, y1+arcHeight) + path.QuadCurveTo(x1, y1, x1+arcWidth, y1) + path.LineTo(x2-arcWidth, y1) + path.QuadCurveTo(x2, y1, x2, y1+arcHeight) + path.LineTo(x2, y2-arcHeight) + path.QuadCurveTo(x2, y2, x2-arcWidth, y2) + path.LineTo(x1+arcWidth, y2) + path.QuadCurveTo(x1, y2, x1, y2-arcHeight) + path.Close() +} + +func Ellipse(path Path, cx, cy, rx, ry float64) { + path.ArcTo(cx, cy, rx, ry, 0, -math.Pi*2) + path.Close() +} + +func Circle(path Path, cx, cy, radius float64) { + path.ArcTo(cx, cy, radius, radius, 0, -math.Pi*2) + path.Close() +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/arc.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/arc.go new file mode 100644 index 000000000..0698b8da0 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/arc.go @@ -0,0 +1,67 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/raster" + "math" +) + +func arc(t VertexConverter, x, y, rx, ry, start, angle, scale float64) (lastX, lastY float64) { + end := start + angle + clockWise := true + if angle < 0 { + clockWise = false + } + ra := (math.Abs(rx) + math.Abs(ry)) / 2 + da := math.Acos(ra/(ra+0.125/scale)) * 2 + //normalize + if !clockWise { + da = -da + } + angle = start + da + var curX, curY float64 + for { + if (angle < end-da/4) != clockWise { + curX = x + math.Cos(end)*rx + curY = y + math.Sin(end)*ry + return curX, curY + } + curX = x + math.Cos(angle)*rx + curY = y + math.Sin(angle)*ry + + angle += da + t.Vertex(curX, curY) + } + return curX, curY +} + +func arcAdder(adder raster.Adder, x, y, rx, ry, start, angle, scale float64) raster.Point { + end := start + angle + clockWise := true + if angle < 0 { + clockWise = false + } + ra := (math.Abs(rx) + math.Abs(ry)) / 2 + da := math.Acos(ra/(ra+0.125/scale)) * 2 + //normalize + if !clockWise { + da = -da + } + angle = start + da + var curX, curY float64 + for { + if (angle < end-da/4) != clockWise { + curX = x + math.Cos(end)*rx + curY = y + math.Sin(end)*ry + return raster.Point{raster.Fix32(curX * 256), raster.Fix32(curY * 256)} + } + curX = x + math.Cos(angle)*rx + curY = y + math.Sin(angle)*ry + + angle += da + adder.Add1(raster.Point{raster.Fix32(curX * 256), raster.Fix32(curY * 256)}) + } + return raster.Point{raster.Fix32(curX * 256), raster.Fix32(curY * 256)} +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/Makefile b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/Makefile new file mode 100644 index 000000000..15ceee070 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/Makefile @@ -0,0 +1,11 @@ +include $(GOROOT)/src/Make.inc
+
+TARG=draw2d.googlecode.com/hg/draw2d/curve
+GOFILES=\
+ cubic_float64.go\
+ quad_float64.go\
+ cubic_float64_others.go\
+
+
+
+include $(GOROOT)/src/Make.pkg
diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/arc.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/arc.go new file mode 100644 index 000000000..92850e979 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/arc.go @@ -0,0 +1,36 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff +package curve + +import ( + "math" +) + +func SegmentArc(t LineTracer, x, y, rx, ry, start, angle, scale float64) { + end := start + angle + clockWise := true + if angle < 0 { + clockWise = false + } + ra := (math.Abs(rx) + math.Abs(ry)) / 2 + da := math.Acos(ra/(ra+0.125/scale)) * 2 + //normalize + if !clockWise { + da = -da + } + angle = start + da + var curX, curY float64 + for { + if (angle < end-da/4) != clockWise { + curX = x + math.Cos(end)*rx + curY = y + math.Sin(end)*ry + break; + } + curX = x + math.Cos(angle)*rx + curY = y + math.Sin(angle)*ry + + angle += da + t.LineTo(curX, curY) + } + t.LineTo(curX, curY) +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64.go new file mode 100644 index 000000000..64a7ac639 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64.go @@ -0,0 +1,67 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 17/05/2011 by Laurent Le Goff +package curve + +import ( + "math" +) + +const ( + CurveRecursionLimit = 32 +) + +// X1, Y1, X2, Y2, X3, Y3, X4, Y4 float64 +type CubicCurveFloat64 [8]float64 + +type LineTracer interface { + LineTo(x, y float64) +} + +func (c *CubicCurveFloat64) Subdivide(c1, c2 *CubicCurveFloat64) (x23, y23 float64) { + // Calculate all the mid-points of the line segments + //---------------------- + c1[0], c1[1] = c[0], c[1] + c2[6], c2[7] = c[6], c[7] + c1[2] = (c[0] + c[2]) / 2 + c1[3] = (c[1] + c[3]) / 2 + x23 = (c[2] + c[4]) / 2 + y23 = (c[3] + c[5]) / 2 + c2[4] = (c[4] + c[6]) / 2 + c2[5] = (c[5] + c[7]) / 2 + c1[4] = (c1[2] + x23) / 2 + c1[5] = (c1[3] + y23) / 2 + c2[2] = (x23 + c2[4]) / 2 + c2[3] = (y23 + c2[5]) / 2 + c1[6] = (c1[4] + c2[2]) / 2 + c1[7] = (c1[5] + c2[3]) / 2 + c2[0], c2[1] = c1[6], c1[7] + return +} + +func (curve *CubicCurveFloat64) Segment(t LineTracer, flattening_threshold float64) { + var curves [CurveRecursionLimit]CubicCurveFloat64 + curves[0] = *curve + i := 0 + // current curve + var c *CubicCurveFloat64 + + var dx, dy, d2, d3 float64 + + for i >= 0 { + c = &curves[i] + dx = c[6] - c[0] + dy = c[7] - c[1] + + d2 = math.Abs(((c[2]-c[6])*dy - (c[3]-c[7])*dx)) + d3 = math.Abs(((c[4]-c[6])*dy - (c[5]-c[7])*dx)) + + if (d2+d3)*(d2+d3) < flattening_threshold*(dx*dx+dy*dy) || i == len(curves)-1 { + t.LineTo(c[6], c[7]) + i-- + } else { + // second half of bezier go lower onto the stack + c.Subdivide(&curves[i+1], &curves[i]) + i++ + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64_others.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64_others.go new file mode 100644 index 000000000..a888b22a1 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/cubic_float64_others.go @@ -0,0 +1,696 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 17/05/2011 by Laurent Le Goff +package curve + +import ( + "math" +) + +const ( + CurveCollinearityEpsilon = 1e-30 + CurveAngleToleranceEpsilon = 0.01 +) + +//mu ranges from 0 to 1, start to end of curve +func (c *CubicCurveFloat64) ArbitraryPoint(mu float64) (x, y float64) { + + mum1 := 1 - mu + mum13 := mum1 * mum1 * mum1 + mu3 := mu * mu * mu + + x = mum13*c[0] + 3*mu*mum1*mum1*c[2] + 3*mu*mu*mum1*c[4] + mu3*c[6] + y = mum13*c[1] + 3*mu*mum1*mum1*c[3] + 3*mu*mu*mum1*c[5] + mu3*c[7] + return +} + +func (c *CubicCurveFloat64) SubdivideAt(c1, c2 *CubicCurveFloat64, t float64) (x23, y23 float64) { + inv_t := (1 - t) + c1[0], c1[1] = c[0], c[1] + c2[6], c2[7] = c[6], c[7] + + c1[2] = inv_t*c[0] + t*c[2] + c1[3] = inv_t*c[1] + t*c[3] + + x23 = inv_t*c[2] + t*c[4] + y23 = inv_t*c[3] + t*c[5] + + c2[4] = inv_t*c[4] + t*c[6] + c2[5] = inv_t*c[5] + t*c[7] + + c1[4] = inv_t*c1[2] + t*x23 + c1[5] = inv_t*c1[3] + t*y23 + + c2[2] = inv_t*x23 + t*c2[4] + c2[3] = inv_t*y23 + t*c2[5] + + c1[6] = inv_t*c1[4] + t*c2[2] + c1[7] = inv_t*c1[5] + t*c2[3] + + c2[0], c2[1] = c1[6], c1[7] + return +} + +func (c *CubicCurveFloat64) EstimateDistance() float64 { + dx1 := c[2] - c[0] + dy1 := c[3] - c[1] + dx2 := c[4] - c[2] + dy2 := c[5] - c[3] + dx3 := c[6] - c[4] + dy3 := c[7] - c[5] + return math.Sqrt(dx1*dx1+dy1*dy1) + math.Sqrt(dx2*dx2+dy2*dy2) + math.Sqrt(dx3*dx3+dy3*dy3) +} + +// subdivide the curve in straight lines using line approximation and Casteljau recursive subdivision +func (c *CubicCurveFloat64) SegmentRec(t LineTracer, flattening_threshold float64) { + c.segmentRec(t, flattening_threshold) + t.LineTo(c[6], c[7]) +} + +func (c *CubicCurveFloat64) segmentRec(t LineTracer, flattening_threshold float64) { + var c1, c2 CubicCurveFloat64 + c.Subdivide(&c1, &c2) + + // Try to approximate the full cubic curve by a single straight line + //------------------ + dx := c[6] - c[0] + dy := c[7] - c[1] + + d2 := math.Abs(((c[2]-c[6])*dy - (c[3]-c[7])*dx)) + d3 := math.Abs(((c[4]-c[6])*dy - (c[5]-c[7])*dx)) + + if (d2+d3)*(d2+d3) < flattening_threshold*(dx*dx+dy*dy) { + t.LineTo(c[6], c[7]) + return + } + // Continue subdivision + //---------------------- + c1.segmentRec(t, flattening_threshold) + c2.segmentRec(t, flattening_threshold) +} + +/* + The function has the following parameters: + approximationScale : + Eventually determines the approximation accuracy. In practice we need to transform points from the World coordinate system to the Screen one. + It always has some scaling coefficient. + The curves are usually processed in the World coordinates, while the approximation accuracy should be eventually in pixels. + Usually it looks as follows: + curved.approximationScale(transform.scale()); + where transform is the affine matrix that includes all the transformations, including viewport and zoom. + angleTolerance : + You set it in radians. + The less this value is the more accurate will be the approximation at sharp turns. + But 0 means that we don't consider angle conditions at all. + cuspLimit : + An angle in radians. + If 0, only the real cusps will have bevel cuts. + If more than 0, it will restrict the sharpness. + The more this value is the less sharp turns will be cut. + Typically it should not exceed 10-15 degrees. +*/ +func (c *CubicCurveFloat64) AdaptiveSegmentRec(t LineTracer, approximationScale, angleTolerance, cuspLimit float64) { + cuspLimit = computeCuspLimit(cuspLimit) + distanceToleranceSquare := 0.5 / approximationScale + distanceToleranceSquare = distanceToleranceSquare * distanceToleranceSquare + c.adaptiveSegmentRec(t, 0, distanceToleranceSquare, angleTolerance, cuspLimit) + t.LineTo(c[6], c[7]) +} + +func computeCuspLimit(v float64) (r float64) { + if v == 0.0 { + r = 0.0 + } else { + r = math.Pi - v + } + return +} + +func squareDistance(x1, y1, x2, y2 float64) float64 { + dx := x2 - x1 + dy := y2 - y1 + return dx*dx + dy*dy +} + +/** + * http://www.antigrain.com/research/adaptive_bezier/index.html + */ +func (c *CubicCurveFloat64) adaptiveSegmentRec(t LineTracer, level int, distanceToleranceSquare, angleTolerance, cuspLimit float64) { + if level > CurveRecursionLimit { + return + } + var c1, c2 CubicCurveFloat64 + x23, y23 := c.Subdivide(&c1, &c2) + + // Try to approximate the full cubic curve by a single straight line + //------------------ + dx := c[6] - c[0] + dy := c[7] - c[1] + + d2 := math.Abs(((c[2]-c[6])*dy - (c[3]-c[7])*dx)) + d3 := math.Abs(((c[4]-c[6])*dy - (c[5]-c[7])*dx)) + switch { + case d2 <= CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // All collinear OR p1==p4 + //---------------------- + k := dx*dx + dy*dy + if k == 0 { + d2 = squareDistance(c[0], c[1], c[2], c[3]) + d3 = squareDistance(c[6], c[7], c[4], c[5]) + } else { + k = 1 / k + da1 := c[2] - c[0] + da2 := c[3] - c[1] + d2 = k * (da1*dx + da2*dy) + da1 = c[4] - c[0] + da2 = c[5] - c[1] + d3 = k * (da1*dx + da2*dy) + if d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1 { + // Simple collinear case, 1---2---3---4 + // We can leave just two endpoints + return + } + if d2 <= 0 { + d2 = squareDistance(c[2], c[3], c[0], c[1]) + } else if d2 >= 1 { + d2 = squareDistance(c[2], c[3], c[6], c[7]) + } else { + d2 = squareDistance(c[2], c[3], c[0]+d2*dx, c[1]+d2*dy) + } + + if d3 <= 0 { + d3 = squareDistance(c[4], c[5], c[0], c[1]) + } else if d3 >= 1 { + d3 = squareDistance(c[4], c[5], c[6], c[7]) + } else { + d3 = squareDistance(c[4], c[5], c[0]+d3*dx, c[1]+d3*dy) + } + } + if d2 > d3 { + if d2 < distanceToleranceSquare { + t.LineTo(c[2], c[3]) + return + } + } else { + if d3 < distanceToleranceSquare { + t.LineTo(c[4], c[5]) + return + } + } + + case d2 <= CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // p1,p2,p4 are collinear, p3 is significant + //---------------------- + if d3*d3 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + return + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(c[7]-c[5], c[6]-c[4]) - math.Atan2(c[5]-c[3], c[4]-c[2])) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + t.LineTo(c[2], c[3]) + t.LineTo(c[4], c[5]) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[4], c[5]) + return + } + } + } + + case d2 > CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // p1,p3,p4 are collinear, p2 is significant + //---------------------- + if d2*d2 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + return + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(c[5]-c[3], c[4]-c[2]) - math.Atan2(c[3]-c[1], c[2]-c[0])) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + t.LineTo(c[2], c[3]) + t.LineTo(c[4], c[5]) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[2], c[3]) + return + } + } + } + + case d2 > CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // Regular case + //----------------- + if (d2+d3)*(d2+d3) <= distanceToleranceSquare*(dx*dx+dy*dy) { + // If the curvature doesn't exceed the distanceTolerance value + // we tend to finish subdivisions. + //---------------------- + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + return + } + + // Angle & Cusp Condition + //---------------------- + k := math.Atan2(c[5]-c[3], c[4]-c[2]) + da1 := math.Abs(k - math.Atan2(c[3]-c[1], c[2]-c[0])) + da2 := math.Abs(math.Atan2(c[7]-c[5], c[6]-c[4]) - k) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + if da2 >= math.Pi { + da2 = 2*math.Pi - da2 + } + + if da1+da2 < angleTolerance { + // Finally we can stop the recursion + //---------------------- + t.LineTo(x23, y23) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[2], c[3]) + return + } + + if da2 > cuspLimit { + t.LineTo(c[4], c[5]) + return + } + } + } + } + + // Continue subdivision + //---------------------- + c1.adaptiveSegmentRec(t, level+1, distanceToleranceSquare, angleTolerance, cuspLimit) + c2.adaptiveSegmentRec(t, level+1, distanceToleranceSquare, angleTolerance, cuspLimit) + +} + +func (curve *CubicCurveFloat64) AdaptiveSegment(t LineTracer, approximationScale, angleTolerance, cuspLimit float64) { + cuspLimit = computeCuspLimit(cuspLimit) + distanceToleranceSquare := 0.5 / approximationScale + distanceToleranceSquare = distanceToleranceSquare * distanceToleranceSquare + + var curves [CurveRecursionLimit]CubicCurveFloat64 + curves[0] = *curve + i := 0 + // current curve + var c *CubicCurveFloat64 + var c1, c2 CubicCurveFloat64 + var dx, dy, d2, d3, k, x23, y23 float64 + for i >= 0 { + c = &curves[i] + x23, y23 = c.Subdivide(&c1, &c2) + + // Try to approximate the full cubic curve by a single straight line + //------------------ + dx = c[6] - c[0] + dy = c[7] - c[1] + + d2 = math.Abs(((c[2]-c[6])*dy - (c[3]-c[7])*dx)) + d3 = math.Abs(((c[4]-c[6])*dy - (c[5]-c[7])*dx)) + switch { + case i == len(curves)-1: + t.LineTo(c[6], c[7]) + i-- + continue + case d2 <= CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // All collinear OR p1==p4 + //---------------------- + k = dx*dx + dy*dy + if k == 0 { + d2 = squareDistance(c[0], c[1], c[2], c[3]) + d3 = squareDistance(c[6], c[7], c[4], c[5]) + } else { + k = 1 / k + da1 := c[2] - c[0] + da2 := c[3] - c[1] + d2 = k * (da1*dx + da2*dy) + da1 = c[4] - c[0] + da2 = c[5] - c[1] + d3 = k * (da1*dx + da2*dy) + if d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1 { + // Simple collinear case, 1---2---3---4 + // We can leave just two endpoints + i-- + continue + } + if d2 <= 0 { + d2 = squareDistance(c[2], c[3], c[0], c[1]) + } else if d2 >= 1 { + d2 = squareDistance(c[2], c[3], c[6], c[7]) + } else { + d2 = squareDistance(c[2], c[3], c[0]+d2*dx, c[1]+d2*dy) + } + + if d3 <= 0 { + d3 = squareDistance(c[4], c[5], c[0], c[1]) + } else if d3 >= 1 { + d3 = squareDistance(c[4], c[5], c[6], c[7]) + } else { + d3 = squareDistance(c[4], c[5], c[0]+d3*dx, c[1]+d3*dy) + } + } + if d2 > d3 { + if d2 < distanceToleranceSquare { + t.LineTo(c[2], c[3]) + i-- + continue + } + } else { + if d3 < distanceToleranceSquare { + t.LineTo(c[4], c[5]) + i-- + continue + } + } + + case d2 <= CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // p1,p2,p4 are collinear, p3 is significant + //---------------------- + if d3*d3 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + i-- + continue + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(c[7]-c[5], c[6]-c[4]) - math.Atan2(c[5]-c[3], c[4]-c[2])) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + t.LineTo(c[2], c[3]) + t.LineTo(c[4], c[5]) + i-- + continue + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[4], c[5]) + i-- + continue + } + } + } + + case d2 > CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // p1,p3,p4 are collinear, p2 is significant + //---------------------- + if d2*d2 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + i-- + continue + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(c[5]-c[3], c[4]-c[2]) - math.Atan2(c[3]-c[1], c[2]-c[0])) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + t.LineTo(c[2], c[3]) + t.LineTo(c[4], c[5]) + i-- + continue + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[2], c[3]) + i-- + continue + } + } + } + + case d2 > CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // Regular case + //----------------- + if (d2+d3)*(d2+d3) <= distanceToleranceSquare*(dx*dx+dy*dy) { + // If the curvature doesn't exceed the distanceTolerance value + // we tend to finish subdivisions. + //---------------------- + if angleTolerance < CurveAngleToleranceEpsilon { + t.LineTo(x23, y23) + i-- + continue + } + + // Angle & Cusp Condition + //---------------------- + k := math.Atan2(c[5]-c[3], c[4]-c[2]) + da1 := math.Abs(k - math.Atan2(c[3]-c[1], c[2]-c[0])) + da2 := math.Abs(math.Atan2(c[7]-c[5], c[6]-c[4]) - k) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + if da2 >= math.Pi { + da2 = 2*math.Pi - da2 + } + + if da1+da2 < angleTolerance { + // Finally we can stop the recursion + //---------------------- + t.LineTo(x23, y23) + i-- + continue + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + t.LineTo(c[2], c[3]) + i-- + continue + } + + if da2 > cuspLimit { + t.LineTo(c[4], c[5]) + i-- + continue + } + } + } + } + + // Continue subdivision + //---------------------- + curves[i+1], curves[i] = c1, c2 + i++ + } + t.LineTo(curve[6], curve[7]) +} + +/********************** Ahmad thesis *******************/ + +/************************************************************************************** +* This code is the implementation of the Parabolic Approximation (PA). Although * +* it uses recursive subdivision as a safe net for the failing cases, this is an * +* iterative routine and reduces considerably the number of vertices (point) * +* generation. * +**************************************************************************************/ + +func (c *CubicCurveFloat64) ParabolicSegment(t LineTracer, flattening_threshold float64) { + estimatedIFP := c.numberOfInflectionPoints() + if estimatedIFP == 0 { + // If no inflection points then apply PA on the full Bezier segment. + c.doParabolicApproximation(t, flattening_threshold) + return + } + // If one or more inflection point then we will have to subdivide the curve + numOfIfP, t1, t2 := c.findInflectionPoints() + if numOfIfP == 2 { + // Case when 2 inflection points then divide at the smallest one first + var sub1, tmp1, sub2, sub3 CubicCurveFloat64 + c.SubdivideAt(&sub1, &tmp1, t1) + // Now find the second inflection point in the second curve an subdivide + numOfIfP, t1, t2 = tmp1.findInflectionPoints() + if numOfIfP == 2 { + tmp1.SubdivideAt(&sub2, &sub3, t2) + } else if numOfIfP == 1 { + tmp1.SubdivideAt(&sub2, &sub3, t1) + } else { + return + } + // Use PA for first subsegment + sub1.doParabolicApproximation(t, flattening_threshold) + // Use RS for the second (middle) subsegment + sub2.Segment(t, flattening_threshold) + // Drop the last point in the array will be added by the PA in third subsegment + //noOfPoints--; + // Use PA for the third curve + sub3.doParabolicApproximation(t, flattening_threshold) + } else if numOfIfP == 1 { + // Case where there is one inflection point, subdivide once and use PA on + // both subsegments + var sub1, sub2 CubicCurveFloat64 + c.SubdivideAt(&sub1, &sub2, t1) + sub1.doParabolicApproximation(t, flattening_threshold) + //noOfPoints--; + sub2.doParabolicApproximation(t, flattening_threshold) + } else { + // Case where there is no inflection USA PA directly + c.doParabolicApproximation(t, flattening_threshold) + } +} + +// Find the third control point deviation form the axis +func (c *CubicCurveFloat64) thirdControlPointDeviation() float64 { + dx := c[2] - c[0] + dy := c[3] - c[1] + l2 := dx*dx + dy*dy + if l2 == 0 { + return 0 + } + l := math.Sqrt(l2) + r := (c[3] - c[1]) / l + s := (c[0] - c[2]) / l + u := (c[2]*c[1] - c[0]*c[3]) / l + return math.Abs(r*c[4] + s*c[5] + u) +} + +// Find the number of inflection point +func (c *CubicCurveFloat64) numberOfInflectionPoints() int { + dx21 := (c[2] - c[0]) + dy21 := (c[3] - c[1]) + dx32 := (c[4] - c[2]) + dy32 := (c[5] - c[3]) + dx43 := (c[6] - c[4]) + dy43 := (c[7] - c[5]) + if ((dx21*dy32 - dy21*dx32) * (dx32*dy43 - dy32*dx43)) < 0 { + return 1 // One inflection point + } else if ((dx21*dy32 - dy21*dx32) * (dx21*dy43 - dy21*dx43)) > 0 { + return 0 // No inflection point + } else { + // Most cases no inflection point + b1 := (dx21*dx32 + dy21*dy32) > 0 + b2 := (dx32*dx43 + dy32*dy43) > 0 + if b1 || b2 && !(b1 && b2) { // xor!! + return 0 + } + } + return -1 // cases where there in zero or two inflection points +} + +// This is the main function where all the work is done +func (curve *CubicCurveFloat64) doParabolicApproximation(tracer LineTracer, flattening_threshold float64) { + var c *CubicCurveFloat64 + c = curve + var d, t, dx, dy, d2, d3 float64 + for { + dx = c[6] - c[0] + dy = c[7] - c[1] + + d2 = math.Abs(((c[2]-c[6])*dy - (c[3]-c[7])*dx)) + d3 = math.Abs(((c[4]-c[6])*dy - (c[5]-c[7])*dx)) + + if (d2+d3)*(d2+d3) < flattening_threshold*(dx*dx+dy*dy) { + // If the subsegment deviation satisfy the flatness then store the last + // point and stop + tracer.LineTo(c[6], c[7]) + break + } + // Find the third control point deviation and the t values for subdivision + d = c.thirdControlPointDeviation() + t = 2 * math.Sqrt(flattening_threshold/d/3) + if t > 1 { + // Case where the t value calculated is invalid so using RS + c.Segment(tracer, flattening_threshold) + break + } + // Valid t value to subdivide at that calculated value + var b1, b2 CubicCurveFloat64 + c.SubdivideAt(&b1, &b2, t) + // First subsegment should have its deviation equal to flatness + dx = b1[6] - b1[0] + dy = b1[7] - b1[1] + + d2 = math.Abs(((b1[2]-b1[6])*dy - (b1[3]-b1[7])*dx)) + d3 = math.Abs(((b1[4]-b1[6])*dy - (b1[5]-b1[7])*dx)) + + if (d2+d3)*(d2+d3) > flattening_threshold*(dx*dx+dy*dy) { + // if not then use RS to handle any mathematical errors + b1.Segment(tracer, flattening_threshold) + } else { + tracer.LineTo(b1[6], b1[7]) + } + // repeat the process for the left over subsegment. + c = &b2 + } +} + +// Find the actual inflection points and return the number of inflection points found +// if 2 inflection points found, the first one returned will be with smaller t value. +func (curve *CubicCurveFloat64) findInflectionPoints() (int, firstIfp, secondIfp float64) { + // For Cubic Bezier curve with equation P=a*t^3 + b*t^2 + c*t + d + // slope of the curve dP/dt = 3*a*t^2 + 2*b*t + c + // a = (float)(-bez.p1 + 3*bez.p2 - 3*bez.p3 + bez.p4); + // b = (float)(3*bez.p1 - 6*bez.p2 + 3*bez.p3); + // c = (float)(-3*bez.p1 + 3*bez.p2); + ax := (-curve[0] + 3*curve[2] - 3*curve[4] + curve[6]) + bx := (3*curve[0] - 6*curve[2] + 3*curve[4]) + cx := (-3*curve[0] + 3*curve[2]) + ay := (-curve[1] + 3*curve[3] - 3*curve[5] + curve[7]) + by := (3*curve[1] - 6*curve[3] + 3*curve[5]) + cy := (-3*curve[1] + 3*curve[3]) + a := (3 * (ay*bx - ax*by)) + b := (3 * (ay*cx - ax*cy)) + c := (by*cx - bx*cy) + r2 := (b*b - 4*a*c) + firstIfp = 0.0 + secondIfp = 0.0 + if r2 >= 0.0 && a != 0.0 { + r := math.Sqrt(r2) + firstIfp = ((-b + r) / (2 * a)) + secondIfp = ((-b - r) / (2 * a)) + if (firstIfp > 0.0 && firstIfp < 1.0) && (secondIfp > 0.0 && secondIfp < 1.0) { + if firstIfp > secondIfp { + tmp := firstIfp + firstIfp = secondIfp + secondIfp = tmp + } + if secondIfp-firstIfp > 0.00001 { + return 2, firstIfp, secondIfp + } else { + return 1, firstIfp, secondIfp + } + } else if firstIfp > 0.0 && firstIfp < 1.0 { + return 1, firstIfp, secondIfp + } else if secondIfp > 0.0 && secondIfp < 1.0 { + firstIfp = secondIfp + return 1, firstIfp, secondIfp + } + return 0, firstIfp, secondIfp + } + return 0, firstIfp, secondIfp +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/curve_test.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/curve_test.go new file mode 100644 index 000000000..5e9eecac0 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/curve_test.go @@ -0,0 +1,262 @@ +package curve + +import ( + "bufio" + "code.google.com/p/draw2d/draw2d/raster" + "fmt" + "image" + "image/color" + "image/draw" + "image/png" + "log" + "os" + "testing" +) + +var ( + flattening_threshold float64 = 0.5 + testsCubicFloat64 = []CubicCurveFloat64{ + CubicCurveFloat64{100, 100, 200, 100, 100, 200, 200, 200}, + CubicCurveFloat64{100, 100, 300, 200, 200, 200, 300, 100}, + CubicCurveFloat64{100, 100, 0, 300, 200, 0, 300, 300}, + CubicCurveFloat64{150, 290, 10, 10, 290, 10, 150, 290}, + CubicCurveFloat64{10, 290, 10, 10, 290, 10, 290, 290}, + CubicCurveFloat64{100, 290, 290, 10, 10, 10, 200, 290}, + } + testsQuadFloat64 = []QuadCurveFloat64{ + QuadCurveFloat64{100, 100, 200, 100, 200, 200}, + QuadCurveFloat64{100, 100, 290, 200, 290, 100}, + QuadCurveFloat64{100, 100, 0, 290, 200, 290}, + QuadCurveFloat64{150, 290, 10, 10, 290, 290}, + QuadCurveFloat64{10, 290, 10, 10, 290, 290}, + QuadCurveFloat64{100, 290, 290, 10, 120, 290}, + } +) + +type Path struct { + points []float64 +} + +func (p *Path) LineTo(x, y float64) { + if len(p.points)+2 > cap(p.points) { + points := make([]float64, len(p.points)+2, len(p.points)+32) + copy(points, p.points) + p.points = points + } else { + p.points = p.points[0 : len(p.points)+2] + } + p.points[len(p.points)-2] = x + p.points[len(p.points)-1] = y +} + +func init() { + f, err := os.Create("_test.html") + if err != nil { + log.Println(err) + os.Exit(1) + } + defer f.Close() + log.Printf("Create html viewer") + f.Write([]byte("<html><body>")) + for i := 0; i < len(testsCubicFloat64); i++ { + f.Write([]byte(fmt.Sprintf("<div><img src='_testRec%d.png'/>\n<img src='_test%d.png'/>\n<img src='_testAdaptiveRec%d.png'/>\n<img src='_testAdaptive%d.png'/>\n<img src='_testParabolic%d.png'/>\n</div>\n", i, i, i, i, i))) + } + for i := 0; i < len(testsQuadFloat64); i++ { + f.Write([]byte(fmt.Sprintf("<div><img src='_testQuad%d.png'/>\n</div>\n", i))) + } + f.Write([]byte("</body></html>")) + +} + +func savepng(filePath string, m image.Image) { + f, err := os.Create(filePath) + if err != nil { + log.Println(err) + os.Exit(1) + } + defer f.Close() + b := bufio.NewWriter(f) + err = png.Encode(b, m) + if err != nil { + log.Println(err) + os.Exit(1) + } + err = b.Flush() + if err != nil { + log.Println(err) + os.Exit(1) + } +} + +func drawPoints(img draw.Image, c color.Color, s ...float64) image.Image { + /*for i := 0; i < len(s); i += 2 { + x, y := int(s[i]+0.5), int(s[i+1]+0.5) + img.Set(x, y, c) + img.Set(x, y+1, c) + img.Set(x, y-1, c) + img.Set(x+1, y, c) + img.Set(x+1, y+1, c) + img.Set(x+1, y-1, c) + img.Set(x-1, y, c) + img.Set(x-1, y+1, c) + img.Set(x-1, y-1, c) + + }*/ + return img +} + +func TestCubicCurveRec(t *testing.T) { + for i, curve := range testsCubicFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.SegmentRec(&p, flattening_threshold) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_testRec%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func TestCubicCurve(t *testing.T) { + for i, curve := range testsCubicFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.Segment(&p, flattening_threshold) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_test%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func TestCubicCurveAdaptiveRec(t *testing.T) { + for i, curve := range testsCubicFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.AdaptiveSegmentRec(&p, 1, 0, 0) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_testAdaptiveRec%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func TestCubicCurveAdaptive(t *testing.T) { + for i, curve := range testsCubicFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.AdaptiveSegment(&p, 1, 0, 0) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_testAdaptive%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func TestCubicCurveParabolic(t *testing.T) { + for i, curve := range testsCubicFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.ParabolicSegment(&p, flattening_threshold) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_testParabolic%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func TestQuadCurve(t *testing.T) { + for i, curve := range testsQuadFloat64 { + var p Path + p.LineTo(curve[0], curve[1]) + curve.Segment(&p, flattening_threshold) + img := image.NewNRGBA(image.Rect(0, 0, 300, 300)) + raster.PolylineBresenham(img, color.NRGBA{0xff, 0, 0, 0xff}, curve[:]...) + raster.PolylineBresenham(img, image.Black, p.points...) + //drawPoints(img, image.NRGBAColor{0, 0, 0, 0xff}, curve[:]...) + drawPoints(img, color.NRGBA{0, 0, 0, 0xff}, p.points...) + savepng(fmt.Sprintf("_testQuad%d.png", i), img) + log.Printf("Num of points: %d\n", len(p.points)) + } + fmt.Println() +} + +func BenchmarkCubicCurveRec(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsCubicFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.SegmentRec(&p, flattening_threshold) + } + } +} + +func BenchmarkCubicCurve(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsCubicFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.Segment(&p, flattening_threshold) + } + } +} + +func BenchmarkCubicCurveAdaptiveRec(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsCubicFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.AdaptiveSegmentRec(&p, 1, 0, 0) + } + } +} + +func BenchmarkCubicCurveAdaptive(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsCubicFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.AdaptiveSegment(&p, 1, 0, 0) + } + } +} + +func BenchmarkCubicCurveParabolic(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsCubicFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.ParabolicSegment(&p, flattening_threshold) + } + } +} + +func BenchmarkQuadCurve(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, curve := range testsQuadFloat64 { + p := Path{make([]float64, 0, 32)} + p.LineTo(curve[0], curve[1]) + curve.Segment(&p, flattening_threshold) + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/quad_float64.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/quad_float64.go new file mode 100644 index 000000000..bd72affbb --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curve/quad_float64.go @@ -0,0 +1,51 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 17/05/2011 by Laurent Le Goff +package curve + +import ( + "math" +) + +//X1, Y1, X2, Y2, X3, Y3 float64 +type QuadCurveFloat64 [6]float64 + +func (c *QuadCurveFloat64) Subdivide(c1, c2 *QuadCurveFloat64) { + // Calculate all the mid-points of the line segments + //---------------------- + c1[0], c1[1] = c[0], c[1] + c2[4], c2[5] = c[4], c[5] + c1[2] = (c[0] + c[2]) / 2 + c1[3] = (c[1] + c[3]) / 2 + c2[2] = (c[2] + c[4]) / 2 + c2[3] = (c[3] + c[5]) / 2 + c1[4] = (c1[2] + c2[2]) / 2 + c1[5] = (c1[3] + c2[3]) / 2 + c2[0], c2[1] = c1[4], c1[5] + return +} + +func (curve *QuadCurveFloat64) Segment(t LineTracer, flattening_threshold float64) { + var curves [CurveRecursionLimit]QuadCurveFloat64 + curves[0] = *curve + i := 0 + // current curve + var c *QuadCurveFloat64 + var dx, dy, d float64 + + for i >= 0 { + c = &curves[i] + dx = c[4] - c[0] + dy = c[5] - c[1] + + d = math.Abs(((c[2]-c[4])*dy - (c[3]-c[5])*dx)) + + if (d*d) < flattening_threshold*(dx*dx+dy*dy) || i == len(curves)-1 { + t.LineTo(c[4], c[5]) + i-- + } else { + // second half of bezier go lower onto the stack + c.Subdivide(&curves[i+1], &curves[i]) + i++ + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curves.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curves.go new file mode 100644 index 000000000..4623cd4dc --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/curves.go @@ -0,0 +1,336 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "math" +) + +var ( + CurveRecursionLimit = 32 + CurveCollinearityEpsilon = 1e-30 + CurveAngleToleranceEpsilon = 0.01 +) + +/* + The function has the following parameters: + approximationScale : + Eventually determines the approximation accuracy. In practice we need to transform points from the World coordinate system to the Screen one. + It always has some scaling coefficient. + The curves are usually processed in the World coordinates, while the approximation accuracy should be eventually in pixels. + Usually it looks as follows: + curved.approximationScale(transform.scale()); + where transform is the affine matrix that includes all the transformations, including viewport and zoom. + angleTolerance : + You set it in radians. + The less this value is the more accurate will be the approximation at sharp turns. + But 0 means that we don't consider angle conditions at all. + cuspLimit : + An angle in radians. + If 0, only the real cusps will have bevel cuts. + If more than 0, it will restrict the sharpness. + The more this value is the less sharp turns will be cut. + Typically it should not exceed 10-15 degrees. +*/ +func cubicBezier(v VertexConverter, x1, y1, x2, y2, x3, y3, x4, y4, approximationScale, angleTolerance, cuspLimit float64) { + cuspLimit = computeCuspLimit(cuspLimit) + distanceToleranceSquare := 0.5 / approximationScale + distanceToleranceSquare = distanceToleranceSquare * distanceToleranceSquare + recursiveCubicBezier(v, x1, y1, x2, y2, x3, y3, x4, y4, 0, distanceToleranceSquare, angleTolerance, cuspLimit) +} + +/* + * see cubicBezier comments for approximationScale and angleTolerance definition + */ +func quadraticBezier(v VertexConverter, x1, y1, x2, y2, x3, y3, approximationScale, angleTolerance float64) { + distanceToleranceSquare := 0.5 / approximationScale + distanceToleranceSquare = distanceToleranceSquare * distanceToleranceSquare + + recursiveQuadraticBezierBezier(v, x1, y1, x2, y2, x3, y3, 0, distanceToleranceSquare, angleTolerance) +} + +func computeCuspLimit(v float64) (r float64) { + if v == 0.0 { + r = 0.0 + } else { + r = math.Pi - v + } + return +} + +/** + * http://www.antigrain.com/research/adaptive_bezier/index.html + */ +func recursiveQuadraticBezierBezier(v VertexConverter, x1, y1, x2, y2, x3, y3 float64, level int, distanceToleranceSquare, angleTolerance float64) { + if level > CurveRecursionLimit { + return + } + + // Calculate all the mid-points of the line segments + //---------------------- + x12 := (x1 + x2) / 2 + y12 := (y1 + y2) / 2 + x23 := (x2 + x3) / 2 + y23 := (y2 + y3) / 2 + x123 := (x12 + x23) / 2 + y123 := (y12 + y23) / 2 + + dx := x3 - x1 + dy := y3 - y1 + d := math.Abs(((x2-x3)*dy - (y2-y3)*dx)) + + if d > CurveCollinearityEpsilon { + // Regular case + //----------------- + if d*d <= distanceToleranceSquare*(dx*dx+dy*dy) { + // If the curvature doesn't exceed the distanceTolerance value + // we tend to finish subdivisions. + //---------------------- + if angleTolerance < CurveAngleToleranceEpsilon { + v.Vertex(x123, y123) + return + } + + // Angle & Cusp Condition + //---------------------- + da := math.Abs(math.Atan2(y3-y2, x3-x2) - math.Atan2(y2-y1, x2-x1)) + if da >= math.Pi { + da = 2*math.Pi - da + } + + if da < angleTolerance { + // Finally we can stop the recursion + //---------------------- + v.Vertex(x123, y123) + return + } + } + } else { + // Collinear case + //------------------ + da := dx*dx + dy*dy + if da == 0 { + d = squareDistance(x1, y1, x2, y2) + } else { + d = ((x2-x1)*dx + (y2-y1)*dy) / da + if d > 0 && d < 1 { + // Simple collinear case, 1---2---3 + // We can leave just two endpoints + return + } + if d <= 0 { + d = squareDistance(x2, y2, x1, y1) + } else if d >= 1 { + d = squareDistance(x2, y2, x3, y3) + } else { + d = squareDistance(x2, y2, x1+d*dx, y1+d*dy) + } + } + if d < distanceToleranceSquare { + v.Vertex(x2, y2) + return + } + } + + // Continue subdivision + //---------------------- + recursiveQuadraticBezierBezier(v, x1, y1, x12, y12, x123, y123, level+1, distanceToleranceSquare, angleTolerance) + recursiveQuadraticBezierBezier(v, x123, y123, x23, y23, x3, y3, level+1, distanceToleranceSquare, angleTolerance) +} + +/** + * http://www.antigrain.com/research/adaptive_bezier/index.html + */ +func recursiveCubicBezier(v VertexConverter, x1, y1, x2, y2, x3, y3, x4, y4 float64, level int, distanceToleranceSquare, angleTolerance, cuspLimit float64) { + if level > CurveRecursionLimit { + return + } + + // Calculate all the mid-points of the line segments + //---------------------- + x12 := (x1 + x2) / 2 + y12 := (y1 + y2) / 2 + x23 := (x2 + x3) / 2 + y23 := (y2 + y3) / 2 + x34 := (x3 + x4) / 2 + y34 := (y3 + y4) / 2 + x123 := (x12 + x23) / 2 + y123 := (y12 + y23) / 2 + x234 := (x23 + x34) / 2 + y234 := (y23 + y34) / 2 + x1234 := (x123 + x234) / 2 + y1234 := (y123 + y234) / 2 + + // Try to approximate the full cubic curve by a single straight line + //------------------ + dx := x4 - x1 + dy := y4 - y1 + + d2 := math.Abs(((x2-x4)*dy - (y2-y4)*dx)) + d3 := math.Abs(((x3-x4)*dy - (y3-y4)*dx)) + + switch { + case d2 <= CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // All collinear OR p1==p4 + //---------------------- + k := dx*dx + dy*dy + if k == 0 { + d2 = squareDistance(x1, y1, x2, y2) + d3 = squareDistance(x4, y4, x3, y3) + } else { + k = 1 / k + da1 := x2 - x1 + da2 := y2 - y1 + d2 = k * (da1*dx + da2*dy) + da1 = x3 - x1 + da2 = y3 - y1 + d3 = k * (da1*dx + da2*dy) + if d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1 { + // Simple collinear case, 1---2---3---4 + // We can leave just two endpoints + return + } + if d2 <= 0 { + d2 = squareDistance(x2, y2, x1, y1) + } else if d2 >= 1 { + d2 = squareDistance(x2, y2, x4, y4) + } else { + d2 = squareDistance(x2, y2, x1+d2*dx, y1+d2*dy) + } + + if d3 <= 0 { + d3 = squareDistance(x3, y3, x1, y1) + } else if d3 >= 1 { + d3 = squareDistance(x3, y3, x4, y4) + } else { + d3 = squareDistance(x3, y3, x1+d3*dx, y1+d3*dy) + } + } + if d2 > d3 { + if d2 < distanceToleranceSquare { + v.Vertex(x2, y2) + return + } + } else { + if d3 < distanceToleranceSquare { + v.Vertex(x3, y3) + return + } + } + break + + case d2 <= CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // p1,p2,p4 are collinear, p3 is significant + //---------------------- + if d3*d3 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + v.Vertex(x23, y23) + return + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(y4-y3, x4-x3) - math.Atan2(y3-y2, x3-x2)) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + v.Vertex(x2, y2) + v.Vertex(x3, y3) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + v.Vertex(x3, y3) + return + } + } + } + break + + case d2 > CurveCollinearityEpsilon && d3 <= CurveCollinearityEpsilon: + // p1,p3,p4 are collinear, p2 is significant + //---------------------- + if d2*d2 <= distanceToleranceSquare*(dx*dx+dy*dy) { + if angleTolerance < CurveAngleToleranceEpsilon { + v.Vertex(x23, y23) + return + } + + // Angle Condition + //---------------------- + da1 := math.Abs(math.Atan2(y3-y2, x3-x2) - math.Atan2(y2-y1, x2-x1)) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + + if da1 < angleTolerance { + v.Vertex(x2, y2) + v.Vertex(x3, y3) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + v.Vertex(x2, y2) + return + } + } + } + break + + case d2 > CurveCollinearityEpsilon && d3 > CurveCollinearityEpsilon: + // Regular case + //----------------- + if (d2+d3)*(d2+d3) <= distanceToleranceSquare*(dx*dx+dy*dy) { + // If the curvature doesn't exceed the distanceTolerance value + // we tend to finish subdivisions. + //---------------------- + if angleTolerance < CurveAngleToleranceEpsilon { + v.Vertex(x23, y23) + return + } + + // Angle & Cusp Condition + //---------------------- + k := math.Atan2(y3-y2, x3-x2) + da1 := math.Abs(k - math.Atan2(y2-y1, x2-x1)) + da2 := math.Abs(math.Atan2(y4-y3, x4-x3) - k) + if da1 >= math.Pi { + da1 = 2*math.Pi - da1 + } + if da2 >= math.Pi { + da2 = 2*math.Pi - da2 + } + + if da1+da2 < angleTolerance { + // Finally we can stop the recursion + //---------------------- + v.Vertex(x23, y23) + return + } + + if cuspLimit != 0.0 { + if da1 > cuspLimit { + v.Vertex(x2, y2) + return + } + + if da2 > cuspLimit { + v.Vertex(x3, y3) + return + } + } + } + break + } + + // Continue subdivision + //---------------------- + recursiveCubicBezier(v, x1, y1, x12, y12, x123, y123, x1234, y1234, level+1, distanceToleranceSquare, angleTolerance, cuspLimit) + recursiveCubicBezier(v, x1234, y1234, x234, y234, x34, y34, x4, y4, level+1, distanceToleranceSquare, angleTolerance, cuspLimit) + +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/dasher.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/dasher.go new file mode 100644 index 000000000..521029992 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/dasher.go @@ -0,0 +1,90 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +type DashVertexConverter struct { + command VertexCommand + next VertexConverter + x, y, distance float64 + dash []float64 + currentDash int + dashOffset float64 +} + +func NewDashConverter(dash []float64, dashOffset float64, converter VertexConverter) *DashVertexConverter { + var dasher DashVertexConverter + dasher.dash = dash + dasher.currentDash = 0 + dasher.dashOffset = dashOffset + dasher.next = converter + return &dasher +} + +func (dasher *DashVertexConverter) NextCommand(cmd VertexCommand) { + dasher.command = cmd + if dasher.command == VertexStopCommand { + dasher.next.NextCommand(VertexStopCommand) + } +} + +func (dasher *DashVertexConverter) Vertex(x, y float64) { + switch dasher.command { + case VertexStartCommand: + dasher.start(x, y) + default: + dasher.lineTo(x, y) + } + dasher.command = VertexNoCommand +} + +func (dasher *DashVertexConverter) start(x, y float64) { + dasher.next.NextCommand(VertexStartCommand) + dasher.next.Vertex(x, y) + dasher.x, dasher.y = x, y + dasher.distance = dasher.dashOffset + dasher.currentDash = 0 +} + +func (dasher *DashVertexConverter) lineTo(x, y float64) { + rest := dasher.dash[dasher.currentDash] - dasher.distance + for rest < 0 { + dasher.distance = dasher.distance - dasher.dash[dasher.currentDash] + dasher.currentDash = (dasher.currentDash + 1) % len(dasher.dash) + rest = dasher.dash[dasher.currentDash] - dasher.distance + } + d := distance(dasher.x, dasher.y, x, y) + for d >= rest { + k := rest / d + lx := dasher.x + k*(x-dasher.x) + ly := dasher.y + k*(y-dasher.y) + if dasher.currentDash%2 == 0 { + // line + dasher.next.Vertex(lx, ly) + } else { + // gap + dasher.next.NextCommand(VertexStopCommand) + dasher.next.NextCommand(VertexStartCommand) + dasher.next.Vertex(lx, ly) + } + d = d - rest + dasher.x, dasher.y = lx, ly + dasher.currentDash = (dasher.currentDash + 1) % len(dasher.dash) + rest = dasher.dash[dasher.currentDash] + } + dasher.distance = d + if dasher.currentDash%2 == 0 { + // line + dasher.next.Vertex(x, y) + } else { + // gap + dasher.next.NextCommand(VertexStopCommand) + dasher.next.NextCommand(VertexStartCommand) + dasher.next.Vertex(x, y) + } + if dasher.distance >= dasher.dash[dasher.currentDash] { + dasher.distance = dasher.distance - dasher.dash[dasher.currentDash] + dasher.currentDash = (dasher.currentDash + 1) % len(dasher.dash) + } + dasher.x, dasher.y = x, y +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/demux_converter.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/demux_converter.go new file mode 100644 index 000000000..b5c871d2c --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/demux_converter.go @@ -0,0 +1,23 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +type DemuxConverter struct { + converters []VertexConverter +} + +func NewDemuxConverter(converters ...VertexConverter) *DemuxConverter { + return &DemuxConverter{converters} +} + +func (dc *DemuxConverter) NextCommand(cmd VertexCommand) { + for _, converter := range dc.converters { + converter.NextCommand(cmd) + } +} +func (dc *DemuxConverter) Vertex(x, y float64) { + for _, converter := range dc.converters { + converter.Vertex(x, y) + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/doc.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/doc.go new file mode 100644 index 000000000..3baeffb4d --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/doc.go @@ -0,0 +1,5 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +// The package draw2d provide a Graphic Context that can draw vectorial figure on surface. +package draw2d diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/font.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/font.go new file mode 100644 index 000000000..eb0b5325c --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/font.go @@ -0,0 +1,97 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/truetype" + "io/ioutil" + "log" + "path" +) + +var ( + fontFolder = "../resource/font/" + fonts = make(map[string]*truetype.Font) +) + +type FontStyle byte + +const ( + FontStyleNormal FontStyle = iota + FontStyleBold + FontStyleItalic +) + +type FontFamily byte + +const ( + FontFamilySans FontFamily = iota + FontFamilySerif + FontFamilyMono +) + +type FontData struct { + Name string + Family FontFamily + Style FontStyle +} + +func fontFileName(fontData FontData) string { + fontFileName := fontData.Name + switch fontData.Family { + case FontFamilySans: + fontFileName += "s" + case FontFamilySerif: + fontFileName += "r" + case FontFamilyMono: + fontFileName += "m" + } + if fontData.Style&FontStyleBold != 0 { + fontFileName += "b" + } else { + fontFileName += "r" + } + + if fontData.Style&FontStyleItalic != 0 { + fontFileName += "i" + } + fontFileName += ".ttf" + return fontFileName +} + +func RegisterFont(fontData FontData, font *truetype.Font) { + fonts[fontFileName(fontData)] = font +} + +func GetFont(fontData FontData) *truetype.Font { + fontFileName := fontFileName(fontData) + font := fonts[fontFileName] + if font != nil { + return font + } + fonts[fontFileName] = loadFont(fontFileName) + return fonts[fontFileName] +} + +func GetFontFolder() string { + return fontFolder +} + +func SetFontFolder(folder string) { + fontFolder = folder +} + +func loadFont(fontFileName string) *truetype.Font { + fontBytes, err := ioutil.ReadFile(path.Join(fontFolder, fontFileName)) + if err != nil { + log.Println(err) + return nil + } + font, err := truetype.Parse(fontBytes) + if err != nil { + log.Println(err) + return nil + } + return font +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/gc.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/gc.go new file mode 100644 index 000000000..66dc5088f --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/gc.go @@ -0,0 +1,55 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "image" + "image/color" +) + +type FillRule int + +const ( + FillRuleEvenOdd FillRule = iota + FillRuleWinding +) + +type GraphicContext interface { + Path + // Create a new path + BeginPath() + GetMatrixTransform() MatrixTransform + SetMatrixTransform(tr MatrixTransform) + ComposeMatrixTransform(tr MatrixTransform) + Rotate(angle float64) + Translate(tx, ty float64) + Scale(sx, sy float64) + SetStrokeColor(c color.Color) + SetFillColor(c color.Color) + SetFillRule(f FillRule) + SetLineWidth(lineWidth float64) + SetLineCap(cap Cap) + SetLineJoin(join Join) + SetLineDash(dash []float64, dashOffset float64) + SetFontSize(fontSize float64) + GetFontSize() float64 + SetFontData(fontData FontData) + GetFontData() FontData + DrawImage(image image.Image) + Save() + Restore() + Clear() + ClearRect(x1, y1, x2, y2 int) + SetDPI(dpi int) + GetDPI() int + GetStringBounds(s string) (left, top, right, bottom float64) + CreateStringPath(text string, x, y float64) (cursor float64) + FillString(text string) (cursor float64) + FillStringAt(text string, x, y float64) (cursor float64) + StrokeString(text string) (cursor float64) + StrokeStringAt(text string, x, y float64) (cursor float64) + Stroke(paths ...*PathStorage) + Fill(paths ...*PathStorage) + FillStroke(paths ...*PathStorage) +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/image.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/image.go new file mode 100644 index 000000000..9f91bc71f --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/image.go @@ -0,0 +1,359 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/raster" + "code.google.com/p/freetype-go/freetype/truetype" + "errors" + "image" + "image/color" + "image/draw" + "log" + "math" +) + +type Painter interface { + raster.Painter + SetColor(color color.Color) +} + +var ( + defaultFontData = FontData{"luxi", FontFamilySans, FontStyleNormal} +) + +type ImageGraphicContext struct { + *StackGraphicContext + img draw.Image + painter Painter + fillRasterizer *raster.Rasterizer + strokeRasterizer *raster.Rasterizer + glyphBuf *truetype.GlyphBuf + DPI int +} + +/** + * Create a new Graphic context from an image + */ +func NewGraphicContext(img draw.Image) *ImageGraphicContext { + var painter Painter + switch selectImage := img.(type) { + case *image.RGBA: + painter = raster.NewRGBAPainter(selectImage) + default: + panic("Image type not supported") + } + return NewGraphicContextWithPainter(img, painter) +} + +// Create a new Graphic context from an image and a Painter (see Freetype-go) +func NewGraphicContextWithPainter(img draw.Image, painter Painter) *ImageGraphicContext { + width, height := img.Bounds().Dx(), img.Bounds().Dy() + dpi := 92 + gc := &ImageGraphicContext{ + NewStackGraphicContext(), + img, + painter, + raster.NewRasterizer(width, height), + raster.NewRasterizer(width, height), + truetype.NewGlyphBuf(), + dpi, + } + return gc +} + +func (gc *ImageGraphicContext) GetDPI() int { + return gc.DPI +} + +func (gc *ImageGraphicContext) Clear() { + width, height := gc.img.Bounds().Dx(), gc.img.Bounds().Dy() + gc.ClearRect(0, 0, width, height) +} + +func (gc *ImageGraphicContext) ClearRect(x1, y1, x2, y2 int) { + imageColor := image.NewUniform(gc.Current.FillColor) + draw.Draw(gc.img, image.Rect(x1, y1, x2, y2), imageColor, image.ZP, draw.Over) +} + +func (gc *ImageGraphicContext) DrawImage(img image.Image) { + DrawImage(img, gc.img, gc.Current.Tr, draw.Over, BilinearFilter) +} + +func (gc *ImageGraphicContext) FillString(text string) (cursor float64) { + return gc.FillStringAt(text, 0, 0) +} + +func (gc *ImageGraphicContext) FillStringAt(text string, x, y float64) (cursor float64) { + width := gc.CreateStringPath(text, x, y) + gc.Fill() + return width +} + +func (gc *ImageGraphicContext) StrokeString(text string) (cursor float64) { + return gc.StrokeStringAt(text, 0, 0) +} + +func (gc *ImageGraphicContext) StrokeStringAt(text string, x, y float64) (cursor float64) { + width := gc.CreateStringPath(text, x, y) + gc.Stroke() + return width +} + +func (gc *ImageGraphicContext) loadCurrentFont() (*truetype.Font, error) { + font := GetFont(gc.Current.FontData) + if font == nil { + font = GetFont(defaultFontData) + } + if font == nil { + return nil, errors.New("No font set, and no default font available.") + } + gc.SetFont(font) + gc.SetFontSize(gc.Current.FontSize) + return font, nil +} + +func fUnitsToFloat64(x int32) float64 { + scaled := x << 2 + return float64(scaled/256) + float64(scaled%256)/256.0 +} + +// p is a truetype.Point measured in FUnits and positive Y going upwards. +// The returned value is the same thing measured in floating point and positive Y +// going downwards. +func pointToF64Point(p truetype.Point) (x, y float64) { + return fUnitsToFloat64(p.X), -fUnitsToFloat64(p.Y) +} + +// drawContour draws the given closed contour at the given sub-pixel offset. +func (gc *ImageGraphicContext) drawContour(ps []truetype.Point, dx, dy float64) { + if len(ps) == 0 { + return + } + startX, startY := pointToF64Point(ps[0]) + gc.MoveTo(startX+dx, startY+dy) + q0X, q0Y, on0 := startX, startY, true + for _, p := range ps[1:] { + qX, qY := pointToF64Point(p) + on := p.Flags&0x01 != 0 + if on { + if on0 { + gc.LineTo(qX+dx, qY+dy) + } else { + gc.QuadCurveTo(q0X+dx, q0Y+dy, qX+dx, qY+dy) + } + } else { + if on0 { + // No-op. + } else { + midX := (q0X + qX) / 2 + midY := (q0Y + qY) / 2 + gc.QuadCurveTo(q0X+dx, q0Y+dy, midX+dx, midY+dy) + } + } + q0X, q0Y, on0 = qX, qY, on + } + // Close the curve. + if on0 { + gc.LineTo(startX+dx, startY+dy) + } else { + gc.QuadCurveTo(q0X+dx, q0Y+dy, startX+dx, startY+dy) + } +} + +func (gc *ImageGraphicContext) drawGlyph(glyph truetype.Index, dx, dy float64) error { + if err := gc.glyphBuf.Load(gc.Current.font, gc.Current.scale, glyph, truetype.NoHinting); err != nil { + return err + } + e0 := 0 + for _, e1 := range gc.glyphBuf.End { + gc.drawContour(gc.glyphBuf.Point[e0:e1], dx, dy) + e0 = e1 + } + return nil +} + +// CreateStringPath creates a path from the string s at x, y, and returns the string width. +// The text is placed so that the left edge of the em square of the first character of s +// and the baseline intersect at x, y. The majority of the affected pixels will be +// above and to the right of the point, but some may be below or to the left. +// For example, drawing a string that starts with a 'J' in an italic font may +// affect pixels below and left of the point. +func (gc *ImageGraphicContext) CreateStringPath(s string, x, y float64) float64 { + font, err := gc.loadCurrentFont() + if err != nil { + log.Println(err) + return 0.0 + } + startx := x + prev, hasPrev := truetype.Index(0), false + for _, rune := range s { + index := font.Index(rune) + if hasPrev { + x += fUnitsToFloat64(font.Kerning(gc.Current.scale, prev, index)) + } + err := gc.drawGlyph(index, x, y) + if err != nil { + log.Println(err) + return startx - x + } + x += fUnitsToFloat64(font.HMetric(gc.Current.scale, index).AdvanceWidth) + prev, hasPrev = index, true + } + return x - startx +} + +// GetStringBounds returns the approximate pixel bounds of the string s at x, y. +// The the left edge of the em square of the first character of s +// and the baseline intersect at 0, 0 in the returned coordinates. +// Therefore the top and left coordinates may well be negative. +func (gc *ImageGraphicContext) GetStringBounds(s string) (left, top, right, bottom float64) { + font, err := gc.loadCurrentFont() + if err != nil { + log.Println(err) + return 0, 0, 0, 0 + } + top, left, bottom, right = 10e6, 10e6, -10e6, -10e6 + cursor := 0.0 + prev, hasPrev := truetype.Index(0), false + for _, rune := range s { + index := font.Index(rune) + if hasPrev { + cursor += fUnitsToFloat64(font.Kerning(gc.Current.scale, prev, index)) + } + if err := gc.glyphBuf.Load(gc.Current.font, gc.Current.scale, index, truetype.NoHinting); err != nil { + log.Println(err) + return 0, 0, 0, 0 + } + e0 := 0 + for _, e1 := range gc.glyphBuf.End { + ps := gc.glyphBuf.Point[e0:e1] + for _, p := range ps { + x, y := pointToF64Point(p) + top = math.Min(top, y) + bottom = math.Max(bottom, y) + left = math.Min(left, x+cursor) + right = math.Max(right, x+cursor) + } + } + cursor += fUnitsToFloat64(font.HMetric(gc.Current.scale, index).AdvanceWidth) + prev, hasPrev = index, true + } + return left, top, right, bottom +} + +// recalc recalculates scale and bounds values from the font size, screen +// resolution and font metrics, and invalidates the glyph cache. +func (gc *ImageGraphicContext) recalc() { + gc.Current.scale = int32(gc.Current.FontSize * float64(gc.DPI) * (64.0 / 72.0)) +} + +// SetDPI sets the screen resolution in dots per inch. +func (gc *ImageGraphicContext) SetDPI(dpi int) { + gc.DPI = dpi + gc.recalc() +} + +// SetFont sets the font used to draw text. +func (gc *ImageGraphicContext) SetFont(font *truetype.Font) { + gc.Current.font = font +} + +// SetFontSize sets the font size in points (as in ``a 12 point font''). +func (gc *ImageGraphicContext) SetFontSize(fontSize float64) { + gc.Current.FontSize = fontSize + gc.recalc() +} + +func (gc *ImageGraphicContext) paint(rasterizer *raster.Rasterizer, color color.Color) { + gc.painter.SetColor(color) + rasterizer.Rasterize(gc.painter) + rasterizer.Clear() + gc.Current.Path.Clear() +} + +/**** second method ****/ +func (gc *ImageGraphicContext) Stroke(paths ...*PathStorage) { + paths = append(paths, gc.Current.Path) + gc.strokeRasterizer.UseNonZeroWinding = true + + stroker := NewLineStroker(gc.Current.Cap, gc.Current.Join, NewVertexMatrixTransform(gc.Current.Tr, NewVertexAdder(gc.strokeRasterizer))) + stroker.HalfLineWidth = gc.Current.LineWidth / 2 + var pathConverter *PathConverter + if gc.Current.Dash != nil && len(gc.Current.Dash) > 0 { + dasher := NewDashConverter(gc.Current.Dash, gc.Current.DashOffset, stroker) + pathConverter = NewPathConverter(dasher) + } else { + pathConverter = NewPathConverter(stroker) + } + pathConverter.ApproximationScale = gc.Current.Tr.GetScale() + pathConverter.Convert(paths...) + + gc.paint(gc.strokeRasterizer, gc.Current.StrokeColor) +} + +/**** second method ****/ +func (gc *ImageGraphicContext) Fill(paths ...*PathStorage) { + paths = append(paths, gc.Current.Path) + gc.fillRasterizer.UseNonZeroWinding = gc.Current.FillRule.UseNonZeroWinding() + + /**** first method ****/ + pathConverter := NewPathConverter(NewVertexMatrixTransform(gc.Current.Tr, NewVertexAdder(gc.fillRasterizer))) + pathConverter.ApproximationScale = gc.Current.Tr.GetScale() + pathConverter.Convert(paths...) + + gc.paint(gc.fillRasterizer, gc.Current.FillColor) +} + +/* second method */ +func (gc *ImageGraphicContext) FillStroke(paths ...*PathStorage) { + gc.fillRasterizer.UseNonZeroWinding = gc.Current.FillRule.UseNonZeroWinding() + gc.strokeRasterizer.UseNonZeroWinding = true + + filler := NewVertexMatrixTransform(gc.Current.Tr, NewVertexAdder(gc.fillRasterizer)) + + stroker := NewLineStroker(gc.Current.Cap, gc.Current.Join, NewVertexMatrixTransform(gc.Current.Tr, NewVertexAdder(gc.strokeRasterizer))) + stroker.HalfLineWidth = gc.Current.LineWidth / 2 + + demux := NewDemuxConverter(filler, stroker) + paths = append(paths, gc.Current.Path) + pathConverter := NewPathConverter(demux) + pathConverter.ApproximationScale = gc.Current.Tr.GetScale() + pathConverter.Convert(paths...) + + gc.paint(gc.fillRasterizer, gc.Current.FillColor) + gc.paint(gc.strokeRasterizer, gc.Current.StrokeColor) +} + +func (f FillRule) UseNonZeroWinding() bool { + switch f { + case FillRuleEvenOdd: + return false + case FillRuleWinding: + return true + } + return false +} + +func (c Cap) Convert() raster.Capper { + switch c { + case RoundCap: + return raster.RoundCapper + case ButtCap: + return raster.ButtCapper + case SquareCap: + return raster.SquareCapper + } + return raster.RoundCapper +} + +func (j Join) Convert() raster.Joiner { + switch j { + case RoundJoin: + return raster.RoundJoiner + case BevelJoin: + return raster.BevelJoiner + } + return raster.RoundJoiner +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/math.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/math.go new file mode 100644 index 000000000..c4bb761df --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/math.go @@ -0,0 +1,52 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "math" +) + +func distance(x1, y1, x2, y2 float64) float64 { + dx := x2 - x1 + dy := y2 - y1 + return float64(math.Sqrt(dx*dx + dy*dy)) +} + +func vectorDistance(dx, dy float64) float64 { + return float64(math.Sqrt(dx*dx + dy*dy)) +} + +func squareDistance(x1, y1, x2, y2 float64) float64 { + dx := x2 - x1 + dy := y2 - y1 + return dx*dx + dy*dy +} + +func min(x, y float64) float64 { + if x < y { + return x + } + return y +} + +func max(x, y float64) float64 { + if x > y { + return x + } + return y +} + +func minMax(x, y float64) (min, max float64) { + if x > y { + return y, x + } + return x, y +} + +func minUint32(a, b uint32) uint32 { + if a < b { + return a + } + return b +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/paint.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/paint.go new file mode 100644 index 000000000..885d993ae --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/paint.go @@ -0,0 +1,92 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +/* +import ( + "image/draw" + "image" + "freetype-go.googlecode.com/hg/freetype/raster" +)*/ + +const M = 1<<16 - 1 + +/* +type NRGBAPainter struct { + // The image to compose onto. + Image *image.NRGBA + // The Porter-Duff composition operator. + Op draw.Op + // The 16-bit color to paint the spans. + cr, cg, cb, ca uint32 +} + +// Paint satisfies the Painter interface by painting ss onto an image.RGBA. +func (r *NRGBAPainter) Paint(ss []raster.Span, done bool) { + b := r.Image.Bounds() + for _, s := range ss { + if s.Y < b.Min.Y { + continue + } + if s.Y >= b.Max.Y { + return + } + if s.X0 < b.Min.X { + s.X0 = b.Min.X + } + if s.X1 > b.Max.X { + s.X1 = b.Max.X + } + if s.X0 >= s.X1 { + continue + } + base := s.Y * r.Image.Stride + p := r.Image.Pix[base+s.X0 : base+s.X1] + // This code is duplicated from drawGlyphOver in $GOROOT/src/pkg/image/draw/draw.go. + // TODO(nigeltao): Factor out common code into a utility function, once the compiler + // can inline such function calls. + ma := s.A >> 16 + if r.Op == draw.Over { + for i, nrgba := range p { + dr, dg, db, da := nrgba. + a := M - (r.ca*ma)/M + da = (da*a + r.ca*ma) / M + if da != 0 { + dr = minUint32(M, (dr*a+r.cr*ma)/da) + dg = minUint32(M, (dg*a+r.cg*ma)/da) + db = minUint32(M, (db*a+r.cb*ma)/da) + } else { + dr, dg, db = 0, 0, 0 + } + p[i] = image.NRGBAColor{uint8(dr >> 8), uint8(dg >> 8), uint8(db >> 8), uint8(da >> 8)} + } + } else { + for i, nrgba := range p { + dr, dg, db, da := nrgba.RGBA() + a := M - ma + da = (da*a + r.ca*ma) / M + if da != 0 { + dr = minUint32(M, (dr*a+r.cr*ma)/da) + dg = minUint32(M, (dg*a+r.cg*ma)/da) + db = minUint32(M, (db*a+r.cb*ma)/da) + } else { + dr, dg, db = 0, 0, 0 + } + p[i] = image.NRGBAColor{uint8(dr >> 8), uint8(dg >> 8), uint8(db >> 8), uint8(da >> 8)} + } + } + } + +} + +// SetColor sets the color to paint the spans. +func (r *NRGBAPainter) SetColor(c image.Color) { + r.cr, r.cg, r.cb, r.ca = c.RGBA() +} + +// NewRGBAPainter creates a new RGBAPainter for the given image. +func NewNRGBAPainter(m *image.NRGBA) *NRGBAPainter { + return &NRGBAPainter{Image: m} +} +*/ diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path.go new file mode 100644 index 000000000..b82910e24 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path.go @@ -0,0 +1,27 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +type Path interface { + // Return the current point of the path + LastPoint() (x, y float64) + // Create a new subpath that start at the specified point + MoveTo(x, y float64) + // Create a new subpath that start at the specified point + // relative to the current point + RMoveTo(dx, dy float64) + // Add a line to the current subpath + LineTo(x, y float64) + // Add a line to the current subpath + // relative to the current point + RLineTo(dx, dy float64) + + QuadCurveTo(cx, cy, x, y float64) + RQuadCurveTo(dcx, dcy, dx, dy float64) + CubicCurveTo(cx1, cy1, cx2, cy2, x, y float64) + RCubicCurveTo(dcx1, dcy1, dcx2, dcy2, dx, dy float64) + ArcTo(cx, cy, rx, ry, startAngle, angle float64) + RArcTo(dcx, dcy, rx, ry, startAngle, angle float64) + Close() +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_adder.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_adder.go new file mode 100644 index 000000000..c5efd2beb --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_adder.go @@ -0,0 +1,70 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/raster" +) + +type VertexAdder struct { + command VertexCommand + adder raster.Adder +} + +func NewVertexAdder(adder raster.Adder) *VertexAdder { + return &VertexAdder{VertexNoCommand, adder} +} + +func (vertexAdder *VertexAdder) NextCommand(cmd VertexCommand) { + vertexAdder.command = cmd +} + +func (vertexAdder *VertexAdder) Vertex(x, y float64) { + switch vertexAdder.command { + case VertexStartCommand: + vertexAdder.adder.Start(raster.Point{raster.Fix32(x * 256), raster.Fix32(y * 256)}) + default: + vertexAdder.adder.Add1(raster.Point{raster.Fix32(x * 256), raster.Fix32(y * 256)}) + } + vertexAdder.command = VertexNoCommand +} + +type PathAdder struct { + adder raster.Adder + firstPoint raster.Point + ApproximationScale float64 +} + +func NewPathAdder(adder raster.Adder) *PathAdder { + return &PathAdder{adder, raster.Point{0, 0}, 1} +} + +func (pathAdder *PathAdder) Convert(paths ...*PathStorage) { + for _, path := range paths { + j := 0 + for _, cmd := range path.commands { + switch cmd { + case MoveTo: + pathAdder.firstPoint = raster.Point{raster.Fix32(path.vertices[j] * 256), raster.Fix32(path.vertices[j+1] * 256)} + pathAdder.adder.Start(pathAdder.firstPoint) + j += 2 + case LineTo: + pathAdder.adder.Add1(raster.Point{raster.Fix32(path.vertices[j] * 256), raster.Fix32(path.vertices[j+1] * 256)}) + j += 2 + case QuadCurveTo: + pathAdder.adder.Add2(raster.Point{raster.Fix32(path.vertices[j] * 256), raster.Fix32(path.vertices[j+1] * 256)}, raster.Point{raster.Fix32(path.vertices[j+2] * 256), raster.Fix32(path.vertices[j+3] * 256)}) + j += 4 + case CubicCurveTo: + pathAdder.adder.Add3(raster.Point{raster.Fix32(path.vertices[j] * 256), raster.Fix32(path.vertices[j+1] * 256)}, raster.Point{raster.Fix32(path.vertices[j+2] * 256), raster.Fix32(path.vertices[j+3] * 256)}, raster.Point{raster.Fix32(path.vertices[j+4] * 256), raster.Fix32(path.vertices[j+5] * 256)}) + j += 6 + case ArcTo: + lastPoint := arcAdder(pathAdder.adder, path.vertices[j], path.vertices[j+1], path.vertices[j+2], path.vertices[j+3], path.vertices[j+4], path.vertices[j+5], pathAdder.ApproximationScale) + pathAdder.adder.Add1(lastPoint) + j += 6 + case Close: + pathAdder.adder.Add1(pathAdder.firstPoint) + } + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_converter.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_converter.go new file mode 100644 index 000000000..0ef96b84d --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_converter.go @@ -0,0 +1,173 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 06/12/2010 by Laurent Le Goff + +package draw2d + +import ( + "math" +) + +type PathConverter struct { + converter VertexConverter + ApproximationScale, AngleTolerance, CuspLimit float64 + startX, startY, x, y float64 +} + +func NewPathConverter(converter VertexConverter) *PathConverter { + return &PathConverter{converter, 1, 0, 0, 0, 0, 0, 0} +} + +func (c *PathConverter) Convert(paths ...*PathStorage) { + for _, path := range paths { + j := 0 + for _, cmd := range path.commands { + j = j + c.ConvertCommand(cmd, path.vertices[j:]...) + } + c.converter.NextCommand(VertexStopCommand) + } +} + +func (c *PathConverter) ConvertCommand(cmd PathCmd, vertices ...float64) int { + switch cmd { + case MoveTo: + c.x, c.y = vertices[0], vertices[1] + c.startX, c.startY = c.x, c.y + c.converter.NextCommand(VertexStopCommand) + c.converter.NextCommand(VertexStartCommand) + c.converter.Vertex(c.x, c.y) + return 2 + case LineTo: + c.x, c.y = vertices[0], vertices[1] + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + c.converter.NextCommand(VertexJoinCommand) + return 2 + case QuadCurveTo: + quadraticBezier(c.converter, c.x, c.y, vertices[0], vertices[1], vertices[2], vertices[3], c.ApproximationScale, c.AngleTolerance) + c.x, c.y = vertices[2], vertices[3] + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return 4 + case CubicCurveTo: + cubicBezier(c.converter, c.x, c.y, vertices[0], vertices[1], vertices[2], vertices[3], vertices[4], vertices[5], c.ApproximationScale, c.AngleTolerance, c.CuspLimit) + c.x, c.y = vertices[4], vertices[5] + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return 6 + case ArcTo: + c.x, c.y = arc(c.converter, vertices[0], vertices[1], vertices[2], vertices[3], vertices[4], vertices[5], c.ApproximationScale) + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return 6 + case Close: + c.converter.NextCommand(VertexCloseCommand) + c.converter.Vertex(c.startX, c.startY) + return 0 + } + return 0 +} + +func (c *PathConverter) MoveTo(x, y float64) *PathConverter { + c.x, c.y = x, y + c.startX, c.startY = c.x, c.y + c.converter.NextCommand(VertexStopCommand) + c.converter.NextCommand(VertexStartCommand) + c.converter.Vertex(c.x, c.y) + return c +} + +func (c *PathConverter) RMoveTo(dx, dy float64) *PathConverter { + c.MoveTo(c.x+dx, c.y+dy) + return c +} + +func (c *PathConverter) LineTo(x, y float64) *PathConverter { + c.x, c.y = x, y + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + c.converter.NextCommand(VertexJoinCommand) + return c +} + +func (c *PathConverter) RLineTo(dx, dy float64) *PathConverter { + c.LineTo(c.x+dx, c.y+dy) + return c +} + +func (c *PathConverter) QuadCurveTo(cx, cy, x, y float64) *PathConverter { + quadraticBezier(c.converter, c.x, c.y, cx, cy, x, y, c.ApproximationScale, c.AngleTolerance) + c.x, c.y = x, y + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return c +} + +func (c *PathConverter) RQuadCurveTo(dcx, dcy, dx, dy float64) *PathConverter { + c.QuadCurveTo(c.x+dcx, c.y+dcy, c.x+dx, c.y+dy) + return c +} + +func (c *PathConverter) CubicCurveTo(cx1, cy1, cx2, cy2, x, y float64) *PathConverter { + cubicBezier(c.converter, c.x, c.y, cx1, cy1, cx2, cy2, x, y, c.ApproximationScale, c.AngleTolerance, c.CuspLimit) + c.x, c.y = x, y + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return c +} + +func (c *PathConverter) RCubicCurveTo(dcx1, dcy1, dcx2, dcy2, dx, dy float64) *PathConverter { + c.CubicCurveTo(c.x+dcx1, c.y+dcy1, c.x+dcx2, c.y+dcy2, c.x+dx, c.y+dy) + return c +} + +func (c *PathConverter) ArcTo(cx, cy, rx, ry, startAngle, angle float64) *PathConverter { + endAngle := startAngle + angle + clockWise := true + if angle < 0 { + clockWise = false + } + // normalize + if clockWise { + for endAngle < startAngle { + endAngle += math.Pi * 2.0 + } + } else { + for startAngle < endAngle { + startAngle += math.Pi * 2.0 + } + } + startX := cx + math.Cos(startAngle)*rx + startY := cy + math.Sin(startAngle)*ry + c.MoveTo(startX, startY) + c.x, c.y = arc(c.converter, cx, cy, rx, ry, startAngle, angle, c.ApproximationScale) + if c.startX == c.x && c.startY == c.y { + c.converter.NextCommand(VertexCloseCommand) + } + c.converter.Vertex(c.x, c.y) + return c +} + +func (c *PathConverter) RArcTo(dcx, dcy, rx, ry, startAngle, angle float64) *PathConverter { + c.ArcTo(c.x+dcx, c.y+dcy, rx, ry, startAngle, angle) + return c +} + +func (c *PathConverter) Close() *PathConverter { + c.converter.NextCommand(VertexCloseCommand) + c.converter.Vertex(c.startX, c.startY) + return c +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_storage.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_storage.go new file mode 100644 index 000000000..c2a887037 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/path_storage.go @@ -0,0 +1,190 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "fmt" + "math" +) + +type PathCmd int + +const ( + MoveTo PathCmd = iota + LineTo + QuadCurveTo + CubicCurveTo + ArcTo + Close +) + +type PathStorage struct { + commands []PathCmd + vertices []float64 + x, y float64 +} + +func NewPathStorage() (p *PathStorage) { + p = new(PathStorage) + p.commands = make([]PathCmd, 0, 256) + p.vertices = make([]float64, 0, 256) + return +} + +func (p *PathStorage) Clear() { + p.commands = p.commands[0:0] + p.vertices = p.vertices[0:0] + return +} + +func (p *PathStorage) appendToPath(cmd PathCmd, vertices ...float64) { + if cap(p.vertices) <= len(p.vertices)+6 { + a := make([]PathCmd, len(p.commands), cap(p.commands)+256) + b := make([]float64, len(p.vertices), cap(p.vertices)+256) + copy(a, p.commands) + p.commands = a + copy(b, p.vertices) + p.vertices = b + } + p.commands = p.commands[0 : len(p.commands)+1] + p.commands[len(p.commands)-1] = cmd + copy(p.vertices[len(p.vertices):len(p.vertices)+len(vertices)], vertices) + p.vertices = p.vertices[0 : len(p.vertices)+len(vertices)] +} + +func (src *PathStorage) Copy() (dest *PathStorage) { + dest = new(PathStorage) + dest.commands = make([]PathCmd, len(src.commands)) + copy(dest.commands, src.commands) + dest.vertices = make([]float64, len(src.vertices)) + copy(dest.vertices, src.vertices) + return dest +} + +func (p *PathStorage) LastPoint() (x, y float64) { + return p.x, p.y +} + +func (p *PathStorage) IsEmpty() bool { + return len(p.commands) == 0 +} + +func (p *PathStorage) Close() *PathStorage { + p.appendToPath(Close) + return p +} + +func (p *PathStorage) MoveTo(x, y float64) *PathStorage { + p.appendToPath(MoveTo, x, y) + p.x = x + p.y = y + return p +} + +func (p *PathStorage) RMoveTo(dx, dy float64) *PathStorage { + x, y := p.LastPoint() + p.MoveTo(x+dx, y+dy) + return p +} + +func (p *PathStorage) LineTo(x, y float64) *PathStorage { + p.appendToPath(LineTo, x, y) + p.x = x + p.y = y + return p +} + +func (p *PathStorage) RLineTo(dx, dy float64) *PathStorage { + x, y := p.LastPoint() + p.LineTo(x+dx, y+dy) + return p +} + +func (p *PathStorage) QuadCurveTo(cx, cy, x, y float64) *PathStorage { + p.appendToPath(QuadCurveTo, cx, cy, x, y) + p.x = x + p.y = y + return p +} + +func (p *PathStorage) RQuadCurveTo(dcx, dcy, dx, dy float64) *PathStorage { + x, y := p.LastPoint() + p.QuadCurveTo(x+dcx, y+dcy, x+dx, y+dy) + return p +} + +func (p *PathStorage) CubicCurveTo(cx1, cy1, cx2, cy2, x, y float64) *PathStorage { + p.appendToPath(CubicCurveTo, cx1, cy1, cx2, cy2, x, y) + p.x = x + p.y = y + return p +} + +func (p *PathStorage) RCubicCurveTo(dcx1, dcy1, dcx2, dcy2, dx, dy float64) *PathStorage { + x, y := p.LastPoint() + p.CubicCurveTo(x+dcx1, y+dcy1, x+dcx2, y+dcy2, x+dx, y+dy) + return p +} + +func (p *PathStorage) ArcTo(cx, cy, rx, ry, startAngle, angle float64) *PathStorage { + endAngle := startAngle + angle + clockWise := true + if angle < 0 { + clockWise = false + } + // normalize + if clockWise { + for endAngle < startAngle { + endAngle += math.Pi * 2.0 + } + } else { + for startAngle < endAngle { + startAngle += math.Pi * 2.0 + } + } + startX := cx + math.Cos(startAngle)*rx + startY := cy + math.Sin(startAngle)*ry + if len(p.commands) > 0 { + p.LineTo(startX, startY) + } else { + p.MoveTo(startX, startY) + } + p.appendToPath(ArcTo, cx, cy, rx, ry, startAngle, angle) + p.x = cx + math.Cos(endAngle)*rx + p.y = cy + math.Sin(endAngle)*ry + return p +} + +func (p *PathStorage) RArcTo(dcx, dcy, rx, ry, startAngle, angle float64) *PathStorage { + x, y := p.LastPoint() + p.ArcTo(x+dcx, y+dcy, rx, ry, startAngle, angle) + return p +} + +func (p *PathStorage) String() string { + s := "" + j := 0 + for _, cmd := range p.commands { + switch cmd { + case MoveTo: + s += fmt.Sprintf("MoveTo: %f, %f\n", p.vertices[j], p.vertices[j+1]) + j = j + 2 + case LineTo: + s += fmt.Sprintf("LineTo: %f, %f\n", p.vertices[j], p.vertices[j+1]) + j = j + 2 + case QuadCurveTo: + s += fmt.Sprintf("QuadCurveTo: %f, %f, %f, %f\n", p.vertices[j], p.vertices[j+1], p.vertices[j+2], p.vertices[j+3]) + j = j + 4 + case CubicCurveTo: + s += fmt.Sprintf("CubicCurveTo: %f, %f, %f, %f, %f, %f\n", p.vertices[j], p.vertices[j+1], p.vertices[j+2], p.vertices[j+3], p.vertices[j+4], p.vertices[j+5]) + j = j + 6 + case ArcTo: + s += fmt.Sprintf("ArcTo: %f, %f, %f, %f, %f, %f\n", p.vertices[j], p.vertices[j+1], p.vertices[j+2], p.vertices[j+3], p.vertices[j+4], p.vertices[j+5]) + j = j + 6 + case Close: + s += "Close\n" + } + } + return s +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/coverage_table.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/coverage_table.go new file mode 100644 index 000000000..429836f39 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/coverage_table.go @@ -0,0 +1,203 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +var SUBPIXEL_OFFSETS_SAMPLE_8 = [8]float64{ + 5.0 / 8, + 0.0 / 8, + 3.0 / 8, + 6.0 / 8, + 1.0 / 8, + 4.0 / 8, + 7.0 / 8, + 2.0 / 8, +} + +var SUBPIXEL_OFFSETS_SAMPLE_8_FIXED = [8]Fix{ + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[0] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[1] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[2] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[3] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[4] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[5] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[6] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_8[7] * FIXED_FLOAT_COEF), +} + +var SUBPIXEL_OFFSETS_SAMPLE_16 = [16]float64{ + 1.0 / 16, + 8.0 / 16, + 4.0 / 16, + 15.0 / 16, + 11.0 / 16, + 2.0 / 16, + 6.0 / 16, + 14.0 / 16, + 10.0 / 16, + 3.0 / 16, + 7.0 / 16, + 12.0 / 16, + 0.0 / 16, + 9.0 / 16, + 5.0 / 16, + 13.0 / 16, +} + +var SUBPIXEL_OFFSETS_SAMPLE_16_FIXED = [16]Fix{ + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[0] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[1] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[2] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[3] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[4] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[5] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[6] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[7] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[8] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[9] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[10] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[11] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[12] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[13] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[14] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_16[15] * FIXED_FLOAT_COEF), +} + +var SUBPIXEL_OFFSETS_SAMPLE_32 = [32]float64{ + 28.0 / 32, + 13.0 / 32, + 6.0 / 32, + 23.0 / 32, + 0.0 / 32, + 17.0 / 32, + 10.0 / 32, + 27.0 / 32, + 4.0 / 32, + 21.0 / 32, + 14.0 / 32, + 31.0 / 32, + 8.0 / 32, + 25.0 / 32, + 18.0 / 32, + 3.0 / 32, + 12.0 / 32, + 29.0 / 32, + 22.0 / 32, + 7.0 / 32, + 16.0 / 32, + 1.0 / 32, + 26.0 / 32, + 11.0 / 32, + 20.0 / 32, + 5.0 / 32, + 30.0 / 32, + 15.0 / 32, + 24.0 / 32, + 9.0 / 32, + 2.0 / 32, + 19.0 / 32, +} +var SUBPIXEL_OFFSETS_SAMPLE_32_FIXED = [32]Fix{ + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[0] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[1] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[2] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[3] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[4] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[5] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[6] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[7] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[8] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[9] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[10] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[11] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[12] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[13] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[14] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[15] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[16] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[17] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[18] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[19] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[20] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[21] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[22] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[23] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[24] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[25] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[26] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[27] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[28] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[29] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[30] * FIXED_FLOAT_COEF), + Fix(SUBPIXEL_OFFSETS_SAMPLE_32[31] * FIXED_FLOAT_COEF), +} + +var coverageTable = [256]uint8{ + pixelCoverage(0x00), pixelCoverage(0x01), pixelCoverage(0x02), pixelCoverage(0x03), + pixelCoverage(0x04), pixelCoverage(0x05), pixelCoverage(0x06), pixelCoverage(0x07), + pixelCoverage(0x08), pixelCoverage(0x09), pixelCoverage(0x0a), pixelCoverage(0x0b), + pixelCoverage(0x0c), pixelCoverage(0x0d), pixelCoverage(0x0e), pixelCoverage(0x0f), + pixelCoverage(0x10), pixelCoverage(0x11), pixelCoverage(0x12), pixelCoverage(0x13), + pixelCoverage(0x14), pixelCoverage(0x15), pixelCoverage(0x16), pixelCoverage(0x17), + pixelCoverage(0x18), pixelCoverage(0x19), pixelCoverage(0x1a), pixelCoverage(0x1b), + pixelCoverage(0x1c), pixelCoverage(0x1d), pixelCoverage(0x1e), pixelCoverage(0x1f), + pixelCoverage(0x20), pixelCoverage(0x21), pixelCoverage(0x22), pixelCoverage(0x23), + pixelCoverage(0x24), pixelCoverage(0x25), pixelCoverage(0x26), pixelCoverage(0x27), + pixelCoverage(0x28), pixelCoverage(0x29), pixelCoverage(0x2a), pixelCoverage(0x2b), + pixelCoverage(0x2c), pixelCoverage(0x2d), pixelCoverage(0x2e), pixelCoverage(0x2f), + pixelCoverage(0x30), pixelCoverage(0x31), pixelCoverage(0x32), pixelCoverage(0x33), + pixelCoverage(0x34), pixelCoverage(0x35), pixelCoverage(0x36), pixelCoverage(0x37), + pixelCoverage(0x38), pixelCoverage(0x39), pixelCoverage(0x3a), pixelCoverage(0x3b), + pixelCoverage(0x3c), pixelCoverage(0x3d), pixelCoverage(0x3e), pixelCoverage(0x3f), + pixelCoverage(0x40), pixelCoverage(0x41), pixelCoverage(0x42), pixelCoverage(0x43), + pixelCoverage(0x44), pixelCoverage(0x45), pixelCoverage(0x46), pixelCoverage(0x47), + pixelCoverage(0x48), pixelCoverage(0x49), pixelCoverage(0x4a), pixelCoverage(0x4b), + pixelCoverage(0x4c), pixelCoverage(0x4d), pixelCoverage(0x4e), pixelCoverage(0x4f), + pixelCoverage(0x50), pixelCoverage(0x51), pixelCoverage(0x52), pixelCoverage(0x53), + pixelCoverage(0x54), pixelCoverage(0x55), pixelCoverage(0x56), pixelCoverage(0x57), + pixelCoverage(0x58), pixelCoverage(0x59), pixelCoverage(0x5a), pixelCoverage(0x5b), + pixelCoverage(0x5c), pixelCoverage(0x5d), pixelCoverage(0x5e), pixelCoverage(0x5f), + pixelCoverage(0x60), pixelCoverage(0x61), pixelCoverage(0x62), pixelCoverage(0x63), + pixelCoverage(0x64), pixelCoverage(0x65), pixelCoverage(0x66), pixelCoverage(0x67), + pixelCoverage(0x68), pixelCoverage(0x69), pixelCoverage(0x6a), pixelCoverage(0x6b), + pixelCoverage(0x6c), pixelCoverage(0x6d), pixelCoverage(0x6e), pixelCoverage(0x6f), + pixelCoverage(0x70), pixelCoverage(0x71), pixelCoverage(0x72), pixelCoverage(0x73), + pixelCoverage(0x74), pixelCoverage(0x75), pixelCoverage(0x76), pixelCoverage(0x77), + pixelCoverage(0x78), pixelCoverage(0x79), pixelCoverage(0x7a), pixelCoverage(0x7b), + pixelCoverage(0x7c), pixelCoverage(0x7d), pixelCoverage(0x7e), pixelCoverage(0x7f), + pixelCoverage(0x80), pixelCoverage(0x81), pixelCoverage(0x82), pixelCoverage(0x83), + pixelCoverage(0x84), pixelCoverage(0x85), pixelCoverage(0x86), pixelCoverage(0x87), + pixelCoverage(0x88), pixelCoverage(0x89), pixelCoverage(0x8a), pixelCoverage(0x8b), + pixelCoverage(0x8c), pixelCoverage(0x8d), pixelCoverage(0x8e), pixelCoverage(0x8f), + pixelCoverage(0x90), pixelCoverage(0x91), pixelCoverage(0x92), pixelCoverage(0x93), + pixelCoverage(0x94), pixelCoverage(0x95), pixelCoverage(0x96), pixelCoverage(0x97), + pixelCoverage(0x98), pixelCoverage(0x99), pixelCoverage(0x9a), pixelCoverage(0x9b), + pixelCoverage(0x9c), pixelCoverage(0x9d), pixelCoverage(0x9e), pixelCoverage(0x9f), + pixelCoverage(0xa0), pixelCoverage(0xa1), pixelCoverage(0xa2), pixelCoverage(0xa3), + pixelCoverage(0xa4), pixelCoverage(0xa5), pixelCoverage(0xa6), pixelCoverage(0xa7), + pixelCoverage(0xa8), pixelCoverage(0xa9), pixelCoverage(0xaa), pixelCoverage(0xab), + pixelCoverage(0xac), pixelCoverage(0xad), pixelCoverage(0xae), pixelCoverage(0xaf), + pixelCoverage(0xb0), pixelCoverage(0xb1), pixelCoverage(0xb2), pixelCoverage(0xb3), + pixelCoverage(0xb4), pixelCoverage(0xb5), pixelCoverage(0xb6), pixelCoverage(0xb7), + pixelCoverage(0xb8), pixelCoverage(0xb9), pixelCoverage(0xba), pixelCoverage(0xbb), + pixelCoverage(0xbc), pixelCoverage(0xbd), pixelCoverage(0xbe), pixelCoverage(0xbf), + pixelCoverage(0xc0), pixelCoverage(0xc1), pixelCoverage(0xc2), pixelCoverage(0xc3), + pixelCoverage(0xc4), pixelCoverage(0xc5), pixelCoverage(0xc6), pixelCoverage(0xc7), + pixelCoverage(0xc8), pixelCoverage(0xc9), pixelCoverage(0xca), pixelCoverage(0xcb), + pixelCoverage(0xcc), pixelCoverage(0xcd), pixelCoverage(0xce), pixelCoverage(0xcf), + pixelCoverage(0xd0), pixelCoverage(0xd1), pixelCoverage(0xd2), pixelCoverage(0xd3), + pixelCoverage(0xd4), pixelCoverage(0xd5), pixelCoverage(0xd6), pixelCoverage(0xd7), + pixelCoverage(0xd8), pixelCoverage(0xd9), pixelCoverage(0xda), pixelCoverage(0xdb), + pixelCoverage(0xdc), pixelCoverage(0xdd), pixelCoverage(0xde), pixelCoverage(0xdf), + pixelCoverage(0xe0), pixelCoverage(0xe1), pixelCoverage(0xe2), pixelCoverage(0xe3), + pixelCoverage(0xe4), pixelCoverage(0xe5), pixelCoverage(0xe6), pixelCoverage(0xe7), + pixelCoverage(0xe8), pixelCoverage(0xe9), pixelCoverage(0xea), pixelCoverage(0xeb), + pixelCoverage(0xec), pixelCoverage(0xed), pixelCoverage(0xee), pixelCoverage(0xef), + pixelCoverage(0xf0), pixelCoverage(0xf1), pixelCoverage(0xf2), pixelCoverage(0xf3), + pixelCoverage(0xf4), pixelCoverage(0xf5), pixelCoverage(0xf6), pixelCoverage(0xf7), + pixelCoverage(0xf8), pixelCoverage(0xf9), pixelCoverage(0xfa), pixelCoverage(0xfb), + pixelCoverage(0xfc), pixelCoverage(0xfd), pixelCoverage(0xfe), pixelCoverage(0xff), +} + +func pixelCoverage(a uint8) uint8 { + return a&1 + a>>1&1 + a>>2&1 + a>>3&1 + a>>4&1 + a>>5&1 + a>>6&1 + a>>7&1 +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerAA.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerAA.go new file mode 100644 index 000000000..dbff87f1e --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerAA.go @@ -0,0 +1,320 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +import ( + "image" + "image/color" + "unsafe" +) + +const ( + SUBPIXEL_SHIFT = 3 + SUBPIXEL_COUNT = 1 << SUBPIXEL_SHIFT +) + +var SUBPIXEL_OFFSETS = SUBPIXEL_OFFSETS_SAMPLE_8_FIXED + +type SUBPIXEL_DATA uint8 +type NON_ZERO_MASK_DATA_UNIT uint8 + +type Rasterizer8BitsSample struct { + MaskBuffer []SUBPIXEL_DATA + WindingBuffer []NON_ZERO_MASK_DATA_UNIT + + Width int + BufferWidth int + Height int + ClipBound [4]float64 + RemappingMatrix [6]float64 +} + +/* width and height define the maximum output size for the filler. + * The filler will output to larger bitmaps as well, but the output will + * be cropped. + */ +func NewRasterizer8BitsSample(width, height int) *Rasterizer8BitsSample { + var r Rasterizer8BitsSample + // Scale the coordinates by SUBPIXEL_COUNT in vertical direction + // The sampling point for the sub-pixel is at the top right corner. This + // adjustment moves it to the pixel center. + r.RemappingMatrix = [6]float64{1, 0, 0, SUBPIXEL_COUNT, 0.5 / SUBPIXEL_COUNT, -0.5 * SUBPIXEL_COUNT} + r.Width = width + r.Height = height + // The buffer used for filling needs to be one pixel wider than the bitmap. + // This is because the end flag that turns the fill of is the first pixel + // after the actually drawn edge. + r.BufferWidth = width + 1 + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*height*SUBPIXEL_COUNT) + r.ClipBound = clip(0, 0, width, height, SUBPIXEL_COUNT) + return &r +} + +func clip(x, y, width, height, scale int) [4]float64 { + var clipBound [4]float64 + + offset := 0.99 / float64(scale) + + clipBound[0] = float64(x) + offset + clipBound[2] = float64(x+width) - offset + + clipBound[1] = float64(y * scale) + clipBound[3] = float64((y + height) * scale) + return clipBound +} + +func intersect(r1, r2 [4]float64) [4]float64 { + if r1[0] < r2[0] { + r1[0] = r2[0] + } + if r1[2] > r2[2] { + r1[2] = r2[2] + } + if r1[0] > r1[2] { + r1[0] = r1[2] + } + + if r1[1] < r2[1] { + r1[1] = r2[1] + } + if r1[3] > r2[3] { + r1[3] = r2[3] + } + if r1[1] > r1[3] { + r1[1] = r1[3] + } + return r1 +} + +func (r *Rasterizer8BitsSample) RenderEvenOdd(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + // memset 0 the mask buffer + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addEvenOddEdge(&edges[k]) + } + p += 16 + } + + r.fillEvenOdd(img, color, clipRect) +} + +//! Adds an edge to be used with even-odd fill. +func (r *Rasterizer8BitsSample) addEvenOddEdge(edge *PolygonEdge) { + x := Fix(edge.X * FIXED_FLOAT_COEF) + slope := Fix(edge.Slope * FIXED_FLOAT_COEF) + slopeFix := Fix(0) + if edge.LastLine-edge.FirstLine >= SLOPE_FIX_STEP { + slopeFix = Fix(edge.Slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - slope<<SLOPE_FIX_SHIFT + } + + var mask SUBPIXEL_DATA + var ySub uint32 + var xp, yLine int + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = uint32(y & (SUBPIXEL_COUNT - 1)) + xp = int((x + SUBPIXEL_OFFSETS[ySub]) >> FIXED_SHIFT) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] ^= mask + x += slope + if y&SLOPE_FIX_MASK == 0 { + x += slopeFix + } + } +} + +//! Adds an edge to be used with non-zero winding fill. +func (r *Rasterizer8BitsSample) addNonZeroEdge(edge *PolygonEdge) { + x := Fix(edge.X * FIXED_FLOAT_COEF) + slope := Fix(edge.Slope * FIXED_FLOAT_COEF) + slopeFix := Fix(0) + if edge.LastLine-edge.FirstLine >= SLOPE_FIX_STEP { + slopeFix = Fix(edge.Slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - slope<<SLOPE_FIX_SHIFT + } + var mask SUBPIXEL_DATA + var ySub uint32 + var xp, yLine int + winding := NON_ZERO_MASK_DATA_UNIT(edge.Winding) + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = uint32(y & (SUBPIXEL_COUNT - 1)) + xp = int((x + SUBPIXEL_OFFSETS[ySub]) >> FIXED_SHIFT) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] |= mask + r.WindingBuffer[(yLine*r.BufferWidth+xp)*SUBPIXEL_COUNT+int(ySub)] += winding + x += slope + if y&SLOPE_FIX_MASK == 0 { + x += slopeFix + } + } +} + +// Renders the mask to the canvas with even-odd fill. +func (r *Rasterizer8BitsSample) fillEvenOdd(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + mask ^= r.MaskBuffer[y*uint32(r.BufferWidth)+x] + // 8bits + alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff] + coverageTable[(mask >> 16) & 0xff] + coverageTable[(mask >> 24) & 0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := SUBPIXEL_COUNT - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} + +/* + * Renders the polygon with non-zero winding fill. + * param aTarget the target bitmap. + * param aPolygon the polygon to render. + * param aColor the color to be used for rendering. + * param aTransformation the transformation matrix. + */ +func (r *Rasterizer8BitsSample) RenderNonZeroWinding(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*r.Height*SUBPIXEL_COUNT) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addNonZeroEdge(&edges[k]) + } + p += 16 + } + + r.fillNonZero(img, color, clipRect) +} + +//! Renders the mask to the canvas with non-zero winding fill. +func (r *Rasterizer8BitsSample) fillNonZero(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + var n uint32 + var values [SUBPIXEL_COUNT]NON_ZERO_MASK_DATA_UNIT + for n = 0; n < SUBPIXEL_COUNT; n++ { + values[n] = 0 + } + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + temp := r.MaskBuffer[y*uint32(r.BufferWidth)+x] + if temp != 0 { + var bit SUBPIXEL_DATA = 1 + for n = 0; n < SUBPIXEL_COUNT; n++ { + if temp&bit != 0 { + t := values[n] + values[n] += r.WindingBuffer[(y*uint32(r.BufferWidth)+x)*SUBPIXEL_COUNT+n] + if (t == 0 || values[n] == 0) && t != values[n] { + mask ^= bit + } + } + bit <<= 1 + } + } + + // 8bits + alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff] + coverageTable[(mask >> 16) & 0xff] + coverageTable[(mask >> 24) & 0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := uint32(SUBPIXEL_COUNT) - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV1/fillerAA.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV1/fillerAA.go new file mode 100644 index 000000000..a85d34c77 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV1/fillerAA.go @@ -0,0 +1,303 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +import ( + "image" + "image/color" + "unsafe" +) + +const ( + SUBPIXEL_SHIFT = 3 + SUBPIXEL_COUNT = 1 << SUBPIXEL_SHIFT +) + +var SUBPIXEL_OFFSETS = SUBPIXEL_OFFSETS_SAMPLE_8 + +type SUBPIXEL_DATA uint16 +type NON_ZERO_MASK_DATA_UNIT uint8 + +type Rasterizer8BitsSample struct { + MaskBuffer []SUBPIXEL_DATA + WindingBuffer []NON_ZERO_MASK_DATA_UNIT + + Width int + BufferWidth int + Height int + ClipBound [4]float64 + RemappingMatrix [6]float64 +} + +/* width and height define the maximum output size for the filler. + * The filler will output to larger bitmaps as well, but the output will + * be cropped. + */ +func NewRasterizer8BitsSample(width, height int) *Rasterizer8BitsSample { + var r Rasterizer8BitsSample + // Scale the coordinates by SUBPIXEL_COUNT in vertical direction + // The sampling point for the sub-pixel is at the top right corner. This + // adjustment moves it to the pixel center. + r.RemappingMatrix = [6]float64{1, 0, 0, SUBPIXEL_COUNT, 0.5 / SUBPIXEL_COUNT, -0.5 * SUBPIXEL_COUNT} + r.Width = width + r.Height = height + // The buffer used for filling needs to be one pixel wider than the bitmap. + // This is because the end flag that turns the fill of is the first pixel + // after the actually drawn edge. + r.BufferWidth = width + 1 + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*height*SUBPIXEL_COUNT) + r.ClipBound = clip(0, 0, width, height, SUBPIXEL_COUNT) + return &r +} + +func clip(x, y, width, height, scale int) [4]float64 { + var clipBound [4]float64 + + offset := 0.99 / float64(scale) + + clipBound[0] = float64(x) + offset + clipBound[2] = float64(x+width) - offset + + clipBound[1] = float64(y * scale) + clipBound[3] = float64((y + height) * scale) + return clipBound +} + +func intersect(r1, r2 [4]float64) [4]float64 { + if r1[0] < r2[0] { + r1[0] = r2[0] + } + if r1[2] > r2[2] { + r1[2] = r2[2] + } + if r1[0] > r1[2] { + r1[0] = r1[2] + } + + if r1[1] < r2[1] { + r1[1] = r2[1] + } + if r1[3] > r2[3] { + r1[3] = r2[3] + } + if r1[1] > r1[3] { + r1[1] = r1[3] + } + return r1 +} + +func (r *Rasterizer8BitsSample) RenderEvenOdd(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + // memset 0 the mask buffer + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addEvenOddEdge(&edges[k]) + } + p += 16 + } + + r.fillEvenOdd(img, color, clipRect) +} + +//! Adds an edge to be used with even-odd fill. +func (r *Rasterizer8BitsSample) addEvenOddEdge(edge *PolygonEdge) { + x := edge.X + slope := edge.Slope + var ySub, mask SUBPIXEL_DATA + var xp, yLine int + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = SUBPIXEL_DATA(y & (SUBPIXEL_COUNT - 1)) + xp = int(x + SUBPIXEL_OFFSETS[ySub]) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] ^= mask + x += slope + } +} + +// Renders the mask to the canvas with even-odd fill. +func (r *Rasterizer8BitsSample) fillEvenOdd(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + mask ^= r.MaskBuffer[y*uint32(r.BufferWidth)+x] + // 8bits + alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff] + coverageTable[(mask >> 16) & 0xff] + coverageTable[(mask >> 24) & 0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := uint32(SUBPIXEL_COUNT) - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} + +/* + * Renders the polygon with non-zero winding fill. + * param aTarget the target bitmap. + * param aPolygon the polygon to render. + * param aColor the color to be used for rendering. + * param aTransformation the transformation matrix. + */ +func (r *Rasterizer8BitsSample) RenderNonZeroWinding(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*r.Height*SUBPIXEL_COUNT) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addNonZeroEdge(&edges[k]) + } + p += 16 + } + + r.fillNonZero(img, color, clipRect) +} + +//! Adds an edge to be used with non-zero winding fill. +func (r *Rasterizer8BitsSample) addNonZeroEdge(edge *PolygonEdge) { + x := edge.X + slope := edge.Slope + var ySub, mask SUBPIXEL_DATA + var xp, yLine int + winding := NON_ZERO_MASK_DATA_UNIT(edge.Winding) + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = SUBPIXEL_DATA(y & (SUBPIXEL_COUNT - 1)) + xp = int(x + SUBPIXEL_OFFSETS[ySub]) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] |= mask + r.WindingBuffer[(yLine*r.BufferWidth+xp)*SUBPIXEL_COUNT+int(ySub)] += winding + x += slope + } +} + +//! Renders the mask to the canvas with non-zero winding fill. +func (r *Rasterizer8BitsSample) fillNonZero(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + var n uint32 + var values [SUBPIXEL_COUNT]NON_ZERO_MASK_DATA_UNIT + for n = 0; n < SUBPIXEL_COUNT; n++ { + values[n] = 0 + } + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + temp := r.MaskBuffer[y*uint32(r.BufferWidth)+x] + if temp != 0 { + var bit SUBPIXEL_DATA = 1 + for n = 0; n < SUBPIXEL_COUNT; n++ { + if temp&bit != 0 { + t := values[n] + values[n] += r.WindingBuffer[(y*uint32(r.BufferWidth)+x)*SUBPIXEL_COUNT+n] + if (t == 0 || values[n] == 0) && t != values[n] { + mask ^= bit + } + } + bit <<= 1 + } + } + + // 8bits + alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff] + coverageTable[(mask >> 16) & 0xff] + coverageTable[(mask >> 24) & 0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := uint32(SUBPIXEL_COUNT) - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV2/fillerAA.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV2/fillerAA.go new file mode 100644 index 000000000..0bda5a4db --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fillerV2/fillerAA.go @@ -0,0 +1,320 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +import ( + "image" + "image/color" + "unsafe" +) + +const ( + SUBPIXEL_SHIFT = 5 + SUBPIXEL_COUNT = 1 << SUBPIXEL_SHIFT +) + +var SUBPIXEL_OFFSETS = SUBPIXEL_OFFSETS_SAMPLE_32_FIXED + +type SUBPIXEL_DATA uint32 +type NON_ZERO_MASK_DATA_UNIT uint8 + +type Rasterizer8BitsSample struct { + MaskBuffer []SUBPIXEL_DATA + WindingBuffer []NON_ZERO_MASK_DATA_UNIT + + Width int + BufferWidth int + Height int + ClipBound [4]float64 + RemappingMatrix [6]float64 +} + +/* width and height define the maximum output size for the filler. + * The filler will output to larger bitmaps as well, but the output will + * be cropped. + */ +func NewRasterizer8BitsSample(width, height int) *Rasterizer8BitsSample { + var r Rasterizer8BitsSample + // Scale the coordinates by SUBPIXEL_COUNT in vertical direction + // The sampling point for the sub-pixel is at the top right corner. This + // adjustment moves it to the pixel center. + r.RemappingMatrix = [6]float64{1, 0, 0, SUBPIXEL_COUNT, 0.5 / SUBPIXEL_COUNT, -0.5 * SUBPIXEL_COUNT} + r.Width = width + r.Height = height + // The buffer used for filling needs to be one pixel wider than the bitmap. + // This is because the end flag that turns the fill of is the first pixel + // after the actually drawn edge. + r.BufferWidth = width + 1 + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*height*SUBPIXEL_COUNT) + r.ClipBound = clip(0, 0, width, height, SUBPIXEL_COUNT) + return &r +} + +func clip(x, y, width, height, scale int) [4]float64 { + var clipBound [4]float64 + + offset := 0.99 / float64(scale) + + clipBound[0] = float64(x) + offset + clipBound[2] = float64(x+width) - offset + + clipBound[1] = float64(y * scale) + clipBound[3] = float64((y + height) * scale) + return clipBound +} + +func intersect(r1, r2 [4]float64) [4]float64 { + if r1[0] < r2[0] { + r1[0] = r2[0] + } + if r1[2] > r2[2] { + r1[2] = r2[2] + } + if r1[0] > r1[2] { + r1[0] = r1[2] + } + + if r1[1] < r2[1] { + r1[1] = r2[1] + } + if r1[3] > r2[3] { + r1[3] = r2[3] + } + if r1[1] > r1[3] { + r1[1] = r1[3] + } + return r1 +} + +func (r *Rasterizer8BitsSample) RenderEvenOdd(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + // memset 0 the mask buffer + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addEvenOddEdge(&edges[k]) + } + p += 16 + } + + r.fillEvenOdd(img, color, clipRect) +} + +//! Adds an edge to be used with even-odd fill. +func (r *Rasterizer8BitsSample) addEvenOddEdge(edge *PolygonEdge) { + x := Fix(edge.X * FIXED_FLOAT_COEF) + slope := Fix(edge.Slope * FIXED_FLOAT_COEF) + slopeFix := Fix(0) + if edge.LastLine-edge.FirstLine >= SLOPE_FIX_STEP { + slopeFix = Fix(edge.Slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - slope<<SLOPE_FIX_SHIFT + } + + var mask SUBPIXEL_DATA + var ySub uint32 + var xp, yLine int + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = uint32(y & (SUBPIXEL_COUNT - 1)) + xp = int((x + SUBPIXEL_OFFSETS[ySub]) >> FIXED_SHIFT) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] ^= mask + x += slope + if y&SLOPE_FIX_MASK == 0 { + x += slopeFix + } + } +} + +//! Adds an edge to be used with non-zero winding fill. +func (r *Rasterizer8BitsSample) addNonZeroEdge(edge *PolygonEdge) { + x := Fix(edge.X * FIXED_FLOAT_COEF) + slope := Fix(edge.Slope * FIXED_FLOAT_COEF) + slopeFix := Fix(0) + if edge.LastLine-edge.FirstLine >= SLOPE_FIX_STEP { + slopeFix = Fix(edge.Slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - slope<<SLOPE_FIX_SHIFT + } + var mask SUBPIXEL_DATA + var ySub uint32 + var xp, yLine int + winding := NON_ZERO_MASK_DATA_UNIT(edge.Winding) + for y := edge.FirstLine; y <= edge.LastLine; y++ { + ySub = uint32(y & (SUBPIXEL_COUNT - 1)) + xp = int((x + SUBPIXEL_OFFSETS[ySub]) >> FIXED_SHIFT) + mask = SUBPIXEL_DATA(1 << ySub) + yLine = y >> SUBPIXEL_SHIFT + r.MaskBuffer[yLine*r.BufferWidth+xp] |= mask + r.WindingBuffer[(yLine*r.BufferWidth+xp)*SUBPIXEL_COUNT+int(ySub)] += winding + x += slope + if y&SLOPE_FIX_MASK == 0 { + x += slopeFix + } + } +} + +// Renders the mask to the canvas with even-odd fill. +func (r *Rasterizer8BitsSample) fillEvenOdd(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + mask ^= r.MaskBuffer[y*uint32(r.BufferWidth)+x] + // 8bits + //alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + alpha := uint32(coverageTable[mask&0xff] + coverageTable[mask>>8&0xff] + coverageTable[mask>>16&0xff] + coverageTable[mask>>24&0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := uint32(SUBPIXEL_COUNT) - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} + +/* + * Renders the polygon with non-zero winding fill. + * param aTarget the target bitmap. + * param aPolygon the polygon to render. + * param aColor the color to be used for rendering. + * param aTransformation the transformation matrix. + */ +func (r *Rasterizer8BitsSample) RenderNonZeroWinding(img *image.RGBA, color *color.RGBA, polygon *Polygon, tr [6]float64) { + + r.MaskBuffer = make([]SUBPIXEL_DATA, r.BufferWidth*r.Height) + r.WindingBuffer = make([]NON_ZERO_MASK_DATA_UNIT, r.BufferWidth*r.Height*SUBPIXEL_COUNT) + + // inline matrix multiplication + transform := [6]float64{ + tr[0]*r.RemappingMatrix[0] + tr[1]*r.RemappingMatrix[2], + tr[1]*r.RemappingMatrix[3] + tr[0]*r.RemappingMatrix[1], + tr[2]*r.RemappingMatrix[0] + tr[3]*r.RemappingMatrix[2], + tr[3]*r.RemappingMatrix[3] + tr[2]*r.RemappingMatrix[1], + tr[4]*r.RemappingMatrix[0] + tr[5]*r.RemappingMatrix[2] + r.RemappingMatrix[4], + tr[5]*r.RemappingMatrix[3] + tr[4]*r.RemappingMatrix[1] + r.RemappingMatrix[5], + } + + clipRect := clip(img.Bounds().Min.X, img.Bounds().Min.Y, img.Bounds().Dx(), img.Bounds().Dy(), SUBPIXEL_COUNT) + clipRect = intersect(clipRect, r.ClipBound) + + p := 0 + l := len(*polygon) / 2 + var edges [32]PolygonEdge + for p < l { + edgeCount := polygon.getEdges(p, 16, edges[:], transform, clipRect) + for k := 0; k < edgeCount; k++ { + r.addNonZeroEdge(&edges[k]) + } + p += 16 + } + + r.fillNonZero(img, color, clipRect) +} + +//! Renders the mask to the canvas with non-zero winding fill. +func (r *Rasterizer8BitsSample) fillNonZero(img *image.RGBA, color *color.RGBA, clipBound [4]float64) { + var x, y uint32 + + minX := uint32(clipBound[0]) + maxX := uint32(clipBound[2]) + + minY := uint32(clipBound[1]) >> SUBPIXEL_SHIFT + maxY := uint32(clipBound[3]) >> SUBPIXEL_SHIFT + + //pixColor := (uint32(color.R) << 24) | (uint32(color.G) << 16) | (uint32(color.B) << 8) | uint32(color.A) + pixColor := (*uint32)(unsafe.Pointer(color)) + cs1 := *pixColor & 0xff00ff + cs2 := *pixColor >> 8 & 0xff00ff + + stride := uint32(img.Stride) + var mask SUBPIXEL_DATA + var n uint32 + var values [SUBPIXEL_COUNT]NON_ZERO_MASK_DATA_UNIT + for n = 0; n < SUBPIXEL_COUNT; n++ { + values[n] = 0 + } + + for y = minY; y < maxY; y++ { + tp := img.Pix[y*stride:] + + mask = 0 + for x = minX; x <= maxX; x++ { + p := (*uint32)(unsafe.Pointer(&tp[x])) + temp := r.MaskBuffer[y*uint32(r.BufferWidth)+x] + if temp != 0 { + var bit SUBPIXEL_DATA = 1 + for n = 0; n < SUBPIXEL_COUNT; n++ { + if temp&bit != 0 { + t := values[n] + values[n] += r.WindingBuffer[(y*uint32(r.BufferWidth)+x)*SUBPIXEL_COUNT+n] + if (t == 0 || values[n] == 0) && t != values[n] { + mask ^= bit + } + } + bit <<= 1 + } + } + + // 8bits + //alpha := uint32(coverageTable[mask]) + // 16bits + //alpha := uint32(coverageTable[mask & 0xff] + coverageTable[(mask >> 8) & 0xff]) + // 32bits + alpha := uint32(coverageTable[mask&0xff] + coverageTable[mask>>8&0xff] + coverageTable[mask>>16&0xff] + coverageTable[mask>>24&0xff]) + + // alpha is in range of 0 to SUBPIXEL_COUNT + invAlpha := uint32(SUBPIXEL_COUNT) - alpha + + ct1 := *p & 0xff00ff * invAlpha + ct2 := *p >> 8 & 0xff00ff * invAlpha + + ct1 = (ct1 + cs1*alpha) >> SUBPIXEL_SHIFT & 0xff00ff + ct2 = (ct2 + cs2*alpha) << (8 - SUBPIXEL_SHIFT) & 0xff00ff00 + + *p = ct1 + ct2 + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fixed_point.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fixed_point.go new file mode 100644 index 000000000..14b8419c3 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/fixed_point.go @@ -0,0 +1,17 @@ +package raster + +type Fix int32 + +const ( + FIXED_SHIFT = 16 + FIXED_FLOAT_COEF = 1 << FIXED_SHIFT +) + +/*! Fixed point math inevitably introduces rounding error to the DDA. The error is + * fixed every now and then by a separate fix value. The defines below set these. + */ +const ( + SLOPE_FIX_SHIFT = 8 + SLOPE_FIX_STEP = 1 << SLOPE_FIX_SHIFT + SLOPE_FIX_MASK = SLOPE_FIX_STEP - 1 +) diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/line.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/line.go new file mode 100644 index 000000000..6f6d8863f --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/line.go @@ -0,0 +1,55 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +import ( + "image/color" + "image/draw" +) + +func abs(i int) int { + if i < 0 { + return -i + } + return i +} + +func PolylineBresenham(img draw.Image, c color.Color, s ...float64) { + for i := 2; i < len(s); i += 2 { + Bresenham(img, c, int(s[i-2]+0.5), int(s[i-1]+0.5), int(s[i]+0.5), int(s[i+1]+0.5)) + } +} + +func Bresenham(img draw.Image, color color.Color, x0, y0, x1, y1 int) { + dx := abs(x1 - x0) + dy := abs(y1 - y0) + var sx, sy int + if x0 < x1 { + sx = 1 + } else { + sx = -1 + } + if y0 < y1 { + sy = 1 + } else { + sy = -1 + } + err := dx - dy + + var e2 int + for { + img.Set(x0, y0, color) + if x0 == x1 && y0 == y1 { + return + } + e2 = 2 * err + if e2 > -dy { + err = err - dy + x0 = x0 + sx + } + if e2 < dx { + err = err + dx + y0 = y0 + sy + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go new file mode 100644 index 000000000..2a19e7355 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/polygon.go @@ -0,0 +1,581 @@ +// Copyright 2011 The draw2d Authors. All rights reserved. +// created: 27/05/2011 by Laurent Le Goff +package raster + +const ( + POLYGON_CLIP_NONE = iota + POLYGON_CLIP_LEFT + POLYGON_CLIP_RIGHT + POLYGON_CLIP_TOP + POLYGON_CLIP_BOTTOM +) + +type Polygon []float64 + +type PolygonEdge struct { + X, Slope float64 + FirstLine, LastLine int + Winding int16 +} + +//! A more optimized representation of a polygon edge. +type PolygonScanEdge struct { + FirstLine, LastLine int + Winding int16 + X Fix + Slope Fix + SlopeFix Fix + NextEdge *PolygonScanEdge +} + +//! Calculates the edges of the polygon with transformation and clipping to edges array. +/*! \param startIndex the index for the first vertex. + * \param vertexCount the amount of vertices to convert. + * \param edges the array for result edges. This should be able to contain 2*aVertexCount edges. + * \param tr the transformation matrix for the polygon. + * \param aClipRectangle the clip rectangle. + * \return the amount of edges in the result. + */ +func (p Polygon) getEdges(startIndex, vertexCount int, edges []PolygonEdge, tr [6]float64, clipBound [4]float64) int { + startIndex = startIndex * 2 + endIndex := startIndex + vertexCount*2 + if endIndex > len(p) { + endIndex = len(p) + } + + x := p[startIndex] + y := p[startIndex+1] + // inline transformation + prevX := x*tr[0] + y*tr[2] + tr[4] + prevY := x*tr[1] + y*tr[3] + tr[5] + + //! Calculates the clip flags for a point. + prevClipFlags := POLYGON_CLIP_NONE + if prevX < clipBound[0] { + prevClipFlags |= POLYGON_CLIP_LEFT + } else if prevX >= clipBound[2] { + prevClipFlags |= POLYGON_CLIP_RIGHT + } + + if prevY < clipBound[1] { + prevClipFlags |= POLYGON_CLIP_TOP + } else if prevY >= clipBound[3] { + prevClipFlags |= POLYGON_CLIP_BOTTOM + } + + edgeCount := 0 + var k, clipFlags, clipSum, clipUnion int + var xleft, yleft, xright, yright, oldY, maxX, minX float64 + var swapWinding int16 + for n := startIndex; n < endIndex; n = n + 2 { + k = (n + 2) % len(p) + x = p[k]*tr[0] + p[k+1]*tr[2] + tr[4] + y = p[k]*tr[1] + p[k+1]*tr[3] + tr[5] + + //! Calculates the clip flags for a point. + clipFlags = POLYGON_CLIP_NONE + if prevX < clipBound[0] { + clipFlags |= POLYGON_CLIP_LEFT + } else if prevX >= clipBound[2] { + clipFlags |= POLYGON_CLIP_RIGHT + } + if prevY < clipBound[1] { + clipFlags |= POLYGON_CLIP_TOP + } else if prevY >= clipBound[3] { + clipFlags |= POLYGON_CLIP_BOTTOM + } + + clipSum = prevClipFlags | clipFlags + clipUnion = prevClipFlags & clipFlags + + // Skip all edges that are either completely outside at the top or at the bottom. + if clipUnion&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) == 0 { + if clipUnion&POLYGON_CLIP_RIGHT != 0 { + // Both clip to right, edge is a vertical line on the right side + if getVerticalEdge(prevY, y, clipBound[2], &edges[edgeCount], clipBound) { + edgeCount++ + } + } else if clipUnion&POLYGON_CLIP_LEFT != 0 { + // Both clip to left, edge is a vertical line on the left side + if getVerticalEdge(prevY, y, clipBound[0], &edges[edgeCount], clipBound) { + edgeCount++ + } + } else if clipSum&(POLYGON_CLIP_RIGHT|POLYGON_CLIP_LEFT) == 0 { + // No clipping in the horizontal direction + if getEdge(prevX, prevY, x, y, &edges[edgeCount], clipBound) { + edgeCount++ + } + } else { + // Clips to left or right or both. + + if x < prevX { + xleft, yleft = x, y + xright, yright = prevX, prevY + swapWinding = -1 + } else { + xleft, yleft = prevX, prevY + xright, yright = x, y + swapWinding = 1 + } + + slope := (yright - yleft) / (xright - xleft) + + if clipSum&POLYGON_CLIP_RIGHT != 0 { + // calculate new position for the right vertex + oldY = yright + maxX = clipBound[2] + + yright = yleft + (maxX-xleft)*slope + xright = maxX + + // add vertical edge for the overflowing part + if getVerticalEdge(yright, oldY, maxX, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + + if clipSum&POLYGON_CLIP_LEFT != 0 { + // calculate new position for the left vertex + oldY = yleft + minX = clipBound[0] + + yleft = yleft + (minX-xleft)*slope + xleft = minX + + // add vertical edge for the overflowing part + if getVerticalEdge(oldY, yleft, minX, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + + if getEdge(xleft, yleft, xright, yright, &edges[edgeCount], clipBound) { + edges[edgeCount].Winding *= swapWinding + edgeCount++ + } + } + } + + prevClipFlags = clipFlags + prevX = x + prevY = y + } + + return edgeCount +} + +//! Creates a polygon edge between two vectors. +/*! Clips the edge vertically to the clip rectangle. Returns true for edges that + * should be rendered, false for others. + */ +func getEdge(x0, y0, x1, y1 float64, edge *PolygonEdge, clipBound [4]float64) bool { + var startX, startY, endX, endY float64 + var winding int16 + + if y0 <= y1 { + startX = x0 + startY = y0 + endX = x1 + endY = y1 + winding = 1 + } else { + startX = x1 + startY = y1 + endX = x0 + endY = y0 + winding = -1 + } + + // Essentially, firstLine is floor(startY + 1) and lastLine is floor(endY). + // These are refactored to integer casts in order to avoid function + // calls. The difference with integer cast is that numbers are always + // rounded towards zero. Since values smaller than zero get clipped away, + // only coordinates between 0 and -1 require greater attention as they + // also round to zero. The problems in this range can be avoided by + // adding one to the values before conversion and subtracting after it. + + firstLine := int(startY + 1) + lastLine := int(endY+1) - 1 + + minClip := int(clipBound[1]) + maxClip := int(clipBound[3]) + + // If start and end are on the same line, the edge doesn't cross + // any lines and thus can be ignored. + // If the end is smaller than the first line, edge is out. + // If the start is larger than the last line, edge is out. + if firstLine > lastLine || lastLine < minClip || firstLine >= maxClip { + return false + } + + // Adjust the start based on the target. + if firstLine < minClip { + firstLine = minClip + } + + if lastLine >= maxClip { + lastLine = maxClip - 1 + } + edge.Slope = (endX - startX) / (endY - startY) + edge.X = startX + (float64(firstLine)-startY)*edge.Slope + edge.Winding = winding + edge.FirstLine = firstLine + edge.LastLine = lastLine + + return true +} + +//! Creates a vertical polygon edge between two y values. +/*! Clips the edge vertically to the clip rectangle. Returns true for edges that + * should be rendered, false for others. + */ +func getVerticalEdge(startY, endY, x float64, edge *PolygonEdge, clipBound [4]float64) bool { + var start, end float64 + var winding int16 + if startY < endY { + start = startY + end = endY + winding = 1 + } else { + start = endY + end = startY + winding = -1 + } + + firstLine := int(start + 1) + lastLine := int(end+1) - 1 + + minClip := int(clipBound[1]) + maxClip := int(clipBound[3]) + + // If start and end are on the same line, the edge doesn't cross + // any lines and thus can be ignored. + // If the end is smaller than the first line, edge is out. + // If the start is larger than the last line, edge is out. + if firstLine > lastLine || lastLine < minClip || firstLine >= maxClip { + return false + } + + // Adjust the start based on the clip rect. + if firstLine < minClip { + firstLine = minClip + } + if lastLine >= maxClip { + lastLine = maxClip - 1 + } + + edge.Slope = 0 + edge.X = x + edge.Winding = winding + edge.FirstLine = firstLine + edge.LastLine = lastLine + + return true +} + +type VertexData struct { + X, Y float64 + ClipFlags int + Line int +} + +//! Calculates the edges of the polygon with transformation and clipping to edges array. +/*! Note that this may return upto three times the amount of edges that the polygon has vertices, + * in the unlucky case where both left and right side get clipped for all edges. + * \param edges the array for result edges. This should be able to contain 2*aVertexCount edges. + * \param aTransformation the transformation matrix for the polygon. + * \param aClipRectangle the clip rectangle. + * \return the amount of edges in the result. + */ +func (p Polygon) getScanEdges(edges []PolygonScanEdge, tr [6]float64, clipBound [4]float64) int { + var n int + vertexData := make([]VertexData, len(p)/2+1) + for n = 0; n < len(vertexData)-1; n = n + 1 { + k := n * 2 + vertexData[n].X = p[k]*tr[0] + p[k+1]*tr[2] + tr[4] + vertexData[n].Y = p[k]*tr[1] + p[k+1]*tr[3] + tr[5] + // Calculate clip flags for all vertices. + vertexData[n].ClipFlags = POLYGON_CLIP_NONE + if vertexData[n].X < clipBound[0] { + vertexData[n].ClipFlags |= POLYGON_CLIP_LEFT + } else if vertexData[n].X >= clipBound[2] { + vertexData[n].ClipFlags |= POLYGON_CLIP_RIGHT + } + if vertexData[n].Y < clipBound[1] { + vertexData[n].ClipFlags |= POLYGON_CLIP_TOP + } else if vertexData[n].Y >= clipBound[3] { + vertexData[n].ClipFlags |= POLYGON_CLIP_BOTTOM + } + + // Calculate line of the vertex. If the vertex is clipped by top or bottom, the line + // is determined by the clip rectangle. + if vertexData[n].ClipFlags&POLYGON_CLIP_TOP != 0 { + vertexData[n].Line = int(clipBound[1]) + } else if vertexData[n].ClipFlags&POLYGON_CLIP_BOTTOM != 0 { + vertexData[n].Line = int(clipBound[3] - 1) + } else { + vertexData[n].Line = int(vertexData[n].Y+1) - 1 + } + } + + // Copy the data from 0 to the last entry to make the data to loop. + vertexData[len(vertexData)-1] = vertexData[0] + + // Transform the first vertex; store. + // Process mVertexCount - 1 times, next is n+1 + // copy the first vertex to + // Process 1 time, next is n + + edgeCount := 0 + for n = 0; n < len(vertexData)-1; n++ { + clipSum := vertexData[n].ClipFlags | vertexData[n+1].ClipFlags + clipUnion := vertexData[n].ClipFlags & vertexData[n+1].ClipFlags + + if clipUnion&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) == 0 && + vertexData[n].Line != vertexData[n+1].Line { + var startIndex, endIndex int + var winding int16 + if vertexData[n].Y < vertexData[n+1].Y { + startIndex = n + endIndex = n + 1 + winding = 1 + } else { + startIndex = n + 1 + endIndex = n + winding = -1 + } + + firstLine := vertexData[startIndex].Line + 1 + lastLine := vertexData[endIndex].Line + + if clipUnion&POLYGON_CLIP_RIGHT != 0 { + // Both clip to right, edge is a vertical line on the right side + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(clipBound[2] * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + + edgeCount++ + } else if clipUnion&POLYGON_CLIP_LEFT != 0 { + // Both clip to left, edge is a vertical line on the left side + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(clipBound[0] * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + + edgeCount++ + } else if clipSum&(POLYGON_CLIP_RIGHT|POLYGON_CLIP_LEFT) == 0 { + // No clipping in the horizontal direction + slope := (vertexData[endIndex].X - + vertexData[startIndex].X) / + (vertexData[endIndex].Y - + vertexData[startIndex].Y) + + // If there is vertical clip (for the top) it will be processed here. The calculation + // should be done for all non-clipping edges as well to determine the accurate position + // where the edge crosses the first scanline. + startx := vertexData[startIndex].X + + (float64(firstLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if lastLine-firstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + + edgeCount++ + } else { + // Clips to left or right or both. + slope := (vertexData[endIndex].X - + vertexData[startIndex].X) / + (vertexData[endIndex].Y - + vertexData[startIndex].Y) + + // The edge may clip to both left and right. + // The clip results in one or two new vertices, and one to three segments. + // The rounding for scanlines may produce a result where any of the segments is + // ignored. + + // The start is always above the end. Calculate the clip positions to clipVertices. + // It is possible that only one of the vertices exist. This will be detected from the + // clip flags of the vertex later, so they are initialized here. + var clipVertices [2]VertexData + + if vertexData[startIndex].X < + vertexData[endIndex].X { + clipVertices[0].X = clipBound[0] + clipVertices[1].X = clipBound[2] + clipVertices[0].ClipFlags = POLYGON_CLIP_LEFT + clipVertices[1].ClipFlags = POLYGON_CLIP_RIGHT + } else { + clipVertices[0].X = clipBound[2] + clipVertices[1].X = clipBound[0] + clipVertices[0].ClipFlags = POLYGON_CLIP_RIGHT + clipVertices[1].ClipFlags = POLYGON_CLIP_LEFT + } + + var p int + for p = 0; p < 2; p++ { + // Check if either of the vertices crosses the edge marked for the clip vertex + if clipSum&clipVertices[p].ClipFlags != 0 { + // The the vertex is required, calculate it. + clipVertices[p].Y = vertexData[startIndex].Y + + (clipVertices[p].X- + vertexData[startIndex].X)/slope + + // If there is clipping in the vertical direction, the new vertex may be clipped. + if clipSum&(POLYGON_CLIP_TOP|POLYGON_CLIP_BOTTOM) != 0 { + if clipVertices[p].Y < clipBound[1] { + clipVertices[p].ClipFlags = POLYGON_CLIP_TOP + clipVertices[p].Line = int(clipBound[1]) + } else if clipVertices[p].Y > clipBound[3] { + clipVertices[p].ClipFlags = POLYGON_CLIP_BOTTOM + clipVertices[p].Line = int(clipBound[3] - 1) + } else { + clipVertices[p].ClipFlags = 0 + clipVertices[p].Line = int(clipVertices[p].Y+1) - 1 + } + } else { + clipVertices[p].ClipFlags = 0 + clipVertices[p].Line = int(clipVertices[p].Y+1) - 1 + } + } + } + + // Now there are three or four vertices, in the top-to-bottom order of start, clip0, clip1, + // end. What kind of edges are required for connecting these can be determined from the + // clip flags. + // -if clip vertex has horizontal clip flags, it doesn't exist. No edge is generated. + // -if start vertex or end vertex has horizontal clip flag, the edge to/from the clip vertex is vertical + // -if the line of two vertices is the same, the edge is not generated, since the edge doesn't + // cross any scanlines. + + // The alternative patterns are: + // start - clip0 - clip1 - end + // start - clip0 - end + // start - clip1 - end + + var topClipIndex, bottomClipIndex int + if (clipVertices[0].ClipFlags|clipVertices[1].ClipFlags)& + (POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) == 0 { + // Both sides are clipped, the order is start-clip0-clip1-end + topClipIndex = 0 + bottomClipIndex = 1 + + // Add the edge from clip0 to clip1 + // Check that the line is different for the vertices. + if clipVertices[0].Line != clipVertices[1].Line { + firstClipLine := clipVertices[0].Line + 1 + + startx := vertexData[startIndex].X + + (float64(firstClipLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + edges[edgeCount].FirstLine = firstClipLine + edges[edgeCount].LastLine = clipVertices[1].Line + edges[edgeCount].Winding = winding + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + + edgeCount++ + } + } else { + // Clip at either side, check which side. The clip flag is on for the vertex + // that doesn't exist, i.e. has not been clipped to be inside the rect. + if clipVertices[0].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + topClipIndex = 1 + bottomClipIndex = 1 + } else { + topClipIndex = 0 + bottomClipIndex = 0 + } + } + + // Generate the edges from start - clip top and clip bottom - end + // Clip top and clip bottom may be the same vertex if there is only one + // clipped vertex. + + // Check that the line is different for the vertices. + if vertexData[startIndex].Line != clipVertices[topClipIndex].Line { + edges[edgeCount].FirstLine = firstLine + edges[edgeCount].LastLine = clipVertices[topClipIndex].Line + edges[edgeCount].Winding = winding + + // If startIndex is clipped, the edge is a vertical one. + if vertexData[startIndex].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + edges[edgeCount].X = Fix(clipVertices[topClipIndex].X * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + } else { + startx := vertexData[startIndex].X + + (float64(firstLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + } + + edgeCount++ + } + + // Check that the line is different for the vertices. + if clipVertices[bottomClipIndex].Line != vertexData[endIndex].Line { + firstClipLine := clipVertices[bottomClipIndex].Line + 1 + + edges[edgeCount].FirstLine = firstClipLine + edges[edgeCount].LastLine = lastLine + edges[edgeCount].Winding = winding + + // If endIndex is clipped, the edge is a vertical one. + if vertexData[endIndex].ClipFlags&(POLYGON_CLIP_LEFT|POLYGON_CLIP_RIGHT) != 0 { + edges[edgeCount].X = Fix(clipVertices[bottomClipIndex].X * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = 0 + edges[edgeCount].SlopeFix = 0 + } else { + startx := vertexData[startIndex].X + + (float64(firstClipLine)-vertexData[startIndex].Y)*slope + + edges[edgeCount].X = Fix(startx * FIXED_FLOAT_COEF) + edges[edgeCount].Slope = Fix(slope * FIXED_FLOAT_COEF) + + if edges[edgeCount].LastLine-edges[edgeCount].FirstLine >= SLOPE_FIX_STEP { + edges[edgeCount].SlopeFix = Fix(slope*SLOPE_FIX_STEP*FIXED_FLOAT_COEF) - + edges[edgeCount].Slope<<SLOPE_FIX_SHIFT + } else { + edges[edgeCount].SlopeFix = 0 + } + } + + edgeCount++ + } + + } + } + } + + return edgeCount +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/raster_test.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/raster_test.go new file mode 100644 index 000000000..7872d8d03 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/raster/raster_test.go @@ -0,0 +1,200 @@ +package raster + +import ( + "bufio" + "code.google.com/p/draw2d/draw2d/curve" + "code.google.com/p/freetype-go/freetype/raster" + "image" + "image/color" + "image/png" + "log" + "os" + "testing" +) + +var flattening_threshold float64 = 0.5 + +func savepng(filePath string, m image.Image) { + f, err := os.Create(filePath) + if err != nil { + log.Println(err) + os.Exit(1) + } + defer f.Close() + b := bufio.NewWriter(f) + err = png.Encode(b, m) + if err != nil { + log.Println(err) + os.Exit(1) + } + err = b.Flush() + if err != nil { + log.Println(err) + os.Exit(1) + } +} + +type Path struct { + points []float64 +} + +func (p *Path) LineTo(x, y float64) { + if len(p.points)+2 > cap(p.points) { + points := make([]float64, len(p.points)+2, len(p.points)+32) + copy(points, p.points) + p.points = points + } else { + p.points = p.points[0 : len(p.points)+2] + } + p.points[len(p.points)-2] = x + p.points[len(p.points)-1] = y +} + +func TestFreetype(t *testing.T) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := raster.NewRasterizer(200, 200) + rasterizer.UseNonZeroWinding = false + rasterizer.Start(raster.Point{raster.Fix32(10 * 256), raster.Fix32(190 * 256)}) + for j := 0; j < len(poly); j = j + 2 { + rasterizer.Add1(raster.Point{raster.Fix32(poly[j] * 256), raster.Fix32(poly[j+1] * 256)}) + } + painter := raster.NewRGBAPainter(img) + painter.SetColor(color) + rasterizer.Rasterize(painter) + + savepng("_testFreetype.png", img) +} + +func TestFreetypeNonZeroWinding(t *testing.T) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := raster.NewRasterizer(200, 200) + rasterizer.UseNonZeroWinding = true + rasterizer.Start(raster.Point{raster.Fix32(10 * 256), raster.Fix32(190 * 256)}) + for j := 0; j < len(poly); j = j + 2 { + rasterizer.Add1(raster.Point{raster.Fix32(poly[j] * 256), raster.Fix32(poly[j+1] * 256)}) + } + painter := raster.NewRGBAPainter(img) + painter.SetColor(color) + rasterizer.Rasterize(painter) + + savepng("_testFreetypeNonZeroWinding.png", img) +} + +func TestRasterizer(t *testing.T) { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + tr := [6]float64{1, 0, 0, 1, 0, 0} + r := NewRasterizer8BitsSample(200, 200) + //PolylineBresenham(img, image.Black, poly...) + + r.RenderEvenOdd(img, &color, &poly, tr) + savepng("_testRasterizer.png", img) +} + +func TestRasterizerNonZeroWinding(t *testing.T) { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + tr := [6]float64{1, 0, 0, 1, 0, 0} + r := NewRasterizer8BitsSample(200, 200) + //PolylineBresenham(img, image.Black, poly...) + + r.RenderNonZeroWinding(img, &color, &poly, tr) + savepng("_testRasterizerNonZeroWinding.png", img) +} + +func BenchmarkFreetype(b *testing.B) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + + for i := 0; i < b.N; i++ { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := raster.NewRasterizer(200, 200) + rasterizer.UseNonZeroWinding = false + rasterizer.Start(raster.Point{raster.Fix32(10 * 256), raster.Fix32(190 * 256)}) + for j := 0; j < len(poly); j = j + 2 { + rasterizer.Add1(raster.Point{raster.Fix32(poly[j] * 256), raster.Fix32(poly[j+1] * 256)}) + } + painter := raster.NewRGBAPainter(img) + painter.SetColor(color) + rasterizer.Rasterize(painter) + } +} +func BenchmarkFreetypeNonZeroWinding(b *testing.B) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + + for i := 0; i < b.N; i++ { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := raster.NewRasterizer(200, 200) + rasterizer.UseNonZeroWinding = true + rasterizer.Start(raster.Point{raster.Fix32(10 * 256), raster.Fix32(190 * 256)}) + for j := 0; j < len(poly); j = j + 2 { + rasterizer.Add1(raster.Point{raster.Fix32(poly[j] * 256), raster.Fix32(poly[j+1] * 256)}) + } + painter := raster.NewRGBAPainter(img) + painter.SetColor(color) + rasterizer.Rasterize(painter) + } +} + +func BenchmarkRasterizerNonZeroWinding(b *testing.B) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + tr := [6]float64{1, 0, 0, 1, 0, 0} + for i := 0; i < b.N; i++ { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := NewRasterizer8BitsSample(200, 200) + rasterizer.RenderNonZeroWinding(img, &color, &poly, tr) + } +} + +func BenchmarkRasterizer(b *testing.B) { + var p Path + p.LineTo(10, 190) + c := curve.CubicCurveFloat64{10, 190, 10, 10, 190, 10, 190, 190} + c.Segment(&p, flattening_threshold) + poly := Polygon(p.points) + color := color.RGBA{0, 0, 0, 0xff} + tr := [6]float64{1, 0, 0, 1, 0, 0} + for i := 0; i < b.N; i++ { + img := image.NewRGBA(image.Rect(0, 0, 200, 200)) + rasterizer := NewRasterizer8BitsSample(200, 200) + rasterizer.RenderEvenOdd(img, &color, &poly, tr) + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/rgba_interpolation.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/rgba_interpolation.go new file mode 100644 index 000000000..92534e7eb --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/rgba_interpolation.go @@ -0,0 +1,150 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff +// see http://pippin.gimp.org/image_processing/chap_resampling.html + +package draw2d + +import ( + "image" + "image/color" + "image/draw" + "math" +) + +type ImageFilter int + +const ( + LinearFilter ImageFilter = iota + BilinearFilter + BicubicFilter +) + +//see http://pippin.gimp.org/image_processing/chap_resampling.html +func getColorLinear(img image.Image, x, y float64) color.Color { + return img.At(int(x), int(y)) +} + +func getColorBilinear(img image.Image, x, y float64) color.Color { + x0 := math.Floor(x) + y0 := math.Floor(y) + dx := x - x0 + dy := y - y0 + + rt, gt, bt, at := img.At(int(x0), int(y0)).RGBA() + r0, g0, b0, a0 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = img.At(int(x0+1), int(y0)).RGBA() + r1, g1, b1, a1 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = img.At(int(x0+1), int(y0+1)).RGBA() + r2, g2, b2, a2 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = img.At(int(x0), int(y0+1)).RGBA() + r3, g3, b3, a3 := float64(rt), float64(gt), float64(bt), float64(at) + + r := int(lerp(lerp(r0, r1, dx), lerp(r3, r2, dx), dy)) + g := int(lerp(lerp(g0, g1, dx), lerp(g3, g2, dx), dy)) + b := int(lerp(lerp(b0, b1, dx), lerp(b3, b2, dx), dy)) + a := int(lerp(lerp(a0, a1, dx), lerp(a3, a2, dx), dy)) + return color.RGBA{uint8(r >> 8), uint8(g >> 8), uint8(b >> 8), uint8(a >> 8)} +} + +/** +-- LERP +-- /lerp/, vi.,n. +-- +-- Quasi-acronym for Linear Interpolation, used as a verb or noun for +-- the operation. "Bresenham's algorithm lerps incrementally between the +-- two endpoints of the line." (From Jargon File (4.4.4, 14 Aug 2003) +*/ +func lerp(v1, v2, ratio float64) float64 { + return v1*(1-ratio) + v2*ratio +} + +func getColorCubicRow(img image.Image, x, y, offset float64) color.Color { + c0 := img.At(int(x), int(y)) + c1 := img.At(int(x+1), int(y)) + c2 := img.At(int(x+2), int(y)) + c3 := img.At(int(x+3), int(y)) + rt, gt, bt, at := c0.RGBA() + r0, g0, b0, a0 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c1.RGBA() + r1, g1, b1, a1 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c2.RGBA() + r2, g2, b2, a2 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c3.RGBA() + r3, g3, b3, a3 := float64(rt), float64(gt), float64(bt), float64(at) + r, g, b, a := cubic(offset, r0, r1, r2, r3), cubic(offset, g0, g1, g2, g3), cubic(offset, b0, b1, b2, b3), cubic(offset, a0, a1, a2, a3) + return color.RGBA{uint8(r >> 8), uint8(g >> 8), uint8(b >> 8), uint8(a >> 8)} +} + +func getColorBicubic(img image.Image, x, y float64) color.Color { + x0 := math.Floor(x) + y0 := math.Floor(y) + dx := x - x0 + dy := y - y0 + c0 := getColorCubicRow(img, x0-1, y0-1, dx) + c1 := getColorCubicRow(img, x0-1, y0, dx) + c2 := getColorCubicRow(img, x0-1, y0+1, dx) + c3 := getColorCubicRow(img, x0-1, y0+2, dx) + rt, gt, bt, at := c0.RGBA() + r0, g0, b0, a0 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c1.RGBA() + r1, g1, b1, a1 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c2.RGBA() + r2, g2, b2, a2 := float64(rt), float64(gt), float64(bt), float64(at) + rt, gt, bt, at = c3.RGBA() + r3, g3, b3, a3 := float64(rt), float64(gt), float64(bt), float64(at) + r, g, b, a := cubic(dy, r0, r1, r2, r3), cubic(dy, g0, g1, g2, g3), cubic(dy, b0, b1, b2, b3), cubic(dy, a0, a1, a2, a3) + return color.RGBA{uint8(r >> 8), uint8(g >> 8), uint8(b >> 8), uint8(a >> 8)} +} + +func cubic(offset, v0, v1, v2, v3 float64) uint32 { + // offset is the offset of the sampled value between v1 and v2 + return uint32(((((-7*v0+21*v1-21*v2+7*v3)*offset+ + (15*v0-36*v1+27*v2-6*v3))*offset+ + (-9*v0+9*v2))*offset + (v0 + 16*v1 + v2)) / 18.0) +} + +func DrawImage(src image.Image, dest draw.Image, tr MatrixTransform, op draw.Op, filter ImageFilter) { + bounds := src.Bounds() + x0, y0, x1, y1 := float64(bounds.Min.X), float64(bounds.Min.Y), float64(bounds.Max.X), float64(bounds.Max.Y) + tr.TransformRectangle(&x0, &y0, &x1, &y1) + var x, y, u, v float64 + var c1, c2, cr color.Color + var r, g, b, a, ia, r1, g1, b1, a1, r2, g2, b2, a2 uint32 + var color color.RGBA + for x = x0; x < x1; x++ { + for y = y0; y < y1; y++ { + u = x + v = y + tr.InverseTransform(&u, &v) + if bounds.Min.X <= int(u) && bounds.Max.X > int(u) && bounds.Min.Y <= int(v) && bounds.Max.Y > int(v) { + c1 = dest.At(int(x), int(y)) + switch filter { + case LinearFilter: + c2 = src.At(int(u), int(v)) + case BilinearFilter: + c2 = getColorBilinear(src, u, v) + case BicubicFilter: + c2 = getColorBicubic(src, u, v) + } + switch op { + case draw.Over: + r1, g1, b1, a1 = c1.RGBA() + r2, g2, b2, a2 = c2.RGBA() + ia = M - a2 + r = ((r1 * ia) / M) + r2 + g = ((g1 * ia) / M) + g2 + b = ((b1 * ia) / M) + b2 + a = ((a1 * ia) / M) + a2 + color.R = uint8(r >> 8) + color.G = uint8(g >> 8) + color.B = uint8(b >> 8) + color.A = uint8(a >> 8) + cr = color + default: + cr = c2 + } + dest.Set(int(x), int(y), cr) + } + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stack_gc.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stack_gc.go new file mode 100644 index 000000000..b2cf63fc4 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stack_gc.go @@ -0,0 +1,208 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/truetype" + "image" + "image/color" +) + +type StackGraphicContext struct { + Current *ContextStack +} + +type ContextStack struct { + Tr MatrixTransform + Path *PathStorage + LineWidth float64 + Dash []float64 + DashOffset float64 + StrokeColor color.Color + FillColor color.Color + FillRule FillRule + Cap Cap + Join Join + FontSize float64 + FontData FontData + + font *truetype.Font + // fontSize and dpi are used to calculate scale. scale is the number of + // 26.6 fixed point units in 1 em. + scale int32 + + previous *ContextStack +} + +/** + * Create a new Graphic context from an image + */ +func NewStackGraphicContext() *StackGraphicContext { + gc := &StackGraphicContext{} + gc.Current = new(ContextStack) + gc.Current.Tr = NewIdentityMatrix() + gc.Current.Path = NewPathStorage() + gc.Current.LineWidth = 1.0 + gc.Current.StrokeColor = image.Black + gc.Current.FillColor = image.White + gc.Current.Cap = RoundCap + gc.Current.FillRule = FillRuleEvenOdd + gc.Current.Join = RoundJoin + gc.Current.FontSize = 10 + gc.Current.FontData = defaultFontData + return gc +} + +func (gc *StackGraphicContext) GetMatrixTransform() MatrixTransform { + return gc.Current.Tr +} + +func (gc *StackGraphicContext) SetMatrixTransform(Tr MatrixTransform) { + gc.Current.Tr = Tr +} + +func (gc *StackGraphicContext) ComposeMatrixTransform(Tr MatrixTransform) { + gc.Current.Tr = Tr.Multiply(gc.Current.Tr) +} + +func (gc *StackGraphicContext) Rotate(angle float64) { + gc.Current.Tr = NewRotationMatrix(angle).Multiply(gc.Current.Tr) +} + +func (gc *StackGraphicContext) Translate(tx, ty float64) { + gc.Current.Tr = NewTranslationMatrix(tx, ty).Multiply(gc.Current.Tr) +} + +func (gc *StackGraphicContext) Scale(sx, sy float64) { + gc.Current.Tr = NewScaleMatrix(sx, sy).Multiply(gc.Current.Tr) +} + +func (gc *StackGraphicContext) SetStrokeColor(c color.Color) { + gc.Current.StrokeColor = c +} + +func (gc *StackGraphicContext) SetFillColor(c color.Color) { + gc.Current.FillColor = c +} + +func (gc *StackGraphicContext) SetFillRule(f FillRule) { + gc.Current.FillRule = f +} + +func (gc *StackGraphicContext) SetLineWidth(LineWidth float64) { + gc.Current.LineWidth = LineWidth +} + +func (gc *StackGraphicContext) SetLineCap(Cap Cap) { + gc.Current.Cap = Cap +} + +func (gc *StackGraphicContext) SetLineJoin(Join Join) { + gc.Current.Join = Join +} + +func (gc *StackGraphicContext) SetLineDash(Dash []float64, DashOffset float64) { + gc.Current.Dash = Dash + gc.Current.DashOffset = DashOffset +} + +func (gc *StackGraphicContext) SetFontSize(FontSize float64) { + gc.Current.FontSize = FontSize +} + +func (gc *StackGraphicContext) GetFontSize() float64 { + return gc.Current.FontSize +} + +func (gc *StackGraphicContext) SetFontData(FontData FontData) { + gc.Current.FontData = FontData +} + +func (gc *StackGraphicContext) GetFontData() FontData { + return gc.Current.FontData +} + +func (gc *StackGraphicContext) BeginPath() { + gc.Current.Path.Clear() +} + +func (gc *StackGraphicContext) IsEmpty() bool { + return gc.Current.Path.IsEmpty() +} + +func (gc *StackGraphicContext) LastPoint() (float64, float64) { + return gc.Current.Path.LastPoint() +} + +func (gc *StackGraphicContext) MoveTo(x, y float64) { + gc.Current.Path.MoveTo(x, y) +} + +func (gc *StackGraphicContext) RMoveTo(dx, dy float64) { + gc.Current.Path.RMoveTo(dx, dy) +} + +func (gc *StackGraphicContext) LineTo(x, y float64) { + gc.Current.Path.LineTo(x, y) +} + +func (gc *StackGraphicContext) RLineTo(dx, dy float64) { + gc.Current.Path.RLineTo(dx, dy) +} + +func (gc *StackGraphicContext) QuadCurveTo(cx, cy, x, y float64) { + gc.Current.Path.QuadCurveTo(cx, cy, x, y) +} + +func (gc *StackGraphicContext) RQuadCurveTo(dcx, dcy, dx, dy float64) { + gc.Current.Path.RQuadCurveTo(dcx, dcy, dx, dy) +} + +func (gc *StackGraphicContext) CubicCurveTo(cx1, cy1, cx2, cy2, x, y float64) { + gc.Current.Path.CubicCurveTo(cx1, cy1, cx2, cy2, x, y) +} + +func (gc *StackGraphicContext) RCubicCurveTo(dcx1, dcy1, dcx2, dcy2, dx, dy float64) { + gc.Current.Path.RCubicCurveTo(dcx1, dcy1, dcx2, dcy2, dx, dy) +} + +func (gc *StackGraphicContext) ArcTo(cx, cy, rx, ry, startAngle, angle float64) { + gc.Current.Path.ArcTo(cx, cy, rx, ry, startAngle, angle) +} + +func (gc *StackGraphicContext) RArcTo(dcx, dcy, rx, ry, startAngle, angle float64) { + gc.Current.Path.RArcTo(dcx, dcy, rx, ry, startAngle, angle) +} + +func (gc *StackGraphicContext) Close() { + gc.Current.Path.Close() +} + +func (gc *StackGraphicContext) Save() { + context := new(ContextStack) + context.FontSize = gc.Current.FontSize + context.FontData = gc.Current.FontData + context.LineWidth = gc.Current.LineWidth + context.StrokeColor = gc.Current.StrokeColor + context.FillColor = gc.Current.FillColor + context.FillRule = gc.Current.FillRule + context.Dash = gc.Current.Dash + context.DashOffset = gc.Current.DashOffset + context.Cap = gc.Current.Cap + context.Join = gc.Current.Join + context.Path = gc.Current.Path.Copy() + context.font = gc.Current.font + context.scale = gc.Current.scale + copy(context.Tr[:], gc.Current.Tr[:]) + context.previous = gc.Current + gc.Current = context +} + +func (gc *StackGraphicContext) Restore() { + if gc.Current.previous != nil { + oldContext := gc.Current + gc.Current = gc.Current.previous + oldContext.previous = nil + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stroker.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stroker.go new file mode 100644 index 000000000..9331187f6 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/stroker.go @@ -0,0 +1,135 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 13/12/2010 by Laurent Le Goff + +package draw2d + +type Cap int + +const ( + RoundCap Cap = iota + ButtCap + SquareCap +) + +type Join int + +const ( + BevelJoin Join = iota + RoundJoin + MiterJoin +) + +type LineStroker struct { + Next VertexConverter + HalfLineWidth float64 + Cap Cap + Join Join + vertices []float64 + rewind []float64 + x, y, nx, ny float64 + command VertexCommand +} + +func NewLineStroker(c Cap, j Join, converter VertexConverter) *LineStroker { + l := new(LineStroker) + l.Next = converter + l.HalfLineWidth = 0.5 + l.vertices = make([]float64, 0, 256) + l.rewind = make([]float64, 0, 256) + l.Cap = c + l.Join = j + l.command = VertexNoCommand + return l +} + +func (l *LineStroker) NextCommand(command VertexCommand) { + l.command = command + if command == VertexStopCommand { + l.Next.NextCommand(VertexStartCommand) + for i, j := 0, 1; j < len(l.vertices); i, j = i+2, j+2 { + l.Next.Vertex(l.vertices[i], l.vertices[j]) + l.Next.NextCommand(VertexNoCommand) + } + for i, j := len(l.rewind)-2, len(l.rewind)-1; j > 0; i, j = i-2, j-2 { + l.Next.NextCommand(VertexNoCommand) + l.Next.Vertex(l.rewind[i], l.rewind[j]) + } + if len(l.vertices) > 1 { + l.Next.NextCommand(VertexNoCommand) + l.Next.Vertex(l.vertices[0], l.vertices[1]) + } + l.Next.NextCommand(VertexStopCommand) + // reinit vertices + l.vertices = l.vertices[0:0] + l.rewind = l.rewind[0:0] + l.x, l.y, l.nx, l.ny = 0, 0, 0, 0 + } +} + +func (l *LineStroker) Vertex(x, y float64) { + switch l.command { + case VertexNoCommand: + l.line(l.x, l.y, x, y) + case VertexJoinCommand: + l.joinLine(l.x, l.y, l.nx, l.ny, x, y) + case VertexStartCommand: + l.x, l.y = x, y + case VertexCloseCommand: + l.line(l.x, l.y, x, y) + l.joinLine(l.x, l.y, l.nx, l.ny, x, y) + l.closePolygon() + } + l.command = VertexNoCommand +} + +func (l *LineStroker) appendVertex(vertices ...float64) { + s := len(vertices) / 2 + if len(l.vertices)+s >= cap(l.vertices) { + v := make([]float64, len(l.vertices), cap(l.vertices)+128) + copy(v, l.vertices) + l.vertices = v + v = make([]float64, len(l.rewind), cap(l.rewind)+128) + copy(v, l.rewind) + l.rewind = v + } + + copy(l.vertices[len(l.vertices):len(l.vertices)+s], vertices[:s]) + l.vertices = l.vertices[0 : len(l.vertices)+s] + copy(l.rewind[len(l.rewind):len(l.rewind)+s], vertices[s:]) + l.rewind = l.rewind[0 : len(l.rewind)+s] + +} + +func (l *LineStroker) closePolygon() { + if len(l.vertices) > 1 { + l.appendVertex(l.vertices[0], l.vertices[1], l.rewind[0], l.rewind[1]) + } +} + +func (l *LineStroker) line(x1, y1, x2, y2 float64) { + dx := (x2 - x1) + dy := (y2 - y1) + d := vectorDistance(dx, dy) + if d != 0 { + nx := dy * l.HalfLineWidth / d + ny := -(dx * l.HalfLineWidth / d) + l.appendVertex(x1+nx, y1+ny, x2+nx, y2+ny, x1-nx, y1-ny, x2-nx, y2-ny) + l.x, l.y, l.nx, l.ny = x2, y2, nx, ny + } +} + +func (l *LineStroker) joinLine(x1, y1, nx1, ny1, x2, y2 float64) { + dx := (x2 - x1) + dy := (y2 - y1) + d := vectorDistance(dx, dy) + + if d != 0 { + nx := dy * l.HalfLineWidth / d + ny := -(dx * l.HalfLineWidth / d) + /* l.join(x1, y1, x1 + nx, y1 - ny, nx, ny, x1 + ny2, y1 + nx2, nx2, ny2) + l.join(x1, y1, x1 - ny1, y1 - nx1, nx1, ny1, x1 - ny2, y1 - nx2, nx2, ny2)*/ + + l.appendVertex(x1+nx, y1+ny, x2+nx, y2+ny, x1-nx, y1-ny, x2-nx, y2-ny) + l.x, l.y, l.nx, l.ny = x2, y2, nx, ny + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/transform.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/transform.go new file mode 100644 index 000000000..1d89bfa9b --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/transform.go @@ -0,0 +1,306 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +import ( + "code.google.com/p/freetype-go/freetype/raster" + "math" +) + +type MatrixTransform [6]float64 + +const ( + epsilon = 1e-6 +) + +func (tr MatrixTransform) Determinant() float64 { + return tr[0]*tr[3] - tr[1]*tr[2] +} + +func (tr MatrixTransform) Transform(points ...*float64) { + for i, j := 0, 1; j < len(points); i, j = i+2, j+2 { + x := *points[i] + y := *points[j] + *points[i] = x*tr[0] + y*tr[2] + tr[4] + *points[j] = x*tr[1] + y*tr[3] + tr[5] + } +} + +func (tr MatrixTransform) TransformArray(points []float64) { + for i, j := 0, 1; j < len(points); i, j = i+2, j+2 { + x := points[i] + y := points[j] + points[i] = x*tr[0] + y*tr[2] + tr[4] + points[j] = x*tr[1] + y*tr[3] + tr[5] + } +} + +func (tr MatrixTransform) TransformRectangle(x0, y0, x2, y2 *float64) { + x1 := *x2 + y1 := *y0 + x3 := *x0 + y3 := *y2 + tr.Transform(x0, y0, &x1, &y1, x2, y2, &x3, &y3) + *x0, x1 = minMax(*x0, x1) + *x2, x3 = minMax(*x2, x3) + *y0, y1 = minMax(*y0, y1) + *y2, y3 = minMax(*y2, y3) + + *x0 = min(*x0, *x2) + *y0 = min(*y0, *y2) + *x2 = max(x1, x3) + *y2 = max(y1, y3) +} + +func (tr MatrixTransform) TransformRasterPoint(points ...*raster.Point) { + for _, point := range points { + x := float64(point.X) / 256 + y := float64(point.Y) / 256 + point.X = raster.Fix32((x*tr[0] + y*tr[2] + tr[4]) * 256) + point.Y = raster.Fix32((x*tr[1] + y*tr[3] + tr[5]) * 256) + } +} + +func (tr MatrixTransform) InverseTransform(points ...*float64) { + d := tr.Determinant() // matrix determinant + for i, j := 0, 1; j < len(points); i, j = i+2, j+2 { + x := *points[i] + y := *points[j] + *points[i] = ((x-tr[4])*tr[3] - (y-tr[5])*tr[2]) / d + *points[j] = ((y-tr[5])*tr[0] - (x-tr[4])*tr[1]) / d + } +} + +// ******************** Vector transformations ******************** + +func (tr MatrixTransform) VectorTransform(points ...*float64) { + for i, j := 0, 1; j < len(points); i, j = i+2, j+2 { + x := *points[i] + y := *points[j] + *points[i] = x*tr[0] + y*tr[2] + *points[j] = x*tr[1] + y*tr[3] + } +} + +// ******************** Transformations creation ******************** + +/** Creates an identity transformation. */ +func NewIdentityMatrix() MatrixTransform { + return [6]float64{1, 0, 0, 1, 0, 0} +} + +/** + * Creates a transformation with a translation, that, + * transform point1 into point2. + */ +func NewTranslationMatrix(tx, ty float64) MatrixTransform { + return [6]float64{1, 0, 0, 1, tx, ty} +} + +/** + * Creates a transformation with a sx, sy scale factor + */ +func NewScaleMatrix(sx, sy float64) MatrixTransform { + return [6]float64{sx, 0, 0, sy, 0, 0} +} + +/** + * Creates a rotation transformation. + */ +func NewRotationMatrix(angle float64) MatrixTransform { + c := math.Cos(angle) + s := math.Sin(angle) + return [6]float64{c, s, -s, c, 0, 0} +} + +/** + * Creates a transformation, combining a scale and a translation, that transform rectangle1 into rectangle2. + */ +func NewMatrixTransform(rectangle1, rectangle2 [4]float64) MatrixTransform { + xScale := (rectangle2[2] - rectangle2[0]) / (rectangle1[2] - rectangle1[0]) + yScale := (rectangle2[3] - rectangle2[1]) / (rectangle1[3] - rectangle1[1]) + xOffset := rectangle2[0] - (rectangle1[0] * xScale) + yOffset := rectangle2[1] - (rectangle1[1] * yScale) + return [6]float64{xScale, 0, 0, yScale, xOffset, yOffset} +} + +// ******************** Transformations operations ******************** + +/** + * Returns a transformation that is the inverse of the given transformation. + */ +func (tr MatrixTransform) GetInverseTransformation() MatrixTransform { + d := tr.Determinant() // matrix determinant + return [6]float64{ + tr[3] / d, + -tr[1] / d, + -tr[2] / d, + tr[0] / d, + (tr[2]*tr[5] - tr[3]*tr[4]) / d, + (tr[1]*tr[4] - tr[0]*tr[5]) / d} +} + +func (tr1 MatrixTransform) Multiply(tr2 MatrixTransform) MatrixTransform { + return [6]float64{ + tr1[0]*tr2[0] + tr1[1]*tr2[2], + tr1[1]*tr2[3] + tr1[0]*tr2[1], + tr1[2]*tr2[0] + tr1[3]*tr2[2], + tr1[3]*tr2[3] + tr1[2]*tr2[1], + tr1[4]*tr2[0] + tr1[5]*tr2[2] + tr2[4], + tr1[5]*tr2[3] + tr1[4]*tr2[1] + tr2[5]} +} + +func (tr *MatrixTransform) Scale(sx, sy float64) *MatrixTransform { + tr[0] = sx * tr[0] + tr[1] = sx * tr[1] + tr[2] = sy * tr[2] + tr[3] = sy * tr[3] + return tr +} + +func (tr *MatrixTransform) Translate(tx, ty float64) *MatrixTransform { + tr[4] = tx*tr[0] + ty*tr[2] + tr[4] + tr[5] = ty*tr[3] + tx*tr[1] + tr[5] + return tr +} + +func (tr *MatrixTransform) Rotate(angle float64) *MatrixTransform { + c := math.Cos(angle) + s := math.Sin(angle) + t0 := c*tr[0] + s*tr[2] + t1 := s*tr[3] + c*tr[1] + t2 := c*tr[2] - s*tr[0] + t3 := c*tr[3] - s*tr[1] + tr[0] = t0 + tr[1] = t1 + tr[2] = t2 + tr[3] = t3 + return tr +} + +func (tr MatrixTransform) GetTranslation() (x, y float64) { + return tr[4], tr[5] +} + +func (tr MatrixTransform) GetScaling() (x, y float64) { + return tr[0], tr[3] +} + +func (tr MatrixTransform) GetScale() float64 { + x := 0.707106781*tr[0] + 0.707106781*tr[1] + y := 0.707106781*tr[2] + 0.707106781*tr[3] + return math.Sqrt(x*x + y*y) +} + +func (tr MatrixTransform) GetMaxAbsScaling() (s float64) { + sx := math.Abs(tr[0]) + sy := math.Abs(tr[3]) + if sx > sy { + return sx + } + return sy +} + +func (tr MatrixTransform) GetMinAbsScaling() (s float64) { + sx := math.Abs(tr[0]) + sy := math.Abs(tr[3]) + if sx > sy { + return sy + } + return sx +} + +// ******************** Testing ******************** + +/** + * Tests if a two transformation are equal. A tolerance is applied when + * comparing matrix elements. + */ +func (tr1 MatrixTransform) Equals(tr2 MatrixTransform) bool { + for i := 0; i < 6; i = i + 1 { + if !fequals(tr1[i], tr2[i]) { + return false + } + } + return true +} + +/** + * Tests if a transformation is the identity transformation. A tolerance + * is applied when comparing matrix elements. + */ +func (tr MatrixTransform) IsIdentity() bool { + return fequals(tr[4], 0) && fequals(tr[5], 0) && tr.IsTranslation() +} + +/** + * Tests if a transformation is is a pure translation. A tolerance + * is applied when comparing matrix elements. + */ +func (tr MatrixTransform) IsTranslation() bool { + return fequals(tr[0], 1) && fequals(tr[1], 0) && fequals(tr[2], 0) && fequals(tr[3], 1) +} + +/** + * Compares two floats. + * return true if the distance between the two floats is less than epsilon, false otherwise + */ +func fequals(float1, float2 float64) bool { + return math.Abs(float1-float2) <= epsilon +} + +// this VertexConverter apply the Matrix transformation tr +type VertexMatrixTransform struct { + tr MatrixTransform + Next VertexConverter +} + +func NewVertexMatrixTransform(tr MatrixTransform, converter VertexConverter) *VertexMatrixTransform { + return &VertexMatrixTransform{tr, converter} +} + +// Vertex Matrix Transform +func (vmt *VertexMatrixTransform) NextCommand(command VertexCommand) { + vmt.Next.NextCommand(command) +} + +func (vmt *VertexMatrixTransform) Vertex(x, y float64) { + u := x*vmt.tr[0] + y*vmt.tr[2] + vmt.tr[4] + v := x*vmt.tr[1] + y*vmt.tr[3] + vmt.tr[5] + vmt.Next.Vertex(u, v) +} + +// this adder apply a Matrix transformation to points +type MatrixTransformAdder struct { + tr MatrixTransform + next raster.Adder +} + +func NewMatrixTransformAdder(tr MatrixTransform, adder raster.Adder) *MatrixTransformAdder { + return &MatrixTransformAdder{tr, adder} +} + +// Start starts a new curve at the given point. +func (mta MatrixTransformAdder) Start(a raster.Point) { + mta.tr.TransformRasterPoint(&a) + mta.next.Start(a) +} + +// Add1 adds a linear segment to the current curve. +func (mta MatrixTransformAdder) Add1(b raster.Point) { + mta.tr.TransformRasterPoint(&b) + mta.next.Add1(b) +} + +// Add2 adds a quadratic segment to the current curve. +func (mta MatrixTransformAdder) Add2(b, c raster.Point) { + mta.tr.TransformRasterPoint(&b, &c) + mta.next.Add2(b, c) +} + +// Add3 adds a cubic segment to the current curve. +func (mta MatrixTransformAdder) Add3(b, c, d raster.Point) { + mta.tr.TransformRasterPoint(&b, &c, &d) + mta.next.Add3(b, c, d) +} diff --git a/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/vertex2d.go b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/vertex2d.go new file mode 100644 index 000000000..4e4d4fd83 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/draw2d/draw2d/vertex2d.go @@ -0,0 +1,19 @@ +// Copyright 2010 The draw2d Authors. All rights reserved. +// created: 21/11/2010 by Laurent Le Goff + +package draw2d + +type VertexCommand byte + +const ( + VertexNoCommand VertexCommand = iota + VertexStartCommand + VertexJoinCommand + VertexCloseCommand + VertexStopCommand +) + +type VertexConverter interface { + NextCommand(cmd VertexCommand) + Vertex(x, y float64) +} |