1/*
2
3LinePathBuilder
4
5Copyright (c) 2002 OpenBeOS.
6
7Author:
8	Michael Pfeiffer
9
10Permission is hereby granted, free of charge, to any person obtaining a copy of
11this software and associated documentation files (the "Software"), to deal in
12the Software without restriction, including without limitation the rights to
13use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
14of the Software, and to permit persons to whom the Software is furnished to do
15so, subject to the following conditions:
16
17The above copyright notice and this permission notice shall be included in all
18copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
23AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
26THE SOFTWARE.
27
28*/
29
30#include <math.h>
31#include "LinePathBuilder.h"
32
33#include <math.h>
34
35static const float kNearZero   = 0.000000000001;
36static const float kMinPenSize = 0.0001;
37
38LinePathBuilder::LinePathBuilder(SubPath *subPath, float penSize, cap_mode capMode, join_mode joinMode, float miterLimit)
39	: fSubPath(subPath)
40	, fPenSize(penSize)
41	, fCapMode(capMode)
42	, fJoinMode(joinMode)
43	, fMiterLimit(miterLimit)
44	, fFirst(true)
45{
46}
47
48
49// vector of length w/2 in direction of line [a, b]
50bool
51LinePathBuilder::Vector(BPoint a, BPoint b, float w, BPoint &v)
52{
53	v = b - a;
54	float l = 2.0 * sqrt(v.x * v.x + v.y * v.y);
55	if (fabs(l) <= kNearZero) return false;
56	w /= l;
57	v.x *= w;
58	v.y *= w;
59	return true;
60}
61
62
63// calculate line [pa, pb] parallel to line [a, b] in distance of w/2
64bool
65LinePathBuilder::Parallel(BPoint a, BPoint b, float w, BPoint &pa, BPoint &pb)
66{
67	BPoint d;
68	if (!Vector(a, b, w, d)) return false;
69	BPoint r(-d.y, d.x);
70
71	pa = a - r;
72	pb = b - r;
73	return true;
74}
75
76
77// calculate intercept point e of lines [a, b] and [c, d]
78bool
79LinePathBuilder::Cut(BPoint a, BPoint b, BPoint c, BPoint d, BPoint &e)
80{
81	BPoint r = b - a;
82	BPoint s = d - c;
83	BPoint v = c - a;
84	float div = r.x * s.y - r.y * s.x;
85	if (fabs(div) <= kNearZero) return false;
86	float u = (r.y * v.x - r.x * v.y) / div;
87	e.x = c.x + s.x * u;
88	e.y = c.y + s.y * u;
89	return true;
90}
91
92
93void
94LinePathBuilder::RoundCap(BPoint a, BPoint b, BPoint ra, BPoint rb, bool start)
95{
96	BPoint bezier[3];
97	BPoint v;
98	if (start) { // first quarter circle
99		Vector(b, a, PenSize(), v);
100		BPoint v055(0.55*v.x, 0.55*v.y);
101		BPoint vr055(-v.y, v.x);
102		bezier[0] = a + v + vr055;
103		bezier[1] = ra + v055;
104		bezier[2] = ra;
105		AddPoint(a+v);
106		BezierTo(bezier);
107	} else { // second quarter circle
108		Vector(a, b, PenSize(), v);
109		BPoint v055(0.55*v.x, 0.55*v.y);
110		BPoint vr055(v.y, -v.x);
111		bezier[0] = rb + v055;
112		bezier[1] = b + v + vr055;
113		bezier[2] = b + v;
114		AddPoint(rb);
115		BezierTo(bezier);
116	}
117}
118
119
120void
121LinePathBuilder::Corner(BPoint a, BPoint b, bool start)
122{
123	BPoint ra, rb, r;
124	if (Parallel(a, b, PenSize(), ra, rb)) {
125		BPoint v;
126		switch (LineCapMode()) {
127			case B_ROUND_CAP:
128				RoundCap(a, b, ra, rb, start);
129				return;
130			case B_BUTT_CAP: // nothing to do
131				break;
132			case B_SQUARE_CAP:
133				Vector(a, b, PenSize(), v);
134				ra -= v;
135				rb += v;
136				break;
137		}
138		if (start) r = ra; else r = rb;
139		AddPoint(r);
140	}
141}
142
143
144bool
145LinePathBuilder::Inside(BPoint a, BPoint b, BPoint r)
146{
147	BPoint v;
148	Vector(a, b, 2.0, v);
149
150	if (kNearZero <= fabs(v.x)) return (r.x - b.x) / v.x <= 0.0;
151	else if (kNearZero <= fabs(v.y)) return (r.y - b.y) / v.y <= 0.0;
152	else return false; // should not reach here (length of v > 0.0!)
153}
154
155
156bool
157LinePathBuilder::InMiterLimit(BPoint a, BPoint b)
158{
159	BPoint d = a - b;
160	return 2.0*sqrt(d.x*d.x + d.y*d.y)/PenSize() <= LineMiterLimit();
161}
162
163
164void
165LinePathBuilder::RoundJoin(BPoint p[4])
166{
167	BPoint v[2];
168	Vector(p[0], p[1], PenSize() * 0.63, v[0]);
169	Vector(p[3], p[2], PenSize() * 0.63, v[1]);
170	AddPoint(p[1]);
171	BPoint bezier[3] = {p[1]+v[0], p[2]+v[1], p[2] };
172	BezierTo(bezier);
173}
174
175
176void
177LinePathBuilder::Connect(BPoint a, BPoint b, BPoint c)
178{
179	BPoint p[4], r, v;
180	if (Parallel(a, b, PenSize(), p[0], p[1]) &&
181		Parallel(b, c, PenSize(), p[2], p[3]) &&
182		Cut(p[0], p[1], p[2], p[3], r)) {
183
184
185
186		if (LineJoinMode() != B_BUTT_JOIN &&
187			LineJoinMode() != B_SQUARE_JOIN &&
188			Inside(p[0], p[1], r)) {
189			if (!Inside(p[1], p[0], r) || !Inside(p[2], p[3], r)) {
190				AddPoint(p[1]); AddPoint(p[2]);
191			} else {
192				AddPoint(r);
193			}
194			return;
195		}
196
197		switch (LineJoinMode()) {
198			case B_ROUND_JOIN:
199				RoundJoin(p);
200				break;
201			case B_MITER_JOIN:
202				if (InMiterLimit(b, r)) {
203					AddPoint(r);
204					break;
205				}
206				// fall through
207			case B_BEVEL_JOIN:
208				AddPoint(p[1]); AddPoint(p[2]);
209				break;
210			case B_BUTT_JOIN: // ???
211				AddPoint(p[1]); AddPoint(b); AddPoint(p[2]);
212				break;
213			case B_SQUARE_JOIN: // ???
214				Vector(a, b, PenSize(), v);
215				AddPoint(p[1] + v); AddPoint(b + v);
216				Vector(b, c, PenSize(), v);
217				AddPoint(b - v); AddPoint(p[2] - v);
218				break;
219		}
220	}
221}
222
223
224bool
225LinePathBuilder::IdenticalPoints(int i, int j)
226{
227	BPoint d = fSubPath->PointAt(i) - fSubPath->PointAt(j);
228	return d.x * d.x + d.y * d.y < kNearZero;
229}
230
231
232// remove identical points
233void
234LinePathBuilder::OptimizeSubPath()
235{
236	int i, j = 0;
237	const int n = fSubPath->CountPoints();
238	for (i = 1; i < n; i++) {
239		if (!IdenticalPoints(i, j)) {
240			fSubPath->AtPut(++j, fSubPath->PointAt(i));
241		}
242	}
243	fSubPath->Truncate(i-j-1);
244
245	// check also first point == last point if path is closed
246	if (fSubPath->IsClosed() && fSubPath->CountPoints() >= 2) {
247		const int n = fSubPath->CountPoints()-1;
248		if (IdenticalPoints(0, n)) fSubPath->Truncate(1);
249	}
250}
251
252
253BPoint
254LinePathBuilder::PointAt(int i)
255{
256	const int n = fSubPath->CountPoints();
257	return fSubPath->PointAt((i+n) % n);
258}
259
260
261void
262LinePathBuilder::AddPoint(BPoint p)
263{
264	if (fFirst) {
265		fFirst = false;
266		MoveTo(p);
267	} else {
268		LineTo(p);
269	}
270}
271
272
273void
274LinePathBuilder::CreateLinePath()
275{
276	OptimizeSubPath();
277	if (fPenSize < kMinPenSize) fPenSize = kMinPenSize;
278
279	const bool start = true;
280	const bool end = false;
281	const int n = fSubPath->CountPoints();
282
283	if (n < 2) return;
284
285	bool is_closed = fSubPath->IsClosed() && n != 2;
286
287	if (fSubPath->IsClosed() && n == 2) {
288		switch (LineJoinMode()) {
289			case B_ROUND_JOIN:
290				fCapMode = B_ROUND_CAP;
291				break;
292			case B_MITER_JOIN: // fall through
293			case B_BEVEL_JOIN: // fall through
294			case B_BUTT_JOIN:
295				fCapMode = B_BUTT_CAP;
296				break;
297			case B_SQUARE_JOIN:
298				fCapMode = B_SQUARE_CAP;
299				break;
300		}
301	}
302
303	// ahead
304	if (is_closed) {
305		Connect(PointAt(n-1), PointAt(0), PointAt(1));
306	} else {
307		Corner(PointAt(0), PointAt(1), start);
308	}
309
310	for (int i = 1; i < n-1; i++) {
311		Connect(PointAt(i-1), PointAt(i), PointAt(i+1));
312	}
313
314	if (is_closed) {
315		Connect(PointAt(n-2), PointAt(n-1), PointAt(n));
316		Connect(PointAt(n-1), PointAt(n), PointAt(n+1));
317	} else {
318		Corner(PointAt(n-2), PointAt(n-1), end);
319	}
320
321	// and back
322	if (is_closed) {
323		ClosePath(); fFirst = true;
324		Connect(PointAt(n+1), PointAt(n), PointAt(n-1));
325		Connect(PointAt(n), PointAt(n-1), PointAt(n-2));
326	} else {
327		Corner(PointAt(n-1), PointAt(n-2), start);
328	}
329
330	for (int i = n-2; i >= 1; i--) {
331		Connect(PointAt(i+1), PointAt(i), PointAt(i-1));
332	}
333
334	if (is_closed) {
335		Connect(PointAt(1), PointAt(0), PointAt(n-1));
336	} else {
337		Corner(PointAt(1), PointAt(0), end);
338	}
339	ClosePath();
340}
341
342