[Bf-blender-cvs] [62cc4ba] master: BKE bvhutils: cleanup and refactor to make it more flexible.
Bastien Montagne
noreply at git.blender.org
Fri Jan 9 13:04:36 CET 2015
Commit: 62cc4bab083893a85e451ab96455c9be60c04cc1
Author: Bastien Montagne
Date: Fri Jan 9 12:25:18 2015 +0100
Branches: master
https://developer.blender.org/rB62cc4bab083893a85e451ab96455c9be60c04cc1
BKE bvhutils: cleanup and refactor to make it more flexible.
You can now use lower-level '_ex' versions of bvh creators to only use part of
the mesh's elements in the BVH, and/or create bvh from non-DM sources.
Needed for transfer data.
Note edges extend version of bvh creator is not added here, not needed so far.
===================================================================
M source/blender/blenkernel/BKE_bvhutils.h
M source/blender/blenkernel/intern/bvhutils.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index 4bc8fc4..a360511 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -31,6 +31,7 @@
* \ingroup bke
*/
+#include "BLI_bitmap.h"
#include "BLI_kdopbvh.h"
/*
@@ -56,8 +57,8 @@ typedef struct BVHTreeFromMesh {
struct MEdge *edge; /* only used for BVHTreeFromMeshEdges */
struct MFace *face;
bool vert_allocated;
- bool face_allocated;
bool edge_allocated;
+ bool face_allocated;
/* radius for raycast */
float sphere_radius;
@@ -69,36 +70,28 @@ typedef struct BVHTreeFromMesh {
} BVHTreeFromMesh;
/*
- * Builds a bvh tree where nodes are the vertexs of the given mesh.
+ * Builds a bvh tree where nodes are the relevant elements of the given mesh.
* Configures BVHTreeFromMesh.
*
* The tree is build in mesh space coordinates, this means special care must be made on queries
* so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
- * a BVHTree.
+ * Reason for this is that bvh_from_mesh_* can use a cache in some cases and so it becomes possible to reuse a BVHTree.
*
* free_bvhtree_from_mesh should be called when the tree is no longer needed.
*/
BVHTree *bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
-
-/*
- * Builds a bvh tree where nodes are the faces of the given mesh.
- * Configures BVHTreeFromMesh.
- *
- * The tree is build in mesh space coordinates, this means special care must be made on queries
- * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
- * a BVHTree.
- *
- * The returned value is the same as in data->tree, its only returned to make it easier to test
- * the success
- *
- * free_bvhtree_from_mesh should be called when the tree is no longer needed.
- */
-BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const int numVerts,
+ const bool vert_allocated, BLI_bitmap *mask, int numVerts_active,
+ float epsilon, int tree_type, int axis);
BVHTree *bvhtree_from_mesh_edges(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data, struct MVert *vert, const bool vert_allocated,
+ struct MFace *face, const int numFaces, const bool face_allocated,
+ BLI_bitmap *mask, int numFaces_active,
+ float epsilon, int tree_type, int axis);
+
/*
* Frees data allocated by a call to bvhtree_from_mesh_*.
*/
@@ -114,12 +107,13 @@ float nearest_point_in_tri_surface_squared(const float v0[3], const float v1[3],
* BVHCache
*/
-//Using local coordinates
-#define BVHTREE_FROM_FACES 0
-#define BVHTREE_FROM_VERTICES 1
-#define BVHTREE_FROM_EDGES 2
-
-#define BVHTREE_FROM_FACES_EDITMESH 3
+/* Using local coordinates */
+enum {
+ BVHTREE_FROM_VERTS = 0,
+ BVHTREE_FROM_EDGES = 1,
+ BVHTREE_FROM_FACES = 2,
+ BVHTREE_FROM_FACES_EDITMESH = 3,
+};
typedef struct LinkNode *BVHCache;
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index a3b65b9..1a4a4bd 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -79,7 +79,7 @@ static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, con
* BVH from meshes callbacks
*/
-/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
+/* 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 mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
{
@@ -143,7 +143,7 @@ static void editmesh_faces_nearest_point(void *userdata, int index, const float
}
}
-/* Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
+/* Callback to bvh tree raycast. 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 mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
{
@@ -212,7 +212,7 @@ static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRa
}
}
-/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
+/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges.
* userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
{
@@ -237,68 +237,140 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3
}
}
-/*
- * BVH builders
- */
-/* Builds a bvh tree.. where nodes are the vertexs of the given mesh */
-BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
+/* Helper, does all the point-spherecast work actually. */
+static void mesh_verts_spherecast_do(
+ const BVHTreeFromMesh *UNUSED(data), int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit)
{
- BVHTree *tree;
- MVert *vert;
- bool vert_allocated;
+ float dist;
+ const float *r1;
+ float r2[3], i1[3];
+ r1 = ray->origin;
+ add_v3_v3v3(r2, r1, ray->direction);
+
+ closest_to_line_segment_v3(i1, v, r1, r2);
+
+ /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
+ if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
+ hit->index = index;
+ hit->dist = dist;
+ copy_v3_v3(hit->co, i1);
+ }
+}
- BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
- tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
- BLI_rw_mutex_unlock(&cache_rwlock);
+/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
+static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+ const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
+ float *v = data->vert[index].co;
- vert = DM_get_vert_array(dm, &vert_allocated);
+ mesh_verts_spherecast_do(data, index, v, ray, hit);
+}
- /* Not in cache */
- if (tree == NULL) {
- BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
- tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
- if (tree == NULL) {
- int i;
- int numVerts = dm->getNumVerts(dm);
+/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
+static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+ const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
+ MVert *vert = data->vert;
+ MEdge *edge = &data->edge[index];
- if (vert != NULL) {
- tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
+ const float radius_sq = SQUARE(data->sphere_radius);
+ float dist;
+ const float *v1, *v2, *r1;
+ float r2[3], i1[3], i2[3];
+ v1 = vert[edge->v1].co;
+ v2 = vert[edge->v2].co;
+
+ /* In case we get a zero-length edge, handle it as a point! */
+ if (equals_v3v3(v1, v2)) {
+ mesh_verts_spherecast_do(data, index, v1, ray, hit);
+ return;
+ }
- if (tree != NULL) {
- for (i = 0; i < numVerts; i++) {
- BLI_bvhtree_insert(tree, i, vert[i].co, 1);
- }
+ r1 = ray->origin;
+ add_v3_v3v3(r2, r1, ray->direction);
- BLI_bvhtree_balance(tree);
+ if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
+ /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
+ if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
+ const float e_fac = line_point_factor_v3(i1, v1, v2);
+ if (e_fac < 0.0f) {
+ copy_v3_v3(i1, v1);
+ }
+ else if (e_fac > 1.0f) {
+ copy_v3_v3(i1, v2);
+ }
+ /* Ensure ray is really close enough from edge! */
+ if (len_squared_v3v3(i1, i2) <= radius_sq) {
+ hit->index = index;
+ hit->dist = dist;
+ copy_v3_v3(hit->co, i2);
+ }
+ }
+ }
+}
- /* Save on cache for later use */
-// printf("BVHTree built and saved on cache\n");
- bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTICES);
+/*
+ * BVH builders
+ */
+
+/* ***** Vertex ***** */
+
+static BVHTree *bvhtree_from_mesh_verts_create_tree(float epsilon, int tree_type, int axis,
+ MVert *vert, const int numVerts,
+ BLI_bitmap *mask, int numVerts_active)
+{
+ BVHTree *tree = NULL;
+ int i;
+
+ if (vert) {
+ if (mask && numVerts_active < 0) {
+ numVerts_active = 0;
+ for (i = 0; i < numVerts; i++) {
+ if (BLI_BITMAP_TEST_BOOL(mask, i)) {
+ numVerts_active++;
}
}
}
- BLI_rw_mutex_unlock(&cache_rwlock);
- }
- else {
-// printf("BVHTree is already build, using cached tree\n");
+ else if (!mask) {
+ numVerts_active = numVerts;
+ }
+
+ tree = BLI_bvhtree_new(numVerts_active, epsilon, tree_type, axis);
+
+ if (tree) {
+ for (i = 0; i < numVerts; i++) {
+ if (mask && !BLI_BITMAP_TEST_BOOL(
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list