BMesh: maintain select-history when sorting
[blender.git] / source / blender / bmesh / intern / bmesh_mesh.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  * Contributor(s): Geoffrey Bantle.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_mesh.c
24  *  \ingroup bmesh
25  *
26  * BM mesh level functions.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "DNA_listBase.h"
32 #include "DNA_object_types.h"
33
34 #include "BLI_linklist_stack.h"
35 #include "BLI_listbase.h"
36 #include "BLI_math.h"
37 #include "BLI_stack.h"
38 #include "BLI_utildefines.h"
39
40 #include "BKE_cdderivedmesh.h"
41 #include "BKE_editmesh.h"
42 #include "BKE_mesh.h"
43 #include "BKE_multires.h"
44
45 #include "intern/bmesh_private.h"
46
47 /* used as an extern, defined in bmesh.h */
48 const BMAllocTemplate bm_mesh_allocsize_default = {512, 1024, 2048, 512};
49 const BMAllocTemplate bm_mesh_chunksize_default = {512, 1024, 2048, 512};
50
51 static void bm_mempool_init(BMesh *bm, const BMAllocTemplate *allocsize)
52 {
53         bm->vpool = BLI_mempool_create(sizeof(BMVert), allocsize->totvert,
54                                        bm_mesh_chunksize_default.totvert, BLI_MEMPOOL_ALLOW_ITER);
55         bm->epool = BLI_mempool_create(sizeof(BMEdge), allocsize->totedge,
56                                        bm_mesh_chunksize_default.totedge, BLI_MEMPOOL_ALLOW_ITER);
57         bm->lpool = BLI_mempool_create(sizeof(BMLoop), allocsize->totloop,
58                                        bm_mesh_chunksize_default.totloop, BLI_MEMPOOL_NOP);
59         bm->fpool = BLI_mempool_create(sizeof(BMFace), allocsize->totface,
60                                        bm_mesh_chunksize_default.totface, BLI_MEMPOOL_ALLOW_ITER);
61
62 #ifdef USE_BMESH_HOLES
63         bm->looplistpool = BLI_mempool_create(sizeof(BMLoopList), 512, 512, BLI_MEMPOOL_NOP);
64 #endif
65 }
66
67 void BM_mesh_elem_toolflags_ensure(BMesh *bm)
68 {
69         if (bm->vtoolflagpool && bm->etoolflagpool && bm->ftoolflagpool) {
70                 return;
71         }
72
73         bm->vtoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totvert, 512, BLI_MEMPOOL_NOP);
74         bm->etoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totedge, 512, BLI_MEMPOOL_NOP);
75         bm->ftoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totface, 512, BLI_MEMPOOL_NOP);
76
77 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
78         {
79 #pragma omp section
80                 {
81                         BLI_mempool *toolflagpool = bm->vtoolflagpool;
82                         BMIter iter;
83                         BMElemF *ele;
84                         BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
85                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
86                         }
87                 }
88 #pragma omp section
89                 {
90                         BLI_mempool *toolflagpool = bm->etoolflagpool;
91                         BMIter iter;
92                         BMElemF *ele;
93                         BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
94                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
95                         }
96                 }
97 #pragma omp section
98                 {
99                         BLI_mempool *toolflagpool = bm->ftoolflagpool;
100                         BMIter iter;
101                         BMElemF *ele;
102                         BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
103                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
104                         }
105                 }
106         }
107
108
109         bm->totflags = 1;
110 }
111
112 void BM_mesh_elem_toolflags_clear(BMesh *bm)
113 {
114         if (bm->vtoolflagpool) {
115                 BLI_mempool_destroy(bm->vtoolflagpool);
116                 bm->vtoolflagpool = NULL;
117         }
118         if (bm->etoolflagpool) {
119                 BLI_mempool_destroy(bm->etoolflagpool);
120                 bm->etoolflagpool = NULL;
121         }
122         if (bm->ftoolflagpool) {
123                 BLI_mempool_destroy(bm->ftoolflagpool);
124                 bm->ftoolflagpool = NULL;
125         }
126 }
127
128 /**
129  * \brief BMesh Make Mesh
130  *
131  * Allocates a new BMesh structure.
132  *
133  * \return The New bmesh
134  *
135  * \note ob is needed by multires
136  */
137 BMesh *BM_mesh_create(const BMAllocTemplate *allocsize)
138 {
139         /* allocate the structure */
140         BMesh *bm = MEM_callocN(sizeof(BMesh), __func__);
141         
142         /* allocate the memory pools for the mesh elements */
143         bm_mempool_init(bm, allocsize);
144
145         /* allocate one flag pool that we don't get rid of. */
146         bm->stackdepth = 1;
147         bm->totflags = 0;
148
149         CustomData_reset(&bm->vdata);
150         CustomData_reset(&bm->edata);
151         CustomData_reset(&bm->ldata);
152         CustomData_reset(&bm->pdata);
153
154         return bm;
155 }
156
157 /**
158  * \brief BMesh Free Mesh Data
159  *
160  *      Frees a BMesh structure.
161  *
162  * \note frees mesh, but not actual BMesh struct
163  */
164 void BM_mesh_data_free(BMesh *bm)
165 {
166         BMVert *v;
167         BMEdge *e;
168         BMLoop *l;
169         BMFace *f;
170
171         BMIter iter;
172         BMIter itersub;
173
174         const bool is_ldata_free = CustomData_bmesh_has_free(&bm->ldata);
175         const bool is_pdata_free = CustomData_bmesh_has_free(&bm->pdata);
176
177         /* Check if we have to call free, if not we can avoid a lot of looping */
178         if (CustomData_bmesh_has_free(&(bm->vdata))) {
179                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
180                         CustomData_bmesh_free_block(&(bm->vdata), &(v->head.data));
181                 }
182         }
183         if (CustomData_bmesh_has_free(&(bm->edata))) {
184                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
185                         CustomData_bmesh_free_block(&(bm->edata), &(e->head.data));
186                 }
187         }
188
189         if (is_ldata_free || is_pdata_free) {
190                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
191                         if (is_pdata_free)
192                                 CustomData_bmesh_free_block(&(bm->pdata), &(f->head.data));
193                         if (is_ldata_free) {
194                                 BM_ITER_ELEM (l, &itersub, f, BM_LOOPS_OF_FACE) {
195                                         CustomData_bmesh_free_block(&(bm->ldata), &(l->head.data));
196                                 }
197                         }
198                 }
199         }
200
201         /* Free custom data pools, This should probably go in CustomData_free? */
202         if (bm->vdata.totlayer) BLI_mempool_destroy(bm->vdata.pool);
203         if (bm->edata.totlayer) BLI_mempool_destroy(bm->edata.pool);
204         if (bm->ldata.totlayer) BLI_mempool_destroy(bm->ldata.pool);
205         if (bm->pdata.totlayer) BLI_mempool_destroy(bm->pdata.pool);
206
207         /* free custom data */
208         CustomData_free(&bm->vdata, 0);
209         CustomData_free(&bm->edata, 0);
210         CustomData_free(&bm->ldata, 0);
211         CustomData_free(&bm->pdata, 0);
212
213         /* destroy element pools */
214         BLI_mempool_destroy(bm->vpool);
215         BLI_mempool_destroy(bm->epool);
216         BLI_mempool_destroy(bm->lpool);
217         BLI_mempool_destroy(bm->fpool);
218
219         if (bm->vtable) MEM_freeN(bm->vtable);
220         if (bm->etable) MEM_freeN(bm->etable);
221         if (bm->ftable) MEM_freeN(bm->ftable);
222
223         /* destroy flag pool */
224         BM_mesh_elem_toolflags_clear(bm);
225
226 #ifdef USE_BMESH_HOLES
227         BLI_mempool_destroy(bm->looplistpool);
228 #endif
229
230         BLI_freelistN(&bm->selected);
231
232         BMO_error_clear(bm);
233 }
234
235 /**
236  * \brief BMesh Clear Mesh
237  *
238  * Clear all data in bm
239  */
240 void BM_mesh_clear(BMesh *bm)
241 {
242         /* free old mesh */
243         BM_mesh_data_free(bm);
244         memset(bm, 0, sizeof(BMesh));
245
246         /* allocate the memory pools for the mesh elements */
247         bm_mempool_init(bm, &bm_mesh_allocsize_default);
248
249         bm->stackdepth = 1;
250         bm->totflags = 0;
251
252         CustomData_reset(&bm->vdata);
253         CustomData_reset(&bm->edata);
254         CustomData_reset(&bm->ldata);
255         CustomData_reset(&bm->pdata);
256 }
257
258 /**
259  * \brief BMesh Free Mesh
260  *
261  *      Frees a BMesh data and its structure.
262  */
263 void BM_mesh_free(BMesh *bm)
264 {
265         BM_mesh_data_free(bm);
266
267         if (bm->py_handle) {
268                 /* keep this out of 'BM_mesh_data_free' because we want python
269                  * to be able to clear the mesh and maintain access. */
270                 bpy_bm_generic_invalidate(bm->py_handle);
271                 bm->py_handle = NULL;
272         }
273
274         MEM_freeN(bm);
275 }
276
277 /**
278  * Helpers for #BM_mesh_normals_update and #BM_verts_calc_normal_vcos
279  */
280 static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const float (*vcos)[3])
281 {
282         BMIter eiter;
283         BMEdge *e;
284         int index;
285
286         if (vcos) {
287                 BM_mesh_elem_index_ensure(bm, BM_VERT);
288         }
289
290         BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, index) {
291                 BM_elem_index_set(e, index); /* set_inline */
292
293                 if (e->l) {
294                         const float *v1_co = vcos ? vcos[BM_elem_index_get(e->v1)] : e->v1->co;
295                         const float *v2_co = vcos ? vcos[BM_elem_index_get(e->v2)] : e->v2->co;
296                         sub_v3_v3v3(edgevec[index], v2_co, v1_co);
297                         normalize_v3(edgevec[index]);
298                 }
299                 else {
300                         /* the edge vector will not be needed when the edge has no radial */
301                 }
302         }
303         bm->elem_index_dirty &= ~BM_EDGE;
304 }
305
306 static void bm_mesh_verts_calc_normals(
307         BMesh *bm, const float (*edgevec)[3], const float (*fnos)[3],
308         const float (*vcos)[3], float (*vnos)[3])
309 {
310         BM_mesh_elem_index_ensure(bm, (vnos) ? (BM_EDGE | BM_VERT) : BM_EDGE);
311
312         /* add weighted face normals to vertices */
313         {
314                 BMIter fiter;
315                 BMFace *f;
316                 int i;
317
318                 BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
319                         BMLoop *l_first, *l_iter;
320                         const float *f_no = fnos ? fnos[i] : f->no;
321
322                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
323                         do {
324                                 const float *e1diff, *e2diff;
325                                 float dotprod;
326                                 float fac;
327                                 float *v_no = vnos ? vnos[BM_elem_index_get(l_iter->v)] : l_iter->v->no;
328
329                                 /* calculate the dot product of the two edges that
330                                  * meet at the loop's vertex */
331                                 e1diff = edgevec[BM_elem_index_get(l_iter->prev->e)];
332                                 e2diff = edgevec[BM_elem_index_get(l_iter->e)];
333                                 dotprod = dot_v3v3(e1diff, e2diff);
334
335                                 /* edge vectors are calculated from e->v1 to e->v2, so
336                                  * adjust the dot product if one but not both loops
337                                  * actually runs from from e->v2 to e->v1 */
338                                 if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) {
339                                         dotprod = -dotprod;
340                                 }
341
342                                 fac = saacos(-dotprod);
343
344                                 /* accumulate weighted face normal into the vertex's normal */
345                                 madd_v3_v3fl(v_no, f_no, fac);
346                         } while ((l_iter = l_iter->next) != l_first);
347                 }
348         }
349
350
351         /* normalize the accumulated vertex normals */
352         {
353                 BMIter viter;
354                 BMVert *v;
355                 int i;
356
357                 BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
358                         float *v_no = vnos ? vnos[i] : v->no;
359                         if (UNLIKELY(normalize_v3(v_no) == 0.0f)) {
360                                 const float *v_co = vcos ? vcos[i] : v->co;
361                                 normalize_v3_v3(v_no, v_co);
362                         }
363                 }
364         }
365 }
366
367 /**
368  * \brief BMesh Compute Normals
369  *
370  * Updates the normals of a mesh.
371  */
372 void BM_mesh_normals_update(BMesh *bm)
373 {
374         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
375
376 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
377         {
378 #pragma omp section
379                 {
380                         /* calculate all face normals */
381                         BMIter fiter;
382                         BMFace *f;
383                         int i;
384
385                         BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
386                                 BM_elem_index_set(f, i); /* set_inline */
387                                 BM_face_normal_update(f);
388                         }
389                         bm->elem_index_dirty &= ~BM_FACE;
390                 }
391 #pragma omp section
392                 {
393                         /* Zero out vertex normals */
394                         BMIter viter;
395                         BMVert *v;
396                         int i;
397
398                         BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
399                                 BM_elem_index_set(v, i); /* set_inline */
400                                 zero_v3(v->no);
401                         }
402                         bm->elem_index_dirty &= ~BM_VERT;
403                 }
404 #pragma omp section
405                 {
406                         /* Compute normalized direction vectors for each edge.
407                          * Directions will be used for calculating the weights of the face normals on the vertex normals.
408                          */
409                         bm_mesh_edges_calc_vectors(bm, edgevec, NULL);
410                 }
411         }
412         /* end omp */
413
414         /* Add weighted face normals to vertices, and normalize vert normals. */
415         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, NULL, NULL, NULL);
416         MEM_freeN(edgevec);
417 }
418
419 /**
420  * \brief BMesh Compute Normals from/to external data.
421  *
422  * Computes the vertex normals of a mesh into vnos, using given vertex coordinates (vcos) and polygon normals (fnos).
423  */
424 void BM_verts_calc_normal_vcos(BMesh *bm, const float (*fnos)[3], const float (*vcos)[3], float (*vnos)[3])
425 {
426         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
427
428         /* Compute normalized direction vectors for each edge.
429          * Directions will be used for calculating the weights of the face normals on the vertex normals.
430          */
431         bm_mesh_edges_calc_vectors(bm, edgevec, vcos);
432
433         /* Add weighted face normals to vertices, and normalize vert normals. */
434         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, fnos, vcos, vnos);
435         MEM_freeN(edgevec);
436 }
437
438 /**
439  * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normals_vnos
440  */
441 static void bm_mesh_edges_sharp_tag(
442         BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float split_angle,
443         float (*r_lnos)[3])
444 {
445         BMIter eiter, viter;
446         BMVert *v;
447         BMEdge *e;
448         int i;
449
450         const bool check_angle = (split_angle < (float)M_PI);
451
452         if (check_angle) {
453                 split_angle = cosf(split_angle);
454         }
455
456         {
457                 char htype = BM_LOOP;
458                 if (fnos) {
459                         htype |= BM_FACE;
460                 }
461                 BM_mesh_elem_index_ensure(bm, htype);
462         }
463
464         /* Clear all vertices' tags (means they are all smooth for now). */
465         BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
466                 BM_elem_index_set(v, i); /* set_inline */
467                 BM_elem_flag_disable(v, BM_ELEM_TAG);
468         }
469
470         /* This first loop checks which edges are actually smooth, and pre-populate lnos with vnos (as if they were
471          * all smooth).
472          */
473         BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
474                 BMLoop *l_a, *l_b;
475
476                 BM_elem_index_set(e, i); /* set_inline */
477                 BM_elem_flag_disable(e, BM_ELEM_TAG); /* Clear tag (means edge is sharp). */
478
479                 /* An edge with only two loops, might be smooth... */
480                 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
481                         bool is_angle_smooth = true;
482                         if (check_angle) {
483                                 const float *no_a = fnos ? fnos[BM_elem_index_get(l_a->f)] : l_a->f->no;
484                                 const float *no_b = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_b->f->no;
485                                 is_angle_smooth = (dot_v3v3(no_a, no_b) >= split_angle);
486                         }
487
488                         /* We only tag edges that are *really* smooth:
489                          * If the angle between both its polys' normals is below split_angle value,
490                          * and it is tagged as such,
491                          * and both its faces are smooth,
492                          * and both its faces have compatible (non-flipped) normals,
493                          * i.e. both loops on the same edge do not share the same vertex.
494                          */
495                         if (is_angle_smooth &&
496                             BM_elem_flag_test(e, BM_ELEM_SMOOTH) &&
497                             BM_elem_flag_test(l_a->f, BM_ELEM_SMOOTH) &&
498                             BM_elem_flag_test(l_b->f, BM_ELEM_SMOOTH) &&
499                             l_a->v != l_b->v)
500                         {
501                                 const float *no;
502                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
503
504                                 /* linked vertices might be fully smooth, copy their normals to loop ones. */
505                                 no = vnos ? vnos[BM_elem_index_get(l_a->v)] : l_a->v->no;
506                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_a)], no);
507                                 no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no;
508                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no);
509                         }
510                         else {
511                                 /* Sharp edge, tag its verts as such. */
512                                 BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
513                                 BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
514                         }
515                 }
516                 else {
517                         /* Sharp edge, tag its verts as such. */
518                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
519                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
520                 }
521         }
522
523         bm->elem_index_dirty &= ~(BM_EDGE | BM_VERT);
524 }
525
526 /* BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c
527  * Will use first clnors_data array, and fallback to cd_loop_clnors_offset (use NULL and -1 to not use clnors). */
528 static void bm_mesh_loops_calc_normals(
529         BMesh *bm, const float (*vcos)[3], const float (*fnos)[3], float (*r_lnos)[3],
530         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2], const int cd_loop_clnors_offset)
531 {
532         BMIter fiter;
533         BMFace *f_curr;
534         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
535
536         MLoopNorSpaceArray _lnors_spacearr = {NULL};
537
538         /* Temp normal stack. */
539         BLI_SMALLSTACK_DECLARE(normal, float *);
540         /* Temp clnors stack. */
541         BLI_SMALLSTACK_DECLARE(clnors, short *);
542         /* Temp edge vectors stack, only used when computing lnor spacearr. */
543         BLI_Stack *edge_vectors = NULL;
544
545         {
546                 char htype = BM_LOOP;
547                 if (vcos) {
548                         htype |= BM_VERT;
549                 }
550                 if (fnos) {
551                         htype |= BM_FACE;
552                 }
553                 BM_mesh_elem_index_ensure(bm, htype);
554         }
555
556         if (!r_lnors_spacearr && has_clnors) {
557                 /* We need to compute lnor spacearr if some custom lnor data are given to us! */
558                 r_lnors_spacearr = &_lnors_spacearr;
559         }
560         if (r_lnors_spacearr) {
561                 BKE_lnor_spacearr_init(r_lnors_spacearr, bm->totloop);
562                 edge_vectors = BLI_stack_new(sizeof(float[3]), __func__);
563         }
564
565         /* We now know edges that can be smoothed (they are tagged), and edges that will be hard (they aren't).
566          * Now, time to generate the normals.
567          */
568         BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) {
569                 BMLoop *l_curr, *l_first;
570
571                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
572                 do {
573                         if (BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) &&
574                             (!r_lnors_spacearr || BM_elem_flag_test(l_curr->v, BM_ELEM_TAG)))
575                         {
576                                 /* A smooth edge, and we are not generating lnors_spacearr, or the related vertex is sharp.
577                                  * We skip it because it is either:
578                                  * - in the middle of a 'smooth fan' already computed (or that will be as soon as we hit
579                                  *   one of its ends, i.e. one of its two sharp edges), or...
580                                  * - the related vertex is a "full smooth" one, in which case pre-populated normals from vertex
581                                  *   are just fine!
582                                  */
583                         }
584                         else if (!BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) &&
585                                  !BM_elem_flag_test(l_curr->prev->e, BM_ELEM_TAG))
586                         {
587                                 /* Simple case (both edges around that vertex are sharp in related polygon),
588                                  * this vertex just takes its poly normal.
589                                  */
590                                 const int l_curr_index = BM_elem_index_get(l_curr);
591                                 const float *no = fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no;
592                                 copy_v3_v3(r_lnos[l_curr_index], no);
593
594                                 /* If needed, generate this (simple!) lnor space. */
595                                 if (r_lnors_spacearr) {
596                                         float vec_curr[3], vec_prev[3];
597                                         MLoopNorSpace *lnor_space = BKE_lnor_space_create(r_lnors_spacearr);
598
599                                         {
600                                                 const BMVert *v_pivot = l_curr->v;
601                                                 const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co;
602                                                 const BMVert *v_1 = BM_edge_other_vert(l_curr->e, v_pivot);
603                                                 const float *co_1 = vcos ? vcos[BM_elem_index_get(v_1)] : v_1->co;
604                                                 const BMVert *v_2 = BM_edge_other_vert(l_curr->prev->e, v_pivot);
605                                                 const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
606
607                                                 sub_v3_v3v3(vec_curr, co_1, co_pivot);
608                                                 normalize_v3(vec_curr);
609                                                 sub_v3_v3v3(vec_prev, co_2, co_pivot);
610                                                 normalize_v3(vec_prev);
611                                         }
612
613                                         BKE_lnor_space_define(lnor_space, r_lnos[l_curr_index], vec_curr, vec_prev, NULL);
614                                         /* We know there is only one loop in this space, no need to create a linklist in this case... */
615                                         BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, l_curr_index, false);
616
617                                         if (has_clnors) {
618                                                 short (*clnor)[2] = clnors_data ? &clnors_data[l_curr_index] :
619                                                                                   BM_ELEM_CD_GET_VOID_P(l_curr, cd_loop_clnors_offset);
620                                                 BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor, r_lnos[l_curr_index]);
621                                         }
622                                 }
623                         }
624                         /* We *do not need* to check/tag loops as already computed!
625                          * Due to the fact a loop only links to one of its two edges, a same fan *will never be walked more than
626                          * once!*
627                          * Since we consider edges having neighbor faces with inverted (flipped) normals as sharp, we are sure that
628                          * no fan will be skipped, even only considering the case (sharp curr_edge, smooth prev_edge), and not the
629                          * alternative (smooth curr_edge, sharp prev_edge).
630                          * All this due/thanks to link between normals and loop ordering.
631                          */
632                         else {
633                                 /* We have to fan around current vertex, until we find the other non-smooth edge,
634                                  * and accumulate face normals into the vertex!
635                                  * Note in case this vertex has only one sharp edge, this is a waste because the normal is the same as
636                                  * the vertex normal, but I do not see any easy way to detect that (would need to count number
637                                  * of sharp edges per vertex, I doubt the additional memory usage would be worth it, especially as
638                                  * it should not be a common case in real-life meshes anyway).
639                                  */
640                                 BMVert *v_pivot = l_curr->v;
641                                 BMEdge *e_next;
642                                 const BMEdge *e_org = l_curr->e;
643                                 BMLoop *lfan_pivot, *lfan_pivot_next;
644                                 int lfan_pivot_index;
645                                 float lnor[3] = {0.0f, 0.0f, 0.0f};
646                                 float vec_curr[3], vec_next[3], vec_org[3];
647
648                                 /* We validate clnors data on the fly - cheapest way to do! */
649                                 int clnors_avg[2] = {0, 0};
650                                 short (*clnor_ref)[2] = NULL;
651                                 int clnors_nbr = 0;
652                                 bool clnors_invalid = false;
653
654                                 const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co;
655
656                                 MLoopNorSpace *lnor_space = r_lnors_spacearr ? BKE_lnor_space_create(r_lnors_spacearr) : NULL;
657
658                                 BLI_assert((edge_vectors == NULL) || BLI_stack_is_empty(edge_vectors));
659
660                                 lfan_pivot = l_curr;
661                                 lfan_pivot_index = BM_elem_index_get(lfan_pivot);
662                                 e_next = lfan_pivot->e;  /* Current edge here, actually! */
663
664                                 /* Only need to compute previous edge's vector once, then we can just reuse old current one! */
665                                 {
666                                         const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
667                                         const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
668
669                                         sub_v3_v3v3(vec_org, co_2, co_pivot);
670                                         normalize_v3(vec_org);
671                                         copy_v3_v3(vec_curr, vec_org);
672
673                                         if (r_lnors_spacearr) {
674                                                 BLI_stack_push(edge_vectors, vec_org);
675                                         }
676                                 }
677
678                                 while (true) {
679                                         /* Much simpler than in sibling code with basic Mesh data! */
680                                         lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot, &e_next);
681                                         if (lfan_pivot_next) {
682                                                 BLI_assert(lfan_pivot_next->v == v_pivot);
683                                         }
684                                         else {
685                                                 /* next edge is non-manifold, we have to find it ourselves! */
686                                                 e_next = (lfan_pivot->e == e_next) ? lfan_pivot->prev->e : lfan_pivot->e;
687                                         }
688
689                                         /* Compute edge vector.
690                                          * NOTE: We could pre-compute those into an array, in the first iteration, instead of computing them
691                                          *       twice (or more) here. However, time gained is not worth memory and time lost,
692                                          *       given the fact that this code should not be called that much in real-life meshes...
693                                          */
694                                         {
695                                                 const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
696                                                 const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
697
698                                                 sub_v3_v3v3(vec_next, co_2, co_pivot);
699                                                 normalize_v3(vec_next);
700                                         }
701
702                                         {
703                                                 /* Code similar to accumulate_vertex_normals_poly. */
704                                                 /* Calculate angle between the two poly edges incident on this vertex. */
705                                                 const BMFace *f = lfan_pivot->f;
706                                                 const float fac = saacos(dot_v3v3(vec_next, vec_curr));
707                                                 const float *no = fnos ? fnos[BM_elem_index_get(f)] : f->no;
708                                                 /* Accumulate */
709                                                 madd_v3_v3fl(lnor, no, fac);
710
711                                                 if (has_clnors) {
712                                                         /* Accumulate all clnors, if they are not all equal we have to fix that! */
713                                                         short (*clnor)[2] = clnors_data ? &clnors_data[lfan_pivot_index] :
714                                                                                           BM_ELEM_CD_GET_VOID_P(lfan_pivot, cd_loop_clnors_offset);
715                                                         if (clnors_nbr) {
716                                                                 clnors_invalid |= ((*clnor_ref)[0] != (*clnor)[0] || (*clnor_ref)[1] != (*clnor)[1]);
717                                                         }
718                                                         else {
719                                                                 clnor_ref = clnor;
720                                                         }
721                                                         clnors_avg[0] += (*clnor)[0];
722                                                         clnors_avg[1] += (*clnor)[1];
723                                                         clnors_nbr++;
724                                                         /* We store here a pointer to all custom lnors processed. */
725                                                         BLI_SMALLSTACK_PUSH(clnors, (short *)*clnor);
726                                                 }
727                                         }
728
729                                         /* We store here a pointer to all loop-normals processed. */
730                                         BLI_SMALLSTACK_PUSH(normal, (float *)r_lnos[lfan_pivot_index]);
731
732                                         if (r_lnors_spacearr) {
733                                                 /* Assign current lnor space to current 'vertex' loop. */
734                                                 BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, lfan_pivot_index, true);
735                                                 if (e_next != e_org) {
736                                                         /* We store here all edges-normalized vectors processed. */
737                                                         BLI_stack_push(edge_vectors, vec_next);
738                                                 }
739                                         }
740
741                                         if (!BM_elem_flag_test(e_next, BM_ELEM_TAG) || (e_next == e_org)) {
742                                                 /* Next edge is sharp, we have finished with this fan of faces around this vert! */
743                                                 break;
744                                         }
745
746                                         /* Copy next edge vector to current one. */
747                                         copy_v3_v3(vec_curr, vec_next);
748                                         /* Next pivot loop to current one. */
749                                         lfan_pivot = lfan_pivot_next;
750                                         lfan_pivot_index = BM_elem_index_get(lfan_pivot);
751                                 }
752
753                                 {
754                                         float lnor_len = normalize_v3(lnor);
755
756                                         /* If we are generating lnor spacearr, we can now define the one for this fan. */
757                                         if (r_lnors_spacearr) {
758                                                 if (UNLIKELY(lnor_len == 0.0f)) {
759                                                         /* Use vertex normal as fallback! */
760                                                         copy_v3_v3(lnor, r_lnos[lfan_pivot_index]);
761                                                         lnor_len = 1.0f;
762                                                 }
763
764                                                 BKE_lnor_space_define(lnor_space, lnor, vec_org, vec_next, edge_vectors);
765
766                                                 if (has_clnors) {
767                                                         if (clnors_invalid) {
768                                                                 short *clnor;
769
770                                                                 clnors_avg[0] /= clnors_nbr;
771                                                                 clnors_avg[1] /= clnors_nbr;
772                                                                 /* Fix/update all clnors of this fan with computed average value. */
773                                                                 printf("Invalid clnors in this fan!\n");
774                                                                 while ((clnor = BLI_SMALLSTACK_POP(clnors))) {
775                                                                         //print_v2("org clnor", clnor);
776                                                                         clnor[0] = (short)clnors_avg[0];
777                                                                         clnor[1] = (short)clnors_avg[1];
778                                                                 }
779                                                                 //print_v2("new clnors", clnors_avg);
780                                                         }
781                                                         else {
782                                                                 /* We still have to consume the stack! */
783                                                                 while (BLI_SMALLSTACK_POP(clnors));
784                                                         }
785                                                         BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor_ref, lnor);
786                                                 }
787                                         }
788
789                                         /* In case we get a zero normal here, just use vertex normal already set! */
790                                         if (LIKELY(lnor_len != 0.0f)) {
791                                                 /* Copy back the final computed normal into all related loop-normals. */
792                                                 float *nor;
793
794                                                 while ((nor = BLI_SMALLSTACK_POP(normal))) {
795                                                         copy_v3_v3(nor, lnor);
796                                                 }
797                                         }
798                                         else {
799                                                 /* We still have to consume the stack! */
800                                                 while (BLI_SMALLSTACK_POP(normal));
801                                         }
802                                 }
803
804                                 /* Tag related vertex as sharp, to avoid fanning around it again (in case it was a smooth one). */
805                                 if (r_lnors_spacearr) {
806                                         BM_elem_flag_enable(l_curr->v, BM_ELEM_TAG);
807                                 }
808                         }
809                 } while ((l_curr = l_curr->next) != l_first);
810         }
811
812         if (r_lnors_spacearr) {
813                 BLI_stack_free(edge_vectors);
814                 if (r_lnors_spacearr == &_lnors_spacearr) {
815                         BKE_lnor_spacearr_free(r_lnors_spacearr);
816                 }
817         }
818 }
819
820 static void bm_mesh_loops_calc_normals_no_autosmooth(
821         BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float (*r_lnos)[3])
822 {
823         BMIter fiter;
824         BMFace *f_curr;
825
826         {
827                 char htype = BM_LOOP;
828                 if (vnos) {
829                         htype |= BM_VERT;
830                 }
831                 if (fnos) {
832                         htype |= BM_FACE;
833                 }
834                 BM_mesh_elem_index_ensure(bm, htype);
835         }
836
837         BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) {
838                 BMLoop *l_curr, *l_first;
839                 const bool is_face_flat = !BM_elem_flag_test(f_curr, BM_ELEM_SMOOTH);
840
841                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
842                 do {
843                         const float *no = is_face_flat ? (fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no) :
844                                                          (vnos ? vnos[BM_elem_index_get(l_curr->v)] : l_curr->v->no);
845                         copy_v3_v3(r_lnos[BM_elem_index_get(l_curr)], no);
846
847                 } while ((l_curr = l_curr->next) != l_first);
848         }
849 }
850
851 #if 0  /* Unused currently */
852 /**
853  * \brief BMesh Compute Loop Normals
854  *
855  * Updates the loop normals of a mesh. Assumes vertex and face normals are valid (else call BM_mesh_normals_update()
856  * first)!
857  */
858 void BM_mesh_loop_normals_update(
859         BMesh *bm, const bool use_split_normals, const float split_angle, float (*r_lnos)[3],
860         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2], const int cd_loop_clnors_offset)
861 {
862         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
863
864         if (use_split_normals) {
865                 /* Tag smooth edges and set lnos from vnos when they might be completely smooth...
866                  * When using custom loop normals, disable the angle feature! */
867                 bm_mesh_edges_sharp_tag(bm, NULL, NULL, has_clnors ? (float)M_PI : split_angle, r_lnos);
868
869                 /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
870                 bm_mesh_loops_calc_normals(bm, NULL, NULL, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset);
871         }
872         else {
873                 BLI_assert(!r_lnors_spacearr);
874                 bm_mesh_loops_calc_normals_no_autosmooth(bm, NULL, NULL, r_lnos);
875         }
876 }
877 #endif
878
879 /**
880  * \brief BMesh Compute Loop Normals from/to external data.
881  *
882  * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals').
883  * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry (splitting edges).
884  */
885 void BM_loops_calc_normal_vcos(
886         BMesh *bm, const float (*vcos)[3], const float (*vnos)[3], const float (*fnos)[3],
887         const bool use_split_normals, const float split_angle, float (*r_lnos)[3],
888         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2], const int cd_loop_clnors_offset)
889 {
890         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
891
892         if (use_split_normals) {
893                 /* Tag smooth edges and set lnos from vnos when they might be completely smooth...
894                  * When using custom loop normals, disable the angle feature! */
895                 bm_mesh_edges_sharp_tag(bm, vnos, fnos, has_clnors ? (float)M_PI : split_angle, r_lnos);
896
897                 /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
898                 bm_mesh_loops_calc_normals(bm, vcos, fnos, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset);
899         }
900         else {
901                 BLI_assert(!r_lnors_spacearr);
902                 bm_mesh_loops_calc_normals_no_autosmooth(bm, vnos, fnos, r_lnos);
903         }
904 }
905
906 static void UNUSED_FUNCTION(bm_mdisps_space_set)(Object *ob, BMesh *bm, int from, int to)
907 {
908         /* switch multires data out of tangent space */
909         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
910                 BMEditMesh *em = BKE_editmesh_create(bm, false);
911                 DerivedMesh *dm = CDDM_from_editbmesh(em, true, false);
912                 MDisps *mdisps;
913                 BMFace *f;
914                 BMIter iter;
915                 // int i = 0; // UNUSED
916                 
917                 multires_set_space(dm, ob, from, to);
918                 
919                 mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
920                 
921                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
922                         BMLoop *l;
923                         BMIter liter;
924                         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
925                                 MDisps *lmd = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MDISPS);
926                                 
927                                 if (!lmd->disps) {
928                                         printf("%s: warning - 'lmd->disps' == NULL\n", __func__);
929                                 }
930                                 
931                                 if (lmd->disps && lmd->totdisp == mdisps->totdisp) {
932                                         memcpy(lmd->disps, mdisps->disps, sizeof(float) * 3 * lmd->totdisp);
933                                 }
934                                 else if (mdisps->disps) {
935                                         if (lmd->disps)
936                                                 MEM_freeN(lmd->disps);
937                                         
938                                         lmd->disps = MEM_dupallocN(mdisps->disps);
939                                         lmd->totdisp = mdisps->totdisp;
940                                         lmd->level = mdisps->level;
941                                 }
942                                 
943                                 mdisps++;
944                                 // i += 1;
945                         }
946                 }
947                 
948                 dm->needsFree = 1;
949                 dm->release(dm);
950                 
951                 /* setting this to NULL prevents BKE_editmesh_free from freeing it */
952                 em->bm = NULL;
953                 BKE_editmesh_free(em);
954                 MEM_freeN(em);
955         }
956 }
957
958 /**
959  * \brief BMesh Begin Edit
960  *
961  * Functions for setting up a mesh for editing and cleaning up after
962  * the editing operations are done. These are called by the tools/operator
963  * API for each time a tool is executed.
964  */
965 void bmesh_edit_begin(BMesh *UNUSED(bm), BMOpTypeFlag UNUSED(type_flag))
966 {
967         /* Most operators seem to be using BMO_OPTYPE_FLAG_UNTAN_MULTIRES to change the MDisps to
968          * absolute space during mesh edits. With this enabled, changes to the topology
969          * (loop cuts, edge subdivides, etc) are not reflected in the higher levels of
970          * the mesh at all, which doesn't seem right. Turning off completely for now,
971          * until this is shown to be better for certain types of mesh edits. */
972 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
973         /* switch multires data out of tangent space */
974         if ((type_flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
975                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_TANGENT, MULTIRES_SPACE_ABSOLUTE);
976
977                 /* ensure correct normals, if possible */
978                 bmesh_rationalize_normals(bm, 0);
979                 BM_mesh_normals_update(bm);
980         }
981 #endif
982 }
983
984 /**
985  * \brief BMesh End Edit
986  */
987 void bmesh_edit_end(BMesh *bm, BMOpTypeFlag type_flag)
988 {
989         ListBase select_history;
990
991         /* BMO_OPTYPE_FLAG_UNTAN_MULTIRES disabled for now, see comment above in bmesh_edit_begin. */
992 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
993         /* switch multires data into tangent space */
994         if ((flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
995                 /* set normals to their previous winding */
996                 bmesh_rationalize_normals(bm, 1);
997                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
998         }
999         else if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
1000                 bmesh_rationalize_normals(bm, 1);
1001         }
1002 #endif
1003
1004         /* compute normals, clear temp flags and flush selections */
1005         if (type_flag & BMO_OPTYPE_FLAG_NORMALS_CALC) {
1006                 BM_mesh_normals_update(bm);
1007         }
1008
1009
1010         if ((type_flag & BMO_OPTYPE_FLAG_SELECT_VALIDATE) == 0) {
1011                 select_history = bm->selected;
1012                 BLI_listbase_clear(&bm->selected);
1013         }
1014
1015         if (type_flag & BMO_OPTYPE_FLAG_SELECT_FLUSH) {
1016                 BM_mesh_select_mode_flush(bm);
1017         }
1018
1019         if ((type_flag & BMO_OPTYPE_FLAG_SELECT_VALIDATE) == 0) {
1020                 bm->selected = select_history;
1021         }
1022 }
1023
1024 void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
1025 {
1026         const char htype_needed = bm->elem_index_dirty & htype;
1027
1028 #ifdef DEBUG
1029         BM_ELEM_INDEX_VALIDATE(bm, "Should Never Fail!", __func__);
1030 #endif
1031
1032         if (htype_needed == 0) {
1033                 goto finally;
1034         }
1035
1036         /* skip if we only need to operate on one element */
1037 #pragma omp parallel sections if ((!ELEM(htype_needed, BM_VERT, BM_EDGE, BM_FACE, BM_LOOP, BM_FACE | BM_LOOP)) && \
1038                                       (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT))
1039         {
1040 #pragma omp section
1041
1042                 {
1043                         if (htype & BM_VERT) {
1044                                 if (bm->elem_index_dirty & BM_VERT) {
1045                                         BMIter iter;
1046                                         BMElem *ele;
1047
1048                                         int index;
1049                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, index) {
1050                                                 BM_elem_index_set(ele, index); /* set_ok */
1051                                         }
1052                                         BLI_assert(index == bm->totvert);
1053                                 }
1054                                 else {
1055                                         // printf("%s: skipping vert index calc!\n", __func__);
1056                                 }
1057                         }
1058                 }
1059
1060 #pragma omp section
1061                 {
1062                         if (htype & BM_EDGE) {
1063                                 if (bm->elem_index_dirty & BM_EDGE) {
1064                                         BMIter iter;
1065                                         BMElem *ele;
1066
1067                                         int index;
1068                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, index) {
1069                                                 BM_elem_index_set(ele, index); /* set_ok */
1070                                         }
1071                                         BLI_assert(index == bm->totedge);
1072                                 }
1073                                 else {
1074                                         // printf("%s: skipping edge index calc!\n", __func__);
1075                                 }
1076                         }
1077                 }
1078
1079 #pragma omp section
1080                 {
1081                         if (htype & (BM_FACE | BM_LOOP)) {
1082                                 if (bm->elem_index_dirty & (BM_FACE | BM_LOOP)) {
1083                                         BMIter iter;
1084                                         BMElem *ele;
1085
1086                                         const bool update_face = (htype & BM_FACE) && (bm->elem_index_dirty & BM_FACE);
1087                                         const bool update_loop = (htype & BM_LOOP) && (bm->elem_index_dirty & BM_LOOP);
1088
1089                                         int index;
1090                                         int index_loop = 0;
1091
1092                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, index) {
1093                                                 if (update_face) {
1094                                                         BM_elem_index_set(ele, index); /* set_ok */
1095                                                 }
1096
1097                                                 if (update_loop) {
1098                                                         BMLoop *l_iter, *l_first;
1099
1100                                                         l_iter = l_first = BM_FACE_FIRST_LOOP((BMFace *)ele);
1101                                                         do {
1102                                                                 BM_elem_index_set(l_iter, index_loop++); /* set_ok */
1103                                                         } while ((l_iter = l_iter->next) != l_first);
1104                                                 }
1105                                         }
1106
1107                                         BLI_assert(index == bm->totface);
1108                                         if (update_loop) {
1109                                                 BLI_assert(index_loop == bm->totloop);
1110                                         }
1111                                 }
1112                                 else {
1113                                         // printf("%s: skipping face/loop index calc!\n", __func__);
1114                                 }
1115                         }
1116                 }
1117         }
1118
1119
1120 finally:
1121         bm->elem_index_dirty &= ~htype;
1122 }
1123
1124
1125 /**
1126  * Array checking/setting macros
1127  *
1128  * Currently vert/edge/loop/face index data is being abused, in a few areas of the code.
1129  *
1130  * To avoid correcting them afterwards, set 'bm->elem_index_dirty' however its possible
1131  * this flag is set incorrectly which could crash blender.
1132  *
1133  * These functions ensure its correct and are called more often in debug mode.
1134  */
1135
1136 void BM_mesh_elem_index_validate(
1137         BMesh *bm, const char *location, const char *func,
1138         const char *msg_a, const char *msg_b)
1139 {
1140         const char iter_types[3] = {BM_VERTS_OF_MESH,
1141                                     BM_EDGES_OF_MESH,
1142                                     BM_FACES_OF_MESH};
1143
1144         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
1145         const char *type_names[3] = {"vert", "edge", "face"};
1146
1147         BMIter iter;
1148         BMElem *ele;
1149         int i;
1150         bool is_any_error = 0;
1151
1152         for (i = 0; i < 3; i++) {
1153                 const bool is_dirty = (flag_types[i] & bm->elem_index_dirty) != 0;
1154                 int index = 0;
1155                 bool is_error = false;
1156                 int err_val = 0;
1157                 int err_idx = 0;
1158
1159                 BM_ITER_MESH (ele, &iter, bm, iter_types[i]) {
1160                         if (!is_dirty) {
1161                                 if (BM_elem_index_get(ele) != index) {
1162                                         err_val = BM_elem_index_get(ele);
1163                                         err_idx = index;
1164                                         is_error = true;
1165                                 }
1166                         }
1167
1168                         BM_elem_index_set(ele, index); /* set_ok */
1169                         index++;
1170                 }
1171
1172                 if ((is_error == true) && (is_dirty == false)) {
1173                         is_any_error = true;
1174                         fprintf(stderr,
1175                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
1176                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
1177                 }
1178                 else if ((is_error == false) && (is_dirty == true)) {
1179
1180 #if 0       /* mostly annoying */
1181
1182                         /* dirty may have been incorrectly set */
1183                         fprintf(stderr,
1184                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
1185                                 location, func, type_names[i], msg_a, msg_b);
1186 #endif
1187                 }
1188         }
1189
1190 #if 0 /* mostly annoying, even in debug mode */
1191 #ifdef DEBUG
1192         if (is_any_error == 0) {
1193                 fprintf(stderr,
1194                         "Valid Index Success: at %s, %s, '%s', '%s'\n",
1195                         location, func, msg_a, msg_b);
1196         }
1197 #endif
1198 #endif
1199         (void) is_any_error; /* shut up the compiler */
1200
1201 }
1202
1203 /* debug check only - no need to optimize */
1204 #ifndef NDEBUG
1205 bool BM_mesh_elem_table_check(BMesh *bm)
1206 {
1207         BMIter iter;
1208         BMElem *ele;
1209         int i;
1210
1211         if (bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) {
1212                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, i) {
1213                         if (ele != (BMElem *)bm->vtable[i]) {
1214                                 return false;
1215                         }
1216                 }
1217         }
1218
1219         if (bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) {
1220                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, i) {
1221                         if (ele != (BMElem *)bm->etable[i]) {
1222                                 return false;
1223                         }
1224                 }
1225         }
1226
1227         if (bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) {
1228                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, i) {
1229                         if (ele != (BMElem *)bm->ftable[i]) {
1230                                 return false;
1231                         }
1232                 }
1233         }
1234
1235         return true;
1236 }
1237 #endif
1238
1239
1240
1241 void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
1242 {
1243         /* assume if the array is non-null then its valid and no need to recalc */
1244         const char htype_needed = (((bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) ? 0 : BM_VERT) |
1245                                    ((bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) ? 0 : BM_EDGE) |
1246                                    ((bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) ? 0 : BM_FACE)) & htype;
1247
1248         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1249
1250         /* in debug mode double check we didn't need to recalculate */
1251         BLI_assert(BM_mesh_elem_table_check(bm) == true);
1252
1253         if (htype_needed == 0) {
1254                 goto finally;
1255         }
1256
1257         if (htype_needed & BM_VERT) {
1258                 if (bm->vtable && bm->totvert <= bm->vtable_tot && bm->totvert * 2 >= bm->vtable_tot) {
1259                         /* pass (re-use the array) */
1260                 }
1261                 else {
1262                         if (bm->vtable)
1263                                 MEM_freeN(bm->vtable);
1264                         bm->vtable = MEM_mallocN(sizeof(void **) * bm->totvert, "bm->vtable");
1265                         bm->vtable_tot = bm->totvert;
1266                 }
1267         }
1268         if (htype_needed & BM_EDGE) {
1269                 if (bm->etable && bm->totedge <= bm->etable_tot && bm->totedge * 2 >= bm->etable_tot) {
1270                         /* pass (re-use the array) */
1271                 }
1272                 else {
1273                         if (bm->etable)
1274                                 MEM_freeN(bm->etable);
1275                         bm->etable = MEM_mallocN(sizeof(void **) * bm->totedge, "bm->etable");
1276                         bm->etable_tot = bm->totedge;
1277                 }
1278         }
1279         if (htype_needed & BM_FACE) {
1280                 if (bm->ftable && bm->totface <= bm->ftable_tot && bm->totface * 2 >= bm->ftable_tot) {
1281                         /* pass (re-use the array) */
1282                 }
1283                 else {
1284                         if (bm->ftable)
1285                                 MEM_freeN(bm->ftable);
1286                         bm->ftable = MEM_mallocN(sizeof(void **) * bm->totface, "bm->ftable");
1287                         bm->ftable_tot = bm->totface;
1288                 }
1289         }
1290
1291         /* skip if we only need to operate on one element */
1292 #pragma omp parallel sections if ((!ELEM(htype_needed, BM_VERT, BM_EDGE, BM_FACE)) && \
1293                                       (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT))
1294         {
1295 #pragma omp section
1296                 {
1297                         if (htype_needed & BM_VERT) {
1298                                 BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)bm->vtable, bm->totvert);
1299                         }
1300                 }
1301 #pragma omp section
1302                 {
1303                         if (htype_needed & BM_EDGE) {
1304                                 BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)bm->etable, bm->totedge);
1305                         }
1306                 }
1307 #pragma omp section
1308                 {
1309                         if (htype_needed & BM_FACE) {
1310                                 BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)bm->ftable, bm->totface);
1311                         }
1312                 }
1313         }
1314
1315 finally:
1316         /* Only clear dirty flags when all the pointers and data are actually valid.
1317          * This prevents possible threading issues when dirty flag check failed but
1318          * data wasn't ready still.
1319          */
1320         bm->elem_table_dirty &= ~htype_needed;
1321 }
1322
1323 /* use BM_mesh_elem_table_ensure where possible to avoid full rebuild */
1324 void BM_mesh_elem_table_init(BMesh *bm, const char htype)
1325 {
1326         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1327
1328         /* force recalc */
1329         BM_mesh_elem_table_free(bm, BM_ALL_NOLOOP);
1330         BM_mesh_elem_table_ensure(bm, htype);
1331 }
1332
1333 void BM_mesh_elem_table_free(BMesh *bm, const char htype)
1334 {
1335         if (htype & BM_VERT) {
1336                 MEM_SAFE_FREE(bm->vtable);
1337         }
1338
1339         if (htype & BM_EDGE) {
1340                 MEM_SAFE_FREE(bm->etable);
1341         }
1342
1343         if (htype & BM_FACE) {
1344                 MEM_SAFE_FREE(bm->ftable);
1345         }
1346 }
1347
1348 BMVert *BM_vert_at_index(BMesh *bm, const int index)
1349 {
1350         BLI_assert((index >= 0) && (index < bm->totvert));
1351         BLI_assert((bm->elem_table_dirty & BM_VERT) == 0);
1352         return bm->vtable[index];
1353 }
1354
1355 BMEdge *BM_edge_at_index(BMesh *bm, const int index)
1356 {
1357         BLI_assert((index >= 0) && (index < bm->totedge));
1358         BLI_assert((bm->elem_table_dirty & BM_EDGE) == 0);
1359         return bm->etable[index];
1360 }
1361
1362 BMFace *BM_face_at_index(BMesh *bm, const int index)
1363 {
1364         BLI_assert((index >= 0) && (index < bm->totface));
1365         BLI_assert((bm->elem_table_dirty & BM_FACE) == 0);
1366         return bm->ftable[index];
1367 }
1368
1369
1370 BMVert *BM_vert_at_index_find(BMesh *bm, const int index)
1371 {
1372         return BLI_mempool_findelem(bm->vpool, index);
1373 }
1374
1375 BMEdge *BM_edge_at_index_find(BMesh *bm, const int index)
1376 {
1377         return BLI_mempool_findelem(bm->epool, index);
1378 }
1379
1380 BMFace *BM_face_at_index_find(BMesh *bm, const int index)
1381 {
1382         return BLI_mempool_findelem(bm->fpool, index);
1383 }
1384
1385 /**
1386  * Use lookup table when available, else use slower find functions.
1387  *
1388  * \note Try to use #BM_mesh_elem_table_ensure instead.
1389  */
1390 BMVert *BM_vert_at_index_find_or_table(BMesh *bm, const int index)
1391 {
1392         if ((bm->elem_table_dirty & BM_VERT) == 0) {
1393                 return (index < bm->totvert) ? bm->vtable[index] : NULL;
1394         }
1395         else {
1396                 return BM_vert_at_index_find(bm, index);
1397         }
1398 }
1399
1400 BMEdge *BM_edge_at_index_find_or_table(BMesh *bm, const int index)
1401 {
1402         if ((bm->elem_table_dirty & BM_EDGE) == 0) {
1403                 return (index < bm->totedge) ? bm->etable[index] : NULL;
1404         }
1405         else {
1406                 return BM_edge_at_index_find(bm, index);
1407         }
1408 }
1409
1410 BMFace *BM_face_at_index_find_or_table(BMesh *bm, const int index)
1411 {
1412         if ((bm->elem_table_dirty & BM_FACE) == 0) {
1413                 return (index < bm->totface) ? bm->ftable[index] : NULL;
1414         }
1415         else {
1416                 return BM_face_at_index_find(bm, index);
1417         }
1418 }
1419
1420
1421 /**
1422  * Return the amount of element of type 'type' in a given bmesh.
1423  */
1424 int BM_mesh_elem_count(BMesh *bm, const char htype)
1425 {
1426         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1427
1428         switch (htype) {
1429                 case BM_VERT: return bm->totvert;
1430                 case BM_EDGE: return bm->totedge;
1431                 case BM_FACE: return bm->totface;
1432                 default:
1433                 {
1434                         BLI_assert(0);
1435                         return 0;
1436                 }
1437         }
1438 }
1439
1440 /**
1441  * Special case: Python uses custom-data layers to hold PyObject references.
1442  * These have to be kept in-place, else the PyObject's we point to, wont point back to us.
1443  *
1444  * \note ``ele_src`` Is a duplicate, so we don't need to worry about getting in a feedback loop.
1445  *
1446  * \note If there are other customdata layers which need this functionality, it should be generalized.
1447  * However #BM_mesh_remap is currently the only place where this is done.
1448  */
1449 static void bm_mesh_remap_cd_update(
1450         BMHeader *ele_dst, BMHeader *ele_src,
1451         const int cd_elem_pyptr)
1452 {
1453         void **pyptr_dst_p = BM_ELEM_CD_GET_VOID_P(((BMElem *)ele_dst), cd_elem_pyptr);
1454         void **pyptr_src_p = BM_ELEM_CD_GET_VOID_P(((BMElem *)ele_src), cd_elem_pyptr);
1455         *pyptr_dst_p = *pyptr_src_p;
1456 }
1457
1458 /**
1459  * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays
1460  * (xxx_idx[org_index] = new_index).
1461  *
1462  * A NULL array means no changes.
1463  *
1464  * Note: - Does not mess with indices, just sets elem_index_dirty flag.
1465  *       - For verts/edges/faces only (as loops must remain "ordered" and "aligned"
1466  *         on a per-face basis...).
1467  *
1468  * WARNING: Be careful if you keep pointers to affected BM elements, or arrays, when using this func!
1469  */
1470 void BM_mesh_remap(
1471         BMesh *bm,
1472         const unsigned int *vert_idx,
1473         const unsigned int *edge_idx,
1474         const unsigned int *face_idx)
1475 {
1476         /* Mapping old to new pointers. */
1477         GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL;
1478         BMIter iter, iterl;
1479         BMVert *ve;
1480         BMEdge *ed;
1481         BMFace *fa;
1482         BMLoop *lo;
1483
1484         if (!(vert_idx || edge_idx || face_idx))
1485                 return;
1486
1487         BM_mesh_elem_table_ensure(
1488                 bm,
1489                 (vert_idx ? BM_VERT : 0) |
1490                 (edge_idx ? BM_EDGE : 0) |
1491                 (face_idx ? BM_FACE : 0));
1492
1493         /* Remap Verts */
1494         if (vert_idx) {
1495                 BMVert **verts_pool, *verts_copy, **vep;
1496                 int i, totvert = bm->totvert;
1497                 const unsigned int *new_idx;
1498                 const int cd_vert_pyptr  = CustomData_get_offset(&bm->vdata, CD_BM_ELEM_PYPTR);
1499
1500                 /* Init the old-to-new vert pointers mapping */
1501                 vptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap vert pointers mapping", bm->totvert);
1502
1503                 /* Make a copy of all vertices. */
1504                 verts_pool = bm->vtable;
1505                 verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy");
1506                 for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) {
1507                         *ve = **vep;
1508 /*                      printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/
1509                 }
1510
1511                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1512                 new_idx = vert_idx + totvert - 1;
1513                 ve = verts_copy + totvert - 1;
1514                 vep = verts_pool + totvert - 1; /* old, org pointer */
1515                 for (i = totvert; i--; new_idx--, ve--, vep--) {
1516                         BMVert *new_vep = verts_pool[*new_idx];
1517                         *new_vep = *ve;
1518 /*                      printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/
1519                         BLI_ghash_insert(vptr_map, *vep, new_vep);
1520                         if (cd_vert_pyptr != -1) {
1521                                 bm_mesh_remap_cd_update(&(*vep)->head, &new_vep->head, cd_vert_pyptr);
1522                         }
1523                 }
1524                 bm->elem_index_dirty |= BM_VERT;
1525                 bm->elem_table_dirty |= BM_VERT;
1526
1527                 MEM_freeN(verts_copy);
1528         }
1529
1530         /* Remap Edges */
1531         if (edge_idx) {
1532                 BMEdge **edges_pool, *edges_copy, **edp;
1533                 int i, totedge = bm->totedge;
1534                 const unsigned int *new_idx;
1535                 const int cd_edge_pyptr  = CustomData_get_offset(&bm->edata, CD_BM_ELEM_PYPTR);
1536
1537                 /* Init the old-to-new vert pointers mapping */
1538                 eptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap edge pointers mapping", bm->totedge);
1539
1540                 /* Make a copy of all vertices. */
1541                 edges_pool = bm->etable;
1542                 edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy");
1543                 for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) {
1544                         *ed = **edp;
1545                 }
1546
1547                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1548                 new_idx = edge_idx + totedge - 1;
1549                 ed = edges_copy + totedge - 1;
1550                 edp = edges_pool + totedge - 1; /* old, org pointer */
1551                 for (i = totedge; i--; new_idx--, ed--, edp--) {
1552                         BMEdge *new_edp = edges_pool[*new_idx];
1553                         *new_edp = *ed;
1554                         BLI_ghash_insert(eptr_map, *edp, new_edp);
1555 /*                      printf("mapping edge from %d to %d (%p/%p to %p)\n", i, *new_idx, *edp, edges_pool[i], new_edp);*/
1556                         if (cd_edge_pyptr != -1) {
1557                                 bm_mesh_remap_cd_update(&(*edp)->head, &new_edp->head, cd_edge_pyptr);
1558                         }
1559                 }
1560                 bm->elem_index_dirty |= BM_EDGE;
1561                 bm->elem_table_dirty |= BM_EDGE;
1562
1563                 MEM_freeN(edges_copy);
1564         }
1565
1566         /* Remap Faces */
1567         if (face_idx) {
1568                 BMFace **faces_pool, *faces_copy, **fap;
1569                 int i, totface = bm->totface;
1570                 const unsigned int *new_idx;
1571                 const int cd_poly_pyptr  = CustomData_get_offset(&bm->pdata, CD_BM_ELEM_PYPTR);
1572
1573                 /* Init the old-to-new vert pointers mapping */
1574                 fptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap face pointers mapping", bm->totface);
1575
1576                 /* Make a copy of all vertices. */
1577                 faces_pool = bm->ftable;
1578                 faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy");
1579                 for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) {
1580                         *fa = **fap;
1581                 }
1582
1583                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1584                 new_idx = face_idx + totface - 1;
1585                 fa = faces_copy + totface - 1;
1586                 fap = faces_pool + totface - 1; /* old, org pointer */
1587                 for (i = totface; i--; new_idx--, fa--, fap--) {
1588                         BMFace *new_fap = faces_pool[*new_idx];
1589                         *new_fap = *fa;
1590                         BLI_ghash_insert(fptr_map, *fap, new_fap);
1591                         if (cd_poly_pyptr != -1) {
1592                                 bm_mesh_remap_cd_update(&(*fap)->head, &new_fap->head, cd_poly_pyptr);
1593                         }
1594                 }
1595
1596                 bm->elem_index_dirty |= BM_FACE | BM_LOOP;
1597                 bm->elem_table_dirty |= BM_FACE;
1598
1599                 MEM_freeN(faces_copy);
1600         }
1601
1602         /* And now, fix all vertices/edges/faces/loops pointers! */
1603         /* Verts' pointers, only edge pointers... */
1604         if (eptr_map) {
1605                 BM_ITER_MESH (ve, &iter, bm, BM_VERTS_OF_MESH) {
1606 /*                      printf("Vert e: %p -> %p\n", ve->e, BLI_ghash_lookup(eptr_map, ve->e));*/
1607                         if (ve->e) {
1608                                 ve->e = BLI_ghash_lookup(eptr_map, ve->e);
1609                                 BLI_assert(ve->e);
1610                         }
1611                 }
1612         }
1613
1614         /* Edges' pointers, only vert pointers (as we don't mess with loops!), and - ack! - edge pointers,
1615          * as we have to handle disklinks... */
1616         if (vptr_map || eptr_map) {
1617                 BM_ITER_MESH (ed, &iter, bm, BM_EDGES_OF_MESH) {
1618                         if (vptr_map) {
1619 /*                              printf("Edge v1: %p -> %p\n", ed->v1, BLI_ghash_lookup(vptr_map, ed->v1));*/
1620 /*                              printf("Edge v2: %p -> %p\n", ed->v2, BLI_ghash_lookup(vptr_map, ed->v2));*/
1621                                 ed->v1 = BLI_ghash_lookup(vptr_map, ed->v1);
1622                                 ed->v2 = BLI_ghash_lookup(vptr_map, ed->v2);
1623                                 BLI_assert(ed->v1);
1624                                 BLI_assert(ed->v2);
1625                         }
1626                         if (eptr_map) {
1627 /*                              printf("Edge v1_disk_link prev: %p -> %p\n", ed->v1_disk_link.prev,*/
1628 /*                                     BLI_ghash_lookup(eptr_map, ed->v1_disk_link.prev));*/
1629 /*                              printf("Edge v1_disk_link next: %p -> %p\n", ed->v1_disk_link.next,*/
1630 /*                                     BLI_ghash_lookup(eptr_map, ed->v1_disk_link.next));*/
1631 /*                              printf("Edge v2_disk_link prev: %p -> %p\n", ed->v2_disk_link.prev,*/
1632 /*                                     BLI_ghash_lookup(eptr_map, ed->v2_disk_link.prev));*/
1633 /*                              printf("Edge v2_disk_link next: %p -> %p\n", ed->v2_disk_link.next,*/
1634 /*                                     BLI_ghash_lookup(eptr_map, ed->v2_disk_link.next));*/
1635                                 ed->v1_disk_link.prev = BLI_ghash_lookup(eptr_map, ed->v1_disk_link.prev);
1636                                 ed->v1_disk_link.next = BLI_ghash_lookup(eptr_map, ed->v1_disk_link.next);
1637                                 ed->v2_disk_link.prev = BLI_ghash_lookup(eptr_map, ed->v2_disk_link.prev);
1638                                 ed->v2_disk_link.next = BLI_ghash_lookup(eptr_map, ed->v2_disk_link.next);
1639                                 BLI_assert(ed->v1_disk_link.prev);
1640                                 BLI_assert(ed->v1_disk_link.next);
1641                                 BLI_assert(ed->v2_disk_link.prev);
1642                                 BLI_assert(ed->v2_disk_link.next);
1643                         }
1644                 }
1645         }
1646
1647         /* Faces' pointers (loops, in fact), always needed... */
1648         BM_ITER_MESH (fa, &iter, bm, BM_FACES_OF_MESH) {
1649                 BM_ITER_ELEM (lo, &iterl, fa, BM_LOOPS_OF_FACE) {
1650                         if (vptr_map) {
1651 /*                              printf("Loop v: %p -> %p\n", lo->v, BLI_ghash_lookup(vptr_map, lo->v));*/
1652                                 lo->v = BLI_ghash_lookup(vptr_map, lo->v);
1653                                 BLI_assert(lo->v);
1654                         }
1655                         if (eptr_map) {
1656 /*                              printf("Loop e: %p -> %p\n", lo->e, BLI_ghash_lookup(eptr_map, lo->e));*/
1657                                 lo->e = BLI_ghash_lookup(eptr_map, lo->e);
1658                                 BLI_assert(lo->e);
1659                         }
1660                         if (fptr_map) {
1661 /*                              printf("Loop f: %p -> %p\n", lo->f, BLI_ghash_lookup(fptr_map, lo->f));*/
1662                                 lo->f = BLI_ghash_lookup(fptr_map, lo->f);
1663                                 BLI_assert(lo->f);
1664                         }
1665                 }
1666         }
1667
1668         /* Selection history */
1669         {
1670                 BMEditSelection *ese;
1671                 for (ese = bm->selected.first; ese; ese = ese->next) {
1672                         switch (ese->htype) {
1673                                 case BM_VERT:
1674                                         if (vptr_map) {
1675                                                 ese->ele = BLI_ghash_lookup(vptr_map, ese->ele);
1676                                                 BLI_assert(ese->ele);
1677                                         }
1678                                         break;
1679                                 case BM_EDGE:
1680                                         if (eptr_map) {
1681                                                 ese->ele = BLI_ghash_lookup(eptr_map, ese->ele);
1682                                                 BLI_assert(ese->ele);
1683                                         }
1684                                         break;
1685                                 case BM_FACE:
1686                                         if (fptr_map) {
1687                                                 ese->ele = BLI_ghash_lookup(fptr_map, ese->ele);
1688                                                 BLI_assert(ese->ele);
1689                                         }
1690                                         break;
1691                         }
1692                 }
1693         }
1694
1695         if (fptr_map) {
1696                 if (bm->act_face) {
1697                         bm->act_face = BLI_ghash_lookup(fptr_map, bm->act_face);
1698                         BLI_assert(bm->act_face);
1699                 }
1700         }
1701
1702         if (vptr_map)
1703                 BLI_ghash_free(vptr_map, NULL, NULL);
1704         if (eptr_map)
1705                 BLI_ghash_free(eptr_map, NULL, NULL);
1706         if (fptr_map)
1707                 BLI_ghash_free(fptr_map, NULL, NULL);
1708 }