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