| // Copyright 2013 The Flutter Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "flutter/display_list/geometry/dl_region.h" |
| |
| #include "flutter/fml/logging.h" |
| |
| namespace flutter { |
| |
| // Threshold for switching from linear search through span lines to binary |
| // search. |
| const int kBinarySearchThreshold = 10; |
| |
| DlRegion::SpanBuffer::SpanBuffer(DlRegion::SpanBuffer&& m) |
| : capacity_(m.capacity_), size_(m.size_), spans_(m.spans_) { |
| m.size_ = 0; |
| m.capacity_ = 0; |
| m.spans_ = nullptr; |
| }; |
| |
| DlRegion::SpanBuffer::SpanBuffer(const DlRegion::SpanBuffer& m) |
| : capacity_(m.capacity_), size_(m.size_) { |
| if (m.spans_ == nullptr) { |
| spans_ = nullptr; |
| } else { |
| spans_ = static_cast<Span*>(std::malloc(capacity_ * sizeof(Span))); |
| memcpy(spans_, m.spans_, size_ * sizeof(Span)); |
| } |
| }; |
| |
| DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=( |
| const DlRegion::SpanBuffer& buffer) { |
| SpanBuffer copy(buffer); |
| std::swap(*this, copy); |
| return *this; |
| } |
| |
| DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=( |
| DlRegion::SpanBuffer&& buffer) { |
| std::swap(capacity_, buffer.capacity_); |
| std::swap(size_, buffer.size_); |
| std::swap(spans_, buffer.spans_); |
| return *this; |
| } |
| |
| DlRegion::SpanBuffer::~SpanBuffer() { |
| free(spans_); |
| } |
| |
| void DlRegion::SpanBuffer::reserve(size_t capacity) { |
| if (capacity_ < capacity) { |
| spans_ = static_cast<Span*>(std::realloc(spans_, capacity * sizeof(Span))); |
| capacity_ = capacity; |
| } |
| } |
| |
| DlRegion::SpanChunkHandle DlRegion::SpanBuffer::storeChunk(const Span* begin, |
| const Span* end) { |
| size_t chunk_size = end - begin; |
| size_t min_capacity = size_ + chunk_size + 1; |
| if (capacity_ < min_capacity) { |
| size_t new_capacity = std::max(min_capacity, capacity_ * 2); |
| new_capacity = std::max(new_capacity, size_t(512)); |
| reserve(new_capacity); |
| } |
| SpanChunkHandle res = size_; |
| size_ += chunk_size + 1; |
| setChunkSize(res, chunk_size); |
| |
| auto* dst = spans_ + res + 1; |
| memmove(dst, begin, chunk_size * sizeof(Span)); |
| |
| return res; |
| } |
| |
| size_t DlRegion::SpanBuffer::getChunkSize(SpanChunkHandle handle) const { |
| FML_DCHECK(handle < size_); |
| return spans_[handle].left; |
| } |
| |
| void DlRegion::SpanBuffer::setChunkSize(SpanChunkHandle handle, size_t size) { |
| FML_DCHECK(handle < size_); |
| FML_DCHECK(spans_ != nullptr); |
| // NOLINTNEXTLINE(clang-analyzer-core.NullDereference) |
| spans_[handle].left = size; |
| } |
| |
| void DlRegion::SpanBuffer::getSpans(SpanChunkHandle handle, |
| const DlRegion::Span*& begin, |
| const DlRegion::Span*& end) const { |
| FML_DCHECK(handle < size_); |
| begin = spans_ + handle + 1; |
| end = begin + getChunkSize(handle); |
| } |
| |
| DlRegion::DlRegion(const std::vector<SkIRect>& rects) { |
| setRects(rects); |
| } |
| |
| DlRegion::DlRegion(const SkIRect& rect) : bounds_(rect) { |
| Span span{rect.left(), rect.right()}; |
| lines_.push_back(makeLine(rect.top(), rect.bottom(), &span, &span + 1)); |
| } |
| |
| bool DlRegion::spansEqual(SpanLine& line, |
| const Span* begin, |
| const Span* end) const { |
| const Span *our_begin, *our_end; |
| span_buffer_.getSpans(line.chunk_handle, our_begin, our_end); |
| size_t our_size = our_end - our_begin; |
| size_t their_size = end - begin; |
| if (our_size != their_size) { |
| return false; |
| } |
| |
| return memcmp(our_begin, begin, our_size * sizeof(Span)) == 0; |
| } |
| |
| DlRegion::SpanLine DlRegion::makeLine(int32_t top, |
| int32_t bottom, |
| const SpanVec& v) { |
| return makeLine(top, bottom, v.data(), v.data() + v.size()); |
| } |
| |
| DlRegion::SpanLine DlRegion::makeLine(int32_t top, |
| int32_t bottom, |
| const Span* begin, |
| const Span* end) { |
| auto handle = span_buffer_.storeChunk(begin, end); |
| return {top, bottom, handle}; |
| } |
| |
| // Returns number of valid spans in res. For performance reasons res is never |
| // downsized. |
| size_t DlRegion::unionLineSpans(std::vector<Span>& res, |
| const SpanBuffer& a_buffer, |
| SpanChunkHandle a_handle, |
| const SpanBuffer& b_buffer, |
| SpanChunkHandle b_handle) { |
| class OrderedSpanAccumulator { |
| public: |
| explicit OrderedSpanAccumulator(std::vector<Span>& res) : res(res) {} |
| |
| void accumulate(const Span& span) { |
| if (span.left > last_ || len == 0) { |
| res[len++] = span; |
| last_ = span.right; |
| } else if (span.right > last_) { |
| FML_DCHECK(len > 0); |
| res[len - 1].right = span.right; |
| last_ = span.right; |
| } |
| } |
| |
| size_t len = 0; |
| std::vector<Span>& res; |
| |
| private: |
| int32_t last_ = std::numeric_limits<int32_t>::min(); |
| }; |
| |
| const Span *begin1, *end1; |
| a_buffer.getSpans(a_handle, begin1, end1); |
| |
| const Span *begin2, *end2; |
| b_buffer.getSpans(b_handle, begin2, end2); |
| |
| size_t min_size = (end1 - begin1) + (end2 - begin2); |
| if (res.size() < min_size) { |
| res.resize(min_size); |
| } |
| |
| OrderedSpanAccumulator accumulator(res); |
| |
| while (true) { |
| if (begin1->left < begin2->left) { |
| accumulator.accumulate(*begin1++); |
| if (begin1 == end1) { |
| break; |
| } |
| } else { |
| // Either 2 is first, or they are equal, in which case add 2 now |
| // and we might combine 1 with it next time around |
| accumulator.accumulate(*begin2++); |
| if (begin2 == end2) { |
| break; |
| } |
| } |
| } |
| |
| FML_DCHECK(begin1 == end1 || begin2 == end2); |
| |
| while (begin1 < end1) { |
| accumulator.accumulate(*begin1++); |
| } |
| while (begin2 < end2) { |
| accumulator.accumulate(*begin2++); |
| } |
| |
| FML_DCHECK(begin1 == end1 && begin2 == end2); |
| |
| return accumulator.len; |
| } |
| |
| size_t DlRegion::intersectLineSpans(std::vector<Span>& res, |
| const SpanBuffer& a_buffer, |
| SpanChunkHandle a_handle, |
| const SpanBuffer& b_buffer, |
| SpanChunkHandle b_handle) { |
| const Span *begin1, *end1; |
| a_buffer.getSpans(a_handle, begin1, end1); |
| |
| const Span *begin2, *end2; |
| b_buffer.getSpans(b_handle, begin2, end2); |
| |
| // Worst case scenario, interleaved overlapping spans |
| // AAAA BBBB CCCC |
| // XXX YYYY XXXX |
| size_t min_size = (end1 - begin1) + (end2 - begin2) - 1; |
| if (res.size() < min_size) { |
| res.resize(min_size); |
| } |
| |
| // Pointer to the next span to be written. |
| Span* new_span = res.data(); |
| |
| while (begin1 != end1 && begin2 != end2) { |
| if (begin1->right <= begin2->left) { |
| ++begin1; |
| } else if (begin2->right <= begin1->left) { |
| ++begin2; |
| } else { |
| int32_t left = std::max(begin1->left, begin2->left); |
| int32_t right = std::min(begin1->right, begin2->right); |
| FML_DCHECK(left < right); |
| FML_DCHECK(new_span < res.data() + res.size()); |
| *new_span++ = {left, right}; |
| if (begin1->right == right) { |
| ++begin1; |
| } |
| if (begin2->right == right) { |
| ++begin2; |
| } |
| } |
| } |
| |
| return new_span - res.data(); |
| } |
| |
| void DlRegion::setRects(const std::vector<SkIRect>& unsorted_rects) { |
| // setRects can only be called on empty regions. |
| FML_DCHECK(lines_.empty()); |
| |
| size_t count = unsorted_rects.size(); |
| std::vector<const SkIRect*> rects(count); |
| for (size_t i = 0; i < count; i++) { |
| rects[i] = &unsorted_rects[i]; |
| bounds_.join(unsorted_rects[i]); |
| } |
| std::sort(rects.begin(), rects.end(), [](const SkIRect* a, const SkIRect* b) { |
| if (a->top() < b->top()) { |
| return true; |
| } |
| if (a->top() > b->top()) { |
| return false; |
| } |
| return a->left() < b->left(); |
| }); |
| |
| size_t active_end = 0; |
| size_t next_rect = 0; |
| int32_t cur_y = std::numeric_limits<int32_t>::min(); |
| SpanVec working_spans; |
| |
| #ifdef DlRegion_DO_STATS |
| size_t active_rect_count = 0; |
| size_t span_count = 0; |
| int pass_count = 0; |
| int line_count = 0; |
| #endif |
| |
| while (next_rect < count || active_end > 0) { |
| // First prune passed rects out of the active list |
| size_t preserve_end = 0; |
| for (size_t i = 0; i < active_end; i++) { |
| const SkIRect* r = rects[i]; |
| if (r->bottom() > cur_y) { |
| rects[preserve_end++] = r; |
| } |
| } |
| active_end = preserve_end; |
| |
| // If we have no active rects any more, jump to the top of the |
| // next available input rect. |
| if (active_end == 0) { |
| if (next_rect >= count) { |
| // No active rects and no more rects to bring in. We are done. |
| break; |
| } |
| cur_y = rects[next_rect]->top(); |
| } |
| |
| // Next, insert any new rects we've reached into the active list |
| while (next_rect < count) { |
| const SkIRect* r = rects[next_rect]; |
| if (r->isEmpty()) { |
| continue; |
| } |
| if (r->top() > cur_y) { |
| break; |
| } |
| // We now know that we will be inserting this rect into active list |
| next_rect++; |
| size_t insert_at = active_end++; |
| while (insert_at > 0) { |
| const SkIRect* ir = rects[insert_at - 1]; |
| if (ir->left() <= r->left()) { |
| break; |
| } |
| rects[insert_at--] = ir; |
| } |
| rects[insert_at] = r; |
| } |
| |
| // We either preserved some rects in the active list or added more from |
| // the remaining input rects, or we would have exited the loop above. |
| FML_DCHECK(active_end != 0); |
| working_spans.clear(); |
| FML_DCHECK(working_spans.empty()); |
| |
| #ifdef DlRegion_DO_STATS |
| active_rect_count += active_end; |
| pass_count++; |
| #endif |
| |
| // [start_x, end_x) always represents a valid span to be inserted |
| // [cur_y, end_y) is the intersecting range over which all spans are valid |
| int32_t start_x = rects[0]->left(); |
| int32_t end_x = rects[0]->right(); |
| int32_t end_y = rects[0]->bottom(); |
| for (size_t i = 1; i < active_end; i++) { |
| const SkIRect* r = rects[i]; |
| if (r->left() > end_x) { |
| working_spans.emplace_back(start_x, end_x); |
| start_x = r->left(); |
| end_x = r->right(); |
| } else if (end_x < r->right()) { |
| end_x = r->right(); |
| } |
| if (end_y > r->bottom()) { |
| end_y = r->bottom(); |
| } |
| } |
| working_spans.emplace_back(start_x, end_x); |
| |
| // end_y must not pass by the top of the next input rect |
| if (next_rect < count && end_y > rects[next_rect]->top()) { |
| end_y = rects[next_rect]->top(); |
| } |
| |
| // If all of the rules above work out, we should never collapse the |
| // current range of Y coordinates to empty |
| FML_DCHECK(end_y > cur_y); |
| |
| if (!lines_.empty() && lines_.back().bottom == cur_y && |
| spansEqual(lines_.back(), working_spans.data(), |
| working_spans.data() + working_spans.size())) { |
| lines_.back().bottom = end_y; |
| } else { |
| #ifdef DlRegion_DO_STATS |
| span_count += working_spans.size(); |
| line_count++; |
| #endif |
| lines_.push_back(makeLine(cur_y, end_y, working_spans)); |
| } |
| cur_y = end_y; |
| } |
| |
| #ifdef DlRegion_DO_STATS |
| double span_avg = ((double)span_count) / line_count; |
| double active_avg = ((double)active_rect_count) / pass_count; |
| FML_LOG(ERROR) << lines_.size() << " lines for " << count |
| << " input rects, avg " << span_avg |
| << " spans per line and avg " << active_avg |
| << " active rects per loop"; |
| #endif |
| } |
| |
| void DlRegion::appendLine(int32_t top, |
| int32_t bottom, |
| const Span* begin, |
| const Span* end) { |
| if (lines_.empty()) { |
| lines_.push_back(makeLine(top, bottom, begin, end)); |
| } else { |
| if (lines_.back().bottom == top && spansEqual(lines_.back(), begin, end)) { |
| lines_.back().bottom = bottom; |
| } else { |
| lines_.push_back(makeLine(top, bottom, begin, end)); |
| } |
| } |
| } |
| |
| DlRegion DlRegion::MakeUnion(const DlRegion& a, const DlRegion& b) { |
| if (a.isEmpty()) { |
| return b; |
| } else if (b.isEmpty()) { |
| return a; |
| } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) { |
| return a; |
| } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) { |
| return b; |
| } |
| |
| DlRegion res; |
| res.bounds_ = a.bounds_; |
| res.bounds_.join(b.bounds_); |
| res.span_buffer_.reserve(a.span_buffer_.capacity() + |
| b.span_buffer_.capacity()); |
| |
| auto& lines = res.lines_; |
| lines.reserve(a.lines_.size() + b.lines_.size()); |
| |
| auto a_it = a.lines_.begin(); |
| auto b_it = b.lines_.begin(); |
| auto a_end = a.lines_.end(); |
| auto b_end = b.lines_.end(); |
| |
| FML_DCHECK(a_it != a_end && b_it != b_end); |
| |
| auto& a_buffer = a.span_buffer_; |
| auto& b_buffer = b.span_buffer_; |
| |
| std::vector<Span> tmp; |
| |
| int32_t cur_top = std::numeric_limits<int32_t>::min(); |
| |
| while (a_it != a_end && b_it != b_end) { |
| auto a_top = std::max(cur_top, a_it->top); |
| auto b_top = std::max(cur_top, b_it->top); |
| if (a_it->bottom <= b_top) { |
| res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle); |
| ++a_it; |
| } else if (b_it->bottom <= a_top) { |
| res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle); |
| ++b_it; |
| } else { |
| if (a_top < b_top) { |
| res.appendLine(a_top, b_top, a_buffer, a_it->chunk_handle); |
| cur_top = b_top; |
| if (cur_top == a_it->bottom) { |
| ++a_it; |
| } |
| } else if (b_top < a_top) { |
| res.appendLine(b_top, a_top, b_buffer, b_it->chunk_handle); |
| cur_top = a_top; |
| if (cur_top == b_it->bottom) { |
| ++b_it; |
| } |
| } else { |
| auto new_bottom = std::min(a_it->bottom, b_it->bottom); |
| FML_DCHECK(a_top == b_top); |
| FML_DCHECK(new_bottom > a_top); |
| FML_DCHECK(new_bottom > b_top); |
| auto size = unionLineSpans(tmp, a_buffer, a_it->chunk_handle, b_buffer, |
| b_it->chunk_handle); |
| res.appendLine(a_top, new_bottom, tmp.data(), tmp.data() + size); |
| cur_top = new_bottom; |
| if (cur_top == a_it->bottom) { |
| ++a_it; |
| } |
| if (cur_top == b_it->bottom) { |
| ++b_it; |
| } |
| } |
| } |
| } |
| |
| FML_DCHECK(a_it == a_end || b_it == b_end); |
| |
| while (a_it != a_end) { |
| auto a_top = std::max(cur_top, a_it->top); |
| res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle); |
| ++a_it; |
| } |
| |
| while (b_it != b_end) { |
| auto b_top = std::max(cur_top, b_it->top); |
| res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle); |
| ++b_it; |
| } |
| |
| return res; |
| } |
| |
| DlRegion DlRegion::MakeIntersection(const DlRegion& a, const DlRegion& b) { |
| if (!SkIRect::Intersects(a.bounds_, b.bounds_)) { |
| return DlRegion(); |
| } else if (a.isSimple() && b.isSimple()) { |
| SkIRect r(a.bounds_); |
| auto res = r.intersect(b.bounds_); |
| (void)res; // Suppress unused variable warning in release builds. |
| FML_DCHECK(res); |
| return DlRegion(r); |
| } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) { |
| return b; |
| } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) { |
| return a; |
| } |
| |
| DlRegion res; |
| res.span_buffer_.reserve( |
| std::max(a.span_buffer_.capacity(), b.span_buffer_.capacity())); |
| |
| auto& lines = res.lines_; |
| lines.reserve(std::min(a.lines_.size(), b.lines_.size())); |
| |
| std::vector<SpanLine>::const_iterator a_it, b_it; |
| getIntersectionIterators(a.lines_, b.lines_, a_it, b_it); |
| |
| auto a_end = a.lines_.end(); |
| auto b_end = b.lines_.end(); |
| |
| auto& a_buffer = a.span_buffer_; |
| auto& b_buffer = b.span_buffer_; |
| |
| std::vector<Span> tmp; |
| |
| int32_t cur_top = std::numeric_limits<int32_t>::min(); |
| |
| while (a_it != a_end && b_it != b_end) { |
| auto a_top = std::max(cur_top, a_it->top); |
| auto b_top = std::max(cur_top, b_it->top); |
| if (a_it->bottom <= b_top) { |
| ++a_it; |
| } else if (b_it->bottom <= a_top) { |
| ++b_it; |
| } else { |
| auto top = std::max(a_top, b_top); |
| auto bottom = std::min(a_it->bottom, b_it->bottom); |
| FML_DCHECK(top < bottom); |
| auto size = intersectLineSpans(tmp, a_buffer, a_it->chunk_handle, |
| b_buffer, b_it->chunk_handle); |
| if (size > 0) { |
| res.appendLine(top, bottom, tmp.data(), tmp.data() + size); |
| res.bounds_.join(SkIRect::MakeLTRB( |
| tmp.data()->left, top, (tmp.data() + size - 1)->right, bottom)); |
| } |
| cur_top = bottom; |
| if (cur_top == a_it->bottom) { |
| ++a_it; |
| } |
| if (cur_top == b_it->bottom) { |
| ++b_it; |
| } |
| } |
| } |
| FML_DCHECK(a_it == a_end || b_it == b_end); |
| return res; |
| } |
| |
| std::vector<SkIRect> DlRegion::getRects(bool deband) const { |
| std::vector<SkIRect> rects; |
| if (isEmpty()) { |
| return rects; |
| } else if (isSimple()) { |
| rects.push_back(bounds_); |
| return rects; |
| } |
| |
| size_t rect_count = 0; |
| size_t previous_span_end = 0; |
| for (const auto& line : lines_) { |
| rect_count += span_buffer_.getChunkSize(line.chunk_handle); |
| } |
| rects.reserve(rect_count); |
| |
| for (const auto& line : lines_) { |
| const Span *span_begin, *span_end; |
| span_buffer_.getSpans(line.chunk_handle, span_begin, span_end); |
| for (const auto* span = span_begin; span < span_end; ++span) { |
| SkIRect rect{span->left, line.top, span->right, line.bottom}; |
| if (deband) { |
| auto iter = rects.begin() + previous_span_end; |
| // If there is rectangle previously in rects on which this one is a |
| // vertical continuation, remove the previous rectangle and expand |
| // this one vertically to cover the area. |
| while (iter != rects.begin()) { |
| --iter; |
| if (iter->bottom() < rect.top()) { |
| // Went all the way to previous span line. |
| break; |
| } else if (iter->left() == rect.left() && |
| iter->right() == rect.right()) { |
| FML_DCHECK(iter->bottom() == rect.top()); |
| rect.fTop = iter->fTop; |
| rects.erase(iter); |
| --previous_span_end; |
| break; |
| } |
| } |
| } |
| rects.push_back(rect); |
| } |
| previous_span_end = rects.size(); |
| } |
| return rects; |
| } |
| |
| bool DlRegion::isComplex() const { |
| return lines_.size() > 1 || |
| (lines_.size() == 1 && |
| span_buffer_.getChunkSize(lines_.front().chunk_handle) > 1); |
| } |
| |
| bool DlRegion::intersects(const SkIRect& rect) const { |
| if (isEmpty()) { |
| return false; |
| } |
| |
| auto bounds_intersect = SkIRect::Intersects(bounds_, rect); |
| |
| if (isSimple()) { |
| return bounds_intersect; |
| } |
| |
| if (!bounds_intersect) { |
| return false; |
| } |
| |
| auto it = lines_.begin(); |
| auto end = lines_.end(); |
| if (lines_.size() > kBinarySearchThreshold && |
| it[kBinarySearchThreshold].bottom <= rect.fTop) { |
| it = std::lower_bound( |
| lines_.begin() + kBinarySearchThreshold + 1, lines_.end(), rect.fTop, |
| [](const SpanLine& line, int32_t top) { return line.bottom <= top; }); |
| } else { |
| while (it != end && it->bottom <= rect.fTop) { |
| ++it; |
| continue; |
| } |
| } |
| while (it != end && it->top < rect.fBottom) { |
| FML_DCHECK(rect.fTop < it->bottom && it->top < rect.fBottom); |
| const Span *begin, *end; |
| span_buffer_.getSpans(it->chunk_handle, begin, end); |
| while (begin != end && begin->left < rect.fRight) { |
| if (begin->right > rect.fLeft) { |
| return true; |
| } |
| ++begin; |
| } |
| ++it; |
| } |
| |
| return false; |
| } |
| |
| bool DlRegion::spansIntersect(const Span* begin1, |
| const Span* end1, |
| const Span* begin2, |
| const Span* end2) { |
| while (begin1 != end1 && begin2 != end2) { |
| if (begin1->right <= begin2->left) { |
| ++begin1; |
| } else if (begin2->right <= begin1->left) { |
| ++begin2; |
| } else { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| void DlRegion::getIntersectionIterators( |
| const std::vector<SpanLine>& a_lines, |
| const std::vector<SpanLine>& b_lines, |
| std::vector<SpanLine>::const_iterator& a_it, |
| std::vector<SpanLine>::const_iterator& b_it) { |
| a_it = a_lines.begin(); |
| auto a_end = a_lines.end(); |
| b_it = b_lines.begin(); |
| auto b_end = b_lines.end(); |
| |
| FML_DCHECK(a_it != a_end && b_it != b_end); |
| |
| auto a_len = a_end - a_it; |
| auto b_len = b_end - b_it; |
| |
| if (a_len > kBinarySearchThreshold && |
| a_it[kBinarySearchThreshold].bottom <= b_it->top) { |
| a_it = std::lower_bound( |
| a_lines.begin() + kBinarySearchThreshold + 1, a_lines.end(), b_it->top, |
| [](const SpanLine& line, int32_t top) { return line.bottom <= top; }); |
| } else if (b_len > kBinarySearchThreshold && |
| b_it[kBinarySearchThreshold].bottom <= a_it->top) { |
| b_it = std::lower_bound( |
| b_lines.begin() + kBinarySearchThreshold + 1, b_lines.end(), a_it->top, |
| [](const SpanLine& line, int32_t top) { return line.bottom <= top; }); |
| } |
| } |
| |
| bool DlRegion::intersects(const DlRegion& region) const { |
| if (isEmpty() || region.isEmpty()) { |
| return false; |
| } |
| |
| auto our_complex = isComplex(); |
| auto their_complex = region.isComplex(); |
| auto bounds_intersect = SkIRect::Intersects(bounds_, region.bounds_); |
| |
| if (!our_complex && !their_complex) { |
| return bounds_intersect; |
| } |
| |
| if (!bounds_intersect) { |
| return false; |
| } |
| |
| if (!our_complex) { |
| return region.intersects(bounds_); |
| } |
| |
| if (!their_complex) { |
| return intersects(region.bounds_); |
| } |
| |
| std::vector<SpanLine>::const_iterator ours, theirs; |
| getIntersectionIterators(lines_, region.lines_, ours, theirs); |
| auto ours_end = lines_.end(); |
| auto theirs_end = region.lines_.end(); |
| |
| while (ours != ours_end && theirs != theirs_end) { |
| if (ours->bottom <= theirs->top) { |
| ++ours; |
| } else if (theirs->bottom <= ours->top) { |
| ++theirs; |
| } else { |
| FML_DCHECK(ours->top < theirs->bottom && theirs->top < ours->bottom); |
| const Span *ours_begin, *ours_end; |
| span_buffer_.getSpans(ours->chunk_handle, ours_begin, ours_end); |
| const Span *theirs_begin, *theirs_end; |
| region.span_buffer_.getSpans(theirs->chunk_handle, theirs_begin, |
| theirs_end); |
| if (spansIntersect(ours_begin, ours_end, theirs_begin, theirs_end)) { |
| return true; |
| } |
| if (ours->bottom < theirs->bottom) { |
| ++ours; |
| } else { |
| ++theirs; |
| } |
| } |
| } |
| return false; |
| } |
| |
| } // namespace flutter |