flutter::DlRTree Class Reference

#include <dl_rtree.h>

Inheritance diagram for flutter::DlRTree:

Public Member Functions
	DlRTree (const DlRect rects[], int N, const int ids[]=nullptr, bool predicate(int id)=[](int) { return true;}, int invalid_id=-1)
void	search (const DlRect &query, std::vector< int > *results) const
int	id (int result_index) const
const DlRect &	bounds () const
const DlRect &	bounds (int result_index) const
size_t	bytes_used () const
	Returns the bytes used by the object and all of its node data.
int	leaf_count () const
int	node_count () const
std::list< DlRect >	searchAndConsolidateRects (const DlRect &query, bool deband=true) const
const DlRegion &	region () const
DlRegion	region (const DlRect &query) const

Detailed Description

An R-Tree that stores a list of bounding rectangles with optional associated IDs.

The R-Tree can be searched in one of two ways:

• Query for a list of hits among the original rectangles

  See also

  |search|

• Query for a set of non-overlapping rectangles that are joined from the original rectangles that intersect a query rect

  See also

  |searchAndConsolidateRects|

Definition at line 27 of file dl_rtree.h.

Constructor & Destructor Documentation

DlRTree()

flutter::DlRTree::DlRTree	(	const DlRect	rects[],
		int	N,
		const int	ids[] = nullptr,
		bool	predicateint id = [](int) { return true; },
		int	invalid_id = -1
	)

Construct an R-Tree from the list of rectangles respecting the order in which they appear in the list. An optional array of IDs can be provided to tag each rectangle with information needed by the caller as well as an optional predicate that can filter out rectangles with IDs that should not be stored in the R-Tree.

If an array of IDs is not specified then all leaf nodes will be represented by the |invalid_id| (which defaults to -1).

Invalid rects that are empty or contain a NaN value will not be stored in the R-Tree. And, if a |predicate| function is provided, that function will be called to query if the rectangle associated with the ID should be included.

Duplicate rectangles and IDs are allowed and not processed in any way except to eliminate invalid rectangles and IDs that are rejected by the optional predicate function.

Definition at line 12 of file dl_rtree.cc.

    : invalid_id_(invalid_id) {
  if (N <= 0) {
    FML_DCHECK(N >= 0);
    return;
  }
  FML_DCHECK(rects != nullptr);
 
  // Count the number of rectangles we actually want to track,
  // which includes only non-empty rectangles whose optional
  // ID is not filtered by the predicate.
  int leaf_count = 0;
  for (int i = 0; i < N; i++) {
    if (!rects[i].IsEmpty()) {
      if (ids == nullptr || p(ids[i])) {
        leaf_count++;
      }
    }
  }
  leaf_count_ = leaf_count;
 
  // Count the total number of nodes (leaf and internal) up front
  // so we can resize the vector just once.
  uint32_t total_node_count = leaf_count;
  uint32_t gen_count = leaf_count;
  while (gen_count > 1) {
    uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
    total_node_count += family_count;
    gen_count = family_count;
  }
 
  nodes_.resize(total_node_count);
 
  // Now place only the tracked rectangles into the nodes array
  // in the first leaf_count_ entries.
  int leaf_index = 0;
  int id = invalid_id;
  for (int i = 0; i < N; i++) {
    if (!rects[i].IsEmpty()) {
      if (ids == nullptr || p(id = ids[i])) {
        Node& node = nodes_[leaf_index++];
        node.bounds = rects[i];
        node.id = id;
      }
    }
  }
  FML_DCHECK(leaf_index == leaf_count);
 
  // --- Implementation note ---
  // Many R-Tree algorithms attempt to consolidate nearby rectangles
  // into branches of the tree in order to maximize the benefit of
  // bounds testing against whole sub-trees. The Skia code from which
  // this was based, though, indicated that empirical tests against a
  // browser client showed little gains in rendering performance while
  // costing 17% performance in bulk loading the rects into the R-Tree:
  // https://github.com/google/skia/blob/12b6bd042f7cdffb9012c90c3b4885601fc7be95/src/core/SkRTree.cpp#L96
  //
  // Given that this class will most often be used to track rendering
  // operations that were drawn in an app that performs a type of
  // "page layout" with rendering proceeding in a linear fashion from
  // top to bottom (and left to right or right to left), the rectangles
  // are likely nearly sorted when they are delivered to this constructor
  // so leaving them in their original order should show similar results
  // to what Skia found in their empirical browser tests.
  // ---
 
  // Continually process the previous level (generation) of nodes,
  // combining them into a new generation of parent groups each grouping
  // at most |kMaxChildren| children and joining their bounds into its
  // parent bounds.
  // Each generation will end up reduced by a factor of up to kMaxChildren
  // until there is just one node left, which is the root node of
  // the R-Tree.
  uint32_t gen_start = 0;
  gen_count = leaf_count;
  while (gen_count > 1) {
    uint32_t gen_end = gen_start + gen_count;
 
    uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
    FML_DCHECK(gen_end + family_count <= total_node_count);
 
    // D here is similar to the variable in a Bresenham line algorithm where
    // we want to slowly move |family_count| steps along the minor axis as
    // we move |gen_count| steps along the major axis.
    //
    // Each inner loop increments D by family_count.
    // The inner loop executes a total of gen_count times.
    // Every time D exceeds 0 we subtract gen_count and move to a new parent.
    // All told we will increment D by family_count a total of gen_count times.
    // All told we will decrement D by gen_count a total of family_count times.
    // This leaves D back at its starting value.
    //
    // We could bias/balance where the extra children are placed by varying
    // the initial count of D from 0 to (1 - family_count), but we aren't
    // looking at this process aesthetically so we just use 0 as an initial
    // value. Using 0 provides a "greedy" allocation of the extra children.
    // Bresenham also uses double the size of the steps we use here also to
    // have better rounding of when the minor axis steps occur, but again we
    // don't care about the distribution of the extra children.
    int D = 0;
 
    uint32_t sibling_index = gen_start;
    uint32_t parent_index = gen_end;
    Node* parent = nullptr;
    while (sibling_index < gen_end) {
      if ((D += family_count) > 0) {
        D -= gen_count;
        FML_DCHECK(parent_index < gen_end + family_count);
        parent = &nodes_[parent_index++];
        parent->bounds = kEmpty;
        parent->child.index = sibling_index;
        parent->child.count = 0;
      }
      FML_DCHECK(parent != nullptr);
      parent->bounds = parent->bounds.Union(nodes_[sibling_index++].bounds);
      parent->child.count++;
    }
    FML_DCHECK(D == 0);
    FML_DCHECK(sibling_index == gen_end);
    FML_DCHECK(parent_index == gen_end + family_count);
    gen_start = gen_end;
    gen_count = family_count;
  }
  FML_DCHECK(gen_start + gen_count == total_node_count);
}

References bounds(), FML_DCHECK, i, id, and leaf_count().

Member Function Documentation

bounds() [1/2]

const DlRect & flutter::DlRTree::bounds

(

)

const

Returns maximum and minimum axis values of rectangles in this R-Tree. If R-Tree is empty returns an empty DlRect.

Definition at line 215 of file dl_rtree.cc.

                                    {
  if (!nodes_.empty()) {
    return nodes_.back().bounds;
  } else {
    return kEmpty;
  }
}

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

bounds() [2/2]

const DlRect & flutter::DlRTree::bounds ( int  result_index ) const

inline

Return the rectangle bounds for the indicated result of a query or an empty rect if the index is not a valid leaf node index.

Definition at line 95 of file dl_rtree.h.

                                               {
    return (result_index >= 0 && result_index < leaf_count_)
               ? nodes_[result_index].bounds
               : kEmpty;
  }

bytes_used()

size_t flutter::DlRTree::bytes_used ( ) const

inline

Returns the bytes used by the object and all of its node data.

Definition at line 102 of file dl_rtree.h.

                            {
    return sizeof(DlRTree) + sizeof(Node) * nodes_.size();
  }

id()

int flutter::DlRTree::id ( int  result_index ) const

inline

Return the ID for the indicated result of a query or invalid_id if the index is not a valid leaf node index.

Definition at line 83 of file dl_rtree.h.

                                 {
    return (result_index >= 0 && result_index < leaf_count_)
               ? nodes_[result_index].id
               : invalid_id_;
  }

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

leaf_count()

int flutter::DlRTree::leaf_count ( ) const

inline

Returns the number of leaf nodes corresponding to non-empty rectangles that were passed in the constructor and not filtered out by the predicate.

Definition at line 109 of file dl_rtree.h.

{ return leaf_count_; }

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

node_count()

int flutter::DlRTree::node_count ( ) const

inline

Return the total number of nodes used in the R-Tree, both leaf and internal consolidation nodes.

Definition at line 113 of file dl_rtree.h.

{ return nodes_.size(); }

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

region() [1/2]

const DlRegion & flutter::DlRTree::region

(

)

const

Returns DlRegion that represents the union of all rectangles in the R-Tree.

Definition at line 203 of file dl_rtree.cc.

                                      {
  if (!region_) {
    std::vector<DlIRect> rects;
    rects.resize(leaf_count_);
    for (int i = 0; i < leaf_count_; i++) {
      rects[i] = DlIRect::RoundOut(nodes_[i].bounds);
    }
    region_.emplace(rects);
  }
  return *region_;
}

References bounds(), i, and impeller::TRect< T >::RoundOut().

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

region() [2/2]

DlRegion flutter::DlRTree::region ( const DlRect &  query ) const

inline

Returns DlRegion that represents the union of all rectangles in the R-Tree intersected with the query rect.

Definition at line 133 of file dl_rtree.h.

                                             {
    return DlRegion::MakeIntersection(region(),
                                      DlRegion(DlIRect::RoundOut(query)));
  }

References flutter::DlRegion::MakeIntersection(), region(), and impeller::TRect< T >::RoundOut().

search()

void flutter::DlRTree::search	(	const DlRect &	query,
		std::vector< int > *	results
	)		const

Search the rectangles and return a vector of leaf node indices for rectangles that intersect the query.

Note that the indices are internal indices of the stored data and not the index of the rectangles or ids in the constructor. The returned indices may not themselves be in numerical order, but they will represent the rectangles and IDs in the order in which they were passed into the constructor. The actual rectangle and ID associated with each index can be retrieved using the |DlRTreeid| and |DlRTreebounds| methods.

Definition at line 142 of file dl_rtree.cc.

                                                                       {
  FML_DCHECK(results != nullptr);
  if (query.IsEmpty()) {
    return;
  }
  if (nodes_.size() <= 0) {
    FML_DCHECK(leaf_count_ == 0);
    return;
  }
  const Node& root = nodes_.back();
  if (root.bounds.IntersectsWithRect(query)) {
    if (nodes_.size() == 1) {
      FML_DCHECK(leaf_count_ == 1);
      // The root node is the only node and it is a leaf node
      results->push_back(0);
    } else {
      search(root, query, results);
    }
  }
}

References FML_DCHECK, impeller::TRect< T >::IsEmpty(), and search().

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

searchAndConsolidateRects()

std::list< DlRect > flutter::DlRTree::searchAndConsolidateRects	(	const DlRect &	query,
		bool	deband = true
	)		const

Finds the rects in the tree that intersect with the query rect.

The returned list of rectangles will be non-overlapping. In other words, the bounds of each rect in the result list are mutually exclusive.

If |deband| is true, then matching rectangles from adjacent DlRegion spanlines will be joined together. This reduces the number of rectangles returned, but requires some extra computation.

Definition at line 163 of file dl_rtree.cc.

                                                                        {
  // Get the indexes for the operations that intersect with the query rect.
  std::vector<int> intermediary_results;
  search(query, &intermediary_results);
 
  std::vector<DlIRect> rects;
  rects.reserve(intermediary_results.size());
  for (int index : intermediary_results) {
    DlIRect current_record_rect = DlIRect::RoundOut(bounds(index));
    rects.push_back(current_record_rect);
  }
  DlRegion region(rects);
 
  auto non_overlapping_rects = region.getRects(deband);
  std::list<DlRect> final_results;
  for (const auto& rect : non_overlapping_rects) {
    final_results.push_back(DlRect::Make(rect));
  }
  return final_results;
}

References bounds(), flutter::DlRegion::getRects(), impeller::TRect< Scalar >::Make(), region(), impeller::TRect< T >::RoundOut(), and search().

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

---

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

• display_list/geometry/dl_rtree.h
• display_list/geometry/dl_rtree.cc