[Bf-blender-cvs] [e9e37dd] mathutils_bvhtree: Another alternative BVH Tree representation for totally custom user geometry.
Lukas Tönne
noreply at git.blender.org
Tue Jul 14 17:28:26 CEST 2015
Commit: e9e37ddeb62595c62dc2fddfd02a4cdc7d96d53c
Author: Lukas Tönne
Date: Tue Jul 14 17:27:01 2015 +0200
Branches: mathutils_bvhtree
https://developer.blender.org/rBe9e37ddeb62595c62dc2fddfd02a4cdc7d96d53c
Another alternative BVH Tree representation for totally custom user
geometry.
The new constructor method allows creating a BVHTree from a list of
vertices and triangles directly, without a separate mesh representation.
===================================================================
M source/blender/blenkernel/BKE_bvhutils.h
M source/blender/blenkernel/intern/bvhutils.c
M source/blender/python/mathutils/mathutils_bvhtree.c
M source/blender/python/mathutils/mathutils_bvhtree.h
===================================================================
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index a360511..8109f46 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -101,6 +101,7 @@ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
* Math functions used by callbacks
*/
float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const 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, const float m_dist, const float v0[3], const float v1[3], const float v2[3]);
float nearest_point_in_tri_surface_squared(const float v0[3], const float v1[3], const float v2[3], const float p[3], int *v, int *e, float nearest[3]);
/*
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index 1a4a4bd..2213869 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -60,7 +60,7 @@ float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_d
return FLT_MAX;
}
-static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const 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, const float m_dist, const float v0[3], const float v1[3], const float v2[3])
{
float idist;
@@ -163,7 +163,7 @@ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *r
if (data->sphere_radius == 0.0f)
dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
else
- dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
+ dist = bvhtree_sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
if (dist >= 0 && dist < hit->dist) {
hit->index = index;
@@ -200,7 +200,7 @@ static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRa
if (data->sphere_radius == 0.0f)
dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
else
- dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
+ dist = bvhtree_sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
if (dist >= 0 && dist < hit->dist) {
hit->index = index;
diff --git a/source/blender/python/mathutils/mathutils_bvhtree.c b/source/blender/python/mathutils/mathutils_bvhtree.c
index 7d4d4ef..310ec41 100644
--- a/source/blender/python/mathutils/mathutils_bvhtree.c
+++ b/source/blender/python/mathutils/mathutils_bvhtree.c
@@ -73,6 +73,26 @@ typedef struct {
int bmtotlooptris;
} PyBVHTree_BMesh;
+typedef struct BVHVertex {
+ float co[3];
+} BVHVertex;
+
+typedef struct BVHTriangle {
+ int v1, v2, v3;
+} BVHTriangle;
+
+typedef struct PyBVHTree_Custom {
+ PyBVHTree base;
+ /* geometry data */
+ struct BVHTree *tree;
+
+ struct BVHVertex *vert;
+ struct BVHTriangle *tri;
+ int totvert, tottri;
+
+ float epsilon;
+} PyBVHTree_Custom;
+
/* -------------------------------------------------------------------- */
/* Utility helper functions */
@@ -691,6 +711,360 @@ PyTypeObject PyBVHTreeBMesh_Type = {
};
/* -------------------------------------------------------------------- */
+/* BVHTreeCustom */
+
+static BVHTree *bvhtree_from_triangles_create_tree(float epsilon, int tree_type, int axis,
+ BVHVertex *vert, BVHTriangle *tri, int numtris)
+{
+ BVHTree *tree = NULL;
+ int i;
+
+ if (numtris == 0 || !vert || !tri)
+ return NULL;
+
+ /* Create a bvh-tree of the given target */
+ tree = BLI_bvhtree_new(numtris, epsilon, (char)tree_type, (char)axis);
+ if (tree) {
+ for (i = 0; i < numtris; i++) {
+ float co[3][3];
+
+ copy_v3_v3(co[0], vert[tri[i].v1].co);
+ copy_v3_v3(co[1], vert[tri[i].v2].co);
+ copy_v3_v3(co[2], vert[tri[i].v3].co);
+
+ BLI_bvhtree_insert(tree, i, co[0], 3);
+ }
+
+ BLI_bvhtree_balance(tree);
+ }
+
+ return tree;
+}
+
+static int PyBVHTreeCustom__tp_init(PyBVHTree_Custom *self, PyObject *args, PyObject *kwargs)
+{
+ const char *keywords[] = {"vertices", "triangles", NULL};
+
+ PyObject *py_verts, *py_tris;
+ int numverts, numtris;
+ BVHVertex *verts, *vp;
+ BVHTriangle *tris, *tp;
+ int i;
+ bool valid = true;
+
+ if (PyBVHTree_Type.tp_init((PyObject *)self, args, kwargs) < 0)
+ return -1;
+
+ if (!PyArg_ParseTupleAndKeywords(args, kwargs, (char *)"OO:BVHTreeCustom", (char **)keywords,
+ &py_verts, &py_tris))
+ {
+ return -1;
+ }
+
+ if (!PySequence_Check(py_verts)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sequence of vectors");
+ return -1;
+ }
+
+ if (!PySequence_Check(py_tris)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sequence of lists of integers");
+ return -1;
+ }
+
+ if (valid) {
+ numverts = (int)PySequence_Size(py_verts);
+ vp = verts = MEM_mallocN(sizeof(BVHVertex) * (size_t)numverts, "BPy BVHTree vertices");
+ for (i = 0; i < numverts; i++, vp++) {
+ PyObject *py_vert = PySequence_GetItem(py_verts, i);
+
+ if (mathutils_array_parse(vp->co, 3, 3, py_vert, "BVHTree vertex: ") == -1) {
+ valid = false;
+ break;
+ }
+ }
+ }
+
+ if (valid) {
+ numtris = (int)PySequence_Size(py_tris);
+ /* now construct loop list */
+ tp = tris = MEM_mallocN(sizeof(BVHTriangle) * (size_t)numtris, "BPy BVHTree triangles");
+ for (i = 0; i < numtris; i++) {
+ PyObject *py_triverts = PySequence_GetItem(py_tris, i);
+ int tottri = (int)PySequence_Size(py_triverts);
+
+ if (tottri != 3) {
+ Py_XDECREF(py_triverts); /* may be null so use Py_XDECREF*/
+ PyErr_SetString(PyExc_TypeError,
+ "One or more of the triangles does not have 3 indices");
+ valid = false;
+ break;
+ }
+
+ tp->v1 = (int)PyLong_AsLong(PySequence_GetItem(py_triverts, 0));
+ tp->v2 = (int)PyLong_AsLong(PySequence_GetItem(py_triverts, 1));
+ tp->v3 = (int)PyLong_AsLong(PySequence_GetItem(py_triverts, 2));
+ }
+ }
+
+ if (valid) {
+ self->vert = verts;
+ self->totvert = numverts;
+ self->tri = tris;
+ self->tottri = numtris;
+
+ /* XXX make configurable? */
+ self->epsilon = 0.0f;
+
+ self->tree = bvhtree_from_triangles_create_tree(self->epsilon, 4, 6, self->vert, self->tri, self->tottri);
+
+ return 0;
+ }
+ else {
+ if (verts)
+ MEM_freeN(verts);
+ if (tris)
+ MEM_freeN(tris);
+
+ return -1;
+ }
+}
+
+static void PyBVHTreeCustom__tp_dealloc(PyBVHTree_Custom *self)
+{
+ if (self->tree)
+ BLI_bvhtree_free(self->tree);
+
+ if (self->vert)
+ MEM_freeN(self->vert);
+ if (self->tri)
+ MEM_freeN(self->tri);
+
+ Py_TYPE(self)->tp_free((PyObject *)self);
+}
+
+static void bvhtree_custom_raycast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+ PyBVHTree_Custom *self = (PyBVHTree_Custom *)userdata;
+ const BVHVertex *verts = self->vert;
+ const BVHTriangle *tris = self->tri;
+
+ const float *t0, *t1, *t2;
+ t0 = verts[ tris[index].v1 ].co;
+ t1 = verts[ tris[index].v2 ].co;
+ t2 = verts[ tris[index].v3 ].co;
+
+ {
+ float dist;
+ if (self->epsilon == 0.0f)
+ dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+ else
+ dist = bvhtree_sphereray_tri_intersection(ray, self->epsilon, hit->dist, t0, t1, t2);
+
+ if (dist >= 0 && dist < hit->dist) {
+ hit->index = index;
+ hit->dist = dist;
+ madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
+
+ normal_tri_v3(hit->no, t0, t1, t2);
+ }
+ }
+}
+
+PyDoc_STRVAR(py_BVHTreeCustom_ray_cast_doc,
+".. method:: ray_cast(ray_start, ray_end)\n"
+"\n"
+" Cast a ray onto the mesh.\n"
+"\n"
+" :arg ray_point: Start location of the ray in object space.\n"
+" :type ray_point: :class:`Vector`\n"
+" :arg ray_direction: Direction of the ray in object space.\n"
+" :type ray_direction: :class:`Vector`\n"
+" :arg ray_maxdist: Maximum distance of intersection.\n"
+" :type ray_maxdist: :float\n"
+" :return: Returns a tuple (:class:`Vector` location, :class:`Vector` normal, int index, float distance), index==-1 if no hit was found.\n"
+" :rtype: :class:`tuple`\n"
+);
+static PyObject *py_BVHTreeCustom_ray_cast(PyBVHTree_Custom *self, PyObject *args)
+{
+ const char *error_prefix = "ray_cast";
+
+ PyObject *py_point, *py_direction;
+ float ray_point[3], ray_direction[3];
+ float ray_maxdist = FLT_MAX;
+
+ if (!PyArg_ParseTuple(args, (char *)"OO|f:ray_cast", &py_point, &py_direction, &ray_maxdist))
+ {
+ return NULL;
+ }
+
+ if (mathutils_array_parse(ray_point, 2, 3, py_point, error_prefix) == -1 ||
+ mathutils_array_parse(ray_direction, 2, 3, py_direction, error_prefix) == -1)
+ {
+ return NULL;
+ }
+
+ normalize_v3(ray_direction);
+
+ /* may fail if the mesh has no faces, in that case the ray-cast misses */
+ if (self->tree) {
+ BVHTreeRayHit hit;
+ hit.dist = ray_maxdist;
+ hit.index = -1;
+
+ if (BLI_bvhtree_ray_cast(self->tree, ray_point, ray_direction, 0.0f, &hit,
+ bvhtree_custom_raycast_cb, self) != -1)
+ {
+ if (hit.dist <= ray_maxdist) {
+ return bvhtree_ray_hit_to_py(hit.co, hit.no, hit.index, hit.dist);
+ }
+ }
+ }
+
+ return bvhtree_ray_hit_to_py(NULL, NULL, -1, 0.0f);
+}
+
+/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_faces.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
+static void bvhtree_custom_nearest_point_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
+{
+ PyBVHTree_Custom *self = (PyBVHTree_Custom *)userdata;
+ const BVHVertex *verts = self->vert;
+ const BVHTriangle *tris = self->tri;
+
+ const float *t0, *t1, *t2, *t3;
+ t0 = verts[ tris->v1 ].co;
+ t1 = verts[ tris->v2 ].co;
+ t2 = verts[ tris->v3 ].co;
+
+ {
+ float nearest_tmp[3], dist_sq;
+
+ closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
+ dist_sq = len_squared_v3v3(co, nearest_tmp);
+
+ if (dist_sq < nearest->dist_sq) {
+ nearest->index = index;
+ nearest->dist_sq = dist_sq;
+ copy_v3_v3(nearest->co, nearest_tmp);
+ normal_tri_v3(near
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list