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