code cleanup: spelling,
[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 /**
110  * \brief Iterator as Array
111  *
112  * Allocates a new array, has the advantage that you dont need to know the size ahead of time.
113  *
114  * Takes advantage of less common iterator usage to avoid counting twice,
115  * which you might end up doing when #BM_iter_as_array is used.
116  *
117  * Caller needs to free the array.
118  */
119 void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len,
120                         /* optional args to avoid an alloc (normally stack array) */
121                         void **stack_array, int stack_array_size)
122 {
123         BMIter iter;
124
125         BLI_assert(stack_array_size == 0 || (stack_array_size && stack_array));
126
127         /* we can't rely on coun't being set */
128         switch (itype) {
129                 case BM_VERTS_OF_MESH:
130                         iter.count = bm->totvert;
131                         break;
132                 case BM_EDGES_OF_MESH:
133                         iter.count = bm->totedge;
134                         break;
135                 case BM_FACES_OF_MESH:
136                         iter.count = bm->totface;
137                         break;
138                 default:
139                         break;
140         }
141
142         if (BM_iter_init(&iter, bm, itype, data) && iter.count > 0) {
143                 BMElem *ele;
144                 BMElem **array = iter.count > stack_array_size ?
145                                  MEM_mallocN(sizeof(ele) * iter.count, __func__) :
146                                  stack_array;
147                 int i = 0;
148
149                 *r_len = iter.count;  /* set before iterating */
150
151                 while ((ele = BM_iter_step(&iter))) {
152                         array[i++] = ele;
153                 }
154                 return array;
155         }
156         else {
157                 *r_len = 0;
158                 return NULL;
159         }
160 }
161
162 /**
163  * \brief Elem Iter Flag Count
164  *
165  * Counts how many flagged / unflagged items are found in this element.
166  */
167 int BM_iter_elem_count_flag(const char itype, void *data, const char hflag, const short value)
168 {
169         BMIter iter;
170         BMElem *ele;
171         int count = 0;
172
173         BLI_assert(ELEM(value, TRUE, FALSE));
174
175         for (ele = BM_iter_new(&iter, NULL, itype, data); ele; ele = BM_iter_step(&iter)) {
176                 if (BM_elem_flag_test_bool(ele, hflag) == value) {
177                         count++;
178                 }
179         }
180
181         return count;
182 }
183
184 /**
185  * \brief Mesh Iter Flag Count
186  *
187  * Counts how many flagged / unflagged items are found in this mesh.
188  */
189 int BM_iter_mesh_count_flag(const char itype, BMesh *bm, const char hflag, const short value)
190 {
191         BMIter iter;
192         BMElem *ele;
193         int count = 0;
194
195         BLI_assert(ELEM(value, TRUE, FALSE));
196
197         for (ele = BM_iter_new(&iter, bm, itype, NULL); ele; ele = BM_iter_step(&iter)) {
198                 if (BM_elem_flag_test_bool(ele, hflag) == value) {
199                         count++;
200                 }
201         }
202
203         return count;
204 }
205
206
207 /**
208  * \brief Init Iterator
209  *
210  * Clears the internal state of an iterator for begin() callbacks.
211  */
212 static void init_iterator(BMIter *iter)
213 {
214 //      iter->v_first = iter->v_next = NULL; // UNUSED
215         iter->e_first = iter->e_next = NULL;
216         iter->l_first = iter->l_next = NULL;
217 //      iter->f_first = iter->f_next = NULL; // UNUSED
218         iter->ldata = NULL;
219 }
220
221 /**
222  * Notes on iterator implementation:
223  *
224  * Iterators keep track of the next element in a sequence.
225  * When a step() callback is invoked the current value of 'next'
226  * is stored to be returned later and the next variable is incremented.
227  *
228  * When the end of a sequence is reached, next should always equal NULL
229  *
230  * The 'bmiter__' prefix is used because these are used in
231  * bmesh_iterators_inine.c but should otherwise be seen as
232  * private.
233  */
234
235 /*
236  * VERT OF MESH CALLBACKS
237  */
238
239 void bmiter__vert_of_mesh_begin(BMIter *iter)
240 {
241         BLI_mempool_iternew(iter->bm->vpool, &iter->pooliter);
242 }
243
244 void  *bmiter__vert_of_mesh_step(BMIter *iter)
245 {
246         return BLI_mempool_iterstep(&iter->pooliter);
247
248 }
249
250 void  bmiter__edge_of_mesh_begin(BMIter *iter)
251 {
252         BLI_mempool_iternew(iter->bm->epool, &iter->pooliter);
253         iter->count = iter->bm->totedge;  /* */
254 }
255
256 void  *bmiter__edge_of_mesh_step(BMIter *iter)
257 {
258         return BLI_mempool_iterstep(&iter->pooliter);
259
260 }
261
262 void  bmiter__face_of_mesh_begin(BMIter *iter)
263 {
264         BLI_mempool_iternew(iter->bm->fpool, &iter->pooliter);
265 }
266
267 void  *bmiter__face_of_mesh_step(BMIter *iter)
268 {
269         return BLI_mempool_iterstep(&iter->pooliter);
270
271 }
272
273 /*
274  * EDGE OF VERT CALLBACKS
275  */
276
277 void  bmiter__edge_of_vert_begin(BMIter *iter)
278 {
279         init_iterator(iter);
280         if (iter->vdata->e) {
281                 iter->e_first = iter->vdata->e;
282                 iter->e_next = iter->vdata->e;
283         }
284 }
285
286 void  *bmiter__edge_of_vert_step(BMIter *iter)
287 {
288         BMEdge *current = iter->e_next;
289
290         if (iter->e_next)
291                 iter->e_next = bmesh_disk_edge_next(iter->e_next, iter->vdata);
292         
293         if (iter->e_next == iter->e_first) iter->e_next = NULL;
294
295         return current;
296 }
297
298 /*
299  * FACE OF VERT CALLBACKS
300  */
301
302 void  bmiter__face_of_vert_begin(BMIter *iter)
303 {
304         init_iterator(iter);
305         iter->count = 0;
306         if (iter->vdata->e)
307                 iter->count = bmesh_disk_facevert_count(iter->vdata);
308         if (iter->count) {
309                 iter->e_first = bmesh_disk_faceedge_find_first(iter->vdata->e, iter->vdata);
310                 iter->e_next = iter->e_first;
311                 iter->l_first = bmesh_radial_faceloop_find_first(iter->e_first->l, iter->vdata);
312                 iter->l_next = iter->l_first;
313         }
314 }
315 void  *bmiter__face_of_vert_step(BMIter *iter)
316 {
317         BMLoop *current = iter->l_next;
318
319         if (iter->count && iter->l_next) {
320                 iter->count--;
321                 iter->l_next = bmesh_radial_faceloop_find_next(iter->l_next, iter->vdata);
322                 if (iter->l_next == iter->l_first) {
323                         iter->e_next = bmesh_disk_faceedge_find_next(iter->e_next, iter->vdata);
324                         iter->l_first = bmesh_radial_faceloop_find_first(iter->e_next->l, iter->vdata);
325                         iter->l_next = iter->l_first;
326                 }
327         }
328         
329         if (!iter->count) iter->l_next = NULL;
330
331         return current ? current->f : NULL;
332 }
333
334
335 /*
336  * LOOP OF VERT CALLBACKS
337  *
338  */
339
340 void  bmiter__loop_of_vert_begin(BMIter *iter)
341 {
342         init_iterator(iter);
343         iter->count = 0;
344         if (iter->vdata->e)
345                 iter->count = bmesh_disk_facevert_count(iter->vdata);
346         if (iter->count) {
347                 iter->e_first = bmesh_disk_faceedge_find_first(iter->vdata->e, iter->vdata);
348                 iter->e_next = iter->e_first;
349                 iter->l_first = bmesh_radial_faceloop_find_first(iter->e_first->l, iter->vdata);
350                 iter->l_next = iter->l_first;
351         }
352 }
353 void  *bmiter__loop_of_vert_step(BMIter *iter)
354 {
355         BMLoop *current = iter->l_next;
356
357         if (iter->count) {
358                 iter->count--;
359                 iter->l_next = bmesh_radial_faceloop_find_next(iter->l_next, iter->vdata);
360                 if (iter->l_next == iter->l_first) {
361                         iter->e_next = bmesh_disk_faceedge_find_next(iter->e_next, iter->vdata);
362                         iter->l_first = bmesh_radial_faceloop_find_first(iter->e_next->l, iter->vdata);
363                         iter->l_next = iter->l_first;
364                 }
365         }
366         
367         if (!iter->count) iter->l_next = NULL;
368
369         
370         if (current) {
371                 return current;
372         }
373
374         return NULL;
375 }
376
377
378 void  bmiter__loops_of_edge_begin(BMIter *iter)
379 {
380         BMLoop *l;
381
382         l = iter->edata->l;
383
384         /* note sure why this sets ldata ... */
385         init_iterator(iter);
386         
387         iter->l_first = iter->l_next = l;
388 }
389
390 void  *bmiter__loops_of_edge_step(BMIter *iter)
391 {
392         BMLoop *current = iter->l_next;
393
394         if (iter->l_next) {
395                 iter->l_next = iter->l_next->radial_next;
396         }
397
398         if (iter->l_next == iter->l_first) {
399                 iter->l_next = NULL;
400         }
401
402         if (current) {
403                 return current;
404         }
405
406         return NULL;
407 }
408
409 void  bmiter__loops_of_loop_begin(BMIter *iter)
410 {
411         BMLoop *l;
412
413         l = iter->ldata;
414
415         /* note sure why this sets ldata ... */
416         init_iterator(iter);
417
418         iter->l_first = l;
419         iter->l_next = iter->l_first->radial_next;
420         
421         if (iter->l_next == iter->l_first)
422                 iter->l_next = NULL;
423 }
424
425 void  *bmiter__loops_of_loop_step(BMIter *iter)
426 {
427         BMLoop *current = iter->l_next;
428         
429         if (iter->l_next) {
430                 iter->l_next = iter->l_next->radial_next;
431         }
432
433         if (iter->l_next == iter->l_first) {
434                 iter->l_next = NULL;
435         }
436
437         if (current) {
438                 return current;
439         }
440
441         return NULL;
442 }
443
444 /*
445  * FACE OF EDGE CALLBACKS
446  */
447
448 void  bmiter__face_of_edge_begin(BMIter *iter)
449 {
450         init_iterator(iter);
451         
452         if (iter->edata->l) {
453                 iter->l_first = iter->edata->l;
454                 iter->l_next = iter->edata->l;
455         }
456 }
457
458 void  *bmiter__face_of_edge_step(BMIter *iter)
459 {
460         BMLoop *current = iter->l_next;
461
462         if (iter->l_next) {
463                 iter->l_next = iter->l_next->radial_next;
464         }
465
466         if (iter->l_next == iter->l_first) iter->l_next = NULL;
467
468         return current ? current->f : NULL;
469 }
470
471 /*
472  * VERTS OF EDGE CALLBACKS
473  */
474
475 void  bmiter__vert_of_edge_begin(BMIter *iter)
476 {
477         init_iterator(iter);
478         iter->count = 0;
479 }
480
481 void  *bmiter__vert_of_edge_step(BMIter *iter)
482 {
483         iter->count++;
484         switch (iter->count) {
485                 case 1:
486                         return iter->edata->v1;
487                 case 2:
488                         return iter->edata->v2;
489                 default:
490                         return NULL;
491         }
492 }
493
494 /*
495  * VERT OF FACE CALLBACKS
496  */
497
498 void  bmiter__vert_of_face_begin(BMIter *iter)
499 {
500         init_iterator(iter);
501         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
502 }
503
504 void  *bmiter__vert_of_face_step(BMIter *iter)
505 {
506         BMLoop *current = iter->l_next;
507
508         if (iter->l_next) iter->l_next = iter->l_next->next;
509         if (iter->l_next == iter->l_first) iter->l_next = NULL;
510
511         return current ? current->v : NULL;
512 }
513
514 /*
515  * EDGE OF FACE CALLBACKS
516  */
517
518 void  bmiter__edge_of_face_begin(BMIter *iter)
519 {
520         init_iterator(iter);
521         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
522 }
523
524 void  *bmiter__edge_of_face_step(BMIter *iter)
525 {
526         BMLoop *current = iter->l_next;
527
528         if (iter->l_next) iter->l_next = iter->l_next->next;
529         if (iter->l_next == iter->l_first) iter->l_next = NULL;
530         
531         return current ? current->e : NULL;
532 }
533
534 /*
535  * LOOP OF FACE CALLBACKS
536  */
537
538 void  bmiter__loop_of_face_begin(BMIter *iter)
539 {
540         init_iterator(iter);
541         iter->l_first = iter->l_next = BM_FACE_FIRST_LOOP(iter->pdata);
542 }
543
544 void  *bmiter__loop_of_face_step(BMIter *iter)
545 {
546         BMLoop *current = iter->l_next;
547
548         if (iter->l_next) iter->l_next = iter->l_next->next;
549         if (iter->l_next == iter->l_first) iter->l_next = NULL;
550
551         return current;
552 }