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 :
34 :
35 : namespace basegfx
36 : {
37 : namespace
38 : {
39 65873 : 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 65873 : if(nMaxRecursionDepth)
50 : {
51 : // do angle test
52 65873 : B2DVector aLeft(rfEA - rfPA);
53 131746 : B2DVector aRight(rfEB - rfPB);
54 :
55 : // #i72104#
56 65873 : if(aLeft.equalZero())
57 : {
58 63 : aLeft = rfEB - rfPA;
59 : }
60 :
61 65873 : if(aRight.equalZero())
62 : {
63 12 : aRight = rfEA - rfPB;
64 : }
65 :
66 65873 : const double fCurrentAngle(aLeft.angle(aRight));
67 :
68 65873 : if(fabs(fCurrentAngle) > (F_PI - fAngleBound))
69 : {
70 : // end recursion
71 37506 : nMaxRecursionDepth = 0;
72 : }
73 : else
74 : {
75 28367 : if(bAllowUnsharpen)
76 : {
77 : // #i37443# unsharpen criteria
78 : #ifdef DBG_UTIL
79 : fAngleBound *= fMultFactUnsharpen;
80 : #else
81 28367 : fAngleBound *= FACTOR_FOR_UNSHARPEN;
82 : #endif
83 : }
84 65873 : }
85 : }
86 :
87 65873 : if(nMaxRecursionDepth)
88 : {
89 : // divide at 0.5
90 28367 : const B2DPoint aS1L(average(rfPA, rfEA));
91 56734 : const B2DPoint aS1C(average(rfEA, rfEB));
92 56734 : const B2DPoint aS1R(average(rfEB, rfPB));
93 56734 : const B2DPoint aS2L(average(aS1L, aS1C));
94 56734 : const B2DPoint aS2R(average(aS1C, aS1R));
95 56734 : const B2DPoint aS3C(average(aS2L, aS2R));
96 :
97 : // left recursion
98 28367 : ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
99 :
100 : // right recursion
101 56734 : ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
102 : }
103 : else
104 : {
105 37506 : rTarget.append(rfPB);
106 : }
107 65873 : }
108 :
109 4784 : 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 4784 : sal_uInt16 nMaxRecursionDepth(8);
119 4784 : const B2DVector aLeft(rfEA - rfPA);
120 9568 : const B2DVector aRight(rfEB - rfPB);
121 4784 : bool bLeftEqualZero(aLeft.equalZero());
122 4784 : bool bRightEqualZero(aRight.equalZero());
123 4784 : bool bAllParallel(false);
124 :
125 4784 : if(bLeftEqualZero && bRightEqualZero)
126 : {
127 0 : nMaxRecursionDepth = 0;
128 : }
129 : else
130 : {
131 4784 : const B2DVector aBase(rfPB - rfPA);
132 4784 : const bool bBaseEqualZero(aBase.equalZero()); // #i72104#
133 :
134 4784 : if(!bBaseEqualZero)
135 : {
136 4784 : const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase));
137 4784 : const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase));
138 :
139 4784 : if(bLeftParallel && bRightParallel)
140 : {
141 0 : bAllParallel = true;
142 :
143 0 : if(!bLeftEqualZero)
144 : {
145 : double fFactor;
146 :
147 0 : if(fabs(aBase.getX()) > fabs(aBase.getY()))
148 : {
149 0 : fFactor = aLeft.getX() / aBase.getX();
150 : }
151 : else
152 : {
153 0 : fFactor = aLeft.getY() / aBase.getY();
154 : }
155 :
156 0 : if(fFactor >= 0.0 && fFactor <= 1.0)
157 : {
158 0 : bLeftEqualZero = true;
159 : }
160 : }
161 :
162 0 : if(!bRightEqualZero)
163 : {
164 : double fFactor;
165 :
166 0 : if(fabs(aBase.getX()) > fabs(aBase.getY()))
167 : {
168 0 : fFactor = aRight.getX() / -aBase.getX();
169 : }
170 : else
171 : {
172 0 : fFactor = aRight.getY() / -aBase.getY();
173 : }
174 :
175 0 : if(fFactor >= 0.0 && fFactor <= 1.0)
176 : {
177 0 : bRightEqualZero = true;
178 : }
179 : }
180 :
181 0 : if(bLeftEqualZero && bRightEqualZero)
182 : {
183 0 : nMaxRecursionDepth = 0;
184 : }
185 : }
186 4784 : }
187 : }
188 :
189 4784 : if(nMaxRecursionDepth)
190 : {
191 : // divide at 0.5 ad test both edges for angle criteria
192 4784 : const B2DPoint aS1L(average(rfPA, rfEA));
193 9568 : const B2DPoint aS1C(average(rfEA, rfEB));
194 9568 : const B2DPoint aS1R(average(rfEB, rfPB));
195 9568 : const B2DPoint aS2L(average(aS1L, aS1C));
196 9568 : const B2DPoint aS2R(average(aS1C, aS1R));
197 9568 : const B2DPoint aS3C(average(aS2L, aS2R));
198 :
199 : // test left
200 4784 : bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
201 4784 : if(!bAngleIsSmallerLeft)
202 : {
203 4784 : const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
204 9568 : const B2DVector aRightLeft(aS2L - aS3C);
205 4784 : const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
206 9568 : bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound));
207 : }
208 :
209 : // test right
210 4784 : bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
211 4784 : if(!bAngleIsSmallerRight)
212 : {
213 4784 : const B2DVector aLeftRight(aS2R - aS3C);
214 9568 : const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
215 4784 : const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
216 9568 : bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound));
217 : }
218 :
219 4784 : if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
220 : {
221 : // no recursion necessary at all
222 0 : nMaxRecursionDepth = 0;
223 : }
224 : else
225 : {
226 : // left
227 4784 : if(bAngleIsSmallerLeft)
228 : {
229 202 : rTarget.append(aS3C);
230 : }
231 : else
232 : {
233 4582 : ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
234 : }
235 :
236 : // right
237 4784 : if(bAngleIsSmallerRight)
238 : {
239 227 : rTarget.append(rfPB);
240 : }
241 : else
242 : {
243 4557 : ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
244 : }
245 4784 : }
246 : }
247 :
248 4784 : if(!nMaxRecursionDepth)
249 : {
250 0 : rTarget.append(rfPB);
251 4784 : }
252 4784 : }
253 :
254 0 : 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 0 : 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 0 : const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
280 0 : const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
281 0 : const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
282 0 : const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
283 0 : 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 0 : const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);
289 :
290 0 : if(bFurtherDivision)
291 : {
292 : // remember last error value
293 0 : fLastDistanceError2 = fDistanceError2;
294 : }
295 : else
296 : {
297 : // stop recustion
298 0 : nMaxRecursionDepth = 0;
299 : }
300 : }
301 :
302 0 : if(nMaxRecursionDepth)
303 : {
304 : // divide at 0.5
305 0 : const B2DPoint aS1L(average(rfPA, rfEA));
306 0 : const B2DPoint aS1C(average(rfEA, rfEB));
307 0 : const B2DPoint aS1R(average(rfEB, rfPB));
308 0 : const B2DPoint aS2L(average(aS1L, aS1C));
309 0 : const B2DPoint aS2R(average(aS1C, aS1R));
310 0 : const B2DPoint aS3C(average(aS2L, aS2R));
311 :
312 : // left recursion
313 0 : ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
314 :
315 : // right recursion
316 0 : ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
317 : }
318 : else
319 : {
320 0 : rTarget.append(rfPB);
321 : }
322 0 : }
323 : } // end of anonymous namespace
324 : } // end of namespace basegfx
325 :
326 :
327 :
328 : namespace basegfx
329 : {
330 0 : B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier)
331 : : maStartPoint(rBezier.maStartPoint),
332 : maEndPoint(rBezier.maEndPoint),
333 : maControlPointA(rBezier.maControlPointA),
334 0 : maControlPointB(rBezier.maControlPointB)
335 : {
336 0 : }
337 :
338 79921 : B2DCubicBezier::B2DCubicBezier()
339 : {
340 79921 : }
341 :
342 31114 : B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
343 : : maStartPoint(rStart),
344 : maEndPoint(rEnd),
345 : maControlPointA(rControlPointA),
346 31114 : maControlPointB(rControlPointB)
347 : {
348 31114 : }
349 :
350 111035 : B2DCubicBezier::~B2DCubicBezier()
351 : {
352 111035 : }
353 :
354 : // assignment operator
355 8614 : B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier)
356 : {
357 8614 : maStartPoint = rBezier.maStartPoint;
358 8614 : maEndPoint = rBezier.maEndPoint;
359 8614 : maControlPointA = rBezier.maControlPointA;
360 8614 : maControlPointB = rBezier.maControlPointB;
361 :
362 8614 : return *this;
363 : }
364 :
365 : // compare operators
366 0 : bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
367 : {
368 : return (
369 0 : maStartPoint == rBezier.maStartPoint
370 0 : && maEndPoint == rBezier.maEndPoint
371 0 : && maControlPointA == rBezier.maControlPointA
372 0 : && maControlPointB == rBezier.maControlPointB
373 0 : );
374 : }
375 :
376 0 : bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const
377 : {
378 : return (
379 0 : maStartPoint != rBezier.maStartPoint
380 0 : || maEndPoint != rBezier.maEndPoint
381 0 : || maControlPointA != rBezier.maControlPointA
382 0 : || maControlPointB != rBezier.maControlPointB
383 0 : );
384 : }
385 :
386 2701 : bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
387 : {
388 : return (
389 2701 : maStartPoint.equal(rBezier.maStartPoint)
390 2701 : && maEndPoint.equal(rBezier.maEndPoint)
391 462 : && maControlPointA.equal(rBezier.maControlPointA)
392 3100 : && maControlPointB.equal(rBezier.maControlPointB)
393 2701 : );
394 : }
395 :
396 : // test if vectors are used
397 3312317 : bool B2DCubicBezier::isBezier() const
398 : {
399 3312317 : if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
400 : {
401 3049075 : return true;
402 : }
403 :
404 263242 : return false;
405 : }
406 :
407 838982 : void B2DCubicBezier::testAndSolveTrivialBezier()
408 : {
409 838982 : if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
410 : {
411 382326 : 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 382326 : if(!aEdge.equalZero())
416 : {
417 : // get control vectors
418 382154 : const B2DVector aVecA(maControlPointA - maStartPoint);
419 764308 : const B2DVector aVecB(maControlPointB - maEndPoint);
420 :
421 : // check if trivial per se
422 382154 : bool bAIsTrivial(aVecA.equalZero());
423 382154 : 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 396885 : const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
433 : ? 1.0
434 764308 : : 1.0 / aEdge.getLength());
435 :
436 : // if A is not zero, check if it could be
437 382154 : 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 367423 : const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);
442 :
443 367423 : if(fTools::equalZero(fCross))
444 : {
445 : // get scale to edge. Use bigger distance for numeric quality
446 111347 : const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
447 2927 : ? aVecA.getX() / aEdge.getX()
448 114274 : : aVecA.getY() / aEdge.getY());
449 :
450 : // relative end point of vector in edge range?
451 111347 : if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
452 : {
453 111245 : 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 382154 : if(bAIsTrivial && !bBIsTrivial)
461 : {
462 : // parallel to edge? Check aVecB, aEdge
463 123628 : const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);
464 :
465 123628 : if(fTools::equalZero(fCross))
466 : {
467 : // get scale to edge. Use bigger distance for numeric quality
468 111374 : const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
469 2949 : ? aVecB.getX() / aEdge.getX()
470 114323 : : aVecB.getY() / aEdge.getY());
471 :
472 : // end point of vector in edge range? Caution: controlB is directed AGAINST edge
473 111374 : if(fTools::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
474 : {
475 111374 : 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 382154 : if(bAIsTrivial && bBIsTrivial)
483 : {
484 113722 : maControlPointA = maStartPoint;
485 113722 : maControlPointB = maEndPoint;
486 382154 : }
487 382326 : }
488 : }
489 838982 : }
490 :
491 : namespace {
492 18 : double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
493 : {
494 18 : const double fEdgeLength(rEdge.getEdgeLength());
495 18 : const double fControlPolygonLength(rEdge.getControlPolygonLength());
496 18 : const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));
497 :
498 18 : if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
499 : {
500 18 : return (fEdgeLength + fControlPolygonLength) * 0.5;
501 : }
502 : else
503 : {
504 0 : B2DCubicBezier aLeft, aRight;
505 0 : const double fNewDeviation(fDeviation * 0.5);
506 0 : const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);
507 :
508 0 : rEdge.split(0.5, &aLeft, &aRight);
509 :
510 0 : return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
511 0 : + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
512 : }
513 : }
514 : }
515 :
516 18 : double B2DCubicBezier::getLength(double fDeviation) const
517 : {
518 18 : if(isBezier())
519 : {
520 18 : if(fDeviation < 0.00000001)
521 : {
522 0 : fDeviation = 0.00000001;
523 : }
524 :
525 18 : return impGetLength(*this, fDeviation, 6);
526 : }
527 : else
528 : {
529 0 : return B2DVector(getEndPoint() - getStartPoint()).getLength();
530 : }
531 : }
532 :
533 3080 : double B2DCubicBezier::getEdgeLength() const
534 : {
535 3080 : const B2DVector aEdge(maEndPoint - maStartPoint);
536 3080 : return aEdge.getLength();
537 : }
538 :
539 18 : double B2DCubicBezier::getControlPolygonLength() const
540 : {
541 18 : const B2DVector aVectorA(maControlPointA - maStartPoint);
542 36 : const B2DVector aVectorB(maEndPoint - maControlPointB);
543 :
544 18 : if(!aVectorA.equalZero() || !aVectorB.equalZero())
545 : {
546 18 : const B2DVector aTop(maControlPointB - maControlPointA);
547 18 : return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
548 : }
549 : else
550 : {
551 0 : return getEdgeLength();
552 18 : }
553 : }
554 :
555 4784 : void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const
556 : {
557 4784 : if(isBezier())
558 : {
559 : // use support method #i37443# and allow unsharpen the criteria
560 4784 : ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen);
561 : }
562 : else
563 : {
564 0 : rTarget.append(getEndPoint());
565 : }
566 4784 : }
567 :
568 21645 : B2DVector B2DCubicBezier::getTangent(double t) const
569 : {
570 21645 : if(fTools::lessOrEqual(t, 0.0))
571 : {
572 : // tangent in start point
573 11053 : B2DVector aTangent(getControlPointA() - getStartPoint());
574 :
575 11053 : if(!aTangent.equalZero())
576 : {
577 3539 : return aTangent;
578 : }
579 :
580 : // start point and control vector are the same, fallback
581 : // to implicit start vector to control point B
582 7514 : aTangent = (getControlPointB() - getStartPoint()) * 0.3;
583 :
584 7514 : if(!aTangent.equalZero())
585 : {
586 6998 : return aTangent;
587 : }
588 :
589 : // not a bezier at all, return edge vector
590 516 : return (getEndPoint() - getStartPoint()) * 0.3;
591 : }
592 10592 : else if(fTools::moreOrEqual(t, 1.0))
593 : {
594 : // tangent in end point
595 10592 : B2DVector aTangent(getEndPoint() - getControlPointB());
596 :
597 10592 : if(!aTangent.equalZero())
598 : {
599 3247 : return aTangent;
600 : }
601 :
602 : // end point and control vector are the same, fallback
603 : // to implicit start vector from control point A
604 7345 : aTangent = (getEndPoint() - getControlPointA()) * 0.3;
605 :
606 7345 : if(!aTangent.equalZero())
607 : {
608 6829 : return aTangent;
609 : }
610 :
611 : // not a bezier at all, return edge vector
612 516 : return (getEndPoint() - getStartPoint()) * 0.3;
613 : }
614 : else
615 : {
616 : // t is in ]0.0 .. 1.0[. Split and extract
617 0 : B2DCubicBezier aRight;
618 0 : split(t, 0, &aRight);
619 :
620 0 : return aRight.getControlPointA() - aRight.getStartPoint();
621 : }
622 : }
623 :
624 : // #i37443# adaptive subdivide by nCount subdivisions
625 65472 : void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
626 : {
627 65472 : const double fLenFact(1.0 / static_cast< double >(nCount + 1));
628 :
629 2790615 : for(sal_uInt32 a(1); a <= nCount; a++)
630 : {
631 2725143 : const double fPos(static_cast< double >(a) * fLenFact);
632 2725143 : rTarget.append(interpolatePoint(fPos));
633 : }
634 :
635 65472 : rTarget.append(getEndPoint());
636 65472 : }
637 :
638 : // adaptive subdivide by distance
639 0 : void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const
640 : {
641 0 : if(isBezier())
642 : {
643 : ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
644 0 : fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30);
645 : }
646 : else
647 : {
648 0 : rTarget.append(getEndPoint());
649 : }
650 0 : }
651 :
652 2747199 : B2DPoint B2DCubicBezier::interpolatePoint(double t) const
653 : {
654 : OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
655 :
656 2747199 : if(isBezier())
657 : {
658 2746637 : const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
659 5493274 : const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
660 5493274 : const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
661 5493274 : const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
662 5493274 : const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
663 :
664 5493274 : return interpolate(aS2L, aS2R, t);
665 : }
666 : else
667 : {
668 562 : return interpolate(maStartPoint, maEndPoint, t);
669 : }
670 : }
671 :
672 0 : double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
673 : {
674 0 : const sal_uInt32 nInitialDivisions(3L);
675 0 : B2DPolygon aInitialPolygon;
676 :
677 : // as start make a fix division, creates nInitialDivisions + 2L points
678 0 : aInitialPolygon.append(getStartPoint());
679 0 : adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
680 :
681 : // now look for the closest point
682 0 : const sal_uInt32 nPointCount(aInitialPolygon.count());
683 0 : B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L));
684 0 : double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY());
685 : double fNewQuadDist;
686 0 : sal_uInt32 nSmallestIndex(0L);
687 :
688 0 : for(sal_uInt32 a(1L); a < nPointCount; a++)
689 : {
690 0 : aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
691 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
692 :
693 0 : if(fNewQuadDist < fQuadDist)
694 : {
695 0 : fQuadDist = fNewQuadDist;
696 0 : nSmallestIndex = a;
697 : }
698 : }
699 :
700 : // look right and left for even smaller distances
701 0 : double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width
702 0 : double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L));
703 0 : bool bDone(false);
704 :
705 0 : while(!bDone)
706 : {
707 0 : if(!bDone)
708 : {
709 : // test left
710 0 : double fPosLeft(fPosition - fStepValue);
711 :
712 0 : if(fPosLeft < 0.0)
713 : {
714 0 : fPosLeft = 0.0;
715 0 : aVector = B2DVector(rTestPoint - maStartPoint);
716 : }
717 : else
718 : {
719 0 : aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
720 : }
721 :
722 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
723 :
724 0 : if(fTools::less(fNewQuadDist, fQuadDist))
725 : {
726 0 : fQuadDist = fNewQuadDist;
727 0 : fPosition = fPosLeft;
728 : }
729 : else
730 : {
731 : // test right
732 0 : double fPosRight(fPosition + fStepValue);
733 :
734 0 : if(fPosRight > 1.0)
735 : {
736 0 : fPosRight = 1.0;
737 0 : aVector = B2DVector(rTestPoint - maEndPoint);
738 : }
739 : else
740 : {
741 0 : aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
742 : }
743 :
744 0 : fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
745 :
746 0 : if(fTools::less(fNewQuadDist, fQuadDist))
747 : {
748 0 : fQuadDist = fNewQuadDist;
749 0 : fPosition = fPosRight;
750 : }
751 : else
752 : {
753 : // not less left or right, done
754 0 : bDone = true;
755 : }
756 : }
757 : }
758 :
759 0 : if(0.0 == fPosition || 1.0 == fPosition)
760 : {
761 : // if we are completely left or right, we are done
762 0 : bDone = true;
763 : }
764 :
765 0 : if(!bDone)
766 : {
767 : // prepare next step value
768 0 : fStepValue /= 2.0;
769 : }
770 : }
771 :
772 0 : rCut = fPosition;
773 0 : return sqrt(fQuadDist);
774 : }
775 :
776 3378 : 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 3378 : if(!pBezierA && !pBezierB)
781 : {
782 3378 : return;
783 : }
784 :
785 3378 : if(isBezier())
786 : {
787 3378 : const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
788 6756 : const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
789 6756 : const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
790 6756 : const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
791 6756 : const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
792 6756 : const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
793 :
794 3378 : if(pBezierA)
795 : {
796 2232 : pBezierA->setStartPoint(maStartPoint);
797 2232 : pBezierA->setEndPoint(aS3C);
798 2232 : pBezierA->setControlPointA(aS1L);
799 2232 : pBezierA->setControlPointB(aS2L);
800 : }
801 :
802 3378 : if(pBezierB)
803 : {
804 2236 : pBezierB->setStartPoint(aS3C);
805 2236 : pBezierB->setEndPoint(maEndPoint);
806 2236 : pBezierB->setControlPointA(aS2R);
807 2236 : pBezierB->setControlPointB(aS1R);
808 3378 : }
809 : }
810 : else
811 : {
812 0 : const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
813 :
814 0 : if(pBezierA)
815 : {
816 0 : pBezierA->setStartPoint(maStartPoint);
817 0 : pBezierA->setEndPoint(aSplit);
818 0 : pBezierA->setControlPointA(maStartPoint);
819 0 : pBezierA->setControlPointB(aSplit);
820 : }
821 :
822 0 : if(pBezierB)
823 : {
824 0 : pBezierB->setStartPoint(aSplit);
825 0 : pBezierB->setEndPoint(maEndPoint);
826 0 : pBezierB->setControlPointA(aSplit);
827 0 : pBezierB->setControlPointB(maEndPoint);
828 0 : }
829 : }
830 : }
831 :
832 1141 : B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
833 : {
834 1141 : B2DCubicBezier aRetval;
835 :
836 1141 : if(fTools::more(fStart, 1.0))
837 : {
838 0 : fStart = 1.0;
839 : }
840 1141 : else if(fTools::less(fStart, 0.0))
841 : {
842 0 : fStart = 0.0;
843 : }
844 :
845 1141 : if(fTools::more(fEnd, 1.0))
846 : {
847 0 : fEnd = 1.0;
848 : }
849 1141 : else if(fTools::less(fEnd, 0.0))
850 : {
851 0 : fEnd = 0.0;
852 : }
853 :
854 1141 : if(fEnd <= fStart)
855 : {
856 : // empty or NULL, create single point at center
857 0 : const double fSplit((fEnd + fStart) * 0.5);
858 0 : const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
859 0 : aRetval.setStartPoint(aPoint);
860 0 : aRetval.setEndPoint(aPoint);
861 0 : aRetval.setControlPointA(aPoint);
862 0 : aRetval.setControlPointB(aPoint);
863 : }
864 : else
865 : {
866 1141 : 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 1141 : const bool bEndIsOne(fTools::equal(fEnd, 1.0));
871 1141 : const bool bStartIsZero(fTools::equalZero(fStart));
872 1141 : aRetval = *this;
873 :
874 1141 : if(!bEndIsOne)
875 : {
876 1141 : aRetval.split(fEnd, &aRetval, 0);
877 :
878 1141 : if(!bStartIsZero)
879 : {
880 955 : fStart /= fEnd;
881 : }
882 : }
883 :
884 1141 : if(!bStartIsZero)
885 : {
886 955 : aRetval.split(fStart, 0, &aRetval);
887 : }
888 : }
889 : else
890 : {
891 : // no bezier, create simple edge
892 0 : const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
893 0 : const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
894 0 : aRetval.setStartPoint(aPointA);
895 0 : aRetval.setEndPoint(aPointB);
896 0 : aRetval.setControlPointA(aPointA);
897 0 : aRetval.setControlPointB(aPointB);
898 : }
899 : }
900 :
901 1141 : return aRetval;
902 : }
903 :
904 868808 : B2DRange B2DCubicBezier::getRange() const
905 : {
906 868808 : B2DRange aRetval(maStartPoint, maEndPoint);
907 :
908 868808 : aRetval.expand(maControlPointA);
909 868808 : aRetval.expand(maControlPointB);
910 :
911 868808 : return aRetval;
912 : }
913 :
914 13346 : bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
915 : {
916 13346 : ::std::vector< double > aAllResults;
917 :
918 13346 : aAllResults.reserve(4);
919 13346 : getAllExtremumPositions(aAllResults);
920 :
921 13346 : const sal_uInt32 nCount(aAllResults.size());
922 :
923 13346 : if(!nCount)
924 : {
925 11068 : return false;
926 : }
927 2278 : else if(1 == nCount)
928 : {
929 2225 : rfResult = aAllResults[0];
930 2225 : return true;
931 : }
932 : else
933 : {
934 53 : rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end()));
935 53 : return true;
936 13346 : }
937 : }
938 :
939 : namespace
940 : {
941 117794 : 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 117794 : if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
947 : {
948 69586 : if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
949 : {
950 21086 : rResult.push_back(fCandidate);
951 : }
952 : }
953 117794 : }
954 : }
955 :
956 32687 : void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const
957 : {
958 32687 : 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 32687 : const B2DPoint aControlDiff( maControlPointA - maControlPointB );
964 32687 : double fCX = maControlPointA.getX() - maStartPoint.getX();
965 32687 : const double fBX = fCX + aControlDiff.getX();
966 32687 : const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX());
967 :
968 32687 : if(fTools::equalZero(fCX))
969 : {
970 : // detect fCX equal zero and truncate to real zero value in that case
971 3784 : fCX = 0.0;
972 : }
973 :
974 32687 : if( !fTools::equalZero(fAX) )
975 : {
976 : // derivative is polynomial of order 2 => use binomial formula
977 29362 : const double fD = fBX*fBX - fAX*fCX;
978 29362 : if( fD >= 0.0 )
979 : {
980 28050 : const double fS = sqrt(fD);
981 : // calculate both roots (avoiding a numerically unstable subtraction)
982 28050 : const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
983 28050 : impCheckExtremumResult(fQ / fAX, rResults);
984 28050 : if( !fTools::equalZero(fS) ) // ignore root multiplicity
985 27933 : impCheckExtremumResult(fCX / fQ, rResults);
986 : }
987 : }
988 3325 : else if( !fTools::equalZero(fBX) )
989 : {
990 : // derivative is polynomial of order 1 => one extrema
991 2696 : impCheckExtremumResult(fCX / (2 * fBX), rResults);
992 : }
993 :
994 : // calculate the y-extrema parameters by zeroing first y-derivative
995 32687 : double fCY = maControlPointA.getY() - maStartPoint.getY();
996 32687 : const double fBY = fCY + aControlDiff.getY();
997 32687 : const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY());
998 :
999 32687 : if(fTools::equalZero(fCY))
1000 : {
1001 : // detect fCY equal zero and truncate to real zero value in that case
1002 4317 : fCY = 0.0;
1003 : }
1004 :
1005 32687 : if( !fTools::equalZero(fAY) )
1006 : {
1007 : // derivative is polynomial of order 2 => use binomial formula
1008 29550 : const double fD = fBY*fBY - fAY*fCY;
1009 29550 : if( fD >= 0.0 )
1010 : {
1011 28375 : const double fS = sqrt(fD);
1012 : // calculate both roots (avoiding a numerically unstable subtraction)
1013 28375 : const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
1014 28375 : impCheckExtremumResult(fQ / fAY, rResults);
1015 28375 : if( !fTools::equalZero(fS) ) // ignore root multiplicity
1016 28257 : impCheckExtremumResult(fCY / fQ, rResults);
1017 : }
1018 : }
1019 3137 : else if( !fTools::equalZero(fBY) )
1020 : {
1021 : // derivative is polynomial of order 1 => one extrema
1022 2483 : impCheckExtremumResult(fCY / (2 * fBY), rResults);
1023 32687 : }
1024 32687 : }
1025 :
1026 : } // end of namespace basegfx
1027 :
1028 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
