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