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