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