Merging r58464 through r58474 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / bmesh / intern / bmesh_construct.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  * The Original Code is Copyright (C) 2007 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Geoffrey Bantle.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/bmesh/intern/bmesh_construct.c
29  *  \ingroup bmesh
30  *
31  * BM construction functions.
32  */
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_array.h"
37 #include "BLI_math.h"
38
39 #include "BKE_customdata.h"
40
41 #include "DNA_meshdata_types.h"
42
43 #include "bmesh.h"
44 #include "intern/bmesh_private.h"
45
46 #define SELECT 1
47
48 /* prototypes */
49 static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
50                                const BMLoop *source_loop, BMLoop *target_loop);
51
52 /**
53  * \brief Make Quad/Triangle
54  *
55  * Creates a new quad or triangle from a list of 3 or 4 vertices.
56  * If \a no_double is true, then a check is done to see if a face
57  * with these vertices already exists and returns it instead.
58  *
59  * If a pointer to an example face is provided, it's custom data
60  * and properties will be copied to the new face.
61  *
62  * \note The winding of the face is determined by the order
63  * of the vertices in the vertex array.
64  */
65
66 BMFace *BM_face_create_quad_tri(BMesh *bm,
67                                 BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
68                                 const BMFace *example, const bool no_double)
69 {
70         BMVert *vtar[4] = {v1, v2, v3, v4};
71         return BM_face_create_quad_tri_v(bm, vtar, v4 ? 4 : 3, example, no_double);
72 }
73
74 BMFace *BM_face_create_quad_tri_v(BMesh *bm, BMVert **verts, int len, const BMFace *example, const bool no_double)
75 {
76         BMFace *f = NULL;
77         bool is_overlap = false;
78
79         /* sanity check - debug mode only */
80         if (len == 3) {
81                 BLI_assert(verts[0] != verts[1]);
82                 BLI_assert(verts[0] != verts[2]);
83                 BLI_assert(verts[1] != verts[2]);
84         }
85         else if (len == 4) {
86                 BLI_assert(verts[0] != verts[1]);
87                 BLI_assert(verts[0] != verts[2]);
88                 BLI_assert(verts[0] != verts[3]);
89
90                 BLI_assert(verts[1] != verts[2]);
91                 BLI_assert(verts[1] != verts[3]);
92
93                 BLI_assert(verts[2] != verts[3]);
94         }
95         else {
96                 BLI_assert(0);
97         }
98
99
100         if (no_double) {
101                 /* check if face exists or overlaps */
102                 is_overlap = BM_face_exists(verts, len, &f);
103         }
104
105         /* make new face */
106         if ((f == NULL) && (!is_overlap)) {
107                 BMEdge *edar[4] = {NULL};
108                 edar[0] = BM_edge_create(bm, verts[0], verts[1], NULL, BM_CREATE_NO_DOUBLE);
109                 edar[1] = BM_edge_create(bm, verts[1], verts[2], NULL, BM_CREATE_NO_DOUBLE);
110                 if (len == 4) {
111                         edar[2] = BM_edge_create(bm, verts[2], verts[3], NULL, BM_CREATE_NO_DOUBLE);
112                         edar[3] = BM_edge_create(bm, verts[3], verts[0], NULL, BM_CREATE_NO_DOUBLE);
113                 }
114                 else {
115                         edar[2] = BM_edge_create(bm, verts[2], verts[0], NULL, BM_CREATE_NO_DOUBLE);
116                 }
117
118                 f = BM_face_create(bm, verts, edar, len, 0);
119
120                 if (example && f) {
121                         BM_elem_attrs_copy(bm, bm, example, f);
122                 }
123         }
124
125         return f;
126 }
127
128 /**
129  * \brief copies face loop data from shared adjacent faces.
130  * \note when a matching edge is found, both loops of that edge are copied
131  * this is done since the face may not be completely surrounded by faces,
132  * this way: a quad with 2 connected quads on either side will still get all 4 loops updated */
133 void BM_face_copy_shared(BMesh *bm, BMFace *f)
134 {
135         BMLoop *l_first;
136         BMLoop *l_iter;
137
138         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
139         do {
140                 BMLoop *l_other = l_iter->radial_next;
141
142                 if (l_other && l_other != l_iter) {
143                         if (l_other->v == l_iter->v) {
144                                 bm_loop_attrs_copy(bm, bm, l_other, l_iter);
145                                 bm_loop_attrs_copy(bm, bm, l_other->next, l_iter->next);
146                         }
147                         else {
148                                 bm_loop_attrs_copy(bm, bm, l_other->next, l_iter);
149                                 bm_loop_attrs_copy(bm, bm, l_other, l_iter->next);
150                         }
151                         /* since we copy both loops of the shared edge, step over the next loop here */
152                         if ((l_iter = l_iter->next) == l_first) {
153                                 break;
154                         }
155                 }
156         } while ((l_iter = l_iter->next) != l_first);
157 }
158
159 /**
160  * \brief Make NGon
161  *
162  * Makes an ngon from an unordered list of edges. \a v1 and \a v2
163  * must be the verts defining edges[0],
164  * and define the winding of the new face.
165  *
166  * \a edges are not required to be ordered, simply to to form
167  * a single closed loop as a whole.
168  *
169  * \note While this function will work fine when the edges
170  * are already sorted, if the edges are always going to be sorted,
171  * #BM_face_create should be considered over this function as it
172  * avoids some unnecessary work.
173  */
174 BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, const int create_flag)
175 {
176         BMEdge **edges_sort = BLI_array_alloca(edges_sort, len);
177         BMVert **verts_sort = BLI_array_alloca(verts_sort, len + 1);
178         int esort_index = 0;
179         int vsort_index = 0;
180
181         BMFace *f = NULL;
182         BMEdge *e;
183         BMVert *v, *ev1, *ev2;
184         int i;
185         bool is_v1_found, is_reverse;
186
187
188         /* this code is hideous, yeek.  I'll have to think about ways of
189          *  cleaning it up.  basically, it now combines the old BM_face_create_ngon
190          *  _and_ the old bmesh_mf functions, so its kindof smashed together
191          * - joeedh */
192
193         BLI_assert(len && v1 && v2 && edges && bm);
194
195         /* put edges in correct order */
196         for (i = 0; i < len; i++) {
197                 BM_ELEM_API_FLAG_ENABLE(edges[i], _FLAG_MF);
198         }
199
200         ev1 = edges[0]->v1;
201         ev2 = edges[0]->v2;
202
203         if (v1 == ev2) {
204                 /* Swapping here improves performance and consistency of face
205                  * structure in the special case that the edges are already in
206                  * the correct order and winding */
207                 SWAP(BMVert *, ev1, ev2);
208         }
209
210         verts_sort[vsort_index++] = ev1;
211         v = ev2;
212         e = edges[0];
213         do {
214                 BMEdge *e2 = e;
215
216                 /* vertex array is (len + 1) */
217                 if (UNLIKELY(vsort_index > len)) {
218                         goto err; /* vertex in loop twice */
219                 }
220
221                 verts_sort[vsort_index++] = v;
222                 edges_sort[esort_index++] = e;
223
224                 /* we only flag the verts to check if they are in the face more than once */
225                 BM_ELEM_API_FLAG_ENABLE(v, _FLAG_MV);
226
227                 do {
228                         e2 = bmesh_disk_edge_next(e2, v);
229                         if (e2 != e && BM_ELEM_API_FLAG_TEST(e2, _FLAG_MF)) {
230                                 v = BM_edge_other_vert(e2, v);
231                                 break;
232                         }
233                 } while (e2 != e);
234
235                 if (UNLIKELY(e2 == e)) {
236                         goto err; /* the edges do not form a closed loop */
237                 }
238
239                 e = e2;
240         } while (e != edges[0]);
241
242         if (UNLIKELY(esort_index != len)) {
243                 goto err; /* we didn't use all edges in forming the boundary loop */
244         }
245
246         /* ok, edges are in correct order, now ensure they are going
247          * in the correct direction */
248         is_v1_found = is_reverse = false;
249         for (i = 0; i < len; i++) {
250                 if (BM_vert_in_edge(edges_sort[i], v1)) {
251                         /* see if v1 and v2 are in the same edge */
252                         if (BM_vert_in_edge(edges_sort[i], v2)) {
253                                 /* if v1 is shared by the *next* edge, then the winding
254                                  * is incorrect */
255                                 if (BM_vert_in_edge(edges_sort[(i + 1) % len], v1)) {
256                                         is_reverse = true;
257                                         break;
258                                 }
259                         }
260
261                         is_v1_found = true;
262                 }
263
264                 if ((is_v1_found == false) && BM_vert_in_edge(edges_sort[i], v2)) {
265                         is_reverse = true;
266                         break;
267                 }
268         }
269
270         if (is_reverse) {
271                 for (i = 0; i < len / 2; i++) {
272                         v = verts_sort[i];
273                         verts_sort[i] = verts_sort[len - i - 1];
274                         verts_sort[len - i - 1] = v;
275                 }
276         }
277
278         for (i = 0; i < len; i++) {
279                 edges_sort[i] = BM_edge_exists(verts_sort[i], verts_sort[(i + 1) % len]);
280                 if (UNLIKELY(edges_sort[i] == NULL)) {
281                         goto err;
282                 }
283
284                 /* check if vert is in face more than once. if the flag is disabled. we've already visited */
285                 if (UNLIKELY(!BM_ELEM_API_FLAG_TEST(verts_sort[i], _FLAG_MV))) {
286                         goto err;
287                 }
288                 BM_ELEM_API_FLAG_DISABLE(verts_sort[i], _FLAG_MV);
289         }
290
291         f = BM_face_create(bm, verts_sort, edges_sort, len, create_flag);
292
293         /* clean up flags */
294         for (i = 0; i < len; i++) {
295                 BM_ELEM_API_FLAG_DISABLE(edges_sort[i], _FLAG_MF);
296         }
297
298         return f;
299
300 err:
301         for (i = 0; i < len; i++) {
302                 BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF);
303         }
304         for (i = 0; i < vsort_index; i++) {
305                 BM_ELEM_API_FLAG_DISABLE(verts_sort[i], _FLAG_MV);
306         }
307
308         return NULL;
309 }
310
311 /**
312  * Create an ngon from an array of sorted verts
313  *
314  * Special features this has over other functions.
315  * - Optionally calculate winding based on surrounding edges.
316  * - Optionally create edges between vertices.
317  * - Uses verts so no need to find edges (handy when you only have verts)
318  */
319 BMFace *BM_face_create_ngon_verts(BMesh *bm, BMVert **vert_arr, const int len, const int create_flag,
320                                   const bool calc_winding, const bool create_edges)
321 {
322         BMEdge **edge_arr = BLI_array_alloca(edge_arr, len);
323         unsigned int winding[2] = {0, 0};
324         int i, i_prev = len - 1;
325
326         BLI_assert(len > 2);
327
328         for (i = 0; i < len; i++) {
329                 if (create_edges) {
330                         edge_arr[i] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE);
331                 }
332                 else {
333                         edge_arr[i] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]);
334                         if (edge_arr[i] == NULL) {
335                                 return NULL;
336                         }
337                 }
338
339                 if (calc_winding) {
340                         /* the edge may exist already and be attached to a face
341                          * in this case we can find the best winding to use for the new face */
342                         if (edge_arr[i]->l) {
343                                 BMVert *test_v1, *test_v2;
344                                 /* we want to use the reverse winding to the existing order */
345                                 BM_edge_ordered_verts(edge_arr[i], &test_v2, &test_v1);
346                                 winding[(vert_arr[i_prev] == test_v2)]++;
347                         }
348                 }
349
350                 i_prev = i;
351         }
352
353         /* --- */
354
355         if (calc_winding) {
356                 if (winding[0] < winding[1]) {
357                         winding[0] = 1;
358                         winding[1] = 0;
359                 }
360                 else {
361                         winding[0] = 0;
362                         winding[1] = 1;
363                 }
364         }
365         else {
366                 winding[0] = 0;
367                 winding[1] = 1;
368         }
369
370         /* --- */
371
372         /* create the face */
373         return BM_face_create_ngon(bm, vert_arr[winding[0]], vert_arr[winding[1]], edge_arr, len, create_flag);
374 }
375
376
377 typedef struct AngleIndexPair {
378         float angle;
379         int index;
380 } AngleIndexPair;
381
382 static int angle_index_pair_cmp(const void *e1, const void *e2)
383 {
384         const AngleIndexPair *p1 = e1, *p2 = e2;
385         if      (p1->angle > p2->angle) return  1;
386         else if (p1->angle < p2->angle) return -1;
387         else return 0;
388 }
389
390 /**
391  * Makes an NGon from an un-ordered set of verts
392  *
393  * assumes...
394  * - that verts are only once in the list.
395  * - that the verts have roughly planer bounds
396  * - that the verts are roughly circular
397  * there can be concave areas but overlapping folds from the center point will fail.
398  *
399  * a brief explanation of the method used
400  * - find the center point
401  * - find the normal of the vcloud
402  * - order the verts around the face based on their angle to the normal vector at the center point.
403  *
404  * \note Since this is a vcloud there is no direction.
405  */
406 BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, const int create_flag)
407 {
408         BMFace *f;
409
410         float totv_inv = 1.0f / (float)len;
411         int i = 0;
412
413         float cent[3], nor[3];
414
415         float *far = NULL, *far_cross = NULL;
416
417         float far_vec[3];
418         float far_cross_vec[3];
419         float sign_vec[3]; /* work out if we are pos/neg angle */
420
421         float far_dist, far_best;
422         float far_cross_dist, far_cross_best = 0.0f;
423
424         AngleIndexPair *vang;
425
426         BMVert **vert_arr_map;
427
428         /* get the center point and collect vector array since we loop over these a lot */
429         zero_v3(cent);
430         for (i = 0; i < len; i++) {
431                 madd_v3_v3fl(cent, vert_arr[i]->co, totv_inv);
432         }
433
434
435         /* find the far point from cent */
436         far_best = 0.0f;
437         for (i = 0; i < len; i++) {
438                 far_dist = len_squared_v3v3(vert_arr[i]->co, cent);
439                 if (far_dist > far_best || far == NULL) {
440                         far = vert_arr[i]->co;
441                         far_best = far_dist;
442                 }
443         }
444
445         sub_v3_v3v3(far_vec, far, cent);
446         // far_dist = len_v3(far_vec); /* real dist */ /* UNUSED */
447
448         /* --- */
449
450         /* find a point 90deg about to compare with */
451         far_cross_best = 0.0f;
452         for (i = 0; i < len; i++) {
453
454                 if (far == vert_arr[i]->co) {
455                         continue;
456                 }
457
458                 sub_v3_v3v3(far_cross_vec, vert_arr[i]->co, cent);
459                 far_cross_dist = normalize_v3(far_cross_vec);
460
461                 /* more of a weight then a distance */
462                 far_cross_dist = (/* first we want to have a value close to zero mapped to 1 */
463                                   1.0f - fabsf(dot_v3v3(far_vec, far_cross_vec)) *
464
465                                   /* second  we multiply by the distance
466                                    * so points close to the center are not preferred */
467                                   far_cross_dist);
468
469                 if (far_cross_dist > far_cross_best || far_cross == NULL) {
470                         far_cross = vert_arr[i]->co;
471                         far_cross_best = far_cross_dist;
472                 }
473         }
474
475         sub_v3_v3v3(far_cross_vec, far_cross, cent);
476
477         /* --- */
478
479         /* now we have 2 vectors we can have a cross product */
480         cross_v3_v3v3(nor, far_vec, far_cross_vec);
481         normalize_v3(nor);
482         cross_v3_v3v3(sign_vec, far_vec, nor); /* this vector should match 'far_cross_vec' closely */
483
484         /* --- */
485
486         /* now calculate every points angle around the normal (signed) */
487         vang = MEM_mallocN(sizeof(AngleIndexPair) * len, __func__);
488
489         for (i = 0; i < len; i++) {
490                 float co[3];
491                 float proj_vec[3];
492                 float angle;
493
494                 /* center relative vec */
495                 sub_v3_v3v3(co, vert_arr[i]->co, cent);
496
497                 /* align to plane */
498                 project_v3_v3v3(proj_vec, co, nor);
499                 sub_v3_v3(co, proj_vec);
500
501                 /* now 'co' is valid - we can compare its angle against the far vec */
502                 angle = angle_v3v3(far_vec, co);
503
504                 if (dot_v3v3(co, sign_vec) < 0.0f) {
505                         angle = -angle;
506                 }
507
508                 vang[i].angle = angle;
509                 vang[i].index = i;
510         }
511
512         /* sort by angle and magic! - we have our ngon */
513         qsort(vang, len, sizeof(AngleIndexPair), angle_index_pair_cmp);
514
515         /* --- */
516
517         /* create edges and find the winding (if faces are attached to any existing edges) */
518         vert_arr_map = MEM_mallocN(sizeof(BMVert **) * len, __func__);
519
520         for (i = 0; i < len; i++) {
521                 vert_arr_map[i] = vert_arr[vang[i].index];
522         }
523         MEM_freeN(vang);
524
525         f = BM_face_create_ngon_verts(bm, vert_arr_map, len, create_flag, true, true);
526
527         MEM_freeN(vert_arr_map);
528
529         return f;
530 }
531
532 /**
533  * Called by operators to remove elements that they have marked for
534  * removal.
535  */
536 void BMO_remove_tagged_faces(BMesh *bm, const short oflag)
537 {
538         BMFace *f;
539         BMIter iter;
540
541         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
542                 if (BMO_elem_flag_test(bm, f, oflag)) {
543                         BM_face_kill(bm, f);
544                 }
545         }
546 }
547
548 void BMO_remove_tagged_edges(BMesh *bm, const short oflag)
549 {
550         BMEdge *e;
551         BMIter iter;
552
553         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
554                 if (BMO_elem_flag_test(bm, e, oflag)) {
555                         BM_edge_kill(bm, e);
556                 }
557         }
558 }
559
560 void BMO_remove_tagged_verts(BMesh *bm, const short oflag)
561 {
562         BMVert *v;
563         BMIter iter;
564
565         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
566                 if (BMO_elem_flag_test(bm, v, oflag)) {
567                         BM_vert_kill(bm, v);
568                 }
569         }
570 }
571
572 /**
573  * you need to make remove tagged verts/edges/faces
574  * api functions that take a filter callback.....
575  * and this new filter type will be for opstack flags.
576  * This is because the BM_remove_taggedXXX functions bypass iterator API.
577  *  - Ops don't care about 'UI' considerations like selection state, hide state, etc.
578  *    If you want to work on unhidden selections for instance,
579  *    copy output from a 'select context' operator to another operator....
580  */
581
582 static void bmo_remove_tagged_context_verts(BMesh *bm, const short oflag)
583 {
584         BMVert *v;
585         BMEdge *e;
586         BMFace *f;
587
588         BMIter iter;
589         BMIter itersub;
590
591         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
592                 if (BMO_elem_flag_test(bm, v, oflag)) {
593                         /* Visit edge */
594                         BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
595                                 BMO_elem_flag_enable(bm, e, oflag);
596                         }
597                         /* Visit face */
598                         BM_ITER_ELEM (f, &itersub, v, BM_FACES_OF_VERT) {
599                                 BMO_elem_flag_enable(bm, f, oflag);
600                         }
601                 }
602         }
603
604         BMO_remove_tagged_faces(bm, oflag);
605         BMO_remove_tagged_edges(bm, oflag);
606         BMO_remove_tagged_verts(bm, oflag);
607 }
608
609 static void bmo_remove_tagged_context_edges(BMesh *bm, const short oflag)
610 {
611         BMEdge *e;
612         BMFace *f;
613
614         BMIter iter;
615         BMIter itersub;
616
617         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
618                 if (BMO_elem_flag_test(bm, e, oflag)) {
619                         BM_ITER_ELEM (f, &itersub, e, BM_FACES_OF_EDGE) {
620                                 BMO_elem_flag_enable(bm, f, oflag);
621                         }
622                 }
623         }
624         BMO_remove_tagged_faces(bm, oflag);
625         BMO_remove_tagged_edges(bm, oflag);
626 }
627
628 #define DEL_WIREVERT    (1 << 10)
629
630 /**
631  * \warning oflag applies to different types in some contexts,
632  * not just the type being removed.
633  *
634  * \warning take care, uses operator flag DEL_WIREVERT
635  */
636 void BMO_remove_tagged_context(BMesh *bm, const short oflag, const int type)
637 {
638         BMVert *v;
639         BMEdge *e;
640         BMFace *f;
641
642         BMIter viter;
643         BMIter eiter;
644         BMIter fiter;
645
646         switch (type) {
647                 case DEL_VERTS:
648                 {
649                         bmo_remove_tagged_context_verts(bm, oflag);
650
651                         break;
652                 }
653                 case DEL_EDGES:
654                 {
655                         /* flush down to vert */
656                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
657                                 if (BMO_elem_flag_test(bm, e, oflag)) {
658                                         BMO_elem_flag_enable(bm, e->v1, oflag);
659                                         BMO_elem_flag_enable(bm, e->v2, oflag);
660                                 }
661                         }
662                         bmo_remove_tagged_context_edges(bm, oflag);
663                         /* remove loose vertice */
664                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
665                                 if (BMO_elem_flag_test(bm, v, oflag) && (!(v->e)))
666                                         BMO_elem_flag_enable(bm, v, DEL_WIREVERT);
667                         }
668                         BMO_remove_tagged_verts(bm, DEL_WIREVERT);
669
670                         break;
671                 }
672                 case DEL_EDGESFACES:
673                 {
674                         bmo_remove_tagged_context_edges(bm, oflag);
675
676                         break;
677                 }
678                 case DEL_ONLYFACES:
679                 {
680                         BMO_remove_tagged_faces(bm, oflag);
681
682                         break;
683                 }
684                 case DEL_ONLYTAGGED:
685                 {
686                         BMO_remove_tagged_faces(bm, oflag);
687                         BMO_remove_tagged_edges(bm, oflag);
688                         BMO_remove_tagged_verts(bm, oflag);
689
690                         break;
691                 }
692                 case DEL_FACES:
693                 {
694                         /* go through and mark all edges and all verts of all faces for delete */
695                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
696                                 if (BMO_elem_flag_test(bm, f, oflag)) {
697                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter))
698                                                 BMO_elem_flag_enable(bm, e, oflag);
699                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter))
700                                                 BMO_elem_flag_enable(bm, v, oflag);
701                                 }
702                         }
703                         /* now go through and mark all remaining faces all edges for keeping */
704                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
705                                 if (!BMO_elem_flag_test(bm, f, oflag)) {
706                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter)) {
707                                                 BMO_elem_flag_disable(bm, e, oflag);
708                                         }
709                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter)) {
710                                                 BMO_elem_flag_disable(bm, v, oflag);
711                                         }
712                                 }
713                         }
714                         /* also mark all the vertices of remaining edges for keeping */
715                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
716                                 if (!BMO_elem_flag_test(bm, e, oflag)) {
717                                         BMO_elem_flag_disable(bm, e->v1, oflag);
718                                         BMO_elem_flag_disable(bm, e->v2, oflag);
719                                 }
720                         }
721                         /* now delete marked face */
722                         BMO_remove_tagged_faces(bm, oflag);
723                         /* delete marked edge */
724                         BMO_remove_tagged_edges(bm, oflag);
725                         /* remove loose vertice */
726                         BMO_remove_tagged_verts(bm, oflag);
727
728                         break;
729                 }
730                 case DEL_ALL:
731                 {
732                         /* does this option even belong in here? */
733                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
734                                 BMO_elem_flag_enable(bm, f, oflag);
735                         }
736                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
737                                 BMO_elem_flag_enable(bm, e, oflag);
738                         }
739                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
740                                 BMO_elem_flag_enable(bm, v, oflag);
741                         }
742
743                         BMO_remove_tagged_faces(bm, oflag);
744                         BMO_remove_tagged_edges(bm, oflag);
745                         BMO_remove_tagged_verts(bm, oflag);
746
747                         break;
748                 }
749         }
750 }
751 /*************************************************************/
752
753
754 static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
755                                const BMVert *source_vertex, BMVert *target_vertex)
756 {
757         if ((source_mesh == target_mesh) && (source_vertex == target_vertex)) {
758                 BLI_assert(!"BMVert: source and targer match");
759                 return;
760         }
761         copy_v3_v3(target_vertex->no, source_vertex->no);
762         CustomData_bmesh_free_block_data(&target_mesh->vdata, &target_vertex->head.data);
763         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata,
764                                    source_vertex->head.data, &target_vertex->head.data);
765 }
766
767 static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
768                                const BMEdge *source_edge, BMEdge *target_edge)
769 {
770         if ((source_mesh == target_mesh) && (source_edge == target_edge)) {
771                 BLI_assert(!"BMEdge: source and targer match");
772                 return;
773         }
774         CustomData_bmesh_free_block_data(&target_mesh->edata, &target_edge->head.data);
775         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata,
776                                    source_edge->head.data, &target_edge->head.data);
777 }
778
779 static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
780                                const BMLoop *source_loop, BMLoop *target_loop)
781 {
782         if ((source_mesh == target_mesh) && (source_loop == target_loop)) {
783                 BLI_assert(!"BMLoop: source and targer match");
784                 return;
785         }
786         CustomData_bmesh_free_block_data(&target_mesh->ldata, &target_loop->head.data);
787         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata,
788                                    source_loop->head.data, &target_loop->head.data);
789 }
790
791 static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
792                                const BMFace *source_face, BMFace *target_face)
793 {
794         if ((source_mesh == target_mesh) && (source_face == target_face)) {
795                 BLI_assert(!"BMFace: source and targer match");
796                 return;
797         }
798         copy_v3_v3(target_face->no, source_face->no);
799         CustomData_bmesh_free_block_data(&target_mesh->pdata, &target_face->head.data);
800         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata,
801                                    source_face->head.data, &target_face->head.data);
802         target_face->mat_nr = source_face->mat_nr;
803 }
804
805 /* BMESH_TODO: Special handling for hide flags? */
806 /* BMESH_TODO: swap src/dst args, everywhere else in bmesh does other way round */
807
808 /**
809  * Copies attributes, e.g. customdata, header flags, etc, from one element
810  * to another of the same type.
811  */
812 void BM_elem_attrs_copy_ex(BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v,
813                            const char hflag_mask)
814 {
815         const BMHeader *ele_src = ele_src_v;
816         BMHeader *ele_dst = ele_dst_v;
817
818         BLI_assert(ele_src->htype == ele_dst->htype);
819
820         if (ele_src->htype != ele_dst->htype) {
821                 BLI_assert(!"type mismatch");
822                 return;
823         }
824
825         if ((hflag_mask & BM_ELEM_SELECT) == 0) {
826                 /* First we copy select */
827                 if (BM_elem_flag_test((BMElem *)ele_src, BM_ELEM_SELECT)) {
828                         BM_elem_select_set(bm_dst, (BMElem *)ele_dst, true);
829                 }
830         }
831
832         /* Now we copy flags */
833         if (hflag_mask == 0) {
834                 ele_dst->hflag = ele_src->hflag;
835         }
836         else {
837                 ele_dst->hflag = ((ele_dst->hflag & hflag_mask) | (ele_src->hflag & ~hflag_mask));
838         }
839
840         /* Copy specific attributes */
841         switch (ele_dst->htype) {
842                 case BM_VERT:
843                         bm_vert_attrs_copy(bm_src, bm_dst, (const BMVert *)ele_src, (BMVert *)ele_dst);
844                         break;
845                 case BM_EDGE:
846                         bm_edge_attrs_copy(bm_src, bm_dst, (const BMEdge *)ele_src, (BMEdge *)ele_dst);
847                         break;
848                 case BM_LOOP:
849                         bm_loop_attrs_copy(bm_src, bm_dst, (const BMLoop *)ele_src, (BMLoop *)ele_dst);
850                         break;
851                 case BM_FACE:
852                         bm_face_attrs_copy(bm_src, bm_dst, (const BMFace *)ele_src, (BMFace *)ele_dst);
853                         break;
854                 default:
855                         BLI_assert(0);
856                         break;
857         }
858 }
859
860 void BM_elem_attrs_copy(BMesh *bm_src, BMesh *bm_dst, const void *ele_src, void *ele_dst)
861 {
862         /* BMESH_TODO, default 'use_flags' to false */
863         BM_elem_attrs_copy_ex(bm_src, bm_dst, ele_src, ele_dst, 0);
864 }
865
866 /* helper function for 'BM_mesh_copy' */
867 static BMFace *bm_mesh_copy_new_face(BMesh *bm_new, BMesh *bm_old,
868                                      BMVert **vtable, BMEdge **etable,
869                                      BMFace *f)
870 {
871         BMLoop **loops = BLI_array_alloca(loops, f->len);
872         BMVert **verts = BLI_array_alloca(verts, f->len);
873         BMEdge **edges = BLI_array_alloca(edges, f->len);
874
875         BMFace *f_new;
876         BMLoop *l_iter, *l_first;
877         int j;
878
879         j = 0;
880         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
881         do {
882                 loops[j] = l_iter;
883                 verts[j] = vtable[BM_elem_index_get(l_iter->v)];
884                 edges[j] = etable[BM_elem_index_get(l_iter->e)];
885                 j++;
886         } while ((l_iter = l_iter->next) != l_first);
887
888         f_new = BM_face_create(bm_new, verts, edges, f->len, BM_CREATE_SKIP_CD);
889
890         if (UNLIKELY(f_new == NULL)) {
891                 return NULL;
892         }
893
894         /* use totface in case adding some faces fails */
895         BM_elem_index_set(f_new, (bm_new->totface - 1)); /* set_inline */
896
897         BM_elem_attrs_copy(bm_old, bm_new, f, f_new);
898
899         j = 0;
900         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
901         do {
902                 BM_elem_attrs_copy(bm_old, bm_new, loops[j], l_iter);
903                 j++;
904         } while ((l_iter = l_iter->next) != l_first);
905
906         return f_new;
907 }
908
909 void BM_mesh_copy_init_customdata(BMesh *bm_dst, BMesh *bm_src, const BMAllocTemplate *allocsize)
910 {
911         if (allocsize == NULL) {
912                 allocsize = &bm_mesh_allocsize_default;
913         }
914
915         CustomData_copy(&bm_src->vdata, &bm_dst->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
916         CustomData_copy(&bm_src->edata, &bm_dst->edata, CD_MASK_BMESH, CD_CALLOC, 0);
917         CustomData_copy(&bm_src->ldata, &bm_dst->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
918         CustomData_copy(&bm_src->pdata, &bm_dst->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
919
920         CustomData_bmesh_init_pool(&bm_dst->vdata, allocsize->totvert, BM_VERT);
921         CustomData_bmesh_init_pool(&bm_dst->edata, allocsize->totedge, BM_EDGE);
922         CustomData_bmesh_init_pool(&bm_dst->ldata, allocsize->totloop, BM_LOOP);
923         CustomData_bmesh_init_pool(&bm_dst->pdata, allocsize->totface, BM_FACE);
924 }
925
926
927 BMesh *BM_mesh_copy(BMesh *bm_old)
928 {
929         BMesh *bm_new;
930         BMVert *v, *v_new, **vtable = NULL;
931         BMEdge *e, *e_new, **etable = NULL;
932         BMFace *f, *f_new, **ftable = NULL;
933         BMElem **eletable;
934         BMEditSelection *ese;
935         BMIter iter;
936         int i;
937         const BMAllocTemplate allocsize = {bm_old->totvert,
938                                            bm_old->totedge,
939                                            bm_old->totloop,
940                                            bm_old->totface};
941
942         /* allocate a bmesh */
943         bm_new = BM_mesh_create(&allocsize);
944
945         BM_mesh_copy_init_customdata(bm_new, bm_old, &allocsize);
946
947         vtable = MEM_mallocN(sizeof(BMVert *) * bm_old->totvert, "BM_mesh_copy vtable");
948         etable = MEM_mallocN(sizeof(BMEdge *) * bm_old->totedge, "BM_mesh_copy etable");
949         ftable = MEM_mallocN(sizeof(BMFace *) * bm_old->totface, "BM_mesh_copy ftable");
950
951         BM_ITER_MESH_INDEX (v, &iter, bm_old, BM_VERTS_OF_MESH, i) {
952                 /* copy between meshes so cant use 'example' argument */
953                 v_new = BM_vert_create(bm_new, v->co, NULL, BM_CREATE_SKIP_CD);
954                 BM_elem_attrs_copy(bm_old, bm_new, v, v_new);
955                 vtable[i] = v_new;
956                 BM_elem_index_set(v, i); /* set_inline */
957                 BM_elem_index_set(v_new, i); /* set_inline */
958         }
959         bm_old->elem_index_dirty &= ~BM_VERT;
960         bm_new->elem_index_dirty &= ~BM_VERT;
961
962         /* safety check */
963         BLI_assert(i == bm_old->totvert);
964         
965         BM_ITER_MESH_INDEX (e, &iter, bm_old, BM_EDGES_OF_MESH, i) {
966                 e_new = BM_edge_create(bm_new,
967                                        vtable[BM_elem_index_get(e->v1)],
968                                        vtable[BM_elem_index_get(e->v2)],
969                                        e, BM_CREATE_SKIP_CD);
970
971                 BM_elem_attrs_copy(bm_old, bm_new, e, e_new);
972                 etable[i] = e_new;
973                 BM_elem_index_set(e, i); /* set_inline */
974                 BM_elem_index_set(e_new, i); /* set_inline */
975         }
976         bm_old->elem_index_dirty &= ~BM_EDGE;
977         bm_new->elem_index_dirty &= ~BM_EDGE;
978
979         /* safety check */
980         BLI_assert(i == bm_old->totedge);
981         
982         BM_ITER_MESH_INDEX (f, &iter, bm_old, BM_FACES_OF_MESH, i) {
983                 BM_elem_index_set(f, i); /* set_inline */
984
985                 f_new = bm_mesh_copy_new_face(bm_new, bm_old, vtable, etable, f);
986
987                 ftable[i] = f_new;
988
989                 if (f == bm_old->act_face) bm_new->act_face = f_new;
990         }
991         bm_old->elem_index_dirty &= ~BM_FACE;
992         bm_new->elem_index_dirty &= ~BM_FACE;
993
994         /* safety check */
995         BLI_assert(i == bm_old->totface);
996
997         /* copy over edit selection history */
998         for (ese = bm_old->selected.first; ese; ese = ese->next) {
999                 BMElem *ele = NULL;
1000
1001                 switch (ese->htype) {
1002                         case BM_VERT:
1003                                 eletable = (BMElem **)vtable;
1004                                 break;
1005                         case BM_EDGE:
1006                                 eletable = (BMElem **)etable;
1007                                 break;
1008                         case BM_FACE:
1009                                 eletable = (BMElem **)ftable;
1010                                 break;
1011                         default:
1012                                 eletable = NULL;
1013                                 break;
1014                 }
1015
1016                 if (eletable) {
1017                         ele = eletable[BM_elem_index_get(ese->ele)];
1018                         if (ele) {
1019                                 BM_select_history_store(bm_new, ele);
1020                         }
1021                 }
1022         }
1023
1024         MEM_freeN(etable);
1025         MEM_freeN(vtable);
1026         MEM_freeN(ftable);
1027
1028         return bm_new;
1029 }
1030
1031 /* ME -> BM */
1032 char BM_vert_flag_from_mflag(const char  meflag)
1033 {
1034         return ( ((meflag & SELECT)       ? BM_ELEM_SELECT : 0) |
1035                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
1036                  );
1037 }
1038 char BM_edge_flag_from_mflag(const short meflag)
1039 {
1040         return ( ((meflag & SELECT)        ? BM_ELEM_SELECT : 0) |
1041                  ((meflag & ME_SEAM)       ? BM_ELEM_SEAM   : 0) |
1042                  ((meflag & ME_EDGEDRAW)   ? BM_ELEM_DRAW   : 0) |
1043                  ((meflag & ME_SHARP) == 0 ? BM_ELEM_SMOOTH : 0) | /* invert */
1044                  ((meflag & ME_HIDE)       ? BM_ELEM_HIDDEN : 0)
1045                  );
1046 }
1047 char BM_face_flag_from_mflag(const char  meflag)
1048 {
1049         return ( ((meflag & ME_FACE_SEL)  ? BM_ELEM_SELECT : 0) |
1050                  ((meflag & ME_SMOOTH)    ? BM_ELEM_SMOOTH : 0) |
1051                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
1052                  );
1053 }
1054
1055 /* BM -> ME */
1056 char  BM_vert_flag_to_mflag(BMVert *eve)
1057 {
1058         const char hflag = eve->head.hflag;
1059
1060         return ( ((hflag & BM_ELEM_SELECT)  ? SELECT  : 0) |
1061                  ((hflag & BM_ELEM_HIDDEN)  ? ME_HIDE : 0)
1062                  );
1063 }
1064
1065 short BM_edge_flag_to_mflag(BMEdge *eed)
1066 {
1067         const char hflag = eed->head.hflag;
1068
1069         return ( ((hflag & BM_ELEM_SELECT)       ? SELECT       : 0) |
1070                  ((hflag & BM_ELEM_SEAM)         ? ME_SEAM      : 0) |
1071                  ((hflag & BM_ELEM_DRAW)         ? ME_EDGEDRAW  : 0) |
1072                  ((hflag & BM_ELEM_SMOOTH) == 0  ? ME_SHARP     : 0) |
1073                  ((hflag & BM_ELEM_HIDDEN)       ? ME_HIDE      : 0) |
1074                  ((BM_edge_is_wire(eed))         ? ME_LOOSEEDGE : 0) | /* not typical */
1075                  ME_EDGERENDER
1076                  );
1077 }
1078 char  BM_face_flag_to_mflag(BMFace *efa)
1079 {
1080         const char hflag = efa->head.hflag;
1081
1082         return ( ((hflag & BM_ELEM_SELECT) ? ME_FACE_SEL : 0) |
1083                  ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH   : 0) |
1084                  ((hflag & BM_ELEM_HIDDEN) ? ME_HIDE     : 0)
1085                  );
1086 }