SVN maintenance.
[blender.git] / source / blender / blenkernel / intern / mesh_validate.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2011 Blender Foundation.
21  * All rights reserved.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <limits.h>
30
31 #include "DNA_mesh_types.h"
32 #include "DNA_meshdata_types.h"
33
34 #include "BLI_utildefines.h"
35 #include "BLI_edgehash.h"
36
37 #include "BKE_DerivedMesh.h"
38
39 #include "MEM_guardedalloc.h"
40
41 #include "ED_mesh.h"
42
43 typedef struct SearchFace {
44         unsigned int v[4];
45         unsigned int index;
46 } SearchFace;
47
48 static int uint_cmp(const void *v1, const void *v2)
49 {
50         const unsigned int x1= GET_INT_FROM_POINTER(v1), x2= GET_INT_FROM_POINTER(v2);
51
52         if( x1 > x2 ) return 1;
53         else if( x1 < x2 ) return -1;
54         return 0;
55 }
56
57 static int search_face_cmp(const void *v1, const void *v2)
58 {
59         const SearchFace *sfa= v1, *sfb= v2;
60
61         if              (sfa->v[0] > sfb->v[0]) return 1;
62         else if (sfa->v[0] < sfb->v[0]) return -1;
63
64         if              (sfa->v[1] > sfb->v[1]) return 1;
65         else if (sfa->v[1] < sfb->v[1]) return -1;
66
67         if              (sfa->v[2] > sfb->v[2]) return 1;
68         else if (sfa->v[2] < sfb->v[2]) return -1;
69
70         if              (sfa->v[3] > sfb->v[3]) return 1;
71         else if (sfa->v[3] < sfb->v[3]) return -1;
72
73         return 0;
74 }
75
76 void BKE_mesh_validate_arrays(MVert *UNUSED(mverts), int totvert, MEdge *medges, int totedge, MFace *mfaces, int totface)
77 {
78 //      MVert *mv;
79         MEdge *med;
80         MFace *mf;
81         int i;
82
83         EdgeHash *edge_hash = BLI_edgehash_new();
84
85         SearchFace *search_faces= MEM_callocN(sizeof(SearchFace) * totface, "search faces");
86         SearchFace *sf;
87         SearchFace *sf_prev;
88
89         printf("ED_mesh_validate: verts(%d), edges(%d), faces(%d)\n", totvert, totedge, totface);
90
91         if(totedge==0 && totface != 0) {
92                 printf("    locical error, %d faces and 0 edges\n", totface);
93         }
94
95         for(i=0, med=medges; i<totedge; i++, med++) {
96                 if(med->v1 == med->v2) {
97                         printf("    edge %d: has matching verts, both %d\n", i, med->v1);
98                 }
99                 if(med->v1 < 0 || med->v1 >= totvert) {
100                         printf("    edge %d: v1 index out of range, %d\n", i, med->v1);
101                 }
102                 if(med->v2 < 0 || med->v2 >= totvert) {
103                         printf("    edge %d: v2 index out of range, %d\n", i, med->v2);
104                 }
105
106                 if(BLI_edgehash_haskey(edge_hash, med->v1, med->v2)) {
107                         printf("    edge %d: is a duplicate of, %d\n", i, GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, med->v1, med->v2)));
108                 }
109
110                 BLI_edgehash_insert(edge_hash, med->v1, med->v2, SET_INT_IN_POINTER(i));
111         }
112
113         for(i=0, mf=mfaces; i<totface; i++, mf++) {
114                 unsigned int fverts[4];
115                 // unsigned int fedges[4];
116                 int fidx;
117
118                 fidx = mf->v4 ? 3:2;
119                 do {
120                         fverts[fidx]= *(&mf->v1 + fidx);
121                         if(fverts[fidx] < 0 || fverts[fidx] >= totvert) {
122                                 printf("    face %d: 'v%d' index out of range, %d\n", i, fidx + 1, fverts[fidx]);
123                         }
124                 } while (fidx--);
125
126                 if(mf->v4) {
127                         if(mf->v1 == mf->v2) printf("    face %d: verts invalid, v1/v2 both %d\n", i, mf->v1);
128                         if(mf->v1 == mf->v3) printf("    face %d: verts invalid, v1/v3 both %d\n", i, mf->v1);
129                         if(mf->v1 == mf->v4) printf("    face %d: verts invalid, v1/v4 both %d\n", i, mf->v1);
130
131                         if(mf->v2 == mf->v3) printf("    face %d: verts invalid, v2/v3 both %d\n", i, mf->v2);
132                         if(mf->v2 == mf->v4) printf("    face %d: verts invalid, v2/v4 both %d\n", i, mf->v2);
133
134                         if(mf->v3 == mf->v4) printf("    face %d: verts invalid, v3/v4 both %d\n", i, mf->v3);
135
136                         if(totedge) {
137                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) printf("    face %d: edge v1/v2 (%d,%d) is missing egde data\n", i, mf->v1, mf->v2);
138                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) printf("    face %d: edge v2/v3 (%d,%d) is missing egde data\n", i, mf->v2, mf->v3);
139                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v4)) printf("    face %d: edge v3/v4 (%d,%d) is missing egde data\n", i, mf->v3, mf->v4);
140                                 if(!BLI_edgehash_haskey(edge_hash, mf->v4, mf->v1)) printf("    face %d: edge v4/v1 (%d,%d) is missing egde data\n", i, mf->v4, mf->v1);
141                         }
142                         /* TODO, avoid double lookop */
143                         /*
144                         fedges[0]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v1, mf->v2));
145                         fedges[1]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v2, mf->v3));
146                         fedges[2]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v3, mf->v4));
147                         fedges[3]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v4, mf->v1));
148                         */
149                         qsort(fverts, 4, sizeof(int), uint_cmp);
150                 }
151                 else {
152                         if(mf->v1 == mf->v2) printf("    face %d: verts invalid, v1/v2 both %d\n", i, mf->v1);
153                         if(mf->v1 == mf->v3) printf("    face %d: verts invalid, v1/v3 both %d\n", i, mf->v1);
154
155                         if(mf->v2 == mf->v3) printf("    face %d: verts invalid, v2/v3 both %d\n", i, mf->v2);
156
157                         if(totedge) {
158                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) printf("    face %d: edge v1/v2 (%d,%d) is missing egde data\n", i, mf->v1, mf->v2);
159                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) printf("    face %d: edge v2/v3 (%d,%d) is missing egde data\n", i, mf->v2, mf->v3);
160                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v1)) printf("    face %d: edge v3/v1 (%d,%d) is missing egde data\n", i, mf->v3, mf->v1);
161                         }
162                         /* TODO, avoid double lookop */
163                         /*
164                         fedges[0]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v1, mf->v2));
165                         fedges[1]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v2, mf->v3));
166                         fedges[2]= GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, mf->v3, mf->v1));
167                         */
168                         qsort(fverts, 3, sizeof(int), uint_cmp);
169                 }
170
171                 search_faces[i].index = i;
172
173                 if(mf->v4) {
174                         search_faces[i].v[0] = fverts[0];
175                         search_faces[i].v[1] = fverts[1];
176                         search_faces[i].v[2] = fverts[2];
177                         search_faces[i].v[3] = fverts[3];
178                 }
179                 else {
180                         search_faces[i].v[0] = fverts[0];
181                         search_faces[i].v[1] = fverts[1];
182                         search_faces[i].v[2] = fverts[2];
183                         search_faces[i].v[3] = UINT_MAX;
184                 }
185         }
186
187         qsort(search_faces, totface, sizeof(SearchFace), search_face_cmp);
188
189         sf= search_faces;
190         sf_prev= sf;
191         sf++;
192
193         for(i=1; i<totface; i++, sf++, sf_prev++) {
194                 /* on a valid mesh, code below will never run */
195                 if(memcmp(sf->v, sf_prev->v, sizeof(sf_prev->v)) == 0) {
196                         /* slow, could be smarter here */
197                         MFace *mf= mfaces + sf->index;
198                         MFace *mf_prev= mfaces + sf_prev->index;
199                         int size_expect, size_found;
200
201                         EdgeHash *eh_tmp= BLI_edgehash_new();
202                         if(mf->v4) {
203                                 BLI_edgehash_insert(eh_tmp, mf->v1, mf->v2, NULL);
204                                 BLI_edgehash_insert(eh_tmp, mf->v2, mf->v3, NULL);
205                                 BLI_edgehash_insert(eh_tmp, mf->v3, mf->v4, NULL);
206                                 BLI_edgehash_insert(eh_tmp, mf->v4, mf->v1, NULL);
207
208                                 BLI_edgehash_insert(eh_tmp, mf_prev->v1, mf_prev->v2, NULL);
209                                 BLI_edgehash_insert(eh_tmp, mf_prev->v2, mf_prev->v3, NULL);
210                                 BLI_edgehash_insert(eh_tmp, mf_prev->v3, mf_prev->v4, NULL);
211                                 BLI_edgehash_insert(eh_tmp, mf_prev->v4, mf_prev->v1, NULL);
212
213                                 size_expect= 4;
214                         }
215                         else {
216                                 BLI_edgehash_insert(eh_tmp, mf->v1, mf->v2, NULL);
217                                 BLI_edgehash_insert(eh_tmp, mf->v2, mf->v3, NULL);
218                                 BLI_edgehash_insert(eh_tmp, mf->v3, mf->v1, NULL);
219
220                                 BLI_edgehash_insert(eh_tmp, mf_prev->v1, mf_prev->v2, NULL);
221                                 BLI_edgehash_insert(eh_tmp, mf_prev->v2, mf_prev->v3, NULL);
222                                 BLI_edgehash_insert(eh_tmp, mf_prev->v3, mf_prev->v1, NULL);
223
224                                 size_expect= 3;
225                         }
226
227                         size_found= BLI_edgehash_size(eh_tmp);
228                         BLI_edgehash_free(eh_tmp, NULL);
229
230                         if(size_found != size_expect) {
231                                 printf("    face %d & %d: are duplicates ", sf->index, sf_prev->index);
232                                 if(mf->v4) {
233                                         printf("(%d,%d,%d,%d) ", mf->v1, mf->v2, mf->v3, mf->v4);
234                                         printf("(%d,%d,%d,%d)\n", mf_prev->v1, mf_prev->v2, mf_prev->v3, mf_prev->v4);
235                                 }
236                                 else {
237                                         printf("(%d,%d,%d) ", mf->v1, mf->v2, mf->v3);
238                                         printf("(%d,%d,%d)\n", mf_prev->v1, mf_prev->v2, mf_prev->v3);
239                                 }
240                         }
241                 }
242         }
243
244         BLI_edgehash_free(edge_hash, NULL);
245         MEM_freeN(search_faces);
246
247         printf("BKE_mesh_validate: finished\n\n");
248 }
249
250 void BKE_mesh_validate(Mesh *me)
251 {
252         printf("MESH: %s\n", me->id.name+2);
253         BKE_mesh_validate_arrays(me->mvert, me->totvert, me->medge, me->totedge, me->mface, me->totface);
254 }
255
256 void BKE_mesh_validate_dm(DerivedMesh *dm)
257 {
258         BKE_mesh_validate_arrays(dm->getVertArray(dm), dm->getNumVerts(dm), dm->getEdgeArray(dm), dm->getNumEdges(dm), dm->getFaceArray(dm), dm->getNumFaces(dm));
259 }