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
14namespace 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 {
82 __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;
119 Allocator (BVHN* bvh) : bvh(bvh) {}
120 __forceinline void* operator() (size_t bytes) const {
121 return bvh->alloc._threadLocal()->malloc(&bvh->alloc,bytes);
122 }
123 };
124
125 /*! post build cleanup */
126 void cleanup() {
127 alloc.cleanup();
128 }
129
130 public:
131
132 /*! Encodes a node */
133 static __forceinline NodeRef encodeNode(AABBNode* node) { return NodeRef::encodeNode(node); }
134 static __forceinline NodeRef encodeNode(AABBNodeMB* node) { return NodeRef::encodeNode(node); }
135 static __forceinline NodeRef encodeNode(AABBNodeMB4D* node) { return NodeRef::encodeNode(node); }
136 static __forceinline NodeRef encodeNode(OBBNode* node) { return NodeRef::encodeNode(node); }
137 static __forceinline NodeRef encodeNode(OBBNodeMB* node) { return NodeRef::encodeNode(node); }
138 static __forceinline NodeRef encodeLeaf(void* tri, size_t num) { return NodeRef::encodeLeaf(tri,num); }
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