diff options
| author | Campbell Barton <ideasman42@gmail.com> | 2019-03-19 16:57:52 +0300 |
|---|---|---|
| committer | Campbell Barton <ideasman42@gmail.com> | 2019-03-19 17:07:07 +0300 |
| commit | d1b9b838be8a09735f52637fecdd2a8200eb9862 (patch) | |
| tree | 3fbab92692cea2bbcd3b6f898761d6b580401e68 /source/blender | |
| parent | 84fe4cdcb37c28469749d673006c8e6083bede7f (diff) | |
BLI_kdtree: add 2D kdtree support
Some users of the 3D versions were storing 2D data in it.
Using a 3D tree for 2D data adds a spatially redundant branch
every 3rd level, as well as some extra memory use, best avoid this.
Diffstat (limited to 'source/blender')
| -rw-r--r-- | source/blender/blenlib/BLI_kdtree.h | 11 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/kdtree_2d.c | 25 |
3 files changed, 37 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index af10a448423..18f3236a310 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -22,6 +22,17 @@ * \brief A kd-tree for nearest neighbor search. */ +/* 2D version */ +#define KD_DIMS 2 +#define KDTREE_PREFIX_ID BLI_kdtree_2d +#define KDTree KDTree_2d +#define KDTreeNearest KDTreeNearest_2d +#include "BLI_kdtree_impl.h" +#undef KD_DIMS +#undef KDTree +#undef KDTreeNearest +#undef KDTREE_PREFIX_ID + /* 3D version */ #define KD_DIMS 3 #define KDTREE_PREFIX_ID BLI_kdtree_3d diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index d740fa03e70..fef24c059e7 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -75,6 +75,7 @@ set(SRC intern/hash_mm2a.c intern/hash_mm3.c intern/jitter_2d.c + intern/kdtree_2d.c intern/kdtree_3d.c intern/kdtree_4d.c intern/lasso_2d.c diff --git a/source/blender/blenlib/intern/kdtree_2d.c b/source/blender/blenlib/intern/kdtree_2d.c new file mode 100644 index 00000000000..8ad55e2d964 --- /dev/null +++ b/source/blender/blenlib/intern/kdtree_2d.c @@ -0,0 +1,25 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + */ + +#define KD_DIMS 2 +#define KDTREE_PREFIX_ID BLI_kdtree_2d +#define KDTree KDTree_2d +#define KDTreeNearest KDTreeNearest_2d +# include "kdtree_impl.h" |