Merge branch 'blender2.7'
[blender.git] / source / blender / bmesh / intern / bmesh_mesh_validate.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2012 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file \ingroup bmesh
21  *
22  * BM mesh validation function.
23  */
24
25 /* debug builds only */
26 #ifdef DEBUG
27
28 #include "BLI_utildefines.h"
29 #include "BLI_edgehash.h"
30
31 #include "bmesh.h"
32
33 #include "bmesh_mesh_validate.h"
34
35
36 /* macro which inserts the function name */
37 #if defined __GNUC__
38 #  define ERRMSG(format, args...) { fprintf(stderr, "%s: " format ", " AT "\n", __func__, ##args); errtot++; } (void)0
39 #else
40 #  define ERRMSG(format, ...) { fprintf(stderr, "%s: " format ", " AT "\n", __func__, __VA_ARGS__); errtot++; } (void)0
41 #endif
42
43 /**
44  * Check of this BMesh is valid, this function can be slow since its intended to help with debugging.
45  *
46  * \return true when the mesh is valid.
47  */
48 bool BM_mesh_validate(BMesh *bm)
49 {
50         EdgeHash *edge_hash = BLI_edgehash_new_ex(__func__, bm->totedge);
51         int errtot;
52
53         BMIter iter;
54         BMVert *v;
55         BMEdge *e;
56         BMFace *f;
57
58         int i, j;
59
60         errtot = -1; /* 'ERRMSG' next line will set at zero */
61         fprintf(stderr, "\n");
62         ERRMSG("This is a debugging function and not intended for general use, running slow test!");
63
64         /* force recalc, even if tagged as valid, since this mesh is suspect! */
65         bm->elem_index_dirty |= BM_ALL;
66         BM_mesh_elem_index_ensure(bm, BM_ALL);
67
68         BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
69                 if (BM_elem_flag_test(v, BM_ELEM_SELECT | BM_ELEM_HIDDEN) == (BM_ELEM_SELECT | BM_ELEM_HIDDEN)) {
70                         ERRMSG("vert %d: is hidden and selected", i);
71                 }
72
73                 if (v->e) {
74                         if (!BM_vert_in_edge(v->e, v)) {
75                                 ERRMSG("vert %d: is not in its referenced edge: %d", i, BM_elem_index_get(v->e));
76                         }
77                 }
78         }
79
80         /* check edges */
81         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
82                 void **val_p;
83
84                 if (e->v1 == e->v2) {
85                         ERRMSG("edge %d: duplicate index: %d", i, BM_elem_index_get(e->v1));
86                 }
87
88                 /* build edgehash at the same time */
89                 if (BLI_edgehash_ensure_p(edge_hash, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2), &val_p)) {
90                         BMEdge *e_other = *val_p;
91                         ERRMSG("edge %d, %d: are duplicates", i, BM_elem_index_get(e_other));
92                 }
93                 else {
94                         *val_p = e;
95                 }
96         }
97
98         /* edge radial structure */
99         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
100                 if (BM_elem_flag_test(e, BM_ELEM_SELECT | BM_ELEM_HIDDEN) == (BM_ELEM_SELECT | BM_ELEM_HIDDEN)) {
101                         ERRMSG("edge %d: is hidden and selected", i);
102                 }
103
104                 if (e->l) {
105                         BMLoop *l_iter;
106                         BMLoop *l_first;
107
108                         j = 0;
109
110                         l_iter = l_first = e->l;
111                         /* we could do more checks here, but save for face checks */
112                         do {
113                                 if (l_iter->e != e) {
114                                         ERRMSG("edge %d: has invalid loop, loop is of face %d", i, BM_elem_index_get(l_iter->f));
115                                 }
116                                 else if (BM_vert_in_edge(e, l_iter->v) == false) {
117                                         ERRMSG("edge %d: has invalid loop with vert not in edge, loop is of face %d",
118                                                i, BM_elem_index_get(l_iter->f));
119                                 }
120                                 else if (BM_vert_in_edge(e, l_iter->next->v) == false) {
121                                         ERRMSG("edge %d: has invalid loop with next vert not in edge, loop is of face %d",
122                                                i, BM_elem_index_get(l_iter->f));
123                                 }
124                         } while ((l_iter = l_iter->radial_next) != l_first);
125                 }
126         }
127
128         /* face structure */
129         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
130                 BMLoop *l_iter;
131                 BMLoop *l_first;
132
133                 if (BM_elem_flag_test(f, BM_ELEM_SELECT | BM_ELEM_HIDDEN) == (BM_ELEM_SELECT | BM_ELEM_HIDDEN)) {
134                         ERRMSG("face %d: is hidden and selected", i);
135                 }
136
137                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
138
139                 do {
140                         BM_elem_flag_disable(l_iter,    BM_ELEM_INTERNAL_TAG);
141                         BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
142                         BM_elem_flag_disable(l_iter->e, BM_ELEM_INTERNAL_TAG);
143                 } while ((l_iter = l_iter->next) != l_first);
144
145                 j = 0;
146
147                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
148                 do {
149                         if (BM_elem_flag_test(l_iter, BM_ELEM_INTERNAL_TAG)) {
150                                 ERRMSG("face %d: has duplicate loop at corner: %d", i, j);
151                         }
152                         if (BM_elem_flag_test(l_iter->v, BM_ELEM_INTERNAL_TAG)) {
153                                 ERRMSG("face %d: has duplicate vert: %d, at corner: %d", i, BM_elem_index_get(l_iter->v), j);
154                         }
155                         if (BM_elem_flag_test(l_iter->e, BM_ELEM_INTERNAL_TAG)) {
156                                 ERRMSG("face %d: has duplicate edge: %d, at corner: %d", i,  BM_elem_index_get(l_iter->e), j);
157                         }
158
159                         /* adjacent data checks */
160                         if (l_iter->f != f) {
161                                 ERRMSG("face %d: has loop that points to face: %d at corner: %d", i, BM_elem_index_get(l_iter->f), j);
162                         }
163                         if (l_iter != l_iter->prev->next) {
164                                 ERRMSG("face %d: has invalid 'prev/next' at corner: %d", i, j);
165                         }
166                         if (l_iter != l_iter->next->prev) {
167                                 ERRMSG("face %d: has invalid 'next/prev' at corner: %d", i, j);
168                         }
169                         if (l_iter != l_iter->radial_prev->radial_next) {
170                                 ERRMSG("face %d: has invalid 'radial_prev/radial_next' at corner: %d", i, j);
171                         }
172                         if (l_iter != l_iter->radial_next->radial_prev) {
173                                 ERRMSG("face %d: has invalid 'radial_next/radial_prev' at corner: %d", i, j);
174                         }
175
176                         BM_elem_flag_enable(l_iter,    BM_ELEM_INTERNAL_TAG);
177                         BM_elem_flag_enable(l_iter->v, BM_ELEM_INTERNAL_TAG);
178                         BM_elem_flag_enable(l_iter->e, BM_ELEM_INTERNAL_TAG);
179                         j++;
180                 } while ((l_iter = l_iter->next) != l_first);
181
182                 if (j != f->len) {
183                         ERRMSG("face %d: has length of %d but should be %d", i, f->len, j);
184                 }
185
186                 /* leave elements un-tagged, not essential but nice to avoid unintended dirty tag use later. */
187                 do {
188                         BM_elem_flag_disable(l_iter,    BM_ELEM_INTERNAL_TAG);
189                         BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
190                         BM_elem_flag_disable(l_iter->e, BM_ELEM_INTERNAL_TAG);
191                 } while ((l_iter = l_iter->next) != l_first);
192         }
193
194         BLI_edgehash_free(edge_hash, NULL);
195
196         const bool is_valid = (errtot == 0);
197         ERRMSG("Finished - errors %d", errtot);
198         return is_valid;
199 }
200
201
202 #endif