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