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