code cleanup: rename bmesh operator files to be more consistent
[blender.git] / source / blender / bmesh / operators / bmo_fill_grid.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): Campbell Barton.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_fill_grid.c
24  *  \ingroup bmesh
25  *
26  * Fill 2 isolated, open edge loops with a grid of quads.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_listbase.h"
32 #include "BLI_math.h"
33
34 #include "BKE_customdata.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 #define EDGE_MARK       4
41 #define FACE_OUT        16
42
43 #define BARYCENTRIC_INTERP
44
45 #ifdef BARYCENTRIC_INTERP
46 /**
47  * 2 edge vectors to normal.
48  */
49 static void quad_edges_to_normal(
50         float no[3],
51         const float co_a1[3], const float co_a2[3],
52         const float co_b1[3], const float co_b2[3])
53 {
54         float diff_a[3];
55         float diff_b[3];
56
57         sub_v3_v3v3(diff_a, co_a2, co_a1);
58         sub_v3_v3v3(diff_b, co_b2, co_b1);
59         normalize_v3(diff_a);
60         normalize_v3(diff_b);
61         add_v3_v3v3(no, diff_a, diff_b);
62         normalize_v3(no);
63 }
64
65 static void quad_verts_to_barycentric_tri(
66         float tri[3][3],
67         float co_a[3],
68         float co_b[3],
69
70         float co_a_next[3],
71         float co_b_next[3],
72
73         float co_a_prev[3],
74         float co_b_prev[3],
75         bool is_flip
76         )
77 {
78         float no[3];
79
80         copy_v3_v3(tri[0], co_a);
81         copy_v3_v3(tri[1], co_b);
82
83         quad_edges_to_normal(no,
84                              co_a, co_a_next,
85                              co_b, co_b_next);
86
87         if (co_a_prev) {
88                 float no_t[3];
89                 quad_edges_to_normal(no_t,
90                                      co_a_prev, co_a,
91                                      co_b_prev, co_b);
92                 add_v3_v3(no, no_t);
93                 normalize_v3(no);
94         }
95
96         if (is_flip) negate_v3(no);
97         mul_v3_fl(no, len_v3v3(tri[0], tri[1]));
98
99         mid_v3_v3v3(tri[2], tri[0], tri[1]);
100         add_v3_v3(tri[2], no);
101 }
102
103 #endif
104
105
106 /**
107  * This may be useful outside the bmesh operator.
108  *
109  * \param v_grid  2d array of verts, all boundary verts must be set, we fill in the middle.
110  */
111 static void bm_grid_fill_array(BMesh *bm, BMVert **v_grid, const int xtot, const int ytot,
112                                const short mat_nr, const bool use_smooth,
113                                const bool use_flip)
114 {
115         const bool use_vert_interp = CustomData_has_interp(&bm->vdata);
116         int x, y;
117
118 #define XY(_x, _y)  ((_x) + ((_y) * (xtot)))
119
120 #ifdef BARYCENTRIC_INTERP
121         float tri_a[3][3];
122         float tri_b[3][3];
123         float tri_t[3][3];  /* temp */
124
125         quad_verts_to_barycentric_tri(
126                 tri_a,
127                 v_grid[XY(0,        0)]->co,
128                 v_grid[XY(xtot - 1, 0)]->co,
129                 v_grid[XY(0,        1)]->co,
130                 v_grid[XY(xtot - 1, 1)]->co,
131                 NULL, NULL,
132                 false);
133
134         quad_verts_to_barycentric_tri(
135                 tri_b,
136                 v_grid[XY(0,        (ytot - 1))]->co,
137                 v_grid[XY(xtot - 1, (ytot - 1))]->co,
138                 v_grid[XY(0,        (ytot - 2))]->co,
139                 v_grid[XY(xtot - 1, (ytot - 2))]->co,
140                 NULL, NULL,
141                 true);
142 #endif
143
144         /* Build Verts */
145         for (y = 1; y < ytot - 1; y++) {
146 #ifdef BARYCENTRIC_INTERP
147                 quad_verts_to_barycentric_tri(
148                         tri_t,
149                         v_grid[XY(0,        y + 0)]->co,
150                         v_grid[XY(xtot - 1, y + 0)]->co,
151                         v_grid[XY(0,        y + 1)]->co,
152                         v_grid[XY(xtot - 1, y + 1)]->co,
153                         v_grid[XY(0,        y - 1)]->co,
154                         v_grid[XY(xtot - 1, y - 1)]->co,
155                         false);
156 #endif
157                 for (x = 1; x < xtot - 1; x++) {
158                         float co[3];
159                         BMVert *v;
160                         /* we may want to allow sparse filled arrays, but for now, ensure its empty */
161                         BLI_assert(v_grid[(y * xtot) + x] == NULL);
162
163                         /* place the vertex */
164 #ifdef BARYCENTRIC_INTERP
165                         {
166                                 float co_a[3], co_b[3];
167
168                                 barycentric_transform(
169                                             co_a,
170                                             v_grid[x]->co,
171                                             tri_t[0], tri_t[1], tri_t[2],
172                                             tri_a[0], tri_a[1], tri_a[2]);
173                                 barycentric_transform(
174                                             co_b,
175                                             v_grid[(xtot * ytot) + (x - xtot)]->co,
176                                             tri_t[0], tri_t[1], tri_t[2],
177                                             tri_b[0], tri_b[1], tri_b[2]);
178
179                                 interp_v3_v3v3(co, co_a, co_b, (float)y / ((float)ytot - 1));
180                         }
181
182 #else
183                         interp_v3_v3v3(
184                                 co,
185                                 v_grid[x]->co,
186                                 v_grid[(xtot * ytot) + (x - xtot)]->co,
187                                 (float)y / ((float)ytot - 1));
188 #endif
189
190                         v = BM_vert_create(bm, co, NULL, 0);
191                         v_grid[(y * xtot) + x] = v;
192
193                         /* interpolate only along one axis, this could be changed
194                          * but from user pov gives predictable results since these are selected loop */
195                         if (use_vert_interp) {
196                                 void *v_cdata[2] = {
197                                     v_grid[XY(x,          0)]->head.data,
198                                     v_grid[XY(x, (ytot - 1))]->head.data,
199                                 };
200                                 const float t = (float)y / ((float)ytot - 1);
201                                 const float w[2] = {1.0f - t, t};
202                                 CustomData_bmesh_interp(&bm->vdata, v_cdata, w, NULL, 2, v->head.data);
203                         }
204
205                 }
206         }
207
208         /* Build Faces */
209         for (x = 0; x < xtot - 1; x++) {
210                 for (y = 0; y < ytot - 1; y++) {
211                         BMFace *f;
212
213                         if (use_flip) {
214                                 f = BM_face_create_quad_tri(
215                                         bm,
216                                         v_grid[XY(x,     y + 0)],  /* BL */
217                                         v_grid[XY(x,     y + 1)],  /* TL */
218                                         v_grid[XY(x + 1, y + 1)],  /* TR */
219                                         v_grid[XY(x + 1, y + 0)],  /* BR */
220                                         NULL,
221                                         false);
222                         }
223                         else {
224                                 f = BM_face_create_quad_tri(
225                                         bm,
226                                         v_grid[XY(x + 1, y + 0)],  /* BR */
227                                         v_grid[XY(x + 1, y + 1)],  /* TR */
228                                         v_grid[XY(x,     y + 1)],  /* TL */
229                                         v_grid[XY(x,     y + 0)],  /* BL */
230                                         NULL,
231                                         false);
232                         }
233                         BMO_elem_flag_enable(bm, f, FACE_OUT);
234                         f->mat_nr = mat_nr;
235                         if (use_smooth) {
236                                 BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
237                         }
238                 }
239         }
240 #undef XY
241 }
242
243 static void bm_grid_fill(BMesh *bm,
244                          struct BMEdgeLoopStore *estore_a,      struct BMEdgeLoopStore *estore_b,
245                          struct BMEdgeLoopStore *estore_rail_a, struct BMEdgeLoopStore *estore_rail_b,
246                          const short mat_nr, const bool use_smooth)
247 {
248 #define USE_FLIP_DETECT
249
250         const int xtot = BM_edgeloop_length_get(estore_a);
251         const int ytot = BM_edgeloop_length_get(estore_rail_a);
252         //BMVert *v;
253         int i;
254 #ifdef DEBUG
255         int x, y;
256 #endif
257         LinkData *el;
258         bool use_flip = false;
259
260         ListBase *lb_a = BM_edgeloop_verts_get(estore_a);
261         ListBase *lb_b = BM_edgeloop_verts_get(estore_b);
262
263         ListBase *lb_rail_a = BM_edgeloop_verts_get(estore_rail_a);
264         ListBase *lb_rail_b = BM_edgeloop_verts_get(estore_rail_b);
265
266         BMVert **v_grid = MEM_callocN(sizeof(BMVert *) * xtot * ytot, __func__);
267         /**
268          * <pre>
269          *           estore_b
270          *          +------------------+
271          *       ^  |                  |
272          *   end |  |                  |
273          *       |  |                  |
274          *       |  |estore_rail_a     |estore_rail_b
275          *       |  |                  |
276          * start |  |                  |
277          *          |estore_a          |
278          *          +------------------+
279          *                --->
280          *             start -> end
281          * </pre>
282          */
283
284         BLI_assert(((LinkData *)lb_a->first)->data == ((LinkData *)lb_rail_a->first)->data);  /* BL */
285         BLI_assert(((LinkData *)lb_b->first)->data == ((LinkData *)lb_rail_a->last)->data);   /* TL */
286         BLI_assert(((LinkData *)lb_b->last)->data  == ((LinkData *)lb_rail_b->last)->data);   /* TR */
287         BLI_assert(((LinkData *)lb_a->last)->data  == ((LinkData *)lb_rail_b->first)->data);  /* BR */
288
289         for (el = lb_a->first,      i = 0; el; el = el->next, i++) { v_grid[i]                          = el->data; }
290         for (el = lb_b->first,      i = 0; el; el = el->next, i++) { v_grid[(ytot * xtot) + (i - xtot)] = el->data; }
291         for (el = lb_rail_a->first, i = 0; el; el = el->next, i++) { v_grid[xtot * i]                   = el->data; }
292         for (el = lb_rail_b->first, i = 0; el; el = el->next, i++) { v_grid[(xtot * i) + (xtot - 1)]    = el->data; }
293 #ifdef DEBUG
294         for (x = 1; x < xtot - 1; x++) { for (y = 1; y < ytot - 1; y++) { BLI_assert(v_grid[(y * xtot) + x] == NULL); }}
295 #endif
296
297 #ifdef USE_FLIP_DETECT
298         {
299                 ListBase *lb_iter[4] = {lb_a, lb_b, lb_rail_a, lb_rail_b};
300                 const int lb_iter_dir[4] = {-1, 1, 1, -1};
301                 int winding_votes = 0;
302
303                 for (i = 0; i < 4; i++) {
304                         LinkData *el_next;
305                         for (el = lb_iter[i]->first; el && (el_next = el->next); el = el->next) {
306                                 BMEdge *e = BM_edge_exists(el->data, el_next->data);
307                                 if (BM_edge_is_boundary(e)) {
308                                         winding_votes += (e->l->v == el->data) ? lb_iter_dir[i] : -lb_iter_dir[i];
309                                 }
310                         }
311                 }
312                 use_flip = (winding_votes < 0);
313         }
314 #endif
315
316
317         bm_grid_fill_array(bm, v_grid, xtot, ytot, mat_nr, use_smooth, use_flip);
318         MEM_freeN(v_grid);
319
320 #undef USE_FLIP_DETECT
321 }
322
323 static bool bm_edge_test_cb(BMEdge *e, void *bm_v)
324 {
325         return BMO_elem_flag_test((BMesh *)bm_v, e, EDGE_MARK);
326 }
327
328 static bool bm_edge_test_rail_cb(BMEdge *e, void *UNUSED(bm_v))
329 {
330         /* normally operators dont check for hidden state
331          * but alternative would be to pass slot of rail edges */
332         if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
333                 return false;
334         }
335         return BM_edge_is_wire(e) || BM_edge_is_boundary(e);
336 }
337
338 void bmo_grid_fill_exec(BMesh *bm, BMOperator *op)
339 {
340         ListBase eloops = {NULL, NULL};
341         ListBase eloops_rail = {NULL, NULL};
342         struct BMEdgeLoopStore *estore_a, *estore_b;
343         struct BMEdgeLoopStore *estore_rail_a, *estore_rail_b;
344         BMVert *v_a_first, *v_a_last;
345         BMVert *v_b_first, *v_b_last;
346         const short mat_nr     = BMO_slot_int_get(op->slots_in,  "mat_nr");
347         const bool use_smooth  = BMO_slot_bool_get(op->slots_in, "use_smooth");
348
349         int count;
350         bool change = false;
351         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
352
353         count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, (void *)bm);
354
355         if (count != 2) {
356                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
357                                 "Select two edge loops");
358                 goto cleanup;
359         }
360
361         estore_a = eloops.first;
362         estore_b = eloops.last;
363
364         v_a_first = ((LinkData *)BM_edgeloop_verts_get(estore_a)->first)->data;
365         v_a_last  = ((LinkData *)BM_edgeloop_verts_get(estore_a)->last)->data;
366         v_b_first = ((LinkData *)BM_edgeloop_verts_get(estore_b)->first)->data;
367         v_b_last  = ((LinkData *)BM_edgeloop_verts_get(estore_b)->last)->data;
368
369         if (BM_edgeloop_length_get(estore_a) != BM_edgeloop_length_get(estore_b)) {
370                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
371                                 "Edge loop vertex count mismatch");
372                 goto cleanup;
373         }
374
375         if (BM_edgeloop_is_closed(estore_a) || BM_edgeloop_is_closed(estore_b)) {
376                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
377                                 "Closed loops unsupported");
378                 goto cleanup;
379         }
380
381         /* ok. all error checking done, now we can find the rail edges */
382
383         if (BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, bm, v_a_first, v_b_first) == false) {
384                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
385                                 "Loops are not connected by wire/boundary edges");
386                 goto cleanup;
387         }
388
389         BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm, v_a_first, v_b_last);
390
391         /* Check flipping by comparing path length */
392         estore_rail_a = eloops_rail.first;
393         estore_rail_b = eloops_rail.last;
394
395         BLI_assert(BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b));
396
397         if (BM_edgeloop_length_get(estore_rail_a) < BM_edgeloop_length_get(estore_rail_b)) {
398                 BLI_remlink(&eloops_rail, estore_rail_b);
399                 BM_edgeloop_free(estore_rail_b);
400                 estore_rail_b = NULL;
401
402                 BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm,
403                                             v_a_last,
404                                             v_b_last);
405                 estore_rail_b = eloops_rail.last;
406         }
407         else {  /* a > b */
408                 BLI_remlink(&eloops_rail, estore_rail_a);
409                 BM_edgeloop_free(estore_rail_a);
410                 estore_rail_a = estore_rail_b;
411
412                 /* reverse so these so both are sorted the same way */
413                 BM_edgeloop_flip(bm, estore_b);
414                 SWAP(BMVert *, v_b_first, v_b_last);
415
416                 BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm,
417                                             v_a_last,
418                                             v_b_last);
419                 estore_rail_b = eloops_rail.last;
420         }
421
422         BLI_assert(estore_a != estore_b);
423         BLI_assert(v_a_last != v_b_last);
424
425         if (BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b)) {
426                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
427                                 "Connecting edges vertex mismatch");
428                 goto cleanup;
429         }
430
431         if (BM_edgeloop_overlap_check(estore_rail_a, estore_rail_b)) {
432                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
433                                 "Connecting edge loops overlap");
434                 goto cleanup;
435         }
436
437         /* finally we have all edge loops needed */
438         bm_grid_fill(bm, estore_a, estore_b, estore_rail_a, estore_rail_b,
439                      mat_nr, use_smooth);
440
441         change = true;
442 cleanup:
443         BM_mesh_edgeloops_free(&eloops);
444         BM_mesh_edgeloops_free(&eloops_rail);
445
446         if (change) {
447                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
448         }
449 }