7d42b3031ecc011703a2b4624c2814209997aa83
[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 *= -1.0f;
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                         copy_v3_v3(v->no, v->co);
325                         normalize_v3(v->no);
326                 }
327         }
328         
329         MEM_freeN(edgevec);
330         MEM_freeN(projectverts);
331 }
332
333 /*
334  This function ensures correct normals for the mesh, but
335  sets the flag BM_TMP_TAG in flipped faces, to allow restoration
336  of original normals.
337  
338  if undo is 0: calculate right normals
339  if undo is 1: restore original normals
340 */
341 //keep in sycn with utils.c!
342 #define FACE_FLIP       8
343 static void bmesh_rationalize_normals(BMesh *bm, int undo)
344 {
345         BMOperator bmop;
346         BMFace *f;
347         BMIter iter;
348         
349         if (undo) {
350                 BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
351                         if (BM_TestHFlag(f, BM_TMP_TAG)) {
352                                 BM_flip_normal(bm, f);
353                         }
354                         BM_ClearHFlag(f, BM_TMP_TAG);
355                 }
356                 
357                 return;
358         }
359         
360         BMO_InitOpf(bm, &bmop, "righthandfaces faces=%af doflip=%d", 0);
361         
362         BMO_push(bm, &bmop);
363         bmesh_righthandfaces_exec(bm, &bmop);
364         
365         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
366                 if (BMO_TestFlag(bm, f, FACE_FLIP))
367                         BM_SetHFlag(f, BM_TMP_TAG);
368                 else BM_ClearHFlag(f, BM_TMP_TAG);
369         }
370
371         BMO_pop(bm);
372         BMO_Finish_Op(bm, &bmop);
373 }
374
375 static void bmesh_set_mdisps_space(BMesh *bm, int from, int to)
376 {
377         /*switch multires data out of tangent space*/
378         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
379                 Object *ob = bm->ob;
380                 BMEditMesh *em = BMEdit_Create(bm);
381                 DerivedMesh *dm = CDDM_from_BMEditMesh(em, NULL, 1);
382                 MDisps *mdisps;
383                 BMFace *f;
384                 BMIter iter;
385                 // int i= 0; // UNUSED
386                 
387                 multires_set_space(dm, ob, from, to);
388                 
389                 mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
390                 
391                 BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
392                         BMLoop *l;
393                         BMIter liter;
394                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
395                                 MDisps *lmd = CustomData_bmesh_get(&bm->ldata, l->head.data, CD_MDISPS);
396                                 
397                                 if (!lmd->disps) {
398                                         printf("eck!\n");
399                                 }
400                                 
401                                 if (lmd->disps && lmd->totdisp == mdisps->totdisp) {
402                                         memcpy(lmd->disps, mdisps->disps, sizeof(float)*3*lmd->totdisp);
403                                 } else if (mdisps->disps) {
404                                         if (lmd->disps)
405                                                 BLI_cellalloc_free(lmd->disps);
406                                         
407                                         lmd->disps = BLI_cellalloc_dupalloc(mdisps->disps);
408                                         lmd->totdisp = mdisps->totdisp;
409                                 }
410                                 
411                                 mdisps++;
412                                 // i += 1;
413                         }
414                 }
415                 
416                 dm->needsFree = 1;
417                 dm->release(dm);
418                 
419                 /*setting this to NULL prevents BMEdit_Free from freeing it*/
420                 em->bm = NULL;
421                 BMEdit_Free(em);
422                 MEM_freeN(em);
423         }
424 }
425
426 /*      
427  *      BMESH BEGIN/END EDIT
428  *
429  *      Functions for setting up a mesh for editing and cleaning up after 
430  *  the editing operations are done. These are called by the tools/operator 
431  *  API for each time a tool is executed.
432  *
433  *  Returns -
434  *  Nothing
435  *
436 */
437 void bmesh_begin_edit(BMesh *bm, int flag)
438 {
439         bm->opflag = flag;
440         
441         /* Most operators seem to be using BMOP_UNTAN_MULTIRES to change the MDisps to
442            absolute space during mesh edits. With this enabled, changes to the topology
443            (loop cuts, edge subdivides, etc) are not reflected in the higher levels of
444            the mesh at all, which doesn't seem right. Turning off completely for now,
445            until this is shown to be better for certain types of mesh edits. */
446 #if BMOP_UNTAN_MULTIRES_ENABLED
447         /*switch multires data out of tangent space*/
448         if ((flag & BMOP_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
449                 bmesh_set_mdisps_space(bm, MULTIRES_SPACE_TANGENT, MULTIRES_SPACE_ABSOLUTE);
450
451                 /*ensure correct normals, if possible*/
452                 bmesh_rationalize_normals(bm, 0);
453                 BM_Compute_Normals(bm);
454         } else if (flag & BMOP_RATIONALIZE_NORMALS) {
455                 bmesh_rationalize_normals(bm, 0);
456         }
457 #else
458         if (flag & BMOP_RATIONALIZE_NORMALS) {
459                 bmesh_rationalize_normals(bm, 0);
460         }
461 #endif
462 }
463
464 void bmesh_end_edit(BMesh *bm, int flag)
465 {
466         /* BMOP_UNTAN_MULTIRES disabled for now, see comment above in bmesh_begin_edit. */
467 #if BMOP_UNTAN_MULTIRES_ENABLED
468         /*switch multires data into tangent space*/
469         if ((flag & BMOP_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
470                 /*set normals to their previous winding*/
471                 bmesh_rationalize_normals(bm, 1);
472                 bmesh_set_mdisps_space(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
473         } else if (flag & BMOP_RATIONALIZE_NORMALS) {
474                 bmesh_rationalize_normals(bm, 1);
475         }
476 #else
477         if (flag & BMOP_RATIONALIZE_NORMALS) {
478                 bmesh_rationalize_normals(bm, 1);
479         }
480 #endif
481
482         bm->opflag = 0;
483
484         /*compute normals, clear temp flags and flush selections*/
485         BM_Compute_Normals(bm);
486         BM_SelectMode_Flush(bm);
487 }
488
489 void BM_ElemIndex_Ensure(BMesh *bm, const char hflag)
490 {
491         BMIter iter;
492         BMHeader *ele;
493
494         /* TODO, mark arrays as dirty, only calculate if needed!,
495          * uncomment bm->elem_index_dirty checks */
496
497         if ((hflag & BM_VERT) /* && (bm->elem_index_dirty & BM_VERT) */) {
498                 int index= 0;
499                 BM_ITER(ele, &iter, bm, BM_VERTS_OF_MESH, NULL) {
500                         BM_SetIndex(ele, index); /* set_ok */
501                         index++;
502                 }
503                 bm->elem_index_dirty &= ~BM_VERT;
504                 BLI_assert(index == bm->totvert);
505         }
506
507         if ((hflag & BM_EDGE) /* && (bm->elem_index_dirty & BM_EDGE) */) {
508                 int index= 0;
509                 BM_ITER(ele, &iter, bm, BM_EDGES_OF_MESH, NULL) {
510                         BM_SetIndex(ele, index); /* set_ok */
511                         index++;
512                 }
513                 bm->elem_index_dirty &= ~BM_EDGE;
514                 BLI_assert(index == bm->totedge);
515         }
516
517         if ((hflag & BM_FACE) /* && (bm->elem_index_dirty & BM_FACES) */) {
518                 int index= 0;
519                 BM_ITER(ele, &iter, bm, BM_FACES_OF_MESH, NULL) {
520                         BM_SetIndex(ele, index); /* set_ok */
521                         index++;
522                 }
523                 bm->elem_index_dirty &= ~BM_FACE;
524                 BLI_assert(index == bm->totface);
525         }
526 }
527
528
529 /* array checking/setting macros */
530 /* currently vert/edge/loop/face index data is being abused, but we should
531  * eventually be able to rely on it being valid. To this end, there are macros
532  * that validate them (so blender doesnt crash), but also print errors so we can
533  * fix the offending parts of the code, this way after some months we can
534  * confine this code for debug mode.
535  *
536  *
537  */
538
539 void BM_ElemIndex_Validate(BMesh *bm, const char *location, const char *func, const char *msg_a, const char *msg_b)
540 {
541         BMIter iter;
542         BMHeader *ele;
543         int types[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
544         const char *type_names[3]= {"vert", "edge", "face"};
545         const char type_flags[3]= {BM_VERT, BM_EDGE, BM_FACE};
546         int i;
547         int is_any_error= 0;
548
549         for (i=0; i<3; i++) {
550                 const int is_dirty= (type_flags[i] & bm->elem_index_dirty);
551                 int index= 0;
552                 int is_error= FALSE;
553                 int err_val= 0;
554                 int err_idx= 0;
555
556                 BM_ITER(ele, &iter, bm, types[i], NULL) {
557                         if (BM_GetIndex(ele) != index) {
558                                 err_val= BM_GetIndex(ele);
559                                 err_idx= index;
560                                 is_error= TRUE;
561                         }
562
563                         BM_SetIndex(ele, index); /* set_ok */
564                         index++;
565                 }
566
567                 if ((is_error == TRUE) && (is_dirty == FALSE)) {
568                         is_any_error= TRUE;
569                         fprintf(stderr,
570                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
571                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
572                 }
573                 else if ((is_error == FALSE) && (is_dirty == TRUE)) {
574                         /* dirty may have been incorrectly set */
575                         fprintf(stderr,
576                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
577                                 location, func, type_names[i], msg_a, msg_b);
578                 }
579         }
580
581 #if 0 /* mostly annoying, even in debug mode */
582 #ifdef DEBUG
583         if (is_any_error == 0) {
584                 fprintf(stderr,
585                                 "Valid Index Success: at %s, %s, '%s', '%s'\n",
586                                 location, func, msg_a, msg_b);
587         }
588 #endif
589 #endif
590 }