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 "./blarrayops_p.h"
10#include "./blgeometry_p.h"
11#include "./blregion_p.h"
12#include "./blruntime_p.h"
13#include "./blsupport_p.h"
14
15// ============================================================================
16// [Global Variables]
17// ============================================================================
18
19static BLWrap<BLInternalRegionImpl> blNullRegionImpl;
20
21static const BLBoxI blRegionLargestBoxI {
22 blMinValue<int>(),
23 blMinValue<int>(),
24 blMaxValue<int>(),
25 blMaxValue<int>()
26};
27
28// ============================================================================
29// [BLRegion - Internal]
30// ============================================================================
31
32static constexpr size_t blRegionImplSizeOf(size_t n = 0) noexcept { return blContainerSizeOf(sizeof(BLInternalRegionImpl), sizeof(BLBoxI), n); }
33static constexpr size_t blRegionCapacityOf(size_t implSize) noexcept { return blContainerCapacityOf(sizeof(BLInternalRegionImpl), sizeof(BLBoxI), implSize); }
34static constexpr size_t blRegionMaximumCapacity() noexcept { return blRegionCapacityOf(SIZE_MAX); }
35static BL_INLINE size_t blRegionFittingCapacity(size_t n) noexcept { return blContainerFittingCapacity(blRegionImplSizeOf(), sizeof(BLBoxI), n); }
36static BL_INLINE size_t blRegionGrowingCapacity(size_t n) noexcept { return blContainerGrowingCapacity(blRegionImplSizeOf(), sizeof(BLBoxI), n, BL_ALLOC_HINT_REGION); }
37
38static BL_INLINE void blRegionCopyData(BLBoxI* dst, const BLBoxI* src, size_t n) noexcept {
39 for (size_t i = 0; i < n; i++)
40 dst[i] = src[i];
41}
42
43static BL_INLINE BLBoxI blRegionCopyDataAndCalcBBox(BLBoxI* dst, const BLBoxI* src, size_t n) noexcept {
44 BL_ASSUME(n > 0);
45
46 int bBoxX0 = blMaxValue<int>();
47 int bBoxX1 = blMinValue<int>();
48
49 for (size_t i = 0; i < n; i++) {
50 bBoxX0 = blMin(bBoxX0, src[i].x0);
51 bBoxX1 = blMax(bBoxX1, src[i].x1);
52 dst[i] = src[i];
53 }
54
55 return BLBoxI(bBoxX0, src[0].y0, bBoxX1, src[n - 1].y1);
56}
57
58static BL_INLINE BLInternalRegionImpl* blRegionImplNew(size_t n) noexcept {
59 uint16_t memPoolData;
60 BLInternalRegionImpl* impl = blRuntimeAllocImplT<BLInternalRegionImpl>(blRegionImplSizeOf(n), &memPoolData);
61
62 if (BL_UNLIKELY(!impl))
63 return impl;
64
65 blImplInit(impl, BL_IMPL_TYPE_REGION, BL_IMPL_TRAIT_MUTABLE, memPoolData);
66 impl->data = blOffsetPtr<BLBoxI>(impl, sizeof(BLInternalRegionImpl));
67 impl->size = 0;
68 impl->capacity = n;
69 impl->reserved[0] = 0;
70 impl->reserved[1] = 0;
71 impl->reserved[2] = 0;
72 impl->reserved[3] = 0;
73 impl->boundingBox.reset();
74
75 return impl;
76}
77
78// Cannot be static, called by `BLVariant` implementation.
79BLResult blRegionImplDelete(BLRegionImpl* impl_) noexcept {
80 BLInternalRegionImpl* impl = blInternalCast(impl_);
81
82 uint8_t* implBase = reinterpret_cast<uint8_t*>(impl);
83 size_t implSize = blRegionImplSizeOf(impl->capacity);
84 uint32_t implTraits = impl->implTraits;
85 uint32_t memPoolData = impl->memPoolData;
86
87 if (implTraits & BL_IMPL_TRAIT_EXTERNAL) {
88 implSize = blRegionImplSizeOf() + sizeof(BLExternalImplPreface);
89 implBase -= sizeof(BLExternalImplPreface);
90 blImplDestroyExternal(impl);
91 }
92
93 if (implTraits & BL_IMPL_TRAIT_FOREIGN)
94 return BL_SUCCESS;
95 else
96 return blRuntimeFreeImpl(implBase, implSize, memPoolData);
97}
98
99static BL_INLINE BLResult blRegionImplRelease(BLInternalRegionImpl* impl) noexcept {
100 if (blImplDecRefAndTest(impl))
101 return blRegionImplDelete(impl);
102 return BL_SUCCESS;
103}
104
105static BL_NOINLINE BLResult blRegionRealloc(BLRegionCore* self, size_t n) noexcept {
106 BLInternalRegionImpl* oldI = blInternalCast(self->impl);
107 BLInternalRegionImpl* newI = blRegionImplNew(n);
108
109 if (BL_UNLIKELY(!newI))
110 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
111
112 size_t size = oldI->size;
113 BL_ASSERT(size <= n);
114
115 self->impl = newI;
116 newI->size = size;
117 newI->boundingBox = oldI->boundingBox;
118 blRegionCopyData(newI->data, oldI->data, size);
119
120 return blRegionImplRelease(oldI);
121}
122
123// ============================================================================
124// [BLRegion - Matcher]
125// ============================================================================
126
127struct BLRegionXYMatcher {
128 int x, y;
129 BL_INLINE BLRegionXYMatcher(int x, int y) noexcept : x(x), y(y) {}
130};
131static BL_INLINE bool operator<(const BLBoxI& a, const BLRegionXYMatcher& b) noexcept { return (a.y1 <= b.y) || ((a.y0 <= b.y) & (a.x1 <= b.x)); }
132
133// ============================================================================
134// [BLRegion - Utilities]
135// ============================================================================
136
137static BL_INLINE const BLBoxI& blAsBox(const BLBoxI& box) noexcept { return box; }
138static BL_INLINE BLBoxI blAsBox(const BLRectI& rect) noexcept { return BLBoxI(rect.x, rect.y, rect.x + rect.w, rect.y + rect.h); }
139
140//! Checks whether two bands (of the same size) must coalesce.
141static BL_INLINE bool blRegionMustCoalesce(const BLBoxI* aBand, const BLBoxI* bBand, size_t n) noexcept {
142 size_t i = 0;
143 while (i < n && (aBand[i].x0 == bBand[i].x0) & (aBand[i].x1 == bBand[i].x1))
144 i++;
145 return i == n;
146}
147
148//! Checks whether two bands (of the same size) must coalesce.
149static BL_INLINE bool blRegionMustCoalesce(const BLRectI* aBand, const BLRectI* bBand, size_t n) noexcept {
150 size_t i = 0;
151 while (i < n && (aBand[i].x == bBand[i].x) & (aBand[i].w == bBand[i].w))
152 i++;
153 return i == n;
154}
155
156static BL_INLINE void blRegionSetBandY1(BLBoxI* band, size_t n, int y1) noexcept {
157 for (size_t i = 0; i < n; i++)
158 band[i].y1 = y1;
159}
160
161// Get the end band of the current horizontal rectangle list.
162static BL_INLINE const BLBoxI* blRegionGetEndBand(const BLBoxI* data, const BLBoxI* end) {
163 const BLBoxI* cur = data;
164 int y0 = data[0].y0;
165
166 while (++cur != end && cur[0].y0 == y0)
167 continue;
168 return cur;
169}
170
171static BL_INLINE BLBoxI* blRegionCoalesce(BLBoxI* p, BLBoxI* curBand, int y1, size_t *prevBandSize) noexcept {
172 size_t bandSize = (size_t)(p - curBand);
173 if (*prevBandSize == bandSize) {
174 BLBoxI* prevBand = curBand - bandSize;
175 if (prevBand->y1 == curBand->y0 && blRegionMustCoalesce(prevBand, curBand, bandSize)) {
176 blRegionSetBandY1(prevBand, bandSize, y1);
177 return curBand;
178 }
179 }
180 *prevBandSize = bandSize;
181 return p;
182}
183
184// ============================================================================
185// [BLRegion - Analysis]
186// ============================================================================
187
188static uint32_t blRegionAnalyzeBoxIArray(const BLBoxI* data, size_t size, size_t* sizeOut) {
189 const BLBoxI* end = data + size;
190 *sizeOut = size;
191
192 if (data == end)
193 return BL_DATA_ANALYSIS_CONFORMING;
194
195 const BLBoxI* prevBand = data;
196 uint32_t prevBandSum = 0;
197
198 do {
199 int y0 = data->y0;
200 int y1 = data->y1;
201 int x1 = data->x1;
202
203 const BLBoxI* curBand = data;
204 uint32_t curBandSum = unsigned(x1);
205
206 if (BL_UNLIKELY((data->x0 >= x1) | (y0 >= y1)))
207 return BL_DATA_ANALYSIS_INVALID_VALUE;
208
209 while (++data != end) {
210 if ((data->y0 != y0) | (data->y1 != y1)) {
211 // Start of a next band.
212 if (data->y0 >= y1)
213 break;
214
215 // Detect non-conforming box.
216 if (BL_UNLIKELY(data->y0 < y1))
217 goto NonConforming;
218 }
219
220 if (BL_UNLIKELY((data->x0 <= x1) | (data->x0 >= data->x1)))
221 goto NonConforming;
222
223 x1 = data->x1;
224 curBandSum += unsigned(x1);
225 }
226
227 if (prevBand->y1 == y0) {
228 if (curBandSum == prevBandSum) {
229 size_t prevBandSize = (size_t)(curBand - prevBand);
230 size_t curBandSize = (size_t)(data - curBand);
231
232 if (prevBandSize == curBandSize && blRegionMustCoalesce(prevBand, curBand, curBandSize))
233 size -= curBandSize;
234 }
235 }
236
237 prevBand = curBand;
238 prevBandSum = curBandSum;
239 } while (data != end);
240
241 *sizeOut = size;
242 return BL_DATA_ANALYSIS_CONFORMING;
243
244NonConforming:
245 do {
246 if (BL_UNLIKELY((data->x0 >= data->x1) | (data->y0 >= data->y1)))
247 return BL_DATA_ANALYSIS_INVALID_VALUE;
248 } while (++data != end);
249
250 return BL_DATA_ANALYSIS_NON_CONFORMING;
251}
252
253static uint32_t blRegionAnalyzeRectIArray(const BLRectI* data, size_t size, size_t* sizeOut) {
254 const BLRectI* end = data + size;
255 *sizeOut = size;
256
257 if (data == end)
258 return BL_DATA_ANALYSIS_CONFORMING;
259
260 const BLRectI* prevBand = data;
261 uint32_t prevBandSum = 0;
262
263 do {
264 int y0 = data->y;
265 int y1;
266 int x1 = data->x;
267 int h = data->h;
268
269 BLOverflowFlag of = 0;
270 x1 = blAddOverflow(x1, data->w, &of);
271 y1 = blAddOverflow(y0, h, &of);
272
273 if (BL_UNLIKELY(of | (data->w <= 0) | (h <= 0)))
274 return BL_DATA_ANALYSIS_INVALID_VALUE;
275
276 const BLRectI* curBand = data;
277 uint32_t curBandSum = unsigned(x1);
278
279 while (++data != end) {
280 if ((data->y != y0) | (data->h != h)) {
281 // Start of a next band.
282 if (data->y >= y1)
283 break;
284
285 // Detect non-conforming box.
286 if (data->y < y1)
287 goto NonConforming;
288 }
289
290 if (BL_UNLIKELY((data->x <= x1)))
291 goto NonConforming;
292
293 x1 = blAddOverflow(data->x, data->w, &of);
294 if (BL_UNLIKELY(of | (data->w <= 0)))
295 return BL_DATA_ANALYSIS_INVALID_VALUE;
296
297 curBandSum += unsigned(x1);
298 }
299
300 if (prevBand->y + prevBand->h == y0) {
301 if (curBandSum == prevBandSum) {
302 size_t prevBandSize = (size_t)(curBand - prevBand);
303 size_t curBandSize = (size_t)(data - curBand);
304
305 if (prevBandSize == curBandSize && blRegionMustCoalesce(prevBand, curBand, curBandSize))
306 size -= curBandSize;
307 }
308 }
309
310 prevBand = curBand;
311 prevBandSum = curBandSum;
312 } while (data != end);
313
314 *sizeOut = size;
315 return BL_DATA_ANALYSIS_CONFORMING;
316
317NonConforming:
318 do {
319 BLOverflowFlag of = 0;
320 int w = data->w;
321 int h = data->h;
322 blAddOverflow(data->x, w, &of);
323 blAddOverflow(data->y, h, &of);
324 if (BL_UNLIKELY(of | (w <= 0) | (h <= 0)))
325 return BL_DATA_ANALYSIS_INVALID_VALUE;
326 } while (++data != end);
327
328 return BL_DATA_ANALYSIS_NON_CONFORMING;
329}
330
331static bool blRegionImplIsValid(const BLInternalRegionImpl* impl) noexcept {
332 if (impl->capacity < impl->size)
333 return false;
334
335 const BLBoxI* data = impl->data;
336 const BLBoxI& bbox = impl->boundingBox;
337
338 size_t n = impl->size;
339
340 // If the region is empty the bounding box must match [0, 0, 0, 0].
341 if (!n)
342 return bbox.x0 == 0 && bbox.y0 == 0 && bbox.x1 == 0 && bbox.y1 == 0;
343
344 if (n == 1)
345 return blIsValid(data[0]) && data[0] == bbox;
346
347 size_t coalescedSize;
348 uint32_t status = blRegionAnalyzeBoxIArray(data, n, &coalescedSize);
349
350 return status == BL_DATA_ANALYSIS_CONFORMING && n == coalescedSize;
351}
352
353// ============================================================================
354// [BLRegion - Init / Reset]
355// ============================================================================
356
357BLResult blRegionInit(BLRegionCore* self) noexcept {
358 self->impl = BLRegion::none().impl;
359 return BL_SUCCESS;
360}
361
362BLResult blRegionReset(BLRegionCore* self) noexcept {
363 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
364 self->impl = &blNullRegionImpl;
365 return blRegionImplRelease(selfI);
366}
367
368// ============================================================================
369// [BLRegion - Storage]
370// ============================================================================
371
372BLResult blRegionClear(BLRegionCore* self) noexcept {
373 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
374
375 if (!blImplIsMutable(selfI)) {
376 self->impl = &blNullRegionImpl;
377 return blRegionImplRelease(selfI);
378 }
379 else {
380 selfI->size = 0;
381 selfI->boundingBox.reset();
382 return BL_SUCCESS;
383 }
384}
385
386BLResult blRegionShrink(BLRegionCore* self) noexcept {
387 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
388 size_t size = selfI->size;
389
390 if (!size) {
391 self->impl = &blNullRegionImpl;
392 return blRegionImplRelease(selfI);
393 }
394
395 size_t capacity = blRegionFittingCapacity(size);
396 if (capacity >= selfI->capacity)
397 return BL_SUCCESS;
398
399 return blRegionRealloc(self, capacity);
400}
401
402BLResult blRegionReserve(BLRegionCore* self, size_t n) noexcept {
403 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
404 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
405
406 if ((n | immutableMsk) > selfI->capacity) {
407 if (BL_UNLIKELY(n > blRegionMaximumCapacity()))
408 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
409
410 size_t capacity = blRegionFittingCapacity(blMax(n, selfI->size));
411 return blRegionRealloc(self, capacity);
412 }
413
414 return BL_SUCCESS;
415}
416
417static BLResult blRegionMakeMutableToAssign(BLRegionCore* self, size_t n) noexcept {
418 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
419 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
420
421 if ((n | immutableMsk) > selfI->capacity) {
422 if (BL_UNLIKELY(n > blRegionMaximumCapacity()))
423 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
424
425 size_t capacity = blRegionFittingCapacity(n);
426 BLInternalRegionImpl* newI = blRegionImplNew(capacity);
427
428 if (BL_UNLIKELY(!newI))
429 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
430
431 self->impl = newI;
432 return blRegionImplRelease(selfI);
433 }
434
435 return BL_SUCCESS;
436}
437
438static BLResult blRegionMakeMutableToAppend(BLRegionCore* self, size_t n) noexcept {
439 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
440 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
441
442 // NOTE: This can never overflow in theory due to size of `BLBoxI`.
443 n += selfI->size;
444
445 if ((n | immutableMsk) > selfI->capacity) {
446 if (BL_UNLIKELY(n > blRegionMaximumCapacity()))
447 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
448
449 size_t capacity = blRegionFittingCapacity(n);
450 return blRegionRealloc(self, capacity);
451 }
452
453 return BL_SUCCESS;
454}
455
456// ============================================================================
457// [BLRegion - Assign]
458// ============================================================================
459
460static BLResult blRegionAssignValidBoxIArray(BLRegionCore* self, const BLBoxI* data, size_t n) noexcept {
461 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
462 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
463
464 if ((n | immutableMsk) > selfI->capacity) {
465 if (BL_UNLIKELY(n > blRegionMaximumCapacity()))
466 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
467
468 size_t capacity = blRegionFittingCapacity(n);
469 BLInternalRegionImpl* newI = blRegionImplNew(capacity);
470
471 if (BL_UNLIKELY(!newI))
472 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
473
474 self->impl = newI;
475 newI->size = n;
476 newI->boundingBox = blRegionCopyDataAndCalcBBox(newI->data, data, n);
477
478 return blRegionImplRelease(selfI);
479 }
480
481 if (!n)
482 return blRegionClear(self);
483
484 selfI->size = n;
485 selfI->boundingBox = blRegionCopyDataAndCalcBBox(selfI->data, data, n);
486
487 return BL_SUCCESS;
488}
489
490static BLResult blRegionAssignValidBoxIArray(BLRegionCore* self, const BLBoxI* data, size_t n, const BLBoxI* bbox) noexcept {
491 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
492 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI));
493
494 if ((n | immutableMsk) > selfI->capacity) {
495 if (BL_UNLIKELY(n > blRegionMaximumCapacity()))
496 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
497
498 size_t capacity = blRegionFittingCapacity(n);
499 BLInternalRegionImpl* newI = blRegionImplNew(capacity);
500
501 if (BL_UNLIKELY(!newI))
502 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
503
504 self->impl = newI;
505 newI->size = n;
506 newI->boundingBox = *bbox;
507 blRegionCopyData(newI->data, data, n);
508
509 return blRegionImplRelease(selfI);
510 }
511
512 if (!n)
513 return blRegionClear(self);
514
515 selfI->size = n;
516 selfI->boundingBox = *bbox;
517 blRegionCopyData(selfI->data, data, n);
518
519 return BL_SUCCESS;
520}
521
522template<typename T>
523static BLResult blRegionAssignAlmostConformingBoxIArray(BLRegionCore* self, const T* srcData, size_t n, size_t analysisSize) noexcept {
524 BL_PROPAGATE(blRegionMakeMutableToAssign(self, analysisSize));
525 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
526
527 BLBoxI* dstData = selfI->data;
528 size_t prevBandSize = SIZE_MAX;
529
530 BL_ASSUME(n > 0);
531 const T* srcEnd = srcData + n;
532
533 int bBoxX0 = blMaxValue<int>();
534 int bBoxX1 = blMinValue<int>();
535
536 do {
537 // First box is always appended as is.
538 BL_ASSERT(dstData != selfI->data + selfI->capacity);
539 dstData->reset(blAsBox(*srcData));
540
541 int y0 = dstData[0].y0;
542 int y1 = dstData[0].y1;
543
544 // Next boxes are either merged with the previous one or appended.
545 BLBoxI* curBand = dstData++;
546 while (++srcData != srcEnd) {
547 BLBoxI src = blAsBox(*srcData);
548 if (src.y0 != y0)
549 break;
550
551 if (dstData[-1].x1 == src.x0) {
552 dstData[-1].x1 = src.x1;
553 }
554 else {
555 BL_ASSERT(dstData != selfI->data + selfI->capacity);
556 dstData->reset(src.x0, y0, src.x1, y1);
557 dstData++;
558 }
559 }
560
561 bBoxX0 = blMin(bBoxX0, curBand[0].x0);
562 bBoxX1 = blMax(bBoxX1, dstData[-1].x1);
563
564 dstData = blRegionCoalesce(dstData, curBand, y1, &prevBandSize);
565 } while (srcData != srcEnd);
566
567 n = (size_t)(dstData - selfI->data);
568 selfI->size = n;
569 selfI->boundingBox.reset(bBoxX0, selfI->data[0].y0, bBoxX1, dstData[-1].y1);
570
571 BL_ASSERT(blRegionImplIsValid(selfI));
572 return BL_SUCCESS;
573}
574
575template<typename T>
576static BLResult blRegionAssignNonConformingBoxIArray(BLRegionCore* self, const T* srcData, size_t n) noexcept {
577 BLRegion tmp;
578 BLRegionCore* regions[2] = { &tmp, self };
579 size_t index = 0;
580
581 const T* srcEnd = srcData + n;
582 while (srcData != srcEnd) {
583 BLBoxI src = blAsBox(*srcData);
584 BL_PROPAGATE(blRegionCombineRB(regions[index ^ 1], regions[index], &src, BL_BOOLEAN_OP_OR));
585 index ^= 1;
586 }
587
588 return blRegionAssignWeak(self, regions[index]);
589}
590
591BLResult blRegionAssignMove(BLRegionCore* self, BLRegionCore* other) noexcept {
592 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
593 BLInternalRegionImpl* otherI = blInternalCast(other->impl);
594
595 self->impl = otherI;
596 other->impl = &blNullRegionImpl;
597
598 return blRegionImplRelease(selfI);
599}
600
601BLResult blRegionAssignWeak(BLRegionCore* self, const BLRegionCore* other) noexcept {
602 BLInternalRegionImpl* selfI = blInternalCast(self->impl);
603 BLInternalRegionImpl* otherI = blInternalCast(other->impl);
604
605 self->impl = blImplIncRef(otherI);
606 return blRegionImplRelease(selfI);
607}
608
609BLResult blRegionAssignDeep(BLRegionCore* self, const BLRegionCore* other) noexcept {
610 BLInternalRegionImpl* otherI = blInternalCast(other->impl);
611 return blRegionAssignValidBoxIArray(self, otherI->data, otherI->size, &otherI->boundingBox);
612}
613
614BLResult blRegionAssignBoxI(BLRegionCore* self, const BLBoxI* src) noexcept {
615 if ((src->x0 >= src->x1) | (src->y0 >= src->y1))
616 return blTraceError(BL_ERROR_INVALID_VALUE);
617 return blRegionAssignValidBoxIArray(self, src, 1, src);
618}
619
620BLResult blRegionAssignBoxIArray(BLRegionCore* self, const BLBoxI* data, size_t n) noexcept {
621 if (!n)
622 return blRegionClear(self);
623
624 size_t analysisSize;
625 uint32_t analysisStatus = blRegionAnalyzeBoxIArray(data, n, &analysisSize);
626
627 if (analysisStatus >= BL_DATA_ANALYSIS_INVALID_VALUE)
628 return blTraceError(BL_ERROR_INVALID_VALUE);
629
630 if (analysisStatus == BL_DATA_ANALYSIS_NON_CONFORMING)
631 return blRegionAssignNonConformingBoxIArray<BLBoxI>(self, data, n);
632
633 // If `analysisSize == n` it means that the given data is conforming and
634 // properly coalesced. The easiest way to assign these boxes to the
635 // region is to use `blRegionAssignValidBoxIArray()` as it would also
636 // handle the case in which the given `data` overlaps `self` data.
637 if (analysisSize == n)
638 return blRegionAssignValidBoxIArray(self, data, n);
639 else
640 return blRegionAssignAlmostConformingBoxIArray<BLBoxI>(self, data, n, analysisSize);
641}
642
643BLResult blRegionAssignRectI(BLRegionCore* self, const BLRectI* rect) noexcept {
644 int w = rect->w;
645 int h = rect->h;
646
647 if (BL_UNLIKELY((w <= 0) | (h <= 0)))
648 return blTraceError(BL_ERROR_INVALID_VALUE);
649
650 BLOverflowFlag of = 0;
651 int x0 = rect->x;
652 int y0 = rect->y;
653 int x1 = blAddOverflow(x0, w, &of);
654 int y1 = blAddOverflow(y0, h, &of);
655
656 if (BL_UNLIKELY(of))
657 return blTraceError(BL_ERROR_INVALID_VALUE);
658
659 BLBoxI box(x0, y0, x1, y1);
660 return blRegionAssignValidBoxIArray(self, &box, 1, &box);
661}
662
663BLResult blRegionAssignRectIArray(BLRegionCore* self, const BLRectI* data, size_t n) noexcept {
664 if (!n)
665 return blRegionClear(self);
666
667 size_t analysisSize;
668 uint32_t analysisStatus = blRegionAnalyzeRectIArray(data, n, &analysisSize);
669
670 if (analysisStatus >= BL_DATA_ANALYSIS_INVALID_VALUE)
671 return blTraceError(BL_ERROR_INVALID_VALUE);
672
673 if (analysisStatus == BL_DATA_ANALYSIS_NON_CONFORMING)
674 return blRegionAssignNonConformingBoxIArray<BLRectI>(self, data, n);
675 else
676 return blRegionAssignAlmostConformingBoxIArray<BLRectI>(self, data, n, analysisSize);
677}
678
679// ============================================================================
680// [BLRegion - Append]
681// ============================================================================
682
683// Get whether it is possible to append box B after box A (or merge with it).
684static BL_INLINE bool blRegionCanAppend(const BLBoxI& a, const BLBoxI& b) noexcept {
685 return (a.y0 == b.y0) & (a.y1 == b.y1) & (a.x1 <= b.x0);
686}
687
688// Internal append - The DST data must be large enough to append SRC into them.
689// This function handles possible cases that require coalescing. It first tries
690// to append the first box in SRC with the last box in DST. This is a very
691// special case used by OR and possibly non-overlapping XOR:
692//
693// 1) The first source rectangle immediately follows the last destination one.
694// 2) The first source rectangle follows the last destination band.
695//
696// 1) 2)
697// .......... ..........
698// ..DDDDDDDD ..DDDDDDDD D - Destination rectangle(srcData)
699// DDDDDDSSSS DDDD SSS
700// SSSSSSSS.. SSSSSSSS.. S - Source rectangle(srcData)
701// .......... ..........
702//
703// The function must also handle several special cases:
704//
705// ..........
706// DDDD DDDD
707// DDSS SSSS <- First Coalesce
708// SSSS SSSS <- Second coalesce
709// ..........
710static BLBoxI* blRegionAppendInternal(BLBoxI* dstStart, BLBoxI* dstData, const BLBoxI* srcData, const BLBoxI* srcEnd) noexcept {
711 BLBoxI* prevBand = dstData;
712 int y0 = srcData->y0;
713
714 if (dstData != dstStart && dstData[-1].y0 == y0) {
715 // This must be checked before calling this function.
716 int y1 = dstData[-1].y1;
717 BL_ASSERT(dstData[-1].y1 == y1);
718
719 // BLBoxI* pMark = dstData;
720
721 // Merge the last destination rectangle with the first source one? (Case 1).
722 if (dstData[-1].x1 == srcData->x0) {
723 dstData[-1].x1 = srcData->x1;
724 srcData++;
725 }
726
727 // Append the remaining part of the band.
728 while (srcData != srcEnd && srcData->y0 == y0)
729 *dstData++ = *srcData++;
730
731 // Find the beginning of the current band. It's called `prevBand` here
732 // as it will be the previous band after we handle this special case.
733 while (--prevBand != dstStart && prevBand[-1].y0 == y0)
734 continue;
735
736 // Attempt to coalesce the last two consecutive bands.
737 size_t bandSize = (size_t)(dstData - prevBand);
738 if (prevBand != dstStart && prevBand[-1].y1 == y0) {
739 size_t beforeSize = (size_t)(prevBand - dstStart);
740
741 // The size of previous band must be exactly same as `bandSize`.
742 if (beforeSize == bandSize || (beforeSize > bandSize && prevBand[bandSize - 1].y1 != y0)) {
743 if (blRegionMustCoalesce(prevBand - bandSize, prevBand, bandSize)) {
744 prevBand -= bandSize;
745 dstData -= bandSize;
746 blRegionSetBandY1(prevBand, bandSize, y1);
747 }
748 }
749 }
750
751 // If the second band of source data is consecutive we have to attempt to
752 // coalesce this one as well. Since we know the beginning of the previous
753 // band this is a bit easier than before.
754 if (srcData != srcEnd) {
755 y0 = srcData->y0;
756 if (y0 == y1) {
757 // Append the whole band, terminate at its end.
758 BLBoxI* curBand = dstData;
759 y1 = srcData->y1;
760
761 do {
762 *dstData++ = *srcData++;
763 } while (srcData != srcEnd && srcData->y0 == y0);
764
765 if ((size_t)(dstData - curBand) == bandSize) {
766 if (blRegionMustCoalesce(prevBand, curBand, bandSize)) {
767 dstData -= bandSize;
768 blRegionSetBandY1(prevBand, bandSize, y1);
769 }
770 }
771 }
772 }
773 }
774
775 // Simply append the rest of source as there is no way it would need coalescing.
776 while (srcData != srcEnd)
777 *dstData++ = *srcData++;
778
779 return dstData;
780}
781
782static BLResult blRegionAppendSelf(
783 BLRegionCore* dst,
784 const BLBoxI* sData, size_t sSize, const BLBoxI& sBoundingBox) noexcept {
785
786 BL_PROPAGATE(blRegionMakeMutableToAppend(dst, sSize));
787 BLInternalRegionImpl* dstI = blInternalCast(dst->impl);
788
789 BLBoxI* dstStart = dstI->data;
790 BLBoxI* dstData = blRegionAppendInternal(dstStart, dstStart + dstI->size, sData, sData + sSize);
791
792 dstI->size = (size_t)(dstData - dstStart);
793 dstI->boundingBox.reset(blMin(dstI->boundingBox.x0, sBoundingBox.x1), dstStart[0].y0,
794 blMax(dstI->boundingBox.x1, sBoundingBox.x1), dstData[-1].y1);
795 return BL_SUCCESS;
796}
797
798static BLResult blRegionAppendAB(
799 BLRegionCore* dst,
800 const BLBoxI* aData, size_t aSize, const BLBoxI& aBoundingBox,
801 const BLBoxI* bData, size_t bSize, const BLBoxI& bBoundingBox) noexcept {
802
803 // NOTE: The calculation cannot overflow due to the size of `BLBoxI`.
804 size_t n = aSize + bSize;
805
806 BL_PROPAGATE(blRegionMakeMutableToAssign(dst, n));
807 BLInternalRegionImpl* dstI = blInternalCast(dst->impl);
808
809 BLBoxI* dstStart = dstI->data;
810 BLBoxI* dstData = dstStart;
811
812 blRegionCopyData(dstData, aData, aSize);
813 dstData = blRegionAppendInternal(dstStart, dstData + aSize, bData, bData + bSize);
814
815 dstI->size = (size_t)(dstData - dstStart);
816 dstI->boundingBox.reset(blMin(aBoundingBox.x0, bBoundingBox.x1), dstStart[0].y0,
817 blMax(aBoundingBox.x1, bBoundingBox.x1), dstData[-1].y1);
818 return BL_SUCCESS;
819}
820
821// ============================================================================
822// [BLRegion - Intersect]
823// ============================================================================
824
825static BLResult blRegionIntersectBox(BLRegionCore* dst, const BLRegionCore* src, const BLBoxI* box) noexcept {
826 BLInternalRegionImpl* dstI = blInternalCast(dst->impl);
827 BLInternalRegionImpl* srcI = blInternalCast(src->impl);
828
829 size_t n = srcI->size;
830 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(dstI));
831
832 BLInternalRegionImpl* oldI = nullptr;
833 if ((n | immutableMsk) > dstI->capacity) {
834 oldI = dstI;
835 dstI = blRegionImplNew(blRegionFittingCapacity(n));
836
837 if (BL_UNLIKELY(!dstI))
838 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
839
840 dst->impl = dstI;
841 }
842
843 BL_ASSERT(dstI->capacity >= n);
844
845 BLBoxI* dstDataPtr = dstI->data;
846 size_t prevBandSize = SIZE_MAX;
847
848 BLBoxI* srcDataPtr = srcI->data;
849 BLBoxI* srcDataEnd = srcDataPtr + n;
850
851 int ix0 = box->x0;
852 int iy0 = box->y0;
853 int ix1 = box->x1;
854 int iy1 = box->y1;
855
856 int dstBBoxX0 = blMaxValue<int>();
857 int dstBBoxX1 = blMinValue<int>();
858
859 // Skip boxes which do not intersect with the clip-box.
860 while (srcDataPtr->y1 <= iy0) {
861 if (++srcDataPtr == srcDataEnd)
862 goto Done;
863 }
864
865 // Do the intersection part.
866 for (;;) {
867 BL_ASSERT(srcDataPtr != srcDataEnd);
868
869 int bandY0 = srcDataPtr->y0;
870 if (bandY0 >= iy1)
871 break;
872
873 int y0;
874 int y1 = 0; // Be quiet.
875 BLBoxI* dstBandPtr = dstDataPtr;
876
877 // Skip leading boxes which do not intersect with the clip-box.
878 while (srcDataPtr->x1 <= ix0) {
879 if (++srcDataPtr == srcDataEnd) goto Done;
880 if (srcDataPtr->y0 != bandY0) goto Skip;
881 }
882
883 // Do the inner part.
884 if (srcDataPtr->x0 < ix1) {
885 y0 = blMax(srcDataPtr->y0, iy0);
886 y1 = blMin(srcDataPtr->y1, iy1);
887
888 // First box.
889 BL_ASSERT(dstDataPtr < dstI->data + n);
890 dstDataPtr->reset(blMax(srcDataPtr->x0, ix0), y0, blMin(srcDataPtr->x1, ix1), y1);
891 dstDataPtr++;
892
893 if (++srcDataPtr == srcDataEnd || srcDataPtr->y0 != bandY0)
894 goto Merge;
895
896 // Inner boxes.
897 while (srcDataPtr->x1 <= ix1) {
898 BL_ASSERT(dstDataPtr < dstI->data + n);
899 BL_ASSERT(srcDataPtr->x0 >= ix0 && srcDataPtr->x1 <= ix1);
900
901 dstDataPtr->reset(srcDataPtr->x0, y0, srcDataPtr->x1, y1);
902 dstDataPtr++;
903
904 if (++srcDataPtr == srcDataEnd || srcDataPtr->y0 != bandY0)
905 goto Merge;
906 }
907
908 // Last box.
909 if (srcDataPtr->x0 < ix1) {
910 BL_ASSERT(dstDataPtr < dstI->data + n);
911 BL_ASSERT(srcDataPtr->x0 >= ix0);
912
913 dstDataPtr->reset(srcDataPtr->x0, y0, blMin(srcDataPtr->x1, ix1), y1);
914 dstDataPtr++;
915
916 if (++srcDataPtr == srcDataEnd || srcDataPtr->y0 != bandY0)
917 goto Merge;
918 }
919
920 BL_ASSERT(srcDataPtr->x0 >= ix1);
921 }
922
923 // Skip trailing boxes which do not intersect with the clip-box.
924 while (srcDataPtr->x0 >= ix1) {
925 if (++srcDataPtr == srcDataEnd || srcDataPtr->y0 != bandY0)
926 break;
927 }
928
929Merge:
930 if (dstBandPtr != dstDataPtr) {
931 dstBBoxX0 = blMin(dstBBoxX0, dstBandPtr[0].x0);
932 dstBBoxX1 = blMax(dstBBoxX1, dstDataPtr[-1].x1);
933 dstDataPtr = blRegionCoalesce(dstDataPtr, dstBandPtr, y1, &prevBandSize);
934 }
935
936Skip:
937 if (srcDataPtr == srcDataEnd)
938 break;
939 }
940
941Done:
942 n = (size_t)(dstDataPtr - dstI->data);
943 dstI->size = n;
944
945 if (!n)
946 dstI->boundingBox.reset();
947 else
948 dstI->boundingBox.reset(dstBBoxX0, dstI->data[0].y0, dstBBoxX1, dstI->data[n - 1].y1);
949
950 BL_ASSERT(blRegionImplIsValid(dstI));
951 return oldI ? blRegionImplRelease(oldI) : BL_SUCCESS;
952}
953
954// ============================================================================
955// [BLRegion - Combine]
956// ============================================================================
957
958// A helper function used by `blRegionCombineInternal()` to reallocate the impl.
959// Reallocation is not something that should happen often so it's fine that it's
960// outside of the main implementation.
961static BLInternalRegionImpl* blRegionCombineGrow(BLInternalRegionImpl* impl, BLBoxI** dstData, size_t n, bool fitOnly) noexcept {
962 size_t size = (size_t)(*dstData - impl->data);
963 size_t afterSize = size + n;
964
965 BL_ASSERT(impl->refCount == 1);
966 BL_ASSERT(size <= impl->capacity);
967
968 if (BL_UNLIKELY(afterSize > blRegionMaximumCapacity()))
969 return nullptr;
970
971 size_t capacity = fitOnly ? blRegionFittingCapacity(afterSize)
972 : blRegionGrowingCapacity(afterSize);
973 BLInternalRegionImpl* newI = blRegionImplNew(capacity);
974
975 if (BL_UNLIKELY(!newI))
976 return nullptr;
977
978 newI->size = size;
979 *dstData = newI->data + size;
980
981 blRegionCopyData(newI->data, impl->data, size);
982 blRegionImplDelete(impl);
983
984 return newI;
985}
986
987// A low-level function that performs the boolean operation of two regions,
988// Box+Region or Region+Box combinations. This function does raw processing
989// and doesn't special case anything, thus, all special cases must be dealed
990// with before.
991static BLResult blRegionCombineInternal(
992 BLRegionCore* dst,
993 const BLBoxI* aData, size_t aSize, const BLBoxI& aBoundingBox,
994 const BLBoxI* bData, size_t bSize, const BLBoxI& bBoundingBox,
995 uint32_t op, bool memOverlap) noexcept {
996
997 // Make sure the inputs are as required.
998 BL_ASSUME(op != BL_BOOLEAN_OP_COPY);
999 BL_ASSUME(op < BL_BOOLEAN_OP_COUNT);
1000 BL_ASSUME(aSize > 0);
1001 BL_ASSUME(bSize > 0);
1002
1003 // The resulting number of boxes after (A & B) can't be larger than (A + B) * 2.
1004 // However, ror other operators this value is only a hint as the output could
1005 // be greater than the estimation in some cases. Each combiner except AND checks
1006 // for availale space before each band is processed.
1007 //
1008 // NOTE: The calculation cannot overflow due to the size of `BLBoxI`.
1009 size_t n = 8 + (aSize + bSize) * 2;
1010
1011 BLInternalRegionImpl* oldI = nullptr;
1012 BLInternalRegionImpl* dstI = blInternalCast(dst->impl);
1013
1014 size_t overlapMsk = blBitMaskFromBool<size_t>(memOverlap);
1015 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(dstI));
1016
1017 if ((n | overlapMsk | immutableMsk) > dstI->capacity) {
1018 if (BL_UNLIKELY(n >= blRegionMaximumCapacity()))
1019 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
1020
1021 oldI = dstI;
1022 dstI = blRegionImplNew(n);
1023
1024 if (BL_UNLIKELY(!dstI))
1025 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
1026 }
1027
1028 BLBoxI* dstData = dstI->data;
1029 BLBoxI* dstEnd = dstData + dstI->capacity;
1030 size_t prevBandSize = SIZE_MAX;
1031
1032 int dstBBoxX0 = blMaxValue<int>();
1033 int dstBBoxX1 = blMinValue<int>();
1034
1035 const BLBoxI* aEnd = aData + aSize;
1036 const BLBoxI* bEnd = bData + bSize;
1037
1038 const BLBoxI* aBandEnd = nullptr;
1039 const BLBoxI* bBandEnd = nullptr;
1040
1041 int y0, y1;
1042
1043 #define BL_REGION_ENSURE_SPACE(N, FIT_ONLY) \
1044 do { \
1045 size_t remain = (size_t)(dstEnd - dstData); \
1046 size_t needed = (size_t)(N); \
1047 \
1048 if (BL_UNLIKELY(remain < needed)) { \
1049 BLInternalRegionImpl* newI = \
1050 blRegionCombineGrow(dstI, &dstData, needed, FIT_ONLY); \
1051 \
1052 if (BL_UNLIKELY(!newI)) \
1053 goto OutOfMemory; \
1054 \
1055 dstI = newI; \
1056 dstEnd = dstI->data + dstI->capacity; \
1057 } \
1058 } while (0)
1059
1060 switch (op) {
1061 // ------------------------------------------------------------------------
1062 // [Intersect]
1063 // ------------------------------------------------------------------------
1064
1065 case BL_BOOLEAN_OP_AND: {
1066 int yStop = blMin(aBoundingBox.y1, bBoundingBox.y1);
1067
1068 // Skip all parts which do not intersect.
1069 for (;;) {
1070 if (aData->y1 <= bData->y0) { if (++aData == aEnd) goto Done; else continue; }
1071 if (bData->y1 <= aData->y0) { if (++bData == bEnd) goto Done; else continue; }
1072 break;
1073 }
1074
1075 BL_ASSERT(aData != aEnd);
1076 BL_ASSERT(bData != bEnd);
1077
1078 aBandEnd = blRegionGetEndBand(aData, aEnd);
1079 bBandEnd = blRegionGetEndBand(bData, bEnd);
1080
1081 for (;;) {
1082 // Vertical intersection.
1083 y0 = blMax(aData->y0, bData->y0);
1084 y1 = blMin(aData->y1, bData->y1);
1085
1086 if (y0 < y1) {
1087 BLBoxI* dstDataBand = dstData;
1088 const BLBoxI* aBand = aData;
1089 const BLBoxI* bBand = bData;
1090
1091 for (;;) {
1092 // Skip boxes which do not intersect.
1093 if (aBand->x1 <= bBand->x0) { if (++aBand == aBandEnd) break; else continue; }
1094 if (bBand->x1 <= aBand->x0) { if (++bBand == bBandEnd) break; else continue; }
1095
1096 // Horizontal intersection.
1097 int x0 = blMax(aBand->x0, bBand->x0);
1098 int x1 = blMin(aBand->x1, bBand->x1);
1099
1100 BL_ASSERT(x0 < x1);
1101 BL_ASSERT(dstData != dstEnd);
1102
1103 dstData->reset(x0, y0, x1, y1);
1104 dstData++;
1105
1106 // Advance.
1107 if (aBand->x1 == x1 && ++aBand == aBandEnd) break;
1108 if (bBand->x1 == x1 && ++bBand == bBandEnd) break;
1109 }
1110
1111 // Update bounding box and coalesce.
1112 if (dstDataBand != dstData) {
1113 dstBBoxX0 = blMin(dstBBoxX0, dstDataBand[0].x0);
1114 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
1115 dstData = blRegionCoalesce(dstData, dstDataBand, y1, &prevBandSize);
1116 }
1117 }
1118
1119 // Advance A.
1120 if (aData->y1 == y1) {
1121 if ((aData = aBandEnd) == aEnd || aData->y0 >= yStop) break;
1122 aBandEnd = blRegionGetEndBand(aData, aEnd);
1123 }
1124
1125 // Advance B.
1126 if (bData->y1 == y1) {
1127 if ((bData = bBandEnd) == bEnd || bData->y0 >= yStop) break;
1128 bBandEnd = blRegionGetEndBand(bData, bEnd);
1129 }
1130 }
1131 break;
1132 }
1133
1134 // ------------------------------------------------------------------------
1135 // [Union]
1136 // ------------------------------------------------------------------------
1137
1138 case BL_BOOLEAN_OP_OR: {
1139 dstBBoxX0 = blMin(aBoundingBox.x0, bBoundingBox.x0);
1140 dstBBoxX1 = blMax(aBoundingBox.x1, bBoundingBox.x1);
1141
1142 aBandEnd = blRegionGetEndBand(aData, aEnd);
1143 bBandEnd = blRegionGetEndBand(bData, bEnd);
1144
1145 y0 = blMin(aData->y0, bData->y0);
1146 for (;;) {
1147 const BLBoxI* aBand = aData;
1148 const BLBoxI* bBand = bData;
1149
1150 BL_REGION_ENSURE_SPACE((size_t)(aBandEnd - aBand) + (size_t)(bBandEnd - bBand), false);
1151 BLBoxI* dstDataBand = dstData;
1152
1153 // Merge bands which do not intersect.
1154 if (bBand->y0 > y0) {
1155 y1 = blMin(aBand->y1, bBand->y0);
1156 do {
1157 BL_ASSERT(dstData != dstEnd);
1158 dstData->reset(aBand->x0, y0, aBand->x1, y1);
1159 dstData++;
1160 } while (++aBand != aBandEnd);
1161 goto OnUnionBandDone;
1162 }
1163
1164 if (aBand->y0 > y0) {
1165 y1 = blMin(bBand->y1, aBand->y0);
1166 do {
1167 BL_ASSERT(dstData != dstEnd);
1168 dstData->reset(bBand->x0, y0, bBand->x1, y1);
1169 dstData++;
1170 } while (++bBand != bBandEnd);
1171 goto OnUnionBandDone;
1172 }
1173
1174 // Vertical intersection of current A and B bands.
1175 y1 = blMin(aBand->y1, bBand->y1);
1176 BL_ASSERT(y0 < y1);
1177
1178 do {
1179 int x0;
1180 int x1;
1181
1182 if (aBand->x0 < bBand->x0) {
1183 x0 = aBand->x0;
1184 x1 = aBand->x1;
1185 aBand++;
1186 }
1187 else {
1188 x0 = bBand->x0;
1189 x1 = bBand->x1;
1190 bBand++;
1191 }
1192
1193 for (;;) {
1194 bool didAdvance = false;
1195
1196 while (aBand != aBandEnd && aBand->x0 <= x1) {
1197 x1 = blMax(x1, aBand->x1);
1198 aBand++;
1199 didAdvance = true;
1200 }
1201
1202 while (bBand != bBandEnd && bBand->x0 <= x1) {
1203 x1 = blMax(x1, bBand->x1);
1204 bBand++;
1205 didAdvance = true;
1206 }
1207
1208 if (!didAdvance)
1209 break;
1210 }
1211
1212 #ifdef BL_BUILD_DEBUG
1213 BL_ASSERT(dstData != dstEnd);
1214 if (dstData != dstDataBand)
1215 BL_ASSERT(dstData[-1].x1 < x0);
1216 #endif
1217
1218 dstData->reset(x0, y0, x1, y1);
1219 dstData++;
1220 } while (aBand != aBandEnd && bBand != bBandEnd);
1221
1222 // Merge boxes which do not intersect.
1223 while (aBand != aBandEnd) {
1224 #ifdef BL_BUILD_DEBUG
1225 BL_ASSERT(dstData != dstEnd);
1226 if (dstData != dstDataBand)
1227 BL_ASSERT(dstData[-1].x1 < aBand->x0);
1228 #endif
1229
1230 dstData->reset(aBand->x0, y0, aBand->x1, y1);
1231 dstData++;
1232 aBand++;
1233 }
1234
1235 while (bBand != bBandEnd) {
1236 #ifdef BL_BUILD_DEBUG
1237 BL_ASSERT(dstData != dstEnd);
1238 if (dstData != dstDataBand)
1239 BL_ASSERT(dstData[-1].x1 < bBand->x0);
1240 #endif
1241
1242 dstData->reset(bBand->x0, y0, bBand->x1, y1);
1243 dstData++;
1244 bBand++;
1245 }
1246
1247 // Coalesce.
1248OnUnionBandDone:
1249 dstData = blRegionCoalesce(dstData, dstDataBand, y1, &prevBandSize);
1250
1251 y0 = y1;
1252
1253 // Advance A.
1254 if (aData->y1 == y1) {
1255 if ((aData = aBandEnd) == aEnd) break;
1256 aBandEnd = blRegionGetEndBand(aData, aEnd);
1257 }
1258
1259 // Advance B.
1260 if (bData->y1 == y1) {
1261 if ((bData = bBandEnd) == bEnd) break;
1262 bBandEnd = blRegionGetEndBand(bData, bEnd);
1263 }
1264
1265 y0 = blMax(y0, blMin(aData->y0, bData->y0));
1266 }
1267
1268 if (aData != aEnd) goto OnMergeA;
1269 if (bData != bEnd) goto OnMergeB;
1270 break;
1271 }
1272
1273 // ------------------------------------------------------------------------
1274 // [Xor]
1275 // ------------------------------------------------------------------------
1276
1277 case BL_BOOLEAN_OP_XOR: {
1278 aBandEnd = blRegionGetEndBand(aData, aEnd);
1279 bBandEnd = blRegionGetEndBand(bData, bEnd);
1280
1281 y0 = blMin(aData->y0, bData->y0);
1282 for (;;) {
1283 const BLBoxI* aBand = aData;
1284 const BLBoxI* bBand = bData;
1285
1286 BL_REGION_ENSURE_SPACE(((size_t)(aBandEnd - aBand) + (size_t)(bBandEnd - bBand)) * 2, false);
1287 BLBoxI* dstDataBand = dstData;
1288
1289 // Merge bands which do not intersect.
1290 if (bBand->y0 > y0) {
1291 y1 = blMin(aBand->y1, bBand->y0);
1292 do {
1293 BL_ASSERT(dstData != dstEnd);
1294 dstData->reset(aBand->x0, y0, aBand->x1, y1);
1295 dstData++;
1296 } while (++aBand != aBandEnd);
1297 goto OnXorBandDone;
1298 }
1299
1300 if (aBand->y0 > y0) {
1301 y1 = blMin(bBand->y1, aBand->y0);
1302 do {
1303 BL_ASSERT(dstData != dstEnd);
1304 dstData->reset(bBand->x0, y0, bBand->x1, y1);
1305 dstData++;
1306 } while (++bBand != bBandEnd);
1307 goto OnXorBandDone;
1308 }
1309
1310 // Vertical intersection of current A and B bands.
1311 y1 = blMin(aBand->y1, bBand->y1);
1312 BL_ASSERT(y0 < y1);
1313
1314 {
1315 int pos = blMin(aBand->x0, bBand->x0);
1316 int x0;
1317 int x1;
1318
1319 for (;;) {
1320 if (aBand->x1 <= bBand->x0) {
1321 x0 = blMax(aBand->x0, pos);
1322 x1 = aBand->x1;
1323 pos = x1;
1324 goto OnXorMerge;
1325 }
1326
1327 if (bBand->x1 <= aBand->x0) {
1328 x0 = blMax(bBand->x0, pos);
1329 x1 = bBand->x1;
1330 pos = x1;
1331 goto OnXorMerge;
1332 }
1333
1334 x0 = pos;
1335 x1 = blMax(aBand->x0, bBand->x0);
1336 pos = blMin(aBand->x1, bBand->x1);
1337
1338 if (x0 >= x1)
1339 goto OnXorSkip;
1340
1341OnXorMerge:
1342 BL_ASSERT(x0 < x1);
1343 if (dstData != dstDataBand && dstData[-1].x1 == x0) {
1344 dstData[-1].x1 = x1;
1345 }
1346 else {
1347 dstData->reset(x0, y0, x1, y1);
1348 dstData++;
1349 }
1350
1351OnXorSkip:
1352 if (aBand->x1 <= pos) aBand++;
1353 if (bBand->x1 <= pos) bBand++;
1354
1355 if (aBand == aBandEnd || bBand == bBandEnd)
1356 break;
1357 pos = blMax(pos, blMin(aBand->x0, bBand->x0));
1358 }
1359
1360 // Merge boxes which do not intersect.
1361 if (aBand != aBandEnd) {
1362 x0 = blMax(aBand->x0, pos);
1363 for (;;) {
1364 x1 = aBand->x1;
1365 BL_ASSERT(x0 < x1);
1366 BL_ASSERT(dstData != dstEnd);
1367
1368 if (dstData != dstDataBand && dstData[-1].x1 == x0) {
1369 dstData[-1].x1 = x1;
1370 }
1371 else {
1372 dstData->reset(x0, y0, x1, y1);
1373 dstData++;
1374 }
1375
1376 if (++aBand == aBandEnd)
1377 break;
1378 x0 = aBand->x0;
1379 }
1380 }
1381
1382 if (bBand != bBandEnd) {
1383 x0 = blMax(bBand->x0, pos);
1384 for (;;) {
1385 x1 = bBand->x1;
1386 BL_ASSERT(x0 < x1);
1387 BL_ASSERT(dstData != dstEnd);
1388
1389 if (dstData != dstDataBand && dstData[-1].x1 == x0) {
1390 dstData[-1].x1 = x1;
1391 }
1392 else {
1393 dstData->reset(x0, y0, x1, y1);
1394 dstData++;
1395 }
1396
1397 if (++bBand == bBandEnd)
1398 break;
1399 x0 = bBand->x0;
1400 }
1401 }
1402 }
1403
1404 // Update bounding box and coalesce.
1405OnXorBandDone:
1406 if (dstDataBand != dstData) {
1407 dstBBoxX0 = blMin(dstBBoxX0, dstDataBand[0].x0);
1408 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
1409 dstData = blRegionCoalesce(dstData, dstDataBand, y1, &prevBandSize);
1410 }
1411
1412 y0 = y1;
1413
1414 // Advance A.
1415 if (aData->y1 == y1) {
1416 if ((aData = aBandEnd) == aEnd)
1417 break;
1418 aBandEnd = blRegionGetEndBand(aData, aEnd);
1419 }
1420
1421 // Advance B.
1422 if (bData->y1 == y1) {
1423 if ((bData = bBandEnd) == bEnd)
1424 break;
1425 bBandEnd = blRegionGetEndBand(bData, bEnd);
1426 }
1427
1428 y0 = blMax(y0, blMin(aData->y0, bData->y0));
1429 }
1430
1431 if (aData != aEnd) goto OnMergeA;
1432 if (bData != bEnd) goto OnMergeB;
1433 break;
1434 }
1435
1436 // ------------------------------------------------------------------------
1437 // [Subtract]
1438 // ------------------------------------------------------------------------
1439
1440 case BL_BOOLEAN_OP_SUB: {
1441 aBandEnd = blRegionGetEndBand(aData, aEnd);
1442 bBandEnd = blRegionGetEndBand(bData, bEnd);
1443
1444 y0 = blMin(aData->y0, bData->y0);
1445 for (;;) {
1446 const BLBoxI* aBand = aData;
1447 const BLBoxI* bBand = bData;
1448
1449 BL_REGION_ENSURE_SPACE(((size_t)(aBandEnd - aBand) + (size_t)(bBandEnd - bBand)) * 2, false);
1450 BLBoxI* dstDataBand = dstData;
1451
1452 // Merge (A) / Skip (B) bands which do not intersect.
1453 if (bBand->y0 > y0) {
1454 y1 = blMin(aBand->y1, bBand->y0);
1455 do {
1456 BL_ASSERT(dstData != dstEnd);
1457 dstData->reset(aBand->x0, y0, aBand->x1, y1);
1458 dstData++;
1459 } while (++aBand != aBandEnd);
1460 goto OnSubtractBandDone;
1461 }
1462
1463 if (aBand->y0 > y0) {
1464 y1 = blMin(bBand->y1, aBand->y0);
1465 goto OnSubtractBandSkip;
1466 }
1467
1468 // Vertical intersection of current A and B bands.
1469 y1 = blMin(aBand->y1, bBand->y1);
1470 BL_ASSERT(y0 < y1);
1471
1472 {
1473 int pos = aBand->x0;
1474 int sub = bBand->x0;
1475
1476 int x0;
1477 int x1;
1478
1479 for (;;) {
1480 if (aBand->x1 <= sub) {
1481 x0 = pos;
1482 x1 = aBand->x1;
1483 pos = x1;
1484
1485 if (x0 < x1)
1486 goto OnSubtractMerge;
1487 else
1488 goto OnSubtractSkip;
1489 }
1490
1491 if (aBand->x0 >= sub) {
1492 pos = bBand->x1;
1493 goto OnSubtractSkip;
1494 }
1495
1496 x0 = pos;
1497 x1 = bBand->x0;
1498 pos = bBand->x1;
1499
1500OnSubtractMerge:
1501 BL_ASSERT(x0 < x1);
1502 dstData->reset(x0, y0, x1, y1);
1503 dstData++;
1504
1505OnSubtractSkip:
1506 if (aBand->x1 <= pos) aBand++;
1507 if (bBand->x1 <= pos) bBand++;
1508
1509 if (aBand == aBandEnd || bBand == bBandEnd)
1510 break;
1511
1512 sub = bBand->x0;
1513 pos = blMax(pos, aBand->x0);
1514 }
1515
1516 // Merge boxes (A) / Ignore boxes (B) which do not intersect.
1517 while (aBand != aBandEnd) {
1518 x0 = blMax(aBand->x0, pos);
1519 x1 = aBand->x1;
1520
1521 if (x0 < x1) {
1522 BL_ASSERT(dstData != dstEnd);
1523 dstData->reset(x0, y0, x1, y1);
1524 dstData++;
1525 }
1526 aBand++;
1527 }
1528 }
1529
1530 // Update bounding box and coalesce.
1531OnSubtractBandDone:
1532 if (dstDataBand != dstData) {
1533 dstBBoxX0 = blMin(dstBBoxX0, dstDataBand[0].x0);
1534 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
1535 dstData = blRegionCoalesce(dstData, dstDataBand, y1, &prevBandSize);
1536 }
1537
1538OnSubtractBandSkip:
1539 y0 = y1;
1540
1541 // Advance A.
1542 if (aData->y1 == y1) {
1543 if ((aData = aBandEnd) == aEnd)
1544 break;
1545 aBandEnd = blRegionGetEndBand(aData, aEnd);
1546 }
1547
1548 // Advance B.
1549 if (bData->y1 == y1) {
1550 if ((bData = bBandEnd) == bEnd)
1551 break;
1552 bBandEnd = blRegionGetEndBand(bData, bEnd);
1553 }
1554
1555 y0 = blMax(y0, blMin(aData->y0, bData->y0));
1556 }
1557
1558 if (aData != aEnd)
1559 goto OnMergeA;
1560 break;
1561 }
1562
1563 default:
1564 BL_NOT_REACHED();
1565 }
1566
1567Done:
1568 n = (size_t)(dstData - dstI->data);
1569 dstI->size = n;
1570
1571 if (!n)
1572 dstI->boundingBox.reset();
1573 else
1574 dstI->boundingBox.reset(dstBBoxX0, dstI->data[0].y0, dstBBoxX1, dstData[-1].y1);
1575
1576 BL_ASSERT(blRegionImplIsValid(dstI));
1577 return oldI ? blRegionImplRelease(oldI) : BL_SUCCESS;
1578
1579OutOfMemory:
1580 dstI->boundingBox.reset();
1581 dstI->size = 0;
1582 dst->impl = dstI;
1583
1584 if (oldI) blRegionImplRelease(oldI);
1585 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
1586
1587OnMergeB:
1588 BL_ASSERT(aData == aEnd);
1589
1590 aData = bData;
1591 aEnd = bEnd;
1592 aBandEnd = bBandEnd;
1593
1594OnMergeA:
1595 BL_ASSERT(aData != aEnd);
1596 if (y0 >= aData->y1) {
1597 if ((aData = aBandEnd) == aEnd)
1598 goto Done;
1599 aBandEnd = blRegionGetEndBand(aData, aEnd);
1600 }
1601
1602 y0 = blMax(y0, aData->y0);
1603 y1 = aData->y1;
1604
1605 {
1606 BL_REGION_ENSURE_SPACE((size_t)(aEnd - aData), true);
1607 BLBoxI* dstDataBand = dstData;
1608
1609 do {
1610 BL_ASSERT(dstData != dstEnd);
1611 dstData->reset(aData->x0, y0, aData->x1, y1);
1612 dstData++;
1613 } while (++aData != aBandEnd);
1614
1615 dstBBoxX0 = blMin(dstBBoxX0, dstDataBand[0].x0);
1616 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
1617 dstData = blRegionCoalesce(dstData, dstDataBand, y1, &prevBandSize);
1618 }
1619
1620 if (aData == aEnd)
1621 goto Done;
1622
1623 if (op == BL_BOOLEAN_OP_OR) {
1624 // Special case for OR. The bounding box can be easily calculated
1625 // by using `A | B`. We don't have to do anthing else than that.
1626 do {
1627 BL_ASSERT(dstData != dstEnd);
1628 dstData->reset(aData->x0, aData->y0, aData->x1, aData->y1);
1629 dstData++;
1630 } while (++aData != aEnd);
1631 }
1632 else {
1633 do {
1634 BL_ASSERT(dstData != dstEnd);
1635 dstData->reset(aData->x0, aData->y0, aData->x1, aData->y1);
1636 dstData++;
1637
1638 dstBBoxX0 = blMin(dstBBoxX0, aData->x0);
1639 dstBBoxX1 = blMax(dstBBoxX1, aData->x1);
1640 } while (++aData != aEnd);
1641 }
1642
1643 goto Done;
1644
1645 #undef BL_REGION_ENSURE_SPACE
1646}
1647
1648BLResult blRegionCombine(BLRegionCore* self, const BLRegionCore* a, const BLRegionCore* b, uint32_t op) noexcept {
1649 const BLInternalRegionImpl* aI = blInternalCast(a->impl);
1650 const BLInternalRegionImpl* bI = blInternalCast(b->impl);
1651
1652 if (BL_UNLIKELY(op >= BL_BOOLEAN_OP_COUNT))
1653 return blTraceError(BL_ERROR_INVALID_VALUE);
1654
1655 if (BL_UNLIKELY(aI == bI)) {
1656 if (op == BL_BOOLEAN_OP_COPY || op == BL_BOOLEAN_OP_AND || op == BL_BOOLEAN_OP_OR)
1657 return blRegionAssignWeak(self, b);
1658 else
1659 return blRegionClear(self);
1660 }
1661
1662 size_t aSize = aI->size;
1663 size_t bSize = bI->size;
1664
1665 // Fast-paths that take advantage of box on any side.
1666 if (aSize <= 1) {
1667 BLBoxI aBox(aI->boundingBox);
1668 return blRegionCombineBR(self, &aBox, b, op);
1669 }
1670
1671 if (bSize <= 1) {
1672 BLBoxI bBox(bI->boundingBox);
1673 return blRegionCombineRB(self, a, &bBox, op);
1674 }
1675
1676 BL_ASSERT(aSize > 1 && bSize > 1);
1677
1678 switch (op) {
1679 case BL_BOOLEAN_OP_COPY:
1680 return blRegionAssignWeak(self, b);
1681
1682 case BL_BOOLEAN_OP_AND:
1683 if (!blOverlaps(aI->boundingBox, bI->boundingBox))
1684 return blRegionClear(self);
1685 break;
1686
1687 case BL_BOOLEAN_OP_XOR:
1688 // Check whether to use UNION instead of XOR.
1689 if (blOverlaps(aI->boundingBox, bI->boundingBox))
1690 break;
1691
1692 op = BL_BOOLEAN_OP_OR;
1693 BL_FALLTHROUGH
1694
1695 case BL_BOOLEAN_OP_OR:
1696 // Check whether to use APPEND instead of OR. This is a special case, but
1697 // happens often when the region is constructed from many boxes using OR.
1698 if (aI->boundingBox.y1 <= bI->boundingBox.y0 || blRegionCanAppend(aI->data[aSize - 1], bI->data[0])) {
1699 if (self->impl == aI)
1700 return blRegionAppendSelf(self, bI->data, bSize, bI->boundingBox);
1701
1702 if (self->impl == bI) {
1703 BLRegion bTmp(*blDownCast(b));
1704 return blRegionAppendAB(self, aI->data, aSize, aI->boundingBox, bI->data, bSize, bI->boundingBox);
1705 }
1706
1707 return blRegionAppendAB(self, aI->data, aSize, aI->boundingBox, bI->data, bSize, bI->boundingBox);
1708 }
1709
1710 if (bI->boundingBox.y1 <= aI->boundingBox.y0 || blRegionCanAppend(bI->data[bSize - 1], aI->data[0])) {
1711 if (self->impl == bI)
1712 return blRegionAppendSelf(self, aI->data, aSize, aI->boundingBox);
1713
1714 if (self->impl == aI) {
1715 BLRegion aTmp(*blDownCast(a));
1716 return blRegionAppendAB(self, bI->data, bSize, bI->boundingBox, aI->data, aSize, aI->boundingBox);
1717 }
1718
1719 return blRegionAppendAB(self, bI->data, bSize, bI->boundingBox, aI->data, aSize, aI->boundingBox);
1720 }
1721 break;
1722
1723 case BL_BOOLEAN_OP_SUB:
1724 if (!blOverlaps(aI->boundingBox, bI->boundingBox))
1725 return blRegionAssignWeak(self, a);
1726 break;
1727 }
1728
1729 return blRegionCombineInternal(self, aI->data, aSize, aI->boundingBox, bI->data, bSize, bI->boundingBox, op, self->impl == aI || self->impl == bI);
1730}
1731
1732BLResult blRegionCombineRB(BLRegionCore* self, const BLRegionCore* a, const BLBoxI* b, uint32_t op) noexcept {
1733 BLInternalRegionImpl* aI = blInternalCast(a->impl);
1734
1735 // Fast-path.
1736 if (aI->size <= 1)
1737 return blRegionCombineBB(self, &aI->boundingBox, b, op);
1738
1739 BLBoxI bBox(*b);
1740 bool bIsValid = blIsValid(bBox);
1741
1742 switch (op) {
1743 case BL_BOOLEAN_OP_COPY:
1744 if (!bIsValid)
1745 return blRegionClear(self);
1746 else
1747 return blRegionAssignBoxI(self, &bBox); // DST <- B.
1748
1749 case BL_BOOLEAN_OP_AND:
1750 if (!bIsValid || !blOverlaps(bBox, aI->boundingBox))
1751 return blRegionClear(self);
1752
1753 if (blSubsumes(bBox, aI->boundingBox))
1754 return blRegionAssignWeak(self, a);
1755
1756 return blRegionIntersectBox(self, a, &bBox);
1757
1758 case BL_BOOLEAN_OP_OR:
1759 case BL_BOOLEAN_OP_XOR:
1760 if (!bIsValid)
1761 return blRegionAssignWeak(self, a);
1762
1763 if (aI->boundingBox.y1 <= bBox.y0 || blRegionCanAppend(aI->data[aI->size - 1], bBox)) {
1764 if (self->impl == aI)
1765 return blRegionAppendSelf(self, &bBox, 1, bBox);
1766 else
1767 return blRegionAppendAB(self, aI->data, aI->size, aI->boundingBox, &bBox, 1, bBox);
1768 }
1769 break;
1770
1771 case BL_BOOLEAN_OP_SUB:
1772 if (!bIsValid || !blOverlaps(bBox, aI->boundingBox))
1773 return blRegionAssignWeak(self, a);
1774 break;
1775
1776 default:
1777 return blTraceError(BL_ERROR_INVALID_VALUE);
1778 }
1779
1780 return blRegionCombineInternal(self, aI->data, aI->size, aI->boundingBox, &bBox, 1, bBox, op, self->impl == aI);
1781}
1782
1783BLResult blRegionCombineBR(BLRegionCore* self, const BLBoxI* a, const BLRegionCore* b, uint32_t op) noexcept {
1784 const BLInternalRegionImpl* bI = blInternalCast(b->impl);
1785
1786 // Box-Box is faster than Box-Region so use this fast-path when possible.
1787 if (bI->size <= 1) {
1788 BLBoxI bBox(bI->boundingBox);
1789 return blRegionCombineBB(self, a, &bBox, op);
1790 }
1791
1792 BLBoxI aBox(*a);
1793 bool aIsValid = blIsValid(aBox);
1794
1795 switch (op) {
1796 case BL_BOOLEAN_OP_COPY:
1797 return blRegionAssignWeak(self, b);
1798
1799 case BL_BOOLEAN_OP_AND:
1800 if (!aIsValid || !blOverlaps(aBox, bI->boundingBox))
1801 return blRegionClear(self);
1802
1803 if (blSubsumes(aBox, bI->boundingBox))
1804 return blRegionAssignWeak(self, b);
1805
1806 return blRegionIntersectBox(self, b, &aBox);
1807
1808 case BL_BOOLEAN_OP_OR:
1809 if (!aIsValid)
1810 return blRegionAssignWeak(self, b);
1811 break;
1812
1813 case BL_BOOLEAN_OP_XOR:
1814 if (!aIsValid)
1815 return blRegionAssignWeak(self, b);
1816
1817 if (!blOverlaps(aBox, bI->boundingBox))
1818 op = BL_BOOLEAN_OP_OR;
1819 break;
1820
1821 case BL_BOOLEAN_OP_SUB:
1822 if (!aIsValid)
1823 return blRegionClear(self);
1824
1825 if (!blOverlaps(aBox, bI->boundingBox))
1826 return blRegionAssignBoxI(self, &aBox);
1827 break;
1828
1829 default:
1830 return blTraceError(BL_ERROR_INVALID_VALUE);
1831 }
1832
1833 return blRegionCombineInternal(self, &aBox, 1, aBox, bI->data, bI->size, bI->boundingBox, op, self->impl == bI);
1834}
1835
1836BLResult blRegionCombineBB(BLRegionCore* self, const BLBoxI* a, const BLBoxI* b, uint32_t op) noexcept {
1837 if (BL_UNLIKELY(op >= BL_BOOLEAN_OP_COUNT))
1838 return blTraceError(BL_ERROR_INVALID_VALUE);
1839
1840 // There are several combinations of A and B.
1841 //
1842 // Special cases:
1843 //
1844 // 1) Both boxes are invalid.
1845 // 2) Only one box is valid (one invalid).
1846 // 3) Boxes do not intersect, but they are continuous on the y-axis (In some
1847 // cases this can be extended that boxes intersect, but their left and
1848 // right coordinates are shared).
1849 // 4) Boxes do not intersect, but they are continuous on the x-axis (In some
1850 // cases this can be extended that boxes intersect, but their top and
1851 // bottom coordinates are shared).
1852 //
1853 // Common cases:
1854 //
1855 // 5) Boxes do not intersect and do not share any area on the y-axis.
1856 // 6) Boxes do not intersect, but they share any area on the y-axis.
1857 // 7) Boxes intersect.
1858 // 8) One box overlaps the other.
1859 //
1860 // +--------------+--------------+--------------+--------------+
1861 // | 1) | 2) | 3) | 4) |
1862 // | | | | |
1863 // | | +--------+ | +--------+ | +----+----+ |
1864 // | | | | | | | | | | | |
1865 // | | | | | | | | | | | |
1866 // | | | | | +--------+ | | | | |
1867 // | | | | | | | | | | | |
1868 // | | | | | | | | | | | |
1869 // | | | | | | | | | | | |
1870 // | | +--------+ | +--------+ | +----+----+ |
1871 // | | | | |
1872 // +--------------+--------------+--------------+--------------+
1873 // | 5) | 6) | 7) | 8) |
1874 // | | | | |
1875 // | +----+ | +---+ | +-----+ | +--------+ |
1876 // | | | | | | | | | | | | |
1877 // | | | | | | +----+ | | +--+--+ | | +--+ | |
1878 // | +----+ | +---+ | | | | | | | | | | | | |
1879 // | | | | | +--+--+ | | | +--+ | |
1880 // | +----+ | +----+ | | | | | | |
1881 // | | | | | +-----+ | +--------+ |
1882 // | | | | | | |
1883 // | +----+ | | | |
1884 // +--------------+--------------+--------------+--------------+
1885
1886 BLBoxI box[4]; // Maximum number of generated boxes by any operator is 4.
1887 size_t n = 1; // We assume 1 box by default, overriden when needed.
1888
1889 // COPY & AND & SUB Operators
1890 // --------------------------
1891
1892 if (op == BL_BOOLEAN_OP_COPY) {
1893Copy:
1894 if (!blIsValid(*b))
1895 goto Clear;
1896
1897 box[0] = *b;
1898 goto Done;
1899 }
1900
1901 if (op == BL_BOOLEAN_OP_AND) {
1902 if (!blIntersectBoxes(box[0], *a, *b))
1903 goto Clear; // Case 1, 2, 3, 4, 5, 6.
1904 else
1905 goto Done; // Case 7, 8 (has intersection).
1906 }
1907
1908 // From now we assume A to be the output in case of bailing out early.
1909 box[0] = *a;
1910
1911 if (op == BL_BOOLEAN_OP_SUB) {
1912 // case 1, 2.
1913 if (!blIsValid(*a)) goto Clear;
1914 if (!blIsValid(*b)) goto Done; // Copy A.
1915
1916 // Case 3, 4, 5, 6.
1917 // If the input boxes A and B do not intersect then the result is A.
1918 if (!blIntersectBoxes(box[3], *a, *b))
1919 goto Done;
1920
1921 // Case 7, 8.
1922
1923 // Top part.
1924 n = size_t(a->y0 < b->y0);
1925 box[0].reset(a->x0, a->y0, a->x1, box[3].y0);
1926
1927 // Inner part.
1928 if (a->x0 < box[3].x0) box[n++].reset(a->x0, box[3].y0, box[3].x0, box[3].y1);
1929 if (box[3].x1 < a->x1) box[n++].reset(box[3].x1, box[3].y0, a->x1, box[3].y1);
1930
1931 // Bottom part.
1932 if (a->y1 > box[3].y1) box[n++].reset(a->x0, box[3].y1, a->x1, a->y1);
1933
1934 if (!n)
1935 goto Clear;
1936 else
1937 goto Done;
1938 }
1939
1940 // OR & XOR Operators
1941 // ------------------
1942
1943 // The order of boxes doesn't matter for next operators, so make the upper first.
1944 if (a->y0 > b->y0)
1945 std::swap(a, b);
1946
1947 // Case 1, 2.
1948 if (!blIsValid(*a)) goto Copy; // Copy B (if valid).
1949 if (!blIsValid(*b)) goto Done; // Copy A.
1950
1951 if (op == BL_BOOLEAN_OP_XOR) {
1952 if (blIntersectBoxes(box[3], *a, *b)) {
1953 // Case 7, 8.
1954
1955 // Top part.
1956 n = size_t(a->y0 < b->y0);
1957 box[0].reset(a->x0, a->y0, a->x1, b->y0);
1958
1959 // Inner part.
1960 if (a->x0 > b->x0)
1961 std::swap(a, b);
1962
1963 if (a->x0 < box[3].x0) box[n++].reset(a->x0, box[3].y0, box[3].x0, box[3].y1);
1964 if (b->x1 > box[3].x1) box[n++].reset(box[3].x1, box[3].y0, b->x1, box[3].y1);
1965
1966 // Bottom part.
1967 if (a->y1 > b->y1) std::swap(a, b);
1968 if (b->y1 > box[3].y1) box[n++].reset(b->x0, box[3].y1, b->x1, b->y1);
1969
1970 if (!n)
1971 goto Clear;
1972 else
1973 goto Done;
1974 }
1975 else {
1976 // Case 3, 4, 5, 6.
1977 // If the input boxes A and B do not intersect then we fall to OR operator.
1978 }
1979 }
1980
1981 // OR or non-intersecting XOR:
1982 {
1983 if (a->y1 <= b->y0) {
1984 // Case 3, 5.
1985 box[0] = *a;
1986 box[1] = *b;
1987 n = 2;
1988
1989 // Coalesce (Case 3).
1990 if ((box[0].y1 == box[1].y0) & (box[0].x0 == box[1].x0) & (box[0].x1 == box[1].x1)) {
1991 box[0].y1 = box[1].y1;
1992 n = 1;
1993 }
1994
1995 goto Done;
1996 }
1997
1998 if (a->y0 == b->y0 && a->y1 == b->y1) {
1999 // Case 4 - with addition that rectangles can intersect.
2000 // - with addition that rectangles do not need to be continuous on the x-axis.
2001 box[0].y0 = a->y0;
2002 box[0].y1 = a->y1;
2003
2004 if (a->x0 > b->x0)
2005 std::swap(a, b);
2006
2007 box[0].x0 = a->x0;
2008 box[0].x1 = a->x1;
2009
2010 // Intersects or continuous.
2011 if (b->x0 <= a->x1) {
2012 if (b->x1 > a->x1)
2013 box[0].x1 = b->x1;
2014 n = 1;
2015 }
2016 else {
2017 box[1].reset(b->x0, box[0].y0, b->x1, box[0].y1);
2018 n = 2;
2019 }
2020 }
2021 else {
2022 // Case 6, 7, 8.
2023 BL_ASSERT(b->y0 < a->y1);
2024
2025 // Top part.
2026 n = size_t(a->y0 < b->y0);
2027 box[0].reset(a->x0, a->y0, a->x1, b->y0);
2028
2029 // Inner part.
2030 int iy0 = b->y0;
2031 int iy1 = blMin(a->y1, b->y1);
2032
2033 if (a->x0 > b->x0)
2034 std::swap(a, b);
2035
2036 int ix0 = blMax(a->x0, b->x0);
2037 int ix1 = blMin(a->x1, b->x1);
2038
2039 if (ix0 > ix1) {
2040 box[n + 0].reset(a->x0, iy0, a->x1, iy1);
2041 box[n + 1].reset(b->x0, iy0, b->x1, iy1);
2042 n += 2;
2043 }
2044 else {
2045 BL_ASSERT(a->x1 >= ix0 && b->x0 <= ix1);
2046
2047 // If the A or B subsumes the intersection area, extend also the iy1
2048 // and skip the bottom part (we append it).
2049 if (a->x0 <= ix0 && a->x1 >= ix1 && iy1 < a->y1) iy1 = a->y1;
2050 if (b->x0 <= ix0 && b->x1 >= ix1 && iy1 < b->y1) iy1 = b->y1;
2051 box[n].reset(a->x0, iy0, blMax(a->x1, b->x1), iy1);
2052
2053 // Coalesce.
2054 if (n == 1 && box[0].x0 == box[1].x0 && box[0].x1 == box[1].x1)
2055 box[0].y1 = box[1].y1;
2056 else
2057 n++;
2058 }
2059
2060 // Bottom part.
2061 if (a->y1 > iy1) {
2062 box[n].reset(a->x0, iy1, a->x1, a->y1);
2063 goto UnionLastCoalesce;
2064 }
2065 else if (b->y1 > iy1) {
2066 box[n].reset(b->x0, iy1, b->x1, b->y1);
2067UnionLastCoalesce:
2068 if (n == 1 && box[0].x0 == box[1].x0 && box[0].x1 == box[1].x1)
2069 box[0].y1 = box[1].y1;
2070 else
2071 n++;
2072 }
2073 }
2074
2075 goto Done;
2076 }
2077
2078Clear:
2079 return blRegionClear(self);
2080
2081Done:
2082 BL_ASSUME(n > 0);
2083 return blRegionAssignValidBoxIArray(self, box, n);
2084}
2085
2086// ============================================================================
2087// [BLRegion - Translate]
2088// ============================================================================
2089
2090BLResult blRegionTranslate(BLRegionCore* self, const BLRegionCore* r, const BLPointI* pt) noexcept {
2091 BLInternalRegionImpl* dstI = blInternalCast(self->impl);
2092 BLInternalRegionImpl* srcI = blInternalCast(r->impl);
2093
2094 int tx = pt->x;
2095 int ty = pt->y;
2096
2097 if ((tx | ty) == 0)
2098 return blRegionAssignWeak(self, r);
2099
2100 size_t n = srcI->size;
2101 if (!n)
2102 return blRegionClear(self);
2103
2104 // If the translation cause arithmetic overflow then we first clip the input
2105 // region into a safe boundary which might be translated without overflow.
2106 BLOverflowFlag of = 0;
2107 BLBoxI bbox(blAddOverflow(srcI->boundingBox.x0, tx, &of),
2108 blAddOverflow(srcI->boundingBox.y0, ty, &of),
2109 blAddOverflow(srcI->boundingBox.x1, tx, &of),
2110 blAddOverflow(srcI->boundingBox.y1, ty, &of));
2111 if (BL_UNLIKELY(of))
2112 return blRegionTranslateAndClip(self, r, pt, &blRegionLargestBoxI);
2113
2114 BLInternalRegionImpl* oldI = nullptr;
2115 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(dstI));
2116
2117 if ((n | immutableMsk) > dstI->capacity) {
2118 oldI = dstI;
2119 dstI = blRegionImplNew(blRegionFittingCapacity(n));
2120
2121 if (BL_UNLIKELY(!dstI))
2122 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
2123
2124 self->impl = dstI;
2125 }
2126
2127 dstI->size = n;
2128 dstI->boundingBox = bbox;
2129
2130 BLBoxI* dstData = dstI->data;
2131 BLBoxI* srcData = srcI->data;
2132
2133 for (size_t i = 0; i < n; i++)
2134 dstData[i].reset(srcData[i].x0 + tx, srcData[i].y0 + ty, srcData[i].x1 + tx, srcData[i].y1 + ty);
2135
2136 BL_ASSERT(blRegionImplIsValid(dstI));
2137 return oldI ? blRegionImplRelease(oldI) : BL_SUCCESS;
2138}
2139
2140BLResult blRegionTranslateAndClip(BLRegionCore* self, const BLRegionCore* r, const BLPointI* pt, const BLBoxI* clipBox) noexcept {
2141 BLInternalRegionImpl* dstI = blInternalCast(self->impl);
2142 BLInternalRegionImpl* srcI = blInternalCast(r->impl);
2143
2144 size_t n = srcI->size;
2145 if (!n || !blIsValid(*clipBox))
2146 return blRegionClear(self);
2147
2148 int tx = pt->x;
2149 int ty = pt->y;
2150
2151 // Use faster `blRegionIntersectBox()` in case that there is no translation.
2152 if ((tx | ty) == 0)
2153 return blRegionIntersectBox(self, r, clipBox);
2154
2155 int cx0 = clipBox->x0;
2156 int cy0 = clipBox->y0;
2157 int cx1 = clipBox->x1;
2158 int cy1 = clipBox->y1;
2159
2160 // This function is possibly called also by `blRegionTranslate()` in case that
2161 // the translation would overflow. We adjust the given clipBox in a way so it
2162 // would never overflow and then pre-translate it so we can first clip and then
2163 // translate safely.
2164 if (tx < 0) {
2165 cx0 = blMin(cx0, blMaxValue<int>() + tx);
2166 cx1 = blMin(cx1, blMaxValue<int>() + tx);
2167 }
2168 else if (tx > 0) {
2169 cx0 = blMax(cx0, blMinValue<int>() + tx);
2170 cx1 = blMax(cx1, blMinValue<int>() + tx);
2171 }
2172
2173 if (ty < 0) {
2174 cy0 = blMin(cy0, blMaxValue<int>() + ty);
2175 cy1 = blMin(cy1, blMaxValue<int>() + ty);
2176 }
2177 else if (ty > 0) {
2178 cy0 = blMax(cy0, blMinValue<int>() + ty);
2179 cy1 = blMax(cy1, blMinValue<int>() + ty);
2180 }
2181
2182 // Pre-translate clipBox.
2183 cx0 -= tx;
2184 cy0 -= ty;
2185 cx1 -= tx;
2186 cy1 -= ty;
2187
2188 if (cx0 >= cx1 || cy0 >= cy1)
2189 return blRegionClear(self);
2190
2191 BLBoxI* srcData = srcI->data;
2192 BLBoxI* srcEnd = srcData + n;
2193
2194 // Skip boxes which do not intersect with `clipBox`. We do it here as we can
2195 // change the size requirements of the new region if we skip some boxes here.
2196 while (srcData->y1 <= cy0)
2197 if (++srcData == srcEnd)
2198 return blRegionClear(self);
2199
2200 while (srcEnd[-1].y0 >= cy1)
2201 if (--srcEnd == srcData)
2202 return blRegionClear(self);
2203
2204 n = (size_t)(srcEnd - srcData);
2205
2206 // Make sure there is enough space in the destination region.
2207 BLInternalRegionImpl* oldI = nullptr;
2208 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(dstI));
2209
2210 if ((n | immutableMsk) > dstI->capacity) {
2211 oldI = dstI;
2212 dstI = blRegionImplNew(blRegionFittingCapacity(n));
2213
2214 if (BL_UNLIKELY(!dstI))
2215 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
2216
2217 self->impl = dstI;
2218 }
2219
2220 BLBoxI* dstData = dstI->data;
2221 size_t prevBandSize = SIZE_MAX;
2222
2223 int dstBBoxX0 = blMaxValue<int>();
2224 int dstBBoxX1 = blMinValue<int>();
2225
2226 // Do the intersection part.
2227 for (;;) {
2228 BL_ASSERT(srcData != srcEnd);
2229 if (srcData->y0 >= cy1)
2230 break;
2231
2232 int y0;
2233 int y1 = 0; // Be quiet.
2234 int bandY0 = srcData->y0;
2235
2236 // Skip leading boxes which do not intersect with `clipBox`.
2237 if (srcData->x1 <= cx0) {
2238 do {
2239 if (++srcData == srcEnd)
2240 goto Done;
2241 } while (srcData->x1 <= cx0);
2242
2243 if (srcData->y0 != bandY0)
2244 continue;
2245 }
2246
2247 // Do the inner part.
2248 if (srcData->x0 < cx1) {
2249 BLBoxI* dstCurBand = dstData;
2250 y0 = blMax(srcData->y0, cy0) + ty;
2251 y1 = blMin(srcData->y1, cy1) + ty;
2252
2253 // First box (could clip).
2254 BL_ASSERT(dstData != dstI->data + dstI->capacity);
2255 dstData->reset(blMax(srcData->x0, cx0) + tx, y0, blMin(srcData->x1, cx1) + tx, y1);
2256 dstData++;
2257
2258 if (++srcData == srcEnd || srcData->y0 != bandY0)
2259 goto EndBand;
2260
2261 // Inner boxes (won't clip).
2262 while (srcData->x1 <= cx1) {
2263 BL_ASSERT(dstData != dstI->data + dstI->capacity);
2264 BL_ASSERT(srcData->x0 >= cx0 && srcData->x1 <= cx1);
2265
2266 dstData->reset(srcData->x0 + tx, y0, srcData->x1 + tx, y1);
2267 dstData++;
2268
2269 if (++srcData == srcEnd || srcData->y0 != bandY0)
2270 goto EndBand;
2271 }
2272
2273 // Last box (could clip).
2274 if (srcData->x0 < cx1) {
2275 BL_ASSERT(dstData != dstI->data + dstI->capacity);
2276 BL_ASSERT(srcData->x0 >= cx0);
2277
2278 dstData->reset(srcData->x0 + tx, y0, blMin(srcData->x1, cx1) + tx, y1);
2279 dstData++;
2280
2281 if (++srcData == srcEnd || srcData->y0 != bandY0)
2282 goto EndBand;
2283 }
2284
2285 BL_ASSERT(srcData->x0 >= cx1);
2286
2287EndBand:
2288 dstBBoxX0 = blMin(dstBBoxX0, dstCurBand[0].x0);
2289 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
2290 dstData = blRegionCoalesce(dstData, dstCurBand, y1, &prevBandSize);
2291
2292 if (srcData == srcEnd)
2293 break;
2294 }
2295 else {
2296 // Skip trailing boxes which do not intersect with `clipBox`.
2297 while (srcData->x0 >= cx1)
2298 if (++srcData == srcEnd)
2299 goto Done;
2300 }
2301 }
2302
2303Done:
2304 n = (size_t)(dstData - dstI->data);
2305 dstI->size = n;
2306
2307 if (!n)
2308 dstI->boundingBox.reset();
2309 else
2310 dstI->boundingBox.reset(dstBBoxX0, dstI->data[0].y0, dstBBoxX1, dstData[-1].y1);
2311
2312 BL_ASSERT(blRegionImplIsValid(dstI));
2313 return oldI ? blRegionImplRelease(oldI) : BL_SUCCESS;
2314}
2315
2316// ============================================================================
2317// [BLRegion - Intersect]
2318// ============================================================================
2319
2320BLResult blRegionIntersectAndClip(BLRegionCore* self, const BLRegionCore* a, const BLRegionCore* b, const BLBoxI* clipBox) noexcept {
2321 const BLInternalRegionImpl* aI = blInternalCast(a->impl);
2322 const BLInternalRegionImpl* bI = blInternalCast(b->impl);
2323
2324 int cx0 = blMax(clipBox->x0, aI->boundingBox.x0, bI->boundingBox.x0);
2325 int cy0 = blMax(clipBox->y0, aI->boundingBox.y0, bI->boundingBox.y0);
2326 int cx1 = blMin(clipBox->x1, aI->boundingBox.x1, bI->boundingBox.x1);
2327 int cy1 = blMin(clipBox->y1, aI->boundingBox.y1, bI->boundingBox.y1);
2328
2329 // This would handle empty `a` or `b`, non-intersecting regions, and invalid
2330 // `clipBox` as well.
2331 if ((cx0 >= cx1) | (cy0 >= cy1))
2332 return blRegionClear(self);
2333
2334 size_t aSize = aI->size;
2335 size_t bSize = bI->size;
2336
2337 if ((aSize == 1) | (bSize == 1)) {
2338 BLBoxI newClipBox(cx0, cy0, cx1, cy1);
2339 if (aSize != 1) return blRegionIntersectBox(self, a, &newClipBox);
2340 if (bSize != 1) return blRegionIntersectBox(self, b, &newClipBox);
2341 return blRegionAssignBoxI(self, &newClipBox);
2342 }
2343
2344 // These define input regions [aData:aEnd] and [bData:bEnd].
2345 const BLBoxI* aData = aI->data;
2346 const BLBoxI* bData = bI->data;
2347
2348 const BLBoxI* aEnd = aData + aSize;
2349 const BLBoxI* bEnd = bData + bSize;
2350
2351 // Skip all parts which do not intersect.
2352 while (aData->y0 <= cy0) { if (++aData == aEnd) return blRegionClear(self); }
2353 while (bData->y0 <= cy0) { if (++bData == bEnd) return blRegionClear(self); }
2354
2355 for (;;) {
2356 bool cont = false;
2357
2358 while (aData->y1 <= bData->y0) { cont = true; if (++aData == aEnd) return blRegionClear(self); }
2359 while (bData->y1 <= aData->y0) { cont = true; if (++bData == bEnd) return blRegionClear(self); }
2360
2361 if (cont)
2362 continue;
2363
2364 while ((aData->x1 <= cx0) | (aData->x0 >= cx1)) { cont = true; if (++aData == aEnd) return blRegionClear(self); }
2365 while ((bData->x1 <= cx0) | (bData->x0 >= cx1)) { cont = true; if (++bData == bEnd) return blRegionClear(self); }
2366
2367 if (!cont)
2368 break;
2369 }
2370
2371 if (aData->y0 >= cy1 || bData->y0 >= cy1)
2372 return blRegionClear(self);
2373
2374 // If we are here it means there are still some `a` and `b` boxes left.
2375 BL_ASSERT(aData != aEnd);
2376 BL_ASSERT(bData != bEnd);
2377
2378 // Update aSize and bSize so the estimated size is closer to the result.
2379 aSize = (size_t)(aEnd - aData);
2380 bSize = (size_t)(bEnd - bData);
2381
2382 // The maximum number of boxes this operation can generate is (A + B) * 2.
2383 //
2384 // NOTE: The calculation cannot overflow due to the size of `BLBoxI`.
2385 size_t n = (aSize + bSize) * 2;
2386
2387 BLInternalRegionImpl* oldI = nullptr;
2388 BLInternalRegionImpl* dstI = blInternalCast(self->impl);
2389
2390 size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(dstI));
2391 if ((dstI == aI) | (dstI == bI) | ((n | immutableMsk) > dstI->capacity)) {
2392 oldI = dstI;
2393 dstI = blRegionImplNew(n);
2394
2395 if (BL_UNLIKELY(!dstI))
2396 return blTraceError(BL_ERROR_OUT_OF_MEMORY);
2397 }
2398
2399 BLBoxI* dstData = dstI->data;
2400 size_t prevBandSize = SIZE_MAX;
2401
2402 const BLBoxI* aBandEnd = blRegionGetEndBand(aData, aEnd);
2403 const BLBoxI* bBandEnd = blRegionGetEndBand(bData, bEnd);
2404
2405 int dstBBoxX0 = blMaxValue<int>();
2406 int dstBBoxX1 = blMinValue<int>();
2407
2408 for (;;) {
2409 int ym = blMin(aData->y1, bData->y1);
2410
2411 // Vertical intersection of current A and B bands.
2412 int y0 = blMax(aData->y0, blMax(bData->y0, cy0));
2413 int y1 = blMin(cy1, ym);
2414
2415 if (y0 < y1) {
2416 const BLBoxI* aBand = aData;
2417 const BLBoxI* bBand = bData;
2418 BLBoxI* dstCurBand = dstData;
2419
2420 for (;;) {
2421 // Skip boxes which do not intersect.
2422 if (aBand->x1 <= bBand->x0) { if (++aBand == aBandEnd) goto EndBand; else continue; }
2423 if (bBand->x1 <= aBand->x0) { if (++bBand == bBandEnd) goto EndBand; else continue; }
2424
2425 // Horizontal intersection of current A and B boxes.
2426 int x0 = blMax(aBand->x0, bBand->x0, cx0);
2427 int xm = blMin(aBand->x1, bBand->x1);
2428 int x1 = blMin(cx1, xm);
2429
2430 if (x0 < x1) {
2431 BL_ASSERT(dstData != dstI->data + dstI->capacity);
2432 dstData->reset(x0, y0, x1, y1);
2433 dstData++;
2434 }
2435
2436 // Advance.
2437 if (aBand->x1 == xm && (++aBand == aBandEnd || aBand->x0 >= cx1)) break;
2438 if (bBand->x1 == xm && (++bBand == bBandEnd || bBand->x0 >= cx1)) break;
2439 }
2440
2441 // Update bounding box and coalesce.
2442EndBand:
2443 if (dstCurBand != dstData) {
2444 dstBBoxX0 = blMin(dstBBoxX0, dstCurBand[0].x0);
2445 dstBBoxX1 = blMax(dstBBoxX1, dstData[-1].x1);
2446 dstData = blRegionCoalesce(dstData, dstCurBand, y1, &prevBandSize);
2447 }
2448 }
2449
2450 // Advance A.
2451 if (aData->y1 == ym) {
2452 aData = aBandEnd;
2453 if (aData == aEnd || aData->y0 >= cy1)
2454 break;
2455
2456 while (aData->x1 <= cx0 || aData->x0 >= cx1)
2457 if (++aData == aEnd)
2458 goto Done;
2459
2460 aBandEnd = blRegionGetEndBand(aData, aEnd);
2461 }
2462
2463 // Advance B.
2464 if (bData->y1 == ym) {
2465 bData = bBandEnd;
2466 if (bData == bEnd || bData->y0 >= cy1)
2467 break;
2468
2469 while (bData->x1 <= cx0 || bData->x0 >= cx1)
2470 if (++bData == bEnd)
2471 goto Done;
2472
2473 bBandEnd = blRegionGetEndBand(bData, bEnd);
2474 }
2475 }
2476
2477Done:
2478 n = (size_t)(dstData - dstI->data);
2479 dstI->size = n;
2480
2481 if (!n)
2482 dstI->boundingBox.reset();
2483 else
2484 dstI->boundingBox.reset(dstBBoxX0, dstI->data[0].y0, dstBBoxX1, dstData[-1].y1);
2485
2486 BL_ASSERT(blRegionImplIsValid(dstI));
2487 return oldI ? blRegionImplRelease(oldI) : BL_SUCCESS;
2488}
2489
2490// ============================================================================
2491// [BLRegion - Equals]
2492// ============================================================================
2493
2494bool blRegionEquals(const BLRegionCore* a, const BLRegionCore* b) noexcept {
2495 const BLInternalRegionImpl* aI = blInternalCast(a->impl);
2496 const BLInternalRegionImpl* bI = blInternalCast(b->impl);
2497
2498 size_t size = aI->size;
2499
2500 if (aI == bI)
2501 return true;
2502
2503 if (size != bI->size || aI->boundingBox != bI->boundingBox)
2504 return false;
2505
2506 return memcmp(aI->data, bI->data, size * sizeof(BLBoxI)) == 0;
2507}
2508
2509// ============================================================================
2510// [BLRegion - Type]
2511// ============================================================================
2512
2513uint32_t blRegionGetType(const BLRegionCore* self) noexcept {
2514 return uint32_t(blMin<size_t>(self->impl->size, BL_REGION_TYPE_COMPLEX));
2515}
2516
2517// ============================================================================
2518// [BLRegion - HitTest]
2519// ============================================================================
2520
2521uint32_t blRegionHitTest(const BLRegionCore* self, const BLPointI* pt) noexcept {
2522 const BLInternalRegionImpl* selfI = blInternalCast(self->impl);
2523
2524 const BLBoxI* data = selfI->data;
2525 size_t n = selfI->size;
2526
2527 BLRegionXYMatcher m(pt->x, pt->y);
2528 if (!selfI->boundingBox.contains(m.x, m.y))
2529 return BL_HIT_TEST_OUT;
2530
2531 // If the bounding-box check passed the size MUST be greater than zero.
2532 BL_ASSUME(n > 0);
2533
2534 size_t i = blBinarySearchClosestFirst(data, n, m);
2535 return data[i].contains(m.x, m.y) ? BL_HIT_TEST_IN : BL_HIT_TEST_OUT;
2536}
2537
2538uint32_t blRegionHitTestBoxI(const BLRegionCore* self, const BLBoxI* box) noexcept {
2539 const BLInternalRegionImpl* selfI = blInternalCast(self->impl);
2540
2541 const BLBoxI* data = selfI->data;
2542 size_t n = selfI->size;
2543
2544 if (!blIsValid(*box))
2545 return BL_HIT_TEST_INVALID;
2546
2547 int bx0 = box->x0;
2548 int by0 = box->y0;
2549 int bx1 = box->x1;
2550 int by1 = box->y1;
2551
2552 if ((bx0 >= selfI->boundingBox.x1) | (by0 >= selfI->boundingBox.y1) |
2553 (bx1 <= selfI->boundingBox.x0) | (by1 <= selfI->boundingBox.y0))
2554 return BL_HIT_TEST_OUT;
2555
2556 // If the bounding-box check passed the size MUST be greater than zero.
2557 BL_ASSUME(n > 0);
2558
2559 const BLBoxI* end = data + n;
2560 data += blBinarySearchClosestFirst(data, n, BLRegionXYMatcher(bx0, by0));
2561
2562 // [data:end] is our new working set, there is nothing to do if it's empty.
2563 if (data == end)
2564 return BL_HIT_TEST_OUT;
2565
2566 // Initially we assume that the hit-test would be BL_HIT_TEST_IN, which
2567 // means that all parts of the input box are within the region. When we
2568 // fail this condition we would try to match BL_HIT_TEST_PART and if
2569 // that fails we would return BL_HIT_TEST_OUT.
2570 if (data->y0 <= by0) {
2571 // 1. If the box is split into multiple region bands then each band must
2572 // contain a single rectangle that fully subsumes `box` to have a
2573 // full-in result.
2574 // 2. In addition, each band must follow the previous band, if there is
2575 // a gap then the hit-test cannot return full-in.
2576 int ry0 = data->y0;
2577 for (;;) {
2578 int ry1 = data->y1;
2579
2580 while (data->x1 <= bx0 && ++data == end)
2581 return ry0 > by0 ? BL_HIT_TEST_PART : BL_HIT_TEST_OUT;
2582
2583 if (data->x0 >= bx1)
2584 return ry0 > by0 ? BL_HIT_TEST_PART : BL_HIT_TEST_OUT;
2585
2586 // Now we know that the box pointed by data intersects our input box.
2587 // We don't know, however, whether we skipped multiple bands during
2588 // the loop and whether the box at `data[0]` fully subsumes our input
2589 // box.
2590 if ((data->y0 != ry0) | (data->x0 > bx0) | (data->x1 < bx1))
2591 return BL_HIT_TEST_PART;
2592
2593 // Last important band.
2594 if (by1 <= ry1)
2595 return BL_HIT_TEST_IN;
2596
2597 // Skip all remaining rectangles in this band.
2598 do {
2599 if (++data == end)
2600 return BL_HIT_TEST_PART;
2601 } while (data[0].y0 == ry0);
2602
2603 // It would be a partial hit if the next band doesn't follow this band.
2604 ry0 = ry1;
2605 if (ry0 != data->y0)
2606 return BL_HIT_TEST_PART;
2607 }
2608 }
2609
2610 // Partial hit at most.
2611 while (data->y0 < by1) {
2612 if ((data->x0 < bx1) & (data->x1 > bx0))
2613 return BL_HIT_TEST_PART;
2614 if (++data == end)
2615 break;
2616 }
2617
2618 return BL_HIT_TEST_OUT;
2619}
2620
2621// ============================================================================
2622// [BLRegion - Runtime Init]
2623// ============================================================================
2624
2625void blRegionRtInit(BLRuntimeContext* rt) noexcept {
2626 BL_UNUSED(rt);
2627
2628 BLInternalRegionImpl* regionI = &blNullRegionImpl;
2629 regionI->implType = uint8_t(BL_IMPL_TYPE_REGION);
2630 regionI->implTraits = uint8_t(BL_IMPL_TRAIT_NULL);
2631 blAssignBuiltInNull(regionI);
2632}
2633