-> Fix for last few commits
[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         //if(example)
199         //      CustomData_em_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
200         //else
201         //      CustomData_em_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         //      CustomData_em_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
226         //else
227         //      CustomData_em_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         /*allocate a BME_Loop and add it to the loophash*/
234         BME_Loop *l=NULL;
235         l = BME_mempool_alloc(bm->lpool);
236         l->next = l->prev = NULL;
237         l->EID = bm->nextl;
238         l->radial.next = l->radial.prev = NULL;
239         l->radial.data = l;
240         l->v = v;
241         l->e = e;
242         l->f = f;
243         l->data = NULL;
244         l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
245         l->flag = l->h = 0; //stupid waste!
246         bm->nextl++;
247         bm->totloop++;
248         
249
250 /*      if(example)
251                 BME_CustomData_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
252         else
253                 BME_CustomData_set_default(&bm->ldata, &l->data);
254 */
255         return l;
256 }
257
258 BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
259         BME_Poly *f = NULL;
260         f = BME_mempool_alloc(bm->ppool);
261         f->next = f->prev = NULL;
262         f->EID = bm->nextp;
263         f->loopbase = NULL;
264         f->len = 0;
265         f->data = NULL;
266         f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
267         f->flag = f->h = f->mat_nr;
268         BLI_addtail(&(bm->polys),f);
269         bm->nextp++;
270         bm->totpoly++;
271
272         //if(example)
273         //      CustomData_em_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
274         //else
275         //      CustomData_em_set_default(&bm->pdata, &f->data);
276
277
278         return f;
279 }
280
281 /*      free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
282         data is added though these will be needed.
283 */
284 void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
285         bm->totvert--;
286         //CustomData_em_free_block(&bm->vdata, &v->data);
287         BME_mempool_free(bm->vpool, v);
288 }
289 void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
290         bm->totedge--;
291         //CustomData_em_free_block(&bm->edata, &e->data);
292         BME_mempool_free(bm->epool, e);
293 }
294 void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
295         bm->totpoly--;
296         //CustomData_em_free_block(&bm->pdata, &f->data);
297         BME_mempool_free(bm->ppool, f);
298 }
299 void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
300         bm->totloop--;
301         //CustomData_em_free_block(&bm->ldata, &l->data);
302         BME_mempool_free(bm->lpool, l);
303 }
304 /**
305  *      BMESH CYCLES
306  *
307  *      Cycles are circular doubly linked lists that form the basis of adjacency
308  *      information in the BME modeller. Full adjacency relations can be derived
309  *      from examining these cycles very quickly. Although each cycle is a double
310  *  circular linked list, each one is considered to have a 'base' or 'head',
311  *      and care must be taken by Euler code when modifying the contents of a cycle.
312  *
313  *      The contents of this file are split into two parts. First there are the 
314  *      BME_cycle family of functions which are generic circular double linked list 
315  *      procedures. The second part contains higher level procedures for supporting 
316  *      modification of specific cycle types.
317  *
318  *      The three cycles explicitly stored in the BMesh data structure are as follows:
319  *
320  *      1: The Disk Cycle - A circle of edges around a vertex
321  *     Base: vertex->edge pointer.
322  *         
323  *     This cycle is the most complicated in terms of its structure. Each BME_Edge contains     
324  *         two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
325  *         of each of its vertices. However for any given vertex it may be the first in some edges
326  *         in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
327  *         some nice utilities for navigating disk cycles in a way that hides this detail from the 
328  *         tool writer.
329  *
330  *              Note that the disk cycle is completley independant from face data. One advantage of this
331  *              is that wire edges are fully integrated into the topology database. Another is that the 
332  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
333  *
334  *              Functions relating to this cycle:
335  *              
336  *                      BME_disk_append_edge
337  *                      BME_disk_remove_edge
338  *                      BME_disk_nextedge
339  *                      BME_disk_getpointer
340  *
341  *      2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
342  *         Base: edge->loop->radial structure.
343  *
344  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
345  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory 
346  *              to store non-manifold conditions since BMesh does not keep track of region/shell
347  *              information.
348  *              
349  *              Functions relating to this cycle:
350  *                      
351  *                      BME_radial_append
352  *                      BME_radial_remove_loop
353  *                      BME_radial_nextloop
354  *                      BME_radial_find_face
355  *              
356  *
357  *      3: The Loop Cycle - A circle of face edges around a polygon.
358  *     Base: polygon->loopbase.
359  *
360  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
361  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is 
362  *     not oriented to the faces editedges. 
363  *
364  *              Functions relating to this cycle:
365  *              
366  *                      BME_cycle_XXX family of functions.
367  *
368  *      
369  *      Note that the order of elements in all cycles except the loop cycle is undefined. This 
370  *  leads to slightly increased seek time for deriving some adjacency relations, however the 
371  *  advantage is that no intrinsic properties of the data structures are dependant upon the 
372  *  cycle order and all non-manifold conditions are represented trivially.
373  *
374 */
375  
376  
377 void BME_cycle_append(void *h, void *nt)
378 {
379         BME_CycleNode *oldtail, *head, *newtail;
380         
381         head = (BME_CycleNode*)h;
382         newtail = (BME_CycleNode*)nt;
383         
384         if(head->next == NULL){
385                 head->next = newtail;
386                 head->prev = newtail;
387                 newtail->next = head;
388                 newtail->prev = head;
389         }
390         else{
391                 oldtail = head->prev;
392                 oldtail->next = newtail;
393                 newtail->next = head;
394                 newtail->prev = oldtail;
395                 head->prev = newtail;
396                 
397         }
398 }
399
400 /**
401  *                      BME_cycle_length
402  *
403  *      Count the nodes in a cycle.
404  *
405  *  Returns -
406  *      Integer
407  */
408
409 int BME_cycle_length(void *h){
410         
411         int len = 0;
412         BME_CycleNode *head, *curnode;
413         head = (BME_CycleNode*)h;
414         
415         if(head){ 
416                 len = 1;
417                 for(curnode = head->next; curnode != head; curnode=curnode->next){ 
418                         if(len == INT_MAX){ //check for infinite loop/corrupted cycle
419                                         return -1;
420                         }
421                         len++;
422                 }
423         }
424         return len;
425 }
426
427
428 /**
429  *                      BME_cycle_remove
430  *
431  *      Removes a node from a cycle.
432  *
433  *  Returns -
434  *      1 for success, 0 for failure.
435  */
436
437 int BME_cycle_remove(void *h, void *remn)
438 {
439         int i, len;
440         BME_CycleNode *head, *remnode, *curnode;
441         
442         head = (BME_CycleNode*)h;
443         remnode = (BME_CycleNode*)remn;
444         len = BME_cycle_length(h);
445         
446         if(len == 1 && head == remnode){
447                 head->next = NULL;
448                 head->prev = NULL;
449                 return 1;
450         }
451         else{
452                 for(i=0, curnode = head; i < len; curnode = curnode->next){
453                         if(curnode == remnode){
454                                 remnode->prev->next = remnode->next;
455                                 remnode->next->prev = remnode->prev;
456                                 /*zero out remnode pointers, important!*/
457                                 //remnode->next = NULL;
458                                 //remnode->prev = NULL;
459                                 return 1;
460                 
461                         }
462                 }
463         }
464         return 0;
465 }
466
467 /**
468  *                      BME_cycle_validate
469  *
470  *      Validates a cycle. Takes as an argument the expected length of the cycle and
471  *      a pointer to the cycle head or base.
472  *
473  *
474  *  Returns -
475  *      1 for success, 0 for failure.
476  */
477
478 int BME_cycle_validate(int len, void *h){
479         int i;
480         BME_CycleNode *curnode, *head;
481         head = (BME_CycleNode*)h;
482         
483         /*forward validation*/
484         for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
485         if(curnode != head) return 0;
486         
487         /*reverse validation*/
488         for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
489         if(curnode != head) return 0;
490         
491         return 1;
492 }
493
494 /*Begin Disk Cycle routines*/
495
496 /**
497  *                      BME_disk_nextedge
498  *
499  *      Find the next edge in a disk cycle
500  *
501  *  Returns -
502  *      Pointer to the next edge in the disk cycle for the vertex v.
503  */
504  
505 BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
506 {       
507         if(BME_vert_in_edge(e, v)){
508                 if(e->v1 == v) return e->d1.next->data;
509                 else if(e->v2 == v) return e->d2.next->data;
510         }
511         return NULL;
512 }
513
514 /**
515  *                      BME_disk_getpointer
516  *
517  *      Given an edge and one of its vertices, find the apporpriate CycleNode
518  *
519  *  Returns -
520  *      Pointer to BME_CycleNode.
521  */
522 BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
523         /*returns pointer to the cycle node for the appropriate vertex in this disk*/
524         if(e->v1 == v) return &(e->d1);
525         else if (e->v2 == v) return &(e->d2);
526         return NULL;
527 }
528
529 /**
530  *                      BME_disk_append_edge
531  *
532  *      Appends edge to the end of a vertex disk cycle.
533  *
534  *  Returns -
535  *      1 for success, 0 for failure
536  */
537
538 int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
539
540         
541         BME_CycleNode *base, *tail;
542         
543         if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
544         
545         /*check for loose vert first*/
546         if(v->edge == NULL){
547                 v->edge = e;
548                 base = tail = BME_disk_getpointer(e, v);
549                 BME_cycle_append(base, tail); /*circular reference is ok!*/
550                 return 1;
551         }
552         
553         /*insert e at the end of disk cycle and make it the new v->edge*/
554         base = BME_disk_getpointer(v->edge, v);
555         tail = BME_disk_getpointer(e, v);
556         BME_cycle_append(base, tail);
557         return 1;
558 }
559
560 /**
561  *                      BME_disk_remove_edge
562  *
563  *      Removes an edge from a disk cycle. If the edge to be removed is
564  *      at the base of the cycle, the next edge becomes the new base.
565  *
566  *
567  *  Returns -
568  *      Nothing
569  */
570
571 void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
572 {
573         BME_CycleNode *base, *remnode;
574         BME_Edge *newbase;
575         int len;
576         
577         base = BME_disk_getpointer(v->edge, v);
578         remnode = BME_disk_getpointer(e, v);
579         
580         /*first deal with v->edge pointer...*/
581         len = BME_cycle_length(base);
582         if(len == 1) newbase = NULL;
583         else if(v->edge == e) newbase = base->next-> data;
584         else newbase = v->edge;
585         
586         /*remove and rebase*/
587         BME_cycle_remove(base, remnode);
588         v->edge = newbase;
589 }
590
591 /**
592  *                      BME_disk_next_edgeflag
593  *
594  *      Searches the disk cycle of v, starting with e, for the 
595  *  next edge that has either eflag or tflag.
596  *
597  *      BME_Edge pointer.
598  */
599
600 BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
601         
602         BME_CycleNode *diskbase;
603         BME_Edge *curedge;
604         int len, ok;
605         
606         if(eflag && tflag) return NULL;
607         
608         ok = BME_vert_in_edge(e,v);
609         if(ok){
610                 diskbase = BME_disk_getpointer(e, v);
611                 len = BME_cycle_length(diskbase);
612                 curedge = BME_disk_nextedge(e,v);
613                 while(curedge != e){
614                         if(tflag){
615                                 if(curedge->tflag1 == tflag) return curedge;
616                         }
617                         else if(eflag){
618                                 if(curedge->eflag1 == eflag) return curedge;
619                         }
620                         curedge = BME_disk_nextedge(curedge, v);
621                 }
622         }
623         return NULL;
624 }
625
626 /**
627  *                      BME_disk_count_edgeflag
628  *
629  *      Counts number of edges in this verts disk cycle which have 
630  *      either eflag or tflag (but not both!)
631  *
632  *  Returns -
633  *      Integer.
634  */
635
636 int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
637         BME_CycleNode *diskbase;
638         BME_Edge *curedge;
639         int i, len=0, count=0;
640         
641         if(v->edge){
642                 if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
643                 diskbase = BME_disk_getpointer(v->edge, v);
644                 len = BME_cycle_length(diskbase);
645                 
646                 for(i = 0, curedge=v->edge; i<len; i++){
647                         if(tflag){
648                                 if(curedge->tflag1 == tflag) count++;
649                         }
650                         else if(eflag){
651                                 if(curedge->eflag1 == eflag) count++;
652                         }
653                         curedge = BME_disk_nextedge(curedge, v);
654                 }
655         }
656         return count;
657 }
658
659 int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
660         BME_CycleNode *diskbase;
661         BME_Edge *curedge;
662         int i, len=0;
663         
664         if(v->edge){
665                 diskbase = BME_disk_getpointer(v->edge,v);
666                 len = BME_cycle_length(diskbase);
667                 
668                 for(i = 0, curedge=v->edge; i<len; i++){
669                         if(curedge == e) return 1;
670                         else curedge=BME_disk_nextedge(curedge, v);
671                 }
672         }
673         return 0;
674 }
675 /*end disk cycle routines*/
676
677 BME_Loop *BME_radial_nextloop(BME_Loop *l){
678         return (BME_Loop*)(l->radial.next->data);
679 }
680
681 void BME_radial_append(BME_Edge *e, BME_Loop *l){
682         if(e->loop == NULL) e->loop = l;
683         BME_cycle_append(&(e->loop->radial), &(l->radial));
684 }
685
686 void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
687 {
688         BME_Loop *newbase;
689         int len;
690         
691         /*deal with edge->loop pointer*/
692         len = BME_cycle_length(&(e->loop->radial));
693         if(len == 1) newbase = NULL;
694         else if(e->loop == l) newbase = e->loop->radial.next->data;
695         else newbase = e->loop;
696         
697         /*remove and rebase*/
698         BME_cycle_remove(&(e->loop->radial), &(l->radial));
699         e->loop = newbase;
700 }
701
702 int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
703 {
704                 
705         BME_Loop *curloop;
706         int i, len;
707         
708         len = BME_cycle_length(&(e->loop->radial));
709         for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
710                 if(curloop->f == f) return 1;
711         }
712         return 0;
713 }
714
715 struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
716         BME_Loop *l;
717         int i, len;
718         
719         len = BME_cycle_length(f->loopbase);
720         for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
721                 if (l->v == v) return l;
722         }
723         return NULL;
724 }