Commit: 18af73e461f9a943ae606fcc1401297f4afad20f Author: Campbell Barton Date: Wed Jul 29 21:16:28 2015 +1000 Branches: master https://developer.blender.org/rB18af73e461f9a943ae606fcc1401297f4afad20f
Add mathutils.bvhtree API Originally D966 by @lukastoenne, with own additions - trees can be initialized from Object's, BMesh, or passed in as vert+polygon arrays. - original indices of ngons/faces are used. (instead of tessellated indices). - ray_cast, find_nearest methods - find overlapping faces between 2 trees =================================================================== M doc/python_api/sphinx_doc_gen.py M source/blender/python/mathutils/CMakeLists.txt M source/blender/python/mathutils/mathutils.c A source/blender/python/mathutils/mathutils_bvhtree.c A source/blender/python/mathutils/mathutils_bvhtree.h =================================================================== diff --git a/doc/python_api/sphinx_doc_gen.py b/doc/python_api/sphinx_doc_gen.py index 05ea0d0..4e14706 100644 --- a/doc/python_api/sphinx_doc_gen.py +++ b/doc/python_api/sphinx_doc_gen.py @@ -263,6 +263,7 @@ else: "gpu", "mathutils", "mathutils.geometry", + "mathutils.bvhtree", "mathutils.kdtree", "mathutils.noise", "freestyle", @@ -1644,7 +1645,7 @@ def write_rst_contents(basepath): standalone_modules = ( # mathutils - "mathutils", "mathutils.geometry", "mathutils.kdtree", "mathutils.noise", + "mathutils", "mathutils.geometry", "mathutils.bvhtree", "mathutils.kdtree", "mathutils.noise", # misc "freestyle", "bgl", "blf", "gpu", "aud", "bpy_extras", # bmesh, submodules are in own page @@ -1796,6 +1797,7 @@ def write_rst_importable_modules(basepath): "bpy.props" : "Property Definitions", "mathutils" : "Math Types & Utilities", "mathutils.geometry" : "Geometry Utilities", + "mathutils.bvhtree" : "BVHTree Utilities", "mathutils.kdtree" : "KDTree Utilities", "mathutils.noise" : "Noise Utilities", "freestyle" : "Freestyle Module", diff --git a/source/blender/python/mathutils/CMakeLists.txt b/source/blender/python/mathutils/CMakeLists.txt index ef6b090..f70f893 100644 --- a/source/blender/python/mathutils/CMakeLists.txt +++ b/source/blender/python/mathutils/CMakeLists.txt @@ -22,6 +22,7 @@ set(INC . ../../blenlib ../../blenkernel + ../../bmesh ../../makesdna ../../../../intern/guardedalloc ) @@ -37,6 +38,7 @@ set(SRC mathutils_Matrix.c mathutils_Quaternion.c mathutils_Vector.c + mathutils_bvhtree.c mathutils_geometry.c mathutils_interpolate.c mathutils_kdtree.c @@ -48,6 +50,7 @@ set(SRC mathutils_Matrix.h mathutils_Quaternion.h mathutils_Vector.h + mathutils_bvhtree.h mathutils_geometry.h mathutils_interpolate.h mathutils_kdtree.h diff --git a/source/blender/python/mathutils/mathutils.c b/source/blender/python/mathutils/mathutils.c index ba7f351..ec249e8 100644 --- a/source/blender/python/mathutils/mathutils.c +++ b/source/blender/python/mathutils/mathutils.c @@ -600,6 +600,7 @@ static struct PyModuleDef M_Mathutils_module_def = { #include "mathutils_geometry.h" #include "mathutils_interpolate.h" #ifndef MATH_STANDALONE +# include "mathutils_bvhtree.h" # include "mathutils_kdtree.h" # include "mathutils_noise.h" #endif @@ -653,6 +654,11 @@ PyMODINIT_FUNC PyInit_mathutils(void) PyDict_SetItemString(sys_modules, PyModule_GetName(submodule), submodule); Py_INCREF(submodule); + /* BVHTree submodule */ + PyModule_AddObject(mod, "bvhtree", (submodule = PyInit_mathutils_bvhtree())); + 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); diff --git a/source/blender/python/mathutils/mathutils_bvhtree.c b/source/blender/python/mathutils/mathutils_bvhtree.c new file mode 100644 index 0000000..b3b9532 --- /dev/null +++ b/source/blender/python/mathutils/mathutils_bvhtree.c @@ -0,0 +1,1193 @@ +/* + * ***** 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): Lukas Toenne, Campbell Barton + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/python/mathutils/mathutils_bvhtree.c + * \ingroup mathutils + * + * This file defines the 'mathutils.bvhtree' module, a general purpose module to access + * blenders bvhtree for mesh surface nearest-element search and ray casting. + */ + +#include <Python.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_kdopbvh.h" +#include "BLI_polyfill2d.h" +#include "BLI_math.h" +#include "BLI_ghash.h" +#include "BLI_memarena.h" + +#include "BKE_bvhutils.h" + +#include "../generic/py_capi_utils.h" +#include "../generic/python_utildefines.h" + +#include "mathutils.h" +#include "mathutils_bvhtree.h" /* own include */ + +#ifndef MATH_STANDALONE +#include "DNA_object_types.h" + +#include "BKE_customdata.h" +#include "BKE_DerivedMesh.h" +#include "BKE_editmesh_bvh.h" + +#include "bmesh.h" + +#include "../bmesh/bmesh_py_types.h" +#endif /* MATH_STANDALONE */ + + +#include "BLI_strict_flags.h" + + +/* -------------------------------------------------------------------- */ + +/** \name Docstring (snippets) + * \{ */ + +#define PYBVH_FIND_GENERIC_DISTANCE_DOC \ +" :arg distance: Maximum distance threshold.\n" \ +" :type distance: float\n" + +#define PYBVH_FIND_GENERIC_RETURN_DOC \ +" :return: Returns a tuple (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \ +" Values will all be None if no hit is found.\n" \ +" :rtype: :class:`tuple`\n" + +#define PYBVH_FROM_GENERIC_EPSILON_DOC \ +" :arg epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \ +" :type epsilon: float\n" + +/** \} */ + +/* sqrt(FLT_MAX) */ +#define PYBVH_MAX_DIST_STR "1.84467e+19" +static const float max_dist_default = 1.844674352395373e+19f; + +static const char PY_BVH_TREE_TYPE_DEFAULT = 4; +static const char PY_BVH_AXIS_DEFAULT = 6; + +typedef struct { + PyObject_HEAD + BVHTree *tree; + float epsilon; + + float (*coords)[3]; + unsigned int (*tris)[3]; + unsigned int coords_len, tris_len; + + /* Optional members */ + /* aligned with 'tris' */ + int *orig_index; + /* aligned with array that 'orig_index' points to */ + float (*orig_normal)[3]; +} PyBVHTree; + + +/* -------------------------------------------------------------------- */ + +/** \name Utility helper functions + * \{ */ + +static PyObject *bvhtree_CreatePyObject( + BVHTree *tree, float epsilon, + + float (*coords)[3], unsigned int coords_len, + unsigned int (*tris)[3], unsigned int tris_len, + + /* optional arrays */ + int *orig_index, float (*orig_normal)[3]) +{ + PyBVHTree *result = PyObject_New(PyBVHTree, &PyBVHTree_Type); + + result->tree = tree; + result->epsilon = epsilon; + + result->coords = coords; + result->tris = tris; + result->coords_len = coords_len; + result->tris_len = tris_len; + + result->orig_index = orig_index; + result->orig_normal = orig_normal; + + return (PyObject *)result; +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name BVHTreeRayHit to Python utilities + * \{ */ + +static void py_bvhtree_raycast_to_py_tuple(const BVHTreeRayHit *hit, PyObject *py_retval) +{ + BLI_assert(hit->index >= 0); + BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); + + PyTuple_SET_ITEMS(py_retval, + Vector_CreatePyObject(hit->co, 3, NULL), + Vector_CreatePyObject(hit->no, 3, NULL), + PyLong_FromLong(hit->index), + PyFloat_FromDouble(hit->dist)); + +} + +static PyObject *py_bvhtree_raycast_to_py(const BVHTreeRayHit *hit) +{ + PyObject *py_retval = PyTuple_New(4); + + py_bvhtree_raycast_to_py_tuple(hit, py_retval); + + return py_retval; +} + +static PyObject *py_bvhtree_raycast_to_py_none(void) +{ + PyObject *py_retval = PyTuple_New(4); + + PyC_Tuple_Fill(py_retval, Py_None); + + return py_retval; +} + +#if 0 +static PyObject *py_bvhtree_raycast_to_py_and_check(const BVHTreeRayHit *hit) +{ + PyObject *py_retval; + + py_retval = PyTuple_New(4); + + if (hit->index != -1) { + py_bvhtree_raycast_to_py_tuple(hit, py_retval); + } + else { + PyC_Tuple_Fill(py_retval, Py_None); + } + + return py_retval; +} +#endif + +/** \} */ + + +/* -------------------------------------------------------------------- */ + +/** \name BVHTreeNearest to Python utilities + * \{ */ + +static void py_bvhtree_nearest_to_py_tuple(const BVHTreeNearest *nearest, PyObject *py_retval) +{ + BLI_assert(nearest->index >= 0); + BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); + + PyTuple_SET_ITEMS(py_retval, + Vector_CreatePyObject(nearest->co, 3, NULL), + Vector_CreatePyObject(nearest->no, 3, NULL), + PyLong_FromLong(nearest->index), + PyFloat_FromDouble(sqrtf(nearest->dist_sq))); + +} + +static PyObject *py_bvhtree_nearest_to_py(const BVHTreeNearest *nearest) +{ + PyObject *py_retval = PyTuple_New(4); + + py_bvhtree_nearest_to_py_tuple(nearest, py_retval); + + return py_retval; +} + +static PyObject *py_bvhtree_nearest_to_py_none(void) +{ + PyObject *py_retval = PyTuple_New(4); + + PyC_Tuple_Fill(py_retval, Py_None); + + return py_retval; +} + +#if 0 +static PyObject *py_bvhtree_nearest_to_py_and_check(const BVHTreeNearest *nearest) +{ + PyObject *py_retval; + + py_retval = PyTuple_New(4); + + if (nearest->index != -1) { + py_bvhtree_nearest_to_py_tuple(nearest, py_retval); + } + else { + PyC_Tuple_Fill(py_retval, Py_None); + } + + return py_retval; +} +#endif + +/** \} */ + +static void py_bvhtree__tp_dealloc(PyBVHTree *self) +{ + if (self->tree) { + BLI_bvhtree_free(self->tree); + } + + MEM_SAFE_FREE(self->coords); + MEM_SAFE_FREE(self->tris); + + MEM_SAFE_FREE(self->orig_index); + MEM_SAFE_FREE(self->orig_normal); + + Py_TYPE(self)->tp_free((PyObject *)self); +} + + +/* -------------------------------------------------------------------- */ + +/** \name Methods + * \{ */ + +static void py_bvhtree_raycast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + const PyBVHTree *self = userdata; + + const float (*coords)[3] = self->coords; + const un @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs