flutter::DlRegion Class Reference

#include <dl_region.h>

Public Member Functions
	DlRegion ()=default
	Creates an empty region.
	DlRegion (const std::vector< DlIRect > &rects)
	DlRegion (const DlIRect &rect)
	Creates region covering area of a rectangle.
	DlRegion (const DlRegion &)=default
	DlRegion (DlRegion &&)=default
DlRegion &	operator= (const DlRegion &)=default
DlRegion &	operator= (DlRegion &&)=default
std::vector< DlIRect >	getRects (bool deband=true) const
const DlIRect &	bounds () const
bool	intersects (const DlIRect &rect) const
	Returns whether this region intersects with a rectangle.
bool	intersects (const DlRegion &region) const
	Returns whether this region intersects with another region.
bool	isEmpty () const
	Returns true if region is empty (contains no rectangles).
bool	isComplex () const
	Returns true if region is not empty and contains more than one rectangle.
bool	isSimple () const

Static Public Member Functions
static DlRegion	MakeUnion (const DlRegion &a, const DlRegion &b)
static DlRegion	MakeIntersection (const DlRegion &a, const DlRegion &b)

Detailed Description

Represents a region as a collection of non-overlapping rectangles. Implements a subset of SkRegion functionality optimized for quickly converting set of overlapping rectangles to non-overlapping rectangles.

Definition at line 18 of file dl_region.h.

Constructor & Destructor Documentation

DlRegion() [1/5]

flutter::DlRegion::DlRegion ( )

default

Creates an empty region.

DlRegion() [2/5]

flutter::DlRegion::DlRegion ( const std::vector< DlIRect > &  rects )

explicit

Creates region by bulk adding the rectangles. Matches SkRegion::op(rect, SkRegion::kUnion_Op) behavior.

Definition at line 97 of file dl_region.cc.

                                                  {
  setRects(rects);
}

DlRegion() [3/5]

flutter::DlRegion::DlRegion ( const DlIRect &  rect )

explicit

Creates region covering area of a rectangle.

Definition at line 101 of file dl_region.cc.

                                      : bounds_(rect) {
  Span span{rect.GetLeft(), rect.GetRight()};
  lines_.push_back(makeLine(rect.GetTop(), rect.GetBottom(), &span, &span + 1));
}

References impeller::TRect< T >::GetBottom(), impeller::TRect< T >::GetLeft(), impeller::TRect< T >::GetRight(), and impeller::TRect< T >::GetTop().

DlRegion() [4/5]

flutter::DlRegion::DlRegion ( const DlRegion &  )

default

DlRegion() [5/5]

flutter::DlRegion::DlRegion ( DlRegion &&  )

default

Member Function Documentation

bounds()

const DlIRect & flutter::DlRegion::bounds ( ) const

inline

Returns maximum and minimum axis values of rectangles in this region. If region is empty returns SKIRect::MakeEmpty().

Definition at line 53 of file dl_region.h.

{ return bounds_; }

Referenced by flutter::testing::CheckEquality().

getRects()

std::vector< DlIRect > flutter::DlRegion::getRects

(

bool

deband = true

)

const

Returns list of non-overlapping rectangles that cover current region. If |deband| is false, each span line will result in separate rectangles, closely matching SkRegion::Iterator behavior. If |deband| is true, matching rectangles from adjacent span lines will be merged into single rectangle.

Definition at line 560 of file dl_region.cc.

                                                       {
  std::vector<DlIRect> 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) {
      int32_t top = line.top;
      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->GetBottom() < top) {
            // Went all the way to previous span line.
            break;
          } else if (iter->GetLeft() == span->left &&
                     iter->GetRight() == span->right) {
            FML_DCHECK(iter->GetBottom() == top);
            top = iter->GetTop();
            rects.erase(iter);
            --previous_span_end;
            break;
          }
        }
      }
      rects.push_back(
          DlIRect::MakeLTRB(span->left, top, span->right, line.bottom));
    }
    previous_span_end = rects.size();
  }
  return rects;
}

References FML_DCHECK.

Referenced by flutter::testing::CheckEquality(), flutter::DlRTree::searchAndConsolidateRects(), flutter::RTree::searchNonOverlappingDrawnRects(), flutter::SliceViews(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), and flutter::testing::TEST().

intersects() [1/2]

bool flutter::DlRegion::intersects

(

const DlIRect &

rect

)

const

Returns whether this region intersects with a rectangle.

Definition at line 615 of file dl_region.cc.

                                                   {
  if (isEmpty()) {
    return false;
  }
 
  auto bounds_intersect = bounds_.IntersectsWithRect(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.GetTop()) {
    it = std::lower_bound(
        lines_.begin() + kBinarySearchThreshold + 1, lines_.end(),
        rect.GetTop(),
        [](const SpanLine& line, int32_t top) { return line.bottom <= top; });
  } else {
    while (it != end && it->bottom <= rect.GetTop()) {
      ++it;
      continue;
    }
  }
  while (it != end && it->top < rect.GetBottom()) {
    FML_DCHECK(rect.GetTop() < it->bottom && it->top < rect.GetBottom());
    const Span *begin, *end;
    span_buffer_.getSpans(it->chunk_handle, begin, end);
    while (begin != end && begin->left < rect.GetRight()) {
      if (begin->right > rect.GetLeft()) {
        return true;
      }
      ++begin;
    }
    ++it;
  }
 
  return false;
}

References end, FML_DCHECK, impeller::TRect< T >::GetBottom(), impeller::TRect< T >::GetLeft(), impeller::TRect< T >::GetRight(), impeller::TRect< T >::GetTop(), and flutter::kBinarySearchThreshold.

Referenced by intersects(), and flutter::testing::TEST().

intersects() [2/2]

bool flutter::DlRegion::intersects

(

const DlRegion &

region

)

const

Returns whether this region intersects with another region.

Definition at line 704 of file dl_region.cc.

                                                      {
  if (isEmpty() || region.isEmpty()) {
    return false;
  }
 
  auto our_complex = isComplex();
  auto their_complex = region.isComplex();
  auto bounds_intersect = bounds_.IntersectsWithRect(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;
}

References FML_DCHECK, intersects(), isComplex(), and isEmpty().

isComplex()

bool flutter::DlRegion::isComplex

(

)

const

Returns true if region is not empty and contains more than one rectangle.

Definition at line 609 of file dl_region.cc.

                               {
  return lines_.size() > 1 ||
         (lines_.size() == 1 &&
          span_buffer_.getChunkSize(lines_.front().chunk_handle) > 1);
}

Referenced by intersects(), and isSimple().

isEmpty()

bool flutter::DlRegion::isEmpty ( ) const

inline

Returns true if region is empty (contains no rectangles).

Definition at line 62 of file dl_region.h.

{ return lines_.empty(); }

Referenced by intersects(), MakeUnion(), and flutter::testing::TEST().

isSimple()

bool flutter::DlRegion::isSimple ( ) const

inline

Returns true if region can be represented by single rectangle or is empty.

Definition at line 69 of file dl_region.h.

{ return !isComplex(); }

References isComplex().

Referenced by MakeIntersection(), and MakeUnion().

MakeIntersection()

DlRegion flutter::DlRegion::MakeIntersection ( const DlRegion &  a, const DlRegion &  b  )

static

Creates intersection region of region a and b. Matches SkRegion a; a.op(b, SkRegion::kIntersect_Op) behavior.

Definition at line 496 of file dl_region.cc.

                                                                        {
  if (!a.bounds_.IntersectsWithRect(b.bounds_)) {
    return DlRegion();
  } else if (a.isSimple() && b.isSimple()) {
    auto res = a.bounds_.Intersection(b.bounds_);
    FML_DCHECK(res.has_value());
    return res.has_value() ? DlRegion(res.value()) : DlRegion();
  } 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_ = res.bounds_.Union(DlIRect::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;
}

References impeller::TRect< T >::Contains(), FML_DCHECK, impeller::TRect< T >::Intersection(), impeller::TRect< T >::IntersectsWithRect(), isSimple(), flutter::size, and impeller::TRect< T >::Union().

Referenced by flutter::DlRTree::region(), flutter::EmbedderViewSlice::region(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), and flutter::testing::TEST().

MakeUnion()

DlRegion flutter::DlRegion::MakeUnion ( const DlRegion &  a, const DlRegion &  b  )

static

Creates union region of region a and b. Matches SkRegion a; a.op(b, SkRegion::kUnion_Op) behavior.

Definition at line 405 of file dl_region.cc.

                                                                 {
  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_.Union(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;
}

References impeller::TRect< T >::Contains(), FML_DCHECK, isEmpty(), isSimple(), flutter::size, and impeller::TRect< T >::Union().

Referenced by flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), flutter::testing::TEST(), and flutter::testing::TEST().

operator=() [1/2]

DlRegion & flutter::DlRegion::operator= ( const DlRegion &  )

default

operator=() [2/2]

DlRegion & flutter::DlRegion::operator= ( DlRegion &&  )

default

---

The documentation for this class was generated from the following files:

• display_list/geometry/dl_region.h
• display_list/geometry/dl_region.cc