Blender V5.3
mathutils_kdtree.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <Python.h>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_kdtree.hh"
17#include "BLI_utildefines.hh"
18
21
22#include "mathutils.hh"
23#include "mathutils_kdtree.hh" /* own include */
24
25#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
26
27namespace blender {
28
29struct PyKDTree {
30 PyObject_HEAD
31 /* Used for 2D/3D KDTrees. */
32 void *obj;
35 uint count_balance; /* size when we last balanced */
37};
38
39/* -------------------------------------------------------------------- */
42
46template<typename CoordT> static KDTree<CoordT> *pykdtree_tree_get(PyKDTree *self)
47{
48 /* Null when `__init__` never ran or raised an error, `dimensions` is unset in that case. */
49 BLI_assert(self->obj == nullptr || CoordT::type_length == self->dimensions);
50 return reinterpret_cast<KDTree<CoordT> *>(self->obj);
51}
52
53template<typename CoordT>
54static void kdtree_nearest_to_py_tuple(const KDTreeNearest<CoordT> *nearest, PyObject *py_retval)
55{
56 BLI_assert(nearest->index >= 0);
57 BLI_assert(PyTuple_GET_SIZE(py_retval) == 3);
58
59 PyTuple_SET_ITEMS(py_retval,
60 Vector_CreatePyObject(nearest->co, CoordT::type_length, nullptr),
61 PyLong_FromLong(nearest->index),
62 PyFloat_FromDouble(nearest->dist));
63}
64
65template<typename CoordT>
66static PyObject *kdtree_nearest_to_py(const KDTreeNearest<CoordT> *nearest)
67{
68 PyObject *py_retval = PyTuple_New(3);
69
70 kdtree_nearest_to_py_tuple<CoordT>(nearest, py_retval);
71
72 return py_retval;
73}
74
75template<typename CoordT>
77{
78 PyObject *py_retval = PyTuple_New(3);
79
80 if (nearest->index != -1) {
81 kdtree_nearest_to_py_tuple<CoordT>(nearest, py_retval);
82 }
83 else {
84 PyC_Tuple_Fill(py_retval, Py_None);
85 }
86
87 return py_retval;
88}
89
91
92/* -------------------------------------------------------------------- */
95
96/* annoying since arg parsing won't check overflow */
97#define UINT_IS_NEG(n) ((n) > INT_MAX)
98
99static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs)
100{
101 uint maxsize;
102 int dimensions = 3;
103 const char *keywords[] = {
104 "size",
105 "dimensions",
106 nullptr,
107 };
108
109 if (!PyArg_ParseTupleAndKeywords(args,
110 kwargs,
111 "I" /* `size` */
112 "|$" /* Optional, keyword only arguments. */
113 "i" /* `dimensions` */
114 ":KDTree",
115 const_cast<char **>(keywords),
116 &maxsize,
117 &dimensions))
118 {
119 return -1;
120 }
121
122 if (UINT_IS_NEG(maxsize)) {
123 PyErr_SetString(PyExc_ValueError, "negative 'size' given");
124 return -1;
125 }
126
127 if (dimensions == 2) {
128 self->obj = kdtree_new<float2>(maxsize);
129 }
130 else if (dimensions == 3) {
131 self->obj = kdtree_new<float3>(maxsize);
132 }
133 else {
134 PyErr_SetString(PyExc_ValueError, "dimensions must be 2 or 3");
135 return -1;
136 }
137
138 self->maxsize = maxsize;
139 self->count = 0;
140 /* Initialize `uint-max` to avoid crashes on unbalanced trees. */
141 self->count_balance = uint(-1);
142 self->dimensions = dimensions;
143
144 return 0;
145}
146
148{
149 if (self->dimensions == 2) {
151 }
152 else {
154 }
155
156 Py_TYPE(self)->tp_free(reinterpret_cast<PyObject *>(self));
157}
158
160
161/* -------------------------------------------------------------------- */
164
166 /* Wrap. */
167 py_kdtree_insert_doc,
168 ".. method:: insert(co, index)\n"
169 "\n"
170 " Insert a point into the KDTree.\n"
171 "\n"
172 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
173 " :type co: Sequence[float]\n"
174 " :param index: The index of the point (must be non-negative).\n"
175 " :type index: int\n");
176static PyObject *py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwargs)
177{
178 PyObject *py_co;
179 float co[3];
180 int index;
181 const char *keywords[] = {"co", "index", nullptr};
182
183 if (!PyArg_ParseTupleAndKeywords(args,
184 kwargs,
185 "O" /* `co` */
186 "i" /* `index` */
187 ":insert",
188 const_cast<char **>(keywords),
189 &py_co,
190 &index))
191 {
192 return nullptr;
193 }
194
196 co, self->dimensions, self->dimensions, py_co, "insert: invalid 'co' arg") == -1)
197 {
198 return nullptr;
199 }
200
201 if (index < 0) {
202 PyErr_SetString(PyExc_ValueError, "negative index given");
203 return nullptr;
204 }
205
206 if (self->count >= self->maxsize) {
207 PyErr_SetString(PyExc_RuntimeError, "Trying to insert more items than KDTree has room for");
208 return nullptr;
209 }
210
211 if (self->dimensions == 2) {
213 }
214 else {
216 }
217 self->count++;
218
219 Py_RETURN_NONE;
220}
221
223
224/* -------------------------------------------------------------------- */
227
229 /* Wrap. */
230 py_kdtree_balance_doc,
231 ".. method:: balance()\n"
232 "\n"
233 " Balance the tree.\n"
234 "\n"
235 " .. note::\n"
236 "\n"
237 " This builds the entire tree, avoid calling after each insertion.\n");
238static PyObject *py_kdtree_balance(PyKDTree *self)
239{
240 if (self->dimensions == 2) {
242 }
243 else {
245 }
246
247 self->count_balance = self->count;
248 Py_RETURN_NONE;
249}
250
252
253/* -------------------------------------------------------------------- */
256
258 PyObject *py_filter;
260};
261
262static int py_find_nearest_cb(void *user_data, int index)
263{
264 PyKDTree_NearestData *data = static_cast<PyKDTree_NearestData *>(user_data);
265
266 PyObject *py_args = PyTuple_New(1);
267 PyTuple_SET_ITEM(py_args, 0, PyLong_FromLong(index));
268 PyObject *result = PyObject_CallObject(data->py_filter, py_args);
269 Py_DECREF(py_args);
270
271 if (result) {
272 bool use_node;
273 const int ok = PyC_ParseBool(result, &use_node);
274 Py_DECREF(result);
275 if (ok) {
276 return int(use_node);
277 }
278 }
279
280 data->is_error = true;
281 return -1;
282}
283
284template<typename CoordT>
285static PyObject *py_kdtree_find_impl(PyKDTree *self, const float *co, PyObject *py_filter)
286{
288 KDTreeNearest<CoordT> nearest;
289 nearest.index = -1;
290
291 if (py_filter == Py_None) {
292 kdtree_find_nearest<CoordT>(tree, co, &nearest);
293 }
294 else {
295 PyKDTree_NearestData data{py_filter, false};
296
298 tree, co, &nearest, [&](int index, const CoordT & /*co_nearest*/, float /*dist_sq*/) {
299 return py_find_nearest_cb(&data, index);
300 });
301
302 if (data.is_error) {
303 return nullptr;
304 }
305 }
306
308}
309
311 /* Wrap. */
312 py_kdtree_find_doc,
313 ".. method:: find(co, *, filter=None)\n"
314 "\n"
315 " Find nearest point to ``co``.\n"
316 "\n"
317 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
318 " :type co: Sequence[float]\n"
319 " :param filter: function which takes an index and returns True for indices to "
320 "include in the search.\n"
321 " :type filter: Callable[[int], bool] | None\n"
322 " :return: Returns (position, index, distance),\n"
323 " or (None, None, None) when no match is found.\n"
324 " :rtype: tuple[:class:`Vector`, int, float] | tuple[None, None, None]\n");
325static PyObject *py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs)
326{
327 PyObject *py_co, *py_filter = Py_None;
328 float co[3];
329 const char *keywords[] = {"co", "filter", nullptr};
330
331 if (!PyArg_ParseTupleAndKeywords(args,
332 kwargs,
333 "O" /* `co` */
334 "|$" /* Optional, keyword only arguments. */
335 "O" /* `filter` */
336 ":find",
337 const_cast<char **>(keywords),
338 &py_co,
339 &py_filter))
340 {
341 return nullptr;
342 }
343
345 co, self->dimensions, self->dimensions, py_co, "find: invalid 'co' arg") == -1)
346 {
347 return nullptr;
348 }
349
350 if (self->count != self->count_balance) {
351 PyErr_SetString(PyExc_RuntimeError, "KDTree must be balanced before calling find()");
352 return nullptr;
353 }
354
355 if (self->dimensions == 2) {
356 return py_kdtree_find_impl<float2>(self, co, py_filter);
357 }
358 return py_kdtree_find_impl<float3>(self, co, py_filter);
359}
360
362
363/* -------------------------------------------------------------------- */
366
367template<typename CoordT>
368static PyObject *py_kdtree_find_n_impl(PyKDTree *self, const float *co, uint n)
369{
371
372 const int found = kdtree_find_nearest_n<CoordT>(pykdtree_tree_get<CoordT>(self), co, nearest, n);
373
374 PyObject *py_list = PyList_New(found);
375
376 for (int i = 0; i < found; i++) {
377 PyList_SET_ITEM(py_list, i, kdtree_nearest_to_py<CoordT>(&nearest[i]));
378 }
379
380 MEM_delete(nearest);
381
382 return py_list;
383}
384
386 /* Wrap. */
387 py_kdtree_find_n_doc,
388 ".. method:: find_n(co, n)\n"
389 "\n"
390 " Find nearest ``n`` points to ``co``.\n"
391 "\n"
392 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
393 " :type co: Sequence[float]\n"
394 " :param n: Number of points to find.\n"
395 " :type n: int\n"
396 " :return: Returns a list of tuples (position, index, distance).\n"
397 " :rtype: list[tuple[:class:`Vector`, int, float]]\n");
398static PyObject *py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwargs)
399{
400 PyObject *py_co;
401 float co[3];
402 uint n;
403 const char *keywords[] = {"co", "n", nullptr};
404
405 if (!PyArg_ParseTupleAndKeywords(args,
406 kwargs,
407 "O" /* `co` */
408 "I" /* `n` */
409 ":find_n",
410 const_cast<char **>(keywords),
411 &py_co,
412 &n))
413 {
414 return nullptr;
415 }
416
418 co, self->dimensions, self->dimensions, py_co, "find_n: invalid 'co' arg") == -1)
419 {
420 return nullptr;
421 }
422
423 if (UINT_IS_NEG(n)) {
424 PyErr_SetString(PyExc_RuntimeError, "negative 'n' given");
425 return nullptr;
426 }
427
428 if (self->count != self->count_balance) {
429 PyErr_SetString(PyExc_RuntimeError, "KDTree must be balanced before calling find_n()");
430 return nullptr;
431 }
432
433 if (self->dimensions == 2) {
434 return py_kdtree_find_n_impl<float2>(self, co, n);
435 }
436 return py_kdtree_find_n_impl<float3>(self, co, n);
437}
438
440
441/* -------------------------------------------------------------------- */
444
445template<typename CoordT>
446static PyObject *py_kdtree_find_range_impl(PyKDTree *self, const float *co, float radius)
447{
448 KDTreeNearest<CoordT> *nearest = nullptr;
449 const int found = kdtree_range_search<CoordT>(
450 pykdtree_tree_get<CoordT>(self), co, &nearest, radius);
451
452 PyObject *py_list = PyList_New(found);
453
454 for (int i = 0; i < found; i++) {
455 PyList_SET_ITEM(py_list, i, kdtree_nearest_to_py<CoordT>(&nearest[i]));
456 }
457
458 if (nearest) {
459 MEM_delete(nearest);
460 }
461
462 return py_list;
463}
464
466 /* Wrap. */
467 py_kdtree_find_range_doc,
468 ".. method:: find_range(co, radius)\n"
469 "\n"
470 " Find all points within ``radius`` of ``co``.\n"
471 "\n"
472 " :param co: Point position. Can be 2D or 3D, based on the KDTree dimensions.\n"
473 " :type co: Sequence[float]\n"
474 " :param radius: Maximum distance to search for points.\n"
475 " :type radius: float\n"
476 " :return: Returns a list of tuples (position, index, distance).\n"
477 " :rtype: list[tuple[:class:`Vector`, int, float]]\n");
478static PyObject *py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject *kwargs)
479{
480 PyObject *py_co;
481 float co[3];
482 float radius;
483
484 const char *keywords[] = {"co", "radius", nullptr};
485
486 if (!PyArg_ParseTupleAndKeywords(args,
487 kwargs,
488 "O" /* `co` */
489 "f" /* `radius` */
490 ":find_range",
491 const_cast<char **>(keywords),
492 &py_co,
493 &radius))
494 {
495 return nullptr;
496 }
497
499 co, self->dimensions, self->dimensions, py_co, "find_range: invalid 'co' arg") == -1)
500 {
501 return nullptr;
502 }
503
504 if (radius < 0.0f) {
505 PyErr_SetString(PyExc_RuntimeError, "negative radius given");
506 return nullptr;
507 }
508
509 if (self->count != self->count_balance) {
510 PyErr_SetString(PyExc_RuntimeError, "KDTree must be balanced before calling find_range()");
511 return nullptr;
512 }
513
514 if (self->dimensions == 2) {
515 return py_kdtree_find_range_impl<float2>(self, co, radius);
516 }
517 return py_kdtree_find_range_impl<float3>(self, co, radius);
518}
519
521
522/* -------------------------------------------------------------------- */
525
526/* `KDTree.dimensions`. */
528 /* Wrap. */
529 py_kdtree_dimensions_doc,
530 "KDTree dimensions.\n"
531 "\n"
532 ":type: int\n");
533static PyObject *py_kdtree_dimensions_get(PyKDTree *self, void * /*closure*/)
534{
535 return PyLong_FromLong(self->dimensions);
536}
537
539
540/* -------------------------------------------------------------------- */
543
544#ifdef __GNUC__
545# ifdef __clang__
546# pragma clang diagnostic push
547# pragma clang diagnostic ignored "-Wcast-function-type"
548# else
549# pragma GCC diagnostic push
550# pragma GCC diagnostic ignored "-Wcast-function-type"
551# endif
552#endif
553
554static PyGetSetDef PyKDTree_getseters[] = {
555 {"dimensions",
556 reinterpret_cast<getter>(py_kdtree_dimensions_get),
557 static_cast<setter>(nullptr),
558 py_kdtree_dimensions_doc,
559 nullptr},
560
561 {nullptr, nullptr, nullptr, nullptr, nullptr} /* Sentinel */
562};
563
564#ifdef __GNUC__
565# ifdef __clang__
566# pragma clang diagnostic pop
567# else
568# pragma GCC diagnostic pop
569# endif
570#endif
571
573
574#ifdef __GNUC__
575# ifdef __clang__
576# pragma clang diagnostic push
577# pragma clang diagnostic ignored "-Wcast-function-type"
578# else
579# pragma GCC diagnostic push
580# pragma GCC diagnostic ignored "-Wcast-function-type"
581# endif
582#endif
583
584static PyMethodDef PyKDTree_methods[] = {
585 {"insert",
586 reinterpret_cast<PyCFunction>(py_kdtree_insert),
587 METH_VARARGS | METH_KEYWORDS,
588 py_kdtree_insert_doc},
589 {"balance",
590 reinterpret_cast<PyCFunction>(py_kdtree_balance),
591 METH_NOARGS,
592 py_kdtree_balance_doc},
593 {"find",
594 reinterpret_cast<PyCFunction>(py_kdtree_find),
595 METH_VARARGS | METH_KEYWORDS,
596 py_kdtree_find_doc},
597 {"find_n",
598 reinterpret_cast<PyCFunction>(py_kdtree_find_n),
599 METH_VARARGS | METH_KEYWORDS,
600 py_kdtree_find_n_doc},
601 {"find_range",
602 reinterpret_cast<PyCFunction>(py_kdtree_find_range),
603 METH_VARARGS | METH_KEYWORDS,
604 py_kdtree_find_range_doc},
605 {nullptr, nullptr, 0, nullptr},
606};
607
608#ifdef __GNUC__
609# ifdef __clang__
610# pragma clang diagnostic pop
611# else
612# pragma GCC diagnostic pop
613# endif
614#endif
615
617 /* Wrap. */
618 py_KDtree_doc,
619 ".. class:: KDTree(size, *, dimensions=3)\n"
620 "\n"
621 " A KD-tree initialized to hold up to ``size`` items.\n"
622 "\n"
623 " :param size: Maximum number of items.\n"
624 " :type size: int\n"
625 " :param dimensions: The dimensions of the tree (2 or 3).\n"
626 " :type dimensions: int\n"
627 "\n"
628 " .. note::\n"
629 "\n"
630 " :meth:`KDTree.balance` must have been called before using any of the ``find`` "
631 "methods.\n");
632PyTypeObject PyKDTree_Type = {
633 /*ob_base*/ PyVarObject_HEAD_INIT(nullptr, 0)
634 /*tp_name*/ "KDTree",
635 /*tp_basicsize*/ sizeof(PyKDTree),
636 /*tp_itemsize*/ 0,
637 /*tp_dealloc*/ reinterpret_cast<destructor>(PyKDTree__tp_dealloc),
638 /*tp_vectorcall_offset*/ 0,
639 /*tp_getattr*/ nullptr,
640 /*tp_setattr*/ nullptr,
641 /*tp_as_async*/ nullptr,
642 /*tp_repr*/ nullptr,
643 /*tp_as_number*/ nullptr,
644 /*tp_as_sequence*/ nullptr,
645 /*tp_as_mapping*/ nullptr,
646 /*tp_hash*/ nullptr,
647 /*tp_call*/ nullptr,
648 /*tp_str*/ nullptr,
649 /*tp_getattro*/ nullptr,
650 /*tp_setattro*/ nullptr,
651 /*tp_as_buffer*/ nullptr,
652 /*tp_flags*/ Py_TPFLAGS_DEFAULT,
653 /*tp_doc*/ py_KDtree_doc,
654 /*tp_traverse*/ nullptr,
655 /*tp_clear*/ nullptr,
656 /*tp_richcompare*/ nullptr,
657 /*tp_weaklistoffset*/ 0,
658 /*tp_iter*/ nullptr,
659 /*tp_iternext*/ nullptr,
660 /*tp_methods*/ static_cast<PyMethodDef *>(PyKDTree_methods),
661 /*tp_members*/ nullptr,
662 /*tp_getset*/ PyKDTree_getseters,
663 /*tp_base*/ nullptr,
664 /*tp_dict*/ nullptr,
665 /*tp_descr_get*/ nullptr,
666 /*tp_descr_set*/ nullptr,
667 /*tp_dictoffset*/ 0,
668 /*tp_init*/ reinterpret_cast<initproc>(PyKDTree__tp_init),
669 /*tp_alloc*/ static_cast<allocfunc>(PyType_GenericAlloc),
670 /*tp_new*/ static_cast<newfunc>(PyType_GenericNew),
671 /*tp_free*/ static_cast<freefunc>(nullptr),
672 /*tp_is_gc*/ nullptr,
673 /*tp_bases*/ nullptr,
674 /*tp_mro*/ nullptr,
675 /*tp_cache*/ nullptr,
676 /*tp_subclasses*/ nullptr,
677 /*tp_weaklist*/ nullptr,
678 /*tp_del*/ static_cast<destructor>(nullptr),
679 /*tp_version_tag*/ 0,
680 /*tp_finalize*/ nullptr,
681 /*tp_vectorcall*/ nullptr,
682};
683
685 /* Wrap. */
686 py_kdtree_doc,
687 "Generic 2D/3D KD-tree to perform spatial searches.");
688static PyModuleDef kdtree_moduledef = {
689 /*m_base*/ PyModuleDef_HEAD_INIT,
690 /*m_name*/ "mathutils.kdtree",
691 /*m_doc*/ py_kdtree_doc,
692 /*m_size*/ 0,
693 /*m_methods*/ nullptr,
694 /*m_slots*/ nullptr,
695 /*m_traverse*/ nullptr,
696 /*m_clear*/ nullptr,
697 /*m_free*/ nullptr,
698};
699
701{
702 /* Register the 'KDTree' class */
703 if (PyType_Ready(&PyKDTree_Type)) {
704 return nullptr;
705 }
706
707 PyObject *m = PyModule_Create(&kdtree_moduledef);
708
709 if (m == nullptr) {
710 return nullptr;
711 }
712
713 PyModule_AddType(m, &PyKDTree_Type);
714
715 return m;
716}
717
718} // namespace blender
A KD-tree for nearest neighbor search.
Read Blender memory allocation and freeing.
#define UINT_IS_NEG(n)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void kdtree_balance(KDTree< CoordT > *tree)
static PyGetSetDef PyKDTree_getseters[]
int PyC_ParseBool(PyObject *o, void *p)
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static PyModuleDef kdtree_moduledef
static PyObject * py_kdtree_find_range_impl(PyKDTree *self, const float *co, float radius)
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
PyDoc_STRVAR(bpy_bm_new_doc, ".. function:: new(*, use_operators=True)\n" "\n" " :param use_operators: Support calling operators in :mod:`bmesh.ops` (uses some " "extra memory per vert/edge/face).\n" " :type use_operators: bool\n" " :return: Return a new, empty BMesh.\n" " :rtype: :class:`bmesh.types.BMesh`\n")
static PyObject * kdtree_nearest_to_py(const KDTreeNearest< CoordT > *nearest)
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
static PyObject * py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwargs)
PyObject * Vector_CreatePyObject(const float *vec, const int vec_num, PyTypeObject *base_type)
static PyObject * kdtree_nearest_to_py_and_check(const KDTreeNearest< CoordT > *nearest)
BMesh const char void * data
int kdtree_find_nearest_n(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
int mathutils_array_parse(float *array, int array_num_min, int array_num_max, PyObject *value, const char *error_prefix)
Definition mathutils.cc:97
static int py_find_nearest_cb(void *user_data, int index)
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
static KDTree< CoordT > * pykdtree_tree_get(PyKDTree *self)
static PyObject * py_kdtree_dimensions_get(PyKDTree *self, void *)
static PyObject * py_kdtree_find_n_impl(PyKDTree *self, const float *co, uint n)
static void kdtree_nearest_to_py_tuple(const KDTreeNearest< CoordT > *nearest, PyObject *py_retval)
static PyObject * py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwargs)
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
void PyC_Tuple_Fill(PyObject *tuple, PyObject *value)
static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs)
static PyObject * py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs)
PyMODINIT_FUNC PyInit_mathutils_kdtree()
int kdtree_range_search(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > **r_nearest, typename KDTree< CoordT >::ValueType range)
static void PyKDTree__tp_dealloc(PyKDTree *self)
static PyObject * py_kdtree_balance(PyKDTree *self)
static PyObject * py_kdtree_find_impl(PyKDTree *self, const float *co, PyObject *py_filter)
PyTypeObject PyKDTree_Type
static PyMethodDef PyKDTree_methods[]
static PyObject * py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject *kwargs)
header-only utilities
#define PyTuple_SET_ITEMS(op_arg,...)
PyObject_HEAD void * obj