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