810ecd10319979f3efb1e5bf49b29e081ab23f2b
[blender.git] / source / blender / bmesh / operators / subdivideop.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_arithb.h"
6 #include "BLI_rand.h"
7 #include "BLI_ghash.h"
8
9 #include "DNA_object_types.h"
10
11 #include "ED_mesh.h"
12
13 #include "bmesh.h"
14 #include "mesh_intern.h"
15 #include "subdivideop.h"
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21
22 #define SUBD_SPLIT      1
23
24 #define EDGE_PERCENT    2
25
26 /*I don't think new faces are flagged, currently, but
27   better safe than sorry.*/
28 #define FACE_NEW        2
29 #define FACE_CUSTOMFILL 4
30
31 /*stuff for the flag paramter.  note that
32   what used to live in "beauty" and
33   in "seltype" live here.  still have to
34   convert the beauty flags over, which
35   is why it starts at 128 (to avoid
36   collision).*/
37 #define SELTYPE_INNER   128
38
39 /*
40 NOTE: beauty has been renamed to flag!
41 */
42
43 /*generic subdivision rules:
44   
45   * two selected edges in a face should make a link
46     between them.
47
48   * one edge should do, what? make pretty topology, or just
49     split the edge only?
50 */
51
52 /* calculates offset for co, based on fractal, sphere or smooth settings  */
53 static void alter_co(float *co, BMEdge *edge, subdparams *params, float perc,
54                      BMVert *vsta, BMVert *vend)
55 {
56         float vec1[3], fac;
57         
58         if(params->flag & B_SMOOTH) {
59                 /* we calculate an offset vector vec1[], to be added to *co */
60                 float len, fac, nor[3], nor1[3], nor2[3];
61                 
62                 VecSubf(nor, vsta->co, vend->co);
63                 len= 0.5f*Normalize(nor);
64         
65                 VECCOPY(nor1, vsta->no);
66                 VECCOPY(nor2, vend->no);
67         
68                 /* cosine angle */
69                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
70                 
71                 vec1[0]= fac*nor1[0];
72                 vec1[1]= fac*nor1[1];
73                 vec1[2]= fac*nor1[2];
74         
75                 /* cosine angle */
76                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
77                 
78                 vec1[0]+= fac*nor2[0];
79                 vec1[1]+= fac*nor2[1];
80                 vec1[2]+= fac*nor2[2];
81                 
82                 vec1[0]*= params->rad*len;
83                 vec1[1]*= params->rad*len;
84                 vec1[2]*= params->rad*len;
85                 
86                 co[0] += vec1[0];
87                 co[1] += vec1[1];
88                 co[2] += vec1[2];
89         }
90         else {
91                 if(params->rad > 0.0) {   /* subdivide sphere */
92                         Normalize(co);
93                         co[0]*= params->rad;
94                         co[1]*= params->rad;
95                         co[2]*= params->rad;
96                 }
97                 else if(params->rad< 0.0) {  /* fractal subdivide */
98                         fac= params->rad* VecLenf(vsta->co, vend->co);
99                         vec1[0]= fac*(float)(0.5-BLI_drand());
100                         vec1[1]= fac*(float)(0.5-BLI_drand());
101                         vec1[2]= fac*(float)(0.5-BLI_drand());
102                         VecAddf(co, co, vec1);
103                 }
104
105         }
106 }
107
108 /* assumes in the edge is the correct interpolated vertices already */
109 /* percent defines the interpolation, rad and flag are for special options */
110 /* results in new vertex with correct coordinate, vertex normal and weight group info */
111 static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge, 
112                                         subdparams *params, float percent, 
113                                         BMEdge **out,BMVert *vsta,BMVert *vend)
114 {
115         BMVert *ev;
116 //      float co[3];
117         
118         ev = BM_Split_Edge(bm, edge->v1, edge, out, percent, 1);
119         if (params->flag & SELTYPE_INNER) BM_Select_Vert(bm, ev, 1);
120
121         /* offset for smooth or sphere or fractal */
122         alter_co(ev->co, edge, params, percent, vsta, vend);
123
124 #if 0 //TODO
125         /* clip if needed by mirror modifier */
126         if (edge->v1->f2) {
127                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
128                         co[0]= 0.0f;
129                 }
130                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
131                         co[1]= 0.0f;
132                 }
133                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
134                         co[2]= 0.0f;
135                 }
136         }
137 #endif  
138         
139         return ev;
140 }
141
142 static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, 
143                                 int curpoint, int totpoint, subdparams *params,
144                                 BMEdge **newe, BMVert *vsta, BMVert *vend)
145 {
146         BMVert *ev;
147         float percent;
148          
149         if (BMO_TestFlag(bm, edge, EDGE_PERCENT) && totpoint == 1)
150                 percent= *((float*)BLI_ghash_lookup(params->percenthash,edge));
151         else {
152                 percent= 1.0f/(float)(totpoint+1-curpoint);
153
154         }
155         
156         ev= bm_subdivide_edge_addvert(bm, edge, params, percent, 
157                                       newe, vsta, vend);
158         return ev;
159 }
160
161 static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, subdparams *params, 
162                                   BMVert *vsta, BMVert *vend) {
163         BMEdge *eed = edge, *newe;
164         BMVert *v;
165         int i, numcuts = params->numcuts;
166
167         for(i=0;i<numcuts;i++) {
168                 v = subdivideedgenum(bm, eed, i, params->numcuts, params, 
169                                      &newe, vsta, vend);
170                 BMO_SetFlag(bm, v, SUBD_SPLIT);
171                 BMO_SetFlag(bm, eed, SUBD_SPLIT);
172         }
173 }
174
175 /*note: the patterns are rotated as necassary to
176   match the input geometry.  they're based on the
177   pre-split state of the  face*/
178
179 /*
180      
181 v3---------v2
182 |          |
183 |          |
184 |          |
185 |          |
186 v4---v0---v1
187
188 */
189 static void q_1edge_split(BMesh *bm, BMFace *face,
190                           BMVert **verts, subdparams *params) {
191         BMFace *nf;
192         int i, add, numcuts = params->numcuts;
193
194         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
195         if (numcuts % 2==0) {
196                 add = 2;
197                 for (i=0; i<numcuts; i++) {
198                         if (i == numcuts/2) add -= 1;
199                         BM_Connect_Verts(bm, verts[i], verts[numcuts+add], 
200                                            &nf);
201                 }
202         } else {
203                 add = 2;
204                 for (i=0; i<numcuts; i++) {
205                         BM_Connect_Verts(bm, verts[i], verts[numcuts+add], 
206                                            &nf);
207                         if (i == numcuts/2) {
208                                 add -= 1;
209                                 BM_Connect_Verts(bm, verts[i], 
210                                                    verts[numcuts+add],
211                                                    &nf);
212                         }
213                 }
214
215         }
216 }
217
218 subdpattern q_1edge = {
219         {1, 0, 0, 0},
220         q_1edge_split,
221         4,
222 };
223
224
225 /*
226  
227 v4---v3---v2
228 |     s    |
229 |          |
230 |          |
231 |     s    |
232 v5---v0---v1
233
234 */
235
236 static void q_2edge_op_split(BMesh *bm, BMFace *face, BMVert **verts, 
237                              subdparams *params)
238 {
239         BMFace *nf;
240         int i, numcuts = params->numcuts;
241         
242         for (i=0; i<numcuts; i++) {
243                 BM_Connect_Verts(bm, verts[i],verts[(numcuts-i-1)+numcuts+2],
244                                    &nf);
245         }
246 }
247
248 subdpattern q_2edge_op = {
249         {1, 0, 1, 0},
250         q_2edge_op_split,
251         4,
252 };
253
254 /*
255 v6--------v5
256 |          |
257 |          |v4s
258 |          |v3s
259 |   s  s   |
260 v7-v0--v1-v2
261
262 */
263 static void q_2edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
264                           subdparams *params)
265 {
266         BMFace *nf;
267         int i, numcuts = params->numcuts;
268         
269         for (i=0; i<numcuts; i++) {
270                 BM_Connect_Verts(bm, verts[i], verts[numcuts+(numcuts-i)],
271                                    &nf);
272         }
273         BM_Connect_Verts(bm, verts[numcuts*2+3], verts[numcuts*2+1], &nf);
274 }
275
276 subdpattern q_2edge = {
277         {1, 1, 0, 0},
278         q_2edge_split,
279         4,
280 };
281
282 /*  s   s
283 v8--v7--v6-v5
284 |          |
285 |          v4 s
286 |          |
287 |          v3 s
288 |   s  s   |
289 v9-v0--v1-v2
290
291 */
292 static void q_3edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
293                           subdparams *params)
294 {
295         BMFace *nf;
296         int i, add=0, numcuts = params->numcuts;
297         
298         for (i=0; i<numcuts; i++) {
299                 if (i == numcuts/2) {
300                         if (numcuts % 2 != 0) {
301                                 BM_Connect_Verts(bm, verts[numcuts-i-1+add], 
302                                                  verts[i+numcuts+1], &nf);
303                         }
304                         add = numcuts*2+2;
305                 }
306                 BM_Connect_Verts(bm, verts[numcuts-i-1+add], 
307                                      verts[i+numcuts+1], &nf);
308         }
309
310         for (i=0; i<numcuts/2+1; i++) {
311                 BM_Connect_Verts(bm, verts[i],verts[(numcuts-i)+numcuts*2+1],
312                                    &nf);
313         }
314 }
315
316 subdpattern q_3edge = {
317         {1, 1, 1, 0},
318         q_3edge_split,
319         4,
320 };
321
322 /*
323  
324            v8--v7-v6--v5
325            |     s    |
326            |v9 s     s|v4
327 first line |          |   last line
328            |v10s s   s|v3
329            v11-v0--v1-v2
330
331            it goes from bottom up
332 */
333 static void q_4edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
334                           subdparams *params)
335 {
336         BMFace *nf;
337         BMVert *v, *v1, *v2;
338         BMEdge *e, *ne;
339         BMVert **lines;
340         int numcuts = params->numcuts;
341         int i, j, a, b, s=numcuts+2, totv=numcuts*4+4;
342
343         lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
344                                      "q_4edge_split");
345         /*build a 2-dimensional array of verts,
346           containing every vert (and all new ones)
347           in the face.*/
348
349         /*first line*/
350         for (i=0; i<numcuts+2; i++) {
351                 lines[i] = verts[numcuts*3+2+(numcuts-i+1)];
352         }
353
354         /*last line*/
355         for (i=0; i<numcuts+2; i++) {
356                 lines[(s-1)*s+i] = verts[numcuts+i];
357         }
358         
359         /*first and last members of middle lines*/
360         for (i=0; i<numcuts; i++) {
361                 a = i;
362                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
363                 
364                 e = BM_Connect_Verts(bm, verts[a], verts[b], &nf);
365                 if (params->flag & SELTYPE_INNER) {
366                         BM_Select_Edge(bm, e, 1);
367                         BM_Select_Face(bm, nf, 1);
368                 }
369                 
370                 v1 = lines[(i+1)*s] = verts[a];
371                 v2 = lines[(i+1)*s + s-1] = verts[b];
372
373                 for (a=0; a<numcuts; a++) {
374                         v = subdivideedgenum(bm, e, a, numcuts, params, &ne,
375                                              v1, v2);
376                         if (params->flag & SELTYPE_INNER) {
377                                 BM_Select_Edge(bm, ne, 1);
378                         }
379                         lines[(i+1)*s+a+1] = v;
380                 }
381         }
382
383         for (i=1; i<numcuts+2; i++) {
384                 for (j=1; j<numcuts+1; j++) {
385                         a = i*s + j;
386                         b = (i-1)*s + j;
387                         e = BM_Connect_Verts(bm, lines[a], lines[b], &nf);
388                         if (params->flag & SELTYPE_INNER) {
389                                 BM_Select_Edge(bm, e, 1);
390                                 BM_Select_Face(bm, nf, 1);
391                         }
392                 }
393         }
394
395         MEM_freeN(lines);
396 }
397
398 /*    v3
399      / \
400     /   \
401    /     \
402   /       \
403  /         \
404 v4--v0--v1--v2
405     s    s
406 */
407 static void t_1edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
408                           subdparams *params)
409 {
410         BMFace *nf;
411         int i, numcuts = params->numcuts;
412         
413         for (i=0; i<numcuts; i++) {
414                 BM_Connect_Verts(bm, verts[i], verts[numcuts+1], &nf);
415         }
416 }
417
418 subdpattern t_1edge = {
419         {1, 0, 0},
420         t_1edge_split,
421         3,
422 };
423
424 /*    v5
425      / \
426     /   \ v4 s
427    /     \
428   /       \ v3 s
429  /         \
430 v6--v0--v1--v2
431     s   s
432 */
433 static void t_2edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
434                           subdparams *params)
435 {
436         BMFace *nf;
437         int i, numcuts = params->numcuts;
438         
439         for (i=0; i<numcuts; i++) {
440                 BM_Connect_Verts(bm, verts[i], verts[numcuts+numcuts-i], &nf);
441         }
442 }
443
444 subdpattern t_2edge = {
445         {1, 1, 0},
446         t_2edge_split,
447         3,
448 };
449
450
451 /*     v5
452       / \
453  s v6/---\ v4 s
454     / \ / \
455 sv7/---v---\ v3 s
456   /  \/  \/ \
457  v8--v0--v1--v2
458     s    s
459 */
460 static void t_3edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
461                           subdparams *params)
462 {
463         BMFace *nf;
464         BMEdge *e, *ne;
465         BMVert ***lines, *v;
466         void *stackarr[1];
467         int i, j, a, b, numcuts = params->numcuts;
468         
469         /*number of verts in each line*/
470         lines = MEM_callocN(sizeof(void*)*(numcuts+2), "triangle vert table");
471         
472         lines[0] = (BMVert**) stackarr;
473         lines[0][0] = verts[numcuts*2+1];
474         
475         lines[1+numcuts] = MEM_callocN(sizeof(void*)*(numcuts+2), 
476                                        "triangle vert table 2");
477         for (i=0; i<numcuts; i++) {
478                 lines[1+numcuts][1+i] = verts[i];
479         }
480         lines[1+numcuts][0] = verts[numcuts*3+2];
481         lines[1+numcuts][1+numcuts] = verts[numcuts];
482
483         for (i=0; i<numcuts; i++) {
484                 lines[i+1] = MEM_callocN(sizeof(void*)*(2+i), 
485                                        "triangle vert table row");
486                 a = numcuts*2 + 2 + i;
487                 b = numcuts + numcuts - i;
488                 e = BM_Connect_Verts(bm, verts[a], verts[b], &nf);
489                 
490                 if (params->flag & SELTYPE_INNER) {
491                         BM_Select_Edge(bm, e, 1);
492                         BM_Select_Face(bm, nf, 1);
493                 }
494
495                 lines[i+1][0] = verts[a];
496                 lines[i+1][1+i] = verts[b];
497
498                 for (j=0; j<i; j++) {
499                         v = subdivideedgenum(bm, e, j, i, params, &ne,
500                                              verts[a], verts[b]);
501                         lines[i+1][j+1] = v;
502
503                         if (params->flag & SELTYPE_INNER) {
504                                 BM_Select_Edge(bm, ne, 1);
505                         }
506                 }
507         }
508         
509
510 /*     v5
511       / \
512  s v6/---\ v4 s
513     / \ / \
514 sv7/---v---\ v3 s
515   /  \/  \/ \
516  v8--v0--v1--v2
517     s    s
518 */
519         for (i=1; i<numcuts+1; i++) {
520                 for (j=0; j<i; j++) {
521                         e= BM_Connect_Verts(bm, lines[i][j], lines[i+1][j+1],
522                                            &nf);
523                         if (params->flag & SELTYPE_INNER) {
524                                 BM_Select_Edge(bm, e, 1);
525                                 BM_Select_Face(bm, nf, 1);
526                         }
527
528                         e= BM_Connect_Verts(bm,lines[i][j+1],lines[i+1][j+1],
529                                            &nf);
530                         if (params->flag & SELTYPE_INNER) {
531                                 BM_Select_Edge(bm, e, 1);
532                                 BM_Select_Face(bm, nf, 1);
533                         }
534                 }
535         }
536
537         for (i=1; i<numcuts+2; i++) {
538                 MEM_freeN(lines[i]);
539         }
540
541         MEM_freeN(lines);
542 }
543
544 subdpattern t_3edge = {
545         {1, 1, 1},
546         t_3edge_split,
547         3,
548 };
549
550
551 subdpattern q_4edge = {
552         {1, 1, 1, 1},
553         q_4edge_split,
554         4,
555 };
556
557 subdpattern *patterns[] = {
558         &q_1edge,
559         &q_2edge_op,
560         &q_4edge,
561         &q_3edge,
562         &q_2edge,
563         &t_1edge,
564         &t_2edge,
565         &t_3edge,
566 };
567
568 #define PLEN    (sizeof(patterns) / sizeof(void*))
569
570 typedef struct subd_facedata {
571         BMVert *start; subdpattern *pat;
572 } subd_facedata;
573
574 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
575 {
576         BMOpSlot *einput, *finput, *pinput;
577         BMEdge *edge, **edges = NULL;
578         V_DECLARE(edges);
579         BMFace *face;
580         BMLoop *nl;
581         BMVert **verts = NULL;
582         V_DECLARE(verts);
583         BMIter fiter, liter;
584         GHash *customfill_hash, *percent_hash; 
585         subdpattern *pat;
586         subdparams params;
587         subd_facedata *facedata = NULL;
588         V_DECLARE(facedata);
589         float rad;
590         int i, j, matched, a, b, numcuts, flag, selaction;
591         
592         BMO_Flag_Buffer(bmesh, op, BMOP_ESUBDIVIDE_EDGES, SUBD_SPLIT);
593         
594         numcuts = BMO_GetSlot(op, BMOP_ESUBDIVIDE_NUMCUTS)->data.i;
595         flag = BMO_GetSlot(op, BMOP_ESUBDIVIDE_FLAG)->data.i;
596         rad = BMO_GetSlot(op, BMOP_ESUBDIVIDE_RADIUS)->data.f;
597
598         selaction = BMO_GetSlot(op, BMOP_ESUBDIVIDE_SELACTION)->data.i;
599         if (selaction == SUBDIV_SELECT_INNER) flag |= SELTYPE_INNER;
600
601         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
602         /*first go through and tag edges*/
603         for (i=0; i<einput->len; i++) {
604                 edge = ((BMEdge**)einput->data.p)[i];
605                 BMO_SetFlag(bmesh, edge, SUBD_SPLIT);
606         }
607         
608         customfill_hash = BLI_ghash_new(BLI_ghashutil_ptrhash,
609                                         BLI_ghashutil_ptrcmp);
610         percent_hash = BLI_ghash_new(BLI_ghashutil_ptrhash,
611                                         BLI_ghashutil_ptrcmp);
612
613         /*process custom fill patterns*/
614         finput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_CUSTOMFILL_FACES);
615         pinput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_CUSTOMFILL_PATTERNS);
616         for (i=0; i<finput->len; i++) {
617                 face = ((BMFace**)finput->data.p)[i];
618                 BMO_SetFlag(bmesh, face, FACE_CUSTOMFILL);
619                 BLI_ghash_insert(customfill_hash, face,
620                                 ((void**)pinput->data.p)[i]);
621         }
622         
623         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_PERCENT_EDGES);
624         pinput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_PERCENT_VALUES);
625         
626         for (i=0; i<einput->len; i++) {
627                 edge = ((BMEdge**)einput->data.p)[i];
628                 BMO_SetFlag(bmesh, edge, EDGE_PERCENT);
629                 BLI_ghash_insert(percent_hash, edge, ((float*)pinput->data.p)+i);
630         }
631         
632         params.flag = flag;
633         params.numcuts = numcuts;
634         params.percenthash = percent_hash;
635         params.rad = rad;
636
637         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
638              face; face=BMIter_Step(&fiter)) {
639                 /*figure out which pattern to use*/
640
641                 V_RESET(edges);
642                 V_RESET(verts);
643                 i = 0;
644                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
645                      nl; nl=BMIter_Step(&liter)) {
646                         V_GROW(edges);
647                         V_GROW(verts);
648                         edges[i] = nl->e;
649                         verts[i] = nl->v;
650                         i++;
651                 }
652
653                 if (BMO_TestFlag(bmesh, face, FACE_CUSTOMFILL)) {
654                         pat = BLI_ghash_lookup(customfill_hash, face);
655                         for (i=0; i<pat->len; i++) {
656                                 matched = 1;
657                                 for (j=0; j<pat->len; j++) {
658                                         a = (j + i) % pat->len;
659                                         if ((!!BMO_TestFlag(bmesh, edges[a], SUBD_SPLIT))
660                                                 != (!!pat->seledges[j])) {
661                                                         matched = 0;
662                                                         break;
663                                         }
664                                 }
665                                 if (matched) {
666                                         V_GROW(facedata);
667                                         b = V_COUNT(facedata)-1;
668                                         facedata[b].pat = pat;
669                                         facedata[b].start = verts[i];
670                                         break;
671                                 }
672                         }
673                         if (!matched) {
674                                 /*if no match, append null element to array.*/
675                                 V_GROW(facedata);
676                         }
677
678                         /*obvously don't test for other patterns matching*/
679                         continue;
680                 }
681
682                 for (i=0; i<PLEN; i++) {
683                         pat = patterns[i];
684                         if (pat->len == face->len) {
685                                 for (a=0; a<pat->len; a++) {
686                                 matched = 1;
687                                 for (b=0; b<pat->len; b++) {
688                                         j = (b + a) % pat->len;
689                                         if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
690                                                 != (!!pat->seledges[b])) {
691                                                         matched = 0;
692                                                         break;
693                                         }
694                                 }
695                                 if (matched) break;
696                                 }
697                                 if (matched) {
698                                         V_GROW(facedata);
699                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
700                                         j = V_COUNT(facedata) - 1;
701                                         facedata[j].pat = pat;
702                                         facedata[j].start = verts[a];
703                                         break;
704                                 }
705                         }
706                 }
707         }
708
709         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
710
711         /*go through and split edges*/
712         for (i=0; i<einput->len; i++) {
713                 edge = ((BMEdge**)einput->data.p)[i];
714                 bm_subdivide_multicut(bmesh, edge,&params, edge->v1, edge->v2);
715                 //BM_Split_Edge_Multi(bmesh, edge, numcuts);
716         }
717
718         //if (facedata) V_FREE(facedata);
719         //return;
720
721         i = 0;
722         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
723              face; face=BMIter_Step(&fiter)) {
724                 /*figure out which pattern to use*/
725                 V_RESET(verts);
726                 if (BMO_TestFlag(bmesh, face, SUBD_SPLIT) == 0) continue;
727
728                 pat = facedata[i].pat;
729                 if (!pat) continue;
730
731                 j = a = 0;
732                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
733                      nl; nl=BMIter_Step(&liter)) {
734                         if (nl->v == facedata[i].start) {
735                                 a = j+1;
736                                 break;
737                         }
738                         j++;
739                 }
740
741                 for (j=0; j<face->len; j++) {
742                         V_GROW(verts);
743                 }
744                 
745                 j = 0;
746                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
747                      nl; nl=BMIter_Step(&liter)) {
748                         b = (j-a+face->len) % face->len;
749                         verts[b] = nl->v;
750                         j += 1;
751                 }
752                 
753                 pat->connectexec(bmesh, face, verts, &params);
754                 i++;
755         }
756
757         if (facedata) V_FREE(facedata);
758         if (edges) V_FREE(edges);
759         if (verts) V_FREE(verts);
760 }
761
762 /*editmesh-emulating function*/
763 void BM_esubdivideflag(Object *obedit, BMesh *bm, int selflag, float rad, 
764                        int flag, int numcuts, int seltype) {
765         BMOperator op;
766
767         BMO_Init_Op(&op, BMOP_ESUBDIVIDE);
768         
769         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_NUMCUTS, numcuts);
770         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_FLAG, flag);
771         BMO_Set_Float(&op, BMOP_ESUBDIVIDE_RADIUS, rad);
772         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_SELACTION, seltype);
773         BMO_HeaderFlag_To_Slot(bm, &op, BMOP_ESUBDIVIDE_EDGES, selflag, BM_EDGE);
774         
775         BMO_Exec_Op(bm, &op);
776         BMO_Finish_Op(bm, &op);
777 }
778
779 void BM_esubdivideflag_conv(Object *obedit,EditMesh *em,int selflag, float rad, 
780                        int flag, int numcuts, int seltype) {
781         BMesh *bm = editmesh_to_bmesh(em);
782         EditMesh *em2;
783
784         BM_esubdivideflag(obedit, bm, selflag, rad, flag, numcuts, seltype);
785         em2 = bmesh_to_editmesh(bm);
786         
787         free_editMesh(em);
788         *em = *em2;
789         MEM_freeN(em2);
790         BM_Free_Mesh(bm);
791 }