Split Normals I (2/5): Add basic BMesh support of split 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
34 #include "BLI_linklist_stack.h"
35 #include "BLI_listbase.h"
36 #include "BLI_math.h"
37 #include "BLI_utildefines.h"
38
39 #include "BKE_cdderivedmesh.h"
40 #include "BKE_editmesh.h"
41 #include "BKE_multires.h"
42
43 #include "intern/bmesh_private.h"
44
45 /* used as an extern, defined in bmesh.h */
46 const BMAllocTemplate bm_mesh_allocsize_default = {512, 1024, 2048, 512};
47 const BMAllocTemplate bm_mesh_chunksize_default = {512, 1024, 2048, 512};
48
49 static void bm_mempool_init(BMesh *bm, const BMAllocTemplate *allocsize)
50 {
51         bm->vpool = BLI_mempool_create(sizeof(BMVert), allocsize->totvert,
52                                        bm_mesh_chunksize_default.totvert, BLI_MEMPOOL_ALLOW_ITER);
53         bm->epool = BLI_mempool_create(sizeof(BMEdge), allocsize->totedge,
54                                        bm_mesh_chunksize_default.totedge, BLI_MEMPOOL_ALLOW_ITER);
55         bm->lpool = BLI_mempool_create(sizeof(BMLoop), allocsize->totloop,
56                                        bm_mesh_chunksize_default.totloop, BLI_MEMPOOL_NOP);
57         bm->fpool = BLI_mempool_create(sizeof(BMFace), allocsize->totface,
58                                        bm_mesh_chunksize_default.totface, BLI_MEMPOOL_ALLOW_ITER);
59
60 #ifdef USE_BMESH_HOLES
61         bm->looplistpool = BLI_mempool_create(sizeof(BMLoopList), 512, 512, BLI_MEMPOOL_NOP);
62 #endif
63 }
64
65 void BM_mesh_elem_toolflags_ensure(BMesh *bm)
66 {
67         if (bm->vtoolflagpool && bm->etoolflagpool && bm->ftoolflagpool) {
68                 return;
69         }
70
71         bm->vtoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totvert, 512, BLI_MEMPOOL_NOP);
72         bm->etoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totedge, 512, BLI_MEMPOOL_NOP);
73         bm->ftoolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), bm->totface, 512, BLI_MEMPOOL_NOP);
74
75 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
76         {
77 #pragma omp section
78                 {
79                         BLI_mempool *toolflagpool = bm->vtoolflagpool;
80                         BMIter iter;
81                         BMElemF *ele;
82                         BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
83                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
84                         }
85                 }
86 #pragma omp section
87                 {
88                         BLI_mempool *toolflagpool = bm->etoolflagpool;
89                         BMIter iter;
90                         BMElemF *ele;
91                         BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
92                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
93                         }
94                 }
95 #pragma omp section
96                 {
97                         BLI_mempool *toolflagpool = bm->ftoolflagpool;
98                         BMIter iter;
99                         BMElemF *ele;
100                         BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
101                                 ele->oflags = BLI_mempool_calloc(toolflagpool);
102                         }
103                 }
104         }
105
106
107         bm->totflags = 1;
108 }
109
110 void BM_mesh_elem_toolflags_clear(BMesh *bm)
111 {
112         if (bm->vtoolflagpool) {
113                 BLI_mempool_destroy(bm->vtoolflagpool);
114                 bm->vtoolflagpool = NULL;
115         }
116         if (bm->etoolflagpool) {
117                 BLI_mempool_destroy(bm->etoolflagpool);
118                 bm->etoolflagpool = NULL;
119         }
120         if (bm->ftoolflagpool) {
121                 BLI_mempool_destroy(bm->ftoolflagpool);
122                 bm->ftoolflagpool = NULL;
123         }
124 }
125
126 /**
127  * \brief BMesh Make Mesh
128  *
129  * Allocates a new BMesh structure.
130  *
131  * \return The New bmesh
132  *
133  * \note ob is needed by multires
134  */
135 BMesh *BM_mesh_create(const BMAllocTemplate *allocsize)
136 {
137         /* allocate the structure */
138         BMesh *bm = MEM_callocN(sizeof(BMesh), __func__);
139         
140         /* allocate the memory pools for the mesh elements */
141         bm_mempool_init(bm, allocsize);
142
143         /* allocate one flag pool that we don't get rid of. */
144         bm->stackdepth = 1;
145         bm->totflags = 0;
146
147         CustomData_reset(&bm->vdata);
148         CustomData_reset(&bm->edata);
149         CustomData_reset(&bm->ldata);
150         CustomData_reset(&bm->pdata);
151
152         return bm;
153 }
154
155 /**
156  * \brief BMesh Free Mesh Data
157  *
158  *      Frees a BMesh structure.
159  *
160  * \note frees mesh, but not actual BMesh struct
161  */
162 void BM_mesh_data_free(BMesh *bm)
163 {
164         BMVert *v;
165         BMEdge *e;
166         BMLoop *l;
167         BMFace *f;
168
169         BMIter iter;
170         BMIter itersub;
171
172         const bool is_ldata_free = CustomData_bmesh_has_free(&bm->ldata);
173         const bool is_pdata_free = CustomData_bmesh_has_free(&bm->pdata);
174
175         /* Check if we have to call free, if not we can avoid a lot of looping */
176         if (CustomData_bmesh_has_free(&(bm->vdata))) {
177                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
178                         CustomData_bmesh_free_block(&(bm->vdata), &(v->head.data));
179                 }
180         }
181         if (CustomData_bmesh_has_free(&(bm->edata))) {
182                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
183                         CustomData_bmesh_free_block(&(bm->edata), &(e->head.data));
184                 }
185         }
186
187         if (is_ldata_free || is_pdata_free) {
188                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
189                         if (is_pdata_free)
190                                 CustomData_bmesh_free_block(&(bm->pdata), &(f->head.data));
191                         if (is_ldata_free) {
192                                 BM_ITER_ELEM (l, &itersub, f, BM_LOOPS_OF_FACE) {
193                                         CustomData_bmesh_free_block(&(bm->ldata), &(l->head.data));
194                                 }
195                         }
196                 }
197         }
198
199         /* Free custom data pools, This should probably go in CustomData_free? */
200         if (bm->vdata.totlayer) BLI_mempool_destroy(bm->vdata.pool);
201         if (bm->edata.totlayer) BLI_mempool_destroy(bm->edata.pool);
202         if (bm->ldata.totlayer) BLI_mempool_destroy(bm->ldata.pool);
203         if (bm->pdata.totlayer) BLI_mempool_destroy(bm->pdata.pool);
204
205         /* free custom data */
206         CustomData_free(&bm->vdata, 0);
207         CustomData_free(&bm->edata, 0);
208         CustomData_free(&bm->ldata, 0);
209         CustomData_free(&bm->pdata, 0);
210
211         /* destroy element pools */
212         BLI_mempool_destroy(bm->vpool);
213         BLI_mempool_destroy(bm->epool);
214         BLI_mempool_destroy(bm->lpool);
215         BLI_mempool_destroy(bm->fpool);
216
217         if (bm->vtable) MEM_freeN(bm->vtable);
218         if (bm->etable) MEM_freeN(bm->etable);
219         if (bm->ftable) MEM_freeN(bm->ftable);
220
221         /* destroy flag pool */
222         BM_mesh_elem_toolflags_clear(bm);
223
224 #ifdef USE_BMESH_HOLES
225         BLI_mempool_destroy(bm->looplistpool);
226 #endif
227
228         BLI_freelistN(&bm->selected);
229
230         BMO_error_clear(bm);
231 }
232
233 /**
234  * \brief BMesh Clear Mesh
235  *
236  * Clear all data in bm
237  */
238 void BM_mesh_clear(BMesh *bm)
239 {
240         /* free old mesh */
241         BM_mesh_data_free(bm);
242         memset(bm, 0, sizeof(BMesh));
243
244         /* allocate the memory pools for the mesh elements */
245         bm_mempool_init(bm, &bm_mesh_allocsize_default);
246
247         bm->stackdepth = 1;
248         bm->totflags = 0;
249
250         CustomData_reset(&bm->vdata);
251         CustomData_reset(&bm->edata);
252         CustomData_reset(&bm->ldata);
253         CustomData_reset(&bm->pdata);
254 }
255
256 /**
257  * \brief BMesh Free Mesh
258  *
259  *      Frees a BMesh data and its structure.
260  */
261 void BM_mesh_free(BMesh *bm)
262 {
263         BM_mesh_data_free(bm);
264
265         if (bm->py_handle) {
266                 /* keep this out of 'BM_mesh_data_free' because we want python
267                  * to be able to clear the mesh and maintain access. */
268                 bpy_bm_generic_invalidate(bm->py_handle);
269                 bm->py_handle = NULL;
270         }
271
272         MEM_freeN(bm);
273 }
274
275 /**
276  * Helpers for #BM_mesh_normals_update and #BM_verts_calc_normal_vcos
277  */
278 static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const float (*vcos)[3])
279 {
280         BMIter eiter;
281         BMEdge *e;
282         int index;
283
284         if (vcos) {
285                 BM_mesh_elem_index_ensure(bm, BM_VERT);
286         }
287
288         BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, index) {
289                 BM_elem_index_set(e, index); /* set_inline */
290
291                 if (e->l) {
292                         const float *v1_co = vcos ? vcos[BM_elem_index_get(e->v1)] : e->v1->co;
293                         const float *v2_co = vcos ? vcos[BM_elem_index_get(e->v2)] : e->v2->co;
294                         sub_v3_v3v3(edgevec[index], v2_co, v1_co);
295                         normalize_v3(edgevec[index]);
296                 }
297                 else {
298                         /* the edge vector will not be needed when the edge has no radial */
299                 }
300         }
301         bm->elem_index_dirty &= ~BM_EDGE;
302 }
303
304 static void bm_mesh_verts_calc_normals(BMesh *bm, const float (*edgevec)[3], const float (*fnos)[3],
305                                        const float (*vcos)[3], float (*vnos)[3])
306 {
307         BM_mesh_elem_index_ensure(bm, (vnos) ? (BM_EDGE | BM_VERT) : BM_EDGE);
308
309         /* add weighted face normals to vertices */
310         {
311                 BMIter fiter;
312                 BMFace *f;
313                 int i;
314
315                 BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
316                         BMLoop *l_first, *l_iter;
317                         const float *f_no = fnos ? fnos[i] : f->no;
318
319                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
320                         do {
321                                 const float *e1diff, *e2diff;
322                                 float dotprod;
323                                 float fac;
324                                 float *v_no = vnos ? vnos[BM_elem_index_get(l_iter->v)] : l_iter->v->no;
325
326                                 /* calculate the dot product of the two edges that
327                                  * meet at the loop's vertex */
328                                 e1diff = edgevec[BM_elem_index_get(l_iter->prev->e)];
329                                 e2diff = edgevec[BM_elem_index_get(l_iter->e)];
330                                 dotprod = dot_v3v3(e1diff, e2diff);
331
332                                 /* edge vectors are calculated from e->v1 to e->v2, so
333                                  * adjust the dot product if one but not both loops
334                                  * actually runs from from e->v2 to e->v1 */
335                                 if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) {
336                                         dotprod = -dotprod;
337                                 }
338
339                                 fac = saacos(-dotprod);
340
341                                 /* accumulate weighted face normal into the vertex's normal */
342                                 madd_v3_v3fl(v_no, f_no, fac);
343                         } while ((l_iter = l_iter->next) != l_first);
344                 }
345         }
346
347
348         /* normalize the accumulated vertex normals */
349         {
350                 BMIter viter;
351                 BMVert *v;
352                 int i;
353
354                 BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
355                         float *v_no = vnos ? vnos[i] : v->no;
356                         if (UNLIKELY(normalize_v3(v_no) == 0.0f)) {
357                                 const float *v_co = vcos ? vcos[i] : v->co;
358                                 normalize_v3_v3(v_no, v_co);
359                         }
360                 }
361         }
362 }
363
364 /**
365  * \brief BMesh Compute Normals
366  *
367  * Updates the normals of a mesh.
368  */
369 void BM_mesh_normals_update(BMesh *bm)
370 {
371         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
372
373 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
374         {
375 #pragma omp section
376                 {
377                         /* calculate all face normals */
378                         BMIter fiter;
379                         BMFace *f;
380                         int i;
381
382                         BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
383                                 BM_elem_index_set(f, i); /* set_inline */
384                                 BM_face_normal_update(f);
385                         }
386                         bm->elem_index_dirty &= ~BM_FACE;
387                 }
388 #pragma omp section
389                 {
390                         /* Zero out vertex normals */
391                         BMIter viter;
392                         BMVert *v;
393                         int i;
394
395                         BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
396                                 BM_elem_index_set(v, i); /* set_inline */
397                                 zero_v3(v->no);
398                         }
399                         bm->elem_index_dirty &= ~BM_VERT;
400                 }
401 #pragma omp section
402                 {
403                         /* Compute normalized direction vectors for each edge.
404                          * Directions will be used for calculating the weights of the face normals on the vertex normals.
405                          */
406                         bm_mesh_edges_calc_vectors(bm, edgevec, NULL);
407                 }
408         }
409         /* end omp */
410
411         /* Add weighted face normals to vertices, and normalize vert normals. */
412         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, NULL, NULL, NULL);
413         MEM_freeN(edgevec);
414 }
415
416 /**
417  * \brief BMesh Compute Normals from/to external data.
418  *
419  * Computes the vertex normals of a mesh into vnos, using given vertex coordinates (vcos) and polygon normals (fnos).
420  */
421 void BM_verts_calc_normal_vcos(BMesh *bm, const float (*fnos)[3], const float (*vcos)[3], float (*vnos)[3])
422 {
423         float (*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__);
424
425         /* Compute normalized direction vectors for each edge.
426          * Directions will be used for calculating the weights of the face normals on the vertex normals.
427          */
428         bm_mesh_edges_calc_vectors(bm, edgevec, vcos);
429
430         /* Add weighted face normals to vertices, and normalize vert normals. */
431         bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, fnos, vcos, vnos);
432         MEM_freeN(edgevec);
433 }
434
435 /**
436  * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normals_vnos
437  */
438 static void bm_mesh_edges_sharp_tag(BMesh *bm, const float (*vnos)[3], const float (*fnos)[3], float split_angle,
439                                     float (*r_lnos)[3])
440 {
441         BMIter eiter;
442         BMEdge *e;
443         int i;
444
445         const bool check_angle = (split_angle < (float)M_PI);
446
447         if (check_angle) {
448                 split_angle = cosf(split_angle);
449         }
450
451         {
452                 char hflag = BM_LOOP;
453                 if (vnos)
454                         hflag |= BM_VERT;
455                 if (fnos)
456                         hflag |= BM_FACE;
457                 BM_mesh_elem_index_ensure(bm, hflag);
458         }
459
460         /* This first loop checks which edges are actually smooth, and pre-populate lnos with vnos (as if they were
461          * all smooth).
462          */
463         BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
464                 BMLoop *l_a, *l_b;
465
466                 BM_elem_index_set(e, i); /* set_inline */
467                 BM_elem_flag_disable(e, BM_ELEM_TAG); /* Clear tag (means edge is sharp). */
468
469                 /* An edge with only two loops, might be smooth... */
470                 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
471                         bool is_angle_smooth = true;
472                         if (check_angle) {
473                                 const float *no_a = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_a->f->no;
474                                 const float *no_b = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_b->f->no;
475                                 is_angle_smooth = (dot_v3v3(no_a, no_b) >= split_angle);
476                         }
477
478                         /* We only tag edges that are *really* smooth... */
479                         if (is_angle_smooth &&
480                             BM_elem_flag_test_bool(e, BM_ELEM_SMOOTH) &&
481                             BM_elem_flag_test_bool(l_a->f, BM_ELEM_SMOOTH) &&
482                             BM_elem_flag_test_bool(l_b->f, BM_ELEM_SMOOTH))
483                         {
484                                 const float *no;
485                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
486
487                                 /* linked vertices might be fully smooth, copy their normals to loop ones. */
488                                 no = vnos ? vnos[BM_elem_index_get(l_a->v)] : l_a->v->no;
489                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_a)], no);
490                                 no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no;
491                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no);
492                         }
493                 }
494         }
495
496         bm->elem_index_dirty &= ~BM_EDGE;
497 }
498
499 /* BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c */
500 static void bm_mesh_loops_calc_normals(BMesh *bm, const float (*vcos)[3], const float (*fnos)[3], float (*r_lnos)[3])
501 {
502         BMIter fiter;
503         BMFace *f_curr;
504
505         /* Temp normal stack. */
506         BLI_SMALLSTACK_DECLARE(normal, float *);
507
508         {
509                 char hflag = BM_LOOP;
510                 if (vcos)
511                         hflag |= BM_VERT;
512                 if (fnos)
513                         hflag |= BM_FACE;
514                 BM_mesh_elem_index_ensure(bm, hflag);
515         }
516
517         /* We now know edges that can be smoothed (they are tagged), and edges that will be hard (they aren't).
518          * Now, time to generate the normals.
519          */
520         BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) {
521                 BMLoop *l_curr, *l_first;
522
523                 l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr);
524                 do {
525                         if (BM_elem_flag_test_bool(l_curr->e, BM_ELEM_TAG)) {
526                                 /* A smooth edge.
527                                  * We skip it because it is either:
528                                  * - in the middle of a 'smooth fan' already computed (or that will be as soon as we hit
529                                  *   one of its ends, i.e. one of its two sharp edges), or...
530                                  * - the related vertex is a "full smooth" one, in which case pre-populated normals from vertex
531                                  *   are just fine!
532                                  */
533                         }
534                         else if (!BM_elem_flag_test_bool(l_curr->prev->e, BM_ELEM_TAG)) {
535                                 /* Simple case (both edges around that vertex are sharp in related polygon),
536                                  * this vertex just takes its poly normal.
537                                  */
538                                 const float *no = fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no;
539                                 copy_v3_v3(r_lnos[BM_elem_index_get(l_curr)], no);
540                         }
541                         else {
542                                 /* We have to fan around current vertex, until we find the other non-smooth edge,
543                                  * and accumulate face normals into the vertex!
544                                  * Note in case this vertex has only one sharp edge, this is a waste because the normal is the same as
545                                  * the vertex normal, but I do not see any easy way to detect that (would need to count number
546                                  * of sharp edges per vertex, I doubt the additional memory usage would be worth it, especially as
547                                  * it should not be a common case in real-life meshes anyway).
548                                  */
549                                 BMVert *v_pivot = l_curr->v;
550                                 BMEdge *e_next;
551                                 BMLoop *lfan_pivot, *lfan_pivot_next;
552                                 float lnor[3] = {0.0f, 0.0f, 0.0f};
553                                 float vec_curr[3], vec_next[3];
554
555                                 const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co;
556
557                                 lfan_pivot = l_curr;
558                                 e_next = lfan_pivot->e;  /* Current edge here, actually! */
559
560                                 /* Only need to compute previous edge's vector once, then we can just reuse old current one! */
561                                 {
562                                         const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
563                                         const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
564
565                                         sub_v3_v3v3(vec_curr, co_2, co_pivot);
566                                         normalize_v3(vec_curr);
567                                 }
568
569                                 while (true) {
570                                         /* Much simpler than in sibling code with basic Mesh data! */
571                                         lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot, &e_next);
572                                         BLI_assert(lfan_pivot_next->v == v_pivot);
573
574                                         /* Compute edge vector.
575                                          * NOTE: We could pre-compute those into an array, in the first iteration, instead of computing them
576                                          *       twice (or more) here. However, time gained is not worth memory and time lost,
577                                          *       given the fact that this code should not be called that much in real-life meshes...
578                                          */
579                                         {
580                                                 const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot);
581                                                 const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co;
582
583                                                 sub_v3_v3v3(vec_next, co_2, co_pivot);
584                                                 normalize_v3(vec_next);
585                                         }
586
587                                         {
588                                                 /* Code similar to accumulate_vertex_normals_poly. */
589                                                 /* Calculate angle between the two poly edges incident on this vertex. */
590                                                 const BMFace *f = lfan_pivot->f;
591                                                 const float fac = saacos(dot_v3v3(vec_next, vec_curr));
592                                                 const float *no = fnos ? fnos[BM_elem_index_get(f)] : f->no;
593                                                 /* Accumulate */
594                                                 madd_v3_v3fl(lnor, no, fac);
595                                         }
596
597                                         /* We store here a pointer to all loop-normals processed. */
598                                         BLI_SMALLSTACK_PUSH(normal, (float *)r_lnos[BM_elem_index_get(lfan_pivot)]);
599
600                                         if (!BM_elem_flag_test_bool(e_next, BM_ELEM_TAG)) {
601                                                 /* Next edge is sharp, we have finished with this fan of faces around this vert! */
602                                                 break;
603                                         }
604
605                                         /* Copy next edge vector to current one. */
606                                         copy_v3_v3(vec_curr, vec_next);
607                                         /* Next pivot loop to current one. */
608                                         lfan_pivot = lfan_pivot_next;
609                                 }
610
611                                 /* In case we get a zero normal here, just use vertex normal already set! */
612                                 if (LIKELY(normalize_v3(lnor) != 0.0f)) {
613                                         /* Copy back the final computed normal into all related loop-normals. */
614                                         float *nor;
615                                         while ((nor = BLI_SMALLSTACK_POP(normal))) {
616                                                 copy_v3_v3(nor, lnor);
617                                         }
618                                 }
619                         }
620                 } while ((l_curr = l_curr->next) != l_first);
621         }
622
623         BLI_SMALLSTACK_FREE(normal);
624 }
625
626 #if 0  /* Unused currently */
627 /**
628  * \brief BMesh Compute Loop Normals
629  *
630  * Updates the loop normals of a mesh. Assumes vertex and face normals are valid (else call BM_mesh_normals_update()
631  * first)!
632  */
633 void BM_mesh_loop_normals_update(BMesh *bm, const float split_angle, float (*r_lnos)[3])
634 {
635         /* Tag smooth edges and set lnos from vnos when they might be completely smooth... */
636         bm_mesh_edges_sharp_tag(bm, NULL, NULL, split_angle, r_lnos);
637
638         /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
639         bm_mesh_loops_calc_normals(bm, NULL, NULL, r_lnos);
640 }
641 #endif
642
643 /**
644  * \brief BMesh Compute Loop Normals from/to external data.
645  *
646  * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals').
647  * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry (splitting edges).
648  */
649 void BM_loops_calc_normal_vcos(BMesh *bm, const float (*vcos)[3], const float (*vnos)[3], const float (*fnos)[3],
650                                 const float split_angle, float (*r_lnos)[3])
651 {
652         /* Tag smooth edges and set lnos from vnos when they might be completely smooth... */
653         bm_mesh_edges_sharp_tag(bm, vnos, fnos, split_angle, r_lnos);
654
655         /* Finish computing lnos by accumulating face normals in each fan of faces defined by sharp edges. */
656         bm_mesh_loops_calc_normals(bm, vcos, fnos, r_lnos);
657 }
658
659 static void UNUSED_FUNCTION(bm_mdisps_space_set)(Object *ob, BMesh *bm, int from, int to)
660 {
661         /* switch multires data out of tangent space */
662         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
663                 BMEditMesh *em = BKE_editmesh_create(bm, false);
664                 DerivedMesh *dm = CDDM_from_editbmesh(em, true, false);
665                 MDisps *mdisps;
666                 BMFace *f;
667                 BMIter iter;
668                 // int i = 0; // UNUSED
669                 
670                 multires_set_space(dm, ob, from, to);
671                 
672                 mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
673                 
674                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
675                         BMLoop *l;
676                         BMIter liter;
677                         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
678                                 MDisps *lmd = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MDISPS);
679                                 
680                                 if (!lmd->disps) {
681                                         printf("%s: warning - 'lmd->disps' == NULL\n", __func__);
682                                 }
683                                 
684                                 if (lmd->disps && lmd->totdisp == mdisps->totdisp) {
685                                         memcpy(lmd->disps, mdisps->disps, sizeof(float) * 3 * lmd->totdisp);
686                                 }
687                                 else if (mdisps->disps) {
688                                         if (lmd->disps)
689                                                 MEM_freeN(lmd->disps);
690                                         
691                                         lmd->disps = MEM_dupallocN(mdisps->disps);
692                                         lmd->totdisp = mdisps->totdisp;
693                                         lmd->level = mdisps->level;
694                                 }
695                                 
696                                 mdisps++;
697                                 // i += 1;
698                         }
699                 }
700                 
701                 dm->needsFree = 1;
702                 dm->release(dm);
703                 
704                 /* setting this to NULL prevents BKE_editmesh_free from freeing it */
705                 em->bm = NULL;
706                 BKE_editmesh_free(em);
707                 MEM_freeN(em);
708         }
709 }
710
711 /**
712  * \brief BMesh Begin Edit
713  *
714  * Functions for setting up a mesh for editing and cleaning up after
715  * the editing operations are done. These are called by the tools/operator
716  * API for each time a tool is executed.
717  */
718 void bmesh_edit_begin(BMesh *UNUSED(bm), BMOpTypeFlag UNUSED(type_flag))
719 {
720         /* Most operators seem to be using BMO_OPTYPE_FLAG_UNTAN_MULTIRES to change the MDisps to
721          * absolute space during mesh edits. With this enabled, changes to the topology
722          * (loop cuts, edge subdivides, etc) are not reflected in the higher levels of
723          * the mesh at all, which doesn't seem right. Turning off completely for now,
724          * until this is shown to be better for certain types of mesh edits. */
725 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
726         /* switch multires data out of tangent space */
727         if ((type_flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
728                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_TANGENT, MULTIRES_SPACE_ABSOLUTE);
729
730                 /* ensure correct normals, if possible */
731                 bmesh_rationalize_normals(bm, 0);
732                 BM_mesh_normals_update(bm);
733         }
734 #endif
735 }
736
737 /**
738  * \brief BMesh End Edit
739  */
740 void bmesh_edit_end(BMesh *bm, BMOpTypeFlag type_flag)
741 {
742         /* BMO_OPTYPE_FLAG_UNTAN_MULTIRES disabled for now, see comment above in bmesh_edit_begin. */
743 #ifdef BMOP_UNTAN_MULTIRES_ENABLED
744         /* switch multires data into tangent space */
745         if ((flag & BMO_OPTYPE_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
746                 /* set normals to their previous winding */
747                 bmesh_rationalize_normals(bm, 1);
748                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
749         }
750         else if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
751                 bmesh_rationalize_normals(bm, 1);
752         }
753 #endif
754
755         /* compute normals, clear temp flags and flush selections */
756         if (type_flag & BMO_OPTYPE_FLAG_NORMALS_CALC) {
757                 BM_mesh_normals_update(bm);
758         }
759
760         if (type_flag & BMO_OPTYPE_FLAG_SELECT_FLUSH) {
761                 BM_mesh_select_mode_flush(bm);
762         }
763 }
764
765 void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag)
766 {
767 #ifdef DEBUG
768         BM_ELEM_INDEX_VALIDATE(bm, "Should Never Fail!", __func__);
769 #endif
770
771 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
772         {
773 #pragma omp section
774                 {
775                         if (hflag & BM_VERT) {
776                                 if (bm->elem_index_dirty & BM_VERT) {
777                                         BMIter iter;
778                                         BMElem *ele;
779
780                                         int index;
781                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, index) {
782                                                 BM_elem_index_set(ele, index); /* set_ok */
783                                         }
784                                         BLI_assert(index == bm->totvert);
785                                 }
786                                 else {
787                                         // printf("%s: skipping vert index calc!\n", __func__);
788                                 }
789                         }
790                 }
791
792 #pragma omp section
793                 {
794                         if (hflag & BM_EDGE) {
795                                 if (bm->elem_index_dirty & BM_EDGE) {
796                                         BMIter iter;
797                                         BMElem *ele;
798
799                                         int index;
800                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, index) {
801                                                 BM_elem_index_set(ele, index); /* set_ok */
802                                         }
803                                         BLI_assert(index == bm->totedge);
804                                 }
805                                 else {
806                                         // printf("%s: skipping edge index calc!\n", __func__);
807                                 }
808                         }
809                 }
810
811 #pragma omp section
812                 {
813                         if (hflag & (BM_FACE | BM_LOOP)) {
814                                 if (bm->elem_index_dirty & (BM_FACE | BM_LOOP)) {
815                                         BMIter iter;
816                                         BMElem *ele;
817
818                                         const bool hflag_loop = (hflag & BM_LOOP) && (bm->elem_index_dirty & BM_LOOP);
819
820                                         int index;
821                                         int index_loop_start = 0;
822                                         BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, index) {
823                                                 BM_elem_index_set(ele, index); /* set_ok */
824
825                                                 if (hflag_loop) {
826                                                         BMIter liter;
827                                                         BMElem *lele;
828
829                                                         int index_diff;
830                                                         BM_ITER_ELEM_INDEX (lele, &liter, ele, BM_LOOPS_OF_FACE, index_diff) {
831                                                                 BM_elem_index_set(lele, index_loop_start + index_diff); /* set_ok */
832                                                         }
833                                                         index_loop_start += index_diff;
834                                                 }
835                                         }
836                                         BLI_assert(index == bm->totface);
837                                         if (hflag & BM_LOOP)
838                                                 BLI_assert(index_loop_start == bm->totloop);
839                                 }
840                                 else {
841                                         // printf("%s: skipping face/loop index calc!\n", __func__);
842                                 }
843                         }
844                 }
845         }
846
847         bm->elem_index_dirty &= ~hflag;
848 }
849
850
851 /**
852  * Array checking/setting macros
853  *
854  * Currently vert/edge/loop/face index data is being abused, in a few areas of the code.
855  *
856  * To avoid correcting them afterwards, set 'bm->elem_index_dirty' however its possible
857  * this flag is set incorrectly which could crash blender.
858  *
859  * These functions ensure its correct and are called more often in debug mode.
860  */
861
862 void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func,
863                                  const char *msg_a, const char *msg_b)
864 {
865         const char iter_types[3] = {BM_VERTS_OF_MESH,
866                                     BM_EDGES_OF_MESH,
867                                     BM_FACES_OF_MESH};
868
869         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
870         const char *type_names[3] = {"vert", "edge", "face"};
871
872         BMIter iter;
873         BMElem *ele;
874         int i;
875         bool is_any_error = 0;
876
877         for (i = 0; i < 3; i++) {
878                 const bool is_dirty = (flag_types[i] & bm->elem_index_dirty) != 0;
879                 int index = 0;
880                 bool is_error = false;
881                 int err_val = 0;
882                 int err_idx = 0;
883
884                 BM_ITER_MESH (ele, &iter, bm, iter_types[i]) {
885                         if (!is_dirty) {
886                                 if (BM_elem_index_get(ele) != index) {
887                                         err_val = BM_elem_index_get(ele);
888                                         err_idx = index;
889                                         is_error = true;
890                                 }
891                         }
892
893                         BM_elem_index_set(ele, index); /* set_ok */
894                         index++;
895                 }
896
897                 if ((is_error == true) && (is_dirty == false)) {
898                         is_any_error = true;
899                         fprintf(stderr,
900                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
901                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
902                 }
903                 else if ((is_error == false) && (is_dirty == true)) {
904
905 #if 0       /* mostly annoying */
906
907                         /* dirty may have been incorrectly set */
908                         fprintf(stderr,
909                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
910                                 location, func, type_names[i], msg_a, msg_b);
911 #endif
912                 }
913         }
914
915 #if 0 /* mostly annoying, even in debug mode */
916 #ifdef DEBUG
917         if (is_any_error == 0) {
918                 fprintf(stderr,
919                         "Valid Index Success: at %s, %s, '%s', '%s'\n",
920                         location, func, msg_a, msg_b);
921         }
922 #endif
923 #endif
924         (void) is_any_error; /* shut up the compiler */
925
926 }
927
928 /* debug check only - no need to optimize */
929 #ifndef NDEBUG
930 bool BM_mesh_elem_table_check(BMesh *bm)
931 {
932         BMIter iter;
933         BMElem *ele;
934         int i;
935
936         if (bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) {
937                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_VERTS_OF_MESH, i) {
938                         if (ele != (BMElem *)bm->vtable[i]) {
939                                 return false;
940                         }
941                 }
942         }
943
944         if (bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) {
945                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_EDGES_OF_MESH, i) {
946                         if (ele != (BMElem *)bm->etable[i]) {
947                                 return false;
948                         }
949                 }
950         }
951
952         if (bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) {
953                 BM_ITER_MESH_INDEX (ele, &iter, bm, BM_FACES_OF_MESH, i) {
954                         if (ele != (BMElem *)bm->ftable[i]) {
955                                 return false;
956                         }
957                 }
958         }
959
960         return true;
961 }
962 #endif
963
964
965
966 void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
967 {
968         /* assume if the array is non-null then its valid and no need to recalc */
969         const char htype_needed = (((bm->vtable && ((bm->elem_table_dirty & BM_VERT) == 0)) ? 0 : BM_VERT) |
970                                    ((bm->etable && ((bm->elem_table_dirty & BM_EDGE) == 0)) ? 0 : BM_EDGE) |
971                                    ((bm->ftable && ((bm->elem_table_dirty & BM_FACE) == 0)) ? 0 : BM_FACE)) & htype;
972
973         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
974
975         /* in debug mode double check we didn't need to recalculate */
976         BLI_assert(BM_mesh_elem_table_check(bm) == true);
977
978         if (htype_needed & BM_VERT) {
979                 if (bm->vtable && bm->totvert <= bm->vtable_tot && bm->totvert * 2 >= bm->vtable_tot) {
980                         /* pass (re-use the array) */
981                 }
982                 else {
983                         if (bm->vtable)
984                                 MEM_freeN(bm->vtable);
985                         bm->vtable = MEM_mallocN(sizeof(void **) * bm->totvert, "bm->vtable");
986                         bm->vtable_tot = bm->totvert;
987                 }
988         }
989         if (htype_needed & BM_EDGE) {
990                 if (bm->etable && bm->totedge <= bm->etable_tot && bm->totedge * 2 >= bm->etable_tot) {
991                         /* pass (re-use the array) */
992                 }
993                 else {
994                         if (bm->etable)
995                                 MEM_freeN(bm->etable);
996                         bm->etable = MEM_mallocN(sizeof(void **) * bm->totedge, "bm->etable");
997                         bm->etable_tot = bm->totedge;
998                 }
999         }
1000         if (htype_needed & BM_FACE) {
1001                 if (bm->ftable && bm->totface <= bm->ftable_tot && bm->totface * 2 >= bm->ftable_tot) {
1002                         /* pass (re-use the array) */
1003                 }
1004                 else {
1005                         if (bm->ftable)
1006                                 MEM_freeN(bm->ftable);
1007                         bm->ftable = MEM_mallocN(sizeof(void **) * bm->totface, "bm->ftable");
1008                         bm->ftable_tot = bm->totface;
1009                 }
1010         }
1011
1012 #pragma omp parallel sections if (bm->totvert + bm->totedge + bm->totface >= BM_OMP_LIMIT)
1013         {
1014 #pragma omp section
1015                 {
1016                         if (htype_needed & BM_VERT) {
1017                                 BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)bm->vtable, bm->totvert);
1018                         }
1019                 }
1020 #pragma omp section
1021                 {
1022                         if (htype_needed & BM_EDGE) {
1023                                 BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)bm->etable, bm->totedge);
1024                         }
1025                 }
1026 #pragma omp section
1027                 {
1028                         if (htype_needed & BM_FACE) {
1029                                 BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)bm->ftable, bm->totface);
1030                         }
1031                 }
1032         }
1033
1034         /* Only clear dirty flags when all the pointers and data are actually valid.
1035          * This prevents possible threading issues when dirty flag check failed but
1036          * data wasn't ready still.
1037          */
1038         if (htype_needed & BM_VERT) {
1039                 bm->elem_table_dirty &= ~BM_VERT;
1040         }
1041         if (htype_needed & BM_EDGE) {
1042                 bm->elem_table_dirty &= ~BM_EDGE;
1043         }
1044         if (htype_needed & BM_FACE) {
1045                 bm->elem_table_dirty &= ~BM_FACE;
1046         }
1047 }
1048
1049 /* use BM_mesh_elem_table_ensure where possible to avoid full rebuild */
1050 void BM_mesh_elem_table_init(BMesh *bm, const char htype)
1051 {
1052         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1053
1054         /* force recalc */
1055         BM_mesh_elem_table_free(bm, BM_ALL_NOLOOP);
1056         BM_mesh_elem_table_ensure(bm, htype);
1057 }
1058
1059 void BM_mesh_elem_table_free(BMesh *bm, const char htype)
1060 {
1061         if (htype & BM_VERT) {
1062                 MEM_SAFE_FREE(bm->vtable);
1063         }
1064
1065         if (htype & BM_EDGE) {
1066                 MEM_SAFE_FREE(bm->etable);
1067         }
1068
1069         if (htype & BM_FACE) {
1070                 MEM_SAFE_FREE(bm->ftable);
1071         }
1072 }
1073
1074 BMVert *BM_vert_at_index(BMesh *bm, const int index)
1075 {
1076         BLI_assert((index >= 0) && (index < bm->totvert));
1077         BLI_assert((bm->elem_table_dirty & BM_VERT) == 0);
1078         return bm->vtable[index];
1079 }
1080
1081 BMEdge *BM_edge_at_index(BMesh *bm, const int index)
1082 {
1083         BLI_assert((index >= 0) && (index < bm->totedge));
1084         BLI_assert((bm->elem_table_dirty & BM_EDGE) == 0);
1085         return bm->etable[index];
1086 }
1087
1088 BMFace *BM_face_at_index(BMesh *bm, const int index)
1089 {
1090         BLI_assert((index >= 0) && (index < bm->totface));
1091         BLI_assert((bm->elem_table_dirty & BM_FACE) == 0);
1092         return bm->ftable[index];
1093 }
1094
1095
1096 BMVert *BM_vert_at_index_find(BMesh *bm, const int index)
1097 {
1098         return BLI_mempool_findelem(bm->vpool, index);
1099 }
1100
1101 BMEdge *BM_edge_at_index_find(BMesh *bm, const int index)
1102 {
1103         return BLI_mempool_findelem(bm->epool, index);
1104 }
1105
1106 BMFace *BM_face_at_index_find(BMesh *bm, const int index)
1107 {
1108         return BLI_mempool_findelem(bm->fpool, index);
1109 }
1110
1111
1112 /**
1113  * Return the amount of element of type 'type' in a given bmesh.
1114  */
1115 int BM_mesh_elem_count(BMesh *bm, const char htype)
1116 {
1117         BLI_assert((htype & ~BM_ALL_NOLOOP) == 0);
1118
1119         switch (htype) {
1120                 case BM_VERT: return bm->totvert;
1121                 case BM_EDGE: return bm->totedge;
1122                 case BM_FACE: return bm->totface;
1123                 default:
1124                 {
1125                         BLI_assert(0);
1126                         return 0;
1127                 }
1128         }
1129 }
1130
1131 /**
1132  * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays
1133  * (xxx_idx[org_index] = new_index).
1134  *
1135  * A NULL array means no changes.
1136  *
1137  * Note: - Does not mess with indices, just sets elem_index_dirty flag.
1138  *       - For verts/edges/faces only (as loops must remain "ordered" and "aligned"
1139  *         on a per-face basis...).
1140  *
1141  * WARNING: Be careful if you keep pointers to affected BM elements, or arrays, when using this func!
1142  */
1143 void BM_mesh_remap(BMesh *bm, unsigned int *vert_idx, unsigned int *edge_idx, unsigned int *face_idx)
1144 {
1145         /* Mapping old to new pointers. */
1146         GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL;
1147         BMIter iter, iterl;
1148         BMVert *ve;
1149         BMEdge *ed;
1150         BMFace *fa;
1151         BMLoop *lo;
1152
1153         if (!(vert_idx || edge_idx || face_idx))
1154                 return;
1155
1156         /* Remap Verts */
1157         if (vert_idx) {
1158                 BMVert **verts_pool, *verts_copy, **vep;
1159                 int i, totvert = bm->totvert;
1160                 unsigned int *new_idx = NULL;
1161
1162                 /* Init the old-to-new vert pointers mapping */
1163                 vptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap vert pointers mapping", bm->totvert);
1164
1165                 /* Make a copy of all vertices. */
1166                 verts_pool = MEM_callocN(sizeof(BMVert *) * totvert, "BM_mesh_remap verts pool");
1167                 BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void **)verts_pool, totvert);
1168                 verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy");
1169                 for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) {
1170                         *ve = **vep;
1171 /*                      printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/
1172                 }
1173
1174                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1175                 new_idx = vert_idx + totvert - 1;
1176                 ve = verts_copy + totvert - 1;
1177                 vep = verts_pool + totvert - 1; /* old, org pointer */
1178                 for (i = totvert; i--; new_idx--, ve--, vep--) {
1179                         BMVert *new_vep = verts_pool[*new_idx];
1180                         *new_vep = *ve;
1181 /*                      printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/
1182                         BLI_ghash_insert(vptr_map, (void *)*vep, (void *)new_vep);
1183                 }
1184                 bm->elem_index_dirty |= BM_VERT;
1185
1186                 MEM_freeN(verts_pool);
1187                 MEM_freeN(verts_copy);
1188         }
1189
1190         /* Remap Edges */
1191         if (edge_idx) {
1192                 BMEdge **edges_pool, *edges_copy, **edp;
1193                 int i, totedge = bm->totedge;
1194                 unsigned int *new_idx = NULL;
1195
1196                 /* Init the old-to-new vert pointers mapping */
1197                 eptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap edge pointers mapping", bm->totedge);
1198
1199                 /* Make a copy of all vertices. */
1200                 edges_pool = MEM_callocN(sizeof(BMEdge *) * totedge, "BM_mesh_remap edges pool");
1201                 BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void **)edges_pool, totedge);
1202                 edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy");
1203                 for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) {
1204                         *ed = **edp;
1205                 }
1206
1207                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1208                 new_idx = edge_idx + totedge - 1;
1209                 ed = edges_copy + totedge - 1;
1210                 edp = edges_pool + totedge - 1; /* old, org pointer */
1211                 for (i = totedge; i--; new_idx--, ed--, edp--) {
1212                         BMEdge *new_edp = edges_pool[*new_idx];
1213                         *new_edp = *ed;
1214                         BLI_ghash_insert(eptr_map, (void *)*edp, (void *)new_edp);
1215 /*                      printf("mapping edge from %d to %d (%p/%p to %p)\n", i, *new_idx, *edp, edges_pool[i], new_edp);*/
1216                 }
1217                 bm->elem_index_dirty |= BM_EDGE;
1218
1219                 MEM_freeN(edges_pool);
1220                 MEM_freeN(edges_copy);
1221         }
1222
1223         /* Remap Faces */
1224         if (face_idx) {
1225                 BMFace **faces_pool, *faces_copy, **fap;
1226                 int i, totface = bm->totface;
1227                 unsigned int *new_idx = NULL;
1228
1229                 /* Init the old-to-new vert pointers mapping */
1230                 fptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap face pointers mapping", bm->totface);
1231
1232                 /* Make a copy of all vertices. */
1233                 faces_pool = MEM_callocN(sizeof(BMFace *) * totface, "BM_mesh_remap faces pool");
1234                 BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void **)faces_pool, totface);
1235                 faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy");
1236                 for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) {
1237                         *fa = **fap;
1238                 }
1239
1240                 /* Copy back verts to their new place, and update old2new pointers mapping. */
1241                 new_idx = face_idx + totface - 1;
1242                 fa = faces_copy + totface - 1;
1243                 fap = faces_pool + totface - 1; /* old, org pointer */
1244                 for (i = totface; i--; new_idx--, fa--, fap--) {
1245                         BMFace *new_fap = faces_pool[*new_idx];
1246                         *new_fap = *fa;
1247                         BLI_ghash_insert(fptr_map, (void *)*fap, (void *)new_fap);
1248                 }
1249
1250                 bm->elem_index_dirty |= BM_FACE | BM_LOOP;
1251
1252                 MEM_freeN(faces_pool);
1253                 MEM_freeN(faces_copy);
1254         }
1255
1256         /* And now, fix all vertices/edges/faces/loops pointers! */
1257         /* Verts' pointers, only edge pointers... */
1258         if (eptr_map) {
1259                 BM_ITER_MESH (ve, &iter, bm, BM_VERTS_OF_MESH) {
1260 /*                      printf("Vert e: %p -> %p\n", ve->e, BLI_ghash_lookup(eptr_map, (const void *)ve->e));*/
1261                         ve->e = BLI_ghash_lookup(eptr_map, (const void *)ve->e);
1262                 }
1263         }
1264
1265         /* Edges' pointers, only vert pointers (as we don't mess with loops!), and - ack! - edge pointers,
1266          * as we have to handle disklinks... */
1267         if (vptr_map || eptr_map) {
1268                 BM_ITER_MESH (ed, &iter, bm, BM_EDGES_OF_MESH) {
1269                         if (vptr_map) {
1270 /*                              printf("Edge v1: %p -> %p\n", ed->v1, BLI_ghash_lookup(vptr_map, (const void *)ed->v1));*/
1271 /*                              printf("Edge v2: %p -> %p\n", ed->v2, BLI_ghash_lookup(vptr_map, (const void *)ed->v2));*/
1272                                 ed->v1 = BLI_ghash_lookup(vptr_map, (const void *)ed->v1);
1273                                 ed->v2 = BLI_ghash_lookup(vptr_map, (const void *)ed->v2);
1274                         }
1275                         if (eptr_map) {
1276 /*                              printf("Edge v1_disk_link prev: %p -> %p\n", ed->v1_disk_link.prev,*/
1277 /*                                     BLI_ghash_lookup(eptr_map, (const void *)ed->v1_disk_link.prev));*/
1278 /*                              printf("Edge v1_disk_link next: %p -> %p\n", ed->v1_disk_link.next,*/
1279 /*                                     BLI_ghash_lookup(eptr_map, (const void *)ed->v1_disk_link.next));*/
1280 /*                              printf("Edge v2_disk_link prev: %p -> %p\n", ed->v2_disk_link.prev,*/
1281 /*                                     BLI_ghash_lookup(eptr_map, (const void *)ed->v2_disk_link.prev));*/
1282 /*                              printf("Edge v2_disk_link next: %p -> %p\n", ed->v2_disk_link.next,*/
1283 /*                                     BLI_ghash_lookup(eptr_map, (const void *)ed->v2_disk_link.next));*/
1284                                 ed->v1_disk_link.prev = BLI_ghash_lookup(eptr_map, (const void *)ed->v1_disk_link.prev);
1285                                 ed->v1_disk_link.next = BLI_ghash_lookup(eptr_map, (const void *)ed->v1_disk_link.next);
1286                                 ed->v2_disk_link.prev = BLI_ghash_lookup(eptr_map, (const void *)ed->v2_disk_link.prev);
1287                                 ed->v2_disk_link.next = BLI_ghash_lookup(eptr_map, (const void *)ed->v2_disk_link.next);
1288                         }
1289                 }
1290         }
1291
1292         /* Faces' pointers (loops, in fact), always needed... */
1293         BM_ITER_MESH (fa, &iter, bm, BM_FACES_OF_MESH) {
1294                 BM_ITER_ELEM (lo, &iterl, fa, BM_LOOPS_OF_FACE) {
1295                         if (vptr_map) {
1296 /*                              printf("Loop v: %p -> %p\n", lo->v, BLI_ghash_lookup(vptr_map, (const void *)lo->v));*/
1297                                 lo->v = BLI_ghash_lookup(vptr_map, (const void *)lo->v);
1298                         }
1299                         if (eptr_map) {
1300 /*                              printf("Loop e: %p -> %p\n", lo->e, BLI_ghash_lookup(eptr_map, (const void *)lo->e));*/
1301                                 lo->e = BLI_ghash_lookup(eptr_map, (const void *)lo->e);
1302                         }
1303                         if (fptr_map) {
1304 /*                              printf("Loop f: %p -> %p\n", lo->f, BLI_ghash_lookup(fptr_map, (const void *)lo->f));*/
1305                                 lo->f = BLI_ghash_lookup(fptr_map, (const void *)lo->f);
1306                         }
1307                 }
1308         }
1309
1310         if (vptr_map)
1311                 BLI_ghash_free(vptr_map, NULL, NULL);
1312         if (eptr_map)
1313                 BLI_ghash_free(eptr_map, NULL, NULL);
1314         if (fptr_map)
1315                 BLI_ghash_free(fptr_map, NULL, NULL);
1316 }