1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "primrefgen.h"
5#include "primrefgen_presplit.h"
6
7#include "../../common/algorithms/parallel_for_for.h"
8#include "../../common/algorithms/parallel_for_for_prefix_sum.h"
9
10namespace embree
11{
12 namespace isa
13 {
14 PrimInfo createPrimRefArray(Geometry* geometry, unsigned int geomID, const size_t numPrimRefs, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor)
15 {
16 ParallelPrefixSumState<PrimInfo> pstate;
17
18 /* first try */
19 progressMonitor(0);
20 PrimInfo pinfo = parallel_prefix_sum( state&: pstate, first: size_t(0), last: geometry->size(), minStepSize: size_t(1024), identity: PrimInfo(empty), func: [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo {
21 return geometry->createPrimRefArray(prims,r,k: r.begin(),geomID);
22 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
23
24 /* if we need to filter out geometry, run again */
25 if (pinfo.size() != numPrimRefs)
26 {
27 progressMonitor(0);
28 pinfo = parallel_prefix_sum( state&: pstate, first: size_t(0), last: geometry->size(), minStepSize: size_t(1024), identity: PrimInfo(empty), func: [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo {
29 return geometry->createPrimRefArray(prims,r,k: base.size(),geomID);
30 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
31 }
32 return pinfo;
33 }
34
35 PrimInfo createPrimRefArray(Scene* scene, Geometry::GTypeMask types, bool mblur, const size_t numPrimRefs, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor)
36 {
37 ParallelForForPrefixSumState<PrimInfo> pstate;
38 Scene::Iterator2 iter(scene,types,mblur);
39
40 /* first try */
41 progressMonitor(0);
42 pstate.init(array2&: iter,minStepSize: size_t(1024));
43 PrimInfo pinfo = parallel_for_for_prefix_sum0( state&: pstate, array2&: iter, identity: PrimInfo(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
44 return mesh->createPrimRefArray(prims,r,k,geomID: (unsigned)geomID);
45 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
46
47 /* if we need to filter out geometry, run again */
48 if (pinfo.size() != numPrimRefs)
49 {
50 progressMonitor(0);
51 pinfo = parallel_for_for_prefix_sum1( state&: pstate, array2&: iter, identity: PrimInfo(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
52 return mesh->createPrimRefArray(prims,r,k: base.size(),geomID: (unsigned)geomID);
53 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
54 }
55 return pinfo;
56 }
57
58 PrimInfo createPrimRefArrayMBlur(Scene* scene, Geometry::GTypeMask types, const size_t numPrimRefs, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor, size_t itime)
59 {
60 ParallelForForPrefixSumState<PrimInfo> pstate;
61 Scene::Iterator2 iter(scene,types,true);
62
63 /* first try */
64 progressMonitor(0);
65 pstate.init(array2&: iter,minStepSize: size_t(1024));
66 PrimInfo pinfo = parallel_for_for_prefix_sum0( state&: pstate, array2&: iter, identity: PrimInfo(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
67 return mesh->createPrimRefArrayMB(prims,itime,r,k,geomID: (unsigned)geomID);
68 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
69
70 /* if we need to filter out geometry, run again */
71 if (pinfo.size() != numPrimRefs)
72 {
73 progressMonitor(0);
74 pinfo = parallel_for_for_prefix_sum1( state&: pstate, array2&: iter, identity: PrimInfo(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
75 return mesh->createPrimRefArrayMB(prims,itime,r,k: base.size(),geomID: (unsigned)geomID);
76 }, reduction: [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
77 }
78 return pinfo;
79 }
80
81 PrimInfoMB createPrimRefArrayMSMBlur(Scene* scene, Geometry::GTypeMask types, const size_t numPrimRefs, mvector<PrimRefMB>& prims, BuildProgressMonitor& progressMonitor, BBox1f t0t1)
82 {
83 ParallelForForPrefixSumState<PrimInfoMB> pstate;
84 Scene::Iterator2 iter(scene,types,true);
85
86 /* first try */
87 progressMonitor(0);
88 pstate.init(array2&: iter,minStepSize: size_t(1024));
89 PrimInfoMB pinfo = parallel_for_for_prefix_sum0( state&: pstate, array2&: iter, identity: PrimInfoMB(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfoMB {
90 return mesh->createPrimRefMBArray(prims,t0t1,r,k,geomID: (unsigned)geomID);
91 }, reduction: [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
92
93 /* if we need to filter out geometry, run again */
94 if (pinfo.size() != numPrimRefs)
95 {
96 progressMonitor(0);
97 pinfo = parallel_for_for_prefix_sum1( state&: pstate, array2&: iter, identity: PrimInfoMB(empty), func: [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfoMB& base) -> PrimInfoMB {
98 return mesh->createPrimRefMBArray(prims,t0t1,r,k: base.size(),geomID: (unsigned)geomID);
99 }, reduction: [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
100 }
101
102 /* the BVH starts with that time range, even though primitives might have smaller/larger time range */
103 pinfo.time_range = t0t1;
104 return pinfo;
105 }
106
107 template<typename Mesh>
108 size_t createMortonCodeArray(Mesh* mesh, mvector<BVHBuilderMorton::BuildPrim>& morton, BuildProgressMonitor& progressMonitor)
109 {
110 size_t numPrimitives = morton.size();
111
112 /* compute scene bounds */
113 std::pair<size_t,BBox3fa> cb_empty(0,empty);
114 auto cb = parallel_reduce
115 ( size_t(0), numPrimitives, size_t(1024), cb_empty, [&](const range<size_t>& r) -> std::pair<size_t,BBox3fa>
116 {
117 size_t num = 0;
118 BBox3fa bounds = empty;
119
120 for (size_t j=r.begin(); j<r.end(); j++)
121 {
122 BBox3fa prim_bounds = empty;
123 if (unlikely(!mesh->buildBounds(j,&prim_bounds))) continue;
124 bounds.extend(other: center2(box: prim_bounds));
125 num++;
126 }
127 return std::make_pair(x&: num,y&: bounds);
128 }, [] (const std::pair<size_t,BBox3fa>& a, const std::pair<size_t,BBox3fa>& b) {
129 return std::make_pair(x: a.first + b.first,y: merge(a: a.second,b: b.second));
130 });
131
132
133 size_t numPrimitivesGen = cb.first;
134 const BBox3fa centBounds = cb.second;
135
136 /* compute morton codes */
137 if (likely(numPrimitivesGen == numPrimitives))
138 {
139 /* fast path if all primitives were valid */
140 BVHBuilderMorton::MortonCodeMapping mapping(centBounds);
141 parallel_for( size_t(0), numPrimitives, size_t(1024), [&](const range<size_t>& r) -> void {
142 BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[r.begin()]);
143 for (size_t j=r.begin(); j<r.end(); j++)
144 generator(mesh->bounds(j),unsigned(j));
145 });
146 }
147 else
148 {
149 /* slow path, fallback in case some primitives were invalid */
150 ParallelPrefixSumState<size_t> pstate;
151 BVHBuilderMorton::MortonCodeMapping mapping(centBounds);
152 parallel_prefix_sum( pstate, size_t(0), numPrimitives, size_t(1024), size_t(0), [&](const range<size_t>& r, const size_t base) -> size_t {
153 size_t num = 0;
154 BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[r.begin()]);
155 for (size_t j=r.begin(); j<r.end(); j++)
156 {
157 BBox3fa bounds = empty;
158 if (unlikely(!mesh->buildBounds(j,&bounds))) continue;
159 generator(bounds,unsigned(j));
160 num++;
161 }
162 return num;
163 }, std::plus<size_t>());
164
165 parallel_prefix_sum( pstate, size_t(0), numPrimitives, size_t(1024), size_t(0), [&](const range<size_t>& r, const size_t base) -> size_t {
166 size_t num = 0;
167 BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[base]);
168 for (size_t j=r.begin(); j<r.end(); j++)
169 {
170 BBox3fa bounds = empty;
171 if (!mesh->buildBounds(j,&bounds)) continue;
172 generator(bounds,unsigned(j));
173 num++;
174 }
175 return num;
176 }, std::plus<size_t>());
177 }
178 return numPrimitivesGen;
179 }
180
181 // ====================================================================================================
182 // ====================================================================================================
183 // ====================================================================================================
184
185 // special variants for grid meshes
186
187#if defined(EMBREE_GEOMETRY_GRID)
188 PrimInfo createPrimRefArrayGrids(Scene* scene, mvector<PrimRef>& prims, mvector<SubGridBuildData>& sgrids)
189 {
190 PrimInfo pinfo(empty);
191 size_t numPrimitives = 0;
192
193 /* first run to get #primitives */
194
195 ParallelForForPrefixSumState<PrimInfo> pstate;
196 Scene::Iterator<GridMesh,false> iter(scene);
197
198 pstate.init(iter,size_t(1024));
199
200 /* iterate over all meshes in the scene */
201 pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
202 PrimInfo pinfo(empty);
203 for (size_t j=r.begin(); j<r.end(); j++)
204 {
205 if (!mesh->valid(j)) continue;
206 BBox3fa bounds = empty;
207 const PrimRef prim(bounds,(unsigned)geomID,(unsigned)j);
208 if (!mesh->valid(j)) continue;
209 pinfo.add_center2(prim,mesh->getNumSubGrids(j));
210 }
211 return pinfo;
212 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
213 numPrimitives = pinfo.size();
214
215 /* resize arrays */
216 sgrids.resize(numPrimitives);
217 prims.resize(numPrimitives);
218
219 /* second run to fill primrefs and SubGridBuildData arrays */
220 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 {
221 k = base.size();
222 size_t p_index = k;
223 PrimInfo pinfo(empty);
224 for (size_t j=r.begin(); j<r.end(); j++)
225 {
226 if (!mesh->valid(j)) continue;
227 const GridMesh::Grid &g = mesh->grid(j);
228 for (unsigned int y=0; y<g.resY-1u; y+=2)
229 for (unsigned int x=0; x<g.resX-1u; x+=2)
230 {
231 BBox3fa bounds = empty;
232 if (!mesh->buildBounds(g,x,y,bounds)) continue; // get bounds of subgrid
233 const PrimRef prim(bounds,(unsigned)geomID,(unsigned)p_index);
234 pinfo.add_center2(prim);
235 sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
236 prims[p_index++] = prim;
237 }
238 }
239 return pinfo;
240 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
241 assert(pinfo.size() == numPrimitives);
242 return pinfo;
243 }
244
245 PrimInfo createPrimRefArrayGrids(GridMesh* mesh, mvector<PrimRef>& prims, mvector<SubGridBuildData>& sgrids)
246 {
247 unsigned int geomID_ = std::numeric_limits<unsigned int>::max ();
248
249 PrimInfo pinfo(empty);
250 size_t numPrimitives = 0;
251
252 ParallelPrefixSumState<PrimInfo> pstate;
253 /* iterate over all grids in a single mesh */
254 pinfo = parallel_prefix_sum( pstate, size_t(0), mesh->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo
255 {
256 PrimInfo pinfo(empty);
257 for (size_t j=r.begin(); j<r.end(); j++)
258 {
259 if (!mesh->valid(j)) continue;
260 BBox3fa bounds = empty;
261 const PrimRef prim(bounds,geomID_,unsigned(j));
262 pinfo.add_center2(prim,mesh->getNumSubGrids(j));
263 }
264 return pinfo;
265 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
266 numPrimitives = pinfo.size();
267 /* resize arrays */
268 sgrids.resize(numPrimitives);
269 prims.resize(numPrimitives);
270
271 /* second run to fill primrefs and SubGridBuildData arrays */
272 pinfo = parallel_prefix_sum( pstate, size_t(0), mesh->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo
273 {
274
275 size_t p_index = base.size();
276 PrimInfo pinfo(empty);
277 for (size_t j=r.begin(); j<r.end(); j++)
278 {
279 if (!mesh->valid(j)) continue;
280 const GridMesh::Grid &g = mesh->grid(j);
281 for (unsigned int y=0; y<g.resY-1u; y+=2)
282 for (unsigned int x=0; x<g.resX-1u; x+=2)
283 {
284 BBox3fa bounds = empty;
285 if (!mesh->buildBounds(g,x,y,bounds)) continue; // get bounds of subgrid
286 const PrimRef prim(bounds,geomID_,unsigned(p_index));
287 pinfo.add_center2(prim);
288 sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
289 prims[p_index++] = prim;
290 }
291 }
292 return pinfo;
293 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
294
295 return pinfo;
296 }
297#endif
298
299 // ====================================================================================================
300 // ====================================================================================================
301 // ====================================================================================================
302
303 IF_ENABLED_TRIS (template size_t createMortonCodeArray<TriangleMesh>(TriangleMesh* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
304 IF_ENABLED_QUADS(template size_t createMortonCodeArray<QuadMesh>(QuadMesh* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
305 IF_ENABLED_USER (template size_t createMortonCodeArray<UserGeometry>(UserGeometry* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
306 IF_ENABLED_INSTANCE (template size_t createMortonCodeArray<Instance>(Instance* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
307 }
308}
309

source code of qtquick3d/src/3rdparty/embree/kernels/builders/primrefgen.cpp