Legends-of-Azeroth-Pandaria-5.4.8

1
/*
2
* This file is part of the Pandaria 5.4.8 Project. See THANKS file for Copyright information
3
*
4
* This program is free software; you can redistribute it and/or modify it
5
* under the terms of the GNU General Public License as published by the
6
* Free Software Foundation; either version 2 of the License, or (at your
7
* option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful, but WITHOUT
10
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12
* more details.
13
*
14
* You should have received a copy of the GNU General Public License along
15
* with this program. If not, see <http://www.gnu.org/licenses/>.
16
*/
17

18
#include "BoundingIntervalHierarchy.h"
19

20
#ifdef _MSC_VER
21
  #define isnan _isnan
22
#else
23
  #define isnan std::isnan
24
#endif
25

26
void BIH::buildHierarchy(std::vector<uint32> &tempTree, buildData &dat, BuildStats &stats)
27
{
28
    // create space for the first node
29
    tempTree.push_back(uint32(3 << 30)); // dummy leaf
30
    tempTree.insert(tempTree.end(), 2, 0);
31
    //tempTree.add(0);
32

33
    // seed bbox
34
    AABound gridBox = { bounds.low(), bounds.high() };
35
    AABound nodeBox = gridBox;
36
    // seed subdivide function
37
    subdivide(0, dat.numPrims - 1, tempTree, dat, gridBox, nodeBox, 0, 1, stats);
38
}
39

40
void BIH::subdivide(int left, int right, std::vector<uint32> &tempTree, buildData &dat, AABound &gridBox, AABound &nodeBox, int nodeIndex, int depth, BuildStats &stats)
41
{
42
    if ((right - left + 1) <= dat.maxPrims || depth >= MAX_STACK_SIZE)
43
    {
44
        // write leaf node
45
        stats.updateLeaf(depth, right - left + 1);
46
        createNode(tempTree, nodeIndex, left, right);
47
        return;
48
    }
49
    // calculate extents
50
    int axis = -1, prevAxis, rightOrig;
51
    float clipL = G3D::fnan(), clipR = G3D::fnan(), prevClip = G3D::fnan();
52
    float split = G3D::fnan(), prevSplit;
53
    bool wasLeft = true;
54
    while (true)
55
    {
56
        prevAxis = axis;
57
        prevSplit = split;
58
        // perform quick consistency checks
59
        G3D::Vector3 d( gridBox.hi - gridBox.lo );
60
        if (d.x < 0 || d.y < 0 || d.z < 0)
61
            throw std::logic_error("negative node extents");
62
        for (int i = 0; i < 3; i++)
63
        {
64
            if (nodeBox.hi[i] < gridBox.lo[i] || nodeBox.lo[i] > gridBox.hi[i])
65
            {
66
                //UI.printError(Module.ACCEL, "Reached tree area in error - discarding node with: %d objects", right - left + 1);
67
                throw std::logic_error("invalid node overlap");
68
            }
69
        }
70
        // find longest axis
71
        axis = d.primaryAxis();
72
        split = 0.5f * (gridBox.lo[axis] + gridBox.hi[axis]);
73
        // partition L/R subsets
74
        clipL = -G3D::inf();
75
        clipR = G3D::inf();
76
        rightOrig = right; // save this for later
77
        float nodeL = G3D::inf();
78
        float nodeR = -G3D::inf();
79
        for (int i = left; i <= right;)
80
        {
81
            int obj = dat.indices[i];
82
            float minb = dat.primBound[obj].low()[axis];
83
            float maxb = dat.primBound[obj].high()[axis];
84
            float center = (minb + maxb) * 0.5f;
85
            if (center <= split)
86
            {
87
                // stay left
88
                i++;
89
                if (clipL < maxb)
90
                    clipL = maxb;
91
            }
92
            else
93
            {
94
                // move to the right most
95
                int t = dat.indices[i];
96
                dat.indices[i] = dat.indices[right];
97
                dat.indices[right] = t;
98
                right--;
99
                if (clipR > minb)
100
                    clipR = minb;
101
            }
102
            nodeL = std::min(nodeL, minb);
103
            nodeR = std::max(nodeR, maxb);
104
        }
105
        // check for empty space
106
        if (nodeL > nodeBox.lo[axis] && nodeR < nodeBox.hi[axis])
107
        {
108
            float nodeBoxW = nodeBox.hi[axis] - nodeBox.lo[axis];
109
            float nodeNewW = nodeR - nodeL;
110
            // node box is too big compare to space occupied by primitives?
111
            if (1.3f * nodeNewW < nodeBoxW)
112
            {
113
                stats.updateBVH2();
114
                int nextIndex = tempTree.size();
115
                // allocate child
116
                tempTree.push_back(0);
117
                tempTree.push_back(0);
118
                tempTree.push_back(0);
119
                // write bvh2 clip node
120
                stats.updateInner();
121
                tempTree[nodeIndex + 0] = (axis << 30) | (1 << 29) | nextIndex;
122
                tempTree[nodeIndex + 1] = floatToRawIntBits(nodeL);
123
                tempTree[nodeIndex + 2] = floatToRawIntBits(nodeR);
124
                // update nodebox and recurse
125
                nodeBox.lo[axis] = nodeL;
126
                nodeBox.hi[axis] = nodeR;
127
                subdivide(left, rightOrig, tempTree, dat, gridBox, nodeBox, nextIndex, depth + 1, stats);
128
                return;
129
            }
130
        }
131
        // ensure we are making progress in the subdivision
132
        if (right == rightOrig)
133
        {
134
            // all left
135
            if (prevAxis == axis && G3D::fuzzyEq(prevSplit, split)) {
136
                // we are stuck here - create a leaf
137
                stats.updateLeaf(depth, right - left + 1);
138
                createNode(tempTree, nodeIndex, left, right);
139
                return;
140
            }
141
            if (clipL <= split) {
142
                // keep looping on left half
143
                gridBox.hi[axis] = split;
144
                prevClip = clipL;
145
                wasLeft = true;
146
                continue;
147
            }
148
            gridBox.hi[axis] = split;
149
            prevClip = G3D::fnan();
150
        }
151
        else if (left > right)
152
        {
153
            // all right
154
            right = rightOrig;
155
            if (prevAxis == axis && G3D::fuzzyEq(prevSplit, split)) {
156
                // we are stuck here - create a leaf
157
                stats.updateLeaf(depth, right - left + 1);
158
                createNode(tempTree, nodeIndex, left, right);
159
                return;
160
            }
161
            if (clipR >= split) {
162
                // keep looping on right half
163
                gridBox.lo[axis] = split;
164
                prevClip = clipR;
165
                wasLeft = false;
166
                continue;
167
            }
168
            gridBox.lo[axis] = split;
169
            prevClip = G3D::fnan();
170
        }
171
        else
172
        {
173
            // we are actually splitting stuff
174
            if (prevAxis != -1 && !isnan(prevClip))
175
            {
176
                // second time through - lets create the previous split
177
                // since it produced empty space
178
                int nextIndex = tempTree.size();
179
                // allocate child node
180
                tempTree.push_back(0);
181
                tempTree.push_back(0);
182
                tempTree.push_back(0);
183
                if (wasLeft) {
184
                    // create a node with a left child
185
                    // write leaf node
186
                    stats.updateInner();
187
                    tempTree[nodeIndex + 0] = (prevAxis << 30) | nextIndex;
188
                    tempTree[nodeIndex + 1] = floatToRawIntBits(prevClip);
189
                    tempTree[nodeIndex + 2] = floatToRawIntBits(G3D::inf());
190
                } else {
191
                    // create a node with a right child
192
                    // write leaf node
193
                    stats.updateInner();
194
                    tempTree[nodeIndex + 0] = (prevAxis << 30) | (nextIndex - 3);
195
                    tempTree[nodeIndex + 1] = floatToRawIntBits(-G3D::inf());
196
                    tempTree[nodeIndex + 2] = floatToRawIntBits(prevClip);
197
                }
198
                // count stats for the unused leaf
199
                depth++;
200
                stats.updateLeaf(depth, 0);
201
                // now we keep going as we are, with a new nodeIndex:
202
                nodeIndex = nextIndex;
203
            }
204
            break;
205
        }
206
    }
207
    // compute index of child nodes
208
    int nextIndex = tempTree.size();
209
    // allocate left node
210
    int nl = right - left + 1;
211
    int nr = rightOrig - (right + 1) + 1;
212
    if (nl > 0) {
213
        tempTree.push_back(0);
214
        tempTree.push_back(0);
215
        tempTree.push_back(0);
216
    } else
217
        nextIndex -= 3;
218
    // allocate right node
219
    if (nr > 0) {
220
        tempTree.push_back(0);
221
        tempTree.push_back(0);
222
        tempTree.push_back(0);
223
    }
224
    // write leaf node
225
    stats.updateInner();
226
    tempTree[nodeIndex + 0] = (axis << 30) | nextIndex;
227
    tempTree[nodeIndex + 1] = floatToRawIntBits(clipL);
228
    tempTree[nodeIndex + 2] = floatToRawIntBits(clipR);
229
    // prepare L/R child boxes
230
    AABound gridBoxL(gridBox), gridBoxR(gridBox);
231
    AABound nodeBoxL(nodeBox), nodeBoxR(nodeBox);
232
    gridBoxL.hi[axis] = gridBoxR.lo[axis] = split;
233
    nodeBoxL.hi[axis] = clipL;
234
    nodeBoxR.lo[axis] = clipR;
235
    // recurse
236
    if (nl > 0)
237
        subdivide(left, right, tempTree, dat, gridBoxL, nodeBoxL, nextIndex, depth + 1, stats);
238
    else
239
        stats.updateLeaf(depth + 1, 0);
240
    if (nr > 0)
241
        subdivide(right + 1, rightOrig, tempTree, dat, gridBoxR, nodeBoxR, nextIndex + 3, depth + 1, stats);
242
    else
243
        stats.updateLeaf(depth + 1, 0);
244
}
245

246
bool BIH::writeToFile(FILE* wf) const
247
{
248
    uint32 treeSize = tree.size();
249
    uint32 check=0, count;
250
    check += fwrite(&bounds.low(), sizeof(float), 3, wf);
251
    check += fwrite(&bounds.high(), sizeof(float), 3, wf);
252
    check += fwrite(&treeSize, sizeof(uint32), 1, wf);
253
    check += fwrite(&tree[0], sizeof(uint32), treeSize, wf);
254
    count = objects.size();
255
    check += fwrite(&count, sizeof(uint32), 1, wf);
256
    check += fwrite(&objects[0], sizeof(uint32), count, wf);
257
    return check == (3 + 3 + 2 + treeSize + count);
258
}
259

260
bool BIH::readFromFile(FILE* rf)
261
{
262
    uint32 treeSize;
263
    G3D::Vector3 lo, hi;
264
    uint32 check=0, count=0;
265
    check += fread(&lo, sizeof(float), 3, rf);
266
    check += fread(&hi, sizeof(float), 3, rf);
267
    bounds = G3D::AABox(lo, hi);
268
    check += fread(&treeSize, sizeof(uint32), 1, rf);
269
    tree.resize(treeSize);
270
    check += fread(&tree[0], sizeof(uint32), treeSize, rf);
271
    check += fread(&count, sizeof(uint32), 1, rf);
272
    objects.resize(count); // = new uint32[nObjects];
273
    check += fread(&objects[0], sizeof(uint32), count, rf);
274
    return uint64(check) == uint64(3 + 3 + 1 + 1 + uint64(treeSize) + uint64(count));
275
}
276

277
void BIH::BuildStats::updateLeaf(int depth, int n)
278
{
279
    numLeaves++;
280
    minDepth = std::min(depth, minDepth);
281
    maxDepth = std::max(depth, maxDepth);
282
    sumDepth += depth;
283
    minObjects = std::min(n, minObjects);
284
    maxObjects = std::max(n, maxObjects);
285
    sumObjects += n;
286
    int nl = std::min(n, 5);
287
    ++numLeavesN[nl];
288
}
289

290
void BIH::BuildStats::printStats()
291
{
292
    printf("Tree stats:\n");
293
    printf("  * Nodes:          %d\n", numNodes);
294
    printf("  * Leaves:         %d\n", numLeaves);
295
    printf("  * Objects: min    %d\n", minObjects);
296
    printf("             avg    %.2f\n", (float) sumObjects / numLeaves);
297
    printf("           avg(n>0) %.2f\n", (float) sumObjects / (numLeaves - numLeavesN[0]));
298
    printf("             max    %d\n", maxObjects);
299
    printf("  * Depth:   min    %d\n", minDepth);
300
    printf("             avg    %.2f\n", (float) sumDepth / numLeaves);
301
    printf("             max    %d\n", maxDepth);
302
    printf("  * Leaves w/: N=0  %3d%%\n", 100 * numLeavesN[0] / numLeaves);
303
    printf("               N=1  %3d%%\n", 100 * numLeavesN[1] / numLeaves);
304
    printf("               N=2  %3d%%\n", 100 * numLeavesN[2] / numLeaves);
305
    printf("               N=3  %3d%%\n", 100 * numLeavesN[3] / numLeaves);
306
    printf("               N=4  %3d%%\n", 100 * numLeavesN[4] / numLeaves);
307
    printf("               N>4  %3d%%\n", 100 * numLeavesN[5] / numLeaves);
308
    printf("  * BVH2 nodes:     %d (%3d%%)\n", numBVH2, 100 * numBVH2 / (numNodes + numLeaves - 2 * numBVH2));
309
}
310