1// [Blend2D]
2// 2D Vector Graphics Powered by a JIT Compiler.
3//
4// [License]
5// Zlib - See LICENSE.md file in the package.
6
7#include "./blapi-build_p.h"
8#include "./bltables_p.h"
9#include "./blgeometry_p.h"
10#include "./blmath_p.h"
11#include "./blmatrix_p.h"
12#include "./blpath_p.h"
13#include "./blpathstroke_p.h"
14
15// ============================================================================
16// [Constants]
17// ============================================================================
18
19// Default minimum miter-join length that always bypasses any other join-type.
20// The reason behind this is to prevent emitting very small line segments in
21// case that normals of joining segments are almost equal.
22static constexpr double BL_STROKE_MITER_MINIMUM = 1e-10;
23static constexpr double BL_STROKE_MITER_MINIMUM_SQ = blSquare(BL_STROKE_MITER_MINIMUM);
24
25// Minimum length for a line/curve the stroker will accept. If the segment is
26// smaller than this it would be skipped.
27static constexpr double BL_STROKE_LENGHT_EPSILON = 1e-10;
28static constexpr double BL_STROKE_LENGTH_EPSILON_SQ = blSquare(BL_STROKE_LENGHT_EPSILON);
29
30static constexpr double BL_STROKE_COLLINEARITY_EPSILON = 1e-10;
31static constexpr double BL_STROKE_COLLINEARITY_EPSILON_SQ = blSquare(BL_STROKE_COLLINEARITY_EPSILON);
32
33static constexpr double BL_STROKE_CUSP_T_THRESHOLD = 1e-10;
34static constexpr double BL_STROKE_DEGENERATE_FLATNESS = 1e-6;
35
36// Minimum vertices that would be required for any join + additional line.
37//
38// Calculated from:
39// JOIN:
40// bevel: 1 vertex
41// miter: 3 vertices
42// round: 7 vertices (2 cubics at most)
43// ADDITIONAL:
44// end-point: 1 vertex
45// line-to : 1 vertex
46static constexpr size_t BL_STROKE_MIN_JOIN_VERTICES = 9;
47
48struct BLStrokeCapVertexCountGen {
49 static constexpr uint8_t value(size_t cap) noexcept {
50 return cap == BL_STROKE_CAP_SQUARE ? 3 :
51 cap == BL_STROKE_CAP_ROUND ? 6 :
52 cap == BL_STROKE_CAP_ROUND_REV ? 8 :
53 cap == BL_STROKE_CAP_TRIANGLE ? 2 :
54 cap == BL_STROKE_CAP_TRIANGLE_REV ? 4 :
55 cap == BL_STROKE_CAP_BUTT ? 1 : 1; // Default if not known.
56 }
57};
58
59static const auto blStrokeCapVertexCountTable =
60 blLookupTable<uint8_t, BL_STROKE_CAP_COUNT, BLStrokeCapVertexCountGen>();
61
62// ============================================================================
63// [BLPathStroker - Utilities]
64// ============================================================================
65
66static BL_INLINE uint32_t blSanityStrokeCap(uint32_t cap) noexcept {
67 return cap < BL_STROKE_CAP_COUNT ? cap : BL_STROKE_CAP_BUTT;
68}
69
70static BL_INLINE bool blIsMiterJoinCategory(uint32_t joinType) noexcept {
71 return joinType == BL_STROKE_JOIN_MITER_CLIP ||
72 joinType == BL_STROKE_JOIN_MITER_BEVEL ||
73 joinType == BL_STROKE_JOIN_MITER_ROUND ;
74}
75
76static BL_INLINE uint32_t blMiterJoinToSimpleJoin(uint32_t joinType) {
77 if (joinType == BL_STROKE_JOIN_MITER_BEVEL)
78 return BL_STROKE_JOIN_BEVEL;
79 else if (joinType == BL_STROKE_JOIN_MITER_ROUND)
80 return BL_STROKE_JOIN_ROUND;
81 else
82 return joinType;
83}
84
85static BL_INLINE bool blTestInnerJoinIntersecion(const BLPoint& a0, const BLPoint& a1, const BLPoint& b0, const BLPoint& b1, const BLPoint& join) noexcept {
86 BLPoint min = blMax(blMin(a0, a1), blMin(b0, b1));
87 BLPoint max = blMin(blMax(a0, a1), blMax(b0, b1));
88
89 return (join.x >= min.x) & (join.y >= min.y) &
90 (join.x <= max.x) & (join.y <= max.y) ;
91}
92
93// TODO: ???
94template<typename T>
95BL_INLINE T signBySide(const T& in, uint32_t side) noexcept {
96 return side ? in : -in;
97}
98
99// ============================================================================
100// BLPathStroker - Implementation]
101// ============================================================================
102
103class BLPathStroker {
104public:
105 enum Flags : uint32_t {
106 kFlagIsOpen = 0x01,
107 kFlagIsClosed = 0x02
108 };
109
110 enum Side : uint32_t {
111 kSideA = 0,
112 kSideB = 1
113 };
114
115 // Stroke input.
116 BLPathIterator _iter;
117
118 // Stroke options.
119 const BLStrokeOptions& _options;
120 const BLApproximationOptions& _approx;
121
122 double _d; // Distance (StrokeWidth / 2).
123 double _d2; // Distance multiplied by 2.
124 double _miterLimit; // Miter limit possibly clamped to a safe range.
125 double _miterLimitSq; // Miter limit squared.
126 uint32_t _joinType; // Simplified join type.
127
128 // Stroke output.
129 BLPath* _aPath; // Output path A (contains offsetted figure and possible end cap).
130 BLPath* _bPath; // Output path B (contains offsetted figure that has to be reversed).
131 BLPath* _cPath; // Output path C (contains possible start cap).
132
133 BLPathAppender _aOut; // Appender of `_aPath`.
134 BLPathAppender _bOut; // Appender of `_bPath`.
135 size_t _aInitialSize; // Initial size of `_aPath`.
136
137 // Global state.
138 BLPoint _p0; // Current point.
139 BLPoint _n0; // Unit normal of `_p0`.
140 BLPoint _pInitial; // Initial point (MoveTo).
141 BLPoint _nInitial; // Unit normal of `_pInitial`.
142 uint32_t _flags; // Work flags.
143
144 BL_INLINE BLPathStroker(const BLPathView& input, const BLStrokeOptions& options, const BLApproximationOptions& approx, BLPath* a, BLPath* b, BLPath* c) noexcept
145 : _iter(input),
146 _options(options),
147 _approx(approx),
148 _d(options.width * 0.5),
149 _d2(options.width),
150 _joinType(options.join),
151 _aPath(a),
152 _bPath(b),
153 _cPath(c),
154 _aOut(),
155 _bOut(),
156 _aInitialSize(0) {
157
158 // Initialize miter calculation options. What we do here is to change
159 // `_joinType` to a value that would be easier for us to use during
160 // joining. We always honor `_miterLimitSq` even when the `_joinType`
161 // is not miter to prevent emitting very small line segments next to
162 // next other, which saves vertices and also prevents border cases in
163 // additional processing.
164 if (blIsMiterJoinCategory(_joinType)) {
165 // Simplify miter-join type to non-miter join, if possible.
166 _joinType = blMiterJoinToSimpleJoin(_joinType);
167
168 // Final miter limit is `0.5 * width * miterLimit`.
169 _miterLimit = _d * options.miterLimit;
170 _miterLimitSq = blSquare(_miterLimit);
171 }
172 else {
173 _miterLimit = BL_STROKE_MITER_MINIMUM;
174 _miterLimitSq = BL_STROKE_MITER_MINIMUM_SQ;
175 }
176 }
177
178 BL_INLINE bool isOpen() const noexcept { return (_flags & kFlagIsOpen) != 0; }
179 BL_INLINE bool isClosed() const noexcept { return (_flags & kFlagIsClosed) != 0; }
180
181 BL_INLINE BLResult stroke(BLPathStrokeSinkFunc sink, void* closure) noexcept {
182 size_t estimatedSize = _iter.remainingForward() * 2u;
183 BL_PROPAGATE(_aPath->reserve(_aPath->size() + estimatedSize));
184
185 while (!_iter.atEnd()) {
186 // Start of the figure.
187 if (BL_UNLIKELY(_iter.cmd[0] != BL_PATH_CMD_MOVE)) {
188 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
189 }
190
191 _aInitialSize = _aPath->size();
192 BL_PROPAGATE(_aOut.begin(_aPath, BL_MODIFY_OP_APPEND_GROW, _iter.remainingForward()));
193 BL_PROPAGATE(_bOut.begin(_bPath, BL_MODIFY_OP_ASSIGN_GROW, 48));
194
195 BLPoint polyPts[4];
196 size_t polySize;
197
198 _p0 = *_iter.vtx;
199 _pInitial = _p0;
200 _flags = 0;
201
202 // Content of the figure.
203 _iter++;
204 while (!_iter.atEnd()) {
205 BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES));
206 BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES));
207
208 uint8_t cmd = _iter.cmd[0]; // Next command.
209 BLPoint p1 = _iter.vtx[0]; // Next line-to or control point.
210 BLPoint v1; // Vector of `p1 - _p0`.
211 BLPoint n1; // Unit normal of `v1`.
212
213 if (cmd == BL_PATH_CMD_ON) {
214 // Line command, collinear curve converted to line or close of the figure.
215 _iter++;
216LineTo:
217 v1 = p1 - _p0;
218 if (blLengthSq(v1) < BL_STROKE_LENGTH_EPSILON_SQ)
219 continue;
220
221 n1 = blNormal(blUnitVector(v1));
222 if (!isOpen())
223 BL_PROPAGATE(openLineTo(p1, n1));
224 else
225 BL_PROPAGATE(joinLineTo(p1, n1));
226 continue;
227
228 // This is again to minimize inline expansion of `smoothPolyTo()`.
229SmoothPolyTo:
230 BL_PROPAGATE(smoothPolyTo(polyPts, polySize));
231 continue;
232 }
233 else if (cmd == BL_PATH_CMD_QUAD) {
234 // Quadratic curve segment.
235 _iter += 2;
236 if (BL_UNLIKELY(_iter.afterEnd()))
237 return BL_ERROR_INVALID_GEOMETRY;
238
239 const BLPoint* quad = _iter.vtx - 3;
240 BLPoint p2 = quad[2];
241 BLPoint v2 = p2 - p1;
242
243 v1 = p1 - _p0;
244 n1 = blNormal(blUnitVector(v1));
245
246 double cm = blCrossProduct(v2, v1);
247 if (blAbs(cm) <= BL_STROKE_COLLINEARITY_EPSILON) {
248 // All points are [almost] collinear (degenerate case).
249 double dot = blDotProduct(-v1, v2);
250
251 // Check if control point lies outside of the start/end points.
252 if (dot > 0.0) {
253 // Rotate all points to x-axis.
254 double r1 = blDotProduct(p1 - _p0, v1);
255 double r2 = blDotProduct(p2 - _p0, v1);
256
257 // Parameter of the cusp if it's within (0, 1).
258 double t = r1 / (2.0 * r1 - r2);
259 if (t > 0.0 && t < 1.0) {
260 polyPts[0] = blGetQuadValueAt(quad, t);
261 polyPts[1] = p2;
262 polySize = 2;
263 goto SmoothPolyTo;
264 }
265 }
266
267 // Collinear without cusp => straight line.
268 p1 = p2;
269 goto LineTo;
270 }
271
272 // Very small curve segment => straight line.
273 if (blLengthSq(v1) < BL_STROKE_LENGTH_EPSILON_SQ || blLengthSq(v2) < BL_STROKE_LENGTH_EPSILON_SQ) {
274 p1 = p2;
275 goto LineTo;
276 }
277
278 if (!isOpen())
279 BL_PROPAGATE(openCurve(n1));
280 else
281 BL_PROPAGATE(joinCurve(n1));
282
283 BL_PROPAGATE(offsetQuad(_iter.vtx - 3));
284 }
285 else if (cmd == BL_PATH_CMD_CUBIC) {
286 // Cubic curve segment.
287 _iter += 3;
288 if (BL_UNLIKELY(_iter.afterEnd()))
289 return BL_ERROR_INVALID_GEOMETRY;
290
291 BLPoint p[7];
292
293 int cusp = 0;
294 double tCusp = 0;
295
296 p[0] = _p0;
297 p[1] = _iter.vtx[-3];
298 p[2] = _iter.vtx[-2];
299 p[3] = _iter.vtx[-1];
300
301 // Check if the curve is flat enough to be potentially degenerate.
302 if (blIsCubicFlat(p, BL_STROKE_DEGENERATE_FLATNESS)) {
303 double dot1 = blDotProduct(p[0] - p[1], p[3] - p[1]);
304 double dot2 = blDotProduct(p[0] - p[2], p[3] - p[2]);
305
306 if (!(dot1 < 0.0) || !(dot2 < 0.0)) {
307 // Rotate all points to x-axis.
308 const BLPoint r = blGetCubicStartTangent(p);
309
310 double r1 = blDotProduct(p[1] - p[0], r);
311 double r2 = blDotProduct(p[2] - p[0], r);
312 double r3 = blDotProduct(p[3] - p[0], r);
313
314 double a = 1.0 / (3.0 * r1 - 3.0 * r2 + r3);
315 double b = 2.0 * r1 - r2;
316 double s = blSqrt(r2 * (r2 - r1) - r1 * (r3 - r1));
317
318 // Parameters of the cusps.
319 double t1 = a * (b - s);
320 double t2 = a * (b + s);
321
322 // Offset the first and second cusps (if they exist).
323 polySize = 0;
324 if (t1 > BL_STROKE_CUSP_T_THRESHOLD && t1 < 1.0 - BL_STROKE_CUSP_T_THRESHOLD)
325 polyPts[polySize++] = blGetCubicValueAt(p, t1);
326
327 if (t2 > BL_STROKE_CUSP_T_THRESHOLD && t2 < 1.0 - BL_STROKE_CUSP_T_THRESHOLD)
328 polyPts[polySize++] = blGetCubicValueAt(p, t2);
329
330 if (polySize == 0) {
331 p1 = p[3];
332 goto LineTo;
333 }
334
335 polyPts[polySize++] = p[3];
336 goto SmoothPolyTo;
337 }
338 else {
339 p1 = p[3];
340 goto LineTo;
341 }
342 }
343 else {
344 double tl;
345 blGetCubicInflectionParameter(p, tCusp, tl);
346
347 if (tl == 0.0 && tCusp > 0.0 && tCusp < 1.0) {
348 blSplitCubic(p, p, p + 3);
349 cusp = 1;
350 }
351 }
352
353 for (;;) {
354 v1 = p[1] - _p0;
355 if (blIsZero(v1))
356 v1 = p[2] - _p0;
357 n1 = blNormal(blUnitVector(v1));
358
359 if (!isOpen())
360 BL_PROPAGATE(openCurve(n1));
361 else if (cusp >= 0)
362 BL_PROPAGATE(joinCurve(n1));
363 else
364 BL_PROPAGATE(joinCusp(n1));
365
366 BL_PROPAGATE(offsetCubic(p));
367 if (cusp <= 0)
368 break;
369
370 // Second part of the cubic after the cusp. We assign `-1` to `cusp`
371 // so we can call `joinCusp()` later. This is a special join that we
372 // need in this case.
373 BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES));
374 BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES));
375
376 cusp = -1;
377 p[0] = p[3];
378 p[1] = p[4];
379 p[2] = p[5];
380 p[3] = p[6];
381 }
382 }
383 else {
384 // Either invalid command or close of the figure. If the figure is
385 // already closed it means that we have already jumped to `LineTo`
386 // and we should terminate now. Otherwise we just encountered close
387 // or something else which is not part of the current figure.
388 if (isClosed())
389 break;
390
391 if (cmd != BL_PATH_CMD_CLOSE)
392 break;
393
394 // The figure is closed. We just jump to `LineTo` to minimize inlining
395 // expansion and mark the figure as closed. Next time we terminate on
396 // `isClosed()` condition above.
397 _flags |= kFlagIsClosed;
398 p1 = _pInitial;
399 goto LineTo;
400 }
401 }
402
403 // Don't emit anything if the figure has no points (and thus no direction).
404 _iter += size_t(isClosed());
405 if (!isOpen())
406 continue;
407
408 if (isClosed()) {
409 // The figure is closed => the end result is two closed figures without
410 // caps. In this case only paths A and B have a content, path C will be
411 // empty and should be thus ignored by the sink.
412
413 // Allocate space for the end join and close command.
414 BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES + 1));
415 BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES + 1));
416
417 BL_PROPAGATE(joinEndPoint(_nInitial));
418 _aOut.close();
419 _bOut.close();
420 _cPath->clear();
421 }
422 else {
423 // The figure is open => the end result is a single figure with caps.
424 // In this case the paths contain the following:
425 // A - Offset of the figure and end cap.
426 // B - Offset of the figure that MUST BE reversed.
427 // C - Start cap (not reversed).
428 uint32_t startCap = blSanityStrokeCap(_options.startCap);
429 uint32_t endCap = blSanityStrokeCap(_options.endCap);
430
431 BL_PROPAGATE(_aOut.ensure(_aPath, blStrokeCapVertexCountTable[endCap]));
432 BL_PROPAGATE(addCap(_aOut, _p0, _bOut.vtx[-1], endCap));
433
434 BLPathAppender cOut;
435 BL_PROPAGATE(cOut.begin(_cPath, BL_MODIFY_OP_ASSIGN_GROW, blStrokeCapVertexCountTable[startCap] + 1));
436 cOut.moveTo(_bPath->vertexData()[0]);
437 BL_PROPAGATE(addCap(cOut, _pInitial, _aPath->vertexData()[_aInitialSize], startCap));
438 cOut.done(_cPath);
439 }
440
441 _aOut.done(_aPath);
442 _bOut.done(_bPath);
443
444 // Call the path to the provided sink with resulting paths.
445 BL_PROPAGATE(sink(_aPath, _bPath, _cPath, closure));
446 }
447
448 return BL_SUCCESS;
449 }
450
451 // Opens a new figure with a line segment starting from the current point
452 // and ending at `p1`. The `n1` is a normal calculated from a unit vector
453 // of `p1 - _p0`.
454 //
455 // This function can only be called after we have at least two vertices that
456 // form the line. These vertices cannot be a single point as that would mean
457 // that we cannot calculate unit vector and then normal for the offset. This
458 // must be handled before calling `openLineTo()`.
459 //
460 // NOTE: Path cannot be open when calling this function.
461 BL_INLINE BLResult openLineTo(const BLPoint& p1, const BLPoint& n1) noexcept {
462 BL_ASSERT(!isOpen());
463 BLPoint w = n1 * _d;
464
465 _aOut.moveTo(_p0 + w);
466 _bOut.moveTo(_p0 - w);
467
468 _p0 = p1;
469 _n0 = n1;
470 _nInitial = n1;
471
472 _aOut.lineTo(_p0 + w);
473 _bOut.lineTo(_p0 - w);
474
475 _flags |= kFlagIsOpen;
476 return BL_SUCCESS;
477 }
478
479 // Joins line-to segment described by `p1` point and `n1` normal.
480 BL_INLINE BLResult joinLineTo(const BLPoint& p1, const BLPoint& n1) noexcept {
481 BLPoint w1 = n1 * _d;
482 BLPoint a1 = p1 + w1;
483 BLPoint b1 = p1 - w1;
484
485 if (_n0 == n1) {
486 // Collinear case - patch the previous point(s) if they connect lines.
487 _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON);
488 _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON);
489 }
490 else {
491 BLPoint m = _n0 + n1;
492 BLPoint k = (_d2 * m) / blLengthSq(m);
493
494 double dir = blCrossProduct(_n0, n1);
495 size_t miterFlag = 0;
496
497 if (dir < 0) {
498 // A is outer, B is inner.
499 outerJoin(_aOut, kSideA, n1, w1, k, miterFlag);
500 _aOut.back(miterFlag);
501 innerJoinLineTo(_bOut, _p0 - w1, b1, _p0 - k);
502 }
503 else {
504 // B is outer, A is inner.
505 outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag);
506 _bOut.back(miterFlag);
507 innerJoinLineTo(_aOut, _p0 + w1, a1, _p0 + k);
508 }
509 }
510
511 _aOut.lineTo(a1);
512 _bOut.lineTo(b1);
513
514 _p0 = p1;
515 _n0 = n1;
516 return BL_SUCCESS;
517 }
518
519 // Opens a new figure at the current point `_p0`. The first vertex (MOVE) is
520 // calculated by offsetting `_p0` by the given unit normal `n0`.
521 //
522 // NOTE: Path cannot be open when calling this function.
523 BL_INLINE BLResult openCurve(const BLPoint& n0) noexcept {
524 BL_ASSERT(!isOpen());
525 BLPoint w = n0 * _d;
526
527 _aOut.moveTo(_p0 + w);
528 _bOut.moveTo(_p0 - w);
529
530 _n0 = n0;
531 _nInitial = n0;
532
533 _flags |= kFlagIsOpen;
534 return BL_SUCCESS;
535 }
536
537 // Joins curve-to segment.
538 BL_INLINE BLResult joinCurve(const BLPoint& n1) noexcept {
539 BLPoint w1 = n1 * _d;
540
541 if (_n0 == n1) {
542 // Collinear case - do nothing.
543 }
544 else {
545 BLPoint m = _n0 + n1;
546 BLPoint k = (_d2 * m) / blLengthSq(m);
547
548 double dir = blCrossProduct(_n0, n1);
549 size_t miterFlag;
550
551 if (dir < 0) {
552 // A is outer, B is inner.
553 outerJoin(_aOut, kSideA, n1, w1, k, miterFlag);
554 innerJoinCurveTo(_bOut, _p0 - w1);
555 }
556 else {
557 // B is outer, A is inner.
558 outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag);
559 innerJoinCurveTo(_aOut, _p0 + w1);
560 }
561
562 _n0 = n1;
563 }
564
565 return BL_SUCCESS;
566 }
567
568 BL_INLINE BLResult joinCusp(const BLPoint& n1) noexcept {
569 BLPoint w1 = n1 * _d;
570
571 double dir = blCrossProduct(_n0, n1);
572 if (dir < 0) {
573 // A is outer, B is inner.
574 dullRoundJoin(_aOut, kSideA, n1, w1);
575 _bOut.lineTo(_p0 - w1);
576 }
577 else {
578 // B is outer, A is inner.
579 dullRoundJoin(_bOut, kSideB, n1, -w1);
580 _aOut.lineTo(_p0 + w1);
581 }
582
583 _n0 = n1;
584 return BL_SUCCESS;
585 }
586
587 BL_INLINE BLResult smoothPolyTo(const BLPoint* poly, size_t count) noexcept {
588 BL_ASSERT(count >= 2);
589
590 BLPoint p1 = poly[0];
591 BLPoint v1 = p1 - _p0;
592 BLPoint n1 = blNormal(blUnitVector(v1));
593
594 if (!isOpen())
595 BL_PROPAGATE(openLineTo(p1, n1));
596 else
597 BL_PROPAGATE(joinLineTo(p1, n1));
598
599 // We have already ensured vertices for `openLineTo()` and `joinLineTo()`,
600 // however, we need more vertices for consecutive joins and line segments.
601 BL_PROPAGATE(_aOut.ensure(_aPath, (count - 1) * BL_STROKE_MIN_JOIN_VERTICES));
602 BL_PROPAGATE(_bOut.ensure(_bPath, (count - 1) * BL_STROKE_MIN_JOIN_VERTICES));
603
604 for (size_t i = 1; i < count; i++) {
605 p1 = poly[i];
606 v1 = p1 - _p0;
607 n1 = blNormal(blUnitVector(v1));
608
609 BL_PROPAGATE(joinCusp(n1));
610 BLPoint w1 = n1 * _d;
611
612 _aOut.lineTo(p1 + w1);
613 _bOut.lineTo(p1 - w1);
614
615 _p0 = p1;
616 _n0 = n1;
617 }
618
619 return BL_SUCCESS;
620 }
621
622 // Joins end point that is only applied to closed figures.
623 BL_INLINE BLResult joinEndPoint(const BLPoint& n1) noexcept {
624 BLPoint w1 = n1 * _d;
625
626 if (_n0 == n1) {
627 // Collinear case - patch the previous point(s) if they connect lines.
628 _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON);
629 _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON);
630 return BL_SUCCESS;
631 }
632
633 BLPoint m = _n0 + n1;
634 BLPoint k = (_d2 * m) / blLengthSq(m);
635
636 BLPoint* aStartVtx = _aPath->impl->vertexData + _aInitialSize;
637 uint8_t* aStartCmd = _aPath->impl->commandData + _aInitialSize;
638
639 BLPoint* bStartVtx = _bPath->impl->vertexData;
640 uint8_t* bStartCmd = _bPath->impl->commandData;
641
642 double dir = blCrossProduct(_n0, n1);
643 size_t miterFlag = 0;
644
645 if (dir < 0) {
646 // A is outer, B is inner.
647 outerJoin(_aOut, kSideA, n1, w1, k, miterFlag);
648
649 // Shift the start point to be at the miter intersection and remove the
650 // Line from the intersection to the start of A path if miter was applied.
651 if (miterFlag) {
652 if (aStartCmd[1] == BL_PATH_CMD_ON) {
653 _aOut.back();
654 aStartVtx[0] = _aOut.vtx[-1];
655 _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON);
656 }
657 }
658
659 if (bStartCmd[1] <= BL_PATH_CMD_ON)
660 innerJoinEndPoint(_bOut, bStartVtx[0], bStartVtx[1], _p0 - k);
661 }
662 else {
663 // B is outer, A is inner.
664 outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag);
665
666 // Shift the start point to be at the miter intersection and remove the
667 // Line from the intersection to the start of B path if miter was applied.
668 if (miterFlag) {
669 if (bStartCmd[1] == BL_PATH_CMD_ON) {
670 _bOut.back();
671 bStartVtx[0] = _bOut.vtx[-1];
672 _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON);
673 }
674 }
675
676 if (aStartCmd[1] == BL_PATH_CMD_ON)
677 innerJoinEndPoint(_aOut, aStartVtx[0], aStartVtx[1], _p0 + k);
678 }
679
680 return BL_SUCCESS;
681 }
682
683 BL_INLINE void innerJoinCurveTo(BLPathAppender& out, const BLPoint& p1) noexcept {
684 out.lineTo(_p0);
685 out.lineTo(p1);
686 }
687
688 BL_INLINE void innerJoinLineTo(BLPathAppender& out, const BLPoint& lineP0, const BLPoint& lineP1, const BLPoint& innerPt) noexcept {
689 if (out.cmd[-2] <= BL_PATH_CMD_ON && blTestInnerJoinIntersecion(out.vtx[-2], out.vtx[-1], lineP0, lineP1, innerPt)) {
690 out.vtx[-1] = innerPt;
691 }
692 else {
693 out.lineTo(_p0);
694 out.lineTo(lineP0);
695 }
696 }
697
698 BL_INLINE void innerJoinEndPoint(BLPathAppender& out, BLPoint& lineP0, const BLPoint& lineP1, const BLPoint& innerPt) noexcept {
699 if (out.cmd[-2] <= BL_PATH_CMD_ON && blTestInnerJoinIntersecion(out.vtx[-2], out.vtx[-1], lineP0, lineP1, innerPt)) {
700 lineP0 = innerPt;
701 out.back(1);
702 }
703 else {
704 out.lineTo(_p0);
705 out.lineTo(lineP0);
706 }
707 }
708
709 // Calculates outer join to `pb`.
710 BL_INLINE BLResult outerJoin(BLPathAppender& out, uint32_t side, const BLPoint& n1, const BLPoint& w1, const BLPoint& k, size_t& miterFlag) noexcept {
711 BLPoint pb = _p0 + w1;
712
713 if (blLengthSq(k) <= _miterLimitSq) {
714 // Miter condition is met.
715 out.back(out.cmd[-2] <= BL_PATH_CMD_ON);
716 out.lineTo(_p0 + k);
717 out.lineTo(pb);
718
719 miterFlag = 1;
720 return BL_SUCCESS;
721 }
722
723 if (_joinType == BL_STROKE_JOIN_MITER_CLIP) {
724 double b2 = blAbs(blCrossProduct(k, _n0));
725
726 // Avoid degenerate cases and NaN.
727 if (b2 > 0)
728 b2 = b2 * _miterLimit / blLength(k);
729 else
730 b2 = _miterLimit;
731
732 out.back(out.cmd[-2] <= BL_PATH_CMD_ON);
733 if (side == kSideA) {
734 out.lineTo(_p0 + _d * _n0 - b2 * blNormal(_n0));
735 out.lineTo(_p0 + _d * n1 + b2 * blNormal(n1));
736 }
737 else {
738 out.lineTo(_p0 - _d * _n0 - b2 * blNormal(_n0));
739 out.lineTo(_p0 - _d * n1 + b2 * blNormal(n1));
740 }
741
742 miterFlag = 1;
743 out.lineTo(pb);
744 return BL_SUCCESS;
745 }
746
747 if (_joinType == BL_STROKE_JOIN_ROUND) {
748 BLPoint pa = out.vtx[-1];
749 if (blDotProduct(_p0 - pa, _p0 - pb) < 0.0) {
750 // Dull angle.
751 BLPoint n2 = blNormal(blUnitVector(pb - pa));
752 BLPoint m = _n0 + n2;
753 BLPoint k = _d2 * m / blLengthSq(m);
754 BLPoint q = _d * n2;
755
756 BLPoint pc1 = side == kSideA ? _p0 + k : _p0 - k;
757 BLPoint pp1 = side == kSideA ? _p0 + q : _p0 - q;
758 BLPoint pc2 = blLerp(pc1, pp1, 2.0);
759
760 auto arcTo = [&](const BLPoint& p0, const BLPoint& pa, const BLPoint& pb, const BLPoint& intersection) noexcept {
761 BLPoint pm = (pa + pb) * 0.5;
762
763 double w = blSqrt(blLength(p0 - pm) / blLength(p0 - intersection));
764 double a = 4 * w / (3.0 * (1.0 + w));
765
766 BLPoint c0 = pa + a * (intersection - pa);
767 BLPoint c1 = pb + a * (intersection - pb);
768
769 out.cubicTo(c0, c1, pb);
770 };
771
772 arcTo(_p0, pa, pp1, pc1);
773 arcTo(_p0, pp1, pb, pc2);
774 }
775 else {
776 // Acute angle.
777 BLPoint pm = blLerp(pa, pb);
778 BLPoint pi = _p0 + k;
779
780 double w = blSqrt(blLength(_p0 - pm) / blLength(_p0 - pi));
781 double a = 4.0 * w / (3.0 * (1.0 + w));
782
783 BLPoint c0 = pa + a * (pi - pa);
784 BLPoint c1 = pb + a * (pi - pb);
785
786 out.cubicTo(c0, c1, pb);
787 }
788 return BL_SUCCESS;
789 }
790
791 // Bevel or unknown `_joinType`.
792 out.lineTo(pb);
793 return BL_SUCCESS;
794 }
795
796 // Calculates round join to `pb` (dull angle), only used by offseting cusps.
797 BL_INLINE BLResult dullRoundJoin(BLPathAppender& out, uint32_t side, const BLPoint& n1, const BLPoint& w1) noexcept {
798 BLPoint pa = out.vtx[-1];
799 BLPoint pb = _p0 + w1;
800 BLPoint n2 = blNormal(blUnitVector(pb - pa));
801 BLPoint m = _n0 + n2;
802 BLPoint k = _d2 * m / blLengthSq(m);
803 BLPoint q = _d * n2;
804
805 BLPoint pc1 = side == kSideA ? _p0 + k : _p0 - k;
806 BLPoint pp1 = side == kSideA ? _p0 + q : _p0 - q;
807 BLPoint pc2 = blLerp(pc1, pp1, 2.0);
808
809 auto arcTo = [&](const BLPoint& p0, const BLPoint& pa, const BLPoint& pb, const BLPoint& intersection) noexcept {
810 BLPoint pm = (pa + pb) * 0.5;
811
812 double w = blSqrt(blLength(p0 - pm) / blLength(p0 - intersection));
813 double a = 4.0 * w / (3.0 * (1.0 + w));
814
815 BLPoint c0 = pa + a * (intersection - pa);
816 BLPoint c1 = pb + a * (intersection - pb);
817
818 out.cubicTo(c0, c1, pb);
819 };
820
821 arcTo(_p0, pa, pp1, pc1);
822 arcTo(_p0, pp1, pb, pc2);
823 return BL_SUCCESS;
824 }
825
826 BL_INLINE BLResult offsetQuad(const BLPoint bez[3]) noexcept {
827 double ts[3];
828 size_t tn = blGetQuadOffsetCuspTs(bez, _d, ts);
829 ts[tn++] = 1.0;
830
831 BLQuadCurveTsIter iter(bez, ts, tn);
832 double m = _approx.offsetParameter;
833
834 do {
835 for (;;) {
836 BL_PROPAGATE(_aOut.ensure(_aPath, 2));
837 BL_PROPAGATE(_bOut.ensure(_bPath, 2));
838
839 double t = blGetQuadParameterAtAngle(iter.part, m);
840 if (t <= blEpsilon<double>() || t > 1.0 - blEpsilon<double>())
841 t = 1.0;
842
843 BLPoint part[3];
844 blSplitQuad(iter.part, part, iter.part, t);
845 offsetQuadSimple(part[0], part[1], part[2]);
846
847 if (t == 1.0)
848 break;
849 }
850 } while (iter.next());
851
852 return BL_SUCCESS;
853 }
854
855 BL_INLINE void offsetQuadSimple(const BLPoint& p0, const BLPoint& p1, const BLPoint& p2) noexcept {
856 if (p0 == p2)
857 return;
858
859 BLPoint v0 = p1 - p0;
860 BLPoint v1 = p2 - p1;
861
862 BLPoint m0 = blNormal(blUnitVector(p0 != p1 ? v0 : v1));
863 BLPoint m2 = blNormal(blUnitVector(p1 != p2 ? v1 : v0));
864
865 _p0 = p2;
866 _n0 = m2;
867
868 BLPoint m = m0 + m2;
869 BLPoint k1 = _d2 * m / blLengthSq(m);
870 BLPoint k2 = _d * m2;
871
872 _aOut.quadTo(p1 + k1, p2 + k2);
873 _bOut.quadTo(p1 - k1, p2 - k2);
874 }
875
876 BL_INLINE BLResult offsetCubic(const BLPoint bez[4]) noexcept {
877 return blApproximateCubicWithQuads(bez, _approx.simplifyTolerance, [&](BLPoint quad[3]) noexcept -> BLResult {
878 return offsetQuad(quad);
879 });
880 }
881
882 BL_INLINE BLResult addCap(BLPathAppender& out, BLPoint pivot, BLPoint p1, uint32_t capType) noexcept {
883 BLPoint p0 = out.vtx[-1];
884 BLPoint q = blNormal(p1 - p0) * 0.5;
885
886 switch (capType) {
887 case BL_STROKE_CAP_BUTT:
888 default: {
889 out.lineTo(p1);
890 break;
891 }
892
893 case BL_STROKE_CAP_SQUARE: {
894 out.lineTo(p0 + q);
895 out.lineTo(p1 + q);
896 out.lineTo(p1);
897 break;
898 }
899
900 case BL_STROKE_CAP_ROUND: {
901 out.arcQuadrantTo(p0 + q, pivot + q);
902 out.arcQuadrantTo(p1 + q, p1);
903 break;
904 }
905
906 case BL_STROKE_CAP_ROUND_REV: {
907 out.lineTo(p0 + q);
908 out.arcQuadrantTo(p0, pivot);
909 out.arcQuadrantTo(p1, p1 + q);
910 out.lineTo(p1);
911 break;
912 }
913
914 case BL_STROKE_CAP_TRIANGLE: {
915 out.lineTo(pivot + q);
916 out.lineTo(p1);
917 break;
918 }
919
920 case BL_STROKE_CAP_TRIANGLE_REV: {
921 out.lineTo(p0 + q);
922 out.lineTo(pivot);
923 out.lineTo(p1 + q);
924 out.lineTo(p1);
925 break;
926 }
927 }
928
929 return BL_SUCCESS;
930 }
931};
932
933// ============================================================================
934// [BLPathStroker - Interface]
935// ============================================================================
936
937BLResult blPathStrokeInternal(
938 const BLPathView& input,
939 const BLStrokeOptions& options,
940 const BLApproximationOptions& approx,
941 BLPath* a,
942 BLPath* b,
943 BLPath* c,
944 BLPathStrokeSinkFunc sink, void* closure) noexcept {
945
946 return BLPathStroker(input, options, approx, a, b, c).stroke(sink, closure);
947}
948