bmesh: fixed merge issues with navmesh (though I've not tested if it works yet).
[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], 0, 1);
91         bm->epool = BLI_mempool_create(esize, allocsize[1], allocsize[1], 0, 1);
92         bm->lpool = BLI_mempool_create(lsize, allocsize[2], allocsize[2], 0, 0);
93         bm->looplistpool = BLI_mempool_create(lstsize, allocsize[3], allocsize[3], 0, 0);
94         bm->fpool = BLI_mempool_create(fsize, allocsize[3], allocsize[3], 0, 1);
95
96         /*allocate one flag pool that we dont get rid of.*/
97         bm->toolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), 512, 512, 0, 0);
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], 0, 1);
187         bm->epool = BLI_mempool_create(esize, allocsize[1], allocsize[1], 0, 1);
188         bm->lpool = BLI_mempool_create(lsize, allocsize[2], allocsize[2], 0, 0);
189         bm->looplistpool = BLI_mempool_create(lstsize, allocsize[3], allocsize[3], 0, 0);
190         bm->fpool = BLI_mempool_create(fsize, allocsize[4], allocsize[4], 0, 1);
191
192         /*allocate one flag pool that we dont get rid of.*/
193         bm->toolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), 512, 512, 0, 0);
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                 if (!e->l) {
274                         /* the edge vector will not be needed when the edge has no radial */
275                         continue;
276                 }
277                 BM_SetIndex(e, index);
278                 sub_v3_v3v3(edgevec[index], e->v2->co, e->v1->co);
279                 normalize_v3(edgevec[index]);
280                 index++;
281         }
282
283         /*add weighted face normals to vertices*/
284         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
285
286                 if (BM_TestHFlag(f, BM_HIDDEN))
287                         continue;
288
289                 BM_ITER(l, &loops, bm, BM_LOOPS_OF_FACE, f) {
290                         float *e1diff, *e2diff;
291                         float dotprod;
292                         float fac;
293
294                         /* calculate the dot product of the two edges that
295                            meet at the loop's vertex */
296                         e1diff = edgevec[BM_GetIndex(l->prev->e)];
297                         e2diff = edgevec[BM_GetIndex(l->e)];
298                         dotprod = dot_v3v3(e1diff, e2diff);
299
300                         /* edge vectors are calculated from e->v1 to e->v2, so
301                            adjust the dot product if one but not both loops 
302                            actually runs from from e->v2 to e->v1 */
303                         if ((l->prev->e->v1 == l->prev->v) ^ (l->e->v1 == l->v)) {
304                                 dotprod *= -1.0f;
305                         }
306
307                         fac = saacos(-dotprod);
308
309                         /* accumulate weighted face normal into the vertex's normal */
310                         madd_v3_v3fl(l->v->no, f->no, fac);
311                 }
312         }
313         
314         /* normalize the accumulated vertex normals */
315         BM_ITER(v, &verts, bm, BM_VERTS_OF_MESH, NULL) {
316                 if (BM_TestHFlag(v, BM_HIDDEN))
317                         continue;
318
319                 if (normalize_v3(v->no) == 0.0f) {
320                         copy_v3_v3(v->no, v->co);
321                         normalize_v3(v->no);
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);
377                 DerivedMesh *dm = CDDM_from_BMEditMesh(em, NULL, 1);
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("eck!\n");
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                                                 BLI_cellalloc_free(lmd->disps);
402                                         
403                                         lmd->disps = BLI_cellalloc_dupalloc(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 }