BMesh: optimize edge & face group calculation

This changes the search for unprocessed faces to only search
from the previously found face. Local testing on 1.5 million
triangle meshes gives a 75x speedup
(of the code affected, which is the first half of the work).

The former code would traverse all faces of a mesh until a face was
found that had not been processed. This ended up being slow mainly
because it had to load face-data to determine the state of the flag.
Secondarily, the way it iterated and marked the mesh, it would end up
traversing all previously processed faces to find and unprocessed one.

The same optimization has been made for edge-group calculation.

Reviewed By: campbellbarton

Ref D12379

1 files changed, 14 insertions, 11 deletions

diff --git a/source/blender/bmesh/intern/bmesh_query.c b/source/blender/bmesh/intern/bmesh_query.c
index cb5764b1c91..795d8829ee7 100644
--- a/source/blender/bmesh/intern/bmesh_query.c
+++ b/source/blender/bmesh/intern/bmesh_query.c
@@ -2637,7 +2637,7 @@ int BM_mesh_calc_face_groups(BMesh *bm,
   STACK_DECLARE(stack);
 
   BMIter iter;
-  BMFace *f;
+  BMFace *f, *f_next;
   int i;
 
   STACK_INIT(group_array, bm->totface);
@@ -2662,6 +2662,8 @@ int BM_mesh_calc_face_groups(BMesh *bm,
   /* detect groups */
   stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
 
+  f_next = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL);
+
   while (tot_touch != tot_faces) {
     int *group_item;
     bool ok = false;
@@ -2670,10 +2672,10 @@ int BM_mesh_calc_face_groups(BMesh *bm,
 
     STACK_INIT(stack, tot_faces);
 
-    BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
-      if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
-        BM_elem_flag_enable(f, BM_ELEM_TAG);
-        STACK_PUSH(stack, f);
+    for (; f_next; f_next = BM_iter_step(&iter)) {
+      if (BM_elem_flag_test(f_next, BM_ELEM_TAG) == false) {
+        BM_elem_flag_enable(f_next, BM_ELEM_TAG);
+        STACK_PUSH(stack, f_next);
         ok = true;
         break;
       }
@@ -2799,9 +2801,8 @@ int BM_mesh_calc_edge_groups(BMesh *bm,
   STACK_DECLARE(stack);
 
   BMIter iter;
-  BMEdge *e;
+  BMEdge *e, *e_next;
   int i;
-
   STACK_INIT(group_array, bm->totedge);
 
   /* init the array */
@@ -2822,6 +2823,8 @@ int BM_mesh_calc_edge_groups(BMesh *bm,
   /* detect groups */
   stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
 
+  e_next = BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, NULL);
+
   while (tot_touch != tot_edges) {
     int *group_item;
     bool ok = false;
@@ -2830,10 +2833,10 @@ int BM_mesh_calc_edge_groups(BMesh *bm,
 
     STACK_INIT(stack, tot_edges);
 
-    BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
-      if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
-        BM_elem_flag_enable(e, BM_ELEM_TAG);
-        STACK_PUSH(stack, e);
+    for (; e_next; e_next = BM_iter_step(&iter)) {
+      if (BM_elem_flag_test(e_next, BM_ELEM_TAG) == false) {
+        BM_elem_flag_enable(e_next, BM_ELEM_TAG);
+        STACK_PUSH(stack, e_next);
         ok = true;
         break;
       }