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