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