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#include "experimental/graphite/src/geom/IntersectionTree.h"
9
10#include "include/private/SkTPin.h"
11#include <algorithm>
12#include <limits>
13
14namespace skgpu {
15
16// BSP node. Space is partitioned by an either vertical or horizontal line. Note that if a rect
17// straddles the partition line, it will need to go on both sides of the tree.
18template<IntersectionTree::SplitType kSplitType>
19class IntersectionTree::TreeNode final : public Node {
20public:
21    TreeNode(float splitCoord, Node* lo, Node* hi)
22            : fSplitCoord(splitCoord), fLo(lo), fHi(hi) {
23    }
24
25    bool intersects(Rect rect) override {
26        if (GetLoVal(rect) < fSplitCoord && fLo->intersects(rect)) {
27            return true;
28        }
29        if (GetHiVal(rect) > fSplitCoord && fHi->intersects(rect)) {
30            return true;
31        }
32        return false;
33    }
34
35    Node* addNonIntersecting(Rect rect, SkArenaAlloc* arena) override {
36        if (GetLoVal(rect) < fSplitCoord) {
37            fLo = fLo->addNonIntersecting(rect, arena);
38        }
39        if (GetHiVal(rect) > fSplitCoord) {
40            fHi = fHi->addNonIntersecting(rect, arena);
41        }
42        return this;
43    }
44
45private:
46    SK_ALWAYS_INLINE static float GetLoVal(const Rect& rect) {
47        return (kSplitType == SplitType::kX) ? rect.left() : rect.top();
48    }
49    SK_ALWAYS_INLINE static float GetHiVal(const Rect& rect) {
50        return (kSplitType == SplitType::kX) ? rect.right() : rect.bot();
51    }
52
53    float fSplitCoord;
54    Node* fLo;
55    Node* fHi;
56};
57
58// Leaf node. Rects are kept in a simple list and intersection testing is performed by brute force.
59class IntersectionTree::LeafNode final : public Node {
60public:
61    // Max number of rects to store in this node before splitting. With SSE/NEON optimizations, ~64
62    // brute force rect comparisons seems to be the optimal number.
63    constexpr static int kMaxRectsInList = 64;
64
65    LeafNode() {
66        this->popAll();
67        // Initialize our arrays with maximally negative rects. These have the advantage of always
68        // failing intersection tests, thus allowing us to test for intersection beyond fNumRects
69        // without failing.
70        constexpr static float infinity = std::numeric_limits<float>::infinity();
71        std::fill_n(fLefts, kMaxRectsInList, infinity);
72        std::fill_n(fTops, kMaxRectsInList, infinity);
73        std::fill_n(fNegRights, kMaxRectsInList, infinity);
74        std::fill_n(fNegBots, kMaxRectsInList, infinity);
75    }
76
77    void popAll() {
78        fNumRects = 0;
79        fSplittableBounds = -std::numeric_limits<float>::infinity();
80        fRectValsSum = 0;
81        // Leave the rect arrays untouched. Since we know they are either already valid in the tree,
82        // or else maximally negative, this allows the future list to check for intersection beyond
83        // fNumRects without failing.
84    }
85
86    bool intersects(Rect rect) override {
87        // Test for intersection in sets of 4. Since all the data in our rect arrays is either
88        // maximally negative, or valid from somewhere else in the tree, we can test beyond
89        // fNumRects without failing.
90        static_assert(kMaxRectsInList % 4 == 0);
91        SkASSERT(fNumRects <= kMaxRectsInList);
92        float4 comp = Rect::ComplementRect(rect).fVals;
93        for (int i = 0; i < fNumRects; i += 4) {
94            float4 l = float4::Load(fLefts + i);
95            float4 t = float4::Load(fTops + i);
96            float4 nr = float4::Load(fNegRights + i);
97            float4 nb = float4::Load(fNegBots + i);
98            if (any((l < comp[0]) &
99                    (t < comp[1]) &
100                    (nr < comp[2]) &
101                    (nb < comp[3]))) {
102                return true;
103            }
104        }
105        return false;
106    }
107
108    Node* addNonIntersecting(Rect rect, SkArenaAlloc* arena) override {
109        if (fNumRects == kMaxRectsInList) {
110            // The new rect doesn't fit. Split our rect list first and then add.
111            return this->split(arena)->addNonIntersecting(rect, arena);
112        }
113        this->appendToList(rect);
114        return this;
115    }
116
117private:
118    void appendToList(Rect rect) {
119        SkASSERT(fNumRects < kMaxRectsInList);
120        int i = fNumRects++;
121        // [maxLeft, maxTop, -minRight, -minBot]
122        fSplittableBounds = max(fSplittableBounds, rect.vals());
123        fRectValsSum += rect.vals();  // [sum(left), sum(top), -sum(right), -sum(bot)]
124        fLefts[i] = rect.vals()[0];
125        fTops[i] = rect.vals()[1];
126        fNegRights[i] = rect.vals()[2];
127        fNegBots[i] = rect.vals()[3];
128    }
129
130    Rect loadRect(int i) const {
131        return Rect::FromVals(float4(fLefts[i], fTops[i], fNegRights[i], fNegBots[i]));
132    }
133
134    // Splits this node with a new LeafNode, then returns a TreeNode that reuses our "this" pointer
135    // along with the new node.
136    IntersectionTree::Node* split(SkArenaAlloc* arena) {
137        // This should only get called when our list is full.
138        SkASSERT(fNumRects == kMaxRectsInList);
139
140        // Since rects cannot overlap, there will always be a split that places at least one pairing
141        // of rects on opposite sides. The region:
142        //
143        //     fSplittableBounds == [maxLeft, maxTop, -minRight, -minBot] == [r, b, -l, -t]
144        //
145        // Represents the region of splits that guarantee a strict subdivision of our rect list.
146        float2 splittableSize = fSplittableBounds.xy() + fSplittableBounds.zw();  // == [r-l, b-t]
147        SkASSERT(max(splittableSize) >= 0);
148        SplitType splitType = (splittableSize.x() > splittableSize.y()) ? SplitType::kX
149                                                                        : SplitType::kY;
150
151        float splitCoord;
152        const float *loVals, *negHiVals;
153        if (splitType == SplitType::kX) {
154            // Split horizontally, at the geometric midpoint if it falls within the splittable
155            // bounds.
156            splitCoord = (fRectValsSum.x() - fRectValsSum.z()) * (.5f/kMaxRectsInList);
157            splitCoord = SkTPin(splitCoord, -fSplittableBounds.z(), fSplittableBounds.x());
158            loVals = fLefts;
159            negHiVals = fNegRights;
160        } else {
161            // Split vertically, at the geometric midpoint if it falls within the splittable bounds.
162            splitCoord = (fRectValsSum.y() - fRectValsSum.w()) * (.5f/kMaxRectsInList);
163            splitCoord = SkTPin(splitCoord, -fSplittableBounds.w(), fSplittableBounds.y());
164            loVals = fTops;
165            negHiVals = fNegBots;
166        }
167
168        // Split "this", leaving all rects below "splitCoord" in this, and placing all rects above
169        // splitCoord in "hiNode". There may be some reduncancy between lists, but we made sure to
170        // select a split that would leave both lists strictly smaller than the original.
171        LeafNode* hiNode = arena->make<LeafNode>();
172        int numCombinedRects = fNumRects;
173        float negSplitCoord = -splitCoord;
174        this->popAll();
175        for (int i = 0; i < numCombinedRects; ++i) {
176            Rect rect = this->loadRect(i);
177            if (loVals[i] < splitCoord) {
178                this->appendToList(rect);
179            }
180            if (negHiVals[i] < negSplitCoord) {
181                hiNode->appendToList(rect);
182            }
183        }
184
185        SkASSERT(0 < fNumRects && fNumRects < numCombinedRects);
186        SkASSERT(0 < hiNode->fNumRects && hiNode->fNumRects < numCombinedRects);
187
188        return (splitType == SplitType::kX)
189                ? (Node*)arena->make<TreeNode<SplitType::kX>>(splitCoord, this, hiNode)
190                : (Node*)arena->make<TreeNode<SplitType::kY>>(splitCoord, this, hiNode);
191    }
192
193    int fNumRects;
194    float4 fSplittableBounds;  // [maxLeft, maxTop, -minRight, -minBot]
195    float4 fRectValsSum;  // [sum(left), sum(top), -sum(right), -sum(bot)]
196    alignas(float4) float fLefts[kMaxRectsInList];
197    alignas(float4) float fTops[kMaxRectsInList];
198    alignas(float4) float fNegRights[kMaxRectsInList];
199    alignas(float4) float fNegBots[kMaxRectsInList];
200    static_assert((kMaxRectsInList * sizeof(float)) % sizeof(float4) == 0);
201};
202
203IntersectionTree::IntersectionTree()
204        : fRoot(fArena.make<LeafNode>()) {
205    static_assert(kTreeNodeSize == sizeof(TreeNode<SplitType::kX>));
206    static_assert(kTreeNodeSize == sizeof(TreeNode<SplitType::kY>));
207    static_assert(kLeafNodeSize == sizeof(LeafNode));
208}
209
210} // namespace skgpu
211