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