Memory: Fix guarded aligned malloc with small alignment
[blender.git] / source / blender / bmesh / operators / bmo_inset.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bmesh
19  *
20  * Inset face regions.
21  * Inset individual faces.
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_math.h"
27 #include "BLI_alloca.h"
28 #include "BLI_memarena.h"
29 #include "BKE_customdata.h"
30
31 #include "bmesh.h"
32
33 #include "intern/bmesh_operators_private.h" /* own include */
34
35 /* Merge loop-data that diverges, see: T41445 */
36 #define USE_LOOP_CUSTOMDATA_MERGE
37
38 #define ELE_NEW 1
39
40 /* -------------------------------------------------------------------- */
41 /* Generic Interp Face (use for both types of inset) */
42
43 /**
44  * Interpolation, this is more complex for regions since we're not creating new faces
45  * and throwing away old ones, so instead, store face data needed for interpolation.
46  *
47  * \note This uses CustomData functions in quite a low-level way which should be
48  * avoided, but in this case its hard to do without storing a duplicate mesh. */
49
50 /* just enough of a face to store interpolation data we can use once the inset is done */
51 typedef struct InterpFace {
52   BMFace *f;
53   void **blocks_l;
54   void **blocks_v;
55   float (*cos_2d)[2];
56   float axis_mat[3][3];
57 } InterpFace;
58
59 /* basically a clone of #BM_vert_interp_from_face */
60 static void bm_interp_face_store(InterpFace *iface, BMesh *bm, BMFace *f, MemArena *interp_arena)
61 {
62   BMLoop *l_iter, *l_first;
63   void **blocks_l = iface->blocks_l = BLI_memarena_alloc(interp_arena,
64                                                          sizeof(*iface->blocks_l) * f->len);
65   void **blocks_v = iface->blocks_v = BLI_memarena_alloc(interp_arena,
66                                                          sizeof(*iface->blocks_v) * f->len);
67   float(*cos_2d)[2] = iface->cos_2d = BLI_memarena_alloc(interp_arena,
68                                                          sizeof(*iface->cos_2d) * f->len);
69   void *axis_mat = iface->axis_mat;
70   int i;
71
72   BLI_assert(BM_face_is_normal_valid(f));
73
74   axis_dominant_v3_to_m3(axis_mat, f->no);
75
76   iface->f = f;
77
78   i = 0;
79   l_iter = l_first = BM_FACE_FIRST_LOOP(f);
80   do {
81     mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
82     blocks_l[i] = NULL;
83     CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_iter->head.data, &blocks_l[i]);
84     /* if we were not modifying the loops later we would do... */
85     // blocks[i] = l_iter->head.data;
86
87     blocks_v[i] = NULL;
88     CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, l_iter->v->head.data, &blocks_v[i]);
89
90     /* use later for index lookups */
91     BM_elem_index_set(l_iter, i); /* set_dirty */
92   } while ((void)i++, (l_iter = l_iter->next) != l_first);
93   bm->elem_index_dirty |= BM_LOOP;
94 }
95 static void bm_interp_face_free(InterpFace *iface, BMesh *bm)
96 {
97   void **blocks_l = iface->blocks_l;
98   void **blocks_v = iface->blocks_v;
99   int i;
100
101   for (i = 0; i < iface->f->len; i++) {
102     CustomData_bmesh_free_block(&bm->ldata, &blocks_l[i]);
103     CustomData_bmesh_free_block(&bm->vdata, &blocks_v[i]);
104   }
105 }
106
107 #ifdef USE_LOOP_CUSTOMDATA_MERGE
108 /**
109  * This function merges loop customdata (UV's)
110  * where interpolating the values across the face causes values to diverge.
111  */
112 static void bm_loop_customdata_merge(BMesh *bm,
113                                      BMEdge *e_connect,
114                                      BMLoop *l_a_outer,
115                                      BMLoop *l_b_outer,
116                                      BMLoop *l_a_inner,
117                                      BMLoop *l_b_inner)
118 {
119   /**
120    * Check for diverged values at the vert shared by
121    * \a l_a_inner & \a l_b_inner.
122    *
123    * <pre>
124    *  -----------------------+
125    *           l_a_outer--> /|<--l_b_outer
126    *                       / |
127    *      (face a)        /  |
128    *                     / <--e_connect
129    *                    /    |
130    * e_a  l_a_inner--> / <--l_b_inner
131    * -----------------+      |
132    *                 /|      |
133    * l_a/b_inner_inset| (face b)
134    *               /  |      |
135    *              /   |e_b   |
136    *  (inset face(s)) |      |
137    *            /     |      |
138    * </pre>
139    */
140
141   const bool is_flip = (l_a_inner->next == l_a_outer);
142   BMLoop *l_a_inner_inset, *l_b_inner_inset;
143   BMEdge *e_a, *e_b;
144   int layer_n;
145
146   /* paranoid sanity checks */
147   BLI_assert(l_a_outer->v == l_b_outer->v);
148   BLI_assert(l_a_inner->v == l_b_inner->v);
149
150   BLI_assert(l_b_inner->f != l_a_inner->f);
151
152   BLI_assert(l_a_outer->f == l_a_inner->f);
153   BLI_assert(l_b_outer->f == l_b_inner->f);
154
155   (void)e_connect;
156   BLI_assert(BM_edge_in_face(e_connect, l_a_inner->f));
157   BLI_assert(BM_edge_in_face(e_connect, l_b_inner->f));
158
159   if (is_flip) {
160     e_a = l_a_inner->prev->e;
161     e_b = l_b_inner->e;
162   }
163   else {
164     e_a = l_a_inner->e;
165     e_b = l_b_inner->prev->e;
166   }
167
168   l_a_inner_inset = BM_edge_other_loop(e_a, l_a_inner);
169   l_b_inner_inset = BM_edge_other_loop(e_b, l_b_inner);
170   BLI_assert(l_a_inner_inset->v == l_b_inner_inset->v);
171
172   /* check if there is no chance of diversion */
173   if (l_a_inner_inset->f == l_b_inner_inset->f) {
174     return;
175   }
176
177   for (layer_n = 0; layer_n < bm->ldata.totlayer; layer_n++) {
178     const int type = bm->ldata.layers[layer_n].type;
179     const int offset = bm->ldata.layers[layer_n].offset;
180     if (!CustomData_layer_has_math(&bm->ldata, layer_n)) {
181       continue;
182     }
183
184     /* check we begin with merged data */
185     if ((CustomData_data_equals(type,
186                                 BM_ELEM_CD_GET_VOID_P(l_a_outer, offset),
187                                 BM_ELEM_CD_GET_VOID_P(l_b_outer, offset)) == true)
188
189     /* Epsilon for comparing UV's is too big, gives noticeable problems. */
190 #  if 0
191         &&
192         /* check if the data ends up diverged */
193         (CustomData_data_equals(type,
194                                 BM_ELEM_CD_GET_VOID_P(l_a_inner, offset),
195                                 BM_ELEM_CD_GET_VOID_P(l_b_inner, offset)) == false)
196 #  endif
197     ) {
198       /* no need to allocate a temp block:
199        * a = (a + b);
200        * a *= 0.5f;
201        * b = a;
202        */
203       const void *data_src;
204
205       CustomData_data_mix_value(type,
206                                 BM_ELEM_CD_GET_VOID_P(l_a_inner_inset, offset),
207                                 BM_ELEM_CD_GET_VOID_P(l_b_inner_inset, offset),
208                                 CDT_MIX_MIX,
209                                 0.5f);
210       CustomData_data_copy_value(type,
211                                  BM_ELEM_CD_GET_VOID_P(l_a_inner_inset, offset),
212                                  BM_ELEM_CD_GET_VOID_P(l_b_inner_inset, offset));
213
214       /* use this as a reference (could be 'l_b_inner_inset' too) */
215       data_src = BM_ELEM_CD_GET_VOID_P(l_a_inner_inset, offset);
216
217       /* check if the 2 faces share an edge */
218       if (is_flip ? (l_b_inner_inset->e == l_a_inner_inset->prev->e) :
219                     (l_a_inner_inset->e == l_b_inner_inset->prev->e)) {
220         /* simple case, we have all loops already */
221       }
222       else {
223         /* compare with (l_a_inner / l_b_inner) and assign the blended value if they match */
224         BMIter iter;
225         BMLoop *l_iter;
226         const void *data_cmp_a = BM_ELEM_CD_GET_VOID_P(l_b_inner, offset);
227         const void *data_cmp_b = BM_ELEM_CD_GET_VOID_P(l_a_inner, offset);
228         BM_ITER_ELEM (l_iter, &iter, l_a_inner_inset->v, BM_LOOPS_OF_VERT) {
229           if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
230             if (!ELEM(l_iter, l_a_inner, l_b_inner, l_a_inner_inset, l_b_inner_inset)) {
231               void *data_dst = BM_ELEM_CD_GET_VOID_P(l_iter, offset);
232
233               if (CustomData_data_equals(type, data_dst, data_cmp_a) ||
234                   CustomData_data_equals(type, data_dst, data_cmp_b)) {
235                 CustomData_data_copy_value(type, data_src, data_dst);
236               }
237             }
238           }
239         }
240       }
241
242       CustomData_data_copy_value(type, data_src, BM_ELEM_CD_GET_VOID_P(l_b_inner, offset));
243       CustomData_data_copy_value(type, data_src, BM_ELEM_CD_GET_VOID_P(l_a_inner, offset));
244     }
245   }
246 }
247 #endif /* USE_LOOP_CUSTOMDATA_MERGE */
248
249 /* -------------------------------------------------------------------- */
250 /* Inset Individual */
251
252 static void bmo_face_inset_individual(BMesh *bm,
253                                       BMFace *f,
254                                       MemArena *interp_arena,
255                                       const float thickness,
256                                       const float depth,
257                                       const bool use_even_offset,
258                                       const bool use_relative_offset,
259                                       const bool use_interpolate)
260 {
261   InterpFace *iface = NULL;
262
263   /* stores verts split away from the face (aligned with face verts) */
264   BMVert **verts = BLI_array_alloca(verts, f->len);
265   /* store edge normals (aligned with face-loop-edges) */
266   float(*edge_nors)[3] = BLI_array_alloca(edge_nors, f->len);
267   float(*coords)[3] = BLI_array_alloca(coords, f->len);
268
269   BMLoop *l_iter, *l_first;
270   BMLoop *l_other;
271   uint i;
272   float e_length_prev;
273
274   l_first = BM_FACE_FIRST_LOOP(f);
275
276   /* split off all loops */
277   l_iter = l_first;
278   i = 0;
279   do {
280     BMVert *v_other = l_iter->v;
281     BMVert *v_sep = BM_face_loop_separate(bm, l_iter);
282     if (v_sep == v_other) {
283       v_other = BM_vert_create(bm, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
284     }
285     verts[i] = v_other;
286
287     /* unrelated to splitting, but calc here */
288     BM_edge_calc_face_tangent(l_iter->e, l_iter, edge_nors[i]);
289   } while ((void)i++, ((l_iter = l_iter->next) != l_first));
290
291   /* build rim faces */
292   l_iter = l_first;
293   i = 0;
294   do {
295     BMFace *f_new_outer;
296     BMVert *v_other = verts[i];
297     BMVert *v_other_next = verts[(i + 1) % f->len];
298
299     BMEdge *e_other = BM_edge_create(bm, v_other, v_other_next, l_iter->e, BM_CREATE_NO_DOUBLE);
300     (void)e_other;
301
302     f_new_outer = BM_face_create_quad_tri(
303         bm, v_other, v_other_next, l_iter->next->v, l_iter->v, f, BM_CREATE_NOP);
304     BMO_face_flag_enable(bm, f_new_outer, ELE_NEW);
305
306     /* copy loop data */
307     l_other = l_iter->radial_next;
308     BM_elem_attrs_copy(bm, bm, l_iter->next, l_other->prev);
309     BM_elem_attrs_copy(bm, bm, l_iter, l_other->next->next);
310
311     if (use_interpolate == false) {
312       BM_elem_attrs_copy(bm, bm, l_iter->next, l_other);
313       BM_elem_attrs_copy(bm, bm, l_iter, l_other->next);
314     }
315   } while ((void)i++, ((l_iter = l_iter->next) != l_first));
316
317   /* hold interpolation values */
318   if (use_interpolate) {
319     iface = BLI_memarena_alloc(interp_arena, sizeof(*iface));
320     bm_interp_face_store(iface, bm, f, interp_arena);
321   }
322
323   /* Calculate translation vector for new */
324   l_iter = l_first;
325   i = 0;
326
327   if (depth != 0.0f) {
328     e_length_prev = BM_edge_calc_length(l_iter->prev->e);
329   }
330
331   do {
332     const float *eno_prev = edge_nors[(i ? i : f->len) - 1];
333     const float *eno_next = edge_nors[i];
334     float tvec[3];
335     float v_new_co[3];
336
337     add_v3_v3v3(tvec, eno_prev, eno_next);
338     normalize_v3(tvec);
339
340     copy_v3_v3(v_new_co, l_iter->v->co);
341
342     if (use_even_offset) {
343       mul_v3_fl(tvec, shell_v3v3_mid_normalized_to_dist(eno_prev, eno_next));
344     }
345
346     /* Modify vertices and their normals */
347     if (use_relative_offset) {
348       mul_v3_fl(tvec,
349                 (BM_edge_calc_length(l_iter->e) + BM_edge_calc_length(l_iter->prev->e)) / 2.0f);
350     }
351
352     madd_v3_v3fl(v_new_co, tvec, thickness);
353
354     /* Set normal, add depth and write new vertex position*/
355     copy_v3_v3(l_iter->v->no, f->no);
356
357     if (depth != 0.0f) {
358       const float e_length = BM_edge_calc_length(l_iter->e);
359       const float fac = depth * (use_relative_offset ? ((e_length_prev + e_length) * 0.5f) : 1.0f);
360       e_length_prev = e_length;
361
362       madd_v3_v3fl(v_new_co, f->no, fac);
363     }
364
365     copy_v3_v3(coords[i], v_new_co);
366   } while ((void)i++, ((l_iter = l_iter->next) != l_first));
367
368   /* update the coords */
369   l_iter = l_first;
370   i = 0;
371   do {
372     copy_v3_v3(l_iter->v->co, coords[i]);
373   } while ((void)i++, ((l_iter = l_iter->next) != l_first));
374
375   if (use_interpolate) {
376     BM_face_interp_from_face_ex(bm,
377                                 iface->f,
378                                 iface->f,
379                                 true,
380                                 (const void **)iface->blocks_l,
381                                 (const void **)iface->blocks_v,
382                                 iface->cos_2d,
383                                 iface->axis_mat);
384
385     /* build rim faces */
386     l_iter = l_first;
387     do {
388       /* copy loop data */
389       l_other = l_iter->radial_next;
390
391       BM_elem_attrs_copy(bm, bm, l_iter->next, l_other);
392       BM_elem_attrs_copy(bm, bm, l_iter, l_other->next);
393     } while ((l_iter = l_iter->next) != l_first);
394
395     bm_interp_face_free(iface, bm);
396   }
397 }
398
399 /**
400  * Individual Face Inset.
401  * Find all tagged faces (f), duplicate edges around faces, inset verts of
402  * created edges, create new faces between old and new edges, fill face
403  * between connected new edges, kill old face (f).
404  */
405 void bmo_inset_individual_exec(BMesh *bm, BMOperator *op)
406 {
407   BMFace *f;
408
409   BMOIter oiter;
410   MemArena *interp_arena = NULL;
411
412   const float thickness = BMO_slot_float_get(op->slots_in, "thickness");
413   const float depth = BMO_slot_float_get(op->slots_in, "depth");
414   const bool use_even_offset = BMO_slot_bool_get(op->slots_in, "use_even_offset");
415   const bool use_relative_offset = BMO_slot_bool_get(op->slots_in, "use_relative_offset");
416   const bool use_interpolate = BMO_slot_bool_get(op->slots_in, "use_interpolate");
417
418   /* Only tag faces in slot */
419   BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
420
421   BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
422
423   if (use_interpolate) {
424     interp_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
425   }
426
427   BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
428     bmo_face_inset_individual(bm,
429                               f,
430                               interp_arena,
431                               thickness,
432                               depth,
433                               use_even_offset,
434                               use_relative_offset,
435                               use_interpolate);
436
437     if (use_interpolate) {
438       BLI_memarena_clear(interp_arena);
439     }
440   }
441
442   /* we could flag new edges/verts too, is it useful? */
443   BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, ELE_NEW);
444
445   if (use_interpolate) {
446     BLI_memarena_free(interp_arena);
447   }
448 }
449
450 /* -------------------------------------------------------------------- */
451 /* Inset Region */
452
453 typedef struct SplitEdgeInfo {
454   float no[3];
455   float length;
456   BMEdge *e_old;
457   BMEdge *e_new;
458   BMLoop *l;
459 } SplitEdgeInfo;
460
461 /**
462  * return the tag loop where there is...
463  * - only 1 tagged face attached to this edge.
464  * - 1 or more untagged faces.
465  *
466  * \note this function looks to be expensive
467  * but in most cases it will only do 2 iterations.
468  */
469 static BMLoop *bm_edge_is_mixed_face_tag(BMLoop *l)
470 {
471   if (LIKELY(l != NULL)) {
472     int tot_tag = 0;
473     int tot_untag = 0;
474     BMLoop *l_iter;
475     BMLoop *l_tag = NULL;
476     l_iter = l;
477     do {
478       if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
479         /* more than one tagged face - bail out early! */
480         if (tot_tag == 1) {
481           return NULL;
482         }
483         l_tag = l_iter;
484         tot_tag++;
485       }
486       else {
487         tot_untag++;
488       }
489
490     } while ((l_iter = l_iter->radial_next) != l);
491
492     return ((tot_tag == 1) && (tot_untag >= 1)) ? l_tag : NULL;
493   }
494   else {
495     return NULL;
496   }
497 }
498
499 static float bm_edge_info_average_length(BMVert *v, SplitEdgeInfo *edge_info)
500 {
501   BMIter iter;
502   BMEdge *e;
503
504   float len = 0.0f;
505   int tot = 0;
506
507   BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
508     const int i = BM_elem_index_get(e);
509     if (i != -1) {
510       len += edge_info[i].length;
511       tot++;
512     }
513   }
514
515   BLI_assert(tot != 0);
516   return len / (float)tot;
517 }
518
519 /**
520  * implementation is as follows...
521  *
522  * - set all faces as tagged/untagged based on selection.
523  * - find all edges that have 1 tagged, 1 untagged face.
524  * - separate these edges and tag vertices, set their index to point to the original edge.
525  * - build faces between old/new edges.
526  * - inset the new edges into their faces.
527  */
528
529 void bmo_inset_region_exec(BMesh *bm, BMOperator *op)
530 {
531   const bool use_outset = BMO_slot_bool_get(op->slots_in, "use_outset");
532   const bool use_boundary = BMO_slot_bool_get(op->slots_in, "use_boundary") &&
533                             (use_outset == false);
534   const bool use_even_offset = BMO_slot_bool_get(op->slots_in, "use_even_offset");
535   const bool use_even_boundary = use_even_offset; /* could make own option */
536   const bool use_relative_offset = BMO_slot_bool_get(op->slots_in, "use_relative_offset");
537   const bool use_edge_rail = BMO_slot_bool_get(op->slots_in, "use_edge_rail");
538   const bool use_interpolate = BMO_slot_bool_get(op->slots_in, "use_interpolate");
539   const float thickness = BMO_slot_float_get(op->slots_in, "thickness");
540   const float depth = BMO_slot_float_get(op->slots_in, "depth");
541 #ifdef USE_LOOP_CUSTOMDATA_MERGE
542   const bool has_math_ldata = (use_interpolate && CustomData_has_math(&bm->ldata));
543 #endif
544
545   int edge_info_len = 0;
546
547   BMIter iter;
548   SplitEdgeInfo *edge_info;
549   SplitEdgeInfo *es;
550
551   /* Interpolation Vars */
552   /* an array aligned with faces but only fill items which are used. */
553   InterpFace **iface_array = NULL;
554   int iface_array_len;
555   MemArena *interp_arena = NULL;
556
557   /* BMVert original location storage */
558   const bool use_vert_coords_orig = use_edge_rail;
559   MemArena *vert_coords_orig = NULL;
560   GHash *vert_coords = NULL;
561
562   BMVert *v;
563   BMEdge *e;
564   BMFace *f;
565   int i, k;
566
567   if (use_interpolate) {
568     interp_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
569     /* warning, we could be more clever here and not over alloc */
570     iface_array = MEM_callocN(sizeof(*iface_array) * bm->totface, __func__);
571     iface_array_len = bm->totface;
572   }
573
574   if (use_outset == false) {
575     BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
576     BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
577   }
578   else {
579     BM_mesh_elem_hflag_enable_all(bm, BM_FACE, BM_ELEM_TAG, false);
580     BMO_slot_buffer_hflag_disable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
581     BMO_slot_buffer_hflag_disable(bm, op->slots_in, "faces_exclude", BM_FACE, BM_ELEM_TAG, false);
582   }
583
584   /* first count all inset edges we will split */
585   /* fill in array and initialize tagging */
586   BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
587     if (
588         /* tag if boundary is enabled */
589         (use_boundary && BM_edge_is_boundary(e) && BM_elem_flag_test(e->l->f, BM_ELEM_TAG)) ||
590
591         /* tag if edge is an interior edge inbetween a tagged and untagged face */
592         (bm_edge_is_mixed_face_tag(e->l))) {
593       /* tag */
594       BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
595       BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
596       BM_elem_flag_enable(e, BM_ELEM_TAG);
597
598       BM_elem_index_set(e, edge_info_len); /* set_dirty! */
599       edge_info_len++;
600     }
601     else {
602       BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
603       BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
604       BM_elem_flag_disable(e, BM_ELEM_TAG);
605
606       BM_elem_index_set(e, -1); /* set_dirty! */
607     }
608   }
609   bm->elem_index_dirty |= BM_EDGE;
610
611   edge_info = MEM_mallocN(edge_info_len * sizeof(SplitEdgeInfo), __func__);
612
613   /* fill in array and initialize tagging */
614   es = edge_info;
615   BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
616     i = BM_elem_index_get(e);
617     if (i != -1) {
618       /* calc edge-split info */
619       es->length = BM_edge_calc_length(e);
620       es->e_old = e;
621       es++;
622       /* initialize no and e_new after */
623     }
624   }
625
626   if (use_vert_coords_orig) {
627     vert_coords_orig = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
628     vert_coords = BLI_ghash_ptr_new(__func__);
629   }
630
631   /* util macros */
632 #define VERT_ORIG_STORE(_v) \
633   { \
634     float *_co = BLI_memarena_alloc(vert_coords_orig, sizeof(float[3])); \
635     copy_v3_v3(_co, (_v)->co); \
636     BLI_ghash_insert(vert_coords, _v, _co); \
637   } \
638   (void)0
639 #define VERT_ORIG_GET(_v) (const float *)BLI_ghash_lookup_default(vert_coords, (_v), (_v)->co)
640   /* memory for the coords isn't given back to the arena,
641    * acceptable in this case since it runs a fixed number of times. */
642 #define VERT_ORIG_REMOVE(_v) BLI_ghash_remove(vert_coords, (_v), NULL, NULL)
643
644   for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
645     if ((es->l = bm_edge_is_mixed_face_tag(es->e_old->l))) {
646       /* do nothing */
647     }
648     else {
649       es->l = es->e_old->l; /* must be a boundary */
650     }
651
652     /* run the separate arg */
653     if (!BM_edge_is_boundary(es->e_old)) {
654       bmesh_kernel_edge_separate(bm, es->e_old, es->l, false);
655     }
656
657     /* calc edge-split info */
658     es->e_new = es->l->e;
659     BM_edge_calc_face_tangent(es->e_new, es->l, es->no);
660
661     if (es->e_new == es->e_old) { /* happens on boundary edges */
662       /* Take care here, we're creating this double edge which _must_
663        * have its verts replaced later on. */
664       es->e_old = BM_edge_create(bm, es->e_new->v1, es->e_new->v2, es->e_new, BM_CREATE_NOP);
665     }
666
667     /* store index back to original in 'edge_info' */
668     BM_elem_index_set(es->e_new, i);
669     BM_elem_flag_enable(es->e_new, BM_ELEM_TAG);
670
671     /* important to tag again here */
672     BM_elem_flag_enable(es->e_new->v1, BM_ELEM_TAG);
673     BM_elem_flag_enable(es->e_new->v2, BM_ELEM_TAG);
674
675     /* initialize interpolation vars */
676     /* this could go in its own loop,
677      * only use the 'es->l->f' so we don't store loops for faces which have no mixed selection
678      *
679      * note: faces on the other side of the inset will be interpolated too since this is hard to
680      * detect, just allow it even though it will cause some redundant interpolation */
681     if (use_interpolate) {
682       BMIter viter;
683       BM_ITER_ELEM (v, &viter, es->l->e, BM_VERTS_OF_EDGE) {
684         BMIter fiter;
685         BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
686           const int j = BM_elem_index_get(f);
687           if (iface_array[j] == NULL) {
688             InterpFace *iface = BLI_memarena_alloc(interp_arena, sizeof(*iface));
689             bm_interp_face_store(iface, bm, f, interp_arena);
690             iface_array[j] = iface;
691           }
692         }
693       }
694     }
695     /* done interpolation */
696   }
697
698   /* show edge normals for debugging */
699 #if 0
700   for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
701     float tvec[3];
702     BMVert *v1, *v2;
703
704     mid_v3_v3v3(tvec, es->e_new->v1->co, es->e_new->v2->co);
705
706     v1 = BM_vert_create(bm, tvec, NULL, BM_CREATE_NOP);
707     v2 = BM_vert_create(bm, tvec, NULL, BM_CREATE_NOP);
708     madd_v3_v3fl(v2->co, es->no, 0.1f);
709     BM_edge_create(bm, v1, v2, NULL, 0);
710   }
711 #endif
712
713   /* Execute the split and position verts, it would be most obvious to loop
714    * over verts here but don't do this since we will be splitting them off
715    * (iterating stuff you modify is bad juju)
716    * instead loop over edges then their verts. */
717   for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
718     for (int j = 0; j < 2; j++) {
719       v = (j == 0) ? es->e_new->v1 : es->e_new->v2;
720
721       /* end confusing part - just pretend this is a typical loop on verts */
722
723       /* only split of tagged verts - used by separated edges */
724
725       /* comment the first part because we know this verts in a tagged face */
726       if (/* v->e && */ BM_elem_flag_test(v, BM_ELEM_TAG)) {
727         BMVert **vout;
728         int r_vout_len;
729         BMVert *v_glue = NULL;
730
731         /* disable touching twice, this _will_ happen if the flags not disabled */
732         BM_elem_flag_disable(v, BM_ELEM_TAG);
733
734         bmesh_kernel_vert_separate(bm, v, &vout, &r_vout_len, false);
735         v = NULL; /* don't use again */
736
737         /* in some cases the edge doesn't split off */
738         if (r_vout_len == 1) {
739           if (use_vert_coords_orig) {
740             VERT_ORIG_STORE(vout[0]);
741           }
742           MEM_freeN(vout);
743           continue;
744         }
745
746         for (k = 0; k < r_vout_len; k++) {
747           BMVert *v_split = vout[k]; /* only to avoid vout[k] all over */
748
749           /* need to check if this vertex is from a */
750           int vert_edge_tag_tot = 0;
751           int vecpair[2];
752
753           if (use_vert_coords_orig) {
754             VERT_ORIG_STORE(v_split);
755           }
756
757           /* find adjacent */
758           BM_ITER_ELEM (e, &iter, v_split, BM_EDGES_OF_VERT) {
759             if (BM_elem_flag_test(e, BM_ELEM_TAG) && e->l &&
760                 BM_elem_flag_test(e->l->f, BM_ELEM_TAG)) {
761               if (vert_edge_tag_tot < 2) {
762                 vecpair[vert_edge_tag_tot] = BM_elem_index_get(e);
763                 BLI_assert(vecpair[vert_edge_tag_tot] != -1);
764               }
765
766               vert_edge_tag_tot++;
767             }
768           }
769
770           if (vert_edge_tag_tot != 0) {
771             float tvec[3];
772
773             if (vert_edge_tag_tot >= 2) { /* 2 edge users - common case */
774               /* now there are 2 cases to check for,
775                *
776                * if both edges use the same face OR both faces have the same normal,
777                * ...then we can calculate an edge that fits nicely between the 2 edge normals.
778                *
779                * Otherwise use the shared edge OR the corner defined by these 2 face normals,
780                * when both edges faces are adjacent this works best but even when this vertex
781                * fans out faces it should work ok.
782                */
783
784               SplitEdgeInfo *e_info_a = &edge_info[vecpair[0]];
785               SplitEdgeInfo *e_info_b = &edge_info[vecpair[1]];
786
787               BMFace *f_a = e_info_a->l->f;
788               BMFace *f_b = e_info_b->l->f;
789
790               /* set to true when we're not in-between (e_info_a->no, e_info_b->no) exactly
791                * in this case use a check the angle of the tvec when calculating shell thickness */
792               bool is_mid = true;
793
794               /* we use this as either the normal OR to find the right direction for the
795                * cross product between both face normals */
796               add_v3_v3v3(tvec, e_info_a->no, e_info_b->no);
797
798               if (use_edge_rail == false) {
799                 /* pass */
800               }
801               else if (f_a != f_b) {
802                 /* these lookups are very quick */
803                 BMLoop *l_other_a = BM_loop_other_vert_loop(e_info_a->l, v_split);
804                 BMLoop *l_other_b = BM_loop_other_vert_loop(e_info_b->l, v_split);
805
806                 if (l_other_a->v == l_other_b->v) {
807                   /* both edges faces are adjacent, but we don't need to know the shared edge
808                    * having both verts is enough. */
809                   const float *co_other;
810
811                   /* note that we can't use 'l_other_a->v' directly since it
812                    * may be inset and give a feedback loop. */
813                   if (use_vert_coords_orig) {
814                     co_other = VERT_ORIG_GET(l_other_a->v);
815                   }
816                   else {
817                     co_other = l_other_a->v->co;
818                   }
819
820                   sub_v3_v3v3(tvec, co_other, v_split->co);
821                   is_mid = false;
822                 }
823
824                 /* distable gives odd results at times, see [#39288] */
825 #if 0
826                 else if (compare_v3v3(f_a->no, f_b->no, 0.001f) == false) {
827                   /* epsilon increased to fix [#32329] */
828
829                   /* faces don't touch,
830                    * just get cross product of their normals, its *good enough*
831                    */
832                   float tno[3];
833                   cross_v3_v3v3(tno, f_a->no, f_b->no);
834                   if (dot_v3v3(tvec, tno) < 0.0f) {
835                     negate_v3(tno);
836                   }
837                   copy_v3_v3(tvec, tno);
838                   is_mid = false;
839                 }
840 #endif
841               }
842               normalize_v3(tvec);
843
844               /* scale by edge angle */
845               if (use_even_offset) {
846                 if (is_mid) {
847                   mul_v3_fl(tvec, shell_v3v3_mid_normalized_to_dist(e_info_a->no, e_info_b->no));
848                 }
849                 else {
850                   /* use the largest angle */
851                   mul_v3_fl(
852                       tvec,
853                       shell_v3v3_normalized_to_dist(tvec,
854                                                     len_squared_v3v3(tvec, e_info_a->no) >
855                                                             len_squared_v3v3(tvec, e_info_b->no) ?
856                                                         e_info_a->no :
857                                                         e_info_b->no));
858                 }
859               }
860
861               /* scale relative to edge lengths */
862               if (use_relative_offset) {
863                 mul_v3_fl(tvec,
864                           (edge_info[vecpair[0]].length + edge_info[vecpair[1]].length) / 2.0f);
865               }
866             }
867             else if (vert_edge_tag_tot == 1) { /* 1 edge user - boundary vert, not so common */
868               const float *e_no_a = edge_info[vecpair[0]].no;
869
870               if (use_even_boundary) {
871
872                 /* This case where only one edge attached to v_split
873                  * is used - ei - the face to inset is on a boundary.
874                  *
875                  *                  We want the inset to align flush with the
876                  *                  boundary edge, not the normal of the interior
877                  *             <--- edge which would give an unsightly bump.
878                  * --+-------------------------+---------------+--
879                  *   |^v_other    ^e_other    /^v_split        |
880                  *   |                       /                 |
881                  *   |                      /                  |
882                  *   |                     / <- tag split edge |
883                  *   |                    /                    |
884                  *   |                   /                     |
885                  *   |                  /                      |
886                  * --+-----------------+-----------------------+--
887                  *   |                                         |
888                  *   |                                         |
889                  *
890                  * note, the fact we are doing location comparisons on verts that are moved about
891                  * doesn't matter because the direction will remain the same in this case.
892                  */
893
894                 BMEdge *e_other;
895                 BMVert *v_other;
896                 /* loop will always be either next of prev */
897                 BMLoop *l = v_split->e->l;
898                 if (l->prev->v == v_split) {
899                   l = l->prev;
900                 }
901                 else if (l->next->v == v_split) {
902                   l = l->next;
903                 }
904                 else if (l->v == v_split) {
905                   /* pass */
906                 }
907                 else {
908                   /* should never happen */
909                   BLI_assert(0);
910                 }
911
912                 /* find the edge which is _not_ being split here */
913                 if (!BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
914                   e_other = l->e;
915                 }
916                 else if (!BM_elem_flag_test(l->prev->e, BM_ELEM_TAG)) {
917                   e_other = l->prev->e;
918                 }
919                 else {
920                   BLI_assert(0);
921                   e_other = NULL;
922                 }
923
924                 v_other = BM_edge_other_vert(e_other, v_split);
925                 sub_v3_v3v3(tvec, v_other->co, v_split->co);
926                 normalize_v3(tvec);
927
928                 if (use_even_offset) {
929                   mul_v3_fl(tvec, shell_v3v3_normalized_to_dist(e_no_a, tvec));
930                 }
931               }
932               else {
933                 copy_v3_v3(tvec, e_no_a);
934               }
935
936               /* use_even_offset - doesn't apply here */
937
938               /* scale relative to edge length */
939               if (use_relative_offset) {
940                 mul_v3_fl(tvec, edge_info[vecpair[0]].length);
941               }
942             }
943             else {
944               /* should never happen */
945               BLI_assert(0);
946               zero_v3(tvec);
947             }
948
949             /* apply the offset */
950             madd_v3_v3fl(v_split->co, tvec, thickness);
951           }
952
953           /* this saves expensive/slow glue check for common cases */
954           if (r_vout_len > 2) {
955             bool ok = true;
956             /* last step, NULL this vertex if has a tagged face */
957             BM_ITER_ELEM (f, &iter, v_split, BM_FACES_OF_VERT) {
958               if (BM_elem_flag_test(f, BM_ELEM_TAG)) {
959                 ok = false;
960                 break;
961               }
962             }
963
964             if (ok) {
965               if (v_glue == NULL) {
966                 v_glue = v_split;
967               }
968               else {
969                 if (BM_vert_splice(bm, v_glue, v_split)) {
970                   if (use_vert_coords_orig) {
971                     VERT_ORIG_REMOVE(v_split);
972                   }
973                 }
974               }
975             }
976           }
977           /* end glue */
978         }
979         MEM_freeN(vout);
980       }
981     }
982   }
983
984   if (use_vert_coords_orig) {
985     BLI_memarena_free(vert_coords_orig);
986     BLI_ghash_free(vert_coords, NULL, NULL);
987   }
988
989   if (use_interpolate) {
990     for (i = 0; i < iface_array_len; i++) {
991       if (iface_array[i]) {
992         InterpFace *iface = iface_array[i];
993         BM_face_interp_from_face_ex(bm,
994                                     iface->f,
995                                     iface->f,
996                                     true,
997                                     (const void **)iface->blocks_l,
998                                     (const void **)iface->blocks_v,
999                                     iface->cos_2d,
1000                                     iface->axis_mat);
1001       }
1002     }
1003   }
1004
1005   /* create faces */
1006   for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
1007     BMVert *varr[4] = {NULL};
1008     int j;
1009     /* get the verts in the correct order */
1010     BM_edge_ordered_verts_ex(es->e_new, &varr[1], &varr[0], es->l);
1011 #if 0
1012     if (varr[0] == es->e_new->v1) {
1013       varr[2] = es->e_old->v2;
1014       varr[3] = es->e_old->v1;
1015     }
1016     else {
1017       varr[2] = es->e_old->v1;
1018       varr[3] = es->e_old->v2;
1019     }
1020     j = 4;
1021 #else
1022     /* slightly trickier check - since we can't assume the verts are split */
1023     j = 2; /* 2 edges are set */
1024     if (varr[0] == es->e_new->v1) {
1025       if (es->e_old->v2 != es->e_new->v2) {
1026         varr[j++] = es->e_old->v2;
1027       }
1028       if (es->e_old->v1 != es->e_new->v1) {
1029         varr[j++] = es->e_old->v1;
1030       }
1031     }
1032     else {
1033       if (es->e_old->v1 != es->e_new->v1) {
1034         varr[j++] = es->e_old->v1;
1035       }
1036       if (es->e_old->v2 != es->e_new->v2) {
1037         varr[j++] = es->e_old->v2;
1038       }
1039     }
1040
1041     if (j == 2) {
1042       /* can't make face! */
1043       continue;
1044     }
1045 #endif
1046     /* no need to check doubles, we KNOW there won't be any */
1047     /* yes - reverse face is correct in this case */
1048     f = BM_face_create_verts(bm, varr, j, es->l->f, BM_CREATE_NOP, true);
1049     BMO_face_flag_enable(bm, f, ELE_NEW);
1050
1051     /* Copy for loop data, otherwise UV's and vcols are no good.
1052      * tiny speedup here we could be more clever and copy from known adjacent data
1053      * also - we could attempt to interpolate the loop data,
1054      * this would be much slower but more useful too. */
1055     if (0) {
1056       /* Don't use this because face boundaries have no adjacent loops and won't be filled in.
1057        * instead copy from the opposite side with the code below */
1058       BM_face_copy_shared(bm, f, NULL, NULL);
1059     }
1060     else {
1061       /* 2 inner loops on the edge between the new face and the original */
1062       BMLoop *l_a;
1063       BMLoop *l_b;
1064       BMLoop *l_a_other;
1065       BMLoop *l_b_other;
1066
1067       l_a = BM_FACE_FIRST_LOOP(f);
1068       l_b = l_a->next;
1069
1070       /* we know this side has a radial_next because of the order of created verts in the quad */
1071       l_a_other = BM_edge_other_loop(l_a->e, l_a);
1072       l_b_other = BM_edge_other_loop(l_a->e, l_b);
1073       BM_elem_attrs_copy(bm, bm, l_a_other, l_a);
1074       BM_elem_attrs_copy(bm, bm, l_b_other, l_b);
1075
1076       BLI_assert(l_a->f != l_a_other->f);
1077       BLI_assert(l_b->f != l_b_other->f);
1078
1079       /* step around to the opposite side of the quad - warning, this may have no other edges! */
1080       l_a = l_a->next->next;
1081       l_b = l_a->next;
1082
1083       /**
1084        * Loops vars from newly created face (face_a/b)
1085        * <pre>
1086        *              l_a->e & l_b->prev->e
1087        * +------------------------------------+
1088        * |\ l_a                          l_b /|
1089        * | \ l_a->prev->e            l_b->e / |
1090        * |  \ l_a->prev          l_b->next /  |
1091        * |   +----------------------------+   |
1092        * |   |l_a_other    ^     l_b_other|   |
1093        * |   |        l_b->next->e &...   |   |
1094        * |   |        l_a->prev->prev->e  |   |
1095        * |   |        (inset face)        |   |
1096        * |   +----------------------------+   |
1097        * |  /                              \  |
1098        * | /                                \ |
1099        * |/                                  \|
1100        * +------------------------------------+
1101        * </pre>
1102        */
1103
1104       /* swap a<->b intentionally */
1105       if (use_interpolate) {
1106         InterpFace *iface = iface_array[BM_elem_index_get(es->l->f)];
1107         const int i_a = BM_elem_index_get(l_a_other);
1108         const int i_b = BM_elem_index_get(l_b_other);
1109         CustomData_bmesh_free_block_data(&bm->ldata, l_b->head.data);
1110         CustomData_bmesh_free_block_data(&bm->ldata, l_a->head.data);
1111         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, iface->blocks_l[i_a], &l_b->head.data);
1112         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, iface->blocks_l[i_b], &l_a->head.data);
1113
1114 #ifdef USE_LOOP_CUSTOMDATA_MERGE
1115         if (has_math_ldata) {
1116           BMEdge *e_connect;
1117
1118           /* connecting edge 'a' */
1119           e_connect = l_a->prev->e;
1120           if (BM_edge_is_manifold(e_connect)) {
1121             bm_loop_customdata_merge(bm,
1122                                      e_connect,
1123                                      l_a,
1124                                      BM_edge_other_loop(e_connect, l_a),
1125                                      l_a->prev,
1126                                      BM_edge_other_loop(e_connect, l_a->prev));
1127           }
1128
1129           /* connecting edge 'b' */
1130           e_connect = l_b->e;
1131           if (BM_edge_is_manifold(e_connect)) {
1132             /* swap arg order to maintain winding */
1133             bm_loop_customdata_merge(bm,
1134                                      e_connect,
1135                                      l_b,
1136                                      BM_edge_other_loop(e_connect, l_b),
1137                                      l_b->next,
1138                                      BM_edge_other_loop(e_connect, l_b->next));
1139           }
1140         }
1141 #endif /* USE_LOOP_CUSTOMDATA_MERGE */
1142       }
1143       else {
1144         BM_elem_attrs_copy(bm, bm, l_a_other, l_b);
1145         BM_elem_attrs_copy(bm, bm, l_b_other, l_a);
1146       }
1147     }
1148   }
1149
1150   if (use_interpolate) {
1151     for (i = 0; i < iface_array_len; i++) {
1152       if (iface_array[i]) {
1153         bm_interp_face_free(iface_array[i], bm);
1154       }
1155     }
1156
1157     BLI_memarena_free(interp_arena);
1158     MEM_freeN(iface_array);
1159   }
1160
1161   /* we could flag new edges/verts too, is it useful? */
1162   BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, ELE_NEW);
1163
1164   /* cheap feature to add depth to the inset */
1165   if (depth != 0.0f) {
1166     float(*varr_co)[3];
1167     BMOIter oiter;
1168
1169     /* We need to re-calculate tagged normals,
1170      * but for this purpose we can copy tagged verts from the faces they inset from. */
1171     for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
1172       zero_v3(es->e_new->v1->no);
1173       zero_v3(es->e_new->v2->no);
1174     }
1175     for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
1176       const float *no = es->l->f->no;
1177       add_v3_v3(es->e_new->v1->no, no);
1178       add_v3_v3(es->e_new->v2->no, no);
1179     }
1180     for (i = 0, es = edge_info; i < edge_info_len; i++, es++) {
1181       /* annoying, avoid normalizing twice */
1182       if (len_squared_v3(es->e_new->v1->no) != 1.0f) {
1183         normalize_v3(es->e_new->v1->no);
1184       }
1185       if (len_squared_v3(es->e_new->v2->no) != 1.0f) {
1186         normalize_v3(es->e_new->v2->no);
1187       }
1188     }
1189     /* done correcting edge verts normals */
1190
1191     /* untag verts */
1192     BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
1193
1194     /* tag face verts */
1195     BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
1196       BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
1197         BM_elem_flag_enable(v, BM_ELEM_TAG);
1198       }
1199     }
1200
1201     /* do in 2 passes so moving the verts doesn't feed back into face angle checks
1202      * which BM_vert_calc_shell_factor uses. */
1203
1204     /* over allocate */
1205     varr_co = MEM_callocN(sizeof(*varr_co) * bm->totvert, __func__);
1206
1207     BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1208       if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1209         const float fac = (depth *
1210                            (use_relative_offset ? bm_edge_info_average_length(v, edge_info) :
1211                                                   1.0f) *
1212                            (use_even_boundary ? BM_vert_calc_shell_factor(v) : 1.0f));
1213         madd_v3_v3v3fl(varr_co[i], v->co, v->no, fac);
1214       }
1215     }
1216
1217     BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1218       if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1219         copy_v3_v3(v->co, varr_co[i]);
1220       }
1221     }
1222     MEM_freeN(varr_co);
1223   }
1224
1225   MEM_freeN(edge_info);
1226 }