← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/bmesh/intern/bmesh_structure.c

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/bmesh/intern/bmesh_structure.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) 2007 Blender Foundation.
 
19
 * All rights reserved.
 
20
 *
 
21
 * The Original Code is: all of this file.
 
22
 *
 
23
 * Contributor(s): Geoffrey Bantle.
 
24
 *
 
25
 * ***** END GPL LICENSE BLOCK *****
 
26
 */
 
27
 
 
28
/** \file blender/bmesh/intern/bmesh_structure.c
 
29
 *  \ingroup bmesh
 
30
 *
 
31
 * Low level routines for manipulating the BM structure.
 
32
 */
 
33
 
 
34
#include "BLI_utildefines.h"
 
35
 
 
36
#include "bmesh.h"
 
37
#include "intern/bmesh_private.h"
 
38
 
 
39
/**
 
40
 *      MISC utility functions.
 
41
 */
 
42
 
 
43
int bmesh_vert_in_edge(BMEdge *e, BMVert *v)
 
44
{
 
45
        if (e->v1 == v || e->v2 == v) return TRUE;
 
46
        return FALSE;
 
47
}
 
48
int bmesh_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
 
49
{
 
50
        if (e->v1 == v1 && e->v2 == v2) return TRUE;
 
51
        else if (e->v1 == v2 && e->v2 == v1) return TRUE;
 
52
        return FALSE;
 
53
}
 
54
 
 
55
BMVert *bmesh_edge_other_vert_get(BMEdge *e, BMVert *v)
 
56
{
 
57
        if (e->v1 == v) {
 
58
                return e->v2;
 
59
        }
 
60
        else if (e->v2 == v) {
 
61
                return e->v1;
 
62
        }
 
63
        return NULL;
 
64
}
 
65
 
 
66
int bmesh_edge_swapverts(BMEdge *e, BMVert *orig, BMVert *newv)
 
67
{
 
68
        if (e->v1 == orig) {
 
69
                e->v1 = newv;
 
70
                e->v1_disk_link.next = e->v1_disk_link.prev = NULL;
 
71
                return TRUE;
 
72
        }
 
73
        else if (e->v2 == orig) {
 
74
                e->v2 = newv;
 
75
                e->v2_disk_link.next = e->v2_disk_link.prev = NULL;
 
76
                return TRUE;
 
77
        }
 
78
        return FALSE;
 
79
}
 
80
 
 
81
/**
 
82
 * \section bm_cycles BMesh Cycles
 
83
 * (this is somewhat outdate, though bits of its API are still used) - joeedh
 
84
 *
 
85
 * Cycles are circular doubly linked lists that form the basis of adjacency
 
86
 * information in the BME modeler. Full adjacency relations can be derived
 
87
 * from examining these cycles very quickly. Although each cycle is a double
 
88
 * circular linked list, each one is considered to have a 'base' or 'head',
 
89
 * and care must be taken by Euler code when modifying the contents of a cycle.
 
90
 *
 
91
 * The contents of this file are split into two parts. First there are the
 
92
 * bmesh_cycle family of functions which are generic circular double linked list
 
93
 * procedures. The second part contains higher level procedures for supporting
 
94
 * modification of specific cycle types.
 
95
 *
 
96
 * The three cycles explicitly stored in the BM data structure are as follows:
 
97
 *
 
98
 *
 
99
 * 1: The Disk Cycle - A circle of edges around a vertex
 
100
 * Base: vertex->edge pointer.
 
101
 *
 
102
 * This cycle is the most complicated in terms of its structure. Each bmesh_Edge contains
 
103
 * two bmesh_CycleNode structures to keep track of that edges membership in the disk cycle
 
104
 * of each of its vertices. However for any given vertex it may be the first in some edges
 
105
 * in its disk cycle and the second for others. The bmesh_disk_XXX family of functions contain
 
106
 * some nice utilities for navigating disk cycles in a way that hides this detail from the
 
107
 * tool writer.
 
108
 *
 
109
 * Note that the disk cycle is completely independent from face data. One advantage of this
 
110
 * is that wire edges are fully integrated into the topology database. Another is that the
 
111
 * the disk cycle has no problems dealing with non-manifold conditions involving faces.
 
112
 *
 
113
 * Functions relating to this cycle:
 
114
 * - #bmesh_disk_edge_append
 
115
 * - #bmesh_disk_edge_remove
 
116
 * - #bmesh_disk_edge_next
 
117
 * - #bmesh_disk_edge_prev
 
118
 * - #bmesh_disk_facevert_count
 
119
 * - #bmesh_disk_faceedge_find_first
 
120
 * - #bmesh_disk_faceedge_find_next
 
121
 *
 
122
 *
 
123
 * 2: The Radial Cycle - A circle of face edges (bmesh_Loop) around an edge
 
124
 * Base: edge->l->radial structure.
 
125
 *
 
126
 * The radial cycle is similar to the radial cycle in the radial edge data structure.*
 
127
 * Unlike the radial edge however, the radial cycle does not require a large amount of memory
 
128
 * to store non-manifold conditions since BM does not keep track of region/shell information.
 
129
 *
 
130
 * Functions relating to this cycle:
 
131
 * - #bmesh_radial_append
 
132
 * - #bmesh_radial_loop_remove
 
133
 * - #bmesh_radial_face_find
 
134
 * - #bmesh_radial_facevert_count
 
135
 * - #bmesh_radial_faceloop_find_first
 
136
 * - #bmesh_radial_faceloop_find_next
 
137
 * - #bmesh_radial_validate
 
138
 *
 
139
 *
 
140
 * 3: The Loop Cycle - A circle of face edges around a polygon.
 
141
 * Base: polygon->lbase.
 
142
 *
 
143
 * The loop cycle keeps track of a faces vertices and edges. It should be noted that the
 
144
 * direction of a loop cycle is either CW or CCW depending on the face normal, and is
 
145
 * not oriented to the faces editedges.
 
146
 *
 
147
 * Functions relating to this cycle:
 
148
 * - bmesh_cycle_XXX family of functions.
 
149
 *
 
150
 *
 
151
 * \note the order of elements in all cycles except the loop cycle is undefined. This
 
152
 * leads to slightly increased seek time for deriving some adjacency relations, however the
 
153
 * advantage is that no intrinsic properties of the data structures are dependent upon the
 
154
 * cycle order and all non-manifold conditions are represented trivially.
 
155
 */
 
156
int bmesh_disk_edge_append(BMEdge *e, BMVert *v)
 
157
{
 
158
        if (!v->e) {
 
159
                BMDiskLink *dl1 = BM_DISK_EDGE_LINK_GET(e, v);
 
160
 
 
161
                v->e = e;
 
162
                dl1->next = dl1->prev = e;
 
163
        }
 
164
        else {
 
165
                BMDiskLink *dl1, *dl2, *dl3;
 
166
 
 
167
                dl1 = BM_DISK_EDGE_LINK_GET(e, v);
 
168
                dl2 = BM_DISK_EDGE_LINK_GET(v->e, v);
 
169
                dl3 = dl2->prev ? BM_DISK_EDGE_LINK_GET(dl2->prev, v) : NULL;
 
170
 
 
171
                dl1->next = v->e;
 
172
                dl1->prev = dl2->prev;
 
173
 
 
174
                dl2->prev = e;
 
175
                if (dl3)
 
176
                        dl3->next = e;
 
177
        }
 
178
 
 
179
        return TRUE;
 
180
}
 
181
 
 
182
void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
 
183
{
 
184
        BMDiskLink *dl1, *dl2;
 
185
 
 
186
        dl1 = BM_DISK_EDGE_LINK_GET(e, v);
 
187
        if (dl1->prev) {
 
188
                dl2 = BM_DISK_EDGE_LINK_GET(dl1->prev, v);
 
189
                dl2->next = dl1->next;
 
190
        }
 
191
 
 
192
        if (dl1->next) {
 
193
                dl2 = BM_DISK_EDGE_LINK_GET(dl1->next, v);
 
194
                dl2->prev = dl1->prev;
 
195
        }
 
196
 
 
197
        if (v->e == e)
 
198
                v->e = (e != dl1->next) ? dl1->next : NULL;
 
199
 
 
200
        dl1->next = dl1->prev = NULL;
 
201
}
 
202
 
 
203
/**
 
204
 * \brief Next Disk Edge
 
205
 *
 
206
 *      Find the next edge in a disk cycle
 
207
 *
 
208
 *      \return Pointer to the next edge in the disk cycle for the vertex v.
 
209
 */
 
210
BMEdge *bmesh_disk_edge_next(BMEdge *e, BMVert *v)
 
211
{
 
212
        if (v == e->v1)
 
213
                return e->v1_disk_link.next;
 
214
        if (v == e->v2)
 
215
                return e->v2_disk_link.next;
 
216
        return NULL;
 
217
}
 
218
 
 
219
BMEdge *bmesh_disk_edge_prev(BMEdge *e, BMVert *v)
 
220
{
 
221
        if (v == e->v1)
 
222
                return e->v1_disk_link.prev;
 
223
        if (v == e->v2)
 
224
                return e->v2_disk_link.prev;
 
225
        return NULL;
 
226
}
 
227
 
 
228
BMEdge *bmesh_disk_edge_exists(BMVert *v1, BMVert *v2)
 
229
{
 
230
        BMEdge *e_iter, *e_first;
 
231
        
 
232
        if (v1->e) {
 
233
                e_first = e_iter = v1->e;
 
234
 
 
235
                do {
 
236
                        if (bmesh_verts_in_edge(v1, v2, e_iter)) {
 
237
                                return e_iter;
 
238
                        }
 
239
                } while ((e_iter = bmesh_disk_edge_next(e_iter, v1)) != e_first);
 
240
        }
 
241
        
 
242
        return NULL;
 
243
}
 
244
 
 
245
int bmesh_disk_count(BMVert *v)
 
246
{
 
247
        if (v->e) {
 
248
                BMEdge *e_first, *e_iter;
 
249
                int count = 0;
 
250
 
 
251
                e_iter = e_first = v->e;
 
252
 
 
253
                do {
 
254
                        if (!e_iter) {
 
255
                                return 0;
 
256
                        }
 
257
 
 
258
                        if (count >= (1 << 20)) {
 
259
                                printf("bmesh error: infinite loop in disk cycle!\n");
 
260
                                return 0;
 
261
                        }
 
262
                        count++;
 
263
                } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
 
264
                return count;
 
265
        }
 
266
        else {
 
267
                return 0;
 
268
        }
 
269
}
 
270
 
 
271
int bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
 
272
{
 
273
        BMEdge *e_iter;
 
274
 
 
275
        if (!BM_vert_in_edge(e, v))
 
276
                return FALSE;
 
277
        if (bmesh_disk_count(v) != len || len == 0)
 
278
                return FALSE;
 
279
 
 
280
        e_iter = e;
 
281
        do {
 
282
                if (len != 1 && bmesh_disk_edge_prev(e_iter, v) == e_iter) {
 
283
                        return FALSE;
 
284
                }
 
285
        } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
 
286
 
 
287
        return TRUE;
 
288
}
 
289
 
 
290
/**
 
291
 * \brief DISK COUNT FACE VERT
 
292
 *
 
293
 * Counts the number of loop users
 
294
 * for this vertex. Note that this is
 
295
 * equivalent to counting the number of
 
296
 * faces incident upon this vertex
 
297
 */
 
298
int bmesh_disk_facevert_count(BMVert *v)
 
299
{
 
300
        /* is there an edge on this vert at all */
 
301
        if (v->e) {
 
302
                BMEdge *e_first, *e_iter;
 
303
                int count = 0;
 
304
 
 
305
                /* first, loop around edge */
 
306
                e_first = e_iter = v->e;
 
307
                do {
 
308
                        if (e_iter->l) {
 
309
                                count += bmesh_radial_facevert_count(e_iter->l, v);
 
310
                        }
 
311
                } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
 
312
                return count;
 
313
        }
 
314
        else {
 
315
                return 0;
 
316
        }
 
317
}
 
318
 
 
319
/**
 
320
 * \brief FIND FIRST FACE EDGE
 
321
 *
 
322
 * Finds the first edge in a vertices
 
323
 * Disk cycle that has one of this
 
324
 * vert's loops attached
 
325
 * to it.
 
326
 */
 
327
BMEdge *bmesh_disk_faceedge_find_first(BMEdge *e, BMVert *v)
 
328
{
 
329
        BMEdge *searchedge = NULL;
 
330
        searchedge = e;
 
331
        do {
 
332
                if (searchedge->l && bmesh_radial_facevert_count(searchedge->l, v)) {
 
333
                        return searchedge;
 
334
                }
 
335
        } while ((searchedge = bmesh_disk_edge_next(searchedge, v)) != e);
 
336
 
 
337
        return NULL;
 
338
}
 
339
 
 
340
BMEdge *bmesh_disk_faceedge_find_next(BMEdge *e, BMVert *v)
 
341
{
 
342
        BMEdge *searchedge = NULL;
 
343
        searchedge = bmesh_disk_edge_next(e, v);
 
344
        do {
 
345
                if (searchedge->l && bmesh_radial_facevert_count(searchedge->l, v)) {
 
346
                        return searchedge;
 
347
                }
 
348
        } while ((searchedge = bmesh_disk_edge_next(searchedge, v)) != e);
 
349
        return e;
 
350
}
 
351
 
 
352
/*****radial cycle functions, e.g. loops surrounding edges**** */
 
353
int bmesh_radial_validate(int radlen, BMLoop *l)
 
354
{
 
355
        BMLoop *l_iter = l;
 
356
        int i = 0;
 
357
        
 
358
        if (bmesh_radial_length(l) != radlen)
 
359
                return FALSE;
 
360
 
 
361
        do {
 
362
                if (UNLIKELY(!l_iter)) {
 
363
                        BMESH_ASSERT(0);
 
364
                        return FALSE;
 
365
                }
 
366
                
 
367
                if (l_iter->e != l->e)
 
368
                        return FALSE;
 
369
                if (l_iter->v != l->e->v1 && l_iter->v != l->e->v2)
 
370
                        return FALSE;
 
371
                
 
372
                if (UNLIKELY(i > BM_LOOP_RADIAL_MAX)) {
 
373
                        BMESH_ASSERT(0);
 
374
                        return FALSE;
 
375
                }
 
376
                
 
377
                i++;
 
378
        } while ((l_iter = l_iter->radial_next) != l);
 
379
 
 
380
        return TRUE;
 
381
}
 
382
 
 
383
/**
 
384
 * \brief BMESH RADIAL REMOVE LOOP
 
385
 *
 
386
 * Removes a loop from an radial cycle. If edge e is non-NULL
 
387
 * it should contain the radial cycle, and it will also get
 
388
 * updated (in the case that the edge's link into the radial
 
389
 * cycle was the loop which is being removed from the cycle).
 
390
 */
 
391
void bmesh_radial_loop_remove(BMLoop *l, BMEdge *e)
 
392
{
 
393
        /* if e is non-NULL, l must be in the radial cycle of e */
 
394
        if (UNLIKELY(e && e != l->e)) {
 
395
                BMESH_ASSERT(0);
 
396
        }
 
397
 
 
398
        if (l->radial_next != l) {
 
399
                if (e && l == e->l)
 
400
                        e->l = l->radial_next;
 
401
 
 
402
                l->radial_next->radial_prev = l->radial_prev;
 
403
                l->radial_prev->radial_next = l->radial_next;
 
404
        }
 
405
        else {
 
406
                if (e) {
 
407
                        if (l == e->l) {
 
408
                                e->l = NULL;
 
409
                        }
 
410
                        else {
 
411
                                BMESH_ASSERT(0);
 
412
                        }
 
413
                }
 
414
        }
 
415
 
 
416
        /* l is no longer in a radial cycle; empty the links
 
417
         * to the cycle and the link back to an edge */
 
418
        l->radial_next = l->radial_prev = NULL;
 
419
        l->e = NULL;
 
420
}
 
421
 
 
422
 
 
423
/**
 
424
 * \brief BME RADIAL FIND FIRST FACE VERT
 
425
 *
 
426
 * Finds the first loop of v around radial
 
427
 * cycle
 
428
 */
 
429
BMLoop *bmesh_radial_faceloop_find_first(BMLoop *l, BMVert *v)
 
430
{
 
431
        BMLoop *l_iter;
 
432
        l_iter = l;
 
433
        do {
 
434
                if (l_iter->v == v) {
 
435
                        return l_iter;
 
436
                }
 
437
        } while ((l_iter = l_iter->radial_next) != l);
 
438
        return NULL;
 
439
}
 
440
 
 
441
BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v)
 
442
{
 
443
        BMLoop *l_iter;
 
444
        l_iter = l->radial_next;
 
445
        do {
 
446
                if (l_iter->v == v) {
 
447
                        return l_iter;
 
448
                }
 
449
        } while ((l_iter = l_iter->radial_next) != l);
 
450
        return l;
 
451
}
 
452
 
 
453
int bmesh_radial_length(BMLoop *l)
 
454
{
 
455
        BMLoop *l_iter = l;
 
456
        int i = 0;
 
457
 
 
458
        if (!l)
 
459
                return 0;
 
460
 
 
461
        do {
 
462
                if (UNLIKELY(!l_iter)) {
 
463
                        /* radial cycle is broken (not a circulat loop) */
 
464
                        BMESH_ASSERT(0);
 
465
                        return 0;
 
466
                }
 
467
                
 
468
                i++;
 
469
                if (UNLIKELY(i >= BM_LOOP_RADIAL_MAX)) {
 
470
                        BMESH_ASSERT(0);
 
471
                        return -1;
 
472
                }
 
473
        } while ((l_iter = l_iter->radial_next) != l);
 
474
 
 
475
        return i;
 
476
}
 
477
 
 
478
void bmesh_radial_append(BMEdge *e, BMLoop *l)
 
479
{
 
480
        if (e->l == NULL) {
 
481
                e->l = l;
 
482
                l->radial_next = l->radial_prev = l;
 
483
        }
 
484
        else {
 
485
                l->radial_prev = e->l;
 
486
                l->radial_next = e->l->radial_next;
 
487
 
 
488
                e->l->radial_next->radial_prev = l;
 
489
                e->l->radial_next = l;
 
490
 
 
491
                e->l = l;
 
492
        }
 
493
 
 
494
        if (UNLIKELY(l->e && l->e != e)) {
 
495
                /* l is already in a radial cycle for a different edge */
 
496
                BMESH_ASSERT(0);
 
497
        }
 
498
        
 
499
        l->e = e;
 
500
}
 
501
 
 
502
int bmesh_radial_face_find(BMEdge *e, BMFace *f)
 
503
{
 
504
        BMLoop *l_iter;
 
505
        int i, len;
 
506
 
 
507
        len = bmesh_radial_length(e->l);
 
508
        for (i = 0, l_iter = e->l; i < len; i++, l_iter = l_iter->radial_next) {
 
509
                if (l_iter->f == f)
 
510
                        return TRUE;
 
511
        }
 
512
        return FALSE;
 
513
}
 
514
 
 
515
/**
 
516
 * \brief RADIAL COUNT FACE VERT
 
517
 *
 
518
 * Returns the number of times a vertex appears
 
519
 * in a radial cycle
 
520
 */
 
521
int bmesh_radial_facevert_count(BMLoop *l, BMVert *v)
 
522
{
 
523
        BMLoop *l_iter;
 
524
        int count = 0;
 
525
        l_iter = l;
 
526
        do {
 
527
                if (l_iter->v == v) {
 
528
                        count++;
 
529
                }
 
530
        } while ((l_iter = l_iter->radial_next) != l);
 
531
 
 
532
        return count;
 
533
}
 
534
 
 
535
/*****loop cycle functions, e.g. loops surrounding a face**** */
 
536
int bmesh_loop_validate(BMFace *f)
 
537
{
 
538
        int i;
 
539
        int len = f->len;
 
540
        BMLoop *l_iter, *l_first;
 
541
 
 
542
        l_first = BM_FACE_FIRST_LOOP(f);
 
543
 
 
544
        if (l_first == NULL) {
 
545
                return FALSE;
 
546
        }
 
547
 
 
548
        /* Validate that the face loop cycle is the length specified by f->len */
 
549
        for (i = 1, l_iter = l_first->next; i < len; i++, l_iter = l_iter->next) {
 
550
                if ((l_iter->f != f) ||
 
551
                    (l_iter == l_first))
 
552
                {
 
553
                        return FALSE;
 
554
                }
 
555
        }
 
556
        if (l_iter != l_first) {
 
557
                return FALSE;
 
558
        }
 
559
 
 
560
        /* Validate the loop->prev links also form a cycle of length f->len */
 
561
        for (i = 1, l_iter = l_first->prev; i < len; i++, l_iter = l_iter->prev) {
 
562
                if (l_iter == l_first) {
 
563
                        return FALSE;
 
564
                }
 
565
        }
 
566
        if (l_iter != l_first) {
 
567
                return FALSE;
 
568
        }
 
569
 
 
570
        return TRUE;
 
571
}