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