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