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_BoundsManager_DEFINED 9 #define skgpu_geom_BoundsManager_DEFINED 10 11 #include "experimental/graphite/src/DrawOrder.h" 12 #include "experimental/graphite/src/geom/Rect.h" 13 14 #include "src/core/SkTBlockList.h" 15 16 #include <cstdint> 17 18 namespace skgpu { 19 20 /** 21 * BoundsManager is an acceleration structure for device-space related pixel bounds queries. 22 * The BoundsManager relies on two related ordinal values: the CompressedPaintersOrder of a draw 23 * and the Z/depth value of the draw. The CompressedPaintersOrder enforces a specific submission 24 * order of draws to the GPU but can re-arrange draws out of their original painter's order if the 25 * GREATER depth test and the draw's Z value resolve out-of-order rendering. 26 * 27 * It supports querying the most recent draw intersecting a bounding rect (represented as a 28 * CompressedPaintersOrder value), recording a (bounds, CompressedPaintersOrder, and Z value) tuple, 29 * and querying if a (bounds, Z value) pair is fully occluded by another draw. 30 */ 31 class BoundsManager { 32 public: ~BoundsManager()33 virtual ~BoundsManager() {} 34 35 virtual CompressedPaintersOrder getMostRecentDraw(const Rect& bounds) const = 0; 36 37 virtual bool isOccluded(const Rect& bounds, PaintersDepth z) const = 0; 38 39 virtual void recordDraw(const Rect& bounds, 40 CompressedPaintersOrder order, 41 PaintersDepth z, 42 bool fullyOpaque=false) = 0; 43 44 virtual void reset() = 0; 45 }; 46 47 // TODO: Select one most-effective BoundsManager implementation, make it the only option, and remove 48 // virtual-ness. For now, this seems useful for correctness testing by comparing against trivial 49 // implementations and for identifying how much "smarts" are actually worthwhile. 50 51 // A BoundsManager that produces exact painter's order and assumes nothing is occluded. 52 class NaiveBoundsManager final : public BoundsManager { 53 public: ~NaiveBoundsManager()54 ~NaiveBoundsManager() override {} 55 getMostRecentDraw(const Rect & bounds)56 CompressedPaintersOrder getMostRecentDraw(const Rect& bounds) const override { 57 return fLatestDraw; 58 } 59 isOccluded(const Rect & bounds,PaintersDepth z)60 bool isOccluded(const Rect& bounds, PaintersDepth z) const override { return false; } 61 62 void recordDraw(const Rect& bounds, CompressedPaintersOrder order, PaintersDepth z, 63 bool fullyOpaque=false) override { 64 if (fLatestDraw < order) { 65 fLatestDraw = order; 66 } 67 } 68 reset()69 void reset() override { 70 fLatestDraw = CompressedPaintersOrder::First(); 71 } 72 73 private: 74 CompressedPaintersOrder fLatestDraw = CompressedPaintersOrder::First(); 75 }; 76 77 // A BoundsManager that tracks every draw and can exactly determine all queries 78 // using a brute force search. 79 class BruteForceBoundsManager : public BoundsManager { 80 public: ~BruteForceBoundsManager()81 ~BruteForceBoundsManager() override {} 82 getMostRecentDraw(const Rect & bounds)83 CompressedPaintersOrder getMostRecentDraw(const Rect& bounds) const override { 84 CompressedPaintersOrder max = CompressedPaintersOrder::First(); 85 for (const Record& r : fRects.items()) { 86 if (max < r.fOrder && r.fBounds.intersects(bounds)) { 87 max = r.fOrder; 88 } 89 } 90 return max; 91 } 92 isOccluded(const Rect & bounds,PaintersDepth z)93 bool isOccluded(const Rect& bounds, PaintersDepth z) const override { 94 // Iterate in reverse since the records were likely recorded in increasing Z 95 for (const Record& r : fRects.ritems()) { 96 if (r.fOpaque && z < r.fZ && r.fBounds.contains(bounds)) { 97 return true; 98 } 99 } 100 return false; 101 } 102 103 void recordDraw(const Rect& bounds, CompressedPaintersOrder order, PaintersDepth z, 104 bool fullyOpaque=false) override { 105 fRects.push_back({bounds, order, z, fullyOpaque}); 106 } 107 reset()108 void reset() override { 109 fRects.reset(); 110 } 111 112 private: 113 struct Record { 114 Rect fBounds; 115 CompressedPaintersOrder fOrder; 116 PaintersDepth fZ; 117 bool fOpaque; 118 }; 119 120 SkTBlockList<Record> fRects{16, SkBlockAllocator::GrowthPolicy::kFibonacci}; 121 }; 122 123 } // namespace skgpu 124 125 #endif // skgpu_geom_BoundsManager_DEFINED 126