CoCalc -- primrefgen.cpp

GitHub Repository: godotengine/godot
Path: blob/master/thirdparty/embree/kernels/builders/primrefgen.cpp
⁹⁹⁰⁶ views
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

10
namespace 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( pstate, size_t(0), geometry->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo {
21
          return geometry->createPrimRefArray(prims,r,r.begin(),geomID);
22
        }, [](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( pstate, size_t(0), geometry->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo {
29
          return geometry->createPrimRefArray(prims,r,base.size(),geomID);
30
        }, [](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(iter,size_t(1024));
43
      PrimInfo pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
44
          return mesh->createPrimRefArray(prims,r,k,(unsigned)geomID);
45
        }, [](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( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
52
            return mesh->createPrimRefArray(prims,r,base.size(),(unsigned)geomID);
53
          }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
54
      }
55
      return pinfo;
56
    }
57

58
    PrimInfo createPrimRefArray(Scene* scene, Geometry::GTypeMask types, bool mblur, const size_t numPrimRefs, mvector<PrimRef>& prims, mvector<SubGridBuildData>& sgrids, BuildProgressMonitor& progressMonitor)
59
    {
60
      ParallelForForPrefixSumState<PrimInfo> pstate;
61
      Scene::Iterator2 iter(scene,types,mblur);
62
      
63
      /* first try */
64
      progressMonitor(0);
65
      pstate.init(iter,size_t(1024));
66
      PrimInfo pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
67
         return mesh->createPrimRefArray(prims,sgrids,r,k,(unsigned)geomID);
68
       }, [](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( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
75
          return mesh->createPrimRefArray(prims,sgrids,r,base.size(),(unsigned)geomID);
76
        }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
77
      }
78
      return pinfo;
79
    }
80

81
    PrimInfo createPrimRefArrayMBlur(Scene* scene, Geometry::GTypeMask types, const size_t numPrimRefs, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor, size_t itime)
82
    {
83
      ParallelForForPrefixSumState<PrimInfo> pstate;
84
      Scene::Iterator2 iter(scene,types,true);
85
      
86
      /* first try */
87
      progressMonitor(0);
88
      pstate.init(iter,size_t(1024));
89
      PrimInfo pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
90
          return mesh->createPrimRefArrayMB(prims,itime,r,k,(unsigned)geomID);
91
        }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(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( pstate, iter, PrimInfo(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
98
            return mesh->createPrimRefArrayMB(prims,itime,r,base.size(),(unsigned)geomID);
99
          }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
100
      }
101
      return pinfo;
102
    }
103

104
    PrimInfoMB createPrimRefArrayMSMBlur(Scene* scene, Geometry::GTypeMask types, const size_t numPrimRefs, mvector<PrimRefMB>& prims, BuildProgressMonitor& progressMonitor, BBox1f t0t1)
105
    {
106
      ParallelForForPrefixSumState<PrimInfoMB> pstate;
107
      Scene::Iterator2 iter(scene,types,true);
108
      
109
      /* first try */
110
      progressMonitor(0);
111
      pstate.init(iter,size_t(1024));
112
      PrimInfoMB pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfoMB(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfoMB {
113
          return mesh->createPrimRefMBArray(prims,t0t1,r,k,(unsigned)geomID);
114
      }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
115
      
116
      /* if we need to filter out geometry, run again */
117
      if (pinfo.size() != numPrimRefs)
118
      {
119
        progressMonitor(0);
120
        pinfo = parallel_for_for_prefix_sum1( pstate, iter, PrimInfoMB(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfoMB& base) -> PrimInfoMB {
121
            return mesh->createPrimRefMBArray(prims,t0t1,r,base.size(),(unsigned)geomID);
122
        }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
123
      }
124

125
      /* the BVH starts with that time range, even though primitives might have smaller/larger time range */
126
      pinfo.time_range = t0t1;
127
      return pinfo;
128
    }
129

130
    PrimInfoMB createPrimRefArrayMSMBlur(Scene* scene, Geometry::GTypeMask types, const size_t numPrimRefs, mvector<PrimRefMB>& prims, mvector<SubGridBuildData>& sgrids, BuildProgressMonitor& progressMonitor, BBox1f t0t1)
131
    {
132
      ParallelForForPrefixSumState<PrimInfoMB> pstate;
133
      Scene::Iterator2 iter(scene,types,true);
134
      
135
      /* first try */
136
      progressMonitor(0);
137
      pstate.init(iter,size_t(1024));
138
      PrimInfoMB pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfoMB(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfoMB {
139
         return mesh->createPrimRefMBArray(prims,sgrids,t0t1,r,k,(unsigned)geomID);
140
      }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
141
      
142
      /* if we need to filter out geometry, run again */
143
      if (pinfo.size() != numPrimRefs)
144
      {
145
        progressMonitor(0);
146
        pinfo = parallel_for_for_prefix_sum1( pstate, iter, PrimInfoMB(empty), [&](Geometry* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfoMB& base) -> PrimInfoMB {
147
          return mesh->createPrimRefMBArray(prims,sgrids,t0t1,r,base.size(),(unsigned)geomID);
148
        }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
149
      }
150

151
      /* the BVH starts with that time range, even though primitives might have smaller/larger time range */
152
      pinfo.time_range = t0t1;
153
      return pinfo;
154
    }
155

156
    template<typename Mesh>
157
    size_t createMortonCodeArray(Mesh* mesh, mvector<BVHBuilderMorton::BuildPrim>& morton, BuildProgressMonitor& progressMonitor)
158
    {
159
      size_t numPrimitives = morton.size();
160

161
      /* compute scene bounds */
162
      std::pair<size_t,BBox3fa> cb_empty(0,empty);
163
      auto cb = parallel_reduce 
164
        ( size_t(0), numPrimitives, size_t(1024), cb_empty, [&](const range<size_t>& r) -> std::pair<size_t,BBox3fa>
165
          {
166
            size_t num = 0;
167
            BBox3fa bounds = empty;
168
            
169
            for (size_t j=r.begin(); j<r.end(); j++)
170
            {
171
              BBox3fa prim_bounds = empty;
172
              if (unlikely(!mesh->buildBounds(j,&prim_bounds))) continue;
173
              bounds.extend(center2(prim_bounds));
174
              num++;
175
            }
176
            return std::make_pair(num,bounds);
177
          }, [] (const std::pair<size_t,BBox3fa>& a, const std::pair<size_t,BBox3fa>& b) {
178
          return std::make_pair(a.first + b.first,merge(a.second,b.second)); 
179
        });
180
      
181
      
182
      size_t numPrimitivesGen = cb.first;
183
      const BBox3fa centBounds = cb.second;
184
      
185
      /* compute morton codes */
186
      if (likely(numPrimitivesGen == numPrimitives))
187
      {
188
        /* fast path if all primitives were valid */
189
        BVHBuilderMorton::MortonCodeMapping mapping(centBounds);
190
        parallel_for( size_t(0), numPrimitives, size_t(1024), [&](const range<size_t>& r) -> void {
191
            BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[r.begin()]);
192
            for (size_t j=r.begin(); j<r.end(); j++)
193
              generator(mesh->bounds(j),unsigned(j));
194
          });
195
      }
196
      else
197
      {
198
        /* slow path, fallback in case some primitives were invalid */
199
        ParallelPrefixSumState<size_t> pstate;
200
        BVHBuilderMorton::MortonCodeMapping mapping(centBounds);
201
        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 {
202
            size_t num = 0;
203
            BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[r.begin()]);
204
            for (size_t j=r.begin(); j<r.end(); j++)
205
            {
206
              BBox3fa bounds = empty;
207
              if (unlikely(!mesh->buildBounds(j,&bounds))) continue;
208
              generator(bounds,unsigned(j));
209
              num++;
210
            }
211
            return num;
212
          }, std::plus<size_t>());
213
        
214
        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 {
215
            size_t num = 0;
216
            BVHBuilderMorton::MortonCodeGenerator generator(mapping,&morton.data()[base]);
217
            for (size_t j=r.begin(); j<r.end(); j++)
218
            {
219
              BBox3fa bounds = empty;
220
              if (!mesh->buildBounds(j,&bounds)) continue;
221
              generator(bounds,unsigned(j));
222
              num++;
223
            }
224
            return num;
225
          }, std::plus<size_t>());          
226
      }
227
      return numPrimitivesGen;
228
    }
229

230
    // ====================================================================================================
231
    // ====================================================================================================
232
    // ====================================================================================================
233

234
    // special variants for grid meshes
235

236
#if defined(EMBREE_GEOMETRY_GRID)
237
    PrimInfo createPrimRefArrayGrids(Scene* scene, mvector<PrimRef>& prims, mvector<SubGridBuildData>& sgrids)
238
    {
239
      PrimInfo pinfo(empty);
240
      size_t numPrimitives = 0;
241
      
242
      /* first run to get #primitives */
243

244
      ParallelForForPrefixSumState<PrimInfo> pstate;
245
      Scene::Iterator<GridMesh,false> iter(scene);
246

247
      pstate.init(iter,size_t(1024));
248

249
      /* iterate over all meshes in the scene */
250
      pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
251
          PrimInfo pinfo(empty);
252
          for (size_t j=r.begin(); j<r.end(); j++)
253
          {
254
            if (!mesh->valid(j)) continue;
255
            BBox3fa bounds = empty;
256
            const PrimRef prim(bounds,(unsigned)geomID,(unsigned)j);
257
            if (!mesh->valid(j)) continue;
258
            pinfo.add_center2(prim,mesh->getNumSubGrids(j));
259
          }
260
          return pinfo;
261
        }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
262
      numPrimitives = pinfo.size();
263
          
264
      /* resize arrays */
265
      sgrids.resize(numPrimitives); 
266
      prims.resize(numPrimitives); 
267

268
      /* second run to fill primrefs and SubGridBuildData arrays */
269
      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 {
270
        return mesh->createPrimRefArray(prims,sgrids,r,base.size(),geomID);
271
      }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
272
      assert(pinfo.size() == numPrimitives);
273
      return pinfo;
274
    }
275

276
    PrimInfo createPrimRefArrayGrids(GridMesh* mesh, mvector<PrimRef>& prims, mvector<SubGridBuildData>& sgrids)
277
    {
278
      unsigned int geomID_ = std::numeric_limits<unsigned int>::max ();
279

280
      PrimInfo pinfo(empty);
281
      size_t numPrimitives = 0;
282
      
283
      ParallelPrefixSumState<PrimInfo> pstate;
284
      /* iterate over all grids in a single mesh */
285
      pinfo = parallel_prefix_sum( pstate, size_t(0), mesh->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo
286
                                   {
287
                                     PrimInfo pinfo(empty);
288
                                     for (size_t j=r.begin(); j<r.end(); j++)
289
                                     {
290
                                       if (!mesh->valid(j)) continue;
291
                                       BBox3fa bounds = empty;
292
                                       const PrimRef prim(bounds,geomID_,unsigned(j));
293
                                       pinfo.add_center2(prim,mesh->getNumSubGrids(j));
294
                                     }
295
                                     return pinfo;
296
                                   }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
297
      numPrimitives = pinfo.size();
298
      /* resize arrays */
299
      sgrids.resize(numPrimitives); 
300
      prims.resize(numPrimitives); 
301

302
      /* second run to fill primrefs and SubGridBuildData arrays */
303
      pinfo = parallel_prefix_sum( pstate, size_t(0), mesh->size(), size_t(1024), PrimInfo(empty), [&](const range<size_t>& r, const PrimInfo& base) -> PrimInfo {
304
        return mesh->createPrimRefArray(prims,sgrids,r,base.size(),geomID_);
305
      }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
306

307
      return pinfo;
308
    }
309

310
    PrimInfoMB createPrimRefArrayMSMBlurGrid(Scene* scene, mvector<PrimRefMB>& prims, mvector<SubGridBuildData>& sgrids, BuildProgressMonitor& progressMonitor, BBox1f t0t1)
311
    {
312
      /* first run to get #primitives */
313
      ParallelForForPrefixSumState<PrimInfoMB> pstate;
314
      Scene::Iterator<GridMesh,true> iter(scene);
315
      
316
      pstate.init(iter,size_t(1024));
317
      /* iterate over all meshes in the scene */
318
      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 {
319
                                                                                            
320
         PrimInfoMB pinfoMB(empty);
321
         for (size_t j=r.begin(); j<r.end(); j++)
322
         {
323
           if (!mesh->valid(j, mesh->timeSegmentRange(t0t1))) continue;
324
           LBBox3fa bounds(empty);
325
           PrimInfoMB gridMB(0,mesh->getNumSubGrids(j));
326
           pinfoMB.merge(gridMB);
327
         }
328
         return pinfoMB;
329
      }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
330
      
331
      size_t numPrimitives = pinfoMB.size();
332
      if (numPrimitives == 0) return pinfoMB;
333
      
334
      /* resize arrays */
335
      sgrids.resize(numPrimitives); 
336
      prims.resize(numPrimitives); 
337
      /* second run to fill primrefs and SubGridBuildData arrays */
338
      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 {
339
        return mesh->createPrimRefMBArray(prims,sgrids,t0t1,r,base.size(),(unsigned)geomID);                                                                                 
340
      }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
341
      
342
      assert(pinfoMB.size() == numPrimitives);
343
      pinfoMB.time_range = t0t1;
344
      return pinfoMB;
345
    }
346
    
347
#endif
348
    
349
    // ====================================================================================================
350
    // ====================================================================================================
351
    // ====================================================================================================
352
    
353
    IF_ENABLED_TRIS (template size_t createMortonCodeArray<TriangleMesh>(TriangleMesh* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
354
    IF_ENABLED_QUADS(template size_t createMortonCodeArray<QuadMesh>(QuadMesh* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
355
    IF_ENABLED_USER (template size_t createMortonCodeArray<UserGeometry>(UserGeometry* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
356
    IF_ENABLED_INSTANCE (template size_t createMortonCodeArray<Instance>(Instance* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
357
    IF_ENABLED_INSTANCE_ARRAY (template size_t createMortonCodeArray<InstanceArray>(InstanceArray* mesh COMMA mvector<BVHBuilderMorton::BuildPrim>& morton COMMA BuildProgressMonitor& progressMonitor));
358
  }
359
}
360

361
Product

Resources

Company
