1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh_refit.h"
5#include "bvh_statistics.h"
6
7#include "../geometry/linei.h"
8#include "../geometry/triangle.h"
9#include "../geometry/trianglev.h"
10#include "../geometry/trianglei.h"
11#include "../geometry/quadv.h"
12#include "../geometry/object.h"
13#include "../geometry/instance.h"
14
15namespace embree
16{
17 namespace isa
18 {
19 static const size_t SINGLE_THREAD_THRESHOLD = 4*1024;
20
21 template<int N>
22 __forceinline bool compare(const typename BVHN<N>::NodeRef* a, const typename BVHN<N>::NodeRef* b)
23 {
24 size_t sa = *(size_t*)&a->node()->lower_x;
25 size_t sb = *(size_t*)&b->node()->lower_x;
26 return sa < sb;
27 }
28
29 template<int N>
30 BVHNRefitter<N>::BVHNRefitter (BVH* bvh, const LeafBoundsInterface& leafBounds)
31 : bvh(bvh), leafBounds(leafBounds), numSubTrees(0)
32 {
33 }
34
35 template<int N>
36 void BVHNRefitter<N>::refit()
37 {
38 if (bvh->numPrimitives <= SINGLE_THREAD_THRESHOLD) {
39 bvh->bounds = LBBox3fa(recurse_bottom(bvh->root));
40 }
41 else
42 {
43 BBox3fa subTreeBounds[MAX_NUM_SUB_TREES];
44 numSubTrees = 0;
45 gather_subtree_refs(bvh->root,numSubTrees,0);
46 if (numSubTrees)
47 parallel_for(size_t(0), numSubTrees, size_t(1), [&](const range<size_t>& r) {
48 for (size_t i=r.begin(); i<r.end(); i++) {
49 NodeRef& ref = subTrees[i];
50 subTreeBounds[i] = recurse_bottom(ref);
51 }
52 });
53
54 numSubTrees = 0;
55 bvh->bounds = LBBox3fa(refit_toplevel(bvh->root,numSubTrees,subTreeBounds,0));
56 }
57 }
58
59 template<int N>
60 void BVHNRefitter<N>::gather_subtree_refs(NodeRef& ref,
61 size_t &subtrees,
62 const size_t depth)
63 {
64 if (depth >= MAX_SUB_TREE_EXTRACTION_DEPTH)
65 {
66 assert(subtrees < MAX_NUM_SUB_TREES);
67 subTrees[subtrees++] = ref;
68 return;
69 }
70
71 if (ref.isAABBNode())
72 {
73 AABBNode* node = ref.getAABBNode();
74 for (size_t i=0; i<N; i++) {
75 NodeRef& child = node->child(i);
76 if (unlikely(child == BVH::emptyNode)) continue;
77 gather_subtree_refs(child,subtrees,depth+1);
78 }
79 }
80 }
81
82 template<int N>
83 BBox3fa BVHNRefitter<N>::refit_toplevel(NodeRef& ref,
84 size_t &subtrees,
85 const BBox3fa *const subTreeBounds,
86 const size_t depth)
87 {
88 if (depth >= MAX_SUB_TREE_EXTRACTION_DEPTH)
89 {
90 assert(subtrees < MAX_NUM_SUB_TREES);
91 assert(subTrees[subtrees] == ref);
92 return subTreeBounds[subtrees++];
93 }
94
95 if (ref.isAABBNode())
96 {
97 AABBNode* node = ref.getAABBNode();
98 BBox3fa bounds[N];
99
100 for (size_t i=0; i<N; i++)
101 {
102 NodeRef& child = node->child(i);
103
104 if (unlikely(child == BVH::emptyNode))
105 bounds[i] = BBox3fa(empty);
106 else
107 bounds[i] = refit_toplevel(child,subtrees,subTreeBounds,depth+1);
108 }
109
110 BBox3vf<N> boundsT = transpose<N>(bounds);
111
112 /* set new bounds */
113 node->lower_x = boundsT.lower.x;
114 node->lower_y = boundsT.lower.y;
115 node->lower_z = boundsT.lower.z;
116 node->upper_x = boundsT.upper.x;
117 node->upper_y = boundsT.upper.y;
118 node->upper_z = boundsT.upper.z;
119
120 return merge<N>(bounds);
121 }
122 else
123 return leafBounds.leafBounds(ref);
124 }
125
126 // =========================================================
127 // =========================================================
128 // =========================================================
129
130
131 template<int N>
132 BBox3fa BVHNRefitter<N>::recurse_bottom(NodeRef& ref)
133 {
134 /* this is a leaf node */
135 if (unlikely(ref.isLeaf()))
136 return leafBounds.leafBounds(ref);
137
138 /* recurse if this is an internal node */
139 AABBNode* node = ref.getAABBNode();
140
141 /* enable exclusive prefetch for >= AVX platforms */
142#if defined(__AVX__)
143 BVH::prefetchW(ref);
144#endif
145 BBox3fa bounds[N];
146
147 for (size_t i=0; i<N; i++)
148 if (unlikely(node->child(i) == BVH::emptyNode))
149 {
150 bounds[i] = BBox3fa(empty);
151 }
152 else
153 bounds[i] = recurse_bottom(node->child(i));
154
155 /* AOS to SOA transform */
156 BBox3vf<N> boundsT = transpose<N>(bounds);
157
158 /* set new bounds */
159 node->lower_x = boundsT.lower.x;
160 node->lower_y = boundsT.lower.y;
161 node->lower_z = boundsT.lower.z;
162 node->upper_x = boundsT.upper.x;
163 node->upper_y = boundsT.upper.y;
164 node->upper_z = boundsT.upper.z;
165
166 return merge<N>(bounds);
167 }
168
169 template<int N, typename Mesh, typename Primitive>
170 BVHNRefitT<N,Mesh,Primitive>::BVHNRefitT (BVH* bvh, Builder* builder, Mesh* mesh, size_t mode)
171 : bvh(bvh), builder(builder), refitter(new BVHNRefitter<N>(bvh,*(typename BVHNRefitter<N>::LeafBoundsInterface*)this)), mesh(mesh), topologyVersion(0) {}
172
173 template<int N, typename Mesh, typename Primitive>
174 void BVHNRefitT<N,Mesh,Primitive>::clear()
175 {
176 if (builder)
177 builder->clear();
178 }
179
180 template<int N, typename Mesh, typename Primitive>
181 void BVHNRefitT<N,Mesh,Primitive>::build()
182 {
183 if (mesh->topologyChanged(topologyVersion)) {
184 topologyVersion = mesh->getTopologyVersion();
185 builder->build();
186 }
187 else
188 refitter->refit();
189 }
190
191 template class BVHNRefitter<4>;
192#if defined(__AVX__)
193 template class BVHNRefitter<8>;
194#endif
195
196#if defined(EMBREE_GEOMETRY_TRIANGLE)
197 Builder* BVH4Triangle4MeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
198 Builder* BVH4Triangle4vMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
199 Builder* BVH4Triangle4iMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
200
201 Builder* BVH4Triangle4MeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4> ((BVH4*)accel,BVH4Triangle4MeshBuilderSAH (accel,mesh,geomID,mode),mesh,mode); }
202 Builder* BVH4Triangle4vMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4v>((BVH4*)accel,BVH4Triangle4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
203 Builder* BVH4Triangle4iMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4i>((BVH4*)accel,BVH4Triangle4iMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
204#if defined(__AVX__)
205 Builder* BVH8Triangle4MeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
206 Builder* BVH8Triangle4vMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
207 Builder* BVH8Triangle4iMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
208
209 Builder* BVH8Triangle4MeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4> ((BVH8*)accel,BVH8Triangle4MeshBuilderSAH (accel,mesh,geomID,mode),mesh,mode); }
210 Builder* BVH8Triangle4vMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4v>((BVH8*)accel,BVH8Triangle4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
211 Builder* BVH8Triangle4iMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4i>((BVH8*)accel,BVH8Triangle4iMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
212#endif
213#endif
214
215#if defined(EMBREE_GEOMETRY_QUAD)
216 Builder* BVH4Quad4vMeshBuilderSAH (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode);
217 Builder* BVH4Quad4vMeshRefitSAH (void* accel, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,QuadMesh,Quad4v>((BVH4*)accel,BVH4Quad4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
218
219#if defined(__AVX__)
220 Builder* BVH8Quad4vMeshBuilderSAH (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode);
221 Builder* BVH8Quad4vMeshRefitSAH (void* accel, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,QuadMesh,Quad4v>((BVH8*)accel,BVH8Quad4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
222#endif
223
224#endif
225
226#if defined(EMBREE_GEOMETRY_USER)
227 Builder* BVH4VirtualMeshBuilderSAH (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode);
228 Builder* BVH4VirtualMeshRefitSAH (void* accel, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,UserGeometry,Object>((BVH4*)accel,BVH4VirtualMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
229
230#if defined(__AVX__)
231 Builder* BVH8VirtualMeshBuilderSAH (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode);
232 Builder* BVH8VirtualMeshRefitSAH (void* accel, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,UserGeometry,Object>((BVH8*)accel,BVH8VirtualMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
233#endif
234#endif
235
236#if defined(EMBREE_GEOMETRY_INSTANCE)
237 Builder* BVH4InstanceMeshBuilderSAH (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
238 Builder* BVH4InstanceMeshRefitSAH (void* accel, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,Instance,InstancePrimitive>((BVH4*)accel,BVH4InstanceMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
239
240#if defined(__AVX__)
241 Builder* BVH8InstanceMeshBuilderSAH (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
242 Builder* BVH8InstanceMeshRefitSAH (void* accel, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,Instance,InstancePrimitive>((BVH8*)accel,BVH8InstanceMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
243#endif
244#endif
245
246 }
247}
248