1 /* 2 * Copyright 2021 Google LLC 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef skgpu_geom_IntersectionTree_DEFINED 9 #define skgpu_geom_IntersectionTree_DEFINED 10 11 #include "experimental/graphite/src/geom/Rect.h" 12 #include "src/core/SkArenaAlloc.h" 13 14 namespace skgpu { 15 16 /** 17 * Maintains a collection of non-overlapping rectangles. 18 * 19 * add() either adds the given rect to the collection, or returns false if it intersected with a 20 * rect already in the collection. 21 */ 22 class IntersectionTree { 23 public: 24 IntersectionTree(); 25 add(Rect rect)26 bool add(Rect rect) { 27 if (rect.isEmptyNegativeOrNaN()) { 28 // Empty and undefined rects can simply pass without modifying the tree. 29 return true; 30 } 31 if (!fRoot->intersects(rect)) { 32 fRoot = fRoot->addNonIntersecting(rect, &fArena); 33 return true; 34 } 35 return false; 36 } 37 38 private: 39 class Node { 40 public: 41 virtual ~Node() = default; 42 43 virtual bool intersects(Rect) = 0; 44 virtual Node* addNonIntersecting(Rect, SkArenaAlloc*) = 0; 45 }; 46 47 enum class SplitType : bool { 48 kX, 49 kY 50 }; 51 52 template<SplitType kSplitType> class TreeNode; 53 class LeafNode; 54 55 constexpr static int kTreeNodeSize = 16 + sizeof(Node*) * 2; 56 constexpr static int kLeafNodeSize = 16 + (2 + 64) * sizeof(float4); 57 constexpr static int kPadSize = 256; // For footers and alignment. 58 SkArenaAlloc fArena{kLeafNodeSize + kTreeNodeSize + kPadSize*2}; 59 Node* fRoot; 60 }; 61 62 } // namespace skgpu 63 64 #endif // skgpu_geom_IntersectionTree_DEFINED 65