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