fix [#30613] B-mesh - inset created invalid mesh
[blender.git] / source / blender / bmesh / operators / bmo_inset.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 #include "MEM_guardedalloc.h"
24
25 #include "BLI_math.h"
26
27 #include "bmesh.h"
28
29 #include "intern/bmesh_operators_private.h" /* own include */
30
31 #define ELE_NEW         1
32
33 typedef struct SplitEdgeInfo {
34         float   no[3];
35         float   length;
36         BMEdge *e_old;
37         BMEdge *e_new;
38         BMLoop *l;
39 } SplitEdgeInfo;
40
41 static void edge_loop_tangent(BMEdge *e, BMLoop *e_loop, float r_no[3])
42 {
43         float tvec[3];
44         BMVert *v1, *v2;
45         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
46
47         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
48         cross_v3_v3v3(r_no, tvec, e_loop->f->no);
49         normalize_v3(r_no);
50 }
51
52 /**
53  * return the tag loop where there is...
54  * - only 1 tagged face attached to this edge.
55  * - 1 or more untagged faces.
56  *
57  * \note this function looks to be expensive
58  * but in most cases it will only do 2 iterations.
59  */
60 static BMLoop *bm_edge_is_mixed_face_tag(BMLoop *l)
61 {
62         if (LIKELY(l != NULL)) {
63                 int tot_tag = 0;
64                 int tot_untag = 0;
65                 BMLoop *l_iter;
66                 BMLoop *l_tag = NULL;
67                 l_iter = l;
68                 do {
69                         if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
70                                 /* more then one tagged face - bail out early! */
71                                 if (tot_tag == 1) {
72                                         return NULL;
73                                 }
74                                 l_tag = l_iter;
75                                 tot_tag++;
76                         }
77                         else {
78                                 tot_untag++;
79                         }
80
81                 } while ((l_iter = l_iter->radial_next) != l);
82
83                 return ((tot_tag == 1) && (tot_untag >= 1)) ? l_tag : NULL;
84         }
85         else {
86                 return NULL;
87         }
88 }
89
90
91 /**
92  * implementation is as follows...
93  *
94  * - set all faces as tagged/untagged based on selection.
95  * - find all edges that have 1 tagged, 1 untagged face.
96  * - separate these edges and tag vertices, set their index to point to the original edge.
97  * - build faces between old/new edges.
98  * - inset the new edges into their faces.
99  */
100
101 void bmo_inset_exec(BMesh *bm, BMOperator *op)
102 {
103         const int use_outset          = BMO_slot_bool_get(op, "use_outset");
104         const int use_boundary        = BMO_slot_bool_get(op, "use_boundary") && (use_outset == FALSE);
105         const int use_even_offset     = BMO_slot_bool_get(op, "use_even_offset");
106         const int use_even_boundry    = use_even_offset; /* could make own option */
107         const int use_relative_offset = BMO_slot_bool_get(op, "use_relative_offset");
108         const float thickness = BMO_slot_float_get(op, "thickness");
109
110         int edge_info_len = 0;
111
112         BMIter iter;
113         SplitEdgeInfo *edge_info;
114         SplitEdgeInfo *es;
115
116         BMVert *v;
117         BMEdge *e;
118         BMFace *f;
119         int i, j, k;
120
121         if (use_outset == FALSE) {
122                 BM_mesh_elem_flag_disable_all(bm, BM_FACE, BM_ELEM_TAG);
123                 BMO_slot_buffer_hflag_enable(bm, op, "faces", BM_FACE, BM_ELEM_TAG, FALSE);
124         }
125         else {
126                 BM_mesh_elem_flag_enable_all(bm, BM_FACE, BM_ELEM_TAG);
127                 BMO_slot_buffer_hflag_disable(bm, op, "faces", BM_FACE, BM_ELEM_TAG, FALSE);
128         }
129
130         /* first count all inset edges we will split */
131         /* fill in array and initialize tagging */
132         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
133                 if (
134                     /* tag if boundary is enabled */
135                     (use_boundary && BM_edge_is_boundary(e) && BM_elem_flag_test(e->l->f, BM_ELEM_TAG)) ||
136
137                     /* tag if edge is an interior edge inbetween a tagged and untagged face */
138                     (bm_edge_is_mixed_face_tag(e->l)))
139                 {
140                         /* tag */
141                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
142                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
143                         BM_elem_flag_enable(e, BM_ELEM_TAG);
144
145                         BM_elem_index_set(e, edge_info_len); /* set_dirty! */
146                         edge_info_len++;
147                 }
148                 else {
149                         BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
150                         BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
151                         BM_elem_flag_disable(e, BM_ELEM_TAG);
152
153                         BM_elem_index_set(e, -1); /* set_dirty! */
154                 }
155         }
156         bm->elem_index_dirty |= BM_EDGE;
157
158         edge_info = MEM_mallocN(edge_info_len * sizeof(SplitEdgeInfo), __func__);
159
160         /* fill in array and initialize tagging */
161         es = edge_info;
162         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
163                 i = BM_elem_index_get(e);
164                 if (i != -1) {
165                         /* calc edge-split info */
166                         es->length = BM_edge_length_calc(e);
167                         es->e_old = e;
168                         es++;
169                         /* initialize no and e_new after */
170                 }
171         }
172
173         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
174                 if ((es->l = bm_edge_is_mixed_face_tag(es->e_old->l))) {
175                         /* do nothing */
176                 }
177                 else {
178                         es->l = es->e_old->l; /* must be a boundary */
179                 }
180
181
182                 /* run the separate arg */
183                 bmesh_edge_separate(bm, es->e_old, es->l);
184
185                 /* calc edge-split info */
186                 es->e_new = es->l->e;
187                 edge_loop_tangent(es->e_new, es->l, es->no);
188
189                 if (es->e_new == es->e_old) { /* happens on boundary edges */
190                         es->e_old = BM_edge_create(bm, es->e_new->v1, es->e_new->v2, es->e_new, FALSE);
191                 }
192
193                 /* store index back to original in 'edge_info' */
194                 BM_elem_index_set(es->e_new, i);
195                 BM_elem_flag_enable(es->e_new, BM_ELEM_TAG);
196
197                 /* important to tag again here */
198                 BM_elem_flag_enable(es->e_new->v1, BM_ELEM_TAG);
199                 BM_elem_flag_enable(es->e_new->v2, BM_ELEM_TAG);
200         }
201
202
203         /* show edge normals for debugging */
204 #if 0
205         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
206                 float tvec[3];
207                 BMVert *v1, *v2;
208
209                 mid_v3_v3v3(tvec, es->e_new->v1->co, es->e_new->v2->co);
210
211                 v1 = BM_vert_create(bm, tvec, NULL);
212                 v2 = BM_vert_create(bm, tvec, NULL);
213                 madd_v3_v3fl(v2->co, es->no, 0.1f);
214                 BM_edge_create(bm, v1, v2, NULL, FALSE);
215         }
216 #endif
217
218         /* execute the split and position verts, it would be most obvious to loop over verts
219          * here but don't do this since we will be splitting them off (iterating stuff you modify is bad juju)
220          * instead loop over edges then their verts */
221         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
222                 for (j = 0; j < 2; j++) {
223                         v = (j == 0) ? es->e_new->v1 : es->e_new->v2;
224
225                         /* end confusing part - just pretend this is a typical loop on verts */
226
227                         /* only split of tagged verts - used by separated edges */
228
229                         /* comment the first part because we know this verts in a tagged face */
230                         if (/* v->e && */BM_elem_flag_test(v, BM_ELEM_TAG)) {
231                                 BMVert **vout;
232                                 int r_vout_len;
233                                 BMVert *v_glue = NULL;
234
235                                 /* disable touching twice, this _will_ happen if the flags not disabled */
236                                 BM_elem_flag_disable(v, BM_ELEM_TAG);
237
238                                 bmesh_vert_separate(bm, v, &vout, &r_vout_len);
239                                 v = NULL; /* don't use again */
240
241                                 /* in some cases the edge doesnt split off */
242                                 if (r_vout_len == 1) {
243                                         MEM_freeN(vout);
244                                         continue;
245                                 }
246
247                                 for (k = 0; k < r_vout_len; k++) {
248                                         BMVert *v_split = vout[k]; /* only to avoid vout[k] all over */
249
250                                         /* need to check if this vertex is from a */
251                                         int vert_edge_tag_tot = 0;
252                                         int vecpair[2];
253
254                                         /* find adjacent */
255                                         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v_split) {
256                                                 if (BM_elem_flag_test(e, BM_ELEM_TAG) &&
257                                                     BM_elem_flag_test(e->l->f, BM_ELEM_TAG))
258                                                 {
259                                                         if (vert_edge_tag_tot < 2) {
260                                                                 vecpair[vert_edge_tag_tot] = BM_elem_index_get(e);
261                                                                 BLI_assert(vecpair[vert_edge_tag_tot] != -1);
262                                                         }
263
264                                                         vert_edge_tag_tot++;
265                                                 }
266                                         }
267
268                                         if (vert_edge_tag_tot != 0) {
269                                                 float tvec[3];
270
271                                                 if (vert_edge_tag_tot >= 2) { /* 2 edge users - common case */
272                                                         const float *e_no_a = edge_info[vecpair[0]].no;
273                                                         const float *e_no_b = edge_info[vecpair[1]].no;
274
275                                                         add_v3_v3v3(tvec, e_no_a, e_no_b);
276                                                         normalize_v3(tvec);
277
278                                                         /* scale by edge angle */
279                                                         if (use_even_offset) {
280                                                                 mul_v3_fl(tvec, shell_angle_to_dist(angle_normalized_v3v3(e_no_a, e_no_b) / 2.0f));
281                                                         }
282
283                                                         /* scale relative to edge lengths */
284                                                         if (use_relative_offset) {
285                                                                 mul_v3_fl(tvec, (edge_info[vecpair[0]].length + edge_info[vecpair[1]].length) / 2.0f);
286                                                         }
287                                                 }
288                                                 else if (vert_edge_tag_tot == 1) { /* 1 edge user - boundary vert, not so common */
289                                                         const float *e_no_a = edge_info[vecpair[0]].no;
290
291                                                         if (use_even_boundry) {
292
293                                                                 /* This case where only one edge attached to v_split
294                                                                  * is used - ei - the face to inset is on a boundary.
295                                                                  *
296                                                                  *                  We want the inset to align flush with the
297                                                                  *                  boundary edge, not the normal of the interior
298                                                                  *             <--- edge which would give an unsightly bump.
299                                                                  * --+-------------------------+---------------+--
300                                                                  *   |^v_other    ^e_other    /^v_split        |
301                                                                  *   |                       /                 |
302                                                                  *   |                      /                  |
303                                                                  *   |                     / <- tag split edge |
304                                                                  *   |                    /                    |
305                                                                  *   |                   /                     |
306                                                                  *   |                  /                      |
307                                                                  * --+-----------------+-----------------------+--
308                                                                  *   |                                         |
309                                                                  *   |                                         |
310                                                                  *
311                                                                  * note, the fact we are doing location comparisons on verts that are moved about
312                                                                  * doesn’t matter because the direction will remain the same in this case.
313                                                                  */
314
315                                                                 BMEdge *e_other;
316                                                                 BMVert *v_other;
317                                                                 /* loop will always be either next of prev */
318                                                                 BMLoop *l = v_split->e->l;
319                                                                 if (l->prev->v == v_split) {
320                                                                         l = l->prev;
321                                                                 }
322                                                                 else if (l->next->v == v_split) {
323                                                                         l = l->next;
324                                                                 }
325                                                                 else if (l->v == v_split) {
326                                                                         /* pass */
327                                                                 }
328                                                                 else {
329                                                                         /* should never happen */
330                                                                         BLI_assert(0);
331                                                                 }
332
333                                                                 /* find the edge which is _not_ being split here */
334                                                                 if (!BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
335                                                                         e_other = l->e;
336                                                                 }
337                                                                 else if (!BM_elem_flag_test(l->prev->e, BM_ELEM_TAG)) {
338                                                                         e_other = l->prev->e;
339                                                                 }
340                                                                 else {
341                                                                         BLI_assert(0);
342                                                                         e_other = NULL;
343                                                                 }
344
345                                                                 v_other = BM_edge_other_vert(e_other, v_split);
346                                                                 sub_v3_v3v3(tvec, v_other->co, v_split->co);
347                                                                 normalize_v3(tvec);
348
349                                                                 if (use_even_offset) {
350                                                                         mul_v3_fl(tvec, shell_angle_to_dist(angle_normalized_v3v3(e_no_a, tvec)));
351                                                                 }
352                                                         }
353                                                         else {
354                                                                 copy_v3_v3(tvec, e_no_a);
355                                                         }
356
357                                                         /* use_even_offset - doesn't apply here */
358
359                                                         /* scale relative to edge length */
360                                                         if (use_relative_offset) {
361                                                                 mul_v3_fl(tvec, edge_info[vecpair[0]].length);
362                                                         }
363                                                 }
364                                                 else {
365                                                         /* should never happen */
366                                                         BLI_assert(0);
367                                                         zero_v3(tvec);
368                                                 }
369
370                                                 /* apply the offset */
371                                                 madd_v3_v3fl(v_split->co, tvec, thickness);
372                                         }
373
374                                         /* this saves expensive/slow glue check for common cases */
375                                         if (r_vout_len > 2) {
376                                                 int ok = TRUE;
377                                                 /* last step, NULL this vertex if has a tagged face */
378                                                 BM_ITER(f, &iter, bm, BM_FACES_OF_VERT, v_split) {
379                                                         if (BM_elem_flag_test(f, BM_ELEM_TAG)) {
380                                                                 ok = FALSE;
381                                                                 break;
382                                                         }
383                                                 }
384
385                                                 if (ok) {
386                                                         if (v_glue == NULL) {
387                                                                 v_glue = v_split;
388                                                         }
389                                                         else {
390                                                                 BM_vert_splice(bm, v_split, v_glue);
391                                                         }
392                                                 }
393                                         }
394                                         /* end glue */
395
396                                 }
397                                 MEM_freeN(vout);
398                         }
399                 }
400         }
401
402         /* create faces */
403         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
404                 BMVert *varr[4] = {NULL};
405                 /* get the verts in the correct order */
406                 BM_edge_ordered_verts_ex(es->e_new, &varr[1], &varr[0], es->l);
407 #if 0
408                 if (varr[0] == es->e_new->v1) {
409                         varr[2] = es->e_old->v2;
410                         varr[3] = es->e_old->v1;
411                 }
412                 else {
413                         varr[2] = es->e_old->v1;
414                         varr[3] = es->e_old->v2;
415                 }
416                 j = 4;
417 #else
418                 /* slightly trickier check - since we can't assume the verts are split */
419                 j = 2; /* 2 edges are set */
420                 if (varr[0] == es->e_new->v1) {
421                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
422                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
423                 }
424                 else {
425                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
426                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
427                 }
428
429                 if (j == 2) {
430                         /* can't make face! */
431                         continue;
432                 }
433 #endif
434                 /* no need to check doubles, we KNOW there won't be any */
435                 /* yes - reverse face is correct in this case */
436                 f = BM_face_create_quad_tri_v(bm, varr, j, es->l->f, FALSE);
437                 BMO_elem_flag_enable(bm, f, ELE_NEW);
438         }
439
440         MEM_freeN(edge_info);
441
442         /* we could flag new edges/verts too, is it useful? */
443         BMO_slot_buffer_from_flag(bm, op, "faceout", BM_FACE, ELE_NEW);
444 }