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

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",

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

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);

source/blender/python/mathutils/mathutils_bvhtree.h

@@ -0,0 +1,36 @@
+/*
+ * ***** 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+
+/** \file blender/python/mathutils/mathutils_bvhtree.h
+ *  \ingroup mathutils
+ */
+
+#ifndef __MATHUTILS_BVHTREE_H__
+#define __MATHUTILS_BVHTREE_H__
+
+PyMODINIT_FUNC PyInit_mathutils_bvhtree(void);
+
+extern PyTypeObject PyBVHTree_Type;
+
+#define PyBVHTree_Check(_v)  PyObject_TypeCheck((_v), &PyBVHTree_Type)
+#define PyBVHTree_CheckExact(v)  (Py_TYPE(v) == &PyBVHTree_Type)
+
+#endif /* __MATHUTILS_BVHTREE_H__ */