1/*
2 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "Region.h"
28
29#include <stdio.h>
30#include <wtf/text/TextStream.h>
31
32// A region class based on the paper "Scanline Coherent Shape Algebra"
33// by Jonathan E. Steinhart from the book "Graphics Gems II".
34//
35// This implementation uses two vectors instead of linked list, and
36// also compresses regions when possible.
37
38namespace WebCore {
39
40Region::Region()
41{
42}
43
44Region::Region(const IntRect& rect)
45 : m_bounds(rect)
46{
47}
48
49Region::Region(const Region& other)
50 : m_bounds(other.m_bounds)
51 , m_shape(other.copyShape())
52{
53}
54
55Region::Region(Region&& other)
56 : m_bounds(WTFMove(other.m_bounds))
57 , m_shape(WTFMove(other.m_shape))
58{
59}
60
61Region::~Region()
62{
63}
64
65Region& Region::operator=(const Region& other)
66{
67 m_bounds = other.m_bounds;
68 m_shape = other.copyShape();
69 return *this;
70}
71
72Region& Region::operator=(Region&& other)
73{
74 m_bounds = WTFMove(other.m_bounds);
75 m_shape = WTFMove(other.m_shape);
76 return *this;
77}
78
79Vector<IntRect, 1> Region::rects() const
80{
81 Vector<IntRect, 1> rects;
82
83 if (!m_shape) {
84 if (!m_bounds.isEmpty())
85 rects.uncheckedAppend(m_bounds);
86 return rects;
87 }
88
89 for (Shape::SpanIterator span = m_shape->spans_begin(), end = m_shape->spans_end(); span != end && span + 1 != end; ++span) {
90 int y = span->y;
91 int height = (span + 1)->y - y;
92
93 for (Shape::SegmentIterator segment = m_shape->segments_begin(span), end = m_shape->segments_end(span); segment != end && segment + 1 != end; segment += 2) {
94 int x = *segment;
95 int width = *(segment + 1) - x;
96
97 rects.append(IntRect(x, y, width, height));
98 }
99 }
100
101 return rects;
102}
103
104bool Region::contains(const Region& region) const
105{
106 if (!m_bounds.contains(region.m_bounds))
107 return false;
108
109 if (!m_shape)
110 return true;
111
112 return Shape::compareShapes<Shape::CompareContainsOperation>(*m_shape, region.m_shape ? *region.m_shape : Shape(region.m_bounds));
113}
114
115bool Region::contains(const IntPoint& point) const
116{
117 if (!m_bounds.contains(point))
118 return false;
119
120 if (!m_shape)
121 return true;
122
123 for (Shape::SpanIterator span = m_shape->spans_begin(), end = m_shape->spans_end(); span != end && span + 1 != end; ++span) {
124 int y = span->y;
125 int maxY = (span + 1)->y;
126
127 if (y > point.y())
128 break;
129 if (maxY <= point.y())
130 continue;
131
132 for (Shape::SegmentIterator segment = m_shape->segments_begin(span), end = m_shape->segments_end(span); segment != end && segment + 1 != end; segment += 2) {
133 int x = *segment;
134 int maxX = *(segment + 1);
135
136 if (x > point.x())
137 break;
138 if (maxX > point.x())
139 return true;
140 }
141 }
142
143 return false;
144}
145
146bool Region::intersects(const Region& region) const
147{
148 if (!m_bounds.intersects(region.m_bounds))
149 return false;
150
151 if (!m_shape && !region.m_shape)
152 return true;
153
154 return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds);
155}
156
157uint64_t Region::totalArea() const
158{
159 uint64_t totalArea = 0;
160
161 for (auto& rect : rects())
162 totalArea += (rect.width() * rect.height());
163
164 return totalArea;
165}
166
167template<typename CompareOperation>
168bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape)
169{
170 bool result = CompareOperation::defaultResult;
171
172 Shape::SpanIterator aSpan = aShape.spans_begin();
173 Shape::SpanIterator aSpanEnd = aShape.spans_end();
174 Shape::SpanIterator bSpan = bShape.spans_begin();
175 Shape::SpanIterator bSpanEnd = bShape.spans_end();
176
177 bool aHadSegmentInPreviousSpan = false;
178 bool bHadSegmentInPreviousSpan = false;
179 while (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && bSpan != bSpanEnd && bSpan + 1 != bSpanEnd) {
180 int aY = aSpan->y;
181 int aMaxY = (aSpan + 1)->y;
182 int bY = bSpan->y;
183 int bMaxY = (bSpan + 1)->y;
184
185 Shape::SegmentIterator aSegment = aShape.segments_begin(aSpan);
186 Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan);
187 Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan);
188 Shape::SegmentIterator bSegmentEnd = bShape.segments_end(bSpan);
189
190 // Look for a non-overlapping part of the spans. If B had a segment in its previous span, then we already tested A against B within that span.
191 bool aHasSegmentInSpan = aSegment != aSegmentEnd;
192 bool bHasSegmentInSpan = bSegment != bSegmentEnd;
193 if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result))
194 return result;
195 if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result))
196 return result;
197
198 aHadSegmentInPreviousSpan = aHasSegmentInSpan;
199 bHadSegmentInPreviousSpan = bHasSegmentInSpan;
200
201 bool spansOverlap = bMaxY > aY && bY < aMaxY;
202 if (spansOverlap) {
203 while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) {
204 int aX = *aSegment;
205 int aMaxX = *(aSegment + 1);
206 int bX = *bSegment;
207 int bMaxX = *(bSegment + 1);
208
209 bool segmentsOverlap = bMaxX > aX && bX < aMaxX;
210 if (segmentsOverlap && CompareOperation::aOverlapsB(result))
211 return result;
212 if (aX < bX && CompareOperation::aOutsideB(result))
213 return result;
214 if (bX < aX && CompareOperation::bOutsideA(result))
215 return result;
216
217 if (aMaxX < bMaxX)
218 aSegment += 2;
219 else if (bMaxX < aMaxX)
220 bSegment += 2;
221 else {
222 aSegment += 2;
223 bSegment += 2;
224 }
225 }
226
227 if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result))
228 return result;
229 if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result))
230 return result;
231 }
232
233 if (aMaxY < bMaxY)
234 aSpan += 1;
235 else if (bMaxY < aMaxY)
236 bSpan += 1;
237 else {
238 aSpan += 1;
239 bSpan += 1;
240 }
241 }
242
243 if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result))
244 return result;
245 if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result))
246 return result;
247
248 return result;
249}
250
251struct Region::Shape::CompareContainsOperation {
252 const static bool defaultResult = true;
253 inline static bool aOutsideB(bool& /* result */) { return false; }
254 inline static bool bOutsideA(bool& result) { result = false; return true; }
255 inline static bool aOverlapsB(bool& /* result */) { return false; }
256};
257
258struct Region::Shape::CompareIntersectsOperation {
259 const static bool defaultResult = false;
260 inline static bool aOutsideB(bool& /* result */) { return false; }
261 inline static bool bOutsideA(bool& /* result */) { return false; }
262 inline static bool aOverlapsB(bool& result) { result = true; return true; }
263};
264
265Region::Shape::Shape(const IntRect& rect)
266 : m_segments({ rect.x(), rect.maxX() })
267 , m_spans({ { rect.y(), 0 }, { rect.maxY(), 2 } })
268{
269}
270
271void Region::Shape::appendSpan(int y)
272{
273 m_spans.append({ y, m_segments.size() });
274}
275
276bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
277{
278 if (m_spans.isEmpty())
279 return false;
280
281 SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
282 SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
283
284 // Check if both spans have an equal number of segments.
285 if (lastSpanEnd - lastSpanBegin != end - begin)
286 return false;
287
288 // Check if both spans are equal.
289 if (!std::equal(begin, end, lastSpanBegin))
290 return false;
291
292 // Since the segments are equal the second segment can just be ignored.
293 return true;
294}
295
296void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
297{
298 if (canCoalesce(begin, end))
299 return;
300
301 appendSpan(y);
302 m_segments.appendRange(begin, end);
303}
304
305void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
306{
307 for (SpanIterator it = begin; it != end; ++it)
308 appendSpan(it->y, shape.segments_begin(it), shape.segments_end(it));
309}
310
311void Region::Shape::appendSegment(int x)
312{
313 m_segments.append(x);
314}
315
316Region::Shape::SpanIterator Region::Shape::spans_begin() const
317{
318 return m_spans.data();
319}
320
321Region::Shape::SpanIterator Region::Shape::spans_end() const
322{
323 return m_spans.data() + m_spans.size();
324}
325
326Region::Shape::SegmentIterator Region::Shape::segments_begin(SpanIterator it) const
327{
328 ASSERT(it >= m_spans.data());
329 ASSERT(it < m_spans.data() + m_spans.size());
330
331 // Check if this span has any segments.
332 if (it->segmentIndex == m_segments.size())
333 return 0;
334
335 return &m_segments[it->segmentIndex];
336}
337
338Region::Shape::SegmentIterator Region::Shape::segments_end(SpanIterator it) const
339{
340 ASSERT(it >= m_spans.data());
341 ASSERT(it < m_spans.data() + m_spans.size());
342
343 // Check if this span has any segments.
344 if (it->segmentIndex == m_segments.size())
345 return 0;
346
347 ASSERT(it + 1 < m_spans.data() + m_spans.size());
348 size_t segmentIndex = (it + 1)->segmentIndex;
349
350 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
351 return m_segments.data() + segmentIndex;
352}
353
354#ifndef NDEBUG
355void Region::Shape::dump() const
356{
357 for (auto span = spans_begin(), end = spans_end(); span != end; ++span) {
358 printf("%6d: (", span->y);
359
360 for (auto segment = segments_begin(span), end = segments_end(span); segment != end; ++segment)
361 printf("%d ", *segment);
362 printf(")\n");
363 }
364
365 printf("\n");
366}
367#endif
368
369IntRect Region::Shape::bounds() const
370{
371 if (isEmpty())
372 return IntRect();
373
374 SpanIterator span = spans_begin();
375 int minY = span->y;
376
377 SpanIterator lastSpan = spans_end() - 1;
378 int maxY = lastSpan->y;
379
380 int minX = std::numeric_limits<int>::max();
381 int maxX = std::numeric_limits<int>::min();
382
383 while (span != lastSpan) {
384 SegmentIterator firstSegment = segments_begin(span);
385 SegmentIterator lastSegment = segments_end(span) - 1;
386
387 if (firstSegment && lastSegment) {
388 ASSERT(firstSegment != lastSegment);
389
390 if (*firstSegment < minX)
391 minX = *firstSegment;
392
393 if (*lastSegment > maxX)
394 maxX = *lastSegment;
395 }
396
397 ++span;
398 }
399
400 ASSERT(minX <= maxX);
401 ASSERT(minY <= maxY);
402
403 return IntRect(minX, minY, maxX - minX, maxY - minY);
404}
405
406void Region::Shape::translate(const IntSize& offset)
407{
408 for (size_t i = 0; i < m_segments.size(); ++i)
409 m_segments[i] += offset.width();
410 for (size_t i = 0; i < m_spans.size(); ++i)
411 m_spans[i].y += offset.height();
412}
413
414enum {
415 Shape1,
416 Shape2,
417};
418
419template<typename Operation>
420Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
421{
422 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
423 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
424
425 Shape result;
426 if (Operation::trySimpleOperation(shape1, shape2, result))
427 return result;
428
429 SpanIterator spans1 = shape1.spans_begin();
430 SpanIterator spans1End = shape1.spans_end();
431
432 SpanIterator spans2 = shape2.spans_begin();
433 SpanIterator spans2End = shape2.spans_end();
434
435 SegmentIterator segments1 = 0;
436 SegmentIterator segments1End = 0;
437
438 SegmentIterator segments2 = 0;
439 SegmentIterator segments2End = 0;
440
441 // Iterate over all spans.
442 while (spans1 != spans1End && spans2 != spans2End) {
443 int y = 0;
444 int test = spans1->y - spans2->y;
445
446 if (test <= 0) {
447 y = spans1->y;
448
449 segments1 = shape1.segments_begin(spans1);
450 segments1End = shape1.segments_end(spans1);
451 ++spans1;
452 }
453 if (test >= 0) {
454 y = spans2->y;
455
456 segments2 = shape2.segments_begin(spans2);
457 segments2End = shape2.segments_end(spans2);
458 ++spans2;
459 }
460
461 int flag = 0;
462 int oldFlag = 0;
463
464 SegmentIterator s1 = segments1;
465 SegmentIterator s2 = segments2;
466
467 Vector<int, 32> segments;
468
469 // Now iterate over the segments in each span and construct a new vector of segments.
470 while (s1 != segments1End && s2 != segments2End) {
471 int test = *s1 - *s2;
472 int x;
473
474 if (test <= 0) {
475 x = *s1;
476 flag = flag ^ 1;
477 ++s1;
478 }
479 if (test >= 0) {
480 x = *s2;
481 flag = flag ^ 2;
482 ++s2;
483 }
484
485 if (flag == Operation::opCode || oldFlag == Operation::opCode)
486 segments.append(x);
487
488 oldFlag = flag;
489 }
490
491 // Add any remaining segments.
492 if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
493 segments.appendRange(s1, segments1End);
494 else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
495 segments.appendRange(s2, segments2End);
496
497 // Add the span.
498 if (!segments.isEmpty() || !result.isEmpty())
499 result.appendSpan(y, segments.data(), segments.data() + segments.size());
500 }
501
502 // Add any remaining spans.
503 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
504 result.appendSpans(shape1, spans1, spans1End);
505 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
506 result.appendSpans(shape2, spans2, spans2End);
507
508 return result;
509}
510
511struct Region::Shape::UnionOperation {
512 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
513 {
514 if (shape1.isEmpty()) {
515 result = shape2;
516 return true;
517 }
518
519 return false;
520 }
521
522 static const int opCode = 0;
523
524 static const bool shouldAddRemainingSegmentsFromSpan1 = true;
525 static const bool shouldAddRemainingSegmentsFromSpan2 = true;
526 static const bool shouldAddRemainingSpansFromShape1 = true;
527 static const bool shouldAddRemainingSpansFromShape2 = true;
528};
529
530Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
531{
532 return shapeOperation<UnionOperation>(shape1, shape2);
533}
534
535struct Region::Shape::IntersectOperation {
536 static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
537 {
538 return false;
539 }
540
541 static const int opCode = 3;
542
543 static const bool shouldAddRemainingSegmentsFromSpan1 = false;
544 static const bool shouldAddRemainingSegmentsFromSpan2 = false;
545 static const bool shouldAddRemainingSpansFromShape1 = false;
546 static const bool shouldAddRemainingSpansFromShape2 = false;
547};
548
549Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
550{
551 return shapeOperation<IntersectOperation>(shape1, shape2);
552}
553
554struct Region::Shape::SubtractOperation {
555 static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
556 {
557 return false;
558 }
559
560 static const int opCode = 1;
561
562 static const bool shouldAddRemainingSegmentsFromSpan1 = true;
563 static const bool shouldAddRemainingSegmentsFromSpan2 = false;
564 static const bool shouldAddRemainingSpansFromShape1 = true;
565 static const bool shouldAddRemainingSpansFromShape2 = false;
566};
567
568Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
569{
570 return shapeOperation<SubtractOperation>(shape1, shape2);
571}
572
573#ifndef NDEBUG
574void Region::dump() const
575{
576 printf("Bounds: (%d, %d, %d, %d)\n",
577 m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
578 if (m_shape)
579 m_shape->dump();
580}
581#endif
582
583void Region::intersect(const Region& region)
584{
585 if (m_bounds.isEmpty())
586 return;
587 if (!m_bounds.intersects(region.m_bounds)) {
588 m_shape = nullptr;
589 m_bounds = IntRect();
590 return;
591 }
592 if (!m_shape && !region.m_shape) {
593 m_bounds = intersection(m_bounds, region.m_bounds);
594 return;
595 }
596
597 setShape(Shape::intersectShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
598}
599
600void Region::unite(const Region& region)
601{
602 if (region.isEmpty())
603 return;
604 if (isEmpty()) {
605 m_bounds = region.m_bounds;
606 m_shape = region.copyShape();
607 return;
608 }
609 if (region.isRect() && region.m_bounds.contains(m_bounds)) {
610 m_bounds = region.m_bounds;
611 m_shape = nullptr;
612 return;
613 }
614 if (contains(region))
615 return;
616
617 setShape(Shape::unionShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
618}
619
620void Region::subtract(const Region& region)
621{
622 if (isEmpty())
623 return;
624 if (region.isEmpty())
625 return;
626 if (!m_bounds.intersects(region.m_bounds))
627 return;
628
629 setShape(Shape::subtractShapes(m_shape ? *m_shape : m_bounds, region.m_shape ? *region.m_shape : region.m_bounds));
630}
631
632void Region::translate(const IntSize& offset)
633{
634 m_bounds.move(offset);
635 if (m_shape)
636 m_shape->translate(offset);
637}
638
639void Region::setShape(Shape&& shape)
640{
641 m_bounds = shape.bounds();
642
643 if (shape.isRect()) {
644 m_shape = nullptr;
645 return;
646 }
647
648 if (!m_shape)
649 m_shape = std::make_unique<Shape>(WTFMove(shape));
650 else
651 *m_shape = WTFMove(shape);
652}
653
654TextStream& operator<<(TextStream& ts, const Region& region)
655{
656 ts << "\n";
657 {
658 TextStream::IndentScope indentScope(ts);
659 for (auto& rect : region.rects())
660 ts << indent << "(rect " << rect << ")\n";
661 }
662
663 return ts;
664}
665
666} // namespace WebCore
667