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