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