← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty-proposed

« back to all changes in this revision

Viewing changes to source/blender/bmesh/tools/bmesh_path.c

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2013-08-14 10:43:49 UTC
  • mfrom: (14.2.19 sid)
  • Revision ID: package-import@ubuntu.com-20130814104349-t1d5mtwkphp12dyj
Tags: 2.68a-3
* Upload to unstable
* debian/: python3.3 Depends simplified
  - debian/control: python3.3 Depends dropped
    for blender-data package
  - 0001-blender_thumbnailer.patch refreshed
* debian/control: libavcodec b-dep versioning dropped

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/bmesh/tools/bmesh_path.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
 * The Original Code is Copyright (C) 2004 Blender Foundation.
 
19
 * All rights reserved.
 
20
 *
 
21
 * The Original Code is: all of this file.
 
22
 *
 
23
 * Contributor(s): none yet.
 
24
 *
 
25
 * ***** END GPL LICENSE BLOCK *****
 
26
 */
 
27
 
 
28
/** \file blender/bmesh/tools/bmesh_path.c
 
29
 *  \ingroup bmesh
 
30
 *
 
31
 * Find a path between 2 elements.
 
32
 *
 
33
 */
 
34
 
 
35
#include "MEM_guardedalloc.h"
 
36
 
 
37
#include "BLI_math.h"
 
38
#include "BLI_linklist.h"
 
39
#include "BLI_heap.h"
 
40
 
 
41
#include "bmesh.h"
 
42
#include "bmesh_path.h"  /* own include */
 
43
 
 
44
/* -------------------------------------------------------------------- */
 
45
/* Generic Helpers */
 
46
 
 
47
static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
 
48
{
 
49
        float cost, d1[3], d2[3];
 
50
 
 
51
 
 
52
        /* The cost is based on the simple sum of the length of the two edgees... */
 
53
        sub_v3_v3v3(d1, v2, v1);
 
54
        sub_v3_v3v3(d2, v3, v2);
 
55
        cost = normalize_v3(d1) + normalize_v3(d2);
 
56
 
 
57
        /* but is biased to give higher values to sharp turns, so that it will take
 
58
         * paths with fewer "turns" when selecting between equal-weighted paths between
 
59
         * the two edges */
 
60
        cost = cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2)))));
 
61
 
 
62
        return cost;
 
63
}
 
64
 
 
65
 
 
66
 
 
67
/* -------------------------------------------------------------------- */
 
68
/* BM_mesh_calc_path_vert */
 
69
 
 
70
static void verttag_add_adjacent(Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const bool use_length)
 
71
{
 
72
        BMIter eiter;
 
73
        BMEdge *e;
 
74
        BMVert *v_b;
 
75
 
 
76
        const int v_a_index = BM_elem_index_get(v_a);
 
77
 
 
78
        /* loop over faces of face, but do so by first looping over loops */
 
79
        BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
 
80
                v_b = BM_edge_other_vert(e, v_a);
 
81
                if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
 
82
                        /* we know 'f_b' is not visited, check it out! */
 
83
                        const int v_b_index = BM_elem_index_get(v_b);
 
84
                        const float cost_cut = use_length ? len_v3v3(v_a->co, v_b->co) : 1.0f;
 
85
                        const float cost_new = cost[v_a_index] + cost_cut;
 
86
 
 
87
                        if (cost[v_b_index] > cost_new) {
 
88
                                cost[v_b_index] = cost_new;
 
89
                                verts_prev[v_b_index] = v_a;
 
90
                                BLI_heap_insert(heap, cost_new, v_b);
 
91
                        }
 
92
                }
 
93
        }
 
94
}
 
95
 
 
96
LinkNode *BM_mesh_calc_path_vert(
 
97
        BMesh *bm, BMVert *v_src, BMVert *v_dst, const bool use_length,
 
98
        void *user_data, bool (*test_fn)(BMVert *, void *user_data))
 
99
{
 
100
        LinkNode *path = NULL;
 
101
        /* BM_ELEM_TAG flag is used to store visited edges */
 
102
        BMVert *v;
 
103
        BMIter viter;
 
104
        Heap *heap;
 
105
        float *cost;
 
106
        BMVert **verts_prev;
 
107
        int i, totvert;
 
108
 
 
109
        /* note, would pass BM_EDGE except we are looping over all faces anyway */
 
110
        // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
111
 
 
112
        BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
 
113
                if (test_fn(v, user_data)) {
 
114
                        BM_elem_flag_disable(v, BM_ELEM_TAG);
 
115
                }
 
116
                else {
 
117
                        BM_elem_flag_enable(v, BM_ELEM_TAG);
 
118
                }
 
119
 
 
120
                BM_elem_index_set(v, i); /* set_inline */
 
121
        }
 
122
        bm->elem_index_dirty &= ~BM_VERT;
 
123
 
 
124
        /* alloc */
 
125
        totvert = bm->totvert;
 
126
        verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__);
 
127
        cost = MEM_mallocN(sizeof(*cost) * totvert, __func__);
 
128
 
 
129
        fill_vn_fl(cost, totvert, 1e20f);
 
130
 
 
131
        /*
 
132
         * Arrays are now filled as follows:
 
133
         *
 
134
         * As the search continues, verts_prev[n] will be the previous verts on the shortest
 
135
         * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited,
 
136
         * cost[n] will contain the length of the shortest
 
137
         * path to face n found so far, Finally, heap is a priority heap which is built on the
 
138
         * the same data as the cost array, but inverted: it is a worklist of faces prioritized
 
139
         * by the shortest path found so far to the face.
 
140
         */
 
141
 
 
142
        /* regular dijkstra shortest path, but over faces instead of vertices */
 
143
        heap = BLI_heap_new();
 
144
        BLI_heap_insert(heap, 0.0f, v_src);
 
145
        cost[BM_elem_index_get(v_src)] = 0.0f;
 
146
 
 
147
        while (!BLI_heap_is_empty(heap)) {
 
148
                v = BLI_heap_popmin(heap);
 
149
 
 
150
                if (v == v_dst)
 
151
                        break;
 
152
 
 
153
                if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
 
154
                        BM_elem_flag_enable(v, BM_ELEM_TAG);
 
155
                        verttag_add_adjacent(heap, v, verts_prev, cost, use_length);
 
156
                }
 
157
        }
 
158
 
 
159
        if (v == v_dst) {
 
160
                do {
 
161
                        BLI_linklist_prepend(&path, v);
 
162
                } while ((v = verts_prev[BM_elem_index_get(v)]));
 
163
        }
 
164
 
 
165
        MEM_freeN(verts_prev);
 
166
        MEM_freeN(cost);
 
167
        BLI_heap_free(heap, NULL);
 
168
 
 
169
        return path;
 
170
}
 
171
 
 
172
 
 
173
 
 
174
/* -------------------------------------------------------------------- */
 
175
/* BM_mesh_calc_path_edge */
 
176
 
 
177
 
 
178
static float edgetag_cut_cost(BMEdge *e1, BMEdge *e2, BMVert *v)
 
179
{
 
180
        BMVert *v1 = BM_edge_other_vert(e1, v);
 
181
        BMVert *v2 = BM_edge_other_vert(e2, v);
 
182
        return step_cost_3_v3(v1->co, v->co, v2->co);
 
183
}
 
184
 
 
185
static void edgetag_add_adjacent(Heap *heap, BMEdge *e1, BMEdge **edges_prev, float *cost, const bool use_length)
 
186
{
 
187
        BMIter viter;
 
188
        BMVert *v;
 
189
 
 
190
        BMIter eiter;
 
191
        BMEdge *e2;
 
192
 
 
193
        const int e1_index = BM_elem_index_get(e1);
 
194
 
 
195
        BM_ITER_ELEM (v, &viter, e1, BM_VERTS_OF_EDGE) {
 
196
                BM_ITER_ELEM (e2, &eiter, v, BM_EDGES_OF_VERT) {
 
197
                        if (!BM_elem_flag_test(e2, BM_ELEM_TAG)) {
 
198
                                /* we know 'e2' is not visited, check it out! */
 
199
                                const int e2_index = BM_elem_index_get(e2);
 
200
                                const float cost_cut = use_length ? edgetag_cut_cost(e1, e2, v) : 1.0f;
 
201
                                const float cost_new = cost[e1_index] + cost_cut;
 
202
 
 
203
                                if (cost[e2_index] > cost_new) {
 
204
                                        cost[e2_index] = cost_new;
 
205
                                        edges_prev[e2_index] = e1;
 
206
                                        BLI_heap_insert(heap, cost_new, e2);
 
207
                                }
 
208
                        }
 
209
                }
 
210
        }
 
211
}
 
212
 
 
213
 
 
214
LinkNode *BM_mesh_calc_path_edge(
 
215
        BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const bool use_length,
 
216
        void *user_data, bool (*filter_fn)(BMEdge *, void *user_data))
 
217
{
 
218
        LinkNode *path = NULL;
 
219
        /* BM_ELEM_TAG flag is used to store visited edges */
 
220
        BMEdge *e;
 
221
        BMIter eiter;
 
222
        Heap *heap;
 
223
        float *cost;
 
224
        BMEdge **edges_prev;
 
225
        int i, totedge;
 
226
 
 
227
        /* note, would pass BM_EDGE except we are looping over all edges anyway */
 
228
        BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */);
 
229
 
 
230
        BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
 
231
                if (filter_fn(e, user_data)) {
 
232
                        BM_elem_flag_disable(e, BM_ELEM_TAG);
 
233
                }
 
234
                else {
 
235
                        BM_elem_flag_enable(e, BM_ELEM_TAG);
 
236
                }
 
237
 
 
238
                BM_elem_index_set(e, i); /* set_inline */
 
239
        }
 
240
        bm->elem_index_dirty &= ~BM_EDGE;
 
241
 
 
242
        /* alloc */
 
243
        totedge = bm->totedge;
 
244
        edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious");
 
245
        cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost");
 
246
 
 
247
        fill_vn_fl(cost, totedge, 1e20f);
 
248
 
 
249
        /*
 
250
         * Arrays are now filled as follows:
 
251
         *
 
252
         * As the search continues, prevedge[n] will be the previous edge on the shortest
 
253
         * path found so far to edge n. BM_ELEM_TAG is used to tag elements we have visited,
 
254
         * cost[n] will contain the length of the shortest
 
255
         * path to edge n found so far, Finally, heap is a priority heap which is built on the
 
256
         * the same data as the cost array, but inverted: it is a worklist of edges prioritized
 
257
         * by the shortest path found so far to the edge.
 
258
         */
 
259
 
 
260
        /* regular dijkstra shortest path, but over edges instead of vertices */
 
261
        heap = BLI_heap_new();
 
262
        BLI_heap_insert(heap, 0.0f, e_src);
 
263
        cost[BM_elem_index_get(e_src)] = 0.0f;
 
264
 
 
265
        while (!BLI_heap_is_empty(heap)) {
 
266
                e = BLI_heap_popmin(heap);
 
267
 
 
268
                if (e == e_dst)
 
269
                        break;
 
270
 
 
271
                if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
 
272
                        BM_elem_flag_enable(e, BM_ELEM_TAG);
 
273
                        edgetag_add_adjacent(heap, e, edges_prev, cost, use_length);
 
274
                }
 
275
        }
 
276
 
 
277
        if (e == e_dst) {
 
278
                do {
 
279
                        BLI_linklist_prepend(&path, e);
 
280
                } while ((e = edges_prev[BM_elem_index_get(e)]));
 
281
        }
 
282
 
 
283
        MEM_freeN(edges_prev);
 
284
        MEM_freeN(cost);
 
285
        BLI_heap_free(heap, NULL);
 
286
 
 
287
        return path;
 
288
}
 
289
 
 
290
 
 
291
 
 
292
/* -------------------------------------------------------------------- */
 
293
/* BM_mesh_calc_path_face */
 
294
 
 
295
static float facetag_cut_cost(BMFace *f_a, BMFace *f_b, BMEdge *e)
 
296
{
 
297
        float f_a_cent[3];
 
298
        float f_b_cent[3];
 
299
        float e_cent[3];
 
300
 
 
301
        BM_face_calc_center_mean(f_a, f_a_cent);
 
302
        BM_face_calc_center_mean(f_b, f_b_cent);
 
303
        mid_v3_v3v3(e_cent, e->v1->co, e->v2->co);
 
304
 
 
305
        return step_cost_3_v3(f_a_cent, e_cent, f_b_cent);
 
306
}
 
307
 
 
308
static void facetag_add_adjacent(Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const bool use_length)
 
309
{
 
310
        BMIter liter;
 
311
        BMLoop *l_a;
 
312
        BMFace *f_b;
 
313
 
 
314
        const int f_a_index = BM_elem_index_get(f_a);
 
315
 
 
316
        /* loop over faces of face, but do so by first looping over loops */
 
317
        BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
 
318
                BMLoop *l_first;
 
319
                BMLoop *l_iter;
 
320
 
 
321
                l_iter = l_first = l_a;
 
322
                do {
 
323
                        f_b = l_iter->f;
 
324
                        if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
 
325
                                /* we know 'f_b' is not visited, check it out! */
 
326
                                const int f_b_index = BM_elem_index_get(f_b);
 
327
                                const float cost_cut = use_length ? facetag_cut_cost(f_a, f_b, l_iter->e) : 1.0f;
 
328
                                const float cost_new = cost[f_a_index] + cost_cut;
 
329
 
 
330
                                if (cost[f_b_index] > cost_new) {
 
331
                                        cost[f_b_index] = cost_new;
 
332
                                        faces_prev[f_b_index] = f_a;
 
333
                                        BLI_heap_insert(heap, cost_new, f_b);
 
334
                                }
 
335
                        }
 
336
                } while ((l_iter = l_iter->radial_next) != l_first);
 
337
        }
 
338
}
 
339
 
 
340
LinkNode *BM_mesh_calc_path_face(
 
341
        BMesh *bm, BMFace *f_src, BMFace *f_dst, const bool use_length,
 
342
        void *user_data, bool (*test_fn)(BMFace *, void *user_data))
 
343
{
 
344
        LinkNode *path = NULL;
 
345
        /* BM_ELEM_TAG flag is used to store visited edges */
 
346
        BMFace *f;
 
347
        BMIter fiter;
 
348
        Heap *heap;
 
349
        float *cost;
 
350
        BMFace **faces_prev;
 
351
        int i, totface;
 
352
 
 
353
        /* note, would pass BM_EDGE except we are looping over all faces anyway */
 
354
        // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
355
 
 
356
        BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
 
357
                if (test_fn(f, user_data)) {
 
358
                        BM_elem_flag_disable(f, BM_ELEM_TAG);
 
359
                }
 
360
                else {
 
361
                        BM_elem_flag_enable(f, BM_ELEM_TAG);
 
362
                }
 
363
 
 
364
                BM_elem_index_set(f, i); /* set_inline */
 
365
        }
 
366
        bm->elem_index_dirty &= ~BM_FACE;
 
367
 
 
368
        /* alloc */
 
369
        totface = bm->totface;
 
370
        faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__);
 
371
        cost = MEM_mallocN(sizeof(*cost) * totface, __func__);
 
372
 
 
373
        fill_vn_fl(cost, totface, 1e20f);
 
374
 
 
375
        /*
 
376
         * Arrays are now filled as follows:
 
377
         *
 
378
         * As the search continues, faces_prev[n] will be the previous face on the shortest
 
379
         * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited,
 
380
         * cost[n] will contain the length of the shortest
 
381
         * path to face n found so far, Finally, heap is a priority heap which is built on the
 
382
         * the same data as the cost array, but inverted: it is a worklist of faces prioritized
 
383
         * by the shortest path found so far to the face.
 
384
         */
 
385
 
 
386
        /* regular dijkstra shortest path, but over faces instead of vertices */
 
387
        heap = BLI_heap_new();
 
388
        BLI_heap_insert(heap, 0.0f, f_src);
 
389
        cost[BM_elem_index_get(f_src)] = 0.0f;
 
390
 
 
391
        while (!BLI_heap_is_empty(heap)) {
 
392
                f = BLI_heap_popmin(heap);
 
393
 
 
394
                if (f == f_dst)
 
395
                        break;
 
396
 
 
397
                if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
 
398
                        BM_elem_flag_enable(f, BM_ELEM_TAG);
 
399
                        facetag_add_adjacent(heap, f, faces_prev, cost, use_length);
 
400
                }
 
401
        }
 
402
 
 
403
        if (f == f_dst) {
 
404
                do {
 
405
                        BLI_linklist_prepend(&path, f);
 
406
                } while ((f = faces_prev[BM_elem_index_get(f)]));
 
407
        }
 
408
 
 
409
        MEM_freeN(faces_prev);
 
410
        MEM_freeN(cost);
 
411
        BLI_heap_free(heap, NULL);
 
412
 
 
413
        return path;
 
414
}