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