307047463cf05b69a17ce2c8c2e8d09bdffa8056
[blender.git] / source / blender / blenkernel / intern / BME_mesh.c
1 /**
2  * BME_mesh.c    jan 2007
3  *
4  *      BMesh mesh level functions.
5  *
6  * $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  * about this.  
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  *
25  * The Original Code is Copyright (C) 2007 Blender Foundation.
26  * All rights reserved.
27  *
28  * The Original Code is: all of this file.
29  *
30  * Contributor(s): Geoffrey Bantle.
31  *
32  * ***** END GPL LICENSE BLOCK *****
33  */
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_listBase.h"
38 #include "DNA_meshdata_types.h"
39 #include "DNA_mesh_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_scene_types.h"
42
43
44 #include "BKE_utildefines.h"
45 #include "BKE_bmesh.h"
46 #include "BKE_global.h"
47 #include "BKE_depsgraph.h"
48 #include "BLI_blenlib.h"
49 #include "BLI_editVert.h"
50 #include "BIF_editmesh.h"
51 #include "BIF_space.h"
52 #include "editmesh.h"
53 #include "bmesh_private.h"
54 #include "mydevice.h"
55
56 #include "BSE_edit.h"
57
58
59 /*      
60  *      BME MAKE MESH
61  *
62  *  Allocates a new BME_Mesh structure
63 */
64
65
66
67 BME_Mesh *BME_make_mesh(int valloc, int ealloc, int lalloc, int palloc){
68         /*allocate the structure*/
69         BME_Mesh *bm = MEM_callocN(sizeof(BME_Mesh),"BMesh");
70         /*allocate the memory pools for the mesh elements*/
71         bm->vpool = BME_mempool_create(sizeof(BME_Vert), valloc, valloc);
72         bm->epool = BME_mempool_create(sizeof(BME_Edge), ealloc, ealloc);
73         bm->ppool = BME_mempool_create(sizeof(BME_Poly), palloc, palloc);
74         bm->lpool = BME_mempool_create(sizeof(BME_Loop), lalloc, lalloc);
75         /*allocate the customdata pools*/
76         return bm;
77 }
78
79
80 /*      
81  *      BME FREE MESH
82  *
83  *      Frees a BME_Mesh structure.
84 */
85
86 void BME_free_mesh(BME_Mesh *bm)
87 {
88         /*destroy element pools*/
89         BME_mempool_destroy(bm->vpool);
90         BME_mempool_destroy(bm->epool);
91         BME_mempool_destroy(bm->ppool);
92         BME_mempool_destroy(bm->lpool);
93         /*destroy custom data pools*/
94
95         MEM_freeN(bm);  
96 }
97
98 /*      
99  *      BME MODEL BEGIN AND END
100  *
101  *      These two functions represent the 'point of entry' for tools. Every BMesh tool
102  *      must begin with a call to BME_model_end() and finish with a call to BME_model_end().
103  *      No modification of mesh data is allowed except in between these two calls.
104  *
105  *      TODO 
106  *              FOR BME_MODEL_BEGIN:
107  *              -integrate euler undo system.
108  *              -make full copy of structure to safely recover from errors.
109  *              -accept a toolname string.
110  *              -accept param to turn off full copy if just selection tool. (perhaps check for this in eulers...)
111  *
112  *              BME_MODEL_END:
113  *              -full mesh validation if debugging turned on
114  *              -free structure copy or use it to restore.
115  *              -do euler undo push.
116  *
117 */
118
119 int BME_model_begin(BME_Mesh *bm){
120         /*Initialize some scratch pointer arrays used by eulers*/
121         bm->vtar = MEM_callocN(sizeof(BME_Vert *) * 1024, "BMesh scratch vert array");
122         bm->edar = MEM_callocN(sizeof(BME_Edge *) * 1024, "BMesh scratch edge array");
123         bm->lpar = MEM_callocN(sizeof(BME_Loop *) * 1024, "BMesh scratch loop array");
124         bm->plar = MEM_callocN(sizeof(BME_Poly *) * 1024, "BMesh scratch poly array");
125
126         bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 1024;
127
128         return 1;
129 }
130
131 void BME_model_end(BME_Mesh *bm){
132         int meshok, totvert, totedge, totpoly, totloop;
133
134         totvert = BLI_countlist(&(bm->verts));
135         totedge = BLI_countlist(&(bm->edges));
136         totpoly = BLI_countlist(&(bm->polys));
137
138         if(bm->vtar) MEM_freeN(bm->vtar);
139         if(bm->edar) MEM_freeN(bm->edar);
140         if(bm->lpar) MEM_freeN(bm->lpar);
141         if(bm->plar) MEM_freeN(bm->plar);
142         
143         bm->vtar = NULL;
144         bm->edar = NULL;
145         bm->lpar = NULL;
146         bm->plar = NULL;
147         bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 0;
148         
149         
150         if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly)
151                 BME_error();
152         
153         meshok = BME_validate_mesh(bm, 1);
154         if(!meshok){
155                 BME_error();
156         }
157 }
158
159 /*      
160  *      BME VALIDATE MESH
161  *
162  *      There are several levels of validation for meshes. At the 
163  *  Euler level, some basic validation is done to local topology.
164  *  To catch more subtle problems however, BME_validate_mesh() is 
165  *  called by BME_model_end() whenever a tool is done executing.
166  *  The purpose of this function is to insure that during the course 
167  *  of tool execution that nothing has been done to invalidate the 
168  *  structure, and if it has, provide a way of reporting that so that
169  *  we can restore the proper structure from a backup. Since a full mesh
170  *  validation would be too expensive, this is presented as a compromise.
171  *
172  *      TODO 
173  *      
174  *      -Write a full mesh validation function for debugging purposes.
175  */
176
177 #define VHALT(halt) {BME_error(); if(halt) return 0;}
178
179 int BME_validate_mesh(struct BME_Mesh *bm, int halt)
180 {
181         BME_Vert *v;
182         BME_Edge *e;
183         BME_Poly *f;
184         BME_Loop *l;
185         BME_CycleNode *diskbase;
186         int i, ok;
187         
188         /*Simple edge verification*/
189         for(e=bm->edges.first; e; e=e->next){
190                 if(e->v1 == e->v2) VHALT(halt);
191                 /*validate e->d1.data and e->d2.data*/
192                 if(e->d1.data != e || e->d2.data != e) VHALT(halt);
193                 /*validate e->loop->e*/
194                 if(e->loop){
195                         if(e->loop->e != e) VHALT(halt);
196                 }
197         }
198         
199         /*calculate disk cycle lengths*/
200         for(v=bm->verts.first; v; v=v->next) v->tflag1 = v->tflag2 = 0;
201         for(e=bm->edges.first; e; e=e->next){ 
202                 e->v1->tflag1++;
203                 e->v2->tflag1++;
204         }
205         /*Validate vertices and disk cycle*/
206         for(v=bm->verts.first; v; v=v->next){
207                 /*validate v->edge pointer*/
208                 if(v->tflag1){
209                         if(v->edge){
210                                 ok = BME_vert_in_edge(v->edge,v);
211                                 if(!ok) VHALT(halt);
212                                 /*validate length of disk cycle*/
213                                 diskbase = BME_disk_getpointer(v->edge, v);
214                                 ok = BME_cycle_validate(v->tflag1, diskbase);
215                                 if(!ok) VHALT(halt);
216                                 /*validate that each edge in disk cycle contains V*/
217                                 for(i=0, e=v->edge; i < v->tflag1; i++, e = BME_disk_nextedge(e,v)){
218                                         ok = BME_vert_in_edge(e, v);
219                                         if(!ok) VHALT(halt);
220                                 }
221                         }
222                         else VHALT(halt);
223                 }
224         }
225         /*validate edges*/
226         for(e=bm->edges.first; e; e=e->next){
227                 /*seperate these into BME_disk_hasedge (takes pointer to edge)*/
228                 /*search v1 disk cycle for edge*/
229                 ok = BME_disk_hasedge(e->v1,e);
230                 if(!ok) VHALT(halt);
231                 /*search v2 disk cycle for edge*/
232                 ok = BME_disk_hasedge(e->v2,e);
233                 if(!ok) VHALT(halt);
234         }
235         
236         for(e=bm->edges.first; e; e=e->next) e->tflag2 = 0; //store incident faces
237         /*Validate the loop cycle integrity.*/
238         for(f=bm->polys.first; f; f=f->next){
239                 ok = BME_cycle_length(f->loopbase);
240                 if(ok > 1){
241                         f->tflag1 = ok;
242                 }
243                 else VHALT(halt);
244                 for(i=0, l=f->loopbase; i < f->tflag1; i++, l=l->next){
245                         /*verify loop->v pointers*/
246                         ok = BME_verts_in_edge(l->v, l->next->v, l->e);
247                         if(!ok) VHALT(halt);
248                         /*verify radial node data pointer*/
249                         if(l->radial.data != l) VHALT(halt);
250                         /*validate l->e->loop poitner*/
251                         if(l->e->loop == NULL) VHALT(halt);
252                         /*validate l->f pointer*/
253                         if(l->f != f) VHALT(halt);
254                         /*see if l->e->loop is actually in radial cycle*/
255                         
256                         l->e->tflag2++;
257                  }
258         }
259         
260         /*validate length of radial cycle*/
261         for(e=bm->edges.first; e; e=e->next){
262                 if(e->loop){
263                         ok = BME_cycle_validate(e->tflag2,&(e->loop->radial));
264                         if(!ok) VHALT(halt);
265                 }
266         }
267         
268         /*validate that EIDs are within range... if not indicates corrupted mem*/
269
270         /*if we get this far, pretty safe to return 1*/
271         return 1;
272 }
273
274 /*      Currently just a convient place for a breakpoint.
275         Probably should take an error string
276 */
277 void BME_error(void){
278         printf("BME modelling error!");
279 }