Merge branch 'blender2.7'
[blender.git] / source / blender / blenlib / BLI_kdtree.h
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
17 #ifndef __BLI_KDTREE_H__
18 #define __BLI_KDTREE_H__
19
20 /** \file
21  * \ingroup bli
22  * \brief A kd-tree for nearest neighbor search.
23  */
24
25 #include "BLI_compiler_attrs.h"
26
27 struct KDTree;
28 typedef struct KDTree KDTree;
29
30 typedef struct KDTreeNearest {
31         int index;
32         float dist;
33         float co[3];
34 } KDTreeNearest;
35
36 KDTree *BLI_kdtree_new(unsigned int maxsize);
37 void BLI_kdtree_free(KDTree *tree);
38 void BLI_kdtree_balance(KDTree *tree) ATTR_NONNULL(1);
39
40 void BLI_kdtree_insert(
41         KDTree *tree, int index,
42         const float co[3]) ATTR_NONNULL(1, 3);
43 int BLI_kdtree_find_nearest(
44         const KDTree *tree, const float co[3],
45         KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2);
46
47 #define BLI_kdtree_find_nearest_n(tree, co, r_nearest, n) \
48         BLI_kdtree_find_nearest_n__normal(tree, co, NULL, r_nearest, n)
49 #define BLI_kdtree_range_search(tree, co, r_nearest, range) \
50         BLI_kdtree_range_search__normal(tree, co, NULL, r_nearest, range)
51
52 int BLI_kdtree_find_nearest_cb(
53         const KDTree *tree, const float co[3],
54         int (*filter_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data,
55         KDTreeNearest *r_nearest);
56 void BLI_kdtree_range_search_cb(
57         const KDTree *tree, const float co[3], float range,
58         bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data);
59
60 int BLI_kdtree_calc_duplicates_fast(
61         const KDTree *tree, const float range, bool use_index_order,
62         int *doubles);
63
64 /* Normal use is deprecated */
65 /* remove __normal functions when last users drop */
66 int BLI_kdtree_find_nearest_n__normal(
67         const KDTree *tree, const float co[3], const float nor[3],
68         KDTreeNearest *r_nearest,
69         unsigned int n) ATTR_NONNULL(1, 2, 4);
70 int BLI_kdtree_range_search__normal(
71         const KDTree *tree, const float co[3], const float nor[3],
72         KDTreeNearest **r_nearest,
73         float range) ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT;
74
75 #endif  /* __BLI_KDTREE_H__ */