Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / bmesh / operators / bmo_beautify.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_beautify.c
24  *  \ingroup bmesh
25  *
26  * Beautify the mesh by rotating edges between triangles
27  * to more attractive positions until no more rotations can be made.
28  *
29  * In principle this is very simple however there is the possibility of
30  * going into an eternal loop where edges keep rotating.
31  * To avoid this - each edge stores a hash of it previous
32  * states so as not to rotate back.
33  *
34  * TODO
35  * - Take face normals into account.
36  */
37
38 #include "BLI_math.h"
39 #include "BLI_heap.h"
40
41 #include "MEM_guardedalloc.h"
42
43 #include "bmesh.h"
44 #include "intern/bmesh_operators_private.h"
45
46 // #define DEBUG_TIME
47
48 #ifdef DEBUG_TIME
49 #  include "PIL_time.h"
50 #endif
51
52 enum {
53         VERT_RESTRICT_TAG = (1 << 0),
54 };
55
56 /* -------------------------------------------------------------------- */
57 /* GHash for edge rotation */
58
59 typedef struct EdRotState {
60         int v1, v2; /*  edge vert, small -> large */
61         int f1, f2; /*  face vert, small -> large */
62 } EdRotState;
63
64 static unsigned int erot_ghashutil_hash(const void *ptr)
65 {
66         const EdRotState *e_state = (const EdRotState *)ptr;
67         unsigned int
68         hash  = BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v1));
69         hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v2));
70         hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f1));
71         hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f2));
72         return hash;
73 }
74 static int erot_ghashutil_cmp(const void *a, const void *b)
75 {
76         const EdRotState *e_state_a = (const EdRotState *)a;
77         const EdRotState *e_state_b = (const EdRotState *)b;
78         if      (e_state_a->v1 < e_state_b->v1) return -1;
79         else if (e_state_a->v1 > e_state_b->v1) return  1;
80         else if (e_state_a->v2 < e_state_b->v2) return -1;
81         else if (e_state_a->v2 > e_state_b->v2) return  1;
82         else if (e_state_a->f1 < e_state_b->f1) return -1;
83         else if (e_state_a->f1 > e_state_b->f1) return  1;
84         else if (e_state_a->f2 < e_state_b->f2) return -1;
85         else if (e_state_a->f2 > e_state_b->f2) return  1;
86         else                                    return  0;
87 }
88
89 static GHash *erot_ghash_new(void)
90 {
91         return BLI_ghash_new(erot_ghashutil_hash, erot_ghashutil_cmp, __func__);
92 }
93
94 /* ensure v0 is smaller */
95 #define EDGE_ORD(v0, v1) \
96         if (v0 > v1) {       \
97                 v0 ^= v1;        \
98                 v1 ^= v0;        \
99                 v0 ^= v1;        \
100         } (void)0
101
102 static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2])
103 {
104         BLI_assert(BM_edge_is_manifold((BMEdge *)e));
105         BLI_assert(BM_vert_in_edge(e, e->l->prev->v)              == false);
106         BLI_assert(BM_vert_in_edge(e, e->l->radial_next->prev->v) == false);
107
108         /* verts of the edge */
109         v_index[0] = BM_elem_index_get(e->v1);
110         v_index[1] = BM_elem_index_get(e->v2);
111         EDGE_ORD(v_index[0], v_index[1]);
112
113         /* verts of each of the 2 faces attached to this edge
114          * (that are not apart of this edge) */
115         f_index[0] = BM_elem_index_get(e->l->prev->v);
116         f_index[1] = BM_elem_index_get(e->l->radial_next->prev->v);
117         EDGE_ORD(f_index[0], f_index[1]);
118 }
119
120 static void erot_state_current(const BMEdge *e, EdRotState *e_state)
121 {
122         erot_state_ex(e, &e_state->v1, &e_state->f1);
123 }
124
125 static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
126 {
127         erot_state_ex(e, &e_state->f1, &e_state->v1);
128 }
129
130 /* -------------------------------------------------------------------- */
131 /* Calculate the improvement of rotating the edge */
132
133 /**
134  * \return a negative value means the edge can be rotated.
135  */
136 static float bm_edge_calc_rotate_beauty(const BMEdge *e, const int flag)
137 {
138         /* not a loop (only to be able to break out) */
139         do {
140                 float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
141
142                 /* first get the 2d values */
143                 {
144                         const float *v1, *v2, *v3, *v4;
145                         bool is_zero_a, is_zero_b;
146                         float no[3];
147                         float axis_mat[3][3];
148
149                         v1 = e->l->prev->v->co;               /* first face co */
150                         v2 = e->l->v->co;                     /* e->v1 or e->v2*/
151                         v3 = e->l->radial_next->prev->v->co;  /* second face co */
152                         v4 = e->l->next->v->co;               /* e->v1 or e->v2*/
153
154                         if (flag & VERT_RESTRICT_TAG) {
155                                 BMVert *v_a = e->l->prev->v, *v_b = e->l->radial_next->prev->v;
156                                 if (BM_elem_flag_test(v_a, BM_ELEM_TAG) ==  BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
157                                         break;
158                                 }
159                         }
160
161                         if (UNLIKELY(v1 == v3)) {
162                                 // printf("This should never happen, but does sometimes!\n");
163                                 break;
164                         }
165
166                         // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
167                         BLI_assert((ELEM3(v1, v2, v3, v4) == false) &&
168                                    (ELEM3(v2, v1, v3, v4) == false) &&
169                                    (ELEM3(v3, v1, v2, v4) == false) &&
170                                    (ELEM3(v4, v1, v2, v3) == false));
171
172                         is_zero_a = area_tri_v3(v2, v3, v4) <= FLT_EPSILON;
173                         is_zero_b = area_tri_v3(v2, v4, v1) <= FLT_EPSILON;
174
175                         if (LIKELY(is_zero_a == false && is_zero_b == false)) {
176                                 float no_a[3], no_b[3];
177                                 normal_tri_v3(no_a, v2, v3, v4);  /* a */
178                                 normal_tri_v3(no_b, v2, v4, v1);  /* b */
179                                 add_v3_v3v3(no, no_a, no_b);
180                                 if (UNLIKELY(normalize_v3(no) <= FLT_EPSILON)) {
181                                         break;
182                                 }
183                         }
184                         else if (is_zero_a == false) {
185                                 normal_tri_v3(no, v2, v3, v4);  /* a */
186                         }
187                         else if (is_zero_b == false) {
188                                 normal_tri_v3(no, v2, v4, v1);  /* b */
189                         }
190                         else {
191                                 /* both zero area, no useful normal can be calculated */
192                                 break;
193                         }
194
195                         // { float a = angle_normalized_v3v3(no_a, no_b); printf("~ %.7f\n", a); fflush(stdout);}
196
197                         axis_dominant_v3_to_m3(axis_mat, no);
198                         mul_v2_m3v3(v1_xy, axis_mat, v1);
199                         mul_v2_m3v3(v2_xy, axis_mat, v2);
200                         mul_v2_m3v3(v3_xy, axis_mat, v3);
201                         mul_v2_m3v3(v4_xy, axis_mat, v4);
202                 }
203
204                 // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
205
206                 if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) {
207                         float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
208                         /* testing rule:
209                          * the area divided by the total edge lengths
210                          */
211                         len1 = len_v2v2(v1_xy, v2_xy);
212                         len2 = len_v2v2(v2_xy, v3_xy);
213                         len3 = len_v2v2(v3_xy, v4_xy);
214                         len4 = len_v2v2(v4_xy, v1_xy);
215                         len5 = len_v2v2(v1_xy, v3_xy);
216                         len6 = len_v2v2(v2_xy, v4_xy);
217
218                         opp1 = area_tri_v2(v1_xy, v2_xy, v3_xy);
219                         opp2 = area_tri_v2(v1_xy, v3_xy, v4_xy);
220
221                         fac1 = opp1 / (len1 + len2 + len5) + opp2 / (len3 + len4 + len5);
222
223                         opp1 = area_tri_v2(v2_xy, v3_xy, v4_xy);
224                         opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy);
225
226                         fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
227                         /* negative number if we're OK */
228                         return fac2 - fac1;
229                 }
230         } while (false);
231
232         return FLT_MAX;
233 }
234
235 /* -------------------------------------------------------------------- */
236 /* Update the edge cost of rotation in the heap */
237
238 /* recalc an edge in the heap (surrounding geometry has changed) */
239 static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr,
240                                               const int flag)
241 {
242         if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
243                 const int i = BM_elem_index_get(e);
244                 GHash *e_state_hash = edge_state_arr[i];
245
246                 if (eheap_table[i]) {
247                         BLI_heap_remove(eheap, eheap_table[i]);
248                         eheap_table[i] = NULL;
249                 }
250
251                 /* check if we can add it back */
252                 BLI_assert(BM_edge_is_manifold(e) == true);
253                 //BLI_assert(BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
254                 //           BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK));
255
256                 /* check we're not moving back into a state we have been in before */
257                 if (e_state_hash != NULL) {
258                         EdRotState e_state_alt;
259                         erot_state_alternate(e, &e_state_alt);
260                         if (BLI_ghash_haskey(e_state_hash, (void *)&e_state_alt)) {
261                                 // printf("  skipping, we already have this state\n");
262                                 return;
263                         }
264                 }
265
266                 {
267                         /* recalculate edge */
268                         const float cost = bm_edge_calc_rotate_beauty(e, flag);
269                         if (cost < 0.0f) {
270                                 eheap_table[i] = BLI_heap_insert(eheap, cost, e);
271                         }
272                         else {
273                                 eheap_table[i] = NULL;
274                         }
275                 }
276         }
277 }
278
279 /* we have rotated an edge, tag other edges and clear this one */
280 static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GHash **edge_state_arr,
281                                        const int flag)
282 {
283         BMLoop *l;
284         BLI_assert(e->l->f->len == 3 &&
285                    e->l->radial_next->f->len == 3);
286
287         l = e->l;
288         bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag);
289         bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag);
290         l = l->radial_next;
291         bm_edge_update_beauty_cost_single(l->next->e, eheap, eheap_table, edge_state_arr, flag);
292         bm_edge_update_beauty_cost_single(l->prev->e, eheap, eheap_table, edge_state_arr, flag);
293 }
294
295 /* -------------------------------------------------------------------- */
296 /* Beautify Fill */
297
298 #define ELE_NEW         1
299 #define FACE_MARK       2
300
301 /**
302  * \note All edges in \a edge_array must be tagged and
303  * have their index values set according to their position in the array.
304  */
305 static void bm_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len,
306                                   const int flag)
307 {
308         Heap *eheap;             /* edge heap */
309         HeapNode **eheap_table;  /* edge index aligned table pointing to the eheap */
310
311         GHash      **edge_state_arr  = MEM_callocN(edge_array_len * sizeof(GHash *), __func__);
312         BLI_mempool *edge_state_pool = BLI_mempool_create(sizeof(EdRotState), 512, 512, BLI_MEMPOOL_SYSMALLOC);
313         int i;
314
315 #ifdef DEBUG_TIME
316         TIMEIT_START(beautify_fill);
317 #endif
318
319         eheap = BLI_heap_new_ex(edge_array_len);
320         eheap_table = MEM_mallocN(sizeof(HeapNode *) * edge_array_len, __func__);
321
322         /* build heap */
323         for (i = 0; i < edge_array_len; i++) {
324                 BMEdge *e = edge_array[i];
325                 const float cost = bm_edge_calc_rotate_beauty(e, flag);
326                 if (cost < 0.0f) {
327                         eheap_table[i] = BLI_heap_insert(eheap, cost, e);
328                 }
329                 else {
330                         eheap_table[i] = NULL;
331                 }
332         }
333
334         while (BLI_heap_is_empty(eheap) == false) {
335                 BMEdge *e = BLI_heap_popmin(eheap);
336                 i = BM_elem_index_get(e);
337                 eheap_table[i] = NULL;
338
339                 e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
340                 if (LIKELY(e)) {
341                         GHash *e_state_hash = edge_state_arr[i];
342
343                         /* add the new state into the hash so we don't move into this state again
344                          * note: we could add the previous state too but this isn't essential)
345                          *       for avoiding eternal loops */
346                         EdRotState *e_state = BLI_mempool_alloc(edge_state_pool);
347                         erot_state_current(e, e_state);
348                         if (UNLIKELY(e_state_hash == NULL)) {
349                                 edge_state_arr[i] = e_state_hash = erot_ghash_new();  /* store previous state */
350                         }
351                         BLI_assert(BLI_ghash_haskey(e_state_hash, (void *)e_state) == false);
352                         BLI_ghash_insert(e_state_hash, e_state, NULL);
353
354
355                         // printf("  %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
356
357                         /* maintain the index array */
358                         edge_array[i] = e;
359                         BM_elem_index_set(e, i);
360
361                         /* recalculate faces connected on the heap */
362                         bm_edge_update_beauty_cost(e, eheap, eheap_table, edge_state_arr, flag);
363
364                         /* update flags */
365                         BMO_elem_flag_enable(bm, e, ELE_NEW);
366                         BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW);
367                         BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW);
368                 }
369         }
370
371         BLI_heap_free(eheap, NULL);
372         MEM_freeN(eheap_table);
373
374         for (i = 0; i < edge_array_len; i++) {
375                 if (edge_state_arr[i]) {
376                         BLI_ghash_free(edge_state_arr[i], NULL, NULL);
377                 }
378         }
379
380         MEM_freeN(edge_state_arr);
381         BLI_mempool_destroy(edge_state_pool);
382
383 #ifdef DEBUG_TIME
384         TIMEIT_END(beautify_fill);
385 #endif
386 }
387
388
389 void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
390 {
391         BMIter iter;
392         BMOIter siter;
393         BMFace *f;
394         BMEdge *e;
395         const bool use_restrict_tag = BMO_slot_bool_get(op->slots_in,  "use_restrict_tag");
396         const int flag = (use_restrict_tag ? VERT_RESTRICT_TAG : 0);
397
398         BMEdge **edge_array;
399         int edge_array_len = 0;
400
401         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
402                 if (f->len == 3) {
403                         BMO_elem_flag_enable(bm, f, FACE_MARK);
404                 }
405         }
406
407         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
408                 BM_elem_flag_disable(e, BM_ELEM_TAG);
409         }
410
411         /* will over alloc if some edges can't be rotated */
412         edge_array = MEM_mallocN(sizeof(*edge_array) *  BMO_slot_buffer_count(op->slots_in, "edges"), __func__);
413
414         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
415
416                 /* edge is manifold and can be rotated */
417                 if (BM_edge_rotate_check(e) &&
418                     /* faces are tagged */
419                     BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
420                     BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
421                 {
422                         BM_elem_index_set(e, edge_array_len);  /* set_dirty */
423                         BM_elem_flag_enable(e, BM_ELEM_TAG);
424                         edge_array[edge_array_len] = e;
425                         edge_array_len++;
426                 }
427         }
428         bm->elem_index_dirty |= BM_EDGE;
429
430         bm_mesh_beautify_fill(bm, edge_array, edge_array_len, flag);
431
432         MEM_freeN(edge_array);
433
434         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_EDGE | BM_FACE, ELE_NEW);
435 }