blender
/
blender
134
399
Fork 581
Code Issues 6.2k Pull Requests 753 Projects 19 Wiki Activity

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
This commit is contained in:
Mikkel Gjoel 2021-09-04 22:44:18 +10:00 committed by Campbell Barton
parent e6194e7357
commit 863d806526
1 changed files with 14 additions and 11 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

25
source/blender/bmesh/intern/bmesh_query.c
View File

@ -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;
}