Changeset View
Changeset View
Standalone View
Standalone View
source/blender/blenlib/BLI_kdtree_impl.h
- This file was copied from source/blender/blenlib/BLI_kdtree.h.
| /* | /* | ||||
| * This program is free software; you can redistribute it and/or | * This program is free software; you can redistribute it and/or | ||||
| * modify it under the terms of the GNU General Public License | * modify it under the terms of the GNU General Public License | ||||
| * as published by the Free Software Foundation; either version 2 | * as published by the Free Software Foundation; either version 2 | ||||
| * of the License, or (at your option) any later version. | * of the License, or (at your option) any later version. | ||||
| * | * | ||||
| * This program is distributed in the hope that it will be useful, | * This program is distributed in the hope that it will be useful, | ||||
| * but WITHOUT ANY WARRANTY; without even the implied warranty of | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||||
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||||
| * GNU General Public License for more details. | * GNU General Public License for more details. | ||||
| * | * | ||||
| * You should have received a copy of the GNU General Public License | * You should have received a copy of the GNU General Public License | ||||
| * along with this program; if not, write to the Free Software Foundation, | * along with this program; if not, write to the Free Software Foundation, | ||||
| * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. | * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. | ||||
| */ | */ | ||||
| #ifndef __BLI_KDTREE_H__ | |||||
| #define __BLI_KDTREE_H__ | |||||
| /** \file | /** \file | ||||
| * \ingroup bli | * \ingroup bli | ||||
| * \brief A kd-tree for nearest neighbor search. | * \brief A kd-tree for nearest neighbor search. | ||||
| */ | */ | ||||
| #include "BLI_compiler_attrs.h" | #include "BLI_compiler_attrs.h" | ||||
| #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2 | |||||
| #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) | |||||
| #define BLI_KDTREE_PREFIX(id) _CONCAT(KDTREE_PREFIX_ID, _##id) | |||||
| #define BLI_KDTREE_SUFFIX(id) _CONCAT(KDTREE_SUFFIX_ID, id) | |||||
| struct KDTree; | struct KDTree; | ||||
| typedef struct KDTree KDTree; | typedef struct KDTree KDTree; | ||||
| typedef struct KDTreeNearest { | typedef struct KDTreeNearest { | ||||
| int index; | int index; | ||||
| float dist; | float dist; | ||||
| float co[3]; | float co[3]; | ||||
| } KDTreeNearest; | } KDTreeNearest; | ||||
| KDTree *BLI_kdtree_new(unsigned int maxsize); | KDTree *BLI_KDTREE_PREFIX(new)(unsigned int maxsize); | ||||
| void BLI_kdtree_free(KDTree *tree); | void BLI_KDTREE_PREFIX(free)(KDTree *tree); | ||||
| void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1); | void BLI_KDTREE_PREFIX(balance)(KDTree *tree) ATTR_NONNULL(1); | ||||
| void BLI_kdtree_insert( | void BLI_KDTREE_PREFIX(insert)( | ||||
| KDTree *tree, int index, | KDTree *tree, int index, | ||||
| const float co[3]) ATTR_NONNULL(1, 3); | const float co[3]) ATTR_NONNULL(1, 3); | ||||
| int BLI_kdtree_find_nearest( | int BLI_KDTREE_PREFIX(find_nearest)( | ||||
| const KDTree *tree, const float co[3], | const KDTree *tree, const float co[3], | ||||
| KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); | KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2); | ||||
| #define BLI_kdtree_find_nearest_n(tree, co, r_nearest, nearest_len_capacity) \ | int BLI_KDTREE_PREFIX(find_nearest_n)( | ||||
| BLI_kdtree_find_nearest_n_with_len_squared_cb(tree, co, r_nearest, nearest_len_capacity, NULL, NULL) | const KDTree *tree, const float co[3], | ||||
| #define BLI_kdtree_range_search(tree, co, r_nearest, range) \ | KDTreeNearest *r_nearest, | ||||
| BLI_kdtree_range_search_with_len_squared_cb(tree, co, r_nearest, range, NULL, NULL) | const uint nearest_len_capacity) ATTR_NONNULL(1, 2, 3); | ||||
| int BLI_KDTREE_PREFIX(range_search)( | |||||
| const KDTree *tree, const float co[3], | |||||
| KDTreeNearest **r_nearest, | |||||
| const float range) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; | |||||
| int BLI_kdtree_find_nearest_cb( | int BLI_KDTREE_PREFIX(find_nearest_cb)( | ||||
| const KDTree *tree, const float co[3], | const KDTree *tree, const float co[3], | ||||
| int (*filter_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data, | int (*filter_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data, | ||||
| KDTreeNearest *r_nearest); | KDTreeNearest *r_nearest); | ||||
| void BLI_kdtree_range_search_cb( | void BLI_KDTREE_PREFIX(range_search_cb)( | ||||
| const KDTree *tree, const float co[3], float range, | const KDTree *tree, const float co[3], float range, | ||||
| bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data); | bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data); | ||||
| int BLI_kdtree_calc_duplicates_fast( | int BLI_KDTREE_PREFIX(calc_duplicates_fast)( | ||||
| const KDTree *tree, const float range, bool use_index_order, | const KDTree *tree, const float range, bool use_index_order, | ||||
| int *doubles); | int *doubles); | ||||
| /* Versions of find/range search that take a squared distance callback to support bias. */ | /* Versions of find/range search that take a squared distance callback to support bias. */ | ||||
| int BLI_kdtree_find_nearest_n_with_len_squared_cb( | int BLI_KDTREE_PREFIX(find_nearest_n_with_len_squared_cb)( | ||||
| const KDTree *tree, const float co[3], | const KDTree *tree, const float co[3], | ||||
| KDTreeNearest *r_nearest, | KDTreeNearest *r_nearest, | ||||
| const uint nearest_len_capacity, | const uint nearest_len_capacity, | ||||
| float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | ||||
| const void *user_data) ATTR_NONNULL(1, 2, 3); | const void *user_data) ATTR_NONNULL(1, 2, 3); | ||||
| int BLI_kdtree_range_search_with_len_squared_cb( | int BLI_KDTREE_PREFIX(range_search_with_len_squared_cb)( | ||||
| const KDTree *tree, const float co[3], | const KDTree *tree, const float co[3], | ||||
| KDTreeNearest **r_nearest, | KDTreeNearest **r_nearest, | ||||
| const float range, | const float range, | ||||
| float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | float (*len_sq_fn)(const float co_search[3], const float co_test[3], const void *user_data), | ||||
| const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; | const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT; | ||||
| #endif /* __BLI_KDTREE_H__ */ | |||||