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