BLI_kdopbvh.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2006 NaN Holding BV. All rights reserved.
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once

 
#include "BLI_function_ref.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_sys_types.h"
 
struct BVHTree;
struct DistProjectedAABBPrecalc;
 
struct BVHTree;
#define USE_KDOPBVH_WATERTIGHT
 
struct BVHTreeAxisRange {
  union {
    struct {
      float min, max;
    };
    /* alternate access */
    float range[2];
  };
};
 
struct BVHTreeOverlap {
  int indexA;
  int indexB;
};
 
struct BVHTreeNearest {
  int index;
  float co[3];
  float no[3];
  float dist_sq;
  int flags;
};
 
struct BVHTreeRay {
  float origin[3];
  float direction[3];
  float radius;
#ifdef USE_KDOPBVH_WATERTIGHT
  struct IsectRayPrecalc *isect_precalc;
#endif
};
 
struct BVHTreeRayHit {
  int index;
  float co[3];
  float no[3];
  float dist;
};
 
enum {
  BVH_OVERLAP_USE_THREADING = (1 << 0),
  BVH_OVERLAP_RETURN_PAIRS = (1 << 1),
  /* Use a specialized self-overlap traversal to only test and output every
   * pair once, rather than twice in different order as usual. */
  BVH_OVERLAP_SELF = (1 << 2),
};
enum {
  /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
  BVH_NEAREST_OPTIMAL_ORDER = (1 << 0),
};
enum {
  /* calculate IsectRayPrecalc data */
  BVH_RAYCAST_WATERTIGHT = (1 << 0),
};
#define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT)
#define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f)

using BVHTree_NearestPointCallback = void (*)(void *userdata,
                                              int index,
                                              const float co[3],
                                              BVHTreeNearest *nearest);

using BVHTree_RayCastCallback = void (*)(void *userdata,
                                         int index,
                                         const BVHTreeRay *ray,
                                         BVHTreeRayHit *hit);

using BVHTree_OverlapCallback = bool (*)(void *userdata, int index_a, int index_b, int thread);

using BVHTree_RangeQuery = void (*)(void *userdata, int index, const float co[3], float dist_sq);

using BVHTree_NearestProjectedCallback = void (*)(void *userdata,
                                                  int index,
                                                  const DistProjectedAABBPrecalc *precalc,
                                                  const float (*clip_plane)[4],
                                                  int clip_plane_len,
                                                  BVHTreeNearest *nearest);
 
void BLI_bvhtree_free(BVHTree *tree);
 
class BVHTreeDeleter {
 public:
  void operator()(BVHTree *tree)
  {
    BLI_bvhtree_free(tree);
  }
};

BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);

void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints);
void BLI_bvhtree_balance(BVHTree *tree);

bool BLI_bvhtree_update_node(
    BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints);
void BLI_bvhtree_update_tree(BVHTree *tree);

int BLI_bvhtree_overlap_thread_num(const BVHTree *tree);

BVHTreeOverlap *BLI_bvhtree_overlap_ex(const BVHTree *tree1,
                                       const BVHTree *tree2,
                                       uint *r_overlap_num,
                                       BVHTree_OverlapCallback callback,
                                       void *userdata,
                                       uint max_interactions,
                                       int flag);
BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1,
                                    const BVHTree *tree2,
                                    unsigned int *r_overlap_num,
                                    BVHTree_OverlapCallback callback,
                                    void *userdata);
BVHTreeOverlap *BLI_bvhtree_overlap_self(const BVHTree *tree,
                                         unsigned int *r_overlap_num,
                                         BVHTree_OverlapCallback callback,
                                         void *userdata);
 
int *BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num);

int BLI_bvhtree_get_len(const BVHTree *tree);
int BLI_bvhtree_get_tree_type(const BVHTree *tree);
float BLI_bvhtree_get_epsilon(const BVHTree *tree);
void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3]);

int BLI_bvhtree_find_nearest_ex(const BVHTree *tree,
                                const float co[3],
                                BVHTreeNearest *nearest,
                                BVHTree_NearestPointCallback callback,
                                void *userdata,
                                int flag);
int BLI_bvhtree_find_nearest(const BVHTree *tree,
                             const float co[3],
                             BVHTreeNearest *nearest,
                             BVHTree_NearestPointCallback callback,
                             void *userdata);

int BLI_bvhtree_find_nearest_first(const BVHTree *tree,
                                   const float co[3],
                                   float dist_sq,
                                   BVHTree_NearestPointCallback callback,
                                   void *userdata);
 
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree,
                            const float co[3],
                            const float dir[3],
                            float radius,
                            BVHTreeRayHit *hit,
                            BVHTree_RayCastCallback callback,
                            void *userdata,
                            int flag);
int BLI_bvhtree_ray_cast(const BVHTree *tree,
                         const float co[3],
                         const float dir[3],
                         float radius,
                         BVHTreeRayHit *hit,
                         BVHTree_RayCastCallback callback,
                         void *userdata);

void BLI_bvhtree_ray_cast_all_ex(const BVHTree *tree,
                                 const float co[3],
                                 const float dir[3],
                                 float radius,
                                 float hit_dist,
                                 BVHTree_RayCastCallback callback,
                                 void *userdata,
                                 int flag);
void BLI_bvhtree_ray_cast_all(const BVHTree *tree,
                              const float co[3],
                              const float dir[3],
                              float radius,
                              float hit_dist,
                              BVHTree_RayCastCallback callback,
                              void *userdata);
 
float BLI_bvhtree_bb_raycast(const float bv[6],
                             const float light_start[3],
                             const float light_end[3],
                             float pos[3]);

int BLI_bvhtree_range_query(const BVHTree *tree,
                            const float co[3],
                            float radius,
                            BVHTree_RangeQuery callback,
                            void *userdata);
 
int BLI_bvhtree_find_nearest_projected(const BVHTree *tree,
                                       float projmat[4][4],
                                       float winsize[2],
                                       float mval[2],
                                       float (*clip_planes)[4],
                                       int clip_plane_len,
                                       BVHTreeNearest *nearest,
                                       BVHTree_NearestProjectedCallback callback,
                                       void *userdata);

extern const float bvhtree_kdop_axes[13][3];
 
namespace blender {
 
using BVHTree_RayCastCallback_CPP =
    FunctionRef<void(int index, const BVHTreeRay &ray, BVHTreeRayHit &hit)>;
 
inline void BLI_bvhtree_ray_cast_all_cpp(const BVHTree &tree,
                                         const float3 co,
                                         const float3 dir,
                                         float radius,
                                         float hit_dist,
                                         BVHTree_RayCastCallback_CPP fn)
{
  BLI_bvhtree_ray_cast_all(
      &tree,
      co,
      dir,
      radius,
      hit_dist,
      [](void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) {
        BVHTree_RayCastCallback_CPP fn = *static_cast<BVHTree_RayCastCallback_CPP *>(userdata);
        fn(index, *ray, *hit);
      },
      &fn);
}
 
using BVHTree_RangeQuery_CPP = FunctionRef<void(int index, const float3 &co, float dist_sq)>;
 
inline void BLI_bvhtree_range_query_cpp(const BVHTree &tree,
                                        const float3 co,
                                        float radius,
                                        BVHTree_RangeQuery_CPP fn)
{
  BLI_bvhtree_range_query(
      &tree,
      co,
      radius,
      [](void *userdata, const int index, const float co[3], const float dist_sq) {
        BVHTree_RangeQuery_CPP fn = *static_cast<BVHTree_RangeQuery_CPP *>(userdata);
        fn(index, co, dist_sq);
      },
      &fn);
}
 
}  // namespace blender