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