[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