f18a0835e5e6dd6113ef628a6ff7ae913dd8e195
[blender.git] / source / blender / bmesh / intern / bmesh_walkers.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, Levi Schooley.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_walkers.c
24  *  \ingroup bmesh
25  *
26  * BMesh Walker API.
27  */
28
29 #include <stdlib.h>
30 #include <string.h> /* for memcpy */
31
32 #include "BLI_listbase.h"
33
34 #include "bmesh.h"
35
36 #include "bmesh_walkers_private.h"
37
38 /**
39  * - joeedh -
40  * design notes:
41  *
42  * original desing: walkers directly emulation recursive functions.
43  * functions save their state onto a worklist, and also add new states
44  * to implement recursive or looping behavior.  generally only one
45  * state push per call with a specific state is desired.
46  *
47  * basic design pattern: the walker step function goes through it's
48  * list of possible choices for recursion, and recurses (by pushing a new state)
49  * using the first non-visited one.  this choise is the flagged as visited using
50  * the ghash.  each step may push multiple new states onto the worklist at once.
51  *
52  * - Walkers use tool flags, not header flags.
53  * - Walkers now use ghash for storing visited elements,
54  *   rather then stealing flags.  ghash can be rewritten
55  *   to be faster if necessary, in the far future :) .
56  * - tools should ALWAYS have necessary error handling
57  *   for if walkers fail.
58  */
59
60 void *BMW_begin(BMWalker *walker, void *start)
61 {
62         walker->begin(walker, start);
63         
64         return BMW_current_state(walker) ? walker->step(walker) : NULL;
65 }
66
67 /**
68  * \brief Init Walker
69  *
70  * Allocates and returns a new mesh walker of
71  * a given type. The elements visited are filtered
72  * by the bitmask 'searchmask'.
73  */
74 void BMW_init(BMWalker *walker, BMesh *bm, int type,
75               short mask_vert, short mask_edge, short mask_loop, short mask_face,
76               int layer)
77 {
78         memset(walker, 0, sizeof(BMWalker));
79
80         walker->layer = layer;
81         walker->bm = bm;
82
83         walker->mask_vert = mask_vert;
84         walker->mask_edge = mask_edge;
85         walker->mask_loop = mask_loop;
86         walker->mask_face = mask_face;
87
88         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh walkers 1");
89         
90         if (UNLIKELY(type >= BMW_MAXWALKERS || type < 0)) {
91                 fprintf(stderr,
92                         "Invalid walker type in BMW_init; type: %d, "
93                         "searchmask: (v:%d, e:%d, l:%d, f:%d), flag: %d\n",
94                         type, mask_vert, mask_edge, mask_loop, mask_face, layer);
95                 BMESH_ASSERT(0);
96         }
97         
98         if (type != BMW_CUSTOM) {
99                 walker->begin = bm_walker_types[type]->begin;
100                 walker->yield = bm_walker_types[type]->yield;
101                 walker->step = bm_walker_types[type]->step;
102                 walker->structsize = bm_walker_types[type]->structsize;
103                 walker->order = bm_walker_types[type]->order;
104                 walker->valid_mask = bm_walker_types[type]->valid_mask;
105
106                 /* safety checks */
107                 /* if this raises an error either the caller is wrong or
108                  * 'bm_walker_types' needs updating */
109                 BLI_assert(mask_vert == 0 || (walker->valid_mask & BM_VERT));
110                 BLI_assert(mask_edge == 0 || (walker->valid_mask & BM_EDGE));
111                 BLI_assert(mask_loop == 0 || (walker->valid_mask & BM_LOOP));
112                 BLI_assert(mask_face == 0 || (walker->valid_mask & BM_FACE));
113         }
114         
115         walker->worklist = BLI_mempool_create(walker->structsize, 100, 100, TRUE, FALSE);
116         walker->states.first = walker->states.last = NULL;
117 }
118
119 /**
120  * \brief End Walker
121  *
122  * Frees a walker's worklist.
123  */
124 void BMW_end(BMWalker *walker)
125 {
126         BLI_mempool_destroy(walker->worklist);
127         BLI_ghash_free(walker->visithash, NULL, NULL);
128 }
129
130
131 /**
132  * \brief Step Walker
133  */
134 void *BMW_step(BMWalker *walker)
135 {
136         BMHeader *head;
137
138         head = BMW_walk(walker);
139
140         return head;
141 }
142
143 /**
144  * \brief Walker Current Depth
145  *
146  * Returns the current depth of the walker.
147  */
148
149 int BMW_current_depth(BMWalker *walker)
150 {
151         return walker->depth;
152 }
153
154 /**
155  * \brief Main Walking Function
156  *
157  * Steps a mesh walker forward by one element
158  */
159 void *BMW_walk(BMWalker *walker)
160 {
161         void *current = NULL;
162
163         while (BMW_current_state(walker)) {
164                 current = walker->step(walker);
165                 if (current) {
166                         return current;
167                 }
168         }
169         return NULL;
170 }
171
172 /**
173  * \brief Current Walker State
174  *
175  * Returns the first state from the walker state
176  * worklist. This state is the the next in the
177  * worklist for processing.
178  */
179 void *BMW_current_state(BMWalker *walker)
180 {
181         bmesh_walkerGeneric *currentstate = walker->states.first;
182         if (currentstate) {
183                 /* Automatic update of depth. For most walkers that
184                  * follow the standard "Step" pattern of:
185                  *  - read current state
186                  *  - remove current state
187                  *  - push new states
188                  *  - return walk result from just-removed current state
189                  * this simple automatic update should keep track of depth
190                  * just fine. Walkers that deviate from that pattern may
191                  * need to manually update the depth if they care about
192                  * keeping it correct. */
193                 walker->depth = currentstate->depth + 1;
194         }
195         return currentstate;
196 }
197
198 /**
199  * \brief Remove Current Walker State
200  *
201  * Remove and free an item from the end of the walker state
202  * worklist.
203  */
204 void BMW_state_remove(BMWalker *walker)
205 {
206         void *oldstate;
207         oldstate = BMW_current_state(walker);
208         BLI_remlink(&walker->states, oldstate);
209         BLI_mempool_free(walker->worklist, oldstate);
210 }
211
212 /**
213  * \brief Add a new Walker State
214  *
215  * Allocate a new empty state and put it on the worklist.
216  * A pointer to the new state is returned so that the caller
217  * can fill in the state data. The new state will be inserted
218  * at the front for depth-first walks, and at the end for
219  * breadth-first walks.
220  */
221 void *BMW_state_add(BMWalker *walker)
222 {
223         bmesh_walkerGeneric *newstate;
224         newstate = BLI_mempool_alloc(walker->worklist);
225         newstate->depth = walker->depth;
226         switch (walker->order)
227         {
228                 case BMW_DEPTH_FIRST:
229                         BLI_addhead(&walker->states, newstate);
230                         break;
231                 case BMW_BREADTH_FIRST:
232                         BLI_addtail(&walker->states, newstate);
233                         break;
234                 default:
235                         BLI_assert(0);
236                         break;
237         }
238         return newstate;
239 }
240
241 /**
242  * \brief Reset Walker
243  *
244  * Frees all states from the worklist, resetting the walker
245  * for reuse in a new walk.
246  */
247 void BMW_reset(BMWalker *walker)
248 {
249         while (BMW_current_state(walker)) {
250                 BMW_state_remove(walker);
251         }
252         walker->depth = 0;
253         BLI_ghash_free(walker->visithash, NULL, NULL);
254         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh walkers 1");
255 }