d261238d1286bf48e19439b3a8bb73e4340d3113
[blender.git] / source / blender / blenkernel / intern / BME_structure.c
1 /**
2  * BME_structure.c    jan 2007
3  *
4  *      Low level routines for manipulating the BMesh structure.
5  *
6  * $Id: BME_structure.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 <limits.h>
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_listBase.h"
39 #include "BKE_utildefines.h"
40 #include "BKE_bmesh.h"
41 #include "BLI_blenlib.h"
42 #include "BLI_linklist.h"
43 #include "BLI_ghash.h"
44
45 #include "BKE_customdata.h"
46
47 /*
48         Simple, fast memory allocator for allocating many elements of the same size.
49 */
50 typedef struct BME_mempool_chunk{
51         struct BME_mempool_chunk *next, *prev;
52         void *data;
53 }BME_mempool_chunk;
54
55 /*this is just to make things prettier*/
56 typedef struct BME_freenode{
57         struct BME_freenode *next;
58 }BME_freenode;
59
60 typedef struct BME_mempool{
61         struct ListBase chunks;
62         int esize, csize, pchunk;               /*size of elements and chunks in bytes and number of elements per chunk*/
63         struct BME_freenode     *free;          /*free element list. Interleaved into chunk datas.*/
64 }BME_mempool;
65
66 BME_mempool *BME_mempool_create(int esize, int tote, int pchunk)
67 {       BME_mempool  *pool = NULL;
68         BME_freenode *lasttail = NULL, *curnode = NULL;
69         int i,j, maxchunks;
70         char *addr;
71
72         /*allocate the pool structure*/
73         pool = MEM_mallocN(sizeof(BME_mempool),"memory pool");
74         pool->esize = esize;
75         pool->pchunk = pchunk;  
76         pool->csize = esize * pchunk;
77         pool->chunks.first = pool->chunks.last = NULL;
78         
79         maxchunks = tote / pchunk;
80         
81         /*allocate the actual chunks*/
82         for(i=0; i < maxchunks; i++){
83                 BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk");
84                 mpchunk->next = mpchunk->prev = NULL;
85                 mpchunk->data = MEM_mallocN(pool->csize, "BME Mempool Chunk Data");
86                 BLI_addtail(&(pool->chunks), mpchunk);
87                 
88                 if(i==0) pool->free = mpchunk->data; /*start of the list*/
89                 /*loop through the allocated data, building the pointer structures*/
90                 for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
91                         curnode = ((BME_freenode*)addr);
92                         addr += pool->esize;
93                         curnode->next = (BME_freenode*)addr;
94                 }
95                 /*final pointer in the previously allocated chunk is wrong.*/
96                 if(lasttail) lasttail->next = mpchunk->data;
97                 /*set the end of this chunks memory to the new tail for next iteration*/
98                 lasttail = curnode;
99         }
100         /*terminate the list*/
101         curnode->next = NULL;
102         return pool;
103 }
104
105 void *BME_mempool_alloc(BME_mempool *pool){
106         void *retval=NULL;
107         BME_freenode *curnode=NULL;
108         char *addr=NULL;
109         int j;
110
111         if(!(pool->free)){
112                 /*need to allocate a new chunk*/
113                 BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk");
114                 mpchunk->next = mpchunk->prev = NULL;
115                 mpchunk->data = MEM_mallocN(pool->csize, "BME_Mempool Chunk Data");
116                 BLI_addtail(&(pool->chunks), mpchunk);
117
118                 pool->free = mpchunk->data; /*start of the list*/
119                 for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
120                         curnode = ((BME_freenode*)addr);
121                         addr += pool->esize;
122                         curnode->next = (BME_freenode*)addr;
123                 }
124                 curnode->next = NULL; /*terminate the list*/
125         }
126
127         retval = pool->free;
128         pool->free = pool->free->next;
129         //memset(retval, 0, pool->esize);
130         return retval;
131 }
132
133 void BME_mempool_free(BME_mempool *pool, void *addr){ //doesnt protect against double frees, dont be stupid!
134         BME_freenode *newhead = addr;
135         newhead->next = pool->free;
136         pool->free = newhead;
137 }
138 void BME_mempool_destroy(BME_mempool *pool)
139 {
140         BME_mempool_chunk *mpchunk=NULL;
141         for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) MEM_freeN(mpchunk->data);
142         BLI_freelistN(&(pool->chunks));
143         MEM_freeN(pool);
144 }
145 /**
146  *      MISC utility functions.
147  *
148  */
149  
150 int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
151         if(e->v1 == v || e->v2 == v) return 1;
152         return 0;
153 }
154 int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
155         if(e->v1 == v1 && e->v2 == v2) return 1;
156         else if(e->v1 == v2 && e->v2 == v1) return 1;
157         return 0;
158 }
159
160 BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){      
161         if(e->v1 == v) return e->v2;
162         else if(e->v2 == v) return e->v1;
163         return NULL;
164 }
165
166 int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
167         if(e->v1 == orig){ 
168                 e->v1 = new;
169                 e->d1.next = NULL;
170                 e->d1.prev = NULL;
171                 return 1;
172         }
173         else if(e->v2 == orig){
174                 e->v2 = new;
175                 e->d2.next = NULL;
176                 e->d2.prev = NULL;
177                 return 1;
178         }
179         return 0;
180 }
181
182 /**
183  *      ALLOCATION/DEALLOCATION FUNCTIONS
184  */
185
186 BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
187         BME_Vert *v=NULL;
188         v = BME_mempool_alloc(bm->vpool);
189         v->next = v->prev = NULL;
190         v->EID = bm->nextv;
191         v->co[0] = v->co[1] = v->co[2] = 0.0f;
192         v->no[0] = v->no[1] = v->no[2] = 0.0f;
193         v->edge = NULL;
194         v->data = NULL;
195         v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
196         v->flag = v->h = 0;
197         v->bweight = 0.0f;
198         BLI_addtail(&(bm->verts), v);
199         bm->nextv++;
200         bm->totvert++;
201
202         if(example)
203                 VECCOPY(v->co,example->co);
204         //if(example)
205         //      CustomData_em_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
206         //else
207         //      CustomData_em_set_default(&bm->vdata, &v->data);
208
209         return v;
210 }
211 BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
212         BME_Edge *e=NULL;
213         e = BME_mempool_alloc(bm->epool);
214         e->next = e->prev = NULL;
215         e->EID = bm->nexte;
216         e->v1 = v1;
217         e->v2 = v2;
218         e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
219         e->d1.data = e;
220         e->d2.data = e;
221         e->loop = NULL;
222         e->data = NULL;
223         e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
224         e->flag = e->h = 0;
225         e->crease = e->bweight = 0.0f;
226         bm->nexte++;
227         bm->totedge++;
228         BLI_addtail(&(bm->edges), e);
229         
230         //if(example)
231         //      CustomData_em_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
232         //else
233         //      CustomData_em_set_default(&bm->edata, &e->data);
234
235
236         return e;
237 }
238 BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
239         /*allocate a BME_Loop and add it to the loophash*/
240         BME_Loop *l=NULL;
241         l = BME_mempool_alloc(bm->lpool);
242         l->next = l->prev = NULL;
243         l->EID = bm->nextl;
244         l->radial.next = l->radial.prev = NULL;
245         l->radial.data = l;
246         l->v = v;
247         l->e = e;
248         l->f = f;
249         l->data = NULL;
250         l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
251         l->flag = l->h = 0; //stupid waste!
252         bm->nextl++;
253         bm->totloop++;
254         
255
256 /*      if(example)
257                 BME_CustomData_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
258         else
259                 BME_CustomData_set_default(&bm->ldata, &l->data);
260 */
261         return l;
262 }
263
264 BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
265         BME_Poly *f = NULL;
266         f = BME_mempool_alloc(bm->ppool);
267         f->next = f->prev = NULL;
268         f->EID = bm->nextp;
269         f->loopbase = NULL;
270         f->len = 0;
271         f->data = NULL;
272         f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
273         f->flag = f->h = f->mat_nr;
274         BLI_addtail(&(bm->polys),f);
275         bm->nextp++;
276         bm->totpoly++;
277
278         //if(example)
279         //      CustomData_em_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
280         //else
281         //      CustomData_em_set_default(&bm->pdata, &f->data);
282
283
284         return f;
285 }
286
287 /*      free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
288         data is added though these will be needed.
289 */
290 void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
291         bm->totvert--;
292         //CustomData_em_free_block(&bm->vdata, &v->data);
293         BME_mempool_free(bm->vpool, v);
294 }
295 void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
296         bm->totedge--;
297         //CustomData_em_free_block(&bm->edata, &e->data);
298         BME_mempool_free(bm->epool, e);
299 }
300 void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
301         bm->totpoly--;
302         //CustomData_em_free_block(&bm->pdata, &f->data);
303         BME_mempool_free(bm->ppool, f);
304 }
305 void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
306         bm->totloop--;
307         //CustomData_em_free_block(&bm->ldata, &l->data);
308         BME_mempool_free(bm->lpool, l);
309 }
310 /**
311  *      BMESH CYCLES
312  *
313  *      Cycles are circular doubly linked lists that form the basis of adjacency
314  *      information in the BME modeller. Full adjacency relations can be derived
315  *      from examining these cycles very quickly. Although each cycle is a double
316  *  circular linked list, each one is considered to have a 'base' or 'head',
317  *      and care must be taken by Euler code when modifying the contents of a cycle.
318  *
319  *      The contents of this file are split into two parts. First there are the 
320  *      BME_cycle family of functions which are generic circular double linked list 
321  *      procedures. The second part contains higher level procedures for supporting 
322  *      modification of specific cycle types.
323  *
324  *      The three cycles explicitly stored in the BMesh data structure are as follows:
325  *
326  *      1: The Disk Cycle - A circle of edges around a vertex
327  *     Base: vertex->edge pointer.
328  *         
329  *     This cycle is the most complicated in terms of its structure. Each BME_Edge contains     
330  *         two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
331  *         of each of its vertices. However for any given vertex it may be the first in some edges
332  *         in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
333  *         some nice utilities for navigating disk cycles in a way that hides this detail from the 
334  *         tool writer.
335  *
336  *              Note that the disk cycle is completley independant from face data. One advantage of this
337  *              is that wire edges are fully integrated into the topology database. Another is that the 
338  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
339  *
340  *              Functions relating to this cycle:
341  *              
342  *                      BME_disk_append_edge
343  *                      BME_disk_remove_edge
344  *                      BME_disk_nextedge
345  *                      BME_disk_getpointer
346  *
347  *      2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
348  *         Base: edge->loop->radial structure.
349  *
350  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
351  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory 
352  *              to store non-manifold conditions since BMesh does not keep track of region/shell
353  *              information.
354  *              
355  *              Functions relating to this cycle:
356  *                      
357  *                      BME_radial_append
358  *                      BME_radial_remove_loop
359  *                      BME_radial_nextloop
360  *                      BME_radial_find_face
361  *              
362  *
363  *      3: The Loop Cycle - A circle of face edges around a polygon.
364  *     Base: polygon->loopbase.
365  *
366  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
367  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is 
368  *     not oriented to the faces editedges. 
369  *
370  *              Functions relating to this cycle:
371  *              
372  *                      BME_cycle_XXX family of functions.
373  *
374  *      
375  *      Note that the order of elements in all cycles except the loop cycle is undefined. This 
376  *  leads to slightly increased seek time for deriving some adjacency relations, however the 
377  *  advantage is that no intrinsic properties of the data structures are dependant upon the 
378  *  cycle order and all non-manifold conditions are represented trivially.
379  *
380 */
381  
382  
383 void BME_cycle_append(void *h, void *nt)
384 {
385         BME_CycleNode *oldtail, *head, *newtail;
386         
387         head = (BME_CycleNode*)h;
388         newtail = (BME_CycleNode*)nt;
389         
390         if(head->next == NULL){
391                 head->next = newtail;
392                 head->prev = newtail;
393                 newtail->next = head;
394                 newtail->prev = head;
395         }
396         else{
397                 oldtail = head->prev;
398                 oldtail->next = newtail;
399                 newtail->next = head;
400                 newtail->prev = oldtail;
401                 head->prev = newtail;
402                 
403         }
404 }
405
406 /**
407  *                      BME_cycle_length
408  *
409  *      Count the nodes in a cycle.
410  *
411  *  Returns -
412  *      Integer
413  */
414
415 int BME_cycle_length(void *h){
416         
417         int len = 0;
418         BME_CycleNode *head, *curnode;
419         head = (BME_CycleNode*)h;
420         
421         if(head){ 
422                 len = 1;
423                 for(curnode = head->next; curnode != head; curnode=curnode->next){ 
424                         if(len == INT_MAX){ //check for infinite loop/corrupted cycle
425                                         return -1;
426                         }
427                         len++;
428                 }
429         }
430         return len;
431 }
432
433
434 /**
435  *                      BME_cycle_remove
436  *
437  *      Removes a node from a cycle.
438  *
439  *  Returns -
440  *      1 for success, 0 for failure.
441  */
442
443 int BME_cycle_remove(void *h, void *remn)
444 {
445         int i, len;
446         BME_CycleNode *head, *remnode, *curnode;
447         
448         head = (BME_CycleNode*)h;
449         remnode = (BME_CycleNode*)remn;
450         len = BME_cycle_length(h);
451         
452         if(len == 1 && head == remnode){
453                 head->next = NULL;
454                 head->prev = NULL;
455                 return 1;
456         }
457         else{
458                 for(i=0, curnode = head; i < len; curnode = curnode->next){
459                         if(curnode == remnode){
460                                 remnode->prev->next = remnode->next;
461                                 remnode->next->prev = remnode->prev;
462                                 /*zero out remnode pointers, important!*/
463                                 //remnode->next = NULL;
464                                 //remnode->prev = NULL;
465                                 return 1;
466                 
467                         }
468                 }
469         }
470         return 0;
471 }
472
473 /**
474  *                      BME_cycle_validate
475  *
476  *      Validates a cycle. Takes as an argument the expected length of the cycle and
477  *      a pointer to the cycle head or base.
478  *
479  *
480  *  Returns -
481  *      1 for success, 0 for failure.
482  */
483
484 int BME_cycle_validate(int len, void *h){
485         int i;
486         BME_CycleNode *curnode, *head;
487         head = (BME_CycleNode*)h;
488         
489         /*forward validation*/
490         for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
491         if(curnode != head) return 0;
492         
493         /*reverse validation*/
494         for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
495         if(curnode != head) return 0;
496         
497         return 1;
498 }
499
500 /*Begin Disk Cycle routines*/
501
502 /**
503  *                      BME_disk_nextedge
504  *
505  *      Find the next edge in a disk cycle
506  *
507  *  Returns -
508  *      Pointer to the next edge in the disk cycle for the vertex v.
509  */
510  
511 BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
512 {       
513         if(BME_vert_in_edge(e, v)){
514                 if(e->v1 == v) return e->d1.next->data;
515                 else if(e->v2 == v) return e->d2.next->data;
516         }
517         return NULL;
518 }
519
520 /**
521  *                      BME_disk_getpointer
522  *
523  *      Given an edge and one of its vertices, find the apporpriate CycleNode
524  *
525  *  Returns -
526  *      Pointer to BME_CycleNode.
527  */
528 BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
529         /*returns pointer to the cycle node for the appropriate vertex in this disk*/
530         if(e->v1 == v) return &(e->d1);
531         else if (e->v2 == v) return &(e->d2);
532         return NULL;
533 }
534
535 /**
536  *                      BME_disk_append_edge
537  *
538  *      Appends edge to the end of a vertex disk cycle.
539  *
540  *  Returns -
541  *      1 for success, 0 for failure
542  */
543
544 int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
545
546         
547         BME_CycleNode *base, *tail;
548         
549         if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
550         
551         /*check for loose vert first*/
552         if(v->edge == NULL){
553                 v->edge = e;
554                 base = tail = BME_disk_getpointer(e, v);
555                 BME_cycle_append(base, tail); /*circular reference is ok!*/
556                 return 1;
557         }
558         
559         /*insert e at the end of disk cycle and make it the new v->edge*/
560         base = BME_disk_getpointer(v->edge, v);
561         tail = BME_disk_getpointer(e, v);
562         BME_cycle_append(base, tail);
563         return 1;
564 }
565
566 /**
567  *                      BME_disk_remove_edge
568  *
569  *      Removes an edge from a disk cycle. If the edge to be removed is
570  *      at the base of the cycle, the next edge becomes the new base.
571  *
572  *
573  *  Returns -
574  *      Nothing
575  */
576
577 void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
578 {
579         BME_CycleNode *base, *remnode;
580         BME_Edge *newbase;
581         int len;
582         
583         base = BME_disk_getpointer(v->edge, v);
584         remnode = BME_disk_getpointer(e, v);
585         
586         /*first deal with v->edge pointer...*/
587         len = BME_cycle_length(base);
588         if(len == 1) newbase = NULL;
589         else if(v->edge == e) newbase = base->next-> data;
590         else newbase = v->edge;
591         
592         /*remove and rebase*/
593         BME_cycle_remove(base, remnode);
594         v->edge = newbase;
595 }
596
597 /**
598  *                      BME_disk_next_edgeflag
599  *
600  *      Searches the disk cycle of v, starting with e, for the 
601  *  next edge that has either eflag or tflag.
602  *
603  *      BME_Edge pointer.
604  */
605
606 BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
607         
608         BME_CycleNode *diskbase;
609         BME_Edge *curedge;
610         int len, ok;
611         
612         if(eflag && tflag) return NULL;
613         
614         ok = BME_vert_in_edge(e,v);
615         if(ok){
616                 diskbase = BME_disk_getpointer(e, v);
617                 len = BME_cycle_length(diskbase);
618                 curedge = BME_disk_nextedge(e,v);
619                 while(curedge != e){
620                         if(tflag){
621                                 if(curedge->tflag1 == tflag) return curedge;
622                         }
623                         else if(eflag){
624                                 if(curedge->eflag1 == eflag) return curedge;
625                         }
626                         curedge = BME_disk_nextedge(curedge, v);
627                 }
628         }
629         return NULL;
630 }
631
632 /**
633  *                      BME_disk_count_edgeflag
634  *
635  *      Counts number of edges in this verts disk cycle which have 
636  *      either eflag or tflag (but not both!)
637  *
638  *  Returns -
639  *      Integer.
640  */
641
642 int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
643         BME_CycleNode *diskbase;
644         BME_Edge *curedge;
645         int i, len=0, count=0;
646         
647         if(v->edge){
648                 if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
649                 diskbase = BME_disk_getpointer(v->edge, v);
650                 len = BME_cycle_length(diskbase);
651                 
652                 for(i = 0, curedge=v->edge; i<len; i++){
653                         if(tflag){
654                                 if(curedge->tflag1 == tflag) count++;
655                         }
656                         else if(eflag){
657                                 if(curedge->eflag1 == eflag) count++;
658                         }
659                         curedge = BME_disk_nextedge(curedge, v);
660                 }
661         }
662         return count;
663 }
664
665 int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
666         BME_CycleNode *diskbase;
667         BME_Edge *curedge;
668         int i, len=0;
669         
670         if(v->edge){
671                 diskbase = BME_disk_getpointer(v->edge,v);
672                 len = BME_cycle_length(diskbase);
673                 
674                 for(i = 0, curedge=v->edge; i<len; i++){
675                         if(curedge == e) return 1;
676                         else curedge=BME_disk_nextedge(curedge, v);
677                 }
678         }
679         return 0;
680 }
681 /*end disk cycle routines*/
682
683 BME_Loop *BME_radial_nextloop(BME_Loop *l){
684         return (BME_Loop*)(l->radial.next->data);
685 }
686
687 void BME_radial_append(BME_Edge *e, BME_Loop *l){
688         if(e->loop == NULL) e->loop = l;
689         BME_cycle_append(&(e->loop->radial), &(l->radial));
690 }
691
692 void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
693 {
694         BME_Loop *newbase;
695         int len;
696         
697         /*deal with edge->loop pointer*/
698         len = BME_cycle_length(&(e->loop->radial));
699         if(len == 1) newbase = NULL;
700         else if(e->loop == l) newbase = e->loop->radial.next->data;
701         else newbase = e->loop;
702         
703         /*remove and rebase*/
704         BME_cycle_remove(&(e->loop->radial), &(l->radial));
705         e->loop = newbase;
706 }
707
708 int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
709 {
710                 
711         BME_Loop *curloop;
712         int i, len;
713         
714         len = BME_cycle_length(&(e->loop->radial));
715         for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
716                 if(curloop->f == f) return 1;
717         }
718         return 0;
719 }
720
721 struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
722         BME_Loop *l;
723         int i, len;
724         
725         len = BME_cycle_length(f->loopbase);
726         for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
727                 if (l->v == v) return l;
728         }
729         return NULL;
730 }