1 // Copyright 2009-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3 
4 #pragma once
5 
6 /* include all node types */
7 #include "bvh_node_aabb.h"
8 #include "bvh_node_aabb_mb.h"
9 #include "bvh_node_aabb_mb4d.h"
10 #include "bvh_node_obb.h"
11 #include "bvh_node_obb_mb.h"
12 #include "bvh_node_qaabb.h"
13 
14 namespace embree
15 {
16   /*! flags used to enable specific node types in intersectors */
17   enum BVHNodeFlags
18   {
19     BVH_FLAG_ALIGNED_NODE = 0x00001,
20     BVH_FLAG_ALIGNED_NODE_MB = 0x00010,
21     BVH_FLAG_UNALIGNED_NODE = 0x00100,
22     BVH_FLAG_UNALIGNED_NODE_MB = 0x01000,
23     BVH_FLAG_QUANTIZED_NODE = 0x100000,
24     BVH_FLAG_ALIGNED_NODE_MB4D = 0x1000000,
25 
26     /* short versions */
27     BVH_AN1 = BVH_FLAG_ALIGNED_NODE,
28     BVH_AN2 = BVH_FLAG_ALIGNED_NODE_MB,
29     BVH_AN2_AN4D = BVH_FLAG_ALIGNED_NODE_MB | BVH_FLAG_ALIGNED_NODE_MB4D,
30     BVH_UN1 = BVH_FLAG_UNALIGNED_NODE,
31     BVH_UN2 = BVH_FLAG_UNALIGNED_NODE_MB,
32     BVH_MB = BVH_FLAG_ALIGNED_NODE_MB | BVH_FLAG_UNALIGNED_NODE_MB | BVH_FLAG_ALIGNED_NODE_MB4D,
33     BVH_AN1_UN1 = BVH_FLAG_ALIGNED_NODE | BVH_FLAG_UNALIGNED_NODE,
34     BVH_AN2_UN2 = BVH_FLAG_ALIGNED_NODE_MB | BVH_FLAG_UNALIGNED_NODE_MB,
35     BVH_AN2_AN4D_UN2 = BVH_FLAG_ALIGNED_NODE_MB | BVH_FLAG_ALIGNED_NODE_MB4D | BVH_FLAG_UNALIGNED_NODE_MB,
36     BVH_QN1 = BVH_FLAG_QUANTIZED_NODE
37   };
38 
39   /*! Multi BVH with N children. Each node stores the bounding box of
40    * it's N children as well as N child references. */
41   template<int N>
42     class BVHN : public AccelData
43   {
44     ALIGNED_CLASS_(16);
45   public:
46 
47     /*! forward declaration of node ref type */
48     typedef NodeRefPtr<N> NodeRef;
49     typedef BaseNode_t<NodeRef,N> BaseNode;
50     typedef AABBNode_t<NodeRef,N> AABBNode;
51     typedef AABBNodeMB_t<NodeRef,N> AABBNodeMB;
52     typedef AABBNodeMB4D_t<NodeRef,N> AABBNodeMB4D;
53     typedef OBBNode_t<NodeRef,N> OBBNode;
54     typedef OBBNodeMB_t<NodeRef,N> OBBNodeMB;
55     typedef QuantizedBaseNode_t<N> QuantizedBaseNode;
56     typedef QuantizedBaseNodeMB_t<N> QuantizedBaseNodeMB;
57     typedef QuantizedNode_t<NodeRef,N> QuantizedNode;
58 
59     /*! Number of bytes the nodes and primitives are minimally aligned to.*/
60     static const size_t byteAlignment = 16;
61     static const size_t byteNodeAlignment = 4*N;
62 
63     /*! Empty node */
64     static const size_t emptyNode = NodeRef::emptyNode;
65 
66     /*! Invalid node, used as marker in traversal */
67     static const size_t invalidNode = NodeRef::invalidNode;
68     static const size_t popRay      = NodeRef::popRay;
69 
70     /*! Maximum depth of the BVH. */
71     static const size_t maxBuildDepth = 32;
72     static const size_t maxBuildDepthLeaf = maxBuildDepth+8;
73     static const size_t maxDepth = 2*maxBuildDepthLeaf; // 2x because of two level builder
74 
75     /*! Maximum number of primitive blocks in a leaf. */
76     static const size_t maxLeafBlocks = NodeRef::maxLeafBlocks;
77 
78   public:
79 
80     /*! Builder interface to create allocator */
81     struct CreateAlloc : public FastAllocator::Create {
CreateAllocCreateAlloc82       __forceinline CreateAlloc (BVHN* bvh) : FastAllocator::Create(&bvh->alloc) {}
83     };
84 
85     typedef BVHNodeRecord<NodeRef>     NodeRecord;
86     typedef BVHNodeRecordMB<NodeRef>   NodeRecordMB;
87     typedef BVHNodeRecordMB4D<NodeRef> NodeRecordMB4D;
88 
89   public:
90 
91     /*! BVHN default constructor. */
92     BVHN (const PrimitiveType& primTy, Scene* scene);
93 
94     /*! BVHN destruction */
95     ~BVHN ();
96 
97     /*! clears the acceleration structure */
98     void clear();
99 
100     /*! sets BVH members after build */
101     void set (NodeRef root, const LBBox3fa& bounds, size_t numPrimitives);
102 
103     /*! Clears the barrier bits of a subtree. */
104     void clearBarrier(NodeRef& node);
105 
106     /*! lays out num large nodes of the BVH */
107     void layoutLargeNodes(size_t num);
108     NodeRef layoutLargeNodesRecursion(NodeRef& node, const FastAllocator::CachedAllocator& allocator);
109 
110     /*! called by all builders before build starts */
111     double preBuild(const std::string& builderName);
112 
113     /*! called by all builders after build ended */
114     void postBuild(double t0);
115 
116     /*! allocator class */
117     struct Allocator {
118       BVHN* bvh;
AllocatorAllocator119       Allocator (BVHN* bvh) : bvh(bvh) {}
operatorAllocator120       __forceinline void* operator() (size_t bytes) const {
121         return bvh->alloc._threadLocal()->malloc(&bvh->alloc,bytes);
122       }
123     };
124 
125     /*! post build cleanup */
cleanup()126     void cleanup() {
127       alloc.cleanup();
128     }
129 
130   public:
131 
132     /*! Encodes a node */
encodeNode(AABBNode * node)133     static __forceinline NodeRef encodeNode(AABBNode* node) { return NodeRef::encodeNode(node); }
encodeNode(AABBNodeMB * node)134     static __forceinline NodeRef encodeNode(AABBNodeMB* node) { return NodeRef::encodeNode(node); }
encodeNode(AABBNodeMB4D * node)135     static __forceinline NodeRef encodeNode(AABBNodeMB4D* node) { return NodeRef::encodeNode(node); }
encodeNode(OBBNode * node)136     static __forceinline NodeRef encodeNode(OBBNode* node) { return NodeRef::encodeNode(node); }
encodeNode(OBBNodeMB * node)137     static __forceinline NodeRef encodeNode(OBBNodeMB* node) { return NodeRef::encodeNode(node); }
encodeLeaf(void * tri,size_t num)138     static __forceinline NodeRef encodeLeaf(void* tri, size_t num) { return NodeRef::encodeLeaf(tri,num); }
encodeTypedLeaf(void * ptr,size_t ty)139     static __forceinline NodeRef encodeTypedLeaf(void* ptr, size_t ty) { return NodeRef::encodeTypedLeaf(ptr,ty); }
140 
141   public:
142 
143     /*! Prefetches the node this reference points to */
144     __forceinline static void prefetch(const NodeRef ref, int types=0)
145     {
146 #if defined(__AVX512PF__) // MIC
147       if (types != BVH_FLAG_QUANTIZED_NODE) {
148         prefetchL2(((char*)ref.ptr)+0*64);
149         prefetchL2(((char*)ref.ptr)+1*64);
150         if ((N >= 8) || (types > BVH_FLAG_ALIGNED_NODE)) {
151           prefetchL2(((char*)ref.ptr)+2*64);
152           prefetchL2(((char*)ref.ptr)+3*64);
153         }
154         if ((N >= 8) && (types > BVH_FLAG_ALIGNED_NODE)) {
155           /* KNL still needs L2 prefetches for large nodes */
156           prefetchL2(((char*)ref.ptr)+4*64);
157           prefetchL2(((char*)ref.ptr)+5*64);
158           prefetchL2(((char*)ref.ptr)+6*64);
159           prefetchL2(((char*)ref.ptr)+7*64);
160         }
161       }
162       else
163       {
164         /* todo: reduce if 32bit offsets are enabled */
165         prefetchL2(((char*)ref.ptr)+0*64);
166         prefetchL2(((char*)ref.ptr)+1*64);
167         prefetchL2(((char*)ref.ptr)+2*64);
168       }
169 #else
170       if (types != BVH_FLAG_QUANTIZED_NODE) {
171         prefetchL1(((char*)ref.ptr)+0*64);
172         prefetchL1(((char*)ref.ptr)+1*64);
173         if ((N >= 8) || (types > BVH_FLAG_ALIGNED_NODE)) {
174           prefetchL1(((char*)ref.ptr)+2*64);
175           prefetchL1(((char*)ref.ptr)+3*64);
176         }
177         if ((N >= 8) && (types > BVH_FLAG_ALIGNED_NODE)) {
178           /* deactivate for large nodes on Xeon, as it introduces regressions */
179           //prefetchL1(((char*)ref.ptr)+4*64);
180           //prefetchL1(((char*)ref.ptr)+5*64);
181           //prefetchL1(((char*)ref.ptr)+6*64);
182           //prefetchL1(((char*)ref.ptr)+7*64);
183         }
184       }
185       else
186       {
187         /* todo: reduce if 32bit offsets are enabled */
188         prefetchL1(((char*)ref.ptr)+0*64);
189         prefetchL1(((char*)ref.ptr)+1*64);
190         prefetchL1(((char*)ref.ptr)+2*64);
191       }
192 #endif
193     }
194 
195     __forceinline static void prefetchW(const NodeRef ref, int types=0)
196     {
197       embree::prefetchEX(((char*)ref.ptr)+0*64);
198       embree::prefetchEX(((char*)ref.ptr)+1*64);
199       if ((N >= 8) || (types > BVH_FLAG_ALIGNED_NODE)) {
200         embree::prefetchEX(((char*)ref.ptr)+2*64);
201         embree::prefetchEX(((char*)ref.ptr)+3*64);
202       }
203       if ((N >= 8) && (types > BVH_FLAG_ALIGNED_NODE)) {
204         embree::prefetchEX(((char*)ref.ptr)+4*64);
205         embree::prefetchEX(((char*)ref.ptr)+5*64);
206         embree::prefetchEX(((char*)ref.ptr)+6*64);
207         embree::prefetchEX(((char*)ref.ptr)+7*64);
208       }
209     }
210 
211     /*! bvh type information */
212   public:
213     const PrimitiveType* primTy;       //!< primitive type stored in the BVH
214 
215     /*! bvh data */
216   public:
217     Device* device;                    //!< device pointer
218     Scene* scene;                      //!< scene pointer
219     NodeRef root;                      //!< root node
220     FastAllocator alloc;               //!< allocator used to allocate nodes
221 
222     /*! statistics data */
223   public:
224     size_t numPrimitives;              //!< number of primitives the BVH is build over
225     size_t numVertices;                //!< number of vertices the BVH references
226 
227     /*! data arrays for special builders */
228   public:
229     std::vector<BVHN*> objects;
230     vector_t<char,aligned_allocator<char,32>> subdiv_patches;
231   };
232 
233   typedef BVHN<4> BVH4;
234   typedef BVHN<8> BVH8;
235 }
236