submodule/skia/src/gpu/graphite/DrawOrder.h

   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_DrawOrder_DEFINED
   9 #define skgpu_graphite_DrawOrder_DEFINED
  10
  11 #include "include/core/SkTypes.h"
  12
  13 namespace skgpu::graphite {
  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:
  22     static constexpr MonotonicValue First() { return 0;      }
  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
  39     uint16_t bits() const { return fIndex; }
  40
  41     // Get the next value in the sequence after this one
  42     MonotonicValue next() const { return fIndex + 1; }
  43
  44 private:
  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
 131     explicit DrawOrder(PaintersDepth originalOrder)
 132             : fPaintOrder(kNoIntersection)
 133             , fStencilIndex(kUnassigned)
 134             , fDepth(originalOrder) {}
 135
 136     DrawOrder(PaintersDepth originalOrder, CompressedPaintersOrder compressedOrder)
 137             : fPaintOrder(compressedOrder)
 138             , fStencilIndex(kUnassigned)
 139             , fDepth(originalOrder) {}
 140
 141     CompressedPaintersOrder paintOrder()   const { return fPaintOrder;   }
 142     DisjointStencilIndex    stencilIndex() const { return fStencilIndex; }
 143     PaintersDepth           depth()        const { return fDepth;        }
 144
 145     float depthAsFloat() const { return fDepth.bits() / (float) PaintersDepth::Last().bits(); }
 146
 147     DrawOrder& dependsOnPaintersOrder(CompressedPaintersOrder prevDraw) {
 148         // A draw must be ordered after all previous draws that it depends on
 149         CompressedPaintersOrder next = prevDraw.next();
 150         if (fPaintOrder < next) {
 151             fPaintOrder = next;
 152         }
 153         return *this;
 154     }
 155
 156     DrawOrder& dependsOnStencil(DisjointStencilIndex disjointSet) {
 157         // Stencil usage should only be set once
 158         SkASSERT(fStencilIndex == kUnassigned);
 159         fStencilIndex = disjointSet;
 160         return *this;
 161     }
 162
 163 private:
 164     CompressedPaintersOrder fPaintOrder;
 165     DisjointStencilIndex    fStencilIndex;
 166     PaintersDepth           fDepth;
 167 };
 168
 169 } // namespace skgpu::graphite
 170
 171 #endif // skgpu_graphite_DrawOrder_DEFINED