1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh_rotate.h"
5
6namespace embree
7{
8 namespace isa
9 {
10 /*! Computes half surface area of box. */
11 __forceinline float halfArea3f(const BBox<vfloat4>& box) {
12 const vfloat4 d = box.size();
13 const vfloat4 a = d*shuffle<1,2,0,3>(d);
14 return a[0]+a[1]+a[2];
15 }
16
17 size_t BVHNRotate<4>::rotate(NodeRef parentRef, size_t depth)
18 {
19 /*! nothing to rotate if we reached a leaf node. */
20 if (parentRef.isBarrier()) return 0;
21 if (parentRef.isLeaf()) return 0;
22 AABBNode* parent = parentRef.getAABBNode();
23
24 /*! rotate all children first */
25 vint4 cdepth;
26 for (size_t c=0; c<4; c++)
27 cdepth[c] = (int)rotate(parent->child(c),depth+1);
28
29 /* compute current areas of all children */
30 vfloat4 sizeX = parent->upper_x-parent->lower_x;
31 vfloat4 sizeY = parent->upper_y-parent->lower_y;
32 vfloat4 sizeZ = parent->upper_z-parent->lower_z;
33 vfloat4 childArea = madd(sizeX,(sizeY + sizeZ),sizeY*sizeZ);
34
35 /*! get node bounds */
36 BBox<vfloat4> child1_0,child1_1,child1_2,child1_3;
37 parent->bounds(child1_0,child1_1,child1_2,child1_3);
38
39 /*! Find best rotation. We pick a first child (child1) and a sub-child
40 (child2child) of a different second child (child2), and swap child1
41 and child2child. We perform the best such swap. */
42 float bestArea = 0;
43 size_t bestChild1 = -1, bestChild2 = -1, bestChild2Child = -1;
44 for (size_t c2=0; c2<4; c2++)
45 {
46 /*! ignore leaf nodes as we cannot descent into them */
47 if (parent->child(c2).isBarrier()) continue;
48 if (parent->child(c2).isLeaf()) continue;
49 AABBNode* child2 = parent->child(c2).getAABBNode();
50
51 /*! transpose child bounds */
52 BBox<vfloat4> child2c0,child2c1,child2c2,child2c3;
53 child2->bounds(child2c0,child2c1,child2c2,child2c3);
54
55 /*! put child1_0 at each child2 position */
56 float cost00 = halfArea3f(merge(child1_0,child2c1,child2c2,child2c3));
57 float cost01 = halfArea3f(merge(child2c0,child1_0,child2c2,child2c3));
58 float cost02 = halfArea3f(merge(child2c0,child2c1,child1_0,child2c3));
59 float cost03 = halfArea3f(merge(child2c0,child2c1,child2c2,child1_0));
60 vfloat4 cost0 = vfloat4(cost00,cost01,cost02,cost03);
61 vfloat4 min0 = vreduce_min(cost0);
62 int pos0 = (int)bsf(movemask(min0 == cost0));
63
64 /*! put child1_1 at each child2 position */
65 float cost10 = halfArea3f(merge(child1_1,child2c1,child2c2,child2c3));
66 float cost11 = halfArea3f(merge(child2c0,child1_1,child2c2,child2c3));
67 float cost12 = halfArea3f(merge(child2c0,child2c1,child1_1,child2c3));
68 float cost13 = halfArea3f(merge(child2c0,child2c1,child2c2,child1_1));
69 vfloat4 cost1 = vfloat4(cost10,cost11,cost12,cost13);
70 vfloat4 min1 = vreduce_min(cost1);
71 int pos1 = (int)bsf(movemask(min1 == cost1));
72
73 /*! put child1_2 at each child2 position */
74 float cost20 = halfArea3f(merge(child1_2,child2c1,child2c2,child2c3));
75 float cost21 = halfArea3f(merge(child2c0,child1_2,child2c2,child2c3));
76 float cost22 = halfArea3f(merge(child2c0,child2c1,child1_2,child2c3));
77 float cost23 = halfArea3f(merge(child2c0,child2c1,child2c2,child1_2));
78 vfloat4 cost2 = vfloat4(cost20,cost21,cost22,cost23);
79 vfloat4 min2 = vreduce_min(cost2);
80 int pos2 = (int)bsf(movemask(min2 == cost2));
81
82 /*! put child1_3 at each child2 position */
83 float cost30 = halfArea3f(merge(child1_3,child2c1,child2c2,child2c3));
84 float cost31 = halfArea3f(merge(child2c0,child1_3,child2c2,child2c3));
85 float cost32 = halfArea3f(merge(child2c0,child2c1,child1_3,child2c3));
86 float cost33 = halfArea3f(merge(child2c0,child2c1,child2c2,child1_3));
87 vfloat4 cost3 = vfloat4(cost30,cost31,cost32,cost33);
88 vfloat4 min3 = vreduce_min(cost3);
89 int pos3 = (int)bsf(movemask(min3 == cost3));
90
91 /*! find best other child */
92 vfloat4 area0123 = vfloat4(extract<0>(min0),extract<0>(min1),extract<0>(min2),extract<0>(min3)) - vfloat4(childArea[c2]);
93 int pos[4] = { pos0,pos1,pos2,pos3 };
94 const size_t mbd = BVH4::maxBuildDepth;
95 vbool4 valid = vint4(int(depth+1))+cdepth <= vint4(mbd); // only select swaps that fulfill depth constraints
96 valid &= vint4(int(c2)) != vint4(step);
97 if (none(valid)) continue;
98 size_t c1 = select_min(valid,area0123);
99 float area = area0123[c1];
100 if (c1 == c2) continue; // can happen if bounds are NANs
101
102 /*! accept a swap when it reduces cost and is not swapping a node with itself */
103 if (area < bestArea) {
104 bestArea = area;
105 bestChild1 = c1;
106 bestChild2 = c2;
107 bestChild2Child = pos[c1];
108 }
109 }
110
111 /*! if we did not find a swap that improves the SAH then do nothing */
112 if (bestChild1 == size_t(-1)) return 1+reduce_max(cdepth);
113
114 /*! perform the best found tree rotation */
115 AABBNode* child2 = parent->child(bestChild2).getAABBNode();
116 AABBNode::swap(parent,bestChild1,child2,bestChild2Child);
117 parent->setBounds(bestChild2,child2->bounds());
118 AABBNode::compact(parent);
119 AABBNode::compact(child2);
120
121 /*! This returned depth is conservative as the child that was
122 * pulled up in the tree could have been on the critical path. */
123 cdepth[bestChild1]++; // bestChild1 was pushed down one level
124 return 1+reduce_max(cdepth);
125 }
126 }
127}
128