blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

BMesh: improve edge rotate when edges share faces 

Previously outcome depended on order of edges,
now the longest boundary edges are rotated first,
then the faces connected edges.

This gives more predictable results, allowing regions containing
a vertex fan to be rotated onto the next vertex.
This commit is contained in:
Campbell Barton 2017-11-26 17:48:00 +11:00
parent 5b225c59bb
commit 329bf8e1bf
1 changed files with 204 additions and 32 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

236
source/blender/bmesh/operators/bmo_rotate_edge.c
View File

@ -27,62 +27,234 @@
#include "MEM_guardedalloc.h"
#include "BLI_math.h"
#include "BLI_heap.h"
#include "bmesh.h"
#include "intern/bmesh_operators_private.h" /* own include */
void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
#define EDGE_OUT 1
#define FACE_MARK 1
/**
* Rotate edges where every edge has it's own faces (we can rotate in any order).
*/
static void bm_rotate_edges_simple(
BMesh *bm, BMOperator *op,
const short check_flag, const bool use_ccw)
{
BMOIter siter;
BMEdge *e, *e2;
const bool use_ccw = BMO_slot_bool_get(op->slots_in, "use_ccw");
const bool is_single = BMO_slot_buffer_count(op->slots_in, "edges") == 1;
short check_flag = is_single ?
BM_EDGEROT_CHECK_EXISTS :
BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
#define EDGE_OUT 1
#define FACE_TAINT 1
BMEdge *e;
BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
/**
* this ends up being called twice, could add option to not to call check in
* #BM_edge_rotate to get some extra speed */
if (BM_edge_rotate_check(e)) {
BMFace *fa, *fb;
if (BM_edge_face_pair(e, &fa, &fb)) {
BMEdge *e_rotate = BM_edge_rotate(bm, e, use_ccw, check_flag);
if (e_rotate != NULL) {
BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
}
}
}
}
/* check we're untouched */
if (BMO_face_flag_test(bm, fa, FACE_TAINT) == false &&
BMO_face_flag_test(bm, fb, FACE_TAINT) == false)
{
/* don't touch again (faces will be freed so run before rotating the edge) */
BMO_face_flag_enable(bm, fa, FACE_TAINT);
BMO_face_flag_enable(bm, fb, FACE_TAINT);
/**
* Edge length is just a way of ordering that's independent of order in the edges argument,
* we could use some other method since ideally all edges will be rotated,
* this just happens to be simple to calculate.
*/
static float bm_edge_calc_rotate_cost(const BMEdge *e)
{
return -BM_edge_calc_length_squared(e);
}
if (!(e2 = BM_edge_rotate(bm, e, use_ccw, check_flag))) {
/**
* Check if this edge is a boundary: Are more than one of the connected faces edges rotating too?
*/
static float bm_edge_rotate_is_boundary(const BMEdge *e)
{
/* Number of adjacent shared faces. */
int count = 0;
BMLoop *l_radial_iter = e->l;
do {
/* Skip this edge. */
BMLoop *l_iter = l_radial_iter->next;
do {
BMEdge *e_iter = l_iter->e;
const int e_iter_index = BM_elem_index_get(e_iter);
if ((e_iter_index != -1)) {
if (count == 1) {
return false;
}
count += 1;
break;
}
} while ((l_iter = l_iter->next) != l_radial_iter);
} while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
return true;
}
BMO_face_flag_disable(bm, fa, FACE_TAINT);
BMO_face_flag_disable(bm, fb, FACE_TAINT);
#if 0
BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Could not rotate edge");
return;
#endif
/**
* Rotate edges where edges share faces,
* edges which could not rotate need to be re-considered after neighbors are rotated.
*/
static void bm_rotate_edges_shared(
BMesh *bm, BMOperator *op,
short check_flag, const bool use_ccw, const int edges_len)
{
Heap *heap = BLI_heap_new_ex(edges_len);
HeapNode **eheap_table = MEM_mallocN(sizeof(*eheap_table) * edges_len, __func__);
int edges_len_rotate = 0;
continue;
{
BMIter iter;
BMEdge *e;
BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
BM_elem_index_set(e, -1); /* set_dirty! */
}
bm->elem_index_dirty |= BM_EDGE;
}
{
BMOIter siter;
BMEdge *e;
uint i;
BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
BM_elem_index_set(e, BM_edge_is_manifold(e) ? i : -1); /* set_dirty! */
eheap_table[i] = NULL;
}
}
/* First operate on boundary edges, this is often all that's needed,
* regions that have no boundaries are handles after. */
enum {
PASS_TYPE_BOUNDARY = 0,
PASS_TYPE_ALL = 1,
PASS_TYPE_DONE = 2,
};
uint pass_type = PASS_TYPE_BOUNDARY;
while ((pass_type != PASS_TYPE_DONE) && (edges_len_rotate != edges_len)) {
BLI_assert(BLI_heap_is_empty(heap));
{
BMOIter siter;
BMEdge *e;
uint i;
BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
BLI_assert(eheap_table[i] == NULL);
bool ok = (BM_elem_index_get(e) != -1) && BM_edge_rotate_check(e);
if (ok) {
if (pass_type == PASS_TYPE_BOUNDARY) {
ok = bm_edge_rotate_is_boundary(e);
}
}
BMO_edge_flag_enable(bm, e2, EDGE_OUT);
if (ok) {
float cost = bm_edge_calc_rotate_cost(e);
eheap_table[i] = BLI_heap_insert(heap, cost, e);
}
}
}
if (BLI_heap_is_empty(heap)) {
pass_type += 1;
continue;
}
const int edges_len_rotate_prev = edges_len_rotate;
while (!BLI_heap_is_empty(heap)) {
BMEdge *e_best = BLI_heap_popmin(heap);
eheap_table[BM_elem_index_get(e_best)] = NULL;
/* No problem if this fails, re-evaluate if faces connected to this edge are touched. */
if (BM_edge_rotate_check(e_best)) {
BMEdge *e_rotate = BM_edge_rotate(bm, e_best, use_ccw, check_flag);
if (e_rotate != NULL) {
BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
/* invalidate so we don't try touch this again. */
BM_elem_index_set(e_rotate, -1); /* set_dirty! */
edges_len_rotate += 1;
/* Note: we could validate all edges which have not been rotated
* (not just previously degenerate edges).
* However there is no real need - they can be left until they're popped off the queue. */
/* We don't know the exact topology after rotating the edge,
* so loop over all faces attached to the new edge, typically this will only be two faces. */
BMLoop *l_radial_iter = e_rotate->l;
do {
/* Skip this edge. */
BMLoop *l_iter = l_radial_iter->next;
do {
BMEdge *e_iter = l_iter->e;
const int e_iter_index = BM_elem_index_get(e_iter);
if ((e_iter_index != -1) && (eheap_table[e_iter_index] == NULL)) {
if (BM_edge_rotate_check(e_iter)) {
/* Previously degenerate, now valid. */
float cost = bm_edge_calc_rotate_cost(e_iter);
eheap_table[e_iter_index] = BLI_heap_insert(heap, cost, e_iter);
}
}
} while ((l_iter = l_iter->next) != l_radial_iter);
} while ((l_radial_iter = l_radial_iter->radial_next) != e_rotate->l);
}
}
}
/* If no actions were taken, move onto the next pass. */
if (edges_len_rotate == edges_len_rotate_prev) {
pass_type += 1;
continue;
}
}
BLI_heap_free(heap, NULL);
MEM_freeN(eheap_table);
}
void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
{
BMOIter siter;
BMEdge *e;
const int edges_len = BMO_slot_buffer_count(op->slots_in, "edges");
const bool use_ccw = BMO_slot_bool_get(op->slots_in, "use_ccw");
const bool is_single = (edges_len == 1);
short check_flag = is_single ?
BM_EDGEROT_CHECK_EXISTS :
BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
bool is_simple = true;
if (is_single == false) {
BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
BMFace *f_pair[2];
if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
for (uint i = 0; i < ARRAY_SIZE(f_pair); i += 1) {
if (BMO_face_flag_test(bm, f_pair[i], FACE_MARK)) {
is_simple = false;
break;
}
BMO_face_flag_enable(bm, f_pair[i], FACE_MARK);
}
if (is_simple == false) {
break;
}
}
}
}
if (is_simple) {
bm_rotate_edges_simple(bm, op, use_ccw, check_flag);
}
else {
bm_rotate_edges_shared(bm, op, check_flag, use_ccw, edges_len);
}
BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
#undef EDGE_OUT
#undef FACE_TAINT
}