Blender V2.61 - r43446

BLI_kdtree.h

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: none of this file.
00022  *
00023  * Contributor(s): Janne Karhu
00024  *                 Brecht Van Lommel
00025  *
00026  * ***** END GPL LICENSE BLOCK *****
00027  */
00028  
00029 #ifndef BLI_KDTREE_H
00030 #define BLI_KDTREE_H
00031 
00039 struct KDTree;
00040 typedef struct KDTree KDTree;
00041 
00042 typedef struct KDTreeNearest {
00043     int index;
00044     float dist;
00045     float co[3];
00046 } KDTreeNearest;
00047 
00048 /* Creates or free a kdtree */
00049 KDTree* BLI_kdtree_new(int maxsize);
00050 void BLI_kdtree_free(KDTree *tree);
00051 
00052 /* Construction: first insert points, then call balance. Normal is optional. */
00053 void BLI_kdtree_insert(KDTree *tree, int index, float *co, float *nor);
00054 void BLI_kdtree_balance(KDTree *tree);
00055 
00056 /* Find nearest returns index, and -1 if no node is found.
00057  * Find n nearest returns number of points found, with results in nearest.
00058  * Normal is optional, but if given will limit results to points in normal direction from co. */
00059 int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *nearest);
00060 int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest);
00061 
00062 /* Range search returns number of points found, with results in nearest */
00063 /* Normal is optional, but if given will limit results to points in normal direction from co. */
00064 /* Remember to free nearest after use! */
00065 int BLI_kdtree_range_search(KDTree *tree, float range, float *co, float *nor, KDTreeNearest **nearest);
00066 #endif
00067