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