Merged changes in the trunk up to revision 55700.
[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 /** \file blender/bmesh/operators/bmo_inset.c
24  *  \ingroup bmesh
25  *
26  * Inset face regions.
27  *
28  * TODO
29  * - Inset indervidual faces.
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_math.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 #define ELE_NEW         1
41
42 typedef struct SplitEdgeInfo {
43         float   no[3];
44         float   length;
45         BMEdge *e_old;
46         BMEdge *e_new;
47         BMLoop *l;
48 } SplitEdgeInfo;
49
50 /**
51  * return the tag loop where there is...
52  * - only 1 tagged face attached to this edge.
53  * - 1 or more untagged faces.
54  *
55  * \note this function looks to be expensive
56  * but in most cases it will only do 2 iterations.
57  */
58 static BMLoop *bm_edge_is_mixed_face_tag(BMLoop *l)
59 {
60         if (LIKELY(l != NULL)) {
61                 int tot_tag = 0;
62                 int tot_untag = 0;
63                 BMLoop *l_iter;
64                 BMLoop *l_tag = NULL;
65                 l_iter = l;
66                 do {
67                         if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
68                                 /* more then one tagged face - bail out early! */
69                                 if (tot_tag == 1) {
70                                         return NULL;
71                                 }
72                                 l_tag = l_iter;
73                                 tot_tag++;
74                         }
75                         else {
76                                 tot_untag++;
77                         }
78
79                 } while ((l_iter = l_iter->radial_next) != l);
80
81                 return ((tot_tag == 1) && (tot_untag >= 1)) ? l_tag : NULL;
82         }
83         else {
84                 return NULL;
85         }
86 }
87
88 /**
89  * implementation is as follows...
90  *
91  * - set all faces as tagged/untagged based on selection.
92  * - find all edges that have 1 tagged, 1 untagged face.
93  * - separate these edges and tag vertices, set their index to point to the original edge.
94  * - build faces between old/new edges.
95  * - inset the new edges into their faces.
96  */
97
98 void bmo_inset_exec(BMesh *bm, BMOperator *op)
99 {
100         const bool use_outset          = BMO_slot_bool_get(op->slots_in, "use_outset");
101         const bool use_boundary        = BMO_slot_bool_get(op->slots_in, "use_boundary") && (use_outset == false);
102         const bool use_even_offset     = BMO_slot_bool_get(op->slots_in, "use_even_offset");
103         const bool use_even_boundry    = use_even_offset; /* could make own option */
104         const bool use_relative_offset = BMO_slot_bool_get(op->slots_in, "use_relative_offset");
105         const float thickness          = BMO_slot_float_get(op->slots_in, "thickness");
106         const float depth              = BMO_slot_float_get(op->slots_in, "depth");
107
108         int edge_info_len = 0;
109
110         BMIter iter;
111         SplitEdgeInfo *edge_info;
112         SplitEdgeInfo *es;
113
114         BMVert *v;
115         BMEdge *e;
116         BMFace *f;
117         int i, j, k;
118
119         if (use_outset == false) {
120                 BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
121                 BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
122         }
123         else {
124                 BM_mesh_elem_hflag_enable_all(bm, BM_FACE, BM_ELEM_TAG, false);
125                 BMO_slot_buffer_hflag_disable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
126         }
127
128         /* first count all inset edges we will split */
129         /* fill in array and initialize tagging */
130         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
131                 if (
132                     /* tag if boundary is enabled */
133                     (use_boundary && BM_edge_is_boundary(e) && BM_elem_flag_test(e->l->f, BM_ELEM_TAG)) ||
134
135                     /* tag if edge is an interior edge inbetween a tagged and untagged face */
136                     (bm_edge_is_mixed_face_tag(e->l)))
137                 {
138                         /* tag */
139                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
140                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
141                         BM_elem_flag_enable(e, BM_ELEM_TAG);
142
143                         BM_elem_index_set(e, edge_info_len); /* set_dirty! */
144                         edge_info_len++;
145                 }
146                 else {
147                         BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
148                         BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
149                         BM_elem_flag_disable(e, BM_ELEM_TAG);
150
151                         BM_elem_index_set(e, -1); /* set_dirty! */
152                 }
153         }
154         bm->elem_index_dirty |= BM_EDGE;
155
156         edge_info = MEM_mallocN(edge_info_len * sizeof(SplitEdgeInfo), __func__);
157
158         /* fill in array and initialize tagging */
159         es = edge_info;
160         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
161                 i = BM_elem_index_get(e);
162                 if (i != -1) {
163                         /* calc edge-split info */
164                         es->length = BM_edge_calc_length(e);
165                         es->e_old = e;
166                         es++;
167                         /* initialize no and e_new after */
168                 }
169         }
170
171         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
172                 if ((es->l = bm_edge_is_mixed_face_tag(es->e_old->l))) {
173                         /* do nothing */
174                 }
175                 else {
176                         es->l = es->e_old->l; /* must be a boundary */
177                 }
178
179
180                 /* run the separate arg */
181                 bmesh_edge_separate(bm, es->e_old, es->l);
182
183                 /* calc edge-split info */
184                 es->e_new = es->l->e;
185                 BM_edge_calc_face_tangent(es->e_new, es->l, es->no);
186
187                 if (es->e_new == es->e_old) { /* happens on boundary edges */
188                         /* take care here, we're creating this double edge which _must_ have its verts replaced later on */
189                         es->e_old = BM_edge_create(bm, es->e_new->v1, es->e_new->v2, es->e_new, 0);
190                 }
191
192                 /* store index back to original in 'edge_info' */
193                 BM_elem_index_set(es->e_new, i);
194                 BM_elem_flag_enable(es->e_new, BM_ELEM_TAG);
195
196                 /* important to tag again here */
197                 BM_elem_flag_enable(es->e_new->v1, BM_ELEM_TAG);
198                 BM_elem_flag_enable(es->e_new->v2, BM_ELEM_TAG);
199         }
200
201
202         /* show edge normals for debugging */
203 #if 0
204         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
205                 float tvec[3];
206                 BMVert *v1, *v2;
207
208                 mid_v3_v3v3(tvec, es->e_new->v1->co, es->e_new->v2->co);
209
210                 v1 = BM_vert_create(bm, tvec, NULL);
211                 v2 = BM_vert_create(bm, tvec, NULL);
212                 madd_v3_v3fl(v2->co, es->no, 0.1f);
213                 BM_edge_create(bm, v1, v2, NULL, 0);
214         }
215 #endif
216
217         /* execute the split and position verts, it would be most obvious to loop over verts
218          * here but don't do this since we will be splitting them off (iterating stuff you modify is bad juju)
219          * instead loop over edges then their verts */
220         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
221                 for (j = 0; j < 2; j++) {
222                         v = (j == 0) ? es->e_new->v1 : es->e_new->v2;
223
224                         /* end confusing part - just pretend this is a typical loop on verts */
225
226                         /* only split of tagged verts - used by separated edges */
227
228                         /* comment the first part because we know this verts in a tagged face */
229                         if (/* v->e && */BM_elem_flag_test(v, BM_ELEM_TAG)) {
230                                 BMVert **vout;
231                                 int r_vout_len;
232                                 BMVert *v_glue = NULL;
233
234                                 /* disable touching twice, this _will_ happen if the flags not disabled */
235                                 BM_elem_flag_disable(v, BM_ELEM_TAG);
236
237                                 bmesh_vert_separate(bm, v, &vout, &r_vout_len);
238                                 v = NULL; /* don't use again */
239
240                                 /* in some cases the edge doesn't split off */
241                                 if (r_vout_len == 1) {
242                                         MEM_freeN(vout);
243                                         continue;
244                                 }
245
246                                 for (k = 0; k < r_vout_len; k++) {
247                                         BMVert *v_split = vout[k]; /* only to avoid vout[k] all over */
248
249                                         /* need to check if this vertex is from a */
250                                         int vert_edge_tag_tot = 0;
251                                         int vecpair[2];
252
253                                         /* find adjacent */
254                                         BM_ITER_ELEM (e, &iter, v_split, BM_EDGES_OF_VERT) {
255                                                 if (BM_elem_flag_test(e, BM_ELEM_TAG) &&
256                                                     e->l && BM_elem_flag_test(e->l->f, BM_ELEM_TAG))
257                                                 {
258                                                         if (vert_edge_tag_tot < 2) {
259                                                                 vecpair[vert_edge_tag_tot] = BM_elem_index_get(e);
260                                                                 BLI_assert(vecpair[vert_edge_tag_tot] != -1);
261                                                         }
262
263                                                         vert_edge_tag_tot++;
264                                                 }
265                                         }
266
267                                         if (vert_edge_tag_tot != 0) {
268                                                 float tvec[3];
269
270                                                 if (vert_edge_tag_tot >= 2) { /* 2 edge users - common case */
271                                                         /* now there are 2 cases to check for,
272                                                          *
273                                                          * if both edges use the same face OR both faces have the same normal,
274                                                          * ...then we can calculate an edge that fits nicely between the 2 edge normals.
275                                                          *
276                                                          * Otherwise use the shared edge OR the corner defined by these 2 face normals,
277                                                          * when both edges faces are adjacent this works best but even when this vertex
278                                                          * fans out faces it should work ok.
279                                                          */
280
281                                                         SplitEdgeInfo *e_info_a = &edge_info[vecpair[0]];
282                                                         SplitEdgeInfo *e_info_b = &edge_info[vecpair[1]];
283
284                                                         BMFace *f_a = e_info_a->l->f;
285                                                         BMFace *f_b = e_info_b->l->f;
286
287                                                         /* we use this as either the normal OR to find the right direction for the
288                                                          * cross product between both face normals */
289                                                         add_v3_v3v3(tvec, e_info_a->no, e_info_b->no);
290
291                                                         /* epsilon increased to fix [#32329] */
292                                                         if ((f_a == f_b) || compare_v3v3(f_a->no, f_b->no, 0.001f)) {
293                                                                 normalize_v3(tvec);
294                                                         }
295                                                         else {
296                                                                 /* these lookups are very quick */
297                                                                 BMLoop *l_other_a = BM_loop_other_vert_loop(e_info_a->l, v_split);
298                                                                 BMLoop *l_other_b = BM_loop_other_vert_loop(e_info_b->l, v_split);
299
300                                                                 if (l_other_a->v == l_other_b->v) {
301                                                                         /* both edges faces are adjacent, but we don't need to know the shared edge
302                                                                          * having both verts is enough. */
303                                                                         sub_v3_v3v3(tvec, l_other_a->v->co, v_split->co);
304                                                                 }
305                                                                 else {
306                                                                         /* faces don't touch,
307                                                                          * just get cross product of their normals, its *good enough*
308                                                                          */
309                                                                         float tno[3];
310                                                                         cross_v3_v3v3(tno, f_a->no, f_b->no);
311                                                                         if (dot_v3v3(tvec, tno) < 0.0f) {
312                                                                                 negate_v3(tno);
313                                                                         }
314                                                                         copy_v3_v3(tvec, tno);
315                                                                 }
316
317                                                                 normalize_v3(tvec);
318                                                         }
319
320                                                         /* scale by edge angle */
321                                                         if (use_even_offset) {
322                                                                 mul_v3_fl(tvec, shell_angle_to_dist(angle_normalized_v3v3(e_info_a->no,
323                                                                                                                           e_info_b->no) / 2.0f));
324                                                         }
325
326                                                         /* scale relative to edge lengths */
327                                                         if (use_relative_offset) {
328                                                                 mul_v3_fl(tvec, (edge_info[vecpair[0]].length + edge_info[vecpair[1]].length) / 2.0f);
329                                                         }
330                                                 }
331                                                 else if (vert_edge_tag_tot == 1) { /* 1 edge user - boundary vert, not so common */
332                                                         const float *e_no_a = edge_info[vecpair[0]].no;
333
334                                                         if (use_even_boundry) {
335
336                                                                 /* This case where only one edge attached to v_split
337                                                                  * is used - ei - the face to inset is on a boundary.
338                                                                  *
339                                                                  *                  We want the inset to align flush with the
340                                                                  *                  boundary edge, not the normal of the interior
341                                                                  *             <--- edge which would give an unsightly bump.
342                                                                  * --+-------------------------+---------------+--
343                                                                  *   |^v_other    ^e_other    /^v_split        |
344                                                                  *   |                       /                 |
345                                                                  *   |                      /                  |
346                                                                  *   |                     / <- tag split edge |
347                                                                  *   |                    /                    |
348                                                                  *   |                   /                     |
349                                                                  *   |                  /                      |
350                                                                  * --+-----------------+-----------------------+--
351                                                                  *   |                                         |
352                                                                  *   |                                         |
353                                                                  *
354                                                                  * note, the fact we are doing location comparisons on verts that are moved about
355                                                                  * doesn't matter because the direction will remain the same in this case.
356                                                                  */
357
358                                                                 BMEdge *e_other;
359                                                                 BMVert *v_other;
360                                                                 /* loop will always be either next of prev */
361                                                                 BMLoop *l = v_split->e->l;
362                                                                 if (l->prev->v == v_split) {
363                                                                         l = l->prev;
364                                                                 }
365                                                                 else if (l->next->v == v_split) {
366                                                                         l = l->next;
367                                                                 }
368                                                                 else if (l->v == v_split) {
369                                                                         /* pass */
370                                                                 }
371                                                                 else {
372                                                                         /* should never happen */
373                                                                         BLI_assert(0);
374                                                                 }
375
376                                                                 /* find the edge which is _not_ being split here */
377                                                                 if (!BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
378                                                                         e_other = l->e;
379                                                                 }
380                                                                 else if (!BM_elem_flag_test(l->prev->e, BM_ELEM_TAG)) {
381                                                                         e_other = l->prev->e;
382                                                                 }
383                                                                 else {
384                                                                         BLI_assert(0);
385                                                                         e_other = NULL;
386                                                                 }
387
388                                                                 v_other = BM_edge_other_vert(e_other, v_split);
389                                                                 sub_v3_v3v3(tvec, v_other->co, v_split->co);
390                                                                 normalize_v3(tvec);
391
392                                                                 if (use_even_offset) {
393                                                                         mul_v3_fl(tvec, shell_angle_to_dist(angle_normalized_v3v3(e_no_a, tvec)));
394                                                                 }
395                                                         }
396                                                         else {
397                                                                 copy_v3_v3(tvec, e_no_a);
398                                                         }
399
400                                                         /* use_even_offset - doesn't apply here */
401
402                                                         /* scale relative to edge length */
403                                                         if (use_relative_offset) {
404                                                                 mul_v3_fl(tvec, edge_info[vecpair[0]].length);
405                                                         }
406                                                 }
407                                                 else {
408                                                         /* should never happen */
409                                                         BLI_assert(0);
410                                                         zero_v3(tvec);
411                                                 }
412
413                                                 /* apply the offset */
414                                                 madd_v3_v3fl(v_split->co, tvec, thickness);
415                                         }
416
417                                         /* this saves expensive/slow glue check for common cases */
418                                         if (r_vout_len > 2) {
419                                                 bool ok = true;
420                                                 /* last step, NULL this vertex if has a tagged face */
421                                                 BM_ITER_ELEM (f, &iter, v_split, BM_FACES_OF_VERT) {
422                                                         if (BM_elem_flag_test(f, BM_ELEM_TAG)) {
423                                                                 ok = false;
424                                                                 break;
425                                                         }
426                                                 }
427
428                                                 if (ok) {
429                                                         if (v_glue == NULL) {
430                                                                 v_glue = v_split;
431                                                         }
432                                                         else {
433                                                                 BM_vert_splice(bm, v_split, v_glue);
434                                                         }
435                                                 }
436                                         }
437                                         /* end glue */
438
439                                 }
440                                 MEM_freeN(vout);
441                         }
442                 }
443         }
444
445         /* create faces */
446         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
447                 BMVert *varr[4] = {NULL};
448                 /* get the verts in the correct order */
449                 BM_edge_ordered_verts_ex(es->e_new, &varr[1], &varr[0], es->l);
450 #if 0
451                 if (varr[0] == es->e_new->v1) {
452                         varr[2] = es->e_old->v2;
453                         varr[3] = es->e_old->v1;
454                 }
455                 else {
456                         varr[2] = es->e_old->v1;
457                         varr[3] = es->e_old->v2;
458                 }
459                 j = 4;
460 #else
461                 /* slightly trickier check - since we can't assume the verts are split */
462                 j = 2; /* 2 edges are set */
463                 if (varr[0] == es->e_new->v1) {
464                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
465                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
466                 }
467                 else {
468                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
469                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
470                 }
471
472                 if (j == 2) {
473                         /* can't make face! */
474                         continue;
475                 }
476 #endif
477                 /* no need to check doubles, we KNOW there won't be any */
478                 /* yes - reverse face is correct in this case */
479                 f = BM_face_create_quad_tri_v(bm, varr, j, es->l->f, false);
480                 BMO_elem_flag_enable(bm, f, ELE_NEW);
481
482                 /* copy for loop data, otherwise UV's and vcols are no good.
483                  * tiny speedup here we could be more clever and copy from known adjacent data
484                  * also - we could attempt to interpolate the loop data, this would be much slower but more useful too */
485 #if 0
486                 /* don't use this because face boundaries have no adjacent loops and won't be filled in.
487                  * instead copy from the opposite side with the code below */
488                 BM_face_copy_shared(bm, f);
489 #else
490                 {
491                         /* 2 inner loops on the edge between the new face and the original */
492                         BMLoop *l_a;
493                         BMLoop *l_b;
494                         BMLoop *l_a_other;
495                         BMLoop *l_b_other;
496
497                         l_a = BM_FACE_FIRST_LOOP(f);
498                         l_b = l_a->next;
499
500                         /* we know this side has a radial_next because of the order of created verts in the quad */
501                         l_a_other = BM_edge_other_loop(l_a->e, l_a);
502                         l_b_other = BM_edge_other_loop(l_a->e, l_b);
503                         BM_elem_attrs_copy(bm, bm, l_a_other, l_a);
504                         BM_elem_attrs_copy(bm, bm, l_b_other, l_b);
505
506                         /* step around to the opposite side of the quad - warning, this may have no other edges! */
507                         l_a = l_a->next->next;
508                         l_b = l_a->next;
509                         if (!BM_edge_is_boundary(l_a->e)) {
510                                 /* same as above */
511                                 l_a_other = BM_edge_other_loop(l_a->e, l_a);
512                                 l_b_other = BM_edge_other_loop(l_a->e, l_b);
513                                 BM_elem_attrs_copy(bm, bm, l_a_other, l_a);
514                                 BM_elem_attrs_copy(bm, bm, l_b_other, l_b);
515                         }
516                         else {  /* boundary edges have no useful data to copy from, use opposite side of face */
517                                 /* swap a<->b intentionally */
518                                 BM_elem_attrs_copy(bm, bm, l_a_other, l_b);
519                                 BM_elem_attrs_copy(bm, bm, l_b_other, l_a);
520                         }
521                 }
522 #endif
523         }
524
525         /* we could flag new edges/verts too, is it useful? */
526         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, ELE_NEW);
527
528         /* cheap feature to add depth to the inset */
529         if (depth != 0.0f) {
530                 float (*varr_co)[3];
531                 BMOIter oiter;
532
533                 /* we need to re-calculate tagged normals, but for this purpose we can copy tagged verts from the
534                  * faces they inset from,  */
535                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
536                         zero_v3(es->e_new->v1->no);
537                         zero_v3(es->e_new->v2->no);
538                 }
539                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
540                         float *no = es->l->f->no;
541                         add_v3_v3(es->e_new->v1->no, no);
542                         add_v3_v3(es->e_new->v2->no, no);
543                 }
544                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
545                         /* annoying, avoid normalizing twice */
546                         if (len_squared_v3(es->e_new->v1->no) != 1.0f) {
547                                 normalize_v3(es->e_new->v1->no);
548                         }
549                         if (len_squared_v3(es->e_new->v2->no) != 1.0f) {
550                                 normalize_v3(es->e_new->v2->no);
551                         }
552                 }
553                 /* done correcting edge verts normals */
554
555                 /* untag verts */
556                 BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
557
558                 /* tag face verts */
559                 BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
560                         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
561                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
562                         }
563                 }
564
565                 /* do in 2 passes so moving the verts doesn't feed back into face angle checks
566                  * which BM_vert_calc_shell_factor uses. */
567
568                 /* over allocate */
569                 varr_co = MEM_callocN(sizeof(*varr_co) * bm->totvert, __func__);
570
571                 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
572                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
573                                 const float fac = (depth *
574                                                    (use_relative_offset ? BM_vert_calc_mean_tagged_edge_length(v) : 1.0f) *
575                                                    (use_even_boundry    ? BM_vert_calc_shell_factor(v) : 1.0f));
576                                 madd_v3_v3v3fl(varr_co[i], v->co, v->no, fac);
577                         }
578                 }
579
580                 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
581                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
582                                 copy_v3_v3(v->co, varr_co[i]);
583                         }
584                 }
585                 MEM_freeN(varr_co);
586         }
587
588         MEM_freeN(edge_info);
589 }