Line data Source code
1 : /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 : * This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "2D.h"
7 : #include "PathAnalysis.h"
8 : #include "PathHelpers.h"
9 :
10 : namespace mozilla {
11 : namespace gfx {
12 :
13 0 : static double CubicRoot(double aValue) {
14 0 : if (aValue < 0.0) {
15 0 : return -CubicRoot(-aValue);
16 : }
17 : else {
18 0 : return pow(aValue, 1.0 / 3.0);
19 : }
20 : }
21 :
22 : struct PointD : public BasePoint<double, PointD> {
23 : typedef BasePoint<double, PointD> Super;
24 :
25 0 : PointD() : Super() {}
26 0 : PointD(double aX, double aY) : Super(aX, aY) {}
27 0 : MOZ_IMPLICIT PointD(const Point& aPoint) : Super(aPoint.x, aPoint.y) {}
28 :
29 0 : Point ToPoint() const {
30 0 : return Point(static_cast<Float>(x), static_cast<Float>(y));
31 : }
32 : };
33 :
34 : struct BezierControlPoints
35 : {
36 0 : BezierControlPoints() {}
37 0 : BezierControlPoints(const PointD &aCP1, const PointD &aCP2,
38 : const PointD &aCP3, const PointD &aCP4)
39 0 : : mCP1(aCP1), mCP2(aCP2), mCP3(aCP3), mCP4(aCP4)
40 : {
41 0 : }
42 :
43 : PointD mCP1, mCP2, mCP3, mCP4;
44 : };
45 :
46 : void
47 : FlattenBezier(const BezierControlPoints &aPoints,
48 : PathSink *aSink, double aTolerance);
49 :
50 :
51 112 : Path::Path()
52 : {
53 112 : }
54 :
55 68 : Path::~Path()
56 : {
57 68 : }
58 :
59 : Float
60 0 : Path::ComputeLength()
61 : {
62 0 : EnsureFlattenedPath();
63 0 : return mFlattenedPath->ComputeLength();
64 : }
65 :
66 : Point
67 0 : Path::ComputePointAtLength(Float aLength, Point* aTangent)
68 : {
69 0 : EnsureFlattenedPath();
70 0 : return mFlattenedPath->ComputePointAtLength(aLength, aTangent);
71 : }
72 :
73 : void
74 0 : Path::EnsureFlattenedPath()
75 : {
76 0 : if (!mFlattenedPath) {
77 0 : mFlattenedPath = new FlattenedPath();
78 0 : StreamToSink(mFlattenedPath);
79 : }
80 0 : }
81 :
82 : // This is the maximum deviation we allow (with an additional ~20% margin of
83 : // error) of the approximation from the actual Bezier curve.
84 : const Float kFlatteningTolerance = 0.0001f;
85 :
86 : void
87 0 : FlattenedPath::MoveTo(const Point &aPoint)
88 : {
89 0 : MOZ_ASSERT(!mCalculatedLength);
90 0 : FlatPathOp op;
91 0 : op.mType = FlatPathOp::OP_MOVETO;
92 0 : op.mPoint = aPoint;
93 0 : mPathOps.push_back(op);
94 :
95 0 : mLastMove = aPoint;
96 0 : }
97 :
98 : void
99 0 : FlattenedPath::LineTo(const Point &aPoint)
100 : {
101 0 : MOZ_ASSERT(!mCalculatedLength);
102 0 : FlatPathOp op;
103 0 : op.mType = FlatPathOp::OP_LINETO;
104 0 : op.mPoint = aPoint;
105 0 : mPathOps.push_back(op);
106 0 : }
107 :
108 : void
109 0 : FlattenedPath::BezierTo(const Point &aCP1,
110 : const Point &aCP2,
111 : const Point &aCP3)
112 : {
113 0 : MOZ_ASSERT(!mCalculatedLength);
114 0 : FlattenBezier(BezierControlPoints(CurrentPoint(), aCP1, aCP2, aCP3), this, kFlatteningTolerance);
115 0 : }
116 :
117 : void
118 0 : FlattenedPath::QuadraticBezierTo(const Point &aCP1,
119 : const Point &aCP2)
120 : {
121 0 : MOZ_ASSERT(!mCalculatedLength);
122 : // We need to elevate the degree of this quadratic B�zier to cubic, so we're
123 : // going to add an intermediate control point, and recompute control point 1.
124 : // The first and last control points remain the same.
125 : // This formula can be found on http://fontforge.sourceforge.net/bezier.html
126 0 : Point CP0 = CurrentPoint();
127 0 : Point CP1 = (CP0 + aCP1 * 2.0) / 3.0;
128 0 : Point CP2 = (aCP2 + aCP1 * 2.0) / 3.0;
129 0 : Point CP3 = aCP2;
130 :
131 0 : BezierTo(CP1, CP2, CP3);
132 0 : }
133 :
134 : void
135 0 : FlattenedPath::Close()
136 : {
137 0 : MOZ_ASSERT(!mCalculatedLength);
138 0 : LineTo(mLastMove);
139 0 : }
140 :
141 : void
142 0 : FlattenedPath::Arc(const Point &aOrigin, float aRadius, float aStartAngle,
143 : float aEndAngle, bool aAntiClockwise)
144 : {
145 0 : ArcToBezier(this, aOrigin, Size(aRadius, aRadius), aStartAngle, aEndAngle, aAntiClockwise);
146 0 : }
147 :
148 : Float
149 0 : FlattenedPath::ComputeLength()
150 : {
151 0 : if (!mCalculatedLength) {
152 0 : Point currentPoint;
153 :
154 0 : for (uint32_t i = 0; i < mPathOps.size(); i++) {
155 0 : if (mPathOps[i].mType == FlatPathOp::OP_MOVETO) {
156 0 : currentPoint = mPathOps[i].mPoint;
157 : } else {
158 0 : mCachedLength += Distance(currentPoint, mPathOps[i].mPoint);
159 0 : currentPoint = mPathOps[i].mPoint;
160 : }
161 : }
162 :
163 0 : mCalculatedLength = true;
164 : }
165 :
166 0 : return mCachedLength;
167 : }
168 :
169 : Point
170 0 : FlattenedPath::ComputePointAtLength(Float aLength, Point *aTangent)
171 : {
172 : // We track the last point that -wasn't- in the same place as the current
173 : // point so if we pass the edge of the path with a bunch of zero length
174 : // paths we still get the correct tangent vector.
175 0 : Point lastPointSinceMove;
176 0 : Point currentPoint;
177 0 : for (uint32_t i = 0; i < mPathOps.size(); i++) {
178 0 : if (mPathOps[i].mType == FlatPathOp::OP_MOVETO) {
179 0 : if (Distance(currentPoint, mPathOps[i].mPoint)) {
180 0 : lastPointSinceMove = currentPoint;
181 : }
182 0 : currentPoint = mPathOps[i].mPoint;
183 : } else {
184 0 : Float segmentLength = Distance(currentPoint, mPathOps[i].mPoint);
185 :
186 0 : if (segmentLength) {
187 0 : lastPointSinceMove = currentPoint;
188 0 : if (segmentLength > aLength) {
189 0 : Point currentVector = mPathOps[i].mPoint - currentPoint;
190 0 : Point tangent = currentVector / segmentLength;
191 0 : if (aTangent) {
192 0 : *aTangent = tangent;
193 : }
194 0 : return currentPoint + tangent * aLength;
195 : }
196 : }
197 :
198 0 : aLength -= segmentLength;
199 0 : currentPoint = mPathOps[i].mPoint;
200 : }
201 : }
202 :
203 0 : Point currentVector = currentPoint - lastPointSinceMove;
204 0 : if (aTangent) {
205 0 : if (hypotf(currentVector.x, currentVector.y)) {
206 0 : *aTangent = currentVector / hypotf(currentVector.x, currentVector.y);
207 : } else {
208 0 : *aTangent = Point();
209 : }
210 : }
211 0 : return currentPoint;
212 : }
213 :
214 : // This function explicitly permits aControlPoints to refer to the same object
215 : // as either of the other arguments.
216 : static void
217 0 : SplitBezier(const BezierControlPoints &aControlPoints,
218 : BezierControlPoints *aFirstSegmentControlPoints,
219 : BezierControlPoints *aSecondSegmentControlPoints,
220 : double t)
221 : {
222 0 : MOZ_ASSERT(aSecondSegmentControlPoints);
223 :
224 0 : *aSecondSegmentControlPoints = aControlPoints;
225 :
226 0 : PointD cp1a = aControlPoints.mCP1 + (aControlPoints.mCP2 - aControlPoints.mCP1) * t;
227 0 : PointD cp2a = aControlPoints.mCP2 + (aControlPoints.mCP3 - aControlPoints.mCP2) * t;
228 0 : PointD cp1aa = cp1a + (cp2a - cp1a) * t;
229 0 : PointD cp3a = aControlPoints.mCP3 + (aControlPoints.mCP4 - aControlPoints.mCP3) * t;
230 0 : PointD cp2aa = cp2a + (cp3a - cp2a) * t;
231 0 : PointD cp1aaa = cp1aa + (cp2aa - cp1aa) * t;
232 0 : aSecondSegmentControlPoints->mCP4 = aControlPoints.mCP4;
233 :
234 0 : if(aFirstSegmentControlPoints) {
235 0 : aFirstSegmentControlPoints->mCP1 = aControlPoints.mCP1;
236 0 : aFirstSegmentControlPoints->mCP2 = cp1a;
237 0 : aFirstSegmentControlPoints->mCP3 = cp1aa;
238 0 : aFirstSegmentControlPoints->mCP4 = cp1aaa;
239 : }
240 0 : aSecondSegmentControlPoints->mCP1 = cp1aaa;
241 0 : aSecondSegmentControlPoints->mCP2 = cp2aa;
242 0 : aSecondSegmentControlPoints->mCP3 = cp3a;
243 0 : }
244 :
245 : static void
246 0 : FlattenBezierCurveSegment(const BezierControlPoints &aControlPoints,
247 : PathSink *aSink,
248 : double aTolerance)
249 : {
250 : /* The algorithm implemented here is based on:
251 : * http://cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf
252 : *
253 : * The basic premise is that for a small t the third order term in the
254 : * equation of a cubic bezier curve is insignificantly small. This can
255 : * then be approximated by a quadratic equation for which the maximum
256 : * difference from a linear approximation can be much more easily determined.
257 : */
258 0 : BezierControlPoints currentCP = aControlPoints;
259 :
260 0 : double t = 0;
261 0 : while (t < 1.0) {
262 0 : PointD cp21 = currentCP.mCP2 - currentCP.mCP1;
263 0 : PointD cp31 = currentCP.mCP3 - currentCP.mCP1;
264 :
265 : /* To remove divisions and check for divide-by-zero, this is optimized from:
266 : * Float s3 = (cp31.x * cp21.y - cp31.y * cp21.x) / hypotf(cp21.x, cp21.y);
267 : * t = 2 * Float(sqrt(aTolerance / (3. * std::abs(s3))));
268 : */
269 0 : double cp21x31 = cp31.x * cp21.y - cp31.y * cp21.x;
270 0 : double h = hypot(cp21.x, cp21.y);
271 0 : if (cp21x31 * h == 0) {
272 0 : break;
273 : }
274 :
275 0 : double s3inv = h / cp21x31;
276 0 : t = 2 * sqrt(aTolerance * std::abs(s3inv) / 3.);
277 0 : if (t >= 1.0) {
278 0 : break;
279 : }
280 :
281 0 : SplitBezier(currentCP, nullptr, ¤tCP, t);
282 :
283 0 : aSink->LineTo(currentCP.mCP1.ToPoint());
284 : }
285 :
286 0 : aSink->LineTo(currentCP.mCP4.ToPoint());
287 0 : }
288 :
289 : static inline void
290 0 : FindInflectionApproximationRange(BezierControlPoints aControlPoints,
291 : double *aMin, double *aMax, double aT,
292 : double aTolerance)
293 : {
294 0 : SplitBezier(aControlPoints, nullptr, &aControlPoints, aT);
295 :
296 0 : PointD cp21 = aControlPoints.mCP2 - aControlPoints.mCP1;
297 0 : PointD cp41 = aControlPoints.mCP4 - aControlPoints.mCP1;
298 :
299 0 : if (cp21.x == 0. && cp21.y == 0.) {
300 : // In this case s3 becomes lim[n->0] (cp41.x * n) / n - (cp41.y * n) / n = cp41.x - cp41.y.
301 :
302 : // Use the absolute value so that Min and Max will correspond with the
303 : // minimum and maximum of the range.
304 0 : *aMin = aT - CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
305 0 : *aMax = aT + CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
306 0 : return;
307 : }
308 :
309 0 : double s3 = (cp41.x * cp21.y - cp41.y * cp21.x) / hypot(cp21.x, cp21.y);
310 :
311 0 : if (s3 == 0) {
312 : // This means within the precision we have it can be approximated
313 : // infinitely by a linear segment. Deal with this by specifying the
314 : // approximation range as extending beyond the entire curve.
315 0 : *aMin = -1.0;
316 0 : *aMax = 2.0;
317 0 : return;
318 : }
319 :
320 0 : double tf = CubicRoot(std::abs(aTolerance / s3));
321 :
322 0 : *aMin = aT - tf * (1 - aT);
323 0 : *aMax = aT + tf * (1 - aT);
324 : }
325 :
326 : /* Find the inflection points of a bezier curve. Will return false if the
327 : * curve is degenerate in such a way that it is best approximated by a straight
328 : * line.
329 : *
330 : * The below algorithm was written by Jeff Muizelaar <jmuizelaar@mozilla.com>, explanation follows:
331 : *
332 : * The lower inflection point is returned in aT1, the higher one in aT2. In the
333 : * case of a single inflection point this will be in aT1.
334 : *
335 : * The method is inspired by the algorithm in "analysis of in?ection points for planar cubic bezier curve"
336 : *
337 : * Here are some differences between this algorithm and versions discussed elsewhere in the literature:
338 : *
339 : * zhang et. al compute a0, d0 and e0 incrementally using the follow formula:
340 : *
341 : * Point a0 = CP2 - CP1
342 : * Point a1 = CP3 - CP2
343 : * Point a2 = CP4 - CP1
344 : *
345 : * Point d0 = a1 - a0
346 : * Point d1 = a2 - a1
347 :
348 : * Point e0 = d1 - d0
349 : *
350 : * this avoids any multiplications and may or may not be faster than the approach take below.
351 : *
352 : * "fast, precise flattening of cubic bezier path and ofset curves" by hain et. al
353 : * Point a = CP1 + 3 * CP2 - 3 * CP3 + CP4
354 : * Point b = 3 * CP1 - 6 * CP2 + 3 * CP3
355 : * Point c = -3 * CP1 + 3 * CP2
356 : * Point d = CP1
357 : * the a, b, c, d can be expressed in terms of a0, d0 and e0 defined above as:
358 : * c = 3 * a0
359 : * b = 3 * d0
360 : * a = e0
361 : *
362 : *
363 : * a = 3a = a.y * b.x - a.x * b.y
364 : * b = 3b = a.y * c.x - a.x * c.y
365 : * c = 9c = b.y * c.x - b.x * c.y
366 : *
367 : * The additional multiples of 3 cancel each other out as show below:
368 : *
369 : * x = (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
370 : * x = (-3 * b + sqrt(3 * b * 3 * b - 4 * a * 3 * 9 * c / 3)) / (2 * 3 * a)
371 : * x = 3 * (-b + sqrt(b * b - 4 * a * c)) / (2 * 3 * a)
372 : * x = (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
373 : *
374 : * I haven't looked into whether the formulation of the quadratic formula in
375 : * hain has any numerical advantages over the one used below.
376 : */
377 : static inline void
378 0 : FindInflectionPoints(const BezierControlPoints &aControlPoints,
379 : double *aT1, double *aT2, uint32_t *aCount)
380 : {
381 : // Find inflection points.
382 : // See www.faculty.idc.ac.il/arik/quality/appendixa.html for an explanation
383 : // of this approach.
384 0 : PointD A = aControlPoints.mCP2 - aControlPoints.mCP1;
385 0 : PointD B = aControlPoints.mCP3 - (aControlPoints.mCP2 * 2) + aControlPoints.mCP1;
386 0 : PointD C = aControlPoints.mCP4 - (aControlPoints.mCP3 * 3) + (aControlPoints.mCP2 * 3) - aControlPoints.mCP1;
387 :
388 0 : double a = B.x * C.y - B.y * C.x;
389 0 : double b = A.x * C.y - A.y * C.x;
390 0 : double c = A.x * B.y - A.y * B.x;
391 :
392 0 : if (a == 0) {
393 : // Not a quadratic equation.
394 0 : if (b == 0) {
395 : // Instead of a linear acceleration change we have a constant
396 : // acceleration change. This means the equation has no solution
397 : // and there are no inflection points, unless the constant is 0.
398 : // In that case the curve is a straight line, essentially that means
399 : // the easiest way to deal with is is by saying there's an inflection
400 : // point at t == 0. The inflection point approximation range found will
401 : // automatically extend into infinity.
402 0 : if (c == 0) {
403 0 : *aCount = 1;
404 0 : *aT1 = 0;
405 0 : return;
406 : }
407 0 : *aCount = 0;
408 0 : return;
409 : }
410 0 : *aT1 = -c / b;
411 0 : *aCount = 1;
412 0 : return;
413 : } else {
414 0 : double discriminant = b * b - 4 * a * c;
415 :
416 0 : if (discriminant < 0) {
417 : // No inflection points.
418 0 : *aCount = 0;
419 0 : } else if (discriminant == 0) {
420 0 : *aCount = 1;
421 0 : *aT1 = -b / (2 * a);
422 : } else {
423 : /* Use the following formula for computing the roots:
424 : *
425 : * q = -1/2 * (b + sign(b) * sqrt(b^2 - 4ac))
426 : * t1 = q / a
427 : * t2 = c / q
428 : */
429 0 : double q = sqrt(discriminant);
430 0 : if (b < 0) {
431 0 : q = b - q;
432 : } else {
433 0 : q = b + q;
434 : }
435 0 : q *= -1./2;
436 :
437 0 : *aT1 = q / a;
438 0 : *aT2 = c / q;
439 0 : if (*aT1 > *aT2) {
440 0 : std::swap(*aT1, *aT2);
441 : }
442 0 : *aCount = 2;
443 : }
444 : }
445 :
446 0 : return;
447 : }
448 :
449 : void
450 0 : FlattenBezier(const BezierControlPoints &aControlPoints,
451 : PathSink *aSink, double aTolerance)
452 : {
453 : double t1;
454 : double t2;
455 : uint32_t count;
456 :
457 0 : FindInflectionPoints(aControlPoints, &t1, &t2, &count);
458 :
459 : // Check that at least one of the inflection points is inside [0..1]
460 0 : if (count == 0 || ((t1 < 0.0 || t1 >= 1.0) && (count == 1 || (t2 < 0.0 || t2 >= 1.0))) ) {
461 0 : FlattenBezierCurveSegment(aControlPoints, aSink, aTolerance);
462 0 : return;
463 : }
464 :
465 0 : double t1min = t1, t1max = t1, t2min = t2, t2max = t2;
466 :
467 0 : BezierControlPoints remainingCP = aControlPoints;
468 :
469 : // For both inflection points, calulate the range where they can be linearly
470 : // approximated if they are positioned within [0,1]
471 0 : if (count > 0 && t1 >= 0 && t1 < 1.0) {
472 0 : FindInflectionApproximationRange(aControlPoints, &t1min, &t1max, t1, aTolerance);
473 : }
474 0 : if (count > 1 && t2 >= 0 && t2 < 1.0) {
475 0 : FindInflectionApproximationRange(aControlPoints, &t2min, &t2max, t2, aTolerance);
476 : }
477 0 : BezierControlPoints nextCPs = aControlPoints;
478 0 : BezierControlPoints prevCPs;
479 :
480 : // Process ranges. [t1min, t1max] and [t2min, t2max] are approximated by line
481 : // segments.
482 0 : if (count == 1 && t1min <= 0 && t1max >= 1.0) {
483 : // The whole range can be approximated by a line segment.
484 0 : aSink->LineTo(aControlPoints.mCP4.ToPoint());
485 0 : return;
486 : }
487 :
488 0 : if (t1min > 0) {
489 : // Flatten the Bezier up until the first inflection point's approximation
490 : // point.
491 : SplitBezier(aControlPoints, &prevCPs,
492 0 : &remainingCP, t1min);
493 0 : FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
494 : }
495 0 : if (t1max >= 0 && t1max < 1.0 && (count == 1 || t2min > t1max)) {
496 : // The second inflection point's approximation range begins after the end
497 : // of the first, approximate the first inflection point by a line and
498 : // subsequently flatten up until the end or the next inflection point.
499 0 : SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
500 :
501 0 : aSink->LineTo(nextCPs.mCP1.ToPoint());
502 :
503 0 : if (count == 1 || (count > 1 && t2min >= 1.0)) {
504 : // No more inflection points to deal with, flatten the rest of the curve.
505 0 : FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
506 : }
507 0 : } else if (count > 1 && t2min > 1.0) {
508 : // We've already concluded t2min <= t1max, so if this is true the
509 : // approximation range for the first inflection point runs past the
510 : // end of the curve, draw a line to the end and we're done.
511 0 : aSink->LineTo(aControlPoints.mCP4.ToPoint());
512 0 : return;
513 : }
514 :
515 0 : if (count > 1 && t2min < 1.0 && t2max > 0) {
516 0 : if (t2min > 0 && t2min < t1max) {
517 : // In this case the t2 approximation range starts inside the t1
518 : // approximation range.
519 0 : SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
520 0 : aSink->LineTo(nextCPs.mCP1.ToPoint());
521 0 : } else if (t2min > 0 && t1max > 0) {
522 0 : SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
523 :
524 : // Find a control points describing the portion of the curve between t1max and t2min.
525 0 : double t2mina = (t2min - t1max) / (1 - t1max);
526 0 : SplitBezier(nextCPs, &prevCPs, &nextCPs, t2mina);
527 0 : FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
528 0 : } else if (t2min > 0) {
529 : // We have nothing interesting before t2min, find that bit and flatten it.
530 0 : SplitBezier(aControlPoints, &prevCPs, &nextCPs, t2min);
531 0 : FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
532 : }
533 0 : if (t2max < 1.0) {
534 : // Flatten the portion of the curve after t2max
535 0 : SplitBezier(aControlPoints, nullptr, &nextCPs, t2max);
536 :
537 : // Draw a line to the start, this is the approximation between t2min and
538 : // t2max.
539 0 : aSink->LineTo(nextCPs.mCP1.ToPoint());
540 0 : FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
541 : } else {
542 : // Our approximation range extends beyond the end of the curve.
543 0 : aSink->LineTo(aControlPoints.mCP4.ToPoint());
544 0 : return;
545 : }
546 : }
547 : }
548 :
549 : } // namespace gfx
550 : } // namespace mozilla
|
