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
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.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
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.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
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.spans_begin();
132    Shape::SpanIterator aSpanEnd = aShape.spans_end();
133    Shape::SpanIterator bSpan = bShape.spans_begin();
134    Shape::SpanIterator bSpanEnd = bShape.spans_end();
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.segments_begin(aSpan);
145        Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan);
146        Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan);
147        Shape::SegmentIterator bSegmentEnd = bShape.segments_end(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.segments_begin(it), shape.segments_end(it));
274}
275
276void Region::Shape::appendSegment(int x)
277{
278    m_segments.append(x);
279}
280
281Region::Shape::SpanIterator Region::Shape::spans_begin() const
282{
283    return m_spans.data();
284}
285
286Region::Shape::SpanIterator Region::Shape::spans_end() const
287{
288    return m_spans.data() + m_spans.size();
289}
290
291Region::Shape::SegmentIterator Region::Shape::segments_begin(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::segments_end(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 (auto span = spans_begin(), end = spans_end(); span != end; ++span) {
323        printf("%6d: (", span->y);
324
325        for (auto segment = segments_begin(span), end = segments_end(span); segment != end; ++segment)
326            printf("%d ", *segment);
327        printf(")\n");
328    }
329
330    printf("\n");
331}
332#endif
333
334bool Region::Shape::isValid() const
335{
336    for (auto span = spans_begin(), end = spans_end(); span != end && span + 1 != end; ++span) {
337        int y = span->y;
338        int height = (span + 1)->y - y;
339
340        if (height < 0)
341            return false;
342
343        for (auto segment = segments_begin(span), end = segments_end(span); segment != end && segment + 1 != end; segment += 2) {
344            int x = *segment;
345            int width = *(segment + 1) - x;
346
347            if (width < 0)
348                return false;
349        }
350    }
351
352    return true;
353}
354
355IntRect Region::Shape::bounds() const
356{
357    if (isEmpty())
358        return IntRect();
359
360    SpanIterator span = spans_begin();
361    int minY = span->y;
362
363    SpanIterator lastSpan = spans_end() - 1;
364    int maxY = lastSpan->y;
365
366    int minX = std::numeric_limits<int>::max();
367    int maxX = std::numeric_limits<int>::min();
368
369    while (span != lastSpan) {
370        SegmentIterator firstSegment = segments_begin(span);
371        SegmentIterator lastSegment = segments_end(span) - 1;
372
373        if (firstSegment && lastSegment) {
374            ASSERT(firstSegment != lastSegment);
375
376            if (*firstSegment < minX)
377                minX = *firstSegment;
378
379            if (*lastSegment > maxX)
380                maxX = *lastSegment;
381        }
382
383        ++span;
384    }
385
386    ASSERT(minX <= maxX);
387    ASSERT(minY <= maxY);
388
389    return IntRect(minX, minY, maxX - minX, maxY - minY);
390}
391
392void Region::Shape::translate(const IntSize& offset)
393{
394    for (size_t i = 0; i < m_segments.size(); ++i)
395        m_segments[i] += offset.width();
396    for (size_t i = 0; i < m_spans.size(); ++i)
397        m_spans[i].y += offset.height();
398}
399
400void Region::Shape::swap(Shape& other)
401{
402    m_segments.swap(other.m_segments);
403    m_spans.swap(other.m_spans);
404}
405
406enum {
407    Shape1,
408    Shape2,
409};
410
411template<typename Operation>
412Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
413{
414    COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
415    COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
416
417    Shape result;
418    if (Operation::trySimpleOperation(shape1, shape2, result))
419        return result;
420
421    SpanIterator spans1 = shape1.spans_begin();
422    SpanIterator spans1End = shape1.spans_end();
423
424    SpanIterator spans2 = shape2.spans_begin();
425    SpanIterator spans2End = shape2.spans_end();
426
427    SegmentIterator segments1 = 0;
428    SegmentIterator segments1End = 0;
429
430    SegmentIterator segments2 = 0;
431    SegmentIterator segments2End = 0;
432
433    // Iterate over all spans.
434    while (spans1 != spans1End && spans2 != spans2End) {
435        int y = 0;
436        int test = spans1->y - spans2->y;
437
438        if (test <= 0) {
439            y = spans1->y;
440
441            segments1 = shape1.segments_begin(spans1);
442            segments1End = shape1.segments_end(spans1);
443            ++spans1;
444        }
445        if (test >= 0) {
446            y = spans2->y;
447
448            segments2 = shape2.segments_begin(spans2);
449            segments2End = shape2.segments_end(spans2);
450            ++spans2;
451        }
452
453        int flag = 0;
454        int oldFlag = 0;
455
456        SegmentIterator s1 = segments1;
457        SegmentIterator s2 = segments2;
458
459        Vector<int, 32> segments;
460
461        // Now iterate over the segments in each span and construct a new vector of segments.
462        while (s1 != segments1End && s2 != segments2End) {
463            int test = *s1 - *s2;
464            int x;
465
466            if (test <= 0) {
467                x = *s1;
468                flag = flag ^ 1;
469                ++s1;
470            }
471            if (test >= 0) {
472                x = *s2;
473                flag = flag ^ 2;
474                ++s2;
475            }
476
477            if (flag == Operation::opCode || oldFlag == Operation::opCode)
478                segments.append(x);
479
480            oldFlag = flag;
481        }
482
483        // Add any remaining segments.
484        if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
485            segments.appendRange(s1, segments1End);
486        else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
487            segments.appendRange(s2, segments2End);
488
489        // Add the span.
490        if (!segments.isEmpty() || !result.isEmpty())
491            result.appendSpan(y, segments.data(), segments.data() + segments.size());
492    }
493
494    // Add any remaining spans.
495    if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
496        result.appendSpans(shape1, spans1, spans1End);
497    else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
498        result.appendSpans(shape2, spans2, spans2End);
499
500    return result;
501}
502
503struct Region::Shape::UnionOperation {
504    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
522Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
523{
524    return shapeOperation<UnionOperation>(shape1, shape2);
525}
526
527struct Region::Shape::IntersectOperation {
528    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
541Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
542{
543    return shapeOperation<IntersectOperation>(shape1, shape2);
544}
545
546struct Region::Shape::SubtractOperation {
547    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
560Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
561{
562    return shapeOperation<SubtractOperation>(shape1, shape2);
563}
564
565#ifndef NDEBUG
566void Region::dump() const
567{
568    printf("Bounds: (%d, %d, %d, %d)\n",
569           m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
570    m_shape.dump();
571}
572#endif
573
574void Region::updateBoundsFromShape()
575{
576    m_bounds = m_shape.bounds();
577}
578
579void Region::intersect(const Region& region)
580{
581    if (m_bounds.isEmpty())
582        return;
583    if (!m_bounds.intersects(region.m_bounds)) {
584        m_shape = Shape();
585        m_bounds = IntRect();
586        return;
587    }
588
589    Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
590
591    m_shape.swap(intersectedShape);
592    m_bounds = m_shape.bounds();
593}
594
595void Region::unite(const Region& region)
596{
597    if (region.isEmpty())
598        return;
599    if (isRect() && m_bounds.contains(region.m_bounds))
600        return;
601    if (region.isRect() && region.m_bounds.contains(m_bounds)) {
602        m_shape = region.m_shape;
603        m_bounds = region.m_bounds;
604        return;
605    }
606    // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
607    if (!isRect() && contains(region))
608        return;
609
610    Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
611
612    m_shape.swap(unitedShape);
613    m_bounds.unite(region.m_bounds);
614}
615
616void Region::subtract(const Region& region)
617{
618    if (m_bounds.isEmpty())
619        return;
620    if (region.isEmpty())
621        return;
622    if (!m_bounds.intersects(region.m_bounds))
623        return;
624
625    Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
626
627    m_shape.swap(subtractedShape);
628    m_bounds = m_shape.bounds();
629}
630
631void Region::translate(const IntSize& offset)
632{
633    m_bounds.move(offset);
634    m_shape.translate(offset);
635}
636
637} // namespace WebCore
638