ClangFormat: apply to source, most of intern
[blender.git] / source / blender / blenlib / BLI_kdtree_impl.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 /** \file
18  * \ingroup bli
19  * \brief A kd-tree for nearest neighbor search.
20  */
21
22 #include "BLI_compiler_attrs.h"
23
24 #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2
25 #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
26 #define BLI_kdtree_nd_(id) _CONCAT(KDTREE_PREFIX_ID, _##id)
27
28 struct KDTree;
29 typedef struct KDTree KDTree;
30
31 typedef struct KDTreeNearest {
32   int index;
33   float dist;
34   float co[KD_DIMS];
35 } KDTreeNearest;
36
37 KDTree *BLI_kdtree_nd_(new)(unsigned int maxsize);
38 void BLI_kdtree_nd_(free)(KDTree *tree);
39 void BLI_kdtree_nd_(balance)(KDTree *tree) ATTR_NONNULL(1);
40
41 void BLI_kdtree_nd_(insert)(KDTree *tree, int index, const float co[KD_DIMS]) ATTR_NONNULL(1, 3);
42 int BLI_kdtree_nd_(find_nearest)(const KDTree *tree,
43                                  const float co[KD_DIMS],
44                                  KDTreeNearest *r_nearest) ATTR_NONNULL(1, 2);
45
46 int BLI_kdtree_nd_(find_nearest_n)(const KDTree *tree,
47                                    const float co[KD_DIMS],
48                                    KDTreeNearest *r_nearest,
49                                    const uint nearest_len_capacity) ATTR_NONNULL(1, 2, 3);
50
51 int BLI_kdtree_nd_(range_search)(const KDTree *tree,
52                                  const float co[KD_DIMS],
53                                  KDTreeNearest **r_nearest,
54                                  const float range) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT;
55
56 int BLI_kdtree_nd_(find_nearest_cb)(
57     const KDTree *tree,
58     const float co[KD_DIMS],
59     int (*filter_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq),
60     void *user_data,
61     KDTreeNearest *r_nearest);
62 void BLI_kdtree_nd_(range_search_cb)(
63     const KDTree *tree,
64     const float co[KD_DIMS],
65     float range,
66     bool (*search_cb)(void *user_data, int index, const float co[KD_DIMS], float dist_sq),
67     void *user_data);
68
69 int BLI_kdtree_nd_(calc_duplicates_fast)(const KDTree *tree,
70                                          const float range,
71                                          bool use_index_order,
72                                          int *doubles);
73
74 int BLI_kdtree_nd_(deduplicate)(KDTree *tree);
75
76 /* Versions of find/range search that take a squared distance callback to support bias. */
77 int BLI_kdtree_nd_(find_nearest_n_with_len_squared_cb)(
78     const KDTree *tree,
79     const float co[KD_DIMS],
80     KDTreeNearest *r_nearest,
81     const uint nearest_len_capacity,
82     float (*len_sq_fn)(const float co_search[KD_DIMS],
83                        const float co_test[KD_DIMS],
84                        const void *user_data),
85     const void *user_data) ATTR_NONNULL(1, 2, 3);
86 int BLI_kdtree_nd_(range_search_with_len_squared_cb)(
87     const KDTree *tree,
88     const float co[KD_DIMS],
89     KDTreeNearest **r_nearest,
90     const float range,
91     float (*len_sq_fn)(const float co_search[KD_DIMS],
92                        const float co_test[KD_DIMS],
93                        const void *user_data),
94     const void *user_data) ATTR_NONNULL(1, 2) ATTR_WARN_UNUSED_RESULT;
95
96 #undef _CONCAT_AUX
97 #undef _CONCAT
98 #undef BLI_kdtree_nd_