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