Blender  V3.3
Classes | Macros | Functions | Variables
mathutils_bvhtree.c File Reference
#include <Python.h>
#include "MEM_guardedalloc.h"
#include "BLI_ghash.h"
#include "BLI_kdopbvh.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d.h"
#include "BLI_utildefines.h"
#include "BKE_bvhutils.h"
#include "../generic/py_capi_utils.h"
#include "../generic/python_utildefines.h"
#include "mathutils.h"
#include "mathutils_bvhtree.h"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"
#include "BKE_customdata.h"
#include "BKE_editmesh_bvh.h"
#include "BKE_lib_id.h"
#include "BKE_mesh.h"
#include "BKE_mesh_runtime.h"
#include "DEG_depsgraph_query.h"
#include "bmesh.h"
#include "../bmesh/bmesh_py_types.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes

struct  PyBVHTree
 
struct  PyBVH_RangeData
 
struct  PyBVHTree_OverlapData
 

Macros

#define PYBVH_MAX_DIST_STR   "1.84467e+19"
 
Documentation String (snippets)
#define PYBVH_FIND_GENERIC_DISTANCE_DOC
 
#define PYBVH_FIND_GENERIC_RETURN_DOC
 
#define PYBVH_FIND_GENERIC_RETURN_LIST_DOC
 
#define PYBVH_FROM_GENERIC_EPSILON_DOC
 

Functions

static void py_bvhtree__tp_dealloc (PyBVHTree *self)
 
Utility helper functions
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])
 
BVHTreeRayHit to Python utilities
static void py_bvhtree_raycast_to_py_tuple (const BVHTreeRayHit *hit, PyObject *py_retval)
 
static PyObject * py_bvhtree_raycast_to_py (const BVHTreeRayHit *hit)
 
static PyObject * py_bvhtree_raycast_to_py_none (void)
 
BVHTreeNearest to Python utilities
static void py_bvhtree_nearest_to_py_tuple (const BVHTreeNearest *nearest, PyObject *py_retval)
 
static PyObject * py_bvhtree_nearest_to_py (const BVHTreeNearest *nearest)
 
static PyObject * py_bvhtree_nearest_to_py_none (void)
 
Methods
static void py_bvhtree_raycast_cb (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 
static void py_bvhtree_nearest_point_cb (void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 
 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)
 
static PyObject * py_bvhtree_ray_cast (PyBVHTree *self, PyObject *args)
 
 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)
 
static PyObject * py_bvhtree_find_nearest (PyBVHTree *self, PyObject *args)
 
static void py_bvhtree_nearest_point_range_cb (void *userdata, int index, const float co[3], float UNUSED(dist_sq_bvh))
 
 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)
 
BLI_INLINE uint overlap_hash (const void *overlap_v)
 
BLI_INLINE bool overlap_cmp (const void *a_v, const void *b_v)
 
static bool py_bvhtree_overlap_cb (void *userdata, int index_a, int index_b, int UNUSED(thread))
 
 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)
 
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)
 
static PyObject * C_BVHTree_FromPolygons (PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
 
 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)
 
static PyObject * C_BVHTree_FromBMesh (PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
 
static Meshbvh_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)
 
 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)
 
static PyObject * C_BVHTree_FromObject (PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
 

Variables

static const float max_dist_default = 1.844674352395373e+19f
 
static const char PY_BVH_TREE_TYPE_DEFAULT = 4
 
static const char PY_BVH_AXIS_DEFAULT = 6
 

Module & Type definition

static PyMethodDef py_bvhtree_methods []
 
PyTypeObject PyBVHTree_Type
 
static struct PyModuleDef bvhtree_moduledef
 
 PyDoc_STRVAR (py_bvhtree_doc, "BVH tree structures for proximity searches and ray casts on geometry.")
 
PyMODINIT_FUNC PyInit_mathutils_bvhtree (void)
 

Detailed Description

This file defines the 'mathutils.bvhtree' module, a general purpose module to access blenders bvhtree for mesh surface nearest-element search and ray casting.

Definition in file mathutils_bvhtree.c.

Macro Definition Documentation

◆ PYBVH_FIND_GENERIC_DISTANCE_DOC

#define PYBVH_FIND_GENERIC_DISTANCE_DOC
Value:
" :arg distance: Maximum distance threshold.\n" \
" :type distance: float\n"

Definition at line 53 of file mathutils_bvhtree.c.

◆ PYBVH_FIND_GENERIC_RETURN_DOC

#define PYBVH_FIND_GENERIC_RETURN_DOC
Value:
" :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"

Definition at line 57 of file mathutils_bvhtree.c.

◆ PYBVH_FIND_GENERIC_RETURN_LIST_DOC

#define PYBVH_FIND_GENERIC_RETURN_LIST_DOC
Value:
" :return: Returns a list of tuples\n" \
" (:class:`Vector` location, :class:`Vector` normal, int index, float distance),\n" \
" :rtype: :class:`list`\n"

Definition at line 63 of file mathutils_bvhtree.c.

◆ PYBVH_FROM_GENERIC_EPSILON_DOC

#define PYBVH_FROM_GENERIC_EPSILON_DOC
Value:
" :arg epsilon: Increase the threshold for detecting overlap and raycast hits.\n" \
" :type epsilon: float\n"

Definition at line 68 of file mathutils_bvhtree.c.

◆ PYBVH_MAX_DIST_STR

#define PYBVH_MAX_DIST_STR   "1.84467e+19"

Definition at line 75 of file mathutils_bvhtree.c.

Function Documentation

◆ bvh_get_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 
)
static

◆ bvhtree_CreatePyObject()

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

◆ C_BVHTree_FromBMesh()

static PyObject* C_BVHTree_FromBMesh ( PyObject *  UNUSEDcls,
PyObject *  args,
PyObject *  kwargs 
)
static

◆ C_BVHTree_FromObject()

static PyObject* C_BVHTree_FromObject ( PyObject *  UNUSEDcls,
PyObject *  args,
PyObject *  kwargs 
)
static

◆ C_BVHTree_FromPolygons()

static PyObject* C_BVHTree_FromPolygons ( PyObject *  UNUSEDcls,
PyObject *  args,
PyObject *  kwargs 
)
static

◆ overlap_cmp()

BLI_INLINE bool overlap_cmp ( const void a_v,
const void b_v 
)

Definition at line 499 of file mathutils_bvhtree.c.

References Freestyle::a, and usdtokens::b().

Referenced by py_bvhtree_overlap().

◆ overlap_hash()

BLI_INLINE uint overlap_hash ( const void overlap_v)

Definition at line 492 of file mathutils_bvhtree.c.

References BVHTreeOverlap::indexA.

Referenced by py_bvhtree_overlap().

◆ py_bvhtree__tp_dealloc()

static void py_bvhtree__tp_dealloc ( PyBVHTree self)
static

Definition at line 239 of file mathutils_bvhtree.c.

References BLI_bvhtree_free(), MEM_SAFE_FREE, and self.

◆ py_bvhtree_find_nearest()

static PyObject* py_bvhtree_find_nearest ( PyBVHTree self,
PyObject *  args 
)
static

◆ py_bvhtree_find_nearest_range()

static PyObject* py_bvhtree_find_nearest_range ( PyBVHTree self,
PyObject *  args 
)
static

◆ py_bvhtree_nearest_point_cb()

static void py_bvhtree_nearest_point_cb ( void userdata,
int  index,
const float  co[3],
BVHTreeNearest nearest 
)
static

Definition at line 290 of file mathutils_bvhtree.c.

References float(), and self.

Referenced by py_bvhtree_find_nearest().

◆ py_bvhtree_nearest_point_range_cb()

static void py_bvhtree_nearest_point_range_cb ( void userdata,
int  index,
const float  co[3],
float   UNUSEDdist_sq_bvh 
)
static

◆ py_bvhtree_nearest_to_py()

static PyObject* py_bvhtree_nearest_to_py ( const BVHTreeNearest nearest)
static

◆ py_bvhtree_nearest_to_py_none()

static PyObject* py_bvhtree_nearest_to_py_none ( void  )
static

Definition at line 210 of file mathutils_bvhtree.c.

References PyC_Tuple_Fill().

Referenced by py_bvhtree_find_nearest().

◆ py_bvhtree_nearest_to_py_tuple()

static void py_bvhtree_nearest_to_py_tuple ( const BVHTreeNearest nearest,
PyObject *  py_retval 
)
static

◆ py_bvhtree_overlap()

static PyObject* py_bvhtree_overlap ( PyBVHTree self,
PyBVHTree other 
)
static

◆ py_bvhtree_overlap_cb()

static bool py_bvhtree_overlap_cb ( void userdata,
int  index_a,
int  index_b,
int   UNUSEDthread 
)
static

◆ py_bvhtree_ray_cast()

static PyObject* py_bvhtree_ray_cast ( PyBVHTree self,
PyObject *  args 
)
static

◆ py_bvhtree_raycast_cb()

static void py_bvhtree_raycast_cb ( void userdata,
int  index,
const BVHTreeRay ray,
BVHTreeRayHit hit 
)
static

Definition at line 258 of file mathutils_bvhtree.c.

References float(), and self.

Referenced by py_bvhtree_ray_cast().

◆ py_bvhtree_raycast_to_py()

static PyObject* py_bvhtree_raycast_to_py ( const BVHTreeRayHit hit)
static

Definition at line 147 of file mathutils_bvhtree.c.

References py_bvhtree_raycast_to_py_tuple().

Referenced by py_bvhtree_ray_cast().

◆ py_bvhtree_raycast_to_py_none()

static PyObject* py_bvhtree_raycast_to_py_none ( void  )
static

Definition at line 156 of file mathutils_bvhtree.c.

References PyC_Tuple_Fill().

Referenced by py_bvhtree_ray_cast().

◆ py_bvhtree_raycast_to_py_tuple()

static void py_bvhtree_raycast_to_py_tuple ( const BVHTreeRayHit hit,
PyObject *  py_retval 
)
static

◆ PyDoc_STRVAR() [1/8]

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 
)

◆ PyDoc_STRVAR() [2/8]

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 
)

◆ PyDoc_STRVAR() [3/8]

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() [4/8]

PyDoc_STRVAR ( py_bvhtree_doc  ,
"BVH tree structures for proximity searches and ray casts on geometry."   
)

◆ PyDoc_STRVAR() [5/8]

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 
)

◆ PyDoc_STRVAR() [6/8]

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() [7/8]

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() [8/8]

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 
)

◆ PyInit_mathutils_bvhtree()

PyMODINIT_FUNC PyInit_mathutils_bvhtree ( void  )

Definition at line 1303 of file mathutils_bvhtree.c.

References bvhtree_moduledef, NULL, and PyBVHTree_Type.

Referenced by PyInit_mathutils().

Variable Documentation

◆ bvhtree_moduledef

struct PyModuleDef bvhtree_moduledef
static
Initial value:
= {
PyModuleDef_HEAD_INIT,
"mathutils.bvhtree",
py_bvhtree_doc,
0,
NULL,
NULL,
NULL,
NULL,
NULL,
}

Definition at line 1289 of file mathutils_bvhtree.c.

Referenced by PyInit_mathutils_bvhtree().

◆ max_dist_default

const float max_dist_default = 1.844674352395373e+19f
static

Definition at line 76 of file mathutils_bvhtree.c.

Referenced by py_bvhtree_find_nearest(), and py_bvhtree_find_nearest_range().

◆ PY_BVH_AXIS_DEFAULT

const char PY_BVH_AXIS_DEFAULT = 6
static

◆ PY_BVH_TREE_TYPE_DEFAULT

const char PY_BVH_TREE_TYPE_DEFAULT = 4
static

◆ py_bvhtree_methods

PyMethodDef py_bvhtree_methods[]
static
Initial value:
= {
{"ray_cast", (PyCFunction)py_bvhtree_ray_cast, METH_VARARGS, py_bvhtree_ray_cast_doc},
{"find_nearest",
METH_VARARGS,
py_bvhtree_find_nearest_doc},
{"find_nearest_range",
METH_VARARGS,
py_bvhtree_find_nearest_range_doc},
{"overlap", (PyCFunction)py_bvhtree_overlap, METH_O, py_bvhtree_overlap_doc},
{"FromPolygons",
(PyCFunction)C_BVHTree_FromPolygons,
METH_VARARGS | METH_KEYWORDS | METH_CLASS,
C_BVHTree_FromPolygons_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},
{NULL, NULL, 0, NULL},
}
static PyObject * C_BVHTree_FromPolygons(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
static PyObject * py_bvhtree_find_nearest(PyBVHTree *self, PyObject *args)
static PyObject * py_bvhtree_find_nearest_range(PyBVHTree *self, PyObject *args)
static PyObject * C_BVHTree_FromBMesh(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
static PyObject * C_BVHTree_FromObject(PyObject *UNUSED(cls), PyObject *args, PyObject *kwargs)
static PyObject * py_bvhtree_overlap(PyBVHTree *self, PyBVHTree *other)
static PyObject * py_bvhtree_ray_cast(PyBVHTree *self, PyObject *args)

Definition at line 1207 of file mathutils_bvhtree.c.

◆ PyBVHTree_Type

PyTypeObject PyBVHTree_Type

Definition at line 1237 of file mathutils_bvhtree.c.

Referenced by bvhtree_CreatePyObject(), and PyInit_mathutils_bvhtree().