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