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