diff options
author | Henrik Dick <weasel> | 2020-09-21 18:30:49 +0300 |
---|---|---|
committer | Germano Cavalcante <germano.costa@ig.com.br> | 2020-09-21 22:29:33 +0300 |
commit | 8eda3ddc4f047fcf7d8bd71d4fea958d8005ade8 (patch) | |
tree | 090ccda61036ccd5235f74d5e3b20e06c34f2ced /source/blender/modifiers | |
parent | 6a9e9bef44d2aff5f115d6798ae1c7c6d486a393 (diff) |
Weld Modifier: Performance improvement
This commit contains the Performance improvement, that was originally
proposed in D8966.
It improves the performance of the Weld Modifier by a lot.
It had a loop with execution time O(N^2) which is now O(N*log(N)) at a
bare maximum.
Diffstat (limited to 'source/blender/modifiers')
-rw-r--r-- | source/blender/modifiers/intern/MOD_weld.c | 69 |
1 files changed, 28 insertions, 41 deletions
diff --git a/source/blender/modifiers/intern/MOD_weld.c b/source/blender/modifiers/intern/MOD_weld.c index 855f96df82f..d7d24062fc5 100644 --- a/source/blender/modifiers/intern/MOD_weld.c +++ b/source/blender/modifiers/intern/MOD_weld.c @@ -390,10 +390,7 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len, uint *r_wvert_len, uint *r_vert_kill_len) { - uint *v_dest_iter = &r_vert_dest_map[0]; - for (uint i = mvert_len; i--; v_dest_iter++) { - *v_dest_iter = OUT_OF_CONTEXT; - } + range_vn_u(r_vert_dest_map, mvert_len, 0); uint vert_kill_len = 0; const BVHTreeOverlap *overlap_iter = &overlap[0]; @@ -404,46 +401,36 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len, BLI_assert(indexA < indexB); uint va_dst = r_vert_dest_map[indexA]; + while (va_dst != r_vert_dest_map[va_dst]) { + va_dst = r_vert_dest_map[va_dst]; + } uint vb_dst = r_vert_dest_map[indexB]; - if (va_dst == OUT_OF_CONTEXT) { - if (vb_dst == OUT_OF_CONTEXT) { - vb_dst = indexA; - r_vert_dest_map[indexB] = vb_dst; - } - r_vert_dest_map[indexA] = vb_dst; - vert_kill_len++; + while (vb_dst != r_vert_dest_map[vb_dst]) { + vb_dst = r_vert_dest_map[vb_dst]; } - else if (vb_dst == OUT_OF_CONTEXT) { - r_vert_dest_map[indexB] = va_dst; - vert_kill_len++; + if (va_dst == vb_dst) { + continue; } - else if (va_dst != vb_dst) { - uint v_new, v_old; - if (va_dst < vb_dst) { - v_new = va_dst; - v_old = vb_dst; - } - else { - v_new = vb_dst; - v_old = va_dst; - } - BLI_assert(r_vert_dest_map[v_old] == v_old); - BLI_assert(r_vert_dest_map[v_new] == v_new); - vert_kill_len++; - - const BVHTreeOverlap *overlap_iter_b = &overlap[0]; - for (uint j = i + 1; j--; overlap_iter_b++) { - indexA = overlap_iter_b->indexA; - indexB = overlap_iter_b->indexB; - va_dst = r_vert_dest_map[indexA]; - vb_dst = r_vert_dest_map[indexB]; - if (ELEM(v_old, vb_dst, va_dst)) { - r_vert_dest_map[indexA] = v_new; - r_vert_dest_map[indexB] = v_new; - } - } - BLI_assert(r_vert_dest_map[v_old] == v_new); + if (va_dst > vb_dst) { + SWAP(uint, va_dst, vb_dst); + } + vert_kill_len++; + r_vert_dest_map[vb_dst] = va_dst; + } + + /* Fix #r_vert_dest_map for next step. */ + for (uint i = 0; i < mvert_len; i++) { + if (i == r_vert_dest_map[i]) { + r_vert_dest_map[i] = OUT_OF_CONTEXT; + continue; + } + + uint v = i; + while (v != r_vert_dest_map[v] && r_vert_dest_map[v] != OUT_OF_CONTEXT) { + v = r_vert_dest_map[v]; } + r_vert_dest_map[v] = v; + r_vert_dest_map[i] = v; } /* Vert Context. */ @@ -453,7 +440,7 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len, wvert = MEM_mallocN(sizeof(*wvert) * mvert_len, __func__); wv = &wvert[0]; - v_dest_iter = &r_vert_dest_map[0]; + uint *v_dest_iter = &r_vert_dest_map[0]; for (uint i = 0; i < mvert_len; i++, v_dest_iter++) { if (*v_dest_iter != OUT_OF_CONTEXT) { wv->vert_dest = *v_dest_iter; |