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