doxygen: add newline after \file
[blender.git] / source / blender / bmesh / operators / bmo_subdivide.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  * Edge based subdivision with various subdivision patterns.
21  */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_math.h"
26 #include "BLI_rand.h"
27 #include "BLI_array.h"
28 #include "BLI_noise.h"
29 #include "BLI_stack.h"
30
31 #include "BKE_customdata.h"
32
33
34 #include "bmesh.h"
35 #include "intern/bmesh_private.h"
36 #include "intern/bmesh_operators_private.h"
37
38 typedef struct SubDParams {
39         int numcuts;
40         float smooth;
41         int   smooth_falloff;
42         float fractal;
43         float along_normal;
44         //int beauty;
45         bool use_smooth;
46         bool use_smooth_even;
47         bool use_sphere;
48         bool use_fractal;
49         int seed;
50         BMOperator *op;
51         BMOpSlot *slot_edge_percents;  /* BMO_slot_get(params->op->slots_in, "edge_percents"); */
52         BMOpSlot *slot_custom_patterns;  /* BMO_slot_get(params->op->slots_in, "custom_patterns"); */
53         float fractal_ofs[3];
54
55         /* rumtime storage for shape key */
56         struct {
57                 int cd_vert_shape_offset;
58                 int cd_vert_shape_offset_tmp;
59                 int totlayer;
60
61                 /* shapekey holding displaced vertex coordinates for current geometry */
62                 int tmpkey;
63         } shape_info;
64
65 } SubDParams;
66
67 static void bmo_subd_init_shape_info(BMesh *bm, SubDParams *params)
68 {
69         const int skey = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY) - 1;
70         params->shape_info.tmpkey = skey;
71         params->shape_info.cd_vert_shape_offset = CustomData_get_offset(&bm->vdata, CD_SHAPEKEY);
72         params->shape_info.cd_vert_shape_offset_tmp = CustomData_get_n_offset(&bm->vdata, CD_SHAPEKEY, skey);
73         params->shape_info.totlayer = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY);
74
75 }
76
77 typedef void (*subd_pattern_fill_fp)(
78         BMesh *bm, BMFace *face, BMVert **verts,
79         const SubDParams *params);
80
81 /*
82  * note: this is a pattern-based edge subdivider.
83  * it tries to match a pattern to edge selections on faces,
84  * then executes functions to cut them.
85  */
86 typedef struct SubDPattern {
87         int seledges[20]; /* selected edges mask, for splitting */
88
89         /* verts starts at the first new vert cut, not the first vert in the face */
90         subd_pattern_fill_fp connectexec;
91         int len; /* total number of verts, before any subdivision */
92 } SubDPattern;
93
94 /* generic subdivision rules:
95  *
96  * - two selected edges in a face should make a link
97  *   between them.
98  *
99  * - one edge should do, what? make pretty topology, or just
100  *   split the edge only?
101  */
102
103 /* flags for all elements share a common bitfield space */
104 #define SUBD_SPLIT      1
105
106 #define EDGE_PERCENT    2
107
108 /* I don't think new faces are flagged, currently, but
109  * better safe than sorry. */
110 #define FACE_CUSTOMFILL 4
111 #define ELE_INNER       8
112 #define ELE_SPLIT       16
113
114 /* see bug [#32665], 0.00005 means a we get face splits at a little under 1.0 degrees */
115 #define FLT_FACE_SPLIT_EPSILON 0.00005f
116
117 /*
118  * NOTE: beauty has been renamed to flag!
119  */
120
121 /* generic subdivision rules:
122  *
123  * - two selected edges in a face should make a link
124  *   between them.
125  *
126  * - one edge should do, what? make pretty topology, or just
127  *   split the edge only?
128  */
129
130 /* connects face with smallest len, which I think should always be correct for
131  * edge subdivision */
132 static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v_a, BMVert *v_b, BMFace **r_f_new)
133 {
134         BMLoop *l_a, *l_b;
135         BMFace *f;
136
137         /* this isn't the best thing in the world.  it doesn't handle cases where there's
138          * multiple faces yet.  that might require a convexity test to figure out which
139          * face is "best" and who knows what for non-manifold conditions.
140          *
141          * note: we allow adjacent here, since theres no chance this happens.
142          */
143         f = BM_vert_pair_share_face_by_len(v_a, v_b, &l_a, &l_b, true);
144
145
146         if (f) {
147                 BMFace *f_new;
148                 BMLoop *l_new;
149
150                 BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
151
152                 f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false);
153
154                 if (r_f_new) *r_f_new = f_new;
155                 return l_new ? l_new->e : NULL;
156         }
157
158         return NULL;
159 }
160
161 /**
162  * Specialized slerp that uses a sphere defined by each points normal.
163  */
164 static void interp_slerp_co_no_v3(
165         const float co_a[3], const float no_a[3],
166         const float co_b[3], const float no_b[3],
167         const float no_dir[3],  /* caller already knows, avoid normalize */
168         float fac,
169         float r_co[3])
170 {
171         /* center of the sphere defined by both normals */
172         float center[3];
173
174         BLI_assert(len_squared_v3v3(no_a, no_b) != 0);
175
176         /* calculate sphere 'center' */
177         {
178                 /* use point on plane to */
179                 float no_mid[3], no_ortho[3];
180                 /* pass this as an arg instead */
181 #if 0
182                 float no_dir[3];
183 #endif
184
185                 add_v3_v3v3(no_mid, no_a, no_b);
186                 normalize_v3(no_mid);
187
188 #if 0
189                 sub_v3_v3v3(no_dir, co_a, co_b);
190                 normalize_v3(no_dir);
191 #endif
192
193                 /* axis of slerp */
194                 bool center_ok = false;
195                 cross_v3_v3v3(no_ortho, no_mid, no_dir);
196                 if (normalize_v3(no_ortho) != 0.0f) {
197                         float plane_a[4], plane_b[4], plane_c[4];
198                         float v_a_no_ortho[3], v_b_no_ortho[3];
199
200                         /* create planes */
201                         cross_v3_v3v3(v_a_no_ortho, no_ortho, no_a);
202                         cross_v3_v3v3(v_b_no_ortho, no_ortho, no_b);
203                         project_v3_plane(v_a_no_ortho, no_ortho, v_a_no_ortho);
204                         project_v3_plane(v_b_no_ortho, no_ortho, v_b_no_ortho);
205
206                         plane_from_point_normal_v3(plane_a, co_a, v_a_no_ortho);
207                         plane_from_point_normal_v3(plane_b, co_b, v_b_no_ortho);
208                         plane_from_point_normal_v3(plane_c, co_b, no_ortho);
209
210                         /* find the sphere center from 3 planes */
211                         if (isect_plane_plane_plane_v3(plane_a, plane_b, plane_c, center)) {
212                                 center_ok = true;
213                         }
214                 }
215                 if (center_ok == false) {
216                         mid_v3_v3v3(center, co_a, co_b);
217                 }
218         }
219
220         /* calculate the final output 'r_co' */
221         {
222                 float ofs_a[3], ofs_b[3], ofs_slerp[3];
223                 float dist_a, dist_b;
224
225                 sub_v3_v3v3(ofs_a, co_a, center);
226                 sub_v3_v3v3(ofs_b, co_b, center);
227
228                 dist_a = normalize_v3(ofs_a);
229                 dist_b = normalize_v3(ofs_b);
230
231                 if (interp_v3_v3v3_slerp(ofs_slerp, ofs_a, ofs_b, fac)) {
232                         madd_v3_v3v3fl(r_co, center, ofs_slerp, interpf(dist_b, dist_a, fac));
233                 }
234                 else {
235                         interp_v3_v3v3(r_co, co_a, co_b, fac);
236                 }
237         }
238 }
239
240 /* calculates offset for co, based on fractal, sphere or smooth settings  */
241 static void alter_co(
242         BMVert *v, BMEdge *UNUSED(e_orig),
243         const SubDParams *params, const float perc,
244         const BMVert *v_a, const BMVert *v_b)
245 {
246         float *co = BM_ELEM_CD_GET_VOID_P(v, params->shape_info.cd_vert_shape_offset_tmp);
247         int i;
248
249         copy_v3_v3(co, v->co);
250
251         if (UNLIKELY(params->use_sphere)) { /* subdivide sphere */
252                 normalize_v3_length(co, params->smooth);
253         }
254         else if (params->use_smooth) {
255                 /* calculating twice and blending gives smoother results,
256                  * removing visible seams. */
257 #define USE_SPHERE_DUAL_BLEND
258
259                 const float eps_unit_vec = 1e-5f;
260                 float smooth;
261                 float no_dir[3];
262
263 #ifdef USE_SPHERE_DUAL_BLEND
264                 float no_reflect[3], co_a[3], co_b[3];
265 #endif
266
267                 sub_v3_v3v3(no_dir, v_a->co, v_b->co);
268                 normalize_v3(no_dir);
269
270 #ifndef USE_SPHERE_DUAL_BLEND
271                 if (len_squared_v3v3(v_a->no, v_b->no) < eps_unit_vec) {
272                         interp_v3_v3v3(co, v_a->co, v_b->co, perc);
273                 }
274                 else {
275                         interp_slerp_co_no_v3(v_a->co, v_a->no, v_b->co, v_b->no, no_dir, perc, co);
276                 }
277 #else
278                 /* sphere-a */
279                 reflect_v3_v3v3(no_reflect, v_a->no, no_dir);
280                 if (len_squared_v3v3(v_a->no, no_reflect) < eps_unit_vec) {
281                         interp_v3_v3v3(co_a, v_a->co, v_b->co, perc);
282                 }
283                 else {
284                         interp_slerp_co_no_v3(v_a->co, v_a->no, v_b->co, no_reflect, no_dir, perc, co_a);
285                 }
286
287                 /* sphere-b */
288                 reflect_v3_v3v3(no_reflect, v_b->no, no_dir);
289                 if (len_squared_v3v3(v_b->no, no_reflect) < eps_unit_vec) {
290                         interp_v3_v3v3(co_b, v_a->co, v_b->co, perc);
291                 }
292                 else {
293                         interp_slerp_co_no_v3(v_a->co, no_reflect, v_b->co, v_b->no, no_dir, perc, co_b);
294                 }
295
296                 /* blend both spheres */
297                 interp_v3_v3v3(co, co_a, co_b, perc);
298 #endif  /* USE_SPHERE_DUAL_BLEND */
299
300                 /* apply falloff */
301                 if (params->smooth_falloff == SUBD_FALLOFF_LIN) {
302                         smooth = 1.0f;
303                 }
304                 else {
305                         smooth = fabsf(1.0f - 2.0f * fabsf(0.5f - perc));
306                         smooth = 1.0f + bmesh_subd_falloff_calc(params->smooth_falloff, smooth);
307                 }
308
309                 if (params->use_smooth_even) {
310                         smooth *= shell_v3v3_mid_normalized_to_dist(v_a->no, v_b->no);
311                 }
312
313                 smooth *= params->smooth;
314                 if (smooth != 1.0f) {
315                         float co_flat[3];
316                         interp_v3_v3v3(co_flat, v_a->co, v_b->co, perc);
317                         interp_v3_v3v3(co, co_flat, co, smooth);
318                 }
319
320 #undef USE_SPHERE_DUAL_BLEND
321         }
322
323         if (params->use_fractal) {
324                 float normal[3], co2[3], base1[3], base2[3], tvec[3];
325                 const float len = len_v3v3(v_a->co, v_b->co);
326                 float fac;
327
328                 fac = params->fractal * len;
329
330                 mid_v3_v3v3(normal, v_a->no, v_b->no);
331                 ortho_basis_v3v3_v3(base1, base2, normal);
332
333                 add_v3_v3v3(co2, v->co, params->fractal_ofs);
334                 mul_v3_fl(co2, 10.0f);
335
336                 tvec[0] = fac * (BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 2) - 0.5f);
337                 tvec[1] = fac * (BLI_gTurbulence(1.0, co2[1], co2[0], co2[2], 15, 0, 2) - 0.5f);
338                 tvec[2] = fac * (BLI_gTurbulence(1.0, co2[1], co2[2], co2[0], 15, 0, 2) - 0.5f);
339
340                 /* add displacement */
341                 madd_v3_v3fl(co, normal, tvec[0]);
342                 madd_v3_v3fl(co, base1, tvec[1] * (1.0f - params->along_normal));
343                 madd_v3_v3fl(co, base2, tvec[2] * (1.0f - params->along_normal));
344         }
345
346         /* apply the new difference to the rest of the shape keys,
347          * note that this doesn't take rotations into account, we _could_ support
348          * this by getting the normals and coords for each shape key and
349          * re-calculate the smooth value for each but this is quite involved.
350          * for now its ok to simply apply the difference IMHO - campbell */
351
352         if (params->shape_info.totlayer > 1) {
353                 float tvec[3];
354
355                 sub_v3_v3v3(tvec, v->co, co);
356
357                 /* skip the last layer since its the temp */
358                 i = params->shape_info.totlayer - 1;
359                 co = BM_ELEM_CD_GET_VOID_P(v, params->shape_info.cd_vert_shape_offset);
360                 while (i--) {
361                         BLI_assert(co != BM_ELEM_CD_GET_VOID_P(v, params->shape_info.cd_vert_shape_offset_tmp));
362                         sub_v3_v3(co += 3, tvec);
363                 }
364         }
365 }
366
367 /* assumes in the edge is the correct interpolated vertices already */
368 /* percent defines the interpolation, rad and flag are for special options */
369 /* results in new vertex with correct coordinate, vertex normal and weight group info */
370 static BMVert *bm_subdivide_edge_addvert(
371         BMesh *bm, BMEdge *edge, BMEdge *e_orig,
372         const SubDParams *params,
373         const float factor_edge_split, const float factor_subd,
374         BMVert *v_a, BMVert *v_b,
375         BMEdge **r_edge)
376 {
377         BMVert *v_new;
378
379         v_new = BM_edge_split(bm, edge, edge->v1, r_edge, factor_edge_split);
380
381         BMO_vert_flag_enable(bm, v_new, ELE_INNER);
382
383         /* offset for smooth or sphere or fractal */
384         alter_co(v_new, e_orig, params, factor_subd, v_a, v_b);
385
386 #if 0 //BMESH_TODO
387         /* clip if needed by mirror modifier */
388         if (edge->v1->f2) {
389                 if (edge->v1->f2 & edge->v2->f2 & 1) {
390                         co[0] = 0.0f;
391                 }
392                 if (edge->v1->f2 & edge->v2->f2 & 2) {
393                         co[1] = 0.0f;
394                 }
395                 if (edge->v1->f2 & edge->v2->f2 & 4) {
396                         co[2] = 0.0f;
397                 }
398         }
399 #endif
400
401         interp_v3_v3v3(v_new->no, v_a->no, v_b->no, factor_subd);
402         normalize_v3(v_new->no);
403
404         return v_new;
405 }
406
407 static BMVert *subdivide_edge_num(
408         BMesh *bm, BMEdge *edge, BMEdge *e_orig,
409         int curpoint, int totpoint, const SubDParams *params,
410         BMVert *v_a, BMVert *v_b,
411         BMEdge **r_edge)
412 {
413         BMVert *v_new;
414         float factor_edge_split, factor_subd;
415
416         if (BMO_edge_flag_test(bm, edge, EDGE_PERCENT) && totpoint == 1) {
417                 factor_edge_split = BMO_slot_map_float_get(params->slot_edge_percents, edge);
418                 factor_subd = 0.0f;
419         }
420         else {
421                 factor_edge_split = 1.0f / (float)(totpoint + 1 - curpoint);
422                 factor_subd = (float)(curpoint + 1) / (float)(totpoint + 1);
423         }
424
425         v_new = bm_subdivide_edge_addvert(
426                 bm, edge, e_orig, params,
427                 factor_edge_split, factor_subd,
428                 v_a, v_b, r_edge);
429         return v_new;
430 }
431
432 static void bm_subdivide_multicut(
433         BMesh *bm, BMEdge *edge, const SubDParams *params,
434         BMVert *v_a, BMVert *v_b)
435 {
436         BMEdge *eed = edge, *e_new, e_tmp = *edge;
437         BMVert *v, v1_tmp = *edge->v1, v2_tmp = *edge->v2, *v1 = edge->v1, *v2 = edge->v2;
438         int i, numcuts = params->numcuts;
439
440         e_tmp.v1 = &v1_tmp;
441         e_tmp.v2 = &v2_tmp;
442
443         for (i = 0; i < numcuts; i++) {
444                 v = subdivide_edge_num(bm, eed, &e_tmp, i, params->numcuts, params, v_a, v_b, &e_new);
445
446                 BMO_vert_flag_enable(bm, v, SUBD_SPLIT | ELE_SPLIT);
447                 BMO_edge_flag_enable(bm, eed, SUBD_SPLIT | ELE_SPLIT);
448                 BMO_edge_flag_enable(bm, e_new, SUBD_SPLIT | ELE_SPLIT);
449
450                 BM_CHECK_ELEMENT(v);
451                 if (v->e) BM_CHECK_ELEMENT(v->e);
452                 if (v->e && v->e->l) BM_CHECK_ELEMENT(v->e->l->f);
453         }
454
455         alter_co(v1, &e_tmp, params, 0, &v1_tmp, &v2_tmp);
456         alter_co(v2, &e_tmp, params, 1.0, &v1_tmp, &v2_tmp);
457 }
458
459 /* note: the patterns are rotated as necessary to
460  * match the input geometry.  they're based on the
461  * pre-split state of the  face */
462
463 /**
464  * <pre>
465  *  v3---------v2
466  *  |          |
467  *  |          |
468  *  |          |
469  *  |          |
470  *  v4---v0---v1
471  * </pre>
472  */
473 static void quad_1edge_split(BMesh *bm, BMFace *UNUSED(face),
474                              BMVert **verts, const SubDParams *params)
475 {
476         BMFace *f_new;
477         int i, add, numcuts = params->numcuts;
478
479         /* if it's odd, the middle face is a quad, otherwise it's a triangle */
480         if ((numcuts % 2) == 0) {
481                 add = 2;
482                 for (i = 0; i < numcuts; i++) {
483                         if (i == numcuts / 2) {
484                                 add -= 1;
485                         }
486                         connect_smallest_face(bm, verts[i], verts[numcuts + add], &f_new);
487                 }
488         }
489         else {
490                 add = 2;
491                 for (i = 0; i < numcuts; i++) {
492                         connect_smallest_face(bm, verts[i], verts[numcuts + add], &f_new);
493                         if (i == numcuts / 2) {
494                                 add -= 1;
495                                 connect_smallest_face(bm, verts[i], verts[numcuts + add], &f_new);
496                         }
497                 }
498
499         }
500 }
501
502 static const SubDPattern quad_1edge = {
503         {1, 0, 0, 0},
504         quad_1edge_split,
505         4,
506 };
507
508
509 /**
510  * <pre>
511  *  v6--------v5
512  *  |          |
513  *  |          |v4s
514  *  |          |v3s
515  *  |   s  s   |
516  *  v7-v0--v1-v2
517  * </pre>
518  */
519 static void quad_2edge_split_path(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
520                                   const SubDParams *params)
521 {
522         BMFace *f_new;
523         int i, numcuts = params->numcuts;
524
525         for (i = 0; i < numcuts; i++) {
526                 connect_smallest_face(bm, verts[i], verts[numcuts + (numcuts - i)], &f_new);
527         }
528         connect_smallest_face(bm, verts[numcuts * 2 + 3], verts[numcuts * 2 + 1], &f_new);
529 }
530
531 static const SubDPattern quad_2edge_path = {
532         {1, 1, 0, 0},
533         quad_2edge_split_path,
534         4,
535 };
536
537 /**
538  * <pre>
539  *  v6--------v5
540  *  |          |
541  *  |          |v4s
542  *  |          |v3s
543  *  |   s  s   |
544  *  v7-v0--v1-v2
545  * </pre>
546  */
547 static void quad_2edge_split_innervert(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
548                                        const SubDParams *params)
549 {
550         BMFace *f_new;
551         BMVert *v, *v_last;
552         BMEdge *e, *e_new, e_tmp;
553         int i, numcuts = params->numcuts;
554
555         v_last = verts[numcuts];
556
557         for (i = numcuts - 1; i >= 0; i--) {
558                 e = connect_smallest_face(bm, verts[i], verts[numcuts + (numcuts - i)], &f_new);
559
560                 e_tmp = *e;
561                 v = bm_subdivide_edge_addvert(bm, e, &e_tmp, params, 0.5f, 0.5f, e->v1, e->v2, &e_new);
562
563                 if (i != numcuts - 1) {
564                         connect_smallest_face(bm, v_last, v, &f_new);
565                 }
566
567                 v_last = v;
568         }
569
570         connect_smallest_face(bm, v_last, verts[numcuts * 2 + 2], &f_new);
571 }
572
573 static const SubDPattern quad_2edge_innervert = {
574         {1, 1, 0, 0},
575         quad_2edge_split_innervert,
576         4,
577 };
578
579 /**
580  * <pre>
581  *  v6--------v5
582  *  |          |
583  *  |          |v4s
584  *  |          |v3s
585  *  |   s  s   |
586  *  v7-v0--v1-v2
587  * </pre>
588  */
589 static void quad_2edge_split_fan(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
590                                  const SubDParams *params)
591 {
592         BMFace *f_new;
593         /* BMVert *v; */               /* UNUSED */
594         /* BMVert *v_last = verts[2]; */ /* UNUSED */
595         /* BMEdge *e, *e_new; */          /* UNUSED */
596         int i, numcuts = params->numcuts;
597
598         for (i = 0; i < numcuts; i++) {
599                 connect_smallest_face(bm, verts[i], verts[numcuts * 2 + 2], &f_new);
600                 connect_smallest_face(bm, verts[numcuts + (numcuts - i)], verts[numcuts * 2 + 2], &f_new);
601         }
602 }
603
604 static const SubDPattern quad_2edge_fan = {
605         {1, 1, 0, 0},
606         quad_2edge_split_fan,
607         4,
608 };
609
610 /**
611  * <pre>
612  *      s   s
613  *  v8--v7--v6-v5
614  *  |          |
615  *  |          v4 s
616  *  |          |
617  *  |          v3 s
618  *  |   s  s   |
619  *  v9-v0--v1-v2
620  * </pre>
621  */
622 static void quad_3edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
623                              const SubDParams *params)
624 {
625         BMFace *f_new;
626         int i, add = 0, numcuts = params->numcuts;
627
628         for (i = 0; i < numcuts; i++) {
629                 if (i == numcuts / 2) {
630                         if (numcuts % 2 != 0) {
631                                 connect_smallest_face(bm, verts[numcuts - i - 1 + add], verts[i + numcuts + 1], &f_new);
632                         }
633                         add = numcuts * 2 + 2;
634                 }
635                 connect_smallest_face(bm, verts[numcuts - i - 1 + add], verts[i + numcuts + 1], &f_new);
636         }
637
638         for (i = 0; i < numcuts / 2 + 1; i++) {
639                 connect_smallest_face(bm, verts[i], verts[(numcuts - i) + numcuts * 2 + 1], &f_new);
640         }
641 }
642
643 static const SubDPattern quad_3edge = {
644         {1, 1, 1, 0},
645         quad_3edge_split,
646         4,
647 };
648
649 /**
650  * <pre>
651  *            v8--v7-v6--v5
652  *            |     s    |
653  *            |v9 s     s|v4
654  * first line |          |   last line
655  *            |v10s s   s|v3
656  *            v11-v0--v1-v2
657  *
658  *            it goes from bottom up
659  * </pre>
660  */
661 static void quad_4edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
662                                  const SubDParams *params)
663 {
664         BMFace *f_new;
665         BMVert *v, *v1, *v2;
666         BMEdge *e, *e_new, e_tmp;
667         BMVert **lines;
668         int numcuts = params->numcuts;
669         int i, j, a, b, s = numcuts + 2 /* , totv = numcuts * 4 + 4 */;
670
671         lines = MEM_callocN(sizeof(BMVert *) * (numcuts + 2) * (numcuts + 2), "q_4edge_split");
672         /* build a 2-dimensional array of verts,
673          * containing every vert (and all new ones)
674          * in the face */
675
676         /* first line */
677         for (i = 0; i < numcuts + 2; i++) {
678                 lines[i] = verts[numcuts * 3 + 2 + (numcuts - i + 1)];
679         }
680
681         /* last line */
682         for (i = 0; i < numcuts + 2; i++) {
683                 lines[(s - 1) * s + i] = verts[numcuts + i];
684         }
685
686         /* first and last members of middle lines */
687         for (i = 0; i < numcuts; i++) {
688                 a = i;
689                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
690
691                 e = connect_smallest_face(bm, verts[a], verts[b], &f_new);
692                 if (!e)
693                         continue;
694
695                 BMO_edge_flag_enable(bm, e, ELE_INNER);
696                 BMO_face_flag_enable(bm, f_new, ELE_INNER);
697
698
699                 v1 = lines[(i + 1) * s] = verts[a];
700                 v2 = lines[(i + 1) * s + s - 1] = verts[b];
701
702                 e_tmp = *e;
703                 for (a = 0; a < numcuts; a++) {
704                         v = subdivide_edge_num(bm, e, &e_tmp, a, numcuts, params, v1, v2, &e_new);
705
706                         BMESH_ASSERT(v != NULL);
707
708                         BMO_edge_flag_enable(bm, e_new, ELE_INNER);
709                         lines[(i + 1) * s + a + 1] = v;
710                 }
711         }
712
713         for (i = 1; i < numcuts + 2; i++) {
714                 for (j = 1; j <= numcuts; j++) {
715                         a = i * s + j;
716                         b = (i - 1) * s + j;
717                         e = connect_smallest_face(bm, lines[a], lines[b], &f_new);
718                         if (!e)
719                                 continue;
720
721                         BMO_edge_flag_enable(bm, e, ELE_INNER);
722                         BMO_face_flag_enable(bm, f_new, ELE_INNER);
723                 }
724         }
725
726         MEM_freeN(lines);
727 }
728
729 /**
730  * <pre>
731  *        v3
732  *       / \
733  *      /   \
734  *     /     \
735  *    /       \
736  *   /         \
737  *  v4--v0--v1--v2
738  *      s    s
739  * </pre>
740  */
741 static void tri_1edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
742                             const SubDParams *params)
743 {
744         BMFace *f_new;
745         int i, numcuts = params->numcuts;
746
747         for (i = 0; i < numcuts; i++) {
748                 connect_smallest_face(bm, verts[i], verts[numcuts + 1], &f_new);
749         }
750 }
751
752 static const SubDPattern tri_1edge = {
753         {1, 0, 0},
754         tri_1edge_split,
755         3,
756 };
757
758 /**
759  * <pre>
760  *         v5
761  *        / \
762  *   s v6/---\ v4 s
763  *      / \ / \
764  *  sv7/---v---\ v3 s
765  *    /  \/  \/ \
766  *   v8--v0--v1--v2
767  *      s    s
768  * </pre>
769  */
770 static void tri_3edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
771                                 const SubDParams *params)
772 {
773         BMFace *f_new;
774         BMEdge *e, *e_new, e_tmp;
775         BMVert ***lines, *v, v1_tmp, v2_tmp;
776         void *stackarr[1];
777         int i, j, a, b, numcuts = params->numcuts;
778
779         /* number of verts in each lin */
780         lines = MEM_callocN(sizeof(void *) * (numcuts + 2), "triangle vert table");
781
782         lines[0] = (BMVert **) stackarr;
783         lines[0][0] = verts[numcuts * 2 + 1];
784
785         lines[numcuts + 1] = MEM_callocN(sizeof(void *) * (numcuts + 2), "triangle vert table 2");
786         for (i = 0; i < numcuts; i++) {
787                 lines[numcuts + 1][i + 1] = verts[i];
788         }
789         lines[numcuts + 1][0] = verts[numcuts * 3 + 2];
790         lines[numcuts + 1][numcuts + 1] = verts[numcuts];
791
792         for (i = 0; i < numcuts; i++) {
793                 lines[i + 1] = MEM_callocN(sizeof(void *) * (2 + i), "triangle vert table row");
794                 a = numcuts * 2 + 2 + i;
795                 b = numcuts + numcuts - i;
796                 e = connect_smallest_face(bm, verts[a], verts[b], &f_new);
797                 if (!e) goto cleanup;
798
799                 BMO_edge_flag_enable(bm, e, ELE_INNER);
800                 BMO_face_flag_enable(bm, f_new, ELE_INNER);
801
802                 lines[i + 1][0] = verts[a];
803                 lines[i + 1][i + 1] = verts[b];
804
805                 e_tmp = *e;
806                 v1_tmp = *verts[a];
807                 v2_tmp = *verts[b];
808                 e_tmp.v1 = &v1_tmp;
809                 e_tmp.v2 = &v2_tmp;
810                 for (j = 0; j < i; j++) {
811                         v = subdivide_edge_num(bm, e, &e_tmp, j, i, params, verts[a], verts[b], &e_new);
812                         lines[i + 1][j + 1] = v;
813
814                         BMO_edge_flag_enable(bm, e_new, ELE_INNER);
815                 }
816         }
817
818         /**
819          * <pre>
820          *         v5
821          *        / \
822          *   s v6/---\ v4 s
823          *      / \ / \
824          *  sv7/---v---\ v3 s
825          *    /  \/  \/ \
826          *   v8--v0--v1--v2
827          *      s    s
828          * </pre>
829          */
830         for (i = 1; i <= numcuts; i++) {
831                 for (j = 0; j < i; j++) {
832                         e = connect_smallest_face(bm, lines[i][j], lines[i + 1][j + 1], &f_new);
833
834                         BMO_edge_flag_enable(bm, e, ELE_INNER);
835                         BMO_face_flag_enable(bm, f_new, ELE_INNER);
836
837                         e = connect_smallest_face(bm, lines[i][j + 1], lines[i + 1][j + 1], &f_new);
838
839                         BMO_edge_flag_enable(bm, e, ELE_INNER);
840                         BMO_face_flag_enable(bm, f_new, ELE_INNER);
841                 }
842         }
843
844 cleanup:
845         for (i = 1; i < numcuts + 2; i++) {
846                 if (lines[i]) MEM_freeN(lines[i]);
847         }
848
849         MEM_freeN(lines);
850 }
851
852 static const SubDPattern tri_3edge = {
853         {1, 1, 1},
854         tri_3edge_subdivide,
855         3,
856 };
857
858
859 static const SubDPattern quad_4edge = {
860         {1, 1, 1, 1},
861         quad_4edge_subdivide,
862         4,
863 };
864
865 static const SubDPattern *patterns[] = {
866         NULL,  /* quad single edge pattern is inserted here */
867         NULL,  /* quad corner vert pattern is inserted here */
868         NULL,  /* tri single edge pattern is inserted here */
869         NULL,
870         &quad_3edge,
871         NULL,
872 };
873
874 #define PATTERNS_TOT  ARRAY_SIZE(patterns)
875
876 typedef struct SubDFaceData {
877         BMVert *start;
878         const SubDPattern *pat;
879         int totedgesel;  /* only used if pat was NULL, e.g. no pattern was found */
880         BMFace *face;
881 } SubDFaceData;
882
883 void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op)
884 {
885         BMOpSlot *einput;
886         const SubDPattern *pat;
887         SubDParams params;
888         BLI_Stack *facedata;
889         BMIter viter, fiter, liter;
890         BMVert *v, **verts = NULL;
891         BMEdge *edge;
892         BMEdge **edges = NULL;
893         BLI_array_declare(edges);
894         BMLoop *(*loops_split)[2] = NULL;
895         BLI_array_declare(loops_split);
896         BMLoop **loops = NULL;
897         BLI_array_declare(loops);
898         BMLoop *l_new, *l;
899         BMFace *face;
900         BLI_array_declare(verts);
901         float smooth, fractal, along_normal;
902         bool use_sphere, use_single_edge, use_grid_fill, use_only_quads;
903         int cornertype, seed, i, j, a, b, numcuts, totesel, smooth_falloff;
904
905         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, SUBD_SPLIT);
906
907         numcuts = BMO_slot_int_get(op->slots_in, "cuts");
908         seed = BMO_slot_int_get(op->slots_in, "seed");
909         smooth = BMO_slot_float_get(op->slots_in, "smooth");
910         smooth_falloff = BMO_slot_int_get(op->slots_in, "smooth_falloff");
911         fractal = BMO_slot_float_get(op->slots_in, "fractal");
912         along_normal = BMO_slot_float_get(op->slots_in, "along_normal");
913         cornertype = BMO_slot_int_get(op->slots_in, "quad_corner_type");
914
915         use_single_edge = BMO_slot_bool_get(op->slots_in, "use_single_edge");
916         use_grid_fill = BMO_slot_bool_get(op->slots_in, "use_grid_fill");
917         use_only_quads = BMO_slot_bool_get(op->slots_in, "use_only_quads");
918         use_sphere = BMO_slot_bool_get(op->slots_in, "use_sphere");
919
920         patterns[1] = NULL;
921         /* straight cut is patterns[1] == NULL */
922         switch (cornertype) {
923                 case SUBD_CORNER_PATH:
924                         patterns[1] = &quad_2edge_path;
925                         break;
926                 case SUBD_CORNER_INNERVERT:
927                         patterns[1] = &quad_2edge_innervert;
928                         break;
929                 case SUBD_CORNER_FAN:
930                         patterns[1] = &quad_2edge_fan;
931                         break;
932         }
933
934         if (use_single_edge) {
935                 patterns[0] = &quad_1edge;
936                 patterns[2] = &tri_1edge;
937         }
938         else {
939                 patterns[0] = NULL;
940                 patterns[2] = NULL;
941         }
942
943         if (use_grid_fill) {
944                 patterns[3] = &quad_4edge;
945                 patterns[5] = &tri_3edge;
946         }
947         else {
948                 patterns[3] = NULL;
949                 patterns[5] = NULL;
950         }
951
952         /* add a temporary shapekey layer to store displacements on current geometry */
953         BM_data_layer_add(bm, &bm->vdata, CD_SHAPEKEY);
954
955         bmo_subd_init_shape_info(bm, &params);
956
957         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
958                 float *co = BM_ELEM_CD_GET_VOID_P(v, params.shape_info.cd_vert_shape_offset_tmp);
959                 copy_v3_v3(co, v->co);
960         }
961
962         /* first go through and tag edges */
963         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_in, "edges", BM_EDGE, SUBD_SPLIT);
964
965         params.numcuts = numcuts;
966         params.op = op;
967         params.slot_edge_percents   = BMO_slot_get(op->slots_in, "edge_percents");
968         params.slot_custom_patterns = BMO_slot_get(op->slots_in, "custom_patterns");
969         params.smooth = smooth;
970         params.smooth_falloff = smooth_falloff;
971         params.seed = seed;
972         params.fractal = fractal;
973         params.along_normal = along_normal;
974         params.use_smooth  = (smooth  != 0.0f);
975         params.use_smooth_even = BMO_slot_bool_get(op->slots_in, "use_smooth_even");
976         params.use_fractal = (fractal != 0.0f);
977         params.use_sphere  = use_sphere;
978
979         if (params.use_fractal) {
980                 RNG *rng = BLI_rng_new_srandom(seed);
981
982                 params.fractal_ofs[0] = BLI_rng_get_float(rng) * 200.0f;
983                 params.fractal_ofs[1] = BLI_rng_get_float(rng) * 200.0f;
984                 params.fractal_ofs[2] = BLI_rng_get_float(rng) * 200.0f;
985
986                 BLI_rng_free(rng);
987         }
988
989         BMO_slot_map_to_flag(bm, op->slots_in, "custom_patterns",
990                              BM_FACE, FACE_CUSTOMFILL);
991
992         BMO_slot_map_to_flag(bm, op->slots_in, "edge_percents",
993                              BM_EDGE, EDGE_PERCENT);
994
995
996         facedata = BLI_stack_new(sizeof(SubDFaceData), __func__);
997
998         BM_ITER_MESH (face, &fiter, bm, BM_FACES_OF_MESH) {
999                 BMEdge *e1 = NULL, *e2 = NULL;
1000                 float vec1[3], vec2[3];
1001                 bool matched = false;
1002
1003                 /* skip non-quads if requested */
1004                 if (use_only_quads && face->len != 4)
1005                         continue;
1006
1007                 /* figure out which pattern to use */
1008
1009                 BLI_array_clear(edges);
1010                 BLI_array_clear(verts);
1011
1012                 BLI_array_grow_items(edges, face->len);
1013                 BLI_array_grow_items(verts, face->len);
1014
1015                 totesel = 0;
1016                 BM_ITER_ELEM_INDEX (l_new, &liter, face, BM_LOOPS_OF_FACE, i) {
1017                         edges[i] = l_new->e;
1018                         verts[i] = l_new->v;
1019
1020                         if (BMO_edge_flag_test(bm, edges[i], SUBD_SPLIT)) {
1021                                 if (!e1) e1 = edges[i];
1022                                 else     e2 = edges[i];
1023
1024                                 totesel++;
1025                         }
1026                 }
1027
1028                 /* make sure the two edges have a valid angle to each other */
1029                 if (totesel == 2 && BM_edge_share_vert_check(e1, e2)) {
1030                         sub_v3_v3v3(vec1, e1->v2->co, e1->v1->co);
1031                         sub_v3_v3v3(vec2, e2->v2->co, e2->v1->co);
1032                         normalize_v3(vec1);
1033                         normalize_v3(vec2);
1034
1035                         if (fabsf(dot_v3v3(vec1, vec2)) > 1.0f - FLT_FACE_SPLIT_EPSILON) {
1036                                 totesel = 0;
1037                         }
1038                 }
1039
1040                 if (BMO_face_flag_test(bm, face, FACE_CUSTOMFILL)) {
1041                         pat = *BMO_slot_map_data_get(params.slot_custom_patterns, face);
1042                         for (i = 0; i < pat->len; i++) {
1043                                 matched = 1;
1044                                 for (j = 0; j < pat->len; j++) {
1045                                         a = (j + i) % pat->len;
1046                                         if ((!!BMO_edge_flag_test(bm, edges[a], SUBD_SPLIT)) != (!!pat->seledges[j])) {
1047                                                 matched = 0;
1048                                                 break;
1049                                         }
1050                                 }
1051                                 if (matched) {
1052                                         SubDFaceData *fd;
1053
1054                                         fd = BLI_stack_push_r(facedata);
1055                                         fd->pat = pat;
1056                                         fd->start = verts[i];
1057                                         fd->face = face;
1058                                         fd->totedgesel = totesel;
1059                                         BMO_face_flag_enable(bm, face, SUBD_SPLIT);
1060                                         break;
1061                                 }
1062                         }
1063
1064                         /* obvously don't test for other patterns matching */
1065                         continue;
1066                 }
1067
1068                 for (i = 0; i < PATTERNS_TOT; i++) {
1069                         pat = patterns[i];
1070                         if (!pat) {
1071                                 continue;
1072                         }
1073
1074                         if (pat->len == face->len) {
1075                                 for (a = 0; a < pat->len; a++) {
1076                                         matched = 1;
1077                                         for (b = 0; b < pat->len; b++) {
1078                                                 j = (b + a) % pat->len;
1079                                                 if ((!!BMO_edge_flag_test(bm, edges[j], SUBD_SPLIT)) != (!!pat->seledges[b])) {
1080                                                         matched = 0;
1081                                                         break;
1082                                                 }
1083                                         }
1084                                         if (matched) {
1085                                                 break;
1086                                         }
1087                                 }
1088                                 if (matched) {
1089                                         SubDFaceData *fd;
1090
1091                                         BMO_face_flag_enable(bm, face, SUBD_SPLIT);
1092
1093                                         fd = BLI_stack_push_r(facedata);
1094                                         fd->pat = pat;
1095                                         fd->start = verts[a];
1096                                         fd->face = face;
1097                                         fd->totedgesel = totesel;
1098                                         break;
1099                                 }
1100                         }
1101
1102                 }
1103
1104                 if (!matched && totesel) {
1105                         SubDFaceData *fd;
1106
1107                         BMO_face_flag_enable(bm, face, SUBD_SPLIT);
1108
1109                         /* must initialize all members here */
1110                         fd = BLI_stack_push_r(facedata);
1111                         fd->start = NULL;
1112                         fd->pat = NULL;
1113                         fd->totedgesel = totesel;
1114                         fd->face = face;
1115                 }
1116         }
1117
1118         einput = BMO_slot_get(op->slots_in, "edges");
1119
1120         /* go through and split edges */
1121         for (i = 0; i < einput->len; i++) {
1122                 edge = einput->data.buf[i];
1123                 bm_subdivide_multicut(bm, edge, &params, edge->v1, edge->v2);
1124         }
1125
1126         /* copy original-geometry displacements to current coordinates */
1127         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
1128                 const float *co = BM_ELEM_CD_GET_VOID_P(v, params.shape_info.cd_vert_shape_offset_tmp);
1129                 copy_v3_v3(v->co, co);
1130         }
1131
1132         for (; !BLI_stack_is_empty(facedata); BLI_stack_discard(facedata)) {
1133                 SubDFaceData *fd = BLI_stack_peek(facedata);
1134
1135                 face = fd->face;
1136
1137                 /* figure out which pattern to use */
1138                 BLI_array_clear(verts);
1139
1140                 pat = fd->pat;
1141
1142                 if (!pat && fd->totedgesel == 2) {
1143                         int vlen;
1144
1145                         /* ok, no pattern.  we still may be able to do something */
1146                         BLI_array_clear(loops);
1147                         BLI_array_clear(loops_split);
1148
1149                         /* for case of two edges, connecting them shouldn't be too hard */
1150                         BLI_array_grow_items(loops, face->len);
1151                         BM_ITER_ELEM_INDEX (l, &liter, face, BM_LOOPS_OF_FACE, a) {
1152                                 loops[a] = l;
1153                         }
1154
1155                         vlen = BLI_array_len(loops);
1156
1157                         /* find the boundary of one of the split edges */
1158                         for (a = 1; a < vlen; a++) {
1159                                 if (!BMO_vert_flag_test(bm, loops[a - 1]->v, ELE_INNER) &&
1160                                     BMO_vert_flag_test(bm, loops[a]->v, ELE_INNER))
1161                                 {
1162                                         break;
1163                                 }
1164                         }
1165
1166                         if (BMO_vert_flag_test(bm, loops[(a + numcuts + 1) % vlen]->v, ELE_INNER)) {
1167                                 b = (a + numcuts + 1) % vlen;
1168                         }
1169                         else {
1170                                 /* find the boundary of the other edge. */
1171                                 for (j = 0; j < vlen; j++) {
1172                                         b = (j + a + numcuts + 1) % vlen;
1173                                         if (!BMO_vert_flag_test(bm, loops[b == 0 ? vlen - 1 : b - 1]->v, ELE_INNER) &&
1174                                             BMO_vert_flag_test(bm, loops[b]->v, ELE_INNER))
1175                                         {
1176                                                 break;
1177                                         }
1178                                 }
1179                         }
1180
1181                         b += numcuts - 1;
1182
1183                         BLI_array_grow_items(loops_split, numcuts);
1184                         for (j = 0; j < numcuts; j++) {
1185                                 bool ok = true;
1186
1187                                 /* Check for special case: [#32500]
1188                                  * This edge pair could be used by more than one face,
1189                                  * in this case it used to (2.63), split both faces along the same verts
1190                                  * while it could be calculated which face should do the split,
1191                                  * it's ambiguous, so in this case we're better off to skip them as exceptional cases
1192                                  * and not try to be clever guessing which face to cut up.
1193                                  *
1194                                  * To avoid this case we need to check:
1195                                  * Do the verts of each share a face besides the one we are subdividing,
1196                                  *  (but not connect to make an edge of that face).
1197                                  */
1198                                 {
1199                                         BMLoop *other_loop;
1200                                         BMIter other_fiter;
1201                                         BM_ITER_ELEM (other_loop, &other_fiter, loops[a]->v, BM_LOOPS_OF_VERT) {
1202                                                 if (other_loop->f != face) {
1203                                                         if (BM_vert_in_face(loops[b]->v, other_loop->f)) {
1204                                                                 /* we assume that these verts are not making an edge in the face */
1205                                                                 BLI_assert(other_loop->prev->v != loops[a]->v);
1206                                                                 BLI_assert(other_loop->next->v != loops[a]->v);
1207
1208                                                                 ok = false;
1209                                                                 break;
1210                                                         }
1211                                                 }
1212                                         }
1213                                 }
1214
1215
1216                                 if (ok == true) {
1217                                         loops_split[j][0] = loops[a];
1218                                         loops_split[j][1] = loops[b];
1219                                 }
1220                                 else {
1221                                         loops_split[j][0] = NULL;
1222                                         loops_split[j][1] = NULL;
1223                                 }
1224
1225                                 b = (b - 1) % vlen;
1226                                 a = (a + 1) % vlen;
1227                         }
1228
1229                         /* Since these are newly created vertices, we don't need to worry about them being legal,
1230                          * ... though there are some cases we _should_ check for
1231                          * - concave corner of an ngon.
1232                          * - 2 edges being used in 2+ ngons.
1233                          */
1234 //                      BM_face_splits_check_legal(bm, face, loops_split, BLI_array_len(loops_split));
1235
1236                         for (j = 0; j < BLI_array_len(loops_split); j++) {
1237                                 if (loops_split[j][0]) {
1238                                         BMFace *f_new;
1239                                         BLI_assert(BM_edge_exists(loops_split[j][0]->v, loops_split[j][1]->v) == NULL);
1240                                         f_new = BM_face_split(bm, face, loops_split[j][0], loops_split[j][1], &l_new, NULL, false);
1241                                         if (f_new) {
1242                                                 BMO_edge_flag_enable(bm, l_new->e, ELE_INNER);
1243                                         }
1244                                 }
1245                         }
1246
1247                         continue;
1248                 }
1249                 else if (!pat) {
1250                         continue;
1251                 }
1252
1253                 a = 0;
1254                 BM_ITER_ELEM_INDEX (l_new, &liter, face, BM_LOOPS_OF_FACE, j) {
1255                         if (l_new->v == fd->start) {
1256                                 a = j + 1;
1257                                 break;
1258                         }
1259                 }
1260
1261                 BLI_array_grow_items(verts, face->len);
1262
1263                 BM_ITER_ELEM_INDEX (l_new, &liter, face, BM_LOOPS_OF_FACE, j) {
1264                         b = (j - a + face->len) % face->len;
1265                         verts[b] = l_new->v;
1266                 }
1267
1268                 BM_CHECK_ELEMENT(face);
1269                 pat->connectexec(bm, face, verts, &params);
1270         }
1271
1272         /* copy original-geometry displacements to current coordinates */
1273         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
1274                 const float *co = BM_ELEM_CD_GET_VOID_P(v, params.shape_info.cd_vert_shape_offset_tmp);
1275                 copy_v3_v3(v->co, co);
1276         }
1277
1278         BM_data_layer_free_n(bm, &bm->vdata, CD_SHAPEKEY, params.shape_info.tmpkey);
1279
1280         BLI_stack_free(facedata);
1281         if (edges) BLI_array_free(edges);
1282         if (verts) BLI_array_free(verts);
1283         BLI_array_free(loops_split);
1284         BLI_array_free(loops);
1285
1286         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_inner.out", BM_ALL_NOLOOP, ELE_INNER);
1287         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_split.out", BM_ALL_NOLOOP, ELE_SPLIT);
1288
1289         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_ALL_NOLOOP, ELE_INNER | ELE_SPLIT | SUBD_SPLIT);
1290 }
1291
1292 /* editmesh-emulating function */
1293 void BM_mesh_esubdivide(
1294         BMesh *bm, const char edge_hflag,
1295         const float smooth, const short smooth_falloff, const bool use_smooth_even,
1296         const float fractal, const float along_normal,
1297         const int numcuts,
1298         const int seltype, const int cornertype,
1299         const short use_single_edge, const short use_grid_fill,
1300         const short use_only_quads,
1301         const int seed)
1302 {
1303         BMOperator op;
1304
1305         /* use_sphere isnt exposed here since its only used for new primitives */
1306         BMO_op_initf(bm, &op, BMO_FLAG_DEFAULTS,
1307                      "subdivide_edges edges=%he "
1308                      "smooth=%f smooth_falloff=%i use_smooth_even=%b "
1309                      "fractal=%f along_normal=%f "
1310                      "cuts=%i "
1311                      "quad_corner_type=%i "
1312                      "use_single_edge=%b use_grid_fill=%b "
1313                      "use_only_quads=%b "
1314                      "seed=%i",
1315                      edge_hflag,
1316                      smooth, smooth_falloff, use_smooth_even,
1317                      fractal, along_normal,
1318                      numcuts,
1319                      cornertype,
1320                      use_single_edge, use_grid_fill,
1321                      use_only_quads,
1322                      seed);
1323
1324         BMO_op_exec(bm, &op);
1325
1326         switch (seltype) {
1327                 case SUBDIV_SELECT_NONE:
1328                         break;
1329                 case SUBDIV_SELECT_ORIG:
1330                         /* set the newly created data to be selected */
1331                         BMO_slot_buffer_hflag_enable(bm, op.slots_out, "geom_inner.out", BM_ALL_NOLOOP, BM_ELEM_SELECT, true);
1332                         BM_mesh_select_flush(bm);
1333                         break;
1334                 case SUBDIV_SELECT_INNER:
1335                         BMO_slot_buffer_hflag_enable(bm, op.slots_out, "geom_inner.out", BM_EDGE | BM_VERT, BM_ELEM_SELECT, true);
1336                         break;
1337                 case SUBDIV_SELECT_LOOPCUT:
1338                         /* deselect input */
1339                         BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, false);
1340                         BMO_slot_buffer_hflag_enable(bm, op.slots_out, "geom_inner.out", BM_EDGE, BM_ELEM_SELECT, true);
1341                         break;
1342         }
1343
1344         BMO_op_finish(bm, &op);
1345 }
1346
1347 void bmo_bisect_edges_exec(BMesh *bm, BMOperator *op)
1348 {
1349         BMOIter siter;
1350         BMEdge *e;
1351         SubDParams params = {0};
1352
1353         params.numcuts = BMO_slot_int_get(op->slots_in, "cuts");
1354         params.op = op;
1355         params.slot_edge_percents = BMO_slot_get(op->slots_in, "edge_percents");
1356
1357         BM_data_layer_add(bm, &bm->vdata, CD_SHAPEKEY);
1358
1359         bmo_subd_init_shape_info(bm, &params);
1360
1361         /* tag edges in map */
1362         BMO_slot_map_to_flag(bm, op->slots_in, "edge_percents", BM_EDGE, EDGE_PERCENT);
1363
1364         /* go through and split edges */
1365         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
1366                 bm_subdivide_multicut(bm, e, &params, e->v1, e->v2);
1367         }
1368
1369         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_split.out", BM_ALL_NOLOOP, ELE_SPLIT);
1370
1371         BM_data_layer_free_n(bm, &bm->vdata, CD_SHAPEKEY, params.shape_info.tmpkey);
1372 }