Spelling
[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  * Inset individual faces.
28  *
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_math.h"
34 #include "BLI_alloca.h"
35 #include "BLI_memarena.h"
36 #include "BKE_customdata.h"
37
38 #include "bmesh.h"
39
40 #include "intern/bmesh_operators_private.h" /* own include */
41
42 #define ELE_NEW         1
43
44
45 /* -------------------------------------------------------------------- */
46 /* Generic Interp Face (use for both types of inset) */
47
48 /**
49  * Interpolation, this is more complex for regions since we're not creating new faces
50  * and throwing away old ones, so instead, store face data needed for interpolation.
51  *
52  * \note This uses CustomData functions in quite a low-level way which should be
53  * avoided, but in this case its hard to do without storing a duplicate mesh. */
54
55 /* just enough of a face to store interpolation data we can use once the inset is done */
56 typedef struct InterpFace {
57         BMFace *f;
58         void **blocks_l;
59         void **blocks_v;
60         float (*cos_2d)[2];
61         float axis_mat[3][3];
62 } InterpFace;
63
64 /* basically a clone of #BM_vert_interp_from_face */
65 static void bm_interp_face_store(InterpFace *iface, BMesh *bm, BMFace *f, MemArena *interp_arena)
66 {
67         BMLoop *l_iter, *l_first;
68         void **blocks_l    = iface->blocks_l = BLI_memarena_alloc(interp_arena, sizeof(*iface->blocks_l) * f->len);
69         void **blocks_v    = iface->blocks_v = BLI_memarena_alloc(interp_arena, sizeof(*iface->blocks_v) * f->len);
70         float (*cos_2d)[2] = iface->cos_2d = BLI_memarena_alloc(interp_arena, sizeof(*iface->cos_2d) * f->len);
71         void *axis_mat     = iface->axis_mat;
72         int i;
73
74         BLI_assert(BM_face_is_normal_valid(f));
75
76         axis_dominant_v3_to_m3(axis_mat, f->no);
77
78         iface->f = f;
79
80         i = 0;
81         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
82         do {
83                 mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
84                 blocks_l[i] = NULL;
85                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_iter->head.data, &blocks_l[i]);
86                 /* if we were not modifying the loops later we would do... */
87                 // blocks[i] = l_iter->head.data;
88
89                 blocks_v[i] = NULL;
90                 CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, l_iter->v->head.data, &blocks_v[i]);
91
92                 /* use later for index lookups */
93                 BM_elem_index_set(l_iter, i); /* set_dirty */
94         } while (i++, (l_iter = l_iter->next) != l_first);
95         bm->elem_index_dirty |= BM_LOOP;
96 }
97 static void bm_interp_face_free(InterpFace *iface, BMesh *bm)
98 {
99         void **blocks_l = iface->blocks_l;
100         void **blocks_v = iface->blocks_v;
101         int i;
102
103         for (i = 0; i < iface->f->len; i++) {
104                 CustomData_bmesh_free_block(&bm->ldata, &blocks_l[i]);
105                 CustomData_bmesh_free_block(&bm->vdata, &blocks_v[i]);
106         }
107 }
108
109
110 /* -------------------------------------------------------------------- */
111 /* Inset Individual */
112
113 static void bmo_face_inset_individual(
114         BMesh *bm, BMFace *f, MemArena *interp_arena,
115         const float thickness, const float depth,
116         const bool use_even_offset, const bool use_relative_offset, const bool use_interpolate)
117 {
118         InterpFace *iface = NULL;
119
120         /* stores verts split away from the face (aligned with face verts) */
121         BMVert **verts = BLI_array_alloca(verts, f->len);
122         /* store edge normals (aligned with face-loop-edges) */
123         float (*edge_nors)[3] = BLI_array_alloca(edge_nors, f->len);
124         float (*coords)[3] = BLI_array_alloca(coords, f->len);
125
126         BMLoop *l_iter, *l_first;
127         BMLoop *l_other;
128         unsigned int i;
129         float e_length_prev;
130
131         l_first = BM_FACE_FIRST_LOOP(f);
132
133         /* split off all loops */
134         l_iter = l_first;
135         i = 0;
136         do {
137                 BMVert *v_other = l_iter->v;
138                 BMVert *v_sep = BM_face_loop_separate(bm, l_iter);
139                 if (v_sep == v_other) {
140                         v_other = BM_vert_create(bm, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
141                 }
142                 verts[i] = v_other;
143
144                 /* unrelated to splitting, but calc here */
145                 BM_edge_calc_face_tangent(l_iter->e, l_iter, edge_nors[i]);
146         } while (i++, ((l_iter = l_iter->next) != l_first));
147
148
149         /* build rim faces */
150         l_iter = l_first;
151         i = 0;
152         do {
153                 BMFace *f_new_outer;
154                 BMVert *v_other = verts[i];
155                 BMVert *v_other_next = verts[(i + 1) % f->len];
156
157                 BMEdge *e_other = BM_edge_create(bm, v_other, v_other_next, l_iter->e, BM_CREATE_NO_DOUBLE);
158                 (void)e_other;
159
160                 f_new_outer = BM_face_create_quad_tri(bm,
161                                                       v_other,
162                                                       v_other_next,
163                                                       l_iter->next->v,
164                                                       l_iter->v,
165                                                       f, BM_CREATE_NOP);
166                 BMO_elem_flag_enable(bm, f_new_outer, ELE_NEW);
167
168                 /* copy loop data */
169                 l_other = l_iter->radial_next;
170                 BM_elem_attrs_copy(bm, bm, l_iter->next, l_other->prev);
171                 BM_elem_attrs_copy(bm, bm, l_iter, l_other->next->next);
172
173                 if (use_interpolate == false) {
174                         BM_elem_attrs_copy(bm, bm, l_iter->next, l_other);
175                         BM_elem_attrs_copy(bm, bm, l_iter, l_other->next);
176                 }
177         } while (i++, ((l_iter = l_iter->next) != l_first));
178
179         /* hold interpolation values */
180         if (use_interpolate) {
181                 iface = BLI_memarena_alloc(interp_arena, sizeof(*iface));
182                 bm_interp_face_store(iface, bm, f, interp_arena);
183         }
184
185         /* Calculate translation vector for new */
186         l_iter = l_first;
187         i = 0;
188
189         if (depth != 0.0f) {
190                 e_length_prev = BM_edge_calc_length(l_iter->prev->e);
191         }
192
193         do {
194                 const float *eno_prev = edge_nors[(i ? i : f->len) - 1];
195                 const float *eno_next = edge_nors[i];
196                 float tvec[3];
197                 float v_new_co[3];
198
199                 add_v3_v3v3(tvec, eno_prev, eno_next);
200                 normalize_v3(tvec);
201
202                 copy_v3_v3(v_new_co, l_iter->v->co);
203
204                 if (use_even_offset) {
205                         mul_v3_fl(tvec, shell_v3v3_mid_normalized_to_dist(eno_prev,  eno_next));
206                 }
207
208                 /* Modify vertices and their normals */
209                 if (use_relative_offset) {
210                         mul_v3_fl(tvec, (BM_edge_calc_length(l_iter->e) + BM_edge_calc_length(l_iter->prev->e)) / 2.0f);
211                 }
212
213                 madd_v3_v3fl(v_new_co, tvec, thickness);
214
215                 /* Set normal, add depth and write new vertex position*/
216                 copy_v3_v3(l_iter->v->no, f->no);
217
218                 if (depth != 0.0f) {
219                         const float e_length = BM_edge_calc_length(l_iter->e);
220                         const float fac = depth * (use_relative_offset ? ((e_length_prev + e_length) * 0.5f) : 1.0f);
221                         e_length_prev = e_length;
222
223                         madd_v3_v3fl(v_new_co, f->no, fac);
224                 }
225
226
227
228                 copy_v3_v3(coords[i], v_new_co);
229         } while (i++, ((l_iter = l_iter->next) != l_first));
230
231         /* update the coords */
232         l_iter = l_first;
233         i = 0;
234         do {
235                 copy_v3_v3(l_iter->v->co, coords[i]);
236         } while (i++, ((l_iter = l_iter->next) != l_first));
237
238
239         if (use_interpolate) {
240                 BM_face_interp_from_face_ex(bm, iface->f, iface->f, true,
241                                             iface->blocks_l, iface->blocks_v, iface->cos_2d, iface->axis_mat);
242
243                 /* build rim faces */
244                 l_iter = l_first;
245                 do {
246                         /* copy loop data */
247                         l_other = l_iter->radial_next;
248
249                         BM_elem_attrs_copy(bm, bm, l_iter->next, l_other);
250                         BM_elem_attrs_copy(bm, bm, l_iter, l_other->next);
251                 } while ((l_iter = l_iter->next) != l_first);
252
253                 bm_interp_face_free(iface, bm);
254         }
255 }
256
257
258 /**
259  * Individual Face Inset.
260  * Find all tagged faces (f), duplicate edges around faces, inset verts of
261  * created edges, create new faces between old and new edges, fill face
262  * between connected new edges, kill old face (f).
263  */
264 void bmo_inset_individual_exec(BMesh *bm, BMOperator *op)
265 {
266         BMFace *f;
267
268         BMOIter oiter;
269         MemArena *interp_arena = NULL;
270
271         const float thickness = BMO_slot_float_get(op->slots_in, "thickness");
272         const float depth = BMO_slot_float_get(op->slots_in, "depth");
273         const bool use_even_offset = BMO_slot_bool_get(op->slots_in, "use_even_offset");
274         const bool use_relative_offset = BMO_slot_bool_get(op->slots_in, "use_relative_offset");
275         const bool use_interpolate = BMO_slot_bool_get(op->slots_in, "use_interpolate");
276
277         /* Only tag faces in slot */
278         BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
279
280         BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
281
282         if (use_interpolate) {
283                 interp_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
284         }
285
286         BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
287                 bmo_face_inset_individual(
288                         bm, f, interp_arena,
289                         thickness, depth,
290                         use_even_offset, use_relative_offset, use_interpolate);
291
292                 if (use_interpolate) {
293                         BLI_memarena_clear(interp_arena);
294                 }
295         }
296
297         /* we could flag new edges/verts too, is it useful? */
298         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, ELE_NEW);
299
300         if (use_interpolate) {
301                 BLI_memarena_free(interp_arena);
302         }
303 }
304
305
306
307 /* -------------------------------------------------------------------- */
308 /* Inset Region */
309
310 typedef struct SplitEdgeInfo {
311         float   no[3];
312         float   length;
313         BMEdge *e_old;
314         BMEdge *e_new;
315         BMLoop *l;
316 } SplitEdgeInfo;
317
318 /**
319  * return the tag loop where there is...
320  * - only 1 tagged face attached to this edge.
321  * - 1 or more untagged faces.
322  *
323  * \note this function looks to be expensive
324  * but in most cases it will only do 2 iterations.
325  */
326 static BMLoop *bm_edge_is_mixed_face_tag(BMLoop *l)
327 {
328         if (LIKELY(l != NULL)) {
329                 int tot_tag = 0;
330                 int tot_untag = 0;
331                 BMLoop *l_iter;
332                 BMLoop *l_tag = NULL;
333                 l_iter = l;
334                 do {
335                         if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
336                                 /* more than one tagged face - bail out early! */
337                                 if (tot_tag == 1) {
338                                         return NULL;
339                                 }
340                                 l_tag = l_iter;
341                                 tot_tag++;
342                         }
343                         else {
344                                 tot_untag++;
345                         }
346
347                 } while ((l_iter = l_iter->radial_next) != l);
348
349                 return ((tot_tag == 1) && (tot_untag >= 1)) ? l_tag : NULL;
350         }
351         else {
352                 return NULL;
353         }
354 }
355
356 static float bm_edge_info_average_length(BMVert *v, SplitEdgeInfo *edge_info)
357 {
358         BMIter iter;
359         BMEdge *e;
360
361         float len = 0.0f;
362         int tot = 0;
363
364
365         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
366                 const int i = BM_elem_index_get(e);
367                 if (i != -1) {
368                         len += edge_info[i].length;
369                         tot++;
370                 }
371         }
372
373         BLI_assert(tot != 0);
374         return len / (float)tot;
375 }
376
377 /**
378  * implementation is as follows...
379  *
380  * - set all faces as tagged/untagged based on selection.
381  * - find all edges that have 1 tagged, 1 untagged face.
382  * - separate these edges and tag vertices, set their index to point to the original edge.
383  * - build faces between old/new edges.
384  * - inset the new edges into their faces.
385  */
386
387 void bmo_inset_region_exec(BMesh *bm, BMOperator *op)
388 {
389         const bool use_outset          = BMO_slot_bool_get(op->slots_in, "use_outset");
390         const bool use_boundary        = BMO_slot_bool_get(op->slots_in, "use_boundary") && (use_outset == false);
391         const bool use_even_offset     = BMO_slot_bool_get(op->slots_in, "use_even_offset");
392         const bool use_even_boundary   = use_even_offset; /* could make own option */
393         const bool use_relative_offset = BMO_slot_bool_get(op->slots_in, "use_relative_offset");
394         const bool use_edge_rail       = BMO_slot_bool_get(op->slots_in, "use_edge_rail");
395         const bool use_interpolate     = BMO_slot_bool_get(op->slots_in, "use_interpolate");
396         const float thickness          = BMO_slot_float_get(op->slots_in, "thickness");
397         const float depth              = BMO_slot_float_get(op->slots_in, "depth");
398
399         int edge_info_len = 0;
400
401         BMIter iter;
402         SplitEdgeInfo *edge_info;
403         SplitEdgeInfo *es;
404
405         /* Interpolation Vars */
406         /* an array alligned with faces but only fill items which are used. */
407         InterpFace **iface_array = NULL;
408         int          iface_array_len;
409         MemArena *interp_arena = NULL;
410
411         /* BMVert original location storage */
412         const bool use_vert_coords_orig = use_edge_rail;
413         MemArena *vert_coords_orig = NULL;
414         GHash *vert_coords = NULL;
415
416         BMVert *v;
417         BMEdge *e;
418         BMFace *f;
419         int i, j, k;
420
421         if (use_interpolate) {
422                 interp_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
423                 /* warning, we could be more clever here and not over alloc */
424                 iface_array = MEM_callocN(sizeof(*iface_array) * bm->totface, __func__);
425                 iface_array_len = bm->totface;
426         }
427
428         if (use_outset == false) {
429                 BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
430                 BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
431         }
432         else {
433                 BM_mesh_elem_hflag_enable_all(bm, BM_FACE, BM_ELEM_TAG, false);
434                 BMO_slot_buffer_hflag_disable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
435         }
436
437         /* first count all inset edges we will split */
438         /* fill in array and initialize tagging */
439         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
440                 if (
441                     /* tag if boundary is enabled */
442                     (use_boundary && BM_edge_is_boundary(e) && BM_elem_flag_test(e->l->f, BM_ELEM_TAG)) ||
443
444                     /* tag if edge is an interior edge inbetween a tagged and untagged face */
445                     (bm_edge_is_mixed_face_tag(e->l)))
446                 {
447                         /* tag */
448                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
449                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
450                         BM_elem_flag_enable(e, BM_ELEM_TAG);
451
452                         BM_elem_index_set(e, edge_info_len); /* set_dirty! */
453                         edge_info_len++;
454                 }
455                 else {
456                         BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
457                         BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
458                         BM_elem_flag_disable(e, BM_ELEM_TAG);
459
460                         BM_elem_index_set(e, -1); /* set_dirty! */
461                 }
462         }
463         bm->elem_index_dirty |= BM_EDGE;
464
465         edge_info = MEM_mallocN(edge_info_len * sizeof(SplitEdgeInfo), __func__);
466
467         /* fill in array and initialize tagging */
468         es = edge_info;
469         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
470                 i = BM_elem_index_get(e);
471                 if (i != -1) {
472                         /* calc edge-split info */
473                         es->length = BM_edge_calc_length(e);
474                         es->e_old = e;
475                         es++;
476                         /* initialize no and e_new after */
477                 }
478         }
479
480
481         if (use_vert_coords_orig) {
482                 vert_coords_orig = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
483                 vert_coords = BLI_ghash_ptr_new(__func__);
484         }
485
486         /* util macros */
487 #define VERT_ORIG_STORE(_v)  { \
488                 float *_co = BLI_memarena_alloc(vert_coords_orig, sizeof(float[3])); \
489                 copy_v3_v3(_co, (_v)->co); \
490                 BLI_ghash_insert(vert_coords, _v, _co); \
491         } (void)0
492 #define VERT_ORIG_GET(_v)  \
493         (const float *)BLI_ghash_lookup_default(vert_coords, (_v), (_v)->co)
494
495
496         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
497                 if ((es->l = bm_edge_is_mixed_face_tag(es->e_old->l))) {
498                         /* do nothing */
499                 }
500                 else {
501                         es->l = es->e_old->l; /* must be a boundary */
502                 }
503
504
505                 /* run the separate arg */
506                 bmesh_edge_separate(bm, es->e_old, es->l, false);
507
508                 /* calc edge-split info */
509                 es->e_new = es->l->e;
510                 BM_edge_calc_face_tangent(es->e_new, es->l, es->no);
511
512                 if (es->e_new == es->e_old) { /* happens on boundary edges */
513                         /* take care here, we're creating this double edge which _must_ have its verts replaced later on */
514                         es->e_old = BM_edge_create(bm, es->e_new->v1, es->e_new->v2, es->e_new, BM_CREATE_NOP);
515                 }
516
517                 /* store index back to original in 'edge_info' */
518                 BM_elem_index_set(es->e_new, i);
519                 BM_elem_flag_enable(es->e_new, BM_ELEM_TAG);
520
521                 /* important to tag again here */
522                 BM_elem_flag_enable(es->e_new->v1, BM_ELEM_TAG);
523                 BM_elem_flag_enable(es->e_new->v2, BM_ELEM_TAG);
524
525
526                 /* initialize interpolation vars */
527                 /* this could go in its own loop,
528                  * only use the 'es->l->f' so we don't store loops for faces which have no mixed selection
529                  *
530                  * note: faces on the other side of the inset will be interpolated too since this is hard to
531                  * detect, just allow it even though it will cause some redundant interpolation */
532                 if (use_interpolate) {
533                         BMIter viter;
534                         BM_ITER_ELEM (v, &viter, es->l->e, BM_VERTS_OF_EDGE) {
535                                 BMIter fiter;
536                                 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
537                                         const int j = BM_elem_index_get(f);
538                                         if (iface_array[j] == NULL) {
539                                                 InterpFace *iface = BLI_memarena_alloc(interp_arena, sizeof(*iface));
540                                                 bm_interp_face_store(iface, bm, f, interp_arena);
541                                                 iface_array[j] = iface;
542                                         }
543                                 }
544                         }
545                 }
546                 /* done interpolation */
547         }
548
549         /* show edge normals for debugging */
550 #if 0
551         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
552                 float tvec[3];
553                 BMVert *v1, *v2;
554
555                 mid_v3_v3v3(tvec, es->e_new->v1->co, es->e_new->v2->co);
556
557                 v1 = BM_vert_create(bm, tvec, NULL, BM_CREATE_NOP);
558                 v2 = BM_vert_create(bm, tvec, NULL, BM_CREATE_NOP);
559                 madd_v3_v3fl(v2->co, es->no, 0.1f);
560                 BM_edge_create(bm, v1, v2, NULL, 0);
561         }
562 #endif
563
564         /* execute the split and position verts, it would be most obvious to loop over verts
565          * here but don't do this since we will be splitting them off (iterating stuff you modify is bad juju)
566          * instead loop over edges then their verts */
567         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
568                 for (j = 0; j < 2; j++) {
569                         v = (j == 0) ? es->e_new->v1 : es->e_new->v2;
570
571                         /* end confusing part - just pretend this is a typical loop on verts */
572
573                         /* only split of tagged verts - used by separated edges */
574
575                         /* comment the first part because we know this verts in a tagged face */
576                         if (/* v->e && */BM_elem_flag_test(v, BM_ELEM_TAG)) {
577                                 BMVert **vout;
578                                 int r_vout_len;
579                                 BMVert *v_glue = NULL;
580
581                                 /* disable touching twice, this _will_ happen if the flags not disabled */
582                                 BM_elem_flag_disable(v, BM_ELEM_TAG);
583
584                                 bmesh_vert_separate(bm, v, &vout, &r_vout_len, false);
585                                 v = NULL; /* don't use again */
586
587                                 /* in some cases the edge doesn't split off */
588                                 if (r_vout_len == 1) {
589                                         if (use_vert_coords_orig) {
590                                                 VERT_ORIG_STORE(vout[0]);
591                                         }
592                                         MEM_freeN(vout);
593                                         continue;
594                                 }
595
596                                 for (k = 0; k < r_vout_len; k++) {
597                                         BMVert *v_split = vout[k]; /* only to avoid vout[k] all over */
598
599                                         /* need to check if this vertex is from a */
600                                         int vert_edge_tag_tot = 0;
601                                         int vecpair[2];
602
603                                         if (use_vert_coords_orig) {
604                                                 VERT_ORIG_STORE(v_split);
605                                         }
606
607                                         /* find adjacent */
608                                         BM_ITER_ELEM (e, &iter, v_split, BM_EDGES_OF_VERT) {
609                                                 if (BM_elem_flag_test(e, BM_ELEM_TAG) &&
610                                                     e->l && BM_elem_flag_test(e->l->f, BM_ELEM_TAG))
611                                                 {
612                                                         if (vert_edge_tag_tot < 2) {
613                                                                 vecpair[vert_edge_tag_tot] = BM_elem_index_get(e);
614                                                                 BLI_assert(vecpair[vert_edge_tag_tot] != -1);
615                                                         }
616
617                                                         vert_edge_tag_tot++;
618                                                 }
619                                         }
620
621                                         if (vert_edge_tag_tot != 0) {
622                                                 float tvec[3];
623
624                                                 if (vert_edge_tag_tot >= 2) { /* 2 edge users - common case */
625                                                         /* now there are 2 cases to check for,
626                                                          *
627                                                          * if both edges use the same face OR both faces have the same normal,
628                                                          * ...then we can calculate an edge that fits nicely between the 2 edge normals.
629                                                          *
630                                                          * Otherwise use the shared edge OR the corner defined by these 2 face normals,
631                                                          * when both edges faces are adjacent this works best but even when this vertex
632                                                          * fans out faces it should work ok.
633                                                          */
634
635                                                         SplitEdgeInfo *e_info_a = &edge_info[vecpair[0]];
636                                                         SplitEdgeInfo *e_info_b = &edge_info[vecpair[1]];
637
638                                                         BMFace *f_a = e_info_a->l->f;
639                                                         BMFace *f_b = e_info_b->l->f;
640
641                                                         /* set to true when we're not in-between (e_info_a->no, e_info_b->no) exactly
642                                                          * in this case use a check the angle of the tvec when calculating shell thickness */
643                                                         bool is_mid = true;
644
645                                                         /* we use this as either the normal OR to find the right direction for the
646                                                          * cross product between both face normals */
647                                                         add_v3_v3v3(tvec, e_info_a->no, e_info_b->no);
648
649                                                         if (use_edge_rail == false) {
650                                                                 /* pass */
651                                                         }
652                                                         else if (f_a != f_b) {
653                                                                 /* these lookups are very quick */
654                                                                 BMLoop *l_other_a = BM_loop_other_vert_loop(e_info_a->l, v_split);
655                                                                 BMLoop *l_other_b = BM_loop_other_vert_loop(e_info_b->l, v_split);
656
657                                                                 if (l_other_a->v == l_other_b->v) {
658                                                                         /* both edges faces are adjacent, but we don't need to know the shared edge
659                                                                          * having both verts is enough. */
660                                                                         const float *co_other;
661
662                                                                         /* note that we can't use 'l_other_a->v' directly since it
663                                                                          * may be inset and give a feedback loop. */
664                                                                         if (use_vert_coords_orig) {
665                                                                                 co_other = VERT_ORIG_GET(l_other_a->v);
666                                                                         }
667                                                                         else {
668                                                                                 co_other = l_other_a->v->co;
669                                                                         }
670
671                                                                         sub_v3_v3v3(tvec, co_other, v_split->co);
672                                                                         is_mid = false;
673                                                                 }
674
675                                                                 /* distable gives odd results at times, see [#39288] */
676 #if 0
677                                                                 else if (compare_v3v3(f_a->no, f_b->no, 0.001f) == false) {
678                                                                         /* epsilon increased to fix [#32329] */
679
680                                                                         /* faces don't touch,
681                                                                          * just get cross product of their normals, its *good enough*
682                                                                          */
683                                                                         float tno[3];
684                                                                         cross_v3_v3v3(tno, f_a->no, f_b->no);
685                                                                         if (dot_v3v3(tvec, tno) < 0.0f) {
686                                                                                 negate_v3(tno);
687                                                                         }
688                                                                         copy_v3_v3(tvec, tno);
689                                                                         is_mid = false;
690                                                                 }
691 #endif
692                                                         }
693                                                         normalize_v3(tvec);
694
695                                                         /* scale by edge angle */
696                                                         if (use_even_offset) {
697                                                                 if (is_mid) {
698                                                                         mul_v3_fl(tvec, shell_v3v3_mid_normalized_to_dist(e_info_a->no,
699                                                                                                                           e_info_b->no));
700                                                                 }
701                                                                 else {
702                                                                         /* use the largest angle */
703                                                                         mul_v3_fl(tvec,
704                                                                                   shell_v3v3_normalized_to_dist(tvec,
705                                                                                                                 len_squared_v3v3(tvec, e_info_a->no) >
706                                                                                                                 len_squared_v3v3(tvec, e_info_b->no) ?
707                                                                                                                     e_info_a->no : e_info_b->no));
708                                                                 }
709                                                         }
710
711                                                         /* scale relative to edge lengths */
712                                                         if (use_relative_offset) {
713                                                                 mul_v3_fl(tvec, (edge_info[vecpair[0]].length + edge_info[vecpair[1]].length) / 2.0f);
714                                                         }
715                                                 }
716                                                 else if (vert_edge_tag_tot == 1) { /* 1 edge user - boundary vert, not so common */
717                                                         const float *e_no_a = edge_info[vecpair[0]].no;
718
719                                                         if (use_even_boundary) {
720
721                                                                 /* This case where only one edge attached to v_split
722                                                                  * is used - ei - the face to inset is on a boundary.
723                                                                  *
724                                                                  *                  We want the inset to align flush with the
725                                                                  *                  boundary edge, not the normal of the interior
726                                                                  *             <--- edge which would give an unsightly bump.
727                                                                  * --+-------------------------+---------------+--
728                                                                  *   |^v_other    ^e_other    /^v_split        |
729                                                                  *   |                       /                 |
730                                                                  *   |                      /                  |
731                                                                  *   |                     / <- tag split edge |
732                                                                  *   |                    /                    |
733                                                                  *   |                   /                     |
734                                                                  *   |                  /                      |
735                                                                  * --+-----------------+-----------------------+--
736                                                                  *   |                                         |
737                                                                  *   |                                         |
738                                                                  *
739                                                                  * note, the fact we are doing location comparisons on verts that are moved about
740                                                                  * doesn't matter because the direction will remain the same in this case.
741                                                                  */
742
743                                                                 BMEdge *e_other;
744                                                                 BMVert *v_other;
745                                                                 /* loop will always be either next of prev */
746                                                                 BMLoop *l = v_split->e->l;
747                                                                 if (l->prev->v == v_split) {
748                                                                         l = l->prev;
749                                                                 }
750                                                                 else if (l->next->v == v_split) {
751                                                                         l = l->next;
752                                                                 }
753                                                                 else if (l->v == v_split) {
754                                                                         /* pass */
755                                                                 }
756                                                                 else {
757                                                                         /* should never happen */
758                                                                         BLI_assert(0);
759                                                                 }
760
761                                                                 /* find the edge which is _not_ being split here */
762                                                                 if (!BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
763                                                                         e_other = l->e;
764                                                                 }
765                                                                 else if (!BM_elem_flag_test(l->prev->e, BM_ELEM_TAG)) {
766                                                                         e_other = l->prev->e;
767                                                                 }
768                                                                 else {
769                                                                         BLI_assert(0);
770                                                                         e_other = NULL;
771                                                                 }
772
773                                                                 v_other = BM_edge_other_vert(e_other, v_split);
774                                                                 sub_v3_v3v3(tvec, v_other->co, v_split->co);
775                                                                 normalize_v3(tvec);
776
777                                                                 if (use_even_offset) {
778                                                                         mul_v3_fl(tvec, shell_v3v3_normalized_to_dist(e_no_a, tvec));
779                                                                 }
780                                                         }
781                                                         else {
782                                                                 copy_v3_v3(tvec, e_no_a);
783                                                         }
784
785                                                         /* use_even_offset - doesn't apply here */
786
787                                                         /* scale relative to edge length */
788                                                         if (use_relative_offset) {
789                                                                 mul_v3_fl(tvec, edge_info[vecpair[0]].length);
790                                                         }
791                                                 }
792                                                 else {
793                                                         /* should never happen */
794                                                         BLI_assert(0);
795                                                         zero_v3(tvec);
796                                                 }
797
798                                                 /* apply the offset */
799                                                 madd_v3_v3fl(v_split->co, tvec, thickness);
800                                         }
801
802                                         /* this saves expensive/slow glue check for common cases */
803                                         if (r_vout_len > 2) {
804                                                 bool ok = true;
805                                                 /* last step, NULL this vertex if has a tagged face */
806                                                 BM_ITER_ELEM (f, &iter, v_split, BM_FACES_OF_VERT) {
807                                                         if (BM_elem_flag_test(f, BM_ELEM_TAG)) {
808                                                                 ok = false;
809                                                                 break;
810                                                         }
811                                                 }
812
813                                                 if (ok) {
814                                                         if (v_glue == NULL) {
815                                                                 v_glue = v_split;
816                                                         }
817                                                         else {
818                                                                 BM_vert_splice(bm, v_split, v_glue);
819                                                         }
820                                                 }
821                                         }
822                                         /* end glue */
823
824                                 }
825                                 MEM_freeN(vout);
826                         }
827                 }
828         }
829
830         if (use_vert_coords_orig) {
831                 BLI_memarena_free(vert_coords_orig);
832                 BLI_ghash_free(vert_coords, NULL, NULL);
833         }
834
835         if (use_interpolate) {
836                 for (i = 0; i < iface_array_len; i++) {
837                         if (iface_array[i]) {
838                                 InterpFace *iface = iface_array[i];
839                                 BM_face_interp_from_face_ex(bm, iface->f, iface->f, true,
840                                                             iface->blocks_l, iface->blocks_v, iface->cos_2d, iface->axis_mat);
841                         }
842                 }
843         }
844
845         /* create faces */
846         for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
847                 BMVert *varr[4] = {NULL};
848                 /* get the verts in the correct order */
849                 BM_edge_ordered_verts_ex(es->e_new, &varr[1], &varr[0], es->l);
850 #if 0
851                 if (varr[0] == es->e_new->v1) {
852                         varr[2] = es->e_old->v2;
853                         varr[3] = es->e_old->v1;
854                 }
855                 else {
856                         varr[2] = es->e_old->v1;
857                         varr[3] = es->e_old->v2;
858                 }
859                 j = 4;
860 #else
861                 /* slightly trickier check - since we can't assume the verts are split */
862                 j = 2; /* 2 edges are set */
863                 if (varr[0] == es->e_new->v1) {
864                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
865                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
866                 }
867                 else {
868                         if (es->e_old->v1 != es->e_new->v1) { varr[j++] = es->e_old->v1; }
869                         if (es->e_old->v2 != es->e_new->v2) { varr[j++] = es->e_old->v2; }
870                 }
871
872                 if (j == 2) {
873                         /* can't make face! */
874                         continue;
875                 }
876 #endif
877                 /* no need to check doubles, we KNOW there won't be any */
878                 /* yes - reverse face is correct in this case */
879                 f = BM_face_create_verts(bm, varr, j, es->l->f, BM_CREATE_NOP, true);
880                 BMO_elem_flag_enable(bm, f, ELE_NEW);
881
882                 /* copy for loop data, otherwise UV's and vcols are no good.
883                  * tiny speedup here we could be more clever and copy from known adjacent data
884                  * also - we could attempt to interpolate the loop data, this would be much slower but more useful too */
885 #if 0
886                 /* don't use this because face boundaries have no adjacent loops and won't be filled in.
887                  * instead copy from the opposite side with the code below */
888                 BM_face_copy_shared(bm, f, NULL, NULL);
889 #else
890                 {
891                         /* 2 inner loops on the edge between the new face and the original */
892                         BMLoop *l_a;
893                         BMLoop *l_b;
894                         BMLoop *l_a_other;
895                         BMLoop *l_b_other;
896
897                         l_a = BM_FACE_FIRST_LOOP(f);
898                         l_b = l_a->next;
899
900                         /* we know this side has a radial_next because of the order of created verts in the quad */
901                         l_a_other = BM_edge_other_loop(l_a->e, l_a);
902                         l_b_other = BM_edge_other_loop(l_a->e, l_b);
903                         BM_elem_attrs_copy(bm, bm, l_a_other, l_a);
904                         BM_elem_attrs_copy(bm, bm, l_b_other, l_b);
905
906                         /* step around to the opposite side of the quad - warning, this may have no other edges! */
907                         l_a = l_a->next->next;
908                         l_b = l_a->next;
909
910                         /* swap a<->b intentionally */
911                         if (use_interpolate) {
912                                 InterpFace *iface = iface_array[BM_elem_index_get(es->l->f)];
913                                 const int i_a = BM_elem_index_get(l_a_other);
914                                 const int i_b = BM_elem_index_get(l_b_other);
915                                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, iface->blocks_l[i_a], &l_b->head.data);
916                                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, iface->blocks_l[i_b], &l_a->head.data);
917                         }
918                         else {
919                                 BM_elem_attrs_copy(bm, bm, l_a_other, l_b);
920                                 BM_elem_attrs_copy(bm, bm, l_b_other, l_a);
921                         }
922                 }
923         }
924 #endif
925
926         if (use_interpolate) {
927                 for (i = 0; i < iface_array_len; i++) {
928                         if (iface_array[i]) {
929                                 bm_interp_face_free(iface_array[i], bm);
930                         }
931                 }
932
933                 BLI_memarena_free(interp_arena);
934                 MEM_freeN(iface_array);
935         }
936
937         /* we could flag new edges/verts too, is it useful? */
938         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, ELE_NEW);
939
940         /* cheap feature to add depth to the inset */
941         if (depth != 0.0f) {
942                 float (*varr_co)[3];
943                 BMOIter oiter;
944
945                 /* we need to re-calculate tagged normals, but for this purpose we can copy tagged verts from the
946                  * faces they inset from,  */
947                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
948                         zero_v3(es->e_new->v1->no);
949                         zero_v3(es->e_new->v2->no);
950                 }
951                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
952                         const float *no = es->l->f->no;
953                         add_v3_v3(es->e_new->v1->no, no);
954                         add_v3_v3(es->e_new->v2->no, no);
955                 }
956                 for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
957                         /* annoying, avoid normalizing twice */
958                         if (len_squared_v3(es->e_new->v1->no) != 1.0f) {
959                                 normalize_v3(es->e_new->v1->no);
960                         }
961                         if (len_squared_v3(es->e_new->v2->no) != 1.0f) {
962                                 normalize_v3(es->e_new->v2->no);
963                         }
964                 }
965                 /* done correcting edge verts normals */
966
967                 /* untag verts */
968                 BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
969
970                 /* tag face verts */
971                 BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
972                         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
973                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
974                         }
975                 }
976
977                 /* do in 2 passes so moving the verts doesn't feed back into face angle checks
978                  * which BM_vert_calc_shell_factor uses. */
979
980                 /* over allocate */
981                 varr_co = MEM_callocN(sizeof(*varr_co) * bm->totvert, __func__);
982
983                 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
984                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
985                                 const float fac = (depth *
986                                                    (use_relative_offset ? bm_edge_info_average_length(v, edge_info) : 1.0f) *
987                                                    (use_even_boundary   ? BM_vert_calc_shell_factor(v) : 1.0f));
988                                 madd_v3_v3v3fl(varr_co[i], v->co, v->no, fac);
989                         }
990                 }
991
992                 BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
993                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
994                                 copy_v3_v3(v->co, varr_co[i]);
995                         }
996                 }
997                 MEM_freeN(varr_co);
998         }
999
1000         MEM_freeN(edge_info);
1001 }