Merge branch 'master' into blender2.8
[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_scene_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         if (bm->lnor_spacearr) {
264                 BKE_lnor_spacearr_free(bm->lnor_spacearr);
265                 MEM_freeN(bm->lnor_spacearr);
266         }
267
268         BMO_error_clear(bm);
269 }
270
271 /**
272  * \brief BMesh Clear Mesh
273  *
274  * Clear all data in bm
275  */
276 void BM_mesh_clear(BMesh *bm)
277 {
278         const bool use_toolflags = bm->use_toolflags;
279
280         /* free old mesh */
281         BM_mesh_data_free(bm);
282         memset(bm, 0, sizeof(BMesh));
283
284         /* allocate the memory pools for the mesh elements */
285         bm_mempool_init(bm, &bm_mesh_allocsize_default, use_toolflags);
286
287         bm->use_toolflags = use_toolflags;
288         bm->toolflag_index = 0;
289         bm->totflags = 0;
290
291         CustomData_reset(&bm->vdata);
292         CustomData_reset(&bm->edata);
293         CustomData_reset(&bm->ldata);
294         CustomData_reset(&bm->pdata);
295 }
296
297 /**
298  * \brief BMesh Free Mesh
299  *
300  * Frees a BMesh data and its structure.
301  */
302 void BM_mesh_free(BMesh *bm)
303 {
304         BM_mesh_data_free(bm);
305
306         if (bm->py_handle) {
307                 /* keep this out of 'BM_mesh_data_free' because we want python
308                  * to be able to clear the mesh and maintain access. */
309                 bpy_bm_generic_invalidate(bm->py_handle);
310                 bm->py_handle = NULL;
311         }
312
313         MEM_freeN(bm);
314 }
315
316
317 /**
318  * Helpers for #BM_mesh_normals_update and #BM_verts_calc_normal_vcos
319  */
320
321 /* We use that existing internal API flag, assuming no other tool using it would run concurrently to clnors editing. */
322 #define BM_LNORSPACE_UPDATE _FLAG_MF
323
324 typedef struct BMEdgesCalcVectorsData {
325         /* Read-only data. */
326         const float (*vcos)[3];
327
328         /* Read-write data, but no need to protect it, no concurrency to fear here. */
329         float (*edgevec)[3];
330 } BMEdgesCalcVectorsData;
331
332
333 static void mesh_edges_calc_vectors_cb(void *userdata, MempoolIterData *mp_e)
334 {
335         BMEdgesCalcVectorsData *data = userdata;
336         BMEdge *e = (BMEdge *)mp_e;
337
338         if (e->l) {
339                 const float *v1_co = data->vcos ? data->vcos[BM_elem_index_get(e->v1)] : e->v1->co;
340                 const float *v2_co = data->vcos ? data->vcos[BM_elem_index_get(e->v2)] : e->v2->co;
341                 sub_v3_v3v3(data->edgevec[BM_elem_index_get(e)], v2_co, v1_co);
342                 normalize_v3(data->edgevec[BM_elem_index_get(e)]);
343         }
344         else {
345                 /* the edge vector will not be needed when the edge has no radial */
346         }
347 }
348
349 static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const float (*vcos)[3])
350 {
351         BM_mesh_elem_index_ensure(bm, BM_EDGE | (vcos ?  BM_VERT : 0));
352
353         BMEdgesCalcVectorsData data = {
354             .vcos = vcos,
355             .edgevec = edgevec
356         };
357
358         BM_iter_parallel(bm, BM_EDGES_OF_MESH, mesh_edges_calc_vectors_cb, &data, bm->totedge >= BM_OMP_LIMIT);
359 }
360
361
362 typedef struct BMVertsCalcNormalsData {
363         /* Read-only data. */
364         const float (*fnos)[3];
365         const float (*edgevec)[3];
366         const float (*vcos)[3];
367
368         /* Read-write data, protected by an atomic-based fake spinlock-like system... */
369         float (*vnos)[3];
370 } BMVertsCalcNormalsData;
371
372 static void mesh_verts_calc_normals_accum_cb(void *userdata, MempoolIterData *mp_f)
373 {
374 #define FLT_EQ_NONAN(_fa, _fb) (*((const uint32_t *)&_fa) == *((const uint32_t *)&_fb))
375
376         BMVertsCalcNormalsData *data = userdata;
377         BMFace *f = (BMFace *)mp_f;
378
379         const float *f_no = data->fnos ? data->fnos[BM_elem_index_get(f)] : f->no;
380
381         BMLoop *l_first, *l_iter;
382         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
383         do {
384                 const float *e1diff, *e2diff;
385                 float dotprod;
386                 float fac;
387
388                 /* calculate the dot product of the two edges that
389                  * meet at the loop's vertex */
390                 e1diff = data->edgevec[BM_elem_index_get(l_iter->prev->e)];
391                 e2diff = data->edgevec[BM_elem_index_get(l_iter->e)];
392                 dotprod = dot_v3v3(e1diff, e2diff);
393
394                 /* edge vectors are calculated from e->v1 to e->v2, so
395                  * adjust the dot product if one but not both loops
396                  * actually runs from from e->v2 to e->v1 */
397                 if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) {
398                         dotprod = -dotprod;
399                 }
400
401                 fac = saacos(-dotprod);
402
403                 if (fac != fac) {  /* NAN detection. */
404                         /* Degenerated case, nothing to do here, just ignore that vertex. */
405                         continue;
406                 }
407
408                 /* accumulate weighted face normal into the vertex's normal */
409                 float *v_no = data->vnos ? data->vnos[BM_elem_index_get(l_iter->v)] : l_iter->v->no;
410
411                 /* This block is a lockless threadsafe madd_v3_v3fl.
412                  * It uses the first float of the vector as a sort of cheap spinlock,
413                  * assuming FLT_MAX is a safe 'illegal' value that cannot be set here otherwise.
414                  * It also assumes that collisions between threads are highly unlikely,
415                  * else performances would be quite bad here. */
416                 float virtual_lock = v_no[0];
417                 while (true) {
418                         /* This loops until following conditions are met:
419                          *   - v_no[0] has same value as virtual_lock (i.e. it did not change since last try).
420                          *   - v_no[0] was not FLT_MAX, i.e. it was not locked by another thread.
421                          */
422                         const float vl = atomic_cas_float(&v_no[0], virtual_lock, FLT_MAX);
423                         if (FLT_EQ_NONAN(vl, virtual_lock) && vl != FLT_MAX) {
424                                 break;
425                         }
426                         virtual_lock = vl;
427                 }
428                 BLI_assert(v_no[0] == FLT_MAX);
429                 /* Now we own that normal value, and can change it.
430                  * But first scalar of the vector must not be changed yet, it's our lock! */
431                 virtual_lock += f_no[0] * fac;
432                 v_no[1] += f_no[1] * fac;
433                 v_no[2] += f_no[2] * fac;
434                 /* Second atomic operation to 'release' our lock on that vector and set its first scalar value. */
435                 /* Note that we do not need to loop here, since we 'locked' v_no[0],
436                  * nobody should have changed it in the mean time. */
437                 virtual_lock = atomic_cas_float(&v_no[0], FLT_MAX, virtual_lock);
438                 BLI_assert(virtual_lock == FLT_MAX);
439
440         } while ((l_iter = l_iter->next) != l_first);
441
442 #undef FLT_EQ_NONAN
443 }
444
445 static void mesh_verts_calc_normals_normalize_cb(void *userdata, MempoolIterData *mp_v)
446 {
447         BMVertsCalcNormalsData *data = userdata;
448         BMVert *v = (BMVert *)mp_v;
449
450         float *v_no = data->vnos ? data->vnos[BM_elem_index_get(v)] : v->no;
451         if (UNLIKELY(normalize_v3(v_no) == 0.0f)) {
452                 const float *v_co = data->vcos ? data->vcos[BM_elem_index_get(v)] : v->co;
453                 normalize_v3_v3(v_no, v_co);
454         }
455 }
456
457 static void bm_mesh_verts_calc_normals(
458         BMesh *bm, const float (*edgevec)[3], const float (*fnos)[3],
459         const float (*vcos)[3], float (*vnos)[3])
460 {
461         BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE) | ((vnos || vcos) ?  BM_VERT : 0));
462
463         BMVertsCalcNormalsData data = {
464             .fnos = fnos,
465             .edgevec = edgevec,
466             .vcos = vcos,
467             .vnos = vnos
468         };
469
470         BM_iter_parallel(bm, BM_FACES_OF_MESH, mesh_verts_calc_normals_accum_cb, &data, bm->totface >= BM_OMP_LIMIT);
471
472         /* normalize the accumulated vertex normals */
473         BM_iter_parallel(bm, BM_VERTS_OF_MESH, mesh_verts_calc_normals_normalize_cb, &data, bm->totvert >= BM_OMP_LIMIT);
474 }
475
476
477 static void mesh_faces_calc_normals_cb(void *UNUSED(userdata), MempoolIterData *mp_f)
478 {
479         BMFace *f = (BMFace *)mp_f;
480
481         BM_face_normal_update(f);
482 }
483
484
485 /**
486  * \brief BMesh Compute Normals
487  *
488  * Updates the normals of a mesh.
489  */
490 void BM_mesh_normals_update(BMesh *bm)
491 {
492         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
493
494         /* Parallel mempool iteration does not allow to generate indices inline anymore... */
495         BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE));
496
497         /* calculate all face normals */
498         BM_iter_parallel(bm, BM_FACES_OF_MESH, mesh_faces_calc_normals_cb, NULL, bm->totface >= BM_OMP_LIMIT);
499
500         /* Zero out vertex normals */
501         BMIter viter;
502         BMVert *v;
503         int i;
504
505         BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
506                 BM_elem_index_set(v, i); /* set_inline */
507                 zero_v3(v->no);
508         }
509         bm->elem_index_dirty &= ~BM_VERT;
510
511         /* Compute normalized direction vectors for each edge.
512          * Directions will be used for calculating the weights of the face normals on the vertex normals.
513          */
514         bm_mesh_edges_calc_vectors(bm, edgevec, NULL);
515
516         /* Add weighted face normals to vertices, and normalize vert normals. */
517         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, NULL, NULL, NULL);
518         MEM_freeN(edgevec);
519 }
520
521 /**
522  * \brief BMesh Compute Normals from/to external data.
523  *
524  * Computes the vertex normals of a mesh into vnos, using given vertex coordinates (vcos) and polygon normals (fnos).
525  */
526 void BM_verts_calc_normal_vcos(BMesh *bm, const float (*fnos)[3], const float (*vcos)[3], float (*vnos)[3])
527 {
528         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
529
530         /* Compute normalized direction vectors for each edge.
531          * Directions will be used for calculating the weights of the face normals on the vertex normals.
532          */
533         bm_mesh_edges_calc_vectors(bm, edgevec, vcos);
534
535         /* Add weighted face normals to vertices, and normalize vert normals. */
536         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, fnos, vcos, vnos);
537         MEM_freeN(edgevec);
538 }
539
540 /**
541  * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normal_vcos
542  */
543 static void bm_mesh_edges_sharp_tag(
544         BMesh *bm,
545         const float (*vnos)[3], const float (*fnos)[3], float (*r_lnos)[3],
546         const float split_angle, const bool do_sharp_edges_tag)
547 {
548         BMIter eiter;
549         BMEdge *e;
550         int i;
551
552         const bool check_angle = (split_angle < (float)M_PI);
553         const float split_angle_cos = check_angle ? cosf(split_angle) : -1.0f;
554
555         {
556                 char htype = BM_VERT | BM_LOOP;
557                 if (fnos) {
558                         htype |= BM_FACE;
559                 }
560                 BM_mesh_elem_index_ensure(bm, htype);
561         }
562
563         /* This first loop checks which edges are actually smooth, and pre-populate lnos with vnos (as if they were
564          * all smooth).
565          */
566         BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
567                 BMLoop *l_a, *l_b;
568
569                 BM_elem_index_set(e, i); /* set_inline */
570                 BM_elem_flag_disable(e, BM_ELEM_TAG); /* Clear tag (means edge is sharp). */
571
572                 /* An edge with only two loops, might be smooth... */
573                 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
574                         bool is_angle_smooth = true;
575                         if (check_angle) {
576                                 const float *no_a = fnos ? fnos[BM_elem_index_get(l_a->f)] : l_a->f->no;
577                                 const float *no_b = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_b->f->no;
578                                 is_angle_smooth = (dot_v3v3(no_a, no_b) >= split_angle_cos);
579                         }
580
581                         /* We only tag edges that are *really* smooth:
582                          * If the angle between both its polys' normals is below split_angle value,
583                          * and it is tagged as such,
584                          * and both its faces are smooth,
585                          * and both its faces have compatible (non-flipped) normals,
586                          * i.e. both loops on the same edge do not share the same vertex.
587                          */
588                         if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) &&
589                             BM_elem_flag_test(l_a->f, BM_ELEM_SMOOTH) &&
590                             BM_elem_flag_test(l_b->f, BM_ELEM_SMOOTH) &&
591                             l_a->v != l_b->v)
592                         {
593                                 if (is_angle_smooth) {
594                                         const float *no;
595                                         BM_elem_flag_enable(e, BM_ELEM_TAG);
596
597                                         /* linked vertices might be fully smooth, copy their normals to loop ones. */
598                                         if (r_lnos) {
599                                                 no = vnos ? vnos[BM_elem_index_get(l_a->v)] : l_a->v->no;
600                                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_a)], no);
601                                                 no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no;
602                                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no);
603                                         }
604                                 }
605                                 else if (do_sharp_edges_tag) {
606                                         /* Note that we do not care about the other sharp-edge cases (sharp poly, non-manifold edge, etc.),
607                                          * only tag edge as sharp when it is due to angle threashold. */
608                                         BM_elem_flag_disable(e, BM_ELEM_SMOOTH);
609                                 }
610                         }
611                 }
612         }
613
614         bm->elem_index_dirty &= ~BM_EDGE;
615 }
616
617 /**
618  * Check whether given loop is part of an unknown-so-far cyclic smooth fan, or not.
619  * Needed because cyclic smooth fans have no obvious 'entry point', and yet we need to walk them once, and only once.
620  */
621 bool BM_loop_check_cyclic_smooth_fan(BMLoop *l_curr)
622 {
623         BMLoop *lfan_pivot_next = l_curr;
624         BMEdge *e_next = l_curr->e;
625
626         BLI_assert(!BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG));
627         BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG);
628
629         while (true) {
630                 /* Much simpler than in sibling code with basic Mesh data! */
631                 lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot_next, &e_next);
632
633                 if (!lfan_pivot_next || !BM_elem_flag_test(e_next, BM_ELEM_TAG)) {
634                         /* Sharp loop/edge, so not a cyclic smooth fan... */
635                         return false;
636                 }
637                 /* Smooth loop/edge... */
638                 else if (BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)) {
639                         if (lfan_pivot_next == l_curr) {
640                                 /* We walked around a whole cyclic smooth fan without finding any already-processed loop, means we can
641                                  * use initial l_curr/l_prev edge as start for this smooth fan. */
642                                 return true;
643                         }
644                         /* ... already checked in some previous looping, we can abort. */
645                         return false;
646                 }
647                 else {
648                         /* ... we can skip it in future, and keep checking the smooth fan. */
649                         BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG);
650                 }
651         }
652 }
653
654 /* BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c
655  * Will use first clnors_data array, and fallback to cd_loop_clnors_offset (use NULL and -1 to not use clnors). */
656 static void bm_mesh_loops_calc_normals(
657         BMesh *bm, const float (*vcos)[3], const float (*fnos)[3], float (*r_lnos)[3],
658         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2],
659         const int cd_loop_clnors_offset, const bool do_rebuild)
660 {
661         BMIter fiter;
662         BMFace *f_curr;
663         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
664
665         MLoopNorSpaceArray _lnors_spacearr = {NULL};
666
667         /* Temp normal stack. */
668         BLI_SMALLSTACK_DECLARE(normal, float *);
669         /* Temp clnors stack. */
670         BLI_SMALLSTACK_DECLARE(clnors, short *);
671         /* Temp edge vectors stack, only used when computing lnor spacearr. */
672         BLI_Stack *edge_vectors = NULL;
673
674         {
675                 char htype = 0;
676                 if (vcos) {
677                         htype |= BM_VERT;
678                 }
679                 /* Face/Loop indices are set inline below. */
680                 BM_mesh_elem_index_ensure(bm, htype);
681         }
682
683         if (!r_lnors_spacearr && has_clnors) {
684                 /* We need to compute lnor spacearr if some custom lnor data are given to us! */
685                 r_lnors_spacearr = &_lnors_spacearr;
686         }
687         if (r_lnors_spacearr) {
688                 BKE_lnor_spacearr_init(r_lnors_spacearr, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR);
689                 edge_vectors = BLI_stack_new(sizeof(float[3]), __func__);
690         }
691
692         /* Clear all loops' tags (means none are to be skipped for now). */
693         int index_face, index_loop = 0;
694         BM_ITER_MESH_INDEX (f_curr, &fiter, bm, BM_FACES_OF_MESH, index_face) {
695                 BMLoop *l_curr, *l_first;
696
697                 BM_elem_index_set(f_curr, index_face); /* set_inline */
698
699                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
700                 do {
701                         BM_elem_index_set(l_curr, index_loop++); /* set_inline */
702                         BM_elem_flag_disable(l_curr, BM_ELEM_TAG);
703                 } while ((l_curr = l_curr->next) != l_first);
704         }
705         bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP);
706
707         /* We now know edges that can be smoothed (they are tagged), and edges that will be hard (they aren't).
708          * Now, time to generate the normals.
709          */
710         BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) {
711                 BMLoop *l_curr, *l_first;
712
713                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
714                 do {
715                         if (do_rebuild && !BM_ELEM_API_FLAG_TEST(l_curr, BM_LNORSPACE_UPDATE) &&
716                             !(bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL))
717                         {
718                                 continue;
719                         }
720                         /* A smooth edge, we have to check for cyclic smooth fan case.
721                          * If we find a new, never-processed cyclic smooth fan, we can do it now using that loop/edge as
722                          * 'entry point', otherwise we can skip it. */
723                         /* Note: In theory, we could make bm_mesh_loop_check_cyclic_smooth_fan() store mlfan_pivot's in a stack,
724                          * to avoid having to fan again around the vert during actual computation of clnor & clnorspace.
725                          * However, this would complicate the code, add more memory usage, and BM_vert_step_fan_loop()
726                          * is quite cheap in term of CPU cycles, so really think it's not worth it. */
727                         if (BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) &&
728                             (BM_elem_flag_test(l_curr, BM_ELEM_TAG) || !BM_loop_check_cyclic_smooth_fan(l_curr)))
729                         {
730                         }
731                         else if (!BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) &&
732                                  !BM_elem_flag_test(l_curr->prev->e, BM_ELEM_TAG))
733                         {
734                                 /* Simple case (both edges around that vertex are sharp in related polygon),
735                                  * this vertex just takes its poly normal.
736                                  */
737                                 const int l_curr_index = BM_elem_index_get(l_curr);
738                                 const float *no = fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no;
739                                 copy_v3_v3(r_lnos[l_curr_index], no);
740
741                                 /* If needed, generate this (simple!) lnor space. */
742                                 if (r_lnors_spacearr) {
743                                         float vec_curr[3], vec_prev[3];
744                                         MLoopNorSpace *lnor_space = BKE_lnor_space_create(r_lnors_spacearr);
745
746                                         {
747                                                 const BMVert *v_pivot = l_curr->v;
748                                                 const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co;
749                                                 const BMVert *v_1 = BM_edge_other_vert(l_curr->e, v_pivot);
750                                                 const float *co_1 = vcos ? vcos[BM_elem_index_get(v_1)] : v_1->co;
751                                                 const BMVert *v_2 = BM_edge_other_vert(l_curr->prev->e, v_pivot);
752                                                 const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
753
754                                                 sub_v3_v3v3(vec_curr, co_1, co_pivot);
755                                                 normalize_v3(vec_curr);
756                                                 sub_v3_v3v3(vec_prev, co_2, co_pivot);
757                                                 normalize_v3(vec_prev);
758                                         }
759
760                                         BKE_lnor_space_define(lnor_space, r_lnos[l_curr_index], vec_curr, vec_prev, NULL);
761                                         /* We know there is only one loop in this space, no need to create a linklist in this case... */
762                                         BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, l_curr_index, l_curr, true);
763
764                                         if (has_clnors) {
765                                                 short (*clnor)[2] = clnors_data ? &clnors_data[l_curr_index] :
766                                                                                   BM_ELEM_CD_GET_VOID_P(l_curr, cd_loop_clnors_offset);
767                                                 BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor, r_lnos[l_curr_index]);
768                                         }
769                                 }
770                         }
771                         /* We *do not need* to check/tag loops as already computed!
772                          * Due to the fact a loop only links to one of its two edges, a same fan *will never be walked more than
773                          * once!*
774                          * Since we consider edges having neighbor faces with inverted (flipped) normals as sharp, we are sure that
775                          * no fan will be skipped, even only considering the case (sharp curr_edge, smooth prev_edge), and not the
776                          * alternative (smooth curr_edge, sharp prev_edge).
777                          * All this due/thanks to link between normals and loop ordering.
778                          */
779                         else {
780                                 /* We have to fan around current vertex, until we find the other non-smooth edge,
781                                  * and accumulate face normals into the vertex!
782                                  * Note in case this vertex has only one sharp edge, this is a waste because the normal is the same as
783                                  * the vertex normal, but I do not see any easy way to detect that (would need to count number
784                                  * of sharp edges per vertex, I doubt the additional memory usage would be worth it, especially as
785                                  * it should not be a common case in real-life meshes anyway).
786                                  */
787                                 BMVert *v_pivot = l_curr->v;
788                                 BMEdge *e_next;
789                                 const BMEdge *e_org = l_curr->e;
790                                 BMLoop *lfan_pivot, *lfan_pivot_next;
791                                 int lfan_pivot_index;
792                                 float lnor[3] = {0.0f, 0.0f, 0.0f};
793                                 float vec_curr[3], vec_next[3], vec_org[3];
794
795                                 /* We validate clnors data on the fly - cheapest way to do! */
796                                 int clnors_avg[2] = {0, 0};
797                                 short (*clnor_ref)[2] = NULL;
798                                 int clnors_nbr = 0;
799                                 bool clnors_invalid = false;
800
801                                 const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co;
802
803                                 MLoopNorSpace *lnor_space = r_lnors_spacearr ? BKE_lnor_space_create(r_lnors_spacearr) : NULL;
804
805                                 BLI_assert((edge_vectors == NULL) || BLI_stack_is_empty(edge_vectors));
806
807                                 lfan_pivot = l_curr;
808                                 lfan_pivot_index = BM_elem_index_get(lfan_pivot);
809                                 e_next = lfan_pivot->e;  /* Current edge here, actually! */
810
811                                 /* Only need to compute previous edge's vector once, then we can just reuse old current one! */
812                                 {
813                                         const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
814                                         const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
815
816                                         sub_v3_v3v3(vec_org, co_2, co_pivot);
817                                         normalize_v3(vec_org);
818                                         copy_v3_v3(vec_curr, vec_org);
819
820                                         if (r_lnors_spacearr) {
821                                                 BLI_stack_push(edge_vectors, vec_org);
822                                         }
823                                 }
824
825                                 while (true) {
826                                         /* Much simpler than in sibling code with basic Mesh data! */
827                                         lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot, &e_next);
828                                         if (lfan_pivot_next) {
829                                                 BLI_assert(lfan_pivot_next->v == v_pivot);
830                                         }
831                                         else {
832                                                 /* next edge is non-manifold, we have to find it ourselves! */
833                                                 e_next = (lfan_pivot->e == e_next) ? lfan_pivot->prev->e : lfan_pivot->e;
834                                         }
835
836                                         /* Compute edge vector.
837                                          * NOTE: We could pre-compute those into an array, in the first iteration, instead of computing them
838                                          *       twice (or more) here. However, time gained is not worth memory and time lost,
839                                          *       given the fact that this code should not be called that much in real-life meshes...
840                                          */
841                                         {
842                                                 const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
843                                                 const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
844
845                                                 sub_v3_v3v3(vec_next, co_2, co_pivot);
846                                                 normalize_v3(vec_next);
847                                         }
848
849                                         {
850                                                 /* Code similar to accumulate_vertex_normals_poly_v3. */
851                                                 /* Calculate angle between the two poly edges incident on this vertex. */
852                                                 const BMFace *f = lfan_pivot->f;
853                                                 const float fac = saacos(dot_v3v3(vec_next, vec_curr));
854                                                 const float *no = fnos ? fnos[BM_elem_index_get(f)] : f->no;
855                                                 /* Accumulate */
856                                                 madd_v3_v3fl(lnor, no, fac);
857
858                                                 if (has_clnors) {
859                                                         /* Accumulate all clnors, if they are not all equal we have to fix that! */
860                                                         short (*clnor)[2] = clnors_data ? &clnors_data[lfan_pivot_index] :
861                                                                                           BM_ELEM_CD_GET_VOID_P(lfan_pivot, cd_loop_clnors_offset);
862                                                         if (clnors_nbr) {
863                                                                 clnors_invalid |= ((*clnor_ref)[0] != (*clnor)[0] || (*clnor_ref)[1] != (*clnor)[1]);
864                                                         }
865                                                         else {
866                                                                 clnor_ref = clnor;
867                                                         }
868                                                         clnors_avg[0] += (*clnor)[0];
869                                                         clnors_avg[1] += (*clnor)[1];
870                                                         clnors_nbr++;
871                                                         /* We store here a pointer to all custom lnors processed. */
872                                                         BLI_SMALLSTACK_PUSH(clnors, (short *)*clnor);
873                                                 }
874                                         }
875
876                                         /* We store here a pointer to all loop-normals processed. */
877                                         BLI_SMALLSTACK_PUSH(normal, (float *)r_lnos[lfan_pivot_index]);
878
879                                         if (r_lnors_spacearr) {
880                                                 /* Assign current lnor space to current 'vertex' loop. */
881                                                 BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, lfan_pivot_index, lfan_pivot, false);
882                                                 if (e_next != e_org) {
883                                                         /* We store here all edges-normalized vectors processed. */
884                                                         BLI_stack_push(edge_vectors, vec_next);
885                                                 }
886                                         }
887
888                                         if (!BM_elem_flag_test(e_next, BM_ELEM_TAG) || (e_next == e_org)) {
889                                                 /* Next edge is sharp, we have finished with this fan of faces around this vert! */
890                                                 break;
891                                         }
892
893                                         /* Copy next edge vector to current one. */
894                                         copy_v3_v3(vec_curr, vec_next);
895                                         /* Next pivot loop to current one. */
896                                         lfan_pivot = lfan_pivot_next;
897                                         lfan_pivot_index = BM_elem_index_get(lfan_pivot);
898                                 }
899
900                                 {
901                                         float lnor_len = normalize_v3(lnor);
902
903                                         /* If we are generating lnor spacearr, we can now define the one for this fan. */
904                                         if (r_lnors_spacearr) {
905                                                 if (UNLIKELY(lnor_len == 0.0f)) {
906                                                         /* Use vertex normal as fallback! */
907                                                         copy_v3_v3(lnor, r_lnos[lfan_pivot_index]);
908                                                         lnor_len = 1.0f;
909                                                 }
910
911                                                 BKE_lnor_space_define(lnor_space, lnor, vec_org, vec_next, edge_vectors);
912
913                                                 if (has_clnors) {
914                                                         if (clnors_invalid) {
915                                                                 short *clnor;
916
917                                                                 clnors_avg[0] /= clnors_nbr;
918                                                                 clnors_avg[1] /= clnors_nbr;
919                                                                 /* Fix/update all clnors of this fan with computed average value. */
920
921                                                                 /* Prints continuously when merge custom normals, so commenting. */
922                                                                 /* printf("Invalid clnors in this fan!\n"); */
923
924                                                                 while ((clnor = BLI_SMALLSTACK_POP(clnors))) {
925                                                                         //print_v2("org clnor", clnor);
926                                                                         clnor[0] = (short)clnors_avg[0];
927                                                                         clnor[1] = (short)clnors_avg[1];
928                                                                 }
929                                                                 //print_v2("new clnors", clnors_avg);
930                                                         }
931                                                         else {
932                                                                 /* We still have to consume the stack! */
933                                                                 while (BLI_SMALLSTACK_POP(clnors));
934                                                         }
935                                                         BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor_ref, lnor);
936                                                 }
937                                         }
938
939                                         /* In case we get a zero normal here, just use vertex normal already set! */
940                                         if (LIKELY(lnor_len != 0.0f)) {
941                                                 /* Copy back the final computed normal into all related loop-normals. */
942                                                 float *nor;
943
944                                                 while ((nor = BLI_SMALLSTACK_POP(normal))) {
945                                                         copy_v3_v3(nor, lnor);
946                                                 }
947                                         }
948                                         else {
949                                                 /* We still have to consume the stack! */
950                                                 while (BLI_SMALLSTACK_POP(normal));
951                                         }
952                                 }
953
954                                 /* Tag related vertex as sharp, to avoid fanning around it again (in case it was a smooth one). */
955                                 if (r_lnors_spacearr) {
956                                         BM_elem_flag_enable(l_curr->v, BM_ELEM_TAG);
957                                 }
958                         }
959                 } while ((l_curr = l_curr->next) != l_first);
960         }
961
962         if (r_lnors_spacearr) {
963                 BLI_stack_free(edge_vectors);
964                 if (r_lnors_spacearr == &_lnors_spacearr) {
965                         BKE_lnor_spacearr_free(r_lnors_spacearr);
966                 }
967         }
968 }
969
970 static void bm_mesh_loops_calc_normals_no_autosmooth(
971         BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float (*r_lnos)[3])
972 {
973         BMIter fiter;
974         BMFace *f_curr;
975
976         {
977                 char htype = BM_LOOP;
978                 if (vnos) {
979                         htype |= BM_VERT;
980                 }
981                 if (fnos) {
982                         htype |= BM_FACE;
983                 }
984                 BM_mesh_elem_index_ensure(bm, htype);
985         }
986
987         BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) {
988                 BMLoop *l_curr, *l_first;
989                 const bool is_face_flat = !BM_elem_flag_test(f_curr, BM_ELEM_SMOOTH);
990
991                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
992                 do {
993                         const float *no = is_face_flat ? (fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no) :
994                                                          (vnos ? vnos[BM_elem_index_get(l_curr->v)] : l_curr->v->no);
995                         copy_v3_v3(r_lnos[BM_elem_index_get(l_curr)], no);
996
997                 } while ((l_curr = l_curr->next) != l_first);
998         }
999 }
1000
1001 #if 0  /* Unused currently */
1002 /**
1003  * \brief BMesh Compute Loop Normals
1004  *
1005  * Updates the loop normals of a mesh. Assumes vertex and face normals are valid (else call BM_mesh_normals_update()
1006  * first)!
1007  */
1008 void BM_mesh_loop_normals_update(
1009         BMesh *bm, const bool use_split_normals, const float split_angle, float (*r_lnos)[3],
1010         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2], const int cd_loop_clnors_offset)
1011 {
1012         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
1013
1014         if (use_split_normals) {
1015                 /* Tag smooth edges and set lnos from vnos when they might be completely smooth...
1016                  * When using custom loop normals, disable the angle feature! */
1017                 bm_mesh_edges_sharp_tag(bm, NULL, NULL, has_clnors ? (float)M_PI : split_angle, r_lnos);
1018
1019                 /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
1020                 bm_mesh_loops_calc_normals(bm, NULL, NULL, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset);
1021         }
1022         else {
1023                 BLI_assert(!r_lnors_spacearr);
1024                 bm_mesh_loops_calc_normals_no_autosmooth(bm, NULL, NULL, r_lnos);
1025         }
1026 }
1027 #endif
1028
1029 /**
1030  * \brief BMesh Compute Loop Normals from/to external data.
1031  *
1032  * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals').
1033  * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry (splitting edges).
1034  */
1035 void BM_loops_calc_normal_vcos(
1036         BMesh *bm, const float (*vcos)[3], const float (*vnos)[3], const float (*fnos)[3],
1037         const bool use_split_normals, const float split_angle, float (*r_lnos)[3],
1038         MLoopNorSpaceArray *r_lnors_spacearr, short (*clnors_data)[2],
1039         const int cd_loop_clnors_offset, const bool do_rebuild)
1040 {
1041         const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1);
1042
1043         if (use_split_normals) {
1044                 /* Tag smooth edges and set lnos from vnos when they might be completely smooth...
1045                  * When using custom loop normals, disable the angle feature! */
1046                 bm_mesh_edges_sharp_tag(bm, vnos, fnos, r_lnos, has_clnors ? (float)M_PI : split_angle, false);
1047
1048                 /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
1049                 bm_mesh_loops_calc_normals(
1050                             bm, vcos, fnos, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset, do_rebuild);
1051         }
1052         else {
1053                 BLI_assert(!r_lnors_spacearr);
1054                 bm_mesh_loops_calc_normals_no_autosmooth(bm, vnos, fnos, r_lnos);
1055         }
1056 }
1057
1058 /** Define sharp edges as needed to mimic 'autosmooth' from angle threshold.
1059  *
1060  * Used when defining an empty custom loop normals data layer, to keep same shading as with autosmooth!
1061  */
1062 void BM_edges_sharp_from_angle_set(BMesh *bm, const float split_angle)
1063 {
1064         if (split_angle >= (float)M_PI) {
1065                 /* Nothing to do! */
1066                 return;
1067         }
1068
1069         bm_mesh_edges_sharp_tag(bm, NULL, NULL, NULL, split_angle, true);
1070 }
1071
1072 void BM_lnorspacearr_store(BMesh *bm, float(*r_lnors)[3])
1073 {
1074         BLI_assert(bm->lnor_spacearr != NULL);
1075
1076         if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) {
1077                 BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL);
1078         }
1079
1080         int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL);
1081
1082         BM_loops_calc_normal_vcos(
1083                 bm, NULL, NULL, NULL, true, M_PI, r_lnors, bm->lnor_spacearr, NULL, cd_loop_clnors_offset, false);
1084         bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL);
1085 }
1086
1087 #define CLEAR_SPACEARRAY_THRESHOLD(x) ((x) / 2)
1088
1089 void BM_lnorspace_invalidate(BMesh *bm, const bool do_invalidate_all)
1090 {
1091         if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) {
1092                 return;
1093         }
1094         if (do_invalidate_all || bm->totvertsel > CLEAR_SPACEARRAY_THRESHOLD(bm->totvert)) {
1095                 bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL;
1096                 return;
1097         }
1098         if (bm->lnor_spacearr == NULL) {
1099                 bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL;
1100                 return;
1101         }
1102
1103         BMVert *v;
1104         BMLoop *l;
1105         BMIter viter, liter;
1106         /* Note: we could use temp tag of BMItem for that, but probably better not use it in such a low-level func?
1107          * --mont29 */
1108         BLI_bitmap *done_verts = BLI_BITMAP_NEW(bm->totvert, __func__);
1109
1110         BM_mesh_elem_index_ensure(bm, BM_VERT);
1111
1112         /* When we affect a given vertex, we may affect following smooth fans:
1113          *     - all smooth fans of said vertex;
1114          *     - all smooth fans of all immediate loop-neighbors vertices;
1115          * This can be simplified as 'all loops of selected vertices and their immediate neighbors'
1116          * need to be tagged for update.
1117          */
1118         BM_ITER_MESH(v, &viter, bm, BM_VERTS_OF_MESH) {
1119                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1120                         BM_ITER_ELEM(l, &liter, v, BM_LOOPS_OF_VERT) {
1121                                 BM_ELEM_API_FLAG_ENABLE(l, BM_LNORSPACE_UPDATE);
1122
1123                                 /* Note that we only handle unselected neighbor vertices here, main loop will take care of
1124                                  * selected ones. */
1125                                 if ((!BM_elem_flag_test(l->prev->v, BM_ELEM_SELECT)) &&
1126                                     !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->prev->v)))
1127                                 {
1128
1129                                         BMLoop *l_prev;
1130                                         BMIter liter_prev;
1131                                         BM_ITER_ELEM(l_prev, &liter_prev, l->prev->v, BM_LOOPS_OF_VERT) {
1132                                                 BM_ELEM_API_FLAG_ENABLE(l_prev, BM_LNORSPACE_UPDATE);
1133                                         }
1134                                         BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_prev->v));
1135                                 }
1136
1137                                 if ((!BM_elem_flag_test(l->next->v, BM_ELEM_SELECT)) &&
1138                                     !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->next->v)))
1139                                 {
1140
1141                                         BMLoop *l_next;
1142                                         BMIter liter_next;
1143                                         BM_ITER_ELEM(l_next, &liter_next, l->next->v, BM_LOOPS_OF_VERT) {
1144                                                 BM_ELEM_API_FLAG_ENABLE(l_next, BM_LNORSPACE_UPDATE);
1145                                         }
1146                                         BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_next->v));
1147                                 }
1148                         }
1149
1150                         BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(v));
1151                 }
1152         }
1153
1154         MEM_freeN(done_verts);
1155         bm->spacearr_dirty |= BM_SPACEARR_DIRTY;
1156 }
1157
1158 void BM_lnorspace_rebuild(BMesh *bm, bool preserve_clnor)
1159 {
1160         BLI_assert(bm->lnor_spacearr != NULL);
1161
1162         if (!(bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL))) {
1163                 return;
1164         }
1165         BMFace *f;
1166         BMLoop *l;
1167         BMIter fiter, liter;
1168
1169         float(*r_lnors)[3] = MEM_callocN(sizeof(*r_lnors) * bm->totloop, __func__);
1170         float(*oldnors)[3] = preserve_clnor ? MEM_mallocN(sizeof(*oldnors) * bm->totloop, __func__) : NULL;
1171
1172         int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL);
1173
1174         BM_mesh_elem_index_ensure(bm, BM_LOOP);
1175
1176         if (preserve_clnor) {
1177                 BLI_assert(bm->lnor_spacearr->lspacearr != NULL);
1178
1179                 BM_ITER_MESH(f, &fiter, bm, BM_FACES_OF_MESH) {
1180                         BM_ITER_ELEM(l, &liter, f, BM_LOOPS_OF_FACE) {
1181                                 if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) {
1182                                         short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset);
1183                                         int l_index = BM_elem_index_get(l);
1184
1185                                         BKE_lnor_space_custom_data_to_normal(
1186                                                 bm->lnor_spacearr->lspacearr[l_index], *clnor,
1187                                                 oldnors[l_index]);
1188                                 }
1189                         }
1190                 }
1191         }
1192
1193         if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) {
1194                 BKE_lnor_spacearr_clear(bm->lnor_spacearr);
1195         }
1196         BM_loops_calc_normal_vcos(
1197                 bm, NULL, NULL, NULL, true, M_PI, r_lnors, bm->lnor_spacearr, NULL, cd_loop_clnors_offset, true);
1198         MEM_freeN(r_lnors);
1199
1200         BM_ITER_MESH(f, &fiter, bm, BM_FACES_OF_MESH) {
1201                 BM_ITER_ELEM(l, &liter, f, BM_LOOPS_OF_FACE) {
1202                         if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) {
1203                                 if (preserve_clnor) {
1204                                         short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset);
1205                                         int l_index = BM_elem_index_get(l);
1206                                         BKE_lnor_space_custom_normal_to_data(
1207                                                 bm->lnor_spacearr->lspacearr[l_index], oldnors[l_index],
1208                                                 *clnor);
1209                                 }
1210                                 BM_ELEM_API_FLAG_DISABLE(l, BM_LNORSPACE_UPDATE);
1211                         }
1212                 }
1213         }
1214
1215         MEM_SAFE_FREE(oldnors);
1216         bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL);
1217
1218 #ifndef NDEBUG
1219         BM_lnorspace_err(bm);
1220 #endif
1221 }
1222
1223 void BM_lnorspace_update(BMesh *bm)
1224 {
1225         if (bm->lnor_spacearr == NULL) {
1226                 bm->lnor_spacearr = MEM_callocN(sizeof(*bm->lnor_spacearr), __func__);
1227         }
1228         if (bm->lnor_spacearr->lspacearr == NULL) {
1229                 float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__);
1230
1231                 BM_lnorspacearr_store(bm, lnors);
1232
1233                 MEM_freeN(lnors);
1234         }
1235         else if (bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL)) {
1236                 BM_lnorspace_rebuild(bm, false);
1237         }
1238 }
1239
1240 void BM_normals_loops_edges_tag(BMesh *bm, const bool do_edges)
1241 {
1242         BMFace *f;
1243         BMEdge *e;
1244         BMIter fiter, eiter;
1245         BMLoop *l_curr, *l_first;
1246
1247         if (do_edges) {
1248                 int index_edge;
1249                 BM_ITER_MESH_INDEX(e, &eiter, bm, BM_EDGES_OF_MESH, index_edge) {
1250                         BMLoop *l_a, *l_b;
1251
1252                         BM_elem_index_set(e, index_edge);  /* set_inline */
1253                         BM_elem_flag_disable(e, BM_ELEM_TAG);
1254                         if (BM_edge_loop_pair(e, &l_a, &l_b)) {
1255                                 if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) && l_a->v != l_b->v) {
1256                                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1257                                 }
1258                         }
1259                 }
1260                 bm->elem_index_dirty &= ~BM_EDGE;
1261         }
1262
1263         int index_face, index_loop = 0;
1264         BM_ITER_MESH_INDEX(f, &fiter, bm, BM_FACES_OF_MESH, index_face) {
1265                 BM_elem_index_set(f, index_face);  /* set_inline */
1266                 l_curr = l_first = BM_FACE_FIRST_LOOP(f);
1267                 do {
1268                         BM_elem_index_set(l_curr, index_loop++);  /* set_inline */
1269                         BM_elem_flag_disable(l_curr, BM_ELEM_TAG);
1270                 } while ((l_curr = l_curr->next) != l_first);
1271         }
1272         bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP);
1273 }
1274
1275 /**
1276  * Auxillary function only used by rebuild to detect if any spaces were not marked as invalid.
1277  * Reports error if any of the lnor spaces change after rebuilding, meaning that all the possible
1278  * lnor spaces to be rebuilt were not correctly marked.
1279  */
1280 #ifndef NDEBUG
1281 void BM_lnorspace_err(BMesh *bm)
1282 {
1283         bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL;
1284         bool clear = true;
1285
1286         MLoopNorSpaceArray *temp = MEM_callocN(sizeof(*temp), __func__);
1287         temp->lspacearr = NULL;
1288
1289         BKE_lnor_spacearr_init(temp, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR);
1290
1291         int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL);
1292         float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__);
1293         BM_loops_calc_normal_vcos(bm, NULL, NULL, NULL, true, M_PI, lnors, temp, NULL, cd_loop_clnors_offset, true);
1294
1295         for (int i = 0; i < bm->totloop; i++) {
1296                 int j = 0;
1297                 j += compare_ff(temp->lspacearr[i]->ref_alpha, bm->lnor_spacearr->lspacearr[i]->ref_alpha, 1e-4f);
1298                 j += compare_ff(temp->lspacearr[i]->ref_beta, bm->lnor_spacearr->lspacearr[i]->ref_beta, 1e-4f);
1299                 j += compare_v3v3(temp->lspacearr[i]->vec_lnor, bm->lnor_spacearr->lspacearr[i]->vec_lnor, 1e-4f);
1300                 j += compare_v3v3(temp->lspacearr[i]->vec_ortho, bm->lnor_spacearr->lspacearr[i]->vec_ortho, 1e-4f);
1301                 j += compare_v3v3(temp->lspacearr[i]->vec_ref, bm->lnor_spacearr->lspacearr[i]->vec_ref, 1e-4f);
1302
1303                 if (j != 5) {
1304                         clear = false;
1305                         break;
1306                 }
1307         }
1308         BKE_lnor_spacearr_free(temp);
1309         MEM_freeN(temp);
1310         MEM_freeN(lnors);
1311         BLI_assert(clear);
1312
1313         bm->spacearr_dirty &= ~BM_SPACEARR_DIRTY_ALL;
1314 }
1315 #endif
1316
1317 static void bm_loop_normal_mark_indiv_do_loop(
1318         BMLoop *l, BLI_bitmap *loops, MLoopNorSpaceArray *lnor_spacearr, int *totloopsel)
1319 {
1320         if (l != NULL) {
1321                 const int l_idx = BM_elem_index_get(l);
1322
1323                 if (!BLI_BITMAP_TEST(loops, BM_elem_index_get(l))) {
1324                         /* If vert and face selected share a loop, mark it for editing. */
1325                         BLI_BITMAP_ENABLE(loops, l_idx);
1326                         (*totloopsel)++;
1327
1328                         /* Mark all loops in same loop normal space (aka smooth fan). */
1329                         if ((lnor_spacearr->lspacearr[l_idx]->flags & MLNOR_SPACE_IS_SINGLE) == 0) {
1330                                 for (LinkNode *node = lnor_spacearr->lspacearr[l_idx]->loops; node; node = node->next) {
1331                                         const int lfan_idx = BM_elem_index_get((BMLoop *)node->link);
1332                                         if (!BLI_BITMAP_TEST(loops, lfan_idx)) {
1333                                                 BLI_BITMAP_ENABLE(loops, lfan_idx);
1334                                                 (*totloopsel)++;
1335                                         }
1336                                 }
1337                         }
1338                 }
1339         }
1340 }
1341
1342 /* Mark the individual clnors to be edited, if multiple selection methods are used. */
1343 static int bm_loop_normal_mark_indiv(BMesh *bm, BLI_bitmap *loops)
1344 {
1345         BMEditSelection *ese, *ese_prev;
1346         int totloopsel = 0;
1347
1348         BM_mesh_elem_index_ensure(bm, BM_LOOP);
1349
1350         BLI_assert(bm->lnor_spacearr != NULL);
1351         BLI_assert(bm->lnor_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR);
1352
1353         /* Goes from last selected to the first selected element. */
1354         for (ese = bm->selected.last; ese; ese = ese->prev) {
1355                 if (ese->htype == BM_FACE) {
1356                         ese_prev = ese;
1357                         /* If current face is selected, then any verts to be edited must have been selected before it. */
1358                         while ((ese_prev = ese_prev->prev)) {
1359                                 if (ese_prev->htype == BM_VERT) {
1360                                         bm_loop_normal_mark_indiv_do_loop(
1361                                                 BM_face_vert_share_loop((BMFace *)ese->ele, (BMVert *)ese_prev->ele),
1362                                                 loops, bm->lnor_spacearr, &totloopsel);
1363                                 }
1364                                 else if (ese_prev->htype == BM_EDGE) {
1365                                         bm_loop_normal_mark_indiv_do_loop(
1366                                                 BM_face_vert_share_loop((BMFace *)ese->ele, ((BMEdge *)ese_prev->ele)->v1),
1367                                                 loops, bm->lnor_spacearr, &totloopsel);
1368
1369                                         bm_loop_normal_mark_indiv_do_loop(
1370                                                 BM_face_vert_share_loop((BMFace *)ese->ele, ((BMEdge *)ese_prev->ele)->v2),
1371                                                 loops, bm->lnor_spacearr, &totloopsel);
1372                                 }
1373                         }
1374                 }
1375         }
1376
1377         return totloopsel;
1378 }
1379
1380 static void loop_normal_editdata_init(BMesh *bm, BMLoopNorEditData *lnor_ed, BMVert *v, BMLoop *l, const int offset)
1381 {
1382         BLI_assert(bm->lnor_spacearr != NULL);
1383         BLI_assert(bm->lnor_spacearr->lspacearr != NULL);
1384
1385         const int l_index = BM_elem_index_get(l);
1386         short *clnors_data = BM_ELEM_CD_GET_VOID_P(l, offset);
1387
1388         lnor_ed->loop_index = l_index;
1389         lnor_ed->loop = l;
1390
1391         float custom_normal[3];
1392         BKE_lnor_space_custom_data_to_normal(bm->lnor_spacearr->lspacearr[l_index], clnors_data, custom_normal);
1393
1394         lnor_ed->clnors_data = clnors_data;
1395         copy_v3_v3(lnor_ed->nloc, custom_normal);
1396         copy_v3_v3(lnor_ed->niloc, custom_normal);
1397
1398         lnor_ed->loc = v->co;
1399 }
1400
1401 BMLoopNorEditDataArray *BM_loop_normal_editdata_array_init(BMesh *bm)
1402 {
1403         BMLoop *l;
1404         BMVert *v;
1405         BMIter liter, viter;
1406
1407         bool verts = (bm->selectmode & SCE_SELECT_VERTEX) != 0;
1408         bool edges = (bm->selectmode & SCE_SELECT_EDGE) != 0;
1409         bool faces = (bm->selectmode & SCE_SELECT_FACE) != 0;
1410         int totloopsel = 0;
1411
1412         BLI_assert(bm->spacearr_dirty == 0);
1413
1414         BMLoopNorEditDataArray *lnors_ed_arr = MEM_mallocN(
1415                 sizeof(*lnors_ed_arr), __func__);
1416         lnors_ed_arr->lidx_to_lnor_editdata = MEM_callocN(
1417                 sizeof(*lnors_ed_arr->lidx_to_lnor_editdata) * bm->totloop, __func__);
1418
1419         if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) {
1420                 BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL);
1421         }
1422         const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL);
1423
1424         BM_mesh_elem_index_ensure(bm, BM_LOOP);
1425
1426         BLI_bitmap *loops = BLI_BITMAP_NEW(bm->totloop, __func__);
1427         if (faces && (verts || edges)) {
1428                 /* More than one selection mode, check for individual normals to edit. */
1429                 totloopsel = bm_loop_normal_mark_indiv(bm, loops);
1430         }
1431
1432         if (totloopsel) {
1433                 BMLoopNorEditData *lnor_ed = lnors_ed_arr->lnor_editdata = MEM_mallocN(sizeof(*lnor_ed) * totloopsel, __func__);
1434
1435                 BM_ITER_MESH(v, &viter, bm, BM_VERTS_OF_MESH) {
1436                         BM_ITER_ELEM(l, &liter, v, BM_LOOPS_OF_VERT) {
1437                                 if (BLI_BITMAP_TEST(loops, BM_elem_index_get(l))) {
1438                                         loop_normal_editdata_init(bm, lnor_ed, v, l, cd_custom_normal_offset);
1439                                         lnors_ed_arr->lidx_to_lnor_editdata[BM_elem_index_get(l)] = lnor_ed;
1440                                         lnor_ed++;
1441                                 }
1442                         }
1443                 }
1444                 lnors_ed_arr->totloop = totloopsel;
1445         }
1446         else {  /* If multiple selection modes are inactive OR no such loop is found, fall back to editing all loops. */
1447                 totloopsel = BM_total_loop_select(bm);
1448                 BMLoopNorEditData *lnor_ed = lnors_ed_arr->lnor_editdata = MEM_mallocN(sizeof(*lnor_ed) * totloopsel, __func__);
1449
1450                 BM_ITER_MESH(v, &viter, bm, BM_VERTS_OF_MESH) {
1451                         if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1452                                 BM_ITER_ELEM(l, &liter, v, BM_LOOPS_OF_VERT) {
1453                                         loop_normal_editdata_init(bm, lnor_ed, v, l, cd_custom_normal_offset);
1454                                         lnors_ed_arr->lidx_to_lnor_editdata[BM_elem_index_get(l)] = lnor_ed;
1455                                         lnor_ed++;
1456                                 }
1457                         }
1458                 }
1459                 lnors_ed_arr->totloop = totloopsel;
1460         }
1461
1462         MEM_freeN(loops);
1463         lnors_ed_arr->cd_custom_normal_offset = cd_custom_normal_offset;
1464         return lnors_ed_arr;
1465 }
1466
1467 void BM_loop_normal_editdata_array_free(BMLoopNorEditDataArray *lnors_ed_arr)
1468 {
1469         MEM_SAFE_FREE(lnors_ed_arr->lnor_editdata);
1470         MEM_SAFE_FREE(lnors_ed_arr->lidx_to_lnor_editdata);
1471         MEM_freeN(lnors_ed_arr);
1472 }
1473
1474 int BM_total_loop_select(BMesh *bm)
1475 {
1476         int r_sel = 0;
1477         BMVert *v;
1478         BMIter viter;
1479
1480         BM_ITER_MESH(v, &viter, bm, BM_VERTS_OF_MESH) {
1481                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1482                         r_sel += BM_vert_face_count(v);
1483                 }
1484         }
1485         return r_sel;
1486 }
1487
1488 /**
1489  * \brief BMesh Begin Edit
1490  *
1491  * Functions for setting up a mesh for editing and cleaning up after
1492  * the editing operations are done. These are called by the tools/operator
1493  * API for each time a tool is executed.
1494  */
1495 void bmesh_edit_begin(BMesh *UNUSED(bm), BMOpTypeFlag UNUSED(type_flag))
1496 {
1497         /* Most operators seem to be using BMO_OPTYPE_FLAG_UNTAN_MULTIRES to change the MDisps to
1498          * absolute space during mesh edits. With this enabled, changes to the topology
1499          * (loop cuts, edge subdivides, etc) are not reflected in the higher levels of
1500          * the mesh at all, which doesn't seem right. Turning off completely for now,
1501          * until this is shown to be better for certain types of mesh edits. */
1502 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
1503         /* switch multires data out of tangent space */
1504         if ((type_flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
1505                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_TANGENT, MULTIRES_SPACE_ABSOLUTE);
1506
1507                 /* ensure correct normals, if possible */
1508                 bmesh_rationalize_normals(bm, 0);
1509                 BM_mesh_normals_update(bm);
1510         }
1511 #endif
1512 }
1513
1514 /**
1515  * \brief BMesh End Edit
1516  */
1517 void bmesh_edit_end(BMesh *bm, BMOpTypeFlag type_flag)
1518 {
1519         ListBase select_history;
1520
1521         /* BMO_OPTYPE_FLAG_UNTAN_MULTIRES disabled for now, see comment above in bmesh_edit_begin. */
1522 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
1523         /* switch multires data into tangent space */
1524         if ((flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
1525                 /* set normals to their previous winding */
1526                 bmesh_rationalize_normals(bm, 1);
1527                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
1528         }
1529         else if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
1530                 bmesh_rationalize_normals(bm, 1);
1531         }
1532 #endif
1533
1534         /* compute normals, clear temp flags and flush selections */
1535         if (type_flag & BMO_OPTYPE_FLAG_NORMALS_CALC) {
1536                 bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL;
1537                 BM_mesh_normals_update(bm);
1538         }
1539
1540
1541         if ((type_flag & BMO_OPTYPE_FLAG_SELECT_VALIDATE) == 0) {
1542                 select_history = bm->selected;
1543                 BLI_listbase_clear(&bm->selected);
1544         }
1545
1546         if (type_flag & BMO_OPTYPE_FLAG_SELECT_FLUSH) {
1547                 BM_mesh_select_mode_flush(bm);
1548         }
1549
1550         if ((type_flag & BMO_OPTYPE_FLAG_SELECT_VALIDATE) == 0) {
1551                 bm->selected = select_history;
1552         }
1553         if (type_flag & BMO_OPTYPE_FLAG_INVALIDATE_CLNOR_ALL) {
1554                 bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL;
1555         }
1556 }
1557
1558 void BM_mesh_elem_index_ensure_ex(BMesh *bm, const char htype, int elem_offset[4])
1559 {
1560
1561 #ifdef DEBUG
1562         BM_ELEM_INDEX_VALIDATE(bm, "Should Never Fail!", __func__);
1563 #endif
1564
1565         if (elem_offset == NULL) {
1566                 /* Simple case. */
1567                 const char htype_needed = bm->elem_index_dirty & htype;
1568                 if (htype_needed == 0) {
1569                         goto finally;
1570                 }
1571         }
1572
1573         if (htype & BM_VERT) {
1574                 if ((bm->elem_index_dirty & BM_VERT) || (elem_offset && elem_offset[0])) {
1575                         BMIter iter;
1576                         BMElem *ele;
1577
1578                         int index = elem_offset ? elem_offset[0] : 0;
1579                         BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
1580                                 BM_elem_index_set(ele, index++); /* set_ok */
1581                         }
1582                         BLI_assert(elem_offset || index == bm->totvert);
1583                 }
1584                 else {
1585                         // printf("%s: skipping vert index calc!\n", __func__);
1586                 }
1587         }
1588
1589         if (htype & BM_EDGE) {
1590                 if ((bm->elem_index_dirty & BM_EDGE) || (elem_offset && elem_offset[1])) {
1591                         BMIter iter;
1592                         BMElem *ele;
1593
1594                         int index = elem_offset ? elem_offset[1] : 0;
1595                         BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
1596                                 BM_elem_index_set(ele, index++); /* set_ok */
1597                         }
1598                         BLI_assert(elem_offset || index == bm->totedge);
1599                 }
1600                 else {
1601                         // printf("%s: skipping edge index calc!\n", __func__);
1602                 }
1603         }
1604
1605         if (htype & (BM_FACE | BM_LOOP)) {
1606                 if ((bm->elem_index_dirty & (BM_FACE | BM_LOOP)) || (elem_offset && (elem_offset[2] || elem_offset[3]))) {
1607                         BMIter iter;
1608                         BMElem *ele;
1609
1610                         const bool update_face = (htype & BM_FACE) && (bm->elem_index_dirty & BM_FACE);
1611                         const bool update_loop = (htype & BM_LOOP) && (bm->elem_index_dirty & BM_LOOP);
1612
1613                         int index_loop = elem_offset ? elem_offset[2] : 0;
1614                         int index = elem_offset ? elem_offset[3] : 0;
1615
1616                         BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
1617                                 if (update_face) {
1618                                         BM_elem_index_set(ele, index++); /* set_ok */
1619                                 }
1620
1621                                 if (update_loop) {
1622                                         BMLoop *l_iter, *l_first;
1623
1624                                         l_iter = l_first = BM_FACE_FIRST_LOOP((BMFace *)ele);
1625                                         do {
1626                                                 BM_elem_index_set(l_iter, index_loop++); /* set_ok */
1627                                         } while ((l_iter = l_iter->next) != l_first);
1628                                 }
1629                         }
1630
1631                         BLI_assert(elem_offset || !update_face || index == bm->totface);
1632                         if (update_loop) {
1633                                 BLI_assert(elem_offset || !update_loop || index_loop == bm->totloop);
1634                         }
1635                 }
1636                 else {
1637                         // printf("%s: skipping face/loop index calc!\n", __func__);
1638                 }
1639         }
1640
1641 finally:
1642         bm->elem_index_dirty &= ~htype;
1643         if (elem_offset) {
1644                 if (htype & BM_VERT) {
1645                         elem_offset[0] += bm->totvert;
1646                         if (elem_offset[0] != bm->totvert) {
1647                                 bm->elem_index_dirty |= BM_VERT;
1648                         }
1649                 }
1650                 if (htype & BM_EDGE) {
1651                         elem_offset[1] += bm->totedge;
1652                         if (elem_offset[1] != bm->totedge) {
1653                                 bm->elem_index_dirty |= BM_EDGE;
1654                         }
1655                 }
1656                 if (htype & BM_LOOP) {
1657                         elem_offset[2] += bm->totloop;
1658                         if (elem_offset[2] != bm->totloop) {
1659                                 bm->elem_index_dirty |= BM_LOOP;
1660                         }
1661                 }
1662                 if (htype & BM_FACE) {
1663                         elem_offset[3] += bm->totface;
1664                         if (elem_offset[3] != bm->totface) {
1665                                 bm->elem_index_dirty |= BM_FACE;
1666                         }
1667                 }
1668         }
1669 }
1670
1671 void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
1672 {
1673         BM_mesh_elem_index_ensure_ex(bm, htype, NULL);
1674 }
1675
1676
1677 /**
1678  * Array checking/setting macros
1679  *
1680  * Currently vert/edge/loop/face index data is being abused, in a few areas of the code.
1681  *
1682  * To avoid correcting them afterwards, set 'bm->elem_index_dirty' however its possible
1683  * this flag is set incorrectly which could crash blender.
1684  *
1685  * These functions ensure its correct and are called more often in debug mode.
1686  */
1687
1688 void BM_mesh_elem_index_validate(
1689         BMesh *bm, const char *location, const char *func,
1690         const char *msg_a, const char *msg_b)
1691 {
1692         const char iter_types[3] = {BM_VERTS_OF_MESH,
1693                                     BM_EDGES_OF_MESH,
1694                                     BM_FACES_OF_MESH};
1695
1696         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
1697         const char *type_names[3] = {"vert", "edge", "face"};
1698
1699         BMIter iter;
1700         BMElem *ele;
1701         int i;
1702         bool is_any_error = 0;
1703
1704         for (i = 0; i < 3; i++) {
1705                 const bool is_dirty = (flag_types[i] & bm->elem_index_dirty) != 0;
1706                 int index = 0;
1707                 bool is_error = false;
1708                 int err_val = 0;
1709                 int err_idx = 0;
1710
1711                 BM_ITER_MESH (ele, &iter, bm, iter_types[i]) {
1712                         if (!is_dirty) {
1713                                 if (BM_elem_index_get(ele) != index) {
1714                                         err_val = BM_elem_index_get(ele);
1715                                         err_idx = index;
1716                                         is_error = true;
1717                                 }
1718                         }
1719
1720                         BM_elem_index_set(ele, index); /* set_ok */
1721                         index++;
1722                 }
1723
1724                 if ((is_error == true) && (is_dirty == false)) {
1725                         is_any_error = true;
1726                         fprintf(stderr,
1727                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
1728                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
1729                 }
1730                 else if ((is_error == false) && (is_dirty == true)) {
1731
1732 #if 0       /* mostly annoying */
1733
1734                         /* dirty may have been incorrectly set */
1735                         fprintf(stderr,
1736                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
1737                                 location, func, type_names[i], msg_a, msg_b);
1738 #endif
1739                 }
1740         }
1741
1742 #if 0 /* mostly annoying, even in debug mode */
1743 #ifdef DEBUG
1744         if (is_any_error == 0) {
1745                 fprintf(stderr,
1746                         "Valid Index Success: at %s, %s, '%s', '%s'\n",
1747                         location, func, msg_a, msg_b);
1748         }
1749 #endif
1750 #endif
1751         (void) is_any_error; /* shut up the compiler */
1752
1753 }
1754
1755 /* debug check only - no need to optimize */
1756 #ifndef NDEBUG
1757 bool BM_mesh_elem_table_check(BMesh *bm)
1758 {
1759         BMIter iter;
1760         BMElem *ele;
1761         int i;
1762
1763         if (bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) {
1764                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, i) {
1765                         if (ele != (BMElem *)bm->vtable[i]) {
1766                                 return false;
1767                         }
1768                 }
1769         }
1770
1771         if (bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) {
1772                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, i) {
1773                         if (ele != (BMElem *)bm->etable[i]) {
1774                                 return false;
1775                         }
1776                 }
1777         }
1778
1779         if (bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) {
1780                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, i) {
1781                         if (ele != (BMElem *)bm->ftable[i]) {
1782                                 return false;
1783                         }
1784                 }
1785         }
1786
1787         return true;
1788 }
1789 #endif
1790
1791
1792
1793 void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
1794 {
1795         /* assume if the array is non-null then its valid and no need to recalc */
1796         const char htype_needed = (((bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) ? 0 : BM_VERT) |
1797                                    ((bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) ? 0 : BM_EDGE) |
1798                                    ((bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) ? 0 : BM_FACE)) & htype;
1799
1800         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1801
1802         /* in debug mode double check we didn't need to recalculate */
1803         BLI_assert(BM_mesh_elem_table_check(bm) == true);
1804
1805         if (htype_needed == 0) {
1806                 goto finally;
1807         }
1808
1809         if (htype_needed & BM_VERT) {
1810                 if (bm->vtable && bm->totvert <= bm->vtable_tot && bm->totvert * 2 >= bm->vtable_tot) {
1811                         /* pass (re-use the array) */
1812                 }
1813                 else {
1814                         if (bm->vtable)
1815                                 MEM_freeN(bm->vtable);
1816                         bm->vtable = MEM_mallocN(sizeof(void **) * bm->totvert, "bm->vtable");
1817                         bm->vtable_tot = bm->totvert;
1818                 }
1819         }
1820         if (htype_needed & BM_EDGE) {
1821                 if (bm->etable && bm->totedge <= bm->etable_tot && bm->totedge * 2 >= bm->etable_tot) {
1822                         /* pass (re-use the array) */
1823                 }
1824                 else {
1825                         if (bm->etable)
1826                                 MEM_freeN(bm->etable);
1827                         bm->etable = MEM_mallocN(sizeof(void **) * bm->totedge, "bm->etable");
1828                         bm->etable_tot = bm->totedge;
1829                 }
1830         }
1831         if (htype_needed & BM_FACE) {
1832                 if (bm->ftable && bm->totface <= bm->ftable_tot && bm->totface * 2 >= bm->ftable_tot) {
1833                         /* pass (re-use the array) */
1834                 }
1835                 else {
1836                         if (bm->ftable)
1837                                 MEM_freeN(bm->ftable);
1838                         bm->ftable = MEM_mallocN(sizeof(void **) * bm->totface, "bm->ftable");
1839                         bm->ftable_tot = bm->totface;
1840                 }
1841         }
1842
1843         if (htype_needed & BM_VERT) {
1844                 BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)bm->vtable, bm->totvert);
1845         }
1846
1847         if (htype_needed & BM_EDGE) {
1848                 BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)bm->etable, bm->totedge);
1849         }
1850
1851         if (htype_needed & BM_FACE) {
1852                 BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)bm->ftable, bm->totface);
1853         }
1854
1855 finally:
1856         /* Only clear dirty flags when all the pointers and data are actually valid.
1857          * This prevents possible threading issues when dirty flag check failed but
1858          * data wasn't ready still.
1859          */
1860         bm->elem_table_dirty &= ~htype_needed;
1861 }
1862
1863 /* use BM_mesh_elem_table_ensure where possible to avoid full rebuild */
1864 void BM_mesh_elem_table_init(BMesh *bm, const char htype)
1865 {
1866         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1867
1868         /* force recalc */
1869         BM_mesh_elem_table_free(bm, BM_ALL_NOLOOP);
1870         BM_mesh_elem_table_ensure(bm, htype);
1871 }
1872
1873 void BM_mesh_elem_table_free(BMesh *bm, const char htype)
1874 {
1875         if (htype & BM_VERT) {
1876                 MEM_SAFE_FREE(bm->vtable);
1877         }
1878
1879         if (htype & BM_EDGE) {
1880                 MEM_SAFE_FREE(bm->etable);
1881         }
1882
1883         if (htype & BM_FACE) {
1884                 MEM_SAFE_FREE(bm->ftable);
1885         }
1886 }
1887
1888 BMVert *BM_vert_at_index_find(BMesh *bm, const int index)
1889 {
1890         return BLI_mempool_findelem(bm->vpool, index);
1891 }
1892
1893 BMEdge *BM_edge_at_index_find(BMesh *bm, const int index)
1894 {
1895         return BLI_mempool_findelem(bm->epool, index);
1896 }
1897
1898 BMFace *BM_face_at_index_find(BMesh *bm, const int index)
1899 {
1900         return BLI_mempool_findelem(bm->fpool, index);
1901 }
1902
1903 /**
1904  * Use lookup table when available, else use slower find functions.
1905  *
1906  * \note Try to use #BM_mesh_elem_table_ensure instead.
1907  */
1908 BMVert *BM_vert_at_index_find_or_table(BMesh *bm, const int index)
1909 {
1910         if ((bm->elem_table_dirty & BM_VERT) == 0) {
1911                 return (index < bm->totvert) ? bm->vtable[index] : NULL;
1912         }
1913         else {
1914                 return BM_vert_at_index_find(bm, index);
1915         }
1916 }
1917
1918 BMEdge *BM_edge_at_index_find_or_table(BMesh *bm, const int index)
1919 {
1920         if ((bm->elem_table_dirty & BM_EDGE) == 0) {
1921                 return (index < bm->totedge) ? bm->etable[index] : NULL;
1922         }
1923         else {
1924                 return BM_edge_at_index_find(bm, index);
1925         }
1926 }
1927
1928 BMFace *BM_face_at_index_find_or_table(BMesh *bm, const int index)
1929 {
1930         if ((bm->elem_table_dirty & BM_FACE) == 0) {
1931                 return (index < bm->totface) ? bm->ftable[index] : NULL;
1932         }
1933         else {
1934                 return BM_face_at_index_find(bm, index);
1935         }
1936 }
1937
1938
1939 /**
1940  * Return the amount of element of type 'type' in a given bmesh.
1941  */
1942 int BM_mesh_elem_count(BMesh *bm, const char htype)
1943 {
1944         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1945
1946         switch (htype) {
1947                 case BM_VERT: return bm->totvert;
1948                 case BM_EDGE: return bm->totedge;
1949                 case BM_FACE: return bm->totface;
1950                 default:
1951                 {
1952                         BLI_assert(0);
1953                         return 0;
1954                 }
1955         }
1956 }
1957
1958
1959 /**
1960  * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays
1961  * (xxx_idx[org_index] = new_index).
1962  *
1963  * A NULL array means no changes.
1964  *
1965  * Note: - Does not mess with indices, just sets elem_index_dirty flag.
1966  *       - For verts/edges/faces only (as loops must remain "ordered" and "aligned"
1967  *         on a per-face basis...).
1968  *
1969  * WARNING: Be careful if you keep pointers to affected BM elements, or arrays, when using this func!
1970  */
1971 void BM_mesh_remap(
1972         BMesh *bm,
1973         const uint *vert_idx,
1974         const uint *edge_idx,
1975         const uint *face_idx)
1976 {
1977         /* Mapping old to new pointers. */
1978         GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL;
1979         BMIter iter, iterl;
1980         BMVert *ve;
1981         BMEdge *ed;
1982         BMFace *fa;
1983         BMLoop *lo;
1984
1985         if (!(vert_idx || edge_idx || face_idx))
1986                 return;
1987
1988         BM_mesh_elem_table_ensure(
1989                 bm,
1990                 (vert_idx ? BM_VERT : 0) |
1991                 (edge_idx ? BM_EDGE : 0) |
1992                 (face_idx ? BM_FACE : 0));
1993
1994         /* Remap Verts */
1995         if (vert_idx) {
1996                 BMVert **verts_pool, *verts_copy, **vep;
1997                 int i, totvert = bm->totvert;
1998                 const uint *new_idx;
1999                 /* Special case: Python uses custom - data layers to hold PyObject references.
2000                  * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */
2001                 const int cd_vert_pyptr  = CustomData_get_offset(&bm->vdata, CD_BM_ELEM_PYPTR);
2002
2003                 /* Init the old-to-new vert pointers mapping */
2004                 vptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap vert pointers mapping", bm->totvert);
2005
2006                 /* Make a copy of all vertices. */
2007                 verts_pool = bm->vtable;
2008                 verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy");
2009                 void **pyptrs = (cd_vert_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totvert, __func__) : NULL;
2010                 for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) {
2011                         *ve = **vep;
2012 /*                      printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/
2013                         if (cd_vert_pyptr != -1) {
2014                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)ve), cd_vert_pyptr);
2015                                 pyptrs[i] = *pyptr;
2016                         }
2017                 }
2018
2019                 /* Copy back verts to their new place, and update old2new pointers mapping. */
2020                 new_idx = vert_idx + totvert - 1;
2021                 ve = verts_copy + totvert - 1;
2022                 vep = verts_pool + totvert - 1; /* old, org pointer */
2023                 for (i = totvert; i--; new_idx--, ve--, vep--) {
2024                         BMVert *new_vep = verts_pool[*new_idx];
2025                         *new_vep = *ve;
2026 /*                      printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/
2027                         BLI_ghash_insert(vptr_map, *vep, new_vep);
2028                         if (cd_vert_pyptr != -1) {
2029                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_vep), cd_vert_pyptr);
2030                                 *pyptr = pyptrs[*new_idx];
2031                         }
2032                 }
2033                 bm->elem_index_dirty |= BM_VERT;
2034                 bm->elem_table_dirty |= BM_VERT;
2035
2036                 MEM_freeN(verts_copy);
2037                 if (pyptrs) {
2038                         MEM_freeN(pyptrs);
2039                 }
2040         }
2041
2042         /* Remap Edges */
2043         if (edge_idx) {
2044                 BMEdge **edges_pool, *edges_copy, **edp;
2045                 int i, totedge = bm->totedge;
2046                 const uint *new_idx;
2047                 /* Special case: Python uses custom - data layers to hold PyObject references.
2048                  * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */
2049                 const int cd_edge_pyptr  = CustomData_get_offset(&bm->edata, CD_BM_ELEM_PYPTR);
2050
2051                 /* Init the old-to-new vert pointers mapping */
2052                 eptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap edge pointers mapping", bm->totedge);
2053
2054                 /* Make a copy of all vertices. */
2055                 edges_pool = bm->etable;
2056                 edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy");
2057                 void **pyptrs = (cd_edge_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totedge, __func__) : NULL;
2058                 for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) {
2059                         *ed = **edp;
2060                         if (cd_edge_pyptr != -1) {
2061                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)ed), cd_edge_pyptr);
2062                                 pyptrs[i] = *pyptr;
2063                         }
2064                 }
2065
2066                 /* Copy back verts to their new place, and update old2new pointers mapping. */
2067                 new_idx = edge_idx + totedge - 1;
2068                 ed = edges_copy + totedge - 1;
2069                 edp = edges_pool + totedge - 1; /* old, org pointer */
2070                 for (i = totedge; i--; new_idx--, ed--, edp--) {
2071                         BMEdge *new_edp = edges_pool[*new_idx];
2072                         *new_edp = *ed;
2073                         BLI_ghash_insert(eptr_map, *edp, new_edp);
2074 /*                      printf("mapping edge from %d to %d (%p/%p to %p)\n", i, *new_idx, *edp, edges_pool[i], new_edp);*/
2075                         if (cd_edge_pyptr != -1) {
2076                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_edp), cd_edge_pyptr);
2077                                 *pyptr = pyptrs[*new_idx];
2078                         }
2079                 }
2080                 bm->elem_index_dirty |= BM_EDGE;
2081                 bm->elem_table_dirty |= BM_EDGE;
2082
2083                 MEM_freeN(edges_copy);
2084                 if (pyptrs) {
2085                         MEM_freeN(pyptrs);
2086                 }
2087         }
2088
2089         /* Remap Faces */
2090         if (face_idx) {
2091                 BMFace **faces_pool, *faces_copy, **fap;
2092                 int i, totface = bm->totface;
2093                 const uint *new_idx;
2094                 /* Special case: Python uses custom - data layers to hold PyObject references.
2095                  * These have to be kept in - place, else the PyObject's we point to, wont point back to us. */
2096                 const int cd_poly_pyptr  = CustomData_get_offset(&bm->pdata, CD_BM_ELEM_PYPTR);
2097
2098                 /* Init the old-to-new vert pointers mapping */
2099                 fptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap face pointers mapping", bm->totface);
2100
2101                 /* Make a copy of all vertices. */
2102                 faces_pool = bm->ftable;
2103                 faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy");
2104                 void **pyptrs = (cd_poly_pyptr != -1) ? MEM_mallocN(sizeof(void *) * totface, __func__) : NULL;
2105                 for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) {
2106                         *fa = **fap;
2107                         if (cd_poly_pyptr != -1) {
2108                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)fa), cd_poly_pyptr);
2109                                 pyptrs[i] = *pyptr;
2110                         }
2111                 }
2112
2113                 /* Copy back verts to their new place, and update old2new pointers mapping. */
2114                 new_idx = face_idx + totface - 1;
2115                 fa = faces_copy + totface - 1;
2116                 fap = faces_pool + totface - 1; /* old, org pointer */
2117                 for (i = totface; i--; new_idx--, fa--, fap--) {
2118                         BMFace *new_fap = faces_pool[*new_idx];
2119                         *new_fap = *fa;
2120                         BLI_ghash_insert(fptr_map, *fap, new_fap);
2121                         if (cd_poly_pyptr != -1) {
2122                                 void **pyptr = BM_ELEM_CD_GET_VOID_P(((BMElem *)new_fap), cd_poly_pyptr);
2123                                 *pyptr = pyptrs[*new_idx];
2124                         }
2125                 }
2126
2127                 bm->elem_index_dirty |= BM_FACE | BM_LOOP;
2128                 bm->elem_table_dirty |= BM_FACE;
2129
2130                 MEM_freeN(faces_copy);
2131                 if (pyptrs) {
2132                         MEM_freeN(pyptrs);
2133                 }
2134         }
2135
2136         /* And now, fix all vertices/edges/faces/loops pointers! */
2137         /* Verts' pointers, only edge pointers... */
2138         if (eptr_map) {
2139                 BM_ITER_MESH (ve, &iter, bm, BM_VERTS_OF_MESH) {
2140 /*                      printf("Vert e: %p -> %p\n", ve->e, BLI_ghash_lookup(eptr_map, ve->e));*/
2141                         if (ve->e) {
2142                                 ve->e = BLI_ghash_lookup(eptr_map, ve->e);
2143                                 BLI_assert(ve->e);
2144                         }
2145                 }
2146         }
2147
2148         /* Edges' pointers, only vert pointers (as we don't mess with loops!), and - ack! - edge pointers,
2149          * as we have to handle disklinks... */
2150         if (vptr_map || eptr_map) {
2151                 BM_ITER_MESH (ed, &iter, bm, BM_EDGES_OF_MESH) {
2152                         if (vptr_map) {
2153 /*                              printf("Edge v1: %p -> %p\n", ed->v1, BLI_ghash_lookup(vptr_map, ed->v1));*/
2154 /*                              printf("Edge v2: %p -> %p\n", ed->v2, BLI_ghash_lookup(vptr_map, ed->v2));*/
2155                                 ed->v1 = BLI_ghash_lookup(vptr_map, ed->v1);
2156                                 ed->v2 = BLI_ghash_lookup(vptr_map, ed->v2);
2157                                 BLI_assert(ed->v1);
2158                                 BLI_assert(ed->v2);
2159                         }
2160                         if (eptr_map) {
2161 /*                              printf("Edge v1_disk_link prev: %p -> %p\n", ed->v1_disk_link.prev,*/
2162 /*                                     BLI_ghash_lookup(eptr_map, ed->v1_disk_link.prev));*/
2163 /*                              printf("Edge v1_disk_link next: %p -> %p\n", ed->v1_disk_link.next,*/
2164 /*                                     BLI_ghash_lookup(eptr_map, ed->v1_disk_link.next));*/
2165 /*                              printf("Edge v2_disk_link prev: %p -> %p\n", ed->v2_disk_link.prev,*/
2166 /*                                     BLI_ghash_lookup(eptr_map, ed->v2_disk_link.prev));*/
2167 /*                              printf("Edge v2_disk_link next: %p -> %p\n", ed->v2_disk_link.next,*/
2168 /*                                     BLI_ghash_lookup(eptr_map, ed->v2_disk_link.next));*/
2169                                 ed->v1_disk_link.prev = BLI_ghash_lookup(eptr_map, ed->v1_disk_link.prev);
2170                                 ed->v1_disk_link.next = BLI_ghash_lookup(eptr_map, ed->v1_disk_link.next);
2171                                 ed->v2_disk_link.prev = BLI_ghash_lookup(eptr_map, ed->v2_disk_link.prev);
2172                                 ed->v2_disk_link.next = BLI_ghash_lookup(eptr_map, ed->v2_disk_link.next);
2173                                 BLI_assert(ed->v1_disk_link.prev);
2174                                 BLI_assert(ed->v1_disk_link.next);
2175                                 BLI_assert(ed->v2_disk_link.prev);
2176                                 BLI_assert(ed->v2_disk_link.next);
2177                         }
2178                 }
2179         }
2180
2181         /* Faces' pointers (loops, in fact), always needed... */
2182         BM_ITER_MESH (fa, &iter, bm, BM_FACES_OF_MESH) {
2183                 BM_ITER_ELEM (lo, &iterl, fa, BM_LOOPS_OF_FACE) {
2184                         if (vptr_map) {
2185 /*                              printf("Loop v: %p -> %p\n", lo->v, BLI_ghash_lookup(vptr_map, lo->v));*/
2186                                 lo->v = BLI_ghash_lookup(vptr_map, lo->v);
2187                                 BLI_assert(lo->v);
2188                         }
2189                         if (eptr_map) {
2190 /*                              printf("Loop e: %p -> %p\n", lo->e, BLI_ghash_lookup(eptr_map, lo->e));*/
2191                                 lo->e = BLI_ghash_lookup(eptr_map, lo->e);
2192                                 BLI_assert(lo->e);
2193                         }
2194                         if (fptr_map) {
2195 /*                              printf("Loop f: %p -> %p\n", lo->f, BLI_ghash_lookup(fptr_map, lo->f));*/
2196                                 lo->f = BLI_ghash_lookup(fptr_map, lo->f);
2197                                 BLI_assert(lo->f);
2198                         }
2199                 }
2200         }
2201
2202         /* Selection history */
2203         {
2204                 BMEditSelection *ese;
2205                 for (ese = bm->selected.first; ese; ese = ese->next) {
2206                         switch (ese->htype) {
2207                                 case BM_VERT:
2208                                         if (vptr_map) {
2209                                                 ese->ele = BLI_ghash_lookup(vptr_map, ese->ele);
2210                                                 BLI_assert(ese->ele);
2211                                         }
2212                                         break;
2213                                 case BM_EDGE:
2214                                         if (eptr_map) {
2215                                                 ese->ele = BLI_ghash_lookup(eptr_map, ese->ele);
2216                                                 BLI_assert(ese->ele);
2217                                         }
2218                                         break;
2219                                 case BM_FACE:
2220                                         if (fptr_map) {
2221                                                 ese->ele = BLI_ghash_lookup(fptr_map, ese->ele);
2222                                                 BLI_assert(ese->ele);
2223                                         }
2224                                         break;
2225                         }
2226                 }
2227         }
2228
2229         if (fptr_map) {
2230                 if (bm->act_face) {
2231                         bm->act_face = BLI_ghash_lookup(fptr_map, bm->act_face);
2232                         BLI_assert(bm->act_face);
2233                 }
2234         }
2235
2236         if (vptr_map)
2237                 BLI_ghash_free(vptr_map, NULL, NULL);
2238         if (eptr_map)
2239                 BLI_ghash_free(eptr_map, NULL, NULL);
2240         if (fptr_map)
2241                 BLI_ghash_free(fptr_map, NULL, NULL);
2242 }
2243
2244 /**
2245  * Use new memory pools for this mesh.
2246  *
2247  * \note needed for re-sizing elements (adding/removing tool flags)
2248  * but could also be used for packing fragmented bmeshes.
2249  */
2250 void BM_mesh_rebuild(
2251         BMesh *bm, const struct BMeshCreateParams *params,
2252         BLI_mempool *vpool_dst, BLI_mempool *epool_dst, BLI_mempool *lpool_dst, BLI_mempool *fpool_dst)
2253 {
2254         const char remap =
2255                 (vpool_dst ? BM_VERT : 0) |
2256                 (epool_dst ? BM_EDGE : 0) |
2257                 (lpool_dst ? BM_LOOP : 0) |
2258                 (fpool_dst ? BM_FACE : 0);
2259
2260         BMVert **vtable_dst = (remap & BM_VERT) ? MEM_mallocN(bm->totvert * sizeof(BMVert *), __func__) : NULL;
2261         BMEdge **etable_dst = (remap & BM_EDGE) ? MEM_mallocN(bm->totedge * sizeof(BMEdge *), __func__) : NULL;
2262         BMLoop **ltable_dst = (remap & BM_LOOP) ? MEM_mallocN(bm->totloop * sizeof(BMLoop *), __func__) : NULL;
2263         BMFace **ftable_dst = (remap & BM_FACE) ? MEM_mallocN(bm->totface * sizeof(BMFace *), __func__) : NULL;
2264
2265         const bool use_toolflags = params->use_toolflags;
2266
2267         if (remap & BM_VERT) {
2268                 BMIter iter;
2269                 int index;
2270                 BMVert *v_src;
2271                 BM_ITER_MESH_INDEX (v_src, &iter, bm, BM_VERTS_OF_MESH, index) {
2272                         BMVert *v_dst = BLI_mempool_alloc(vpool_dst);
2273                         memcpy(v_dst, v_src, sizeof(BMVert));
2274                         if (use_toolflags) {
2275                                 ((BMVert_OFlag *)v_dst)->oflags = bm->vtoolflagpool ? BLI_mempool_calloc(bm->vtoolflagpool) : NULL;
2276                         }
2277
2278                         vtable_dst[index] = v_dst;
2279                         BM_elem_index_set(v_src, index);  /* set_ok */
2280                 }
2281         }
2282
2283         if (remap & BM_EDGE) {
2284                 BMIter iter;
2285                 int index;
2286                 BMEdge *e_src;
2287                 BM_ITER_MESH_INDEX (e_src, &iter, bm, BM_EDGES_OF_MESH, index) {
2288                         BMEdge *e_dst = BLI_mempool_alloc(epool_dst);
2289                         memcpy(e_dst, e_src, sizeof(BMEdge));
2290                         if (use_toolflags) {
2291                                 ((BMEdge_OFlag *)e_dst)->oflags = bm->etoolflagpool ? BLI_mempool_calloc(bm->etoolflagpool) : NULL;
2292                         }
2293
2294                         etable_dst[index] = e_dst;
2295                         BM_elem_index_set(e_src, index);  /* set_ok */
2296                 }
2297         }
2298
2299         if (remap & (BM_LOOP | BM_FACE)) {
2300                 BMIter iter;
2301                 int index, index_loop = 0;
2302                 BMFace *f_src;
2303                 BM_ITER_MESH_INDEX (f_src, &iter, bm, BM_FACES_OF_MESH, index) {
2304
2305                         if (remap & BM_FACE) {
2306                                 BMFace *f_dst = BLI_mempool_alloc(fpool_dst);
2307                                 memcpy(f_dst, f_src, sizeof(BMFace));
2308                                 if (use_toolflags) {
2309                                         ((BMFace_OFlag *)f_dst)->oflags = bm->ftoolflagpool ? BLI_mempool_calloc(bm->ftoolflagpool) : NULL;
2310                                 }
2311
2312                                 ftable_dst[index] = f_dst;
2313                                 BM_elem_index_set(f_src, index);  /* set_ok */
2314                         }
2315
2316                         /* handle loops */
2317                         if (remap & BM_LOOP) {
2318                                 BMLoop *l_iter_src, *l_first_src;
2319                                 l_iter_src = l_first_src = BM_FACE_FIRST_LOOP((BMFace *)f_src);
2320                                 do {
2321                                         BMLoop *l_dst = BLI_mempool_alloc(lpool_dst);
2322                                         memcpy(l_dst, l_iter_src, sizeof(BMLoop));
2323                                         ltable_dst[index_loop] = l_dst;
2324                                         BM_elem_index_set(l_iter_src, index_loop++); /* set_ok */
2325                                 } while ((l_iter_src = l_iter_src->next) != l_first_src);
2326                         }
2327                 }
2328         }
2329
2330 #define MAP_VERT(ele) vtable_dst[BM_elem_index_get(ele)]
2331 #define MAP_EDGE(ele) etable_dst[BM_elem_index_get(ele)]
2332 #define MAP_LOOP(ele) ltable_dst[BM_elem_index_get(ele)]
2333 #define MAP_FACE(ele) ftable_dst[BM_elem_index_get(ele)]
2334
2335 #define REMAP_VERT(ele) { if (remap & BM_VERT) { ele = MAP_VERT(ele); }} ((void)0)
2336 #define REMAP_EDGE(ele) { if (remap & BM_EDGE) { ele = MAP_EDGE(ele); }} ((void)0)
2337 #define REMAP_LOOP(ele) { if (remap & BM_LOOP) { ele = MAP_LOOP(ele); }} ((void)0)
2338 #define REMAP_FACE(ele) { if (remap & BM_FACE) { ele = MAP_FACE(ele); }} ((void)0)
2339
2340         /* verts */
2341         {
2342                 for (int i = 0; i < bm->totvert; i++) {
2343                         BMVert *v = vtable_dst[i];
2344                         if (v->e) {
2345                                 REMAP_EDGE(v->e);
2346                         }
2347                 }
2348         }
2349
2350         /* edges */
2351         {
2352                 for (int i = 0; i < bm->totedge; i++) {
2353                         BMEdge *e = etable_dst[i];
2354                         REMAP_VERT(e->v1);
2355                         REMAP_VERT(e->v2);
2356                         REMAP_EDGE(e->v1_disk_link.next);
2357                         REMAP_EDGE(e->v1_disk_link.prev);
2358                         REMAP_EDGE(e->v2_disk_link.next);
2359                         REMAP_EDGE(e->v2_disk_link.prev);
2360                         if (e->l) {
2361                                 REMAP_LOOP(e->l);
2362                         }
2363                 }
2364         }
2365
2366         /* faces */
2367         {
2368                 for (int i = 0; i < bm->totface; i++) {
2369                         BMFace *f = ftable_dst[i];
2370                         REMAP_LOOP(f->l_first);
2371
2372                         {
2373                                 BMLoop *l_iter, *l_first;
2374                                 l_iter = l_first = BM_FACE_FIRST_LOOP((BMFace *)f);
2375                                 do {
2376                                         REMAP_VERT(l_iter->v);
2377                                         REMAP_EDGE(l_iter->e);
2378                                         REMAP_FACE(l_iter->f);
2379
2380                                         REMAP_LOOP(l_iter->radial_next);
2381                                         REMAP_LOOP(l_iter->radial_prev);
2382                                         REMAP_LOOP(l_iter->next);
2383                                         REMAP_LOOP(l_iter->prev);
2384                                 } while ((l_iter = l_iter->next) != l_first);
2385                         }
2386                 }
2387         }
2388
2389         for (BMEditSelection *ese = bm->selected.first; ese; ese = ese->next) {
2390                 switch (ese->htype) {
2391                         case BM_VERT:
2392                                 if (remap & BM_VERT) {
2393                                         ese->ele = (BMElem *)MAP_VERT(ese->ele);
2394                                 }
2395                                 break;
2396                         case BM_EDGE:
2397                                 if (remap & BM_EDGE) {
2398                                         ese->ele = (BMElem *)MAP_EDGE(ese->ele);
2399                                 }
2400                                 break;
2401                         case BM_FACE:
2402                                 if (remap & BM_FACE) {
2403                                         ese->ele = (BMElem *)MAP_FACE(ese->ele);
2404                                 }
2405                                 break;
2406                 }
2407         }
2408
2409         if (bm->act_face) {
2410                 REMAP_FACE(bm->act_face);
2411         }
2412
2413 #undef MAP_VERT
2414 #undef MAP_EDGE
2415 #undef MAP_LOOP
2416 #undef MAP_EDGE
2417
2418 #undef REMAP_VERT
2419 #undef REMAP_EDGE
2420 #undef REMAP_LOOP
2421 #undef REMAP_EDGE
2422
2423         /* Cleanup, re-use local tables if the current mesh had tables allocated.
2424          * could use irrespective but it may use more memory then the caller wants (and not be needed). */
2425         if (remap & BM_VERT) {
2426                 if (bm->vtable) {
2427                         SWAP(BMVert **, vtable_dst, bm->vtable);
2428                         bm->vtable_tot = bm->totvert;
2429                         bm->elem_table_dirty &= ~BM_VERT;
2430                 }
2431                 MEM_freeN(vtable_dst);
2432                 BLI_mempool_destroy(bm->vpool);
2433                 bm->vpool = vpool_dst;
2434         }
2435
2436         if (remap & BM_EDGE) {
2437                 if (bm->etable) {
2438                         SWAP(BMEdge **, etable_dst, bm->etable);
2439                         bm->etable_tot = bm->totedge;
2440                         bm->elem_table_dirty &= ~BM_EDGE;
2441                 }
2442                 MEM_freeN(etable_dst);
2443                 BLI_mempool_destroy(bm->epool);
2444                 bm->epool = epool_dst;
2445         }
2446
2447         if (remap & BM_LOOP) {
2448                 /* no loop table */
2449                 MEM_freeN(ltable_dst);
2450                 BLI_mempool_destroy(bm->lpool);
2451                 bm->lpool = lpool_dst;
2452         }
2453
2454         if (remap & BM_FACE) {
2455                 if (bm->ftable) {
2456                         SWAP(BMFace **, ftable_dst, bm->ftable);
2457                         bm->ftable_tot = bm->totface;
2458                         bm->elem_table_dirty &= ~BM_FACE;
2459                 }
2460                 MEM_freeN(ftable_dst);
2461                 BLI_mempool_destroy(bm->fpool);
2462                 bm->fpool = fpool_dst;
2463         }
2464 }
2465
2466 /**
2467  * Re-allocates mesh data with/without toolflags.
2468  */
2469 void BM_mesh_toolflags_set(BMesh *bm, bool use_toolflags)
2470 {
2471         if (bm->use_toolflags == use_toolflags) {
2472                 return;
2473         }
2474
2475         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_BM(bm);
2476
2477         BLI_mempool *vpool_dst = NULL;
2478         BLI_mempool *epool_dst = NULL;
2479         BLI_mempool *fpool_dst = NULL;
2480
2481         bm_mempool_init_ex(
2482                 &allocsize, use_toolflags,
2483                 &vpool_dst, &epool_dst, NULL, &fpool_dst);
2484
2485         if (use_toolflags == false) {
2486                 BLI_mempool_destroy(bm->vtoolflagpool);
2487                 BLI_mempool_destroy(bm->etoolflagpool);
2488                 BLI_mempool_destroy(bm->ftoolflagpool);
2489
2490                 bm->vtoolflagpool = NULL;
2491                 bm->etoolflagpool = NULL;
2492                 bm->ftoolflagpool = NULL;
2493         }
2494
2495         BM_mesh_rebuild(
2496                 bm,
2497                 &((struct BMeshCreateParams){.use_toolflags = use_toolflags,}),
2498                 vpool_dst, epool_dst, NULL, fpool_dst);
2499
2500         bm->use_toolflags = use_toolflags;
2501 }