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 | |
19 | static BLWrap<BLInternalRegionImpl> blNullRegionImpl; |
20 | |
21 | static const BLBoxI blRegionLargestBoxI { |
22 | blMinValue<int>(), |
23 | blMinValue<int>(), |
24 | blMaxValue<int>(), |
25 | blMaxValue<int>() |
26 | }; |
27 | |
28 | // ============================================================================ |
29 | // [BLRegion - Internal] |
30 | // ============================================================================ |
31 | |
32 | static constexpr size_t blRegionImplSizeOf(size_t n = 0) noexcept { return blContainerSizeOf(sizeof(BLInternalRegionImpl), sizeof(BLBoxI), n); } |
33 | static constexpr size_t blRegionCapacityOf(size_t implSize) noexcept { return blContainerCapacityOf(sizeof(BLInternalRegionImpl), sizeof(BLBoxI), implSize); } |
34 | static constexpr size_t blRegionMaximumCapacity() noexcept { return blRegionCapacityOf(SIZE_MAX); } |
35 | static BL_INLINE size_t blRegionFittingCapacity(size_t n) noexcept { return blContainerFittingCapacity(blRegionImplSizeOf(), sizeof(BLBoxI), n); } |
36 | static BL_INLINE size_t blRegionGrowingCapacity(size_t n) noexcept { return blContainerGrowingCapacity(blRegionImplSizeOf(), sizeof(BLBoxI), n, BL_ALLOC_HINT_REGION); } |
37 | |
38 | static 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 | |
43 | static 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 | |
58 | static 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. |
79 | BLResult 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 | |
99 | static BL_INLINE BLResult blRegionImplRelease(BLInternalRegionImpl* impl) noexcept { |
100 | if (blImplDecRefAndTest(impl)) |
101 | return blRegionImplDelete(impl); |
102 | return BL_SUCCESS; |
103 | } |
104 | |
105 | static 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 | |
127 | struct BLRegionXYMatcher { |
128 | int x, y; |
129 | BL_INLINE BLRegionXYMatcher(int x, int y) noexcept : x(x), y(y) {} |
130 | }; |
131 | static 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 | |
137 | static BL_INLINE const BLBoxI& blAsBox(const BLBoxI& box) noexcept { return box; } |
138 | static 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. |
141 | static 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. |
149 | static 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 | |
156 | static 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. |
162 | static 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 | |
171 | static 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 | |
188 | static 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 | |
244 | NonConforming: |
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 | |
253 | static 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 | |
317 | NonConforming: |
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 | |
331 | static 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 | |
357 | BLResult blRegionInit(BLRegionCore* self) noexcept { |
358 | self->impl = BLRegion::none().impl; |
359 | return BL_SUCCESS; |
360 | } |
361 | |
362 | BLResult 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 | |
372 | BLResult 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 | |
386 | BLResult 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 | |
402 | BLResult 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 | |
417 | static 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 | |
438 | static 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 | |
460 | static 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 | |
490 | static 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 | |
522 | template<typename T> |
523 | static 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 | |
575 | template<typename T> |
576 | static 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 | |
591 | BLResult 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 | |
601 | BLResult 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 | |
609 | BLResult 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 | |
614 | BLResult 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 | |
620 | BLResult 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 | |
643 | BLResult 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 | |
663 | BLResult 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). |
684 | static 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 | // .......... |
710 | static 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 | |
782 | static 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 | |
798 | static 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 | |
825 | static 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 | |
929 | Merge: |
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 | |
936 | Skip: |
937 | if (srcDataPtr == srcDataEnd) |
938 | break; |
939 | } |
940 | |
941 | Done: |
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. |
961 | static 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. |
991 | static 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. |
1248 | OnUnionBandDone: |
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 | |
1341 | OnXorMerge: |
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 | |
1351 | OnXorSkip: |
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. |
1405 | OnXorBandDone: |
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 | |
1500 | OnSubtractMerge: |
1501 | BL_ASSERT(x0 < x1); |
1502 | dstData->reset(x0, y0, x1, y1); |
1503 | dstData++; |
1504 | |
1505 | OnSubtractSkip: |
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. |
1531 | OnSubtractBandDone: |
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 | |
1538 | OnSubtractBandSkip: |
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 | |
1567 | Done: |
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 | |
1579 | OutOfMemory: |
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 | |
1587 | OnMergeB: |
1588 | BL_ASSERT(aData == aEnd); |
1589 | |
1590 | aData = bData; |
1591 | aEnd = bEnd; |
1592 | aBandEnd = bBandEnd; |
1593 | |
1594 | OnMergeA: |
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 | |
1648 | BLResult 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 | |
1732 | BLResult 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 | |
1783 | BLResult 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 | |
1836 | BLResult 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) { |
1893 | Copy: |
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); |
2067 | UnionLastCoalesce: |
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 | |
2078 | Clear: |
2079 | return blRegionClear(self); |
2080 | |
2081 | Done: |
2082 | BL_ASSUME(n > 0); |
2083 | return blRegionAssignValidBoxIArray(self, box, n); |
2084 | } |
2085 | |
2086 | // ============================================================================ |
2087 | // [BLRegion - Translate] |
2088 | // ============================================================================ |
2089 | |
2090 | BLResult 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 | |
2140 | BLResult 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 | |
2287 | EndBand: |
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 | |
2303 | Done: |
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 | |
2320 | BLResult 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. |
2442 | EndBand: |
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 | |
2477 | Done: |
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 | |
2494 | bool 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 | |
2513 | uint32_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 | |
2521 | uint32_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 | |
2538 | uint32_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 | |
2625 | void 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 | |