Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/bmesh/operators/bmo_beautify.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/bmesh/operators/bmo_beautify.c')
-rw-r--r--source/blender/bmesh/operators/bmo_beautify.c347
1 files changed, 204 insertions, 143 deletions
diff --git a/source/blender/bmesh/operators/bmo_beautify.c b/source/blender/bmesh/operators/bmo_beautify.c
index adf8ed4df67..68d0c662b2c 100644
--- a/source/blender/bmesh/operators/bmo_beautify.c
+++ b/source/blender/bmesh/operators/bmo_beautify.c
@@ -22,9 +22,21 @@
/** \file blender/bmesh/operators/bmo_beautify.c
* \ingroup bmesh
+ *
+ * Beautify the mesh by rotating edes between triangles
+ * to more attractive positions until no more rotations can be made.
+ *
+ * In princible this is very simple however there is the possability of
+ * going into an eternal loop where edges keep rotating.
+ * To avoid this - each edge stores a hash of it previous
+ * states so as not to rotate back.
+ *
+ * TODO
+ * - Take face normals into account.
*/
#include "BLI_math.h"
+#include "BLI_heap.h"
#include "MEM_guardedalloc.h"
@@ -112,21 +124,159 @@ static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
}
/* -------------------------------------------------------------------- */
-/* Util for setting edge tag once rotated */
+/* Calculate the improvement of rotating the edge */
+
+/**
+ * \return a negative value means the edge can be rotated.
+ */
+static float bm_edge_calc_rotate_beauty(const BMEdge *e)
+{
+ /* not a loop (only to be able to break out) */
+ do {
+ float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
+
+ /* first get the 2d values */
+ {
+ const float *v1, *v2, *v3, *v4;
+ bool is_zero_a, is_zero_b;
+ float no[3];
+ float axis_mat[3][3];
+
+ v1 = e->l->prev->v->co; /* first face co */
+ v2 = e->l->v->co; /* e->v1 or e->v2*/
+ v3 = e->l->radial_next->prev->v->co; /* second face co */
+ v4 = e->l->next->v->co; /* e->v1 or e->v2*/
+
+ if (UNLIKELY(v1 == v3)) {
+ // printf("This should never happen, but does sometimes!\n");
+ break;
+ }
+
+ // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
+ BLI_assert((ELEM3(v1, v2, v3, v4) == false) &&
+ (ELEM3(v2, v1, v3, v4) == false) &&
+ (ELEM3(v3, v1, v2, v4) == false) &&
+ (ELEM3(v4, v1, v2, v3) == false));
+
+ is_zero_a = area_tri_v3(v2, v3, v4) <= FLT_EPSILON;
+ is_zero_b = area_tri_v3(v2, v4, v1) <= FLT_EPSILON;
+
+ if (LIKELY(is_zero_a == false && is_zero_b == false)) {
+ float no_a[3], no_b[3];
+ normal_tri_v3(no_a, v2, v3, v4); /* a */
+ normal_tri_v3(no_b, v2, v4, v1); /* b */
+ add_v3_v3v3(no, no_a, no_b);
+ if (UNLIKELY(normalize_v3(no) <= FLT_EPSILON)) {
+ break;
+ }
+ }
+ else if (is_zero_a == false) {
+ normal_tri_v3(no, v2, v3, v4); /* a */
+ }
+ else if (is_zero_b == false) {
+ normal_tri_v3(no, v2, v4, v1); /* b */
+ }
+ else {
+ /* both zero area, no useful normal can be calculated */
+ break;
+ }
+
+ // { float a = angle_normalized_v3v3(no_a, no_b); printf("~ %.7f\n", a); fflush(stdout);}
+
+ axis_dominant_v3_to_m3(axis_mat, no);
+ mul_v2_m3v3(v1_xy, axis_mat, v1);
+ mul_v2_m3v3(v2_xy, axis_mat, v2);
+ mul_v2_m3v3(v3_xy, axis_mat, v3);
+ mul_v2_m3v3(v4_xy, axis_mat, v4);
+ }
+
+ // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
+
+ if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) {
+ float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
+ /* testing rule:
+ * the area divided by the total edge lengths
+ */
+ len1 = len_v2v2(v1_xy, v2_xy);
+ len2 = len_v2v2(v2_xy, v3_xy);
+ len3 = len_v2v2(v3_xy, v4_xy);
+ len4 = len_v2v2(v4_xy, v1_xy);
+ len5 = len_v2v2(v1_xy, v3_xy);
+ len6 = len_v2v2(v2_xy, v4_xy);
+
+ opp1 = area_tri_v2(v1_xy, v2_xy, v3_xy);
+ opp2 = area_tri_v2(v1_xy, v3_xy, v4_xy);
+
+ fac1 = opp1 / (len1 + len2 + len5) + opp2 / (len3 + len4 + len5);
+
+ opp1 = area_tri_v2(v2_xy, v3_xy, v4_xy);
+ opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy);
+
+ fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
+ /* negative number if we're OK */
+ return fac2 - fac1;
+ }
+ } while (false);
+
+ return FLT_MAX;
+}
+
+/* -------------------------------------------------------------------- */
+/* Update the edge cost of rotation in the heap */
+
+/* recalc an edge in the heap (surrounding geometry has changed) */
+static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr)
+{
+ if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+ const int i = BM_elem_index_get(e);
+ GHash *e_state_hash = edge_state_arr[i];
+
+ if (eheap_table[i]) {
+ BLI_heap_remove(eheap, eheap_table[i]);
+ eheap_table[i] = NULL;
+ }
+
+ /* check if we can add it back */
+ BLI_assert(BM_edge_is_manifold(e) == true);
+ //BLI_assert(BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
+ // BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK));
+
+ /* check we're not moving back into a state we have been in before */
+ if (e_state_hash != NULL) {
+ EdRotState e_state_alt;
+ erot_state_alternate(e, &e_state_alt);
+ if (BLI_ghash_haskey(e_state_hash, (void *)&e_state_alt)) {
+ // printf(" skipping, we already have this state\n");
+ return;
+ }
+ }
+
+ {
+ /* recalculate edge */
+ const float cost = bm_edge_calc_rotate_beauty(e);
+ if (cost < 0.0f) {
+ eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+ }
+ else {
+ eheap_table[i] = NULL;
+ }
+ }
+ }
+}
/* we have rotated an edge, tag other egdes and clear this one */
-static void bm_edge_tag_rotated(BMEdge *e)
+static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr)
{
BMLoop *l;
BLI_assert(e->l->f->len == 3 &&
e->l->radial_next->f->len == 3);
l = e->l;
- BM_elem_flag_enable(l->next->e, BM_ELEM_TAG);
- BM_elem_flag_enable(l->prev->e, BM_ELEM_TAG);
+ bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr);
+ bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr);
l = l->radial_next;
- BM_elem_flag_enable(l->next->e, BM_ELEM_TAG);
- BM_elem_flag_enable(l->prev->e, BM_ELEM_TAG);
+ bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr);
+ bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr);
}
/* -------------------------------------------------------------------- */
@@ -141,160 +291,71 @@ static void bm_edge_tag_rotated(BMEdge *e)
*/
static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len)
{
+ Heap *eheap; /* edge heap */
+ HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */
+
GHash **edge_state_arr = MEM_callocN(edge_array_len * sizeof(GHash *), __func__);
BLI_mempool *edge_state_pool = BLI_mempool_create(sizeof(EdRotState), 512, 512, BLI_MEMPOOL_SYSMALLOC);
- bool is_breaked;
int i;
#ifdef DEBUG_TIME
TIMEIT_START(beautify_fill);
#endif
- do {
- is_breaked = true;
-
- for (i = 0; i < edge_array_len; i++) {
- BMEdge *e = edge_array[i];
- GHash *e_state_hash;
-
- float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
-
- BLI_assert(BM_edge_is_manifold(e) == true);
- BLI_assert(BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
- BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK));
+ eheap = BLI_heap_new_ex(edge_array_len);
+ eheap_table = MEM_mallocN(sizeof(HeapNode *) * edge_array_len, __func__);
- if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
- continue;
- }
- else {
- /* don't check this edge again, unless adjaced edges are rotated */
- BM_elem_flag_disable(e, BM_ELEM_TAG);
- }
+ /* build heap */
+ for (i = 0; i < edge_array_len; i++) {
+ BMEdge *e = edge_array[i];
+ const float cost = bm_edge_calc_rotate_beauty(e);
+ if (cost < 0.0f) {
+ eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+ }
+ else {
+ eheap_table[i] = NULL;
+ }
+ }
- /* check we're not moving back into a state we have been in before */
- e_state_hash = edge_state_arr[i];
- if (e_state_hash != NULL) {
- EdRotState e_state_alt;
- erot_state_alternate(e, &e_state_alt);
- if (BLI_ghash_haskey(e_state_hash, (void *)&e_state_alt)) {
- // printf(" skipping, we already have this state\n");
- continue;
- }
+ while (BLI_heap_is_empty(eheap) == false) {
+ BMEdge *e = BLI_heap_popmin(eheap);
+ i = BM_elem_index_get(e);
+ eheap_table[i] = NULL;
+
+ e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
+ if (LIKELY(e)) {
+ GHash *e_state_hash = edge_state_arr[i];
+
+ /* add the new state into the hash so we don't move into this state again
+ * note: we could add the previous state too but this isn't essential)
+ * for avoiding eternal loops */
+ EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
+ erot_state_current(e, e_state);
+ if (UNLIKELY(e_state_hash == NULL)) {
+ edge_state_arr[i] = e_state_hash = erot_ghash_new(); /* store previous state */
}
+ BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false);
+ BLI_ghash_insert(e_state_hash, e_state, NULL);
- {
- const float *v1, *v2, *v3, *v4;
- bool is_zero_a, is_zero_b;
- float no[3];
- float axis_mat[3][3];
-
- v1 = e->l->prev->v->co; /* first face co */
- v2 = e->l->v->co; /* e->v1 or e->v2*/
- v3 = e->l->radial_next->prev->v->co; /* second face co */
- v4 = e->l->next->v->co; /* e->v1 or e->v2*/
-
- if (UNLIKELY(v1 == v3)) {
- // printf("This should never happen, but does sometimes!\n");
- continue;
- }
-
- // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
- BLI_assert((ELEM3(v1, v2, v3, v4) == false) &&
- (ELEM3(v2, v1, v3, v4) == false) &&
- (ELEM3(v3, v1, v2, v4) == false) &&
- (ELEM3(v4, v1, v2, v3) == false));
-
- is_zero_a = area_tri_v3(v2, v3, v4) <= FLT_EPSILON;
- is_zero_b = area_tri_v3(v2, v4, v1) <= FLT_EPSILON;
-
- if (LIKELY(is_zero_a == false && is_zero_b == false)) {
- float no_a[3], no_b[3];
- normal_tri_v3(no_a, v2, v3, v4); /* a */
- normal_tri_v3(no_b, v2, v4, v1); /* b */
- add_v3_v3v3(no, no_a, no_b);
- if (UNLIKELY(normalize_v3(no) <= FLT_EPSILON)) {
- continue;
- }
- }
- else if (is_zero_a == false) {
- normal_tri_v3(no, v2, v3, v4); /* a */
- }
- else if (is_zero_b == false) {
- normal_tri_v3(no, v2, v4, v1); /* b */
- }
- else {
- /* both zero area, no useful normal can be calculated */
- continue;
- }
- // { float a = angle_normalized_v3v3(no_a, no_b); printf("~ %.7f\n", a); fflush(stdout);}
+ // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
- axis_dominant_v3_to_m3(axis_mat, no);
- mul_v2_m3v3(v1_xy, axis_mat, v1);
- mul_v2_m3v3(v2_xy, axis_mat, v2);
- mul_v2_m3v3(v3_xy, axis_mat, v3);
- mul_v2_m3v3(v4_xy, axis_mat, v4);
- }
+ /* maintain the index array */
+ edge_array[i] = e;
+ BM_elem_index_set(e, i);
- // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
+ /* recalculate faces connected on the heap */
+ bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr);
- if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) {
- float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
- /* testing rule:
- * the area divided by the total edge lengths
- */
- len1 = len_v2v2(v1_xy, v2_xy);
- len2 = len_v2v2(v2_xy, v3_xy);
- len3 = len_v2v2(v3_xy, v4_xy);
- len4 = len_v2v2(v4_xy, v1_xy);
- len5 = len_v2v2(v1_xy, v3_xy);
- len6 = len_v2v2(v2_xy, v4_xy);
-
- opp1 = area_tri_v2(v1_xy, v2_xy, v3_xy);
- opp2 = area_tri_v2(v1_xy, v3_xy, v4_xy);
-
- fac1 = opp1 / (len1 + len2 + len5) + opp2 / (len3 + len4 + len5);
-
- opp1 = area_tri_v2(v2_xy, v3_xy, v4_xy);
- opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy);
-
- fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
-
- if (fac1 > fac2) {
- e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
- if (LIKELY(e)) {
-
- /* add the new state into the hash so we don't move into this state again
- * note: we could add the previous state too but this isn't essential)
- * for avoiding eternal loops */
- EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
- erot_state_current(e, e_state);
- if (UNLIKELY(e_state_hash == NULL)) {
- edge_state_arr[i] = e_state_hash = erot_ghash_new(); /* store previous state */
- }
- BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false);
- BLI_ghash_insert(e_state_hash, e_state, NULL);
-
-
- // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
-
- /* maintain the index array */
- edge_array[i] = e;
- BM_elem_index_set(e, i);
-
- /* tag other edges so we know to check them again */
- bm_edge_tag_rotated(e);
-
- /* update flags */
- BMO_elem_flag_enable(bm, e, ELE_NEW);
- BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW);
- BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW);
- is_breaked = false;
- }
- }
- }
+ /* update flags */
+ BMO_elem_flag_enable(bm, e, ELE_NEW);
+ BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW);
+ BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW);
}
- } while (is_breaked == false);
+ }
+
+ BLI_heap_free(eheap, NULL);
+ MEM_freeN(eheap_table);
for (i = 0; i < edge_array_len; i++) {
if (edge_state_arr[i]) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-02 20:45:25 +0300