388ced2fbb62f202590cc0df7a9fb49d3548aca2
[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 /*subdivide future development notes:
23   each pattern should be able to be disabled
24   by the client code, and the client code 
25   should be able to pass in custom patterns.
26
27   so you can configure it anywhere from a simple
28   edge connect tool, to what's in 2.49a.
29  */
30
31 /*flags for all elements share a common bitfield space*/
32 #define SUBD_SPLIT      1
33
34 #define EDGE_PERCENT    2
35
36 /*I don't think new faces are flagged, currently, but
37   better safe than sorry.*/
38 #define FACE_NEW        4
39 #define FACE_CUSTOMFILL 8
40 #define ELE_INNER       16
41 #define ELE_SPLIT       32
42 #define ELE_CONNECT     64
43
44 /*stuff for the flag paramter.  note that
45   what used to live in "beauty" and
46   in "seltype" live here.  still have to
47   convert the beauty flags over, which
48   is why it starts at 128 (to avoid
49   collision).*/
50 #define SELTYPE_INNER   128
51
52 /*
53 NOTE: beauty has been renamed to flag!
54 */
55
56 /*generic subdivision rules:
57   
58   * two selected edges in a face should make a link
59     between them.
60
61   * one edge should do, what? make pretty topology, or just
62     split the edge only?
63 */
64
65 /*connects face with smallest len, which I think should always be correct for
66   edge subdivision*/
67 BMEdge *connect_smallest_face(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
68         BMIter iter, iter2;
69         BMVert *v;
70         BMLoop *nl;
71         BMFace *face, *curf = NULL;
72
73         /*this isn't the best thing in the world.  it doesn't handle cases where there's
74           multiple faces yet.  that might require a convexity test to figure out which
75           face is "best," and who knows what for non-manifold conditions.*/
76         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
77                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
78                         if (v == v2) {
79                                 if (!curf || face->len < curf->len) curf = face;
80                         }
81                 }
82         }
83
84         if (curf) {
85                 face = BM_Split_Face(bm, curf, v1, v2, &nl, NULL);
86                 
87                 if (nf) *nf = face;
88                 return nl ? nl->e : NULL;
89         }
90
91         return NULL;
92 }
93 /* calculates offset for co, based on fractal, sphere or smooth settings  */
94 static void alter_co(float *co, BMEdge *edge, subdparams *params, float perc,
95                      BMVert *vsta, BMVert *vend)
96 {
97         float vec1[3], fac;
98
99         if(params->beauty & B_SMOOTH) {
100                 /* we calculate an offset vector vec1[], to be added to *co */
101                 float len, fac, nor[3], nor1[3], nor2[3], smooth=params->smooth;
102
103                 VecSubf(nor, vsta->co, vend->co);
104                 len= 0.5f*Normalize(nor);
105
106                 VECCOPY(nor1, vsta->no);
107                 VECCOPY(nor2, vend->no);
108
109                 /* cosine angle */
110                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
111
112                 vec1[0]= fac*nor1[0];
113                 vec1[1]= fac*nor1[1];
114                 vec1[2]= fac*nor1[2];
115
116                 /* cosine angle */
117                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
118
119                 vec1[0]+= fac*nor2[0];
120                 vec1[1]+= fac*nor2[1];
121                 vec1[2]+= fac*nor2[2];
122
123                 /* falloff for multi subdivide */
124                 smooth *= sqrt(fabs(1.0f - 2.0f*fabs(perc)));
125
126                 vec1[0]*= smooth*len;
127                 vec1[1]*= smooth*len;
128                 vec1[2]*= smooth*len;
129
130                 co[0] += vec1[0];
131                 co[1] += vec1[1];
132                 co[2] += vec1[2];
133         }
134         else if(params->beauty & B_SPHERE) { /* subdivide sphere */
135                 Normalize(co);
136                 co[0]*= params->smooth;
137                 co[1]*= params->smooth;
138                 co[2]*= params->smooth;
139         }
140
141         if(params->beauty & B_FRACTAL) {
142                 fac= params->fractal*VecLenf(vsta->co, vend->co);
143                 vec1[0]= fac*(float)(0.5-BLI_drand());
144                 vec1[1]= fac*(float)(0.5-BLI_drand());
145                 vec1[2]= fac*(float)(0.5-BLI_drand());
146                 VecAddf(co, co, vec1);
147         }
148 }
149
150 /* assumes in the edge is the correct interpolated vertices already */
151 /* percent defines the interpolation, rad and flag are for special options */
152 /* results in new vertex with correct coordinate, vertex normal and weight group info */
153 static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge,BMEdge *oedge,
154                                         subdparams *params, float percent,
155                                         float percent2,
156                                         BMEdge **out,BMVert *vsta,BMVert *vend)
157 {
158         BMVert *ev;
159 //      float co[3];
160         
161         ev = BM_Split_Edge(bm, edge->v1, edge, out, percent);
162         BM_Vert_UpdateNormal(bm, ev);
163
164         BMO_SetFlag(bm, ev, ELE_INNER);
165
166         /* offset for smooth or sphere or fractal */
167         alter_co(ev->co, oedge, params, percent2, vsta, vend);
168
169 #if 0 //TODO
170         /* clip if needed by mirror modifier */
171         if (edge->v1->f2) {
172                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
173                         co[0]= 0.0f;
174                 }
175                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
176                         co[1]= 0.0f;
177                 }
178                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
179                         co[2]= 0.0f;
180                 }
181         }
182 #endif  
183         
184         return ev;
185 }
186
187 static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, BMEdge *oedge,
188                                 int curpoint, int totpoint, subdparams *params,
189                                 BMEdge **newe, BMVert *vsta, BMVert *vend)
190 {
191         BMVert *ev;
192         float percent, percent2 = 0.0f;
193          
194         if (BMO_TestFlag(bm, edge, EDGE_PERCENT) && totpoint == 1)
195                 percent = BMO_Get_MapFloat(bm, params->op, 
196                                         "edgepercents", edge);
197         else {
198                 percent= 1.0f/(float)(totpoint+1-curpoint);
199                 percent2 = (float)curpoint / (float)(totpoint + 1);
200
201         }
202         
203         ev= bm_subdivide_edge_addvert(bm, edge, oedge, params, percent,
204                                       percent2, newe, vsta, vend);
205         return ev;
206 }
207
208 static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, subdparams *params, 
209                                   BMVert *vsta, BMVert *vend) {
210         BMEdge *eed = edge, *newe, temp = *edge;
211         BMVert *v;
212         int i, numcuts = params->numcuts;
213
214         for(i=0;i<numcuts;i++) {
215                 v = subdivideedgenum(bm, eed, &temp, i, params->numcuts, params, 
216                                      &newe, vsta, vend);
217                 BMO_SetFlag(bm, v, SUBD_SPLIT);
218                 BMO_SetFlag(bm, eed, SUBD_SPLIT);
219
220                 BMO_SetFlag(bm, v, ELE_SPLIT);
221                 BMO_SetFlag(bm, eed, ELE_SPLIT);
222         }
223 }
224
225 /*note: the patterns are rotated as necassary to
226   match the input geometry.  they're based on the
227   pre-split state of the  face*/
228
229 /*
230      
231 v3---------v2
232 |          |
233 |          |
234 |          |
235 |          |
236 v4---v0---v1
237
238 */
239 static void q_1edge_split(BMesh *bm, BMFace *face,
240                           BMVert **verts, subdparams *params) {
241         BMFace *nf;
242         int i, add, numcuts = params->numcuts;
243
244         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
245         if (numcuts % 2==0) {
246                 add = 2;
247                 for (i=0; i<numcuts; i++) {
248                         if (i == numcuts/2) add -= 1;
249                         connect_smallest_face(bm, verts[i], verts[numcuts+add], 
250                                            &nf);
251                 }
252         } else {
253                 add = 2;
254                 for (i=0; i<numcuts; i++) {
255                         connect_smallest_face(bm, verts[i], verts[numcuts+add], 
256                                            &nf);
257                         if (i == numcuts/2) {
258                                 add -= 1;
259                                 connect_smallest_face(bm, verts[i], 
260                                                    verts[numcuts+add],
261                                                    &nf);
262                         }
263                 }
264
265         }
266 }
267
268 subdpattern q_1edge = {
269         {1, 0, 0, 0},
270         q_1edge_split,
271         4,
272 };
273
274
275 /*
276 v6--------v5
277 |          |
278 |          |v4s
279 |          |v3s
280 |   s  s   |
281 v7-v0--v1-v2
282
283 */
284 static void q_2edge_split_tess(BMesh *bm, BMFace *face, BMVert **verts, 
285                           subdparams *params)
286 {
287         BMFace *nf;
288         int i, numcuts = params->numcuts;
289         
290         for (i=0; i<numcuts; i++) {
291                 connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
292                                    &nf);
293         }
294         connect_smallest_face(bm, verts[numcuts*2+3], verts[numcuts*2+1], &nf);
295 }
296
297 subdpattern q_2edge_path = {
298         {1, 1, 0, 0},
299         q_2edge_split_tess,
300         4,
301 };
302
303 /*
304 v6--------v5
305 |          |
306 |          |v4s
307 |          |v3s
308 |   s  s   |
309 v7-v0--v1-v2
310
311 */
312 static void q_2edge_split_innervert(BMesh *bm, BMFace *face, BMVert **verts, 
313                           subdparams *params)
314 {
315         BMFace *nf;
316         BMVert *v, *lastv;
317         BMEdge *e, *ne;
318         int i, numcuts = params->numcuts;
319         
320         lastv = verts[numcuts];
321
322         for (i=numcuts-1; i>=0; i--) {
323                 e = connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
324                                    &nf);
325                 
326                 v = BM_Split_Edge(bm, e->v1, e, &ne, 0.5f);
327                 connect_smallest_face(bm, lastv, v, &nf);
328                 lastv = v;
329         }
330
331         connect_smallest_face(bm, lastv, verts[numcuts*2+2], &nf);      
332 }
333
334 subdpattern q_2edge_innervert = {
335         {1, 1, 0, 0},
336         q_2edge_split_innervert,
337         4,
338 };
339
340 /*
341 v6--------v5
342 |          |
343 |          |v4s
344 |          |v3s
345 |   s  s   |
346 v7-v0--v1-v2
347
348 */
349 static void q_2edge_split_fan(BMesh *bm, BMFace *face, BMVert **verts, 
350                           subdparams *params)
351 {
352         BMFace *nf;
353         BMVert *v, *lastv;
354         BMEdge *e, *ne;
355         int i, numcuts = params->numcuts;
356         
357         lastv = verts[2];
358
359         for (i=0; i<numcuts; i++) {
360                 connect_smallest_face(bm, verts[i], verts[numcuts*2+2], &nf);
361                 connect_smallest_face(bm, verts[numcuts+(numcuts-i)], 
362                         verts[numcuts*2+2], &nf);
363         }
364 }
365
366 subdpattern q_2edge_fan = {
367         {1, 1, 0, 0},
368         q_2edge_split_fan,
369         4,
370 };
371
372 /*  s   s
373 v8--v7--v6-v5
374 |          |
375 |          v4 s
376 |          |
377 |          v3 s
378 |   s  s   |
379 v9-v0--v1-v2
380
381 */
382 static void q_3edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
383                           subdparams *params)
384 {
385         BMFace *nf;
386         int i, add=0, numcuts = params->numcuts;
387         
388         for (i=0; i<numcuts; i++) {
389                 if (i == numcuts/2) {
390                         if (numcuts % 2 != 0) {
391                                 connect_smallest_face(bm, verts[numcuts-i-1+add], 
392                                                  verts[i+numcuts+1], &nf);
393                         }
394                         add = numcuts*2+2;
395                 }
396                 connect_smallest_face(bm, verts[numcuts-i-1+add], 
397                                      verts[i+numcuts+1], &nf);
398         }
399
400         for (i=0; i<numcuts/2+1; i++) {
401                 connect_smallest_face(bm, verts[i],verts[(numcuts-i)+numcuts*2+1],
402                                    &nf);
403         }
404 }
405
406 subdpattern q_3edge = {
407         {1, 1, 1, 0},
408         q_3edge_split,
409         4,
410 };
411
412 /*
413  
414            v8--v7-v6--v5
415            |     s    |
416            |v9 s     s|v4
417 first line |          |   last line
418            |v10s s   s|v3
419            v11-v0--v1-v2
420
421            it goes from bottom up
422 */
423 static void q_4edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
424                           subdparams *params)
425 {
426         BMFace *nf;
427         BMVert *v, *v1, *v2;
428         BMEdge *e, *ne, temp;
429         BMVert **lines;
430         int numcuts = params->numcuts;
431         int i, j, a, b, s=numcuts+2, totv=numcuts*4+4;
432
433         lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
434                                      "q_4edge_split");
435         /*build a 2-dimensional array of verts,
436           containing every vert (and all new ones)
437           in the face.*/
438
439         /*first line*/
440         for (i=0; i<numcuts+2; i++) {
441                 lines[i] = verts[numcuts*3+2+(numcuts-i+1)];
442         }
443
444         /*last line*/
445         for (i=0; i<numcuts+2; i++) {
446                 lines[(s-1)*s+i] = verts[numcuts+i];
447         }
448         
449         /*first and last members of middle lines*/
450         for (i=0; i<numcuts; i++) {
451                 a = i;
452                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
453                 
454                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
455                 if (!e) continue;
456
457                 BMO_SetFlag(bm, e, ELE_INNER);
458                 BMO_SetFlag(bm, nf, ELE_INNER);
459
460                 
461                 v1 = lines[(i+1)*s] = verts[a];
462                 v2 = lines[(i+1)*s + s-1] = verts[b];
463                 
464                 temp = *e;
465                 for (a=0; a<numcuts; a++) {
466                         v = subdivideedgenum(bm, e, &temp, a, numcuts, params, &ne,
467                                              v1, v2);
468                         BMO_SetFlag(bm, ne, ELE_INNER);
469                         lines[(i+1)*s+a+1] = v;
470                 }
471         }
472
473         for (i=1; i<numcuts+2; i++) {
474                 for (j=1; j<numcuts+1; j++) {
475                         a = i*s + j;
476                         b = (i-1)*s + j;
477                         e = connect_smallest_face(bm, lines[a], lines[b], &nf);
478                         if (!e) continue;
479
480                         BMO_SetFlag(bm, e, ELE_INNER);
481                         BMO_SetFlag(bm, nf, ELE_INNER);
482                 }
483         }
484
485         MEM_freeN(lines);
486 }
487
488 /*    v3
489      / \
490     /   \
491    /     \
492   /       \
493  /         \
494 v4--v0--v1--v2
495     s    s
496 */
497 static void t_1edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
498                           subdparams *params)
499 {
500         BMFace *nf;
501         int i, numcuts = params->numcuts;
502         
503         for (i=0; i<numcuts; i++) {
504                 connect_smallest_face(bm, verts[i], verts[numcuts+1], &nf);
505         }
506 }
507
508 subdpattern t_1edge = {
509         {1, 0, 0},
510         t_1edge_split,
511         3,
512 };
513
514 /*     v5
515       / \
516  s v6/---\ v4 s
517     / \ / \
518 sv7/---v---\ v3 s
519   /  \/  \/ \
520  v8--v0--v1--v2
521     s    s
522 */
523 static void t_3edge_split(BMesh *bm, BMFace *face, BMVert **verts, 
524                           subdparams *params)
525 {
526         BMFace *nf;
527         BMEdge *e, *ne, temp;
528         BMVert ***lines, *v;
529         void *stackarr[1];
530         int i, j, a, b, numcuts = params->numcuts;
531         
532         /*number of verts in each line*/
533         lines = MEM_callocN(sizeof(void*)*(numcuts+2), "triangle vert table");
534         
535         lines[0] = (BMVert**) stackarr;
536         lines[0][0] = verts[numcuts*2+1];
537         
538         lines[1+numcuts] = MEM_callocN(sizeof(void*)*(numcuts+2), 
539                                        "triangle vert table 2");
540         for (i=0; i<numcuts; i++) {
541                 lines[1+numcuts][1+i] = verts[i];
542         }
543         lines[1+numcuts][0] = verts[numcuts*3+2];
544         lines[1+numcuts][1+numcuts] = verts[numcuts];
545
546         for (i=0; i<numcuts; i++) {
547                 lines[i+1] = MEM_callocN(sizeof(void*)*(2+i), 
548                                        "triangle vert table row");
549                 a = numcuts*2 + 2 + i;
550                 b = numcuts + numcuts - i;
551                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
552                 if (!e) goto cleanup;
553
554                 BMO_SetFlag(bm, e, ELE_INNER);
555                 BMO_SetFlag(bm, nf, ELE_INNER);
556
557                 lines[i+1][0] = verts[a];
558                 lines[i+1][1+i] = verts[b];
559                 
560                 temp = *e;
561                 for (j=0; j<i; j++) {
562                         v = subdivideedgenum(bm, e, &temp, j, i, params, &ne,
563                                              verts[a], verts[b]);
564                         lines[i+1][j+1] = v;
565
566                         BMO_SetFlag(bm, ne, ELE_INNER);
567                 }
568         }
569         
570
571 /*     v5
572       / \
573  s v6/---\ v4 s
574     / \ / \
575 sv7/---v---\ v3 s
576   /  \/  \/ \
577  v8--v0--v1--v2
578     s    s
579 */
580         for (i=1; i<numcuts+1; i++) {
581                 for (j=0; j<i; j++) {
582                         e= connect_smallest_face(bm, lines[i][j], lines[i+1][j+1],
583                                            &nf);
584
585                         BMO_SetFlag(bm, e, ELE_INNER);
586                         BMO_SetFlag(bm, nf, ELE_INNER);
587
588                         e= connect_smallest_face(bm,lines[i][j+1],lines[i+1][j+1],
589                                            &nf);
590
591                         BMO_SetFlag(bm, e, ELE_INNER);
592                         BMO_SetFlag(bm, nf, ELE_INNER);
593                 }
594         }
595
596 cleanup:
597         for (i=1; i<numcuts+2; i++) {
598                 if (lines[i]) MEM_freeN(lines[i]);
599         }
600
601         MEM_freeN(lines);
602 }
603
604 subdpattern t_3edge = {
605         {1, 1, 1},
606         t_3edge_split,
607         3,
608 };
609
610
611 subdpattern q_4edge = {
612         {1, 1, 1, 1},
613         q_4edge_split,
614         4,
615 };
616
617 subdpattern *patterns[] = {
618         NULL, //quad single edge pattern is inserted here
619         NULL, //quad corner vert pattern is inserted here
620         NULL, //tri single edge pattern is inserted here
621         NULL,
622         &q_3edge,
623         NULL,
624 };
625
626 #define PLEN    (sizeof(patterns) / sizeof(void*))
627
628 typedef struct subd_facedata {
629         BMVert *start; subdpattern *pat;
630         int totedgesel; //only used if pat was NULL, e.g. no pattern was found
631 } subd_facedata;
632
633 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
634 {
635         BMOpSlot *einput;
636         BMEdge *edge, **edges = NULL;
637         V_DECLARE(edges);
638         BMFace *face;
639         BMLoop *nl;
640         BMVert **verts = NULL;
641         V_DECLARE(verts);
642         BMIter fiter, liter;
643         subdpattern *pat;
644         subdparams params;
645         subd_facedata *facedata = NULL;
646         V_DECLARE(facedata);
647         BMLoop *l, **splits = NULL, **loops = NULL;
648         V_DECLARE(splits);
649         V_DECLARE(loops);
650         float smooth, fractal;
651         int beauty, cornertype, singleedge, gridfill;
652         int i, j, matched, a, b, numcuts, totesel;
653         
654         BMO_Flag_Buffer(bmesh, op, "edges", SUBD_SPLIT, BM_EDGE);
655         
656         numcuts = BMO_Get_Int(op, "numcuts");
657         smooth = BMO_Get_Float(op, "smooth");
658         fractal = BMO_Get_Float(op, "fractal");
659         beauty = BMO_Get_Int(op, "beauty");
660         cornertype = BMO_Get_Int(op, "quadcornertype");
661         singleedge = BMO_Get_Int(op, "singleedge");
662         gridfill = BMO_Get_Int(op, "gridfill");
663         
664         patterns[1] = NULL;
665         //straight cut is patterns[1] == NULL
666         switch (cornertype) {
667                 case SUBD_PATH:
668                         patterns[1] = &q_2edge_path;
669                         break;
670                 case SUBD_INNERVERT:
671                         patterns[1] = &q_2edge_innervert;
672                         break;
673                 case SUBD_FAN:
674                         patterns[1] = &q_2edge_fan;
675                         break;
676         }
677         
678         if (singleedge) {
679                 patterns[0] = &q_1edge;
680                 patterns[2] = &t_1edge;
681         } else {
682                 patterns[0] = NULL;
683                 patterns[2] = NULL;
684         }
685
686         if (gridfill) {
687                 patterns[3] = &q_4edge;
688                 patterns[5] = &t_3edge;
689         } else {
690                 patterns[3] = NULL;
691                 patterns[5] = NULL;
692         }
693         
694         /*first go through and tag edges*/
695         BMO_Flag_To_Slot(bmesh, op, "edges",
696                  SUBD_SPLIT, BM_EDGE);
697
698         params.numcuts = numcuts;
699         params.op = op;
700         params.smooth = smooth;
701         params.fractal = fractal;
702         params.beauty = beauty;
703
704         BMO_Mapping_To_Flag(bmesh, op, "custompatterns",
705                             FACE_CUSTOMFILL);
706
707         BMO_Mapping_To_Flag(bmesh, op, "edgepercents",
708                             EDGE_PERCENT);
709
710         for (face=BMIter_New(&fiter, bmesh, BM_FACES_OF_MESH, NULL);
711              face; face=BMIter_Step(&fiter)) {
712                 BMEdge *e1 = NULL, *e2 = NULL;
713                 float vec1[3], vec2[3];
714
715                 /*figure out which pattern to use*/
716
717                 V_RESET(edges);
718                 V_RESET(verts);
719                 matched = 0;
720
721                 i = 0;
722                 totesel = 0;
723                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
724                      nl; nl=BMIter_Step(&liter)) {
725                         V_GROW(edges);
726                         V_GROW(verts);
727                         edges[i] = nl->e;
728                         verts[i] = nl->v;
729
730                         if (BMO_TestFlag(bmesh, edges[i], SUBD_SPLIT)) {
731                                 if (!e1) e1 = edges[i];
732                                 else e2 = edges[i];
733
734                                 totesel++;
735                         }
736
737                         i++;
738                 }
739
740                 /*make sure the two edges have a valid angle to each other*/
741                 if (totesel == 2 && (e1->v1 == e2->v1 || e1->v1 == e2->v2 
742                                      || e1->v2 == e2->v1 || e1->v2 == e2->v1)) {
743                         float angle;
744
745                         VecSubf(vec1, e1->v2->co, e1->v1->co);
746                         VecSubf(vec2, e2->v2->co, e2->v1->co);
747                         Normalize(vec1);
748                         Normalize(vec2);
749
750                         angle = INPR(vec1, vec2);
751                         angle = ABS(angle);
752                         if (ABS(angle-1.0) < 0.01)
753                                 totesel = 0;
754                 }
755
756                 if (BMO_TestFlag(bmesh, face, FACE_CUSTOMFILL)) {
757                         pat = BMO_Get_MapData(bmesh, op, 
758                                     "custompatterns", face);
759                         for (i=0; i<pat->len; i++) {
760                                 matched = 1;
761                                 for (j=0; j<pat->len; j++) {
762                                         a = (j + i) % pat->len;
763                                         if ((!!BMO_TestFlag(bmesh, edges[a], SUBD_SPLIT))
764                                                 != (!!pat->seledges[j])) {
765                                                         matched = 0;
766                                                         break;
767                                         }
768                                 }
769                                 if (matched) {
770                                         V_GROW(facedata);
771                                         b = V_COUNT(facedata)-1;
772                                         facedata[b].pat = pat;
773                                         facedata[b].start = verts[i];
774                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
775                                         break;
776                                 }
777                         }
778                         if (!matched) {
779                                 /*if no match, append null element to array.*/
780                                 V_GROW(facedata);
781                         }
782
783                         /*obvously don't test for other patterns matching*/
784                         continue;
785                 }
786
787                 for (i=0; i<PLEN; i++) {
788                         pat = patterns[i];
789                         if (!pat) continue;
790
791                         if (pat->len == face->len) {
792                                 for (a=0; a<pat->len; a++) {
793                                         matched = 1;
794                                         for (b=0; b<pat->len; b++) {
795                                                 j = (b + a) % pat->len;
796                                                 if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
797                                                         != (!!pat->seledges[b])) {
798                                                                 matched = 0;
799                                                                 break;
800                                                 }
801                                         }
802                                         if (matched) break;
803                                 }
804                                 if (matched) {
805                                         V_GROW(facedata);
806                                         j = V_COUNT(facedata) - 1;
807
808                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
809
810                                         facedata[j].pat = pat;
811                                         facedata[j].start = verts[a];
812                                         break;
813                                 }
814                         }
815                 
816                 }
817                 
818                 if (!matched && totesel) {
819                         V_GROW(facedata);
820                         j = V_COUNT(facedata) - 1;
821                         
822                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
823                         facedata[j].totedgesel = totesel;
824                 }
825         }
826
827         einput = BMO_GetSlot(op, "edges");
828
829         /*go through and split edges*/
830         for (i=0; i<einput->len; i++) {
831                 edge = ((BMEdge**)einput->data.p)[i];
832                 bm_subdivide_multicut(bmesh, edge,&params, edge->v1, edge->v2);
833                 //BM_Split_Edge_Multi(bmesh, edge, numcuts);
834         }
835
836         //if (facedata) V_FREE(facedata);
837         //return;
838
839         i = 0;
840         for (face=BMIter_New(&fiter, bmesh, BM_FACES_OF_MESH, NULL);
841              face; face=BMIter_Step(&fiter)) {
842                 /*figure out which pattern to use*/
843                 V_RESET(verts);
844                 if (BMO_TestFlag(bmesh, face, SUBD_SPLIT) == 0)
845                         continue;
846
847                 pat = facedata[i].pat;
848                 if (!pat && facedata[i].totedgesel == 2) { /*ok, no pattern.  we still may be able to do something.*/
849                         BMFace *nf;
850                         int vlen;
851                         
852                         V_RESET(loops);
853                         V_RESET(splits);
854
855                         /*for case of two edges, connecting them shouldn't be too hard*/
856                         BM_ITER(l, &liter, bmesh, BM_LOOPS_OF_FACE, face) {
857                                 V_GROW(loops);
858                                 loops[V_COUNT(loops)-1] = l;
859                         }
860                         
861                         vlen = V_COUNT(loops);
862
863                         /*find the boundary of one of the split edges*/
864                         for (a=1; a<vlen; a++) {
865                                 if (!BMO_TestFlag(bmesh, loops[a-1]->v, ELE_INNER) 
866                                     && BMO_TestFlag(bmesh, loops[a]->v, ELE_INNER))
867                                         break;
868                         }
869                         
870                         if (BMO_TestFlag(bmesh, loops[(a+numcuts+1)%vlen]->v, ELE_INNER)) {
871                                 b = (a+numcuts+1)%vlen;
872                         } else {
873                                 /*find the boundary of the other edge.*/
874                                 for (j=0; j<vlen; j++) {
875                                         b = (j + a + numcuts + 1) % vlen;
876                                         if (!BMO_TestFlag(bmesh, loops[b==0 ? vlen-1 : b-1]->v, ELE_INNER)
877                                             && BMO_TestFlag(bmesh, loops[b]->v, ELE_INNER))
878                                                 break;
879                                 }
880                         }
881                         
882                         b += numcuts - 1;
883
884                         for (j=0; j<numcuts; j++) {
885                                 V_GROW(splits);
886                                 splits[V_COUNT(splits)-1] = loops[a];
887                                 
888                                 V_GROW(splits);
889                                 splits[V_COUNT(splits)-1] = loops[b];
890
891                                 b = (b-1) % vlen;
892                                 a = (a+1) % vlen;
893                         }
894                         
895                         //BM_LegalSplits(bmesh, face, splits, V_COUNT(splits)/2);
896
897                         for (j=0; j<V_COUNT(splits)/2; j++) {
898                                 if (splits[j*2]) {
899                                         BMFace *nf;
900
901                                         nf = BM_Split_Face(bmesh, face, splits[j*2]->v, splits[j*2+1]->v, &nl, NULL);
902                                 }
903                         }
904
905                         i++;
906                         continue;
907                 } else if (!pat) {
908                         i++;
909                         continue;
910                 }
911
912                 j = a = 0;
913                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
914                      nl; nl=BMIter_Step(&liter)) {
915                         if (nl->v == facedata[i].start) {
916                                 a = j+1;
917                                 break;
918                         }
919                         j++;
920                 }
921
922                 for (j=0; j<face->len; j++) {
923                         V_GROW(verts);
924                 }
925                 
926                 j = 0;
927                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
928                      nl; nl=BMIter_Step(&liter)) {
929                         b = (j-a+face->len) % face->len;
930                         verts[b] = nl->v;
931                         j += 1;
932                 }
933                 
934                 pat->connectexec(bmesh, face, verts, &params);
935                 i++;
936         }
937
938         if (facedata) V_FREE(facedata);
939         if (edges) V_FREE(edges);
940         if (verts) V_FREE(verts);
941         V_FREE(splits);
942         V_FREE(loops);
943
944         BMO_Flag_To_Slot(bmesh, op, "outinner",
945                          ELE_INNER, BM_ALL);
946         BMO_Flag_To_Slot(bmesh, op, "outsplit",
947                          ELE_SPLIT, BM_ALL);
948 }
949
950 /*editmesh-emulating function*/
951 void BM_esubdivideflag(Object *obedit, BMesh *bm, int flag, float smooth, 
952                        float fractal, int beauty, int numcuts, 
953                        int seltype, int cornertype, int singleedge, int gridfill)
954 {
955         BMOperator op;
956         
957         BMO_InitOpf(bm, &op, "esubd edges=%he smooth=%f fractal=%f "
958                              "beauty=%d numcuts=%d quadcornertype=%d singleedge=%d "
959                              "gridfill=%d",
960                              flag, smooth, fractal, beauty, numcuts,
961                              cornertype, singleedge, gridfill);
962         
963         BMO_Exec_Op(bm, &op);
964         
965         if (seltype == SUBDIV_SELECT_INNER) {
966                 BMOIter iter;
967                 BMHeader *ele;
968                 int i;
969                 
970                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
971                 for (; ele; ele=BMO_IterStep(&iter)) {
972                         BM_Select(bm, ele, 1);
973                 }
974         } else if (seltype == SUBDIV_SELECT_LOOPCUT) {
975                 BMOIter iter;
976                 BMHeader *ele;
977                 int i;
978                 
979                 /*deselect input*/
980                 BM_clear_flag_all(bm, BM_SELECT);
981
982                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
983                 for (; ele; ele=BMO_IterStep(&iter)) {
984                         BM_Select(bm, ele, 1);
985                 }
986         }
987
988         BMO_Finish_Op(bm, &op);
989 }
990
991 #if 0
992 void BM_esubdivideflag_conv(Object *obedit,EditMesh *em,int selflag, float rad, 
993                        int flag, int numcuts, int seltype) {
994         BMesh *bm = editmesh_to_bmesh(em);
995         EditMesh *em2;
996
997         BM_esubdivideflag(obedit, bm, selflag, rad, flag, numcuts, seltype);
998         em2 = bmesh_to_editmesh(bm);
999         
1000         free_editMesh(em);
1001         *em = *em2;
1002         MEM_freeN(em2);
1003         BM_Free_Mesh(bm);
1004 }
1005 #endif
1006
1007 void esplit_exec(BMesh *bm, BMOperator *op)
1008 {
1009         BMOIter siter;
1010         BMEdge *e;
1011         subdparams params;
1012
1013         params.numcuts = BMO_GetSlot(op, "numcuts")->data.i;
1014         params.op = op;
1015         
1016         /*go through and split edges*/
1017         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1018                 bm_subdivide_multicut(bm, e, &params, e->v1, e->v2);
1019         }
1020
1021         BMO_Flag_To_Slot(bm, op, "outsplit",
1022                          ELE_SPLIT, BM_ALL);
1023 }
1024