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_graphite_geom_IntersectionTree_DEFINED 9 #define skgpu_graphite_geom_IntersectionTree_DEFINED 10 11 #include "include/private/base/SkAlign.h" 12 #include "src/base/SkArenaAlloc.h" 13 #include "src/gpu/graphite/geom/Rect.h" 14 15 namespace skgpu::graphite { 16 17 /** 18 * Maintains a collection of non-overlapping rectangles. 19 * 20 * add() either adds the given rect to the collection, or returns false if it intersected with a 21 * rect already in the collection. 22 */ 23 class IntersectionTree { 24 public: 25 enum class SplitType : bool { 26 kX, 27 kY 28 }; 29 30 IntersectionTree(); 31 add(Rect rect)32 bool add(Rect rect) { 33 if (rect.isEmptyNegativeOrNaN()) { 34 // Empty and undefined rects can simply pass without modifying the tree. 35 return true; 36 } 37 if (!fRoot->intersects(rect)) { 38 fRoot = fRoot->addNonIntersecting(rect, &fArena); 39 return true; 40 } 41 return false; 42 } 43 44 private: 45 class Node { 46 public: 47 virtual ~Node() = default; 48 49 virtual bool intersects(Rect) = 0; 50 virtual Node* addNonIntersecting(Rect, SkArenaAlloc*) = 0; 51 }; 52 53 template<SplitType kSplitType> class TreeNode; 54 class LeafNode; 55 56 // The TreeNode size is made of a vtable (i.e. sizeof(void*)), float, and two Node* pointers. 57 // We also align between the Node* and the float which may add some extra padding. 58 constexpr static int kTreeNodeSize = SkAlignTo(sizeof(void*) + sizeof(float), alignof(void*)) + 59 2 * sizeof(Node*); 60 constexpr static int kLeafNodeSize = 16 + (2 + 64) * sizeof(Rect); 61 constexpr static int kPadSize = 256; // For footers and alignment. 62 SkArenaAlloc fArena{kLeafNodeSize + kTreeNodeSize + kPadSize*2}; 63 Node* fRoot; 64 }; 65 66 } // namespace skgpu::graphite 67 68 #endif // skgpu_graphite_geom_IntersectionTree_DEFINED 69