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