Compositing overlap testing can throw layers into compositing when they should not be.
[WebKit-https.git] / Source / WebCore / platform / graphics / Region.cpp
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
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 WebCore {
38
39 Region::Region()
40 {
41 }
42
43 Region::Region(const IntRect& rect)
44     : m_bounds(rect)
45     , m_shape(rect)
46 {
47 }
48
49 Vector<IntRect> Region::rects() const
50 {
51     Vector<IntRect> rects;
52
53     for (Shape::SpanIterator span = m_shape.spans_begin(), end = m_shape.spans_end(); 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.segments_begin(span), end = m_shape.segments_end(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
68 bool Region::contains(const Region& region) const
69 {
70     return WebCore::intersect(region, *this) == region;
71 }
72
73 bool Region::contains(const IntPoint& point) const
74 {
75     // FIXME: This is inefficient. We should be able to iterate over the spans and find
76     // out if the region contains the point.
77     return contains(IntRect(point, IntSize(1, 1)));
78 }
79
80 bool Region::intersects(const Region& region) const
81 {
82     if (!m_bounds.intersects(region.m_bounds))
83         return false;
84
85     // FIXME: this could be optimized.
86     Region tempRegion(*this);
87     tempRegion.intersect(region);
88     return !tempRegion.isEmpty();
89 }
90
91 unsigned Region::totalArea() const
92 {
93     Vector<IntRect> rects = this->rects();
94     size_t size = rects.size();
95     unsigned totalArea = 0;
96
97     for (size_t i = 0; i < size; ++i) {
98         IntRect rect = rects[i];
99         totalArea += (rect.width() * rect.height());
100     }
101
102     return totalArea;
103 }
104
105 Region::Shape::Shape()
106 {
107 }
108
109 Region::Shape::Shape(const IntRect& rect)
110 {
111     appendSpan(rect.y());
112     appendSegment(rect.x());
113     appendSegment(rect.maxX());
114     appendSpan(rect.maxY());
115 }
116
117 void Region::Shape::appendSpan(int y)
118 {
119     m_spans.append(Span(y, m_segments.size()));
120 }
121
122 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
123 {
124     if (m_spans.isEmpty())
125         return false;
126
127     SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
128     SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
129
130     // Check if both spans have an equal number of segments.
131     if (lastSpanEnd - lastSpanBegin != end - begin)
132         return false;
133
134     // Check if both spans are equal.
135     if (!std::equal(begin, end, lastSpanBegin))
136         return false;
137
138     // Since the segments are equal the second segment can just be ignored.
139     return true;
140 }
141
142 void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
143 {
144     if (canCoalesce(begin, end))
145         return;
146   
147     appendSpan(y);
148     m_segments.appendRange(begin, end);
149 }
150
151 void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
152 {
153     for (SpanIterator it = begin; it != end; ++it)
154         appendSpan(it->y, shape.segments_begin(it), shape.segments_end(it));
155 }
156
157 void Region::Shape::appendSegment(int x)
158 {
159     m_segments.append(x);
160 }
161
162 Region::Shape::SpanIterator Region::Shape::spans_begin() const
163 {
164     return m_spans.data();
165 }
166
167 Region::Shape::SpanIterator Region::Shape::spans_end() const
168 {
169     return m_spans.data() + m_spans.size();
170 }
171
172 Region::Shape::SegmentIterator Region::Shape::segments_begin(SpanIterator it) const
173 {
174     ASSERT(it >= m_spans.data());
175     ASSERT(it < m_spans.data() + m_spans.size());
176
177     // Check if this span has any segments.
178     if (it->segmentIndex == m_segments.size())
179         return 0;
180
181     return &m_segments[it->segmentIndex];
182 }
183
184 Region::Shape::SegmentIterator Region::Shape::segments_end(SpanIterator it) const
185 {
186     ASSERT(it >= m_spans.data());
187     ASSERT(it < m_spans.data() + m_spans.size());
188
189     // Check if this span has any segments.
190     if (it->segmentIndex == m_segments.size())
191         return 0;
192
193     ASSERT(it + 1 < m_spans.data() + m_spans.size());
194     size_t segmentIndex = (it + 1)->segmentIndex;
195
196     ASSERT(segmentIndex <= m_segments.size());
197     return m_segments.data() + segmentIndex;
198 }
199
200 #ifndef NDEBUG
201 void Region::Shape::dump() const
202 {
203     for (Shape::SpanIterator span = spans_begin(), end = spans_end(); span != end; ++span) {
204         printf("%6d: (", span->y);
205
206         for (Shape::SegmentIterator segment = segments_begin(span), end = segments_end(span); segment != end; ++segment)
207             printf("%d ", *segment);
208         printf(")\n");
209     }
210
211     printf("\n");
212 }
213 #endif
214
215 IntRect Region::Shape::bounds() const
216 {
217     if (isEmpty())
218         return IntRect();
219
220     SpanIterator span = spans_begin();
221     int minY = span->y;
222
223     SpanIterator lastSpan = spans_end() - 1;
224     int maxY = lastSpan->y;
225
226     int minX = std::numeric_limits<int>::max();
227     int maxX = std::numeric_limits<int>::min();
228
229     while (span != lastSpan) {
230         SegmentIterator firstSegment = segments_begin(span);
231         SegmentIterator lastSegment = segments_end(span) - 1;
232
233         if (firstSegment && lastSegment) {
234             ASSERT(firstSegment != lastSegment);
235
236             if (*firstSegment < minX)
237                 minX = *firstSegment;
238
239             if (*lastSegment > maxX)
240                 maxX = *lastSegment;
241         }
242
243         ++span;
244     }
245
246     ASSERT(minX <= maxX);
247     ASSERT(minY <= maxY);
248
249     return IntRect(minX, minY, maxX - minX, maxY - minY);
250 }
251
252 void Region::Shape::translate(const IntSize& offset)
253 {
254     for (size_t i = 0; i < m_segments.size(); ++i)
255         m_segments[i] += offset.width();
256     for (size_t i = 0; i < m_spans.size(); ++i)
257         m_spans[i].y += offset.height();
258 }
259
260 void Region::Shape::swap(Shape& other)
261 {
262     m_segments.swap(other.m_segments);
263     m_spans.swap(other.m_spans);
264 }
265
266 enum {
267     Shape1,
268     Shape2,
269 };
270
271 template<typename Operation>
272 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
273 {
274     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
275     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
276
277     Shape result;
278     if (Operation::trySimpleOperation(shape1, shape2, result))
279         return result;
280
281     SpanIterator spans1 = shape1.spans_begin();
282     SpanIterator spans1End = shape1.spans_end();
283
284     SpanIterator spans2 = shape2.spans_begin();
285     SpanIterator spans2End = shape2.spans_end();
286
287     SegmentIterator segments1 = 0;
288     SegmentIterator segments1End = 0;
289
290     SegmentIterator segments2 = 0;
291     SegmentIterator segments2End = 0;
292
293     // Iterate over all spans.
294     while (spans1 != spans1End && spans2 != spans2End) {
295         int y = 0;
296         int test = spans1->y - spans2->y;
297
298         if (test <= 0) {
299             y = spans1->y;
300
301             segments1 = shape1.segments_begin(spans1);
302             segments1End = shape1.segments_end(spans1);
303             ++spans1;
304         }
305         if (test >= 0) {
306             y = spans2->y;
307
308             segments2 = shape2.segments_begin(spans2);
309             segments2End = shape2.segments_end(spans2);
310             ++spans2;
311         }
312
313         int flag = 0;
314         int oldFlag = 0;
315
316         SegmentIterator s1 = segments1;
317         SegmentIterator s2 = segments2;
318
319         Vector<int, 32> segments;
320
321         // Now iterate over the segments in each span and construct a new vector of segments.
322         while (s1 != segments1End && s2 != segments2End) {
323             int test = *s1 - *s2;
324             int x;
325
326             if (test <= 0) {
327                 x = *s1;
328                 flag = flag ^ 1;
329                 ++s1;
330             }
331             if (test >= 0) {
332                 x = *s2;
333                 flag = flag ^ 2;
334                 ++s2;
335             }
336
337             if (flag == Operation::opCode || oldFlag == Operation::opCode)
338                 segments.append(x);
339             
340             oldFlag = flag;
341         }
342
343         // Add any remaining segments.
344         if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
345             segments.appendRange(s1, segments1End);
346         else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
347             segments.appendRange(s2, segments2End);
348
349         // Add the span.
350         if (!segments.isEmpty() || !result.isEmpty())
351             result.appendSpan(y, segments.data(), segments.data() + segments.size());
352     }
353
354     // Add any remaining spans.
355     if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
356         result.appendSpans(shape1, spans1, spans1End);
357     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
358         result.appendSpans(shape2, spans2, spans2End);
359
360     return result;
361 }
362
363 struct Region::Shape::UnionOperation {
364     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
365     {
366         if (shape1.isEmpty()) {
367             result = shape2;
368             return true;
369         }
370         
371         if (shape2.isEmpty()) {
372             result = shape1;
373             return true;
374         }
375
376         return false;
377     }
378
379     static const int opCode = 0;
380
381     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
382     static const bool shouldAddRemainingSegmentsFromSpan2 = true;
383     static const bool shouldAddRemainingSpansFromShape1 = true;
384     static const bool shouldAddRemainingSpansFromShape2 = true;
385 };
386
387 Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
388 {
389     return shapeOperation<UnionOperation>(shape1, shape2);
390 }
391
392 struct Region::Shape::IntersectOperation {
393     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
394     {
395         if (shape1.isEmpty()) {
396             result = Shape();
397             return true;
398         }
399
400         if (shape2.isEmpty()) {
401             result = shape1;
402             return true;
403         }
404         
405         return false;
406     }
407     
408     static const int opCode = 3;
409     
410     static const bool shouldAddRemainingSegmentsFromSpan1 = false;
411     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
412     static const bool shouldAddRemainingSpansFromShape1 = false;
413     static const bool shouldAddRemainingSpansFromShape2 = false;
414 };
415
416 Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
417 {
418     return shapeOperation<IntersectOperation>(shape1, shape2);
419 }
420
421 struct Region::Shape::SubtractOperation {
422     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Region::Shape& result)
423     {
424         
425         if (shape1.isEmpty() || shape2.isEmpty()) {
426             result = Shape();
427             return true;
428         }
429         
430         return false;
431     }
432     
433     static const int opCode = 1;
434     
435     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
436     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
437     static const bool shouldAddRemainingSpansFromShape1 = true;
438     static const bool shouldAddRemainingSpansFromShape2 = false;
439 };
440
441 Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
442 {
443     return shapeOperation<SubtractOperation>(shape1, shape2);
444 }
445
446 #ifndef NDEBUG
447 void Region::dump() const
448 {
449     printf("Bounds: (%d, %d, %d, %d)\n",
450            m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
451     m_shape.dump();
452 }
453 #endif
454
455 void Region::intersect(const Region& region)
456 {
457     if (!m_bounds.intersects(region.m_bounds)) {
458         m_shape = Shape();
459         m_bounds = IntRect();
460         return;
461     }
462
463     Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
464
465     m_shape.swap(intersectedShape);
466     m_bounds = m_shape.bounds();
467 }
468
469 void Region::unite(const Region& region)
470 {
471     if (region.isEmpty())
472         return;
473
474     Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
475
476     m_shape.swap(unitedShape);
477     m_bounds.unite(region.m_bounds);
478 }
479
480 void Region::subtract(const Region& region)
481 {
482     Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
483
484     m_shape.swap(subtractedShape);
485     m_bounds = m_shape.bounds();
486 }
487
488 void Region::translate(const IntSize& offset)
489 {
490     m_bounds.move(offset);
491     m_shape.translate(offset);
492 }
493
494 } // namespace WebCore