ca2811adff03175938028982e3257c95008c0742
[blender-staging.git] / source / blender / bmesh / intern / bmesh_structure.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  * about this.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18  *
19  * The Original Code is Copyright (C) 2007 Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Geoffrey Bantle.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file blender/bmesh/intern/bmesh_structure.c
30  *  \ingroup bmesh
31  *
32  * Low level routines for manipulating the BM structure.
33  */
34
35 #include <limits.h>
36 #include <stdlib.h>
37 #include <stdio.h>
38 #include <string.h>
39
40 #include "MEM_guardedalloc.h"
41
42 #include "DNA_listBase.h"
43 #include "BKE_utildefines.h"
44 #include "bmesh.h"
45 #include "bmesh_private.h"
46 #include "BLI_linklist.h"
47 #include "BLI_ghash.h"
48
49 /**
50  *      MISC utility functions.
51  *
52  */
53  
54 int bmesh_vert_in_edge(BMEdge *e, BMVert *v)
55 {
56         if (e->v1 == v || e->v2 == v) return TRUE;
57         return FALSE;
58 }
59 int bmesh_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
60 {
61         if (e->v1 == v1 && e->v2 == v2) return TRUE;
62         else if (e->v1 == v2 && e->v2 == v1) return TRUE;
63         return FALSE;
64 }
65
66 BMVert *bmesh_edge_getothervert(BMEdge *e, BMVert *v) {
67         if (e->v1 == v) {
68                 return e->v2;
69         }
70         else if (e->v2 == v) {
71                 return e->v1;
72         }
73         return NULL;
74 }
75
76 int bmesh_edge_swapverts(BMEdge *e, BMVert *orig, BMVert *newv)
77 {
78         if (e->v1 == orig) {
79                 e->v1 = newv;
80                 e->dlink1.next = e->dlink1.prev = NULL;
81                 return TRUE;
82         }
83         else if (e->v2 == orig) {
84                 e->v2 = newv;
85                 e->dlink2.next = e->dlink2.prev = NULL;
86                 return TRUE;
87         }
88         return FALSE;
89 }
90
91 /**
92  *      BMESH CYCLES
93  * (this is somewhat outdate, though bits of its API are still used) - joeedh
94  *
95  *      Cycles are circular doubly linked lists that form the basis of adjacency
96  *      information in the BME modeller. Full adjacency relations can be derived
97  *      from examining these cycles very quickly. Although each cycle is a double
98  *  circular linked list, each one is considered to have a 'base' or 'head',
99  *      and care must be taken by Euler code when modifying the contents of a cycle.
100  *
101  *      The contents of this file are split into two parts. First there are the
102  *      bmesh_cycle family of functions which are generic circular double linked list
103  *      procedures. The second part contains higher level procedures for supporting
104  *      modification of specific cycle types.
105  *
106  *      The three cycles explicitly stored in the BM data structure are as follows:
107  *
108  *      1: The Disk Cycle - A circle of edges around a vertex
109  *     Base: vertex->edge pointer.
110  *
111  *     This cycle is the most complicated in terms of its structure. Each bmesh_Edge contains
112  *         two bmesh_CycleNode structures to keep track of that edge's membership in the disk cycle
113  *         of each of its vertices. However for any given vertex it may be the first in some edges
114  *         in its disk cycle and the second for others. The bmesh_disk_XXX family of functions contain
115  *         some nice utilities for navigating disk cycles in a way that hides this detail from the
116  *         tool writer.
117  *
118  *              Note that the disk cycle is completley independant from face data. One advantage of this
119  *              is that wire edges are fully integrated into the topology database. Another is that the
120  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
121  *
122  *              Functions relating to this cycle:
123  *
124  *                      bmesh_disk_append_edge
125  *                      bmesh_disk_remove_edge
126  *                      bmesh_disk_nextedge
127  *                      bmesh_disk_getpointer
128  *
129  *      2: The Radial Cycle - A circle of face edges (bmesh_Loop) around an edge
130  *         Base: edge->l->radial structure.
131  *
132  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
133  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory
134  *              to store non-manifold conditions since BM does not keep track of region/shell
135  *              information.
136  *
137  *              Functions relating to this cycle:
138  *
139  *                      bmesh_radial_append
140  *                      bmesh_radial_remove_loop
141  *                      bmesh_radial_nextloop
142  *                      bmesh_radial_find_face
143  *
144  *
145  *      3: The Loop Cycle - A circle of face edges around a polygon.
146  *     Base: polygon->lbase.
147  *
148  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
149  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is
150  *     not oriented to the faces editedges.
151  *
152  *              Functions relating to this cycle:
153  *
154  *                      bmesh_cycle_XXX family of functions.
155  *
156  *
157  *      Note that the order of elements in all cycles except the loop cycle is undefined. This
158  *  leads to slightly increased seek time for deriving some adjacency relations, however the
159  *  advantage is that no intrinsic properties of the data structures are dependant upon the
160  *  cycle order and all non-manifold conditions are represented trivially.
161  *
162  */
163 int bmesh_disk_append_edge(struct BMEdge *e, struct BMVert *v)
164 {
165         if (!v->e) {
166                 Link *e1 = bm_get_edge_link(e, v);
167
168                 v->e = e;
169                 e1->next = e1->prev = (Link *)e;
170         }
171         else {
172                 Link *e1, *e2, *e3;
173
174                 e1 = bm_get_edge_link(e, v);
175                 e2 = bm_get_edge_link(v->e, v);
176                 e3 = e2->prev ? bm_get_edge_link(e2->prev, v) : NULL;
177
178                 e1->next = (Link *)v->e;
179                 e1->prev = e2->prev;
180
181                 e2->prev = (Link *)e;
182                 if (e3)
183                         e3->next = (Link *)e;
184         }
185
186         return TRUE;
187 }
188
189 void bmesh_disk_remove_edge(struct BMEdge *e, struct BMVert *v)
190 {
191         Link *e1, *e2;
192
193         e1 = bm_get_edge_link(e, v);
194         if (e1->prev) {
195                 e2 = bm_get_edge_link(e1->prev, v);
196                 e2->next = e1->next;
197         }
198
199         if (e1->next) {
200                 e2 = bm_get_edge_link(e1->next, v);
201                 e2->prev = e1->prev;
202         }
203
204         if (v->e == e)
205                 v->e = (e != (BMEdge *)e1->next) ? (BMEdge *)e1->next : NULL;
206
207         e1->next = e1->prev = NULL;
208 }
209
210 struct BMEdge *bmesh_disk_nextedge(struct BMEdge *e, struct BMVert *v)
211 {
212         if (v == e->v1)
213                 return e->dlink1.next;
214         if (v == e->v2)
215                 return e->dlink2.next;
216         return NULL;
217 }
218
219 static BMEdge *bmesh_disk_prevedge(BMEdge *e, BMVert *v)
220 {
221         if (v == e->v1)
222                 return e->dlink1.prev;
223         if (v == e->v2)
224                 return e->dlink2.prev;
225         return NULL;
226 }
227
228 BMEdge *bmesh_disk_existedge(BMVert *v1, BMVert *v2)
229 {
230         BMEdge *curedge, *startedge;
231         
232         if (v1->e) {
233                 startedge = v1->e;
234                 curedge = startedge;
235                 do {
236                         if (bmesh_verts_in_edge(v1, v2, curedge)) {
237                                 return curedge;
238                         }
239
240                         curedge = bmesh_disk_nextedge(curedge, v1);
241                 } while (curedge != startedge);
242         }
243         
244         return NULL;
245 }
246
247 int bmesh_disk_count(struct BMVert *v)
248 {
249         BMEdge *e = v->e;
250         int i = 0;
251
252         if (!e) {
253                 return 0;
254         }
255
256         do {
257                 if (!e) {
258                         return 0;
259                 }
260
261                 e =  bmesh_disk_nextedge(e, v);
262
263                 if (i >= (1 << 20)) {
264                         printf("bmesh error: infinite loop in disk cycle!\n");
265                         return 0;
266                 }
267
268                 i++;
269         } while (e != v->e);
270
271         return i;
272 }
273
274 int bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
275 {
276         BMEdge *e2;
277
278         if (!BM_Vert_In_Edge(e, v))
279                 return FALSE;
280         if (bmesh_disk_count(v) != len || len == 0)
281                 return FALSE;
282
283         e2 = e;
284         do {
285                 if (len != 1 && bmesh_disk_prevedge(e2, v) == e2) {
286                         return FALSE;
287                 }
288
289                 e2 = bmesh_disk_nextedge(e2, v);
290         } while (e2 != e);
291
292         return TRUE;
293 }
294
295 /*
296  * BME DISK COUNT FACE VERT
297  *
298  * Counts the number of loop users
299  * for this vertex. Note that this is
300  * equivalent to counting the number of
301  * faces incident upon this vertex
302  */
303
304 int bmesh_disk_count_facevert(BMVert *v)
305 {
306         BMEdge *curedge;
307         int count = 0;
308
309         /* is there an edge on this vert at all */
310         if (!v->e)
311                 return count;
312
313         /* first, loop around edge */
314         curedge = v->e;
315         do {
316                 if (curedge->l) count += bmesh_radial_count_facevert(curedge->l, v);
317                 curedge = bmesh_disk_nextedge(curedge, v);
318         } while (curedge != v->e);
319
320         return count;
321 }
322
323 struct BMEdge *bmesh_disk_find_first_faceedge(struct BMEdge *e, struct BMVert *v)
324 {
325         BMEdge *searchedge = NULL;
326         searchedge = e;
327         do {
328                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
329                         return searchedge;
330                 }
331
332                 searchedge = bmesh_disk_nextedge(searchedge, v);
333         } while (searchedge != e);
334
335         return NULL;
336 }
337
338 struct BMEdge *bmesh_disk_find_next_faceedge(struct BMEdge *e, struct BMVert *v)
339 {
340         BMEdge *searchedge = NULL;
341         searchedge = bmesh_disk_nextedge(e, v);
342         do {
343                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
344                         return searchedge;
345                 }
346                 searchedge = bmesh_disk_nextedge(searchedge, v);
347         } while (searchedge != e);
348         return e;
349 }
350
351 /*****radial cycle functions, e.g. loops surrounding edges**** */
352 int bmesh_radial_validate(int radlen, BMLoop *l)
353 {
354         BMLoop *l2 = l;
355         int i = 0;
356         
357         if (bmesh_radial_length(l) != radlen)
358                 return FALSE;
359
360         do {
361                 if (!l2) {
362                         bmesh_error();
363                         return FALSE;
364                 }
365                 
366                 if (l2->e != l->e)
367                         return FALSE;
368                 if (l2->v != l->e->v1 && l2->v != l->e->v2)
369                         return FALSE;
370                 
371                 if (i > BM_LOOP_RADIAL_MAX) {
372                         bmesh_error();
373                         return FALSE;
374                 }
375                 
376                 i++;
377                 l2 = l2->radial_next;
378         } while (l2 != l);
379
380         return TRUE;
381 }
382
383 /*
384  * BMESH RADIAL REMOVE LOOP
385  *
386  * Removes a loop from an radial cycle. If edge e is non-NULL
387  * it should contain the radial cycle, and it will also get
388  * updated (in the case that the edge's link into the radial
389  * cycle was the loop which is being removed from the cycle).
390  */
391 void bmesh_radial_remove_loop(BMLoop *l, BMEdge *e)
392 {
393         /* if e is non-NULL, l must be in the radial cycle of e */
394         if (e && e != l->e) {
395                 bmesh_error();
396         }
397
398         if (l->radial_next != l) {
399                 if (e && l == e->l)
400                         e->l = l->radial_next;
401
402                 l->radial_next->radial_prev = l->radial_prev;
403                 l->radial_prev->radial_next = l->radial_next;
404         }
405         else {
406                 if (e) {
407                         if (l == e->l) {
408                                 e->l = NULL;
409                         }
410                         else {
411                                 bmesh_error();
412                         }
413                 }
414         }
415
416         /* l is no longer in a radial cycle; empty the links
417          * to the cycle and the link back to an edge */
418         l->radial_next = l->radial_prev = NULL;
419         l->e = NULL;
420 }
421
422
423 /*
424  * BME RADIAL FIND FIRST FACE VERT
425  *
426  * Finds the first loop of v around radial
427  * cycle
428  */
429 BMLoop *bmesh_radial_find_first_facevert(BMLoop *l, BMVert *v)
430 {
431         BMLoop *curloop;
432         curloop = l;
433         do {
434                 if (curloop->v == v) {
435                         return curloop;
436                 }
437
438                 curloop = bmesh_radial_nextloop(curloop);
439         } while (curloop != l);
440         return NULL;
441 }
442
443 BMLoop *bmesh_radial_find_next_facevert(BMLoop *l, BMVert *v)
444 {
445         BMLoop *curloop;
446         curloop = bmesh_radial_nextloop(l);
447         do {
448                 if (curloop->v == v) {
449                         return curloop;
450                 }
451
452                 curloop = bmesh_radial_nextloop(curloop);
453         } while (curloop != l);
454         return l;
455 }
456
457 BMLoop *bmesh_radial_nextloop(BMLoop *l)
458 {
459         return l->radial_next;
460 }
461
462 int bmesh_radial_length(BMLoop *l)
463 {
464         BMLoop *l2 = l;
465         int i = 0;
466
467         if (!l)
468                 return 0;
469
470         do {
471                 if (!l2) {
472                         /* radial cycle is broken (not a circulat loop) */
473                         bmesh_error();
474                         return 0;
475                 }
476                 
477                 i++;
478                 l2 = l2->radial_next;
479                 if (i >= BM_LOOP_RADIAL_MAX) {
480                         bmesh_error();
481                         return -1;
482                 }
483         } while (l2 != l);
484
485         return i;
486 }
487
488 void bmesh_radial_append(BMEdge *e, BMLoop *l)
489 {
490         if (e->l == NULL) {
491                 e->l = l;
492                 l->radial_next = l->radial_prev = l;
493         }
494         else {
495                 l->radial_prev = e->l;
496                 l->radial_next = e->l->radial_next;
497
498                 e->l->radial_next->radial_prev = l;
499                 e->l->radial_next = l;
500
501                 e->l = l;
502         }
503
504         if (l->e && l->e != e) {
505                 /* l is already in a radial cycle for a different edge */
506                 bmesh_error();
507         }
508         
509         l->e = e;
510 }
511
512 int bmesh_radial_find_face(BMEdge *e, BMFace *f)
513 {
514         BMLoop *curloop;
515         int i, len;
516
517         len = bmesh_radial_length(e->l);
518         for (i = 0, curloop = e->l; i < len; i++, curloop = curloop->radial_next) {
519                 if (curloop->f == f)
520                         return TRUE;
521         }
522         return FALSE;
523 }
524
525 /*
526  * BME RADIAL COUNT FACE VERT
527  *
528  * Returns the number of times a vertex appears
529  * in a radial cycle
530  *
531  */
532
533 int bmesh_radial_count_facevert(BMLoop *l, BMVert *v)
534 {
535         BMLoop *curloop;
536         int count = 0;
537         curloop = l;
538         do {
539                 if (curloop->v == v) count++;
540                 curloop = bmesh_radial_nextloop(curloop);
541         } while (curloop != l);
542         return count;
543 }
544
545 /*****loop cycle functions, e.g. loops surrounding a face**** */
546 int bmesh_loop_validate(BMFace *f)
547 {
548         int i;
549         int len = f->len;
550         BMLoop *curloop, *head;
551         head = BM_FACE_FIRST_LOOP(f);
552         
553         if (head == NULL) {
554                 return FALSE;
555         }
556
557         /* Validate that the face loop cycle is the length specified by f->len */
558         for (i = 1, curloop = head->next; i < len; i++, curloop = curloop->next) {
559                 if ( (curloop->f != f) ||
560                      (curloop == head))
561                 {
562                         return FALSE;
563                 }
564         }
565         if (curloop != head) {
566                 return FALSE;
567         }
568
569         /* Validate the loop->prev links also form a cycle of length f->len */
570         for (i = 1, curloop = head->prev; i < len; i++, curloop = curloop->prev) {
571                 if (curloop == head) {
572                         return FALSE;
573                 }
574         }
575         if (curloop != head) {
576                 return FALSE;
577         }
578
579         return TRUE;
580 }
581
582
583 #if 0
584 void bmesh_cycle_append(void *h, void *nt)
585 {
586         BMNode *oldtail, *head, *newtail;
587         
588         head = (BMNode *)h;
589         newtail = (BMNode *)nt;
590         
591         if (head->next == NULL) {
592                 head->next = newtail;
593                 head->prev = newtail;
594                 newtail->next = head;
595                 newtail->prev = head;
596         }
597         else {
598                 oldtail = head->prev;
599                 oldtail->next = newtail;
600                 newtail->next = head;
601                 newtail->prev = oldtail;
602                 head->prev = newtail;
603                 
604         }
605 }
606
607 /**
608  *                      bmesh_cycle_length
609  *
610  *      Count the nodes in a cycle.
611  *
612  *  Returns -
613  *      Integer
614  */
615
616 int bmesh_cycle_length(BMEdge *e, BMVert *v)
617 {
618         BMEdge *next, *prev, *cur;
619         int len, vi = v == e->v1 ? 0 : 1;
620         
621         /* should skip 2 forward if v is 1, happily reduces to (v * 2) */
622         prev = *(&e->v1_prev + vi * 2);
623         
624         cur = e;
625         len = 1;
626         while (cur != prev) {
627                 vi = cur->v1 == v ? 0 : 1;
628                 
629                 len++;
630                 cur = *(&cur->v1_next + vi * 2);
631         }
632         
633         return len;
634 }
635
636 /**
637  *                      bmesh_cycle_remove
638  *
639  *      Removes a node from a cycle.
640  *
641  *  Returns -
642  *      1 for success, 0 for failure.
643  */
644
645 int bmesh_cycle_remove(void *h, void *remn)
646 {
647         int i, len;
648         BMNode *head, *remnode, *curnode;
649         
650         head = (BMNode *)h;
651         remnode = (BMNode *)remn;
652         len = bmesh_cycle_length(h);
653         
654         if (len == 1 && head == remnode) {
655                 head->next = NULL;
656                 head->prev = NULL;
657                 return TRUE;
658         }
659         else {
660                 for (i = 0, curnode = head; i < len; curnode = curnode->next) {
661                         if (curnode == remnode) {
662                                 remnode->prev->next = remnode->next;
663                                 remnode->next->prev = remnode->prev;
664                                 /* zero out remnode pointers, important */
665                                 //remnode->next = NULL;
666                                 //remnode->prev = NULL;
667                                 return TRUE;
668                 
669                         }
670                 }
671         }
672         return FALSE;
673 }
674
675 /**
676  *                      bmesh_cycle_validate
677  *
678  *      Validates a cycle. Takes as an argument the expected length of the cycle and
679  *      a pointer to the cycle head or base.
680  *
681  *
682  *  Returns -
683  *      1 for success, 0 for failure.
684  */
685
686 int bmesh_cycle_validate(int len, void *h)
687 {
688         int i;
689         BMNode *curnode, *head;
690         head = (BMNode *)h;
691         
692         /* forward validatio */
693         for (i = 0, curnode = head; i < len; i++, curnode = curnode->next);
694         if (curnode != head) {
695                 return FALSE;
696         }
697
698         /* reverse validatio */
699         for (i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
700         if (curnode != head) {
701                 return FALSE;
702         }
703
704         return TRUE;
705 }
706
707 /* Begin Disk Cycle routine */
708
709 /**
710  *                      bmesh_disk_nextedge
711  *
712  *      Find the next edge in a disk cycle
713  *
714  *  Returns -
715  *      Pointer to the next edge in the disk cycle for the vertex v.
716  */
717  
718 BMEdge *bmesh_disk_nextedge(BMEdge *e, BMVert *v)
719 {
720         if (bmesh_vert_in_edge(e, v)) {
721                 if (e->v1 == v) {
722                         return e->d1.next->data;
723                 }
724                 else if (e->v2 == v) {
725                         return e->d2.next->data;
726                 }
727         }
728         return NULL;
729 }
730
731 /**
732  *                      bmesh_disk_getpointer
733  *
734  *      Given an edge and one of its vertices, find the apporpriate CycleNode
735  *
736  *  Returns -
737  *      Pointer to bmesh_CycleNode.
738  */
739 BMNode *bmesh_disk_getpointer(BMEdge *e, BMVert *v)
740 {
741         /* returns pointer to the cycle node for the appropriate vertex in this dis */
742         if (e->v1 == v) {
743                 return &(e->d1);
744         }
745         else if (e->v2 == v) {
746                 return &(e->d2);
747         }
748         return NULL;
749 }
750
751 /**
752  *                      bmesh_disk_append_edge
753  *
754  *      Appends edge to the end of a vertex disk cycle.
755  *
756  *  Returns -
757  *      1 for success, 0 for failure
758  */
759
760 int bmesh_disk_append_edge(BMEdge *e, BMVert *v)
761 {
762         
763         BMNode *base, *tail;
764
765         /* check to make sure v is in */
766         if (bmesh_vert_in_edge(e, v) == 0) {
767                 return FALSE;
768         }
769         
770         /* check for loose vert firs */
771         if (v->e == NULL) {
772                 v->e = e;
773                 base = tail = bmesh_disk_getpointer(e, v);
774                 bmesh_cycle_append(base, tail); /* circular reference is ok */
775                 return TRUE;
776         }
777         
778         /* insert e at the end of disk cycle and make it the new v-> */
779         base = bmesh_disk_getpointer(v->e, v);
780         tail = bmesh_disk_getpointer(e, v);
781         bmesh_cycle_append(base, tail);
782         return TRUE;
783 }
784
785 /**
786  *                      bmesh_disk_remove_edge
787  *
788  *      Removes an edge from a disk cycle. If the edge to be removed is
789  *      at the base of the cycle, the next edge becomes the new base.
790  *
791  *
792  *  Returns -
793  *      Nothing
794  */
795
796 void bmesh_disk_remove_edge(BMEdge *e, BMVert *v)
797 {
798         BMNode *base, *remnode;
799         BMEdge *newbase;
800         int len;
801         
802         base = bmesh_disk_getpointer(v->e, v);
803         remnode = bmesh_disk_getpointer(e, v);
804         
805         /* first deal with v->e pointer.. */
806         len = bmesh_cycle_length(base);
807         if (len == 1) newbase = NULL;
808         else if (v->e == e) newbase = base->next-> data;
809         else newbase = v->e;
810         
811         /* remove and rebas */
812         bmesh_cycle_remove(base, remnode);
813         v->e = newbase;
814 }
815
816 /**
817  *                      bmesh_disk_next_edgeflag
818  *
819  *      Searches the disk cycle of v, starting with e, for the
820  *  next edge that has either eflag or tflag.
821  *
822  *      bmesh_Edge pointer.
823  */
824
825 BMEdge *bmesh_disk_next_edgeflag(BMEdge *e, BMVert *v, int eflag, int tflag)
826 {
827         
828         BMNode *diskbase;
829         BMEdge *curedge;
830         int len, ok;
831         
832         if (eflag && tflag) {
833                 return NULL;
834         }
835
836         ok = bmesh_vert_in_edge(e, v);
837         if (ok) {
838                 diskbase = bmesh_disk_getpointer(e, v);
839                 len = bmesh_cycle_length(diskbase);
840                 curedge = bmesh_disk_nextedge(e, v);
841                 while (curedge != e) {
842                         if (eflag) {
843                                 if (curedge->head.eflag1 == eflag) {
844                                         return curedge;
845                                 }
846                         }
847
848                         curedge = bmesh_disk_nextedge(curedge, v);
849                 }
850         }
851         return NULL;
852 }
853
854 /**
855  *                      bmesh_disk_count_edgeflag
856  *
857  *      Counts number of edges in this verts disk cycle which have
858  *      either eflag or tflag (but not both!)
859  *
860  *  Returns -
861  *      Integer.
862  */
863
864 int bmesh_disk_count_edgeflag(BMVert *v, int eflag, int tflag)
865 {
866         BMNode *diskbase;
867         BMEdge *curedge;
868         int i, len = 0, count = 0;
869         
870         if (v->e) {
871
872                 /* tflag and eflag are reserved for different functions */
873                 if (eflag && tflag) {
874                         return 0;
875                 }
876
877                 diskbase = bmesh_disk_getpointer(v->e, v);
878                 len = bmesh_cycle_length(diskbase);
879                 
880                 for (i = 0, curedge = v->e; i < len; i++) {
881                         if (eflag) {
882                                 if (curedge->head.eflag1 == eflag) count++;
883                         }
884                         curedge = bmesh_disk_nextedge(curedge, v);
885                 }
886         }
887         return count;
888 }
889
890
891 int bmesh_disk_hasedge(BMVert *v, BMEdge *e)
892 {
893         BMNode *diskbase;
894         BMEdge *curedge;
895         int i, len = 0;
896         
897         if (v->e) {
898                 diskbase = bmesh_disk_getpointer(v->e, v);
899                 len = bmesh_cycle_length(diskbase);
900                 
901                 for (i = 0, curedge = v->e; i < len; i++) {
902                         if (curedge == e) {
903                                 return TRUE;
904                         }
905                         else curedge = bmesh_disk_nextedge(curedge, v);
906                 }
907         }
908         return FALSE;
909 }
910
911 BMEdge *bmesh_disk_existedge(BMVert *v1, BMVert *v2)
912 {
913         BMNode *diskbase;
914         BMEdge *curedge;
915         int i, len = 0;
916         
917         if (v1->e) {
918                 diskbase = bmesh_disk_getpointer(v1->e, v1);
919                 len = bmesh_cycle_length(diskbase);
920                 
921                 for (i = 0, curedge = v1->e; i < len; i++, curedge = bmesh_disk_nextedge(curedge, v1)) {
922                         if (bmesh_verts_in_edge(v1, v2, curedge)) {
923                                 return curedge;
924                         }
925                 }
926         }
927         
928         return NULL;
929 }
930
931 /* end disk cycle routine */
932 BMLoop *bmesh_radial_nextloop(BMLoop *l)
933 {
934         return l->radial_next;
935 }
936
937 void bmesh_radial_append(BMEdge *e, BMLoop *l)
938 {
939         if (e->l == NULL) e->l = l;
940         bmesh_cycle_append(&(e->l->radial), &(l->radial));
941 }
942
943 void bmesh_radial_remove_loop(BMLoop *l, BMEdge *e)
944 {
945         BMLoop *newbase;
946         int len;
947         
948         /* deal with edge->l pointe */
949         len = bmesh_cycle_length(&(e->l->radial));
950         if (len == 1) newbase = NULL;
951         else if (e->l == l) newbase = e->l->radial_next;
952         else newbase = e->l;
953         
954         /* remove and rebas */
955         bmesh_cycle_remove(&(e->l->radial), &(l->radial));
956         e->l = newbase;
957 }
958
959 int bmesh_radial_find_face(BMEdge *e, BMFace *f)
960 {
961                 
962         BMLoop *curloop;
963         int i, len;
964         
965         len = bmesh_cycle_length(&(e->l->radial));
966         for (i = 0, curloop = e->l; i < len; i++, curloop = curloop->radial_next) {
967                 if (curloop->f == f) {
968                         return TRUE;
969                 }
970         }
971         return FALSE;
972 }
973
974
975 /*
976  * BME RADIAL COUNT FACE VERT
977  *
978  * Returns the number of times a vertex appears
979  * in a radial cycle
980  *
981  */
982
983 int bmesh_radial_count_facevert(BMLoop *l, BMVert *v)
984 {
985         BMLoop *curloop;
986         int count = 0;
987         curloop = l;
988         do {
989                 if (curloop->v == v) count++;
990                 curloop = bmesh_radial_nextloop(curloop);
991         } while (curloop != l);
992         return count;
993 }
994
995 /*
996  * BME DISK COUNT FACE VERT
997  *
998  * Counts the number of loop users
999  * for this vertex. Note that this is
1000  * equivalent to counting the number of
1001  * faces incident upon this vertex
1002  *
1003  */
1004
1005 int bmesh_disk_count_facevert(BMVert *v)
1006 {
1007         BMEdge *curedge;
1008         int count = 0;
1009
1010         /* is there an edge on this vert at all */
1011         if (!v->e)
1012                 return count;
1013
1014         /* first, loop around edge */
1015         curedge = v->e;
1016         do {
1017                 if (curedge->l) count += bmesh_radial_count_facevert(curedge->l, v);
1018                 curedge = bmesh_disk_nextedge(curedge, v);
1019         } while (curedge != v->e);
1020
1021         return count;
1022 }
1023
1024 /*
1025  * BME RADIAL FIND FIRST FACE VERT
1026  *
1027  * Finds the first loop of v around radial
1028  * cycle
1029  *
1030  */
1031 BMLoop *bmesh_radial_find_first_facevert(BMLoop *l, BMVert *v)
1032 {
1033         BMLoop *curloop;
1034         curloop = l;
1035         do {
1036                 if (curloop->v == v) {
1037                         return curloop;
1038                 }
1039
1040                 curloop = bmesh_radial_nextloop(curloop);
1041         } while (curloop != l);
1042         return NULL;
1043 }
1044
1045 BMLoop *bmesh_radial_find_next_facevert(BMLoop *l, BMVert *v)
1046 {
1047         BMLoop *curloop;
1048         curloop = bmesh_radial_nextloop(l);
1049         do {
1050                 if (curloop->v == v) {
1051                         return curloop;
1052                 }
1053
1054                 curloop = bmesh_radial_nextloop(curloop);
1055         } while (curloop != l);
1056         return l;
1057 }
1058
1059
1060 /*
1061  * BME FIND FIRST FACE EDGE
1062  *
1063  * Finds the first edge in a vertices
1064  * Disk cycle that has one of this
1065  * vert's loops attached
1066  * to it.
1067  */
1068
1069 BMEdge *bmesh_disk_find_first_faceedge(BMEdge *e, BMVert *v)
1070 {
1071         BMEdge *searchedge = NULL;
1072         searchedge = e;
1073         do {
1074                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
1075                         return searchedge;
1076                 }
1077                 searchedge = bmesh_disk_nextedge(searchedge, v);
1078         } while (searchedge != e);
1079         
1080         return NULL;
1081 }
1082
1083 BMEdge *bmesh_disk_find_next_faceedge(BMEdge *e, BMVert *v)
1084 {
1085         BMEdge *searchedge = NULL;
1086         searchedge = bmesh_disk_nextedge(e, v);
1087         do {
1088                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
1089                         return searchedge;
1090                 }
1091                 searchedge = bmesh_disk_nextedge(searchedge, v);
1092         } while (searchedge != e);
1093         return e;
1094 }
1095
1096
1097
1098
1099
1100 struct BMLoop *bmesh_loop_find_loop(struct BMFace *f, struct BMVert *v)
1101 {
1102         BMLoop *l;
1103         int i, len;
1104         
1105         len = bmesh_cycle_length(f->lbase);
1106         for (i = 0, l = f->loopbase; i < len; i++, l = l->next) {
1107                 if (l->v == v) {
1108                         return l;
1109                 }
1110         }
1111         return NULL;
1112 }
1113
1114 #endif