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