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
18namespace 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 */
31class BoundsManager {
32public:
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
45// TODO: Select one most-effective BoundsManager implementation, make it the only option, and remove
46// virtual-ness. For now, this seems useful for correctness testing by comparing against trivial
47// implementations and for identifying how much "smarts" are actually worthwhile.
48
49// A BoundsManager that produces exact painter's order and assumes nothing is occluded.
50class NaiveBoundsManager final : public BoundsManager {
51public:
52    ~NaiveBoundsManager() override {}
53
54    CompressedPaintersOrder getMostRecentDraw(const Rect& bounds) const override {
55        return fLatestDraw;
56    }
57
58    bool isOccluded(const Rect& bounds, PaintersDepth z) const override { return false; }
59
60    void recordDraw(const Rect& bounds, CompressedPaintersOrder order, PaintersDepth z,
61                    bool fullyOpaque=false) override {
62        if (fLatestDraw < order) {
63            fLatestDraw = order;
64        }
65    }
66
67private:
68    CompressedPaintersOrder fLatestDraw = CompressedPaintersOrder::First();
69};
70
71// A BoundsManager that tracks every draw and can exactly determine all queries
72// using a brute force search.
73class BruteForceBoundsManager : public BoundsManager {
74public:
75    ~BruteForceBoundsManager() override {}
76
77    CompressedPaintersOrder getMostRecentDraw(const Rect& bounds) const override {
78        CompressedPaintersOrder max = CompressedPaintersOrder::First();
79        for (const Record& r : fRects.items()) {
80            if (max < r.fOrder && r.fBounds.intersects(bounds)) {
81                max = r.fOrder;
82            }
83        }
84        return max;
85    }
86
87    bool isOccluded(const Rect& bounds, PaintersDepth z) const override {
88        // Iterate in reverse since the records were likely recorded in increasing Z
89        for (const Record& r : fRects.ritems()) {
90            if (r.fOpaque && z < r.fZ && r.fBounds.contains(bounds)) {
91                return true;
92            }
93        }
94        return false;
95    }
96
97    void recordDraw(const Rect& bounds, CompressedPaintersOrder order, PaintersDepth z,
98                    bool fullyOpaque=false) override {
99        fRects.push_back({bounds, order, z, fullyOpaque});
100    }
101
102private:
103    struct Record {
104        Rect fBounds;
105        CompressedPaintersOrder fOrder;
106        PaintersDepth fZ;
107        bool fOpaque;
108    };
109
110    SkTBlockList<Record> fRects{16, SkBlockAllocator::GrowthPolicy::kFibonacci};
111};
112
113} // namespace skgpu
114
115#endif // skgpu_geom_BoundsManager_DEFINED
116