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