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