Merged changes in the trunk up to revision 51718.
[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 nodouble 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 int nodouble)
69 {
70         BMVert *vtar[4] = {v1, v2, v3, v4};
71         return BM_face_create_quad_tri_v(bm, vtar, v4 ? 4 : 3, example, nodouble);
72 }
73
74 BMFace *BM_face_create_quad_tri_v(BMesh *bm, BMVert **verts, int len, const BMFace *example, const int nodouble)
75 {
76         BMFace *f = NULL;
77         int 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 (nodouble) {
101                 /* check if face exists or overlaps */
102                 is_overlap = BM_face_exists(bm, 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, TRUE);
109                 edar[1] = BM_edge_create(bm, verts[1], verts[2], NULL, TRUE);
110                 if (len == 4) {
111                         edar[2] = BM_edge_create(bm, verts[2], verts[3], NULL, TRUE);
112                         edar[3] = BM_edge_create(bm, verts[3], verts[0], NULL, TRUE);
113                 }
114                 else {
115                         edar[2] = BM_edge_create(bm, verts[2], verts[0], NULL, TRUE);
116                 }
117
118                 f = BM_face_create(bm, verts, edar, len, FALSE);
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, int len, int nodouble)
175 {
176         BMEdge **edges2 = NULL;
177         BLI_array_staticdeclare(edges2, BM_NGON_STACK_SIZE);
178         BMVert **verts = NULL;
179         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
180         BMFace *f = NULL;
181         BMEdge *e;
182         BMVert *v, *ev1, *ev2;
183         int i, /* j, */ v1found, reverse;
184
185         /* this code is hideous, yeek.  I'll have to think about ways of
186          *  cleaning it up.  basically, it now combines the old BM_face_create_ngon
187          *  _and_ the old bmesh_mf functions, so its kindof smashed together
188          * - joeedh */
189
190         if (!len || !v1 || !v2 || !edges || !bm)
191                 return NULL;
192
193         /* put edges in correct order */
194         for (i = 0; i < len; i++) {
195                 BM_ELEM_API_FLAG_ENABLE(edges[i], _FLAG_MF);
196         }
197
198         ev1 = edges[0]->v1;
199         ev2 = edges[0]->v2;
200
201         if (v1 == ev2) {
202                 /* Swapping here improves performance and consistency of face
203                  * structure in the special case that the edges are already in
204                  * the correct order and winding */
205                 SWAP(BMVert *, ev1, ev2);
206         }
207
208         BLI_array_append(verts, ev1);
209         v = ev2;
210         e = edges[0];
211         do {
212                 BMEdge *e2 = e;
213
214                 BLI_array_append(verts, v);
215                 BLI_array_append(edges2, e);
216
217                 /* we only flag the verts to check if they are in the face more then once */
218                 BM_ELEM_API_FLAG_ENABLE(v, _FLAG_MV);
219
220                 do {
221                         e2 = bmesh_disk_edge_next(e2, v);
222                         if (e2 != e && BM_ELEM_API_FLAG_TEST(e2, _FLAG_MF)) {
223                                 v = BM_edge_other_vert(e2, v);
224                                 break;
225                         }
226                 } while (e2 != e);
227
228                 if (e2 == e)
229                         goto err; /* the edges do not form a closed loop */
230
231                 e = e2;
232         } while (e != edges[0]);
233
234         if (BLI_array_count(edges2) != len) {
235                 goto err; /* we didn't use all edges in forming the boundary loop */
236         }
237
238         /* ok, edges are in correct order, now ensure they are going
239          * in the correct direction */
240         v1found = reverse = FALSE;
241         for (i = 0; i < len; i++) {
242                 if (BM_vert_in_edge(edges2[i], v1)) {
243                         /* see if v1 and v2 are in the same edge */
244                         if (BM_vert_in_edge(edges2[i], v2)) {
245                                 /* if v1 is shared by the *next* edge, then the winding
246                                  * is incorrect */
247                                 if (BM_vert_in_edge(edges2[(i + 1) % len], v1)) {
248                                         reverse = TRUE;
249                                         break;
250                                 }
251                         }
252
253                         v1found = TRUE;
254                 }
255
256                 if ((v1found == FALSE) && BM_vert_in_edge(edges2[i], v2)) {
257                         reverse = TRUE;
258                         break;
259                 }
260         }
261
262         if (reverse) {
263                 for (i = 0; i < len / 2; i++) {
264                         v = verts[i];
265                         verts[i] = verts[len - i - 1];
266                         verts[len - i - 1] = v;
267                 }
268         }
269
270         for (i = 0; i < len; i++) {
271                 edges2[i] = BM_edge_exists(verts[i], verts[(i + 1) % len]);
272                 if (!edges2[i]) {
273                         goto err;
274                 }
275
276                 /* check if vert is in face more then once. if the flag is disabled. we've already visited */
277                 if (!BM_ELEM_API_FLAG_TEST(verts[i], _FLAG_MV)) {
278                         goto err;
279                 }
280                 BM_ELEM_API_FLAG_DISABLE(verts[i], _FLAG_MV);
281         }
282
283         f = BM_face_create(bm, verts, edges2, len, nodouble);
284
285         /* clean up flags */
286         for (i = 0; i < len; i++) {
287                 BM_ELEM_API_FLAG_DISABLE(edges2[i], _FLAG_MF);
288         }
289
290         BLI_array_free(verts);
291         BLI_array_free(edges2);
292
293         return f;
294
295 err:
296         for (i = 0; i < len; i++) {
297                 BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF);
298                 /* vert count may != len */
299                 if (i < BLI_array_count(verts)) {
300                         BM_ELEM_API_FLAG_DISABLE(verts[i], _FLAG_MV);
301                 }
302         }
303
304         BLI_array_free(verts);
305         BLI_array_free(edges2);
306
307         return NULL;
308 }
309
310 typedef struct AngleIndexPair {
311         float angle;
312         int index;
313 } AngleIndexPair;
314
315 static int angle_index_pair_cmp(const void *e1, const void *e2)
316 {
317         const AngleIndexPair *p1 = e1, *p2 = e2;
318         if      (p1->angle > p2->angle) return  1;
319         else if (p1->angle < p2->angle) return -1;
320         else return 0;
321 }
322
323 /**
324  * Makes an NGon from an un-ordered set of verts
325  *
326  * assumes...
327  * - that verts are only once in the list.
328  * - that the verts have roughly planer bounds
329  * - that the verts are roughly circular
330  * there can be concave areas but overlapping folds from the center point will fail.
331  *
332  * a brief explanation of the method used
333  * - find the center point
334  * - find the normal of the vcloud
335  * - order the verts around the face based on their angle to the normal vector at the center point.
336  *
337  * \note Since this is a vcloud there is no direction.
338  */
339 BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int totv, int nodouble)
340 {
341         BMFace *f;
342
343         float totv_inv = 1.0f / (float)totv;
344         int i = 0;
345
346         float cent[3], nor[3];
347
348         float *far = NULL, *far_cross = NULL;
349
350         float far_vec[3];
351         float far_cross_vec[3];
352         float sign_vec[3]; /* work out if we are pos/neg angle */
353
354         float far_dist, far_best;
355         float far_cross_dist, far_cross_best = 0.0f;
356
357         AngleIndexPair *vang;
358
359         BMVert **vert_arr_map;
360         BMEdge **edge_arr;
361         int i_prev;
362
363         unsigned int winding[2] = {0, 0};
364
365         /* get the center point and collect vector array since we loop over these a lot */
366         zero_v3(cent);
367         for (i = 0; i < totv; i++) {
368                 madd_v3_v3fl(cent, vert_arr[i]->co, totv_inv);
369         }
370
371
372         /* find the far point from cent */
373         far_best = 0.0f;
374         for (i = 0; i < totv; i++) {
375                 far_dist = len_squared_v3v3(vert_arr[i]->co, cent);
376                 if (far_dist > far_best || far == NULL) {
377                         far = vert_arr[i]->co;
378                         far_best = far_dist;
379                 }
380         }
381
382         sub_v3_v3v3(far_vec, far, cent);
383         // far_dist = len_v3(far_vec); /* real dist */ /* UNUSED */
384
385         /* --- */
386
387         /* find a point 90deg about to compare with */
388         far_cross_best = 0.0f;
389         for (i = 0; i < totv; i++) {
390
391                 if (far == vert_arr[i]->co) {
392                         continue;
393                 }
394
395                 sub_v3_v3v3(far_cross_vec, vert_arr[i]->co, cent);
396                 far_cross_dist = normalize_v3(far_cross_vec);
397
398                 /* more of a weight then a distance */
399                 far_cross_dist = (/* first we want to have a value close to zero mapped to 1 */
400                                                   1.0f - fabsf(dot_v3v3(far_vec, far_cross_vec)) *
401
402                                                   /* second  we multiply by the distance
403                                                    * so points close to the center are not preferred */
404                                                   far_cross_dist);
405
406                 if (far_cross_dist > far_cross_best || far_cross == NULL) {
407                         far_cross = vert_arr[i]->co;
408                         far_cross_best = far_cross_dist;
409                 }
410         }
411
412         sub_v3_v3v3(far_cross_vec, far_cross, cent);
413
414         /* --- */
415
416         /* now we have 2 vectors we can have a cross product */
417         cross_v3_v3v3(nor, far_vec, far_cross_vec);
418         normalize_v3(nor);
419         cross_v3_v3v3(sign_vec, far_vec, nor); /* this vector should match 'far_cross_vec' closely */
420
421         /* --- */
422
423         /* now calculate every points angle around the normal (signed) */
424         vang = MEM_mallocN(sizeof(AngleIndexPair) * totv, __func__);
425
426         for (i = 0; i < totv; i++) {
427                 float co[3];
428                 float proj_vec[3];
429                 float angle;
430
431                 /* center relative vec */
432                 sub_v3_v3v3(co, vert_arr[i]->co, cent);
433
434                 /* align to plane */
435                 project_v3_v3v3(proj_vec, co, nor);
436                 sub_v3_v3(co, proj_vec);
437
438                 /* now 'co' is valid - we can compare its angle against the far vec */
439                 angle = angle_v3v3(far_vec, co);
440
441                 if (dot_v3v3(co, sign_vec) < 0.0f) {
442                         angle = -angle;
443                 }
444
445                 vang[i].angle = angle;
446                 vang[i].index = i;
447         }
448
449         /* sort by angle and magic! - we have our ngon */
450         qsort(vang, totv, sizeof(AngleIndexPair), angle_index_pair_cmp);
451
452         /* --- */
453
454         /* create edges and find the winding (if faces are attached to any existing edges) */
455         vert_arr_map = MEM_mallocN(sizeof(BMVert **) * totv, __func__);
456         edge_arr = MEM_mallocN(sizeof(BMEdge **) * totv, __func__);
457
458         for (i = 0; i < totv; i++) {
459                 vert_arr_map[i] = vert_arr[vang[i].index];
460         }
461         MEM_freeN(vang);
462
463         i_prev = totv - 1;
464         for (i = 0; i < totv; i++) {
465                 edge_arr[i] = BM_edge_create(bm, vert_arr_map[i_prev], vert_arr_map[i], NULL, TRUE);
466
467                 /* the edge may exist already and be attached to a face
468                  * in this case we can find the best winding to use for the new face */
469                 if (edge_arr[i]->l) {
470                         BMVert *test_v1, *test_v2;
471                         /* we want to use the reverse winding to the existing order */
472                         BM_edge_ordered_verts(edge_arr[i], &test_v2, &test_v1);
473                         winding[(vert_arr_map[i_prev] == test_v2)]++;
474
475                 }
476
477                 i_prev = i;
478         }
479
480         /* --- */
481
482         if (winding[0] < winding[1]) {
483                 winding[0] = 1;
484                 winding[1] = 0;
485         }
486         else {
487                 winding[0] = 0;
488                 winding[1] = 1;
489         }
490
491         /* --- */
492
493         /* create the face */
494         f = BM_face_create_ngon(bm, vert_arr_map[winding[0]], vert_arr_map[winding[1]], edge_arr, totv, nodouble);
495
496         MEM_freeN(edge_arr);
497         MEM_freeN(vert_arr_map);
498
499         return f;
500 }
501
502 /**
503  * Called by operators to remove elements that they have marked for
504  * removal.
505  */
506 void BMO_remove_tagged_faces(BMesh *bm, const short oflag)
507 {
508         BMFace *f;
509         BMIter iter;
510
511         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
512                 if (BMO_elem_flag_test(bm, f, oflag)) {
513                         BM_face_kill(bm, f);
514                 }
515         }
516 }
517
518 void BMO_remove_tagged_edges(BMesh *bm, const short oflag)
519 {
520         BMEdge *e;
521         BMIter iter;
522
523         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
524                 if (BMO_elem_flag_test(bm, e, oflag)) {
525                         BM_edge_kill(bm, e);
526                 }
527         }
528 }
529
530 void BMO_remove_tagged_verts(BMesh *bm, const short oflag)
531 {
532         BMVert *v;
533         BMIter iter;
534
535         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
536                 if (BMO_elem_flag_test(bm, v, oflag)) {
537                         BM_vert_kill(bm, v);
538                 }
539         }
540 }
541
542 /**
543  * you need to make remove tagged verts/edges/faces
544  * api functions that take a filter callback.....
545  * and this new filter type will be for opstack flags.
546  * This is because the BM_remove_taggedXXX functions bypass iterator API.
547  *  - Ops don't care about 'UI' considerations like selection state, hide state, etc.
548  *    If you want to work on unhidden selections for instance,
549  *    copy output from a 'select context' operator to another operator....
550  */
551
552 static void bmo_remove_tagged_context_verts(BMesh *bm, const short oflag)
553 {
554         BMVert *v;
555         BMEdge *e;
556         BMFace *f;
557
558         BMIter iter;
559         BMIter itersub;
560
561         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
562                 if (BMO_elem_flag_test(bm, v, oflag)) {
563                         /* Visit edge */
564                         BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
565                                 BMO_elem_flag_enable(bm, e, oflag);
566                         }
567                         /* Visit face */
568                         BM_ITER_ELEM (f, &itersub, v, BM_FACES_OF_VERT) {
569                                 BMO_elem_flag_enable(bm, f, oflag);
570                         }
571                 }
572         }
573
574         BMO_remove_tagged_faces(bm, oflag);
575         BMO_remove_tagged_edges(bm, oflag);
576         BMO_remove_tagged_verts(bm, oflag);
577 }
578
579 static void bmo_remove_tagged_context_edges(BMesh *bm, const short oflag)
580 {
581         BMEdge *e;
582         BMFace *f;
583
584         BMIter iter;
585         BMIter itersub;
586
587         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
588                 if (BMO_elem_flag_test(bm, e, oflag)) {
589                         BM_ITER_ELEM (f, &itersub, e, BM_FACES_OF_EDGE) {
590                                 BMO_elem_flag_enable(bm, f, oflag);
591                         }
592                 }
593         }
594         BMO_remove_tagged_faces(bm, oflag);
595         BMO_remove_tagged_edges(bm, oflag);
596 }
597
598 #define DEL_WIREVERT    (1 << 10)
599
600 /**
601  * \warning oflag applies to different types in some contexts,
602  * not just the type being removed.
603  *
604  * \warning take care, uses operator flag DEL_WIREVERT
605  */
606 void BMO_remove_tagged_context(BMesh *bm, const short oflag, const int type)
607 {
608         BMVert *v;
609         BMEdge *e;
610         BMFace *f;
611
612         BMIter viter;
613         BMIter eiter;
614         BMIter fiter;
615
616         switch (type) {
617                 case DEL_VERTS:
618                 {
619                         bmo_remove_tagged_context_verts(bm, oflag);
620
621                         break;
622                 }
623                 case DEL_EDGES:
624                 {
625                         /* flush down to vert */
626                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
627                                 if (BMO_elem_flag_test(bm, e, oflag)) {
628                                         BMO_elem_flag_enable(bm, e->v1, oflag);
629                                         BMO_elem_flag_enable(bm, e->v2, oflag);
630                                 }
631                         }
632                         bmo_remove_tagged_context_edges(bm, oflag);
633                         /* remove loose vertice */
634                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
635                                 if (BMO_elem_flag_test(bm, v, oflag) && (!(v->e)))
636                                         BMO_elem_flag_enable(bm, v, DEL_WIREVERT);
637                         }
638                         BMO_remove_tagged_verts(bm, DEL_WIREVERT);
639
640                         break;
641                 }
642                 case DEL_EDGESFACES:
643                 {
644                         bmo_remove_tagged_context_edges(bm, oflag);
645
646                         break;
647                 }
648                 case DEL_ONLYFACES:
649                 {
650                         BMO_remove_tagged_faces(bm, oflag);
651
652                         break;
653                 }
654                 case DEL_ONLYTAGGED:
655                 {
656                         BMO_remove_tagged_faces(bm, oflag);
657                         BMO_remove_tagged_edges(bm, oflag);
658                         BMO_remove_tagged_verts(bm, oflag);
659
660                         break;
661                 }
662                 case DEL_FACES:
663                 {
664                         /* go through and mark all edges and all verts of all faces for delet */
665                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
666                                 if (BMO_elem_flag_test(bm, f, oflag)) {
667                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter))
668                                                 BMO_elem_flag_enable(bm, e, oflag);
669                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter))
670                                                 BMO_elem_flag_enable(bm, v, oflag);
671                                 }
672                         }
673                         /* now go through and mark all remaining faces all edges for keeping */
674                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
675                                 if (!BMO_elem_flag_test(bm, f, oflag)) {
676                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter)) {
677                                                 BMO_elem_flag_disable(bm, e, oflag);
678                                         }
679                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter)) {
680                                                 BMO_elem_flag_disable(bm, v, oflag);
681                                         }
682                                 }
683                         }
684                         /* also mark all the vertices of remaining edges for keeping */
685                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
686                                 if (!BMO_elem_flag_test(bm, e, oflag)) {
687                                         BMO_elem_flag_disable(bm, e->v1, oflag);
688                                         BMO_elem_flag_disable(bm, e->v2, oflag);
689                                 }
690                         }
691                         /* now delete marked face */
692                         BMO_remove_tagged_faces(bm, oflag);
693                         /* delete marked edge */
694                         BMO_remove_tagged_edges(bm, oflag);
695                         /* remove loose vertice */
696                         BMO_remove_tagged_verts(bm, oflag);
697
698                         break;
699                 }
700                 case DEL_ALL:
701                 {
702                         /* does this option even belong in here? */
703                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
704                                 BMO_elem_flag_enable(bm, f, oflag);
705                         }
706                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
707                                 BMO_elem_flag_enable(bm, e, oflag);
708                         }
709                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
710                                 BMO_elem_flag_enable(bm, v, oflag);
711                         }
712
713                         BMO_remove_tagged_faces(bm, oflag);
714                         BMO_remove_tagged_edges(bm, oflag);
715                         BMO_remove_tagged_verts(bm, oflag);
716
717                         break;
718                 }
719         }
720 }
721 /*************************************************************/
722
723
724 static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
725                                const BMVert *source_vertex, BMVert *target_vertex)
726 {
727         if ((source_mesh == target_mesh) && (source_vertex == target_vertex)) {
728                 BLI_assert(!"BMVert: source and targer match");
729                 return;
730         }
731         copy_v3_v3(target_vertex->no, source_vertex->no);
732         CustomData_bmesh_free_block(&target_mesh->vdata, &target_vertex->head.data);
733         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata,
734                                    source_vertex->head.data, &target_vertex->head.data);
735 }
736
737 static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
738                                const BMEdge *source_edge, BMEdge *target_edge)
739 {
740         if ((source_mesh == target_mesh) && (source_edge == target_edge)) {
741                 BLI_assert(!"BMEdge: source and targer match");
742                 return;
743         }
744         CustomData_bmesh_free_block(&target_mesh->edata, &target_edge->head.data);
745         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata,
746                                    source_edge->head.data, &target_edge->head.data);
747 }
748
749 static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
750                                const BMLoop *source_loop, BMLoop *target_loop)
751 {
752         if ((source_mesh == target_mesh) && (source_loop == target_loop)) {
753                 BLI_assert(!"BMLoop: source and targer match");
754                 return;
755         }
756         CustomData_bmesh_free_block(&target_mesh->ldata, &target_loop->head.data);
757         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata,
758                                    source_loop->head.data, &target_loop->head.data);
759 }
760
761 static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
762                                const BMFace *source_face, BMFace *target_face)
763 {
764         if ((source_mesh == target_mesh) && (source_face == target_face)) {
765                 BLI_assert(!"BMFace: source and targer match");
766                 return;
767         }
768         copy_v3_v3(target_face->no, source_face->no);
769         CustomData_bmesh_free_block(&target_mesh->pdata, &target_face->head.data);
770         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata,
771                                    source_face->head.data, &target_face->head.data);
772         target_face->mat_nr = source_face->mat_nr;
773 }
774
775 /* BMESH_TODO: Special handling for hide flags? */
776
777 /**
778  * Copies attributes, e.g. customdata, header flags, etc, from one element
779  * to another of the same type.
780  */
781 void BM_elem_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, const void *source, void *target)
782 {
783         const BMHeader *sheader = source;
784         BMHeader *theader = target;
785
786         BLI_assert(sheader->htype == theader->htype);
787
788         if (sheader->htype != theader->htype) {
789                 BLI_assert(!"type mismatch");
790                 return;
791         }
792
793         /* First we copy select */
794         if (BM_elem_flag_test((BMElem *)sheader, BM_ELEM_SELECT)) {
795                 BM_elem_select_set(target_mesh, (BMElem *)target, TRUE);
796         }
797         
798         /* Now we copy flags */
799         theader->hflag = sheader->hflag;
800         
801         /* Copy specific attributes */
802         switch (theader->htype) {
803                 case BM_VERT:
804                         bm_vert_attrs_copy(source_mesh, target_mesh, (const BMVert *)source, (BMVert *)target);
805                         break;
806                 case BM_EDGE:
807                         bm_edge_attrs_copy(source_mesh, target_mesh, (const BMEdge *)source, (BMEdge *)target);
808                         break;
809                 case BM_LOOP:
810                         bm_loop_attrs_copy(source_mesh, target_mesh, (const BMLoop *)source, (BMLoop *)target);
811                         break;
812                 case BM_FACE:
813                         bm_face_attrs_copy(source_mesh, target_mesh, (const BMFace *)source, (BMFace *)target);
814                         break;
815                 default:
816                         BLI_assert(0);
817         }
818 }
819
820 BMesh *BM_mesh_copy(BMesh *bm_old)
821 {
822         BMesh *bm_new;
823         BMVert *v, *v2, **vtable = NULL;
824         BMEdge *e, *e2, **edges = NULL, **etable = NULL;
825         BMElem **eletable;
826         BLI_array_declare(edges);
827         BMLoop *l, /* *l2, */ **loops = NULL;
828         BLI_array_declare(loops);
829         BMFace *f, *f2, **ftable = NULL;
830         BMEditSelection *ese;
831         BMIter iter, liter;
832         int i, j;
833         BMAllocTemplate allocsize = {bm_old->totvert,
834                                      bm_old->totedge,
835                                      bm_old->totloop,
836                                      bm_old->totface};
837
838         /* allocate a bmesh */
839         bm_new = BM_mesh_create(&allocsize);
840
841         CustomData_copy(&bm_old->vdata, &bm_new->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
842         CustomData_copy(&bm_old->edata, &bm_new->edata, CD_MASK_BMESH, CD_CALLOC, 0);
843         CustomData_copy(&bm_old->ldata, &bm_new->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
844         CustomData_copy(&bm_old->pdata, &bm_new->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
845
846         CustomData_bmesh_init_pool(&bm_new->vdata, allocsize.totvert, BM_VERT);
847         CustomData_bmesh_init_pool(&bm_new->edata, allocsize.totedge, BM_EDGE);
848         CustomData_bmesh_init_pool(&bm_new->ldata, allocsize.totloop, BM_LOOP);
849         CustomData_bmesh_init_pool(&bm_new->pdata, allocsize.totface, BM_FACE);
850
851         vtable = MEM_mallocN(sizeof(BMVert *) * bm_old->totvert, "BM_mesh_copy vtable");
852         etable = MEM_mallocN(sizeof(BMEdge *) * bm_old->totedge, "BM_mesh_copy etable");
853         ftable = MEM_mallocN(sizeof(BMFace *) * bm_old->totface, "BM_mesh_copy ftable");
854
855         v = BM_iter_new(&iter, bm_old, BM_VERTS_OF_MESH, NULL);
856         for (i = 0; v; v = BM_iter_step(&iter), i++) {
857                 v2 = BM_vert_create(bm_new, v->co, NULL); /* copy between meshes so cant use 'example' argument */
858                 BM_elem_attrs_copy(bm_old, bm_new, v, v2);
859                 vtable[i] = v2;
860                 BM_elem_index_set(v, i); /* set_inline */
861                 BM_elem_index_set(v2, i); /* set_inline */
862         }
863         bm_old->elem_index_dirty &= ~BM_VERT;
864         bm_new->elem_index_dirty &= ~BM_VERT;
865
866         /* safety check */
867         BLI_assert(i == bm_old->totvert);
868         
869         e = BM_iter_new(&iter, bm_old, BM_EDGES_OF_MESH, NULL);
870         for (i = 0; e; e = BM_iter_step(&iter), i++) {
871                 e2 = BM_edge_create(bm_new,
872                                     vtable[BM_elem_index_get(e->v1)],
873                                     vtable[BM_elem_index_get(e->v2)],
874                                     e, FALSE);
875
876                 BM_elem_attrs_copy(bm_old, bm_new, e, e2);
877                 etable[i] = e2;
878                 BM_elem_index_set(e, i); /* set_inline */
879                 BM_elem_index_set(e2, i); /* set_inline */
880         }
881         bm_old->elem_index_dirty &= ~BM_EDGE;
882         bm_new->elem_index_dirty &= ~BM_EDGE;
883
884         /* safety check */
885         BLI_assert(i == bm_old->totedge);
886         
887         f = BM_iter_new(&iter, bm_old, BM_FACES_OF_MESH, NULL);
888         for (i = 0; f; f = BM_iter_step(&iter), i++) {
889                 BM_elem_index_set(f, i); /* set_inline */
890
891                 BLI_array_empty(loops);
892                 BLI_array_empty(edges);
893                 BLI_array_grow_items(loops, f->len);
894                 BLI_array_grow_items(edges, f->len);
895
896                 l = BM_iter_new(&liter, bm_old, BM_LOOPS_OF_FACE, f);
897                 for (j = 0; j < f->len; j++, l = BM_iter_step(&liter)) {
898                         loops[j] = l;
899                         edges[j] = etable[BM_elem_index_get(l->e)];
900                 }
901
902                 v = vtable[BM_elem_index_get(loops[0]->v)];
903                 v2 = vtable[BM_elem_index_get(loops[1]->v)];
904
905                 if (!bmesh_verts_in_edge(v, v2, edges[0])) {
906                         v = vtable[BM_elem_index_get(loops[BLI_array_count(loops) - 1]->v)];
907                         v2 = vtable[BM_elem_index_get(loops[0]->v)];
908                 }
909
910                 f2 = BM_face_create_ngon(bm_new, v, v2, edges, f->len, FALSE);
911                 if (UNLIKELY(f2 == NULL)) {
912                         continue;
913                 }
914                 /* use totface in case adding some faces fails */
915                 BM_elem_index_set(f2, (bm_new->totface - 1)); /* set_inline */
916
917                 ftable[i] = f2;
918
919                 BM_elem_attrs_copy(bm_old, bm_new, f, f2);
920                 copy_v3_v3(f2->no, f->no);
921
922                 l = BM_iter_new(&liter, bm_new, BM_LOOPS_OF_FACE, f2);
923                 for (j = 0; j < f->len; j++, l = BM_iter_step(&liter)) {
924                         BM_elem_attrs_copy(bm_old, bm_new, loops[j], l);
925                 }
926
927                 if (f == bm_old->act_face) bm_new->act_face = f2;
928         }
929         bm_old->elem_index_dirty &= ~BM_FACE;
930         bm_new->elem_index_dirty &= ~BM_FACE;
931
932         /* safety check */
933         BLI_assert(i == bm_old->totface);
934
935         /* copy over edit selection history */
936         for (ese = bm_old->selected.first; ese; ese = ese->next) {
937                 BMElem *ele = NULL;
938
939                 switch (ese->htype) {
940                         case BM_VERT:
941                                 eletable = (BMElem **)vtable;
942                                 break;
943                         case BM_EDGE:
944                                 eletable = (BMElem **)etable;
945                                 break;
946                         case BM_FACE:
947                                 eletable = (BMElem **)ftable;
948                                 break;
949                         default:
950                                 eletable = NULL;
951                                 break;
952                 }
953
954                 if (eletable) {
955                         ele = eletable[BM_elem_index_get(ese->ele)];
956                         if (ele) {
957                                 BM_select_history_store(bm_new, ele);
958                         }
959                 }
960         }
961
962         MEM_freeN(etable);
963         MEM_freeN(vtable);
964         MEM_freeN(ftable);
965
966         BLI_array_free(loops);
967         BLI_array_free(edges);
968
969         return bm_new;
970 }
971
972 /* ME -> BM */
973 char BM_vert_flag_from_mflag(const char  meflag)
974 {
975         return ( ((meflag & SELECT)       ? BM_ELEM_SELECT : 0) |
976                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
977                  );
978 }
979 char BM_edge_flag_from_mflag(const short meflag)
980 {
981         return ( ((meflag & SELECT)        ? BM_ELEM_SELECT : 0) |
982                  ((meflag & ME_SEAM)       ? BM_ELEM_SEAM   : 0) |
983                  ((meflag & ME_EDGEDRAW)   ? BM_ELEM_DRAW   : 0) |
984                  ((meflag & ME_SHARP) == 0 ? BM_ELEM_SMOOTH : 0) | /* invert */
985                  ((meflag & ME_HIDE)       ? BM_ELEM_HIDDEN : 0) |
986                  ((meflag & ME_FREESTYLE_EDGE) ? BM_ELEM_FREESTYLE : 0)
987                  );
988 }
989 char BM_face_flag_from_mflag(const char  meflag)
990 {
991         return ( ((meflag & ME_FACE_SEL)  ? BM_ELEM_SELECT : 0) |
992                  ((meflag & ME_SMOOTH)    ? BM_ELEM_SMOOTH : 0) |
993                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0) |
994                  ((meflag & ME_FREESTYLE_FACE) ? BM_ELEM_FREESTYLE : 0)
995                  );
996 }
997
998 /* BM -> ME */
999 char  BM_vert_flag_to_mflag(BMVert *eve)
1000 {
1001         const char hflag = eve->head.hflag;
1002
1003         return ( ((hflag & BM_ELEM_SELECT)  ? SELECT  : 0) |
1004                  ((hflag & BM_ELEM_HIDDEN)  ? ME_HIDE : 0)
1005                  );
1006 }
1007
1008 short BM_edge_flag_to_mflag(BMEdge *eed)
1009 {
1010         const char hflag = eed->head.hflag;
1011
1012         return ( ((hflag & BM_ELEM_SELECT)       ? SELECT       : 0) |
1013                  ((hflag & BM_ELEM_SEAM)         ? ME_SEAM      : 0) |
1014                  ((hflag & BM_ELEM_DRAW)         ? ME_EDGEDRAW  : 0) |
1015                  ((hflag & BM_ELEM_SMOOTH) == 0  ? ME_SHARP     : 0) |
1016                  ((hflag & BM_ELEM_HIDDEN)       ? ME_HIDE      : 0) |
1017                  ((hflag & BM_ELEM_FREESTYLE)    ? ME_FREESTYLE_EDGE : 0) |
1018                  ((BM_edge_is_wire(eed))         ? ME_LOOSEEDGE : 0) | /* not typical */
1019                  ME_EDGERENDER
1020                  );
1021 }
1022 char  BM_face_flag_to_mflag(BMFace *efa)
1023 {
1024         const char hflag = efa->head.hflag;
1025
1026         return ( ((hflag & BM_ELEM_SELECT) ? ME_FACE_SEL : 0) |
1027                  ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH   : 0) |
1028                  ((hflag & BM_ELEM_HIDDEN) ? ME_HIDE     : 0) |
1029                  ((hflag & BM_ELEM_FREESTYLE) ? ME_FREESTYLE_FACE : 0)
1030                  );
1031 }