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