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 // Maintains a collection of non-overlapping rectangles. 17 // 18 // add() either adds the given rect to the collection, or returns false if it intersected with a 19 // rect already in the collection. 20 class IntersectionTree { 21 public: 22 IntersectionTree(); 23 add(Rect rect)24 bool add(Rect rect) { 25 if (rect.isEmptyNegativeOrNaN()) { 26 // Empty and undefined rects can simply pass without modifying the tree. 27 return true; 28 } 29 if (!fRoot->intersects(rect)) { 30 fRoot = fRoot->addNonIntersecting(rect, &fArena); 31 return true; 32 } 33 return false; 34 } 35 36 private: 37 class Node { 38 public: 39 virtual ~Node() = default; 40 41 virtual bool intersects(Rect) = 0; 42 virtual Node* addNonIntersecting(Rect, SkArenaAlloc*) = 0; 43 }; 44 45 enum class SplitType : bool { 46 kX, 47 kY 48 }; 49 50 template<SplitType kSplitType> class TreeNode; 51 class LeafNode; 52 53 constexpr static int kTreeNodeSize = 16 + sizeof(Node*) * 2; 54 constexpr static int kLeafNodeSize = 16 + (2 + 64) * sizeof(float4); 55 constexpr static int kPadSize = 256; // For footers and alignment. 56 SkArenaAlloc fArena{kLeafNodeSize + kTreeNodeSize + kPadSize*2}; 57 Node* fRoot; 58 }; 59 60 61 } // namespace skgpu 62 63 #endif // skgpu_geom_IntersectionTree_DEFINED 64