Code Cleanup: style change only
[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 **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 (nf) *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 displacement*/
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      
341 v3---------v2
342 |          |
343 |          |
344 |          |
345 |          |
346 v4---v0---v1
347
348 */
349 static void quad_1edge_split(BMesh *bm, BMFace *UNUSED(face),
350                              BMVert **verts, const subdparams *params)
351 {
352         BMFace *nf;
353         int i, add, numcuts = params->numcuts;
354
355         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
356         if (numcuts % 2==0) {
357                 add = 2;
358                 for (i=0; i<numcuts; i++) {
359                         if (i == numcuts/2) add -= 1;
360                         connect_smallest_face(bm, verts[i], verts[numcuts+add], 
361                                            &nf);
362                 }
363         }
364         else {
365                 add = 2;
366                 for (i=0; i<numcuts; i++) {
367                         connect_smallest_face(bm, verts[i], verts[numcuts+add], 
368                                            &nf);
369                         if (i == numcuts/2) {
370                                 add -= 1;
371                                 connect_smallest_face(bm, verts[i], 
372                                                    verts[numcuts+add],
373                                                    &nf);
374                         }
375                 }
376
377         }
378 }
379
380 static subdpattern quad_1edge = {
381         {1, 0, 0, 0},
382         quad_1edge_split,
383         4,
384 };
385
386
387 /*
388 v6--------v5
389 |          |
390 |          |v4s
391 |          |v3s
392 |   s  s   |
393 v7-v0--v1-v2
394
395 */
396 static void quad_2edge_split_path(BMesh *bm, BMFace *UNUSED(face), BMVert **verts, 
397                                   const subdparams *params)
398 {
399         BMFace *nf;
400         int i, numcuts = params->numcuts;
401         
402         for (i=0; i<numcuts; i++) {
403                 connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
404                                    &nf);
405         }
406         connect_smallest_face(bm, verts[numcuts*2+3], verts[numcuts*2+1], &nf);
407 }
408
409 static subdpattern quad_2edge_path = {
410         {1, 1, 0, 0},
411         quad_2edge_split_path,
412         4,
413 };
414
415 /*
416 v6--------v5
417 |          |
418 |          |v4s
419 |          |v3s
420 |   s  s   |
421 v7-v0--v1-v2
422
423 */
424 static void quad_2edge_split_innervert(BMesh *bm, BMFace *UNUSED(face), BMVert **verts, 
425                                        const subdparams *params)
426 {
427         BMFace *nf;
428         BMVert *v, *lastv;
429         BMEdge *e, *ne, olde;
430         int i, numcuts = params->numcuts;
431         
432         lastv = verts[numcuts];
433
434         for (i=numcuts-1; i>=0; i--) {
435                 e = connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
436                                    &nf);
437                 
438                 olde = *e;
439                 v = bm_subdivide_edge_addvert(bm, e, &olde, params, 0.5f, 0.5f, &ne, e->v1, e->v2);
440
441                 if (i != numcuts-1)
442                         connect_smallest_face(bm, lastv, v, &nf);
443                 
444                 lastv = v;
445         }
446
447         connect_smallest_face(bm, lastv, verts[numcuts*2+2], &nf);      
448 }
449
450 static subdpattern quad_2edge_innervert = {
451         {1, 1, 0, 0},
452         quad_2edge_split_innervert,
453         4,
454 };
455
456 /*
457 v6--------v5
458 |          |
459 |          |v4s
460 |          |v3s
461 |   s  s   |
462 v7-v0--v1-v2
463
464 */
465 static void quad_2edge_split_fan(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
466                                  const subdparams *params)
467 {
468         BMFace *nf;
469         /* BMVert *v; */               /* UNUSED */
470         /* BMVert *lastv= verts[2]; */ /* UNUSED */
471         /* BMEdge *e, *ne; */          /* UNUSED */
472         int i, numcuts = params->numcuts;
473
474         for (i=0; i<numcuts; i++) {
475                 connect_smallest_face(bm, verts[i], verts[numcuts*2+2], &nf);
476                 connect_smallest_face(bm, verts[numcuts+(numcuts-i)],
477                                       verts[numcuts*2+2], &nf);
478         }
479 }
480
481 static subdpattern quad_2edge_fan = {
482         {1, 1, 0, 0},
483         quad_2edge_split_fan,
484         4,
485 };
486
487 /*  s   s
488 v8--v7--v6-v5
489 |          |
490 |          v4 s
491 |          |
492 |          v3 s
493 |   s  s   |
494 v9-v0--v1-v2
495
496 */
497 static void quad_3edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
498                              const subdparams *params)
499 {
500         BMFace *nf;
501         int i, add=0, numcuts = params->numcuts;
502         
503         for (i=0; i<numcuts; i++) {
504                 if (i == numcuts/2) {
505                         if (numcuts % 2 != 0) {
506                                 connect_smallest_face(bm, verts[numcuts-i-1+add], 
507                                                  verts[i+numcuts+1], &nf);
508                         }
509                         add = numcuts*2+2;
510                 }
511                 connect_smallest_face(bm, verts[numcuts-i-1+add], 
512                                      verts[i+numcuts+1], &nf);
513         }
514
515         for (i=0; i<numcuts/2+1; i++) {
516                 connect_smallest_face(bm, verts[i],verts[(numcuts-i)+numcuts*2+1],
517                                    &nf);
518         }
519 }
520
521 static subdpattern quad_3edge = {
522         {1, 1, 1, 0},
523         quad_3edge_split,
524         4,
525 };
526
527 /*
528  
529            v8--v7-v6--v5
530            |     s    |
531            |v9 s     s|v4
532 first line |          |   last line
533            |v10s s   s|v3
534            v11-v0--v1-v2
535
536            it goes from bottom up
537 */
538 static void quad_4edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
539                                  const subdparams *params)
540 {
541         BMFace *nf;
542         BMVert *v, *v1, *v2;
543         BMEdge *e, *ne, temp;
544         BMVert **lines;
545         int numcuts = params->numcuts;
546         int i, j, a, b, s=numcuts+2 /* , totv=numcuts*4+4 */;
547
548         lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
549                                      "q_4edge_split");
550         /*build a 2-dimensional array of verts,
551           containing every vert (and all new ones)
552           in the face.*/
553
554         /*first line*/
555         for (i=0; i<numcuts+2; i++) {
556                 lines[i] = verts[numcuts*3+2+(numcuts-i+1)];
557         }
558
559         /*last line*/
560         for (i=0; i<numcuts+2; i++) {
561                 lines[(s-1)*s+i] = verts[numcuts+i];
562         }
563         
564         /*first and last members of middle lines*/
565         for (i=0; i<numcuts; i++) {
566                 a = i;
567                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
568                 
569                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
570                 if (!e)
571                         continue;
572
573                 BMO_SetFlag(bm, e, ELE_INNER);
574                 BMO_SetFlag(bm, nf, ELE_INNER);
575
576                 
577                 v1 = lines[(i+1)*s] = verts[a];
578                 v2 = lines[(i+1)*s + s-1] = verts[b];
579                 
580                 temp = *e;
581                 for (a=0; a<numcuts; a++) {
582                         v = subdivideedgenum(bm, e, &temp, a, numcuts, params, &ne,
583                                             v1, v2);
584                         if (!v)
585                                 bmesh_error();
586
587                         BMO_SetFlag(bm, ne, ELE_INNER);
588                         lines[(i+1)*s+a+1] = v;
589                 }
590         }
591
592         for (i=1; i<numcuts+2; i++) {
593                 for (j=1; j<numcuts+1; j++) {
594                         a = i*s + j;
595                         b = (i-1)*s + j;
596                         e = connect_smallest_face(bm, lines[a], lines[b], &nf);
597                         if (!e)
598                                 continue;
599
600                         BMO_SetFlag(bm, e, ELE_INNER);
601                         BMO_SetFlag(bm, nf, ELE_INNER);
602                 }
603         }
604
605         MEM_freeN(lines);
606 }
607
608 /*    v3
609      / \
610     /   \
611    /     \
612   /       \
613  /         \
614 v4--v0--v1--v2
615     s    s
616 */
617 static void tri_1edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
618                             const subdparams *params)
619 {
620         BMFace *nf;
621         int i, numcuts = params->numcuts;
622         
623         for (i=0; i<numcuts; i++) {
624                 connect_smallest_face(bm, verts[i], verts[numcuts+1], &nf);
625         }
626 }
627
628 static subdpattern tri_1edge = {
629         {1, 0, 0},
630         tri_1edge_split,
631         3,
632 };
633
634 /*     v5
635       / \
636  s v6/---\ v4 s
637     / \ / \
638 sv7/---v---\ v3 s
639   /  \/  \/ \
640  v8--v0--v1--v2
641     s    s
642 */
643 static void tri_3edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
644                                 const subdparams *params)
645 {
646         BMFace *nf;
647         BMEdge *e, *ne, temp;
648         BMVert ***lines, *v, ov1, ov2;
649         void *stackarr[1];
650         int i, j, a, b, numcuts = params->numcuts;
651         
652         /*number of verts in each line*/
653         lines = MEM_callocN(sizeof(void*)*(numcuts+2), "triangle vert table");
654         
655         lines[0] = (BMVert**) stackarr;
656         lines[0][0] = verts[numcuts*2+1];
657         
658         lines[1+numcuts] = MEM_callocN(sizeof(void*)*(numcuts+2), 
659                                        "triangle vert table 2");
660         for (i=0; i<numcuts; i++) {
661                 lines[1+numcuts][1+i] = verts[i];
662         }
663         lines[1+numcuts][0] = verts[numcuts*3+2];
664         lines[1+numcuts][1+numcuts] = verts[numcuts];
665
666         for (i=0; i<numcuts; i++) {
667                 lines[i+1] = MEM_callocN(sizeof(void*)*(2+i), 
668                                        "triangle vert table row");
669                 a = numcuts*2 + 2 + i;
670                 b = numcuts + numcuts - i;
671                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
672                 if (!e) goto cleanup;
673
674                 BMO_SetFlag(bm, e, ELE_INNER);
675                 BMO_SetFlag(bm, nf, ELE_INNER);
676
677                 lines[i+1][0] = verts[a];
678                 lines[i+1][1+i] = verts[b];
679                 
680                 temp = *e;
681                 ov1 = *verts[a];
682                 ov2 = *verts[b];
683                 temp.v1 = &ov1;
684                 temp.v2 = &ov2;
685                 for (j=0; j<i; j++) {
686                         v = subdivideedgenum(bm, e, &temp, j, i, params, &ne,
687                                              verts[a], verts[b]);
688                         lines[i+1][j+1] = v;
689
690                         BMO_SetFlag(bm, ne, ELE_INNER);
691                 }
692         }
693         
694
695 /*     v5
696       / \
697  s v6/---\ v4 s
698     / \ / \
699 sv7/---v---\ v3 s
700   /  \/  \/ \
701  v8--v0--v1--v2
702     s    s
703 */
704         for (i=1; i<numcuts+1; i++) {
705                 for (j=0; j<i; j++) {
706                         e= connect_smallest_face(bm, lines[i][j], lines[i+1][j+1],
707                                            &nf);
708
709                         BMO_SetFlag(bm, e, ELE_INNER);
710                         BMO_SetFlag(bm, nf, ELE_INNER);
711
712                         e= connect_smallest_face(bm,lines[i][j+1],lines[i+1][j+1],
713                                            &nf);
714
715                         BMO_SetFlag(bm, e, ELE_INNER);
716                         BMO_SetFlag(bm, nf, ELE_INNER);
717                 }
718         }
719
720 cleanup:
721         for (i=1; i<numcuts+2; i++) {
722                 if (lines[i]) MEM_freeN(lines[i]);
723         }
724
725         MEM_freeN(lines);
726 }
727
728 static subdpattern tri_3edge = {
729         {1, 1, 1},
730         tri_3edge_subdivide,
731         3,
732 };
733
734
735 static subdpattern quad_4edge = {
736         {1, 1, 1, 1},
737         quad_4edge_subdivide,
738         4,
739 };
740
741 static subdpattern *patterns[] = {
742         NULL, //quad single edge pattern is inserted here
743         NULL, //quad corner vert pattern is inserted here
744         NULL, //tri single edge pattern is inserted here
745         NULL,
746         &quad_3edge,
747         NULL,
748 };
749
750 #define PLEN    (sizeof(patterns) / sizeof(void*))
751
752 typedef struct subd_facedata {
753         BMVert *start; subdpattern *pat;
754         int totedgesel; //only used if pat was NULL, e.g. no pattern was found
755         BMFace *face;
756 } subd_facedata;
757
758 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
759 {
760         BMOpSlot *einput;
761         subdpattern *pat;
762         subdparams params;
763         subd_facedata *facedata = NULL;
764         BMIter viter, fiter, liter;
765         BMVert *v, **verts = NULL;
766         BMEdge *edge, **edges = NULL;
767         BMLoop *nl, *l, **splits = NULL, **loops = NULL;
768         BMFace *face;
769         BLI_array_declare(splits);
770         BLI_array_declare(loops);
771         BLI_array_declare(facedata);
772         BLI_array_declare(edges);
773         BLI_array_declare(verts);
774         float smooth, fractal;
775         int beauty, cornertype, singleedge, gridfill;
776         int skey, seed, i, j, matched, a, b, numcuts, totesel;
777         
778         BMO_Flag_Buffer(bmesh, op, "edges", SUBD_SPLIT, BM_EDGE);
779         
780         numcuts = BMO_Get_Int(op, "numcuts");
781         seed = BMO_Get_Int(op, "seed");
782         smooth = BMO_Get_Float(op, "smooth");
783         fractal = BMO_Get_Float(op, "fractal");
784         beauty = BMO_Get_Int(op, "beauty");
785         cornertype = BMO_Get_Int(op, "quadcornertype");
786         singleedge = BMO_Get_Int(op, "singleedge");
787         gridfill = BMO_Get_Int(op, "gridfill");
788         
789         BLI_srandom(seed);
790         
791         patterns[1] = NULL;
792         //straight cut is patterns[1] == NULL
793         switch (cornertype) {
794                 case SUBD_PATH:
795                         patterns[1] = &quad_2edge_path;
796                         break;
797                 case SUBD_INNERVERT:
798                         patterns[1] = &quad_2edge_innervert;
799                         break;
800                 case SUBD_FAN:
801                         patterns[1] = &quad_2edge_fan;
802                         break;
803         }
804         
805         if (singleedge) {
806                 patterns[0] = &quad_1edge;
807                 patterns[2] = &tri_1edge;
808         }
809         else {
810                 patterns[0] = NULL;
811                 patterns[2] = NULL;
812         }
813
814         if (gridfill) {
815                 patterns[3] = &quad_4edge;
816                 patterns[5] = &tri_3edge;
817         }
818         else {
819                 patterns[3] = NULL;
820                 patterns[5] = NULL;
821         }
822         
823         /*add a temporary shapekey layer to store displacements on current geometry*/
824         BM_add_data_layer(bmesh, &bmesh->vdata, CD_SHAPEKEY);
825         skey = CustomData_number_of_layers(&bmesh->vdata, CD_SHAPEKEY)-1;
826         
827         BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
828                 float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
829                 copy_v3_v3(co, v->co);
830         }
831
832         /*first go through and tag edges*/
833         BMO_Flag_To_Slot(bmesh, op, "edges",
834                  SUBD_SPLIT, BM_EDGE);
835
836         params.numcuts = numcuts;
837         params.op = op;
838         params.smooth = smooth;
839         params.seed = seed;
840         params.fractal = fractal;
841         params.beauty = beauty;
842         params.origkey = skey;
843         params.off[0] = (float)BLI_drand()*200.0f;
844         params.off[1] = (float)BLI_drand()*200.0f;
845         params.off[2] = (float)BLI_drand()*200.0f;
846         
847         BMO_Mapping_To_Flag(bmesh, op, "custompatterns",
848                             FACE_CUSTOMFILL);
849
850         BMO_Mapping_To_Flag(bmesh, op, "edgepercents",
851                             EDGE_PERCENT);
852
853         for (face=BMIter_New(&fiter, bmesh, BM_FACES_OF_MESH, NULL);
854              face; face=BMIter_Step(&fiter)) {
855                 BMEdge *e1 = NULL, *e2 = NULL;
856                 float vec1[3], vec2[3];
857
858                 /*figure out which pattern to use*/
859
860                 BLI_array_empty(edges);
861                 BLI_array_empty(verts);
862                 matched = 0;
863
864                 i = 0;
865                 totesel = 0;
866                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
867                      nl; nl=BMIter_Step(&liter)) {
868                         BLI_array_growone(edges);
869                         BLI_array_growone(verts);
870                         edges[i] = nl->e;
871                         verts[i] = nl->v;
872
873                         if (BMO_TestFlag(bmesh, edges[i], SUBD_SPLIT)) {
874                                 if (!e1) e1 = edges[i];
875                                 else e2 = edges[i];
876
877                                 totesel++;
878                         }
879
880                         i++;
881                 }
882
883                 /*make sure the two edges have a valid angle to each other*/
884                 if (totesel == 2 && BM_Edge_Share_Vert(e1, e2)) {
885                         float angle;
886
887                         sub_v3_v3v3(vec1, e1->v2->co, e1->v1->co);
888                         sub_v3_v3v3(vec2, e2->v2->co, e2->v1->co);
889                         normalize_v3(vec1);
890                         normalize_v3(vec2);
891
892                         angle = dot_v3v3(vec1, vec2);
893                         angle = fabsf(angle);
894                         if (fabsf(angle - 1.0f) < 0.01f) {
895                                 totesel = 0;
896                         }
897                 }
898
899                 if (BMO_TestFlag(bmesh, face, FACE_CUSTOMFILL)) {
900                         pat = BMO_Get_MapData(bmesh, op, 
901                                     "custompatterns", face);
902                         for (i=0; i<pat->len; i++) {
903                                 matched = 1;
904                                 for (j=0; j<pat->len; j++) {
905                                         a = (j + i) % pat->len;
906                                         if ((!!BMO_TestFlag(bmesh, edges[a], SUBD_SPLIT))
907                                                 != (!!pat->seledges[j])) {
908                                                         matched = 0;
909                                                         break;
910                                         }
911                                 }
912                                 if (matched) {
913                                         BLI_array_growone(facedata);
914                                         b = BLI_array_count(facedata)-1;
915                                         facedata[b].pat = pat;
916                                         facedata[b].start = verts[i];
917                                         facedata[b].face = face;
918                                         facedata[b].totedgesel = totesel;
919                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
920                                         break;
921                                 }
922                         }
923
924                         /*obvously don't test for other patterns matching*/
925                         continue;
926                 }
927
928                 for (i=0; i<PLEN; i++) {
929                         pat = patterns[i];
930                         if (!pat) continue;
931
932                         if (pat->len == face->len) {
933                                 for (a=0; a<pat->len; a++) {
934                                         matched = 1;
935                                         for (b=0; b<pat->len; b++) {
936                                                 j = (b + a) % pat->len;
937                                                 if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
938                                                         != (!!pat->seledges[b])) {
939                                                                 matched = 0;
940                                                                 break;
941                                                 }
942                                         }
943                                         if (matched) break;
944                                 }
945                                 if (matched) {
946                                         BLI_array_growone(facedata);
947                                         j = BLI_array_count(facedata) - 1;
948
949                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
950
951                                         facedata[j].pat = pat;
952                                         facedata[j].start = verts[a];
953                                         facedata[j].face = face;
954                                         facedata[j].totedgesel = totesel;
955                                         break;
956                                 }
957                         }
958                 
959                 }
960                 
961                 if (!matched && totesel) {
962                         BLI_array_growone(facedata);
963                         j = BLI_array_count(facedata) - 1;
964                         
965                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
966                         facedata[j].totedgesel = totesel;
967                         facedata[j].face = face;
968                 }
969         }
970
971         einput = BMO_GetSlot(op, "edges");
972
973         /*go through and split edges*/
974         for (i=0; i<einput->len; i++) {
975                 edge = ((BMEdge**)einput->data.p)[i];
976                 bm_subdivide_multicut(bmesh, edge, &params, edge->v1, edge->v2);
977         }
978
979         i = 0;
980         for (i=0; i<BLI_array_count(facedata); i++) {
981                 face = facedata[i].face;
982
983                 /*figure out which pattern to use*/
984                 BLI_array_empty(verts);
985
986                 pat = facedata[i].pat;
987
988                 if (!pat && facedata[i].totedgesel == 2) {
989                         int vlen;
990                         
991                         /*ok, no pattern.  we still may be able to do something.*/
992                         BLI_array_empty(loops);
993                         BLI_array_empty(splits);
994
995                         /*for case of two edges, connecting them shouldn't be too hard*/
996                         BM_ITER(l, &liter, bmesh, BM_LOOPS_OF_FACE, face) {
997                                 BLI_array_growone(loops);
998                                 loops[BLI_array_count(loops)-1] = l;
999                         }
1000                         
1001                         vlen = BLI_array_count(loops);
1002
1003                         /*find the boundary of one of the split edges*/
1004                         for (a=1; a<vlen; a++) {
1005                                 if (!BMO_TestFlag(bmesh, loops[a-1]->v, ELE_INNER) 
1006                                     && BMO_TestFlag(bmesh, loops[a]->v, ELE_INNER))
1007                                         break;
1008                         }
1009                         
1010                         if (BMO_TestFlag(bmesh, loops[(a+numcuts+1)%vlen]->v, ELE_INNER)) {
1011                                 b = (a+numcuts+1)%vlen;
1012                         }
1013                         else {
1014                                 /*find the boundary of the other edge.*/
1015                                 for (j=0; j<vlen; j++) {
1016                                         b = (j + a + numcuts + 1) % vlen;
1017                                         if (!BMO_TestFlag(bmesh, loops[b==0 ? vlen-1 : b-1]->v, ELE_INNER)
1018                                             && BMO_TestFlag(bmesh, loops[b]->v, ELE_INNER))
1019                                                 break;
1020                                 }
1021                         }
1022                         
1023                         b += numcuts - 1;
1024
1025                         for (j=0; j<numcuts; j++) {
1026                                 BLI_array_growone(splits);
1027                                 splits[BLI_array_count(splits)-1] = loops[a];
1028                                 
1029                                 BLI_array_growone(splits);
1030                                 splits[BLI_array_count(splits)-1] = loops[b];
1031
1032                                 b = (b-1) % vlen;
1033                                 a = (a+1) % vlen;
1034                         }
1035                         
1036                         //BM_LegalSplits(bmesh, face, splits, BLI_array_count(splits)/2);
1037
1038                         for (j=0; j<BLI_array_count(splits)/2; j++) {
1039                                 if (splits[j*2]) {
1040                                         /* BMFace *nf= */ /* UNUSED */
1041                                         BM_Split_Face(bmesh, face, splits[j*2]->v, splits[j*2+1]->v, &nl, NULL);
1042                                 }
1043                         }
1044
1045                         continue;
1046                 }
1047                 else if (!pat) {
1048                         continue;
1049                 }
1050
1051                 j = a = 0;
1052                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
1053                      nl; nl=BMIter_Step(&liter)) {
1054                         if (nl->v == facedata[i].start) {
1055                                 a = j+1;
1056                                 break;
1057                         }
1058                         j++;
1059                 }
1060
1061                 for (j=0; j<face->len; j++) {
1062                         BLI_array_growone(verts);
1063                 }
1064                 
1065                 j = 0;
1066                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
1067                      nl; nl=BMIter_Step(&liter)) {
1068                         b = (j-a+face->len) % face->len;
1069                         verts[b] = nl->v;
1070                         j += 1;
1071                 }
1072                                         
1073                 BM_CHECK_ELEMENT(bmesh, face);
1074                 pat->connectexec(bmesh, face, verts, &params);
1075         }
1076
1077         /*copy original-geometry displacements to current coordinates*/
1078         BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
1079                 float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
1080                 copy_v3_v3(v->co, co);
1081         }
1082
1083         BM_free_data_layer_n(bmesh, &bmesh->vdata, CD_SHAPEKEY, skey);
1084         
1085         if (facedata) BLI_array_free(facedata);
1086         if (edges) BLI_array_free(edges);
1087         if (verts) BLI_array_free(verts);
1088         BLI_array_free(splits);
1089         BLI_array_free(loops);
1090
1091         BMO_Flag_To_Slot(bmesh, op, "outinner",
1092                          ELE_INNER, BM_ALL);    
1093         BMO_Flag_To_Slot(bmesh, op, "outsplit",
1094                          ELE_SPLIT, BM_ALL);
1095         
1096         BMO_Flag_To_Slot(bmesh, op, "geomout",
1097                          ELE_INNER|ELE_SPLIT|SUBD_SPLIT, BM_ALL);
1098 }
1099
1100 /*editmesh-emulating function*/
1101 void BM_esubdivideflag(Object *UNUSED(obedit), BMesh *bm, int flag, float smooth,
1102                float fractal, int beauty, int numcuts, 
1103                int seltype, int cornertype, int singleedge, 
1104                int gridfill, int seed)
1105 {
1106         BMOperator op;
1107         
1108         BMO_InitOpf(bm, &op, "esubd edges=%he smooth=%f fractal=%f "
1109                              "beauty=%d numcuts=%d quadcornertype=%d singleedge=%d "
1110                              "gridfill=%d seed=%d",
1111                              flag, smooth, fractal, beauty, numcuts,
1112                              cornertype, singleedge, gridfill, seed);
1113         
1114         BMO_Exec_Op(bm, &op);
1115         
1116         if (seltype == SUBDIV_SELECT_INNER) {
1117                 BMOIter iter;
1118                 BMHeader *ele;
1119                 // int i;
1120                 
1121                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
1122                 for ( ; ele; ele=BMO_IterStep(&iter)) {
1123                         BM_Select(bm, ele, TRUE);
1124                 }
1125         }
1126         else if (seltype == SUBDIV_SELECT_LOOPCUT) {
1127                 BMOIter iter;
1128                 BMHeader *ele;
1129                 // int i;
1130                 
1131                 /*deselect input*/
1132                 BM_clear_flag_all(bm, BM_SELECT);
1133
1134                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
1135                 for ( ; ele; ele=BMO_IterStep(&iter)) {
1136                         BM_Select(bm, ele, TRUE);
1137
1138                         if (ele->htype == BM_VERT) {
1139                                 BMEdge *e;
1140                                 BMIter eiter;
1141
1142                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, ele) {
1143                                         if (!BM_TestHFlag(e, BM_SELECT) && BM_TestHFlag(e->v1, BM_SELECT) 
1144                                                                                                         && BM_TestHFlag(e->v2, BM_SELECT)) {
1145                                                 BM_Select(bm, e, TRUE);
1146                                                 bm->totedgesel += 1;
1147                                         }
1148                                         else if (BM_TestHFlag(e, BM_SELECT) && (!BM_TestHFlag(e->v1, BM_SELECT)
1149                                                                                                                   || !BM_TestHFlag(e->v2, BM_SELECT))) {
1150                                                 BM_Select(bm, e, FALSE);
1151                                                 bm->totedgesel -= 1;
1152                                         }
1153                                 }
1154                         }
1155                 }
1156         }
1157
1158         BMO_Finish_Op(bm, &op);
1159 }
1160
1161 void esplit_exec(BMesh *bm, BMOperator *op)
1162 {
1163         BMOIter siter;
1164         BMEdge *e;
1165         subdparams params;
1166         int skey;
1167         
1168         params.numcuts = BMO_GetSlot(op, "numcuts")->data.i;
1169         params.op = op;
1170         
1171         BM_add_data_layer(bm, &bm->vdata, CD_SHAPEKEY);
1172         skey = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY)-1;
1173         
1174         params.origkey = skey;
1175
1176         /*go through and split edges*/
1177         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1178                 bm_subdivide_multicut(bm, e, &params, e->v1, e->v2);
1179         }
1180
1181         BMO_Flag_To_Slot(bm, op, "outsplit",
1182                          ELE_SPLIT, BM_ALL);
1183
1184         BM_free_data_layer_n(bm, &bm->vdata, CD_SHAPEKEY, skey);
1185 }