Blender V5.3
mathutils_bvhtree.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <Python.h>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_ghash.hh"
17#include "BLI_kdopbvh.hh"
18#include "BLI_math_geom_c.hh"
19#include "BLI_math_matrix_c.hh"
20#include "BLI_math_vector_c.hh"
21#include "BLI_memarena.hh"
22#include "BLI_polyfill_2d.hh"
23#include "BLI_utildefines.hh"
24
25#include "BKE_bvhutils.hh"
26
29
30#include "mathutils.hh"
31#include "mathutils_bvhtree.hh" /* own include */
32
33#ifndef MATH_STANDALONE
34# include "DNA_mesh_types.h"
35# include "DNA_object_types.h"
36
37# include "BKE_customdata.hh"
38# include "BKE_lib_id.hh"
39# include "BKE_mesh.hh"
40# include "BKE_mesh_runtime.hh"
41# include "BKE_object.hh"
42
43# include "DEG_depsgraph_query.hh"
44
45# include "bmesh.hh"
46
48#endif /* MATH_STANDALONE */
49
50#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
51
52namespace blender {
53
54/* -------------------------------------------------------------------- */
57
58#define PYBVH_FIND_GENERIC_DISTANCE_DOC \
59 " :param distance: Maximum distance threshold.\n" \
60 " :type distance: float\n"
61
62#define PYBVH_FIND_GENERIC_RETURN_DOC \
63 " :return: Returns a tuple: (position, normal, index, distance),\n" \
64 " Values will all be None if no hit is found.\n" \
65 " :rtype: tuple[:class:`Vector` | None, :class:`Vector` | None, int | None, float | None]\n"
66
67#define PYBVH_FIND_GENERIC_RETURN_LIST_DOC \
68 " :return: Returns a list of tuples (position, normal, index, distance)\n" \
69 " :rtype: list[tuple[:class:`Vector`, :class:`Vector`, int, float]]\n"
70
71#define PYBVH_FROM_GENERIC_EPSILON_DOC \
72 " :param epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \
73 " :type epsilon: float\n"
74
76
77/* sqrt(FLT_MAX) */
78#define PYBVH_MAX_DIST_STR "1.84467e+19"
79static const float max_dist_default = 1.844674352395373e+19f;
80
81static const char PY_BVH_TREE_TYPE_DEFAULT = 4;
82static const char PY_BVH_AXIS_DEFAULT = 6;
83
84struct PyBVHTree {
85 PyObject_HEAD
87 float epsilon;
88
90 uint (*tris)[3];
92
93 /* Optional members */
94 /* aligned with 'tris' */
96 /* aligned with array that 'orig_index' points to */
98};
99
100/* -------------------------------------------------------------------- */
103
104static PyObject *bvhtree_CreatePyObject(BVHTree *tree,
105 float epsilon,
106
107 float (*coords)[3],
108 uint coords_len,
109 uint (*tris)[3],
110 uint tris_len,
111
112 /* optional arrays */
113 int *orig_index,
114 float (*orig_normal)[3])
115{
116 PyBVHTree *result = PyObject_New(PyBVHTree, &PyBVHTree_Type);
117
118 result->tree = tree;
119 result->epsilon = epsilon;
120
121 result->coords = coords;
122 result->tris = tris;
123 result->coords_len = coords_len;
124 result->tris_len = tris_len;
125
126 result->orig_index = orig_index;
127 result->orig_normal = orig_normal;
128
129 return reinterpret_cast<PyObject *>(result);
130}
131
133
134/* -------------------------------------------------------------------- */
137
138static void py_bvhtree_raycast_to_py_tuple(const BVHTreeRayHit *hit, PyObject *py_retval)
139{
140 BLI_assert(hit->index >= 0);
141 BLI_assert(PyTuple_GET_SIZE(py_retval) == 4);
142
143 PyTuple_SET_ITEMS(py_retval,
144 Vector_CreatePyObject(hit->co, 3, nullptr),
145 Vector_CreatePyObject(hit->no, 3, nullptr),
146 PyLong_FromLong(hit->index),
147 PyFloat_FromDouble(hit->dist));
148}
149
150static PyObject *py_bvhtree_raycast_to_py(const BVHTreeRayHit *hit)
151{
152 PyObject *py_retval = PyTuple_New(4);
153
154 py_bvhtree_raycast_to_py_tuple(hit, py_retval);
155
156 return py_retval;
157}
158
160{
161 PyObject *py_retval = PyTuple_New(4);
162
163 PyC_Tuple_Fill(py_retval, Py_None);
164
165 return py_retval;
166}
167
168#if 0
169static PyObject *py_bvhtree_raycast_to_py_and_check(const BVHTreeRayHit *hit)
170{
171 PyObject *py_retval;
172
173 py_retval = PyTuple_New(4);
174
175 if (hit->index != -1) {
176 py_bvhtree_raycast_to_py_tuple(hit, py_retval);
177 }
178 else {
179 PyC_Tuple_Fill(py_retval, Py_None);
180 }
181
182 return py_retval;
183}
184#endif
185
187
188/* -------------------------------------------------------------------- */
191
192static void py_bvhtree_nearest_to_py_tuple(const BVHTreeNearest *nearest, PyObject *py_retval)
193{
194 BLI_assert(nearest->index >= 0);
195 BLI_assert(PyTuple_GET_SIZE(py_retval) == 4);
196
197 PyTuple_SET_ITEMS(py_retval,
198 Vector_CreatePyObject(nearest->co, 3, nullptr),
199 Vector_CreatePyObject(nearest->no, 3, nullptr),
200 PyLong_FromLong(nearest->index),
201 PyFloat_FromDouble(sqrtf(nearest->dist_sq)));
202}
203
204static PyObject *py_bvhtree_nearest_to_py(const BVHTreeNearest *nearest)
205{
206 PyObject *py_retval = PyTuple_New(4);
207
208 py_bvhtree_nearest_to_py_tuple(nearest, py_retval);
209
210 return py_retval;
211}
212
214{
215 PyObject *py_retval = PyTuple_New(4);
216
217 PyC_Tuple_Fill(py_retval, Py_None);
218
219 return py_retval;
220}
221
222#if 0
223static PyObject *py_bvhtree_nearest_to_py_and_check(const BVHTreeNearest *nearest)
224{
225 PyObject *py_retval;
226
227 py_retval = PyTuple_New(4);
228
229 if (nearest->index != -1) {
230 py_bvhtree_nearest_to_py_tuple(nearest, py_retval);
231 }
232 else {
233 PyC_Tuple_Fill(py_retval, Py_None);
234 }
235
236 return py_retval;
237}
238#endif
239
241
243{
244 if (self->tree) {
245 BLI_bvhtree_free(self->tree);
246 }
247
248 MEM_SAFE_DELETE(self->coords);
249 MEM_SAFE_DELETE(self->tris);
250
251 MEM_SAFE_DELETE(self->orig_index);
252 MEM_SAFE_DELETE(self->orig_normal);
253
254 Py_TYPE(self)->tp_free(reinterpret_cast<PyObject *>(self));
255}
256
257/* -------------------------------------------------------------------- */
260
261static void py_bvhtree_raycast_cb(void *userdata,
262 int index,
263 const BVHTreeRay *ray,
264 BVHTreeRayHit *hit)
265{
266 const PyBVHTree *self = static_cast<const PyBVHTree *>(userdata);
267
268 const float (*coords)[3] = self->coords;
269 const uint *tri = self->tris[index];
270 const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
271 float dist;
272
273 if (self->epsilon == 0.0f) {
274 dist = bke::bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(tri_co));
275 }
276 else {
277 dist = bke::bvhtree_sphereray_tri_intersection(ray, self->epsilon, hit->dist, UNPACK3(tri_co));
278 }
279
280 if (dist >= 0 && dist < hit->dist) {
281 hit->index = self->orig_index ? self->orig_index[index] : index;
282 hit->dist = dist;
283 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
284 if (self->orig_normal) {
285 copy_v3_v3(hit->no, self->orig_normal[hit->index]);
286 }
287 else {
288 normal_tri_v3(hit->no, UNPACK3(tri_co));
289 }
290 }
291}
292
293static void py_bvhtree_nearest_point_cb(void *userdata,
294 int index,
295 const float co[3],
296 BVHTreeNearest *nearest)
297{
298 PyBVHTree *self = static_cast<PyBVHTree *>(userdata);
299
300 const float (*coords)[3] = const_cast<const float (*)[3]>(self->coords);
301 const uint *tri = self->tris[index];
302 const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
303 float nearest_tmp[3], dist_sq;
304
305 closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co));
306 dist_sq = len_squared_v3v3(co, nearest_tmp);
307
308 if (dist_sq < nearest->dist_sq) {
309 nearest->index = self->orig_index ? self->orig_index[index] : index;
310 nearest->dist_sq = dist_sq;
311 copy_v3_v3(nearest->co, nearest_tmp);
312 if (self->orig_normal) {
313 copy_v3_v3(nearest->no, self->orig_normal[nearest->index]);
314 }
315 else {
316 normal_tri_v3(nearest->no, UNPACK3(tri_co));
317 }
318 }
319}
320
322 /* Wrap. */
323 py_bvhtree_ray_cast_doc,
324 ".. method:: ray_cast(origin, direction, distance=sys.float_info.max, /)\n"
325 "\n"
326 " Cast a ray onto the geometry.\n"
327 "\n"
328 " :param origin: Start location of the ray.\n"
329 " :type origin: :class:`Vector`\n"
330 " :param direction: Direction of the ray (normalized internally).\n"
331 " :type direction: :class:`Vector`\n" PYBVH_FIND_GENERIC_DISTANCE_DOC
333static PyObject *py_bvhtree_ray_cast(PyBVHTree *self, PyObject *args)
334{
335 const char *error_prefix = "ray_cast";
336 float co[3], direction[3];
337 float max_dist = FLT_MAX;
338 BVHTreeRayHit hit;
339
340 /* parse args */
341 {
342 PyObject *py_co, *py_direction;
343
344 if (!PyArg_ParseTuple(args,
345 "O" /* `origin` */
346 "O" /* `direction` */
347 "|" /* Optional arguments. */
348 "f" /* `distance` */
349 ":ray_cast",
350 &py_co,
351 &py_direction,
352 &max_dist))
353 {
354 return nullptr;
355 }
356
357 if ((mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) ||
358 (mathutils_array_parse(direction, 2, 3 | MU_ARRAY_ZERO, py_direction, error_prefix) == -1))
359 {
360 return nullptr;
361 }
362
363 normalize_v3(direction);
364 }
365
366 hit.dist = max_dist;
367 hit.index = -1;
368
369 /* may fail if the mesh has no faces, in that case the ray-cast misses */
370 if (self->tree) {
371 if (BLI_bvhtree_ray_cast(self->tree, co, direction, 0.0f, &hit, py_bvhtree_raycast_cb, self) !=
372 -1)
373 {
374 return py_bvhtree_raycast_to_py(&hit);
375 }
376 }
377
379}
380
382 /* Wrap. */
383 py_bvhtree_find_nearest_doc,
384 ".. method:: find_nearest(origin, distance=" PYBVH_MAX_DIST_STR
385 ", /)\n"
386 "\n"
387 " Find the nearest element (typically face index) to a point.\n"
388 "\n"
389 " :param origin: Find nearest element to this point.\n"
390 " :type origin: :class:`Vector`\n" PYBVH_FIND_GENERIC_DISTANCE_DOC
392static PyObject *py_bvhtree_find_nearest(PyBVHTree *self, PyObject *args)
393{
394 const char *error_prefix = "find_nearest";
395 float co[3];
396 float max_dist = max_dist_default;
397
398 BVHTreeNearest nearest;
399
400 /* parse args */
401 {
402 PyObject *py_co;
403
404 if (!PyArg_ParseTuple(args,
405 "O" /* `origin` */
406 "|" /* Optional arguments. */
407 "f" /* `distance` */
408 ":find_nearest",
409 &py_co,
410 &max_dist))
411 {
412 return nullptr;
413 }
414
415 if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) {
416 return nullptr;
417 }
418 }
419
420 nearest.index = -1;
421 nearest.dist_sq = max_dist * max_dist;
422
423 /* may fail if the mesh has no faces, in that case the ray-cast misses */
424 if (self->tree) {
425 if (BLI_bvhtree_find_nearest(self->tree, co, &nearest, py_bvhtree_nearest_point_cb, self) !=
426 -1)
427 {
428 return py_bvhtree_nearest_to_py(&nearest);
429 }
430 }
431
433}
434
437 PyObject *result;
438 float dist_sq;
439};
440
441static void py_bvhtree_nearest_point_range_cb(void *userdata,
442 int index,
443 const float co[3],
444 float /*dist_sq_bvh*/)
445{
446 PyBVH_RangeData *data = static_cast<PyBVH_RangeData *>(userdata);
447 PyBVHTree *self = data->self;
448
449 const float (*coords)[3] = self->coords;
450 const uint *tri = self->tris[index];
451 const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]};
452 float nearest_tmp[3], dist_sq;
453
454 closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co));
455 dist_sq = len_squared_v3v3(co, nearest_tmp);
456
457 if (dist_sq < data->dist_sq) {
458 BVHTreeNearest nearest;
459 nearest.index = self->orig_index ? self->orig_index[index] : index;
460 nearest.dist_sq = dist_sq;
461 copy_v3_v3(nearest.co, nearest_tmp);
462 if (self->orig_normal) {
463 copy_v3_v3(nearest.no, self->orig_normal[nearest.index]);
464 }
465 else {
466 normal_tri_v3(nearest.no, UNPACK3(tri_co));
467 }
468
469 PyList_APPEND(data->result, py_bvhtree_nearest_to_py(&nearest));
470 }
471}
472
474 /* Wrap. */
475 py_bvhtree_find_nearest_range_doc,
476 ".. method:: find_nearest_range(origin, distance=" PYBVH_MAX_DIST_STR
477 ", /)\n"
478 "\n"
479 " Find the nearest elements (typically face index) to a point in the distance range.\n"
480 "\n"
481 " :param origin: Find nearest elements to this point.\n"
482 " :type origin: :class:`Vector`\n" PYBVH_FIND_GENERIC_DISTANCE_DOC
484static PyObject *py_bvhtree_find_nearest_range(PyBVHTree *self, PyObject *args)
485{
486 const char *error_prefix = "find_nearest_range";
487 float co[3];
488 float max_dist = max_dist_default;
489
490 /* parse args */
491 {
492 PyObject *py_co;
493
494 if (!PyArg_ParseTuple(args,
495 "O" /* `origin` */
496 "|" /* Optional arguments. */
497 "f" /* `distance` */
498 ":find_nearest_range",
499 &py_co,
500 &max_dist))
501 {
502 return nullptr;
503 }
504
505 if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) {
506 return nullptr;
507 }
508 }
509
510 PyObject *ret = PyList_New(0);
511
512 if (self->tree) {
514 data.self = self;
515 data.result = ret;
516 data.dist_sq = square_f(max_dist);
518 }
519
520 return ret;
521}
522
523BLI_INLINE uint overlap_hash(const void *overlap_v)
524{
525 const BVHTreeOverlap *overlap = static_cast<const BVHTreeOverlap *>(overlap_v);
526 /* same constants as edge-hash */
527 return ((uint(overlap->indexA) * 65) ^ (uint(overlap->indexA) * 31));
528}
529
530BLI_INLINE bool overlap_cmp(const void *a_v, const void *b_v)
531{
532 const BVHTreeOverlap *a = static_cast<const BVHTreeOverlap *>(a_v);
533 const BVHTreeOverlap *b = static_cast<const BVHTreeOverlap *>(b_v);
534 return (memcmp(a, b, sizeof(*a)) != 0);
535}
536
541
542static bool py_bvhtree_overlap_cb(void *userdata, int index_a, int index_b, int /*thread*/)
543{
544 PyBVHTree_OverlapData *data = static_cast<PyBVHTree_OverlapData *>(userdata);
545 PyBVHTree *tree_a = data->tree_pair[0];
546 PyBVHTree *tree_b = data->tree_pair[1];
547 const uint *tri_a = tree_a->tris[index_a];
548 const uint *tri_b = tree_b->tris[index_b];
549 const float *tri_a_co[3] = {
550 tree_a->coords[tri_a[0]], tree_a->coords[tri_a[1]], tree_a->coords[tri_a[2]]};
551 const float *tri_b_co[3] = {
552 tree_b->coords[tri_b[0]], tree_b->coords[tri_b[1]], tree_b->coords[tri_b[2]]};
553 float ix_pair[2][3];
554 int verts_shared = 0;
555
556 if (tree_a == tree_b) {
557 if (index_a == index_b) [[unlikely]] {
558 return false;
559 }
560
561 verts_shared = (ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
562 ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
563
564 /* if 2 points are shared, bail out */
565 if (verts_shared >= 2) {
566 return false;
567 }
568 }
569
570 return (isect_tri_tri_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1]) &&
571 ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
572}
573
575 /* Wrap. */
576 py_bvhtree_overlap_doc,
577 ".. method:: overlap(other_tree, /)\n"
578 "\n"
579 " Find overlapping indices between 2 trees.\n"
580 "\n"
581 " :param other_tree: Other tree to perform overlap test on.\n"
582 " :type other_tree: :class:`BVHTree`\n"
583 " :return: Returns a list of unique index pairs,"
584 " the first index referencing this tree, the second referencing the **other_tree**.\n"
585 " :rtype: list[tuple[int, int]]\n");
586static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other)
587{
589 BVHTreeOverlap *overlap;
590 uint overlap_len = 0;
591 PyObject *ret;
592
593 if (!PyBVHTree_CheckExact(other)) {
594 PyErr_SetString(PyExc_ValueError, "Expected a BVHTree argument");
595 return nullptr;
596 }
597
598 data.tree_pair[0] = self;
599 data.tree_pair[1] = other;
600 data.epsilon = max_ff(self->epsilon, other->epsilon);
601
602 overlap = BLI_bvhtree_overlap(
603 self->tree, other->tree, &overlap_len, py_bvhtree_overlap_cb, &data);
604
605 ret = PyList_New(0);
606
607 if (overlap == nullptr) {
608 /* pass */
609 }
610 else {
611 const bool use_unique = (self->orig_index || other->orig_index);
612 Set<BVHTreeOverlap> pair_test;
613 if (use_unique) {
614 pair_test.reserve(overlap_len);
615 }
616 /* simple case, no index remapping */
617 uint i;
618
619 for (i = 0; i < overlap_len; i++) {
620 PyObject *item;
621 if (use_unique) {
622 if (self->orig_index) {
623 overlap[i].indexA = self->orig_index[overlap[i].indexA];
624 }
625 if (other->orig_index) {
626 overlap[i].indexB = other->orig_index[overlap[i].indexB];
627 }
628
629 /* skip if its already added */
630 if (!pair_test.add(overlap[i])) {
631 continue;
632 }
633 }
634
635 item = PyTuple_New(2);
637 item, PyLong_FromLong(overlap[i].indexA), PyLong_FromLong(overlap[i].indexB));
638
639 PyList_Append(ret, item);
640 Py_DECREF(item);
641 }
642 }
643
644 if (overlap) {
645 MEM_delete(overlap);
646 }
647
648 return ret;
649}
650
652
653/* -------------------------------------------------------------------- */
656
658 /* Wrap. */
659 C_BVHTree_FromPolygons_doc,
660 ".. classmethod:: FromPolygons(vertices, polygons, *, all_triangles=False, epsilon=0.0)\n"
661 "\n"
662 " BVH tree constructed from geometry passed in as arguments.\n"
663 "\n"
664 " :param vertices: float triplets each representing ``(x, y, z)`` coordinates.\n"
665 " :type vertices: Sequence[Sequence[float]]\n"
666 " :param polygons: Sequence of polygons, each containing indices to the vertices argument.\n"
667 " :type polygons: Sequence[Sequence[int]]\n"
668 " :param all_triangles: Use when all **polygons** are triangles for more efficient "
669 "conversion.\n"
670 " :type all_triangles: bool\n" PYBVH_FROM_GENERIC_EPSILON_DOC
671 " :return: BVHTree from polygon data.\n"
672 " :rtype: :class:`BVHTree`\n");
673static PyObject *C_BVHTree_FromPolygons(PyObject * /*cls*/, PyObject *args, PyObject *kwargs)
674{
675 const char *error_prefix = "BVHTree.FromPolygons";
676 const char *keywords[] = {"vertices", "polygons", "all_triangles", "epsilon", nullptr};
677
678 PyObject *py_coords, *py_tris;
679 PyObject *py_coords_fast = nullptr, *py_tris_fast = nullptr;
680
681 MemArena *poly_arena = nullptr;
682 MemArena *pf_arena = nullptr;
683
684 float (*coords)[3] = nullptr;
685 uint(*tris)[3] = nullptr;
686 uint coords_len, tris_len;
687 float epsilon = 0.0f;
688 bool all_triangles = false;
689
690 /* when all_triangles is False */
691 int *orig_index = nullptr;
692 float (*orig_normal)[3] = nullptr;
693
694 uint i;
695 bool valid = true;
696
697 if (!PyArg_ParseTupleAndKeywords(args,
698 kwargs,
699 "O" /* `vertices` */
700 "O" /* `polygons` */
701 "|$" /* Optional, keyword only arguments. */
702 "O&" /* `all_triangles` */
703 "f" /* `epsilon` */
704 ":BVHTree.FromPolygons",
705 const_cast<char **>(keywords),
706 &py_coords,
707 &py_tris,
709 &all_triangles,
710 &epsilon))
711 {
712 return nullptr;
713 }
714
715 if (!(py_coords_fast = PySequence_Fast(py_coords, error_prefix)) ||
716 !(py_tris_fast = PySequence_Fast(py_tris, error_prefix)))
717 {
718 Py_XDECREF(py_coords_fast);
719 return nullptr;
720 }
721
722 if (valid) {
723 PyObject **py_coords_fast_items = PySequence_Fast_ITEMS(py_coords_fast);
724 coords_len = uint(PySequence_Fast_GET_SIZE(py_coords_fast));
725 coords = MEM_new_array_uninitialized<float[3]>(size_t(coords_len), __func__);
726
727 for (i = 0; i < coords_len; i++) {
728 PyObject *py_vert = py_coords_fast_items[i];
729
730 if (mathutils_array_parse(coords[i], 3, 3, py_vert, "BVHTree vertex: ") == -1) {
731 valid = false;
732 break;
733 }
734 }
735 }
736
737 if (valid == false) {
738 /* pass */
739 }
740 else if (all_triangles) {
741 /* all triangles, simple case */
742 PyObject **py_tris_fast_items = PySequence_Fast_ITEMS(py_tris_fast);
743 tris_len = uint(PySequence_Fast_GET_SIZE(py_tris_fast));
744 tris = MEM_new_array_uninitialized<uint[3]>(size_t(tris_len), __func__);
745
746 for (i = 0; i < tris_len; i++) {
747 PyObject *py_tricoords = py_tris_fast_items[i];
748 PyObject *py_tricoords_fast;
749 PyObject **py_tricoords_fast_items;
750 uint *tri = tris[i];
751 int j;
752
753 if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) {
754 valid = false;
755 break;
756 }
757
758 const Py_ssize_t py_tricoords_num = PySequence_Fast_GET_SIZE(py_tricoords_fast);
759 if (py_tricoords_num != 3) {
760 Py_DECREF(py_tricoords_fast);
761 PyErr_Format(PyExc_ValueError,
762 "%s: non triangle found at index %d with length of %d",
763 error_prefix,
764 i,
765 py_tricoords_num);
766 valid = false;
767 break;
768 }
769
770 py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast);
771
772 for (j = 0; j < 3; j++) {
773 tri[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]);
774 if (tri[j] >= uint(coords_len)) [[unlikely]] {
775 PyErr_Format(PyExc_ValueError,
776 "%s: index %d must be less than %d",
777 error_prefix,
778 tri[j],
779 coords_len);
780
781 /* decref below */
782 valid = false;
783 break;
784 }
785 }
786
787 Py_DECREF(py_tricoords_fast);
788
789 if (!valid) {
790 /* Stop at the first bad triangle, else the error reported is the last one. */
791 break;
792 }
793 }
794 }
795 else {
796 /* ngon support (much more involved) */
797 const uint polys_len = uint(PySequence_Fast_GET_SIZE(py_tris_fast));
798 struct PolyLink {
799 PolyLink *next;
800 uint len;
801 uint poly[0];
802 } *plink_first = nullptr, **p_plink_prev = &plink_first, *plink = nullptr;
803 int poly_index;
804
805 tris_len = 0;
806
807 poly_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
808
809 for (i = 0; i < polys_len; i++) {
810 PyObject *py_tricoords = PySequence_Fast_GET_ITEM(py_tris_fast, i);
811 PyObject *py_tricoords_fast;
812 PyObject **py_tricoords_fast_items;
813 uint py_tricoords_len;
814 uint j;
815
816 if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) {
817 valid = false;
818 break;
819 }
820
821 py_tricoords_len = uint(PySequence_Fast_GET_SIZE(py_tricoords_fast));
822 py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast);
823
824 plink = static_cast<PolyLink *>(BLI_memarena_alloc(
825 poly_arena, sizeof(*plink) + (sizeof(int) * size_t(py_tricoords_len))));
826
827 plink->len = py_tricoords_len;
828 *p_plink_prev = plink;
829 p_plink_prev = &plink->next;
830
831 for (j = 0; j < py_tricoords_len; j++) {
832 plink->poly[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]);
833 if (plink->poly[j] >= uint(coords_len)) [[unlikely]] {
834 PyErr_Format(PyExc_ValueError,
835 "%s: index %d must be less than %d",
836 error_prefix,
837 plink->poly[j],
838 coords_len);
839 /* decref below */
840 valid = false;
841 break;
842 }
843 }
844
845 Py_DECREF(py_tricoords_fast);
846
847 if (!valid) {
848 break;
849 }
850
851 if (py_tricoords_len >= 3) {
852 tris_len += (py_tricoords_len - 2);
853 }
854 }
855 *p_plink_prev = nullptr;
856
857 /* All NGON's are parsed, now tessellate.
858 * Skipped when a polygon was rejected above as its indices are
859 * out of range or were never assigned. */
860 if (valid) {
861 pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
862 tris = MEM_new_array_uninitialized<uint[3]>(size_t(tris_len), __func__);
863
864 orig_index = MEM_new_array_uninitialized<int>(size_t(tris_len), __func__);
865 orig_normal = MEM_new_array_uninitialized<float[3]>(size_t(polys_len), __func__);
866
867 for (plink = plink_first, poly_index = 0, i = 0; plink; plink = plink->next, poly_index++) {
868 if (plink->len == 3) {
869 uint *tri = tris[i];
870 memcpy(tri, plink->poly, sizeof(uint[3]));
871 orig_index[i] = poly_index;
872 normal_tri_v3(orig_normal[poly_index], coords[tri[0]], coords[tri[1]], coords[tri[2]]);
873 i++;
874 }
875 else if (plink->len > 3) {
876 float (*proj_coords)[2] = static_cast<float (*)[2]>(
877 BLI_memarena_alloc(pf_arena, sizeof(*proj_coords) * plink->len));
878 float *normal = orig_normal[poly_index];
879 const float *co_prev;
880 const float *co_curr;
881 float axis_mat[3][3];
882 uint(*tris_offset)[3] = &tris[i];
883 uint j;
884
885 /* calc normal and setup 'proj_coords' */
886 zero_v3(normal);
887 co_prev = coords[plink->poly[plink->len - 1]];
888 for (j = 0; j < plink->len; j++) {
889 co_curr = coords[plink->poly[j]];
890 add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
891 co_prev = co_curr;
892 }
893 normalize_v3(normal);
894
895 axis_dominant_v3_to_m3_negate(axis_mat, normal);
896
897 for (j = 0; j < plink->len; j++) {
898 mul_v2_m3v3(proj_coords[j], axis_mat, coords[plink->poly[j]]);
899 }
900
901 BLI_polyfill_calc_arena(proj_coords, plink->len, 1, tris_offset, pf_arena);
902
903 j = plink->len - 2;
904 while (j--) {
905 uint *tri = tris_offset[j];
906 /* remap to global indices */
907 tri[0] = plink->poly[tri[0]];
908 tri[1] = plink->poly[tri[1]];
909 tri[2] = plink->poly[tri[2]];
910
911 orig_index[i] = poly_index;
912 i++;
913 }
914
915 BLI_memarena_clear(pf_arena);
916 }
917 else {
918 zero_v3(orig_normal[poly_index]);
919 }
920 }
921 }
922 }
923
924 Py_DECREF(py_coords_fast);
925 Py_DECREF(py_tris_fast);
926
927 if (pf_arena) {
928 BLI_memarena_free(pf_arena);
929 }
930
931 if (poly_arena) {
932 BLI_memarena_free(poly_arena);
933 }
934
935 if (valid) {
936 BVHTree *tree;
937
938 tree = BLI_bvhtree_new(int(tris_len), epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
939 if (tree) {
940 for (i = 0; i < tris_len; i++) {
941 float co[3][3];
942
943 copy_v3_v3(co[0], coords[tris[i][0]]);
944 copy_v3_v3(co[1], coords[tris[i][1]]);
945 copy_v3_v3(co[2], coords[tris[i][2]]);
946
947 BLI_bvhtree_insert(tree, int(i), co[0], 3);
948 }
949
951 }
952
954 tree, epsilon, coords, coords_len, tris, tris_len, orig_index, orig_normal);
955 }
956
957 if (coords) {
958 MEM_delete(coords);
959 }
960 if (tris) {
961 MEM_delete(tris);
962 }
963
964 return nullptr;
965}
966
967#ifndef MATH_STANDALONE
968
970 /* Wrap. */
971 C_BVHTree_FromBMesh_doc,
972 ".. classmethod:: FromBMesh(bmesh, *, epsilon=0.0)\n"
973 "\n"
974 " BVH tree based on :class:`BMesh` data.\n"
975 "\n"
976 " :param bmesh: BMesh data.\n"
977 " :type bmesh: :class:`BMesh`\n" PYBVH_FROM_GENERIC_EPSILON_DOC
978 " :return: BVHTree from BMesh data.\n"
979 " :rtype: :class:`BVHTree`\n");
980static PyObject *C_BVHTree_FromBMesh(PyObject * /*cls*/, PyObject *args, PyObject *kwargs)
981{
982 const char *keywords[] = {"bmesh", "epsilon", nullptr};
983
984 BPy_BMesh *py_bm;
985
986 float (*coords)[3] = nullptr;
987 uint(*tris)[3] = nullptr;
988 uint coords_len, tris_len;
989 float epsilon = 0.0f;
990
991 BMesh *bm;
992
993 if (!PyArg_ParseTupleAndKeywords(args,
994 kwargs,
995 "O!" /* `bmesh` */
996 "|$" /* Optional, keyword only arguments. */
997 "f" /* `epsilon` */
998 ":BVHTree.FromBMesh",
999 const_cast<char **>(keywords),
1001 &py_bm,
1002 &epsilon))
1003 {
1004 return nullptr;
1005 }
1006
1007 bm = py_bm->bm;
1008
1009 /* Get data for tessellation */
1010
1011 coords_len = uint(bm->totvert);
1012 tris_len = uint(poly_to_tri_count(bm->totface, bm->totloop));
1013
1014 coords = MEM_new_array_uninitialized<float[3]>(size_t(coords_len), __func__);
1015 tris = MEM_new_array_uninitialized<uint[3]>(size_t(tris_len), __func__);
1016
1017 Array<std::array<BMLoop *, 3>> corner_tris(tris_len);
1018 BM_mesh_calc_tessellation(bm, corner_tris);
1019
1020 {
1021 BMIter iter;
1022 BVHTree *tree;
1023 uint i;
1024
1025 int *orig_index = nullptr;
1026 float (*orig_normal)[3] = nullptr;
1027
1028 tree = BLI_bvhtree_new(int(tris_len), epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
1029 if (tree) {
1030 BMFace *f;
1031 BMVert *v;
1032
1033 orig_index = MEM_new_array_uninitialized<int>(size_t(tris_len), __func__);
1034 orig_normal = MEM_new_array_uninitialized<float[3]>(size_t(bm->totface), __func__);
1035
1036 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1037 copy_v3_v3(coords[i], v->co);
1038 BM_elem_index_set(v, int(i)); /* set_inline */
1039 }
1040 BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
1041 copy_v3_v3(orig_normal[i], f->no);
1042 BM_elem_index_set(f, int(i)); /* set_inline */
1043 }
1044 bm->elem_index_dirty &= char(~(BM_VERT | BM_FACE));
1045
1046 for (i = 0; i < tris_len; i++) {
1047 float co[3][3];
1048
1049 tris[i][0] = uint(BM_elem_index_get(corner_tris[i][0]->v));
1050 tris[i][1] = uint(BM_elem_index_get(corner_tris[i][1]->v));
1051 tris[i][2] = uint(BM_elem_index_get(corner_tris[i][2]->v));
1052
1053 copy_v3_v3(co[0], coords[tris[i][0]]);
1054 copy_v3_v3(co[1], coords[tris[i][1]]);
1055 copy_v3_v3(co[2], coords[tris[i][2]]);
1056
1057 BLI_bvhtree_insert(tree, int(i), co[0], 3);
1058 orig_index[i] = BM_elem_index_get(corner_tris[i][0]->f);
1059 }
1060
1061 BLI_bvhtree_balance(tree);
1062 }
1063
1065 tree, epsilon, coords, coords_len, tris, tris_len, orig_index, orig_normal);
1066 }
1067}
1068
1070static const Mesh *bvh_get_mesh(const char *funcname,
1071 Depsgraph *depsgraph,
1072 Scene *scene,
1073 Object *ob,
1074 const bool use_deform,
1075 const bool use_cage,
1076 bool *r_free_mesh)
1077{
1078 Object *ob_eval = DEG_get_evaluated(depsgraph, ob);
1079 /* we only need minimum mesh data for topology and vertex locations */
1080 const CustomData_MeshMasks data_masks = CD_MASK_BAREMESH;
1081 const bool use_render = DEG_get_mode(depsgraph) == DAG_EVAL_RENDER;
1082 *r_free_mesh = false;
1083 const Mesh *mesh;
1084
1085 /* Write the display mesh into the dummy mesh */
1086 if (use_deform) {
1087 if (use_render) {
1088 if (use_cage) {
1089 PyErr_Format(
1090 PyExc_ValueError,
1091 "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER",
1092 funcname);
1093 return nullptr;
1094 }
1095
1096 mesh = bke::mesh_create_eval_final(depsgraph, scene, ob, &data_masks);
1097 if (mesh == nullptr) {
1098 PyErr_Format(PyExc_ValueError,
1099 "%s(...): Cannot get a mesh from object '%s'",
1100 ob->id.name + 2,
1101 funcname);
1102 return nullptr;
1103 }
1104
1105 *r_free_mesh = true;
1106 return mesh;
1107 }
1108 if (ob_eval != nullptr) {
1109 if (use_cage) {
1110 mesh = bke::mesh_get_eval_deform(depsgraph, scene, ob_eval, &data_masks);
1111 }
1112 else {
1114 }
1115 if (mesh == nullptr) {
1116 PyErr_Format(PyExc_ValueError,
1117 "%s(...): Cannot get a mesh from object '%s'",
1118 ob->id.name + 2,
1119 funcname);
1120 return nullptr;
1121 }
1122 return mesh;
1123 }
1124
1125 PyErr_Format(PyExc_ValueError,
1126 "%s(...): Cannot get evaluated data from given dependency graph / object pair",
1127 funcname);
1128 return nullptr;
1129 }
1130
1131 /* !use_deform */
1132 if (use_render) {
1133 if (use_cage) {
1134 PyErr_Format(
1135 PyExc_ValueError,
1136 "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER",
1137 funcname);
1138 return nullptr;
1139 }
1140 mesh = bke::mesh_create_eval_no_deform_render(depsgraph, scene, ob, &data_masks);
1141 if (mesh == nullptr) {
1142 PyErr_Format(PyExc_ValueError,
1143 "%s(...): Cannot get a mesh from object '%s'",
1144 ob->id.name + 2,
1145 funcname);
1146 return nullptr;
1147 }
1148 *r_free_mesh = true;
1149 return mesh;
1150 }
1151
1152 if (use_cage) {
1153 PyErr_Format(PyExc_ValueError,
1154 "%s(...): cage arg is unsupported when deform=False and dependency graph "
1155 "evaluation mode is not RENDER",
1156 funcname);
1157 return nullptr;
1158 }
1159
1160 mesh = bke::mesh_create_eval_no_deform(depsgraph, scene, ob, &data_masks);
1161 if (mesh == nullptr) {
1162 PyErr_Format(PyExc_ValueError,
1163 "%s(...): Cannot get a mesh from object '%s'",
1164 ob->id.name + 2,
1165 funcname);
1166 return nullptr;
1167 }
1168 *r_free_mesh = true;
1169 return mesh;
1170}
1171
1173 /* Wrap. */
1174 C_BVHTree_FromObject_doc,
1175 ".. classmethod:: FromObject(object, depsgraph, *, deform=True, "
1176 "cage=False, epsilon=0.0)\n"
1177 "\n"
1178 " BVH tree based on :class:`Object` data.\n"
1179 "\n"
1180 " :param object: Mesh object.\n"
1181 " :type object: :class:`Object`\n"
1182 " :param depsgraph: Depsgraph to use for evaluating the mesh.\n"
1183 " :type depsgraph: :class:`Depsgraph`\n"
1184 " :param deform: Use mesh with deformations.\n"
1185 " :type deform: bool\n"
1186 " :param cage: Use modifiers cage.\n"
1187 " :type cage: bool\n" PYBVH_FROM_GENERIC_EPSILON_DOC
1188 " :return: BVHTree from Object data.\n"
1189 " :rtype: :class:`BVHTree`\n");
1190static PyObject *C_BVHTree_FromObject(PyObject * /*cls*/, PyObject *args, PyObject *kwargs)
1191{
1192 /* NOTE: options here match #bpy_bmesh_from_object. */
1193 const char *keywords[] = {"object", "depsgraph", "deform", "cage", "epsilon", nullptr};
1194
1195 PyObject *py_ob, *py_depsgraph;
1196 Object *ob;
1197 Depsgraph *depsgraph;
1198 Scene *scene;
1199 const Mesh *mesh;
1200 bool use_deform = true;
1201 bool use_cage = false;
1202 bool free_mesh = false;
1203
1204 float epsilon = 0.0f;
1205
1206 if (!PyArg_ParseTupleAndKeywords(args,
1207 kwargs,
1208 "O" /* `object` */
1209 "O" /* `depsgraph` */
1210 "|$" /* Optional, keyword only arguments. */
1211 "O&" /* `deform` */
1212 "O&" /* `cage` */
1213 "f" /* `epsilon` */
1214 ":BVHTree.FromObject",
1215 const_cast<char **>(keywords),
1216 &py_ob,
1217 &py_depsgraph,
1219 &use_deform,
1221 &use_cage,
1222 &epsilon) ||
1223 ((ob = static_cast<Object *>(PyC_RNA_AsPointer(py_ob, "Object"))) == nullptr) ||
1224 ((depsgraph = static_cast<Depsgraph *>(PyC_RNA_AsPointer(py_depsgraph, "Depsgraph"))) ==
1225 nullptr))
1226 {
1227 return nullptr;
1228 }
1229
1230 scene = DEG_get_evaluated_scene(depsgraph);
1231 mesh = bvh_get_mesh("BVHTree", depsgraph, scene, ob, use_deform, use_cage, &free_mesh);
1232
1233 if (mesh == nullptr) {
1234 return nullptr;
1235 }
1236
1237 const Span<int> corner_verts = mesh->corner_verts();
1238 const Span<int3> corner_tris = mesh->corner_tris();
1239 const Span<int> tri_faces = mesh->corner_tri_faces();
1240
1241 /* Get data for tessellation */
1242
1243 const uint coords_len = uint(mesh->verts_num);
1244
1245 float (*coords)[3] = MEM_new_array_uninitialized<float[3]>(size_t(coords_len), __func__);
1246 uint(*tris)[3] = MEM_new_array_uninitialized<uint[3]>(size_t(corner_tris.size()), __func__);
1247 memcpy(coords, mesh->vert_positions().data(), sizeof(float[3]) * size_t(mesh->verts_num));
1248
1249 BVHTree *tree;
1250
1251 int *orig_index = nullptr;
1252 float3 *orig_normal = nullptr;
1253
1254 tree = BLI_bvhtree_new(
1255 int(corner_tris.size()), epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT);
1256 if (tree) {
1257 orig_index = MEM_new_array_uninitialized<int>(size_t(corner_tris.size()), __func__);
1259 const Span<float3> face_normals = mesh->face_normals();
1260 orig_normal = MEM_new_array_uninitialized<float3>(size_t(mesh->faces_num), __func__);
1261 MutableSpan(orig_normal, face_normals.size()).copy_from(face_normals);
1262 }
1263
1264 for (const int64_t i : corner_tris.index_range()) {
1265 float co[3][3];
1266
1267 tris[i][0] = uint(corner_verts[corner_tris[i][0]]);
1268 tris[i][1] = uint(corner_verts[corner_tris[i][1]]);
1269 tris[i][2] = uint(corner_verts[corner_tris[i][2]]);
1270
1271 copy_v3_v3(co[0], coords[tris[i][0]]);
1272 copy_v3_v3(co[1], coords[tris[i][1]]);
1273 copy_v3_v3(co[2], coords[tris[i][2]]);
1274
1275 BLI_bvhtree_insert(tree, int(i), co[0], 3);
1276 orig_index[i] = int(tri_faces[i]);
1277 }
1278
1279 BLI_bvhtree_balance(tree);
1280 }
1281
1282 if (free_mesh) {
1283 BKE_id_free(nullptr, const_cast<Mesh *>(mesh));
1284 }
1285
1286 return bvhtree_CreatePyObject(tree,
1287 epsilon,
1288 coords,
1289 coords_len,
1290 tris,
1291 uint(corner_tris.size()),
1292 orig_index,
1293 reinterpret_cast<float (*)[3]>(orig_normal));
1294}
1295#endif /* MATH_STANDALONE */
1296
1298
1299/* -------------------------------------------------------------------- */
1302
1303#ifdef __GNUC__
1304# ifdef __clang__
1305# pragma clang diagnostic push
1306# pragma clang diagnostic ignored "-Wcast-function-type"
1307# else
1308# pragma GCC diagnostic push
1309# pragma GCC diagnostic ignored "-Wcast-function-type"
1310# endif
1311#endif
1312
1313static PyMethodDef py_bvhtree_methods[] = {
1314 {"ray_cast",
1315 reinterpret_cast<PyCFunction>(py_bvhtree_ray_cast),
1316 METH_VARARGS,
1317 py_bvhtree_ray_cast_doc},
1318 {"find_nearest",
1319 reinterpret_cast<PyCFunction>(py_bvhtree_find_nearest),
1320 METH_VARARGS,
1321 py_bvhtree_find_nearest_doc},
1322 {"find_nearest_range",
1323 reinterpret_cast<PyCFunction>(py_bvhtree_find_nearest_range),
1324 METH_VARARGS,
1325 py_bvhtree_find_nearest_range_doc},
1326 {"overlap", reinterpret_cast<PyCFunction>(py_bvhtree_overlap), METH_O, py_bvhtree_overlap_doc},
1327
1328 /* class methods */
1329 {"FromPolygons",
1330 reinterpret_cast<PyCFunction>(C_BVHTree_FromPolygons),
1331 METH_VARARGS | METH_KEYWORDS | METH_CLASS,
1332 C_BVHTree_FromPolygons_doc},
1333#ifndef MATH_STANDALONE
1334 {"FromBMesh",
1335 reinterpret_cast<PyCFunction>(C_BVHTree_FromBMesh),
1336 METH_VARARGS | METH_KEYWORDS | METH_CLASS,
1337 C_BVHTree_FromBMesh_doc},
1338 {"FromObject",
1339 reinterpret_cast<PyCFunction>(C_BVHTree_FromObject),
1340 METH_VARARGS | METH_KEYWORDS | METH_CLASS,
1341 C_BVHTree_FromObject_doc},
1342#endif
1343 {nullptr, nullptr, 0, nullptr},
1344};
1345
1346#ifdef __GNUC__
1347# ifdef __clang__
1348# pragma clang diagnostic pop
1349# else
1350# pragma GCC diagnostic pop
1351# endif
1352#endif
1353
1354PyTypeObject PyBVHTree_Type = {
1355 /*ob_base*/ PyVarObject_HEAD_INIT(nullptr, 0)
1356 /*tp_name*/ "BVHTree",
1357 /*tp_basicsize*/ sizeof(PyBVHTree),
1358 /*tp_itemsize*/ 0,
1359 /*tp_dealloc*/ reinterpret_cast<destructor>(py_bvhtree__tp_dealloc),
1360 /*tp_vectorcall_offset*/ 0,
1361 /*tp_getattr*/ nullptr,
1362 /*tp_setattr*/ nullptr,
1363 /*tp_as_async*/ nullptr,
1364 /*tp_repr*/ nullptr,
1365 /*tp_as_number*/ nullptr,
1366 /*tp_as_sequence*/ nullptr,
1367 /*tp_as_mapping*/ nullptr,
1368 /*tp_hash*/ nullptr,
1369 /*tp_call*/ nullptr,
1370 /*tp_str*/ nullptr,
1371 /*tp_getattro*/ nullptr,
1372 /*tp_setattro*/ nullptr,
1373 /*tp_as_buffer*/ nullptr,
1374 /*tp_flags*/ Py_TPFLAGS_DEFAULT,
1375 /*tp_doc*/ nullptr,
1376 /*tp_traverse*/ nullptr,
1377 /*tp_clear*/ nullptr,
1378 /*tp_richcompare*/ nullptr,
1379 /*tp_weaklistoffset*/ 0,
1380 /*tp_iter*/ nullptr,
1381 /*tp_iternext*/ nullptr,
1382 /*tp_methods*/ py_bvhtree_methods,
1383 /*tp_members*/ nullptr,
1384 /*tp_getset*/ nullptr,
1385 /*tp_base*/ nullptr,
1386 /*tp_dict*/ nullptr,
1387 /*tp_descr_get*/ nullptr,
1388 /*tp_descr_set*/ nullptr,
1389 /*tp_dictoffset*/ 0,
1390 /*tp_init*/ nullptr,
1391 /*tp_alloc*/ static_cast<allocfunc>(PyType_GenericAlloc),
1392 /*tp_new*/ static_cast<newfunc>(PyType_GenericNew),
1393 /*tp_free*/ static_cast<freefunc>(nullptr),
1394 /*tp_is_gc*/ nullptr,
1395 /*tp_bases*/ nullptr,
1396 /*tp_mro*/ nullptr,
1397 /*tp_cache*/ nullptr,
1398 /*tp_subclasses*/ nullptr,
1399 /*tp_weaklist*/ nullptr,
1400 /*tp_del*/ static_cast<destructor>(nullptr),
1401 /*tp_version_tag*/ 0,
1402 /*tp_finalize*/ nullptr,
1403 /*tp_vectorcall*/ nullptr,
1404};
1405
1406/* -------------------------------------------------------------------- */
1407/* Module definition */
1408
1410 /* Wrap. */
1411 py_bvhtree_doc,
1412 "BVH tree structures for proximity searches and ray casts on geometry.");
1413static PyModuleDef bvhtree_moduledef = {
1414 /*m_base*/ PyModuleDef_HEAD_INIT,
1415 /*m_name*/ "mathutils.bvhtree",
1416 /*m_doc*/ py_bvhtree_doc,
1417 /*m_size*/ 0,
1418 /*m_methods*/ nullptr,
1419 /*m_slots*/ nullptr,
1420 /*m_traverse*/ nullptr,
1421 /*m_clear*/ nullptr,
1422 /*m_free*/ nullptr,
1423};
1424
1426{
1427 /* Register classes */
1428 if (PyType_Ready(&PyBVHTree_Type) < 0) {
1429 return nullptr;
1430 }
1431
1432 PyObject *m = PyModule_Create(&bvhtree_moduledef);
1433
1434 if (m == nullptr) {
1435 return nullptr;
1436 }
1437
1438 PyModule_AddType(m, &PyBVHTree_Type);
1439
1440 return m;
1441}
1442
1444
1445} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
General operations, lookup, etc. for blender objects.
#define BLI_MEMARENA_STD_BUFSIZE
#define BLI_POLYFILL_ARENA_SIZE
Object is a sort of wrapper for general info.
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define UNPACK3(a)
#define ELEM(...)
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
constexpr MutableSpan()=default
void reserve(const int64_t n)
Definition BLI_set.hh:656
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
#define FLT_MAX
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
#define MU_ARRAY_ZERO
Definition mathutils.hh:261
#define PYBVH_FIND_GENERIC_RETURN_DOC
#define PYBVH_MAX_DIST_STR
#define PYBVH_FROM_GENERIC_EPSILON_DOC
#define PYBVH_FIND_GENERIC_DISTANCE_DOC
#define PYBVH_FIND_GENERIC_RETURN_LIST_DOC
#define PyBVHTree_CheckExact(v)
float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray, float radius, float m_dist, const float v0[3], const float v1[3], const float v2[3])
Definition bvhutils.cc:51
Mesh * mesh_create_eval_no_deform_render(Depsgraph *depsgraph, const Scene *scene, Object *ob, const CustomData_MeshMasks *dataMask)
Mesh * mesh_create_eval_no_deform(Depsgraph *depsgraph, const Scene *scene, Object *ob, const CustomData_MeshMasks *dataMask)
float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, float m_dist, const float v0[3], const float v1[3], const float v2[3])
Definition bvhutils.cc:30
const Mesh * mesh_get_eval_deform(Depsgraph *depsgraph, const Scene *scene, Object *ob, const CustomData_MeshMasks *dataMask)
Mesh * mesh_create_eval_final(Depsgraph *depsgraph, const Scene *scene, Object *ob, const CustomData_MeshMasks *dataMask)
BMesh Iterators.
static void py_bvhtree_nearest_to_py_tuple(const BVHTreeNearest *nearest, PyObject *py_retval)
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static PyObject * py_bvhtree_find_nearest(PyBVHTree *self, PyObject *args)
__int64 int64_t
Definition BKE_text.h:90
BLI_INLINE bool overlap_cmp(const void *a_v, const void *b_v)
const CustomData_MeshMasks CD_MASK_BAREMESH
int PyC_ParseBool(PyObject *o, void *p)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
bool isect_tri_tri_v3(const float t_a0[3], const float t_a1[3], const float t_a2[3], const float t_b0[3], const float t_b1[3], const float t_b2[3], float r_i1[3], float r_i2[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_bvhtree_free(BVHTree *tree)
PyDoc_STRVAR(bpy_bm_new_doc, ".. function:: new(*, use_operators=True)\n" "\n" " :param use_operators: Support calling operators in :mod:`bmesh.ops` (uses some " "extra memory per vert/edge/face).\n" " :type use_operators: bool\n" " :return: Return a new, empty BMesh.\n" " :rtype: :class:`bmesh.types.BMesh`\n")
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
void BLI_bvhtree_balance(BVHTree *tree)
static const char PY_BVH_TREE_TYPE_DEFAULT
static const Mesh * bvh_get_mesh(const char *funcname, Depsgraph *depsgraph, Scene *scene, Object *ob, const bool use_deform, const bool use_cage, bool *r_free_mesh)
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
static PyObject * C_BVHTree_FromPolygons(PyObject *, PyObject *args, PyObject *kwargs)
static PyObject * py_bvhtree_raycast_to_py_none()
static PyObject * py_bvhtree_ray_cast(PyBVHTree *self, PyObject *args)
PyTypeObject BPy_BMesh_Type
PyObject * Vector_CreatePyObject(const float *vec, const int vec_num, PyTypeObject *base_type)
static void py_bvhtree_raycast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
BMesh const char void * data
static PyMethodDef py_bvhtree_methods[]
T * DEG_get_evaluated(const Depsgraph *depsgraph, T *id)
static void py_bvhtree_nearest_point_range_cb(void *userdata, int index, const float co[3], float)
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
int BLI_bvhtree_range_query(const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
int mathutils_array_parse(float *array, int array_num_min, int array_num_max, PyObject *value, const char *error_prefix)
Definition mathutils.cc:97
PyMODINIT_FUNC PyInit_mathutils_bvhtree()
static void py_bvhtree_nearest_point_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
static PyObject * C_BVHTree_FromObject(PyObject *, PyObject *args, PyObject *kwargs)
void BM_mesh_calc_tessellation(BMesh *bm, MutableSpan< std::array< BMLoop *, 3 > > looptris)
static PyObject * py_bvhtree_nearest_to_py_none()
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
MINLINE void zero_v3(float r[3])
void BKE_id_free(Main *bmain, void *idv)
eEvaluationMode DEG_get_mode(const Depsgraph *graph)
static PyObject * py_bvhtree_find_nearest_range(PyBVHTree *self, PyObject *args)
static PyObject * C_BVHTree_FromBMesh(PyObject *, PyObject *args, PyObject *kwargs)
static const float max_dist_default
static const char PY_BVH_AXIS_DEFAULT
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
static PyObject * py_bvhtree_raycast_to_py(const BVHTreeRayHit *hit)
uint32_t PyC_Long_AsU32(PyObject *value)
void * PyC_RNA_AsPointer(PyObject *value, const char *type_name)
void PyC_Tuple_Fill(PyObject *tuple, PyObject *value)
MINLINE float max_ff(float a, float b)
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static void py_bvhtree__tp_dealloc(PyBVHTree *self)
MINLINE float square_f(float a)
BLI_INLINE uint overlap_hash(const void *overlap_v)
VecBase< float, 3 > float3
static PyObject * py_bvhtree_nearest_to_py(const BVHTreeNearest *nearest)
Scene * DEG_get_evaluated_scene(const Depsgraph *graph)
static PyModuleDef bvhtree_moduledef
static bool py_bvhtree_overlap_cb(void *userdata, int index_a, int index_b, int)
static PyObject * py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other)
bool BKE_mesh_face_normals_are_dirty(const Mesh *mesh)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
static void py_bvhtree_raycast_to_py_tuple(const BVHTreeRayHit *hit, PyObject *py_retval)
static PyObject * bvhtree_CreatePyObject(BVHTree *tree, float epsilon, float(*coords)[3], uint coords_len, uint(*tris)[3], uint tris_len, int *orig_index, float(*orig_normal)[3])
Mesh * BKE_object_get_evaluated_mesh(const Object *object_eval)
Definition object.cc:4436
PyTypeObject PyBVHTree_Type
header-only utilities
#define PyTuple_SET_ITEMS(op_arg,...)
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
PyObject_HEAD BMesh * bm
char name[258]
Definition DNA_ID.h:433
PyObject_HEAD BVHTree * tree