17 #include "../generic/py_capi_utils.h"
18 #include "../generic/python_utildefines.h"
43 PyLong_FromLong(nearest->index),
44 PyFloat_FromDouble(nearest->dist));
51 py_retval = PyTuple_New(3);
62 py_retval = PyTuple_New(3);
64 if (nearest->index != -1) {
78 #define UINT_IS_NEG(n) ((n) > INT_MAX)
83 const char *keywords[] = {
"size",
NULL};
85 if (!PyArg_ParseTupleAndKeywords(args, kwargs,
"I:KDTree", (
char **)keywords, &maxsize)) {
90 PyErr_SetString(PyExc_ValueError,
"negative 'size' given");
94 self->obj = BLI_kdtree_3d_new(maxsize);
95 self->maxsize = maxsize;
97 self->count_balance = 0;
104 BLI_kdtree_3d_free(
self->obj);
105 Py_TYPE(
self)->tp_free((PyObject *)
self);
109 ".. method:: insert(co, index)\n"
111 " Insert a point into the KDTree.\n"
113 " :arg co: Point 3d position.\n"
114 " :type co: float triplet\n"
115 " :arg index: The index of the point.\n"
116 " :type index: int\n");
122 const char *keywords[] = {
"co",
"index",
NULL};
124 if (!PyArg_ParseTupleAndKeywords(args, kwargs,
"Oi:insert", (
char **)keywords, &py_co, &index)) {
133 PyErr_SetString(PyExc_ValueError,
"negative index given");
138 PyErr_SetString(PyExc_RuntimeError,
"Trying to insert more items than KDTree has room for");
142 BLI_kdtree_3d_insert(
self->obj, index, co);
149 ".. method:: balance()\n"
151 " Balance the tree.\n"
155 " This builds the entire tree, avoid calling after each insertion.\n");
158 BLI_kdtree_3d_balance(
self->obj);
159 self->count_balance =
self->count;
174 PyObject *py_args = PyTuple_New(1);
175 PyTuple_SET_ITEM(py_args, 0, PyLong_FromLong(index));
176 PyObject *
result = PyObject_CallObject(
data->py_filter, py_args);
184 return (
int)use_node;
188 data->is_error =
true;
193 ".. method:: find(co, filter=None)\n"
195 " Find nearest point to ``co``.\n"
197 " :arg co: 3d coordinates.\n"
198 " :type co: float triplet\n"
199 " :arg filter: function which takes an index and returns True for indices to "
200 "include in the search.\n"
201 " :type filter: callable\n"
202 " :return: Returns (:class:`Vector`, index, distance).\n"
203 " :rtype: :class:`tuple`\n");
208 KDTreeNearest_3d nearest;
209 const char *keywords[] = {
"co",
"filter",
NULL};
211 if (!PyArg_ParseTupleAndKeywords(
212 args, kwargs,
"O|$O:find", (
char **)keywords, &py_co, &
py_filter)) {
220 if (
self->count !=
self->count_balance) {
221 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find()");
228 BLI_kdtree_3d_find_nearest(
self->obj, co, &nearest);
234 data.is_error =
false;
247 ".. method:: find_n(co, n)\n"
249 " Find nearest ``n`` points to ``co``.\n"
251 " :arg co: 3d coordinates.\n"
252 " :type co: float triplet\n"
253 " :arg n: Number of points to find.\n"
255 " :return: Returns a list of tuples (:class:`Vector`, index, distance).\n"
256 " :rtype: :class:`list`\n");
262 KDTreeNearest_3d *nearest;
265 const char *keywords[] = {
"co",
"n",
NULL};
267 if (!PyArg_ParseTupleAndKeywords(args, kwargs,
"OI:find_n", (
char **)keywords, &py_co, &n)) {
276 PyErr_SetString(PyExc_RuntimeError,
"negative 'n' given");
280 if (
self->count !=
self->count_balance) {
281 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find_n()");
285 nearest =
MEM_mallocN(
sizeof(KDTreeNearest_3d) * n, __func__);
287 found = BLI_kdtree_3d_find_nearest_n(
self->obj, co, nearest, n);
289 py_list = PyList_New(found);
291 for (i = 0; i < found; i++) {
301 ".. method:: find_range(co, radius)\n"
303 " Find all points within ``radius`` of ``co``.\n"
305 " :arg co: 3d coordinates.\n"
306 " :type co: float triplet\n"
307 " :arg radius: Distance to search for points.\n"
308 " :type radius: float\n"
309 " :return: Returns a list of tuples (:class:`Vector`, index, distance).\n"
310 " :rtype: :class:`list`\n");
316 KDTreeNearest_3d *nearest =
NULL;
320 const char *keywords[] = {
"co",
"radius",
NULL};
322 if (!PyArg_ParseTupleAndKeywords(
323 args, kwargs,
"Of:find_range", (
char **)keywords, &py_co, &radius)) {
332 PyErr_SetString(PyExc_RuntimeError,
"negative radius given");
336 if (
self->count !=
self->count_balance) {
337 PyErr_SetString(PyExc_RuntimeError,
"KDTree must be balanced before calling find_range()");
341 found = BLI_kdtree_3d_range_search(
self->obj, co, &nearest, radius);
343 py_list = PyList_New(found);
345 for (i = 0; i < found; i++) {
357 {
"insert", (PyCFunction)
py_kdtree_insert, METH_VARARGS | METH_KEYWORDS, py_kdtree_insert_doc},
359 {
"find", (PyCFunction)
py_kdtree_find, METH_VARARGS | METH_KEYWORDS, py_kdtree_find_doc},
360 {
"find_n", (PyCFunction)
py_kdtree_find_n, METH_VARARGS | METH_KEYWORDS, py_kdtree_find_n_doc},
363 METH_VARARGS | METH_KEYWORDS,
364 py_kdtree_find_range_doc},
369 "KdTree(size) -> new kd-tree initialized to hold ``size`` items.\n"
373 " :class:`KDTree.balance` must have been called before using any of the ``find`` "
376 PyVarObject_HEAD_INIT(
NULL, 0)
"KDTree",
412 (allocfunc)PyType_GenericAlloc,
413 (newfunc)PyType_GenericNew,
424 PyDoc_STRVAR(py_kdtree_doc,
"Generic 3-dimensional kd-tree to perform spatial searches.");
426 PyModuleDef_HEAD_INIT,
A KD-tree for nearest neighbor search.
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
Read Guarded memory(de)allocation.
void(* MEM_freeN)(void *vmemh)
void *(* MEM_mallocN)(size_t len, const char *str)
int mathutils_array_parse(float *array, int array_num_min, int array_num_max, PyObject *value, const char *error_prefix)
PyObject * Vector_CreatePyObject(const float *vec, const int vec_num, PyTypeObject *base_type)
static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs)
static void kdtree_nearest_to_py_tuple(const KDTreeNearest_3d *nearest, PyObject *py_retval)
static PyObject * py_kdtree_balance(PyKDTree *self)
PyTypeObject PyKDTree_Type
PyMODINIT_FUNC PyInit_mathutils_kdtree(void)
static PyObject * py_kdtree_find_range(PyKDTree *self, PyObject *args, PyObject *kwargs)
static PyObject * kdtree_nearest_to_py_and_check(const KDTreeNearest_3d *nearest)
static struct PyModuleDef kdtree_moduledef
static void PyKDTree__tp_dealloc(PyKDTree *self)
static PyMethodDef PyKDTree_methods[]
static int py_find_nearest_cb(void *user_data, int index, const float co[3], float dist_sq)
static PyObject * py_kdtree_find_n(PyKDTree *self, PyObject *args, PyObject *kwargs)
static PyObject * py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs)
PyDoc_STRVAR(py_kdtree_insert_doc, ".. method:: insert(co, index)\n" "\n" " Insert a point into the KDTree.\n" "\n" " :arg co: Point 3d position.\n" " :type co: float triplet\n" " :arg index: The index of the point.\n" " :type index: int\n")
static PyObject * kdtree_nearest_to_py(const KDTreeNearest_3d *nearest)
static PyObject * py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwargs)
int PyC_ParseBool(PyObject *o, void *p)
void PyC_Tuple_Fill(PyObject *tuple, PyObject *value)
#define PyTuple_SET_ITEMS(op_arg,...)
PyObject_HEAD KDTree_3d * obj