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