1// Copyright 2010 The draw2d Authors. All rights reserved. 2// created: 17/05/2011 by Laurent Le Goff 3 4package draw2dbase 5 6import ( 7 "math" 8) 9 10const ( 11 // CurveRecursionLimit represents the maximum recursion that is really necessary to subsivide a curve into straight lines 12 CurveRecursionLimit = 32 13) 14 15// Cubic 16// x1, y1, cpx1, cpy1, cpx2, cpy2, x2, y2 float64 17 18// SubdivideCubic a Bezier cubic curve in 2 equivalents Bezier cubic curves. 19// c1 and c2 parameters are the resulting curves 20func SubdivideCubic(c, c1, c2 []float64) { 21 // First point of c is the first point of c1 22 c1[0], c1[1] = c[0], c[1] 23 // Last point of c is the last point of c2 24 c2[6], c2[7] = c[6], c[7] 25 26 // Subdivide segment using midpoints 27 c1[2] = (c[0] + c[2]) / 2 28 c1[3] = (c[1] + c[3]) / 2 29 30 midX := (c[2] + c[4]) / 2 31 midY := (c[3] + c[5]) / 2 32 33 c2[4] = (c[4] + c[6]) / 2 34 c2[5] = (c[5] + c[7]) / 2 35 36 c1[4] = (c1[2] + midX) / 2 37 c1[5] = (c1[3] + midY) / 2 38 39 c2[2] = (midX + c2[4]) / 2 40 c2[3] = (midY + c2[5]) / 2 41 42 c1[6] = (c1[4] + c2[2]) / 2 43 c1[7] = (c1[5] + c2[3]) / 2 44 45 // Last Point of c1 is equal to the first point of c2 46 c2[0], c2[1] = c1[6], c1[7] 47} 48 49// TraceCubic generate lines subdividing the cubic curve using a Liner 50// flattening_threshold helps determines the flattening expectation of the curve 51func TraceCubic(t Liner, cubic []float64, flatteningThreshold float64) { 52 // Allocation curves 53 var curves [CurveRecursionLimit * 8]float64 54 copy(curves[0:8], cubic[0:8]) 55 i := 0 56 57 // current curve 58 var c []float64 59 60 var dx, dy, d2, d3 float64 61 62 for i >= 0 { 63 c = curves[i*8:] 64 dx = c[6] - c[0] 65 dy = c[7] - c[1] 66 67 d2 = math.Abs((c[2]-c[6])*dy - (c[3]-c[7])*dx) 68 d3 = math.Abs((c[4]-c[6])*dy - (c[5]-c[7])*dx) 69 70 // if it's flat then trace a line 71 if (d2+d3)*(d2+d3) < flatteningThreshold*(dx*dx+dy*dy) || i == len(curves)-1 { 72 t.LineTo(c[6], c[7]) 73 i-- 74 } else { 75 // second half of bezier go lower onto the stack 76 SubdivideCubic(c, curves[(i+1)*8:], curves[i*8:]) 77 i++ 78 } 79 } 80} 81 82// Quad 83// x1, y1, cpx1, cpy2, x2, y2 float64 84 85// SubdivideQuad a Bezier quad curve in 2 equivalents Bezier quad curves. 86// c1 and c2 parameters are the resulting curves 87func SubdivideQuad(c, c1, c2 []float64) { 88 // First point of c is the first point of c1 89 c1[0], c1[1] = c[0], c[1] 90 // Last point of c is the last point of c2 91 c2[4], c2[5] = c[4], c[5] 92 93 // Subdivide segment using midpoints 94 c1[2] = (c[0] + c[2]) / 2 95 c1[3] = (c[1] + c[3]) / 2 96 c2[2] = (c[2] + c[4]) / 2 97 c2[3] = (c[3] + c[5]) / 2 98 c1[4] = (c1[2] + c2[2]) / 2 99 c1[5] = (c1[3] + c2[3]) / 2 100 c2[0], c2[1] = c1[4], c1[5] 101 return 102} 103 104// TraceQuad generate lines subdividing the curve using a Liner 105// flattening_threshold helps determines the flattening expectation of the curve 106func TraceQuad(t Liner, quad []float64, flatteningThreshold float64) { 107 // Allocates curves stack 108 var curves [CurveRecursionLimit * 6]float64 109 copy(curves[0:6], quad[0:6]) 110 i := 0 111 // current curve 112 var c []float64 113 var dx, dy, d float64 114 115 for i >= 0 { 116 c = curves[i*6:] 117 dx = c[4] - c[0] 118 dy = c[5] - c[1] 119 120 d = math.Abs(((c[2]-c[4])*dy - (c[3]-c[5])*dx)) 121 122 // if it's flat then trace a line 123 if (d*d) < flatteningThreshold*(dx*dx+dy*dy) || i == len(curves)-1 { 124 t.LineTo(c[4], c[5]) 125 i-- 126 } else { 127 // second half of bezier go lower onto the stack 128 SubdivideQuad(c, curves[(i+1)*6:], curves[i*6:]) 129 i++ 130 } 131 } 132} 133 134// TraceArc trace an arc using a Liner 135func TraceArc(t Liner, x, y, rx, ry, start, angle, scale float64) (lastX, lastY float64) { 136 end := start + angle 137 clockWise := true 138 if angle < 0 { 139 clockWise = false 140 } 141 ra := (math.Abs(rx) + math.Abs(ry)) / 2 142 da := math.Acos(ra/(ra+0.125/scale)) * 2 143 //normalize 144 if !clockWise { 145 da = -da 146 } 147 angle = start + da 148 var curX, curY float64 149 for { 150 if (angle < end-da/4) != clockWise { 151 curX = x + math.Cos(end)*rx 152 curY = y + math.Sin(end)*ry 153 return curX, curY 154 } 155 curX = x + math.Cos(angle)*rx 156 curY = y + math.Sin(angle)*ry 157 158 angle += da 159 t.LineTo(curX, curY) 160 } 161} 162