9832fdb57d375be3f196efc2baf58cc116b53bba
[blender.git] / source / blender / bmesh / operators / bmo_rotate_edges.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  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/bmesh/operators/bmo_rotate_edges.c
22  *  \ingroup bmesh
23  *
24  * Rotate edges topology that share two faces.
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_math.h"
30 #include "BLI_heap.h"
31
32 #include "bmesh.h"
33
34 #include "intern/bmesh_operators_private.h" /* own include */
35
36 #define EDGE_OUT   1
37 #define FACE_MARK 1
38
39 /**
40  * Rotate edges where every edge has it's own faces (we can rotate in any order).
41  */
42 static void bm_rotate_edges_simple(
43         BMesh *bm, BMOperator *op,
44         const short check_flag, const bool use_ccw)
45 {
46         BMOIter siter;
47         BMEdge *e;
48
49         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
50                 /**
51                  * this ends up being called twice, could add option to not to call check in
52                  * #BM_edge_rotate to get some extra speed */
53                 if (BM_edge_rotate_check(e)) {
54                         BMEdge *e_rotate = BM_edge_rotate(bm, e, use_ccw, check_flag);
55                         if (e_rotate != NULL) {
56                                 BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
57                         }
58                 }
59         }
60 }
61
62
63 /**
64  * Edge length is just a way of ordering that's independent of order in the edges argument,
65  * we could use some other method since ideally all edges will be rotated,
66  * this just happens to be simple to calculate.
67  */
68 static float bm_edge_calc_rotate_cost(const BMEdge *e)
69 {
70         return -BM_edge_calc_length_squared(e);
71 }
72
73 /**
74  * Check if this edge is a boundary: Are more than one of the connected faces edges rotating too?
75  */
76 static float bm_edge_rotate_is_boundary(const BMEdge *e)
77 {
78         /* Number of adjacent shared faces. */
79         int count = 0;
80         BMLoop *l_radial_iter = e->l;
81         do {
82                 /* Skip this edge. */
83                 BMLoop *l_iter = l_radial_iter->next;
84                 do {
85                         BMEdge *e_iter = l_iter->e;
86                         const int e_iter_index = BM_elem_index_get(e_iter);
87                         if ((e_iter_index != -1)) {
88                                 if (count == 1) {
89                                         return false;
90                                 }
91                                 count += 1;
92                                 break;
93                         }
94                 } while ((l_iter = l_iter->next) != l_radial_iter);
95         } while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
96         return true;
97 }
98
99 /**
100  * Rotate edges where edges share faces,
101  * edges which could not rotate need to be re-considered after neighbors are rotated.
102  */
103 static void bm_rotate_edges_shared(
104         BMesh *bm, BMOperator *op,
105         short check_flag, const bool use_ccw, const int edges_len)
106 {
107         Heap *heap = BLI_heap_new_ex(edges_len);
108         HeapNode **eheap_table = MEM_mallocN(sizeof(*eheap_table) * edges_len, __func__);
109         int edges_len_rotate = 0;
110
111         {
112                 BMIter iter;
113                 BMEdge *e;
114                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
115                         BM_elem_index_set(e, -1);  /* set_dirty! */
116                 }
117                 bm->elem_index_dirty |= BM_EDGE;
118         }
119
120         {
121                 BMOIter siter;
122                 BMEdge *e;
123                 uint i;
124                 BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
125                         BM_elem_index_set(e, BM_edge_is_manifold(e) ? i : -1);  /* set_dirty! */
126                         eheap_table[i] = NULL;
127                 }
128         }
129
130         /* First operate on boundary edges, this is often all that's needed,
131          * regions that have no boundaries are handles after. */
132         enum {
133                 PASS_TYPE_BOUNDARY = 0,
134                 PASS_TYPE_ALL = 1,
135                 PASS_TYPE_DONE = 2,
136         };
137         uint pass_type = PASS_TYPE_BOUNDARY;
138
139
140         while ((pass_type != PASS_TYPE_DONE) && (edges_len_rotate != edges_len)) {
141                 BLI_assert(BLI_heap_is_empty(heap));
142                 {
143                         BMOIter siter;
144                         BMEdge *e;
145                         uint i;
146                         BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
147                                 BLI_assert(eheap_table[i] == NULL);
148
149                                 bool ok = (BM_elem_index_get(e) != -1) && BM_edge_rotate_check(e);
150
151                                 if (ok) {
152                                         if (pass_type == PASS_TYPE_BOUNDARY) {
153                                                 ok = bm_edge_rotate_is_boundary(e);
154                                         }
155                                 }
156
157                                 if (ok) {
158                                         float cost = bm_edge_calc_rotate_cost(e);
159                                         if (pass_type == PASS_TYPE_BOUNDARY) {
160                                                 /* Trick to ensure once started, non boundaries are handled before other boundary edges.
161                                                  * This means the first longest boundary defines the starting point which is rotated
162                                                  * until all its connected edges are exhausted and the next boundary is popped off the heap.
163                                                  *
164                                                  * Without this we may rotate from different starting points and meet in the middle
165                                                  * with obviously uneven topology.
166                                                  *
167                                                  * Move from negative to positive value, inverting so large values are still handled first.
168                                                  */
169                                                 cost = cost != 0.0f ? -1.0f / cost : FLT_MAX;
170                                         }
171                                         eheap_table[i] = BLI_heap_insert(heap, cost, e);
172                                 }
173                         }
174                 }
175
176                 if (BLI_heap_is_empty(heap)) {
177                         pass_type += 1;
178                         continue;
179                 }
180
181                 const int edges_len_rotate_prev = edges_len_rotate;
182                 while (!BLI_heap_is_empty(heap)) {
183                         BMEdge *e_best = BLI_heap_popmin(heap);
184                         eheap_table[BM_elem_index_get(e_best)] = NULL;
185
186                         /* No problem if this fails, re-evaluate if faces connected to this edge are touched. */
187                         if (BM_edge_rotate_check(e_best)) {
188                                 BMEdge *e_rotate = BM_edge_rotate(bm, e_best, use_ccw, check_flag);
189                                 if (e_rotate != NULL) {
190                                         BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
191
192                                         /* invalidate so we don't try touch this again. */
193                                         BM_elem_index_set(e_rotate, -1);  /* set_dirty! */
194
195                                         edges_len_rotate += 1;
196
197                                         /* Note: we could validate all edges which have not been rotated
198                                          * (not just previously degenerate edges).
199                                          * However there is no real need - they can be left until they're popped off the queue. */
200
201                                         /* We don't know the exact topology after rotating the edge,
202                                          * so loop over all faces attached to the new edge, typically this will only be two faces. */
203                                         BMLoop *l_radial_iter = e_rotate->l;
204                                         do {
205                                                 /* Skip this edge. */
206                                                 BMLoop *l_iter = l_radial_iter->next;
207                                                 do {
208                                                         BMEdge *e_iter = l_iter->e;
209                                                         const int e_iter_index = BM_elem_index_get(e_iter);
210                                                         if ((e_iter_index != -1) && (eheap_table[e_iter_index] == NULL)) {
211                                                                 if (BM_edge_rotate_check(e_iter)) {
212                                                                         /* Previously degenerate, now valid. */
213                                                                         float cost = bm_edge_calc_rotate_cost(e_iter);
214                                                                         eheap_table[e_iter_index] = BLI_heap_insert(heap, cost, e_iter);
215                                                                 }
216                                                         }
217                                                 } while ((l_iter = l_iter->next) != l_radial_iter);
218                                         } while ((l_radial_iter = l_radial_iter->radial_next) != e_rotate->l);
219                                 }
220                         }
221                 }
222
223                 /* If no actions were taken, move onto the next pass. */
224                 if (edges_len_rotate == edges_len_rotate_prev) {
225                         pass_type += 1;
226                         continue;
227                 }
228         }
229
230         BLI_heap_free(heap, NULL);
231         MEM_freeN(eheap_table);
232 }
233
234 void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
235 {
236         BMOIter siter;
237         BMEdge *e;
238         const int edges_len  = BMO_slot_buffer_count(op->slots_in, "edges");
239         const bool use_ccw   = BMO_slot_bool_get(op->slots_in, "use_ccw");
240         const bool is_single = (edges_len ==  1);
241         short check_flag = is_single ?
242                 BM_EDGEROT_CHECK_EXISTS :
243                 BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
244
245         bool is_simple = true;
246         if (is_single == false) {
247                 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
248                         BMFace *f_pair[2];
249                         if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
250                                 for (uint i = 0; i < ARRAY_SIZE(f_pair); i += 1) {
251                                         if (BMO_face_flag_test(bm, f_pair[i], FACE_MARK)) {
252                                                 is_simple = false;
253                                                 break;
254                                         }
255                                         BMO_face_flag_enable(bm, f_pair[i], FACE_MARK);
256                                 }
257                                 if (is_simple == false) {
258                                         break;
259                                 }
260                         }
261                 }
262         }
263
264         if (is_simple) {
265                 bm_rotate_edges_simple(bm, op, use_ccw, check_flag);
266         }
267         else {
268                 bm_rotate_edges_shared(bm, op, check_flag, use_ccw, edges_len);
269         }
270
271         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
272 }