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_DrawOrder_DEFINED 9 #define skgpu_DrawOrder_DEFINED 10 11 #include "include/core/SkTypes.h" 12 13 namespace skgpu { 14 15 // Helper to encapsulate an unsigned number and enforce that it can only be used to create a 16 // monotonic sequence. The template argument 'Sequence' is used to define different sequences 17 // enforced by the compiler. For simplicity, and current needs within Graphite, it's assumed the 18 // entire sequence can be indexed by uint16_t. 19 template<typename Sequence> 20 class MonotonicValue { 21 public: First()22 static constexpr MonotonicValue First() { return 0; } Last()23 static constexpr MonotonicValue Last() { return 0xffff; } 24 25 MonotonicValue() = default; 26 MonotonicValue(const MonotonicValue& o) = default; 27 28 MonotonicValue& operator=(const MonotonicValue& o) = default; 29 30 bool operator< (MonotonicValue o) const { return fIndex < o.fIndex; } 31 bool operator<=(MonotonicValue o) const { return fIndex <= o.fIndex; } 32 33 bool operator> (MonotonicValue o) const { return fIndex > o.fIndex; } 34 bool operator>=(MonotonicValue o) const { return fIndex >= o.fIndex; } 35 36 bool operator==(MonotonicValue o) const { return fIndex == o.fIndex; } 37 bool operator!=(MonotonicValue o) const { return fIndex != o.fIndex; } 38 bits()39 uint16_t bits() const { return fIndex; } 40 41 // Get the next value in the sequence after this one next()42 MonotonicValue next() const { return fIndex + 1; } 43 44 private: MonotonicValue(uint16_t index)45 constexpr MonotonicValue(uint16_t index) : fIndex(index) {} 46 47 uint16_t fIndex = 0; 48 }; 49 50 /** 51 * CompressedPaintersOrder is an ordinal number that allows draw commands to be re-ordered so long 52 * as when they are executed, the read/writes to the color|depth attachments respect the original 53 * painter's order. Logical draws with the same CompressedPaintersOrder can be assumed to be 54 * executed in any order, however that may have been determined (e.g. BoundsManager or relying on 55 * a depth test during rasterization). 56 */ 57 struct CompressedPaintersOrderSequence {}; 58 using CompressedPaintersOrder = MonotonicValue<CompressedPaintersOrderSequence>; 59 60 /** 61 * Each DisjointStencilIndex specifies an implicit set of non-overlapping draws. Assuming that two 62 * draws have the same CompressedPaintersOrder and the same DisjointStencilIndex, their substeps 63 * for multi-pass rendering (stencil-then-cover, etc.) can be intermingled with each other and 64 * produce the same results as if each draw's substeps were executed in order before moving on to 65 * the next draw's. 66 * 67 * Ordering within a set can be entirely arbitrary (i.e. all stencil steps can go before all cover 68 * steps). Ordering between sets is also arbitrary since all draws share the same 69 * CompressedPaintersOrder, so long as one set is entirely drawn before the next. 70 * 71 * Two draws that have different CompressedPaintersOrders but the same DisjointStencilIndex are 72 * unrelated, they may or may not overlap. The painters order scopes the disjoint sets. 73 */ 74 struct DisjointStencilIndexSequence {}; 75 using DisjointStencilIndex = MonotonicValue<DisjointStencilIndexSequence>; 76 77 /** 78 * Every draw has an associated depth value. The value is constant across the entire draw and is 79 * not related to any varying Z coordinate induced by a 4x4 transform. The painter's depth is stored 80 * in the depth attachment and the GREATER depth test is used to reject or accept pixels/samples 81 * relative to what has already been rendered into the depth attachment. This allows draws that do 82 * not depend on the previous color to be radically re-ordered relative to their original painter's 83 * order while producing correct results. 84 */ 85 struct PaintersDepthSequence {}; 86 using PaintersDepth = MonotonicValue<PaintersDepthSequence>; 87 88 /** 89 * DrawOrder aggregates the three separate sequences that Graphite uses to re-order draws and their 90 * substeps as much as possible while preserving the painter's order semantics of the Skia API. 91 * 92 * To build the full DrawOrder for a draw, start with its assigned PaintersDepth (i.e. the original 93 * painter's order of the draw call). From there, the DrawOrder can be updated to reflect 94 * dependencies on previous draws, either from depth-only clip draws or because the draw is 95 * transparent and must blend with the previous color values. Lastly, once the 96 * CompressedPaintersOrder is finalized, the DrawOrder can be updated to reflect whether or not 97 * the draw will involve the stencil buffer--and if so, specify the disjoint stencil set it 98 * belongs to. 99 * 100 * The original and effective order that draws are executed in is defined by the PaintersDepth. 101 * However, the actual execution order is defined by first the CompressedPaintersOrder and then 102 * the DisjointStencilIndex. This means that draws with much higher depths can be executed earlier 103 * if painter's order compression allows for it. 104 * 105 * 106 *FIXME Integrate this? 107 * This reduces to a vertex 108 * coloring problem on the intersection graph formed by the commands and how their bounds 109 * overlap, followed by ordering by pipeline description and uniform data. General vertex 110 * coloring is NP-complete so DrawPass uses a greedy algorithm where the order it "colors" the 111 * vertices is based on the ordering constraints for the color+depth buffer and optionally the 112 * stencil buffer (stored in fColorDepthIndex and fStencilIndex respectively). skgpu::Device 113 * determines the ordering on-the-fly by using BoundsManager to approximate intersections as 114 * draw commands are recorded. It is possible to issue draws to Skia that produce pathologic 115 * orderings using this method, but it strikes a reasonable balance between finding a near 116 * optimal ordering that respects painter's order and is very efficient to compute. 117 * 118 */ 119 class DrawOrder { 120 public: 121 // The first PaintersDepth is reserved for clearing the depth attachment; any draw using this 122 // depth will always fail the depth test. 123 inline static constexpr PaintersDepth kClearDepth = PaintersDepth::First(); 124 // The first CompressedPaintersOrder is reserved to indicate there is no previous draw that 125 // must come before a draw. 126 inline static constexpr 127 CompressedPaintersOrder kNoIntersection = CompressedPaintersOrder::First(); 128 // The first DisjointStencilIndex is reserved to indicate an unassigned stencil set. 129 inline static constexpr DisjointStencilIndex kUnassigned = DisjointStencilIndex::First(); 130 DrawOrder(PaintersDepth originalOrder)131 explicit DrawOrder(PaintersDepth originalOrder) 132 : fPaintOrder(kNoIntersection) 133 , fStencilIndex(kUnassigned) 134 , fDepth(originalOrder) {} 135 paintOrder()136 CompressedPaintersOrder paintOrder() const { return fPaintOrder; } stencilIndex()137 DisjointStencilIndex stencilIndex() const { return fStencilIndex; } depth()138 PaintersDepth depth() const { return fDepth; } 139 dependsOnPaintersOrder(CompressedPaintersOrder prevDraw)140 DrawOrder& dependsOnPaintersOrder(CompressedPaintersOrder prevDraw) { 141 // A draw must be ordered after all previous draws that it depends on 142 CompressedPaintersOrder next = prevDraw.next(); 143 if (fPaintOrder < next) { 144 fPaintOrder = next; 145 } 146 return *this; 147 } 148 dependsOnStencil(DisjointStencilIndex disjointSet)149 DrawOrder& dependsOnStencil(DisjointStencilIndex disjointSet) { 150 // Stencil usage should only be set once 151 SkASSERT(fStencilIndex == kUnassigned); 152 fStencilIndex = disjointSet; 153 return *this; 154 } 155 156 private: 157 CompressedPaintersOrder fPaintOrder; 158 DisjointStencilIndex fStencilIndex; 159 PaintersDepth fDepth; 160 }; 161 162 } // namespace skgpu 163 164 #endif // skgpu_DrawOrder_DEFINED 165