diff options
Diffstat (limited to 'source/blender/blenlib/BLI_kdopbvh.h')
| -rw-r--r-- | source/blender/blenlib/BLI_kdopbvh.h | 237 |
1 files changed, 136 insertions, 101 deletions
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index 0c40ce48529..a348694c4da 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -17,7 +17,6 @@ * All rights reserved. */ - #ifndef __BLI_KDOPBVH_H__ #define __BLI_KDOPBVH_H__ @@ -36,74 +35,80 @@ typedef struct BVHTree BVHTree; #define USE_KDOPBVH_WATERTIGHT typedef struct BVHTreeAxisRange { - union { - struct { - float min, max; - }; - /* alternate access */ - float range[2]; - }; + union { + struct { + float min, max; + }; + /* alternate access */ + float range[2]; + }; } BVHTreeAxisRange; typedef struct BVHTreeOverlap { - int indexA; - int indexB; + int indexA; + int indexB; } BVHTreeOverlap; typedef struct BVHTreeNearest { - /** The index of the nearest found - * (untouched if none is found within a dist radius from the given coordinates) */ - int index; - /** Nearest coordinates - * (untouched it none is found within a dist radius from the given coordinates). */ - float co[3]; - /** Normal at nearest coordinates - * (untouched it none is found within a dist radius from the given coordinates). */ - float no[3]; - /** squared distance to search around */ - float dist_sq; - int flags; + /** The index of the nearest found + * (untouched if none is found within a dist radius from the given coordinates) */ + int index; + /** Nearest coordinates + * (untouched it none is found within a dist radius from the given coordinates). */ + float co[3]; + /** Normal at nearest coordinates + * (untouched it none is found within a dist radius from the given coordinates). */ + float no[3]; + /** squared distance to search around */ + float dist_sq; + int flags; } BVHTreeNearest; typedef struct BVHTreeRay { - /** ray origin */ - float origin[3]; - /** ray direction */ - float direction[3]; - /** radius around ray */ - float radius; + /** ray origin */ + float origin[3]; + /** ray direction */ + float direction[3]; + /** radius around ray */ + float radius; #ifdef USE_KDOPBVH_WATERTIGHT - struct IsectRayPrecalc *isect_precalc; + struct IsectRayPrecalc *isect_precalc; #endif } BVHTreeRay; typedef struct BVHTreeRayHit { - /** Index of the tree node (untouched if no hit is found). */ - int index; - /** Coordinates of the hit point. */ - float co[3]; - /** Normal on hit point. */ - float no[3]; - /** Distance to the hit point. */ - float dist; + /** Index of the tree node (untouched if no hit is found). */ + int index; + /** Coordinates of the hit point. */ + float co[3]; + /** Normal on hit point. */ + float no[3]; + /** Distance to the hit point. */ + float dist; } BVHTreeRayHit; enum { - /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */ - BVH_NEAREST_OPTIMAL_ORDER = (1 << 0), + /* 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), + /* calculate IsectRayPrecalc data */ + BVH_RAYCAST_WATERTIGHT = (1 << 0), }; #define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT) #define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f) /* callback must update nearest in case it finds a nearest result */ -typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest); +typedef void (*BVHTree_NearestPointCallback)(void *userdata, + int index, + const float co[3], + BVHTreeNearest *nearest); /* callback must update hit in case it finds a nearest successful hit */ -typedef void (*BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit); +typedef void (*BVHTree_RayCastCallback)(void *userdata, + int index, + const BVHTreeRay *ray, + BVHTreeRayHit *hit); /* callback to check if 2 nodes overlap (use thread if intersection results need to be stored) */ typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread); @@ -112,21 +117,24 @@ typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b typedef void (*BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq); /* callback to find nearest projected */ -typedef void (*BVHTree_NearestProjectedCallback)( - void *userdata, int index, - const struct DistProjectedAABBPrecalc *precalc, - const float (*clip_plane)[4], const int clip_plane_len, - BVHTreeNearest *nearest); - +typedef void (*BVHTree_NearestProjectedCallback)(void *userdata, + int index, + const struct DistProjectedAABBPrecalc *precalc, + const float (*clip_plane)[4], + const int clip_plane_len, + BVHTreeNearest *nearest); /* callbacks to BLI_bvhtree_walk_dfs */ /* return true to traverse into this nodes children, else skip. */ typedef bool (*BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata); /* return true to keep walking, else early-exit the search. */ -typedef bool (*BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, int index, void *userdata); +typedef bool (*BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, + int index, + void *userdata); /* return true to search (min, max) else (max, min). */ -typedef bool (*BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, char axis, void *userdata); - +typedef bool (*BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, + char axis, + void *userdata); BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis); void BLI_bvhtree_free(BVHTree *tree); @@ -136,68 +144,95 @@ void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoin void BLI_bvhtree_balance(BVHTree *tree); /* update: first update points/nodes, then call update_tree to refit the bounding volumes */ -bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints); +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); /* collision/overlap: check two trees if they overlap, * alloc's *overlap with length of the int return value */ -BVHTreeOverlap *BLI_bvhtree_overlap( - const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot, - BVHTree_OverlapCallback callback, void *userdata); - -int BLI_bvhtree_get_len(const BVHTree *tree); -int BLI_bvhtree_get_tree_type(const BVHTree *tree); +BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1, + const BVHTree *tree2, + unsigned int *r_overlap_tot, + BVHTree_OverlapCallback callback, + void *userdata); + +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); /* find nearest node to the given coordinates * (if nearest is given it will only search nodes where * square distance is smaller than nearest->dist) */ -int BLI_bvhtree_find_nearest_ex( - BVHTree *tree, const float co[3], BVHTreeNearest *nearest, - BVHTree_NearestPointCallback callback, void *userdata, - int flag); -int BLI_bvhtree_find_nearest( - BVHTree *tree, const float co[3], BVHTreeNearest *nearest, - BVHTree_NearestPointCallback callback, void *userdata); - -int BLI_bvhtree_ray_cast_ex( - 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( - 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( - 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( - 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_find_nearest_ex(BVHTree *tree, + const float co[3], + BVHTreeNearest *nearest, + BVHTree_NearestPointCallback callback, + void *userdata, + int flag); +int BLI_bvhtree_find_nearest(BVHTree *tree, + const float co[3], + BVHTreeNearest *nearest, + BVHTree_NearestPointCallback callback, + void *userdata); + +int BLI_bvhtree_ray_cast_ex(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(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(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(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]); /* range query */ int BLI_bvhtree_range_query( - BVHTree *tree, const float co[3], float radius, - BVHTree_RangeQuery callback, void *userdata); - -int BLI_bvhtree_find_nearest_projected( - BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], - float clip_planes[6][4], int clip_num, - BVHTreeNearest *nearest, - BVHTree_NearestProjectedCallback callback, void *userdata); - -void BLI_bvhtree_walk_dfs( - BVHTree *tree, - BVHTree_WalkParentCallback walk_parent_cb, - BVHTree_WalkLeafCallback walk_leaf_cb, - BVHTree_WalkOrderCallback walk_order_cb, - void *userdata); - + BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata); + +int BLI_bvhtree_find_nearest_projected(BVHTree *tree, + float projmat[4][4], + float winsize[2], + float mval[2], + float clip_planes[6][4], + int clip_num, + BVHTreeNearest *nearest, + BVHTree_NearestProjectedCallback callback, + void *userdata); + +void BLI_bvhtree_walk_dfs(BVHTree *tree, + BVHTree_WalkParentCallback walk_parent_cb, + BVHTree_WalkLeafCallback walk_leaf_cb, + BVHTree_WalkOrderCallback walk_order_cb, + void *userdata); /* expose for bvh callbacks to use */ extern const float bvhtree_kdop_axes[13][3]; @@ -206,4 +241,4 @@ extern const float bvhtree_kdop_axes[13][3]; } #endif -#endif /* __BLI_KDOPBVH_H__ */ +#endif /* __BLI_KDOPBVH_H__ */ |