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