bvh_builder_sah_mb.cpp 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713
  1. // Copyright 2009-2021 Intel Corporation
  2. // SPDX-License-Identifier: Apache-2.0
  3. #include "bvh.h"
  4. #include "bvh_builder.h"
  5. #include "../builders/bvh_builder_msmblur.h"
  6. #include "../builders/primrefgen.h"
  7. #include "../builders/splitter.h"
  8. #include "../geometry/linei.h"
  9. #include "../geometry/triangle.h"
  10. #include "../geometry/trianglev.h"
  11. #include "../geometry/trianglev_mb.h"
  12. #include "../geometry/trianglei.h"
  13. #include "../geometry/quadv.h"
  14. #include "../geometry/quadi.h"
  15. #include "../geometry/object.h"
  16. #include "../geometry/instance.h"
  17. #include "../geometry/instance_array.h"
  18. #include "../geometry/subgrid.h"
  19. #include "../common/state.h"
  20. // FIXME: remove after removing BVHNBuilderMBlurRootTimeSplitsSAH
  21. #include "../../common/algorithms/parallel_for_for.h"
  22. #include "../../common/algorithms/parallel_for_for_prefix_sum.h"
  23. namespace embree
  24. {
  25. namespace isa
  26. {
  27. #if 0
  28. template<int N, typename Primitive>
  29. struct CreateMBlurLeaf
  30. {
  31. typedef BVHN<N> BVH;
  32. typedef typename BVH::NodeRef NodeRef;
  33. typedef typename BVH::NodeRecordMB NodeRecordMB;
  34. __forceinline CreateMBlurLeaf (BVH* bvh, PrimRef* prims, size_t time) : bvh(bvh), prims(prims), time(time) {}
  35. __forceinline NodeRecordMB operator() (const PrimRef* prims, const range<size_t>& set, const FastAllocator::CachedAllocator& alloc) const
  36. {
  37. size_t items = Primitive::blocks(set.size());
  38. size_t start = set.begin();
  39. for (size_t i=start; i<end; i++) assert((*current.prims.prims)[start].geomID() == (*current.prims.prims)[i].geomID()); // assert that all geomIDs are identical
  40. Primitive* accel = (Primitive*) alloc.malloc1(items*sizeof(Primitive),BVH::byteAlignment);
  41. NodeRef node = bvh->encodeLeaf((char*)accel,items);
  42. LBBox3fa allBounds = empty;
  43. for (size_t i=0; i<items; i++)
  44. allBounds.extend(accel[i].fillMB(prims, start, set.end(), bvh->scene, time));
  45. return NodeRecordMB(node,allBounds);
  46. }
  47. BVH* bvh;
  48. PrimRef* prims;
  49. size_t time;
  50. };
  51. #endif
  52. template<int N, typename Mesh, typename Primitive>
  53. struct CreateMSMBlurLeaf
  54. {
  55. typedef BVHN<N> BVH;
  56. typedef typename BVH::NodeRef NodeRef;
  57. typedef typename BVH::NodeRecordMB4D NodeRecordMB4D;
  58. __forceinline CreateMSMBlurLeaf (BVH* bvh) : bvh(bvh) {}
  59. __forceinline const NodeRecordMB4D operator() (const BVHBuilderMSMBlur::BuildRecord& current, const FastAllocator::CachedAllocator& alloc) const
  60. {
  61. size_t items = Primitive::blocks(current.prims.size());
  62. size_t start = current.prims.begin();
  63. size_t end = current.prims.end();
  64. for (size_t i=start; i<end; i++) assert((*current.prims.prims)[start].geomID() == (*current.prims.prims)[i].geomID()); // assert that all geomIDs are identical
  65. Primitive* accel = (Primitive*) alloc.malloc1(items*sizeof(Primitive),BVH::byteNodeAlignment);
  66. NodeRef node = bvh->encodeLeaf((char*)accel,items);
  67. LBBox3fa allBounds = empty;
  68. for (size_t i=0; i<items; i++)
  69. allBounds.extend(accel[i].fillMB(current.prims.prims->data(), start, current.prims.end(), bvh->scene, current.prims.time_range));
  70. return NodeRecordMB4D(node,allBounds,current.prims.time_range);
  71. }
  72. BVH* bvh;
  73. };
  74. /* Motion blur BVH with 4D nodes and internal time splits */
  75. template<int N, typename Mesh, typename Primitive>
  76. struct BVHNBuilderMBlurSAH : public Builder
  77. {
  78. typedef BVHN<N> BVH;
  79. typedef typename BVHN<N>::NodeRef NodeRef;
  80. typedef typename BVHN<N>::NodeRecordMB NodeRecordMB;
  81. typedef typename BVHN<N>::AABBNodeMB AABBNodeMB;
  82. BVH* bvh;
  83. Scene* scene;
  84. const size_t sahBlockSize;
  85. const float intCost;
  86. const size_t minLeafSize;
  87. const size_t maxLeafSize;
  88. const Geometry::GTypeMask gtype_;
  89. BVHNBuilderMBlurSAH (BVH* bvh, Scene* scene, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize, const Geometry::GTypeMask gtype)
  90. : bvh(bvh), scene(scene), sahBlockSize(sahBlockSize), intCost(intCost), minLeafSize(minLeafSize), maxLeafSize(min(maxLeafSize,Primitive::max_size()*BVH::maxLeafBlocks)), gtype_(gtype) {}
  91. void build()
  92. {
  93. /* skip build for empty scene */
  94. const size_t numPrimitives = scene->getNumPrimitives(gtype_,true);
  95. if (numPrimitives == 0) { bvh->clear(); return; }
  96. double t0 = bvh->preBuild(TOSTRING(isa) "::BVH" + toString(N) + "BuilderMBlurSAH");
  97. #if PROFILE
  98. profile(2,PROFILE_RUNS,numPrimitives,[&] (ProfileTimer& timer) {
  99. #endif
  100. //const size_t numTimeSteps = scene->getNumTimeSteps<typename Mesh::type_t,true>();
  101. //const size_t numTimeSegments = numTimeSteps-1; assert(numTimeSteps > 1);
  102. /*if (numTimeSegments == 1)
  103. buildSingleSegment(numPrimitives);
  104. else*/
  105. buildMultiSegment(numPrimitives);
  106. #if PROFILE
  107. });
  108. #endif
  109. /* clear temporary data for static geometry */
  110. bvh->cleanup();
  111. bvh->postBuild(t0);
  112. }
  113. #if 0 // No longer compatible when time_ranges are present for geometries. Would have to create temporal nodes sometimes, and put only a single geometry into leaf.
  114. void buildSingleSegment(size_t numPrimitives)
  115. {
  116. /* create primref array */
  117. mvector<PrimRef> prims(scene->device,numPrimitives);
  118. const PrimInfo pinfo = createPrimRefArrayMBlur(scene,gtype_,numPrimitives,prims,bvh->scene->progressInterface,0);
  119. /* early out if no valid primitives */
  120. if (pinfo.size() == 0) { bvh->clear(); return; }
  121. /* estimate acceleration structure size */
  122. const size_t node_bytes = pinfo.size()*sizeof(AABBNodeMB)/(4*N);
  123. const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.size())*sizeof(Primitive));
  124. bvh->alloc.init_estimate(node_bytes+leaf_bytes);
  125. /* settings for BVH build */
  126. GeneralBVHBuilder::Settings settings;
  127. settings.branchingFactor = N;
  128. settings.maxDepth = BVH::maxBuildDepthLeaf;
  129. settings.logBlockSize = bsr(sahBlockSize);
  130. settings.minLeafSize = min(minLeafSize,maxLeafSize);
  131. settings.maxLeafSize = maxLeafSize;
  132. settings.travCost = travCost;
  133. settings.intCost = intCost;
  134. settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
  135. /* build hierarchy */
  136. auto root = BVHBuilderBinnedSAH::build<NodeRecordMB>
  137. (typename BVH::CreateAlloc(bvh),typename BVH::AABBNodeMB::Create(),typename BVH::AABBNodeMB::Set(),
  138. CreateMBlurLeaf<N,Primitive>(bvh,prims.data(),0),bvh->scene->progressInterface,
  139. prims.data(),pinfo,settings);
  140. bvh->set(root.ref,root.lbounds,pinfo.size());
  141. }
  142. #endif
  143. void buildMultiSegment(size_t numPrimitives)
  144. {
  145. /* create primref array */
  146. mvector<PrimRefMB> prims(scene->device,numPrimitives);
  147. PrimInfoMB pinfo = createPrimRefArrayMSMBlur(scene,gtype_,numPrimitives,prims,bvh->scene->progressInterface);
  148. /* early out if no valid primitives */
  149. if (pinfo.size() == 0) { bvh->clear(); return; }
  150. /* estimate acceleration structure size */
  151. const size_t node_bytes = pinfo.num_time_segments*sizeof(AABBNodeMB)/(4*N);
  152. const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.num_time_segments)*sizeof(Primitive));
  153. bvh->alloc.init_estimate(node_bytes+leaf_bytes);
  154. /* settings for BVH build */
  155. BVHBuilderMSMBlur::Settings settings;
  156. settings.branchingFactor = N;
  157. settings.maxDepth = BVH::maxDepth;
  158. settings.logBlockSize = bsr(sahBlockSize);
  159. settings.minLeafSize = min(minLeafSize,maxLeafSize);
  160. settings.maxLeafSize = maxLeafSize;
  161. settings.travCost = travCost;
  162. settings.intCost = intCost;
  163. settings.singleLeafTimeSegment = Primitive::singleTimeSegment;
  164. settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
  165. /* build hierarchy */
  166. auto root =
  167. BVHBuilderMSMBlur::build<NodeRef>(prims,pinfo,scene->device,
  168. RecalculatePrimRef<Mesh>(scene),
  169. typename BVH::CreateAlloc(bvh),
  170. typename BVH::AABBNodeMB4D::Create(),
  171. typename BVH::AABBNodeMB4D::Set(),
  172. CreateMSMBlurLeaf<N,Mesh,Primitive>(bvh),
  173. bvh->scene->progressInterface,
  174. settings);
  175. bvh->set(root.ref,root.lbounds,pinfo.num_time_segments);
  176. }
  177. void clear() {
  178. }
  179. };
  180. /************************************************************************************/
  181. /************************************************************************************/
  182. /************************************************************************************/
  183. /************************************************************************************/
  184. struct GridRecalculatePrimRef
  185. {
  186. Scene* scene;
  187. const SubGridBuildData * const sgrids;
  188. __forceinline GridRecalculatePrimRef (Scene* scene, const SubGridBuildData * const sgrids)
  189. : scene(scene), sgrids(sgrids) {}
  190. __forceinline PrimRefMB operator() (const PrimRefMB& prim, const BBox1f time_range) const
  191. {
  192. const unsigned int geomID = prim.geomID();
  193. const GridMesh* mesh = scene->get<GridMesh>(geomID);
  194. const unsigned int buildID = prim.primID();
  195. const SubGridBuildData &subgrid = sgrids[buildID];
  196. const unsigned int primID = subgrid.primID;
  197. const size_t x = subgrid.x();
  198. const size_t y = subgrid.y();
  199. const LBBox3fa lbounds = mesh->linearBounds(mesh->grid(primID),x,y,time_range);
  200. const unsigned num_time_segments = mesh->numTimeSegments();
  201. const range<int> tbounds = mesh->timeSegmentRange(time_range);
  202. return PrimRefMB (lbounds, tbounds.size(), mesh->time_range, num_time_segments, geomID, buildID);
  203. }
  204. __forceinline LBBox3fa linearBounds(const PrimRefMB& prim, const BBox1f time_range) const {
  205. const unsigned int geomID = prim.geomID();
  206. const GridMesh* mesh = scene->get<GridMesh>(geomID);
  207. const unsigned int buildID = prim.primID();
  208. const SubGridBuildData &subgrid = sgrids[buildID];
  209. const unsigned int primID = subgrid.primID;
  210. const size_t x = subgrid.x();
  211. const size_t y = subgrid.y();
  212. return mesh->linearBounds(mesh->grid(primID),x,y,time_range);
  213. }
  214. };
  215. template<int N>
  216. struct CreateMSMBlurLeafGrid
  217. {
  218. typedef BVHN<N> BVH;
  219. typedef typename BVH::NodeRef NodeRef;
  220. typedef typename BVH::NodeRecordMB4D NodeRecordMB4D;
  221. __forceinline CreateMSMBlurLeafGrid (Scene* scene, BVH* bvh, const SubGridBuildData * const sgrids) : scene(scene), bvh(bvh), sgrids(sgrids) {}
  222. __forceinline const NodeRecordMB4D operator() (const BVHBuilderMSMBlur::BuildRecord& current, const FastAllocator::CachedAllocator& alloc) const
  223. {
  224. const size_t items = current.prims.size();
  225. const size_t start = current.prims.begin();
  226. const PrimRefMB* prims = current.prims.prims->data();
  227. /* collect all subsets with unique geomIDs */
  228. assert(items <= N);
  229. unsigned int geomIDs[N];
  230. unsigned int num_geomIDs = 1;
  231. geomIDs[0] = prims[start].geomID();
  232. for (size_t i=1;i<items;i++)
  233. {
  234. bool found = false;
  235. const unsigned int new_geomID = prims[start+i].geomID();
  236. for (size_t j=0;j<num_geomIDs;j++)
  237. if (new_geomID == geomIDs[j])
  238. { found = true; break; }
  239. if (!found)
  240. geomIDs[num_geomIDs++] = new_geomID;
  241. }
  242. /* allocate all leaf memory in one single block */
  243. SubGridMBQBVHN<N>* accel = (SubGridMBQBVHN<N>*) alloc.malloc1(num_geomIDs*sizeof(SubGridMBQBVHN<N>),BVH::byteAlignment);
  244. typename BVH::NodeRef node = bvh->encodeLeaf((char*)accel,num_geomIDs);
  245. LBBox3fa allBounds = empty;
  246. for (size_t g=0;g<num_geomIDs;g++)
  247. {
  248. const GridMesh* __restrict__ const mesh = scene->get<GridMesh>(geomIDs[g]);
  249. unsigned int x[N];
  250. unsigned int y[N];
  251. unsigned int primID[N];
  252. BBox3fa bounds0[N];
  253. BBox3fa bounds1[N];
  254. unsigned int pos = 0;
  255. for (size_t i=0;i<items;i++)
  256. {
  257. if (unlikely(prims[start+i].geomID() != geomIDs[g])) continue;
  258. const SubGridBuildData &sgrid_bd = sgrids[prims[start+i].primID()];
  259. x[pos] = sgrid_bd.sx;
  260. y[pos] = sgrid_bd.sy;
  261. primID[pos] = sgrid_bd.primID;
  262. const size_t x = sgrid_bd.x();
  263. const size_t y = sgrid_bd.y();
  264. LBBox3fa newBounds = mesh->linearBounds(mesh->grid(sgrid_bd.primID),x,y,current.prims.time_range);
  265. allBounds.extend(newBounds);
  266. bounds0[pos] = newBounds.bounds0;
  267. bounds1[pos] = newBounds.bounds1;
  268. pos++;
  269. }
  270. assert(pos <= N);
  271. new (&accel[g]) SubGridMBQBVHN<N>(x,y,primID,bounds0,bounds1,geomIDs[g],current.prims.time_range.lower,1.0f/current.prims.time_range.size(),pos);
  272. }
  273. return NodeRecordMB4D(node,allBounds,current.prims.time_range);
  274. }
  275. Scene *scene;
  276. BVH* bvh;
  277. const SubGridBuildData * const sgrids;
  278. };
  279. #if 0
  280. template<int N>
  281. struct CreateLeafGridMB
  282. {
  283. typedef BVHN<N> BVH;
  284. typedef typename BVH::NodeRef NodeRef;
  285. typedef typename BVH::NodeRecordMB NodeRecordMB;
  286. __forceinline CreateLeafGridMB (Scene* scene, BVH* bvh, const SubGridBuildData * const sgrids)
  287. : scene(scene), bvh(bvh), sgrids(sgrids) {}
  288. __forceinline NodeRecordMB operator() (const PrimRef* prims, const range<size_t>& set, const FastAllocator::CachedAllocator& alloc) const
  289. {
  290. const size_t items = set.size();
  291. const size_t start = set.begin();
  292. /* collect all subsets with unique geomIDs */
  293. assert(items <= N);
  294. unsigned int geomIDs[N];
  295. unsigned int num_geomIDs = 1;
  296. geomIDs[0] = prims[start].geomID();
  297. for (size_t i=1;i<items;i++)
  298. {
  299. bool found = false;
  300. const unsigned int new_geomID = prims[start+i].geomID();
  301. for (size_t j=0;j<num_geomIDs;j++)
  302. if (new_geomID == geomIDs[j])
  303. { found = true; break; }
  304. if (!found)
  305. geomIDs[num_geomIDs++] = new_geomID;
  306. }
  307. /* allocate all leaf memory in one single block */
  308. SubGridMBQBVHN<N>* accel = (SubGridMBQBVHN<N>*) alloc.malloc1(num_geomIDs*sizeof(SubGridMBQBVHN<N>),BVH::byteAlignment);
  309. typename BVH::NodeRef node = bvh->encodeLeaf((char*)accel,num_geomIDs);
  310. LBBox3fa allBounds = empty;
  311. for (size_t g=0;g<num_geomIDs;g++)
  312. {
  313. const GridMesh* __restrict__ const mesh = scene->get<GridMesh>(geomIDs[g]);
  314. unsigned int x[N];
  315. unsigned int y[N];
  316. unsigned int primID[N];
  317. BBox3fa bounds0[N];
  318. BBox3fa bounds1[N];
  319. unsigned int pos = 0;
  320. for (size_t i=0;i<items;i++)
  321. {
  322. if (unlikely(prims[start+i].geomID() != geomIDs[g])) continue;
  323. const SubGridBuildData &sgrid_bd = sgrids[prims[start+i].primID()];
  324. x[pos] = sgrid_bd.sx;
  325. y[pos] = sgrid_bd.sy;
  326. primID[pos] = sgrid_bd.primID;
  327. const size_t x = sgrid_bd.x();
  328. const size_t y = sgrid_bd.y();
  329. bool MAYBE_UNUSED valid0 = mesh->buildBounds(mesh->grid(sgrid_bd.primID),x,y,0,bounds0[pos]);
  330. bool MAYBE_UNUSED valid1 = mesh->buildBounds(mesh->grid(sgrid_bd.primID),x,y,1,bounds1[pos]);
  331. assert(valid0);
  332. assert(valid1);
  333. allBounds.extend(LBBox3fa(bounds0[pos],bounds1[pos]));
  334. pos++;
  335. }
  336. new (&accel[g]) SubGridMBQBVHN<N>(x,y,primID,bounds0,bounds1,geomIDs[g],0.0f,1.0f,pos);
  337. }
  338. return NodeRecordMB(node,allBounds);
  339. }
  340. Scene *scene;
  341. BVH* bvh;
  342. const SubGridBuildData * const sgrids;
  343. };
  344. #endif
  345. /* Motion blur BVH with 4D nodes and internal time splits */
  346. template<int N>
  347. struct BVHNBuilderMBlurSAHGrid : public Builder
  348. {
  349. typedef BVHN<N> BVH;
  350. typedef typename BVHN<N>::NodeRef NodeRef;
  351. typedef typename BVHN<N>::NodeRecordMB NodeRecordMB;
  352. typedef typename BVHN<N>::AABBNodeMB AABBNodeMB;
  353. BVH* bvh;
  354. Scene* scene;
  355. const size_t sahBlockSize;
  356. const float intCost;
  357. const size_t minLeafSize;
  358. const size_t maxLeafSize;
  359. mvector<SubGridBuildData> sgrids;
  360. BVHNBuilderMBlurSAHGrid (BVH* bvh, Scene* scene, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize)
  361. : bvh(bvh), scene(scene), sahBlockSize(sahBlockSize), intCost(intCost), minLeafSize(minLeafSize), maxLeafSize(min(maxLeafSize,BVH::maxLeafBlocks)), sgrids(scene->device,0) {}
  362. PrimInfo createPrimRefArrayMBlurGrid(Scene* scene, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor, size_t itime)
  363. {
  364. /* first run to get #primitives */
  365. ParallelForForPrefixSumState<PrimInfo> pstate;
  366. Scene::Iterator<GridMesh,true> iter(scene);
  367. pstate.init(iter,size_t(1024));
  368. /* iterate over all meshes in the scene */
  369. PrimInfo pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
  370. PrimInfo pinfo(empty);
  371. for (size_t j=r.begin(); j<r.end(); j++)
  372. {
  373. if (!mesh->valid(j,range<size_t>(0,1))) continue;
  374. BBox3fa bounds = empty;
  375. const PrimRef prim(bounds,unsigned(geomID),unsigned(j));
  376. pinfo.add_center2(prim,mesh->getNumSubGrids(j));
  377. }
  378. return pinfo;
  379. }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
  380. size_t numPrimitives = pinfo.size();
  381. if (numPrimitives == 0) return pinfo;
  382. /* resize arrays */
  383. sgrids.resize(numPrimitives);
  384. prims.resize(numPrimitives);
  385. /* second run to fill primrefs and SubGridBuildData arrays */
  386. pinfo = parallel_for_for_prefix_sum1( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
  387. k = base.size();
  388. size_t p_index = k;
  389. PrimInfo pinfo(empty);
  390. for (size_t j=r.begin(); j<r.end(); j++)
  391. {
  392. const GridMesh::Grid &g = mesh->grid(j);
  393. if (!mesh->valid(j,range<size_t>(0,1))) continue;
  394. for (unsigned int y=0; y<g.resY-1u; y+=2)
  395. for (unsigned int x=0; x<g.resX-1u; x+=2)
  396. {
  397. BBox3fa bounds = empty;
  398. if (!mesh->buildBounds(g,x,y,itime,bounds)) continue; // get bounds of subgrid
  399. const PrimRef prim(bounds,unsigned(geomID),unsigned(p_index));
  400. pinfo.add_center2(prim);
  401. sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
  402. prims[p_index++] = prim;
  403. }
  404. }
  405. return pinfo;
  406. }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
  407. assert(pinfo.size() == numPrimitives);
  408. return pinfo;
  409. }
  410. PrimInfoMB createPrimRefArrayMSMBlurGrid(Scene* scene, mvector<PrimRefMB>& prims, BuildProgressMonitor& progressMonitor, BBox1f t0t1 = BBox1f(0.0f,1.0f))
  411. {
  412. /* first run to get #primitives */
  413. ParallelForForPrefixSumState<PrimInfoMB> pstate;
  414. Scene::Iterator<GridMesh,true> iter(scene);
  415. pstate.init(iter,size_t(1024));
  416. /* iterate over all meshes in the scene */
  417. PrimInfoMB pinfoMB = parallel_for_for_prefix_sum0( pstate, iter, PrimInfoMB(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t /*geomID*/) -> PrimInfoMB {
  418. PrimInfoMB pinfoMB(empty);
  419. for (size_t j=r.begin(); j<r.end(); j++)
  420. {
  421. if (!mesh->valid(j, mesh->timeSegmentRange(t0t1))) continue;
  422. LBBox3fa bounds(empty);
  423. PrimInfoMB gridMB(0,mesh->getNumSubGrids(j));
  424. pinfoMB.merge(gridMB);
  425. }
  426. return pinfoMB;
  427. }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
  428. size_t numPrimitives = pinfoMB.size();
  429. if (numPrimitives == 0) return pinfoMB;
  430. /* resize arrays */
  431. sgrids.resize(numPrimitives);
  432. prims.resize(numPrimitives);
  433. /* second run to fill primrefs and SubGridBuildData arrays */
  434. pinfoMB = parallel_for_for_prefix_sum1( pstate, iter, PrimInfoMB(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfoMB& base) -> PrimInfoMB {
  435. k = base.size();
  436. size_t p_index = k;
  437. PrimInfoMB pinfoMB(empty);
  438. for (size_t j=r.begin(); j<r.end(); j++)
  439. {
  440. if (!mesh->valid(j, mesh->timeSegmentRange(t0t1))) continue;
  441. const GridMesh::Grid &g = mesh->grid(j);
  442. for (unsigned int y=0; y<g.resY-1u; y+=2)
  443. for (unsigned int x=0; x<g.resX-1u; x+=2)
  444. {
  445. const PrimRefMB prim(mesh->linearBounds(g,x,y,t0t1),mesh->numTimeSegments(),mesh->time_range,mesh->numTimeSegments(),unsigned(geomID),unsigned(p_index));
  446. pinfoMB.add_primref(prim);
  447. sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
  448. prims[p_index++] = prim;
  449. }
  450. }
  451. return pinfoMB;
  452. }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
  453. assert(pinfoMB.size() == numPrimitives);
  454. pinfoMB.time_range = t0t1;
  455. return pinfoMB;
  456. }
  457. void build()
  458. {
  459. /* skip build for empty scene */
  460. const size_t numPrimitives = scene->getNumPrimitives(GridMesh::geom_type,true);
  461. if (numPrimitives == 0) { bvh->clear(); return; }
  462. double t0 = bvh->preBuild(TOSTRING(isa) "::BVH" + toString(N) + "BuilderMBlurSAHGrid");
  463. //const size_t numTimeSteps = scene->getNumTimeSteps<GridMesh,true>();
  464. //const size_t numTimeSegments = numTimeSteps-1; assert(numTimeSteps > 1);
  465. //if (numTimeSegments == 1)
  466. // buildSingleSegment(numPrimitives);
  467. //else
  468. buildMultiSegment(numPrimitives);
  469. /* clear temporary data for static geometry */
  470. bvh->cleanup();
  471. bvh->postBuild(t0);
  472. }
  473. #if 0
  474. void buildSingleSegment(size_t numPrimitives)
  475. {
  476. /* create primref array */
  477. mvector<PrimRef> prims(scene->device,numPrimitives);
  478. const PrimInfo pinfo = createPrimRefArrayMBlurGrid(scene,prims,bvh->scene->progressInterface,0);
  479. /* early out if no valid primitives */
  480. if (pinfo.size() == 0) { bvh->clear(); return; }
  481. /* estimate acceleration structure size */
  482. const size_t node_bytes = pinfo.size()*sizeof(AABBNodeMB)/(4*N);
  483. //TODO: check leaf_bytes
  484. const size_t leaf_bytes = size_t(1.2*(float)numPrimitives/N * sizeof(SubGridQBVHN<N>));
  485. bvh->alloc.init_estimate(node_bytes+leaf_bytes);
  486. /* settings for BVH build */
  487. GeneralBVHBuilder::Settings settings;
  488. settings.branchingFactor = N;
  489. settings.maxDepth = BVH::maxBuildDepthLeaf;
  490. settings.logBlockSize = bsr(sahBlockSize);
  491. settings.minLeafSize = min(minLeafSize,maxLeafSize);
  492. settings.maxLeafSize = maxLeafSize;
  493. settings.travCost = travCost;
  494. settings.intCost = intCost;
  495. settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
  496. /* build hierarchy */
  497. auto root = BVHBuilderBinnedSAH::build<NodeRecordMB>
  498. (typename BVH::CreateAlloc(bvh),
  499. typename BVH::AABBNodeMB::Create(),
  500. typename BVH::AABBNodeMB::Set(),
  501. CreateLeafGridMB<N>(scene,bvh,sgrids.data()),
  502. bvh->scene->progressInterface,
  503. prims.data(),pinfo,settings);
  504. bvh->set(root.ref,root.lbounds,pinfo.size());
  505. }
  506. #endif
  507. void buildMultiSegment(size_t numPrimitives)
  508. {
  509. /* create primref array */
  510. mvector<PrimRefMB> prims(scene->device,numPrimitives);
  511. PrimInfoMB pinfo = createPrimRefArrayMSMBlurGrid(scene,prims,bvh->scene->progressInterface);
  512. /* early out if no valid primitives */
  513. if (pinfo.size() == 0) { bvh->clear(); return; }
  514. GridRecalculatePrimRef recalculatePrimRef(scene,sgrids.data());
  515. /* estimate acceleration structure size */
  516. const size_t node_bytes = pinfo.num_time_segments*sizeof(AABBNodeMB)/(4*N);
  517. //FIXME: check leaf_bytes
  518. //const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.num_time_segments)*sizeof(SubGridQBVHN<N>));
  519. const size_t leaf_bytes = size_t(1.2*(float)numPrimitives/N * sizeof(SubGridQBVHN<N>));
  520. bvh->alloc.init_estimate(node_bytes+leaf_bytes);
  521. /* settings for BVH build */
  522. BVHBuilderMSMBlur::Settings settings;
  523. settings.branchingFactor = N;
  524. settings.maxDepth = BVH::maxDepth;
  525. settings.logBlockSize = bsr(sahBlockSize);
  526. settings.minLeafSize = min(minLeafSize,maxLeafSize);
  527. settings.maxLeafSize = maxLeafSize;
  528. settings.travCost = travCost;
  529. settings.intCost = intCost;
  530. settings.singleLeafTimeSegment = false;
  531. settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
  532. /* build hierarchy */
  533. auto root =
  534. BVHBuilderMSMBlur::build<NodeRef>(prims,pinfo,scene->device,
  535. recalculatePrimRef,
  536. typename BVH::CreateAlloc(bvh),
  537. typename BVH::AABBNodeMB4D::Create(),
  538. typename BVH::AABBNodeMB4D::Set(),
  539. CreateMSMBlurLeafGrid<N>(scene,bvh,sgrids.data()),
  540. bvh->scene->progressInterface,
  541. settings);
  542. bvh->set(root.ref,root.lbounds,pinfo.num_time_segments);
  543. }
  544. void clear() {
  545. }
  546. };
  547. /************************************************************************************/
  548. /************************************************************************************/
  549. /************************************************************************************/
  550. /************************************************************************************/
  551. #if defined(EMBREE_GEOMETRY_TRIANGLE)
  552. Builder* BVH4Triangle4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,TriangleMesh,Triangle4i>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
  553. Builder* BVH4Triangle4vMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,TriangleMesh,Triangle4vMB>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
  554. #if defined(__AVX__)
  555. Builder* BVH8Triangle4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,TriangleMesh,Triangle4i>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
  556. Builder* BVH8Triangle4vMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,TriangleMesh,Triangle4vMB>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
  557. #endif
  558. #endif
  559. #if defined(EMBREE_GEOMETRY_QUAD)
  560. Builder* BVH4Quad4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,QuadMesh,Quad4i>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_QUAD_MESH); }
  561. #if defined(__AVX__)
  562. Builder* BVH8Quad4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,QuadMesh,Quad4i>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_QUAD_MESH); }
  563. #endif
  564. #endif
  565. #if defined(EMBREE_GEOMETRY_USER)
  566. Builder* BVH4VirtualMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) {
  567. int minLeafSize = scene->device->object_accel_mb_min_leaf_size;
  568. int maxLeafSize = scene->device->object_accel_mb_max_leaf_size;
  569. return new BVHNBuilderMBlurSAH<4,UserGeometry,Object>((BVH4*)bvh,scene,4,1.0f,minLeafSize,maxLeafSize,Geometry::MTY_USER_GEOMETRY);
  570. }
  571. #if defined(__AVX__)
  572. Builder* BVH8VirtualMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) {
  573. int minLeafSize = scene->device->object_accel_mb_min_leaf_size;
  574. int maxLeafSize = scene->device->object_accel_mb_max_leaf_size;
  575. return new BVHNBuilderMBlurSAH<8,UserGeometry,Object>((BVH8*)bvh,scene,8,1.0f,minLeafSize,maxLeafSize,Geometry::MTY_USER_GEOMETRY);
  576. }
  577. #endif
  578. #endif
  579. #if defined(EMBREE_GEOMETRY_INSTANCE)
  580. Builder* BVH4InstanceMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<4,Instance,InstancePrimitive>((BVH4*)bvh,scene,4,1.0f,1,1,gtype); }
  581. #if defined(__AVX__)
  582. Builder* BVH8InstanceMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<8,Instance,InstancePrimitive>((BVH8*)bvh,scene,8,1.0f,1,1,gtype); }
  583. #endif
  584. #endif
  585. #if defined(EMBREE_GEOMETRY_INSTANCE_ARRAY)
  586. Builder* BVH4InstanceArrayMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<4,InstanceArray,InstanceArrayPrimitive>((BVH4*)bvh,scene,4,1.0f,1,1,gtype); }
  587. #if defined(__AVX__)
  588. Builder* BVH8InstanceArrayMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<8,InstanceArray,InstanceArrayPrimitive>((BVH8*)bvh,scene,8,1.0f,1,1,gtype); }
  589. #endif
  590. #endif
  591. #if defined(EMBREE_GEOMETRY_GRID)
  592. Builder* BVH4GridMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAHGrid<4>((BVH4*)bvh,scene,4,1.0f,4,4); }
  593. #if defined(__AVX__)
  594. Builder* BVH8GridMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAHGrid<8>((BVH8*)bvh,scene,8,1.0f,8,8); }
  595. #endif
  596. #endif
  597. }
  598. }