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