Merge with 2.5 -r 21619:21756.
[blender.git] / source / blender / blenlib / BLI_kdtree.h
1 /**
2  * A kd-tree for nearest neighbour search.
3  * 
4  * $Id$
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: none of this file.
26  *
27  * Contributor(s): Janne Karhu
28  *                 Brecht Van Lommel
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  */
32  
33 #ifndef BLI_KDTREE_H
34 #define BLI_KDTREE_H
35
36 struct KDTree;
37 typedef struct KDTree KDTree;
38
39 typedef struct KDTreeNearest {
40         int index;
41         float dist;
42         float co[3];
43 } KDTreeNearest;
44
45 /* Creates or free a kdtree */
46 KDTree* BLI_kdtree_new(int maxsize);
47 void BLI_kdtree_free(KDTree *tree);
48
49 /* Construction: first insert points, then call balance. Normal is optional. */
50 void BLI_kdtree_insert(KDTree *tree, int index, float *co, float *nor);
51 void BLI_kdtree_balance(KDTree *tree);
52
53 /* Find nearest returns index, and -1 if no node is found.
54  * Find n nearest returns number of points found, with results in nearest.
55 /* Normal is optional, but if given will limit results to points in normal direction from co. */
56 int     BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *nearest);
57 int     BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest);
58
59 /* Range search returns number of points found, with results in nearest */
60 /* Normal is optional, but if given will limit results to points in normal direction from co. */
61 /* Remember to free nearest after use! */
62 int BLI_kdtree_range_search(KDTree *tree, float range, float *co, float *nor, KDTreeNearest **nearest);
63 #endif
64