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