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