Optimize BVHTree creation of vertices that have BLI_bitmap test

Instead of reference the vertex first and test the bitmap afterwards. Test the bitmap first and reference the vertex after.

In a mesh with 31146 vertices and the entire bitmap disabled, the loop time is 243% faster
With all bitmap enabled, the time becomes 463473% faster!!!

One possible reason for this huge difference in peformance is that maybe the compiler is not putting the function "BM_vert_at_index" inline (I dont know if buildbot do this, but it's good to investigate).

1 files changed, 40 insertions, 6 deletions

diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index 264d87b86f3..126c37f87b1 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -387,7 +387,7 @@ static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *r
 
 /** \name Vertex Builder
  * \{ */
-
+#include "PIL_time.h"
 static BVHTree *bvhtree_from_editmesh_verts_create_tree(
         float epsilon, int tree_type, int axis,
         BMEditMesh *em, const int verts_num,
@@ -403,16 +403,50 @@ static BVHTree *bvhtree_from_editmesh_verts_create_tree(
 		verts_num_active = verts_num;
 	}
 
+	float dummy[3];
+	double t1 = PIL_check_seconds_timer();
+
+	/* loop 1: BM_ITER */
+	BMIter iter;
+	BMVert *eve;
+	BM_ITER_MESH_INDEX(eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
+		if (!verts_mask || BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
+			copy_v3_v3(dummy, eve->co);
+		}
+	}
+	double t2 = PIL_check_seconds_timer();
+
+	/* loop 2: BM_vert_at_index */
+	for (int i = 0; i < verts_num_active; i++) {
+		if (!verts_mask || BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
+			BMVert *eve = BM_vert_at_index(em->bm, i);
+			copy_v3_v3(dummy, eve->co);
+		}
+	}
+	double t3 = PIL_check_seconds_timer();
+
+	/* loop 3: vtable */
+	for (int i = 0; i < verts_num_active; i++) {
+		if (!verts_mask || BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
+			BMVert *eve = em->bm->vtable[i];
+			copy_v3_v3(dummy, eve->co);
+		}
+	}
+	double t4 = PIL_check_seconds_timer();
+	printf("loop_bmes = %lf\n", (t2 - t1));
+	printf("loop_mask = %lf\n", (t3 - t2));
+	printf("loop_mvtb = %lf\n", (t4 - t3));
+	printf("factor___ = %lf\n", (t2 - t1) / (t3 - t2));
+
 	tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
 
 	if (tree) {
 		BMIter iter;
-		BMVert *eve;
-		BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
-			if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
-				continue;
+		for (int i = 0; i < verts_num; i++) {
+			if (!verts_mask || BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
+				BMVert *eve = BM_vert_at_index(em->bm, i);
+				BLI_bvhtree_insert(tree, i, eve->co, 1);
 			}
-			BLI_bvhtree_insert(tree, i, eve->co, 1);
 		}
 		BLI_assert(BLI_bvhtree_get_size(tree) == verts_num_active);
 		BLI_bvhtree_balance(tree);