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