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