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