| 1 | // Copyright 2009-2021 Intel Corporation | 
| 2 | // SPDX-License-Identifier: Apache-2.0 | 
| 3 |  | 
| 4 | #include "bvh.h" | 
| 5 | #include "bvh_statistics.h" | 
| 6 | #include "bvh_rotate.h" | 
| 7 | #include "../common/profile.h" | 
| 8 | #include "../../common/algorithms/parallel_prefix_sum.h" | 
| 9 |  | 
| 10 | #include "../builders/primrefgen.h" | 
| 11 | #include "../builders/bvh_builder_morton.h" | 
| 12 |  | 
| 13 | #include "../geometry/triangle.h" | 
| 14 | #include "../geometry/trianglev.h" | 
| 15 | #include "../geometry/trianglei.h" | 
| 16 | #include "../geometry/quadv.h" | 
| 17 | #include "../geometry/quadi.h" | 
| 18 | #include "../geometry/object.h" | 
| 19 | #include "../geometry/instance.h" | 
| 20 |  | 
| 21 | #if defined(__64BIT__) | 
| 22 | #  define ROTATE_TREE 1 // specifies number of tree rotation rounds to perform | 
| 23 | #else | 
| 24 | #  define ROTATE_TREE 0 // do not use tree rotations on 32 bit platforms, barrier bit in NodeRef will cause issues | 
| 25 | #endif | 
| 26 |  | 
| 27 | namespace embree  | 
| 28 | { | 
| 29 |   namespace isa | 
| 30 |   { | 
| 31 |     template<int N> | 
| 32 |     struct SetBVHNBounds | 
| 33 |     { | 
| 34 |       typedef BVHN<N> BVH; | 
| 35 |       typedef typename BVH::NodeRef NodeRef; | 
| 36 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 37 |       typedef typename BVH::AABBNode AABBNode; | 
| 38 |  | 
| 39 |       BVH* bvh; | 
| 40 |       __forceinline SetBVHNBounds (BVH* bvh) : bvh(bvh) {} | 
| 41 |  | 
| 42 |       __forceinline NodeRecord operator() (NodeRef ref, const NodeRecord* children, size_t num) | 
| 43 |       { | 
| 44 |         AABBNode* node = ref.getAABBNode(); | 
| 45 |  | 
| 46 |         BBox3fa res = empty; | 
| 47 |         for (size_t i=0; i<num; i++) { | 
| 48 |           const BBox3fa b = children[i].bounds; | 
| 49 |           res.extend(other: b); | 
| 50 |           node->setRef(i,children[i].ref); | 
| 51 |           node->setBounds(i,b); | 
| 52 |         } | 
| 53 |  | 
| 54 |         BBox3fx result = (BBox3fx&)res; | 
| 55 | #if ROTATE_TREE | 
| 56 |         if (N == 4) | 
| 57 |         { | 
| 58 |           size_t n = 0; | 
| 59 |           for (size_t i=0; i<num; i++) | 
| 60 |             n += children[i].bounds.lower.a; | 
| 61 |  | 
| 62 |           if (n >= 4096) { | 
| 63 |             for (size_t i=0; i<num; i++) { | 
| 64 |               if (children[i].bounds.lower.a < 4096) { | 
| 65 |                 for (int j=0; j<ROTATE_TREE; j++) | 
| 66 |                   BVHNRotate<N>::rotate(node->child(i)); | 
| 67 |                 node->child(i).setBarrier(); | 
| 68 |               } | 
| 69 |             } | 
| 70 |           } | 
| 71 |           result.lower.a = unsigned(n); | 
| 72 |         } | 
| 73 | #endif | 
| 74 |  | 
| 75 |         return NodeRecord(ref,result); | 
| 76 |       } | 
| 77 |     }; | 
| 78 |  | 
| 79 |     template<int N, typename Primitive> | 
| 80 |     struct CreateMortonLeaf; | 
| 81 |  | 
| 82 |     template<int N> | 
| 83 |     struct CreateMortonLeaf<N,Triangle4> | 
| 84 |     { | 
| 85 |       typedef BVHN<N> BVH; | 
| 86 |       typedef typename BVH::NodeRef NodeRef; | 
| 87 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 88 |  | 
| 89 |       __forceinline CreateMortonLeaf (TriangleMesh* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 90 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 91 |  | 
| 92 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 93 |       { | 
| 94 |         vfloat4 lower(pos_inf); | 
| 95 |         vfloat4 upper(neg_inf); | 
| 96 |         size_t items = current.size(); | 
| 97 |         size_t start = current.begin(); | 
| 98 |         assert(items<=4); | 
| 99 |          | 
| 100 |         /* allocate leaf node */ | 
| 101 |         Triangle4* accel = (Triangle4*) alloc.malloc1(bytes: sizeof(Triangle4),align: BVH::byteAlignment); | 
| 102 |         NodeRef ref = BVH::encodeLeaf((char*)accel,1); | 
| 103 |         vuint4 vgeomID = -1, vprimID = -1; | 
| 104 |         Vec3vf4 v0 = zero, v1 = zero, v2 = zero; | 
| 105 |         const TriangleMesh* __restrict__ const mesh = this->mesh; | 
| 106 |  | 
| 107 |         for (size_t i=0; i<items; i++) | 
| 108 |         { | 
| 109 |           const unsigned int primID = morton[start+i].index; | 
| 110 |           const TriangleMesh::Triangle& tri = mesh->triangle(i: primID); | 
| 111 |           const Vec3fa& p0 = mesh->vertex(i: tri.v[0]); | 
| 112 |           const Vec3fa& p1 = mesh->vertex(i: tri.v[1]); | 
| 113 |           const Vec3fa& p2 = mesh->vertex(i: tri.v[2]); | 
| 114 |           lower = min(a: lower,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 115 |           upper = max(a: upper,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 116 |           vgeomID [i] = geomID_; | 
| 117 |           vprimID [i] = primID; | 
| 118 |           v0.x[i] = p0.x; v0.y[i] = p0.y; v0.z[i] = p0.z; | 
| 119 |           v1.x[i] = p1.x; v1.y[i] = p1.y; v1.z[i] = p1.z; | 
| 120 |           v2.x[i] = p2.x; v2.y[i] = p2.y; v2.z[i] = p2.z; | 
| 121 |         } | 
| 122 |  | 
| 123 |         Triangle4::store_nt(dst: accel,src: Triangle4(v0,v1,v2,vgeomID,vprimID)); | 
| 124 |         BBox3fx box_o = BBox3fx((Vec3fx)lower,(Vec3fx)upper); | 
| 125 | #if ROTATE_TREE | 
| 126 |         if (N == 4) | 
| 127 |           box_o.lower.a = unsigned(current.size()); | 
| 128 | #endif | 
| 129 |         return NodeRecord(ref,box_o); | 
| 130 |       } | 
| 131 |      | 
| 132 |     private: | 
| 133 |       TriangleMesh* mesh; | 
| 134 |       BVHBuilderMorton::BuildPrim* morton; | 
| 135 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 136 |     }; | 
| 137 |      | 
| 138 |     template<int N> | 
| 139 |     struct CreateMortonLeaf<N,Triangle4v> | 
| 140 |     { | 
| 141 |       typedef BVHN<N> BVH; | 
| 142 |       typedef typename BVH::NodeRef NodeRef; | 
| 143 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 144 |  | 
| 145 |       __forceinline CreateMortonLeaf (TriangleMesh* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 146 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 147 |        | 
| 148 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 149 |       { | 
| 150 |         vfloat4 lower(pos_inf); | 
| 151 |         vfloat4 upper(neg_inf); | 
| 152 |         size_t items = current.size(); | 
| 153 |         size_t start = current.begin(); | 
| 154 |         assert(items<=4); | 
| 155 |          | 
| 156 |         /* allocate leaf node */ | 
| 157 |         Triangle4v* accel = (Triangle4v*) alloc.malloc1(bytes: sizeof(Triangle4v),align: BVH::byteAlignment); | 
| 158 |         NodeRef ref = BVH::encodeLeaf((char*)accel,1);        | 
| 159 |         vuint4 vgeomID = -1, vprimID = -1; | 
| 160 |         Vec3vf4 v0 = zero, v1 = zero, v2 = zero; | 
| 161 |         const TriangleMesh* __restrict__ mesh = this->mesh; | 
| 162 |  | 
| 163 |         for (size_t i=0; i<items; i++) | 
| 164 |         { | 
| 165 |           const unsigned int primID = morton[start+i].index; | 
| 166 |           const TriangleMesh::Triangle& tri = mesh->triangle(i: primID); | 
| 167 |           const Vec3fa& p0 = mesh->vertex(i: tri.v[0]); | 
| 168 |           const Vec3fa& p1 = mesh->vertex(i: tri.v[1]); | 
| 169 |           const Vec3fa& p2 = mesh->vertex(i: tri.v[2]); | 
| 170 |           lower = min(a: lower,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 171 |           upper = max(a: upper,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 172 |           vgeomID [i] = geomID_; | 
| 173 |           vprimID [i] = primID; | 
| 174 |           v0.x[i] = p0.x; v0.y[i] = p0.y; v0.z[i] = p0.z; | 
| 175 |           v1.x[i] = p1.x; v1.y[i] = p1.y; v1.z[i] = p1.z; | 
| 176 |           v2.x[i] = p2.x; v2.y[i] = p2.y; v2.z[i] = p2.z; | 
| 177 |         } | 
| 178 |         Triangle4v::store_nt(dst: accel,src: Triangle4v(v0,v1,v2,vgeomID,vprimID)); | 
| 179 |         BBox3fx box_o = BBox3fx((Vec3fx)lower,(Vec3fx)upper); | 
| 180 | #if ROTATE_TREE | 
| 181 |         if (N == 4) | 
| 182 |           box_o.lower.a = current.size(); | 
| 183 | #endif | 
| 184 |         return NodeRecord(ref,box_o); | 
| 185 |       } | 
| 186 |     private: | 
| 187 |       TriangleMesh* mesh; | 
| 188 |       BVHBuilderMorton::BuildPrim* morton; | 
| 189 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 190 |     }; | 
| 191 |  | 
| 192 |     template<int N> | 
| 193 |     struct CreateMortonLeaf<N,Triangle4i> | 
| 194 |     { | 
| 195 |       typedef BVHN<N> BVH; | 
| 196 |       typedef typename BVH::NodeRef NodeRef; | 
| 197 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 198 |  | 
| 199 |       __forceinline CreateMortonLeaf (TriangleMesh* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 200 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 201 |        | 
| 202 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 203 |       { | 
| 204 |         vfloat4 lower(pos_inf); | 
| 205 |         vfloat4 upper(neg_inf); | 
| 206 |         size_t items = current.size(); | 
| 207 |         size_t start = current.begin(); | 
| 208 |         assert(items<=4); | 
| 209 |          | 
| 210 |         /* allocate leaf node */ | 
| 211 |         Triangle4i* accel = (Triangle4i*) alloc.malloc1(bytes: sizeof(Triangle4i),align: BVH::byteAlignment); | 
| 212 |         NodeRef ref = BVH::encodeLeaf((char*)accel,1); | 
| 213 |          | 
| 214 |         vuint4 v0 = zero, v1 = zero, v2 = zero; | 
| 215 |         vuint4 vgeomID = -1, vprimID = -1; | 
| 216 |         const TriangleMesh* __restrict__ const mesh = this->mesh; | 
| 217 |          | 
| 218 |         for (size_t i=0; i<items; i++) | 
| 219 |         { | 
| 220 |           const unsigned int primID = morton[start+i].index; | 
| 221 |           const TriangleMesh::Triangle& tri = mesh->triangle(i: primID); | 
| 222 |           const Vec3fa& p0 = mesh->vertex(i: tri.v[0]); | 
| 223 |           const Vec3fa& p1 = mesh->vertex(i: tri.v[1]); | 
| 224 |           const Vec3fa& p2 = mesh->vertex(i: tri.v[2]); | 
| 225 |           lower = min(a: lower,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 226 |           upper = max(a: upper,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2); | 
| 227 |           vgeomID[i] = geomID_; | 
| 228 |           vprimID[i] = primID; | 
| 229 |           unsigned int int_stride = mesh->vertices0.getStride()/4; | 
| 230 |           v0[i] = tri.v[0] * int_stride;  | 
| 231 |           v1[i] = tri.v[1] * int_stride; | 
| 232 |           v2[i] = tri.v[2] * int_stride; | 
| 233 |         } | 
| 234 |          | 
| 235 |         for (size_t i=items; i<4; i++) | 
| 236 |         { | 
| 237 |           vgeomID[i] = vgeomID[0]; | 
| 238 |           vprimID[i] = -1; | 
| 239 |           v0[i] = 0; | 
| 240 |           v1[i] = 0;  | 
| 241 |           v2[i] = 0; | 
| 242 |         } | 
| 243 |         Triangle4i::store_nt(dst: accel,src: Triangle4i(v0,v1,v2,vgeomID,vprimID)); | 
| 244 |         BBox3fx box_o = BBox3fx((Vec3fx)lower,(Vec3fx)upper); | 
| 245 | #if ROTATE_TREE | 
| 246 |         if (N == 4) | 
| 247 |           box_o.lower.a = current.size(); | 
| 248 | #endif | 
| 249 |         return NodeRecord(ref,box_o); | 
| 250 |       } | 
| 251 |     private: | 
| 252 |       TriangleMesh* mesh; | 
| 253 |       BVHBuilderMorton::BuildPrim* morton; | 
| 254 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 255 |     }; | 
| 256 |  | 
| 257 |     template<int N> | 
| 258 |     struct CreateMortonLeaf<N,Quad4v> | 
| 259 |     { | 
| 260 |       typedef BVHN<N> BVH; | 
| 261 |       typedef typename BVH::NodeRef NodeRef; | 
| 262 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 263 |  | 
| 264 |       __forceinline CreateMortonLeaf (QuadMesh* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 265 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 266 |        | 
| 267 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 268 |       { | 
| 269 |         vfloat4 lower(pos_inf); | 
| 270 |         vfloat4 upper(neg_inf); | 
| 271 |         size_t items = current.size(); | 
| 272 |         size_t start = current.begin(); | 
| 273 |         assert(items<=4); | 
| 274 |          | 
| 275 |         /* allocate leaf node */ | 
| 276 |         Quad4v* accel = (Quad4v*) alloc.malloc1(bytes: sizeof(Quad4v),align: BVH::byteAlignment); | 
| 277 |         NodeRef ref = BVH::encodeLeaf((char*)accel,1); | 
| 278 |          | 
| 279 |         vuint4 vgeomID = -1, vprimID = -1; | 
| 280 |         Vec3vf4 v0 = zero, v1 = zero, v2 = zero, v3 = zero; | 
| 281 |         const QuadMesh* __restrict__ mesh = this->mesh; | 
| 282 |  | 
| 283 |         for (size_t i=0; i<items; i++) | 
| 284 |         { | 
| 285 |           const unsigned int primID = morton[start+i].index; | 
| 286 |           const QuadMesh::Quad& tri = mesh->quad(i: primID); | 
| 287 |           const Vec3fa& p0 = mesh->vertex(i: tri.v[0]); | 
| 288 |           const Vec3fa& p1 = mesh->vertex(i: tri.v[1]); | 
| 289 |           const Vec3fa& p2 = mesh->vertex(i: tri.v[2]); | 
| 290 |           const Vec3fa& p3 = mesh->vertex(i: tri.v[3]); | 
| 291 |           lower = min(a: lower,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2,e: (vfloat4)p3); | 
| 292 |           upper = max(a: upper,b: (vfloat4)p0,c: (vfloat4)p1,d: (vfloat4)p2,e: (vfloat4)p3); | 
| 293 |           vgeomID [i] = geomID_; | 
| 294 |           vprimID [i] = primID; | 
| 295 |           v0.x[i] = p0.x; v0.y[i] = p0.y; v0.z[i] = p0.z; | 
| 296 |           v1.x[i] = p1.x; v1.y[i] = p1.y; v1.z[i] = p1.z; | 
| 297 |           v2.x[i] = p2.x; v2.y[i] = p2.y; v2.z[i] = p2.z; | 
| 298 |           v3.x[i] = p3.x; v3.y[i] = p3.y; v3.z[i] = p3.z; | 
| 299 |         } | 
| 300 |         Quad4v::store_nt(dst: accel,src: Quad4v(v0,v1,v2,v3,vgeomID,vprimID)); | 
| 301 |         BBox3fx box_o = BBox3fx((Vec3fx)lower,(Vec3fx)upper); | 
| 302 | #if ROTATE_TREE | 
| 303 |         if (N == 4) | 
| 304 |           box_o.lower.a = current.size(); | 
| 305 | #endif | 
| 306 |         return NodeRecord(ref,box_o); | 
| 307 |       } | 
| 308 |     private: | 
| 309 |       QuadMesh* mesh; | 
| 310 |       BVHBuilderMorton::BuildPrim* morton; | 
| 311 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 312 |     }; | 
| 313 |  | 
| 314 |     template<int N> | 
| 315 |     struct CreateMortonLeaf<N,Object> | 
| 316 |     { | 
| 317 |       typedef BVHN<N> BVH; | 
| 318 |       typedef typename BVH::NodeRef NodeRef; | 
| 319 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 320 |  | 
| 321 |       __forceinline CreateMortonLeaf (UserGeometry* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 322 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 323 |        | 
| 324 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 325 |       { | 
| 326 |         vfloat4 lower(pos_inf); | 
| 327 |         vfloat4 upper(neg_inf); | 
| 328 |         size_t items = current.size(); | 
| 329 |         size_t start = current.begin(); | 
| 330 |          | 
| 331 |         /* allocate leaf node */ | 
| 332 |         Object* accel = (Object*) alloc.malloc1(bytes: items*sizeof(Object),align: BVH::byteAlignment); | 
| 333 |         NodeRef ref = BVH::encodeLeaf((char*)accel,items); | 
| 334 |         const UserGeometry* mesh = this->mesh; | 
| 335 |          | 
| 336 |         BBox3fa bounds = empty; | 
| 337 |         for (size_t i=0; i<items; i++) | 
| 338 |         { | 
| 339 |           const unsigned int index = morton[start+i].index; | 
| 340 |           const unsigned int primID = index;  | 
| 341 |           bounds.extend(other: mesh->bounds(i: primID)); | 
| 342 |           new (&accel[i]) Object(geomID_,primID); | 
| 343 |         } | 
| 344 |  | 
| 345 |         BBox3fx box_o = (BBox3fx&)bounds; | 
| 346 | #if ROTATE_TREE | 
| 347 |         if (N == 4) | 
| 348 |           box_o.lower.a = current.size(); | 
| 349 | #endif | 
| 350 |         return NodeRecord(ref,box_o); | 
| 351 |       } | 
| 352 |     private: | 
| 353 |       UserGeometry* mesh; | 
| 354 |       BVHBuilderMorton::BuildPrim* morton; | 
| 355 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 356 |     }; | 
| 357 |  | 
| 358 |     template<int N> | 
| 359 |     struct CreateMortonLeaf<N,InstancePrimitive> | 
| 360 |     { | 
| 361 |       typedef BVHN<N> BVH; | 
| 362 |       typedef typename BVH::NodeRef NodeRef; | 
| 363 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 364 |  | 
| 365 |       __forceinline CreateMortonLeaf (Instance* mesh, unsigned int geomID, BVHBuilderMorton::BuildPrim* morton) | 
| 366 |         : mesh(mesh), morton(morton), geomID_(geomID) {} | 
| 367 |        | 
| 368 |       __noinline NodeRecord operator() (const range<unsigned>& current, const FastAllocator::CachedAllocator& alloc) | 
| 369 |       { | 
| 370 |         vfloat4 lower(pos_inf); | 
| 371 |         vfloat4 upper(neg_inf); | 
| 372 |         size_t items = current.size(); | 
| 373 |         size_t start = current.begin(); | 
| 374 |         assert(items <= 1); | 
| 375 |          | 
| 376 |         /* allocate leaf node */ | 
| 377 |         InstancePrimitive* accel = (InstancePrimitive*) alloc.malloc1(bytes: items*sizeof(InstancePrimitive),align: BVH::byteAlignment); | 
| 378 |         NodeRef ref = BVH::encodeLeaf((char*)accel,items); | 
| 379 |         const Instance* instance = this->mesh; | 
| 380 |          | 
| 381 |         BBox3fa bounds = empty; | 
| 382 |         for (size_t i=0; i<items; i++) | 
| 383 |         { | 
| 384 |           const unsigned int primID = morton[start+i].index;  | 
| 385 |           bounds.extend(other: instance->bounds(i: primID)); | 
| 386 |           new (&accel[i]) InstancePrimitive(instance, geomID_); | 
| 387 |         } | 
| 388 |  | 
| 389 |         BBox3fx box_o = (BBox3fx&)bounds; | 
| 390 | #if ROTATE_TREE | 
| 391 |         if (N == 4) | 
| 392 |           box_o.lower.a = current.size(); | 
| 393 | #endif | 
| 394 |         return NodeRecord(ref,box_o); | 
| 395 |       } | 
| 396 |     private: | 
| 397 |       Instance* mesh; | 
| 398 |       BVHBuilderMorton::BuildPrim* morton; | 
| 399 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 400 |     }; | 
| 401 |  | 
| 402 |     template<typename Mesh> | 
| 403 |     struct CalculateMeshBounds | 
| 404 |     { | 
| 405 |       __forceinline CalculateMeshBounds (Mesh* mesh) | 
| 406 |         : mesh(mesh) {} | 
| 407 |        | 
| 408 |       __forceinline const BBox3fa operator() (const BVHBuilderMorton::BuildPrim& morton) { | 
| 409 |         return mesh->bounds(morton.index); | 
| 410 |       } | 
| 411 |        | 
| 412 |     private: | 
| 413 |       Mesh* mesh; | 
| 414 |     };         | 
| 415 |  | 
| 416 |     template<int N, typename Mesh, typename Primitive> | 
| 417 |     class BVHNMeshBuilderMorton : public Builder | 
| 418 |     { | 
| 419 |       typedef BVHN<N> BVH; | 
| 420 |       typedef typename BVH::AABBNode AABBNode; | 
| 421 |       typedef typename BVH::NodeRef NodeRef; | 
| 422 |       typedef typename BVH::NodeRecord NodeRecord; | 
| 423 |  | 
| 424 |     public: | 
| 425 |        | 
| 426 |       BVHNMeshBuilderMorton (BVH* bvh, Mesh* mesh, unsigned int geomID, const size_t minLeafSize, const size_t maxLeafSize, const size_t singleThreadThreshold = DEFAULT_SINGLE_THREAD_THRESHOLD) | 
| 427 |         : bvh(bvh), mesh(mesh), morton(bvh->device,0), settings(N,BVH::maxBuildDepth,minLeafSize,min(maxLeafSize,Primitive::max_size()*BVH::maxLeafBlocks),singleThreadThreshold), geomID_(geomID) {} | 
| 428 |        | 
| 429 |       /* build function */ | 
| 430 |       void build()  | 
| 431 |       { | 
| 432 |         /* we reset the allocator when the mesh size changed */ | 
| 433 |         if (mesh->numPrimitives != numPreviousPrimitives) { | 
| 434 |           bvh->alloc.clear(); | 
| 435 |           morton.clear(); | 
| 436 |         } | 
| 437 |         size_t numPrimitives = mesh->size(); | 
| 438 |         numPreviousPrimitives = numPrimitives; | 
| 439 |          | 
| 440 |         /* skip build for empty scene */ | 
| 441 |         if (numPrimitives == 0) { | 
| 442 |           bvh->set(BVH::emptyNode,empty,0); | 
| 443 |           return; | 
| 444 |         } | 
| 445 |          | 
| 446 |         /* preallocate arrays */ | 
| 447 |         morton.resize(new_size: numPrimitives); | 
| 448 |         size_t bytesEstimated = numPrimitives*sizeof(AABBNode)/(4*N) + size_t(1.2f*Primitive::blocks(numPrimitives)*sizeof(Primitive)); | 
| 449 |         size_t bytesMortonCodes = numPrimitives*sizeof(BVHBuilderMorton::BuildPrim); | 
| 450 |         bytesEstimated = max(a: bytesEstimated,b: bytesMortonCodes); // the first allocation block is reused to sort the morton codes | 
| 451 |         bvh->alloc.init(bytesMortonCodes,bytesMortonCodes,bytesEstimated); | 
| 452 |  | 
| 453 |         /* create morton code array */ | 
| 454 |         BVHBuilderMorton::BuildPrim* dest = (BVHBuilderMorton::BuildPrim*) bvh->alloc.specialAlloc(bytesMortonCodes); | 
| 455 |         size_t numPrimitivesGen = createMortonCodeArray<Mesh>(mesh,morton,bvh->scene->progressInterface); | 
| 456 |  | 
| 457 |         /* create BVH */ | 
| 458 |         SetBVHNBounds<N> setBounds(bvh); | 
| 459 |         CreateMortonLeaf<N,Primitive> createLeaf(mesh,geomID_,morton.data()); | 
| 460 |         CalculateMeshBounds<Mesh> calculateBounds(mesh); | 
| 461 |         auto root = BVHBuilderMorton::build<NodeRecord>( | 
| 462 |           typename BVH::CreateAlloc(bvh),  | 
| 463 |           typename BVH::AABBNode::Create(), | 
| 464 |           setBounds,createLeaf,calculateBounds,bvh->scene->progressInterface, | 
| 465 |           morton.data(),dest,numPrimitivesGen,settings); | 
| 466 |          | 
| 467 |         bvh->set(root.ref,LBBox3fa(root.bounds),numPrimitives); | 
| 468 |          | 
| 469 | #if ROTATE_TREE | 
| 470 |         if (N == 4) | 
| 471 |         { | 
| 472 |           for (int i=0; i<ROTATE_TREE; i++) | 
| 473 |             BVHNRotate<N>::rotate(bvh->root); | 
| 474 |           bvh->clearBarrier(bvh->root); | 
| 475 |         } | 
| 476 | #endif | 
| 477 |  | 
| 478 |         /* clear temporary data for static geometry */ | 
| 479 |         if (bvh->scene->isStaticAccel()) { | 
| 480 |           morton.clear(); | 
| 481 |         } | 
| 482 |         bvh->cleanup(); | 
| 483 |       } | 
| 484 |        | 
| 485 |       void clear() { | 
| 486 |         morton.clear(); | 
| 487 |       } | 
| 488 |        | 
| 489 |     private: | 
| 490 |       BVH* bvh; | 
| 491 |       Mesh* mesh; | 
| 492 |       mvector<BVHBuilderMorton::BuildPrim> morton; | 
| 493 |       BVHBuilderMorton::Settings settings; | 
| 494 |       unsigned int geomID_ = std::numeric_limits<unsigned int>::max(); | 
| 495 |       unsigned int numPreviousPrimitives = 0; | 
| 496 |     }; | 
| 497 |  | 
| 498 | #if defined(EMBREE_GEOMETRY_TRIANGLE) | 
| 499 |     Builder* BVH4Triangle4MeshBuilderMortonGeneral  (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,TriangleMesh,Triangle4> ((BVH4*)bvh,mesh,geomID,4,4); } | 
| 500 |     Builder* BVH4Triangle4vMeshBuilderMortonGeneral (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,TriangleMesh,Triangle4v>((BVH4*)bvh,mesh,geomID,4,4); } | 
| 501 |     Builder* BVH4Triangle4iMeshBuilderMortonGeneral (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,TriangleMesh,Triangle4i>((BVH4*)bvh,mesh,geomID,4,4); } | 
| 502 | #if defined(__AVX__) | 
| 503 |     Builder* BVH8Triangle4MeshBuilderMortonGeneral  (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,TriangleMesh,Triangle4> ((BVH8*)bvh,mesh,geomID,4,4); } | 
| 504 |     Builder* BVH8Triangle4vMeshBuilderMortonGeneral (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,TriangleMesh,Triangle4v>((BVH8*)bvh,mesh,geomID,4,4); } | 
| 505 |     Builder* BVH8Triangle4iMeshBuilderMortonGeneral (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,TriangleMesh,Triangle4i>((BVH8*)bvh,mesh,geomID,4,4); } | 
| 506 | #endif | 
| 507 | #endif | 
| 508 |  | 
| 509 | #if defined(EMBREE_GEOMETRY_QUAD) | 
| 510 |     Builder* BVH4Quad4vMeshBuilderMortonGeneral (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,QuadMesh,Quad4v>((BVH4*)bvh,mesh,geomID,4,4); } | 
| 511 | #if defined(__AVX__) | 
| 512 |     Builder* BVH8Quad4vMeshBuilderMortonGeneral (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,QuadMesh,Quad4v>((BVH8*)bvh,mesh,geomID,4,4); } | 
| 513 | #endif | 
| 514 | #endif | 
| 515 |  | 
| 516 | #if defined(EMBREE_GEOMETRY_USER) | 
| 517 |     Builder* BVH4VirtualMeshBuilderMortonGeneral (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,UserGeometry,Object>((BVH4*)bvh,mesh,geomID,1,BVH4::maxLeafBlocks); } | 
| 518 | #if defined(__AVX__) | 
| 519 |     Builder* BVH8VirtualMeshBuilderMortonGeneral (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,UserGeometry,Object>((BVH8*)bvh,mesh,geomID,1,BVH4::maxLeafBlocks); }     | 
| 520 | #endif | 
| 521 | #endif | 
| 522 |  | 
| 523 | #if defined(EMBREE_GEOMETRY_INSTANCE) | 
| 524 |     Builder* BVH4InstanceMeshBuilderMortonGeneral (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<4,Instance,InstancePrimitive>((BVH4*)bvh,mesh,gtype,geomID,1,BVH4::maxLeafBlocks); } | 
| 525 | #if defined(__AVX__) | 
| 526 |     Builder* BVH8InstanceMeshBuilderMortonGeneral (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new class BVHNMeshBuilderMorton<8,Instance,InstancePrimitive>((BVH8*)bvh,mesh,gtype,geomID,1,BVH4::maxLeafBlocks); }     | 
| 527 | #endif | 
| 528 | #endif | 
| 529 |  | 
| 530 |   } | 
| 531 | } | 
| 532 |  |