cf297560c324a46322d1f7fe7241a948b4be5740
[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
34 #include "BLI_listbase.h"
35 #include "BLI_math.h"
36 #include "BLI_utildefines.h"
37
38 #include "BKE_cdderivedmesh.h"
39 #include "BKE_tessmesh.h"
40 #include "BKE_multires.h"
41
42 #include "ED_mesh.h"
43
44 #include "intern/bmesh_private.h"
45
46 /* used as an extern, defined in bmesh.h */
47 BMAllocTemplate bm_mesh_allocsize_default = {512, 1024, 2048, 512};
48 BMAllocTemplate bm_mesh_chunksize_default = {512, 1024, 2048, 512};
49
50 static void bm_mempool_init(BMesh *bm, const BMAllocTemplate *allocsize)
51 {
52         bm->vpool = BLI_mempool_create(sizeof(BMVert), allocsize->totvert, bm_mesh_chunksize_default.totvert, BLI_MEMPOOL_ALLOW_ITER);
53         bm->epool = BLI_mempool_create(sizeof(BMEdge), allocsize->totedge, bm_mesh_chunksize_default.totedge, BLI_MEMPOOL_ALLOW_ITER);
54         bm->lpool = BLI_mempool_create(sizeof(BMLoop), allocsize->totloop, bm_mesh_chunksize_default.totloop, 0);
55         bm->fpool = BLI_mempool_create(sizeof(BMFace), allocsize->totface, bm_mesh_chunksize_default.totface, BLI_MEMPOOL_ALLOW_ITER);
56
57 #ifdef USE_BMESH_HOLES
58         bm->looplistpool = BLI_mempool_create(sizeof(BMLoopList), allocsize[3], allocsize[3], FALSE, FALSE);
59 #endif
60
61         /* allocate one flag pool that we dont get rid of. */
62         bm->toolflagpool = BLI_mempool_create(sizeof(BMFlagLayer), 512, 512, 0);
63 }
64
65 /**
66  * \brief BMesh Make Mesh
67  *
68  * Allocates a new BMesh structure.
69  *
70  * \return The New bmesh
71  *
72  * \note ob is needed by multires
73  */
74 BMesh *BM_mesh_create(struct Object *ob, BMAllocTemplate *allocsize)
75 {
76         /* allocate the structure */
77         BMesh *bm = MEM_callocN(sizeof(BMesh), __func__);
78
79         bm->ob = ob;
80         
81         /* allocate the memory pools for the mesh elements */
82         bm_mempool_init(bm, allocsize);
83
84         /* allocate one flag pool that we dont get rid of. */
85         bm->stackdepth = 1;
86         bm->totflags = 1;
87
88         return bm;
89 }
90
91 /**
92  * \brief BMesh Free Mesh Data
93  *
94  *      Frees a BMesh structure.
95  *
96  * \note frees mesh, but not actual BMesh struct
97  */
98 void BM_mesh_data_free(BMesh *bm)
99 {
100         BMVert *v;
101         BMEdge *e;
102         BMLoop *l;
103         BMFace *f;
104         
105
106         BMIter verts;
107         BMIter edges;
108         BMIter faces;
109         BMIter loops;
110         
111         for (v = BM_iter_new(&verts, bm, BM_VERTS_OF_MESH, bm); v; v = BM_iter_step(&verts)) {
112                 CustomData_bmesh_free_block(&(bm->vdata), &(v->head.data));
113         }
114         for (e = BM_iter_new(&edges, bm, BM_EDGES_OF_MESH, bm); e; e = BM_iter_step(&edges)) {
115                 CustomData_bmesh_free_block(&(bm->edata), &(e->head.data));
116         }
117         for (f = BM_iter_new(&faces, bm, BM_FACES_OF_MESH, bm); f; f = BM_iter_step(&faces)) {
118                 CustomData_bmesh_free_block(&(bm->pdata), &(f->head.data));
119                 for (l = BM_iter_new(&loops, bm, BM_LOOPS_OF_FACE, f); l; l = BM_iter_step(&loops)) {
120                         CustomData_bmesh_free_block(&(bm->ldata), &(l->head.data));
121                 }
122         }
123
124         /* Free custom data pools, This should probably go in CustomData_free? */
125         if (bm->vdata.totlayer) BLI_mempool_destroy(bm->vdata.pool);
126         if (bm->edata.totlayer) BLI_mempool_destroy(bm->edata.pool);
127         if (bm->ldata.totlayer) BLI_mempool_destroy(bm->ldata.pool);
128         if (bm->pdata.totlayer) BLI_mempool_destroy(bm->pdata.pool);
129
130         /* free custom data */
131         CustomData_free(&bm->vdata, 0);
132         CustomData_free(&bm->edata, 0);
133         CustomData_free(&bm->ldata, 0);
134         CustomData_free(&bm->pdata, 0);
135
136         /* destroy element pools */
137         BLI_mempool_destroy(bm->vpool);
138         BLI_mempool_destroy(bm->epool);
139         BLI_mempool_destroy(bm->lpool);
140         BLI_mempool_destroy(bm->fpool);
141
142         /* destroy flag pool */
143         BLI_mempool_destroy(bm->toolflagpool);
144
145 #ifdef USE_BMESH_HOLES
146         BLI_mempool_destroy(bm->looplistpool);
147 #endif
148
149         /* These tables aren't used yet, so it's not strictly necessary
150          * to 'end' them (with 'e' param) but if someone tries to start
151          * using them, having these in place will save a lot of pain */
152         mesh_octree_table(NULL, NULL, NULL, 'e');
153         mesh_mirrtopo_table(NULL, 'e');
154
155         BLI_freelistN(&bm->selected);
156
157         if (bm->py_handle) {
158                 extern void bpy_bm_generic_invalidate(void *self);
159
160                 bpy_bm_generic_invalidate(bm->py_handle);
161                 bm->py_handle = NULL;
162         }
163
164         BMO_error_clear(bm);
165 }
166
167 /**
168  * \brief BMesh Clear Mesh
169  *
170  * Clear all data in bm
171  */
172 void BM_mesh_clear(BMesh *bm)
173 {
174         Object *ob = bm->ob;
175         
176         /* free old mesh */
177         BM_mesh_data_free(bm);
178         memset(bm, 0, sizeof(BMesh));
179         
180         /* re-initialize mesh */
181         bm->ob = ob;
182         
183         /* allocate the memory pools for the mesh elements */
184         bm_mempool_init(bm, &bm_mesh_allocsize_default);
185
186         bm->stackdepth = 1;
187         bm->totflags = 1;
188 }
189
190 /**
191  * \brief BMesh Free Mesh
192  *
193  *      Frees a BMesh data and its structure.
194  */
195 void BM_mesh_free(BMesh *bm)
196 {
197         BM_mesh_data_free(bm);
198         MEM_freeN(bm);
199 }
200
201 /**
202  * \brief BMesh Compute Normals
203  *
204  * Updates the normals of a mesh.
205  */
206 void BM_mesh_normals_update(BMesh *bm, const short skip_hidden)
207 {
208         BMVert *v;
209         BMFace *f;
210         BMLoop *l;
211         BMEdge *e;
212         BMIter verts;
213         BMIter faces;
214         BMIter loops;
215         BMIter edges;
216         unsigned int maxlength = 0;
217         int index;
218         float (*projectverts)[3];
219         float (*edgevec)[3];
220
221         /* first, find out the largest face in mesh */
222         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
223                 if (skip_hidden && BM_elem_flag_test(f, BM_ELEM_HIDDEN))
224                         continue;
225
226                 if (f->len > maxlength) maxlength = f->len;
227         }
228         
229         /* make sure we actually have something to do */
230         if (maxlength < 3) return;
231
232         /* allocate projectverts array */
233         projectverts = MEM_callocN(sizeof(float) * maxlength * 3, "BM normal computation array");
234         
235         /* calculate all face normals */
236         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
237                 if (skip_hidden && BM_elem_flag_test(f, BM_ELEM_HIDDEN))
238                         continue;
239 #if 0   /* UNUSED */
240                 if (f->head.flag & BM_NONORMCALC)
241                         continue;
242 #endif
243
244                 bmesh_face_normal_update(bm, f, f->no, projectverts);
245         }
246         
247         /* Zero out vertex normals */
248         BM_ITER(v, &verts, bm, BM_VERTS_OF_MESH, NULL) {
249                 if (skip_hidden && BM_elem_flag_test(v, BM_ELEM_HIDDEN))
250                         continue;
251
252                 zero_v3(v->no);
253         }
254
255         /* compute normalized direction vectors for each edge. directions will be
256          * used below for calculating the weights of the face normals on the vertex
257          * normals */
258         index = 0;
259         edgevec = MEM_callocN(sizeof(float) * 3 * bm->totedge, "BM normal computation array");
260         BM_ITER(e, &edges, bm, BM_EDGES_OF_MESH, NULL) {
261                 BM_elem_index_set(e, index); /* set_inline */
262
263                 if (e->l) {
264                         sub_v3_v3v3(edgevec[index], e->v2->co, e->v1->co);
265                         normalize_v3(edgevec[index]);
266                 }
267                 else {
268                         /* the edge vector will not be needed when the edge has no radial */
269                 }
270
271                 index++;
272         }
273         bm->elem_index_dirty &= ~BM_EDGE;
274
275         /* add weighted face normals to vertices */
276         BM_ITER(f, &faces, bm, BM_FACES_OF_MESH, NULL) {
277
278                 if (skip_hidden && BM_elem_flag_test(f, BM_ELEM_HIDDEN))
279                         continue;
280
281                 BM_ITER(l, &loops, bm, BM_LOOPS_OF_FACE, f) {
282                         float *e1diff, *e2diff;
283                         float dotprod;
284                         float fac;
285
286                         /* calculate the dot product of the two edges that
287                          * meet at the loop's vertex */
288                         e1diff = edgevec[BM_elem_index_get(l->prev->e)];
289                         e2diff = edgevec[BM_elem_index_get(l->e)];
290                         dotprod = dot_v3v3(e1diff, e2diff);
291
292                         /* edge vectors are calculated from e->v1 to e->v2, so
293                          * adjust the dot product if one but not both loops
294                          * actually runs from from e->v2 to e->v1 */
295                         if ((l->prev->e->v1 == l->prev->v) ^ (l->e->v1 == l->v)) {
296                                 dotprod = -dotprod;
297                         }
298
299                         fac = saacos(-dotprod);
300
301                         /* accumulate weighted face normal into the vertex's normal */
302                         madd_v3_v3fl(l->v->no, f->no, fac);
303                 }
304         }
305         
306         /* normalize the accumulated vertex normals */
307         BM_ITER(v, &verts, bm, BM_VERTS_OF_MESH, NULL) {
308                 if (skip_hidden && BM_elem_flag_test(v, BM_ELEM_HIDDEN))
309                         continue;
310
311                 if (normalize_v3(v->no) == 0.0f) {
312                         normalize_v3_v3(v->no, v->co);
313                 }
314         }
315         
316         MEM_freeN(edgevec);
317         MEM_freeN(projectverts);
318 }
319
320 /*
321  * This function ensures correct normals for the mesh, but
322  * sets the flag BM_ELEM_TAG in flipped faces, to allow restoration
323  * of original normals.
324  *
325  * if undo is 0: calculate right normals
326  * if undo is 1: restore original normals
327  */
328
329 //keep in sycn with utils.c!
330 #define FACE_FLIP       8
331 static void bm_rationalize_normals(BMesh *bm, int undo)
332 {
333         BMOperator bmop;
334         BMFace *f;
335         BMIter iter;
336         
337         if (undo) {
338                 BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
339                         if (BM_elem_flag_test(f, BM_ELEM_TAG)) {
340                                 BM_face_normal_flip(bm, f);
341                         }
342                         BM_elem_flag_disable(f, BM_ELEM_TAG);
343                 }
344                 
345                 return;
346         }
347         
348         BMO_op_initf(bm, &bmop, "righthandfaces faces=%af do_flip=%b", FALSE);
349         
350         BMO_push(bm, &bmop);
351         bmo_righthandfaces_exec(bm, &bmop);
352         
353         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
354                 BM_elem_flag_set(f, BM_ELEM_TAG, BMO_elem_flag_test(bm, f, FACE_FLIP));
355         }
356
357         BMO_pop(bm);
358         BMO_op_finish(bm, &bmop);
359 }
360
361 static void UNUSED_FUNCTION(bm_mdisps_space_set)(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  * \brief BMesh Begin 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_edit_begin(BMesh *bm, int flag)
421 {
422         bm->opflag = flag;
423         
424         /* Most operators seem to be using BMO_OP_FLAG_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 & BMO_OP_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
432                 bmesh_mdisps_space_set(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 & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
439                 bmesh_rationalize_normals(bm, 0);
440         }
441 #else
442         if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
443                 bm_rationalize_normals(bm, 0);
444         }
445 #endif
446 }
447
448 /**
449  * \brief BMesh End Edit
450  */
451 void bmesh_edit_end(BMesh *bm, int flag)
452 {
453         /* BMO_OP_FLAG_UNTAN_MULTIRES disabled for now, see comment above in bmesh_edit_begin. */
454 #if BMOP_UNTAN_MULTIRES_ENABLED
455         /* switch multires data into tangent space */
456         if ((flag & BMO_OP_FLAG_UNTAN_MULTIRES) && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
457                 /* set normals to their previous winding */
458                 bmesh_rationalize_normals(bm, 1);
459                 bmesh_mdisps_space_set(bm, MULTIRES_SPACE_ABSOLUTE, MULTIRES_SPACE_TANGENT);
460         }
461         else if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
462                 bmesh_rationalize_normals(bm, 1);
463         }
464 #else
465         if (flag & BMO_OP_FLAG_RATIONALIZE_NORMALS) {
466                 bm_rationalize_normals(bm, 1);
467         }
468 #endif
469
470         bm->opflag = 0;
471
472         /* compute normals, clear temp flags and flush selections */
473         BM_mesh_normals_update(bm, TRUE);
474         BM_mesh_select_mode_flush(bm);
475 }
476
477 void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag)
478 {
479         BMIter iter;
480         BMElem *ele;
481
482 #ifdef DEBUG
483         BM_ELEM_INDEX_VALIDATE(bm, "Should Never Fail!", __func__);
484 #endif
485
486         if (hflag & BM_VERT) {
487                 if (bm->elem_index_dirty & BM_VERT) {
488                         int index = 0;
489                         BM_ITER(ele, &iter, bm, BM_VERTS_OF_MESH, NULL) {
490                                 BM_elem_index_set(ele, index); /* set_ok */
491                                 index++;
492                         }
493                         bm->elem_index_dirty &= ~BM_VERT;
494                         BLI_assert(index == bm->totvert);
495                 }
496                 else {
497                         // printf("%s: skipping vert index calc!\n", __func__);
498                 }
499         }
500
501         if (hflag & BM_EDGE) {
502                 if (bm->elem_index_dirty & BM_EDGE) {
503                         int index = 0;
504                         BM_ITER(ele, &iter, bm, BM_EDGES_OF_MESH, NULL) {
505                                 BM_elem_index_set(ele, index); /* set_ok */
506                                 index++;
507                         }
508                         bm->elem_index_dirty &= ~BM_EDGE;
509                         BLI_assert(index == bm->totedge);
510                 }
511                 else {
512                         // printf("%s: skipping edge index calc!\n", __func__);
513                 }
514         }
515
516         if (hflag & BM_FACE) {
517                 if (bm->elem_index_dirty & BM_FACE) {
518                         int index = 0;
519                         BM_ITER(ele, &iter, bm, BM_FACES_OF_MESH, NULL) {
520                                 BM_elem_index_set(ele, index); /* set_ok */
521                                 index++;
522                         }
523                         bm->elem_index_dirty &= ~BM_FACE;
524                         BLI_assert(index == bm->totface);
525                 }
526                 else {
527                         // printf("%s: skipping face index calc!\n", __func__);
528                 }
529         }
530 }
531
532
533 /**
534  * Array checking/setting macros
535  *
536  * Currently vert/edge/loop/face index data is being abused, in a few areas of the code.
537  *
538  * To avoid correcting them afterwards, set 'bm->elem_index_dirty' however its possible
539  * this flag is set incorrectly which could crash blender.
540  *
541  * These functions ensure its correct and are called more often in debug mode.
542  */
543
544 void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func,
545                                  const char *msg_a, const char *msg_b)
546 {
547         const char iter_types[3] = {BM_VERTS_OF_MESH,
548                                     BM_EDGES_OF_MESH,
549                                     BM_FACES_OF_MESH};
550
551         const char flag_types[3] = {BM_VERT, BM_EDGE, BM_FACE};
552         const char *type_names[3] = {"vert", "edge", "face"};
553
554         BMIter iter;
555         BMElem *ele;
556         int i;
557         int is_any_error = 0;
558
559         for (i = 0; i < 3; i++) {
560                 const int is_dirty = (flag_types[i] & bm->elem_index_dirty);
561                 int index = 0;
562                 int is_error = FALSE;
563                 int err_val = 0;
564                 int err_idx = 0;
565
566                 BM_ITER(ele, &iter, bm, iter_types[i], NULL) {
567                         if (!is_dirty) {
568                                 if (BM_elem_index_get(ele) != index) {
569                                         err_val = BM_elem_index_get(ele);
570                                         err_idx = index;
571                                         is_error = TRUE;
572                                 }
573                         }
574
575                         BM_elem_index_set(ele, index); /* set_ok */
576                         index++;
577                 }
578
579                 if ((is_error == TRUE) && (is_dirty == FALSE)) {
580                         is_any_error = TRUE;
581                         fprintf(stderr,
582                                 "Invalid Index: at %s, %s, %s[%d] invalid index %d, '%s', '%s'\n",
583                                 location, func, type_names[i], err_idx, err_val, msg_a, msg_b);
584                 }
585                 else if ((is_error == FALSE) && (is_dirty == TRUE)) {
586
587 #if 0           /* mostly annoying */
588
589                         /* dirty may have been incorrectly set */
590                         fprintf(stderr,
591                                 "Invalid Dirty: at %s, %s (%s), dirty flag was set but all index values are correct, '%s', '%s'\n",
592                                 location, func, type_names[i], msg_a, msg_b);
593 #endif
594                 }
595         }
596
597 #if 0 /* mostly annoying, even in debug mode */
598 #ifdef DEBUG
599         if (is_any_error == 0) {
600                 fprintf(stderr,
601                         "Valid Index Success: at %s, %s, '%s', '%s'\n",
602                         location, func, msg_a, msg_b);
603         }
604 #endif
605 #endif
606         (void) is_any_error; /* shut up the compiler */
607
608 }
609
610 BMVert *BM_vert_at_index(BMesh *bm, const int index)
611 {
612         return BLI_mempool_findelem(bm->vpool, index);
613 }
614
615 BMEdge *BM_edge_at_index(BMesh *bm, const int index)
616 {
617         return BLI_mempool_findelem(bm->epool, index);
618 }
619
620 BMFace *BM_face_at_index(BMesh *bm, const int index)
621 {
622         return BLI_mempool_findelem(bm->fpool, index);
623 }