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