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