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