Fix T56872: Edge slide gives invalid normals
[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
50 /**
51  * Fill in a vertex array from an edge array.
52  *
53  * \returns false if any verts aren't found.
54  */
55 bool BM_verts_from_edges(BMVert **vert_arr, BMEdge **edge_arr, const int len)
56 {
57         int i, i_prev = len - 1;
58         for (i = 0; i < len; i++) {
59                 vert_arr[i] = BM_edge_share_vert(edge_arr[i_prev], edge_arr[i]);
60                 if (vert_arr[i] == NULL) {
61                         return false;
62                 }
63                 i_prev = i;
64         }
65         return true;
66 }
67
68 /**
69  * Fill in an edge array from a vertex array (connected polygon loop).
70  *
71  * \returns false if any edges aren't found.
72  */
73 bool BM_edges_from_verts(BMEdge **edge_arr, BMVert **vert_arr, const int len)
74 {
75         int i, i_prev = len - 1;
76         for (i = 0; i < len; i++) {
77                 edge_arr[i_prev] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]);
78                 if (edge_arr[i_prev] == NULL) {
79                         return false;
80                 }
81                 i_prev = i;
82         }
83         return true;
84 }
85
86 /**
87  * Fill in an edge array from a vertex array (connected polygon loop).
88  * Creating edges as-needed.
89  */
90 void BM_edges_from_verts_ensure(BMesh *bm, BMEdge **edge_arr, BMVert **vert_arr, const int len)
91 {
92         int i, i_prev = len - 1;
93         for (i = 0; i < len; i++) {
94                 edge_arr[i_prev] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE);
95                 i_prev = i;
96         }
97 }
98
99 /* prototypes */
100 static void bm_loop_attrs_copy(
101         BMesh *source_mesh, BMesh *target_mesh,
102         const BMLoop *source_loop, BMLoop *target_loop, uint64_t cd_mask);
103
104 /**
105  * \brief Make Quad/Triangle
106  *
107  * Creates a new quad or triangle from a list of 3 or 4 vertices.
108  * If \a no_double is true, then a check is done to see if a face
109  * with these vertices already exists and returns it instead.
110  *
111  * If a pointer to an example face is provided, it's custom data
112  * and properties will be copied to the new face.
113  *
114  * \note The winding of the face is determined by the order
115  * of the vertices in the vertex array.
116  */
117
118 BMFace *BM_face_create_quad_tri(
119         BMesh *bm,
120         BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
121         const BMFace *f_example, const eBMCreateFlag create_flag)
122 {
123         BMVert *vtar[4] = {v1, v2, v3, v4};
124         return BM_face_create_verts(bm, vtar, v4 ? 4 : 3, f_example, create_flag, true);
125 }
126
127 /**
128  * \brief copies face loop data from shared adjacent faces.
129  *
130  * \param filter_fn  A function that filters the source loops before copying (don't always want to copy all)
131  *
132  * \note when a matching edge is found, both loops of that edge are copied
133  * this is done since the face may not be completely surrounded by faces,
134  * this way: a quad with 2 connected quads on either side will still get all 4 loops updated
135  */
136 void BM_face_copy_shared(
137         BMesh *bm, BMFace *f,
138         BMLoopFilterFunc filter_fn, void *user_data)
139 {
140         BMLoop *l_first;
141         BMLoop *l_iter;
142
143 #ifdef DEBUG
144         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
145         do {
146                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_iter, _FLAG_OVERLAP) == 0);
147         } while ((l_iter = l_iter->next) != l_first);
148 #endif
149
150         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
151         do {
152                 BMLoop *l_other = l_iter->radial_next;
153
154                 if (l_other && l_other != l_iter) {
155                         BMLoop *l_src[2];
156                         BMLoop *l_dst[2] = {l_iter, l_iter->next};
157                         uint j;
158
159                         if (l_other->v == l_iter->v) {
160                                 l_src[0] = l_other;
161                                 l_src[1] = l_other->next;
162                         }
163                         else {
164                                 l_src[0] = l_other->next;
165                                 l_src[1] = l_other;
166                         }
167
168                         for (j = 0; j < 2; j++) {
169                                 BLI_assert(l_dst[j]->v == l_src[j]->v);
170                                 if (BM_ELEM_API_FLAG_TEST(l_dst[j], _FLAG_OVERLAP) == 0) {
171                                         if ((filter_fn == NULL) || filter_fn(l_src[j], user_data)) {
172                                                 bm_loop_attrs_copy(bm, bm, l_src[j], l_dst[j], 0x0);
173                                                 BM_ELEM_API_FLAG_ENABLE(l_dst[j], _FLAG_OVERLAP);
174                                         }
175                                 }
176                         }
177                 }
178         } while ((l_iter = l_iter->next) != l_first);
179
180
181         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
182         do {
183                 BM_ELEM_API_FLAG_DISABLE(l_iter, _FLAG_OVERLAP);
184         } while ((l_iter = l_iter->next) != l_first);
185 }
186
187 /**
188  * Given an array of edges,
189  * order them using the winding defined by \a v1 & \a v2
190  * into \a edges_sort & \a verts_sort.
191  *
192  * All arrays must be \a len long.
193  */
194 static bool bm_edges_sort_winding(
195         BMVert *v1, BMVert *v2,
196         BMEdge **edges, const int len,
197         BMEdge **edges_sort, BMVert **verts_sort)
198 {
199         BMEdge *e_iter, *e_first;
200         BMVert *v_iter;
201         int i;
202
203         /* all flags _must_ be cleared on exit! */
204         for (i = 0; i < len; i++) {
205                 BM_ELEM_API_FLAG_ENABLE(edges[i], _FLAG_MF);
206                 BM_ELEM_API_FLAG_ENABLE(edges[i]->v1, _FLAG_MV);
207                 BM_ELEM_API_FLAG_ENABLE(edges[i]->v2, _FLAG_MV);
208         }
209
210         /* find first edge */
211         i = 0;
212         v_iter = v1;
213         e_iter = e_first = v1->e;
214         do {
215                 if (BM_ELEM_API_FLAG_TEST(e_iter, _FLAG_MF) &&
216                     (BM_edge_other_vert(e_iter, v_iter) == v2))
217                 {
218                         i = 1;
219                         break;
220                 }
221         } while ((e_iter = bmesh_disk_edge_next(e_iter, v_iter)) != e_first);
222         if (i == 0) {
223                 goto error;
224         }
225
226         i = 0;
227         do {
228                 /* entering loop will always succeed */
229                 if (BM_ELEM_API_FLAG_TEST(e_iter, _FLAG_MF)) {
230                         if (UNLIKELY(BM_ELEM_API_FLAG_TEST(v_iter, _FLAG_MV) == false)) {
231                                 /* vert is in loop multiple times */
232                                 goto error;
233                         }
234
235                         BM_ELEM_API_FLAG_DISABLE(e_iter, _FLAG_MF);
236                         edges_sort[i] = e_iter;
237
238                         BM_ELEM_API_FLAG_DISABLE(v_iter, _FLAG_MV);
239                         verts_sort[i] = v_iter;
240
241                         i += 1;
242
243                         /* walk onto the next vertex */
244                         v_iter = BM_edge_other_vert(e_iter, v_iter);
245                         if (i == len) {
246                                 if (UNLIKELY(v_iter != verts_sort[0])) {
247                                         goto error;
248                                 }
249                                 break;
250                         }
251
252                         e_first = e_iter;
253                 }
254         } while ((e_iter = bmesh_disk_edge_next(e_iter, v_iter)) != e_first);
255
256         if (i == len) {
257                 return true;
258         }
259
260 error:
261         for (i = 0; i < len; i++) {
262                 BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF);
263                 BM_ELEM_API_FLAG_DISABLE(edges[i]->v1, _FLAG_MV);
264                 BM_ELEM_API_FLAG_DISABLE(edges[i]->v2, _FLAG_MV);
265         }
266
267         return false;
268 }
269
270 /**
271  * \brief Make NGon
272  *
273  * Makes an ngon from an unordered list of edges.
274  * Verts \a v1 and \a v2 define the winding of the new face.
275  *
276  * \a edges are not required to be ordered, simply to to form
277  * a single closed loop as a whole.
278  *
279  * \note While this function will work fine when the edges
280  * are already sorted, if the edges are always going to be sorted,
281  * #BM_face_create should be considered over this function as it
282  * avoids some unnecessary work.
283  */
284 BMFace *BM_face_create_ngon(
285         BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len,
286         const BMFace *f_example, const eBMCreateFlag create_flag)
287 {
288         BMEdge **edges_sort = BLI_array_alloca(edges_sort, len);
289         BMVert **verts_sort = BLI_array_alloca(verts_sort, len);
290
291         BLI_assert(len && v1 && v2 && edges && bm);
292
293         if (bm_edges_sort_winding(v1, v2, edges, len, edges_sort, verts_sort)) {
294                 return BM_face_create(bm, verts_sort, edges_sort, len, f_example, create_flag);
295         }
296
297         return NULL;
298 }
299
300 /**
301  * Create an ngon from an array of sorted verts
302  *
303  * Special features this has over other functions.
304  * - Optionally calculate winding based on surrounding edges.
305  * - Optionally create edges between vertices.
306  * - Uses verts so no need to find edges (handy when you only have verts)
307  */
308 BMFace *BM_face_create_ngon_verts(
309         BMesh *bm, BMVert **vert_arr, const int len,
310         const BMFace *f_example, const eBMCreateFlag create_flag,
311         const bool calc_winding, const bool create_edges)
312 {
313         BMEdge **edge_arr = BLI_array_alloca(edge_arr, len);
314         uint winding[2] = {0, 0};
315         int i, i_prev = len - 1;
316         BMVert *v_winding[2] = {vert_arr[i_prev], vert_arr[0]};
317
318         BLI_assert(len > 2);
319
320         for (i = 0; i < len; i++) {
321                 if (create_edges) {
322                         edge_arr[i] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE);
323                 }
324                 else {
325                         edge_arr[i] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]);
326                         if (edge_arr[i] == NULL) {
327                                 return NULL;
328                         }
329                 }
330
331                 if (calc_winding) {
332                         /* the edge may exist already and be attached to a face
333                          * in this case we can find the best winding to use for the new face */
334                         if (edge_arr[i]->l) {
335                                 BMVert *test_v1, *test_v2;
336                                 /* we want to use the reverse winding to the existing order */
337                                 BM_edge_ordered_verts(edge_arr[i], &test_v2, &test_v1);
338                                 winding[(vert_arr[i_prev] == test_v2)]++;
339                                 BLI_assert(vert_arr[i_prev] == test_v2 || vert_arr[i_prev] == test_v1);
340                         }
341                 }
342
343                 i_prev = i;
344         }
345
346         /* --- */
347
348         if (calc_winding) {
349                 if (winding[0] < winding[1]) {
350                         winding[0] = 1;
351                         winding[1] = 0;
352                 }
353                 else {
354                         winding[0] = 0;
355                         winding[1] = 1;
356                 }
357         }
358         else {
359                 winding[0] = 0;
360                 winding[1] = 1;
361         }
362
363         /* --- */
364
365         /* create the face */
366         return BM_face_create_ngon(
367                 bm,
368                 v_winding[winding[0]],
369                 v_winding[winding[1]],
370                 edge_arr, len,
371                 f_example, create_flag);
372 }
373
374 /**
375  * Makes an NGon from an un-ordered set of verts
376  *
377  * assumes...
378  * - that verts are only once in the list.
379  * - that the verts have roughly planer bounds
380  * - that the verts are roughly circular
381  * there can be concave areas but overlapping folds from the center point will fail.
382  *
383  * a brief explanation of the method used
384  * - find the center point
385  * - find the normal of the vcloud
386  * - order the verts around the face based on their angle to the normal vector at the center point.
387  *
388  * \note Since this is a vcloud there is no direction.
389  */
390 void BM_verts_sort_radial_plane(BMVert **vert_arr, int len)
391 {
392         struct SortIntByFloat *vang = BLI_array_alloca(vang, len);
393         BMVert **vert_arr_map = BLI_array_alloca(vert_arr_map, len);
394
395         float totv_inv = 1.0f / (float)len;
396         int i = 0;
397
398         float cent[3], nor[3];
399
400         const float *far = NULL, *far_cross = NULL;
401
402         float far_vec[3];
403         float far_cross_vec[3];
404         float sign_vec[3]; /* work out if we are pos/neg angle */
405
406         float far_dist_sq, far_dist_max_sq;
407         float far_cross_dist, far_cross_best = 0.0f;
408
409         /* get the center point and collect vector array since we loop over these a lot */
410         zero_v3(cent);
411         for (i = 0; i < len; i++) {
412                 madd_v3_v3fl(cent, vert_arr[i]->co, totv_inv);
413         }
414
415
416         /* find the far point from cent */
417         far_dist_max_sq = 0.0f;
418         for (i = 0; i < len; i++) {
419                 far_dist_sq = len_squared_v3v3(vert_arr[i]->co, cent);
420                 if (far_dist_sq > far_dist_max_sq || far == NULL) {
421                         far = vert_arr[i]->co;
422                         far_dist_max_sq = far_dist_sq;
423                 }
424         }
425
426         sub_v3_v3v3(far_vec, far, cent);
427         // far_dist = len_v3(far_vec); /* real dist */ /* UNUSED */
428
429         /* --- */
430
431         /* find a point 90deg about to compare with */
432         far_cross_best = 0.0f;
433         for (i = 0; i < len; i++) {
434
435                 if (far == vert_arr[i]->co) {
436                         continue;
437                 }
438
439                 sub_v3_v3v3(far_cross_vec, vert_arr[i]->co, cent);
440                 far_cross_dist = normalize_v3(far_cross_vec);
441
442                 /* more of a weight then a distance */
443                 far_cross_dist = (/* first we want to have a value close to zero mapped to 1 */
444                                   1.0f - fabsf(dot_v3v3(far_vec, far_cross_vec)) *
445
446                                   /* second  we multiply by the distance
447                                    * so points close to the center are not preferred */
448                                   far_cross_dist);
449
450                 if (far_cross_dist > far_cross_best || far_cross == NULL) {
451                         far_cross = vert_arr[i]->co;
452                         far_cross_best = far_cross_dist;
453                 }
454         }
455
456         sub_v3_v3v3(far_cross_vec, far_cross, cent);
457
458         /* --- */
459
460         /* now we have 2 vectors we can have a cross product */
461         cross_v3_v3v3(nor, far_vec, far_cross_vec);
462         normalize_v3(nor);
463         cross_v3_v3v3(sign_vec, far_vec, nor); /* this vector should match 'far_cross_vec' closely */
464
465         /* --- */
466
467         /* now calculate every points angle around the normal (signed) */
468         for (i = 0; i < len; i++) {
469                 vang[i].sort_value = angle_signed_on_axis_v3v3v3_v3(far, cent, vert_arr[i]->co, nor);
470                 vang[i].data = i;
471                 vert_arr_map[i] = vert_arr[i];
472         }
473
474         /* sort by angle and magic! - we have our ngon */
475         qsort(vang, len, sizeof(*vang), BLI_sortutil_cmp_float);
476
477         /* --- */
478
479         for (i = 0; i < len; i++) {
480                 vert_arr[i] = vert_arr_map[vang[i].data];
481         }
482 }
483
484 /*************************************************************/
485
486
487 static void bm_vert_attrs_copy(
488         BMesh *source_mesh, BMesh *target_mesh,
489         const BMVert *source_vertex, BMVert *target_vertex, uint64_t cd_mask)
490 {
491         if ((source_mesh == target_mesh) && (source_vertex == target_vertex)) {
492                 BLI_assert(!"BMVert: source and targer match");
493                 return;
494         }
495         if ((cd_mask & CD_MASK_NORMAL) == 0) {
496                 copy_v3_v3(target_vertex->no, source_vertex->no);
497         }
498         CustomData_bmesh_free_block_data(&target_mesh->vdata, target_vertex->head.data);
499         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata,
500                                    source_vertex->head.data, &target_vertex->head.data);
501 }
502
503 static void bm_edge_attrs_copy(
504         BMesh *source_mesh, BMesh *target_mesh,
505         const BMEdge *source_edge, BMEdge *target_edge, uint64_t UNUSED(cd_mask))
506 {
507         if ((source_mesh == target_mesh) && (source_edge == target_edge)) {
508                 BLI_assert(!"BMEdge: source and targer match");
509                 return;
510         }
511         CustomData_bmesh_free_block_data(&target_mesh->edata, target_edge->head.data);
512         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata,
513                                    source_edge->head.data, &target_edge->head.data);
514 }
515
516 static void bm_loop_attrs_copy(
517         BMesh *source_mesh, BMesh *target_mesh,
518         const BMLoop *source_loop, BMLoop *target_loop, uint64_t UNUSED(cd_mask))
519 {
520         if ((source_mesh == target_mesh) && (source_loop == target_loop)) {
521                 BLI_assert(!"BMLoop: source and targer match");
522                 return;
523         }
524         CustomData_bmesh_free_block_data(&target_mesh->ldata, target_loop->head.data);
525         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata,
526                                    source_loop->head.data, &target_loop->head.data);
527 }
528
529 static void bm_face_attrs_copy(
530         BMesh *source_mesh, BMesh *target_mesh,
531         const BMFace *source_face, BMFace *target_face, uint64_t cd_mask)
532 {
533         if ((source_mesh == target_mesh) && (source_face == target_face)) {
534                 BLI_assert(!"BMFace: source and targer match");
535                 return;
536         }
537         if ((cd_mask & CD_MASK_NORMAL) == 0) {
538                 copy_v3_v3(target_face->no, source_face->no);
539         }
540         CustomData_bmesh_free_block_data(&target_mesh->pdata, target_face->head.data);
541         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata,
542                                    source_face->head.data, &target_face->head.data);
543         target_face->mat_nr = source_face->mat_nr;
544 }
545
546 /* BMESH_TODO: Special handling for hide flags? */
547 /* BMESH_TODO: swap src/dst args, everywhere else in bmesh does other way round */
548
549 /**
550  * Copies attributes, e.g. customdata, header flags, etc, from one element
551  * to another of the same type.
552  */
553 void BM_elem_attrs_copy_ex(
554         BMesh *bm_src, BMesh *bm_dst, const void *ele_src_v, void *ele_dst_v,
555         const char hflag_mask, const uint64_t cd_mask)
556 {
557         const BMHeader *ele_src = ele_src_v;
558         BMHeader *ele_dst = ele_dst_v;
559
560         BLI_assert(ele_src->htype == ele_dst->htype);
561         BLI_assert(ele_src != ele_dst);
562
563         /* Only support normal layer at the moment. */
564         BLI_assert((cd_mask & ~CD_MASK_NORMAL) == 0);
565
566         if ((hflag_mask & BM_ELEM_SELECT) == 0) {
567                 /* First we copy select */
568                 if (BM_elem_flag_test((BMElem *)ele_src, BM_ELEM_SELECT)) {
569                         BM_elem_select_set(bm_dst, (BMElem *)ele_dst, true);
570                 }
571         }
572
573         /* Now we copy flags */
574         if (hflag_mask == 0) {
575                 ele_dst->hflag = ele_src->hflag;
576         }
577         else if (hflag_mask == 0xff) {
578                 /* pass */
579         }
580         else {
581                 ele_dst->hflag = ((ele_dst->hflag & hflag_mask) | (ele_src->hflag & ~hflag_mask));
582         }
583
584         /* Copy specific attributes */
585         switch (ele_dst->htype) {
586                 case BM_VERT:
587                         bm_vert_attrs_copy(bm_src, bm_dst, (const BMVert *)ele_src, (BMVert *)ele_dst, cd_mask);
588                         break;
589                 case BM_EDGE:
590                         bm_edge_attrs_copy(bm_src, bm_dst, (const BMEdge *)ele_src, (BMEdge *)ele_dst, cd_mask);
591                         break;
592                 case BM_LOOP:
593                         bm_loop_attrs_copy(bm_src, bm_dst, (const BMLoop *)ele_src, (BMLoop *)ele_dst, cd_mask);
594                         break;
595                 case BM_FACE:
596                         bm_face_attrs_copy(bm_src, bm_dst, (const BMFace *)ele_src, (BMFace *)ele_dst, cd_mask);
597                         break;
598                 default:
599                         BLI_assert(0);
600                         break;
601         }
602 }
603
604 void BM_elem_attrs_copy(BMesh *bm_src, BMesh *bm_dst, const void *ele_src, void *ele_dst)
605 {
606         /* BMESH_TODO, default 'use_flags' to false */
607         BM_elem_attrs_copy_ex(bm_src, bm_dst, ele_src, ele_dst, BM_ELEM_SELECT, 0x0);
608 }
609
610 void BM_elem_select_copy(BMesh *bm_dst, void *ele_dst_v, const void *ele_src_v)
611 {
612         BMHeader *ele_dst = ele_dst_v;
613         const BMHeader *ele_src = ele_src_v;
614
615         BLI_assert(ele_src->htype == ele_dst->htype);
616
617         if ((ele_src->hflag & BM_ELEM_SELECT) != (ele_dst->hflag & BM_ELEM_SELECT)) {
618                 BM_elem_select_set(bm_dst, (BMElem *)ele_dst, (ele_src->hflag & BM_ELEM_SELECT) != 0);
619         }
620 }
621
622 /* helper function for 'BM_mesh_copy' */
623 static BMFace *bm_mesh_copy_new_face(
624         BMesh *bm_new, BMesh *bm_old,
625         BMVert **vtable, BMEdge **etable,
626         BMFace *f)
627 {
628         BMLoop **loops = BLI_array_alloca(loops, f->len);
629         BMVert **verts = BLI_array_alloca(verts, f->len);
630         BMEdge **edges = BLI_array_alloca(edges, f->len);
631
632         BMFace *f_new;
633         BMLoop *l_iter, *l_first;
634         int j;
635
636         j = 0;
637         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
638         do {
639                 loops[j] = l_iter;
640                 verts[j] = vtable[BM_elem_index_get(l_iter->v)];
641                 edges[j] = etable[BM_elem_index_get(l_iter->e)];
642                 j++;
643         } while ((l_iter = l_iter->next) != l_first);
644
645         f_new = BM_face_create(bm_new, verts, edges, f->len, NULL, BM_CREATE_SKIP_CD);
646
647         if (UNLIKELY(f_new == NULL)) {
648                 return NULL;
649         }
650
651         /* use totface in case adding some faces fails */
652         BM_elem_index_set(f_new, (bm_new->totface - 1)); /* set_inline */
653
654         BM_elem_attrs_copy_ex(bm_old, bm_new, f, f_new, 0xff, 0x0);
655         f_new->head.hflag = f->head.hflag;  /* low level! don't do this for normal api use */
656
657         j = 0;
658         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
659         do {
660                 BM_elem_attrs_copy(bm_old, bm_new, loops[j], l_iter);
661                 j++;
662         } while ((l_iter = l_iter->next) != l_first);
663
664         return f_new;
665 }
666
667 void BM_mesh_copy_init_customdata(BMesh *bm_dst, BMesh *bm_src, const BMAllocTemplate *allocsize)
668 {
669         if (allocsize == NULL) {
670                 allocsize = &bm_mesh_allocsize_default;
671         }
672
673         CustomData_copy(&bm_src->vdata, &bm_dst->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
674         CustomData_copy(&bm_src->edata, &bm_dst->edata, CD_MASK_BMESH, CD_CALLOC, 0);
675         CustomData_copy(&bm_src->ldata, &bm_dst->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
676         CustomData_copy(&bm_src->pdata, &bm_dst->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
677
678         CustomData_bmesh_init_pool(&bm_dst->vdata, allocsize->totvert, BM_VERT);
679         CustomData_bmesh_init_pool(&bm_dst->edata, allocsize->totedge, BM_EDGE);
680         CustomData_bmesh_init_pool(&bm_dst->ldata, allocsize->totloop, BM_LOOP);
681         CustomData_bmesh_init_pool(&bm_dst->pdata, allocsize->totface, BM_FACE);
682 }
683
684
685 BMesh *BM_mesh_copy(BMesh *bm_old)
686 {
687         BMesh *bm_new;
688         BMVert *v, *v_new, **vtable = NULL;
689         BMEdge *e, *e_new, **etable = NULL;
690         BMFace *f, *f_new, **ftable = NULL;
691         BMElem **eletable;
692         BMEditSelection *ese;
693         BMIter iter;
694         int i;
695         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_BM(bm_old);
696
697         /* allocate a bmesh */
698         bm_new = BM_mesh_create(
699                 &allocsize,
700                 &((struct BMeshCreateParams){.use_toolflags = bm_old->use_toolflags,}));
701
702         BM_mesh_copy_init_customdata(bm_new, bm_old, &allocsize);
703
704         vtable = MEM_mallocN(sizeof(BMVert *) * bm_old->totvert, "BM_mesh_copy vtable");
705         etable = MEM_mallocN(sizeof(BMEdge *) * bm_old->totedge, "BM_mesh_copy etable");
706         ftable = MEM_mallocN(sizeof(BMFace *) * bm_old->totface, "BM_mesh_copy ftable");
707
708         BM_ITER_MESH_INDEX (v, &iter, bm_old, BM_VERTS_OF_MESH, i) {
709                 /* copy between meshes so cant use 'example' argument */
710                 v_new = BM_vert_create(bm_new, v->co, NULL, BM_CREATE_SKIP_CD);
711                 BM_elem_attrs_copy_ex(bm_old, bm_new, v, v_new, 0xff, 0x0);
712                 v_new->head.hflag = v->head.hflag;  /* low level! don't do this for normal api use */
713                 vtable[i] = v_new;
714                 BM_elem_index_set(v, i); /* set_inline */
715                 BM_elem_index_set(v_new, i); /* set_inline */
716         }
717         bm_old->elem_index_dirty &= ~BM_VERT;
718         bm_new->elem_index_dirty &= ~BM_VERT;
719
720         /* safety check */
721         BLI_assert(i == bm_old->totvert);
722
723         BM_ITER_MESH_INDEX (e, &iter, bm_old, BM_EDGES_OF_MESH, i) {
724                 e_new = BM_edge_create(bm_new,
725                                        vtable[BM_elem_index_get(e->v1)],
726                                        vtable[BM_elem_index_get(e->v2)],
727                                        e, BM_CREATE_SKIP_CD);
728
729                 BM_elem_attrs_copy_ex(bm_old, bm_new, e, e_new, 0xff, 0x0);
730                 e_new->head.hflag = e->head.hflag;  /* low level! don't do this for normal api use */
731                 etable[i] = e_new;
732                 BM_elem_index_set(e, i); /* set_inline */
733                 BM_elem_index_set(e_new, i); /* set_inline */
734         }
735         bm_old->elem_index_dirty &= ~BM_EDGE;
736         bm_new->elem_index_dirty &= ~BM_EDGE;
737
738         /* safety check */
739         BLI_assert(i == bm_old->totedge);
740
741         BM_ITER_MESH_INDEX (f, &iter, bm_old, BM_FACES_OF_MESH, i) {
742                 BM_elem_index_set(f, i); /* set_inline */
743
744                 f_new = bm_mesh_copy_new_face(bm_new, bm_old, vtable, etable, f);
745
746                 ftable[i] = f_new;
747
748                 if (f == bm_old->act_face) bm_new->act_face = f_new;
749         }
750         bm_old->elem_index_dirty &= ~BM_FACE;
751         bm_new->elem_index_dirty &= ~BM_FACE;
752
753
754         /* low level! don't do this for normal api use */
755         bm_new->totvertsel = bm_old->totvertsel;
756         bm_new->totedgesel = bm_old->totedgesel;
757         bm_new->totfacesel = bm_old->totfacesel;
758
759         /* safety check */
760         BLI_assert(i == bm_old->totface);
761
762         /* copy over edit selection history */
763         for (ese = bm_old->selected.first; ese; ese = ese->next) {
764                 BMElem *ele = NULL;
765
766                 switch (ese->htype) {
767                         case BM_VERT:
768                                 eletable = (BMElem **)vtable;
769                                 break;
770                         case BM_EDGE:
771                                 eletable = (BMElem **)etable;
772                                 break;
773                         case BM_FACE:
774                                 eletable = (BMElem **)ftable;
775                                 break;
776                         default:
777                                 eletable = NULL;
778                                 break;
779                 }
780
781                 if (eletable) {
782                         ele = eletable[BM_elem_index_get(ese->ele)];
783                         if (ele) {
784                                 BM_select_history_store(bm_new, ele);
785                         }
786                 }
787         }
788
789         MEM_freeN(etable);
790         MEM_freeN(vtable);
791         MEM_freeN(ftable);
792
793         return bm_new;
794 }
795
796 /* ME -> BM */
797 char BM_vert_flag_from_mflag(const char  meflag)
798 {
799         return ( ((meflag & SELECT)       ? BM_ELEM_SELECT : 0) |
800                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
801                  );
802 }
803 char BM_edge_flag_from_mflag(const short meflag)
804 {
805         return ( ((meflag & SELECT)        ? BM_ELEM_SELECT : 0) |
806                  ((meflag & ME_SEAM)       ? BM_ELEM_SEAM   : 0) |
807                  ((meflag & ME_EDGEDRAW)   ? BM_ELEM_DRAW   : 0) |
808                  ((meflag & ME_SHARP) == 0 ? BM_ELEM_SMOOTH : 0) | /* invert */
809                  ((meflag & ME_HIDE)       ? BM_ELEM_HIDDEN : 0)
810                  );
811 }
812 char BM_face_flag_from_mflag(const char  meflag)
813 {
814         return ( ((meflag & ME_FACE_SEL)  ? BM_ELEM_SELECT : 0) |
815                  ((meflag & ME_SMOOTH)    ? BM_ELEM_SMOOTH : 0) |
816                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
817                  );
818 }
819
820 /* BM -> ME */
821 char  BM_vert_flag_to_mflag(BMVert *eve)
822 {
823         const char hflag = eve->head.hflag;
824
825         return ( ((hflag & BM_ELEM_SELECT)  ? SELECT  : 0) |
826                  ((hflag & BM_ELEM_HIDDEN)  ? ME_HIDE : 0)
827                  );
828 }
829
830 short BM_edge_flag_to_mflag(BMEdge *eed)
831 {
832         const char hflag = eed->head.hflag;
833
834         return ( ((hflag & BM_ELEM_SELECT)       ? SELECT       : 0) |
835                  ((hflag & BM_ELEM_SEAM)         ? ME_SEAM      : 0) |
836                  ((hflag & BM_ELEM_DRAW)         ? ME_EDGEDRAW  : 0) |
837                  ((hflag & BM_ELEM_SMOOTH) == 0  ? ME_SHARP     : 0) |
838                  ((hflag & BM_ELEM_HIDDEN)       ? ME_HIDE      : 0) |
839                  ((BM_edge_is_wire(eed))         ? ME_LOOSEEDGE : 0) | /* not typical */
840                  ME_EDGERENDER
841                  );
842 }
843 char  BM_face_flag_to_mflag(BMFace *efa)
844 {
845         const char hflag = efa->head.hflag;
846
847         return ( ((hflag & BM_ELEM_SELECT) ? ME_FACE_SEL : 0) |
848                  ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH   : 0) |
849                  ((hflag & BM_ELEM_HIDDEN) ? ME_HIDE     : 0)
850                  );
851 }