Merging r50522 through r50572 from trunk into soc-2011-tomato
[blender.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 "BLI_utildefines.h"
35
36 #include "bmesh.h"
37 #include "intern/bmesh_private.h"
38
39 /**
40  *      MISC utility functions.
41  */
42
43 int bmesh_vert_in_edge(BMEdge *e, BMVert *v)
44 {
45         if (e->v1 == v || e->v2 == v) return TRUE;
46         return FALSE;
47 }
48 int bmesh_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
49 {
50         if (e->v1 == v1 && e->v2 == v2) return TRUE;
51         else if (e->v1 == v2 && e->v2 == v1) return TRUE;
52         return FALSE;
53 }
54
55 BMVert *bmesh_edge_other_vert_get(BMEdge *e, BMVert *v)
56 {
57         if (e->v1 == v) {
58                 return e->v2;
59         }
60         else if (e->v2 == v) {
61                 return e->v1;
62         }
63         return NULL;
64 }
65
66 int bmesh_edge_swapverts(BMEdge *e, BMVert *orig, BMVert *newv)
67 {
68         if (e->v1 == orig) {
69                 e->v1 = newv;
70                 e->v1_disk_link.next = e->v1_disk_link.prev = NULL;
71                 return TRUE;
72         }
73         else if (e->v2 == orig) {
74                 e->v2 = newv;
75                 e->v2_disk_link.next = e->v2_disk_link.prev = NULL;
76                 return TRUE;
77         }
78         return FALSE;
79 }
80
81 /**
82  * \section bm_cycles BMesh Cycles
83  * (this is somewhat outdate, though bits of its API are still used) - joeedh
84  *
85  * Cycles are circular doubly linked lists that form the basis of adjacency
86  * information in the BME modeler. Full adjacency relations can be derived
87  * from examining these cycles very quickly. Although each cycle is a double
88  * circular linked list, each one is considered to have a 'base' or 'head',
89  * and care must be taken by Euler code when modifying the contents of a cycle.
90  *
91  * The contents of this file are split into two parts. First there are the
92  * bmesh_cycle family of functions which are generic circular double linked list
93  * procedures. The second part contains higher level procedures for supporting
94  * modification of specific cycle types.
95  *
96  * The three cycles explicitly stored in the BM data structure are as follows:
97  *
98  *
99  * 1: The Disk Cycle - A circle of edges around a vertex
100  * Base: vertex->edge pointer.
101  *
102  * This cycle is the most complicated in terms of its structure. Each bmesh_Edge contains
103  * two bmesh_CycleNode structures to keep track of that edges membership in the disk cycle
104  * of each of its vertices. However for any given vertex it may be the first in some edges
105  * in its disk cycle and the second for others. The bmesh_disk_XXX family of functions contain
106  * some nice utilities for navigating disk cycles in a way that hides this detail from the
107  * tool writer.
108  *
109  * Note that the disk cycle is completely independent from face data. One advantage of this
110  * is that wire edges are fully integrated into the topology database. Another is that the
111  * the disk cycle has no problems dealing with non-manifold conditions involving faces.
112  *
113  * Functions relating to this cycle:
114  * - #bmesh_disk_edge_append
115  * - #bmesh_disk_edge_remove
116  * - #bmesh_disk_edge_next
117  * - #bmesh_disk_edge_prev
118  * - #bmesh_disk_facevert_count
119  * - #bmesh_disk_faceedge_find_first
120  * - #bmesh_disk_faceedge_find_next
121  *
122  *
123  * 2: The Radial Cycle - A circle of face edges (bmesh_Loop) around an edge
124  * Base: edge->l->radial structure.
125  *
126  * The radial cycle is similar to the radial cycle in the radial edge data structure.*
127  * Unlike the radial edge however, the radial cycle does not require a large amount of memory
128  * to store non-manifold conditions since BM does not keep track of region/shell information.
129  *
130  * Functions relating to this cycle:
131  * - #bmesh_radial_append
132  * - #bmesh_radial_loop_remove
133  * - #bmesh_radial_face_find
134  * - #bmesh_radial_facevert_count
135  * - #bmesh_radial_faceloop_find_first
136  * - #bmesh_radial_faceloop_find_next
137  * - #bmesh_radial_validate
138  *
139  *
140  * 3: The Loop Cycle - A circle of face edges around a polygon.
141  * Base: polygon->lbase.
142  *
143  * The loop cycle keeps track of a faces vertices and edges. It should be noted that the
144  * direction of a loop cycle is either CW or CCW depending on the face normal, and is
145  * not oriented to the faces editedges.
146  *
147  * Functions relating to this cycle:
148  * - bmesh_cycle_XXX family of functions.
149  *
150  *
151  * \note the order of elements in all cycles except the loop cycle is undefined. This
152  * leads to slightly increased seek time for deriving some adjacency relations, however the
153  * advantage is that no intrinsic properties of the data structures are dependent upon the
154  * cycle order and all non-manifold conditions are represented trivially.
155  */
156
157 BLI_INLINE BMDiskLink *bmesh_disk_edge_link_from_vert(BMEdge *e, BMVert *v)
158 {
159         if (v == e->v1) {
160                 return &e->v1_disk_link;
161         }
162         else {
163                 BLI_assert(v == e->v2);
164                 return &e->v2_disk_link;
165         }
166 }
167
168 int bmesh_disk_edge_append(BMEdge *e, BMVert *v)
169 {
170         if (!v->e) {
171                 BMDiskLink *dl1 = bmesh_disk_edge_link_from_vert(e, v);
172
173                 v->e = e;
174                 dl1->next = dl1->prev = e;
175         }
176         else {
177                 BMDiskLink *dl1, *dl2, *dl3;
178
179                 dl1 = bmesh_disk_edge_link_from_vert(e, v);
180                 dl2 = bmesh_disk_edge_link_from_vert(v->e, v);
181                 dl3 = dl2->prev ? bmesh_disk_edge_link_from_vert(dl2->prev, v) : NULL;
182
183                 dl1->next = v->e;
184                 dl1->prev = dl2->prev;
185
186                 dl2->prev = e;
187                 if (dl3)
188                         dl3->next = e;
189         }
190
191         return TRUE;
192 }
193
194 void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
195 {
196         BMDiskLink *dl1, *dl2;
197
198         dl1 = bmesh_disk_edge_link_from_vert(e, v);
199         if (dl1->prev) {
200                 dl2 = bmesh_disk_edge_link_from_vert(dl1->prev, v);
201                 dl2->next = dl1->next;
202         }
203
204         if (dl1->next) {
205                 dl2 = bmesh_disk_edge_link_from_vert(dl1->next, v);
206                 dl2->prev = dl1->prev;
207         }
208
209         if (v->e == e)
210                 v->e = (e != dl1->next) ? dl1->next : NULL;
211
212         dl1->next = dl1->prev = NULL;
213 }
214
215 /**
216  * \brief Next Disk Edge
217  *
218  * Find the next edge in a disk cycle
219  *
220  * \return Pointer to the next edge in the disk cycle for the vertex v.
221  */
222 BMEdge *bmesh_disk_edge_next(BMEdge *e, BMVert *v)
223 {
224         if (v == e->v1)
225                 return e->v1_disk_link.next;
226         if (v == e->v2)
227                 return e->v2_disk_link.next;
228         return NULL;
229 }
230
231 BMEdge *bmesh_disk_edge_prev(BMEdge *e, BMVert *v)
232 {
233         if (v == e->v1)
234                 return e->v1_disk_link.prev;
235         if (v == e->v2)
236                 return e->v2_disk_link.prev;
237         return NULL;
238 }
239
240 BMEdge *bmesh_disk_edge_exists(BMVert *v1, BMVert *v2)
241 {
242         BMEdge *e_iter, *e_first;
243         
244         if (v1->e) {
245                 e_first = e_iter = v1->e;
246
247                 do {
248                         if (bmesh_verts_in_edge(v1, v2, e_iter)) {
249                                 return e_iter;
250                         }
251                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v1)) != e_first);
252         }
253         
254         return NULL;
255 }
256
257 int bmesh_disk_count(BMVert *v)
258 {
259         if (v->e) {
260                 BMEdge *e_first, *e_iter;
261                 int count = 0;
262
263                 e_iter = e_first = v->e;
264
265                 do {
266                         if (!e_iter) {
267                                 return 0;
268                         }
269
270                         if (count >= (1 << 20)) {
271                                 printf("bmesh error: infinite loop in disk cycle!\n");
272                                 return 0;
273                         }
274                         count++;
275                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
276                 return count;
277         }
278         else {
279                 return 0;
280         }
281 }
282
283 int bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
284 {
285         BMEdge *e_iter;
286
287         if (!BM_vert_in_edge(e, v))
288                 return FALSE;
289         if (bmesh_disk_count(v) != len || len == 0)
290                 return FALSE;
291
292         e_iter = e;
293         do {
294                 if (len != 1 && bmesh_disk_edge_prev(e_iter, v) == e_iter) {
295                         return FALSE;
296                 }
297         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
298
299         return TRUE;
300 }
301
302 /**
303  * \brief DISK COUNT FACE VERT
304  *
305  * Counts the number of loop users
306  * for this vertex. Note that this is
307  * equivalent to counting the number of
308  * faces incident upon this vertex
309  */
310 int bmesh_disk_facevert_count(BMVert *v)
311 {
312         /* is there an edge on this vert at all */
313         if (v->e) {
314                 BMEdge *e_first, *e_iter;
315                 int count = 0;
316
317                 /* first, loop around edge */
318                 e_first = e_iter = v->e;
319                 do {
320                         if (e_iter->l) {
321                                 count += bmesh_radial_facevert_count(e_iter->l, v);
322                         }
323                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
324                 return count;
325         }
326         else {
327                 return 0;
328         }
329 }
330
331 /**
332  * \brief FIND FIRST FACE EDGE
333  *
334  * Finds the first edge in a vertices
335  * Disk cycle that has one of this
336  * vert's loops attached
337  * to it.
338  */
339 BMEdge *bmesh_disk_faceedge_find_first(BMEdge *e, BMVert *v)
340 {
341         BMEdge *searchedge = NULL;
342         searchedge = e;
343         do {
344                 if (searchedge->l && bmesh_radial_facevert_count(searchedge->l, v)) {
345                         return searchedge;
346                 }
347         } while ((searchedge = bmesh_disk_edge_next(searchedge, v)) != e);
348
349         return NULL;
350 }
351
352 BMEdge *bmesh_disk_faceedge_find_next(BMEdge *e, BMVert *v)
353 {
354         BMEdge *searchedge = NULL;
355         searchedge = bmesh_disk_edge_next(e, v);
356         do {
357                 if (searchedge->l && bmesh_radial_facevert_count(searchedge->l, v)) {
358                         return searchedge;
359                 }
360         } while ((searchedge = bmesh_disk_edge_next(searchedge, v)) != e);
361         return e;
362 }
363
364 /*****radial cycle functions, e.g. loops surrounding edges**** */
365 int bmesh_radial_validate(int radlen, BMLoop *l)
366 {
367         BMLoop *l_iter = l;
368         int i = 0;
369         
370         if (bmesh_radial_length(l) != radlen)
371                 return FALSE;
372
373         do {
374                 if (UNLIKELY(!l_iter)) {
375                         BMESH_ASSERT(0);
376                         return FALSE;
377                 }
378                 
379                 if (l_iter->e != l->e)
380                         return FALSE;
381                 if (l_iter->v != l->e->v1 && l_iter->v != l->e->v2)
382                         return FALSE;
383                 
384                 if (UNLIKELY(i > BM_LOOP_RADIAL_MAX)) {
385                         BMESH_ASSERT(0);
386                         return FALSE;
387                 }
388                 
389                 i++;
390         } while ((l_iter = l_iter->radial_next) != l);
391
392         return TRUE;
393 }
394
395 /**
396  * \brief BMESH RADIAL REMOVE LOOP
397  *
398  * Removes a loop from an radial cycle. If edge e is non-NULL
399  * it should contain the radial cycle, and it will also get
400  * updated (in the case that the edge's link into the radial
401  * cycle was the loop which is being removed from the cycle).
402  */
403 void bmesh_radial_loop_remove(BMLoop *l, BMEdge *e)
404 {
405         /* if e is non-NULL, l must be in the radial cycle of e */
406         if (UNLIKELY(e && e != l->e)) {
407                 BMESH_ASSERT(0);
408         }
409
410         if (l->radial_next != l) {
411                 if (e && l == e->l)
412                         e->l = l->radial_next;
413
414                 l->radial_next->radial_prev = l->radial_prev;
415                 l->radial_prev->radial_next = l->radial_next;
416         }
417         else {
418                 if (e) {
419                         if (l == e->l) {
420                                 e->l = NULL;
421                         }
422                         else {
423                                 BMESH_ASSERT(0);
424                         }
425                 }
426         }
427
428         /* l is no longer in a radial cycle; empty the links
429          * to the cycle and the link back to an edge */
430         l->radial_next = l->radial_prev = NULL;
431         l->e = NULL;
432 }
433
434
435 /**
436  * \brief BME RADIAL FIND FIRST FACE VERT
437  *
438  * Finds the first loop of v around radial
439  * cycle
440  */
441 BMLoop *bmesh_radial_faceloop_find_first(BMLoop *l, BMVert *v)
442 {
443         BMLoop *l_iter;
444         l_iter = l;
445         do {
446                 if (l_iter->v == v) {
447                         return l_iter;
448                 }
449         } while ((l_iter = l_iter->radial_next) != l);
450         return NULL;
451 }
452
453 BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v)
454 {
455         BMLoop *l_iter;
456         l_iter = l->radial_next;
457         do {
458                 if (l_iter->v == v) {
459                         return l_iter;
460                 }
461         } while ((l_iter = l_iter->radial_next) != l);
462         return l;
463 }
464
465 int bmesh_radial_length(BMLoop *l)
466 {
467         BMLoop *l_iter = l;
468         int i = 0;
469
470         if (!l)
471                 return 0;
472
473         do {
474                 if (UNLIKELY(!l_iter)) {
475                         /* radial cycle is broken (not a circulat loop) */
476                         BMESH_ASSERT(0);
477                         return 0;
478                 }
479                 
480                 i++;
481                 if (UNLIKELY(i >= BM_LOOP_RADIAL_MAX)) {
482                         BMESH_ASSERT(0);
483                         return -1;
484                 }
485         } while ((l_iter = l_iter->radial_next) != l);
486
487         return i;
488 }
489
490 void bmesh_radial_append(BMEdge *e, BMLoop *l)
491 {
492         if (e->l == NULL) {
493                 e->l = l;
494                 l->radial_next = l->radial_prev = l;
495         }
496         else {
497                 l->radial_prev = e->l;
498                 l->radial_next = e->l->radial_next;
499
500                 e->l->radial_next->radial_prev = l;
501                 e->l->radial_next = l;
502
503                 e->l = l;
504         }
505
506         if (UNLIKELY(l->e && l->e != e)) {
507                 /* l is already in a radial cycle for a different edge */
508                 BMESH_ASSERT(0);
509         }
510         
511         l->e = e;
512 }
513
514 int bmesh_radial_face_find(BMEdge *e, BMFace *f)
515 {
516         BMLoop *l_iter;
517         int i, len;
518
519         len = bmesh_radial_length(e->l);
520         for (i = 0, l_iter = e->l; i < len; i++, l_iter = l_iter->radial_next) {
521                 if (l_iter->f == f)
522                         return TRUE;
523         }
524         return FALSE;
525 }
526
527 /**
528  * \brief RADIAL COUNT FACE VERT
529  *
530  * Returns the number of times a vertex appears
531  * in a radial cycle
532  */
533 int bmesh_radial_facevert_count(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 = l_iter->radial_next) != 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 }