migrated NDOF code from soc-2010-merwin, SpaceNavigator now works on Mac blender
[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 /** \file blender/blenkernel/intern/mesh_validate.c
27  *  \ingroup bke
28  */
29
30
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <limits.h>
35
36 #include "DNA_mesh_types.h"
37 #include "DNA_meshdata_types.h"
38
39 #include "BLO_sys_types.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_edgehash.h"
43
44 #include "BKE_DerivedMesh.h"
45
46 #include "MEM_guardedalloc.h"
47
48 #include "BKE_mesh.h"
49
50 #define SELECT 1
51
52 typedef union {
53         uint32_t verts[2];
54         int64_t edval;
55 } EdgeUUID;
56
57 typedef struct SortFace {
58 //      unsigned int    v[4];
59         EdgeUUID                es[4];
60         unsigned int    index;
61 } SortFace;
62
63 static void edge_store_assign(uint32_t verts[2],  const uint32_t v1, const uint32_t v2)
64 {
65         if(v1 < v2) {
66                 verts[0]= v1;
67                 verts[1]= v2;
68         }
69         else {
70                 verts[0]= v2;
71                 verts[1]= v1;
72         }
73 }
74
75 static void edge_store_from_mface_quad(EdgeUUID es[4], MFace *mf)
76 {
77         edge_store_assign(es[0].verts, mf->v1, mf->v2);
78         edge_store_assign(es[1].verts, mf->v2, mf->v3);
79         edge_store_assign(es[2].verts, mf->v3, mf->v4);
80         edge_store_assign(es[3].verts, mf->v4, mf->v1);
81 }
82
83 static void edge_store_from_mface_tri(EdgeUUID es[3], MFace *mf)
84 {
85         edge_store_assign(es[0].verts, mf->v1, mf->v2);
86         edge_store_assign(es[1].verts, mf->v2, mf->v3);
87         edge_store_assign(es[2].verts, mf->v3, mf->v1);
88         es[3].verts[0] = es[3].verts[1] = UINT_MAX;
89 }
90
91 static int int64_cmp(const void *v1, const void *v2)
92 {
93         const int64_t x1= *(const int64_t *)v1;
94         const int64_t x2= *(const int64_t *)v2;
95
96         if( x1 > x2 ) return 1;
97         else if( x1 < x2 ) return -1;
98         return 0;
99 }
100
101 static int search_face_cmp(const void *v1, const void *v2)
102 {
103         const SortFace *sfa= v1, *sfb= v2;
104
105         if      (sfa->es[0].edval > sfb->es[0].edval) return 1;
106         else if (sfa->es[0].edval < sfb->es[0].edval) return -1;
107
108         else if (sfa->es[1].edval > sfb->es[1].edval) return 1;
109         else if (sfa->es[1].edval < sfb->es[1].edval) return -1;
110
111         else if (sfa->es[2].edval > sfb->es[2].edval) return 1;
112         else if (sfa->es[2].edval < sfb->es[2].edval) return -1;
113
114         else if (sfa->es[3].edval > sfb->es[3].edval) return 1;
115         else if (sfa->es[3].edval < sfb->es[3].edval) return -1;
116         else                                                                              return 0;
117
118 }
119
120 int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), unsigned int totvert, MEdge *medges, unsigned int totedge, MFace *mfaces, unsigned int totface, const short do_verbose, const short do_fixes)
121 {
122 #       define PRINT if(do_verbose) printf
123 #       define REMOVE_EDGE_TAG(_med) { _med->v2= _med->v1; do_edge_free= 1; }
124 #       define REMOVE_FACE_TAG(_mf) { _mf->v3=0; do_face_free= 1; }
125
126 //      MVert *mv;
127         MEdge *med;
128         MFace *mf;
129         MFace *mf_prev;
130         unsigned int i;
131
132         int do_face_free= FALSE;
133         int do_edge_free= FALSE;
134
135         int do_edge_recalc= FALSE;
136
137         EdgeHash *edge_hash = BLI_edgehash_new();
138
139         SortFace *sort_faces= MEM_callocN(sizeof(SortFace) * totface, "search faces");
140         SortFace *sf;
141         SortFace *sf_prev;
142         unsigned int totsortface= 0;
143
144         BLI_assert(!(do_fixes && me == NULL));
145
146         PRINT("ED_mesh_validate: verts(%d), edges(%d), faces(%d)\n", totvert, totedge, totface);
147
148         if(totedge == 0 && totface != 0) {
149                 PRINT("    locical error, %d faces and 0 edges\n", totface);
150                 do_edge_recalc= TRUE;
151         }
152
153         for(i=0, med= medges; i<totedge; i++, med++) {
154                 int remove= FALSE;
155                 if(med->v1 == med->v2) {
156                         PRINT("    edge %d: has matching verts, both %d\n", i, med->v1);
157                         remove= do_fixes;
158                 }
159                 if(med->v1 >= totvert) {
160                         PRINT("    edge %d: v1 index out of range, %d\n", i, med->v1);
161                         remove= do_fixes;
162                 }
163                 if(med->v2 >= totvert) {
164                         PRINT("    edge %d: v2 index out of range, %d\n", i, med->v2);
165                         remove= do_fixes;
166                 }
167
168                 if(BLI_edgehash_haskey(edge_hash, med->v1, med->v2)) {
169                         PRINT("    edge %d: is a duplicate of, %d\n", i, GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, med->v1, med->v2)));
170                         remove= do_fixes;
171                 }
172
173                 if(remove == FALSE){
174                         BLI_edgehash_insert(edge_hash, med->v1, med->v2, SET_INT_IN_POINTER(i));
175                 }
176                 else {
177                         REMOVE_EDGE_TAG(med);
178                 }
179         }
180
181         for(i=0, mf=mfaces, sf=sort_faces; i<totface; i++, mf++) {
182                 int remove= FALSE;
183                 int fidx;
184                 unsigned int fv[4];
185
186                 fidx = mf->v4 ? 3:2;
187                 do {
188                         fv[fidx]= *(&(mf->v1) + fidx);
189                         if(fv[fidx] >= totvert) {
190                                 PRINT("    face %d: 'v%d' index out of range, %d\n", i, fidx + 1, fv[fidx]);
191                                 remove= do_fixes;
192                         }
193                 } while (fidx--);
194
195                 if(remove == FALSE) {
196                         if(mf->v4) {
197                                 if(mf->v1 == mf->v2) { PRINT("    face %d: verts invalid, v1/v2 both %d\n", i, mf->v1); remove= do_fixes; }
198                                 if(mf->v1 == mf->v3) { PRINT("    face %d: verts invalid, v1/v3 both %d\n", i, mf->v1); remove= do_fixes;  }
199                                 if(mf->v1 == mf->v4) { PRINT("    face %d: verts invalid, v1/v4 both %d\n", i, mf->v1); remove= do_fixes;  }
200
201                                 if(mf->v2 == mf->v3) { PRINT("    face %d: verts invalid, v2/v3 both %d\n", i, mf->v2); remove= do_fixes;  }
202                                 if(mf->v2 == mf->v4) { PRINT("    face %d: verts invalid, v2/v4 both %d\n", i, mf->v2); remove= do_fixes;  }
203
204                                 if(mf->v3 == mf->v4) { PRINT("    face %d: verts invalid, v3/v4 both %d\n", i, mf->v3); remove= do_fixes;  }
205                         }
206                         else {
207                                 if(mf->v1 == mf->v2) { PRINT("    faceT %d: verts invalid, v1/v2 both %d\n", i, mf->v1); remove= do_fixes; }
208                                 if(mf->v1 == mf->v3) { PRINT("    faceT %d: verts invalid, v1/v3 both %d\n", i, mf->v1); remove= do_fixes; }
209
210                                 if(mf->v2 == mf->v3) { PRINT("    faceT %d: verts invalid, v2/v3 both %d\n", i, mf->v2); remove= do_fixes; }
211                         }
212
213                         if(remove == FALSE) {
214                                 if(totedge) {
215                                         if(mf->v4) {
216                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) { PRINT("    face %d: edge v1/v2 (%d,%d) is missing egde data\n", i, mf->v1, mf->v2); do_edge_recalc= TRUE; }
217                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) { PRINT("    face %d: edge v2/v3 (%d,%d) is missing egde data\n", i, mf->v2, mf->v3); do_edge_recalc= TRUE; }
218                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v4)) { PRINT("    face %d: edge v3/v4 (%d,%d) is missing egde data\n", i, mf->v3, mf->v4); do_edge_recalc= TRUE; }
219                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v4, mf->v1)) { PRINT("    face %d: edge v4/v1 (%d,%d) is missing egde data\n", i, mf->v4, mf->v1); do_edge_recalc= TRUE; }
220                                         }
221                                         else {
222                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) { PRINT("    face %d: edge v1/v2 (%d,%d) is missing egde data\n", i, mf->v1, mf->v2); do_edge_recalc= TRUE; }
223                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) { PRINT("    face %d: edge v2/v3 (%d,%d) is missing egde data\n", i, mf->v2, mf->v3); do_edge_recalc= TRUE; }
224                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v1)) { PRINT("    face %d: edge v3/v1 (%d,%d) is missing egde data\n", i, mf->v3, mf->v1); do_edge_recalc= TRUE; }
225                                         }
226                                 }
227
228                                 sf->index = i;
229
230                                 if(mf->v4) {
231                                         edge_store_from_mface_quad(sf->es, mf);
232
233                                         qsort(sf->es, 4, sizeof(int64_t), int64_cmp);
234                                 }
235                                 else {
236                                         edge_store_from_mface_tri(sf->es, mf);
237                                         qsort(sf->es, 3, sizeof(int64_t), int64_cmp);
238                                 }
239
240                                 totsortface++;
241                                 sf++;
242                         }
243                 }
244                 if(remove) {
245                         REMOVE_FACE_TAG(mf);
246                 }
247         }
248
249         qsort(sort_faces, totsortface, sizeof(SortFace), search_face_cmp);
250
251         sf= sort_faces;
252         sf_prev= sf;
253         sf++;
254
255         for(i=1; i<totsortface; i++, sf++) {
256                 int remove= FALSE;
257                 /* on a valid mesh, code below will never run */
258                 if(memcmp(sf->es, sf_prev->es, sizeof(sf_prev->es)) == 0) {
259                         mf= mfaces + sf->index;
260
261                         if(do_verbose) {
262                                 mf_prev= mfaces + sf_prev->index;
263                                 if(mf->v4) {
264                                         PRINT("    face %d & %d: are duplicates (%d,%d,%d,%d) (%d,%d,%d,%d)\n", sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3, mf->v4, mf_prev->v1, mf_prev->v2, mf_prev->v3, mf_prev->v4);
265                                 }
266                                 else {
267                                         PRINT("    face %d & %d: are duplicates (%d,%d,%d) (%d,%d,%d)\n", sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3, mf_prev->v1, mf_prev->v2, mf_prev->v3);
268                                 }
269                         }
270
271                         remove= do_fixes;
272                 }
273                 else {
274                         sf_prev= sf;
275                 }
276
277                 if(remove) {
278                         REMOVE_FACE_TAG(mf);
279                 }
280         }
281
282         BLI_edgehash_free(edge_hash, NULL);
283         MEM_freeN(sort_faces);
284
285         PRINT("BKE_mesh_validate: finished\n\n");
286
287 #        undef PRINT
288 #        undef REMOVE_EDGE_TAG
289 #        undef REMOVE_FACE_TAG
290
291         if(me) {
292                 if(do_face_free) {
293                         mesh_strip_loose_faces(me);
294                 }
295
296                 if (do_edge_free) {
297                         mesh_strip_loose_edges(me);
298                 }
299
300                 if(do_fixes && do_edge_recalc) {
301                         BKE_mesh_calc_edges(me, TRUE);
302                 }
303         }
304
305         return (do_face_free || do_edge_free || do_edge_recalc);
306 }
307
308 int BKE_mesh_validate(Mesh *me, int do_verbose)
309 {
310         if(do_verbose) {
311                 printf("MESH: %s\n", me->id.name+2);
312         }
313         return BKE_mesh_validate_arrays(me, me->mvert, me->totvert, me->medge, me->totedge, me->mface, me->totface, do_verbose, TRUE);
314 }
315
316 int BKE_mesh_validate_dm(DerivedMesh *dm)
317 {
318         return BKE_mesh_validate_arrays(NULL, dm->getVertArray(dm), dm->getNumVerts(dm), dm->getEdgeArray(dm), dm->getNumEdges(dm), dm->getFaceArray(dm), dm->getNumFaces(dm), TRUE, FALSE);
319 }
320
321 void BKE_mesh_calc_edges(Mesh *mesh, int update)
322 {
323         CustomData edata;
324         EdgeHashIterator *ehi;
325         MFace *mf = mesh->mface;
326         MEdge *med, *med_orig;
327         EdgeHash *eh = BLI_edgehash_new();
328         int i, totedge, totface = mesh->totface;
329
330         if(mesh->totedge==0)
331                 update= 0;
332
333         if(update) {
334                 /* assume existing edges are valid
335                  * useful when adding more faces and generating edges from them */
336                 med= mesh->medge;
337                 for(i= 0; i<mesh->totedge; i++, med++)
338                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
339         }
340
341         for (i = 0; i < totface; i++, mf++) {
342                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
343                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
344                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
345                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
346
347                 if (mf->v4) {
348                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
349                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
350                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
351                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
352                 } else {
353                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
354                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
355                 }
356         }
357
358         totedge = BLI_edgehash_size(eh);
359
360         /* write new edges into a temporary CustomData */
361         memset(&edata, 0, sizeof(edata));
362         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
363
364         ehi = BLI_edgehashIterator_new(eh);
365         med = CustomData_get_layer(&edata, CD_MEDGE);
366         for(i = 0; !BLI_edgehashIterator_isDone(ehi);
367                 BLI_edgehashIterator_step(ehi), ++i, ++med) {
368
369                 if(update && (med_orig=BLI_edgehashIterator_getValue(ehi))) {
370                         *med= *med_orig; /* copy from the original */
371                 } else {
372                         BLI_edgehashIterator_getKey(ehi, (int*)&med->v1, (int*)&med->v2);
373                         med->flag = ME_EDGEDRAW|ME_EDGERENDER|SELECT; /* select for newly created meshes which are selected [#25595] */
374                 }
375         }
376         BLI_edgehashIterator_free(ehi);
377
378         /* free old CustomData and assign new one */
379         CustomData_free(&mesh->edata, mesh->totedge);
380         mesh->edata = edata;
381         mesh->totedge = totedge;
382
383         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
384
385         BLI_edgehash_free(eh, NULL);
386 }