diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-09-15 22:06:19 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-09-15 22:15:09 +0300 |
commit | 7c8e87fc52d1e6c283f69b1aaaccfc98872f006b (patch) | |
tree | 0c0d1afbdd53782d2ac8d1802a073eff689e2a79 /source/blender/bmesh | |
parent | 14eadf55fddb08d4b62a53eb59b04439ed66d187 (diff) |
Fix T52384: Bridge pair result depends on other loops
When 2x loops have different number of vertices,
the distribution for vertices fan-fill depended on the loop order
and was often lop-sided.
This caused noticeable inconstancies depending on the input
since edge-loops are flipped to match each others winding order.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_edgeloop.c | 83 |
1 files changed, 53 insertions, 30 deletions
diff --git a/source/blender/bmesh/intern/bmesh_edgeloop.c b/source/blender/bmesh/intern/bmesh_edgeloop.c index 5780dc57d78..16c1b2cc6d0 100644 --- a/source/blender/bmesh/intern/bmesh_edgeloop.c +++ b/source/blender/bmesh/intern/bmesh_edgeloop.c @@ -708,41 +708,64 @@ void BM_edgeloop_expand( } if (el_store->len < el_store_len) { - const int step = max_ii(1, el_store->len / (el_store->len % el_store_len)); - LinkData *node_first = el_store->verts.first; - LinkData *node_curr = node_first; + LinkData *node_curr = el_store->verts.first; - do { - LinkData *node_curr_init = node_curr; - LinkData *node_curr_copy; - int i = 0; - BLI_LISTBASE_CIRCULAR_FORWARD_BEGIN (&el_store->verts, node_curr, node_curr_init) { - if (i++ < step) { - break; + /** + * Bresenham's line algorithm is used for even spaced edge-loop distribution. + * + * Step over x until y reaches a large enough error and a new pivot is added. + * Note that x/y aren't meaningful in this context, but keep since logic matches line drawing. + */ + const int x_span = el_store->len; + const int y_span = el_store_len - el_store->len; + + const int x_span_2x = x_span * 2; + const int y_span_2x = y_span * 2; + + BLI_assert(x_span >= y_span); + + /* error may go below zero */ + int error = y_span_2x - x_span; + + int x_iter = 0; /* traverse elements in 'el_store->len'. */ + int y_iter = 0; /* each step on this variable represents a new pivot. */ + + while (x_iter != x_span) { + if (error >= 0) { + y_iter += 1; + error -= x_span_2x; + + /* Split logic */ + { + LinkData *node_curr_copy; + node_curr_copy = MEM_dupallocN(node_curr); + if (split == false) { + BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); + node_curr = node_curr_copy->next; + } + else { + if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) { + EDGE_SPLIT(node_curr_copy, + node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first); + BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); + node_curr = node_curr_copy->next; + } + else { + EDGE_SPLIT(node_curr_copy, node_curr->prev); + BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy); + node_curr = node_curr->next; + } + split_swap = !split_swap; + } + el_store->len++; } } - BLI_LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init); - - node_curr_copy = MEM_dupallocN(node_curr); - if (split == false) { - BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); - node_curr = node_curr_copy->next; - } else { - if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) { - EDGE_SPLIT(node_curr_copy, node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first); - BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy); - node_curr = node_curr_copy->next; - } - else { - EDGE_SPLIT(node_curr_copy, node_curr->prev); - BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy); - node_curr = node_curr->next; - } - split_swap = !split_swap; + node_curr = node_curr->next; } - el_store->len++; - } while (el_store->len < el_store_len); + x_iter += 1; + error += y_span_2x; + } } #undef EDGE_SPLIT |