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