Merge branch 'blender2.7'
[blender.git] / source / blender / python / mathutils / mathutils_bvhtree.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Lukas Toenne, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/python/mathutils/mathutils_bvhtree.c
24  *  \ingroup mathutils
25  *
26  * This file defines the 'mathutils.bvhtree' module, a general purpose module to access
27  * blenders bvhtree for mesh surface nearest-element search and ray casting.
28  */
29
30 #include <Python.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_utildefines.h"
35 #include "BLI_kdopbvh.h"
36 #include "BLI_polyfill_2d.h"
37 #include "BLI_math.h"
38 #include "BLI_ghash.h"
39 #include "BLI_memarena.h"
40
41 #include "BKE_bvhutils.h"
42
43 #include "../generic/py_capi_utils.h"
44 #include "../generic/python_utildefines.h"
45
46 #include "mathutils.h"
47 #include "mathutils_bvhtree.h"  /* own include */
48
49 #ifndef MATH_STANDALONE
50 #include "DNA_object_types.h"
51 #include "DNA_mesh_types.h"
52 #include "DNA_meshdata_types.h"
53
54 #include "BKE_customdata.h"
55 #include "BKE_editmesh_bvh.h"
56 #include "BKE_library.h"
57 #include "BKE_mesh.h"
58 #include "BKE_mesh_runtime.h"
59
60 #include "DEG_depsgraph_query.h"
61
62 #include "bmesh.h"
63
64 #include "../bmesh/bmesh_py_types.h"
65 #endif  /* MATH_STANDALONE */
66
67
68 #include "BLI_strict_flags.h"
69
70
71 /* -------------------------------------------------------------------- */
72 /** \name Docstring (snippets)
73  * \{ */
74
75 #define PYBVH_FIND_GENERIC_DISTANCE_DOC \
76 "   :arg distance: Maximum distance threshold.\n" \
77 "   :type distance: float\n"
78
79 #define PYBVH_FIND_GENERIC_RETURN_DOC \
80 "   :return: Returns a tuple\n" \
81 "      (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \
82 "      Values will all be None if no hit is found.\n" \
83 "   :rtype: :class:`tuple`\n"
84
85 #define PYBVH_FIND_GENERIC_RETURN_LIST_DOC \
86 "   :return: Returns a list of tuples\n" \
87 "      (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \
88 "   :rtype: :class:`list`\n"
89
90 #define PYBVH_FROM_GENERIC_EPSILON_DOC \
91 "   :arg epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \
92 "   :type epsilon: float\n"
93
94 /** \} */
95
96 /* sqrt(FLT_MAX) */
97 #define PYBVH_MAX_DIST_STR "1.84467e+19"
98 static const float max_dist_default = 1.844674352395373e+19f;
99
100 static const char PY_BVH_TREE_TYPE_DEFAULT = 4;
101 static const char PY_BVH_AXIS_DEFAULT = 6;
102
103 typedef struct {
104         PyObject_HEAD
105         BVHTree *tree;
106         float epsilon;
107
108         float (*coords)[3];
109         unsigned int (*tris)[3];
110         unsigned int coords_len, tris_len;
111
112         /* Optional members */
113         /* aligned with 'tris' */
114         int *orig_index;
115         /* aligned with array that 'orig_index' points to */
116         float (*orig_normal)[3];
117 } PyBVHTree;
118
119
120 /* -------------------------------------------------------------------- */
121 /** \name Utility helper functions
122  * \{ */
123
124 static PyObject *bvhtree_CreatePyObject(
125         BVHTree *tree, float epsilon,
126
127         float (*coords)[3], unsigned int coords_len,
128         unsigned int (*tris)[3], unsigned int tris_len,
129
130         /* optional arrays */
131         int *orig_index, float (*orig_normal)[3])
132 {
133         PyBVHTree *result = PyObject_New(PyBVHTree, &PyBVHTree_Type);
134
135         result->tree = tree;
136         result->epsilon = epsilon;
137
138         result->coords = coords;
139         result->tris = tris;
140         result->coords_len = coords_len;
141         result->tris_len = tris_len;
142
143         result->orig_index = orig_index;
144         result->orig_normal = orig_normal;
145
146         return (PyObject *)result;
147 }
148
149 /** \} */
150
151
152 /* -------------------------------------------------------------------- */
153 /** \name BVHTreeRayHit to Python utilities
154  * \{ */
155
156 static void py_bvhtree_raycast_to_py_tuple(const BVHTreeRayHit *hit, PyObject *py_retval)
157 {
158         BLI_assert(hit->index >= 0);
159         BLI_assert(PyTuple_GET_SIZE(py_retval) == 4);
160
161         PyTuple_SET_ITEMS(py_retval,
162                 Vector_CreatePyObject(hit->co, 3, NULL),
163                 Vector_CreatePyObject(hit->no, 3, NULL),
164                 PyLong_FromLong(hit->index),
165                 PyFloat_FromDouble(hit->dist));
166
167 }
168
169 static PyObject *py_bvhtree_raycast_to_py(const BVHTreeRayHit *hit)
170 {
171         PyObject *py_retval = PyTuple_New(4);
172
173         py_bvhtree_raycast_to_py_tuple(hit, py_retval);
174
175         return py_retval;
176 }
177
178 static PyObject *py_bvhtree_raycast_to_py_none(void)
179 {
180         PyObject *py_retval = PyTuple_New(4);
181
182         PyC_Tuple_Fill(py_retval, Py_None);
183
184         return py_retval;
185 }
186
187 #if 0
188 static PyObject *py_bvhtree_raycast_to_py_and_check(const BVHTreeRayHit *hit)
189 {
190         PyObject *py_retval;
191
192         py_retval = PyTuple_New(4);
193
194         if (hit->index != -1) {
195                 py_bvhtree_raycast_to_py_tuple(hit, py_retval);
196         }
197         else {
198                 PyC_Tuple_Fill(py_retval, Py_None);
199         }
200
201         return py_retval;
202 }
203 #endif
204
205 /** \} */
206
207
208 /* -------------------------------------------------------------------- */
209 /** \name BVHTreeNearest to Python utilities
210  * \{ */
211
212 static void py_bvhtree_nearest_to_py_tuple(const BVHTreeNearest *nearest, PyObject *py_retval)
213 {
214         BLI_assert(nearest->index >= 0);
215         BLI_assert(PyTuple_GET_SIZE(py_retval) == 4);
216
217         PyTuple_SET_ITEMS(py_retval,
218                 Vector_CreatePyObject(nearest->co, 3, NULL),
219                 Vector_CreatePyObject(nearest->no, 3, NULL),
220                 PyLong_FromLong(nearest->index),
221                 PyFloat_FromDouble(sqrtf(nearest->dist_sq)));
222
223 }
224
225 static PyObject *py_bvhtree_nearest_to_py(const BVHTreeNearest *nearest)
226 {
227         PyObject *py_retval = PyTuple_New(4);
228
229         py_bvhtree_nearest_to_py_tuple(nearest, py_retval);
230
231         return py_retval;
232 }
233
234 static PyObject *py_bvhtree_nearest_to_py_none(void)
235 {
236         PyObject *py_retval = PyTuple_New(4);
237
238         PyC_Tuple_Fill(py_retval, Py_None);
239
240         return py_retval;
241 }
242
243 #if 0
244 static PyObject *py_bvhtree_nearest_to_py_and_check(const BVHTreeNearest *nearest)
245 {
246         PyObject *py_retval;
247
248         py_retval = PyTuple_New(4);
249
250         if (nearest->index != -1) {
251                 py_bvhtree_nearest_to_py_tuple(nearest, py_retval);
252         }
253         else {
254                 PyC_Tuple_Fill(py_retval, Py_None);
255         }
256
257         return py_retval;
258 }
259 #endif
260
261 /** \} */
262
263 static void py_bvhtree__tp_dealloc(PyBVHTree *self)
264 {
265         if (self->tree) {
266                 BLI_bvhtree_free(self->tree);
267         }
268
269         MEM_SAFE_FREE(self->coords);
270         MEM_SAFE_FREE(self->tris);
271
272         MEM_SAFE_FREE(self->orig_index);
273         MEM_SAFE_FREE(self->orig_normal);
274
275         Py_TYPE(self)->tp_free((PyObject *)self);
276 }
277
278
279 /* -------------------------------------------------------------------- */
280 /** \name Methods
281  * \{ */
282
283 static void py_bvhtree_raycast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
284 {
285         const PyBVHTree *self = userdata;
286
287         const float (*coords)[3] = (const float (*)[3])self->coords;
288         const unsigned int *tri = self->tris[index];
289         const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
290         float dist;
291
292         if (self->epsilon == 0.0f) {
293                 dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(tri_co));
294         }
295         else {
296                 dist = bvhtree_sphereray_tri_intersection(ray, self->epsilon, hit->dist, UNPACK3(tri_co));
297         }
298
299         if (dist >= 0 && dist < hit->dist) {
300                 hit->index = self->orig_index ? self->orig_index[index] : index;
301                 hit->dist = dist;
302                 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
303                 if (self->orig_normal) {
304                         copy_v3_v3(hit->no, self->orig_normal[hit->index]);
305                 }
306                 else {
307                         normal_tri_v3(hit->no, UNPACK3(tri_co));
308                 }
309         }
310 }
311
312 static void py_bvhtree_nearest_point_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
313 {
314         PyBVHTree *self = userdata;
315
316         const float (*coords)[3] = (const float (*)[3])self->coords;
317         const unsigned int *tri = self->tris[index];
318         const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
319         float nearest_tmp[3], dist_sq;
320
321         closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co));
322         dist_sq = len_squared_v3v3(co, nearest_tmp);
323
324         if (dist_sq < nearest->dist_sq) {
325                 nearest->index = self->orig_index ? self->orig_index[index] : index;
326                 nearest->dist_sq = dist_sq;
327                 copy_v3_v3(nearest->co, nearest_tmp);
328                 if (self->orig_normal) {
329                         copy_v3_v3(nearest->no, self->orig_normal[nearest->index]);
330                 }
331                 else {
332                         normal_tri_v3(nearest->no, UNPACK3(tri_co));
333                 }
334         }
335 }
336
337 PyDoc_STRVAR(py_bvhtree_ray_cast_doc,
338 ".. method:: ray_cast(origin, direction, distance=sys.float_info.max)\n"
339 "\n"
340 "   Cast a ray onto the mesh.\n"
341 "\n"
342 "   :arg co: Start location of the ray in object space.\n"
343 "   :type co: :class:`Vector`\n"
344 "   :arg direction: Direction of the ray in object space.\n"
345 "   :type direction: :class:`Vector`\n"
346 PYBVH_FIND_GENERIC_DISTANCE_DOC
347 PYBVH_FIND_GENERIC_RETURN_DOC
348 );
349 static PyObject *py_bvhtree_ray_cast(PyBVHTree *self, PyObject *args)
350 {
351         const char *error_prefix = "ray_cast";
352         float co[3], direction[3];
353         float max_dist = FLT_MAX;
354         BVHTreeRayHit hit;
355
356         /* parse args */
357         {
358                 PyObject *py_co, *py_direction;
359
360                 if (!PyArg_ParseTuple(
361                         args, (char *)"OO|f:ray_cast",
362                         &py_co, &py_direction, &max_dist))
363                 {
364                         return NULL;
365                 }
366
367                 if ((mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) ||
368                     (mathutils_array_parse(direction, 2, 3 | MU_ARRAY_ZERO, py_direction, error_prefix) == -1))
369                 {
370                         return NULL;
371                 }
372
373                 normalize_v3(direction);
374         }
375
376         hit.dist = max_dist;
377         hit.index = -1;
378
379         /* may fail if the mesh has no faces, in that case the ray-cast misses */
380         if (self->tree) {
381                 if (BLI_bvhtree_ray_cast(
382                         self->tree, co, direction, 0.0f, &hit,
383                         py_bvhtree_raycast_cb, self) != -1)
384                 {
385                         return py_bvhtree_raycast_to_py(&hit);
386                 }
387         }
388
389         return py_bvhtree_raycast_to_py_none();
390 }
391
392 PyDoc_STRVAR(py_bvhtree_find_nearest_doc,
393 ".. method:: find_nearest(origin, distance=" PYBVH_MAX_DIST_STR ")\n"
394 "\n"
395 "   Find the nearest element (typically face index) to a point.\n"
396 "\n"
397 "   :arg co: Find nearest element to this point.\n"
398 "   :type co: :class:`Vector`\n"
399 PYBVH_FIND_GENERIC_DISTANCE_DOC
400 PYBVH_FIND_GENERIC_RETURN_DOC
401 );
402 static PyObject *py_bvhtree_find_nearest(PyBVHTree *self, PyObject *args)
403 {
404         const char *error_prefix = "find_nearest";
405         float co[3];
406         float max_dist = max_dist_default;
407
408         BVHTreeNearest nearest;
409
410         /* parse args */
411         {
412                 PyObject *py_co;
413
414                 if (!PyArg_ParseTuple(
415                         args, (char *)"O|f:find_nearest",
416                         &py_co, &max_dist))
417                 {
418                         return NULL;
419                 }
420
421                 if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) {
422                         return NULL;
423                 }
424         }
425
426         nearest.index = -1;
427         nearest.dist_sq = max_dist * max_dist;
428
429         /* may fail if the mesh has no faces, in that case the ray-cast misses */
430         if (self->tree) {
431                 if (BLI_bvhtree_find_nearest(
432                         self->tree, co, &nearest,
433                         py_bvhtree_nearest_point_cb, self) != -1)
434                 {
435                         return py_bvhtree_nearest_to_py(&nearest);
436                 }
437         }
438
439         return py_bvhtree_nearest_to_py_none();
440 }
441
442 struct PyBVH_RangeData {
443         PyBVHTree *self;
444         PyObject *result;
445         float dist_sq;
446 };
447
448 static void py_bvhtree_nearest_point_range_cb(void *userdata, int index, const float co[3], float UNUSED(dist_sq_bvh))
449 {
450         struct PyBVH_RangeData *data = userdata;
451         PyBVHTree *self = data->self;
452
453         const float (*coords)[3] = (const float (*)[3])self->coords;
454         const unsigned int *tri = self->tris[index];
455         const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
456         float nearest_tmp[3], dist_sq;
457
458         closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co));
459         dist_sq = len_squared_v3v3(co, nearest_tmp);
460
461         if (dist_sq < data->dist_sq) {
462                 BVHTreeNearest nearest;
463                 nearest.index = self->orig_index ? self->orig_index[index] : index;
464                 nearest.dist_sq = dist_sq;
465                 copy_v3_v3(nearest.co, nearest_tmp);
466                 if (self->orig_normal) {
467                         copy_v3_v3(nearest.no, self->orig_normal[nearest.index]);
468                 }
469                 else {
470                         normal_tri_v3(nearest.no, UNPACK3(tri_co));
471                 }
472
473                 PyList_APPEND(data->result, py_bvhtree_nearest_to_py(&nearest));
474         }
475 }
476
477 PyDoc_STRVAR(py_bvhtree_find_nearest_range_doc,
478 ".. method:: find_nearest_range(origin, distance=" PYBVH_MAX_DIST_STR ")\n"
479 "\n"
480 "   Find the nearest elements (typically face index) to a point in the distance range.\n"
481 "\n"
482 "   :arg co: Find nearest elements to this point.\n"
483 "   :type co: :class:`Vector`\n"
484 PYBVH_FIND_GENERIC_DISTANCE_DOC
485 PYBVH_FIND_GENERIC_RETURN_LIST_DOC
486 );
487 static PyObject *py_bvhtree_find_nearest_range(PyBVHTree *self, PyObject *args)
488 {
489         const char *error_prefix = "find_nearest_range";
490         float co[3];
491         float max_dist = max_dist_default;
492
493         /* parse args */
494         {
495                 PyObject *py_co;
496
497                 if (!PyArg_ParseTuple(
498                         args, (char *)"O|f:find_nearest_range",
499                         &py_co, &max_dist))
500                 {
501                         return NULL;
502                 }
503
504                 if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) {
505                         return NULL;
506                 }
507         }
508
509         PyObject *ret = PyList_New(0);
510
511         if (self->tree) {
512                 struct PyBVH_RangeData data = {
513                         .self = self,
514                         .result = ret,
515                         .dist_sq = SQUARE(max_dist),
516                 };
517
518                 BLI_bvhtree_range_query(
519                         self->tree, co, max_dist,
520                         py_bvhtree_nearest_point_range_cb, &data);
521         }
522
523         return ret;
524 }
525
526
527 BLI_INLINE unsigned int overlap_hash(const void *overlap_v)
528 {
529         const BVHTreeOverlap *overlap = overlap_v;
530         /* same constants as edge-hash */
531         return (((unsigned int)overlap->indexA * 65) ^ ((unsigned int)overlap->indexA * 31));
532 }
533
534 BLI_INLINE bool overlap_cmp(const void *a_v, const void *b_v)
535 {
536         const BVHTreeOverlap *a = a_v;
537         const BVHTreeOverlap *b = b_v;
538         return (memcmp(a, b, sizeof(*a)) != 0);
539 }
540
541 struct PyBVHTree_OverlapData {
542         PyBVHTree *tree_pair[2];
543         float epsilon;
544 };
545
546 static bool py_bvhtree_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
547 {
548         struct PyBVHTree_OverlapData *data = userdata;
549         PyBVHTree *tree_a = data->tree_pair[0];
550         PyBVHTree *tree_b = data->tree_pair[1];
551         const unsigned int *tri_a = tree_a->tris[index_a];
552         const unsigned int *tri_b = tree_b->tris[index_b];
553         const float *tri_a_co[3] = {tree_a->coords[tri_a[0]], tree_a->coords[tri_a[1]], tree_a->coords[tri_a[2]]};
554         const float *tri_b_co[3] = {tree_b->coords[tri_b[0]], tree_b->coords[tri_b[1]], tree_b->coords[tri_b[2]]};
555         float ix_pair[2][3];
556         int verts_shared = 0;
557
558         if (tree_a == tree_b) {
559                 if (UNLIKELY(index_a == index_b)) {
560                         return false;
561                 }
562
563                 verts_shared = (
564                         ELEM(tri_a_co[0], UNPACK3(tri_b_co)) +
565                         ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
566                         ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
567
568                 /* if 2 points are shared, bail out */
569                 if (verts_shared >= 2) {
570                         return false;
571                 }
572         }
573
574         return (isect_tri_tri_epsilon_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) &&
575                 ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
576 }
577
578 PyDoc_STRVAR(py_bvhtree_overlap_doc,
579 ".. method:: overlap(other_tree)\n"
580 "\n"
581 "   Find overlapping indices between 2 trees.\n"
582 "\n"
583 "   :arg other_tree: Other tree to perform overlap test on.\n"
584 "   :type other_tree: :class:`BVHTree`\n"
585 "   :return: Returns a list of unique index pairs,"
586 "      the first index referencing this tree, the second referencing the **other_tree**.\n"
587 "   :rtype: :class:`list`\n"
588 );
589 static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other)
590 {
591         struct PyBVHTree_OverlapData data;
592         BVHTreeOverlap *overlap;
593         unsigned int overlap_len = 0;
594         PyObject *ret;
595
596         if (!PyBVHTree_CheckExact(other)) {
597                 PyErr_SetString(PyExc_ValueError, "Expected a BVHTree argument");
598                 return NULL;
599         }
600
601         data.tree_pair[0] = self;
602         data.tree_pair[1] = other;
603         data.epsilon = max_ff(self->epsilon, other->epsilon);
604
605         overlap = BLI_bvhtree_overlap(self->tree, other->tree, &overlap_len, py_bvhtree_overlap_cb, &data);
606
607         ret = PyList_New(0);
608
609         if (overlap == NULL) {
610                 /* pass */
611         }
612         else {
613                 bool use_unique = (self->orig_index || other->orig_index);
614                 GSet *pair_test = use_unique ? BLI_gset_new_ex(overlap_hash, overlap_cmp, __func__, overlap_len) : NULL;
615                 /* simple case, no index remapping */
616                 unsigned int i;
617
618                 for (i = 0; i < overlap_len; i++) {
619                         PyObject *item;
620                         if (use_unique) {
621                                 if (self->orig_index) {
622                                         overlap[i].indexA = self->orig_index[overlap[i].indexA];
623                                 }
624                                 if (other->orig_index) {
625                                         overlap[i].indexB = other->orig_index[overlap[i].indexB];
626                                 }
627
628                                 /* skip if its already added */
629                                 if (!BLI_gset_add(pair_test, &overlap[i])) {
630                                         continue;
631                                 }
632                         }
633
634                         item = PyTuple_New(2);
635                         PyTuple_SET_ITEMS(item,
636                                 PyLong_FromLong(overlap[i].indexA),
637                                 PyLong_FromLong(overlap[i].indexB));
638
639                         PyList_Append(ret, item);
640                         Py_DECREF(item);
641                 }
642
643                 if (pair_test) {
644                         BLI_gset_free(pair_test, NULL);
645                 }
646         }
647
648         if (overlap) {
649                 MEM_freeN(overlap);
650         }
651
652         return ret;
653 }
654
655 /** \} */
656
657
658 /* -------------------------------------------------------------------- */
659 /** \name Class Methods
660  * \{ */
661
662 PyDoc_STRVAR(C_BVHTree_FromPolygons_doc,
663 ".. classmethod:: FromPolygons(vertices, polygons, all_triangles=False, epsilon=0.0)\n"
664 "\n"
665 "   BVH tree constructed geometry passed in as arguments.\n"
666 "\n"
667 "   :arg vertices: float triplets each representing ``(x, y, z)``\n"
668 "   :type vertices: float triplet sequence\n"
669 "   :arg polygons: Sequence of polyugons, each containing indices to the vertices argument.\n"
670 "   :type polygons: Sequence of sequences containing ints\n"
671 "   :arg all_triangles: Use when all **polygons** are triangles for more efficient conversion.\n"
672 "   :type all_triangles: bool\n"
673 PYBVH_FROM_GENERIC_EPSILON_DOC
674 );
675 static PyObject *C_BVHTree_FromPolygons(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
676 {
677         const char *error_prefix = "BVHTree.FromPolygons";
678         const char *keywords[] = {"vertices", "polygons", "all_triangles", "epsilon", NULL};
679
680         PyObject *py_coords, *py_tris;
681         PyObject *py_coords_fast = NULL, *py_tris_fast = NULL;
682
683         MemArena *poly_arena = NULL;
684         MemArena *pf_arena = NULL;
685
686         float (*coords)[3] = NULL;
687         unsigned int (*tris)[3] = NULL;
688         unsigned int coords_len, tris_len;
689         float epsilon = 0.0f;
690         bool all_triangles = false;
691
692         /* when all_triangles is False */
693         int *orig_index = NULL;
694         float (*orig_normal)[3] = NULL;
695
696         unsigned int i;
697         bool valid = true;
698
699
700         if (!PyArg_ParseTupleAndKeywords(
701                 args, kwargs, (char *)"OO|$O&f:BVHTree.FromPolygons", (char **)keywords,
702                 &py_coords, &py_tris,
703                 PyC_ParseBool, &all_triangles,
704                 &epsilon))
705         {
706                 return NULL;
707         }
708
709         if (!(py_coords_fast = PySequence_Fast(py_coords, error_prefix)) ||
710             !(py_tris_fast  = PySequence_Fast(py_tris, error_prefix)))
711         {
712                 Py_XDECREF(py_coords_fast);
713                 return NULL;
714         }
715
716         if (valid) {
717                 PyObject **py_coords_fast_items = PySequence_Fast_ITEMS(py_coords_fast);
718                 coords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_coords_fast);
719                 coords = MEM_mallocN((size_t)coords_len * sizeof(*coords), __func__);
720
721                 for (i = 0; i < coords_len; i++) {
722                         PyObject *py_vert = py_coords_fast_items[i];
723
724                         if (mathutils_array_parse(coords[i], 3, 3, py_vert, "BVHTree vertex: ") == -1) {
725                                 valid = false;
726                                 break;
727                         }
728                 }
729         }
730
731         if (valid == false) {
732                 /* pass */
733         }
734         else if (all_triangles) {
735                 /* all triangles, simple case */
736                 PyObject **py_tris_fast_items = PySequence_Fast_ITEMS(py_tris_fast);
737                 tris_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast);
738                 tris = MEM_mallocN((size_t)tris_len * sizeof(*tris), __func__);
739
740                 for (i = 0; i < tris_len; i++) {
741                         PyObject *py_tricoords = py_tris_fast_items[i];
742                         PyObject *py_tricoords_fast;
743                         PyObject **py_tricoords_fast_items;
744                         unsigned int *tri = tris[i];
745                         int j;
746
747                         if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) {
748                                 valid = false;
749                                 break;
750                         }
751
752                         if (PySequence_Fast_GET_SIZE(py_tricoords_fast) != 3) {
753                                 Py_DECREF(py_tricoords_fast);
754                                 PyErr_Format(PyExc_ValueError,
755                                              "%s: non triangle found at index %d with length of %d",
756                                              error_prefix, i, PySequence_Fast_GET_SIZE(py_tricoords_fast));
757                                 valid = false;
758                                 break;
759                         }
760
761                         py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast);
762
763                         for (j = 0; j < 3; j++) {
764                                 tri[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]);
765                                 if (UNLIKELY(tri[j] >= (unsigned int)coords_len)) {
766                                         PyErr_Format(PyExc_ValueError,
767                                                      "%s: index %d must be less than %d",
768                                                      error_prefix, tri[j], coords_len);
769
770                                         /* decref below */
771                                         valid = false;
772                                         break;
773                                 }
774                         }
775
776                         Py_DECREF(py_tricoords_fast);
777                 }
778         }
779         else {
780                 /* ngon support (much more involved) */
781                 const unsigned int polys_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast);
782                 struct PolyLink {
783                         struct PolyLink *next;
784                         unsigned int len;
785                         unsigned int poly[0];
786                 } *plink_first = NULL, **p_plink_prev = &plink_first, *plink = NULL;
787                 int poly_index;
788
789                 tris_len = 0;
790
791                 poly_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
792
793                 for (i = 0; i < polys_len; i++) {
794                         PyObject *py_tricoords = PySequence_Fast_GET_ITEM(py_tris_fast, i);
795                         PyObject *py_tricoords_fast;
796                         PyObject **py_tricoords_fast_items;
797                         unsigned int py_tricoords_len;
798                         unsigned int j;
799
800                         if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) {
801                                 valid = false;
802                                 break;
803                         }
804
805                         py_tricoords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tricoords_fast);
806                         py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast);
807
808                         plink = BLI_memarena_alloc(poly_arena, sizeof(*plink) + (sizeof(int) * (size_t)py_tricoords_len));
809
810                         plink->len = (unsigned int)py_tricoords_len;
811                         *p_plink_prev = plink;
812                         p_plink_prev = &plink->next;
813
814                         for (j = 0; j < py_tricoords_len; j++) {
815                                 plink->poly[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]);
816                                 if (UNLIKELY(plink->poly[j] >= (unsigned int)coords_len)) {
817                                         PyErr_Format(PyExc_ValueError,
818                                                      "%s: index %d must be less than %d",
819                                                      error_prefix, plink->poly[j], coords_len);
820                                         /* decref below */
821                                         valid = false;
822                                         break;
823                                 }
824                         }
825
826                         Py_DECREF(py_tricoords_fast);
827
828                         if (py_tricoords_len >= 3) {
829                                 tris_len += (py_tricoords_len - 2);
830                         }
831                 }
832                 *p_plink_prev = NULL;
833
834                 /* all ngon's are parsed, now tessellate */
835
836                 pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
837                 tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__);
838
839                 orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__);
840                 orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)polys_len, __func__);
841
842                 for (plink = plink_first, poly_index = 0, i = 0; plink; plink = plink->next, poly_index++) {
843                         if (plink->len == 3) {
844                                 unsigned int *tri = tris[i];
845                                 memcpy(tri, plink->poly, sizeof(unsigned int[3]));
846                                 orig_index[i] = poly_index;
847                                 normal_tri_v3(orig_normal[poly_index], coords[tri[0]], coords[tri[1]], coords[tri[2]]);
848                                 i++;
849                         }
850                         else if (plink->len > 3) {
851                                 float (*proj_coords)[2] = BLI_memarena_alloc(pf_arena, sizeof(*proj_coords) * plink->len);
852                                 float *normal = orig_normal[poly_index];
853                                 const float *co_prev;
854                                 const float *co_curr;
855                                 float axis_mat[3][3];
856                                 unsigned int (*tris_offset)[3] = &tris[i];
857                                 unsigned int j;
858
859                                 /* calc normal and setup 'proj_coords' */
860                                 zero_v3(normal);
861                                 co_prev = coords[plink->poly[plink->len - 1]];
862                                 for (j = 0; j < plink->len; j++) {
863                                         co_curr = coords[plink->poly[j]];
864                                         add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
865                                         co_prev = co_curr;
866                                 }
867                                 normalize_v3(normal);
868
869                                 axis_dominant_v3_to_m3_negate(axis_mat, normal);
870
871                                 for (j = 0; j < plink->len; j++) {
872                                         mul_v2_m3v3(proj_coords[j], axis_mat, coords[plink->poly[j]]);
873                                 }
874
875                                 BLI_polyfill_calc_arena(proj_coords, plink->len, 1, tris_offset, pf_arena);
876
877                                 j = plink->len - 2;
878                                 while (j--) {
879                                         unsigned int *tri = tris_offset[j];
880                                         /* remap to global indices */
881                                         tri[0] = plink->poly[tri[0]];
882                                         tri[1] = plink->poly[tri[1]];
883                                         tri[2] = plink->poly[tri[2]];
884
885                                         orig_index[i] = poly_index;
886                                         i++;
887                                 }
888
889                                 BLI_memarena_clear(pf_arena);
890                         }
891                         else {
892                                 zero_v3(orig_normal[poly_index]);
893                         }
894                 }
895         }
896
897         Py_DECREF(py_coords_fast);
898         Py_DECREF(py_tris_fast);
899
900         if (pf_arena) {
901                 BLI_memarena_free(pf_arena);
902         }
903
904         if (poly_arena) {
905                 BLI_memarena_free(poly_arena);
906         }
907
908         if (valid) {
909                 BVHTree *tree;
910
911                 tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
912                 if (tree) {
913                         for (i = 0; i < tris_len; i++) {
914                                 float co[3][3];
915
916                                 copy_v3_v3(co[0], coords[tris[i][0]]);
917                                 copy_v3_v3(co[1], coords[tris[i][1]]);
918                                 copy_v3_v3(co[2], coords[tris[i][2]]);
919
920                                 BLI_bvhtree_insert(tree, (int)i, co[0], 3);
921                         }
922
923                         BLI_bvhtree_balance(tree);
924                 }
925
926                 return bvhtree_CreatePyObject(
927                         tree, epsilon,
928                         coords, coords_len,
929                         tris, tris_len,
930                         orig_index, orig_normal);
931         }
932         else {
933                 if (coords)
934                         MEM_freeN(coords);
935                 if (tris)
936                         MEM_freeN(tris);
937
938                 return NULL;
939         }
940 }
941
942
943 #ifndef MATH_STANDALONE
944
945 PyDoc_STRVAR(C_BVHTree_FromBMesh_doc,
946 ".. classmethod:: FromBMesh(bmesh, epsilon=0.0)\n"
947 "\n"
948 "   BVH tree based on :class:`BMesh` data.\n"
949 "\n"
950 "   :arg bmesh: BMesh data.\n"
951 "   :type bmesh: :class:`BMesh`\n"
952 PYBVH_FROM_GENERIC_EPSILON_DOC
953 );
954 static PyObject *C_BVHTree_FromBMesh(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
955 {
956         const char *keywords[] = {"bmesh", "epsilon", NULL};
957
958         BPy_BMesh *py_bm;
959
960         float (*coords)[3] = NULL;
961         unsigned int (*tris)[3] = NULL;
962         unsigned int coords_len, tris_len;
963         float epsilon = 0.0f;
964
965         BMesh *bm;
966         BMLoop *(*looptris)[3];
967
968         if (!PyArg_ParseTupleAndKeywords(
969                 args, kwargs, (char *)"O!|$f:BVHTree.FromBMesh", (char **)keywords,
970                 &BPy_BMesh_Type, &py_bm, &epsilon))
971         {
972                 return NULL;
973         }
974
975         bm = py_bm->bm;
976
977         /* Get data for tessellation */
978         {
979                 int tris_len_dummy;
980
981                 coords_len = (unsigned int)bm->totvert;
982                 tris_len = (unsigned int)poly_to_tri_count(bm->totface, bm->totloop);
983
984                 coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__);
985                 tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__);
986
987                 looptris = MEM_mallocN(sizeof(*looptris) * (size_t)tris_len, __func__);
988
989                 BM_mesh_calc_tessellation(bm, looptris, &tris_len_dummy);
990                 BLI_assert(tris_len_dummy == (int)tris_len);
991         }
992
993         {
994                 BMIter iter;
995                 BVHTree *tree;
996                 unsigned int i;
997
998                 int *orig_index = NULL;
999                 float (*orig_normal)[3] = NULL;
1000
1001                 tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
1002                 if (tree) {
1003                         BMFace *f;
1004                         BMVert *v;
1005
1006                         orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__);
1007                         orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)bm->totface, __func__);
1008
1009                         BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1010                                 copy_v3_v3(coords[i], v->co);
1011                                 BM_elem_index_set(v, (int)i);  /* set_inline */
1012                         }
1013                         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
1014                                 copy_v3_v3(orig_normal[i], f->no);
1015                                 BM_elem_index_set(f, (int)i);  /* set_inline */
1016                         }
1017                         bm->elem_index_dirty &= (char)~(BM_VERT | BM_FACE);
1018
1019                         for (i = 0; i < tris_len; i++) {
1020                                 float co[3][3];
1021
1022                                 tris[i][0] = (unsigned int)BM_elem_index_get(looptris[i][0]->v);
1023                                 tris[i][1] = (unsigned int)BM_elem_index_get(looptris[i][1]->v);
1024                                 tris[i][2] = (unsigned int)BM_elem_index_get(looptris[i][2]->v);
1025
1026                                 copy_v3_v3(co[0], coords[tris[i][0]]);
1027                                 copy_v3_v3(co[1], coords[tris[i][1]]);
1028                                 copy_v3_v3(co[2], coords[tris[i][2]]);
1029
1030                                 BLI_bvhtree_insert(tree, (int)i, co[0], 3);
1031                                 orig_index[i] = BM_elem_index_get(looptris[i][0]->f);
1032                         }
1033
1034                         BLI_bvhtree_balance(tree);
1035                 }
1036
1037                 MEM_freeN(looptris);
1038
1039                 return bvhtree_CreatePyObject(
1040                         tree, epsilon,
1041                         coords, coords_len,
1042                         tris, tris_len,
1043                         orig_index, orig_normal);
1044         }
1045 }
1046
1047 /* return various derived meshes based on requested settings */
1048 static Mesh *bvh_get_mesh(
1049         const char *funcname, struct Depsgraph *depsgraph, struct Scene *scene, Object *ob,
1050         const bool use_deform, const bool use_cage, bool *r_free_mesh)
1051 {
1052         Object *ob_eval = DEG_get_evaluated_object(depsgraph, ob);
1053         /* we only need minimum mesh data for topology and vertex locations */
1054         CustomDataMask mask = CD_MASK_BAREMESH;
1055         const bool use_render = DEG_get_mode(depsgraph) == DAG_EVAL_RENDER;
1056         *r_free_mesh = false;
1057
1058         /* Write the display mesh into the dummy mesh */
1059         if (use_deform) {
1060                 if (use_render) {
1061                         if (use_cage) {
1062                                 PyErr_Format(PyExc_ValueError,
1063                                              "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", funcname);
1064                                 return NULL;
1065                         }
1066                         else {
1067                                 *r_free_mesh = true;
1068                                 return mesh_create_eval_final_render(depsgraph, scene, ob, mask);
1069                         }
1070                 }
1071                 else if (ob_eval != NULL) {
1072                         if (use_cage) {
1073                                 return mesh_get_eval_deform(depsgraph, scene, ob_eval, mask);  /* ob->derivedDeform */
1074                         }
1075                         else {
1076                                 return mesh_get_eval_final(depsgraph, scene, ob_eval, mask);  /* ob->derivedFinal */
1077                         }
1078                 }
1079                 else {
1080                         PyErr_Format(PyExc_ValueError,
1081                                      "%s(...): Cannot get evaluated data from given dependency graph / object pair", funcname);
1082                         return NULL;
1083                 }
1084         }
1085         else {
1086                 /* !use_deform */
1087                 if (use_render) {
1088                         if (use_cage) {
1089                                 PyErr_Format(PyExc_ValueError,
1090                                              "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", funcname);
1091                                 return NULL;
1092                         }
1093                         else {
1094                                 *r_free_mesh = true;
1095                                 return mesh_create_eval_no_deform_render(depsgraph, scene, ob, NULL, mask);
1096                         }
1097                 }
1098                 else {
1099                         if (use_cage) {
1100                                 PyErr_Format(PyExc_ValueError,
1101                                              "%s(...): cage arg is unsupported when deform=False and dependency graph evaluation mode is not RENDER", funcname);
1102                                 return NULL;
1103                         }
1104                         else {
1105                                 *r_free_mesh = true;
1106                                 return mesh_create_eval_no_deform(depsgraph, scene, ob, NULL, mask);
1107                         }
1108                 }
1109         }
1110 }
1111
1112 PyDoc_STRVAR(C_BVHTree_FromObject_doc,
1113 ".. classmethod:: FromObject(object, depsgraph, deform=True, render=False, cage=False, epsilon=0.0)\n"
1114 "\n"
1115 "   BVH tree based on :class:`Object` data.\n"
1116 "\n"
1117 "   :arg object: Object data.\n"
1118 "   :type object: :class:`Object`\n"
1119 "   :arg depsgraph: Depsgraph to use for evaluating the mesh.\n"
1120 "   :type depsgraph: :class:`Depsgraph`\n"
1121 "   :arg deform: Use mesh with deformations.\n"
1122 "   :type deform: bool\n"
1123 "   :arg cage: Use modifiers cage.\n"
1124 "   :type cage: bool\n"
1125 PYBVH_FROM_GENERIC_EPSILON_DOC
1126 );
1127 static PyObject *C_BVHTree_FromObject(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
1128 {
1129         /* note, options here match 'bpy_bmesh_from_object' */
1130         const char *keywords[] = {"object", "depsgraph", "deform", "cage", "epsilon", NULL};
1131
1132         PyObject *py_ob, *py_depsgraph;
1133         Object *ob;
1134         struct Depsgraph *depsgraph;
1135         struct Scene *scene;
1136         Mesh *mesh;
1137         bool use_deform = true;
1138         bool use_cage = false;
1139         bool free_mesh = false;
1140
1141         const MLoopTri *lt;
1142         const MLoop *mloop;
1143
1144         float (*coords)[3] = NULL;
1145         unsigned int (*tris)[3] = NULL;
1146         unsigned int coords_len, tris_len;
1147         float epsilon = 0.0f;
1148
1149         if (!PyArg_ParseTupleAndKeywords(
1150                 args, kwargs, (char *)"OO|$O&O&f:BVHTree.FromObject", (char **)keywords,
1151                 &py_ob, &py_depsgraph,
1152                 PyC_ParseBool, &use_deform,
1153                 PyC_ParseBool, &use_cage,
1154                 &epsilon) ||
1155             ((ob = PyC_RNA_AsPointer(py_ob, "Object")) == NULL) ||
1156             ((depsgraph = PyC_RNA_AsPointer(py_depsgraph, "Depsgraph")) == NULL))
1157         {
1158                 return NULL;
1159         }
1160
1161         scene = DEG_get_evaluated_scene(depsgraph);
1162         mesh = bvh_get_mesh("BVHTree", depsgraph, scene, ob, use_deform, use_cage, &free_mesh);
1163
1164         if (mesh == NULL) {
1165                 return NULL;
1166         }
1167
1168         /* Get data for tessellation */
1169         {
1170                 lt = BKE_mesh_runtime_looptri_ensure(mesh);
1171
1172                 tris_len = (unsigned int)BKE_mesh_runtime_looptri_len(mesh);
1173                 coords_len = (unsigned int)mesh->totvert;
1174
1175                 coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__);
1176                 tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__);
1177
1178                 MVert *mv = mesh->mvert;
1179                 for (int i = 0; i < mesh->totvert; i++, mv++) {
1180                         copy_v3_v3(coords[i], mv->co);
1181                 }
1182
1183                 mloop = mesh->mloop;
1184         }
1185
1186         {
1187                 BVHTree *tree;
1188                 unsigned int i;
1189
1190                 int *orig_index = NULL;
1191                 float (*orig_normal)[3] = NULL;
1192
1193                 tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
1194                 if (tree) {
1195                         orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__);
1196                         CustomData *pdata = &mesh->pdata;
1197                         orig_normal = CustomData_get_layer(pdata, CD_NORMAL); /* can be NULL */
1198                         if (orig_normal) {
1199                                 orig_normal = MEM_dupallocN(orig_normal);
1200                         }
1201
1202                         for (i = 0; i < tris_len; i++, lt++) {
1203                                 float co[3][3];
1204
1205                                 tris[i][0] = mloop[lt->tri[0]].v;
1206                                 tris[i][1] = mloop[lt->tri[1]].v;
1207                                 tris[i][2] = mloop[lt->tri[2]].v;
1208
1209                                 copy_v3_v3(co[0], coords[tris[i][0]]);
1210                                 copy_v3_v3(co[1], coords[tris[i][1]]);
1211                                 copy_v3_v3(co[2], coords[tris[i][2]]);
1212
1213                                 BLI_bvhtree_insert(tree, (int)i, co[0], 3);
1214                                 orig_index[i] = (int)lt->poly;
1215                         }
1216
1217                         BLI_bvhtree_balance(tree);
1218                 }
1219
1220                 if (free_mesh) {
1221                         BKE_id_free(NULL, mesh);
1222                 }
1223
1224                 return bvhtree_CreatePyObject(
1225                         tree, epsilon,
1226                         coords, coords_len,
1227                         tris, tris_len,
1228                         orig_index, orig_normal);
1229         }
1230 }
1231 #endif  /* MATH_STANDALONE */
1232
1233 /** \} */
1234
1235
1236 /* -------------------------------------------------------------------- */
1237 /** \name Module & Type definition
1238  * \{ */
1239
1240 static PyMethodDef py_bvhtree_methods[] = {
1241         {"ray_cast", (PyCFunction)py_bvhtree_ray_cast, METH_VARARGS, py_bvhtree_ray_cast_doc},
1242         {"find_nearest", (PyCFunction)py_bvhtree_find_nearest, METH_VARARGS, py_bvhtree_find_nearest_doc},
1243         {"find_nearest_range", (PyCFunction)py_bvhtree_find_nearest_range, METH_VARARGS, py_bvhtree_find_nearest_range_doc},
1244         {"overlap", (PyCFunction)py_bvhtree_overlap, METH_O, py_bvhtree_overlap_doc},
1245
1246         /* class methods */
1247         {"FromPolygons", (PyCFunction) C_BVHTree_FromPolygons, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromPolygons_doc},
1248 #ifndef MATH_STANDALONE
1249         {"FromBMesh", (PyCFunction) C_BVHTree_FromBMesh, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromBMesh_doc},
1250         {"FromObject", (PyCFunction) C_BVHTree_FromObject, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromObject_doc},
1251 #endif
1252         {NULL, NULL, 0, NULL}
1253 };
1254
1255 PyTypeObject PyBVHTree_Type = {
1256         PyVarObject_HEAD_INIT(NULL, 0)
1257         "BVHTree",                                   /* tp_name */
1258         sizeof(PyBVHTree),                           /* tp_basicsize */
1259         0,                                           /* tp_itemsize */
1260         /* methods */
1261         (destructor)py_bvhtree__tp_dealloc,          /* tp_dealloc */
1262         NULL,                                        /* tp_print */
1263         NULL,                                        /* tp_getattr */
1264         NULL,                                        /* tp_setattr */
1265         NULL,                                        /* tp_compare */
1266         NULL,                                        /* tp_repr */
1267         NULL,                                        /* tp_as_number */
1268         NULL,                                        /* tp_as_sequence */
1269         NULL,                                        /* tp_as_mapping */
1270         NULL,                                        /* tp_hash */
1271         NULL,                                        /* tp_call */
1272         NULL,                                        /* tp_str */
1273         NULL,                                        /* tp_getattro */
1274         NULL,                                        /* tp_setattro */
1275         NULL,                                        /* tp_as_buffer */
1276         Py_TPFLAGS_DEFAULT,                          /* tp_flags */
1277         NULL,                                        /* Documentation string */
1278         NULL,                                        /* tp_traverse */
1279         NULL,                                        /* tp_clear */
1280         NULL,                                        /* tp_richcompare */
1281         0,                                           /* tp_weaklistoffset */
1282         NULL,                                        /* tp_iter */
1283         NULL,                                        /* tp_iternext */
1284         py_bvhtree_methods,                          /* tp_methods */
1285         NULL,                                        /* tp_members */
1286         NULL,                                        /* tp_getset */
1287         NULL,                                        /* tp_base */
1288         NULL,                                        /* tp_dict */
1289         NULL,                                        /* tp_descr_get */
1290         NULL,                                        /* tp_descr_set */
1291         0,                                           /* tp_dictoffset */
1292         NULL,                                        /* tp_init */
1293         (allocfunc)PyType_GenericAlloc,              /* tp_alloc */
1294         (newfunc)PyType_GenericNew,                  /* tp_new */
1295         (freefunc)0,                                 /* tp_free */
1296         NULL,                                        /* tp_is_gc */
1297         NULL,                                        /* tp_bases */
1298         NULL,                                        /* tp_mro */
1299         NULL,                                        /* tp_cache */
1300         NULL,                                        /* tp_subclasses */
1301         NULL,                                        /* tp_weaklist */
1302         (destructor) NULL                            /* tp_del */
1303 };
1304
1305 /* -------------------------------------------------------------------- */
1306 /* Module definition */
1307
1308 PyDoc_STRVAR(py_bvhtree_doc,
1309 "BVH tree structures for proximity searches and ray casts on geometry."
1310 );
1311 static struct PyModuleDef bvhtree_moduledef = {
1312         PyModuleDef_HEAD_INIT,
1313         "mathutils.bvhtree",                         /* m_name */
1314         py_bvhtree_doc,                              /* m_doc */
1315         0,                                           /* m_size */
1316         NULL,                                        /* m_methods */
1317         NULL,                                        /* m_reload */
1318         NULL,                                        /* m_traverse */
1319         NULL,                                        /* m_clear */
1320         NULL                                         /* m_free */
1321 };
1322
1323 PyMODINIT_FUNC PyInit_mathutils_bvhtree(void)
1324 {
1325         PyObject *m = PyModule_Create(&bvhtree_moduledef);
1326
1327         if (m == NULL) {
1328                 return NULL;
1329         }
1330
1331         /* Register classes */
1332         if (PyType_Ready(&PyBVHTree_Type) < 0) {
1333                 return NULL;
1334         }
1335
1336         PyModule_AddObject(m, "BVHTree", (PyObject *)&PyBVHTree_Type);
1337
1338         return m;
1339 }
1340
1341 /** \} */