remove cellalloc, from my tests jemalloc beats cellalloc, so we better just use a...
[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_meshdata_types.h"
34 #include "DNA_mesh_types.h"
35
36 #include "BLI_listbase.h"
37 #include "BLI_math.h"
38 #include "BLI_utildefines.h"
39
40 #include "BKE_utildefines.h"
41 #include "BKE_cdderivedmesh.h"
42 #include "BKE_tessmesh.h"
43 #include "BKE_customdata.h"
44 #include "BKE_DerivedMesh.h"
45 #include "BKE_multires.h"
46
47 #include "ED_mesh.h"
48
49 #include "bmesh.h"
50 #include "bmesh_private.h"
51
52 /*bmesh_error stub*/
53 void bmesh_error(void)
54 {
55         printf("BM modelling error!\n");
56
57         /* This placeholder assert makes modelling errors easier to catch
58            in the debugger, until bmesh_error is replaced with something
59            better. */
60         BLI_assert(0);
61 }
62
63 /*
64  *      BMESH MAKE MESH
65  *
66  *  Allocates a new BMesh structure.
67  *  Returns -
68  *  Pointer to a BM
69  *
70 */
71
72 BMesh *BM_Make_Mesh(struct Object *ob, int allocsize[4])
73 {
74         /*allocate the structure*/
75         BMesh *bm = MEM_callocN(sizeof(BMesh),"BM");
76         int vsize, esize, lsize, fsize, lstsize;
77
78         vsize = sizeof(BMVert);
79         esize = sizeof(BMEdge);
80         lsize = sizeof(BMLoop);
81         fsize = sizeof(BMFace);
82         lstsize = sizeof(BMLoopList);
83
84         bm->ob = ob;
85         
86    /*allocate the memory pools for the mesh elements*/
87         bm->vpool = BLI_mempool_create(vsize, allocsize[0], allocsize[0], FALSE, TRUE);
88         bm->epool = BLI_mempool_create(esize, allocsize[1], allocsize[1], FALSE, TRUE);
89         bm->lpool = BLI_mempool_create(lsize, allocsize[2], allocsize[2], FALSE, FALSE);
90         bm->looplistpool = BLI_mempool_create(lstsize, allocsize[3], allocsize[3], FALSE, FALSE);
91         bm->fpool = BLI_mempool_create(fsize, allocsize[3], allocsize[3], FALSE, TRUE);
92
93         /*allocate one flag pool that we dont get rid of.*/
94         bm->toolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), 512, 512, FALSE, FALSE);
95         bm->stackdepth = 1;
96         bm->totflags = 1;
97
98         return bm;
99 }
100
101 /*      
102  *      BMESH FREE MESH
103  *
104  *      Frees a BMesh structure.
105 */
106
107 void BM_Free_Mesh_Data(BMesh *bm)
108 {
109         BMVert *v;
110         BMEdge *e;
111         BMLoop *l;
112         BMFace *f;
113         
114
115         BMIter verts;
116         BMIter edges;
117         BMIter faces;
118         BMIter loops;
119         
120         for(v = BMIter_New(&verts, bm, BM_VERTS_OF_MESH, bm ); v; v = BMIter_Step(&verts)) CustomData_bmesh_free_block( &(bm->vdata), &(v->head.data) );
121         for(e = BMIter_New(&edges, bm, BM_EDGES_OF_MESH, bm ); e; e = BMIter_Step(&edges)) CustomData_bmesh_free_block( &(bm->edata), &(e->head.data) );
122         for(f = BMIter_New(&faces, bm, BM_FACES_OF_MESH, bm ); f; f = BMIter_Step(&faces)) {
123                 CustomData_bmesh_free_block( &(bm->pdata), &(f->head.data) );
124                 for(l = BMIter_New(&loops, bm, BM_LOOPS_OF_FACE, f ); l; l = BMIter_Step(&loops)) CustomData_bmesh_free_block( &(bm->ldata), &(l->head.data) );
125         }
126
127         /*Free custom data pools, This should probably go in CustomData_free?*/
128         if(bm->vdata.totlayer) BLI_mempool_destroy(bm->vdata.pool);
129         if(bm->edata.totlayer) BLI_mempool_destroy(bm->edata.pool);
130         if(bm->ldata.totlayer) BLI_mempool_destroy(bm->ldata.pool);
131         if(bm->pdata.totlayer) BLI_mempool_destroy(bm->pdata.pool);
132
133         /*free custom data*/
134         CustomData_free(&bm->vdata,0);
135         CustomData_free(&bm->edata,0);
136         CustomData_free(&bm->ldata,0);
137         CustomData_free(&bm->pdata,0);
138
139         /*destroy element pools*/
140         BLI_mempool_destroy(bm->vpool);
141         BLI_mempool_destroy(bm->epool);
142         BLI_mempool_destroy(bm->lpool);
143         BLI_mempool_destroy(bm->fpool);
144
145         /*destroy flag pool*/
146         BLI_mempool_destroy(bm->toolflagpool);
147         BLI_mempool_destroy(bm->looplistpool);
148
149         /* These tables aren't used yet, so it's not stricly necessary
150            to 'end' them (with 'e' param) but if someone tries to start
151            using them, having these in place will save a lot of pain */
152         mesh_octree_table(NULL, NULL, NULL, 'e');
153         mesh_mirrtopo_table(NULL, 'e');
154
155         BLI_freelistN(&bm->selected);
156
157         BMO_ClearStack(bm);
158 }
159
160 void BM_Clear_Mesh(BMesh *bm)
161 {
162         /*allocate the structure*/
163         int vsize, esize, lsize, fsize, lstsize;
164         /*I really need to make the allocation sizes defines, there's no reason why the API
165           should allow client code to mess around with this - joeedh*/
166         int allocsize[5] = {512, 512, 512, 2048, 512};
167         Object *ob = bm->ob;
168         
169         /*free old mesh*/
170         BM_Free_Mesh_Data(bm);
171         memset(bm, 0, sizeof(BMesh));
172         
173         /*re-initialize mesh*/
174         vsize = sizeof(BMVert);
175         esize = sizeof(BMEdge);
176         lsize = sizeof(BMLoop);
177         fsize = sizeof(BMFace);
178         lstsize = sizeof(BMLoopList);
179
180         bm->ob = ob;
181         
182    /*allocate the memory pools for the mesh elements*/
183         bm->vpool = BLI_mempool_create(vsize, allocsize[0], allocsize[0], FALSE, TRUE);
184         bm->epool = BLI_mempool_create(esize, allocsize[1], allocsize[1], FALSE, TRUE);
185         bm->lpool = BLI_mempool_create(lsize, allocsize[2], allocsize[2], FALSE, FALSE);
186         bm->looplistpool = BLI_mempool_create(lstsize, allocsize[3], allocsize[3], FALSE, FALSE);
187         bm->fpool = BLI_mempool_create(fsize, allocsize[4], allocsize[4], FALSE, TRUE);
188
189         /*allocate one flag pool that we dont get rid of.*/
190         bm->toolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), 512, 512, FALSE, FALSE);
191         bm->stackdepth = 1;
192         bm->totflags = 1;
193 }
194
195 /*      
196  *      BMESH FREE MESH
197  *
198  *      Frees a BMesh structure.
199 */
200
201 void BM_Free_Mesh(BMesh *bm)
202 {
203         BM_Free_Mesh_Data(bm);
204         MEM_freeN(bm);
205 }
206
207 /*
208  *  BMESH COMPUTE NORMALS
209  *
210  *  Updates the normals of a mesh.
211  *  Note that this can only be called  
212  *
213 */
214
215 void BM_Compute_Normals(BMesh *bm)
216 {
217         BMVert *v;
218         BMFace *f;
219         BMLoop *l;
220         BMEdge *e;
221         BMIter verts;
222         BMIter faces;
223         BMIter loops;
224         BMIter edges;
225         unsigned int maxlength = 0;
226         int index;
227         float (*projectverts)[3];
228         float (*edgevec)[3];
229
230         /*first, find out the largest face in mesh*/
231         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
232                 if (BM_TestHFlag(f, BM_HIDDEN))
233                         continue;
234
235                 if(f->len > maxlength) maxlength = f->len;
236         }
237         
238         /*make sure we actually have something to do*/
239         if(maxlength < 3) return; 
240
241         /*allocate projectverts array*/
242         projectverts = MEM_callocN(sizeof(float) * maxlength * 3, "BM normal computation array");
243         
244         /*calculate all face normals*/
245         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
246                 if (BM_TestHFlag(f, BM_HIDDEN))
247                         continue;
248 #if 0   /* UNUSED */
249                 if (f->head.flag & BM_NONORMCALC)
250                         continue;
251 #endif
252
253                 bmesh_update_face_normal(bm, f, f->no, projectverts);
254         }
255         
256         /*Zero out vertex normals*/
257         BM_ITER(v, &verts, bm, BM_VERTS_OF_MESH, NULL) {
258                 if (BM_TestHFlag(v, BM_HIDDEN))
259                         continue;
260
261                 zero_v3(v->no);
262         }
263
264         /* compute normalized direction vectors for each edge. directions will be
265            used below for calculating the weights of the face normals on the vertex
266            normals */
267         index = 0;
268         edgevec = MEM_callocN(sizeof(float) * 3 * bm->totedge, "BM normal computation array");
269         BM_ITER(e, &edges, bm, BM_EDGES_OF_MESH, NULL) {
270                 BM_SetIndex(e, index); /* set_inline */
271
272                 if (e->l) {
273                         sub_v3_v3v3(edgevec[index], e->v2->co, e->v1->co);
274                         normalize_v3(edgevec[index]);
275                 }
276                 else {
277                         /* the edge vector will not be needed when the edge has no radial */
278                 }
279
280                 index++;
281         }
282         bm->elem_index_dirty &= ~BM_EDGE;
283
284         /*add weighted face normals to vertices*/
285         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
286
287                 if (BM_TestHFlag(f, BM_HIDDEN))
288                         continue;
289
290                 BM_ITER(l, &loops, bm, BM_LOOPS_OF_FACE, f) {
291                         float *e1diff, *e2diff;
292                         float dotprod;
293                         float fac;
294
295                         /* calculate the dot product of the two edges that
296                            meet at the loop's vertex */
297                         e1diff = edgevec[BM_GetIndex(l->prev->e)];
298                         e2diff = edgevec[BM_GetIndex(l->e)];
299                         dotprod = dot_v3v3(e1diff, e2diff);
300
301                         /* edge vectors are calculated from e->v1 to e->v2, so
302                            adjust the dot product if one but not both loops 
303                            actually runs from from e->v2 to e->v1 */
304                         if ((l->prev->e->v1 == l->prev->v) ^ (l->e->v1 == l->v)) {
305                                 dotprod= -dotprod;
306                         }
307
308                         fac = saacos(-dotprod);
309
310                         /* accumulate weighted face normal into the vertex's normal */
311                         madd_v3_v3fl(l->v->no, f->no, fac);
312                 }
313         }
314         
315         /* normalize the accumulated vertex normals */
316         BM_ITER(v, &verts, bm, BM_VERTS_OF_MESH, NULL) {
317                 if (BM_TestHFlag(v, BM_HIDDEN))
318                         continue;
319
320                 if (normalize_v3(v->no) == 0.0f) {
321                         normalize_v3_v3(v->no, v->co);
322                 }
323         }
324         
325         MEM_freeN(edgevec);
326         MEM_freeN(projectverts);
327 }
328
329 /*
330  This function ensures correct normals for the mesh, but
331  sets the flag BM_TMP_TAG in flipped faces, to allow restoration
332  of original normals.
333  
334  if undo is 0: calculate right normals
335  if undo is 1: restore original normals
336 */
337 //keep in sycn with utils.c!
338 #define FACE_FLIP       8
339 static void bmesh_rationalize_normals(BMesh *bm, int undo)
340 {
341         BMOperator bmop;
342         BMFace *f;
343         BMIter iter;
344         
345         if (undo) {
346                 BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
347                         if (BM_TestHFlag(f, BM_TMP_TAG)) {
348                                 BM_flip_normal(bm, f);
349                         }
350                         BM_ClearHFlag(f, BM_TMP_TAG);
351                 }
352                 
353                 return;
354         }
355         
356         BMO_InitOpf(bm, &bmop, "righthandfaces faces=%af doflip=%d", 0);
357         
358         BMO_push(bm, &bmop);
359         bmesh_righthandfaces_exec(bm, &bmop);
360         
361         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
362                 if (BMO_TestFlag(bm, f, FACE_FLIP))
363                         BM_SetHFlag(f, BM_TMP_TAG);
364                 else BM_ClearHFlag(f, BM_TMP_TAG);
365         }
366
367         BMO_pop(bm);
368         BMO_Finish_Op(bm, &bmop);
369 }
370
371 static void bmesh_set_mdisps_space(BMesh *bm, int from, int to)
372 {
373         /*switch multires data out of tangent space*/
374         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
375                 Object *ob = bm->ob;
376                 BMEditMesh *em = BMEdit_Create(bm, FALSE);
377                 DerivedMesh *dm = CDDM_from_BMEditMesh(em, NULL, TRUE, FALSE);
378                 MDisps *mdisps;
379                 BMFace *f;
380                 BMIter iter;
381                 // int i= 0; // UNUSED
382                 
383                 multires_set_space(dm, ob, from, to);
384                 
385                 mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
386                 
387                 BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
388                         BMLoop *l;
389                         BMIter liter;
390                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
391                                 MDisps *lmd = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MDISPS);
392                                 
393                                 if (!lmd->disps) {
394                                         printf("%s: warning - 'lmd->disps' == NULL\n", __func__);
395                                 }
396                                 
397                                 if (lmd->disps && lmd->totdisp == mdisps->totdisp) {
398                                         memcpy(lmd->disps, mdisps->disps, sizeof(float)*3*lmd->totdisp);
399                                 } else if (mdisps->disps) {
400                                         if (lmd->disps)
401                                                 MEM_freeN(lmd->disps);
402                                         
403                                         lmd->disps = MEM_dupallocN(mdisps->disps);
404                                         lmd->totdisp = mdisps->totdisp;
405                                 }
406                                 
407                                 mdisps++;
408                                 // i += 1;
409                         }
410                 }
411                 
412                 dm->needsFree = 1;
413                 dm->release(dm);
414                 
415                 /*setting this to NULL prevents BMEdit_Free from freeing it*/
416                 em->bm = NULL;
417                 BMEdit_Free(em);
418                 MEM_freeN(em);
419         }
420 }
421
422 /*      
423  *      BMESH BEGIN/END EDIT
424  *
425  *      Functions for setting up a mesh for editing and cleaning up after 
426  *  the editing operations are done. These are called by the tools/operator 
427  *  API for each time a tool is executed.
428  *
429  *  Returns -
430  *  Nothing
431  *
432 */
433 void bmesh_begin_edit(BMesh *bm, int flag)
434 {
435         bm->opflag = flag;
436         
437         /* Most operators seem to be using BMOP_UNTAN_MULTIRES to change the MDisps to
438            absolute space during mesh edits. With this enabled, changes to the topology
439            (loop cuts, edge subdivides, etc) are not reflected in the higher levels of
440            the mesh at all, which doesn't seem right. Turning off completely for now,
441            until this is shown to be better for certain types of mesh edits. */
442 #if BMOP_UNTAN_MULTIRES_ENABLED
443         /*switch multires data out of tangent space*/
444         if ((flag & BMOP_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
445                 bmesh_set_mdisps_space(bm, MULTIRES_SPACE_TANGENT, MULTIRES_SPACE_ABSOLUTE);
446
447                 /*ensure correct normals, if possible*/
448                 bmesh_rationalize_normals(bm, 0);
449                 BM_Compute_Normals(bm);
450         } else if (flag & BMOP_RATIONALIZE_NORMALS) {
451                 bmesh_rationalize_normals(bm, 0);
452         }
453 #else
454         if (flag & BMOP_RATIONALIZE_NORMALS) {
455                 bmesh_rationalize_normals(bm, 0);
456         }
457 #endif
458 }
459
460 void bmesh_end_edit(BMesh *bm, int flag)
461 {
462         /* BMOP_UNTAN_MULTIRES disabled for now, see comment above in bmesh_begin_edit. */
463 #if BMOP_UNTAN_MULTIRES_ENABLED
464         /*switch multires data into tangent space*/
465         if ((flag & BMOP_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
466                 /*set normals to their previous winding*/
467                 bmesh_rationalize_normals(bm, 1);
468                 bmesh_set_mdisps_space(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
469         } else if (flag & BMOP_RATIONALIZE_NORMALS) {
470                 bmesh_rationalize_normals(bm, 1);
471         }
472 #else
473         if (flag & BMOP_RATIONALIZE_NORMALS) {
474                 bmesh_rationalize_normals(bm, 1);
475         }
476 #endif
477
478         bm->opflag = 0;
479
480         /*compute normals, clear temp flags and flush selections*/
481         BM_Compute_Normals(bm);
482         BM_SelectMode_Flush(bm);
483 }
484
485 void BM_ElemIndex_Ensure(BMesh *bm, const char hflag)
486 {
487         BMIter iter;
488         BMHeader *ele;
489
490 #ifdef DEBUG
491         BM_ELEM_INDEX_VALIDATE(bm, "Should Never Fail!", __func__);
492 #endif
493
494         if (hflag & BM_VERT) {
495                 if (bm->elem_index_dirty & BM_VERT) {
496                         int index= 0;
497                         BM_ITER(ele, &iter, bm, BM_VERTS_OF_MESH, NULL) {
498                                 BM_SetIndex(ele, index); /* set_ok */
499                                 index++;
500                         }
501                         bm->elem_index_dirty &= ~BM_VERT;
502                         BLI_assert(index == bm->totvert);
503                 }
504                 else {
505                         // printf("%s: skipping vert index calc!\n", __func__);
506                 }
507         }
508
509         if (hflag & BM_EDGE) {
510                 if (bm->elem_index_dirty & BM_EDGE) {
511                         int index= 0;
512                         BM_ITER(ele, &iter, bm, BM_EDGES_OF_MESH, NULL) {
513                                 BM_SetIndex(ele, index); /* set_ok */
514                                 index++;
515                         }
516                         bm->elem_index_dirty &= ~BM_EDGE;
517                         BLI_assert(index == bm->totedge);
518                 }
519                 else {
520                         // printf("%s: skipping edge index calc!\n", __func__);
521                 }
522         }
523
524         if (hflag & BM_FACE) {
525                 if (bm->elem_index_dirty & BM_FACE) {
526                         int index= 0;
527                         BM_ITER(ele, &iter, bm, BM_FACES_OF_MESH, NULL) {
528                                 BM_SetIndex(ele, index); /* set_ok */
529                                 index++;
530                         }
531                         bm->elem_index_dirty &= ~BM_FACE;
532                         BLI_assert(index == bm->totface);
533                 }
534                 else {
535                         // printf("%s: skipping face index calc!\n", __func__);
536                 }
537         }
538 }
539
540
541 /* array checking/setting macros */
542 /* currently vert/edge/loop/face index data is being abused, but we should
543  * eventually be able to rely on it being valid. To this end, there are macros
544  * that validate them (so blender doesnt crash), but also print errors so we can
545  * fix the offending parts of the code, this way after some months we can
546  * confine this code for debug mode.
547  *
548  *
549  */
550
551 void BM_ElemIndex_Validate(BMesh *bm, const char *location, const char *func, const char *msg_a, const char *msg_b)
552 {
553         BMIter iter;
554         BMHeader *ele;
555         int types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
556         const char *type_names[3]= {"vert", "edge", "face"};
557         const char type_flags[3]= {BM_VERT, BM_EDGE, BM_FACE};
558         int i;
559         int is_any_error= 0;
560
561         for (i=0; i<3; i++) {
562                 const int is_dirty= (type_flags[i] & bm->elem_index_dirty);
563                 int index= 0;
564                 int is_error= FALSE;
565                 int err_val= 0;
566                 int err_idx= 0;
567
568                 BM_ITER(ele, &iter, bm, types[i], NULL) {
569                         if (!is_dirty) {
570                                 if (BM_GetIndex(ele) != index) {
571                                         err_val= BM_GetIndex(ele);
572                                         err_idx= index;
573                                         is_error= TRUE;
574                                 }
575                         }
576
577                         BM_SetIndex(ele, index); /* set_ok */
578                         index++;
579                 }
580
581                 if ((is_error == TRUE) && (is_dirty == FALSE)) {
582                         is_any_error= TRUE;
583                         fprintf(stderr,
584                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
585                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
586                 }
587                 else if ((is_error == FALSE) && (is_dirty == TRUE)) {
588
589 #if 0           /* mostly annoying */
590
591                         /* dirty may have been incorrectly set */
592                         fprintf(stderr,
593                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
594                                 location, func, type_names[i], msg_a, msg_b);
595 #endif
596                 }
597         }
598
599 #if 0 /* mostly annoying, even in debug mode */
600 #ifdef DEBUG
601         if (is_any_error == 0) {
602                 fprintf(stderr,
603                                 "Valid Index Success: at %s, %s, '%s', '%s'\n",
604                                 location, func, msg_a, msg_b);
605         }
606 #endif
607 #endif
608         (void) is_any_error; /* shut up the compiler */
609
610 }
611
612 BMVert *BM_Vert_AtIndex(BMesh *bm, const int index)
613 {
614         return BLI_mempool_findelem(bm->vpool, index);
615 }
616
617 BMEdge *BM_Edge_AtIndex(BMesh *bm, const int index)
618 {
619         return BLI_mempool_findelem(bm->epool, index);
620 }
621
622 BMFace *BM_Face_AtIndex(BMesh *bm, const int index)
623 {
624         return BLI_mempool_findelem(bm->fpool, index);
625 }