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
37namespace WebCore {
38
39Region::Region()
40{
41}
42
43Region::Region(const IntRect& rect)
44    : m_bounds(rect)
45    , m_shape(rect)
46{
47}
48
49Vector<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
68bool 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
76bool 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
104bool 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
112unsigned 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
126template<typename CompareOperation>
127bool 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
210struct Region::Shape::CompareContainsOperation {
211    const static bool defaultResult = true;
212    inline static bool aOutsideB(bool& /* result */) { return false; }
213    inline static bool bOutsideA(bool& result) { result = false; return true; }
214    inline static bool aOverlapsB(bool& /* result */) { return false; }
215};
216
217struct Region::Shape::CompareIntersectsOperation {
218    const static bool defaultResult = false;
219    inline static bool aOutsideB(bool& /* result */) { return false; }
220    inline static bool bOutsideA(bool& /* result */) { return false; }
221    inline static bool aOverlapsB(bool& result) { result = true; return true; }
222};
223
224Region::Shape::Shape()
225{
226}
227
228Region::Shape::Shape(const IntRect& rect)
229{
230    appendSpan(rect.y());
231    appendSegment(rect.x());
232    appendSegment(rect.maxX());
233    appendSpan(rect.maxY());
234}
235
236void Region::Shape::appendSpan(int y)
237{
238    m_spans.append(Span(y, m_segments.size()));
239}
240
241bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
242{
243    if (m_spans.isEmpty())
244        return false;
245
246    SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
247    SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
248
249    // Check if both spans have an equal number of segments.
250    if (lastSpanEnd - lastSpanBegin != end - begin)
251        return false;
252
253    // Check if both spans are equal.
254    if (!std::equal(begin, end, lastSpanBegin))
255        return false;
256
257    // Since the segments are equal the second segment can just be ignored.
258    return true;
259}
260
261void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
262{
263    if (canCoalesce(begin, end))
264        return;
265
266    appendSpan(y);
267    m_segments.appendRange(begin, end);
268}
269
270void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
271{
272    for (SpanIterator it = begin; it != end; ++it)
273        appendSpan(it->y, shape.segmentsBegin(it), shape.segmentsEnd(it));
274}
275
276void Region::Shape::appendSegment(int x)
277{
278    m_segments.append(x);
279}
280
281Region::Shape::SpanIterator Region::Shape::spansBegin() const
282{
283    return m_spans.data();
284}
285
286Region::Shape::SpanIterator Region::Shape::spansEnd() const
287{
288    return m_spans.data() + m_spans.size();
289}
290
291Region::Shape::SegmentIterator Region::Shape::segmentsBegin(SpanIterator it) const
292{
293    ASSERT(it >= m_spans.data());
294    ASSERT(it < m_spans.data() + m_spans.size());
295
296    // Check if this span has any segments.
297    if (it->segmentIndex == m_segments.size())
298        return 0;
299
300    return &m_segments[it->segmentIndex];
301}
302
303Region::Shape::SegmentIterator Region::Shape::segmentsEnd(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    ASSERT(it + 1 < m_spans.data() + m_spans.size());
313    size_t segmentIndex = (it + 1)->segmentIndex;
314
315    ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
316    return m_segments.data() + segmentIndex;
317}
318
319#ifndef NDEBUG
320void Region::Shape::dump() const
321{
322    for (Shape::SpanIterator span = spansBegin(), end = spansEnd(); span != end; ++span) {
323        printf("%6d: (", span->y);
324
325        for (Shape::SegmentIterator segment = segmentsBegin(span), end = segmentsEnd(span); segment != end; ++segment)
326            printf("%d ", *segment);
327        printf(")\n");
328    }
329
330    printf("\n");
331}
332#endif
333
334IntRect Region::Shape::bounds() const
335{
336    if (isEmpty())
337        return IntRect();
338
339    SpanIterator span = spansBegin();
340    int minY = span->y;
341
342    SpanIterator lastSpan = spansEnd() - 1;
343    int maxY = lastSpan->y;
344
345    int minX = std::numeric_limits<int>::max();
346    int maxX = std::numeric_limits<int>::min();
347
348    while (span != lastSpan) {
349        SegmentIterator firstSegment = segmentsBegin(span);
350        SegmentIterator lastSegment = segmentsEnd(span) - 1;
351
352        if (firstSegment && lastSegment) {
353            ASSERT(firstSegment != lastSegment);
354
355            if (*firstSegment < minX)
356                minX = *firstSegment;
357
358            if (*lastSegment > maxX)
359                maxX = *lastSegment;
360        }
361
362        ++span;
363    }
364
365    ASSERT(minX <= maxX);
366    ASSERT(minY <= maxY);
367
368    return IntRect(minX, minY, maxX - minX, maxY - minY);
369}
370
371void Region::Shape::translate(const IntSize& offset)
372{
373    for (size_t i = 0; i < m_segments.size(); ++i)
374        m_segments[i] += offset.width();
375    for (size_t i = 0; i < m_spans.size(); ++i)
376        m_spans[i].y += offset.height();
377}
378
379void Region::Shape::swap(Shape& other)
380{
381    m_segments.swap(other.m_segments);
382    m_spans.swap(other.m_spans);
383}
384
385enum {
386    Shape1,
387    Shape2,
388};
389
390template<typename Operation>
391Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
392{
393    COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
394    COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
395
396    Shape result;
397    if (Operation::trySimpleOperation(shape1, shape2, result))
398        return result;
399
400    SpanIterator spans1 = shape1.spansBegin();
401    SpanIterator spans1End = shape1.spansEnd();
402
403    SpanIterator spans2 = shape2.spansBegin();
404    SpanIterator spans2End = shape2.spansEnd();
405
406    SegmentIterator segments1 = 0;
407    SegmentIterator segments1End = 0;
408
409    SegmentIterator segments2 = 0;
410    SegmentIterator segments2End = 0;
411
412    // Iterate over all spans.
413    while (spans1 != spans1End && spans2 != spans2End) {
414        int y = 0;
415        int test = spans1->y - spans2->y;
416
417        if (test <= 0) {
418            y = spans1->y;
419
420            segments1 = shape1.segmentsBegin(spans1);
421            segments1End = shape1.segmentsEnd(spans1);
422            ++spans1;
423        }
424        if (test >= 0) {
425            y = spans2->y;
426
427            segments2 = shape2.segmentsBegin(spans2);
428            segments2End = shape2.segmentsEnd(spans2);
429            ++spans2;
430        }
431
432        int flag = 0;
433        int oldFlag = 0;
434
435        SegmentIterator s1 = segments1;
436        SegmentIterator s2 = segments2;
437
438        Vector<int, 32> segments;
439
440        // Now iterate over the segments in each span and construct a new vector of segments.
441        while (s1 != segments1End && s2 != segments2End) {
442            int test = *s1 - *s2;
443            int x;
444
445            if (test <= 0) {
446                x = *s1;
447                flag = flag ^ 1;
448                ++s1;
449            }
450            if (test >= 0) {
451                x = *s2;
452                flag = flag ^ 2;
453                ++s2;
454            }
455
456            if (flag == Operation::opCode || oldFlag == Operation::opCode)
457                segments.append(x);
458
459            oldFlag = flag;
460        }
461
462        // Add any remaining segments.
463        if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
464            segments.appendRange(s1, segments1End);
465        else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
466            segments.appendRange(s2, segments2End);
467
468        // Add the span.
469        if (!segments.isEmpty() || !result.isEmpty())
470            result.appendSpan(y, segments.data(), segments.data() + segments.size());
471    }
472
473    // Add any remaining spans.
474    if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
475        result.appendSpans(shape1, spans1, spans1End);
476    else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
477        result.appendSpans(shape2, spans2, spans2End);
478
479    return result;
480}
481
482struct Region::Shape::UnionOperation {
483    static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
484    {
485        if (shape1.isEmpty()) {
486            result = shape2;
487            return true;
488        }
489
490        return false;
491    }
492
493    static const int opCode = 0;
494
495    static const bool shouldAddRemainingSegmentsFromSpan1 = true;
496    static const bool shouldAddRemainingSegmentsFromSpan2 = true;
497    static const bool shouldAddRemainingSpansFromShape1 = true;
498    static const bool shouldAddRemainingSpansFromShape2 = true;
499};
500
501Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
502{
503    return shapeOperation<UnionOperation>(shape1, shape2);
504}
505
506struct Region::Shape::IntersectOperation {
507    static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
508    {
509        return false;
510    }
511
512    static const int opCode = 3;
513
514    static const bool shouldAddRemainingSegmentsFromSpan1 = false;
515    static const bool shouldAddRemainingSegmentsFromSpan2 = false;
516    static const bool shouldAddRemainingSpansFromShape1 = false;
517    static const bool shouldAddRemainingSpansFromShape2 = false;
518};
519
520Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
521{
522    return shapeOperation<IntersectOperation>(shape1, shape2);
523}
524
525struct Region::Shape::SubtractOperation {
526    static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
527    {
528        return false;
529    }
530
531    static const int opCode = 1;
532
533    static const bool shouldAddRemainingSegmentsFromSpan1 = true;
534    static const bool shouldAddRemainingSegmentsFromSpan2 = false;
535    static const bool shouldAddRemainingSpansFromShape1 = true;
536    static const bool shouldAddRemainingSpansFromShape2 = false;
537};
538
539Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
540{
541    return shapeOperation<SubtractOperation>(shape1, shape2);
542}
543
544#ifndef NDEBUG
545void Region::dump() const
546{
547    printf("Bounds: (%d, %d, %d, %d)\n", m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
548    m_shape.dump();
549}
550#endif
551
552void Region::intersect(const Region& region)
553{
554    if (m_bounds.isEmpty())
555        return;
556    if (!m_bounds.intersects(region.m_bounds)) {
557        m_shape = Shape();
558        m_bounds = IntRect();
559        return;
560    }
561
562    Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
563
564    m_shape.swap(intersectedShape);
565    m_bounds = m_shape.bounds();
566}
567
568void Region::unite(const Region& region)
569{
570    if (region.isEmpty())
571        return;
572    if (isRect() && m_bounds.contains(region.m_bounds))
573        return;
574    if (region.isRect() && region.m_bounds.contains(m_bounds)) {
575        m_shape = region.m_shape;
576        m_bounds = region.m_bounds;
577        return;
578    }
579    // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
580    if (!isRect() && contains(region))
581        return;
582
583    Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
584
585    m_shape.swap(unitedShape);
586    m_bounds.unite(region.m_bounds);
587}
588
589void Region::subtract(const Region& region)
590{
591    if (m_bounds.isEmpty())
592        return;
593    if (region.isEmpty())
594        return;
595    if (!m_bounds.intersects(region.m_bounds))
596        return;
597
598    Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
599
600    m_shape.swap(subtractedShape);
601    m_bounds = m_shape.bounds();
602}
603
604void Region::translate(const IntSize& offset)
605{
606    m_bounds.move(offset);
607    m_shape.translate(offset);
608}
609
610} // namespace WebCore
611