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