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