Merge branch 'blender2.7'
[blender.git] / source / blender / bmesh / intern / bmesh_iterators.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
17 /** \file \ingroup bmesh
18  *
19  * Functions to abstract looping over bmesh data structures.
20  *
21  * See: bmesh_iterators_inlin.c too, some functions are here for speed reasons.
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_utildefines.h"
27 #include "BLI_bitmap.h"
28
29 #include "bmesh.h"
30 #include "intern/bmesh_private.h"
31
32 const char bm_iter_itype_htype_map[BM_ITYPE_MAX] = {
33         '\0',
34         BM_VERT, /* BM_VERTS_OF_MESH */
35         BM_EDGE, /* BM_EDGES_OF_MESH */
36         BM_FACE, /* BM_FACES_OF_MESH */
37         BM_EDGE, /* BM_EDGES_OF_VERT */
38         BM_FACE, /* BM_FACES_OF_VERT */
39         BM_LOOP, /* BM_LOOPS_OF_VERT */
40         BM_VERT, /* BM_VERTS_OF_EDGE */
41         BM_FACE, /* BM_FACES_OF_EDGE */
42         BM_VERT, /* BM_VERTS_OF_FACE */
43         BM_EDGE, /* BM_EDGES_OF_FACE */
44         BM_LOOP, /* BM_LOOPS_OF_FACE */
45         BM_LOOP, /* BM_LOOPS_OF_LOOP */
46         BM_LOOP  /* BM_LOOPS_OF_EDGE */
47 };
48
49 /**
50  * Utility function.
51  */
52 int BM_iter_mesh_count(const char itype, BMesh *bm)
53 {
54         int count;
55
56         switch (itype) {
57                 case BM_VERTS_OF_MESH:
58                         count = bm->totvert;
59                         break;
60                 case BM_EDGES_OF_MESH:
61                         count = bm->totedge;
62                         break;
63                 case BM_FACES_OF_MESH:
64                         count = bm->totface;
65                         break;
66                 default:
67                         count = 0;
68                         BLI_assert(0);
69                         break;
70         }
71
72         return count;
73 }
74
75 /**
76  * \note Use #BM_vert_at_index / #BM_edge_at_index / #BM_face_at_index for mesh arrays.
77  */
78 void *BM_iter_at_index(BMesh *bm, const char itype, void *data, int index)
79 {
80         BMIter iter;
81         void *val;
82         int i;
83
84         /* sanity check */
85         if (index < 0) {
86                 return NULL;
87         }
88
89         val = BM_iter_new(&iter, bm, itype, data);
90
91         i = 0;
92         while (i < index) {
93                 val = BM_iter_step(&iter);
94                 i++;
95         }
96
97         return val;
98 }
99
100
101 /**
102  * \brief Iterator as Array
103  *
104  * Sometimes its convenient to get the iterator as an array
105  * to avoid multiple calls to #BM_iter_at_index.
106  */
107 int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len)
108 {
109         int i = 0;
110
111         /* sanity check */
112         if (len > 0) {
113                 BMIter iter;
114                 void *ele;
115
116                 for (ele = BM_iter_new(&iter, bm, itype, data); ele; ele = BM_iter_step(&iter)) {
117                         array[i] = ele;
118                         i++;
119                         if (i == len) {
120                                 return len;
121                         }
122                 }
123         }
124
125         return i;
126 }
127 /**
128  * \brief Operator Iterator as Array
129  *
130  * Sometimes its convenient to get the iterator as an array.
131  */
132 int BMO_iter_as_array(
133         BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask,
134         void **array, const int len)
135 {
136         int i = 0;
137
138         /* sanity check */
139         if (len > 0) {
140                 BMOIter oiter;
141                 void *ele;
142
143                 for (ele = BMO_iter_new(&oiter, slot_args, slot_name, restrictmask); ele; ele = BMO_iter_step(&oiter)) {
144                         array[i] = ele;
145                         i++;
146                         if (i == len) {
147                                 return len;
148                         }
149                 }
150         }
151
152         return i;
153 }
154
155
156 /**
157  * \brief Iterator as Array
158  *
159  * Allocates a new array, has the advantage that you dont need to know the size ahead of time.
160  *
161  * Takes advantage of less common iterator usage to avoid counting twice,
162  * which you might end up doing when #BM_iter_as_array is used.
163  *
164  * Caller needs to free the array.
165  */
166 void *BM_iter_as_arrayN(
167         BMesh *bm, const char itype, void *data, int *r_len,
168         /* optional args to avoid an alloc (normally stack array) */
169         void **stack_array, int stack_array_size)
170 {
171         BMIter iter;
172
173         BLI_assert(stack_array_size == 0 || (stack_array_size && stack_array));
174
175         /* we can't rely on coun't being set */
176         switch (itype) {
177                 case BM_VERTS_OF_MESH:
178                         iter.count = bm->totvert;
179                         break;
180                 case BM_EDGES_OF_MESH:
181                         iter.count = bm->totedge;
182                         break;
183                 case BM_FACES_OF_MESH:
184                         iter.count = bm->totface;
185                         break;
186                 default:
187                         break;
188         }
189
190         if (BM_iter_init(&iter, bm, itype, data) && iter.count > 0) {
191                 BMElem *ele;
192                 BMElem **array = iter.count > stack_array_size ?
193                                  MEM_mallocN(sizeof(ele) * iter.count, __func__) :
194                                  stack_array;
195                 int i = 0;
196
197                 *r_len = iter.count;  /* set before iterating */
198
199                 while ((ele = BM_iter_step(&iter))) {
200                         array[i++] = ele;
201                 }
202                 return array;
203         }
204         else {
205                 *r_len = 0;
206                 return NULL;
207         }
208 }
209
210 void *BMO_iter_as_arrayN(
211         BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, const char restrictmask,
212         int *r_len,
213         /* optional args to avoid an alloc (normally stack array) */
214         void **stack_array, int stack_array_size)
215 {
216         BMOIter iter;
217         BMElem *ele;
218         int count = BMO_slot_buffer_count(slot_args, slot_name);
219
220         BLI_assert(stack_array_size == 0 || (stack_array_size && stack_array));
221
222         if ((ele = BMO_iter_new(&iter, slot_args, slot_name, restrictmask)) && count > 0) {
223                 BMElem **array = count > stack_array_size ?
224                                  MEM_mallocN(sizeof(ele) * count, __func__) :
225                                  stack_array;
226                 int i = 0;
227
228                 do {
229                         array[i++] = ele;
230                 } while ((ele = BMO_iter_step(&iter)));
231                 BLI_assert(i <= count);
232
233                 if (i != count) {
234                         if ((void **)array != stack_array) {
235                                 array = MEM_reallocN(array, sizeof(ele) * i);
236                         }
237                 }
238                 *r_len = i;
239                 return array;
240         }
241         else {
242                 *r_len = 0;
243                 return NULL;
244         }
245 }
246
247 int BM_iter_mesh_bitmap_from_filter(
248         const char itype, BMesh *bm,
249         BLI_bitmap *bitmap,
250         bool (*test_fn)(BMElem *, void *user_data),
251         void *user_data)
252 {
253         BMIter iter;
254         BMElem *ele;
255         int i;
256         int bitmap_enabled = 0;
257
258         BM_ITER_MESH_INDEX (ele, &iter, bm, itype, i) {
259                 if (test_fn(ele, user_data)) {
260                         BLI_BITMAP_ENABLE(bitmap, i);
261                         bitmap_enabled++;
262                 }
263                 else {
264                         BLI_BITMAP_DISABLE(bitmap, i);
265                 }
266         }
267
268         return bitmap_enabled;
269 }
270
271 /**
272  * Needed when we want to check faces, but return a loop aligned array.
273  */
274 int BM_iter_mesh_bitmap_from_filter_tessface(
275         BMesh *bm,
276         BLI_bitmap *bitmap,
277         bool (*test_fn)(BMFace *, void *user_data),
278         void *user_data)
279 {
280         BMIter iter;
281         BMFace *f;
282         int i;
283         int j = 0;
284         int bitmap_enabled = 0;
285
286         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
287                 if (test_fn(f, user_data)) {
288                         for (int tri = 2; tri < f->len; tri++) {
289                                 BLI_BITMAP_ENABLE(bitmap, j);
290                                 bitmap_enabled++;
291                                 j++;
292                         }
293                 }
294                 else {
295                         for (int tri = 2; tri < f->len; tri++) {
296                                 BLI_BITMAP_DISABLE(bitmap, j);
297                                 j++;
298                         }
299                 }
300         }
301
302         return bitmap_enabled;
303 }
304
305 /**
306  * \brief Elem Iter Flag Count
307  *
308  * Counts how many flagged / unflagged items are found in this element.
309  */
310 int BM_iter_elem_count_flag(const char itype, void *data, const char hflag, const bool value)
311 {
312         BMIter iter;
313         BMElem *ele;
314         int count = 0;
315
316         BM_ITER_ELEM (ele, &iter, data, itype) {
317                 if (BM_elem_flag_test_bool(ele, hflag) == value) {
318                         count++;
319                 }
320         }
321
322         return count;
323 }
324
325 /**
326  * \brief Elem Iter Tool Flag Count
327  *
328  * Counts how many flagged / unflagged items are found in this element.
329  */
330 int BMO_iter_elem_count_flag(
331         BMesh *bm, const char itype, void *data,
332         const short oflag, const bool value)
333 {
334         BMIter iter;
335         int count = 0;
336
337         /* loops have no header flags */
338         BLI_assert(bm_iter_itype_htype_map[itype] != BM_LOOP);
339
340         switch (bm_iter_itype_htype_map[itype]) {
341                 case BM_VERT:
342                 {
343                         BMVert *ele;
344                         BM_ITER_ELEM (ele, &iter, data, itype) {
345                                 if (BMO_vert_flag_test_bool(bm, ele, oflag) == value) {
346                                         count++;
347                                 }
348                         }
349                         break;
350                 }
351                 case BM_EDGE:
352                 {
353                         BMEdge *ele;
354                         BM_ITER_ELEM (ele, &iter, data, itype) {
355                                 if (BMO_edge_flag_test_bool(bm, ele, oflag) == value) {
356                                         count++;
357                                 }
358                         }
359                         break;
360                 }
361                 case BM_FACE:
362                 {
363                         BMFace *ele;
364                         BM_ITER_ELEM (ele, &iter, data, itype) {
365                                 if (BMO_face_flag_test_bool(bm, ele, oflag) == value) {
366                                         count++;
367                                 }
368                         }
369                         break;
370                 }
371
372         }
373         return count;
374 }
375
376
377 /**
378  * \brief Mesh Iter Flag Count
379  *
380  * Counts how many flagged / unflagged items are found in this mesh.
381  */
382 int BM_iter_mesh_count_flag(const char itype, BMesh *bm, const char hflag, const bool value)
383 {
384         BMIter iter;
385         BMElem *ele;
386         int count = 0;
387
388         BM_ITER_MESH (ele, &iter, bm, itype) {
389                 if (BM_elem_flag_test_bool(ele, hflag) == value) {
390                         count++;
391                 }
392         }
393
394         return count;
395 }
396
397 /**
398  * Notes on iterator implementation:
399  *
400  * Iterators keep track of the next element in a sequence.
401  * When a step() callback is invoked the current value of 'next'
402  * is stored to be returned later and the next variable is incremented.
403  *
404  * When the end of a sequence is reached, next should always equal NULL
405  *
406  * The 'bmiter__' prefix is used because these are used in
407  * bmesh_iterators_inine.c but should otherwise be seen as
408  * private.
409  */
410
411 /*
412  * VERT OF MESH CALLBACKS
413  */
414
415 /* see bug [#36923] for why we need this,
416  * allow adding but not removing, this isnt _totally_ safe since
417  * you could add/remove within the same loop, but catches common cases
418  */
419 #ifdef DEBUG
420 #  define USE_IMMUTABLE_ASSERT
421 #endif
422
423 void bmiter__elem_of_mesh_begin(struct BMIter__elem_of_mesh *iter)
424 {
425 #ifdef USE_IMMUTABLE_ASSERT
426         ((BMIter *)iter)->count = BLI_mempool_len(iter->pooliter.pool);
427 #endif
428         BLI_mempool_iternew(iter->pooliter.pool, &iter->pooliter);
429 }
430
431 void *bmiter__elem_of_mesh_step(struct BMIter__elem_of_mesh *iter)
432 {
433 #ifdef USE_IMMUTABLE_ASSERT
434         BLI_assert(((BMIter *)iter)->count <= BLI_mempool_len(iter->pooliter.pool));
435 #endif
436         return BLI_mempool_iterstep(&iter->pooliter);
437 }
438
439 #ifdef USE_IMMUTABLE_ASSERT
440 #  undef USE_IMMUTABLE_ASSERT
441 #endif
442
443 /*
444  * EDGE OF VERT CALLBACKS
445  */
446
447 void  bmiter__edge_of_vert_begin(struct BMIter__edge_of_vert *iter)
448 {
449         if (iter->vdata->e) {
450                 iter->e_first = iter->vdata->e;
451                 iter->e_next = iter->vdata->e;
452         }
453         else {
454                 iter->e_first = NULL;
455                 iter->e_next = NULL;
456         }
457 }
458
459 void  *bmiter__edge_of_vert_step(struct BMIter__edge_of_vert *iter)
460 {
461         BMEdge *e_curr = iter->e_next;
462
463         if (iter->e_next) {
464                 iter->e_next = bmesh_disk_edge_next(iter->e_next, iter->vdata);
465                 if (iter->e_next == iter->e_first) {
466                         iter->e_next = NULL;
467                 }
468         }
469
470         return e_curr;
471 }
472
473 /*
474  * FACE OF VERT CALLBACKS
475  */
476
477 void  bmiter__face_of_vert_begin(struct BMIter__face_of_vert *iter)
478 {
479         ((BMIter *)iter)->count = bmesh_disk_facevert_count(iter->vdata);
480         if (((BMIter *)iter)->count) {
481                 iter->l_first = bmesh_disk_faceloop_find_first(iter->vdata->e, iter->vdata);
482                 iter->e_first = iter->l_first->e;
483                 iter->e_next = iter->e_first;
484                 iter->l_next = iter->l_first;
485         }
486         else {
487                 iter->l_first = iter->l_next = NULL;
488                 iter->e_first = iter->e_next = NULL;
489         }
490 }
491 void  *bmiter__face_of_vert_step(struct BMIter__face_of_vert *iter)
492 {
493         BMLoop *l_curr = iter->l_next;
494
495         if (((BMIter *)iter)->count && iter->l_next) {
496                 ((BMIter *)iter)->count--;
497                 iter->l_next = bmesh_radial_faceloop_find_next(iter->l_next, iter->vdata);
498                 if (iter->l_next == iter->l_first) {
499                         iter->e_next = bmesh_disk_faceedge_find_next(iter->e_next, iter->vdata);
500                         iter->l_first = bmesh_radial_faceloop_find_first(iter->e_next->l, iter->vdata);
501                         iter->l_next = iter->l_first;
502                 }
503         }
504
505         if (!((BMIter *)iter)->count) {
506                 iter->l_next = NULL;
507         }
508
509         return l_curr ? l_curr->f : NULL;
510 }
511
512
513 /*
514  * LOOP OF VERT CALLBACKS
515  */
516
517 void  bmiter__loop_of_vert_begin(struct BMIter__loop_of_vert *iter)
518 {
519         ((BMIter *)iter)->count = bmesh_disk_facevert_count(iter->vdata);
520         if (((BMIter *)iter)->count) {
521                 iter->l_first = bmesh_disk_faceloop_find_first(iter->vdata->e, iter->vdata);
522                 iter->e_first = iter->l_first->e;
523                 iter->e_next = iter->e_first;
524                 iter->l_next = iter->l_first;
525         }
526         else {
527                 iter->l_first = iter->l_next = NULL;
528                 iter->e_first = iter->e_next = NULL;
529         }
530 }
531 void  *bmiter__loop_of_vert_step(struct BMIter__loop_of_vert *iter)
532 {
533         BMLoop *l_curr = iter->l_next;
534
535         if (((BMIter *)iter)->count) {
536                 ((BMIter *)iter)->count--;
537                 iter->l_next = bmesh_radial_faceloop_find_next(iter->l_next, iter->vdata);
538                 if (iter->l_next == iter->l_first) {
539                         iter->e_next = bmesh_disk_faceedge_find_next(iter->e_next, iter->vdata);
540                         iter->l_first = bmesh_radial_faceloop_find_first(iter->e_next->l, iter->vdata);
541                         iter->l_next = iter->l_first;
542                 }
543         }
544
545         if (!((BMIter *)iter)->count) {
546                 iter->l_next = NULL;
547         }
548
549         /* NULL on finish */
550         return l_curr;
551 }
552
553 /*
554  * LOOP OF EDGE CALLBACKS
555  */
556
557 void  bmiter__loop_of_edge_begin(struct BMIter__loop_of_edge *iter)
558 {
559         iter->l_first = iter->l_next = iter->edata->l;
560 }
561
562 void  *bmiter__loop_of_edge_step(struct BMIter__loop_of_edge *iter)
563 {
564         BMLoop *l_curr = iter->l_next;
565
566         if (iter->l_next) {
567                 iter->l_next = iter->l_next->radial_next;
568                 if (iter->l_next == iter->l_first) {
569                         iter->l_next = NULL;
570                 }
571         }
572
573         /* NULL on finish */
574         return l_curr;
575 }
576
577 /*
578  * LOOP OF LOOP CALLBACKS
579  */
580
581 void  bmiter__loop_of_loop_begin(struct BMIter__loop_of_loop *iter)
582 {
583         iter->l_first = iter->ldata;
584         iter->l_next = iter->l_first->radial_next;
585
586         if (iter->l_next == iter->l_first)
587                 iter->l_next = NULL;
588 }
589
590 void  *bmiter__loop_of_loop_step(struct BMIter__loop_of_loop *iter)
591 {
592         BMLoop *l_curr = iter->l_next;
593
594         if (iter->l_next) {
595                 iter->l_next = iter->l_next->radial_next;
596                 if (iter->l_next == iter->l_first) {
597                         iter->l_next = NULL;
598                 }
599         }
600
601         /* NULL on finish */
602         return l_curr;
603 }
604
605 /*
606  * FACE OF EDGE CALLBACKS
607  */
608
609 void  bmiter__face_of_edge_begin(struct BMIter__face_of_edge *iter)
610 {
611         iter->l_first = iter->l_next = iter->edata->l;
612 }
613
614 void  *bmiter__face_of_edge_step(struct BMIter__face_of_edge *iter)
615 {
616         BMLoop *current = iter->l_next;
617
618         if (iter->l_next) {
619                 iter->l_next = iter->l_next->radial_next;
620                 if (iter->l_next == iter->l_first) {
621                         iter->l_next = NULL;
622                 }
623         }
624
625         return current ? current->f : NULL;
626 }
627
628 /*
629  * VERTS OF EDGE CALLBACKS
630  */
631
632 void  bmiter__vert_of_edge_begin(struct BMIter__vert_of_edge *iter)
633 {
634         ((BMIter *)iter)->count = 0;
635 }
636
637 void  *bmiter__vert_of_edge_step(struct BMIter__vert_of_edge *iter)
638 {
639         switch (((BMIter *)iter)->count++) {
640                 case 0:
641                         return iter->edata->v1;
642                 case 1:
643                         return iter->edata->v2;
644                 default:
645                         return NULL;
646         }
647 }
648
649 /*
650  * VERT OF FACE CALLBACKS
651  */
652
653 void  bmiter__vert_of_face_begin(struct BMIter__vert_of_face *iter)
654 {
655         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
656 }
657
658 void  *bmiter__vert_of_face_step(struct BMIter__vert_of_face *iter)
659 {
660         BMLoop *l_curr = iter->l_next;
661
662         if (iter->l_next) {
663                 iter->l_next = iter->l_next->next;
664                 if (iter->l_next == iter->l_first) {
665                         iter->l_next = NULL;
666                 }
667         }
668
669         return l_curr ? l_curr->v : NULL;
670 }
671
672 /*
673  * EDGE OF FACE CALLBACKS
674  */
675
676 void  bmiter__edge_of_face_begin(struct BMIter__edge_of_face *iter)
677 {
678         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
679 }
680
681 void  *bmiter__edge_of_face_step(struct BMIter__edge_of_face *iter)
682 {
683         BMLoop *l_curr = iter->l_next;
684
685         if (iter->l_next) {
686                 iter->l_next = iter->l_next->next;
687                 if (iter->l_next == iter->l_first) {
688                         iter->l_next = NULL;
689                 }
690         }
691
692         return l_curr ? l_curr->e : NULL;
693 }
694
695 /*
696  * LOOP OF FACE CALLBACKS
697  */
698
699 void  bmiter__loop_of_face_begin(struct BMIter__loop_of_face *iter)
700 {
701         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
702 }
703
704 void  *bmiter__loop_of_face_step(struct BMIter__loop_of_face *iter)
705 {
706         BMLoop *l_curr = iter->l_next;
707
708         if (iter->l_next) {
709                 iter->l_next = iter->l_next->next;
710                 if (iter->l_next == iter->l_first) {
711                         iter->l_next = NULL;
712                 }
713         }
714
715         return l_curr;
716 }