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