Transform: optimize vertex snap w/ nearest-to-ray
authorGermano Cavalcante <germano.costa@ig.com.br>
Mon, 25 Jan 2016 07:18:42 +0000 (18:18 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Mon, 25 Jan 2016 08:01:54 +0000 (19:01 +1100)
Use BLI_bvhtree_find_nearest_to_ray for vertex snapping,
avoids doing screen-space lookup on each vertex.

source/blender/blenkernel/BKE_bvhutils.h
source/blender/blenkernel/intern/bvhutils.c
source/blender/editors/transform/transform_snap.c

index 749b0db7c272e38437ab2ec12a0b01809c540264..08c0fcc0f3c6f5fc4f61dd67349424ab0d5e9cfd 100644 (file)
@@ -51,6 +51,7 @@ typedef struct BVHTreeFromMesh {
        /* default callbacks to bvh nearest and raycast */
        BVHTree_NearestPointCallback nearest_callback;
        BVHTree_RayCastCallback raycast_callback;
+       BVHTree_NearestToRayCallback nearest_to_ray_callback;
 
        /* Vertex array, so that callbacks have instante access to data */
        const struct MVert *vert;
@@ -147,6 +148,8 @@ enum {
        BVHTREE_FROM_FACES_EDITMESH_ALL     = 4,
        /* visible unselected, only used for transform snapping */
        BVHTREE_FROM_FACES_EDITMESH_SNAP    = 5,
+       // BVHTREE_FROM_EDGES_EDITMESH_SNAP    = 6,
+       BVHTREE_FROM_VERTS_EDITMESH_SNAP    = 7,
 };
 
 typedef struct LinkNode *BVHCache;
index 9004985aebddc7f50293eae851773d759439380e..dfa6c6fb1033c5b300c05465d8cdbcf3a58e19f5 100644 (file)
@@ -382,17 +382,40 @@ static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *r
 
 static BVHTree *bvhtree_from_mesh_verts_create_tree(
         float epsilon, int tree_type, int axis,
+        BMEditMesh *em, const int *index_array,
         MVert *vert, const int numVerts,
         BLI_bitmap *mask, int numVerts_active)
 {
        BVHTree *tree = NULL;
+       BMVert *eve = NULL;
        int i;
-
+       int index = 0;
+       if (em != NULL) {
+               BM_mesh_elem_table_ensure(em->bm, BM_VERT);
+       }
        if (vert) {
                if (mask && numVerts_active < 0) {
                        numVerts_active = 0;
                        for (i = 0; i < numVerts; i++) {
                                if (BLI_BITMAP_TEST_BOOL(mask, i)) {
+                                       if (em != NULL) {
+                                               if (index_array){
+                                                       index = index_array[i];
+                                                       if (index == ORIGINDEX_NONE) {
+                                                               continue;
+                                                       }
+                                               }
+                                               else {
+                                                       index = i;
+                                               }
+
+                                               eve = BM_vert_at_index(em->bm, index);
+                                               if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
+                                                   BM_elem_flag_test(eve, BM_ELEM_SELECT))
+                                               {
+                                                       continue;
+                                               }
+                                       }
                                        numVerts_active++;
                                }
                        }
@@ -408,6 +431,24 @@ static BVHTree *bvhtree_from_mesh_verts_create_tree(
                                if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
                                        continue;
                                }
+                               if (em != NULL) {
+                                       if (index_array){
+                                               index = index_array[i];
+                                               if (index == ORIGINDEX_NONE) {
+                                                       continue;
+                                               }
+                                       }
+                                       else {
+                                               index = i;
+                                       }
+
+                                       eve = BM_vert_at_index(em->bm, index);
+                                       if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
+                                           BM_elem_flag_test(eve, BM_ELEM_SELECT))
+                                       {
+                                               continue;
+                                       }
+                               }
                                BLI_bvhtree_insert(tree, i, vert[i].co, 1);
                        }
 
@@ -432,6 +473,7 @@ static void bvhtree_from_mesh_verts_setup_data(
                 * remember the min distance to point is the same as the min distance to BV of point */
                data->nearest_callback = NULL;
                data->raycast_callback = mesh_verts_spherecast;
+               data->nearest_to_ray_callback = NULL;
 
                data->vert = vert;
                data->vert_allocated = vert_allocated;
@@ -449,12 +491,14 @@ static void bvhtree_from_mesh_verts_setup_data(
 /* Builds a bvh tree where nodes are the vertices of the given dm */
 BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
+       BMEditMesh *em = data->em_evil;
+       const int bvhcache_type = em ? BVHTREE_FROM_VERTS_EDITMESH_SNAP : BVHTREE_FROM_VERTS;
        BVHTree *tree;
        MVert *vert;
        bool vert_allocated;
 
        BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-       tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
+       tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
        BLI_rw_mutex_unlock(&cache_rwlock);
 
        vert = DM_get_vert_array(dm, &vert_allocated);
@@ -462,13 +506,26 @@ BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float e
        /* Not in cache */
        if (tree == NULL) {
                BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-               tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTS);
+               tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
                if (tree == NULL) {
-                       tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, dm->getNumVerts(dm), NULL, -1);
+                       int vert_num, *index_array = NULL;
+                       if (em != NULL) {
+                               vert_num = em->bm->totvert;
+                               index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
+                       }
+                       else {
+                               vert_num = dm->getNumVerts(dm);
+                               BLI_assert(vert_num != 0);
+                       }
+                       tree = bvhtree_from_mesh_verts_create_tree(
+                               epsilon, tree_type, axis,
+                               em, index_array,
+                               vert, vert_num, NULL, -1);
+
                        if (tree) {
                                /* Save on cache for later use */
                                /* printf("BVHTree built and saved on cache\n"); */
-                               bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTS);
+                               bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
                        }
                }
                BLI_rw_mutex_unlock(&cache_rwlock);
@@ -494,7 +551,7 @@ BVHTree *bvhtree_from_mesh_verts_ex(
         BLI_bitmap *mask, int numVerts_active,
         float epsilon, int tree_type, int axis)
 {
-       BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, vert, numVerts, mask, numVerts_active);
+       BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, NULL, NULL, vert, numVerts, mask, numVerts_active);
 
        /* Setup BVHTreeFromMesh */
        bvhtree_from_mesh_verts_setup_data(data, tree, false, epsilon, vert, vert_allocated);
@@ -568,6 +625,7 @@ BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float e
 
                data->nearest_callback = mesh_edges_nearest_point;
                data->raycast_callback = mesh_edges_spherecast;
+               data->nearest_to_ray_callback = NULL;
 
                data->vert = vert;
                data->vert_allocated = vert_allocated;
@@ -723,10 +781,12 @@ static void bvhtree_from_mesh_faces_setup_data(
                if (em) {
                        data->nearest_callback = editmesh_faces_nearest_point;
                        data->raycast_callback = editmesh_faces_spherecast;
+                       data->nearest_to_ray_callback = NULL;
                }
                else {
                        data->nearest_callback = mesh_faces_nearest_point;
                        data->raycast_callback = mesh_faces_spherecast;
+                       data->nearest_to_ray_callback = NULL;
 
                        data->vert = vert;
                        data->vert_allocated = vert_allocated;
@@ -968,10 +1028,12 @@ static void bvhtree_from_mesh_looptri_setup_data(
                if (em) {
                        data->nearest_callback = editmesh_faces_nearest_point;
                        data->raycast_callback = editmesh_faces_spherecast;
+                       data->nearest_to_ray_callback = NULL;
                }
                else {
                        data->nearest_callback = mesh_looptri_nearest_point;
                        data->raycast_callback = mesh_looptri_spherecast;
+                       data->nearest_to_ray_callback = NULL;
 
                        data->vert = vert;
                        data->vert_allocated = vert_allocated;
index ed48478246f2b2bf0444368ccdbccd961617bb03..8e02a402bf83234b608d6d824202fe5ced391556 100644 (file)
@@ -1660,50 +1660,26 @@ static bool snapDerivedMesh(
                        }
                        case SCE_SNAP_MODE_VERTEX:
                        {
-                               MVert *verts = dm->getVertArray(dm);
-                               const int *index_array = NULL;
-                               int index = 0;
-                               int i;
-
-                               if (em != NULL) {
-                                       index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
-                                       BM_mesh_elem_table_ensure(em->bm, BM_VERT);
-                               }
-
-                               for (i = 0; i < totvert; i++) {
-                                       BMVert *eve = NULL;
-                                       MVert *v = verts + i;
-                                       bool test = true;
+                               BVHTreeNearest nearest;
+                               BVHTreeFromMesh treeData;
 
-                                       if (em != NULL) {
-                                               if (index_array) {
-                                                       index = index_array[i];
-                                               }
-                                               else {
-                                                       index = i;
-                                               }
-                                               
-                                               if (index == ORIGINDEX_NONE) {
-                                                       test = false;
-                                               }
-                                               else {
-                                                       eve = BM_vert_at_index(em->bm, index);
-                                                       
-                                                       if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
-                                                           BM_elem_flag_test(eve, BM_ELEM_SELECT))
-                                                       {
-                                                               test = false;
-                                                       }
-                                               }
-                                       }
+                               treeData.em_evil = em;
+                               bvhtree_from_mesh_verts(&treeData, dm, 0.0f, 2, 6);
 
-                                       if (test) {
-                                               retval |= snapVertex(
-                                                       ar, v->co, v->no, obmat, timat, mval,
-                                                       ray_start, ray_start_local, ray_normal_local, ray_depth,
-                                                       r_loc, r_no, r_dist_px);
-                                       }
+                               nearest.index = -1;
+                               nearest.dist_sq = FLT_MAX;
+                               if (treeData.tree &&
+                                   BLI_bvhtree_find_nearest_to_ray(
+                                       treeData.tree, ray_start_local, ray_normal_local, 0.0f,
+                                       &nearest, NULL, &treeData) != -1)
+                               {
+                                       MVert v = treeData.vert[nearest.index];
+                                       retval = snapVertex(
+                                               ar, v.co, v.no, obmat, timat, mval,
+                                               ray_start, ray_start_local, ray_normal_local, ray_depth,
+                                               r_loc, r_no, r_dist_px);
                                }
+                               free_bvhtree_from_mesh(&treeData);
 
                                break;
                        }