1 /* 2 * This program is free software; you can redistribute it and/or 3 * modify it under the terms of the GNU General Public License 4 * as published by the Free Software Foundation; either version 2 5 * of the License, or (at your option) any later version. 6 * 7 * This program is distributed in the hope that it will be useful, 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * GNU General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program; if not, write to the Free Software Foundation, 14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 15 * 16 * The Original Code is Copyright (C) 2006 by NaN Holding BV. 17 * All rights reserved. 18 */ 19 20 #pragma once 21 22 /** \file 23 * \ingroup bli 24 */ 25 26 #include "BLI_sys_types.h" 27 28 #ifdef __cplusplus 29 extern "C" { 30 #endif 31 32 struct BVHTree; 33 struct DistProjectedAABBPrecalc; 34 35 typedef struct BVHTree BVHTree; 36 #define USE_KDOPBVH_WATERTIGHT 37 38 typedef struct BVHTreeAxisRange { 39 union { 40 struct { 41 float min, max; 42 }; 43 /* alternate access */ 44 float range[2]; 45 }; 46 } BVHTreeAxisRange; 47 48 typedef struct BVHTreeOverlap { 49 int indexA; 50 int indexB; 51 } BVHTreeOverlap; 52 53 typedef struct BVHTreeNearest { 54 /** The index of the nearest found 55 * (untouched if none is found within a dist radius from the given coordinates) */ 56 int index; 57 /** Nearest coordinates 58 * (untouched it none is found within a dist radius from the given coordinates). */ 59 float co[3]; 60 /** Normal at nearest coordinates 61 * (untouched it none is found within a dist radius from the given coordinates). */ 62 float no[3]; 63 /** squared distance to search around */ 64 float dist_sq; 65 int flags; 66 } BVHTreeNearest; 67 68 typedef struct BVHTreeRay { 69 /** ray origin */ 70 float origin[3]; 71 /** ray direction */ 72 float direction[3]; 73 /** radius around ray */ 74 float radius; 75 #ifdef USE_KDOPBVH_WATERTIGHT 76 struct IsectRayPrecalc *isect_precalc; 77 #endif 78 } BVHTreeRay; 79 80 typedef struct BVHTreeRayHit { 81 /** Index of the tree node (untouched if no hit is found). */ 82 int index; 83 /** Coordinates of the hit point. */ 84 float co[3]; 85 /** Normal on hit point. */ 86 float no[3]; 87 /** Distance to the hit point. */ 88 float dist; 89 } BVHTreeRayHit; 90 91 enum { 92 /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */ 93 BVH_OVERLAP_USE_THREADING = (1 << 0), 94 BVH_OVERLAP_RETURN_PAIRS = (1 << 1), 95 }; 96 enum { 97 /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */ 98 BVH_NEAREST_OPTIMAL_ORDER = (1 << 0), 99 }; 100 enum { 101 /* calculate IsectRayPrecalc data */ 102 BVH_RAYCAST_WATERTIGHT = (1 << 0), 103 }; 104 #define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT) 105 #define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f) 106 107 /* callback must update nearest in case it finds a nearest result */ 108 typedef void (*BVHTree_NearestPointCallback)(void *userdata, 109 int index, 110 const float co[3], 111 BVHTreeNearest *nearest); 112 113 /* callback must update hit in case it finds a nearest successful hit */ 114 typedef void (*BVHTree_RayCastCallback)(void *userdata, 115 int index, 116 const BVHTreeRay *ray, 117 BVHTreeRayHit *hit); 118 119 /* callback to check if 2 nodes overlap (use thread if intersection results need to be stored) */ 120 typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread); 121 122 /* callback to range search query */ 123 typedef void (*BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq); 124 125 /* callback to find nearest projected */ 126 typedef void (*BVHTree_NearestProjectedCallback)(void *userdata, 127 int index, 128 const struct DistProjectedAABBPrecalc *precalc, 129 const float (*clip_plane)[4], 130 const int clip_plane_len, 131 BVHTreeNearest *nearest); 132 133 /* callbacks to BLI_bvhtree_walk_dfs */ 134 /* return true to traverse into this nodes children, else skip. */ 135 typedef bool (*BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata); 136 /* return true to keep walking, else early-exit the search. */ 137 typedef bool (*BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, 138 int index, 139 void *userdata); 140 /* return true to search (min, max) else (max, min). */ 141 typedef bool (*BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, 142 char axis, 143 void *userdata); 144 145 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis); 146 void BLI_bvhtree_free(BVHTree *tree); 147 148 /* construct: first insert points, then call balance */ 149 void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints); 150 void BLI_bvhtree_balance(BVHTree *tree); 151 152 /* update: first update points/nodes, then call update_tree to refit the bounding volumes */ 153 bool BLI_bvhtree_update_node( 154 BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints); 155 void BLI_bvhtree_update_tree(BVHTree *tree); 156 157 int BLI_bvhtree_overlap_thread_num(const BVHTree *tree); 158 159 /* collision/overlap: check two trees if they overlap, 160 * alloc's *overlap with length of the int return value */ 161 BVHTreeOverlap *BLI_bvhtree_overlap_ex( 162 const BVHTree *tree1, 163 const BVHTree *tree2, 164 uint *r_overlap_tot, 165 /* optional callback to test the overlap before adding (must be thread-safe!) */ 166 BVHTree_OverlapCallback callback, 167 void *userdata, 168 const uint max_interactions, 169 const int flag); 170 BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1, 171 const BVHTree *tree2, 172 unsigned int *r_overlap_tot, 173 BVHTree_OverlapCallback callback, 174 void *userdata); 175 176 int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_tot); 177 178 int BLI_bvhtree_get_len(const BVHTree *tree); 179 int BLI_bvhtree_get_tree_type(const BVHTree *tree); 180 float BLI_bvhtree_get_epsilon(const BVHTree *tree); 181 182 /* find nearest node to the given coordinates 183 * (if nearest is given it will only search nodes where 184 * square distance is smaller than nearest->dist) */ 185 int BLI_bvhtree_find_nearest_ex(BVHTree *tree, 186 const float co[3], 187 BVHTreeNearest *nearest, 188 BVHTree_NearestPointCallback callback, 189 void *userdata, 190 int flag); 191 int BLI_bvhtree_find_nearest(BVHTree *tree, 192 const float co[3], 193 BVHTreeNearest *nearest, 194 BVHTree_NearestPointCallback callback, 195 void *userdata); 196 197 int BLI_bvhtree_find_nearest_first(BVHTree *tree, 198 const float co[3], 199 const float dist_sq, 200 BVHTree_NearestPointCallback callback, 201 void *userdata); 202 203 int BLI_bvhtree_ray_cast_ex(BVHTree *tree, 204 const float co[3], 205 const float dir[3], 206 float radius, 207 BVHTreeRayHit *hit, 208 BVHTree_RayCastCallback callback, 209 void *userdata, 210 int flag); 211 int BLI_bvhtree_ray_cast(BVHTree *tree, 212 const float co[3], 213 const float dir[3], 214 float radius, 215 BVHTreeRayHit *hit, 216 BVHTree_RayCastCallback callback, 217 void *userdata); 218 219 void BLI_bvhtree_ray_cast_all_ex(BVHTree *tree, 220 const float co[3], 221 const float dir[3], 222 float radius, 223 float hit_dist, 224 BVHTree_RayCastCallback callback, 225 void *userdata, 226 int flag); 227 void BLI_bvhtree_ray_cast_all(BVHTree *tree, 228 const float co[3], 229 const float dir[3], 230 float radius, 231 float hit_dist, 232 BVHTree_RayCastCallback callback, 233 void *userdata); 234 235 float BLI_bvhtree_bb_raycast(const float bv[6], 236 const float light_start[3], 237 const float light_end[3], 238 float pos[3]); 239 240 /* range query */ 241 int BLI_bvhtree_range_query( 242 BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata); 243 244 int BLI_bvhtree_find_nearest_projected(BVHTree *tree, 245 float projmat[4][4], 246 float winsize[2], 247 float mval[2], 248 float clip_planes[6][4], 249 int clip_plane_len, 250 BVHTreeNearest *nearest, 251 BVHTree_NearestProjectedCallback callback, 252 void *userdata); 253 254 void BLI_bvhtree_walk_dfs(BVHTree *tree, 255 BVHTree_WalkParentCallback walk_parent_cb, 256 BVHTree_WalkLeafCallback walk_leaf_cb, 257 BVHTree_WalkOrderCallback walk_order_cb, 258 void *userdata); 259 260 /* expose for bvh callbacks to use */ 261 extern const float bvhtree_kdop_axes[13][3]; 262 263 #ifdef __cplusplus 264 } 265 #endif 266