[Bf-blender-cvs] [4848f90] master: Patch D133: Python wrapper for BLI_kdtree (adds mathutils.kdtree)
Campbell Barton
noreply at git.blender.org
Mon Jan 6 10:45:24 CET 2014
Commit: 4848f9029a7cf70324888f18ccfcdea3fa50392b
Author: Campbell Barton
Date: Mon Jan 6 20:32:34 2014 +1100
https://developer.blender.org/rB4848f9029a7cf70324888f18ccfcdea3fa50392b
Patch D133: Python wrapper for BLI_kdtree (adds mathutils.kdtree)
Originally by Dan Eicher, with my own fixes and adjustments (see patch page for details).
For details there are unit tests and api example usage.
doc/python_api/sphinx-in-tmp/menu_id.png
===================================================================
A doc/python_api/examples/mathutils.kdtree.py
M doc/python_api/sphinx_doc_gen.py
M source/blender/python/intern/bpy_interface.c
M source/blender/python/mathutils/CMakeLists.txt
M source/blender/python/mathutils/mathutils.c
M source/blender/python/mathutils/mathutils.h
A source/blender/python/mathutils/mathutils_kdtree.c
A source/blender/python/mathutils/mathutils_kdtree.h
M source/tests/bl_pyapi_mathutils.py
===================================================================
diff --git a/doc/python_api/examples/mathutils.kdtree.py b/doc/python_api/examples/mathutils.kdtree.py
new file mode 100644
index 0000000..d367582
--- /dev/null
+++ b/doc/python_api/examples/mathutils.kdtree.py
@@ -0,0 +1,37 @@
+import mathutils
+
+# create a kd-tree from a mesh
+from bpy import context
+obj = context.object
+
+# 3d cursor relative to the object data
+co_find = context.scene.cursor_location * obj.matrix_world.inverted()
+
+mesh = obj.data
+size = len(mesh.vertices)
+kd = mathutils.kdtree.KDTree(size)
+
+for i, v in enumerate(mesh.vertices):
+ kd.insert(v.co, i)
+
+kd.balance()
+
+
+# Find the closest point to the center
+co_find = (0.0, 0.0, 0.0)
+co, index, dist = kd.find(co_find)
+print("Close to center:", co, index, dist)
+
+
+# Find the closest 10 points to the 3d cursor
+print("Close 10 points")
+for (co, index, dist) in kd.find_n(co_find, 10):
+ print(" ", co, index, dist)
+
+
+# Find points within a radius of the 3d cursor
+print("Close points within 0.5 distance")
+co_find = context.scene.cursor_location
+for (co, index, dist) in kd.find_range(co_find, 0.5):
+ print(" ", co, index, dist)
+
diff --git a/doc/python_api/sphinx_doc_gen.py b/doc/python_api/sphinx_doc_gen.py
index a812863..4cea81d 100644
--- a/doc/python_api/sphinx_doc_gen.py
+++ b/doc/python_api/sphinx_doc_gen.py
@@ -271,6 +271,7 @@ else:
"gpu",
"mathutils",
"mathutils.geometry",
+ "mathutils.kdtree",
"mathutils.noise",
"freestyle",
]
@@ -1625,7 +1626,7 @@ def write_rst_contents(basepath):
standalone_modules = (
# mathutils
- "mathutils", "mathutils.geometry", "mathutils.noise",
+ "mathutils", "mathutils.geometry", "mathutils.kdtree", "mathutils.noise",
# misc
"freestyle", "bgl", "blf", "gpu", "aud", "bpy_extras",
# bmesh, submodules are in own page
@@ -1776,6 +1777,7 @@ def write_rst_importable_modules(basepath):
"bpy.props" : "Property Definitions",
"mathutils" : "Math Types & Utilities",
"mathutils.geometry" : "Geometry Utilities",
+ "mathutils.kdtree" : "KDTree Utilities",
"mathutils.noise" : "Noise Utilities",
"freestyle" : "Freestyle Data Types & Operators",
}
diff --git a/source/blender/python/intern/bpy_interface.c b/source/blender/python/intern/bpy_interface.c
index 68816b7..aafb5e3 100644
--- a/source/blender/python/intern/bpy_interface.c
+++ b/source/blender/python/intern/bpy_interface.c
@@ -213,6 +213,7 @@ static struct _inittab bpy_internal_modules[] = {
{(char *)"mathutils", PyInit_mathutils},
// {(char *)"mathutils.geometry", PyInit_mathutils_geometry},
// {(char *)"mathutils.noise", PyInit_mathutils_noise},
+// {(char *)"mathutils.kdtree", PyInit_mathutils_kdtree},
{(char *)"_bpy_path", BPyInit__bpy_path},
{(char *)"bgl", BPyInit_bgl},
{(char *)"blf", BPyInit_blf},
diff --git a/source/blender/python/mathutils/CMakeLists.txt b/source/blender/python/mathutils/CMakeLists.txt
index dae1c66..133b8d3 100644
--- a/source/blender/python/mathutils/CMakeLists.txt
+++ b/source/blender/python/mathutils/CMakeLists.txt
@@ -38,6 +38,7 @@ set(SRC
mathutils_Quaternion.c
mathutils_Vector.c
mathutils_geometry.c
+ mathutils_kdtree.c
mathutils_noise.c
mathutils.h
@@ -47,6 +48,7 @@ set(SRC
mathutils_Quaternion.h
mathutils_Vector.h
mathutils_geometry.h
+ mathutils_kdtree.h
mathutils_noise.h
)
diff --git a/source/blender/python/mathutils/mathutils.c b/source/blender/python/mathutils/mathutils.c
index 8f94fc8..dd3e5de 100644
--- a/source/blender/python/mathutils/mathutils.c
+++ b/source/blender/python/mathutils/mathutils.c
@@ -515,6 +515,11 @@ PyMODINIT_FUNC PyInit_mathutils(void)
PyModule_AddObject(mod, "noise", (submodule = PyInit_mathutils_noise()));
PyDict_SetItemString(sys_modules, PyModule_GetName(submodule), submodule);
Py_INCREF(submodule);
+
+ /* KDTree submodule */
+ PyModule_AddObject(mod, "kdtree", (submodule = PyInit_mathutils_kdtree()));
+ PyDict_SetItemString(sys_modules, PyModule_GetName(submodule), submodule);
+ Py_INCREF(submodule);
#endif
mathutils_matrix_row_cb_index = Mathutils_RegisterCallback(&mathutils_matrix_row_cb);
diff --git a/source/blender/python/mathutils/mathutils.h b/source/blender/python/mathutils/mathutils.h
index c465c27..df1d570 100644
--- a/source/blender/python/mathutils/mathutils.h
+++ b/source/blender/python/mathutils/mathutils.h
@@ -58,6 +58,7 @@ typedef struct {
/* utility submodules */
#include "mathutils_geometry.h"
#include "mathutils_noise.h"
+#include "mathutils_kdtree.h"
PyObject *BaseMathObject_owner_get(BaseMathObject *self, void *);
PyObject *BaseMathObject_is_wrapped_get(BaseMathObject *self, void *);
diff --git a/source/blender/python/mathutils/mathutils_kdtree.c b/source/blender/python/mathutils/mathutils_kdtree.c
new file mode 100644
index 0000000..aa9c7ee
--- /dev/null
+++ b/source/blender/python/mathutils/mathutils_kdtree.c
@@ -0,0 +1,429 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * Contributor(s): Dan Eicher, Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/python/mathutils/mathutils_kdtree.c
+ * \ingroup mathutils
+ *
+ * This file defines the 'mathutils.kdtree' module, a general purpose module to access
+ * blenders kdtree for 3d spatial lookups.
+ */
+
+#include <Python.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_kdtree.h"
+
+#include "../generic/py_capi_utils.h"
+#include "mathutils.h"
+
+#include "BLI_strict_flags.h"
+
+typedef struct {
+ PyObject_HEAD
+ KDTree *obj;
+ unsigned int maxsize;
+ unsigned int count;
+ unsigned int count_balance; /* size when we last balanced */
+} PyKDTree;
+
+
+/* -------------------------------------------------------------------- */
+/* Utility helper functions */
+
+static void kdtree_nearest_to_py_tuple(const KDTreeNearest *nearest, PyObject *py_retval)
+{
+ BLI_assert(nearest->index >= 0);
+ BLI_assert(PyTuple_GET_SIZE(py_retval) == 3);
+
+ PyTuple_SET_ITEM(py_retval, 0, Vector_CreatePyObject((float *)nearest->co, 3, Py_NEW, NULL));
+ PyTuple_SET_ITEM(py_retval, 1, PyLong_FromLong(nearest->index));
+ PyTuple_SET_ITEM(py_retval, 2, PyFloat_FromDouble(nearest->dist));
+}
+
+static PyObject *kdtree_nearest_to_py(const KDTreeNearest *nearest)
+{
+ PyObject *py_retval;
+
+ py_retval = PyTuple_New(3);
+
+ kdtree_nearest_to_py_tuple(nearest, py_retval);
+
+ return py_retval;
+}
+
+static PyObject *kdtree_nearest_to_py_and_check(const KDTreeNearest *nearest)
+{
+ PyObject *py_retval;
+
+ py_retval = PyTuple_New(3);
+
+ if (nearest->index != -1) {
+ kdtree_nearest_to_py_tuple(nearest, py_retval);
+ }
+ else {
+ PyC_Tuple_Fill(py_retval, Py_None);
+ }
+
+ return py_retval;
+}
+
+
+/* -------------------------------------------------------------------- */
+/* KDTree */
+
+/* annoying since arg parsing won't check overflow */
+#define UINT_IS_NEG(n) ((n) > INT_MAX)
+
+static int PyKDTree__tp_init(PyKDTree *self, PyObject *args, PyObject *kwargs)
+{
+ unsigned int maxsize;
+ const char *keywords[] = {"size", NULL};
+
+ if (!PyArg_ParseTupleAndKeywords(args, kwargs, (char *)"I:KDTree", (char **)keywords, &maxsize)) {
+ return -1;
+ }
+
+ if (UINT_IS_NEG(maxsize)) {
+ PyErr_SetString(PyExc_ValueError, "negative 'size' given");
+ return -1;
+ }
+
+ self->obj = BLI_kdtree_new(maxsize);
+ self->maxsize = maxsize;
+ self->count = 0;
+ self->count_balance = 0;
+
+ return 0;
+}
+
+static void PyKDTree__tp_dealloc(PyKDTree *self)
+{
+ BLI_kdtree_free(self->obj);
+ Py_TYPE(self)->tp_free((PyObject *)self);
+}
+
+PyDoc_STRVAR(py_kdtree_insert_doc,
+".. method:: insert(index, co)\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 *py_kdtree_insert(PyKDTree *self, PyObject *args, PyObject *kwargs)
+{
+ PyObject *py_co;
+ float co[3];
+ int index;
+ const char *keywords[] = {"co", "index", NULL};
+
+ if (!PyArg_ParseTupleAndKeywords(args, kwargs, (char *) "Oi:insert", (char **)keywords,
+ &py_co, &index))
+ {
+ return NULL;
+ }
+
+ if (mathutils_array_parse(co, 3, 3, py_co, "insert: invalid 'co' arg") == -1)
+ return NULL;
+
+ if (index < 0) {
+ PyErr_SetString(PyExc_ValueError, "negative index given");
+ return NULL;
+ }
+
+ if (self->count >= self->maxsize) {
+ PyErr_SetString(PyExc_RuntimeError, "Trying to insert more items than KDTree has room for");
+ return NULL;
+ }
+
+ BLI_kdtree_insert(self->obj, index, co, NULL);
+ self->count++;
+
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(py_kdtree_balance_doc,
+".. method:: balance()\n"
+"\n"
+" Balance the tree.\n"
+);
+static PyObject *py_kdtree_balance(PyKDTree *self)
+{
+ BLI_kdtree_balance(self->obj);
+ self->count_balance = self->count;
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(py_kdtree_find_doc,
+".. method:: find(co)\n"
+"\n"
+" Find nearest point to ``co``.\n"
+"\n"
+" :arg co: 3d coordinates.\n"
+" :type co: float triplet\n"
+" :return: Returns (:class:`Vector`, index, distance).\n"
+" :rtype: :class:`tuple`\n"
+);
+static PyObject *py_kdtree_find(PyKDTree *self, PyObject *args, PyObject *kwargs)
+{
+ PyObject *py_co;
+ float co[3];
+ KDTreeNearest nearest;
+ const char *keywords[] = {"co", NULL};
+
+ if (!PyArg_ParseTupleAndKeywords(args, kwargs, (ch
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list