CoCalc -- bvh_refit.cpp

GitHub Repository: godotengine/godot
Path: blob/master/thirdparty/embree/kernels/bvh/bvh_refit.cpp
⁹⁹¹² views
1
// Copyright 2009-2021 Intel Corporation
2
// SPDX-License-Identifier: Apache-2.0
3

4
#include "bvh_refit.h"
5
#include "bvh_statistics.h"
6

7
#include "../geometry/linei.h"
8
#include "../geometry/triangle.h"
9
#include "../geometry/trianglev.h"
10
#include "../geometry/trianglei.h"
11
#include "../geometry/quadv.h"
12
#include "../geometry/object.h"
13
#include "../geometry/instance.h"
14
#include "../geometry/instance_array.h"
15

16
#include "../../common/algorithms/parallel_for.h"
17

18
namespace embree
19
{
20
  namespace isa
21
  {
22
    static const size_t SINGLE_THREAD_THRESHOLD = 4*1024;
23
    
24
    template<int N>
25
    __forceinline bool compare(const typename BVHN<N>::NodeRef* a, const typename BVHN<N>::NodeRef* b)
26
    {
27
      size_t sa = *(size_t*)&a->node()->lower_x;
28
      size_t sb = *(size_t*)&b->node()->lower_x;
29
      return sa < sb;
30
    }
31

32
    template<int N>
33
    BVHNRefitter<N>::BVHNRefitter (BVH* bvh, const LeafBoundsInterface& leafBounds)
34
      : bvh(bvh), leafBounds(leafBounds), numSubTrees(0)
35
    {
36
    }
37

38
    template<int N>
39
    void BVHNRefitter<N>::refit()
40
    {
41
      if (bvh->numPrimitives <= SINGLE_THREAD_THRESHOLD) {
42
        bvh->bounds = LBBox3fa(recurse_bottom(bvh->root));
43
      }
44
      else
45
      {
46
        BBox3fa subTreeBounds[MAX_NUM_SUB_TREES];
47
        numSubTrees = 0;
48
        gather_subtree_refs(bvh->root,numSubTrees,0);
49
        if (numSubTrees)
50
          parallel_for(size_t(0), numSubTrees, size_t(1), [&](const range<size_t>& r) {
51
              for (size_t i=r.begin(); i<r.end(); i++) {
52
                NodeRef& ref = subTrees[i];
53
                subTreeBounds[i] = recurse_bottom(ref);
54
              }
55
            });
56

57
        numSubTrees = 0;        
58
        bvh->bounds = LBBox3fa(refit_toplevel(bvh->root,numSubTrees,subTreeBounds,0));
59
      }    
60
  }
61

62
    template<int N>
63
    void BVHNRefitter<N>::gather_subtree_refs(NodeRef& ref,
64
                                              size_t &subtrees,
65
                                              const size_t depth)
66
    {
67
      if (depth >= MAX_SUB_TREE_EXTRACTION_DEPTH) 
68
      {
69
        assert(subtrees < MAX_NUM_SUB_TREES);
70
        subTrees[subtrees++] = ref;
71
        return;
72
      }
73

74
      if (ref.isAABBNode())
75
      {
76
        AABBNode* node = ref.getAABBNode();
77
        for (size_t i=0; i<N; i++) {
78
          NodeRef& child = node->child(i);
79
          if (unlikely(child == BVH::emptyNode)) continue;
80
          gather_subtree_refs(child,subtrees,depth+1); 
81
        }
82
      }
83
    }
84

85
    template<int N>
86
    BBox3fa BVHNRefitter<N>::refit_toplevel(NodeRef& ref,
87
                                            size_t &subtrees,
88
                                            const BBox3fa *const subTreeBounds,
89
                                            const size_t depth)
90
    {
91
      if (depth >= MAX_SUB_TREE_EXTRACTION_DEPTH) 
92
      {
93
        assert(subtrees < MAX_NUM_SUB_TREES);
94
        assert(subTrees[subtrees] == ref);
95
        return subTreeBounds[subtrees++];
96
      }
97

98
      if (ref.isAABBNode())
99
      {
100
        AABBNode* node = ref.getAABBNode();
101
        BBox3fa bounds[N];
102

103
        for (size_t i=0; i<N; i++)
104
        {
105
          NodeRef& child = node->child(i);
106

107
          if (unlikely(child == BVH::emptyNode)) 
108
            bounds[i] = BBox3fa(empty);
109
          else
110
            bounds[i] = refit_toplevel(child,subtrees,subTreeBounds,depth+1); 
111
        }
112
        
113
        BBox3vf<N> boundsT = transpose<N>(bounds);
114
      
115
        /* set new bounds */
116
        node->lower_x = boundsT.lower.x;
117
        node->lower_y = boundsT.lower.y;
118
        node->lower_z = boundsT.lower.z;
119
        node->upper_x = boundsT.upper.x;
120
        node->upper_y = boundsT.upper.y;
121
        node->upper_z = boundsT.upper.z;
122
        
123
        return merge<N>(bounds);
124
      }
125
      else
126
        return leafBounds.leafBounds(ref);
127
    }
128

129
    // =========================================================
130
    // =========================================================
131
    // =========================================================
132

133
    
134
    template<int N>
135
    BBox3fa BVHNRefitter<N>::recurse_bottom(NodeRef& ref)
136
    {
137
      /* this is a leaf node */
138
      if (unlikely(ref.isLeaf()))
139
        return leafBounds.leafBounds(ref);
140
      
141
      /* recurse if this is an internal node */
142
      AABBNode* node = ref.getAABBNode();
143

144
      /* enable exclusive prefetch for >= AVX platforms */      
145
#if defined(__AVX__)      
146
      BVH::prefetchW(ref);
147
#endif      
148
      BBox3fa bounds[N];
149

150
      for (size_t i=0; i<N; i++)
151
        if (unlikely(node->child(i) == BVH::emptyNode))
152
        {
153
          bounds[i] = BBox3fa(empty);          
154
        }
155
      else
156
        bounds[i] = recurse_bottom(node->child(i));
157
      
158
      /* AOS to SOA transform */
159
      BBox3vf<N> boundsT = transpose<N>(bounds);
160
      
161
      /* set new bounds */
162
      node->lower_x = boundsT.lower.x;
163
      node->lower_y = boundsT.lower.y;
164
      node->lower_z = boundsT.lower.z;
165
      node->upper_x = boundsT.upper.x;
166
      node->upper_y = boundsT.upper.y;
167
      node->upper_z = boundsT.upper.z;
168

169
      return merge<N>(bounds);
170
    }
171

172
    template<int N, typename Mesh, typename Primitive>
173
    BVHNRefitT<N,Mesh,Primitive>::BVHNRefitT (BVH* bvh, Builder* builder, Mesh* mesh, size_t mode)
174
      : bvh(bvh), builder(builder), refitter(new BVHNRefitter<N>(bvh,*(typename BVHNRefitter<N>::LeafBoundsInterface*)this)), mesh(mesh), topologyVersion(0) {}
175

176
    template<int N, typename Mesh, typename Primitive>
177
    void BVHNRefitT<N,Mesh,Primitive>::clear()
178
    {
179
      if (builder) 
180
        builder->clear();
181
    }
182
    
183
    template<int N, typename Mesh, typename Primitive>
184
    void BVHNRefitT<N,Mesh,Primitive>::build()
185
    {
186
      if (mesh->topologyChanged(topologyVersion)) {
187
        topologyVersion = mesh->getTopologyVersion();
188
        builder->build();
189
      }
190
      else
191
        refitter->refit();
192
    }
193

194
    template class BVHNRefitter<4>;
195
#if defined(__AVX__)
196
    template class BVHNRefitter<8>;
197
#endif
198
    
199
#if defined(EMBREE_GEOMETRY_TRIANGLE)
200
    Builder* BVH4Triangle4MeshBuilderSAH  (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
201
    Builder* BVH4Triangle4vMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
202
    Builder* BVH4Triangle4iMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
203

204
    Builder* BVH4Triangle4MeshRefitSAH  (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4> ((BVH4*)accel,BVH4Triangle4MeshBuilderSAH (accel,mesh,geomID,mode),mesh,mode); }
205
    Builder* BVH4Triangle4vMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4v>((BVH4*)accel,BVH4Triangle4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
206
    Builder* BVH4Triangle4iMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,TriangleMesh,Triangle4i>((BVH4*)accel,BVH4Triangle4iMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
207
#if  defined(__AVX__)
208
    Builder* BVH8Triangle4MeshBuilderSAH  (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
209
    Builder* BVH8Triangle4vMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
210
    Builder* BVH8Triangle4iMeshBuilderSAH (void* bvh, TriangleMesh* mesh, unsigned int geomID, size_t mode);
211

212
    Builder* BVH8Triangle4MeshRefitSAH  (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4> ((BVH8*)accel,BVH8Triangle4MeshBuilderSAH (accel,mesh,geomID,mode),mesh,mode); }
213
    Builder* BVH8Triangle4vMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4v>((BVH8*)accel,BVH8Triangle4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
214
    Builder* BVH8Triangle4iMeshRefitSAH (void* accel, TriangleMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,TriangleMesh,Triangle4i>((BVH8*)accel,BVH8Triangle4iMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
215
#endif
216
#endif
217

218
#if defined(EMBREE_GEOMETRY_QUAD)
219
    Builder* BVH4Quad4vMeshBuilderSAH (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode);
220
    Builder* BVH4Quad4vMeshRefitSAH (void* accel, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,QuadMesh,Quad4v>((BVH4*)accel,BVH4Quad4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
221

222
#if  defined(__AVX__)
223
    Builder* BVH8Quad4vMeshBuilderSAH (void* bvh, QuadMesh* mesh, unsigned int geomID, size_t mode);
224
    Builder* BVH8Quad4vMeshRefitSAH (void* accel, QuadMesh* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,QuadMesh,Quad4v>((BVH8*)accel,BVH8Quad4vMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
225
#endif
226

227
#endif
228

229
#if defined(EMBREE_GEOMETRY_USER)
230
    Builder* BVH4VirtualMeshBuilderSAH (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode);
231
    Builder* BVH4VirtualMeshRefitSAH (void* accel, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,UserGeometry,Object>((BVH4*)accel,BVH4VirtualMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
232

233
#if  defined(__AVX__)
234
    Builder* BVH8VirtualMeshBuilderSAH (void* bvh, UserGeometry* mesh, unsigned int geomID, size_t mode);
235
    Builder* BVH8VirtualMeshRefitSAH (void* accel, UserGeometry* mesh, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,UserGeometry,Object>((BVH8*)accel,BVH8VirtualMeshBuilderSAH(accel,mesh,geomID,mode),mesh,mode); }
236
#endif
237
#endif
238

239
#if defined(EMBREE_GEOMETRY_INSTANCE)
240
    Builder* BVH4InstanceMeshBuilderSAH (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
241
    Builder* BVH4InstanceMeshRefitSAH (void* accel, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,Instance,InstancePrimitive>((BVH4*)accel,BVH4InstanceMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
242
#if  defined(__AVX__)
243
    Builder* BVH8InstanceMeshBuilderSAH (void* bvh, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
244
    Builder* BVH8InstanceMeshRefitSAH (void* accel, Instance* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,Instance,InstancePrimitive>((BVH8*)accel,BVH8InstanceMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
245
#endif
246
#endif
247

248
#if defined(EMBREE_GEOMETRY_INSTANCE_ARRAY)
249
    Builder* BVH4InstanceArrayMeshBuilderSAH (void* bvh, InstanceArray* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
250
    Builder* BVH4InstanceArrayMeshRefitSAH (void* accel, InstanceArray* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<4,InstanceArray,InstanceArrayPrimitive>((BVH4*)accel,BVH4InstanceArrayMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
251

252
#if  defined(__AVX__)
253
    Builder* BVH8InstanceArrayMeshBuilderSAH (void* bvh, InstanceArray* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode);
254
    Builder* BVH8InstanceArrayMeshRefitSAH (void* accel, InstanceArray* mesh, Geometry::GTypeMask gtype, unsigned int geomID, size_t mode) { return new BVHNRefitT<8,InstanceArray,InstanceArrayPrimitive>((BVH8*)accel,BVH8InstanceArrayMeshBuilderSAH(accel,mesh,gtype,geomID,mode),mesh,mode); }
255
#endif
256
#endif
257
  }
258
}
259

260
Product

Resources

Company
