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 "platform/geometry/Region.h"
28
29 #include <stdio.h>
30
31 // A region class based on the paper "Scanline Coherent Shape Algebra"
32 // by Jonathan E. Steinhart from the book "Graphics Gems II".
33 //
34 // This implementation uses two vectors instead of linked list, and
35 // also compresses regions when possible.
36
37 namespace blink {
38
Region()39 Region::Region()
40 {
41 }
42
Region(const IntRect & rect)43 Region::Region(const IntRect& rect)
44 : m_bounds(rect)
45 , m_shape(rect)
46 {
47 }
48
rects() const49 Vector<IntRect> Region::rects() const
50 {
51 Vector<IntRect> rects;
52
53 for (Shape::SpanIterator span = m_shape.spansBegin(), end = m_shape.spansEnd(); span != end && span + 1 != end; ++span) {
54 int y = span->y;
55 int height = (span + 1)->y - y;
56
57 for (Shape::SegmentIterator segment = m_shape.segmentsBegin(span), end = m_shape.segmentsEnd(span); segment != end && segment + 1 != end; segment += 2) {
58 int x = *segment;
59 int width = *(segment + 1) - x;
60
61 rects.append(IntRect(x, y, width, height));
62 }
63 }
64
65 return rects;
66 }
67
contains(const Region & region) const68 bool Region::contains(const Region& region) const
69 {
70 if (!m_bounds.contains(region.m_bounds))
71 return false;
72
73 return Shape::compareShapes<Shape::CompareContainsOperation>(m_shape, region.m_shape);
74 }
75
contains(const IntPoint & point) const76 bool Region::contains(const IntPoint& point) const
77 {
78 if (!m_bounds.contains(point))
79 return false;
80
81 for (Shape::SpanIterator span = m_shape.spansBegin(), end = m_shape.spansEnd(); span != end && span + 1 != end; ++span) {
82 int y = span->y;
83 int maxY = (span + 1)->y;
84
85 if (y > point.y())
86 break;
87 if (maxY <= point.y())
88 continue;
89
90 for (Shape::SegmentIterator segment = m_shape.segmentsBegin(span), end = m_shape.segmentsEnd(span); segment != end && segment + 1 != end; segment += 2) {
91 int x = *segment;
92 int maxX = *(segment + 1);
93
94 if (x > point.x())
95 break;
96 if (maxX > point.x())
97 return true;
98 }
99 }
100
101 return false;
102 }
103
intersects(const Region & region) const104 bool Region::intersects(const Region& region) const
105 {
106 if (!m_bounds.intersects(region.m_bounds))
107 return false;
108
109 return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape, region.m_shape);
110 }
111
totalArea() const112 unsigned Region::totalArea() const
113 {
114 Vector<IntRect> rects = this->rects();
115 size_t size = rects.size();
116 unsigned totalArea = 0;
117
118 for (size_t i = 0; i < size; ++i) {
119 IntRect rect = rects[i];
120 totalArea += (rect.width() * rect.height());
121 }
122
123 return totalArea;
124 }
125
126 template<typename CompareOperation>
compareShapes(const Shape & aShape,const Shape & bShape)127 bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape)
128 {
129 bool result = CompareOperation::defaultResult;
130
131 Shape::SpanIterator aSpan = aShape.spansBegin();
132 Shape::SpanIterator aSpanEnd = aShape.spansEnd();
133 Shape::SpanIterator bSpan = bShape.spansBegin();
134 Shape::SpanIterator bSpanEnd = bShape.spansEnd();
135
136 bool aHadSegmentInPreviousSpan = false;
137 bool bHadSegmentInPreviousSpan = false;
138 while (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && bSpan != bSpanEnd && bSpan + 1 != bSpanEnd) {
139 int aY = aSpan->y;
140 int aMaxY = (aSpan + 1)->y;
141 int bY = bSpan->y;
142 int bMaxY = (bSpan + 1)->y;
143
144 Shape::SegmentIterator aSegment = aShape.segmentsBegin(aSpan);
145 Shape::SegmentIterator aSegmentEnd = aShape.segmentsEnd(aSpan);
146 Shape::SegmentIterator bSegment = bShape.segmentsBegin(bSpan);
147 Shape::SegmentIterator bSegmentEnd = bShape.segmentsEnd(bSpan);
148
149 // 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.
150 bool aHasSegmentInSpan = aSegment != aSegmentEnd;
151 bool bHasSegmentInSpan = bSegment != bSegmentEnd;
152 if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result))
153 return result;
154 if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result))
155 return result;
156
157 aHadSegmentInPreviousSpan = aHasSegmentInSpan;
158 bHadSegmentInPreviousSpan = bHasSegmentInSpan;
159
160 bool spansOverlap = bMaxY > aY && bY < aMaxY;
161 if (spansOverlap) {
162 while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) {
163 int aX = *aSegment;
164 int aMaxX = *(aSegment + 1);
165 int bX = *bSegment;
166 int bMaxX = *(bSegment + 1);
167
168 bool segmentsOverlap = bMaxX > aX && bX < aMaxX;
169 if (segmentsOverlap && CompareOperation::aOverlapsB(result))
170 return result;
171 if (aX < bX && CompareOperation::aOutsideB(result))
172 return result;
173 if (bX < aX && CompareOperation::bOutsideA(result))
174 return result;
175
176 if (aMaxX < bMaxX) {
177 aSegment += 2;
178 } else if (bMaxX < aMaxX) {
179 bSegment += 2;
180 } else {
181 aSegment += 2;
182 bSegment += 2;
183 }
184 }
185
186 if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result))
187 return result;
188 if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result))
189 return result;
190 }
191
192 if (aMaxY < bMaxY) {
193 aSpan += 1;
194 } else if (bMaxY < aMaxY) {
195 bSpan += 1;
196 } else {
197 aSpan += 1;
198 bSpan += 1;
199 }
200 }
201
202 if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result))
203 return result;
204 if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result))
205 return result;
206
207 return result;
208 }
209
trimCapacities()210 void Region::Shape::trimCapacities()
211 {
212 m_segments.shrinkToReasonableCapacity();
213 m_spans.shrinkToReasonableCapacity();
214 }
215
216 struct Region::Shape::CompareContainsOperation {
217 const static bool defaultResult = true;
aOutsideBblink::Region::Shape::CompareContainsOperation218 inline static bool aOutsideB(bool& /* result */) { return false; }
bOutsideAblink::Region::Shape::CompareContainsOperation219 inline static bool bOutsideA(bool& result) { result = false; return true; }
aOverlapsBblink::Region::Shape::CompareContainsOperation220 inline static bool aOverlapsB(bool& /* result */) { return false; }
221 };
222
223 struct Region::Shape::CompareIntersectsOperation {
224 const static bool defaultResult = false;
aOutsideBblink::Region::Shape::CompareIntersectsOperation225 inline static bool aOutsideB(bool& /* result */) { return false; }
bOutsideAblink::Region::Shape::CompareIntersectsOperation226 inline static bool bOutsideA(bool& /* result */) { return false; }
aOverlapsBblink::Region::Shape::CompareIntersectsOperation227 inline static bool aOverlapsB(bool& result) { result = true; return true; }
228 };
229
Shape()230 Region::Shape::Shape()
231 {
232 }
233
Shape(const IntRect & rect)234 Region::Shape::Shape(const IntRect& rect)
235 {
236 appendSpan(rect.y());
237 appendSegment(rect.x());
238 appendSegment(rect.maxX());
239 appendSpan(rect.maxY());
240 }
241
Shape(size_t segmentsCapacity,size_t spansCapacity)242 Region::Shape::Shape(size_t segmentsCapacity, size_t spansCapacity)
243 {
244 m_segments.reserveCapacity(segmentsCapacity);
245 m_spans.reserveCapacity(spansCapacity);
246 }
247
appendSpan(int y)248 void Region::Shape::appendSpan(int y)
249 {
250 m_spans.append(Span(y, m_segments.size()));
251 }
252
canCoalesce(SegmentIterator begin,SegmentIterator end)253 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
254 {
255 if (m_spans.isEmpty())
256 return false;
257
258 SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
259 SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
260
261 // Check if both spans have an equal number of segments.
262 if (lastSpanEnd - lastSpanBegin != end - begin)
263 return false;
264
265 // Check if both spans are equal.
266 if (!std::equal(begin, end, lastSpanBegin))
267 return false;
268
269 // Since the segments are equal the second segment can just be ignored.
270 return true;
271 }
272
appendSpan(int y,SegmentIterator begin,SegmentIterator end)273 void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
274 {
275 if (canCoalesce(begin, end))
276 return;
277
278 appendSpan(y);
279 m_segments.appendRange(begin, end);
280 }
281
appendSpans(const Shape & shape,SpanIterator begin,SpanIterator end)282 void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
283 {
284 for (SpanIterator it = begin; it != end; ++it)
285 appendSpan(it->y, shape.segmentsBegin(it), shape.segmentsEnd(it));
286 }
287
appendSegment(int x)288 void Region::Shape::appendSegment(int x)
289 {
290 m_segments.append(x);
291 }
292
spansBegin() const293 Region::Shape::SpanIterator Region::Shape::spansBegin() const
294 {
295 return m_spans.data();
296 }
297
spansEnd() const298 Region::Shape::SpanIterator Region::Shape::spansEnd() const
299 {
300 return m_spans.data() + m_spans.size();
301 }
302
segmentsBegin(SpanIterator it) const303 Region::Shape::SegmentIterator Region::Shape::segmentsBegin(SpanIterator it) const
304 {
305 ASSERT(it >= m_spans.data());
306 ASSERT(it < m_spans.data() + m_spans.size());
307
308 // Check if this span has any segments.
309 if (it->segmentIndex == m_segments.size())
310 return 0;
311
312 return &m_segments[it->segmentIndex];
313 }
314
segmentsEnd(SpanIterator it) const315 Region::Shape::SegmentIterator Region::Shape::segmentsEnd(SpanIterator it) const
316 {
317 ASSERT(it >= m_spans.data());
318 ASSERT(it < m_spans.data() + m_spans.size());
319
320 // Check if this span has any segments.
321 if (it->segmentIndex == m_segments.size())
322 return 0;
323
324 ASSERT(it + 1 < m_spans.data() + m_spans.size());
325 size_t segmentIndex = (it + 1)->segmentIndex;
326
327 ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
328 return m_segments.data() + segmentIndex;
329 }
330
331 #ifndef NDEBUG
dump() const332 void Region::Shape::dump() const
333 {
334 for (Shape::SpanIterator span = spansBegin(), end = spansEnd(); span != end; ++span) {
335 printf("%6d: (", span->y);
336
337 for (Shape::SegmentIterator segment = segmentsBegin(span), end = segmentsEnd(span); segment != end; ++segment)
338 printf("%d ", *segment);
339 printf(")\n");
340 }
341
342 printf("\n");
343 }
344 #endif
345
bounds() const346 IntRect Region::Shape::bounds() const
347 {
348 if (isEmpty())
349 return IntRect();
350
351 SpanIterator span = spansBegin();
352 int minY = span->y;
353
354 SpanIterator lastSpan = spansEnd() - 1;
355 int maxY = lastSpan->y;
356
357 int minX = std::numeric_limits<int>::max();
358 int maxX = std::numeric_limits<int>::min();
359
360 while (span != lastSpan) {
361 SegmentIterator firstSegment = segmentsBegin(span);
362 SegmentIterator lastSegment = segmentsEnd(span) - 1;
363
364 if (firstSegment && lastSegment) {
365 ASSERT(firstSegment != lastSegment);
366
367 if (*firstSegment < minX)
368 minX = *firstSegment;
369
370 if (*lastSegment > maxX)
371 maxX = *lastSegment;
372 }
373
374 ++span;
375 }
376
377 ASSERT(minX <= maxX);
378 ASSERT(minY <= maxY);
379
380 return IntRect(minX, minY, maxX - minX, maxY - minY);
381 }
382
translate(const IntSize & offset)383 void Region::Shape::translate(const IntSize& offset)
384 {
385 for (size_t i = 0; i < m_segments.size(); ++i)
386 m_segments[i] += offset.width();
387 for (size_t i = 0; i < m_spans.size(); ++i)
388 m_spans[i].y += offset.height();
389 }
390
swap(Shape & other)391 void Region::Shape::swap(Shape& other)
392 {
393 m_segments.swap(other.m_segments);
394 m_spans.swap(other.m_spans);
395 }
396
397 enum {
398 Shape1,
399 Shape2,
400 };
401
402 template<typename Operation>
shapeOperation(const Shape & shape1,const Shape & shape2)403 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
404 {
405 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
406 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
407
408 size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize();
409 size_t spansCapacity = shape1.spansSize() + shape2.spansSize();
410 Shape result(segmentsCapacity, spansCapacity);
411 if (Operation::trySimpleOperation(shape1, shape2, result))
412 return result;
413
414 SpanIterator spans1 = shape1.spansBegin();
415 SpanIterator spans1End = shape1.spansEnd();
416
417 SpanIterator spans2 = shape2.spansBegin();
418 SpanIterator spans2End = shape2.spansEnd();
419
420 SegmentIterator segments1 = 0;
421 SegmentIterator segments1End = 0;
422
423 SegmentIterator segments2 = 0;
424 SegmentIterator segments2End = 0;
425
426 Vector<int, 32> segments;
427 segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize()));
428
429 // Iterate over all spans.
430 while (spans1 != spans1End && spans2 != spans2End) {
431 int y = 0;
432 int test = spans1->y - spans2->y;
433
434 if (test <= 0) {
435 y = spans1->y;
436
437 segments1 = shape1.segmentsBegin(spans1);
438 segments1End = shape1.segmentsEnd(spans1);
439 ++spans1;
440 }
441 if (test >= 0) {
442 y = spans2->y;
443
444 segments2 = shape2.segmentsBegin(spans2);
445 segments2End = shape2.segmentsEnd(spans2);
446 ++spans2;
447 }
448
449 int flag = 0;
450 int oldFlag = 0;
451
452 SegmentIterator s1 = segments1;
453 SegmentIterator s2 = segments2;
454
455 // Clear vector without dropping capacity.
456 segments.resize(0);
457 ASSERT(segments.capacity());
458
459 // Now iterate over the segments in each span and construct a new vector of segments.
460 while (s1 != segments1End && s2 != segments2End) {
461 int test = *s1 - *s2;
462 int x;
463
464 if (test <= 0) {
465 x = *s1;
466 flag = flag ^ 1;
467 ++s1;
468 }
469 if (test >= 0) {
470 x = *s2;
471 flag = flag ^ 2;
472 ++s2;
473 }
474
475 if (flag == Operation::opCode || oldFlag == Operation::opCode)
476 segments.append(x);
477
478 oldFlag = flag;
479 }
480
481 // Add any remaining segments.
482 if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
483 segments.appendRange(s1, segments1End);
484 else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
485 segments.appendRange(s2, segments2End);
486
487 // Add the span.
488 if (!segments.isEmpty() || !result.isEmpty())
489 result.appendSpan(y, segments.data(), segments.data() + segments.size());
490 }
491
492 // Add any remaining spans.
493 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
494 result.appendSpans(shape1, spans1, spans1End);
495 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
496 result.appendSpans(shape2, spans2, spans2End);
497
498 result.trimCapacities();
499
500 return result;
501 }
502
503 struct Region::Shape::UnionOperation {
trySimpleOperationblink::Region::Shape::UnionOperation504 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
505 {
506 if (shape1.isEmpty()) {
507 result = shape2;
508 return true;
509 }
510
511 return false;
512 }
513
514 static const int opCode = 0;
515
516 static const bool shouldAddRemainingSegmentsFromSpan1 = true;
517 static const bool shouldAddRemainingSegmentsFromSpan2 = true;
518 static const bool shouldAddRemainingSpansFromShape1 = true;
519 static const bool shouldAddRemainingSpansFromShape2 = true;
520 };
521
unionShapes(const Shape & shape1,const Shape & shape2)522 Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
523 {
524 return shapeOperation<UnionOperation>(shape1, shape2);
525 }
526
527 struct Region::Shape::IntersectOperation {
trySimpleOperationblink::Region::Shape::IntersectOperation528 static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
529 {
530 return false;
531 }
532
533 static const int opCode = 3;
534
535 static const bool shouldAddRemainingSegmentsFromSpan1 = false;
536 static const bool shouldAddRemainingSegmentsFromSpan2 = false;
537 static const bool shouldAddRemainingSpansFromShape1 = false;
538 static const bool shouldAddRemainingSpansFromShape2 = false;
539 };
540
intersectShapes(const Shape & shape1,const Shape & shape2)541 Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
542 {
543 return shapeOperation<IntersectOperation>(shape1, shape2);
544 }
545
546 struct Region::Shape::SubtractOperation {
trySimpleOperationblink::Region::Shape::SubtractOperation547 static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
548 {
549 return false;
550 }
551
552 static const int opCode = 1;
553
554 static const bool shouldAddRemainingSegmentsFromSpan1 = true;
555 static const bool shouldAddRemainingSegmentsFromSpan2 = false;
556 static const bool shouldAddRemainingSpansFromShape1 = true;
557 static const bool shouldAddRemainingSpansFromShape2 = false;
558 };
559
subtractShapes(const Shape & shape1,const Shape & shape2)560 Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
561 {
562 return shapeOperation<SubtractOperation>(shape1, shape2);
563 }
564
565 #ifndef NDEBUG
dump() const566 void Region::dump() const
567 {
568 printf("Bounds: (%d, %d, %d, %d)\n", m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
569 m_shape.dump();
570 }
571 #endif
572
intersect(const Region & region)573 void Region::intersect(const Region& region)
574 {
575 if (m_bounds.isEmpty())
576 return;
577 if (!m_bounds.intersects(region.m_bounds)) {
578 m_shape = Shape();
579 m_bounds = IntRect();
580 return;
581 }
582
583 Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
584
585 m_shape.swap(intersectedShape);
586 m_bounds = m_shape.bounds();
587 }
588
unite(const Region & region)589 void Region::unite(const Region& region)
590 {
591 if (region.isEmpty())
592 return;
593 if (isRect() && m_bounds.contains(region.m_bounds))
594 return;
595 if (region.isRect() && region.m_bounds.contains(m_bounds)) {
596 m_shape = region.m_shape;
597 m_bounds = region.m_bounds;
598 return;
599 }
600 // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
601 if (!isRect() && contains(region))
602 return;
603
604 Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
605
606 m_shape.swap(unitedShape);
607 m_bounds.unite(region.m_bounds);
608 }
609
subtract(const Region & region)610 void Region::subtract(const Region& region)
611 {
612 if (m_bounds.isEmpty())
613 return;
614 if (region.isEmpty())
615 return;
616 if (!m_bounds.intersects(region.m_bounds))
617 return;
618
619 Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
620
621 m_shape.swap(subtractedShape);
622 m_bounds = m_shape.bounds();
623 }
624
translate(const IntSize & offset)625 void Region::translate(const IntSize& offset)
626 {
627 m_bounds.move(offset);
628 m_shape.translate(offset);
629 }
630
631 } // namespace blink
632