Merge branch 'blender2.7'
[blender.git] / source / blender / bmesh / intern / bmesh_structure.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2007 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file \ingroup bmesh
21  *
22  * Low level routines for manipulating the BM structure.
23  */
24
25 #include "BLI_utildefines.h"
26
27 #include "bmesh.h"
28 #include "intern/bmesh_private.h"
29
30 /**
31  * MISC utility functions.
32  */
33
34 void bmesh_disk_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src)
35 {
36         if (e->v1 == v_src) {
37                 e->v1 = v_dst;
38                 e->v1_disk_link.next = e->v1_disk_link.prev = NULL;
39         }
40         else if (e->v2 == v_src) {
41                 e->v2 = v_dst;
42                 e->v2_disk_link.next = e->v2_disk_link.prev = NULL;
43         }
44         else {
45                 BLI_assert(0);
46         }
47 }
48
49 /**
50  * Handles all connected data, use with care.
51  *
52  * Assumes caller has setup correct state before the swap is done.
53  */
54 void bmesh_edge_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src)
55 {
56         /* swap out loops */
57         if (e->l) {
58                 BMLoop *l_iter, *l_first;
59                 l_iter = l_first = e->l;
60                 do {
61                         if (l_iter->v == v_src) {
62                                 l_iter->v = v_dst;
63                         }
64                         else if (l_iter->next->v == v_src) {
65                                 l_iter->next->v = v_dst;
66                         }
67                         else {
68                                 BLI_assert(l_iter->prev->v != v_src);
69                         }
70                 } while ((l_iter = l_iter->radial_next) != l_first);
71         }
72
73         /* swap out edges */
74         bmesh_disk_vert_replace(e, v_dst, v_src);
75 }
76
77 void bmesh_disk_vert_replace(BMEdge *e, BMVert *v_dst, BMVert *v_src)
78 {
79         BLI_assert(e->v1 == v_src || e->v2 == v_src);
80         bmesh_disk_edge_remove(e, v_src);               /* remove e from tv's disk cycle */
81         bmesh_disk_vert_swap(e, v_dst, v_src);  /* swap out tv for v_new in e */
82         bmesh_disk_edge_append(e, v_dst);               /* add e to v_dst's disk cycle */
83         BLI_assert(e->v1 != e->v2);
84 }
85
86 /**
87  * \section bm_cycles BMesh Cycles
88  * (this is somewhat outdate, though bits of its API are still used) - joeedh
89  *
90  * Cycles are circular doubly linked lists that form the basis of adjacency
91  * information in the BME modeler. Full adjacency relations can be derived
92  * from examining these cycles very quickly. Although each cycle is a double
93  * circular linked list, each one is considered to have a 'base' or 'head',
94  * and care must be taken by Euler code when modifying the contents of a cycle.
95  *
96  * The contents of this file are split into two parts. First there are the
97  * bmesh_cycle family of functions which are generic circular double linked list
98  * procedures. The second part contains higher level procedures for supporting
99  * modification of specific cycle types.
100  *
101  * The three cycles explicitly stored in the BM data structure are as follows:
102  * 1: The Disk Cycle - A circle of edges around a vertex
103  * Base: vertex->edge pointer.
104  *
105  * This cycle is the most complicated in terms of its structure. Each bmesh_Edge contains
106  * two bmesh_CycleNode structures to keep track of that edges membership in the disk cycle
107  * of each of its vertices. However for any given vertex it may be the first in some edges
108  * in its disk cycle and the second for others. The bmesh_disk_XXX family of functions contain
109  * some nice utilities for navigating disk cycles in a way that hides this detail from the
110  * tool writer.
111  *
112  * Note that the disk cycle is completely independent from face data. One advantage of this
113  * is that wire edges are fully integrated into the topology database. Another is that the
114  * the disk cycle has no problems dealing with non-manifold conditions involving faces.
115  *
116  * Functions relating to this cycle:
117  * - #bmesh_disk_vert_replace
118  * - #bmesh_disk_edge_append
119  * - #bmesh_disk_edge_remove
120  * - #bmesh_disk_edge_next
121  * - #bmesh_disk_edge_prev
122  * - #bmesh_disk_facevert_count
123  * - #bmesh_disk_faceedge_find_first
124  * - #bmesh_disk_faceedge_find_next
125  * 2: The Radial Cycle - A circle of face edges (bmesh_Loop) around an edge
126  * Base: edge->l->radial structure.
127  *
128  * The radial cycle is similar to the radial cycle in the radial edge data structure.*
129  * Unlike the radial edge however, the radial cycle does not require a large amount of memory
130  * to store non-manifold conditions since BM does not keep track of region/shell information.
131  *
132  * Functions relating to this cycle:
133  * - #bmesh_radial_loop_append
134  * - #bmesh_radial_loop_remove
135  * - #bmesh_radial_facevert_count
136  * - #bmesh_radial_facevert_check
137  * - #bmesh_radial_faceloop_find_first
138  * - #bmesh_radial_faceloop_find_next
139  * - #bmesh_radial_validate
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  * \note the order of elements in all cycles except the loop cycle is undefined. This
150  * leads to slightly increased seek time for deriving some adjacency relations, however the
151  * advantage is that no intrinsic properties of the data structures are dependent upon the
152  * cycle order and all non-manifold conditions are represented trivially.
153  */
154
155 void bmesh_disk_edge_append(BMEdge *e, BMVert *v)
156 {
157         if (!v->e) {
158                 BMDiskLink *dl1 = bmesh_disk_edge_link_from_vert(e, v);
159
160                 v->e = e;
161                 dl1->next = dl1->prev = e;
162         }
163         else {
164                 BMDiskLink *dl1, *dl2, *dl3;
165
166                 dl1 = bmesh_disk_edge_link_from_vert(e, v);
167                 dl2 = bmesh_disk_edge_link_from_vert(v->e, v);
168                 dl3 = dl2->prev ? bmesh_disk_edge_link_from_vert(dl2->prev, v) : NULL;
169
170                 dl1->next = v->e;
171                 dl1->prev = dl2->prev;
172
173                 dl2->prev = e;
174                 if (dl3)
175                         dl3->next = e;
176         }
177 }
178
179 void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
180 {
181         BMDiskLink *dl1, *dl2;
182
183         dl1 = bmesh_disk_edge_link_from_vert(e, v);
184         if (dl1->prev) {
185                 dl2 = bmesh_disk_edge_link_from_vert(dl1->prev, v);
186                 dl2->next = dl1->next;
187         }
188
189         if (dl1->next) {
190                 dl2 = bmesh_disk_edge_link_from_vert(dl1->next, v);
191                 dl2->prev = dl1->prev;
192         }
193
194         if (v->e == e)
195                 v->e = (e != dl1->next) ? dl1->next : NULL;
196
197         dl1->next = dl1->prev = NULL;
198 }
199
200 BMEdge *bmesh_disk_edge_exists(const BMVert *v1, const BMVert *v2)
201 {
202         BMEdge *e_iter, *e_first;
203
204         if (v1->e) {
205                 e_first = e_iter = v1->e;
206
207                 do {
208                         if (BM_verts_in_edge(v1, v2, e_iter)) {
209                                 return e_iter;
210                         }
211                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v1)) != e_first);
212         }
213
214         return NULL;
215 }
216
217 int bmesh_disk_count(const BMVert *v)
218 {
219         int count = 0;
220         if (v->e) {
221                 BMEdge *e_first, *e_iter;
222                 e_iter = e_first = v->e;
223                 do {
224                         count++;
225                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
226         }
227         return count;
228 }
229
230 int bmesh_disk_count_at_most(const BMVert *v, const int count_max)
231 {
232         int count = 0;
233         if (v->e) {
234                 BMEdge *e_first, *e_iter;
235                 e_iter = e_first = v->e;
236                 do {
237                         count++;
238                         if (count == count_max) {
239                                 break;
240                         }
241                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
242         }
243         return count;
244 }
245
246 bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
247 {
248         BMEdge *e_iter;
249
250         if (!BM_vert_in_edge(e, v)) {
251                 return false;
252         }
253         if (len == 0 || bmesh_disk_count_at_most(v, len + 1) != len) {
254                 return false;
255         }
256
257         e_iter = e;
258         do {
259                 if (len != 1 && bmesh_disk_edge_prev(e_iter, v) == e_iter) {
260                         return false;
261                 }
262         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
263
264         return true;
265 }
266
267 /**
268  * \brief DISK COUNT FACE VERT
269  *
270  * Counts the number of loop users
271  * for this vertex. Note that this is
272  * equivalent to counting the number of
273  * faces incident upon this vertex
274  */
275 int bmesh_disk_facevert_count(const BMVert *v)
276 {
277         /* is there an edge on this vert at all */
278         int count = 0;
279         if (v->e) {
280                 BMEdge *e_first, *e_iter;
281
282                 /* first, loop around edge */
283                 e_first = e_iter = v->e;
284                 do {
285                         if (e_iter->l) {
286                                 count += bmesh_radial_facevert_count(e_iter->l, v);
287                         }
288                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
289         }
290         return count;
291 }
292
293 int bmesh_disk_facevert_count_at_most(const BMVert *v, const int count_max)
294 {
295         /* is there an edge on this vert at all */
296         int count = 0;
297         if (v->e) {
298                 BMEdge *e_first, *e_iter;
299
300                 /* first, loop around edge */
301                 e_first = e_iter = v->e;
302                 do {
303                         if (e_iter->l) {
304                                 count += bmesh_radial_facevert_count_at_most(e_iter->l, v, count_max - count);
305                                 if (count == count_max) {
306                                         break;
307                                 }
308                         }
309                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
310         }
311         return count;
312 }
313
314 /**
315  * \brief FIND FIRST FACE EDGE
316  *
317  * Finds the first edge in a vertices
318  * Disk cycle that has one of this
319  * vert's loops attached
320  * to it.
321  */
322 BMEdge *bmesh_disk_faceedge_find_first(const BMEdge *e, const BMVert *v)
323 {
324         const BMEdge *e_iter = e;
325         do {
326                 if (e_iter->l != NULL) {
327                         return (BMEdge *)((e_iter->l->v == v) ? e_iter : e_iter->l->next->e);
328                 }
329         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
330         return NULL;
331 }
332
333 /**
334  * Special case for BM_LOOPS_OF_VERT & BM_FACES_OF_VERT, avoids 2x calls.
335  *
336  * The returned BMLoop.e matches the result of #bmesh_disk_faceedge_find_first
337  */
338 BMLoop *bmesh_disk_faceloop_find_first(const BMEdge *e, const BMVert *v)
339 {
340         const BMEdge *e_iter = e;
341         do {
342                 if (e_iter->l != NULL) {
343                         return (e_iter->l->v == v) ? e_iter->l : e_iter->l->next;
344                 }
345         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
346         return NULL;
347 }
348
349 BMEdge *bmesh_disk_faceedge_find_next(const BMEdge *e, const BMVert *v)
350 {
351         BMEdge *e_find;
352         e_find = bmesh_disk_edge_next(e, v);
353         do {
354                 if (e_find->l && bmesh_radial_facevert_check(e_find->l, v)) {
355                         return e_find;
356                 }
357         } while ((e_find = bmesh_disk_edge_next(e_find, v)) != e);
358         return (BMEdge *)e;
359 }
360
361 /*****radial cycle functions, e.g. loops surrounding edges**** */
362 bool bmesh_radial_validate(int radlen, BMLoop *l)
363 {
364         BMLoop *l_iter = l;
365         int i = 0;
366
367         if (bmesh_radial_length(l) != radlen)
368                 return false;
369
370         do {
371                 if (UNLIKELY(!l_iter)) {
372                         BMESH_ASSERT(0);
373                         return false;
374                 }
375
376                 if (l_iter->e != l->e)
377                         return false;
378                 if (l_iter->v != l->e->v1 && l_iter->v != l->e->v2)
379                         return false;
380
381                 if (UNLIKELY(i > BM_LOOP_RADIAL_MAX)) {
382                         BMESH_ASSERT(0);
383                         return false;
384                 }
385
386                 i++;
387         } while ((l_iter = l_iter->radial_next) != l);
388
389         return true;
390 }
391
392 void bmesh_radial_loop_append(BMEdge *e, BMLoop *l)
393 {
394         if (e->l == NULL) {
395                 e->l = l;
396                 l->radial_next = l->radial_prev = l;
397         }
398         else {
399                 l->radial_prev = e->l;
400                 l->radial_next = e->l->radial_next;
401
402                 e->l->radial_next->radial_prev = l;
403                 e->l->radial_next = l;
404
405                 e->l = l;
406         }
407
408         if (UNLIKELY(l->e && l->e != e)) {
409                 /* l is already in a radial cycle for a different edge */
410                 BMESH_ASSERT(0);
411         }
412
413         l->e = e;
414 }
415
416 /**
417  * \brief BMESH RADIAL REMOVE LOOP
418  *
419  * Removes a loop from an radial cycle. If edge e is non-NULL
420  * it should contain the radial cycle, and it will also get
421  * updated (in the case that the edge's link into the radial
422  * cycle was the loop which is being removed from the cycle).
423  */
424 void bmesh_radial_loop_remove(BMEdge *e, BMLoop *l)
425 {
426         /* if e is non-NULL, l must be in the radial cycle of e */
427         if (UNLIKELY(e != l->e)) {
428                 BMESH_ASSERT(0);
429         }
430
431         if (l->radial_next != l) {
432                 if (l == e->l) {
433                         e->l = l->radial_next;
434                 }
435
436                 l->radial_next->radial_prev = l->radial_prev;
437                 l->radial_prev->radial_next = l->radial_next;
438         }
439         else {
440                 if (l == e->l) {
441                         e->l = NULL;
442                 }
443                 else {
444                         BMESH_ASSERT(0);
445                 }
446         }
447
448         /* l is no longer in a radial cycle; empty the links
449          * to the cycle and the link back to an edge */
450         l->radial_next = l->radial_prev = NULL;
451         l->e = NULL;
452 }
453
454 /**
455  * A version of #bmesh_radial_loop_remove which only performs the radial unlink,
456  * leaving the edge untouched.
457  */
458 void bmesh_radial_loop_unlink(BMLoop *l)
459 {
460         if (l->radial_next != l) {
461                 l->radial_next->radial_prev = l->radial_prev;
462                 l->radial_prev->radial_next = l->radial_next;
463         }
464
465         /* l is no longer in a radial cycle; empty the links
466          * to the cycle and the link back to an edge */
467         l->radial_next = l->radial_prev = NULL;
468         l->e = NULL;
469 }
470
471 /**
472  * \brief BME RADIAL FIND FIRST FACE VERT
473  *
474  * Finds the first loop of v around radial
475  * cycle
476  */
477 BMLoop *bmesh_radial_faceloop_find_first(const BMLoop *l, const BMVert *v)
478 {
479         const BMLoop *l_iter;
480         l_iter = l;
481         do {
482                 if (l_iter->v == v) {
483                         return (BMLoop *)l_iter;
484                 }
485         } while ((l_iter = l_iter->radial_next) != l);
486         return NULL;
487 }
488
489 BMLoop *bmesh_radial_faceloop_find_next(const BMLoop *l, const BMVert *v)
490 {
491         BMLoop *l_iter;
492         l_iter = l->radial_next;
493         do {
494                 if (l_iter->v == v) {
495                         return l_iter;
496                 }
497         } while ((l_iter = l_iter->radial_next) != l);
498         return (BMLoop *)l;
499 }
500
501 int bmesh_radial_length(const BMLoop *l)
502 {
503         const BMLoop *l_iter = l;
504         int i = 0;
505
506         if (!l)
507                 return 0;
508
509         do {
510                 if (UNLIKELY(!l_iter)) {
511                         /* radial cycle is broken (not a circulat loop) */
512                         BMESH_ASSERT(0);
513                         return 0;
514                 }
515
516                 i++;
517                 if (UNLIKELY(i >= BM_LOOP_RADIAL_MAX)) {
518                         BMESH_ASSERT(0);
519                         return -1;
520                 }
521         } while ((l_iter = l_iter->radial_next) != l);
522
523         return i;
524 }
525
526 /**
527  * \brief RADIAL COUNT FACE VERT
528  *
529  * Returns the number of times a vertex appears
530  * in a radial cycle
531  */
532 int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v)
533 {
534         const BMLoop *l_iter;
535         int count = 0;
536         l_iter = l;
537         do {
538                 if (l_iter->v == v) {
539                         count++;
540                 }
541         } while ((l_iter = l_iter->radial_next) != l);
542
543         return count;
544 }
545
546 int bmesh_radial_facevert_count_at_most(const BMLoop *l, const BMVert *v, const int count_max)
547 {
548         const BMLoop *l_iter;
549         int count = 0;
550         l_iter = l;
551         do {
552                 if (l_iter->v == v) {
553                         count++;
554                         if (count == count_max) {
555                                 break;
556                         }
557                 }
558         } while ((l_iter = l_iter->radial_next) != l);
559
560         return count;
561 }
562
563 /**
564  * \brief RADIAL CHECK FACE VERT
565  *
566  * Quicker check for ``bmesh_radial_facevert_count(...) != 0``
567  */
568 bool bmesh_radial_facevert_check(const BMLoop *l, const BMVert *v)
569 {
570         const BMLoop *l_iter;
571         l_iter = l;
572         do {
573                 if (l_iter->v == v) {
574                         return true;
575                 }
576         } while ((l_iter = l_iter->radial_next) != l);
577
578         return false;
579 }
580
581 /*****loop cycle functions, e.g. loops surrounding a face**** */
582 bool bmesh_loop_validate(BMFace *f)
583 {
584         int i;
585         int len = f->len;
586         BMLoop *l_iter, *l_first;
587
588         l_first = BM_FACE_FIRST_LOOP(f);
589
590         if (l_first == NULL) {
591                 return false;
592         }
593
594         /* Validate that the face loop cycle is the length specified by f->len */
595         for (i = 1, l_iter = l_first->next; i < len; i++, l_iter = l_iter->next) {
596                 if ((l_iter->f != f) ||
597                     (l_iter == l_first))
598                 {
599                         return false;
600                 }
601         }
602         if (l_iter != l_first) {
603                 return false;
604         }
605
606         /* Validate the loop->prev links also form a cycle of length f->len */
607         for (i = 1, l_iter = l_first->prev; i < len; i++, l_iter = l_iter->prev) {
608                 if (l_iter == l_first) {
609                         return false;
610                 }
611         }
612         if (l_iter != l_first) {
613                 return false;
614         }
615
616         return true;
617 }