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