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