Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : : #include <basegfx/curve/b2dcubicbezier.hxx>
30 : : #include <basegfx/vector/b2dvector.hxx>
31 : : #include <basegfx/polygon/b2dpolygon.hxx>
32 : : #include <basegfx/numeric/ftools.hxx>
33 : :
34 : : #include <limits>
35 : :
36 : : // #i37443#
37 : : #define FACTOR_FOR_UNSHARPEN (1.6)
38 : : #ifdef DBG_UTIL
39 : : static double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN;
40 : : #endif
41 : :
42 : : //////////////////////////////////////////////////////////////////////////////
43 : :
44 : : namespace basegfx
45 : : {
46 : : namespace
47 : : {
48 : 3000 : void ImpSubDivAngle(
49 : : const B2DPoint& rfPA, // start point
50 : : const B2DPoint& rfEA, // edge on A
51 : : const B2DPoint& rfEB, // edge on B
52 : : const B2DPoint& rfPB, // end point
53 : : B2DPolygon& rTarget, // target polygon
54 : : double fAngleBound, // angle bound in [0.0 .. 2PI]
55 : : bool bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions
56 : : sal_uInt16 nMaxRecursionDepth) // endless loop protection
57 : : {
58 [ + - ]: 3000 : if(nMaxRecursionDepth)
59 : : {
60 : : // do angle test
61 : 3000 : B2DVector aLeft(rfEA - rfPA);
62 : 3000 : B2DVector aRight(rfEB - rfPB);
63 : :
64 : : // #i72104#
65 [ - + ][ + - ]: 3000 : if(aLeft.equalZero())
66 : : {
67 [ # # ]: 0 : aLeft = rfEB - rfPA;
68 : : }
69 : :
70 [ + - ][ - + ]: 3000 : if(aRight.equalZero())
71 : : {
72 [ # # ]: 0 : aRight = rfEA - rfPB;
73 : : }
74 : :
75 [ + - ]: 3000 : const double fCurrentAngle(aLeft.angle(aRight));
76 : :
77 [ + + ]: 3000 : if(fabs(fCurrentAngle) > (F_PI - fAngleBound))
78 : : {
79 : : // end recursion
80 : 1600 : nMaxRecursionDepth = 0;
81 : : }
82 : : else
83 : : {
84 [ + - ]: 1400 : if(bAllowUnsharpen)
85 : : {
86 : : // #i37443# unsharpen criteria
87 : : #ifdef DBG_UTIL
88 : : fAngleBound *= fMultFactUnsharpen;
89 : : #else
90 : 1400 : fAngleBound *= FACTOR_FOR_UNSHARPEN;
91 : : #endif
92 : : }
93 : 3000 : }
94 : : }
95 : :
96 [ + + ]: 3000 : if(nMaxRecursionDepth)
97 : : {
98 : : // divide at 0.5
99 : 1400 : const B2DPoint aS1L(average(rfPA, rfEA));
100 : 1400 : const B2DPoint aS1C(average(rfEA, rfEB));
101 : 1400 : const B2DPoint aS1R(average(rfEB, rfPB));
102 : 1400 : const B2DPoint aS2L(average(aS1L, aS1C));
103 : 1400 : const B2DPoint aS2R(average(aS1C, aS1R));
104 : 1400 : const B2DPoint aS3C(average(aS2L, aS2R));
105 : :
106 : : // left recursion
107 [ + - ]: 1400 : ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
108 : :
109 : : // right recursion
110 [ + - ]: 1400 : ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
111 : : }
112 : : else
113 : : {
114 : 1600 : rTarget.append(rfPB);
115 : : }
116 : 3000 : }
117 : :
118 : 100 : void ImpSubDivAngleStart(
119 : : const B2DPoint& rfPA, // start point
120 : : const B2DPoint& rfEA, // edge on A
121 : : const B2DPoint& rfEB, // edge on B
122 : : const B2DPoint& rfPB, // end point
123 : : B2DPolygon& rTarget, // target polygon
124 : : const double& rfAngleBound, // angle bound in [0.0 .. 2PI]
125 : : bool bAllowUnsharpen) // #i37443# allow the criteria to get unsharp in recursions
126 : : {
127 : 100 : sal_uInt16 nMaxRecursionDepth(8);
128 : 100 : const B2DVector aLeft(rfEA - rfPA);
129 : 100 : const B2DVector aRight(rfEB - rfPB);
130 [ + - ]: 100 : bool bLeftEqualZero(aLeft.equalZero());
131 [ + - ]: 100 : bool bRightEqualZero(aRight.equalZero());
132 : 100 : bool bAllParallel(false);
133 : :
134 [ - + ][ # # ]: 100 : if(bLeftEqualZero && bRightEqualZero)
135 : : {
136 : 0 : nMaxRecursionDepth = 0;
137 : : }
138 : : else
139 : : {
140 : 100 : const B2DVector aBase(rfPB - rfPA);
141 [ + - ]: 100 : const bool bBaseEqualZero(aBase.equalZero()); // #i72104#
142 : :
143 [ + - ]: 100 : if(!bBaseEqualZero)
144 : : {
145 [ - + ][ + - ]: 100 : const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase));
146 [ - + ][ + - ]: 100 : const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase));
147 : :
148 [ - + ][ # # ]: 100 : if(bLeftParallel && bRightParallel)
149 : : {
150 : 0 : bAllParallel = true;
151 : :
152 [ # # ]: 0 : if(!bLeftEqualZero)
153 : : {
154 : : double fFactor;
155 : :
156 [ # # ]: 0 : if(fabs(aBase.getX()) > fabs(aBase.getY()))
157 : : {
158 : 0 : fFactor = aLeft.getX() / aBase.getX();
159 : : }
160 : : else
161 : : {
162 : 0 : fFactor = aLeft.getY() / aBase.getY();
163 : : }
164 : :
165 [ # # ][ # # ]: 0 : if(fFactor >= 0.0 && fFactor <= 1.0)
166 : : {
167 : 0 : bLeftEqualZero = true;
168 : : }
169 : : }
170 : :
171 [ # # ]: 0 : if(!bRightEqualZero)
172 : : {
173 : : double fFactor;
174 : :
175 [ # # ]: 0 : if(fabs(aBase.getX()) > fabs(aBase.getY()))
176 : : {
177 : 0 : fFactor = aRight.getX() / -aBase.getX();
178 : : }
179 : : else
180 : : {
181 : 0 : fFactor = aRight.getY() / -aBase.getY();
182 : : }
183 : :
184 [ # # ][ # # ]: 0 : if(fFactor >= 0.0 && fFactor <= 1.0)
185 : : {
186 : 0 : bRightEqualZero = true;
187 : : }
188 : : }
189 : :
190 [ # # ][ # # ]: 0 : if(bLeftEqualZero && bRightEqualZero)
191 : : {
192 : 0 : nMaxRecursionDepth = 0;
193 : : }
194 : : }
195 : 100 : }
196 : : }
197 : :
198 [ + - ]: 100 : if(nMaxRecursionDepth)
199 : : {
200 : : // divide at 0.5 ad test both edges for angle criteria
201 : 100 : const B2DPoint aS1L(average(rfPA, rfEA));
202 : 100 : const B2DPoint aS1C(average(rfEA, rfEB));
203 : 100 : const B2DPoint aS1R(average(rfEB, rfPB));
204 : 100 : const B2DPoint aS2L(average(aS1L, aS1C));
205 : 100 : const B2DPoint aS2R(average(aS1C, aS1R));
206 : 100 : const B2DPoint aS3C(average(aS2L, aS2R));
207 : :
208 : : // test left
209 [ # # ][ - + ]: 100 : bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
210 [ + - ]: 100 : if(!bAngleIsSmallerLeft)
211 : : {
212 [ - + ]: 100 : const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
213 : 100 : const B2DVector aRightLeft(aS2L - aS3C);
214 [ + - ]: 100 : const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
215 : 100 : bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound));
216 : : }
217 : :
218 : : // test right
219 [ - + ][ # # ]: 100 : bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
220 [ + - ]: 100 : if(!bAngleIsSmallerRight)
221 : : {
222 : 100 : const B2DVector aLeftRight(aS2R - aS3C);
223 [ - + ]: 100 : const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
224 [ + - ]: 100 : const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
225 : 100 : bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound));
226 : : }
227 : :
228 [ - + ][ # # ]: 100 : if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
229 : : {
230 : : // no recursion necessary at all
231 : 0 : nMaxRecursionDepth = 0;
232 : : }
233 : : else
234 : : {
235 : : // left
236 [ - + ]: 100 : if(bAngleIsSmallerLeft)
237 : : {
238 [ # # ]: 0 : rTarget.append(aS3C);
239 : : }
240 : : else
241 : : {
242 [ + - ]: 100 : ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
243 : : }
244 : :
245 : : // right
246 [ - + ]: 100 : if(bAngleIsSmallerRight)
247 : : {
248 [ # # ]: 0 : rTarget.append(rfPB);
249 : : }
250 : : else
251 : : {
252 [ + - ]: 100 : ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
253 : : }
254 : 100 : }
255 : : }
256 : :
257 [ - + ]: 100 : if(!nMaxRecursionDepth)
258 : : {
259 [ # # ]: 0 : rTarget.append(rfPB);
260 : 100 : }
261 : 100 : }
262 : :
263 : 0 : void ImpSubDivDistance(
264 : : const B2DPoint& rfPA, // start point
265 : : const B2DPoint& rfEA, // edge on A
266 : : const B2DPoint& rfEB, // edge on B
267 : : const B2DPoint& rfPB, // end point
268 : : B2DPolygon& rTarget, // target polygon
269 : : double fDistanceBound2, // quadratic distance criteria
270 : : double fLastDistanceError2, // the last quadratic distance error
271 : : sal_uInt16 nMaxRecursionDepth) // endless loop protection
272 : : {
273 [ # # ]: 0 : if(nMaxRecursionDepth)
274 : : {
275 : : // decide if another recursion is needed. If not, set
276 : : // nMaxRecursionDepth to zero
277 : :
278 : : // Perform bezier flatness test (lecture notes from R. Schaback,
279 : : // Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
280 : : //
281 : : // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)||
282 : : // 0<=j<=n
283 : : //
284 : : // What is calculated here is an upper bound to the distance from
285 : : // a line through b_0 and b_3 (rfPA and P4 in our notation) and the
286 : : // curve. We can drop 0 and n from the running indices, since the
287 : : // argument of max becomes zero for those cases.
288 : 0 : const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
289 : 0 : const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
290 : 0 : const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
291 : 0 : const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
292 [ # # ]: 0 : const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y));
293 : :
294 : : // stop if error measure does not improve anymore. This is a
295 : : // safety guard against floating point inaccuracies.
296 : : // stop if distance from line is guaranteed to be bounded by d
297 [ # # ][ # # ]: 0 : const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);
298 : :
299 [ # # ]: 0 : if(bFurtherDivision)
300 : : {
301 : : // remember last error value
302 : 0 : fLastDistanceError2 = fDistanceError2;
303 : : }
304 : : else
305 : : {
306 : : // stop recustion
307 : 0 : nMaxRecursionDepth = 0;
308 : : }
309 : : }
310 : :
311 [ # # ]: 0 : if(nMaxRecursionDepth)
312 : : {
313 : : // divide at 0.5
314 : 0 : const B2DPoint aS1L(average(rfPA, rfEA));
315 : 0 : const B2DPoint aS1C(average(rfEA, rfEB));
316 : 0 : const B2DPoint aS1R(average(rfEB, rfPB));
317 : 0 : const B2DPoint aS2L(average(aS1L, aS1C));
318 : 0 : const B2DPoint aS2R(average(aS1C, aS1R));
319 : 0 : const B2DPoint aS3C(average(aS2L, aS2R));
320 : :
321 : : // left recursion
322 [ # # ]: 0 : ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
323 : :
324 : : // right recursion
325 [ # # ]: 0 : ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
326 : : }
327 : : else
328 : : {
329 : 0 : rTarget.append(rfPB);
330 : : }
331 : 0 : }
332 : : } // end of anonymous namespace
333 : : } // end of namespace basegfx
334 : :
335 : : //////////////////////////////////////////////////////////////////////////////
336 : :
337 : : namespace basegfx
338 : : {
339 : 0 : B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier)
340 : : : maStartPoint(rBezier.maStartPoint),
341 : : maEndPoint(rBezier.maEndPoint),
342 : : maControlPointA(rBezier.maControlPointA),
343 : 0 : maControlPointB(rBezier.maControlPointB)
344 : : {
345 : 0 : }
346 : :
347 : 35660 : B2DCubicBezier::B2DCubicBezier()
348 : : {
349 : 35660 : }
350 : :
351 : 230 : B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
352 : : : maStartPoint(rStart),
353 : : maEndPoint(rEnd),
354 : : maControlPointA(rControlPointA),
355 : 230 : maControlPointB(rControlPointB)
356 : : {
357 : 230 : }
358 : :
359 : 35890 : B2DCubicBezier::~B2DCubicBezier()
360 : : {
361 : 35890 : }
362 : :
363 : : // assignment operator
364 : 1540 : B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier)
365 : : {
366 : 1540 : maStartPoint = rBezier.maStartPoint;
367 : 1540 : maEndPoint = rBezier.maEndPoint;
368 : 1540 : maControlPointA = rBezier.maControlPointA;
369 : 1540 : maControlPointB = rBezier.maControlPointB;
370 : :
371 : 1540 : return *this;
372 : : }
373 : :
374 : : // compare operators
375 : 0 : bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
376 : : {
377 : : return (
378 : 0 : maStartPoint == rBezier.maStartPoint
379 : 0 : && maEndPoint == rBezier.maEndPoint
380 : 0 : && maControlPointA == rBezier.maControlPointA
381 : 0 : && maControlPointB == rBezier.maControlPointB
382 [ # # # # : 0 : );
# # # # ]
383 : : }
384 : :
385 : 0 : bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const
386 : : {
387 : : return (
388 : 0 : maStartPoint != rBezier.maStartPoint
389 : 0 : || maEndPoint != rBezier.maEndPoint
390 : 0 : || maControlPointA != rBezier.maControlPointA
391 : 0 : || maControlPointB != rBezier.maControlPointB
392 [ # # # # : 0 : );
# # # # ]
393 : : }
394 : :
395 : 165 : bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
396 : : {
397 : : return (
398 : 165 : maStartPoint.equal(rBezier.maStartPoint)
399 : 165 : && maEndPoint.equal(rBezier.maEndPoint)
400 : 65 : && maControlPointA.equal(rBezier.maControlPointA)
401 : 65 : && maControlPointB.equal(rBezier.maControlPointB)
402 [ + - + + : 460 : );
+ - + - ]
403 : : }
404 : :
405 : : // test if vectors are used
406 : 119972 : bool B2DCubicBezier::isBezier() const
407 : : {
408 [ + + ][ + + ]: 119972 : if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
[ + + ]
409 : : {
410 : 73720 : return true;
411 : : }
412 : :
413 : 119972 : return false;
414 : : }
415 : :
416 : 5321 : void B2DCubicBezier::testAndSolveTrivialBezier()
417 : : {
418 [ + + ][ + + ]: 5321 : if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
[ + + ]
419 : : {
420 : 1122 : const B2DVector aEdge(maEndPoint - maStartPoint);
421 : :
422 : : // controls parallel to edge can be trivial. No edge -> not parallel -> control can
423 : : // still not be trivial (e.g. ballon loop)
424 [ + - ][ + - ]: 1122 : if(!aEdge.equalZero())
425 : : {
426 : : // get control vectors
427 : 1122 : const B2DVector aVecA(maControlPointA - maStartPoint);
428 : 1122 : const B2DVector aVecB(maControlPointB - maEndPoint);
429 : :
430 : : // check if trivial per se
431 [ + - ]: 1122 : bool bAIsTrivial(aVecA.equalZero());
432 [ + - ]: 1122 : bool bBIsTrivial(aVecB.equalZero());
433 : :
434 : : // #i102241# prepare inverse edge length to normalize cross values;
435 : : // else the small compare value used in fTools::equalZero
436 : : // will be length dependent and this detection will work as less
437 : : // precise as longer the edge is. In principle, the length of the control
438 : : // vector would need to be used too, but to be trivial it is assumed to
439 : : // be of roughly equal length to the edge, so edge length can be used
440 : : // for both. Only needed when one of both is not trivial per se.
441 : : const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
442 : : ? 1.0
443 [ + + ][ + - ]: 1122 : : 1.0 / aEdge.getLength());
[ + - ]
444 : :
445 : : // if A is not zero, check if it could be
446 [ + + ]: 1122 : if(!bAIsTrivial)
447 : : {
448 : : // #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what
449 : : // we need here with the precision we need
450 [ + - ]: 1112 : const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);
451 : :
452 [ + + ]: 1112 : if(fTools::equalZero(fCross))
453 : : {
454 : : // get scale to edge. Use bigger distance for numeric quality
455 : 82 : const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
456 : 32 : ? aVecA.getX() / aEdge.getX()
457 [ + + ]: 114 : : aVecA.getY() / aEdge.getY());
458 : :
459 : : // relative end point of vector in edge range?
460 [ + - ][ + - ]: 82 : if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
[ + - ][ + - ]
[ + - ]
461 : : {
462 : 1112 : bAIsTrivial = true;
463 : : }
464 : : }
465 : : }
466 : :
467 : : // if B is not zero, check if it could be, but only if A is already trivial;
468 : : // else solve to trivial will not be possible for whole edge
469 [ + + ][ + - ]: 1122 : if(bAIsTrivial && !bBIsTrivial)
470 : : {
471 : : // parallel to edge? Check aVecB, aEdge
472 [ + - ]: 92 : const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);
473 : :
474 [ + + ]: 92 : if(fTools::equalZero(fCross))
475 : : {
476 : : // get scale to edge. Use bigger distance for numeric quality
477 : 82 : const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
478 : 32 : ? aVecB.getX() / aEdge.getX()
479 [ + + ]: 114 : : aVecB.getY() / aEdge.getY());
480 : :
481 : : // end point of vector in edge range? Caution: controlB is directed AGAINST edge
482 [ + - ][ + - ]: 82 : if(fTools::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
[ + - ][ + - ]
[ + - ]
483 : : {
484 : 92 : bBIsTrivial = true;
485 : : }
486 : : }
487 : : }
488 : :
489 : : // if both are/can be reduced, do it.
490 : : // Not possible if only one is/can be reduced (!)
491 [ + + ][ + + ]: 1122 : if(bAIsTrivial && bBIsTrivial)
492 : : {
493 : 82 : maControlPointA = maStartPoint;
494 : 82 : maControlPointB = maEndPoint;
495 : 1122 : }
496 : 1122 : }
497 : : }
498 : 5321 : }
499 : :
500 : : namespace {
501 : 0 : double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
502 : : {
503 [ # # ]: 0 : const double fEdgeLength(rEdge.getEdgeLength());
504 [ # # ]: 0 : const double fControlPolygonLength(rEdge.getControlPolygonLength());
505 [ # # ]: 0 : const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));
506 : :
507 [ # # ][ # # ]: 0 : if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
[ # # ]
508 : : {
509 : 0 : return (fEdgeLength + fControlPolygonLength) * 0.5;
510 : : }
511 : : else
512 : : {
513 [ # # ][ # # ]: 0 : B2DCubicBezier aLeft, aRight;
514 : 0 : const double fNewDeviation(fDeviation * 0.5);
515 : 0 : const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);
516 : :
517 [ # # ]: 0 : rEdge.split(0.5, &aLeft, &aRight);
518 : :
519 [ # # ]: 0 : return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
520 [ # # ][ # # ]: 0 : + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
[ # # ]
521 : : }
522 : : }
523 : : }
524 : :
525 : 0 : double B2DCubicBezier::getLength(double fDeviation) const
526 : : {
527 [ # # ]: 0 : if(isBezier())
528 : : {
529 [ # # ]: 0 : if(fDeviation < 0.00000001)
530 : : {
531 : 0 : fDeviation = 0.00000001;
532 : : }
533 : :
534 : 0 : return impGetLength(*this, fDeviation, 6);
535 : : }
536 : : else
537 : : {
538 [ # # ]: 0 : return B2DVector(getEndPoint() - getStartPoint()).getLength();
539 : : }
540 : : }
541 : :
542 : 3583 : double B2DCubicBezier::getEdgeLength() const
543 : : {
544 : 3583 : const B2DVector aEdge(maEndPoint - maStartPoint);
545 [ + - ]: 3583 : return aEdge.getLength();
546 : : }
547 : :
548 : 0 : double B2DCubicBezier::getControlPolygonLength() const
549 : : {
550 : 0 : const B2DVector aVectorA(maControlPointA - maStartPoint);
551 : 0 : const B2DVector aVectorB(maEndPoint - maControlPointB);
552 : :
553 [ # # ][ # # ]: 0 : if(!aVectorA.equalZero() || !aVectorB.equalZero())
[ # # ][ # # ]
[ # # ]
554 : : {
555 : 0 : const B2DVector aTop(maControlPointB - maControlPointA);
556 [ # # ][ # # ]: 0 : return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
[ # # ]
557 : : }
558 : : else
559 : : {
560 [ # # ]: 0 : return getEdgeLength();
561 : 0 : }
562 : : }
563 : :
564 : 100 : void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const
565 : : {
566 [ + - ]: 100 : if(isBezier())
567 : : {
568 : : // use support method #i37443# and allow unsharpen the criteria
569 [ + - ]: 100 : ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen);
570 : : }
571 : : else
572 : : {
573 [ # # ]: 0 : rTarget.append(getEndPoint());
574 : : }
575 : 100 : }
576 : :
577 : 1736 : B2DVector B2DCubicBezier::getTangent(double t) const
578 : : {
579 [ + + ]: 1736 : if(fTools::lessOrEqual(t, 0.0))
580 : : {
581 : : // tangent in start point
582 : 868 : B2DVector aTangent(getControlPointA() - getStartPoint());
583 : :
584 [ - + ][ + - ]: 868 : if(!aTangent.equalZero())
585 : : {
586 : 0 : return aTangent;
587 : : }
588 : :
589 : : // start point and control vector are the same, fallback
590 : : // to implicit start vector to control point B
591 [ + - ]: 868 : aTangent = (getControlPointB() - getStartPoint()) * 0.3;
592 : :
593 [ + - ][ + - ]: 868 : if(!aTangent.equalZero())
594 : : {
595 : 868 : return aTangent;
596 : : }
597 : :
598 : : // not a bezier at all, return edge vector
599 : 868 : return (getEndPoint() - getStartPoint()) * 0.3;
600 : : }
601 [ + - ]: 868 : else if(fTools::moreOrEqual(t, 1.0))
602 : : {
603 : : // tangent in end point
604 : 868 : B2DVector aTangent(getEndPoint() - getControlPointB());
605 : :
606 [ - + ][ + - ]: 868 : if(!aTangent.equalZero())
607 : : {
608 : 0 : return aTangent;
609 : : }
610 : :
611 : : // end point and control vector are the same, fallback
612 : : // to implicit start vector from control point A
613 [ + - ]: 868 : aTangent = (getEndPoint() - getControlPointA()) * 0.3;
614 : :
615 [ + - ][ + - ]: 868 : if(!aTangent.equalZero())
616 : : {
617 : 868 : return aTangent;
618 : : }
619 : :
620 : : // not a bezier at all, return edge vector
621 : 868 : return (getEndPoint() - getStartPoint()) * 0.3;
622 : : }
623 : : else
624 : : {
625 : : // t is in ]0.0 .. 1.0[. Split and extract
626 [ # # ]: 0 : B2DCubicBezier aRight;
627 [ # # ]: 0 : split(t, 0, &aRight);
628 : :
629 [ # # ]: 1736 : return aRight.getControlPointA() - aRight.getStartPoint();
630 : : }
631 : : }
632 : :
633 : : // #i37443# adaptive subdivide by nCount subdivisions
634 : 40 : void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
635 : : {
636 : 40 : const double fLenFact(1.0 / static_cast< double >(nCount + 1));
637 : :
638 [ + + ]: 2040 : for(sal_uInt32 a(1); a <= nCount; a++)
639 : : {
640 : 2000 : const double fPos(static_cast< double >(a) * fLenFact);
641 [ + - ]: 2000 : rTarget.append(interpolatePoint(fPos));
642 : : }
643 : :
644 [ + - ]: 40 : rTarget.append(getEndPoint());
645 : 40 : }
646 : :
647 : : // adaptive subdivide by distance
648 : 0 : void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const
649 : : {
650 [ # # ]: 0 : if(isBezier())
651 : : {
652 : : ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
653 : 0 : fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30);
654 : : }
655 : : else
656 : : {
657 [ # # ]: 0 : rTarget.append(getEndPoint());
658 : : }
659 : 0 : }
660 : :
661 : 3527 : B2DPoint B2DCubicBezier::interpolatePoint(double t) const
662 : : {
663 : : OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
664 : :
665 [ + + ]: 3527 : if(isBezier())
666 : : {
667 : 2587 : const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
668 : 2587 : const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
669 : 2587 : const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
670 : 2587 : const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
671 : 2587 : const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
672 : :
673 : 2587 : return interpolate(aS2L, aS2R, t);
674 : : }
675 : : else
676 : : {
677 : 3527 : return interpolate(maStartPoint, maEndPoint, t);
678 : : }
679 : : }
680 : :
681 : 0 : double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
682 : : {
683 : 0 : const sal_uInt32 nInitialDivisions(3L);
684 [ # # ]: 0 : B2DPolygon aInitialPolygon;
685 : :
686 : : // as start make a fix division, creates nInitialDivisions + 2L points
687 [ # # ]: 0 : aInitialPolygon.append(getStartPoint());
688 [ # # ]: 0 : adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
689 : :
690 : : // now look for the closest point
691 [ # # ]: 0 : const sal_uInt32 nPointCount(aInitialPolygon.count());
692 [ # # ]: 0 : B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L));
693 : 0 : double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY());
694 : : double fNewQuadDist;
695 : 0 : sal_uInt32 nSmallestIndex(0L);
696 : :
697 [ # # ]: 0 : for(sal_uInt32 a(1L); a < nPointCount; a++)
698 : : {
699 [ # # ][ # # ]: 0 : aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
700 : 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
701 : :
702 [ # # ]: 0 : if(fNewQuadDist < fQuadDist)
703 : : {
704 : 0 : fQuadDist = fNewQuadDist;
705 : 0 : nSmallestIndex = a;
706 : : }
707 : : }
708 : :
709 : : // look right and left for even smaller distances
710 : 0 : double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width
711 : 0 : double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L));
712 : 0 : bool bDone(false);
713 : :
714 [ # # ]: 0 : while(!bDone)
715 : : {
716 [ # # ]: 0 : if(!bDone)
717 : : {
718 : : // test left
719 : 0 : double fPosLeft(fPosition - fStepValue);
720 : :
721 [ # # ]: 0 : if(fPosLeft < 0.0)
722 : : {
723 : 0 : fPosLeft = 0.0;
724 [ # # ]: 0 : aVector = B2DVector(rTestPoint - maStartPoint);
725 : : }
726 : : else
727 : : {
728 [ # # ][ # # ]: 0 : aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
729 : : }
730 : :
731 : 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
732 : :
733 [ # # ]: 0 : if(fTools::less(fNewQuadDist, fQuadDist))
734 : : {
735 : 0 : fQuadDist = fNewQuadDist;
736 : 0 : fPosition = fPosLeft;
737 : : }
738 : : else
739 : : {
740 : : // test right
741 : 0 : double fPosRight(fPosition + fStepValue);
742 : :
743 [ # # ]: 0 : if(fPosRight > 1.0)
744 : : {
745 : 0 : fPosRight = 1.0;
746 [ # # ]: 0 : aVector = B2DVector(rTestPoint - maEndPoint);
747 : : }
748 : : else
749 : : {
750 [ # # ][ # # ]: 0 : aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
751 : : }
752 : :
753 : 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
754 : :
755 [ # # ]: 0 : if(fTools::less(fNewQuadDist, fQuadDist))
756 : : {
757 : 0 : fQuadDist = fNewQuadDist;
758 : 0 : fPosition = fPosRight;
759 : : }
760 : : else
761 : : {
762 : : // not less left or right, done
763 : 0 : bDone = true;
764 : : }
765 : : }
766 : : }
767 : :
768 [ # # ][ # # ]: 0 : if(0.0 == fPosition || 1.0 == fPosition)
769 : : {
770 : : // if we are completely left or right, we are done
771 : 0 : bDone = true;
772 : : }
773 : :
774 [ # # ]: 0 : if(!bDone)
775 : : {
776 : : // prepare next step value
777 : 0 : fStepValue /= 2.0;
778 : : }
779 : : }
780 : :
781 : 0 : rCut = fPosition;
782 [ # # ]: 0 : return sqrt(fQuadDist);
783 : : }
784 : :
785 : 0 : void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const
786 : : {
787 : : OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");
788 : :
789 [ # # ][ # # ]: 0 : if(!pBezierA && !pBezierB)
790 : : {
791 : 0 : return;
792 : : }
793 : :
794 [ # # ]: 0 : if(isBezier())
795 : : {
796 : 0 : const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
797 : 0 : const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
798 : 0 : const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
799 : 0 : const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
800 : 0 : const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
801 : 0 : const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
802 : :
803 [ # # ]: 0 : if(pBezierA)
804 : : {
805 : 0 : pBezierA->setStartPoint(maStartPoint);
806 : 0 : pBezierA->setEndPoint(aS3C);
807 : 0 : pBezierA->setControlPointA(aS1L);
808 : 0 : pBezierA->setControlPointB(aS2L);
809 : : }
810 : :
811 [ # # ]: 0 : if(pBezierB)
812 : : {
813 : 0 : pBezierB->setStartPoint(aS3C);
814 : 0 : pBezierB->setEndPoint(maEndPoint);
815 : 0 : pBezierB->setControlPointA(aS2R);
816 : 0 : pBezierB->setControlPointB(aS1R);
817 : 0 : }
818 : : }
819 : : else
820 : : {
821 : 0 : const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
822 : :
823 [ # # ]: 0 : if(pBezierA)
824 : : {
825 : 0 : pBezierA->setStartPoint(maStartPoint);
826 : 0 : pBezierA->setEndPoint(aSplit);
827 : 0 : pBezierA->setControlPointA(maStartPoint);
828 : 0 : pBezierA->setControlPointB(aSplit);
829 : : }
830 : :
831 [ # # ]: 0 : if(pBezierB)
832 : : {
833 : 0 : pBezierB->setStartPoint(aSplit);
834 : 0 : pBezierB->setEndPoint(maEndPoint);
835 : 0 : pBezierB->setControlPointA(aSplit);
836 : 0 : pBezierB->setControlPointB(maEndPoint);
837 : 0 : }
838 : : }
839 : : }
840 : :
841 : 0 : B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
842 : : {
843 : 0 : B2DCubicBezier aRetval;
844 : :
845 [ # # ]: 0 : if(fTools::more(fStart, 1.0))
846 : : {
847 : 0 : fStart = 1.0;
848 : : }
849 [ # # ]: 0 : else if(fTools::less(fStart, 0.0))
850 : : {
851 : 0 : fStart = 0.0;
852 : : }
853 : :
854 [ # # ]: 0 : if(fTools::more(fEnd, 1.0))
855 : : {
856 : 0 : fEnd = 1.0;
857 : : }
858 [ # # ]: 0 : else if(fTools::less(fEnd, 0.0))
859 : : {
860 : 0 : fEnd = 0.0;
861 : : }
862 : :
863 [ # # ]: 0 : if(fEnd <= fStart)
864 : : {
865 : : // empty or NULL, create single point at center
866 : 0 : const double fSplit((fEnd + fStart) * 0.5);
867 : 0 : const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
868 : 0 : aRetval.setStartPoint(aPoint);
869 : 0 : aRetval.setEndPoint(aPoint);
870 : 0 : aRetval.setControlPointA(aPoint);
871 : 0 : aRetval.setControlPointB(aPoint);
872 : : }
873 : : else
874 : : {
875 [ # # ][ # # ]: 0 : if(isBezier())
876 : : {
877 : : // copy bezier; cut off right, then cut off left. Do not forget to
878 : : // adapt cut value when both cuts happen
879 : 0 : const bool bEndIsOne(fTools::equal(fEnd, 1.0));
880 : 0 : const bool bStartIsZero(fTools::equalZero(fStart));
881 [ # # ]: 0 : aRetval = *this;
882 : :
883 [ # # ]: 0 : if(!bEndIsOne)
884 : : {
885 [ # # ]: 0 : aRetval.split(fEnd, &aRetval, 0);
886 : :
887 [ # # ]: 0 : if(!bStartIsZero)
888 : : {
889 : 0 : fStart /= fEnd;
890 : : }
891 : : }
892 : :
893 [ # # ]: 0 : if(!bStartIsZero)
894 : : {
895 [ # # ]: 0 : aRetval.split(fStart, 0, &aRetval);
896 : : }
897 : : }
898 : : else
899 : : {
900 : : // no bezier, create simple edge
901 : 0 : const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
902 : 0 : const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
903 : 0 : aRetval.setStartPoint(aPointA);
904 : 0 : aRetval.setEndPoint(aPointB);
905 : 0 : aRetval.setControlPointA(aPointA);
906 : 0 : aRetval.setControlPointB(aPointB);
907 : : }
908 : : }
909 : :
910 : 0 : return aRetval;
911 : : }
912 : :
913 : 6226 : B2DRange B2DCubicBezier::getRange() const
914 : : {
915 : 6226 : B2DRange aRetval(maStartPoint, maEndPoint);
916 : :
917 : 6226 : aRetval.expand(maControlPointA);
918 : 6226 : aRetval.expand(maControlPointB);
919 : :
920 : 6226 : return aRetval;
921 : : }
922 : :
923 : 10 : bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
924 : : {
925 [ + - ]: 10 : ::std::vector< double > aAllResults;
926 : :
927 [ + - ]: 10 : aAllResults.reserve(4);
928 [ + - ]: 10 : getAllExtremumPositions(aAllResults);
929 : :
930 : 10 : const sal_uInt32 nCount(aAllResults.size());
931 : :
932 [ - + ]: 10 : if(!nCount)
933 : : {
934 : 0 : return false;
935 : : }
936 [ + - ]: 10 : else if(1 == nCount)
937 : : {
938 [ + - ]: 10 : rfResult = aAllResults[0];
939 : 10 : return true;
940 : : }
941 : : else
942 : : {
943 [ # # ][ # # ]: 0 : rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end()));
944 : 0 : return true;
945 : 10 : }
946 : : }
947 : :
948 : : namespace
949 : : {
950 : 2246 : inline void impCheckExtremumResult(double fCandidate, ::std::vector< double >& rResult)
951 : : {
952 : : // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly
953 : : // by using the equalZero test, NOT ::more or ::less which will use the
954 : : // ApproxEqual() which is too exact here
955 [ + + ][ + - ]: 2246 : if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
[ + + ]
956 : : {
957 [ + + ][ + + ]: 1782 : if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
[ + + ][ + + ]
958 : : {
959 : 597 : rResult.push_back(fCandidate);
960 : : }
961 : : }
962 : 2246 : }
963 : : }
964 : :
965 : 786 : void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const
966 : : {
967 : 786 : rResults.clear();
968 : :
969 : : // calculate the x-extrema parameters by zeroing first x-derivative
970 : : // of the cubic bezier's parametric formula, which results in a
971 : : // quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX
972 : 786 : const B2DPoint aControlDiff( maControlPointA - maControlPointB );
973 : 786 : double fCX = maControlPointA.getX() - maStartPoint.getX();
974 : 786 : const double fBX = fCX + aControlDiff.getX();
975 : 786 : const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX());
976 : :
977 [ + + ]: 786 : if(fTools::equalZero(fCX))
978 : : {
979 : : // detect fCX equal zero and truncate to real zero value in that case
980 : 52 : fCX = 0.0;
981 : : }
982 : :
983 [ + + ]: 786 : if( !fTools::equalZero(fAX) )
984 : : {
985 : : // derivative is polynomial of order 2 => use binomial formula
986 : 766 : const double fD = fBX*fBX - fAX*fCX;
987 [ + + ]: 766 : if( fD >= 0.0 )
988 : : {
989 : 439 : const double fS = sqrt(fD);
990 : : // calculate both roots (avoiding a numerically unstable subtraction)
991 [ + + ]: 439 : const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
992 [ + - ]: 439 : impCheckExtremumResult(fQ / fAX, rResults);
993 [ + - ]: 439 : if( !fTools::equalZero(fS) ) // ignore root multiplicity
994 [ + - ]: 439 : impCheckExtremumResult(fCX / fQ, rResults);
995 : : }
996 : : }
997 [ + - ]: 20 : else if( !fTools::equalZero(fBX) )
998 : : {
999 : : // derivative is polynomial of order 1 => one extrema
1000 [ + - ]: 20 : impCheckExtremumResult(fCX / (2 * fBX), rResults);
1001 : : }
1002 : :
1003 : : // calculate the y-extrema parameters by zeroing first y-derivative
1004 : 786 : double fCY = maControlPointA.getY() - maStartPoint.getY();
1005 : 786 : const double fBY = fCY + aControlDiff.getY();
1006 : 786 : const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY());
1007 : :
1008 [ + + ]: 786 : if(fTools::equalZero(fCY))
1009 : : {
1010 : : // detect fCY equal zero and truncate to real zero value in that case
1011 : 72 : fCY = 0.0;
1012 : : }
1013 : :
1014 [ + - ]: 786 : if( !fTools::equalZero(fAY) )
1015 : : {
1016 : : // derivative is polynomial of order 2 => use binomial formula
1017 : 786 : const double fD = fBY*fBY - fAY*fCY;
1018 [ + + ]: 786 : if( fD >= 0.0 )
1019 : : {
1020 : 684 : const double fS = sqrt(fD);
1021 : : // calculate both roots (avoiding a numerically unstable subtraction)
1022 [ + + ]: 684 : const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
1023 [ + - ]: 684 : impCheckExtremumResult(fQ / fAY, rResults);
1024 [ + + ]: 684 : if( !fTools::equalZero(fS) ) // ignore root multiplicity
1025 [ + - ]: 684 : impCheckExtremumResult(fCY / fQ, rResults);
1026 : : }
1027 : : }
1028 [ # # ]: 0 : else if( !fTools::equalZero(fBY) )
1029 : : {
1030 : : // derivative is polynomial of order 1 => one extrema
1031 [ # # ]: 0 : impCheckExtremumResult(fCY / (2 * fBY), rResults);
1032 : 786 : }
1033 : 786 : }
1034 : :
1035 : : } // end of namespace basegfx
1036 : :
1037 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
