-> More Bmesh Custom Data stuff
[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  *      The arguments are two arrays, one of type int
64  *  and another of type BME_CustomDataInit. The first array
65  *  contains the allocation size for each element pool in 
66  *  the mesh. For instance allocsize[0] contains the number
67  *  of vertices to allocate at a time for the vertex pool.
68  *
69  *  The second array contains structures describing the layout
70  *  of custom data for each element type in the mesh. So init[0]
71  *  contains the custom data layout information for vertices, init[1]
72  *  the layout information for edges and so on.
73  *
74  *  Returns -
75  *  Pointer to a Bmesh
76  *
77 */
78
79 BME_Mesh *BME_make_mesh(int allocsize[4], BME_CustomDataInit init[4])
80 {
81         /*allocate the structure*/
82         BME_Mesh *bm = MEM_callocN(sizeof(BME_Mesh),"BMesh");
83         /*allocate the memory pools for the mesh elements*/
84         bm->vpool = BME_mempool_create(sizeof(BME_Vert), allocsize[0], allocsize[0]);
85         bm->epool = BME_mempool_create(sizeof(BME_Edge), allocsize[1], allocsize[1]);
86         bm->lpool = BME_mempool_create(sizeof(BME_Loop), allocsize[2], allocsize[2]);
87         bm->ppool = BME_mempool_create(sizeof(BME_Poly), allocsize[3], allocsize[3]);
88         /*Setup custom data layers*/
89         BME_CD_Create(&bm->vdata, &init[0], allocsize[0]);
90         BME_CD_Create(&bm->edata, &init[1], allocsize[1]);
91         BME_CD_Create(&bm->ldata, &init[2], allocsize[2]);
92         BME_CD_Create(&bm->pdata, &init[3], allocsize[3]);
93         return bm;
94 }
95 /*      
96  *      BME FREE MESH
97  *
98  *      Frees a BME_Mesh structure.
99 */
100
101 void BME_free_mesh(BME_Mesh *bm)
102 {
103         BME_Vert *v;
104         BME_Edge *e;
105         BME_Loop *l;
106         BME_Poly *f;
107
108         for(v=bm->verts.first; v; v=v->next) BME_CD_free_block(&bm->vdata, &v->data);
109         for(e=bm->edges.first; e; e=e->next) BME_CD_free_block(&bm->edata, &e->data);
110         for(f=bm->polys.first; f; f=f->next){
111                 BME_CD_free_block(&bm->pdata, &f->data);
112                 l = f->loopbase;
113                 do{
114                         BME_CD_free_block(&bm->ldata, &l->data);
115                         l = l->next;
116                 }while(l!=f->loopbase);
117         }
118         /*destroy element pools*/
119         BME_mempool_destroy(bm->vpool);
120         BME_mempool_destroy(bm->epool);
121         BME_mempool_destroy(bm->ppool);
122         BME_mempool_destroy(bm->lpool);
123         /*free custom data pools*/
124         BME_CD_Free(&bm->vdata);
125         BME_CD_Free(&bm->edata);
126         BME_CD_Free(&bm->ldata);
127         BME_CD_Free(&bm->pdata);
128         MEM_freeN(bm);  
129 }
130
131 /*      
132  *      BME MODEL BEGIN AND END
133  *
134  *      These two functions represent the 'point of entry' for tools. Every BMesh tool
135  *      must begin with a call to BME_model_end() and finish with a call to BME_model_end().
136  *      No modification of mesh data is allowed except in between these two calls.
137  *
138  *  The purpose of these calls is allow for housekeeping tasks to be performed,
139  *  such as allocating/freeing scratch arrays or performing debug validation of 
140  *  the mesh structure.
141  *
142  *  Returns -
143  *  Nothing
144  *
145 */
146
147 int BME_model_begin(BME_Mesh *bm){
148         /*Initialize some scratch pointer arrays used by eulers*/
149         bm->vtar = MEM_callocN(sizeof(BME_Vert *) * 1024, "BMesh scratch vert array");
150         bm->edar = MEM_callocN(sizeof(BME_Edge *) * 1024, "BMesh scratch edge array");
151         bm->lpar = MEM_callocN(sizeof(BME_Loop *) * 1024, "BMesh scratch loop array");
152         bm->plar = MEM_callocN(sizeof(BME_Poly *) * 1024, "BMesh scratch poly array");
153
154         bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 1024;
155
156         return 1;
157 }
158
159 void BME_model_end(BME_Mesh *bm){
160         int meshok, totvert, totedge, totpoly;
161
162         totvert = BLI_countlist(&(bm->verts));
163         totedge = BLI_countlist(&(bm->edges));
164         totpoly = BLI_countlist(&(bm->polys));
165
166         if(bm->vtar) MEM_freeN(bm->vtar);
167         if(bm->edar) MEM_freeN(bm->edar);
168         if(bm->lpar) MEM_freeN(bm->lpar);
169         if(bm->plar) MEM_freeN(bm->plar);
170         
171         bm->vtar = NULL;
172         bm->edar = NULL;
173         bm->lpar = NULL;
174         bm->plar = NULL;
175         bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 0;
176         
177         
178         if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly)
179                 BME_error();
180         
181         meshok = BME_validate_mesh(bm, 1);
182         if(!meshok){
183                 BME_error();
184         }
185 }
186
187 /*      
188  *      BME VALIDATE MESH
189  *
190  *      There are several levels of validation for meshes. At the 
191  *  Euler level, some basic validation is done to local topology.
192  *  To catch more subtle problems however, BME_validate_mesh() is 
193  *  called by BME_model_end() whenever a tool is done executing.
194  *  The purpose of this function is to insure that during the course 
195  *  of tool execution that nothing has been done to invalidate the 
196  *  structure, and if it has, provide a way of reporting that so that
197  *  we can restore the proper structure from a backup. Since a full mesh
198  *  validation would be too expensive, this is presented as a compromise.
199  *
200  *      TODO 
201  *      
202  *      -Make this only part of debug builds
203  */
204
205 #define VHALT(halt) {BME_error(); if(halt) return 0;}
206
207 int BME_validate_mesh(struct BME_Mesh *bm, int halt)
208 {
209         BME_Vert *v;
210         BME_Edge *e;
211         BME_Poly *f;
212         BME_Loop *l;
213         BME_CycleNode *diskbase;
214         int i, ok;
215         
216         /*Simple edge verification*/
217         for(e=bm->edges.first; e; e=e->next){
218                 if(e->v1 == e->v2) VHALT(halt);
219                 /*validate e->d1.data and e->d2.data*/
220                 if(e->d1.data != e || e->d2.data != e) VHALT(halt);
221                 /*validate e->loop->e*/
222                 if(e->loop){
223                         if(e->loop->e != e) VHALT(halt);
224                 }
225         }
226         
227         /*calculate disk cycle lengths*/
228         for(v=bm->verts.first; v; v=v->next) v->tflag1 = v->tflag2 = 0;
229         for(e=bm->edges.first; e; e=e->next){ 
230                 e->v1->tflag1++;
231                 e->v2->tflag1++;
232         }
233         /*Validate vertices and disk cycle*/
234         for(v=bm->verts.first; v; v=v->next){
235                 /*validate v->edge pointer*/
236                 if(v->tflag1){
237                         if(v->edge){
238                                 ok = BME_vert_in_edge(v->edge,v);
239                                 if(!ok) VHALT(halt);
240                                 /*validate length of disk cycle*/
241                                 diskbase = BME_disk_getpointer(v->edge, v);
242                                 ok = BME_cycle_validate(v->tflag1, diskbase);
243                                 if(!ok) VHALT(halt);
244                                 /*validate that each edge in disk cycle contains V*/
245                                 for(i=0, e=v->edge; i < v->tflag1; i++, e = BME_disk_nextedge(e,v)){
246                                         ok = BME_vert_in_edge(e, v);
247                                         if(!ok) VHALT(halt);
248                                 }
249                         }
250                         else VHALT(halt);
251                 }
252         }
253         /*validate edges*/
254         for(e=bm->edges.first; e; e=e->next){
255                 /*seperate these into BME_disk_hasedge (takes pointer to edge)*/
256                 /*search v1 disk cycle for edge*/
257                 ok = BME_disk_hasedge(e->v1,e);
258                 if(!ok) VHALT(halt);
259                 /*search v2 disk cycle for edge*/
260                 ok = BME_disk_hasedge(e->v2,e);
261                 if(!ok) VHALT(halt);
262         }
263         
264         for(e=bm->edges.first; e; e=e->next) e->tflag2 = 0; //store incident faces
265         /*Validate the loop cycle integrity.*/
266         for(f=bm->polys.first; f; f=f->next){
267                 ok = BME_cycle_length(f->loopbase);
268                 if(ok > 1){
269                         f->tflag1 = ok;
270                 }
271                 else VHALT(halt);
272                 for(i=0, l=f->loopbase; i < f->tflag1; i++, l=l->next){
273                         /*verify loop->v pointers*/
274                         ok = BME_verts_in_edge(l->v, l->next->v, l->e);
275                         if(!ok) VHALT(halt);
276                         /*verify radial node data pointer*/
277                         if(l->radial.data != l) VHALT(halt);
278                         /*validate l->e->loop poitner*/
279                         if(l->e->loop == NULL) VHALT(halt);
280                         /*validate l->f pointer*/
281                         if(l->f != f) VHALT(halt);
282                         /*see if l->e->loop is actually in radial cycle*/
283                         
284                         l->e->tflag2++;
285                  }
286         }
287         
288         /*validate length of radial cycle*/
289         for(e=bm->edges.first; e; e=e->next){
290                 if(e->loop){
291                         ok = BME_cycle_validate(e->tflag2,&(e->loop->radial));
292                         if(!ok) VHALT(halt);
293                 }
294         }
295         
296         /*validate that EIDs are within range... if not indicates corrupted mem*/
297
298         /*if we get this far, pretty safe to return 1*/
299         return 1;
300 }
301
302 /*      Currently just a convient place for a breakpoint.
303         Probably should take an error string
304 */
305 void BME_error(void){
306         printf("BME modelling error!");
307 }