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 "./blarray_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#include "./blregion_p.h"
15#include "./blruntime_p.h"
16#include "./blsupport_p.h"
17#include "./bltables_p.h"
18
19// ============================================================================
20// [Global Variables]
21// ============================================================================
22
23static BLWrap<BLInternalPathImpl> blNullPathImpl;
24
25// ============================================================================
26// [BLApproximationOptions]
27// ============================================================================
28
29const BLApproximationOptions blDefaultApproximationOptions = blMakeDefaultApproximationOptions();
30
31// ============================================================================
32// [BLStrokeOptions - Init / Reset]
33// ============================================================================
34
35BLResult blStrokeOptionsInit(BLStrokeOptionsCore* self) noexcept {
36 self->hints = 0;
37 self->width = 1.0;
38 self->miterLimit = 4.0;
39 self->dashOffset = 0;
40 blCallCtor(self->dashArray);
41
42 return BL_SUCCESS;
43}
44
45BLResult blStrokeOptionsInitWeak(BLStrokeOptionsCore* self, const BLStrokeOptionsCore* other) noexcept {
46 BLArrayImpl* dashArrayI = other->dashArray.impl;
47
48 self->hints = other->hints;
49 self->width = other->width;
50 self->miterLimit = other->miterLimit;
51 self->dashOffset = other->dashOffset;
52 self->dashArray.impl = blImplIncRef(dashArrayI);
53
54 return BL_SUCCESS;
55}
56
57BLResult blStrokeOptionsInitMove(BLStrokeOptionsCore* self, BLStrokeOptionsCore* other) noexcept {
58 BLArrayImpl* dashArrayI = other->dashArray.impl;
59 blCallCtor(other->dashArray);
60
61 self->hints = other->hints;
62 self->width = other->width;
63 self->miterLimit = other->miterLimit;
64 self->dashOffset = other->dashOffset;
65 self->dashArray.impl = dashArrayI;
66
67 return BL_SUCCESS;
68}
69
70BLResult blStrokeOptionsReset(BLStrokeOptionsCore* self) noexcept {
71 self->hints = 0;
72 self->width = 1.0;
73 self->miterLimit = 4.0;
74 self->dashOffset = 0;
75 self->dashArray.reset();
76
77 return BL_SUCCESS;
78}
79
80// ============================================================================
81// [BLStrokeOptions - Assign]
82// ============================================================================
83
84BLResult blStrokeOptionsAssignMove(BLStrokeOptionsCore* self, BLStrokeOptionsCore* other) noexcept {
85 BLArrayImpl* prevDashArrayI = self->dashArray.impl;
86
87 self->width = other->width;
88 self->miterLimit = other->miterLimit;
89 self->dashOffset = other->dashOffset;
90 self->dashArray.impl = other->dashArray.impl;
91 self->hints = other->hints;
92
93 blCallCtor(other->dashArray);
94 return blImplDecRefAndTest(prevDashArrayI) ? blArrayImplDelete(prevDashArrayI) : BL_SUCCESS;
95}
96
97BLResult blStrokeOptionsAssignWeak(BLStrokeOptionsCore* self, const BLStrokeOptionsCore* other) noexcept {
98 BLArrayImpl* prevDashArrayI = self->dashArray.impl;
99
100 self->width = other->width;
101 self->miterLimit = other->miterLimit;
102 self->dashOffset = other->dashOffset;
103 self->dashArray.impl = blImplIncRef(other->dashArray.impl);
104 self->hints = other->hints;
105
106 return blImplDecRefAndTest(prevDashArrayI) ? blArrayImplDelete(prevDashArrayI) : BL_SUCCESS;
107}
108
109// ============================================================================
110// [BLPath - Utilities]
111// ============================================================================
112
113static BL_INLINE bool blPathRangeCheck(BLInternalPathImpl* pathI, const BLRange* range, size_t* startOut, size_t* nOut) noexcept {
114 size_t start = 0;
115 size_t end = pathI->size;
116
117 if (range) {
118 start = range->start;
119 end = blMin(end, range->end);
120 }
121
122 *startOut = start;
123 *nOut = end - start;
124 return start < end;
125}
126
127static BL_INLINE void blPathCopyData(uint8_t* cmdDst, BLPoint* vtxDst, const uint8_t* cmdSrc, const BLPoint* vtxSrc, size_t n) noexcept {
128 for (size_t i = 0; i < n; i++) {
129 cmdDst[i] = cmdSrc[i];
130 vtxDst[i] = vtxSrc[i];
131 }
132}
133
134// ============================================================================
135// [BLPath - Internal]
136// ============================================================================
137
138static constexpr size_t blPathImplSizeOf(size_t n = 0) noexcept {
139 return blContainerSizeOf(sizeof(BLInternalPathImpl), sizeof(BLPoint) + 1, n);
140}
141
142static constexpr size_t blPathCapacityOf(size_t implSize) noexcept {
143 return blContainerCapacityOf(sizeof(BLInternalPathImpl), sizeof(BLPoint) + 1, implSize);
144}
145
146static BL_INLINE size_t blPathFittingCapacity(size_t n) noexcept {
147 return blContainerFittingCapacity(blPathImplSizeOf(), sizeof(BLPoint) + 1, n);
148}
149
150static BL_INLINE size_t blPathGrowingCapacity(size_t n) noexcept {
151 return blContainerGrowingCapacity(blPathImplSizeOf(), sizeof(BLPoint) + 1, n, BL_ALLOC_HINT_PATH2D);
152}
153
154static BL_INLINE BLInternalPathImpl* blPathImplNew(size_t capacity) noexcept {
155 uint16_t memPoolData;
156 BLInternalPathImpl* impl = blRuntimeAllocImplT<BLInternalPathImpl>(blPathImplSizeOf(capacity), &memPoolData);
157
158 if (BL_UNLIKELY(!impl))
159 return impl;
160
161 blImplInit(impl, BL_IMPL_TYPE_PATH, BL_IMPL_TRAIT_MUTABLE, memPoolData);
162 impl->vertexData = blOffsetPtr<BLPoint>(impl, sizeof(BLInternalPathImpl));
163 impl->commandData = blOffsetPtr<uint8_t>(impl->vertexData, capacity * sizeof(BLPoint));
164 impl->size = 0;
165 impl->flags = BL_PATH_FLAG_DIRTY;
166 impl->capacity = capacity;
167 impl->controlBox.reset();
168 impl->boundingBox.reset();
169
170 return impl;
171}
172
173// Cannot be static, called by `BLVariant` implementation.
174BLResult blPathImplDelete(BLPathImpl* impl_) noexcept {
175 BLInternalPathImpl* impl = blInternalCast(impl_);
176
177 uint8_t* implBase = reinterpret_cast<uint8_t*>(impl);
178 size_t implSize = blPathImplSizeOf(impl->capacity);
179 uint32_t implTraits = impl->implTraits;
180 uint32_t memPoolData = impl->memPoolData;
181
182 if (implTraits & BL_IMPL_TRAIT_EXTERNAL) {
183 implSize = blPathImplSizeOf() + sizeof(BLExternalImplPreface);
184 implBase -= sizeof(BLExternalImplPreface);
185 blImplDestroyExternal(impl);
186 }
187
188 if (implTraits & BL_IMPL_TRAIT_FOREIGN)
189 return BL_SUCCESS;
190 else
191 return blRuntimeFreeImpl(implBase, implSize, memPoolData);
192}
193
194static BL_INLINE BLResult blPathImplRelease(BLInternalPathImpl* impl) noexcept {
195 if (blImplDecRefAndTest(impl))
196 return blPathImplDelete(impl);
197 return BL_SUCCESS;
198}
199
200// Plain realloc - allocates a new path, copies its data into it, and replaces the
201// impl in `self`. Flags and cached information are cleared.
202static BL_NOINLINE BLResult blPathRealloc(BLPathCore* self, size_t newCapacity) noexcept {
203 BLInternalPathImpl* newI = blPathImplNew(newCapacity);
204 if (BL_UNLIKELY(!newI))
205 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
206
207 BLInternalPathImpl* oldI = blInternalCast(self->impl);
208 size_t size = oldI->size;
209
210 self->impl = newI;
211 newI->size = size;
212 blPathCopyData(newI->commandData, newI->vertexData, oldI->commandData, oldI->vertexData, size);
213
214 return blPathImplRelease(oldI);
215}
216
217// Called by `blPathPrepareAdd` and some others to create a new path, copy
218// a content from `self` into it, and release the current impl. The size of
219// the new path will be set to `newSize` so this function should really be
220// only used as an append fallback.
221static BL_NOINLINE BLResult blPathReallocToAdd(BLPathCore* self, size_t newSize, uint8_t** cmdOut, BLPoint** vtxOut) noexcept {
222 size_t newCapacity = blPathGrowingCapacity(newSize);
223 BLInternalPathImpl* newI = blPathImplNew(newCapacity);
224
225 if (BL_UNLIKELY(!newI))
226 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
227
228 BLInternalPathImpl* oldI = blInternalCast(self->impl);
229 size_t oldSize = oldI->size;
230
231 self->impl = newI;
232 newI->size = newSize;
233 blPathCopyData(newI->commandData, newI->vertexData, oldI->commandData, oldI->vertexData, oldSize);
234
235 *cmdOut = newI->commandData + oldSize;
236 *vtxOut = newI->vertexData + oldSize;
237
238 return blPathImplRelease(oldI);
239}
240
241// Called when adding something to the path. Any `n` is always considered safe
242// as it would be impossible that a path length would go to half `size_t`. The
243// memory required by each vertex is either:
244//
245// - 5 bytes (2*i16 + 1 command byte)
246// - 9 bytes (2*f32 + 1 command byte)
247// - 17 bytes (2*f64 + 1 command byte)
248//
249// This means that a theoretical maximum size of a path without considering its
250// header would be:
251//
252// `SIZE_MAX / (sizeof(vertex) + sizeof(uint8_t))
253//
254// which would be always smaller than SIZE_MAX / 2 so we can assume that apending
255// two paths would never overflow the maximum possible capacity representable by
256// `size_t` type.
257static BL_INLINE BLResult blPathPrepareAdd(BLPathCore* self, size_t n, uint8_t** cmdOut, BLPoint** vtxOut) noexcept {
258 BLInternalPathImpl* selfI = blInternalCast(self->impl);
259
260 size_t size = selfI->size;
261 size_t sizeAfter = size + n;
262 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
263
264 if ((sizeAfter | immutableMsk) > selfI->capacity)
265 return blPathReallocToAdd(self, sizeAfter, cmdOut, vtxOut);
266
267 // Likely case, appending to a path that is not shared and has the required
268 // capacity. We have to clear FLAGS in addition to set the new size as
269 // flags can contain bits regarding BLPathInfo that will no longer hold.
270 selfI->flags = BL_PATH_FLAG_DIRTY;
271 selfI->size = sizeAfter;
272
273 *cmdOut = selfI->commandData + size;
274 *vtxOut = selfI->vertexData + size;
275
276 return BL_SUCCESS;
277}
278
279// ============================================================================
280// [BLPath - Init / Reset]
281// ============================================================================
282
283BLResult blPathInit(BLPathCore* self) noexcept {
284 self->impl = BLPath::none().impl;
285 return BL_SUCCESS;
286}
287
288BLResult blPathReset(BLPathCore* self) noexcept {
289 BLInternalPathImpl* selfI = blInternalCast(self->impl);
290 self->impl = &blNullPathImpl;
291 return blPathImplRelease(selfI);
292}
293
294// ============================================================================
295// [BLPath - Storage]
296// ============================================================================
297
298size_t blPathGetSize(const BLPathCore* self) BL_NOEXCEPT_C {
299 return self->impl->size;
300}
301
302size_t blPathGetCapacity(const BLPathCore* self) BL_NOEXCEPT_C {
303 return self->impl->capacity;
304}
305
306const uint8_t* blPathGetCommandData(const BLPathCore* self) BL_NOEXCEPT_C {
307 return self->impl->commandData;
308}
309
310const BLPoint* blPathGetVertexData(const BLPathCore* self) BL_NOEXCEPT_C {
311 return self->impl->vertexData;
312}
313
314BLResult blPathClear(BLPathCore* self) noexcept {
315 BLInternalPathImpl* selfI = blInternalCast(self->impl);
316
317 if (!blImplIsMutable(selfI)) {
318 self->impl = BLPath::none().impl;
319 return blPathImplRelease(selfI);
320 }
321
322 selfI->flags = 0;
323 selfI->size = 0;
324 return BL_SUCCESS;
325}
326
327BLResult blPathShrink(BLPathCore* self) noexcept {
328 BLInternalPathImpl* selfI = blInternalCast(self->impl);
329 size_t size = selfI->size;
330 size_t capacity = selfI->capacity;
331
332 if (!size) {
333 self->impl = BLPath::none().impl;
334 return blPathImplRelease(selfI);
335 }
336
337 size_t fittingCapacity = blPathFittingCapacity(size);
338 if (fittingCapacity < capacity)
339 BL_PROPAGATE(blPathRealloc(self, fittingCapacity));
340
341 // Update path info as this this path may be kept alive for some time.
342 uint32_t dummyFlags;
343 return blPathGetInfoFlags(self, &dummyFlags);
344}
345
346BLResult blPathReserve(BLPathCore* self, size_t n) noexcept {
347 BLInternalPathImpl* selfI = blInternalCast(self->impl);
348 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
349
350 if ((n | immutableMsk) > selfI->capacity)
351 return blPathRealloc(self, blPathFittingCapacity(blMax(n, selfI->size)));
352
353 return BL_SUCCESS;
354}
355
356BLResult blPathModifyOp(BLPathCore* self, uint32_t op, size_t n, uint8_t** cmdDataOut, BLPoint** vtxDataOut) noexcept {
357 BLInternalPathImpl* selfI = blInternalCast(self->impl);
358
359 size_t index = (op >= BL_MODIFY_OP_APPEND_START) ? selfI->size : size_t(0);
360 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
361
362 size_t remaining = selfI->capacity - index;
363 size_t sizeAfter = index + n;
364
365 if ((n | immutableMsk) > remaining) {
366 size_t newCapacity =
367 (op & BL_MODIFY_OP_GROW_MASK)
368 ? blPathGrowingCapacity(sizeAfter)
369 : blPathFittingCapacity(sizeAfter);
370
371 BLInternalPathImpl* newI = blPathImplNew(newCapacity);
372 if (BL_UNLIKELY(!newI)) {
373 *cmdDataOut = nullptr;
374 *vtxDataOut = nullptr;
375 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
376 }
377
378 newI->size = sizeAfter;
379 *cmdDataOut = newI->commandData + index;
380 *vtxDataOut = newI->vertexData + index;
381 blPathCopyData(newI->commandData, newI->vertexData, selfI->commandData, selfI->vertexData, index);
382
383 self->impl = newI;
384 return blPathImplRelease(selfI);
385 }
386
387 if (n) {
388 selfI->size = sizeAfter;
389 }
390 else if (!index) {
391 blPathClear(self);
392 selfI = blInternalCast(self->impl);
393 }
394
395 selfI->flags = BL_PATH_FLAG_DIRTY;
396 *vtxDataOut = selfI->vertexData + index;
397 *cmdDataOut = selfI->commandData + index;
398
399 return BL_SUCCESS;
400}
401
402static BL_INLINE BLResult blPathMakeMutable(BLPathCore* self) noexcept {
403 BLInternalPathImpl* selfI = blInternalCast(self->impl);
404 if (!blImplIsMutable(selfI))
405 return blPathRealloc(self, blPathFittingCapacity(selfI->size));
406 return BL_SUCCESS;
407}
408// ============================================================================
409// [BLPath - Assign]
410// ============================================================================
411
412BLResult blPathAssignMove(BLPathCore* self, BLPathCore* other) noexcept {
413 BLInternalPathImpl* selfI = blInternalCast(self->impl);
414 BLInternalPathImpl* otherI = blInternalCast(other->impl);
415
416 self->impl = otherI;
417 other->impl = &blNullPathImpl;
418
419 return blPathImplRelease(selfI);
420}
421
422BLResult blPathAssignWeak(BLPathCore* self, const BLPathCore* other) noexcept {
423 BLInternalPathImpl* selfI = blInternalCast(self->impl);
424 BLInternalPathImpl* otherI = blInternalCast(other->impl);
425
426 self->impl = blImplIncRef(otherI);
427 return blPathImplRelease(selfI);
428}
429
430BLResult blPathAssignDeep(BLPathCore* self, const BLPathCore* other) noexcept {
431 BLInternalPathImpl* selfI = blInternalCast(self->impl);
432 BLInternalPathImpl* otherI = blInternalCast(other->impl);
433
434 size_t size = otherI->size;
435 if (!size)
436 return blPathClear(self);
437
438 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
439 if ((size | immutableMsk) > selfI->capacity) {
440 BLInternalPathImpl* newI = blPathImplNew(blPathFittingCapacity(size));
441
442 if (BL_UNLIKELY(!newI))
443 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
444
445 newI->size = size;
446 blPathCopyData(newI->commandData, newI->vertexData, otherI->commandData, otherI->vertexData, size);
447
448 self->impl = newI;
449 return blPathImplRelease(selfI);
450 }
451
452 selfI->flags = BL_PATH_FLAG_DIRTY;
453 selfI->size = size;
454
455 blPathCopyData(selfI->commandData, selfI->vertexData, otherI->commandData, otherI->vertexData, size);
456 return BL_SUCCESS;
457}
458
459// ============================================================================
460// [BLPath - Arcs Helpers]
461// ============================================================================
462
463static const double blArc90DegStepsTable[] = {
464 BL_MATH_PI_DIV_2,
465 BL_MATH_PI,
466 BL_MATH_1p5_PI,
467 BL_MATH_2_PI
468};
469
470static void blArcToCubicSpline(BLPathAppender& dst, BLPoint c, BLPoint r, double startAngle, double sweepAngle, uint8_t initialCmd, bool maybeRedundantLineTo = false) noexcept {
471 double startSin = blSin(startAngle);
472 double startCos = blCos(startAngle);
473
474 BLMatrix2D m = BLMatrix2D::makeSinCos(startSin, startCos);
475 m.postScale(r);
476 m.postTranslate(c);
477
478 if (sweepAngle < 0) {
479 m.scale(1.0, -1.0);
480 sweepAngle = -sweepAngle;
481 }
482
483 BLPoint v1(1.0, 0.0);
484 BLPoint vc(1.0, 1.0);
485 BLPoint v2;
486
487 if (sweepAngle >= BL_MATH_2_PI - blEpsilon<double>()) {
488 sweepAngle = BL_MATH_2_PI;
489 v2 = v1;
490 }
491 else {
492 if (blIsNaN(sweepAngle))
493 return;
494
495 double sweepSin = blSin(sweepAngle);
496 double sweepCos = blCos(sweepAngle);
497 v2 = BLPoint(sweepCos, sweepSin);
498 }
499
500 BLPoint p0 = m.mapPoint(v1);
501 dst.addVertex(initialCmd, p0);
502
503 if (maybeRedundantLineTo && dst.cmd[-1] <= BL_PATH_CMD_ON) {
504 BL_ASSERT(initialCmd == BL_PATH_CMD_ON);
505 double diff = blMax(blAbs(p0.x - dst.vtx[-2].x), blAbs(p0.y - dst.vtx[-2].y));
506
507 if (diff < blEpsilon<double>())
508 dst.back(1);
509 }
510
511 size_t i = 0;
512 while (sweepAngle > blArc90DegStepsTable[i]) {
513 v1 = blNormal(v1);
514 BLPoint p1 = m.mapPoint(vc);
515 BLPoint p2 = m.mapPoint(v1);
516 dst.cubicTo(p0 + (p1 - p0) * BL_MATH_KAPPA, p2 + (p1 - p2) * BL_MATH_KAPPA, p2);
517
518 // Full circle.
519 if (++i == 4)
520 return;
521
522 vc = blNormal(vc);
523 p0 = p2;
524 }
525
526 // Calculate the remaining control point.
527 vc = v1 + v2;
528 vc = 2.0 * vc / blDotProduct(vc, vc);
529
530 // This is actually half of the remaining cos. It is required that v1 dot v2 > -1 holds
531 // but we can safely assume it does (only critical for angles close to 180 degrees).
532 double w = blSqrt(0.5 * blDotProduct(v1, v2) + 0.5);
533 dst.conicTo(m.mapPoint(vc), m.mapPoint(v2), w);
534}
535
536// ============================================================================
537// [BLPath - Info Updater]
538// ============================================================================
539
540class BLPathInfoUpdater {
541public:
542 uint32_t moveToCount;
543 uint32_t flags;
544 BLBox controlBox;
545 BLBox boundingBox;
546
547 BL_INLINE BLPathInfoUpdater() noexcept
548 : moveToCount(0),
549 flags(0),
550 controlBox(blMaxValue<double>(), blMaxValue<double>(), blMinValue<double>(), blMinValue<double>()),
551 boundingBox(blMaxValue<double>(), blMaxValue<double>(), blMinValue<double>(), blMinValue<double>()) {}
552
553 BLResult update(const BLPathView& view, uint32_t hasPrevVertex = false) noexcept {
554 const uint8_t* cmdData = view.commandData;
555 const uint8_t* cmdEnd = view.commandData + view.size;
556 const BLPoint* vtxData = view.vertexData;
557
558 // Iterate over the whole path.
559 while (cmdData != cmdEnd) {
560 uint32_t c = cmdData[0];
561 switch (c) {
562 case BL_PATH_CMD_MOVE: {
563 moveToCount++;
564 hasPrevVertex = true;
565
566 blBoundBoxes(boundingBox, vtxData[0]);
567
568 cmdData++;
569 vtxData++;
570 break;
571 }
572
573 case BL_PATH_CMD_ON: {
574 if (!hasPrevVertex)
575 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
576
577 blBoundBoxes(boundingBox, vtxData[0]);
578
579 cmdData++;
580 vtxData++;
581 break;
582 }
583
584 case BL_PATH_CMD_QUAD: {
585 cmdData += 2;
586 vtxData += 2;
587
588 if (cmdData > cmdEnd || !hasPrevVertex)
589 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
590
591 flags |= BL_PATH_FLAG_QUADS;
592 hasPrevVertex = true;
593 blBoundBoxes(boundingBox, vtxData[-1]);
594
595 // Calculate tight bounding-box only when control points are outside the current one.
596 const BLPoint& ctrl = vtxData[-2];
597
598 if (!(ctrl.x >= boundingBox.x0 && ctrl.y >= boundingBox.y0 && ctrl.x <= boundingBox.x1 && ctrl.y <= boundingBox.y1)) {
599 BLPoint extrema;
600 blGetQuadExtremaPoint(vtxData - 3, extrema);
601 blBoundBoxes(boundingBox, extrema);
602 blBoundBoxes(controlBox, vtxData[-2]);
603 }
604 break;
605 }
606
607 case BL_PATH_CMD_CUBIC: {
608 cmdData += 3;
609 vtxData += 3;
610 if (cmdData > cmdEnd || !hasPrevVertex)
611 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
612
613 flags |= BL_PATH_FLAG_CUBICS;
614 hasPrevVertex = true;
615 blBoundBoxes(boundingBox, vtxData[-1]);
616
617 // Calculate tight bounding-box only when control points are outside of the current one.
618 BLPoint ctrlMin = blMin(vtxData[-3], vtxData[-2]);
619 BLPoint ctrlMax = blMax(vtxData[-3], vtxData[-2]);
620
621 if (!(ctrlMin.x >= boundingBox.x0 && ctrlMin.y >= boundingBox.y0 && ctrlMax.x <= boundingBox.x1 && ctrlMax.y <= boundingBox.y1)) {
622 BLPoint extremas[2];
623 blGetCubicExtremaPoints(vtxData - 4, extremas);
624 blBoundBoxes(boundingBox, extremas[0]);
625 blBoundBoxes(boundingBox, extremas[1]);
626 blBoundBoxes(controlBox, vtxData[-3]);
627 blBoundBoxes(controlBox, vtxData[-2]);
628 }
629 break;
630 }
631
632 case BL_PATH_CMD_CLOSE:
633 hasPrevVertex = false;
634
635 cmdData++;
636 vtxData++;
637 break;
638
639 default:
640 blTraceError(BL_ERROR_INVALID_GEOMETRY);
641 }
642 }
643
644 controlBox.x0 = blMin(controlBox.x0, boundingBox.x0);
645 controlBox.y0 = blMin(controlBox.y0, boundingBox.y0);
646 controlBox.x1 = blMax(controlBox.x1, boundingBox.x1);
647 controlBox.y1 = blMax(controlBox.y1, boundingBox.y1);
648
649 if (moveToCount > 1)
650 flags |= BL_PATH_FLAG_MULTIPLE;
651
652 if (!blIsFinite(controlBox, boundingBox))
653 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
654
655 return BL_SUCCESS;
656 }
657};
658
659// ============================================================================
660// [BLPath - Path Construction]
661// ============================================================================
662
663struct BLPathVertexCountOfGeometryTypeGen {
664 static constexpr uint8_t value(size_t i) noexcept {
665 return uint8_t(i == BL_GEOMETRY_TYPE_BOXI ? 5 :
666 i == BL_GEOMETRY_TYPE_BOXD ? 5 :
667 i == BL_GEOMETRY_TYPE_RECTI ? 5 :
668 i == BL_GEOMETRY_TYPE_RECTD ? 5 :
669 i == BL_GEOMETRY_TYPE_CIRCLE ? 14 :
670 i == BL_GEOMETRY_TYPE_ELLIPSE ? 14 :
671 i == BL_GEOMETRY_TYPE_ROUND_RECT ? 18 :
672 i == BL_GEOMETRY_TYPE_ARC ? 13 :
673 i == BL_GEOMETRY_TYPE_CHORD ? 20 :
674 i == BL_GEOMETRY_TYPE_PIE ? 20 :
675 i == BL_GEOMETRY_TYPE_LINE ? 2 :
676 i == BL_GEOMETRY_TYPE_TRIANGLE ? 4 : 255);
677 }
678};
679
680static constexpr const auto blPathVertexCountOfGeometryType =
681 blLookupTable<uint8_t, BL_GEOMETRY_TYPE_COUNT, BLPathVertexCountOfGeometryTypeGen>();
682
683static BL_INLINE BLResult blPathAddBoxInternal(BLPathCore* self, double x0, double y0, double x1, double y1, uint32_t dir) noexcept {
684 uint8_t* cmdData;
685 BLPoint* vtxData;
686 BL_PROPAGATE(blPathPrepareAdd(self, 5, &cmdData, &vtxData));
687
688 vtxData[0].reset(x0, y0);
689 vtxData[1].reset(x1, y0);
690 vtxData[2].reset(x1, y1);
691 vtxData[3].reset(x0, y1);
692 vtxData[4].reset(blNaN<double>(), blNaN<double>());
693 cmdData[0] = BL_PATH_CMD_MOVE;
694 cmdData[1] = BL_PATH_CMD_ON;
695 cmdData[2] = BL_PATH_CMD_ON;
696 cmdData[3] = BL_PATH_CMD_ON;
697 cmdData[4] = BL_PATH_CMD_CLOSE;
698
699 if (dir == BL_GEOMETRY_DIRECTION_CW)
700 return BL_SUCCESS;
701
702 vtxData[1].reset(x0, y1);
703 vtxData[3].reset(x1, y0);
704 return BL_SUCCESS;
705}
706
707BLResult blPathSetVertexAt(BLPathCore* self, size_t index, uint32_t cmd, double x, double y) noexcept {
708 BLInternalPathImpl* selfI = blInternalCast(self->impl);
709 size_t size = selfI->size;
710
711 if (BL_UNLIKELY(index >= size))
712 return blTraceError(BL_ERROR_INVALID_VALUE);
713
714 BL_PROPAGATE(blPathMakeMutable(self));
715 selfI = blInternalCast(self->impl);
716
717 uint32_t oldCmd = selfI->commandData[index];
718 if (cmd == BL_PATH_CMD_PRESERVE) cmd = oldCmd;
719
720 // NOTE: We don't check `cmd` as we don't care of the value. Invalid commands
721 // must always be handled by all Blend2D functions anyway so let it fail at
722 // some other place if the given `cmd` is invalid.
723 selfI->flags = BL_PATH_FLAG_DIRTY;
724 selfI->commandData[index] = cmd & 0xFFu;
725 selfI->vertexData[index].reset(x, y);
726
727 return BL_SUCCESS;
728}
729
730BLResult blPathMoveTo(BLPathCore* self, double x0, double y0) noexcept {
731 uint8_t* cmdData;
732 BLPoint* vtxData;
733 BL_PROPAGATE(blPathPrepareAdd(self, 1, &cmdData, &vtxData));
734
735 vtxData[0].reset(x0, y0);
736 cmdData[0] = BL_PATH_CMD_MOVE;
737
738 return BL_SUCCESS;
739}
740
741BLResult blPathLineTo(BLPathCore* self, double x1, double y1) noexcept {
742 uint8_t* cmdData;
743 BLPoint* vtxData;
744 BL_PROPAGATE(blPathPrepareAdd(self, 1, &cmdData, &vtxData));
745
746 vtxData[0].reset(x1, y1);
747 cmdData[0] = BL_PATH_CMD_ON;
748
749 return BL_SUCCESS;
750}
751
752BLResult blPathPolyTo(BLPathCore* self, const BLPoint* poly, size_t count) noexcept {
753 uint8_t* cmdData;
754 BLPoint* vtxData;
755 BL_PROPAGATE(blPathPrepareAdd(self, count, &cmdData, &vtxData));
756
757 for (size_t i = 0; i < count; i++) {
758 vtxData[i] = poly[i];
759 cmdData[i] = BL_PATH_CMD_ON;
760 }
761
762 return BL_SUCCESS;
763}
764
765BLResult blPathQuadTo(BLPathCore* self, double x1, double y1, double x2, double y2) noexcept {
766 uint8_t* cmdData;
767 BLPoint* vtxData;
768 BL_PROPAGATE(blPathPrepareAdd(self, 2, &cmdData, &vtxData));
769
770 vtxData[0].reset(x1, y1);
771 vtxData[1].reset(x2, y2);
772
773 cmdData[0] = BL_PATH_CMD_QUAD;
774 cmdData[1] = BL_PATH_CMD_ON;
775
776 return BL_SUCCESS;
777}
778
779BLResult blPathCubicTo(BLPathCore* self, double x1, double y1, double x2, double y2, double x3, double y3) noexcept {
780 uint8_t* cmdData;
781 BLPoint* vtxData;
782 BL_PROPAGATE(blPathPrepareAdd(self, 3, &cmdData, &vtxData));
783
784 vtxData[0].reset(x1, y1);
785 vtxData[1].reset(x2, y2);
786 vtxData[2].reset(x3, y3);
787
788 cmdData[0] = BL_PATH_CMD_CUBIC;
789 cmdData[1] = BL_PATH_CMD_CUBIC;
790 cmdData[2] = BL_PATH_CMD_ON;
791
792 return BL_SUCCESS;
793}
794
795BLResult blPathSmoothQuadTo(BLPathCore* self, double x2, double y2) noexcept {
796 BLInternalPathImpl* selfI = blInternalCast(self->impl);
797 size_t size = selfI->size;
798
799 if (BL_UNLIKELY(!size || selfI->commandData[size - 1u] >= BL_PATH_CMD_CLOSE))
800 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
801
802 uint8_t* cmdData;
803 BLPoint* vtxData;
804 BL_PROPAGATE(blPathPrepareAdd(self, 2, &cmdData, &vtxData));
805
806 double x1 = vtxData[-1].x;
807 double y1 = vtxData[-1].y;
808
809 if (size >= 2 && cmdData[-2] == BL_PATH_CMD_QUAD) {
810 x1 += x1 - vtxData[-2].x;
811 y1 += y1 - vtxData[-2].y;
812 }
813
814 vtxData[0].reset(x1, y1);
815 vtxData[1].reset(x2, y2);
816
817 cmdData[0] = BL_PATH_CMD_QUAD;
818 cmdData[1] = BL_PATH_CMD_ON;
819
820 return BL_SUCCESS;
821}
822
823BLResult blPathSmoothCubicTo(BLPathCore* self, double x2, double y2, double x3, double y3) noexcept {
824 BLInternalPathImpl* selfI = blInternalCast(self->impl);
825 size_t size = selfI->size;
826
827 if (BL_UNLIKELY(!size || selfI->commandData[size - 1u] >= BL_PATH_CMD_CLOSE))
828 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
829
830 uint8_t* cmdData;
831 BLPoint* vtxData;
832 BL_PROPAGATE(blPathPrepareAdd(self, 2, &cmdData, &vtxData));
833
834 double x1 = vtxData[-1].x;
835 double y1 = vtxData[-1].y;
836
837 if (size >= 2 && cmdData[-2] == BL_PATH_CMD_CUBIC) {
838 x1 += x1 - vtxData[-2].x;
839 y1 += y1 - vtxData[-2].y;
840 }
841
842 vtxData[0].reset(x1, y1);
843 vtxData[1].reset(x2, y2);
844 vtxData[2].reset(x3, y3);
845
846 cmdData[0] = BL_PATH_CMD_CUBIC;
847 cmdData[1] = BL_PATH_CMD_CUBIC;
848 cmdData[2] = BL_PATH_CMD_ON;
849
850 return BL_SUCCESS;
851}
852
853BLResult blPathArcTo(BLPathCore* self, double x, double y, double rx, double ry, double start, double sweep, bool forceMoveTo) noexcept {
854 BLPathAppender dst;
855
856 uint8_t initialCmd = BL_PATH_CMD_MOVE;
857 bool maybeRedundantLineTo = false;
858
859 if (!forceMoveTo) {
860 BLInternalPathImpl* selfI = blInternalCast(self->impl);
861 size_t size = selfI->size;
862
863 if (size != 0 && selfI->commandData[size - 1] <= BL_PATH_CMD_ON) {
864 initialCmd = BL_PATH_CMD_ON;
865 maybeRedundantLineTo = true;
866 }
867 }
868
869 BL_PROPAGATE(dst.beginAppend(self, 13));
870 blArcToCubicSpline(dst, BLPoint(x, y), BLPoint(rx, ry), start, sweep, initialCmd, maybeRedundantLineTo);
871
872 dst.done(self);
873 return BL_SUCCESS;
874}
875
876BLResult blPathArcQuadrantTo(BLPathCore* self, double x1, double y1, double x2, double y2) noexcept {
877 BLInternalPathImpl* selfI = blInternalCast(self->impl);
878 size_t size = selfI->size;
879
880 if (BL_UNLIKELY(!size || selfI->commandData[size - 1u] >= BL_PATH_CMD_CLOSE))
881 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
882
883 uint8_t* cmdData;
884 BLPoint* vtxData;
885 BL_PROPAGATE(blPathPrepareAdd(self, 3, &cmdData, &vtxData));
886
887 BLPoint p0 = vtxData[-1];
888 BLPoint p1(x1, y1);
889 BLPoint p2(x2, y2);
890
891 vtxData[0].reset(p0 + (p1 - p0) * BL_MATH_KAPPA);
892 vtxData[1].reset(p2 + (p1 - p2) * BL_MATH_KAPPA);
893 vtxData[2].reset(p2);
894
895 cmdData[0] = BL_PATH_CMD_CUBIC;
896 cmdData[1] = BL_PATH_CMD_CUBIC;
897 cmdData[2] = BL_PATH_CMD_ON;
898
899 return BL_SUCCESS;
900}
901
902BLResult blPathEllipticArcTo(BLPathCore* self, double rx, double ry, double xAxisRotation, bool largeArcFlag, bool sweepFlag, double x1, double y1) noexcept {
903 BLPathImpl* selfI = self->impl;
904 size_t size = selfI->size;
905
906 if (!size || selfI->commandData[size - 1u] > BL_PATH_CMD_ON)
907 return BL_ERROR_NO_MATCHING_VERTEX;
908
909 BLPoint p0 = selfI->vertexData[size - 1u]; // Start point.
910 BLPoint p1(x1, y1); // End point.
911
912 // Special case - out of range radii.
913 // - See https://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
914 rx = blAbs(rx);
915 ry = blAbs(ry);
916
917 // Special case - out of range parameters:
918 // - See https://www.w3.org/TR/SVG/paths.html#ArcOutOfRangeParameters
919 if (p0 == p1)
920 return BL_SUCCESS;
921
922 if ((!(rx > blEpsilon<double>())) | (!(ry > blEpsilon<double>())))
923 return blPathLineTo(self, p1.x, p1.y);
924
925 // Calculate sin/cos for reuse.
926 double sin = blSin(xAxisRotation);
927 double cos = blCos(xAxisRotation);
928
929 // Inverse rotation to align the ellipse.
930 BLMatrix2D m = BLMatrix2D::makeSinCos(-sin, cos);
931
932 // Vector from center (transformed midpoint).
933 BLPoint v = m.mapPoint((p0 - p1) * 0.5);
934
935 // If scale > 1 the ellipse will need to be rescaled.
936 double scale = blSquare(v.x) / blSquare(rx) +
937 blSquare(v.y) / blSquare(ry) ;
938 if (scale > 1.0) {
939 scale = blSqrt(scale);
940 rx *= scale;
941 ry *= scale;
942 }
943
944 // Prepend scale.
945 m.postScale(1.0 / rx, 1.0 / ry);
946
947 // Calculate unit coordinates.
948 BLPoint pp0 = m.mapPoint(p0);
949 BLPoint pp1 = m.mapPoint(p1);
950
951 // New vector from center (unit midpoint).
952 v = (pp1 - pp0) * 0.5;
953 BLPoint pc = pp0 + v;
954
955 // If lenght^2 >= 1 the point is already the center.
956 double len2 = blLengthSq(v);
957 if (len2 < 1.0) {
958 v = blSqrt(1.0 / len2 - 1.0) * blNormal(v);
959
960 if (largeArcFlag != sweepFlag)
961 pc += v;
962 else
963 pc -= v;
964 }
965
966 // Both vectors are unit vectors.
967 BLPoint v1 = pp0 - pc;
968 BLPoint v2 = pp1 - pc;
969
970 // Set up the final transformation matrix.
971 m.resetToSinCos(v1.y, v1.x);
972 m.postTranslate(pc);
973 m.postScale(rx, ry);
974 blMatrix2DMultiply(m, m, BLMatrix2D::makeSinCos(sin, cos));
975
976 // We have sin = v1.Cross(v2) / (v1.Length * v2.Length)
977 // with length of 'v1' and 'v2' both 1 (unit vectors).
978 sin = blCrossProduct(v1, v2);
979
980 // Accordingly cos = v1.Dot(v2) / (v1.Length * v2.Length)
981 // to get the angle between 'v1' and 'v2'.
982 cos = blDotProduct(v1, v2);
983
984 // So the sweep angle is Atan2(y, x) = Atan2(sin, cos)
985 // https://stackoverflow.com/a/16544330
986 double sweepAngle = blAtan2(sin, cos);
987 if (sweepFlag) {
988 // Correct the angle if necessary.
989 if (sweepAngle < 0) {
990 sweepAngle += BL_MATH_2_PI;
991 }
992
993 // | v1.X v1.Y 0 | | v2.X | | v1.X * v2.X + v1.Y * v2.Y |
994 // | -v1.Y v1.X 0 | * | v2.Y | = | v1.X * v2.Y - v1.Y * v2.X |
995 // | 0 0 1 | | 1 | | 1 |
996 v2.reset(cos, sin);
997 }
998 else {
999 if (sweepAngle > 0) {
1000 sweepAngle -= BL_MATH_2_PI;
1001 }
1002
1003 // Flip Y.
1004 m.scale(1.0, -1.0);
1005
1006 v2.reset(cos, -sin);
1007 sweepAngle = blAbs(sweepAngle);
1008 }
1009
1010 // First quadrant (start and control point).
1011 v1.reset(1, 0);
1012 v.reset(1, 1);
1013
1014 // The the number of 90deg segments we are gonna need. If `i == 1` it means
1015 // we need one 90deg segment and one smaller segment handled after the loop.
1016 size_t i = 3;
1017 if (sweepAngle < BL_MATH_1p5_PI + BL_MATH_ANGLE_EPSILON) i = 2;
1018 if (sweepAngle < BL_MATH_PI + BL_MATH_ANGLE_EPSILON) i = 1;
1019 if (sweepAngle < BL_MATH_PI_DIV_2 + BL_MATH_ANGLE_EPSILON) i = 0;
1020
1021 BLPathAppender appender;
1022 BL_PROPAGATE(appender.begin(self, BL_MODIFY_OP_APPEND_GROW, (i + 1) * 3));
1023
1024 // Process 90 degree segments.
1025 while (i) {
1026 v1 = blNormal(v1);
1027
1028 // Transformed points of the arc segment.
1029 pp0 = m.mapPoint(v);
1030 pp1 = m.mapPoint(v1);
1031 appender.arcQuadrantTo(pp0, pp1);
1032
1033 v = blNormal(v);
1034 i--;
1035 }
1036
1037 // Calculate the remaining control point.
1038 v = v1 + v2;
1039 v = 2.0 * v / blDotProduct(v, v);
1040
1041 // Final arc segment.
1042 pp0 = m.mapPoint(v);
1043 pp1 = p1;
1044
1045 // This is actually half of the remaining cos. It is required that v1 dot v2 > -1 holds
1046 // but we can safely assume it (only critical for angles close to 180 degrees).
1047 cos = blSqrt(0.5 * (1.0 + blDotProduct(v1, v2)));
1048 appender.conicTo(pp0, pp1, cos);
1049 appender.done(self);
1050
1051 return BL_SUCCESS;
1052}
1053
1054BLResult blPathClose(BLPathCore* self) noexcept {
1055 uint8_t* cmdData;
1056 BLPoint* vtxData;
1057 BL_PROPAGATE(blPathPrepareAdd(self, 1, &cmdData, &vtxData));
1058
1059 vtxData[0].reset(blNaN<double>(), blNaN<double>());
1060 cmdData[0] = BL_PATH_CMD_CLOSE;
1061
1062 return BL_SUCCESS;
1063}
1064
1065BLResult blPathAddBoxI(BLPathCore* self, const BLBoxI* box, uint32_t dir) noexcept {
1066 return blPathAddBoxInternal(self, double(box->x0), double(box->y0), double(box->x1), double(box->y1), dir);
1067}
1068
1069BLResult blPathAddBoxD(BLPathCore* self, const BLBox* box, uint32_t dir) noexcept {
1070 return blPathAddBoxInternal(self, box->x0, box->y0, box->x1, box->y1, dir);
1071}
1072
1073BLResult blPathAddRectI(BLPathCore* self, const BLRectI* rect, uint32_t dir) noexcept {
1074 double x0 = double(rect->x);
1075 double y0 = double(rect->y);
1076 double x1 = double(rect->w) + x0;
1077 double y1 = double(rect->h) + y0;
1078 return blPathAddBoxInternal(self, x0, y0, x1, y1, dir);
1079}
1080
1081BLResult blPathAddRectD(BLPathCore* self, const BLRect* rect, uint32_t dir) noexcept {
1082 double x0 = rect->x;
1083 double y0 = rect->y;
1084 double x1 = rect->w + x0;
1085 double y1 = rect->h + y0;
1086 return blPathAddBoxInternal(self, x0, y0, x1, y1, dir);
1087}
1088
1089static BLResult blPathJoinFigure(BLPathAppender& dst, BLPathIterator src) noexcept {
1090 if (src.atEnd())
1091 return BL_SUCCESS;
1092
1093 bool isClosed = dst.cmd[-1] == BL_PATH_CMD_CLOSE;
1094 uint8_t initialCmd = uint8_t(isClosed ? BL_PATH_CMD_MOVE : BL_PATH_CMD_ON);
1095
1096 // Initial vertex (either MOVE or ON). If the initial vertex matches the
1097 // the last vertex in `dst` we won't emit it as it would be unnecessary.
1098 if (dst.vtx[-1] != src.vtx[0] || initialCmd == BL_PATH_CMD_MOVE)
1099 dst.addVertex(initialCmd, src.vtx[0]);
1100
1101 // Iterate the figure.
1102 while (!(++src).atEnd())
1103 dst.addVertex(src.cmd[0], src.vtx[0]);
1104
1105 return BL_SUCCESS;
1106}
1107
1108static BLResult blPathJoinReversedFigure(BLPathAppender& dst, BLPathIterator src) noexcept {
1109 if (src.atEnd())
1110 return BL_SUCCESS;
1111
1112 src.reverse();
1113 src--;
1114
1115 bool isClosed = dst.cmd[-1] == BL_PATH_CMD_CLOSE;
1116 uint8_t initialCmd = uint8_t(isClosed ? BL_PATH_CMD_MOVE : BL_PATH_CMD_ON);
1117 uint8_t cmd = src.cmd[1];
1118
1119 // Initial MOVE means the whole figure consists of just a single MOVE.
1120 if (cmd == BL_PATH_CMD_MOVE) {
1121 dst.addVertex(initialCmd, src.vtx[1]);
1122 return BL_SUCCESS;
1123 }
1124
1125 // Get whether the figure is closed.
1126 BL_ASSERT(cmd == BL_PATH_CMD_CLOSE || cmd == BL_PATH_CMD_ON);
1127 bool hasClose = (cmd == BL_PATH_CMD_CLOSE);
1128
1129 if (hasClose) {
1130 // Make sure the next command is ON.
1131 if (src.atEnd()) {
1132 dst.close();
1133 return BL_SUCCESS;
1134 }
1135
1136 // We just encountered CLOSE followed by ON (reversed).
1137 BL_ASSERT(src.cmd[0] == BL_PATH_CMD_ON);
1138 src--;
1139 }
1140
1141 // Initial vertex (either MOVE or ON). If the initial vertex matches the
1142 // the last vertex in `dst` we won't emit it as it would be unnecessary.
1143 if (dst.vtx[-1] != src.vtx[1] || initialCmd == BL_PATH_CMD_MOVE)
1144 dst.addVertex(initialCmd, src.vtx[1]);
1145
1146 // Iterate the figure.
1147 if (!src.atEnd()) {
1148 do {
1149 dst.addVertex(src.cmd[0], src.vtx[0]);
1150 src--;
1151 } while (!src.atEnd());
1152 // Fix the last vertex to not be MOVE.
1153 dst.cmd[-1] = BL_PATH_CMD_ON;
1154 }
1155
1156 // Emit CLOSE if the figure is closed.
1157 if (hasClose)
1158 dst.close();
1159 return BL_SUCCESS;
1160}
1161
1162// If the function succeeds then the number of vertices written to destination
1163// equals `n`. If the function fails you should not rely on the output data.
1164//
1165// The algorithm reverses the path, but not the implicit line assumed in case
1166// of CLOSE command. This means that for example a sequence like:
1167//
1168// [0,0] [0,1] [1,0] [1,1] [CLOSE]
1169//
1170// Would be reversed to:
1171//
1172// [1,1] [1,0] [0,1] [0,0] [CLOSE]
1173//
1174// Which is what other libraries do as well.
1175static BLResult blPathCopyDataReversed(BLPathAppender& dst, BLPathIterator src, uint32_t reverseMode) noexcept {
1176 for (;;) {
1177 BLPathIterator next;
1178 if (reverseMode != BL_PATH_REVERSE_MODE_COMPLETE) {
1179 // This mode is more complicated as we have to scan the path forward
1180 // and find the end of each figure so we can then go again backward.
1181 const uint8_t* p = src.cmd;
1182 if (p == src.end)
1183 return BL_SUCCESS;
1184
1185 uint8_t cmd = p[0];
1186 if (cmd != BL_PATH_CMD_MOVE)
1187 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
1188
1189 while (++p != src.end) {
1190 // Terminate on MOVE command, but don't consume it.
1191 if (p[0] == BL_PATH_CMD_MOVE)
1192 break;
1193
1194 // Terminate on CLOSE command and consume it as it's part of the figure.
1195 if (p[0] == BL_PATH_CMD_CLOSE) {
1196 p++;
1197 break;
1198 }
1199 }
1200
1201 size_t figureSize = (size_t)(p - src.cmd);
1202
1203 next.reset(src.cmd + figureSize, src.vtx + figureSize, src.remainingForward() - figureSize);
1204 src.end = src.cmd + figureSize;
1205 }
1206
1207 src.reverse();
1208 while (!src.atEnd()) {
1209 uint8_t cmd = src.cmd[0];
1210 src--;
1211
1212 // Initial MOVE means the whole figure consists of just a single MOVE.
1213 if (cmd == BL_PATH_CMD_MOVE) {
1214 dst.addVertex(cmd, src.vtx[1]);
1215 continue;
1216 }
1217
1218 // Only relevant to non-ON commands
1219 bool hasClose = (cmd == BL_PATH_CMD_CLOSE);
1220 if (cmd != BL_PATH_CMD_ON) {
1221 // A figure cannot end with anything else than MOVE|ON|CLOSE.
1222 if (!hasClose)
1223 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
1224
1225 // Make sure the next command is ON, continue otherwise.
1226 if (src.atEnd() || src.cmd[0] != BL_PATH_CMD_ON) {
1227 dst.addVertex(BL_PATH_CMD_CLOSE, src.vtx[1]);
1228 continue;
1229 }
1230 src--;
1231 }
1232
1233 // Each figure starts with MOVE.
1234 dst.moveTo(src.vtx[1]);
1235
1236 // Iterate the figure.
1237 while (!src.atEnd()) {
1238 cmd = src.cmd[0];
1239 if (cmd == BL_PATH_CMD_MOVE) {
1240 dst.addVertex(BL_PATH_CMD_ON, src.vtx[0]);
1241 src--;
1242 break;
1243 }
1244
1245 if (cmd == BL_PATH_CMD_CLOSE)
1246 break;
1247
1248 dst.addVertex(src.cmd[0], src.vtx[0]);
1249 src--;
1250 }
1251
1252 // Emit CLOSE if the figure is closed.
1253 if (hasClose)
1254 dst.close();
1255 }
1256
1257 if (reverseMode == BL_PATH_REVERSE_MODE_COMPLETE)
1258 return BL_SUCCESS;
1259 src = next;
1260 }
1261}
1262
1263BLResult blPathAddGeometry(BLPathCore* self, uint32_t geometryType, const void* geometryData, const BLMatrix2D* m, uint32_t dir) noexcept {
1264 if (BL_UNLIKELY(geometryType >= BL_GEOMETRY_TYPE_COUNT))
1265 return blTraceError(BL_ERROR_INVALID_VALUE);
1266
1267 size_t n = blPathVertexCountOfGeometryType[geometryType];
1268 if (n == 255) {
1269 switch (geometryType) {
1270 // We don't expect this often so that's why we pessimistically check it here...
1271 case BL_GEOMETRY_TYPE_NONE:
1272 return BL_SUCCESS;
1273
1274 case BL_GEOMETRY_TYPE_POLYLINED:
1275 case BL_GEOMETRY_TYPE_POLYLINEI:
1276 n = static_cast<const BLArrayView<void>*>(geometryData)->size;
1277 if (!n)
1278 return BL_SUCCESS;
1279 break;
1280
1281 case BL_GEOMETRY_TYPE_POLYGOND:
1282 case BL_GEOMETRY_TYPE_POLYGONI:
1283 n = static_cast<const BLArrayView<void>*>(geometryData)->size;
1284 if (!n)
1285 return BL_SUCCESS;
1286 n++;
1287 break;
1288
1289 case BL_GEOMETRY_TYPE_ARRAY_VIEW_BOXD:
1290 case BL_GEOMETRY_TYPE_ARRAY_VIEW_BOXI:
1291 case BL_GEOMETRY_TYPE_ARRAY_VIEW_RECTD:
1292 case BL_GEOMETRY_TYPE_ARRAY_VIEW_RECTI: {
1293 n = static_cast<const BLArrayView<void>*>(geometryData)->size;
1294 if (!n)
1295 return BL_SUCCESS;
1296
1297 n = blUMulSaturate<size_t>(n, 5);
1298 break;
1299 }
1300
1301 case BL_GEOMETRY_TYPE_PATH: {
1302 const BLPath* other = static_cast<const BLPath*>(geometryData);
1303 n = other->size();
1304 if (!n)
1305 return BL_SUCCESS;
1306
1307 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1308 if (m)
1309 return blPathAddTransformedPath(self, other, nullptr, m);
1310 else
1311 return blPathAddPath(self, other, nullptr);
1312 }
1313 break;
1314 }
1315
1316 case BL_GEOMETRY_TYPE_REGION: {
1317 n = static_cast<const BLRegion*>(geometryData)->size();
1318 if (!n)
1319 return BL_SUCCESS;
1320
1321 n = blUMulSaturate<size_t>(n, 5);
1322 break;
1323 }
1324
1325 // Should never be reached as we filtered all border cases already...
1326 default:
1327 return blTraceError(BL_ERROR_INVALID_VALUE);
1328 }
1329 }
1330
1331 // Should never be zero if we went here.
1332 BL_ASSERT(n != 0);
1333 size_t initialSize = self->impl->size;
1334
1335 BLPathAppender appender;
1336 BL_PROPAGATE(appender.beginAppend(self, n));
1337
1338 // For adding 'BLBox', 'BLBoxI', 'BLRect', 'BLRectI', and `BLRoundRect`.
1339 double x0, y0;
1340 double x1, y1;
1341
1342 switch (geometryType) {
1343 case BL_GEOMETRY_TYPE_BOXI:
1344 x0 = double(static_cast<const BLBoxI*>(geometryData)->x0);
1345 y0 = double(static_cast<const BLBoxI*>(geometryData)->y0);
1346 x1 = double(static_cast<const BLBoxI*>(geometryData)->x1);
1347 y1 = double(static_cast<const BLBoxI*>(geometryData)->y1);
1348 goto AddBoxD;
1349
1350 case BL_GEOMETRY_TYPE_BOXD:
1351 x0 = static_cast<const BLBox*>(geometryData)->x0;
1352 y0 = static_cast<const BLBox*>(geometryData)->y0;
1353 x1 = static_cast<const BLBox*>(geometryData)->x1;
1354 y1 = static_cast<const BLBox*>(geometryData)->y1;
1355 goto AddBoxD;
1356
1357 case BL_GEOMETRY_TYPE_RECTI:
1358 x0 = double(static_cast<const BLRectI*>(geometryData)->x);
1359 y0 = double(static_cast<const BLRectI*>(geometryData)->y);
1360 x1 = double(static_cast<const BLRectI*>(geometryData)->w) + x0;
1361 y1 = double(static_cast<const BLRectI*>(geometryData)->h) + y0;
1362 goto AddBoxD;
1363
1364 case BL_GEOMETRY_TYPE_RECTD:
1365 x0 = static_cast<const BLRect*>(geometryData)->x;
1366 y0 = static_cast<const BLRect*>(geometryData)->y;
1367 x1 = static_cast<const BLRect*>(geometryData)->w + x0;
1368 y1 = static_cast<const BLRect*>(geometryData)->h + y0;
1369
1370AddBoxD:
1371 appender.addBox(x0, y0, x1, y1, dir);
1372 break;
1373
1374 case BL_GEOMETRY_TYPE_CIRCLE:
1375 case BL_GEOMETRY_TYPE_ELLIPSE: {
1376 double rx, kx;
1377 double ry, ky;
1378
1379 if (geometryType == BL_GEOMETRY_TYPE_CIRCLE) {
1380 const BLCircle* circle = static_cast<const BLCircle*>(geometryData);
1381 x0 = circle->cx;
1382 y0 = circle->cy;
1383 rx = circle->r;
1384 ry = blAbs(rx);
1385 }
1386 else {
1387 const BLEllipse* ellipse = static_cast<const BLEllipse*>(geometryData);
1388 x0 = ellipse->cx;
1389 y0 = ellipse->cy;
1390 rx = ellipse->rx;
1391 ry = ellipse->ry;
1392 }
1393
1394 if (dir != BL_GEOMETRY_DIRECTION_CW)
1395 ry = -ry;
1396
1397 kx = rx * BL_MATH_KAPPA;
1398 ky = ry * BL_MATH_KAPPA;
1399
1400 appender.moveTo(x0 + rx, y0);
1401 appender.cubicTo(x0 + rx, y0 + ky, x0 + kx, y0 + ry, x0 , y0 + ry);
1402 appender.cubicTo(x0 - kx, y0 + ry, x0 - rx, y0 + ky, x0 - rx, y0 );
1403 appender.cubicTo(x0 - rx, y0 - ky, x0 - kx, y0 - ry, x0 , y0 - ry);
1404 appender.cubicTo(x0 + kx, y0 - ry, x0 + rx, y0 - ky, x0 + rx, y0 );
1405 appender.close();
1406 break;
1407 }
1408
1409 case BL_GEOMETRY_TYPE_ROUND_RECT: {
1410 const BLRoundRect* round = static_cast<const BLRoundRect*>(geometryData);
1411
1412 x0 = round->x;
1413 y0 = round->y;
1414 x1 = round->x + round->w;
1415 y1 = round->y + round->h;
1416
1417 double wHalf = round->w * 0.5;
1418 double hHalf = round->h * 0.5;
1419
1420 double rx = blMin(blAbs(round->rx), wHalf);
1421 double ry = blMin(blAbs(round->ry), hHalf);
1422
1423 // Degrade to box if rx/ry are degenerate.
1424 if (BL_UNLIKELY(!(rx > blEpsilon<double>() && ry > blEpsilon<double>())))
1425 goto AddBoxD;
1426
1427 double kx = rx * (1.0 - BL_MATH_KAPPA);
1428 double ky = ry * (1.0 - BL_MATH_KAPPA);
1429
1430 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1431 appender.moveTo(x0 + rx, y0);
1432 appender.lineTo(x1 - rx, y0);
1433 appender.cubicTo(x1 - kx, y0, x1, y0 + ky, x1, y0 + ry);
1434 appender.lineTo(x1, y1 - ry);
1435 appender.cubicTo(x1, y1 - ky, x1 - kx, y1, x1 - rx, y1);
1436 appender.lineTo(x0 + rx, y1);
1437 appender.cubicTo(x0 + kx, y1, x0, y1 - ky, x0, y1 - ry);
1438 appender.lineTo(x0, y0 + ry);
1439 appender.cubicTo(x0, y0 + ky, x0 + kx, y0, x0 + rx, y0);
1440 appender.close();
1441 }
1442 else {
1443 appender.moveTo(x0 + rx, y0);
1444 appender.cubicTo(x0 + kx, y0, x0, y0 + ky, x0, y0 + ry);
1445 appender.lineTo(x0, y1 - ry);
1446 appender.cubicTo(x0, y1 - ky, x0 + kx, y1, x0 + rx, y1);
1447 appender.lineTo(x1 - rx, y1);
1448 appender.cubicTo(x1 - kx, y1, x1, y1 - ky, x1, y1 - ry);
1449 appender.lineTo(x1, y0 + ry);
1450 appender.cubicTo(x1, y0 + ky, x1 - kx, y0, x1 - rx, y0);
1451 appender.close();
1452 }
1453 break;
1454 }
1455
1456 case BL_GEOMETRY_TYPE_LINE: {
1457 const BLPoint* src = static_cast<const BLPoint*>(geometryData);
1458 size_t first = dir != BL_GEOMETRY_DIRECTION_CW;
1459
1460 appender.moveTo(src[first]);
1461 appender.lineTo(src[first ^ 1]);
1462 break;
1463 }
1464
1465 case BL_GEOMETRY_TYPE_ARC: {
1466 const BLArc* arc = static_cast<const BLArc*>(geometryData);
1467
1468 BLPoint c(arc->cx, arc->cy);
1469 BLPoint r(arc->rx, arc->ry);
1470 double start = arc->start;
1471 double sweep = arc->sweep;
1472
1473 if (dir != BL_GEOMETRY_DIRECTION_CW)
1474 sweep = -sweep;
1475
1476 blArcToCubicSpline(appender, c, r, start, sweep, BL_PATH_CMD_MOVE);
1477 break;
1478 }
1479
1480 case BL_GEOMETRY_TYPE_CHORD:
1481 case BL_GEOMETRY_TYPE_PIE: {
1482 const BLArc* arc = static_cast<const BLArc*>(geometryData);
1483
1484 BLPoint c(arc->cx, arc->cy);
1485 BLPoint r(arc->rx, arc->ry);
1486 double start = arc->start;
1487 double sweep = arc->sweep;
1488
1489 if (dir != BL_GEOMETRY_DIRECTION_CW)
1490 sweep = -sweep;
1491
1492 uint8_t arcInitialCmd = BL_PATH_CMD_MOVE;
1493 if (geometryType == BL_GEOMETRY_TYPE_PIE) {
1494 appender.moveTo(c);
1495 arcInitialCmd = BL_PATH_CMD_ON;
1496 }
1497
1498 blArcToCubicSpline(appender, c, r, start, sweep, arcInitialCmd);
1499 appender.close();
1500 break;
1501 }
1502
1503 case BL_GEOMETRY_TYPE_TRIANGLE: {
1504 const BLPoint* src = static_cast<const BLPoint*>(geometryData);
1505 size_t cw = dir == BL_GEOMETRY_DIRECTION_CW ? 0 : 2;
1506
1507 appender.moveTo(src[0 + cw]);
1508 appender.lineTo(src[1]);
1509 appender.lineTo(src[2 - cw]);
1510 appender.close();
1511 break;
1512 }
1513
1514 case BL_GEOMETRY_TYPE_POLYLINEI: {
1515 const BLArrayView<BLPointI>* array = static_cast<const BLArrayView<BLPointI>*>(geometryData);
1516 const BLPointI* src = array->data;
1517
1518 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1519 for (size_t i = n; i; i--)
1520 appender.lineTo(*src++);
1521 }
1522 else {
1523 src += n - 1;
1524 for (size_t i = n; i; i--)
1525 appender.lineTo(*src--);
1526 }
1527
1528 appender.cmd[-intptr_t(n)] = BL_PATH_CMD_MOVE;
1529 break;
1530 }
1531
1532 case BL_GEOMETRY_TYPE_POLYLINED: {
1533 const BLArrayView<BLPoint>* array = static_cast<const BLArrayView<BLPoint>*>(geometryData);
1534 const BLPoint* src = array->data;
1535
1536 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1537 for (size_t i = n; i; i--)
1538 appender.lineTo(*src++);
1539 }
1540 else {
1541 src += n - 1;
1542 for (size_t i = n; i; i--)
1543 appender.lineTo(*src--);
1544 }
1545
1546 appender.cmd[-intptr_t(n)] = BL_PATH_CMD_MOVE;
1547 break;
1548 }
1549
1550 case BL_GEOMETRY_TYPE_POLYGONI: {
1551 const BLArrayView<BLPointI>* array = static_cast<const BLArrayView<BLPointI>*>(geometryData);
1552 const BLPointI* src = array->data;
1553
1554 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1555 for (size_t i = n - 1; i; i--)
1556 appender.lineTo(*src++);
1557 }
1558 else {
1559 src += n - 1;
1560 for (size_t i = n - 1; i; i--)
1561 appender.lineTo(*src--);
1562 }
1563
1564 appender.close();
1565 appender.cmd[-intptr_t(n)] = BL_PATH_CMD_MOVE;
1566 break;
1567 }
1568
1569 case BL_GEOMETRY_TYPE_POLYGOND: {
1570 const BLArrayView<BLPoint>* array = static_cast<const BLArrayView<BLPoint>*>(geometryData);
1571 const BLPoint* src = array->data;
1572
1573 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1574 for (size_t i = n - 1; i; i--)
1575 appender.lineTo(*src++);
1576 }
1577 else {
1578 src += n - 1;
1579 for (size_t i = n - 1; i; i--)
1580 appender.lineTo(*src--);
1581 }
1582
1583 appender.close();
1584 appender.cmd[-intptr_t(n)] = BL_PATH_CMD_MOVE;
1585 break;
1586 }
1587
1588 case BL_GEOMETRY_TYPE_ARRAY_VIEW_BOXI: {
1589 const BLArrayView<BLBoxI>* array = static_cast<const BLArrayView<BLBoxI>*>(geometryData);
1590 const BLBoxI* src = array->data;
1591
1592 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1593 for (size_t i = n; i != 0; i -= 5, src++) {
1594 if (!blIsValid(*src))
1595 continue;
1596 appender.addBoxCW(src->x0, src->y0, src->x1, src->y1);
1597 }
1598 }
1599 else {
1600 src += n - 1;
1601 for (size_t i = n; i != 0; i -= 5, src--) {
1602 if (!blIsValid(*src))
1603 continue;
1604 appender.addBoxCCW(src->x0, src->y0, src->x1, src->y1);
1605 }
1606 }
1607 break;
1608 }
1609
1610 case BL_GEOMETRY_TYPE_ARRAY_VIEW_BOXD: {
1611 const BLArrayView<BLBox>* array = static_cast<const BLArrayView<BLBox>*>(geometryData);
1612 const BLBox* src = array->data;
1613
1614 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1615 for (size_t i = n; i != 0; i -= 5, src++) {
1616 if (!blIsValid(*src))
1617 continue;
1618 appender.addBoxCW(src->x0, src->y0, src->x1, src->y1);
1619 }
1620 }
1621 else {
1622 src += n - 1;
1623 for (size_t i = n; i != 0; i -= 5, src--) {
1624 if (!blIsValid(*src))
1625 continue;
1626 appender.addBoxCCW(src->x0, src->y0, src->x1, src->y1);
1627 }
1628 }
1629 break;
1630 }
1631
1632 case BL_GEOMETRY_TYPE_ARRAY_VIEW_RECTI: {
1633 const BLArrayView<BLRectI>* array = static_cast<const BLArrayView<BLRectI>*>(geometryData);
1634 const BLRectI* src = array->data;
1635
1636 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1637 for (size_t i = n; i != 0; i -= 5, src++) {
1638 if (!blIsValid(*src))
1639 continue;
1640
1641 x0 = double(src->x);
1642 y0 = double(src->y);
1643 x1 = double(src->w) + x0;
1644 y1 = double(src->h) + y0;
1645 appender.addBoxCW(x0, y0, x1, y1);
1646 }
1647 }
1648 else {
1649 src += n - 1;
1650 for (size_t i = n; i != 0; i -= 5, src--) {
1651 if (!blIsValid(*src))
1652 continue;
1653
1654 x0 = double(src->x);
1655 y0 = double(src->y);
1656 x1 = double(src->w) + x0;
1657 y1 = double(src->h) + y0;
1658 appender.addBoxCCW(x0, y0, x1, y1);
1659 }
1660 }
1661 break;
1662 }
1663
1664 case BL_GEOMETRY_TYPE_ARRAY_VIEW_RECTD: {
1665 const BLArrayView<BLRect>* array = static_cast<const BLArrayView<BLRect>*>(geometryData);
1666 const BLRect* src = array->data;
1667
1668 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1669 for (size_t i = n; i != 0; i -= 5, src++) {
1670 if (!blIsValid(*src))
1671 continue;
1672
1673 x0 = src->x;
1674 y0 = src->y;
1675 x1 = src->w + x0;
1676 y1 = src->h + y0;
1677 appender.addBoxCW(x0, y0, x1, y1);
1678 }
1679 }
1680 else {
1681 src += n - 1;
1682 for (size_t i = n; i != 0; i -= 5, src--) {
1683 if (!blIsValid(*src))
1684 continue;
1685
1686 x0 = src->x;
1687 y0 = src->y;
1688 x1 = src->w + x0;
1689 y1 = src->h + y0;
1690 appender.addBoxCCW(x0, y0, x1, y1);
1691 }
1692 }
1693 break;
1694 }
1695
1696 case BL_GEOMETRY_TYPE_PATH: {
1697 // Only for appending path in reverse order, otherwise we use a better approach.
1698 BL_ASSERT(dir != BL_GEOMETRY_DIRECTION_CW);
1699
1700 const BLInternalPathImpl* otherI = blInternalCast(static_cast<const BLPath*>(geometryData)->impl);
1701 BLResult result = blPathCopyDataReversed(appender, BLPathIterator(otherI->view), BL_PATH_REVERSE_MODE_COMPLETE);
1702
1703 if (result != BL_SUCCESS) {
1704 self->impl->size = initialSize;
1705 return result;
1706 }
1707 break;
1708 }
1709
1710 case BL_GEOMETRY_TYPE_REGION: {
1711 const BLRegion* region = static_cast<const BLRegion*>(geometryData);
1712 const BLBoxI* src = region->data();
1713
1714 if (dir == BL_GEOMETRY_DIRECTION_CW) {
1715 for (size_t i = n; i != 0; i -= 5, src++)
1716 appender.addBoxCW(src->x0, src->y0, src->x1, src->y1);
1717 }
1718 else {
1719 src += n - 1;
1720 for (size_t i = n; i != 0; i -= 5, src--)
1721 appender.addBoxCCW(src->x0, src->y0, src->x1, src->y1);
1722 }
1723 break;
1724 }
1725
1726 default:
1727 // This is not possible considering even bad input as we have filtered this already.
1728 BL_NOT_REACHED();
1729 }
1730
1731 appender.done(self);
1732 if (!m)
1733 return BL_SUCCESS;
1734
1735 BLInternalPathImpl* selfI = blInternalCast(self->impl);
1736 BLPoint* vtxData = selfI->vertexData + initialSize;
1737 return blMatrix2DMapPointDArray(m, vtxData, vtxData, selfI->size - initialSize);
1738}
1739
1740BLResult blPathAddPath(BLPathCore* self, const BLPathCore* other, const BLRange* range) noexcept {
1741 BLInternalPathImpl* otherI = blInternalCast(other->impl);
1742 size_t start, n;
1743
1744 if (!blPathRangeCheck(otherI, range, &start, &n))
1745 return BL_SUCCESS;
1746
1747 uint8_t* cmdData;
1748 BLPoint* vtxData;
1749
1750 // Maybe `self` and `other` are the same, so get the `other` impl.
1751 BL_PROPAGATE(blPathPrepareAdd(self, n, &cmdData, &vtxData));
1752 otherI = blInternalCast(other->impl);
1753
1754 blPathCopyData(cmdData, vtxData, otherI->commandData + start, otherI->vertexData + start, n);
1755 return BL_SUCCESS;
1756}
1757
1758BLResult blPathAddTranslatedPath(BLPathCore* self, const BLPathCore* other, const BLRange* range, const BLPoint* p) noexcept {
1759 BLMatrix2D m = BLMatrix2D::makeTranslation(*p);
1760 return blPathAddTransformedPathWithType(self, other, range, &m, BL_MATRIX2D_TYPE_TRANSLATE);
1761}
1762
1763BLResult blPathAddTransformedPath(BLPathCore* self, const BLPathCore* other, const BLRange* range, const BLMatrix2D* m) noexcept {
1764 BLInternalPathImpl* otherI = blInternalCast(other->impl);
1765 size_t start, n;
1766
1767 if (!blPathRangeCheck(otherI, range, &start, &n))
1768 return BL_SUCCESS;
1769
1770 uint8_t* cmdData;
1771 BLPoint* vtxData;
1772
1773 // Maybe `self` and `other` were the same, so get the `other` impl again.
1774 BL_PROPAGATE(blPathPrepareAdd(self, n, &cmdData, &vtxData));
1775 otherI = blInternalCast(other->impl);
1776
1777 // Only check the matrix type if we reach the limit as the check costs some cycles.
1778 uint32_t mType = (n >= BL_MATRIX_TYPE_MINIMUM_SIZE) ? m->type() : BL_MATRIX2D_TYPE_AFFINE;
1779
1780 memcpy(cmdData, otherI->commandData + start, n);
1781 return blMatrix2DMapPointDArrayFuncs[mType](m, vtxData, otherI->vertexData + start, n);
1782}
1783
1784BLResult blPathAddTransformedPathWithType(BLPathCore* self, const BLPathCore* other, const BLRange* range, const BLMatrix2D* m, uint32_t mType) noexcept {
1785 BLInternalPathImpl* otherI = blInternalCast(other->impl);
1786 size_t start, n;
1787
1788 if (!blPathRangeCheck(otherI, range, &start, &n))
1789 return BL_SUCCESS;
1790
1791 uint8_t* cmdData;
1792 BLPoint* vtxData;
1793
1794 // Maybe `self` and `other` were the same, so get the `other` impl again.
1795 BL_PROPAGATE(blPathPrepareAdd(self, n, &cmdData, &vtxData));
1796 otherI = blInternalCast(other->impl);
1797
1798 memcpy(cmdData, otherI->commandData + start, n);
1799 return blMatrix2DMapPointDArrayFuncs[mType](m, vtxData, otherI->vertexData + start, n);
1800}
1801
1802BLResult blPathAddReversedPath(BLPathCore* self, const BLPathCore* other, const BLRange* range, uint32_t reverseMode) noexcept {
1803 if (BL_UNLIKELY(reverseMode >= BL_PATH_REVERSE_MODE_COUNT))
1804 return blTraceError(BL_ERROR_INVALID_VALUE);
1805
1806 BLInternalPathImpl* otherI = blInternalCast(other->impl);
1807 size_t start, n;
1808
1809 if (!blPathRangeCheck(otherI, range, &start, &n))
1810 return BL_SUCCESS;
1811
1812 size_t initialSize = self->impl->size;
1813
1814 BLPathAppender dst;
1815 BL_PROPAGATE(dst.beginAppend(self, n));
1816
1817 // Maybe `self` and `other` were the same, so get the `other` impl again.
1818 otherI = blInternalCast(other->impl);
1819 BLPathIterator src(otherI->commandData + start, otherI->vertexData + start, n);
1820
1821 BLResult result = blPathCopyDataReversed(dst, src, reverseMode);
1822 dst.done(self);
1823
1824 // Don't keep anything if reversal failed.
1825 if (result != BL_SUCCESS)
1826 self->impl->size = initialSize;
1827 return result;
1828}
1829
1830// ============================================================================
1831// [BLPath - Stroke]
1832// ============================================================================
1833
1834static BLResult blPathAddStrokedPathSink(BLPath* a, BLPath* b, BLPath* c, void* closure) noexcept {
1835 BL_UNUSED(closure);
1836
1837 BLPathAppender dst;
1838 BL_PROPAGATE(dst.begin(a, BL_MODIFY_OP_APPEND_GROW, b->size() + c->size()));
1839
1840 BLResult result = blPathJoinReversedFigure(dst, BLPathIterator(b->view()));
1841 result |= blPathJoinFigure(dst, BLPathIterator(c->view()));
1842
1843 dst.done(a);
1844 return result;
1845}
1846
1847BLResult blPathAddStrokedPath(BLPathCore* self, const BLPathCore* other, const BLRange* range, const BLStrokeOptionsCore* options, const BLApproximationOptions* approx) noexcept {
1848 BLInternalPathImpl* otherI = blInternalCast(other->impl);
1849 size_t start, n;
1850
1851 if (!blPathRangeCheck(otherI, range, &start, &n))
1852 return BL_SUCCESS;
1853
1854 if (!approx)
1855 approx = &blDefaultApproximationOptions;
1856
1857 BLPathView input { otherI->commandData + start, otherI->vertexData + start, n };
1858 BLPath bPath;
1859 BLPath cPath;
1860
1861 if (self == other) {
1862 // Border case, we don't want anything to happen to the `other` path during
1863 // processing. And since stroking may need to reallocate the output path it
1864 // would be unsafe.
1865 BLPath tmp(blDownCast(*other));
1866 return blPathStrokeInternal(input, blDownCast(*options), *approx, blDownCast(self), &bPath, &cPath, blPathAddStrokedPathSink, nullptr);
1867 }
1868 else {
1869 return blPathStrokeInternal(input, blDownCast(*options), *approx, blDownCast(self), &bPath, &cPath, blPathAddStrokedPathSink, nullptr);
1870 }
1871}
1872
1873// ============================================================================
1874// [BLPath - Path Transformations]
1875// ============================================================================
1876
1877BLResult blPathTranslate(BLPathCore* self, const BLRange* range, const BLPoint* p) noexcept {
1878 BLMatrix2D m = BLMatrix2D::makeTranslation(*p);
1879 return blPathTransformWithType(self, range, &m, BL_MATRIX2D_TYPE_TRANSLATE);
1880}
1881
1882BLResult blPathTransform(BLPathCore* self, const BLRange* range, const BLMatrix2D* m) noexcept {
1883 BLInternalPathImpl* selfI = blInternalCast(self->impl);
1884 size_t start, n;
1885
1886 if (!blPathRangeCheck(selfI, range, &start, &n))
1887 return BL_SUCCESS;
1888
1889 BL_PROPAGATE(blPathMakeMutable(self));
1890 selfI = blInternalCast(self->impl);
1891
1892 // Only check the matrix type if we reach the limit as the check costs some cycles.
1893 uint32_t mType = (n >= BL_MATRIX_TYPE_MINIMUM_SIZE) ? m->type() : BL_MATRIX2D_TYPE_AFFINE;
1894
1895 BLPoint* vtxData = selfI->vertexData + start;
1896 return blMatrix2DMapPointDArrayFuncs[mType](m, vtxData, vtxData, n);
1897}
1898
1899BLResult blPathFitTo(BLPathCore* self, const BLRange* range, const BLRect* rect, uint32_t fitFlags) noexcept {
1900 BLInternalPathImpl* selfI = blInternalCast(self->impl);
1901 size_t start, n;
1902
1903 if (!blPathRangeCheck(selfI, range, &start, &n))
1904 return BL_SUCCESS;
1905
1906 if (!blIsFinite(*rect) || rect->w <= 0.0 || rect->h <= 0.0)
1907 return blTraceError(BL_ERROR_INVALID_VALUE);
1908
1909 BLPathInfoUpdater updater;
1910 BL_PROPAGATE(updater.update(BLPathView { selfI->commandData + start, selfI->vertexData + start, n }, true));
1911
1912 // TODO: Honor `fitFlags`.
1913
1914 const BLBox& bBox = updater.boundingBox;
1915
1916 double bx = bBox.x0;
1917 double by = bBox.y0;
1918 double bw = bBox.x1 - bBox.x0;
1919 double bh = bBox.y1 - bBox.y0;
1920
1921 double tx = rect->x;
1922 double ty = rect->y;
1923 double sx = rect->w / bw;
1924 double sy = rect->h / bh;
1925
1926 tx -= bx * sx;
1927 ty -= by * sy;
1928
1929 BLMatrix2D m(sx, 0.0, 0.0, sy, tx, ty);
1930 return blPathTransformWithType(self, range, &m, BL_MATRIX2D_TYPE_SCALE);
1931}
1932
1933BLResult blPathTransformWithType(BLPathCore* self, const BLRange* range, const BLMatrix2D* m, uint32_t mType) noexcept {
1934 BLInternalPathImpl* selfI = blInternalCast(self->impl);
1935 size_t start, n;
1936
1937 if (!blPathRangeCheck(selfI, range, &start, &n))
1938 return BL_SUCCESS;
1939
1940 BL_PROPAGATE(blPathMakeMutable(self));
1941 selfI = blInternalCast(self->impl);
1942
1943 BLPoint* vtxData = selfI->vertexData + start;
1944 return blMatrix2DMapPointDArrayFuncs[mType](m, vtxData, vtxData, n);
1945}
1946
1947// ============================================================================
1948// [BLPath - Equals]
1949// ============================================================================
1950
1951bool blPathEquals(const BLPathCore* a, const BLPathCore* b) noexcept {
1952 const BLInternalPathImpl* aI = blInternalCast(a->impl);
1953 const BLInternalPathImpl* bI = blInternalCast(b->impl);
1954
1955 if (aI == bI)
1956 return true;
1957
1958 size_t size = aI->size;
1959 if (size != bI->size)
1960 return false;
1961
1962 return memcmp(aI->commandData, bI->commandData, size * sizeof(uint8_t)) == 0 &&
1963 memcmp(aI->vertexData , bI->vertexData , size * sizeof(BLPoint)) == 0;
1964}
1965
1966// ============================================================================
1967// [BLPath - Path Info]
1968// ============================================================================
1969
1970static BL_NOINLINE BLResult blPathUpdateInfoInternal(BLInternalPathImpl* selfI) noexcept {
1971 // Special-case. The path info is valid, but the path is invalid. We handle
1972 // it here to simplify `blPathEnsureInfo()` and to make it a bit shorter.
1973 if (selfI->flags & BL_PATH_FLAG_INVALID)
1974 return blTraceError(BL_ERROR_INVALID_GEOMETRY);
1975
1976 BLPathInfoUpdater updater;
1977 BLResult result = updater.update(selfI->view);
1978
1979 // Path is invalid.
1980 if (result != BL_SUCCESS) {
1981 selfI->flags = updater.flags | BL_PATH_FLAG_INVALID;
1982 selfI->controlBox.reset();
1983 selfI->boundingBox.reset();
1984 return result;
1985 }
1986
1987 // Path is empty.
1988 if (!(updater.boundingBox.x0 <= updater.boundingBox.x1 &&
1989 updater.boundingBox.y0 <= updater.boundingBox.y1)) {
1990 selfI->flags = updater.flags | BL_PATH_FLAG_EMPTY;
1991 selfI->controlBox.reset();
1992 selfI->boundingBox.reset();
1993 return BL_SUCCESS;
1994 }
1995
1996 // Path is valid.
1997 selfI->flags = updater.flags;
1998 selfI->controlBox = updater.controlBox;
1999 selfI->boundingBox = updater.boundingBox;
2000 return BL_SUCCESS;
2001}
2002
2003static BL_INLINE BLResult blPathEnsureInfo(BLInternalPathImpl* selfI) noexcept {
2004 if (selfI->flags & (BL_PATH_FLAG_INVALID | BL_PATH_FLAG_DIRTY))
2005 return blPathUpdateInfoInternal(selfI);
2006
2007 return BL_SUCCESS;
2008}
2009
2010BLResult blPathGetInfoFlags(const BLPathCore* self, uint32_t* flagsOut) noexcept {
2011 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2012 BLResult result = blPathEnsureInfo(selfI);
2013
2014 *flagsOut = selfI->flags;
2015 return result;
2016}
2017
2018// ============================================================================
2019// [BLPath - BoundingBox]
2020// ============================================================================
2021
2022BLResult blPathGetControlBox(const BLPathCore* self, BLBox* boxOut) noexcept {
2023 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2024 BLResult result = blPathEnsureInfo(selfI);
2025
2026 *boxOut = selfI->controlBox;
2027 return result;
2028}
2029
2030BLResult blPathGetBoundingBox(const BLPathCore* self, BLBox* boxOut) noexcept {
2031 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2032 BLResult result = blPathEnsureInfo(selfI);
2033
2034 *boxOut = selfI->boundingBox;
2035 return result;
2036}
2037
2038// ============================================================================
2039// [BLPath - Subpath Range]
2040// ============================================================================
2041
2042BLResult blPathGetFigureRange(const BLPathCore* self, size_t index, BLRange* rangeOut) noexcept {
2043 const BLInternalPathImpl* selfI = blInternalCast(self->impl);
2044
2045 const uint8_t* cmdData = selfI->commandData;
2046 size_t size = selfI->size;
2047
2048 if (index >= size) {
2049 rangeOut->reset(0, 0);
2050 return blTraceError(BL_ERROR_INVALID_VALUE);
2051 }
2052
2053 // Find end of the sub-path.
2054 size_t end = index + 1;
2055 while (end < size) {
2056 uint32_t cmd = cmdData[end];
2057 if (cmd == BL_PATH_CMD_MOVE)
2058 break;
2059
2060 end++;
2061 if (cmd == BL_PATH_CMD_CLOSE)
2062 break;
2063 }
2064
2065 // Find start of the sub-path.
2066 if (cmdData[index] != BL_PATH_CMD_MOVE) {
2067 while (index > 0) {
2068 uint32_t cmd = cmdData[index - 1];
2069
2070 if (cmd == BL_PATH_CMD_CLOSE)
2071 break;
2072
2073 index--;
2074 if (cmd == BL_PATH_CMD_MOVE)
2075 break;
2076 }
2077 }
2078
2079 rangeOut->reset(index, end);
2080 return BL_SUCCESS;
2081}
2082
2083// ============================================================================
2084// [BLPath - Vertex Queries]
2085// ============================================================================
2086
2087BLResult blPathGetLastVertex(const BLPathCore* self, BLPoint* vtxOut) noexcept {
2088 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2089 size_t index = selfI->size;
2090
2091 vtxOut->reset();
2092 if (BL_UNLIKELY(!index))
2093 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
2094
2095 const uint8_t* cmdData = selfI->commandData;
2096 uint32_t cmd = cmdData[--index];
2097
2098 if (cmd != BL_PATH_CMD_CLOSE) {
2099 *vtxOut = selfI->vertexData[index];
2100 return BL_SUCCESS;
2101 }
2102
2103 for (;;) {
2104 if (index == 0)
2105 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
2106
2107 cmd = cmdData[--index];
2108 if (cmd == BL_PATH_CMD_CLOSE)
2109 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
2110
2111 if (cmd == BL_PATH_CMD_MOVE)
2112 break;
2113 }
2114
2115 *vtxOut = selfI->vertexData[index];
2116 return BL_SUCCESS;
2117}
2118
2119BLResult blPathGetClosestVertex(const BLPathCore* self, const BLPoint* p, double maxDistance, size_t* indexOut, double* distanceOut) noexcept {
2120 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2121 size_t size = selfI->size;
2122
2123 *indexOut = SIZE_MAX;
2124 *distanceOut = blNaN<double>();
2125
2126 if (BL_UNLIKELY(!size))
2127 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
2128
2129 const uint8_t* cmdData = selfI->commandData;
2130 const BLPoint* vtxData = selfI->vertexData;
2131
2132 size_t bestIndex = SIZE_MAX;
2133 double bestDistance = blInf<double>();
2134 double bestDistanceSq = blInf<double>();
2135
2136 BLPoint pt(*p);
2137 bool hasMaxDistance = maxDistance > 0.0 && maxDistance < blInf<double>();
2138
2139 if (hasMaxDistance) {
2140 bestDistance = maxDistance;
2141 bestDistanceSq = blSquare(bestDistance);
2142
2143 // This code-path can be used to skip the whole path if the given point is
2144 // too far. We need 'maxDistance' to be specified and also bounding-box to
2145 // be available.
2146 if (blPathEnsureInfo(selfI) != BL_SUCCESS) {
2147 // If the given point is outside of the path bounding-box extended by
2148 // `maxDistance` then there is no matching vertex to possibly return.
2149 const BLBox& bBox = selfI->controlBox;
2150 if (!(pt.x >= bBox.x0 - bestDistance && pt.y >= bBox.y0 - bestDistance &&
2151 pt.x <= bBox.x1 + bestDistance && pt.y <= bBox.y1 + bestDistance))
2152 return blTraceError(BL_ERROR_NO_MATCHING_VERTEX);
2153 }
2154 }
2155
2156 for (size_t i = 0; i < size; i++) {
2157 if (cmdData[i] != BL_PATH_CMD_CLOSE) {
2158 double d = blSquare(vtxData[i].x - pt.x) +
2159 blSquare(vtxData[i].y - pt.y);
2160
2161 if (d < bestDistanceSq) {
2162 bestIndex = i;
2163 bestDistanceSq = d;
2164 }
2165 }
2166 }
2167
2168 if (bestIndex == SIZE_MAX)
2169 bestDistance = blNaN<double>();
2170 else
2171 bestDistance = blSqrt(bestDistanceSq);
2172
2173 *indexOut = bestIndex;
2174 *distanceOut = bestDistance;
2175
2176 return BL_SUCCESS;;
2177}
2178
2179// ============================================================================
2180// [BLPath - Hit Test]
2181// ============================================================================
2182
2183uint32_t blPathHitTest(const BLPathCore* self, const BLPoint* p_, uint32_t fillRule) noexcept {
2184 BLInternalPathImpl* selfI = blInternalCast(self->impl);
2185 size_t i = selfI->size;
2186
2187 if (!i)
2188 return BL_HIT_TEST_OUT;
2189
2190 const uint8_t* cmdData = selfI->commandData;
2191 const BLPoint* vtxData = selfI->vertexData;
2192
2193 BLPoint start {};
2194 bool hasMoveTo = false;
2195
2196 BLPoint pt(*p_);
2197
2198 double x0, y0;
2199 double x1, y1;
2200
2201 intptr_t windingNumber = 0;
2202 BLPoint ptBuffer[8];
2203
2204 do {
2205 switch (cmdData[0]) {
2206 case BL_PATH_CMD_MOVE: {
2207 if (hasMoveTo) {
2208 x0 = vtxData[-1].x;
2209 y0 = vtxData[-1].y;
2210 x1 = start.x;
2211 y1 = start.y;
2212
2213 hasMoveTo = false;
2214 goto OnLine;
2215 }
2216
2217 start = vtxData[0];
2218
2219 cmdData++;
2220 vtxData++;
2221 i--;
2222
2223 hasMoveTo = true;
2224 break;
2225 }
2226
2227 case BL_PATH_CMD_ON: {
2228 if (BL_UNLIKELY(!hasMoveTo))
2229 return BL_HIT_TEST_INVALID;
2230
2231 x0 = vtxData[-1].x;
2232 y0 = vtxData[-1].y;
2233 x1 = vtxData[0].x;
2234 y1 = vtxData[0].y;
2235
2236 cmdData++;
2237 vtxData++;
2238 i--;
2239
2240OnLine:
2241 {
2242 double dx = x1 - x0;
2243 double dy = y1 - y0;
2244
2245 if (dy > 0.0) {
2246 if (pt.y >= y0 && pt.y < y1) {
2247 double ix = x0 + (pt.y - y0) * dx / dy;
2248 windingNumber += (pt.x >= ix);
2249 }
2250 }
2251 else if (dy < 0.0) {
2252 if (pt.y >= y1 && pt.y < y0) {
2253 double ix = x0 + (pt.y - y0) * dx / dy;
2254 windingNumber -= (pt.x >= ix);
2255 }
2256 }
2257 }
2258 break;
2259 }
2260
2261 case BL_PATH_CMD_QUAD: {
2262 BL_ASSERT(hasMoveTo);
2263 BL_ASSERT(i >= 2);
2264
2265 const BLPoint* p = vtxData - 1;
2266 if (BL_UNLIKELY(!hasMoveTo))
2267 return BL_HIT_TEST_INVALID;
2268
2269 double minY = blMin(p[0].y, p[1].y, p[2].y);
2270 double maxY = blMax(p[0].y, p[1].y, p[2].y);
2271
2272 cmdData += 2;
2273 vtxData += 2;
2274 i -= 2;
2275
2276 if (pt.y >= minY && pt.y <= maxY) {
2277 bool degenerate = isNear(p[0].y, p[1].y) && isNear(p[1].y, p[2].y);
2278
2279 if (degenerate) {
2280 x0 = p[0].x;
2281 y0 = p[0].y;
2282 x1 = p[2].x;
2283 y1 = p[2].y;
2284 goto OnLine;
2285 }
2286
2287 // Subdivide curve to curve-spline separated at Y-extrama.
2288 BLPoint* left = (BLPoint*)ptBuffer;
2289 BLPoint* rght = (BLPoint*)ptBuffer + 3;
2290
2291 double tArray[2];
2292 tArray[0] = (p[0].y - p[1].y) / (p[0].y - 2.0 * p[1].y + p[2].y);
2293
2294 size_t tLength = tArray[0] > 0.0 && tArray[0] < 1.0;
2295 tArray[tLength++] = 1.0;
2296
2297 rght[0] = p[0];
2298 rght[1] = p[1];
2299 rght[2] = p[2];
2300
2301 double tCut = 0.0;
2302 for (size_t tIndex = 0; tIndex < tLength; tIndex++) {
2303 double tVal = tArray[tIndex];
2304 if (tVal == tCut) continue;
2305
2306 if (tVal == 1.0) {
2307 left[0] = rght[0];
2308 left[1] = rght[1];
2309 left[2] = rght[2];
2310 }
2311 else {
2312 blSplitQuad(rght, left, rght, tCut == 0.0 ? tVal : (tVal - tCut) / (1.0 - tCut));
2313 }
2314
2315 minY = blMin(left[0].y, left[2].y);
2316 maxY = blMax(left[0].y, left[2].y);
2317
2318 if (pt.y >= minY && pt.y < maxY) {
2319 int dir = 0;
2320 if (left[0].y < left[2].y)
2321 dir = 1;
2322 else if (left[0].y > left[2].y)
2323 dir = -1;
2324
2325 // It should be only possible to have none or one solution.
2326 double ti[2];
2327 double ix;
2328
2329 BLPoint a, b, c;
2330 blGetQuadCoefficients(left, a, b, c);
2331
2332 // { At^2 + Bt + C } -> { t(At + B) + C }
2333 if (blQuadRoots(ti, a.y, b.y, c.y - pt.y, BL_MATH_AFTER_0, BL_MATH_BEFORE_1) >= 1)
2334 ix = ti[0] * (a.x * ti[0] + b.x) + c.x;
2335 else if (pt.y - minY < maxY - pt.y)
2336 ix = p[0].x;
2337 else
2338 ix = p[2].x;
2339
2340 if (pt.x >= ix)
2341 windingNumber += dir;
2342 }
2343
2344 tCut = tVal;
2345 }
2346 }
2347 break;
2348 }
2349
2350 case BL_PATH_CMD_CUBIC: {
2351 BL_ASSERT(hasMoveTo);
2352 BL_ASSERT(i >= 3);
2353
2354 const BLPoint* p = vtxData - 1;
2355 if (BL_UNLIKELY(!hasMoveTo))
2356 return BL_HIT_TEST_INVALID;
2357
2358 double minY = blMin(p[0].y, p[1].y, p[2].y, p[3].y);
2359 double maxY = blMax(p[0].y, p[1].y, p[2].y, p[3].y);
2360
2361 cmdData += 3;
2362 vtxData += 3;
2363 i -= 3;
2364
2365 if (pt.y >= minY && pt.y <= maxY) {
2366 bool degenerate = isNear(p[0].y, p[1].y) &&
2367 isNear(p[1].y, p[2].y) &&
2368 isNear(p[2].y, p[3].y) ;
2369
2370 if (degenerate) {
2371 x0 = p[0].x;
2372 y0 = p[0].y;
2373 x1 = p[3].x;
2374 y1 = p[3].y;
2375 goto OnLine;
2376 }
2377
2378 // Subdivide curve to curve-spline separated at Y-extrama.
2379 BLPoint* left = (BLPoint*)ptBuffer;
2380 BLPoint* rght = (BLPoint*)ptBuffer + 4;
2381
2382 double tArray[3];
2383 size_t tLength = blQuadRoots(
2384 tArray,
2385 3.0 * (-p[0].y + 3.0 * (p[1].y - p[2].y) + p[3].y),
2386 6.0 * ( p[0].y - 2.0 * (p[1].y + p[2].y) ),
2387 3.0 * (-p[0].y + (p[1].y ) ),
2388 BL_MATH_AFTER_0,
2389 BL_MATH_BEFORE_1);
2390 tArray[tLength++] = 1.0;
2391
2392 rght[0] = p[0];
2393 rght[1] = p[1];
2394 rght[2] = p[2];
2395 rght[3] = p[3];
2396
2397 double tCut = 0.0;
2398 for (size_t tIndex = 0; tIndex < tLength; tIndex++) {
2399 double tVal = tArray[tIndex];
2400 if (tVal == tCut) continue;
2401
2402 if (tVal == 1.0) {
2403 left[0] = rght[0];
2404 left[1] = rght[1];
2405 left[2] = rght[2];
2406 left[3] = rght[3];
2407 }
2408 else {
2409 blSplitCubic(rght, rght, left, tCut == 0.0 ? tVal : (tVal - tCut) / (1.0 - tCut));
2410 }
2411
2412 minY = blMin(left[0].y, left[3].y);
2413 maxY = blMax(left[0].y, left[3].y);
2414
2415 if (pt.y >= minY && pt.y < maxY) {
2416 int dir = 0;
2417 if (left[0].y < left[3].y)
2418 dir = 1;
2419 else if (left[0].y > left[3].y)
2420 dir = -1;
2421
2422 // It should be only possible to have zero/one solution.
2423 double ti[3];
2424 double ix;
2425
2426 BLPoint a, b, c, d;
2427 blGetCubicCoefficients(left, a, b, c, d);
2428
2429 // { At^3 + Bt^2 + Ct + D } -> { ((At + B)t + C)t + D }
2430 if (blCubicRoots(ti, a.y, b.y, c.y, d.y - pt.y, BL_MATH_AFTER_0, BL_MATH_BEFORE_1) >= 1)
2431 ix = ((a.x * ti[0] + b.x) * ti[0] + c.x) * ti[0] + d.x;
2432 else if (pt.y - minY < maxY - pt.y)
2433 ix = p[0].x;
2434 else
2435 ix = p[3].x;
2436
2437 if (pt.x >= ix)
2438 windingNumber += dir;
2439 }
2440
2441 tCut = tVal;
2442 }
2443 }
2444 break;
2445 }
2446
2447 case BL_PATH_CMD_CLOSE: {
2448 if (hasMoveTo) {
2449 x0 = vtxData[-1].x;
2450 y0 = vtxData[-1].y;
2451 x1 = start.x;
2452 y1 = start.y;
2453
2454 hasMoveTo = false;
2455 goto OnLine;
2456 }
2457
2458 cmdData++;
2459 vtxData++;
2460
2461 i--;
2462 break;
2463 }
2464
2465 default:
2466 return BL_HIT_TEST_INVALID;
2467 }
2468 } while (i);
2469
2470 // Close the path.
2471 if (hasMoveTo) {
2472 x0 = vtxData[-1].x;
2473 y0 = vtxData[-1].y;
2474 x1 = start.x;
2475 y1 = start.y;
2476
2477 hasMoveTo = false;
2478 goto OnLine;
2479 }
2480
2481 if (fillRule == BL_FILL_RULE_EVEN_ODD)
2482 windingNumber &= 1;
2483 return windingNumber != 0;
2484}
2485
2486// ============================================================================
2487// [BLPath - Runtime Init]
2488// ============================================================================
2489
2490void blPathRtInit(BLRuntimeContext* rt) noexcept {
2491 BL_UNUSED(rt);
2492
2493 BLInternalPathImpl* pathI = &blNullPathImpl;
2494 pathI->implType = uint8_t(BL_IMPL_TYPE_PATH);
2495 pathI->implTraits = uint8_t(BL_IMPL_TRAIT_NULL);
2496 pathI->flags = BL_PATH_FLAG_EMPTY;
2497 blAssignBuiltInNull(pathI);
2498}
2499