typo cleanup, no functional changes.
[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 "bmesh.h"
35 #include "bmesh_private.h"
36
37 /**
38  *      MISC utility functions.
39  *
40  */
41
42 int bmesh_vert_in_edge(BMEdge *e, BMVert *v)
43 {
44         if (e->v1 == v || e->v2 == v) return TRUE;
45         return FALSE;
46 }
47 int bmesh_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
48 {
49         if (e->v1 == v1 && e->v2 == v2) return TRUE;
50         else if (e->v1 == v2 && e->v2 == v1) return TRUE;
51         return FALSE;
52 }
53
54 BMVert *bmesh_edge_getothervert(BMEdge *e, BMVert *v) {
55         if (e->v1 == v) {
56                 return e->v2;
57         }
58         else if (e->v2 == v) {
59                 return e->v1;
60         }
61         return NULL;
62 }
63
64 int bmesh_edge_swapverts(BMEdge *e, BMVert *orig, BMVert *newv)
65 {
66         if (e->v1 == orig) {
67                 e->v1 = newv;
68                 e->v1_disk_link.next = e->v1_disk_link.prev = NULL;
69                 return TRUE;
70         }
71         else if (e->v2 == orig) {
72                 e->v2 = newv;
73                 e->v2_disk_link.next = e->v2_disk_link.prev = NULL;
74                 return TRUE;
75         }
76         return FALSE;
77 }
78
79 /**
80  *      BMESH CYCLES
81  * (this is somewhat outdate, though bits of its API are still used) - joeedh
82  *
83  *      Cycles are circular doubly linked lists that form the basis of adjacency
84  *      information in the BME modeller. Full adjacency relations can be derived
85  *      from examining these cycles very quickly. Although each cycle is a double
86  *  circular linked list, each one is considered to have a 'base' or 'head',
87  *      and care must be taken by Euler code when modifying the contents of a cycle.
88  *
89  *      The contents of this file are split into two parts. First there are the
90  *      bmesh_cycle family of functions which are generic circular double linked list
91  *      procedures. The second part contains higher level procedures for supporting
92  *      modification of specific cycle types.
93  *
94  *      The three cycles explicitly stored in the BM data structure are as follows:
95  *
96  *      1: The Disk Cycle - A circle of edges around a vertex
97  *     Base: vertex->edge pointer.
98  *
99  *     This cycle is the most complicated in terms of its structure. Each bmesh_Edge contains
100  *         two bmesh_CycleNode structures to keep track of that edge's membership in the disk cycle
101  *         of each of its vertices. However for any given vertex it may be the first in some edges
102  *         in its disk cycle and the second for others. The bmesh_disk_XXX family of functions contain
103  *         some nice utilities for navigating disk cycles in a way that hides this detail from the
104  *         tool writer.
105  *
106  *              Note that the disk cycle is completley independent from face data. One advantage of this
107  *              is that wire edges are fully integrated into the topology database. Another is that the
108  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
109  *
110  *              Functions relating to this cycle:
111  *
112  *                      bmesh_disk_append_edge
113  *                      bmesh_disk_remove_edge
114  *                      bmesh_disk_nextedge
115  *                      bmesh_disk_getpointer
116  *
117  *      2: The Radial Cycle - A circle of face edges (bmesh_Loop) around an edge
118  *         Base: edge->l->radial structure.
119  *
120  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
121  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory
122  *              to store non-manifold conditions since BM does not keep track of region/shell
123  *              information.
124  *
125  *              Functions relating to this cycle:
126  *
127  *                      bmesh_radial_append
128  *                      bmesh_radial_remove_loop
129  *                      bmesh_radial_nextloop
130  *                      bmesh_radial_find_face
131  *
132  *
133  *      3: The Loop Cycle - A circle of face edges around a polygon.
134  *     Base: polygon->lbase.
135  *
136  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
137  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is
138  *     not oriented to the faces editedges.
139  *
140  *              Functions relating to this cycle:
141  *
142  *                      bmesh_cycle_XXX family of functions.
143  *
144  *
145  *      Note that the order of elements in all cycles except the loop cycle is undefined. This
146  *  leads to slightly increased seek time for deriving some adjacency relations, however the
147  *  advantage is that no intrinsic properties of the data structures are dependant upon the
148  *  cycle order and all non-manifold conditions are represented trivially.
149  *
150  */
151 int bmesh_disk_append_edge(struct BMEdge *e, struct BMVert *v)
152 {
153         if (!v->e) {
154                 BMDiskLink *dl1 = BM_EDGE_DISK_LINK_GET(e, v);
155
156                 v->e = e;
157                 dl1->next = dl1->prev = e;
158         }
159         else {
160                 BMDiskLink *dl1, *dl2, *dl3;
161
162                 dl1 = BM_EDGE_DISK_LINK_GET(e, v);
163                 dl2 = BM_EDGE_DISK_LINK_GET(v->e, v);
164                 dl3 = dl2->prev ? BM_EDGE_DISK_LINK_GET(dl2->prev, v) : NULL;
165
166                 dl1->next = v->e;
167                 dl1->prev = dl2->prev;
168
169                 dl2->prev = e;
170                 if (dl3)
171                         dl3->next = e;
172         }
173
174         return TRUE;
175 }
176
177 void bmesh_disk_remove_edge(struct BMEdge *e, struct BMVert *v)
178 {
179         BMDiskLink *dl1, *dl2;
180
181         dl1 = BM_EDGE_DISK_LINK_GET(e, v);
182         if (dl1->prev) {
183                 dl2 = BM_EDGE_DISK_LINK_GET(dl1->prev, v);
184                 dl2->next = dl1->next;
185         }
186
187         if (dl1->next) {
188                 dl2 = BM_EDGE_DISK_LINK_GET(dl1->next, v);
189                 dl2->prev = dl1->prev;
190         }
191
192         if (v->e == e)
193                 v->e = (e != (BMEdge *)dl1->next) ? (BMEdge *)dl1->next : NULL;
194
195         dl1->next = dl1->prev = NULL;
196 }
197
198 /*
199  *                      bmesh_disk_nextedge
200  *
201  *      Find the next edge in a disk cycle
202  *
203  *  Returns -
204  *      Pointer to the next edge in the disk cycle for the vertex v.
205  */
206
207 struct BMEdge *bmesh_disk_nextedge(struct BMEdge *e, struct BMVert *v)
208 {
209         if (v == e->v1)
210                 return e->v1_disk_link.next;
211         if (v == e->v2)
212                 return e->v2_disk_link.next;
213         return NULL;
214 }
215
216 static BMEdge *bmesh_disk_prevedge(BMEdge *e, BMVert *v)
217 {
218         if (v == e->v1)
219                 return e->v1_disk_link.prev;
220         if (v == e->v2)
221                 return e->v2_disk_link.prev;
222         return NULL;
223 }
224
225 BMEdge *bmesh_disk_existedge(BMVert *v1, BMVert *v2)
226 {
227         BMEdge *curedge, *startedge;
228         
229         if (v1->e) {
230                 startedge = v1->e;
231                 curedge = startedge;
232                 do {
233                         if (bmesh_verts_in_edge(v1, v2, curedge)) {
234                                 return curedge;
235                         }
236
237                         curedge = bmesh_disk_nextedge(curedge, v1);
238                 } while (curedge != startedge);
239         }
240         
241         return NULL;
242 }
243
244 int bmesh_disk_count(struct BMVert *v)
245 {
246         BMEdge *e = v->e;
247         int i = 0;
248
249         if (!e) {
250                 return 0;
251         }
252
253         do {
254                 if (!e) {
255                         return 0;
256                 }
257
258                 e =  bmesh_disk_nextedge(e, v);
259
260                 if (i >= (1 << 20)) {
261                         printf("bmesh error: infinite loop in disk cycle!\n");
262                         return 0;
263                 }
264
265                 i++;
266         } while (e != v->e);
267
268         return i;
269 }
270
271 int bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
272 {
273         BMEdge *e2;
274
275         if (!BM_vert_in_edge(e, v))
276                 return FALSE;
277         if (bmesh_disk_count(v) != len || len == 0)
278                 return FALSE;
279
280         e2 = e;
281         do {
282                 if (len != 1 && bmesh_disk_prevedge(e2, v) == e2) {
283                         return FALSE;
284                 }
285
286                 e2 = bmesh_disk_nextedge(e2, v);
287         } while (e2 != e);
288
289         return TRUE;
290 }
291
292 /*
293  * BME DISK COUNT FACE VERT
294  *
295  * Counts the number of loop users
296  * for this vertex. Note that this is
297  * equivalent to counting the number of
298  * faces incident upon this vertex
299  */
300
301 int bmesh_disk_count_facevert(BMVert *v)
302 {
303         BMEdge *curedge;
304         int count = 0;
305
306         /* is there an edge on this vert at all */
307         if (!v->e)
308                 return count;
309
310         /* first, loop around edge */
311         curedge = v->e;
312         do {
313                 if (curedge->l) count += bmesh_radial_count_facevert(curedge->l, v);
314                 curedge = bmesh_disk_nextedge(curedge, v);
315         } while (curedge != v->e);
316
317         return count;
318 }
319
320 /*
321  * BME FIND FIRST FACE EDGE
322  *
323  * Finds the first edge in a vertices
324  * Disk cycle that has one of this
325  * vert's loops attached
326  * to it.
327  */
328
329 struct BMEdge *bmesh_disk_find_first_faceedge(struct BMEdge *e, struct BMVert *v)
330 {
331         BMEdge *searchedge = NULL;
332         searchedge = e;
333         do {
334                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
335                         return searchedge;
336                 }
337
338                 searchedge = bmesh_disk_nextedge(searchedge, v);
339         } while (searchedge != e);
340
341         return NULL;
342 }
343
344 struct BMEdge *bmesh_disk_find_next_faceedge(struct BMEdge *e, struct BMVert *v)
345 {
346         BMEdge *searchedge = NULL;
347         searchedge = bmesh_disk_nextedge(e, v);
348         do {
349                 if (searchedge->l && bmesh_radial_count_facevert(searchedge->l, v)) {
350                         return searchedge;
351                 }
352                 searchedge = bmesh_disk_nextedge(searchedge, v);
353         } while (searchedge != e);
354         return e;
355 }
356
357 /*****radial cycle functions, e.g. loops surrounding edges**** */
358 int bmesh_radial_validate(int radlen, BMLoop *l)
359 {
360         BMLoop *l_iter = l;
361         int i = 0;
362         
363         if (bmesh_radial_length(l) != radlen)
364                 return FALSE;
365
366         do {
367                 if (!l_iter) {
368                         bmesh_error();
369                         return FALSE;
370                 }
371                 
372                 if (l_iter->e != l->e)
373                         return FALSE;
374                 if (l_iter->v != l->e->v1 && l_iter->v != l->e->v2)
375                         return FALSE;
376                 
377                 if (i > BM_LOOP_RADIAL_MAX) {
378                         bmesh_error();
379                         return FALSE;
380                 }
381                 
382                 i++;
383         } while ((l_iter = bmesh_radial_nextloop(l_iter)) != l);
384
385         return TRUE;
386 }
387
388 /*
389  * BMESH RADIAL REMOVE LOOP
390  *
391  * Removes a loop from an radial cycle. If edge e is non-NULL
392  * it should contain the radial cycle, and it will also get
393  * updated (in the case that the edge's link into the radial
394  * cycle was the loop which is being removed from the cycle).
395  */
396 void bmesh_radial_remove_loop(BMLoop *l, BMEdge *e)
397 {
398         /* if e is non-NULL, l must be in the radial cycle of e */
399         if (e && e != l->e) {
400                 bmesh_error();
401         }
402
403         if (l->radial_next != l) {
404                 if (e && l == e->l)
405                         e->l = l->radial_next;
406
407                 l->radial_next->radial_prev = l->radial_prev;
408                 l->radial_prev->radial_next = l->radial_next;
409         }
410         else {
411                 if (e) {
412                         if (l == e->l) {
413                                 e->l = NULL;
414                         }
415                         else {
416                                 bmesh_error();
417                         }
418                 }
419         }
420
421         /* l is no longer in a radial cycle; empty the links
422          * to the cycle and the link back to an edge */
423         l->radial_next = l->radial_prev = NULL;
424         l->e = NULL;
425 }
426
427
428 /*
429  * BME RADIAL FIND FIRST FACE VERT
430  *
431  * Finds the first loop of v around radial
432  * cycle
433  */
434 BMLoop *bmesh_radial_find_first_faceloop(BMLoop *l, BMVert *v)
435 {
436         BMLoop *l_iter;
437         l_iter = l;
438         do {
439                 if (l_iter->v == v) {
440                         return l_iter;
441                 }
442         } while ((l_iter = bmesh_radial_nextloop(l_iter)) != l);
443         return NULL;
444 }
445
446 BMLoop *bmesh_radial_find_next_faceloop(BMLoop *l, BMVert *v)
447 {
448         BMLoop *l_iter;
449         l_iter = bmesh_radial_nextloop(l);
450         do {
451                 if (l_iter->v == v) {
452                         return l_iter;
453                 }
454         } while ((l_iter = bmesh_radial_nextloop(l_iter)) != l);
455         return l;
456 }
457
458 BMLoop *bmesh_radial_nextloop(BMLoop *l)
459 {
460         return l->radial_next;
461 }
462
463 int bmesh_radial_length(BMLoop *l)
464 {
465         BMLoop *l_iter = l;
466         int i = 0;
467
468         if (!l)
469                 return 0;
470
471         do {
472                 if (!l_iter) {
473                         /* radial cycle is broken (not a circulat loop) */
474                         bmesh_error();
475                         return 0;
476                 }
477                 
478                 i++;
479                 if (i >= BM_LOOP_RADIAL_MAX) {
480                         bmesh_error();
481                         return -1;
482                 }
483         } while ((l_iter = l_iter->radial_next) != 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 *l_iter;
515         int i, len;
516
517         len = bmesh_radial_length(e->l);
518         for (i = 0, l_iter = e->l; i < len; i++, l_iter = l_iter->radial_next) {
519                 if (l_iter->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 *l_iter;
536         int count = 0;
537         l_iter = l;
538         do {
539                 if (l_iter->v == v) {
540                         count++;
541                 }
542         } while ((l_iter = bmesh_radial_nextloop(l_iter)) != l);
543
544         return count;
545 }
546
547 /*****loop cycle functions, e.g. loops surrounding a face**** */
548 int bmesh_loop_validate(BMFace *f)
549 {
550         int i;
551         int len = f->len;
552         BMLoop *l_iter, *l_first;
553
554         l_first = BM_FACE_FIRST_LOOP(f);
555
556         if (l_first == NULL) {
557                 return FALSE;
558         }
559
560         /* Validate that the face loop cycle is the length specified by f->len */
561         for (i = 1, l_iter = l_first->next; i < len; i++, l_iter = l_iter->next) {
562                 if ( (l_iter->f != f) ||
563                      (l_iter == l_first))
564                 {
565                         return FALSE;
566                 }
567         }
568         if (l_iter != l_first) {
569                 return FALSE;
570         }
571
572         /* Validate the loop->prev links also form a cycle of length f->len */
573         for (i = 1, l_iter = l_first->prev; i < len; i++, l_iter = l_iter->prev) {
574                 if (l_iter == l_first) {
575                         return FALSE;
576                 }
577         }
578         if (l_iter != l_first) {
579                 return FALSE;
580         }
581
582         return TRUE;
583 }
584
585
586 #if 0
587
588 /**
589  *                      bmesh_cycle_length
590  *
591  *      Count the nodes in a cycle.
592  *
593  *  Returns -
594  *      Integer
595  */
596
597 int bmesh_cycle_length(BMEdge *e, BMVert *v)
598 {
599         BMEdge *next, *prev, *cur;
600         int len, vi = v == e->v1 ? 0 : 1;
601         
602         /* should skip 2 forward if v is 1, happily reduces to (v * 2) */
603         prev = *(&e->v1_prev + vi * 2);
604         
605         cur = e;
606         len = 1;
607         while (cur != prev) {
608                 vi = cur->v1 == v ? 0 : 1;
609                 
610                 len++;
611                 cur = *(&cur->v1_next + vi * 2);
612         }
613         
614         return len;
615 }
616
617 /* Begin Disk Cycle routine */
618
619 /**
620  *                      bmesh_disk_getpointer
621  *
622  *      Given an edge and one of its vertices, find the apporpriate CycleNode
623  *
624  *  Returns -
625  *      Pointer to bmesh_CycleNode.
626  */
627 BMNode *bmesh_disk_getpointer(BMEdge *e, BMVert *v)
628 {
629         /* returns pointer to the cycle node for the appropriate vertex in this dis */
630         if (e->v1 == v) {
631                 return &(e->d1);
632         }
633         else if (e->v2 == v) {
634                 return &(e->d2);
635         }
636         return NULL;
637 }
638
639 /**
640  *                      bmesh_disk_next_edgeflag
641  *
642  *      Searches the disk cycle of v, starting with e, for the
643  *  next edge that has either eflag or tflag.
644  *
645  *      bmesh_Edge pointer.
646  */
647
648 BMEdge *bmesh_disk_next_edgeflag(BMEdge *e, BMVert *v, int eflag, int tflag)
649 {
650         
651         BMNode *diskbase;
652         BMEdge *curedge;
653         int len, ok;
654         
655         if (eflag && tflag) {
656                 return NULL;
657         }
658
659         ok = bmesh_vert_in_edge(e, v);
660         if (ok) {
661                 diskbase = bmesh_disk_getpointer(e, v);
662                 len = bmesh_cycle_length(diskbase);
663                 curedge = bmesh_disk_nextedge(e, v);
664                 while (curedge != e) {
665                         if (eflag) {
666                                 if (curedge->head.eflag1 == eflag) {
667                                         return curedge;
668                                 }
669                         }
670
671                         curedge = bmesh_disk_nextedge(curedge, v);
672                 }
673         }
674         return NULL;
675 }
676
677 int bmesh_disk_hasedge(BMVert *v, BMEdge *e)
678 {
679         BMNode *diskbase;
680         BMEdge *curedge;
681         int i, len = 0;
682         
683         if (v->e) {
684                 diskbase = bmesh_disk_getpointer(v->e, v);
685                 len = bmesh_cycle_length(diskbase);
686                 
687                 for (i = 0, curedge = v->e; i < len; i++) {
688                         if (curedge == e) {
689                                 return TRUE;
690                         }
691                         else curedge = bmesh_disk_nextedge(curedge, v);
692                 }
693         }
694         return FALSE;
695 }
696
697 struct BMLoop *bmesh_loop_find_loop(struct BMFace *f, struct BMVert *v)
698 {
699         BMLoop *l;
700         int i, len;
701         
702         len = bmesh_cycle_length(f->lbase);
703         for (i = 0, l = f->loopbase; i < len; i++, l = l->next) {
704                 if (l->v == v) {
705                         return l;
706                 }
707         }
708         return NULL;
709 }
710
711 #endif