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