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 // A region class based on the paper "Scanline Coherent Shape Algebra" 30 // by Jonathan E. Steinhart from the book "Graphics Gems II". 31 // 32 // This implementation uses two vectors instead of linked list, and 33 // also compresses regions when possible. 34 35 using namespace WebCore; 36 37 namespace WebKit { 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 WebKit 455 456