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