Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
godotengine
GitHub Repository: godotengine/godot
 Path: blob/master/thirdparty/embree/kernels/bvh/bvh_intersector1.cpp
9913 views
1
// Copyright 2009-2021 Intel Corporation

2
// SPDX-License-Identifier: Apache-2.0

3


4
#include "bvh_intersector1.h"

5
#include "node_intersector1.h"

6
#include "bvh_traverser1.h"

7


8
#include "../geometry/intersector_iterators.h"

9
#include "../geometry/triangle_intersector.h"

10
#include "../geometry/trianglev_intersector.h"

11
#include "../geometry/trianglev_mb_intersector.h"

12
#include "../geometry/trianglei_intersector.h"

13
#include "../geometry/quadv_intersector.h"

14
#include "../geometry/quadi_intersector.h"

15
#include "../geometry/curveNv_intersector.h"

16
#include "../geometry/curveNi_intersector.h"

17
#include "../geometry/curveNi_mb_intersector.h"

18
#include "../geometry/linei_intersector.h"

19
#include "../geometry/subdivpatch1_intersector.h"

20
#include "../geometry/object_intersector.h"

21
#include "../geometry/instance_intersector.h"

22
#include "../geometry/instance_array_intersector.h"

23
#include "../geometry/subgrid_intersector.h"

24
#include "../geometry/subgrid_mb_intersector.h"

25
#include "../geometry/curve_intersector_virtual.h"

26


27
namespace embree

28
{

29
  namespace isa

30
  {

31
    template<int N, int types, bool robust, typename PrimitiveIntersector1>

32
    void BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::intersect(const Accel::Intersectors* __restrict__ This,

33
                                                                              RayHit& __restrict__ ray,

34
                                                                              RayQueryContext* __restrict__ context)

35
    {

36
      const BVH* __restrict__ bvh = (const BVH*)This->ptr;

37
      

38
      /* we may traverse an empty BVH in case all geometry was invalid */

39
      if (bvh->root == BVH::emptyNode)

40
        return;

41
      

42
      /* perform per ray precalculations required by the primitive intersector */

43
      Precalculations pre(ray, bvh);

44


45
      /* stack state */

46
      StackItemT<NodeRef> stack[stackSize];    // stack of nodes

47
      StackItemT<NodeRef>* stackPtr = stack+1; // current stack pointer

48
      StackItemT<NodeRef>* stackEnd = stack+stackSize;

49
      stack[0].ptr  = bvh->root;

50
      stack[0].dist = neg_inf;

51
      

52
      if (bvh->root == BVH::emptyNode)

53
        return;

54
      

55
      /* filter out invalid rays */

56
#if defined(EMBREE_IGNORE_INVALID_RAYS)

57
      if (!ray.valid()) return;

58
#endif

59
      /* verify correct input */

60
      assert(ray.valid());

61
      assert(ray.tnear() >= 0.0f);

62
      assert(!(types & BVH_MB) || (ray.time() >= 0.0f && ray.time() <= 1.0f));

63


64
      /* load the ray into SIMD registers */

65
      TravRay<N,robust> tray(ray.org, ray.dir, max(ray.tnear(), 0.0f), max(ray.tfar, 0.0f));

66


67
      /* initialize the node traverser */

68
      BVHNNodeTraverser1Hit<N, types> nodeTraverser;

69


70
      /* pop loop */

71
      while (true) pop:

72
      {

73
        /* pop next node */

74
        if (unlikely(stackPtr == stack)) break;

75
        stackPtr--;

76
        NodeRef cur = NodeRef(stackPtr->ptr);

77


78
        /* if popped node is too far, pop next one */

79
        if (unlikely(*(float*)&stackPtr->dist > ray.tfar))

80
          continue;

81


82
        /* downtraversal loop */

83
        while (true)

84
        {

85
          /* intersect node */

86
          size_t mask; vfloat<N> tNear;

87
          STAT3(normal.trav_nodes,1,1,1);

88
          bool nodeIntersected = BVHNNodeIntersector1<N, types, robust>::intersect(cur, tray, ray.time(), tNear, mask);

89
          if (unlikely(!nodeIntersected)) { STAT3(normal.trav_nodes,-1,-1,-1); break; }

90


91
          /* if no child is hit, pop next node */

92
          if (unlikely(mask == 0))

93
            goto pop;

94


95
          /* select next child and push other children */

96
          nodeTraverser.traverseClosestHit(cur, mask, tNear, stackPtr, stackEnd);

97
        }

98


99
        /* this is a leaf node */

100
        assert(cur != BVH::emptyNode);

101
        STAT3(normal.trav_leaves,1,1,1);

102
        size_t num; Primitive* prim = (Primitive*)cur.leaf(num);

103
        size_t lazy_node = 0;

104
        PrimitiveIntersector1::intersect(This, pre, ray, context, prim, num, tray, lazy_node);

105
        tray.tfar = ray.tfar;

106


107
        /* push lazy node onto stack */

108
        if (unlikely(lazy_node)) {

109
          stackPtr->ptr = lazy_node;

110
          stackPtr->dist = neg_inf;

111
          stackPtr++;

112
        }

113
      }

114
    }

115


116
    template<int N, int types, bool robust, typename PrimitiveIntersector1>

117
    void BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::occluded(const Accel::Intersectors* __restrict__ This,

118
                                                                             Ray& __restrict__ ray,

119
                                                                             RayQueryContext* __restrict__ context)

120
    {

121
      const BVH* __restrict__ bvh = (const BVH*)This->ptr;

122
      

123
      /* we may traverse an empty BVH in case all geometry was invalid */

124
      if (bvh->root == BVH::emptyNode)

125
        return;

126
       

127
      /* early out for already occluded rays */

128
      if (unlikely(ray.tfar < 0.0f))

129
        return;

130


131
      /* perform per ray precalculations required by the primitive intersector */

132
      Precalculations pre(ray, bvh);

133


134
      /* stack state */

135
      NodeRef stack[stackSize];    // stack of nodes that still need to get traversed

136
      NodeRef* stackPtr = stack+1; // current stack pointer

137
      NodeRef* stackEnd = stack+stackSize;

138
      stack[0] = bvh->root;

139


140
      /* filter out invalid rays */

141
#if defined(EMBREE_IGNORE_INVALID_RAYS)

142
      if (!ray.valid()) return;

143
#endif

144


145
      /* verify correct input */

146
      assert(ray.valid());

147
      assert(ray.tnear() >= 0.0f);

148
      assert(!(types & BVH_MB) || (ray.time() >= 0.0f && ray.time() <= 1.0f));

149


150
      /* load the ray into SIMD registers */

151
      TravRay<N,robust> tray(ray.org, ray.dir, max(ray.tnear(), 0.0f), max(ray.tfar, 0.0f));

152


153
      /* initialize the node traverser */

154
      BVHNNodeTraverser1Hit<N, types> nodeTraverser;

155


156
      /* pop loop */

157
      while (true) pop:

158
      {

159
        /* pop next node */

160
        if (unlikely(stackPtr == stack)) break;

161
        stackPtr--;

162
        NodeRef cur = (NodeRef)*stackPtr;

163


164
        /* downtraversal loop */

165
        while (true)

166
        {

167
          /* intersect node */

168
          size_t mask; vfloat<N> tNear;

169
          STAT3(shadow.trav_nodes,1,1,1);

170
          bool nodeIntersected = BVHNNodeIntersector1<N, types, robust>::intersect(cur, tray, ray.time(), tNear, mask);

171
          if (unlikely(!nodeIntersected)) { STAT3(shadow.trav_nodes,-1,-1,-1); break; }

172


173
          /* if no child is hit, pop next node */

174
          if (unlikely(mask == 0))

175
            goto pop;

176


177
          /* select next child and push other children */

178
          nodeTraverser.traverseAnyHit(cur, mask, tNear, stackPtr, stackEnd);

179
        }

180


181
        /* this is a leaf node */

182
        assert(cur != BVH::emptyNode);

183
        STAT3(shadow.trav_leaves,1,1,1);

184
        size_t num; Primitive* prim = (Primitive*)cur.leaf(num);

185
        size_t lazy_node = 0;

186
        if (PrimitiveIntersector1::occluded(This, pre, ray, context, prim, num, tray, lazy_node)) {

187
          ray.tfar = neg_inf;

188
          break;

189
        }

190


191
        /* push lazy node onto stack */

192
        if (unlikely(lazy_node)) {

193
          *stackPtr = (NodeRef)lazy_node;

194
          stackPtr++;

195
        }

196
      }

197
    }

198


199
    template<int N, int types, bool robust, typename PrimitiveIntersector1>

200
    struct PointQueryDispatch

201
    {

202
      typedef typename PrimitiveIntersector1::Precalculations Precalculations;

203
      typedef typename PrimitiveIntersector1::Primitive Primitive;

204
      typedef BVHN<N> BVH;

205
      typedef typename BVH::NodeRef NodeRef;

206
      typedef typename BVH::AABBNode AABBNode;

207
      typedef typename BVH::AABBNodeMB4D AABBNodeMB4D;

208


209
      static const size_t stackSize = 1+(N-1)*BVH::maxDepth+3; // +3 due to 16-wide store

210


211
      static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context)

212
      {

213
        const BVH* __restrict__ bvh = (const BVH*)This->ptr;

214
        

215
        /* we may traverse an empty BVH in case all geometry was invalid */

216
        if (bvh->root == BVH::emptyNode)

217
          return false;

218
        

219
        /* stack state */

220
        StackItemT<NodeRef> stack[stackSize];    // stack of nodes

221
        StackItemT<NodeRef>* stackPtr = stack+1; // current stack pointer

222
        StackItemT<NodeRef>* stackEnd = stack+stackSize;

223
        stack[0].ptr  = bvh->root;

224
        stack[0].dist = neg_inf;

225
        

226
        /* verify correct input */

227
        assert(!(types & BVH_MB) || (query->time >= 0.0f && query->time <= 1.0f));

228


229
        /* load the point query into SIMD registers */

230
        TravPointQuery<N> tquery(query->p, context->query_radius);

231


232
        /* initialize the node traverser */

233
        BVHNNodeTraverser1Hit<N,types> nodeTraverser;

234


235
        bool changed = false;

236
        float cull_radius = context->query_type == POINT_QUERY_TYPE_SPHERE

237
                          ? query->radius * query->radius

238
                          : dot(context->query_radius, context->query_radius);

239


240
        /* pop loop */

241
        while (true) pop:

242
        {

243
          /* pop next node */

244
          if (unlikely(stackPtr == stack)) break;

245
          stackPtr--;

246
          NodeRef cur = NodeRef(stackPtr->ptr);

247


248
          /* if popped node is too far, pop next one */

249
          if (unlikely(*(float*)&stackPtr->dist > cull_radius))

250
            continue;

251


252
          /* downtraversal loop */

253
          while (true)

254
          {

255
            /* intersect node */

256
            size_t mask; vfloat<N> tNear;

257
            STAT3(point_query.trav_nodes,1,1,1);

258
            bool nodeIntersected;

259
            if (likely(context->query_type == POINT_QUERY_TYPE_SPHERE)) {

260
              nodeIntersected = BVHNNodePointQuerySphere1<N, types>::pointQuery(cur, tquery, query->time, tNear, mask);

261
            } else {

262
              nodeIntersected = BVHNNodePointQueryAABB1  <N, types>::pointQuery(cur, tquery, query->time, tNear, mask);

263
            }

264
            if (unlikely(!nodeIntersected)) { STAT3(point_query.trav_nodes,-1,-1,-1); break; }

265


266
            /* if no child is hit, pop next node */

267
            if (unlikely(mask == 0))

268
              goto pop;

269


270
            /* select next child and push other children */

271
            nodeTraverser.traverseClosestHit(cur, mask, tNear, stackPtr, stackEnd);

272
          }

273


274
          /* this is a leaf node */

275
          assert(cur != BVH::emptyNode);

276
          STAT3(point_query.trav_leaves,1,1,1);

277
          size_t num; Primitive* prim = (Primitive*)cur.leaf(num);

278
          size_t lazy_node = 0;

279
          if (PrimitiveIntersector1::pointQuery(This, query, context, prim, num, tquery, lazy_node))

280
          {

281
            changed = true;

282
            tquery.rad = context->query_radius;

283
            cull_radius = context->query_type == POINT_QUERY_TYPE_SPHERE

284
                        ? query->radius * query->radius

285
                        : dot(context->query_radius, context->query_radius);

286
          }

287


288
          /* push lazy node onto stack */

289
          if (unlikely(lazy_node)) {

290
            stackPtr->ptr = lazy_node;

291
            stackPtr->dist = neg_inf;

292
            stackPtr++;

293
          }

294
        }

295
        return changed;

296
      }

297
    };

298


299
    /* disable point queries for not yet supported geometry types */

300
    template<int N, int types, bool robust>

301
    struct PointQueryDispatch<N, types, robust, VirtualCurveIntersector1> {

302
      static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }

303
    };

304
    

305
    template<int N, int types, bool robust>

306
    struct PointQueryDispatch<N, types, robust, SubdivPatch1Intersector1> {

307
      static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }

308
    };

309
    

310
    template<int N, int types, bool robust>

311
    struct PointQueryDispatch<N, types, robust, SubdivPatch1MBIntersector1> {

312
      static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }

313
    };

314


315
    template<int N, int types, bool robust, typename PrimitiveIntersector1>

316
    bool BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::pointQuery(

317
      const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context)

318
    {

319
      return PointQueryDispatch<N, types, robust, PrimitiveIntersector1>::pointQuery(This, query, context);

320
    }

321
  }

322
}

323


324