diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:17:24 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-04-17 07:21:24 +0300 |
commit | e12c08e8d170b7ca40f204a5b0423c23a9fbc2c1 (patch) | |
tree | 8cf3453d12edb177a218ef8009357518ec6cab6a /source/blender/python/mathutils/mathutils_bvhtree.c | |
parent | b3dabc200a4b0399ec6b81f2ff2730d07b44fcaa (diff) |
ClangFormat: apply to source, most of intern
Apply clang format as proposed in T53211.
For details on usage and instructions for migrating branches
without conflicts, see:
https://wiki.blender.org/wiki/Tools/ClangFormat
Diffstat (limited to 'source/blender/python/mathutils/mathutils_bvhtree.c')
-rw-r--r-- | source/blender/python/mathutils/mathutils_bvhtree.c | 2117 |
1 files changed, 1064 insertions, 1053 deletions
diff --git a/source/blender/python/mathutils/mathutils_bvhtree.c b/source/blender/python/mathutils/mathutils_bvhtree.c index b1420f316e6..cdb3035c0ca 100644 --- a/source/blender/python/mathutils/mathutils_bvhtree.c +++ b/source/blender/python/mathutils/mathutils_bvhtree.c @@ -38,52 +38,50 @@ #include "../generic/python_utildefines.h" #include "mathutils.h" -#include "mathutils_bvhtree.h" /* own include */ +#include "mathutils_bvhtree.h" /* own include */ #ifndef MATH_STANDALONE -#include "DNA_object_types.h" -#include "DNA_mesh_types.h" -#include "DNA_meshdata_types.h" +# include "DNA_object_types.h" +# include "DNA_mesh_types.h" +# include "DNA_meshdata_types.h" -#include "BKE_customdata.h" -#include "BKE_editmesh_bvh.h" -#include "BKE_library.h" -#include "BKE_mesh.h" -#include "BKE_mesh_runtime.h" +# include "BKE_customdata.h" +# include "BKE_editmesh_bvh.h" +# include "BKE_library.h" +# include "BKE_mesh.h" +# include "BKE_mesh_runtime.h" -#include "DEG_depsgraph_query.h" +# include "DEG_depsgraph_query.h" -#include "bmesh.h" - -#include "../bmesh/bmesh_py_types.h" -#endif /* MATH_STANDALONE */ +# include "bmesh.h" +# include "../bmesh/bmesh_py_types.h" +#endif /* MATH_STANDALONE */ #include "BLI_strict_flags.h" - /* -------------------------------------------------------------------- */ /** \name Docstring (snippets) * \{ */ #define PYBVH_FIND_GENERIC_DISTANCE_DOC \ -" :arg distance: Maximum distance threshold.\n" \ -" :type distance: float\n" + " :arg distance: Maximum distance threshold.\n" \ + " :type distance: float\n" #define PYBVH_FIND_GENERIC_RETURN_DOC \ -" :return: Returns a tuple\n" \ -" (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \ -" Values will all be None if no hit is found.\n" \ -" :rtype: :class:`tuple`\n" + " :return: Returns a tuple\n" \ + " (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \ + " Values will all be None if no hit is found.\n" \ + " :rtype: :class:`tuple`\n" #define PYBVH_FIND_GENERIC_RETURN_LIST_DOC \ -" :return: Returns a list of tuples\n" \ -" (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \ -" :rtype: :class:`list`\n" + " :return: Returns a list of tuples\n" \ + " (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \ + " :rtype: :class:`list`\n" #define PYBVH_FROM_GENERIC_EPSILON_DOC \ -" :arg epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \ -" :type epsilon: float\n" + " :arg epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \ + " :type epsilon: float\n" /** \} */ @@ -95,160 +93,157 @@ static const char PY_BVH_TREE_TYPE_DEFAULT = 4; static const char PY_BVH_AXIS_DEFAULT = 6; typedef struct { - PyObject_HEAD - BVHTree *tree; - float epsilon; - - float (*coords)[3]; - unsigned int (*tris)[3]; - unsigned int coords_len, tris_len; - - /* Optional members */ - /* aligned with 'tris' */ - int *orig_index; - /* aligned with array that 'orig_index' points to */ - float (*orig_normal)[3]; + PyObject_HEAD BVHTree *tree; + float epsilon; + + float (*coords)[3]; + unsigned int (*tris)[3]; + unsigned int coords_len, tris_len; + + /* Optional members */ + /* aligned with 'tris' */ + int *orig_index; + /* aligned with array that 'orig_index' points to */ + float (*orig_normal)[3]; } PyBVHTree; - /* -------------------------------------------------------------------- */ /** \name Utility helper functions * \{ */ -static PyObject *bvhtree_CreatePyObject( - BVHTree *tree, float epsilon, +static PyObject *bvhtree_CreatePyObject(BVHTree *tree, + float epsilon, - float (*coords)[3], unsigned int coords_len, - unsigned int (*tris)[3], unsigned int tris_len, + float (*coords)[3], + unsigned int coords_len, + unsigned int (*tris)[3], + unsigned int tris_len, - /* optional arrays */ - int *orig_index, float (*orig_normal)[3]) + /* optional arrays */ + int *orig_index, + float (*orig_normal)[3]) { - PyBVHTree *result = PyObject_New(PyBVHTree, &PyBVHTree_Type); + PyBVHTree *result = PyObject_New(PyBVHTree, &PyBVHTree_Type); - result->tree = tree; - result->epsilon = epsilon; + result->tree = tree; + result->epsilon = epsilon; - result->coords = coords; - result->tris = tris; - result->coords_len = coords_len; - result->tris_len = tris_len; + result->coords = coords; + result->tris = tris; + result->coords_len = coords_len; + result->tris_len = tris_len; - result->orig_index = orig_index; - result->orig_normal = orig_normal; + result->orig_index = orig_index; + result->orig_normal = orig_normal; - return (PyObject *)result; + return (PyObject *)result; } /** \} */ - /* -------------------------------------------------------------------- */ /** \name BVHTreeRayHit to Python utilities * \{ */ static void py_bvhtree_raycast_to_py_tuple(const BVHTreeRayHit *hit, PyObject *py_retval) { - BLI_assert(hit->index >= 0); - BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); - - PyTuple_SET_ITEMS(py_retval, - Vector_CreatePyObject(hit->co, 3, NULL), - Vector_CreatePyObject(hit->no, 3, NULL), - PyLong_FromLong(hit->index), - PyFloat_FromDouble(hit->dist)); - + BLI_assert(hit->index >= 0); + BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); + + PyTuple_SET_ITEMS(py_retval, + Vector_CreatePyObject(hit->co, 3, NULL), + Vector_CreatePyObject(hit->no, 3, NULL), + PyLong_FromLong(hit->index), + PyFloat_FromDouble(hit->dist)); } static PyObject *py_bvhtree_raycast_to_py(const BVHTreeRayHit *hit) { - PyObject *py_retval = PyTuple_New(4); + PyObject *py_retval = PyTuple_New(4); - py_bvhtree_raycast_to_py_tuple(hit, py_retval); + py_bvhtree_raycast_to_py_tuple(hit, py_retval); - return py_retval; + return py_retval; } static PyObject *py_bvhtree_raycast_to_py_none(void) { - PyObject *py_retval = PyTuple_New(4); + PyObject *py_retval = PyTuple_New(4); - PyC_Tuple_Fill(py_retval, Py_None); + PyC_Tuple_Fill(py_retval, Py_None); - return py_retval; + return py_retval; } #if 0 static PyObject *py_bvhtree_raycast_to_py_and_check(const BVHTreeRayHit *hit) { - PyObject *py_retval; + PyObject *py_retval; - py_retval = PyTuple_New(4); + py_retval = PyTuple_New(4); - if (hit->index != -1) { - py_bvhtree_raycast_to_py_tuple(hit, py_retval); - } - else { - PyC_Tuple_Fill(py_retval, Py_None); - } + if (hit->index != -1) { + py_bvhtree_raycast_to_py_tuple(hit, py_retval); + } + else { + PyC_Tuple_Fill(py_retval, Py_None); + } - return py_retval; + return py_retval; } #endif /** \} */ - /* -------------------------------------------------------------------- */ /** \name BVHTreeNearest to Python utilities * \{ */ static void py_bvhtree_nearest_to_py_tuple(const BVHTreeNearest *nearest, PyObject *py_retval) { - BLI_assert(nearest->index >= 0); - BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); - - PyTuple_SET_ITEMS(py_retval, - Vector_CreatePyObject(nearest->co, 3, NULL), - Vector_CreatePyObject(nearest->no, 3, NULL), - PyLong_FromLong(nearest->index), - PyFloat_FromDouble(sqrtf(nearest->dist_sq))); - + BLI_assert(nearest->index >= 0); + BLI_assert(PyTuple_GET_SIZE(py_retval) == 4); + + PyTuple_SET_ITEMS(py_retval, + Vector_CreatePyObject(nearest->co, 3, NULL), + Vector_CreatePyObject(nearest->no, 3, NULL), + PyLong_FromLong(nearest->index), + PyFloat_FromDouble(sqrtf(nearest->dist_sq))); } static PyObject *py_bvhtree_nearest_to_py(const BVHTreeNearest *nearest) { - PyObject *py_retval = PyTuple_New(4); + PyObject *py_retval = PyTuple_New(4); - py_bvhtree_nearest_to_py_tuple(nearest, py_retval); + py_bvhtree_nearest_to_py_tuple(nearest, py_retval); - return py_retval; + return py_retval; } static PyObject *py_bvhtree_nearest_to_py_none(void) { - PyObject *py_retval = PyTuple_New(4); + PyObject *py_retval = PyTuple_New(4); - PyC_Tuple_Fill(py_retval, Py_None); + PyC_Tuple_Fill(py_retval, Py_None); - return py_retval; + return py_retval; } #if 0 static PyObject *py_bvhtree_nearest_to_py_and_check(const BVHTreeNearest *nearest) { - PyObject *py_retval; + PyObject *py_retval; - py_retval = PyTuple_New(4); + py_retval = PyTuple_New(4); - if (nearest->index != -1) { - py_bvhtree_nearest_to_py_tuple(nearest, py_retval); - } - else { - PyC_Tuple_Fill(py_retval, Py_None); - } + if (nearest->index != -1) { + py_bvhtree_nearest_to_py_tuple(nearest, py_retval); + } + else { + PyC_Tuple_Fill(py_retval, Py_None); + } - return py_retval; + return py_retval; } #endif @@ -256,1082 +251,1098 @@ static PyObject *py_bvhtree_nearest_to_py_and_check(const BVHTreeNearest *neares static void py_bvhtree__tp_dealloc(PyBVHTree *self) { - if (self->tree) { - BLI_bvhtree_free(self->tree); - } + if (self->tree) { + BLI_bvhtree_free(self->tree); + } - MEM_SAFE_FREE(self->coords); - MEM_SAFE_FREE(self->tris); + MEM_SAFE_FREE(self->coords); + MEM_SAFE_FREE(self->tris); - MEM_SAFE_FREE(self->orig_index); - MEM_SAFE_FREE(self->orig_normal); + MEM_SAFE_FREE(self->orig_index); + MEM_SAFE_FREE(self->orig_normal); - Py_TYPE(self)->tp_free((PyObject *)self); + Py_TYPE(self)->tp_free((PyObject *)self); } - /* -------------------------------------------------------------------- */ /** \name Methods * \{ */ -static void py_bvhtree_raycast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +static void py_bvhtree_raycast_cb(void *userdata, + int index, + const BVHTreeRay *ray, + BVHTreeRayHit *hit) { - const PyBVHTree *self = userdata; - - const float (*coords)[3] = (const float (*)[3])self->coords; - const unsigned int *tri = self->tris[index]; - const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; - float dist; - - if (self->epsilon == 0.0f) { - dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(tri_co)); - } - else { - dist = bvhtree_sphereray_tri_intersection(ray, self->epsilon, hit->dist, UNPACK3(tri_co)); - } - - if (dist >= 0 && dist < hit->dist) { - hit->index = self->orig_index ? self->orig_index[index] : index; - hit->dist = dist; - madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist); - if (self->orig_normal) { - copy_v3_v3(hit->no, self->orig_normal[hit->index]); - } - else { - normal_tri_v3(hit->no, UNPACK3(tri_co)); - } - } + const PyBVHTree *self = userdata; + + const float(*coords)[3] = (const float(*)[3])self->coords; + const unsigned int *tri = self->tris[index]; + const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; + float dist; + + if (self->epsilon == 0.0f) { + dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(tri_co)); + } + else { + dist = bvhtree_sphereray_tri_intersection(ray, self->epsilon, hit->dist, UNPACK3(tri_co)); + } + + if (dist >= 0 && dist < hit->dist) { + hit->index = self->orig_index ? self->orig_index[index] : index; + hit->dist = dist; + madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist); + if (self->orig_normal) { + copy_v3_v3(hit->no, self->orig_normal[hit->index]); + } + else { + normal_tri_v3(hit->no, UNPACK3(tri_co)); + } + } } -static void py_bvhtree_nearest_point_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) +static void py_bvhtree_nearest_point_cb(void *userdata, + int index, + const float co[3], + BVHTreeNearest *nearest) { - PyBVHTree *self = userdata; - - const float (*coords)[3] = (const float (*)[3])self->coords; - const unsigned int *tri = self->tris[index]; - const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; - float nearest_tmp[3], dist_sq; - - closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co)); - dist_sq = len_squared_v3v3(co, nearest_tmp); - - if (dist_sq < nearest->dist_sq) { - nearest->index = self->orig_index ? self->orig_index[index] : index; - nearest->dist_sq = dist_sq; - copy_v3_v3(nearest->co, nearest_tmp); - if (self->orig_normal) { - copy_v3_v3(nearest->no, self->orig_normal[nearest->index]); - } - else { - normal_tri_v3(nearest->no, UNPACK3(tri_co)); - } - } + PyBVHTree *self = userdata; + + const float(*coords)[3] = (const float(*)[3])self->coords; + const unsigned int *tri = self->tris[index]; + const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; + float nearest_tmp[3], dist_sq; + + closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co)); + dist_sq = len_squared_v3v3(co, nearest_tmp); + + if (dist_sq < nearest->dist_sq) { + nearest->index = self->orig_index ? self->orig_index[index] : index; + nearest->dist_sq = dist_sq; + copy_v3_v3(nearest->co, nearest_tmp); + if (self->orig_normal) { + copy_v3_v3(nearest->no, self->orig_normal[nearest->index]); + } + else { + normal_tri_v3(nearest->no, UNPACK3(tri_co)); + } + } } 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 co: Start location of the ray in object space.\n" -" :type co: :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 -); + ".. method:: ray_cast(origin, direction, distance=sys.float_info.max)\n" + "\n" + " Cast a ray onto the mesh.\n" + "\n" + " :arg co: Start location of the ray in object space.\n" + " :type co: :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); static PyObject *py_bvhtree_ray_cast(PyBVHTree *self, PyObject *args) { - const char *error_prefix = "ray_cast"; - float co[3], direction[3]; - float max_dist = FLT_MAX; - BVHTreeRayHit hit; - - /* parse args */ - { - PyObject *py_co, *py_direction; - - if (!PyArg_ParseTuple( - args, (char *)"OO|f:ray_cast", - &py_co, &py_direction, &max_dist)) - { - return NULL; - } - - if ((mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) || - (mathutils_array_parse(direction, 2, 3 | MU_ARRAY_ZERO, py_direction, error_prefix) == -1)) - { - return NULL; - } - - normalize_v3(direction); - } - - hit.dist = max_dist; - hit.index = -1; - - /* may fail if the mesh has no faces, in that case the ray-cast misses */ - if (self->tree) { - if (BLI_bvhtree_ray_cast( - self->tree, co, direction, 0.0f, &hit, - py_bvhtree_raycast_cb, self) != -1) - { - return py_bvhtree_raycast_to_py(&hit); - } - } - - return py_bvhtree_raycast_to_py_none(); + const char *error_prefix = "ray_cast"; + float co[3], direction[3]; + float max_dist = FLT_MAX; + BVHTreeRayHit hit; + + /* parse args */ + { + PyObject *py_co, *py_direction; + + if (!PyArg_ParseTuple(args, (char *)"OO|f:ray_cast", &py_co, &py_direction, &max_dist)) { + return NULL; + } + + if ((mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) || + (mathutils_array_parse(direction, 2, 3 | MU_ARRAY_ZERO, py_direction, error_prefix) == + -1)) { + return NULL; + } + + normalize_v3(direction); + } + + hit.dist = max_dist; + hit.index = -1; + + /* may fail if the mesh has no faces, in that case the ray-cast misses */ + if (self->tree) { + if (BLI_bvhtree_ray_cast(self->tree, co, direction, 0.0f, &hit, py_bvhtree_raycast_cb, self) != + -1) { + return py_bvhtree_raycast_to_py(&hit); + } + } + + return py_bvhtree_raycast_to_py_none(); } PyDoc_STRVAR(py_bvhtree_find_nearest_doc, -".. method:: find_nearest(origin, distance=" PYBVH_MAX_DIST_STR ")\n" -"\n" -" Find the nearest element (typically face index) to a point.\n" -"\n" -" :arg co: Find nearest element to this point.\n" -" :type co: :class:`Vector`\n" -PYBVH_FIND_GENERIC_DISTANCE_DOC -PYBVH_FIND_GENERIC_RETURN_DOC -); + ".. method:: find_nearest(origin, distance=" PYBVH_MAX_DIST_STR + ")\n" + "\n" + " Find the nearest element (typically face index) to a point.\n" + "\n" + " :arg co: Find nearest element to this point.\n" + " :type co: :class:`Vector`\n" PYBVH_FIND_GENERIC_DISTANCE_DOC + PYBVH_FIND_GENERIC_RETURN_DOC); static PyObject *py_bvhtree_find_nearest(PyBVHTree *self, PyObject *args) { - const char *error_prefix = "find_nearest"; - float co[3]; - float max_dist = max_dist_default; - - BVHTreeNearest nearest; - - /* parse args */ - { - PyObject *py_co; - - if (!PyArg_ParseTuple( - args, (char *)"O|f:find_nearest", - &py_co, &max_dist)) - { - return NULL; - } - - if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) { - return NULL; - } - } - - nearest.index = -1; - nearest.dist_sq = max_dist * max_dist; - - /* may fail if the mesh has no faces, in that case the ray-cast misses */ - if (self->tree) { - if (BLI_bvhtree_find_nearest( - self->tree, co, &nearest, - py_bvhtree_nearest_point_cb, self) != -1) - { - return py_bvhtree_nearest_to_py(&nearest); - } - } - - return py_bvhtree_nearest_to_py_none(); + const char *error_prefix = "find_nearest"; + float co[3]; + float max_dist = max_dist_default; + + BVHTreeNearest nearest; + + /* parse args */ + { + PyObject *py_co; + + if (!PyArg_ParseTuple(args, (char *)"O|f:find_nearest", &py_co, &max_dist)) { + return NULL; + } + + if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) { + return NULL; + } + } + + nearest.index = -1; + nearest.dist_sq = max_dist * max_dist; + + /* may fail if the mesh has no faces, in that case the ray-cast misses */ + if (self->tree) { + if (BLI_bvhtree_find_nearest(self->tree, co, &nearest, py_bvhtree_nearest_point_cb, self) != + -1) { + return py_bvhtree_nearest_to_py(&nearest); + } + } + + return py_bvhtree_nearest_to_py_none(); } struct PyBVH_RangeData { - PyBVHTree *self; - PyObject *result; - float dist_sq; + PyBVHTree *self; + PyObject *result; + float dist_sq; }; -static void py_bvhtree_nearest_point_range_cb(void *userdata, int index, const float co[3], float UNUSED(dist_sq_bvh)) +static void py_bvhtree_nearest_point_range_cb(void *userdata, + int index, + const float co[3], + float UNUSED(dist_sq_bvh)) { - struct PyBVH_RangeData *data = userdata; - PyBVHTree *self = data->self; - - const float (*coords)[3] = (const float (*)[3])self->coords; - const unsigned int *tri = self->tris[index]; - const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; - float nearest_tmp[3], dist_sq; - - closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co)); - dist_sq = len_squared_v3v3(co, nearest_tmp); - - if (dist_sq < data->dist_sq) { - BVHTreeNearest nearest; - nearest.index = self->orig_index ? self->orig_index[index] : index; - nearest.dist_sq = dist_sq; - copy_v3_v3(nearest.co, nearest_tmp); - if (self->orig_normal) { - copy_v3_v3(nearest.no, self->orig_normal[nearest.index]); - } - else { - normal_tri_v3(nearest.no, UNPACK3(tri_co)); - } - - PyList_APPEND(data->result, py_bvhtree_nearest_to_py(&nearest)); - } + struct PyBVH_RangeData *data = userdata; + PyBVHTree *self = data->self; + + const float(*coords)[3] = (const float(*)[3])self->coords; + const unsigned int *tri = self->tris[index]; + const float *tri_co[3] = {coords[tri[0]], coords[tri[1]], coords[tri[2]]}; + float nearest_tmp[3], dist_sq; + + closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(tri_co)); + dist_sq = len_squared_v3v3(co, nearest_tmp); + + if (dist_sq < data->dist_sq) { + BVHTreeNearest nearest; + nearest.index = self->orig_index ? self->orig_index[index] : index; + nearest.dist_sq = dist_sq; + copy_v3_v3(nearest.co, nearest_tmp); + if (self->orig_normal) { + copy_v3_v3(nearest.no, self->orig_normal[nearest.index]); + } + else { + normal_tri_v3(nearest.no, UNPACK3(tri_co)); + } + + PyList_APPEND(data->result, py_bvhtree_nearest_to_py(&nearest)); + } } -PyDoc_STRVAR(py_bvhtree_find_nearest_range_doc, -".. method:: find_nearest_range(origin, distance=" PYBVH_MAX_DIST_STR ")\n" -"\n" -" Find the nearest elements (typically face index) to a point in the distance range.\n" -"\n" -" :arg co: Find nearest elements to this point.\n" -" :type co: :class:`Vector`\n" -PYBVH_FIND_GENERIC_DISTANCE_DOC -PYBVH_FIND_GENERIC_RETURN_LIST_DOC -); +PyDoc_STRVAR( + py_bvhtree_find_nearest_range_doc, + ".. method:: find_nearest_range(origin, distance=" PYBVH_MAX_DIST_STR + ")\n" + "\n" + " Find the nearest elements (typically face index) to a point in the distance range.\n" + "\n" + " :arg co: Find nearest elements to this point.\n" + " :type co: :class:`Vector`\n" PYBVH_FIND_GENERIC_DISTANCE_DOC + PYBVH_FIND_GENERIC_RETURN_LIST_DOC); static PyObject *py_bvhtree_find_nearest_range(PyBVHTree *self, PyObject *args) { - const char *error_prefix = "find_nearest_range"; - float co[3]; - float max_dist = max_dist_default; - - /* parse args */ - { - PyObject *py_co; - - if (!PyArg_ParseTuple( - args, (char *)"O|f:find_nearest_range", - &py_co, &max_dist)) - { - return NULL; - } - - if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) { - return NULL; - } - } - - PyObject *ret = PyList_New(0); - - if (self->tree) { - struct PyBVH_RangeData data = { - .self = self, - .result = ret, - .dist_sq = SQUARE(max_dist), - }; - - BLI_bvhtree_range_query( - self->tree, co, max_dist, - py_bvhtree_nearest_point_range_cb, &data); - } - - return ret; -} + const char *error_prefix = "find_nearest_range"; + float co[3]; + float max_dist = max_dist_default; + + /* parse args */ + { + PyObject *py_co; + + if (!PyArg_ParseTuple(args, (char *)"O|f:find_nearest_range", &py_co, &max_dist)) { + return NULL; + } + + if (mathutils_array_parse(co, 2, 3 | MU_ARRAY_ZERO, py_co, error_prefix) == -1) { + return NULL; + } + } + + PyObject *ret = PyList_New(0); + if (self->tree) { + struct PyBVH_RangeData data = { + .self = self, + .result = ret, + .dist_sq = SQUARE(max_dist), + }; + + BLI_bvhtree_range_query(self->tree, co, max_dist, py_bvhtree_nearest_point_range_cb, &data); + } + + return ret; +} BLI_INLINE unsigned int overlap_hash(const void *overlap_v) { - const BVHTreeOverlap *overlap = overlap_v; - /* same constants as edge-hash */ - return (((unsigned int)overlap->indexA * 65) ^ ((unsigned int)overlap->indexA * 31)); + const BVHTreeOverlap *overlap = overlap_v; + /* same constants as edge-hash */ + return (((unsigned int)overlap->indexA * 65) ^ ((unsigned int)overlap->indexA * 31)); } BLI_INLINE bool overlap_cmp(const void *a_v, const void *b_v) { - const BVHTreeOverlap *a = a_v; - const BVHTreeOverlap *b = b_v; - return (memcmp(a, b, sizeof(*a)) != 0); + const BVHTreeOverlap *a = a_v; + const BVHTreeOverlap *b = b_v; + return (memcmp(a, b, sizeof(*a)) != 0); } struct PyBVHTree_OverlapData { - PyBVHTree *tree_pair[2]; - float epsilon; + PyBVHTree *tree_pair[2]; + float epsilon; }; static bool py_bvhtree_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread)) { - struct PyBVHTree_OverlapData *data = userdata; - PyBVHTree *tree_a = data->tree_pair[0]; - PyBVHTree *tree_b = data->tree_pair[1]; - const unsigned int *tri_a = tree_a->tris[index_a]; - const unsigned int *tri_b = tree_b->tris[index_b]; - const float *tri_a_co[3] = {tree_a->coords[tri_a[0]], tree_a->coords[tri_a[1]], tree_a->coords[tri_a[2]]}; - const float *tri_b_co[3] = {tree_b->coords[tri_b[0]], tree_b->coords[tri_b[1]], tree_b->coords[tri_b[2]]}; - float ix_pair[2][3]; - int verts_shared = 0; - - if (tree_a == tree_b) { - if (UNLIKELY(index_a == index_b)) { - return false; - } - - verts_shared = ( - ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + - ELEM(tri_a_co[1], UNPACK3(tri_b_co)) + - ELEM(tri_a_co[2], UNPACK3(tri_b_co))); - - /* if 2 points are shared, bail out */ - if (verts_shared >= 2) { - return false; - } - } - - return (isect_tri_tri_epsilon_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) && - ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon))); + struct PyBVHTree_OverlapData *data = userdata; + PyBVHTree *tree_a = data->tree_pair[0]; + PyBVHTree *tree_b = data->tree_pair[1]; + const unsigned int *tri_a = tree_a->tris[index_a]; + const unsigned int *tri_b = tree_b->tris[index_b]; + const float *tri_a_co[3] = { + tree_a->coords[tri_a[0]], tree_a->coords[tri_a[1]], tree_a->coords[tri_a[2]]}; + const float *tri_b_co[3] = { + tree_b->coords[tri_b[0]], tree_b->coords[tri_b[1]], tree_b->coords[tri_b[2]]}; + float ix_pair[2][3]; + int verts_shared = 0; + + if (tree_a == tree_b) { + if (UNLIKELY(index_a == index_b)) { + return false; + } + + verts_shared = (ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + ELEM(tri_a_co[1], UNPACK3(tri_b_co)) + + ELEM(tri_a_co[2], UNPACK3(tri_b_co))); + + /* if 2 points are shared, bail out */ + if (verts_shared >= 2) { + return false; + } + } + + return (isect_tri_tri_epsilon_v3( + UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) && + ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon))); } -PyDoc_STRVAR(py_bvhtree_overlap_doc, -".. method:: overlap(other_tree)\n" -"\n" -" Find overlapping indices between 2 trees.\n" -"\n" -" :arg other_tree: Other tree to perform overlap test on.\n" -" :type other_tree: :class:`BVHTree`\n" -" :return: Returns a list of unique index pairs," -" the first index referencing this tree, the second referencing the **other_tree**.\n" -" :rtype: :class:`list`\n" -); +PyDoc_STRVAR( + py_bvhtree_overlap_doc, + ".. method:: overlap(other_tree)\n" + "\n" + " Find overlapping indices between 2 trees.\n" + "\n" + " :arg other_tree: Other tree to perform overlap test on.\n" + " :type other_tree: :class:`BVHTree`\n" + " :return: Returns a list of unique index pairs," + " the first index referencing this tree, the second referencing the **other_tree**.\n" + " :rtype: :class:`list`\n"); static PyObject *py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other) { - struct PyBVHTree_OverlapData data; - BVHTreeOverlap *overlap; - unsigned int overlap_len = 0; - PyObject *ret; - - if (!PyBVHTree_CheckExact(other)) { - PyErr_SetString(PyExc_ValueError, "Expected a BVHTree argument"); - return NULL; - } - - data.tree_pair[0] = self; - data.tree_pair[1] = other; - data.epsilon = max_ff(self->epsilon, other->epsilon); - - overlap = BLI_bvhtree_overlap(self->tree, other->tree, &overlap_len, py_bvhtree_overlap_cb, &data); - - ret = PyList_New(0); - - if (overlap == NULL) { - /* pass */ - } - else { - bool use_unique = (self->orig_index || other->orig_index); - GSet *pair_test = use_unique ? BLI_gset_new_ex(overlap_hash, overlap_cmp, __func__, overlap_len) : NULL; - /* simple case, no index remapping */ - unsigned int i; - - for (i = 0; i < overlap_len; i++) { - PyObject *item; - if (use_unique) { - if (self->orig_index) { - overlap[i].indexA = self->orig_index[overlap[i].indexA]; - } - if (other->orig_index) { - overlap[i].indexB = other->orig_index[overlap[i].indexB]; - } - - /* skip if its already added */ - if (!BLI_gset_add(pair_test, &overlap[i])) { - continue; - } - } - - item = PyTuple_New(2); - PyTuple_SET_ITEMS(item, - PyLong_FromLong(overlap[i].indexA), - PyLong_FromLong(overlap[i].indexB)); - - PyList_Append(ret, item); - Py_DECREF(item); - } - - if (pair_test) { - BLI_gset_free(pair_test, NULL); - } - } - - if (overlap) { - MEM_freeN(overlap); - } - - return ret; + struct PyBVHTree_OverlapData data; + BVHTreeOverlap *overlap; + unsigned int overlap_len = 0; + PyObject *ret; + + if (!PyBVHTree_CheckExact(other)) { + PyErr_SetString(PyExc_ValueError, "Expected a BVHTree argument"); + return NULL; + } + + data.tree_pair[0] = self; + data.tree_pair[1] = other; + data.epsilon = max_ff(self->epsilon, other->epsilon); + + overlap = BLI_bvhtree_overlap( + self->tree, other->tree, &overlap_len, py_bvhtree_overlap_cb, &data); + + ret = PyList_New(0); + + if (overlap == NULL) { + /* pass */ + } + else { + bool use_unique = (self->orig_index || other->orig_index); + GSet *pair_test = use_unique ? + BLI_gset_new_ex(overlap_hash, overlap_cmp, __func__, overlap_len) : + NULL; + /* simple case, no index remapping */ + unsigned int i; + + for (i = 0; i < overlap_len; i++) { + PyObject *item; + if (use_unique) { + if (self->orig_index) { + overlap[i].indexA = self->orig_index[overlap[i].indexA]; + } + if (other->orig_index) { + overlap[i].indexB = other->orig_index[overlap[i].indexB]; + } + + /* skip if its already added */ + if (!BLI_gset_add(pair_test, &overlap[i])) { + continue; + } + } + + item = PyTuple_New(2); + PyTuple_SET_ITEMS( + item, PyLong_FromLong(overlap[i].indexA), PyLong_FromLong(overlap[i].indexB)); + + PyList_Append(ret, item); + Py_DECREF(item); + } + + if (pair_test) { + BLI_gset_free(pair_test, NULL); + } + } + + if (overlap) { + MEM_freeN(overlap); + } + + return ret; } /** \} */ - /* -------------------------------------------------------------------- */ /** \name Class Methods * \{ */ -PyDoc_STRVAR(C_BVHTree_FromPolygons_doc, -".. classmethod:: FromPolygons(vertices, polygons, all_triangles=False, epsilon=0.0)\n" -"\n" -" BVH tree constructed geometry passed in as arguments.\n" -"\n" -" :arg vertices: float triplets each representing ``(x, y, z)``\n" -" :type vertices: float triplet sequence\n" -" :arg polygons: Sequence of polyugons, each containing indices to the vertices argument.\n" -" :type polygons: Sequence of sequences containing ints\n" -" :arg all_triangles: Use when all **polygons** are triangles for more efficient conversion.\n" -" :type all_triangles: bool\n" -PYBVH_FROM_GENERIC_EPSILON_DOC -); +PyDoc_STRVAR( + C_BVHTree_FromPolygons_doc, + ".. classmethod:: FromPolygons(vertices, polygons, all_triangles=False, epsilon=0.0)\n" + "\n" + " BVH tree constructed geometry passed in as arguments.\n" + "\n" + " :arg vertices: float triplets each representing ``(x, y, z)``\n" + " :type vertices: float triplet sequence\n" + " :arg polygons: Sequence of polyugons, each containing indices to the vertices argument.\n" + " :type polygons: Sequence of sequences containing ints\n" + " :arg all_triangles: Use when all **polygons** are triangles for more efficient " + "conversion.\n" + " :type all_triangles: bool\n" PYBVH_FROM_GENERIC_EPSILON_DOC); static PyObject *C_BVHTree_FromPolygons(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs) { - const char *error_prefix = "BVHTree.FromPolygons"; - const char *keywords[] = {"vertices", "polygons", "all_triangles", "epsilon", NULL}; - - PyObject *py_coords, *py_tris; - PyObject *py_coords_fast = NULL, *py_tris_fast = NULL; - - MemArena *poly_arena = NULL; - MemArena *pf_arena = NULL; - - float (*coords)[3] = NULL; - unsigned int (*tris)[3] = NULL; - unsigned int coords_len, tris_len; - float epsilon = 0.0f; - bool all_triangles = false; - - /* when all_triangles is False */ - int *orig_index = NULL; - float (*orig_normal)[3] = NULL; - - unsigned int i; - bool valid = true; - - - if (!PyArg_ParseTupleAndKeywords( - args, kwargs, (char *)"OO|$O&f:BVHTree.FromPolygons", (char **)keywords, - &py_coords, &py_tris, - PyC_ParseBool, &all_triangles, - &epsilon)) - { - return NULL; - } - - if (!(py_coords_fast = PySequence_Fast(py_coords, error_prefix)) || - !(py_tris_fast = PySequence_Fast(py_tris, error_prefix))) - { - Py_XDECREF(py_coords_fast); - return NULL; - } - - if (valid) { - PyObject **py_coords_fast_items = PySequence_Fast_ITEMS(py_coords_fast); - coords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_coords_fast); - coords = MEM_mallocN((size_t)coords_len * sizeof(*coords), __func__); - - for (i = 0; i < coords_len; i++) { - PyObject *py_vert = py_coords_fast_items[i]; - - if (mathutils_array_parse(coords[i], 3, 3, py_vert, "BVHTree vertex: ") == -1) { - valid = false; - break; - } - } - } - - if (valid == false) { - /* pass */ - } - else if (all_triangles) { - /* all triangles, simple case */ - PyObject **py_tris_fast_items = PySequence_Fast_ITEMS(py_tris_fast); - tris_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast); - tris = MEM_mallocN((size_t)tris_len * sizeof(*tris), __func__); - - for (i = 0; i < tris_len; i++) { - PyObject *py_tricoords = py_tris_fast_items[i]; - PyObject *py_tricoords_fast; - PyObject **py_tricoords_fast_items; - unsigned int *tri = tris[i]; - int j; - - if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) { - valid = false; - break; - } - - if (PySequence_Fast_GET_SIZE(py_tricoords_fast) != 3) { - Py_DECREF(py_tricoords_fast); - PyErr_Format(PyExc_ValueError, - "%s: non triangle found at index %d with length of %d", - error_prefix, i, PySequence_Fast_GET_SIZE(py_tricoords_fast)); - valid = false; - break; - } - - py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast); - - for (j = 0; j < 3; j++) { - tri[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]); - if (UNLIKELY(tri[j] >= (unsigned int)coords_len)) { - PyErr_Format(PyExc_ValueError, - "%s: index %d must be less than %d", - error_prefix, tri[j], coords_len); - - /* decref below */ - valid = false; - break; - } - } - - Py_DECREF(py_tricoords_fast); - } - } - else { - /* ngon support (much more involved) */ - const unsigned int polys_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast); - struct PolyLink { - struct PolyLink *next; - unsigned int len; - unsigned int poly[0]; - } *plink_first = NULL, **p_plink_prev = &plink_first, *plink = NULL; - int poly_index; - - tris_len = 0; - - poly_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); - - for (i = 0; i < polys_len; i++) { - PyObject *py_tricoords = PySequence_Fast_GET_ITEM(py_tris_fast, i); - PyObject *py_tricoords_fast; - PyObject **py_tricoords_fast_items; - unsigned int py_tricoords_len; - unsigned int j; - - if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) { - valid = false; - break; - } - - py_tricoords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tricoords_fast); - py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast); - - plink = BLI_memarena_alloc(poly_arena, sizeof(*plink) + (sizeof(int) * (size_t)py_tricoords_len)); - - plink->len = (unsigned int)py_tricoords_len; - *p_plink_prev = plink; - p_plink_prev = &plink->next; - - for (j = 0; j < py_tricoords_len; j++) { - plink->poly[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]); - if (UNLIKELY(plink->poly[j] >= (unsigned int)coords_len)) { - PyErr_Format(PyExc_ValueError, - "%s: index %d must be less than %d", - error_prefix, plink->poly[j], coords_len); - /* decref below */ - valid = false; - break; - } - } - - Py_DECREF(py_tricoords_fast); - - if (py_tricoords_len >= 3) { - tris_len += (py_tricoords_len - 2); - } - } - *p_plink_prev = NULL; - - /* all ngon's are parsed, now tessellate */ - - pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); - tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); - - orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); - orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)polys_len, __func__); - - for (plink = plink_first, poly_index = 0, i = 0; plink; plink = plink->next, poly_index++) { - if (plink->len == 3) { - unsigned int *tri = tris[i]; - memcpy(tri, plink->poly, sizeof(unsigned int[3])); - orig_index[i] = poly_index; - normal_tri_v3(orig_normal[poly_index], coords[tri[0]], coords[tri[1]], coords[tri[2]]); - i++; - } - else if (plink->len > 3) { - float (*proj_coords)[2] = BLI_memarena_alloc(pf_arena, sizeof(*proj_coords) * plink->len); - float *normal = orig_normal[poly_index]; - const float *co_prev; - const float *co_curr; - float axis_mat[3][3]; - unsigned int (*tris_offset)[3] = &tris[i]; - unsigned int j; - - /* calc normal and setup 'proj_coords' */ - zero_v3(normal); - co_prev = coords[plink->poly[plink->len - 1]]; - for (j = 0; j < plink->len; j++) { - co_curr = coords[plink->poly[j]]; - add_newell_cross_v3_v3v3(normal, co_prev, co_curr); - co_prev = co_curr; - } - normalize_v3(normal); - - axis_dominant_v3_to_m3_negate(axis_mat, normal); - - for (j = 0; j < plink->len; j++) { - mul_v2_m3v3(proj_coords[j], axis_mat, coords[plink->poly[j]]); - } - - BLI_polyfill_calc_arena(proj_coords, plink->len, 1, tris_offset, pf_arena); - - j = plink->len - 2; - while (j--) { - unsigned int *tri = tris_offset[j]; - /* remap to global indices */ - tri[0] = plink->poly[tri[0]]; - tri[1] = plink->poly[tri[1]]; - tri[2] = plink->poly[tri[2]]; - - orig_index[i] = poly_index; - i++; - } - - BLI_memarena_clear(pf_arena); - } - else { - zero_v3(orig_normal[poly_index]); - } - } - } - - Py_DECREF(py_coords_fast); - Py_DECREF(py_tris_fast); - - if (pf_arena) { - BLI_memarena_free(pf_arena); - } - - if (poly_arena) { - BLI_memarena_free(poly_arena); - } - - if (valid) { - BVHTree *tree; - - tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); - if (tree) { - for (i = 0; i < tris_len; i++) { - float co[3][3]; - - copy_v3_v3(co[0], coords[tris[i][0]]); - copy_v3_v3(co[1], coords[tris[i][1]]); - copy_v3_v3(co[2], coords[tris[i][2]]); - - BLI_bvhtree_insert(tree, (int)i, co[0], 3); - } - - BLI_bvhtree_balance(tree); - } - - return bvhtree_CreatePyObject( - tree, epsilon, - coords, coords_len, - tris, tris_len, - orig_index, orig_normal); - } - else { - if (coords) { - MEM_freeN(coords); - } - if (tris) { - MEM_freeN(tris); - } - - return NULL; - } + const char *error_prefix = "BVHTree.FromPolygons"; + const char *keywords[] = {"vertices", "polygons", "all_triangles", "epsilon", NULL}; + + PyObject *py_coords, *py_tris; + PyObject *py_coords_fast = NULL, *py_tris_fast = NULL; + + MemArena *poly_arena = NULL; + MemArena *pf_arena = NULL; + + float(*coords)[3] = NULL; + unsigned int(*tris)[3] = NULL; + unsigned int coords_len, tris_len; + float epsilon = 0.0f; + bool all_triangles = false; + + /* when all_triangles is False */ + int *orig_index = NULL; + float(*orig_normal)[3] = NULL; + + unsigned int i; + bool valid = true; + + if (!PyArg_ParseTupleAndKeywords(args, + kwargs, + (char *)"OO|$O&f:BVHTree.FromPolygons", + (char **)keywords, + &py_coords, + &py_tris, + PyC_ParseBool, + &all_triangles, + &epsilon)) { + return NULL; + } + + if (!(py_coords_fast = PySequence_Fast(py_coords, error_prefix)) || + !(py_tris_fast = PySequence_Fast(py_tris, error_prefix))) { + Py_XDECREF(py_coords_fast); + return NULL; + } + + if (valid) { + PyObject **py_coords_fast_items = PySequence_Fast_ITEMS(py_coords_fast); + coords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_coords_fast); + coords = MEM_mallocN((size_t)coords_len * sizeof(*coords), __func__); + + for (i = 0; i < coords_len; i++) { + PyObject *py_vert = py_coords_fast_items[i]; + + if (mathutils_array_parse(coords[i], 3, 3, py_vert, "BVHTree vertex: ") == -1) { + valid = false; + break; + } + } + } + + if (valid == false) { + /* pass */ + } + else if (all_triangles) { + /* all triangles, simple case */ + PyObject **py_tris_fast_items = PySequence_Fast_ITEMS(py_tris_fast); + tris_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast); + tris = MEM_mallocN((size_t)tris_len * sizeof(*tris), __func__); + + for (i = 0; i < tris_len; i++) { + PyObject *py_tricoords = py_tris_fast_items[i]; + PyObject *py_tricoords_fast; + PyObject **py_tricoords_fast_items; + unsigned int *tri = tris[i]; + int j; + + if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) { + valid = false; + break; + } + + if (PySequence_Fast_GET_SIZE(py_tricoords_fast) != 3) { + Py_DECREF(py_tricoords_fast); + PyErr_Format(PyExc_ValueError, + "%s: non triangle found at index %d with length of %d", + error_prefix, + i, + PySequence_Fast_GET_SIZE(py_tricoords_fast)); + valid = false; + break; + } + + py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast); + + for (j = 0; j < 3; j++) { + tri[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]); + if (UNLIKELY(tri[j] >= (unsigned int)coords_len)) { + PyErr_Format(PyExc_ValueError, + "%s: index %d must be less than %d", + error_prefix, + tri[j], + coords_len); + + /* decref below */ + valid = false; + break; + } + } + + Py_DECREF(py_tricoords_fast); + } + } + else { + /* ngon support (much more involved) */ + const unsigned int polys_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tris_fast); + struct PolyLink { + struct PolyLink *next; + unsigned int len; + unsigned int poly[0]; + } *plink_first = NULL, **p_plink_prev = &plink_first, *plink = NULL; + int poly_index; + + tris_len = 0; + + poly_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + + for (i = 0; i < polys_len; i++) { + PyObject *py_tricoords = PySequence_Fast_GET_ITEM(py_tris_fast, i); + PyObject *py_tricoords_fast; + PyObject **py_tricoords_fast_items; + unsigned int py_tricoords_len; + unsigned int j; + + if (!(py_tricoords_fast = PySequence_Fast(py_tricoords, error_prefix))) { + valid = false; + break; + } + + py_tricoords_len = (unsigned int)PySequence_Fast_GET_SIZE(py_tricoords_fast); + py_tricoords_fast_items = PySequence_Fast_ITEMS(py_tricoords_fast); + + plink = BLI_memarena_alloc(poly_arena, + sizeof(*plink) + (sizeof(int) * (size_t)py_tricoords_len)); + + plink->len = (unsigned int)py_tricoords_len; + *p_plink_prev = plink; + p_plink_prev = &plink->next; + + for (j = 0; j < py_tricoords_len; j++) { + plink->poly[j] = PyC_Long_AsU32(py_tricoords_fast_items[j]); + if (UNLIKELY(plink->poly[j] >= (unsigned int)coords_len)) { + PyErr_Format(PyExc_ValueError, + "%s: index %d must be less than %d", + error_prefix, + plink->poly[j], + coords_len); + /* decref below */ + valid = false; + break; + } + } + + Py_DECREF(py_tricoords_fast); + + if (py_tricoords_len >= 3) { + tris_len += (py_tricoords_len - 2); + } + } + *p_plink_prev = NULL; + + /* all ngon's are parsed, now tessellate */ + + pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); + tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); + + orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); + orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)polys_len, __func__); + + for (plink = plink_first, poly_index = 0, i = 0; plink; plink = plink->next, poly_index++) { + if (plink->len == 3) { + unsigned int *tri = tris[i]; + memcpy(tri, plink->poly, sizeof(unsigned int[3])); + orig_index[i] = poly_index; + normal_tri_v3(orig_normal[poly_index], coords[tri[0]], coords[tri[1]], coords[tri[2]]); + i++; + } + else if (plink->len > 3) { + float(*proj_coords)[2] = BLI_memarena_alloc(pf_arena, sizeof(*proj_coords) * plink->len); + float *normal = orig_normal[poly_index]; + const float *co_prev; + const float *co_curr; + float axis_mat[3][3]; + unsigned int(*tris_offset)[3] = &tris[i]; + unsigned int j; + + /* calc normal and setup 'proj_coords' */ + zero_v3(normal); + co_prev = coords[plink->poly[plink->len - 1]]; + for (j = 0; j < plink->len; j++) { + co_curr = coords[plink->poly[j]]; + add_newell_cross_v3_v3v3(normal, co_prev, co_curr); + co_prev = co_curr; + } + normalize_v3(normal); + + axis_dominant_v3_to_m3_negate(axis_mat, normal); + + for (j = 0; j < plink->len; j++) { + mul_v2_m3v3(proj_coords[j], axis_mat, coords[plink->poly[j]]); + } + + BLI_polyfill_calc_arena(proj_coords, plink->len, 1, tris_offset, pf_arena); + + j = plink->len - 2; + while (j--) { + unsigned int *tri = tris_offset[j]; + /* remap to global indices */ + tri[0] = plink->poly[tri[0]]; + tri[1] = plink->poly[tri[1]]; + tri[2] = plink->poly[tri[2]]; + + orig_index[i] = poly_index; + i++; + } + + BLI_memarena_clear(pf_arena); + } + else { + zero_v3(orig_normal[poly_index]); + } + } + } + + Py_DECREF(py_coords_fast); + Py_DECREF(py_tris_fast); + + if (pf_arena) { + BLI_memarena_free(pf_arena); + } + + if (poly_arena) { + BLI_memarena_free(poly_arena); + } + + if (valid) { + BVHTree *tree; + + tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); + if (tree) { + for (i = 0; i < tris_len; i++) { + float co[3][3]; + + copy_v3_v3(co[0], coords[tris[i][0]]); + copy_v3_v3(co[1], coords[tris[i][1]]); + copy_v3_v3(co[2], coords[tris[i][2]]); + + BLI_bvhtree_insert(tree, (int)i, co[0], 3); + } + + BLI_bvhtree_balance(tree); + } + + return bvhtree_CreatePyObject( + tree, epsilon, coords, coords_len, tris, tris_len, orig_index, orig_normal); + } + else { + if (coords) { + MEM_freeN(coords); + } + if (tris) { + MEM_freeN(tris); + } + + return NULL; + } } - #ifndef MATH_STANDALONE PyDoc_STRVAR(C_BVHTree_FromBMesh_doc, -".. classmethod:: FromBMesh(bmesh, epsilon=0.0)\n" -"\n" -" BVH tree based on :class:`BMesh` data.\n" -"\n" -" :arg bmesh: BMesh data.\n" -" :type bmesh: :class:`BMesh`\n" -PYBVH_FROM_GENERIC_EPSILON_DOC -); + ".. classmethod:: FromBMesh(bmesh, epsilon=0.0)\n" + "\n" + " BVH tree based on :class:`BMesh` data.\n" + "\n" + " :arg bmesh: BMesh data.\n" + " :type bmesh: :class:`BMesh`\n" PYBVH_FROM_GENERIC_EPSILON_DOC); static PyObject *C_BVHTree_FromBMesh(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs) { - const char *keywords[] = {"bmesh", "epsilon", NULL}; + const char *keywords[] = {"bmesh", "epsilon", NULL}; - BPy_BMesh *py_bm; + BPy_BMesh *py_bm; - float (*coords)[3] = NULL; - unsigned int (*tris)[3] = NULL; - unsigned int coords_len, tris_len; - float epsilon = 0.0f; + float(*coords)[3] = NULL; + unsigned int(*tris)[3] = NULL; + unsigned int coords_len, tris_len; + float epsilon = 0.0f; - BMesh *bm; - BMLoop *(*looptris)[3]; + BMesh *bm; + BMLoop *(*looptris)[3]; - if (!PyArg_ParseTupleAndKeywords( - args, kwargs, (char *)"O!|$f:BVHTree.FromBMesh", (char **)keywords, - &BPy_BMesh_Type, &py_bm, &epsilon)) - { - return NULL; - } + if (!PyArg_ParseTupleAndKeywords(args, + kwargs, + (char *)"O!|$f:BVHTree.FromBMesh", + (char **)keywords, + &BPy_BMesh_Type, + &py_bm, + &epsilon)) { + return NULL; + } - bm = py_bm->bm; + bm = py_bm->bm; - /* Get data for tessellation */ - { - int tris_len_dummy; + /* Get data for tessellation */ + { + int tris_len_dummy; - coords_len = (unsigned int)bm->totvert; - tris_len = (unsigned int)poly_to_tri_count(bm->totface, bm->totloop); + coords_len = (unsigned int)bm->totvert; + tris_len = (unsigned int)poly_to_tri_count(bm->totface, bm->totloop); - coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__); - tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); + coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__); + tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); - looptris = MEM_mallocN(sizeof(*looptris) * (size_t)tris_len, __func__); + looptris = MEM_mallocN(sizeof(*looptris) * (size_t)tris_len, __func__); - BM_mesh_calc_tessellation(bm, looptris, &tris_len_dummy); - BLI_assert(tris_len_dummy == (int)tris_len); - } + BM_mesh_calc_tessellation(bm, looptris, &tris_len_dummy); + BLI_assert(tris_len_dummy == (int)tris_len); + } - { - BMIter iter; - BVHTree *tree; - unsigned int i; + { + BMIter iter; + BVHTree *tree; + unsigned int i; - int *orig_index = NULL; - float (*orig_normal)[3] = NULL; + int *orig_index = NULL; + float(*orig_normal)[3] = NULL; - tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); - if (tree) { - BMFace *f; - BMVert *v; + tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); + if (tree) { + BMFace *f; + BMVert *v; - orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); - orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)bm->totface, __func__); + orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); + orig_normal = MEM_mallocN(sizeof(*orig_normal) * (size_t)bm->totface, __func__); - BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { - copy_v3_v3(coords[i], v->co); - BM_elem_index_set(v, (int)i); /* set_inline */ - } - BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) { - copy_v3_v3(orig_normal[i], f->no); - BM_elem_index_set(f, (int)i); /* set_inline */ - } - bm->elem_index_dirty &= (char)~(BM_VERT | BM_FACE); + BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { + copy_v3_v3(coords[i], v->co); + BM_elem_index_set(v, (int)i); /* set_inline */ + } + BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) { + copy_v3_v3(orig_normal[i], f->no); + BM_elem_index_set(f, (int)i); /* set_inline */ + } + bm->elem_index_dirty &= (char)~(BM_VERT | BM_FACE); - for (i = 0; i < tris_len; i++) { - float co[3][3]; + for (i = 0; i < tris_len; i++) { + float co[3][3]; - tris[i][0] = (unsigned int)BM_elem_index_get(looptris[i][0]->v); - tris[i][1] = (unsigned int)BM_elem_index_get(looptris[i][1]->v); - tris[i][2] = (unsigned int)BM_elem_index_get(looptris[i][2]->v); + tris[i][0] = (unsigned int)BM_elem_index_get(looptris[i][0]->v); + tris[i][1] = (unsigned int)BM_elem_index_get(looptris[i][1]->v); + tris[i][2] = (unsigned int)BM_elem_index_get(looptris[i][2]->v); - copy_v3_v3(co[0], coords[tris[i][0]]); - copy_v3_v3(co[1], coords[tris[i][1]]); - copy_v3_v3(co[2], coords[tris[i][2]]); + copy_v3_v3(co[0], coords[tris[i][0]]); + copy_v3_v3(co[1], coords[tris[i][1]]); + copy_v3_v3(co[2], coords[tris[i][2]]); - BLI_bvhtree_insert(tree, (int)i, co[0], 3); - orig_index[i] = BM_elem_index_get(looptris[i][0]->f); - } + BLI_bvhtree_insert(tree, (int)i, co[0], 3); + orig_index[i] = BM_elem_index_get(looptris[i][0]->f); + } - BLI_bvhtree_balance(tree); - } + BLI_bvhtree_balance(tree); + } - MEM_freeN(looptris); + MEM_freeN(looptris); - return bvhtree_CreatePyObject( - tree, epsilon, - coords, coords_len, - tris, tris_len, - orig_index, orig_normal); - } + return bvhtree_CreatePyObject( + tree, epsilon, coords, coords_len, tris, tris_len, orig_index, orig_normal); + } } /* return various derived meshes based on requested settings */ -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) +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) { - Object *ob_eval = DEG_get_evaluated_object(depsgraph, ob); - /* we only need minimum mesh data for topology and vertex locations */ - CustomData_MeshMasks data_masks = CD_MASK_BAREMESH; - const bool use_render = DEG_get_mode(depsgraph) == DAG_EVAL_RENDER; - *r_free_mesh = false; - - /* Write the display mesh into the dummy mesh */ - if (use_deform) { - if (use_render) { - if (use_cage) { - PyErr_Format(PyExc_ValueError, - "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", funcname); - return NULL; - } - else { - *r_free_mesh = true; - return mesh_create_eval_final_render(depsgraph, scene, ob, &data_masks); - } - } - else if (ob_eval != NULL) { - if (use_cage) { - return mesh_get_eval_deform(depsgraph, scene, ob_eval, &data_masks); - } - else { - return mesh_get_eval_final(depsgraph, scene, ob_eval, &data_masks); - } - } - else { - PyErr_Format(PyExc_ValueError, - "%s(...): Cannot get evaluated data from given dependency graph / object pair", funcname); - return NULL; - } - } - else { - /* !use_deform */ - if (use_render) { - if (use_cage) { - PyErr_Format(PyExc_ValueError, - "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", funcname); - return NULL; - } - else { - *r_free_mesh = true; - return mesh_create_eval_no_deform_render(depsgraph, scene, ob, &data_masks); - } - } - else { - if (use_cage) { - PyErr_Format(PyExc_ValueError, - "%s(...): cage arg is unsupported when deform=False and dependency graph evaluation mode is not RENDER", funcname); - return NULL; - } - else { - *r_free_mesh = true; - return mesh_create_eval_no_deform(depsgraph, scene, ob, &data_masks); - } - } - } + Object *ob_eval = DEG_get_evaluated_object(depsgraph, ob); + /* we only need minimum mesh data for topology and vertex locations */ + CustomData_MeshMasks data_masks = CD_MASK_BAREMESH; + const bool use_render = DEG_get_mode(depsgraph) == DAG_EVAL_RENDER; + *r_free_mesh = false; + + /* Write the display mesh into the dummy mesh */ + if (use_deform) { + if (use_render) { + if (use_cage) { + PyErr_Format( + PyExc_ValueError, + "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", + funcname); + return NULL; + } + else { + *r_free_mesh = true; + return mesh_create_eval_final_render(depsgraph, scene, ob, &data_masks); + } + } + else if (ob_eval != NULL) { + if (use_cage) { + return mesh_get_eval_deform(depsgraph, scene, ob_eval, &data_masks); + } + else { + return mesh_get_eval_final(depsgraph, scene, ob_eval, &data_masks); + } + } + else { + PyErr_Format(PyExc_ValueError, + "%s(...): Cannot get evaluated data from given dependency graph / object pair", + funcname); + return NULL; + } + } + else { + /* !use_deform */ + if (use_render) { + if (use_cage) { + PyErr_Format( + PyExc_ValueError, + "%s(...): cage arg is unsupported when dependency graph evaluation mode is RENDER", + funcname); + return NULL; + } + else { + *r_free_mesh = true; + return mesh_create_eval_no_deform_render(depsgraph, scene, ob, &data_masks); + } + } + else { + if (use_cage) { + PyErr_Format(PyExc_ValueError, + "%s(...): cage arg is unsupported when deform=False and dependency graph " + "evaluation mode is not RENDER", + funcname); + return NULL; + } + else { + *r_free_mesh = true; + return mesh_create_eval_no_deform(depsgraph, scene, ob, &data_masks); + } + } + } } PyDoc_STRVAR(C_BVHTree_FromObject_doc, -".. classmethod:: FromObject(object, depsgraph, deform=True, render=False, cage=False, epsilon=0.0)\n" -"\n" -" BVH tree based on :class:`Object` data.\n" -"\n" -" :arg object: Object data.\n" -" :type object: :class:`Object`\n" -" :arg depsgraph: Depsgraph to use for evaluating the mesh.\n" -" :type depsgraph: :class:`Depsgraph`\n" -" :arg deform: Use mesh with deformations.\n" -" :type deform: bool\n" -" :arg cage: Use modifiers cage.\n" -" :type cage: bool\n" -PYBVH_FROM_GENERIC_EPSILON_DOC -); + ".. classmethod:: FromObject(object, depsgraph, deform=True, render=False, " + "cage=False, epsilon=0.0)\n" + "\n" + " BVH tree based on :class:`Object` data.\n" + "\n" + " :arg object: Object data.\n" + " :type object: :class:`Object`\n" + " :arg depsgraph: Depsgraph to use for evaluating the mesh.\n" + " :type depsgraph: :class:`Depsgraph`\n" + " :arg deform: Use mesh with deformations.\n" + " :type deform: bool\n" + " :arg cage: Use modifiers cage.\n" + " :type cage: bool\n" PYBVH_FROM_GENERIC_EPSILON_DOC); static PyObject *C_BVHTree_FromObject(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs) { - /* note, options here match 'bpy_bmesh_from_object' */ - const char *keywords[] = {"object", "depsgraph", "deform", "cage", "epsilon", NULL}; - - PyObject *py_ob, *py_depsgraph; - Object *ob; - struct Depsgraph *depsgraph; - struct Scene *scene; - Mesh *mesh; - bool use_deform = true; - bool use_cage = false; - bool free_mesh = false; - - const MLoopTri *lt; - const MLoop *mloop; - - float (*coords)[3] = NULL; - unsigned int (*tris)[3] = NULL; - unsigned int coords_len, tris_len; - float epsilon = 0.0f; - - if (!PyArg_ParseTupleAndKeywords( - args, kwargs, (char *)"OO|$O&O&f:BVHTree.FromObject", (char **)keywords, - &py_ob, &py_depsgraph, - PyC_ParseBool, &use_deform, - PyC_ParseBool, &use_cage, - &epsilon) || - ((ob = PyC_RNA_AsPointer(py_ob, "Object")) == NULL) || - ((depsgraph = PyC_RNA_AsPointer(py_depsgraph, "Depsgraph")) == NULL)) - { - return NULL; - } - - scene = DEG_get_evaluated_scene(depsgraph); - mesh = bvh_get_mesh("BVHTree", depsgraph, scene, ob, use_deform, use_cage, &free_mesh); - - if (mesh == NULL) { - return NULL; - } - - /* Get data for tessellation */ - { - lt = BKE_mesh_runtime_looptri_ensure(mesh); - - tris_len = (unsigned int)BKE_mesh_runtime_looptri_len(mesh); - coords_len = (unsigned int)mesh->totvert; - - coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__); - tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); - - MVert *mv = mesh->mvert; - for (int i = 0; i < mesh->totvert; i++, mv++) { - copy_v3_v3(coords[i], mv->co); - } - - mloop = mesh->mloop; - } - - { - BVHTree *tree; - unsigned int i; - - int *orig_index = NULL; - float (*orig_normal)[3] = NULL; - - tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); - if (tree) { - orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); - CustomData *pdata = &mesh->pdata; - orig_normal = CustomData_get_layer(pdata, CD_NORMAL); /* can be NULL */ - if (orig_normal) { - orig_normal = MEM_dupallocN(orig_normal); - } - - for (i = 0; i < tris_len; i++, lt++) { - float co[3][3]; - - tris[i][0] = mloop[lt->tri[0]].v; - tris[i][1] = mloop[lt->tri[1]].v; - tris[i][2] = mloop[lt->tri[2]].v; - - copy_v3_v3(co[0], coords[tris[i][0]]); - copy_v3_v3(co[1], coords[tris[i][1]]); - copy_v3_v3(co[2], coords[tris[i][2]]); - - BLI_bvhtree_insert(tree, (int)i, co[0], 3); - orig_index[i] = (int)lt->poly; - } - - BLI_bvhtree_balance(tree); - } - - if (free_mesh) { - BKE_id_free(NULL, mesh); - } - - return bvhtree_CreatePyObject( - tree, epsilon, - coords, coords_len, - tris, tris_len, - orig_index, orig_normal); - } + /* note, options here match 'bpy_bmesh_from_object' */ + const char *keywords[] = {"object", "depsgraph", "deform", "cage", "epsilon", NULL}; + + PyObject *py_ob, *py_depsgraph; + Object *ob; + struct Depsgraph *depsgraph; + struct Scene *scene; + Mesh *mesh; + bool use_deform = true; + bool use_cage = false; + bool free_mesh = false; + + const MLoopTri *lt; + const MLoop *mloop; + + float(*coords)[3] = NULL; + unsigned int(*tris)[3] = NULL; + unsigned int coords_len, tris_len; + float epsilon = 0.0f; + + if (!PyArg_ParseTupleAndKeywords(args, + kwargs, + (char *)"OO|$O&O&f:BVHTree.FromObject", + (char **)keywords, + &py_ob, + &py_depsgraph, + PyC_ParseBool, + &use_deform, + PyC_ParseBool, + &use_cage, + &epsilon) || + ((ob = PyC_RNA_AsPointer(py_ob, "Object")) == NULL) || + ((depsgraph = PyC_RNA_AsPointer(py_depsgraph, "Depsgraph")) == NULL)) { + return NULL; + } + + scene = DEG_get_evaluated_scene(depsgraph); + mesh = bvh_get_mesh("BVHTree", depsgraph, scene, ob, use_deform, use_cage, &free_mesh); + + if (mesh == NULL) { + return NULL; + } + + /* Get data for tessellation */ + { + lt = BKE_mesh_runtime_looptri_ensure(mesh); + + tris_len = (unsigned int)BKE_mesh_runtime_looptri_len(mesh); + coords_len = (unsigned int)mesh->totvert; + + coords = MEM_mallocN(sizeof(*coords) * (size_t)coords_len, __func__); + tris = MEM_mallocN(sizeof(*tris) * (size_t)tris_len, __func__); + + MVert *mv = mesh->mvert; + for (int i = 0; i < mesh->totvert; i++, mv++) { + copy_v3_v3(coords[i], mv->co); + } + + mloop = mesh->mloop; + } + + { + BVHTree *tree; + unsigned int i; + + int *orig_index = NULL; + float(*orig_normal)[3] = NULL; + + tree = BLI_bvhtree_new((int)tris_len, epsilon, PY_BVH_TREE_TYPE_DEFAULT, PY_BVH_AXIS_DEFAULT); + if (tree) { + orig_index = MEM_mallocN(sizeof(*orig_index) * (size_t)tris_len, __func__); + CustomData *pdata = &mesh->pdata; + orig_normal = CustomData_get_layer(pdata, CD_NORMAL); /* can be NULL */ + if (orig_normal) { + orig_normal = MEM_dupallocN(orig_normal); + } + + for (i = 0; i < tris_len; i++, lt++) { + float co[3][3]; + + tris[i][0] = mloop[lt->tri[0]].v; + tris[i][1] = mloop[lt->tri[1]].v; + tris[i][2] = mloop[lt->tri[2]].v; + + copy_v3_v3(co[0], coords[tris[i][0]]); + copy_v3_v3(co[1], coords[tris[i][1]]); + copy_v3_v3(co[2], coords[tris[i][2]]); + + BLI_bvhtree_insert(tree, (int)i, co[0], 3); + orig_index[i] = (int)lt->poly; + } + + BLI_bvhtree_balance(tree); + } + + if (free_mesh) { + BKE_id_free(NULL, mesh); + } + + return bvhtree_CreatePyObject( + tree, epsilon, coords, coords_len, tris, tris_len, orig_index, orig_normal); + } } -#endif /* MATH_STANDALONE */ +#endif /* MATH_STANDALONE */ /** \} */ - /* -------------------------------------------------------------------- */ /** \name Module & Type definition * \{ */ static PyMethodDef py_bvhtree_methods[] = { - {"ray_cast", (PyCFunction)py_bvhtree_ray_cast, METH_VARARGS, py_bvhtree_ray_cast_doc}, - {"find_nearest", (PyCFunction)py_bvhtree_find_nearest, METH_VARARGS, py_bvhtree_find_nearest_doc}, - {"find_nearest_range", (PyCFunction)py_bvhtree_find_nearest_range, METH_VARARGS, py_bvhtree_find_nearest_range_doc}, - {"overlap", (PyCFunction)py_bvhtree_overlap, METH_O, py_bvhtree_overlap_doc}, - - /* class methods */ - {"FromPolygons", (PyCFunction) C_BVHTree_FromPolygons, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromPolygons_doc}, + {"ray_cast", (PyCFunction)py_bvhtree_ray_cast, METH_VARARGS, py_bvhtree_ray_cast_doc}, + {"find_nearest", + (PyCFunction)py_bvhtree_find_nearest, + METH_VARARGS, + py_bvhtree_find_nearest_doc}, + {"find_nearest_range", + (PyCFunction)py_bvhtree_find_nearest_range, + METH_VARARGS, + py_bvhtree_find_nearest_range_doc}, + {"overlap", (PyCFunction)py_bvhtree_overlap, METH_O, py_bvhtree_overlap_doc}, + + /* class methods */ + {"FromPolygons", + (PyCFunction)C_BVHTree_FromPolygons, + METH_VARARGS | METH_KEYWORDS | METH_CLASS, + C_BVHTree_FromPolygons_doc}, #ifndef MATH_STANDALONE - {"FromBMesh", (PyCFunction) C_BVHTree_FromBMesh, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromBMesh_doc}, - {"FromObject", (PyCFunction) C_BVHTree_FromObject, METH_VARARGS | METH_KEYWORDS | METH_CLASS, C_BVHTree_FromObject_doc}, + {"FromBMesh", + (PyCFunction)C_BVHTree_FromBMesh, + METH_VARARGS | METH_KEYWORDS | METH_CLASS, + C_BVHTree_FromBMesh_doc}, + {"FromObject", + (PyCFunction)C_BVHTree_FromObject, + METH_VARARGS | METH_KEYWORDS | METH_CLASS, + C_BVHTree_FromObject_doc}, #endif - {NULL, NULL, 0, NULL}, + {NULL, NULL, 0, NULL}, }; PyTypeObject PyBVHTree_Type = { - PyVarObject_HEAD_INIT(NULL, 0) - "BVHTree", /* tp_name */ - sizeof(PyBVHTree), /* tp_basicsize */ - 0, /* tp_itemsize */ - /* methods */ - (destructor)py_bvhtree__tp_dealloc, /* tp_dealloc */ - NULL, /* tp_print */ - NULL, /* tp_getattr */ - NULL, /* tp_setattr */ - NULL, /* tp_compare */ - NULL, /* tp_repr */ - NULL, /* tp_as_number */ - NULL, /* tp_as_sequence */ - NULL, /* tp_as_mapping */ - NULL, /* tp_hash */ - NULL, /* tp_call */ - NULL, /* tp_str */ - NULL, /* tp_getattro */ - NULL, /* tp_setattro */ - NULL, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT, /* tp_flags */ - NULL, /* Documentation string */ - NULL, /* tp_traverse */ - NULL, /* tp_clear */ - NULL, /* tp_richcompare */ - 0, /* tp_weaklistoffset */ - NULL, /* tp_iter */ - NULL, /* tp_iternext */ - py_bvhtree_methods, /* tp_methods */ - NULL, /* tp_members */ - NULL, /* tp_getset */ - NULL, /* tp_base */ - NULL, /* tp_dict */ - NULL, /* tp_descr_get */ - NULL, /* tp_descr_set */ - 0, /* tp_dictoffset */ - NULL, /* tp_init */ - (allocfunc)PyType_GenericAlloc, /* tp_alloc */ - (newfunc)PyType_GenericNew, /* tp_new */ - (freefunc)0, /* tp_free */ - NULL, /* tp_is_gc */ - NULL, /* tp_bases */ - NULL, /* tp_mro */ - NULL, /* tp_cache */ - NULL, /* tp_subclasses */ - NULL, /* tp_weaklist */ - (destructor)NULL, /* tp_del */ + PyVarObject_HEAD_INIT(NULL, 0) "BVHTree", /* tp_name */ + sizeof(PyBVHTree), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)py_bvhtree__tp_dealloc, /* tp_dealloc */ + NULL, /* tp_print */ + NULL, /* tp_getattr */ + NULL, /* tp_setattr */ + NULL, /* tp_compare */ + NULL, /* tp_repr */ + NULL, /* tp_as_number */ + NULL, /* tp_as_sequence */ + NULL, /* tp_as_mapping */ + NULL, /* tp_hash */ + NULL, /* tp_call */ + NULL, /* tp_str */ + NULL, /* tp_getattro */ + NULL, /* tp_setattro */ + NULL, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT, /* tp_flags */ + NULL, /* Documentation string */ + NULL, /* tp_traverse */ + NULL, /* tp_clear */ + NULL, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + NULL, /* tp_iter */ + NULL, /* tp_iternext */ + py_bvhtree_methods, /* tp_methods */ + NULL, /* tp_members */ + NULL, /* tp_getset */ + NULL, /* tp_base */ + NULL, /* tp_dict */ + NULL, /* tp_descr_get */ + NULL, /* tp_descr_set */ + 0, /* tp_dictoffset */ + NULL, /* tp_init */ + (allocfunc)PyType_GenericAlloc, /* tp_alloc */ + (newfunc)PyType_GenericNew, /* tp_new */ + (freefunc)0, /* tp_free */ + NULL, /* tp_is_gc */ + NULL, /* tp_bases */ + NULL, /* tp_mro */ + NULL, /* tp_cache */ + NULL, /* tp_subclasses */ + NULL, /* tp_weaklist */ + (destructor)NULL, /* tp_del */ }; /* -------------------------------------------------------------------- */ /* Module definition */ PyDoc_STRVAR(py_bvhtree_doc, -"BVH tree structures for proximity searches and ray casts on geometry." -); + "BVH tree structures for proximity searches and ray casts on geometry."); static struct PyModuleDef bvhtree_moduledef = { - PyModuleDef_HEAD_INIT, - "mathutils.bvhtree", /* m_name */ - py_bvhtree_doc, /* m_doc */ - 0, /* m_size */ - NULL, /* m_methods */ - NULL, /* m_reload */ - NULL, /* m_traverse */ - NULL, /* m_clear */ - NULL, /* m_free */ + PyModuleDef_HEAD_INIT, + "mathutils.bvhtree", /* m_name */ + py_bvhtree_doc, /* m_doc */ + 0, /* m_size */ + NULL, /* m_methods */ + NULL, /* m_reload */ + NULL, /* m_traverse */ + NULL, /* m_clear */ + NULL, /* m_free */ }; PyMODINIT_FUNC PyInit_mathutils_bvhtree(void) { - PyObject *m = PyModule_Create(&bvhtree_moduledef); + PyObject *m = PyModule_Create(&bvhtree_moduledef); - if (m == NULL) { - return NULL; - } + if (m == NULL) { + return NULL; + } - /* Register classes */ - if (PyType_Ready(&PyBVHTree_Type) < 0) { - return NULL; - } + /* Register classes */ + if (PyType_Ready(&PyBVHTree_Type) < 0) { + return NULL; + } - PyModule_AddObject(m, "BVHTree", (PyObject *)&PyBVHTree_Type); + PyModule_AddObject(m, "BVHTree", (PyObject *)&PyBVHTree_Type); - return m; + return m; } /** \} */ |