svn merge ^/trunk/blender -r43639:43664
[blender.git] / source / blender / blenkernel / intern / mesh_validate.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) 2011 Blender Foundation.
19  * All rights reserved.
20  *
21  * ***** END GPL LICENSE BLOCK *****
22  */
23
24 /** \file blender/blenkernel/intern/mesh_validate.c
25  *  \ingroup bke
26  */
27
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <limits.h>
33
34 #include "DNA_mesh_types.h"
35 #include "DNA_meshdata_types.h"
36
37 #include "BLO_sys_types.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_math_base.h"
42
43 #include "BKE_DerivedMesh.h"
44
45 #include "MEM_guardedalloc.h"
46
47 #include "BKE_mesh.h"
48 #include "BKE_deform.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[4], 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 #define PRINT if(do_verbose) printf
121
122 int BKE_mesh_validate_arrays( Mesh *me,
123                               MVert *mverts, unsigned int totvert,
124                               MEdge *medges, unsigned int totedge,
125                               MFace *mfaces, unsigned int totface,
126                               MDeformVert *dverts, /* assume totvert length */
127                               const short do_verbose, const short do_fixes)
128 {
129 #       define REMOVE_EDGE_TAG(_med) { _med->v2= _med->v1; do_edge_free= 1; }
130 #       define REMOVE_FACE_TAG(_mf) { _mf->v3=0; do_face_free= 1; }
131
132 //      MVert *mv;
133         MEdge *med;
134         MFace *mf;
135         MFace *mf_prev;
136         MVert *mvert= mverts;
137         unsigned int i;
138
139         short do_face_free= FALSE;
140         short do_edge_free= FALSE;
141
142         short verts_fixed= FALSE;
143         short vert_weights_fixed= FALSE;
144
145         int do_edge_recalc= FALSE;
146
147         EdgeHash *edge_hash = BLI_edgehash_new();
148
149         SortFace *sort_faces= MEM_callocN(sizeof(SortFace) * totface, "search faces");
150         SortFace *sf;
151         SortFace *sf_prev;
152         unsigned int totsortface= 0;
153
154         BLI_assert(!(do_fixes && me == NULL));
155
156         PRINT("%s: verts(%u), edges(%u), faces(%u)\n", __func__, totvert, totedge, totface);
157
158         if(totedge == 0 && totface != 0) {
159                 PRINT("    locical error, %u faces and 0 edges\n", totface);
160                 do_edge_recalc= TRUE;
161         }
162
163         for(i=1; i<totvert; i++, mvert++) {
164                 int j;
165                 int fix_normal= TRUE;
166
167                 for(j=0; j<3; j++) {
168                         if(!finite(mvert->co[j])) {
169                                 PRINT("    vertex %u: has invalid coordinate\n", i);
170
171                                 if (do_fixes) {
172                                         zero_v3(mvert->co);
173
174                                         verts_fixed= TRUE;
175                                 }
176                         }
177
178                         if(mvert->no[j]!=0)
179                                 fix_normal= FALSE;
180                 }
181
182                 if(fix_normal) {
183                         PRINT("    vertex %u: has zero normal, assuming Z-up normal\n", i);
184                         if (do_fixes) {
185                                 mvert->no[2]= SHRT_MAX;
186                                 verts_fixed= TRUE;
187                         }
188                 }
189         }
190
191         for(i=0, med= medges; i<totedge; i++, med++) {
192                 int remove= FALSE;
193                 if(med->v1 == med->v2) {
194                         PRINT("    edge %u: has matching verts, both %u\n", i, med->v1);
195                         remove= do_fixes;
196                 }
197                 if(med->v1 >= totvert) {
198                         PRINT("    edge %u: v1 index out of range, %u\n", i, med->v1);
199                         remove= do_fixes;
200                 }
201                 if(med->v2 >= totvert) {
202                         PRINT("    edge %u: v2 index out of range, %u\n", i, med->v2);
203                         remove= do_fixes;
204                 }
205
206                 if(BLI_edgehash_haskey(edge_hash, med->v1, med->v2)) {
207                         PRINT("    edge %u: is a duplicate of, %d\n", i, GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, med->v1, med->v2)));
208                         remove= do_fixes;
209                 }
210
211                 if(remove == FALSE){
212                         BLI_edgehash_insert(edge_hash, med->v1, med->v2, SET_INT_IN_POINTER(i));
213                 }
214                 else {
215                         REMOVE_EDGE_TAG(med);
216                 }
217         }
218
219         for(i=0, mf=mfaces, sf=sort_faces; i<totface; i++, mf++) {
220                 int remove= FALSE;
221                 int fidx;
222                 unsigned int fv[4];
223
224                 fidx = mf->v4 ? 3:2;
225                 do {
226                         fv[fidx]= *(&(mf->v1) + fidx);
227                         if(fv[fidx] >= totvert) {
228                                 PRINT("    face %u: 'v%d' index out of range, %u\n", i, fidx + 1, fv[fidx]);
229                                 remove= do_fixes;
230                         }
231                 } while (fidx--);
232
233                 if(remove == FALSE) {
234                         if(mf->v4) {
235                                 if(mf->v1 == mf->v2) { PRINT("    face %u: verts invalid, v1/v2 both %u\n", i, mf->v1); remove= do_fixes; }
236                                 if(mf->v1 == mf->v3) { PRINT("    face %u: verts invalid, v1/v3 both %u\n", i, mf->v1); remove= do_fixes;  }
237                                 if(mf->v1 == mf->v4) { PRINT("    face %u: verts invalid, v1/v4 both %u\n", i, mf->v1); remove= do_fixes;  }
238
239                                 if(mf->v2 == mf->v3) { PRINT("    face %u: verts invalid, v2/v3 both %u\n", i, mf->v2); remove= do_fixes;  }
240                                 if(mf->v2 == mf->v4) { PRINT("    face %u: verts invalid, v2/v4 both %u\n", i, mf->v2); remove= do_fixes;  }
241
242                                 if(mf->v3 == mf->v4) { PRINT("    face %u: verts invalid, v3/v4 both %u\n", i, mf->v3); remove= do_fixes;  }
243                         }
244                         else {
245                                 if(mf->v1 == mf->v2) { PRINT("    faceT %u: verts invalid, v1/v2 both %u\n", i, mf->v1); remove= do_fixes; }
246                                 if(mf->v1 == mf->v3) { PRINT("    faceT %u: verts invalid, v1/v3 both %u\n", i, mf->v1); remove= do_fixes; }
247
248                                 if(mf->v2 == mf->v3) { PRINT("    faceT %u: verts invalid, v2/v3 both %u\n", i, mf->v2); remove= do_fixes; }
249                         }
250
251                         if(remove == FALSE) {
252                                 if(totedge) {
253                                         if(mf->v4) {
254                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) { PRINT("    face %u: edge v1/v2 (%u,%u) is missing egde data\n", i, mf->v1, mf->v2); do_edge_recalc= TRUE; }
255                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) { PRINT("    face %u: edge v2/v3 (%u,%u) is missing egde data\n", i, mf->v2, mf->v3); do_edge_recalc= TRUE; }
256                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v4)) { PRINT("    face %u: edge v3/v4 (%u,%u) is missing egde data\n", i, mf->v3, mf->v4); do_edge_recalc= TRUE; }
257                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v4, mf->v1)) { PRINT("    face %u: edge v4/v1 (%u,%u) is missing egde data\n", i, mf->v4, mf->v1); do_edge_recalc= TRUE; }
258                                         }
259                                         else {
260                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v1, mf->v2)) { PRINT("    face %u: edge v1/v2 (%u,%u) is missing egde data\n", i, mf->v1, mf->v2); do_edge_recalc= TRUE; }
261                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v2, mf->v3)) { PRINT("    face %u: edge v2/v3 (%u,%u) is missing egde data\n", i, mf->v2, mf->v3); do_edge_recalc= TRUE; }
262                                                 if(!BLI_edgehash_haskey(edge_hash, mf->v3, mf->v1)) { PRINT("    face %u: edge v3/v1 (%u,%u) is missing egde data\n", i, mf->v3, mf->v1); do_edge_recalc= TRUE; }
263                                         }
264                                 }
265
266                                 sf->index = i;
267
268                                 if(mf->v4) {
269                                         edge_store_from_mface_quad(sf->es, mf);
270
271                                         qsort(sf->es, 4, sizeof(int64_t), int64_cmp);
272                                 }
273                                 else {
274                                         edge_store_from_mface_tri(sf->es, mf);
275                                         qsort(sf->es, 3, sizeof(int64_t), int64_cmp);
276                                 }
277
278                                 totsortface++;
279                                 sf++;
280                         }
281                 }
282                 if(remove) {
283                         REMOVE_FACE_TAG(mf);
284                 }
285         }
286
287         qsort(sort_faces, totsortface, sizeof(SortFace), search_face_cmp);
288
289         sf= sort_faces;
290         sf_prev= sf;
291         sf++;
292
293         for(i=1; i<totsortface; i++, sf++) {
294                 int remove= FALSE;
295                 /* on a valid mesh, code below will never run */
296                 if(memcmp(sf->es, sf_prev->es, sizeof(sf_prev->es)) == 0) {
297                         mf= mfaces + sf->index;
298
299                         if(do_verbose) {
300                                 mf_prev= mfaces + sf_prev->index;
301                                 if(mf->v4) {
302                                         PRINT("    face %u & %u: are duplicates (%u,%u,%u,%u) (%u,%u,%u,%u)\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);
303                                 }
304                                 else {
305                                         PRINT("    face %u & %u: are duplicates (%u,%u,%u) (%u,%u,%u)\n", sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3, mf_prev->v1, mf_prev->v2, mf_prev->v3);
306                                 }
307                         }
308
309                         remove= do_fixes;
310                 }
311                 else {
312                         sf_prev= sf;
313                 }
314
315                 if(remove) {
316                         REMOVE_FACE_TAG(mf);
317                 }
318         }
319
320         BLI_edgehash_free(edge_hash, NULL);
321         MEM_freeN(sort_faces);
322
323
324         /* fix deform verts */
325         if (dverts) {
326                 MDeformVert *dv;
327                 for(i=0, dv= dverts; i<totvert; i++, dv++) {
328                         MDeformWeight *dw;
329                         unsigned int j;
330
331                         for(j=0, dw= dv->dw; j < dv->totweight; j++, dw++) {
332                                 /* note, greater then max defgroups is accounted for in our code, but not < 0 */
333                                 if (!finite(dw->weight)) {
334                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
335                                         if (do_fixes) {
336                                                 dw->weight= 0.0f;
337                                                 vert_weights_fixed= TRUE;
338                                         }
339                                 }
340                                 else if (dw->weight < 0.0f || dw->weight > 1.0f) {
341                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
342                                         if (do_fixes) {
343                                                 CLAMP(dw->weight, 0.0f, 1.0f);
344                                                 vert_weights_fixed= TRUE;
345                                         }
346                                 }
347
348                                 if (dw->def_nr < 0) {
349                                         PRINT("    vertex deform %u, has invalid group %d\n", i, dw->def_nr);
350                                         if (do_fixes) {
351                                                 defvert_remove_group(dv, dw);
352                                                 if (dv->dw) {
353                                                         /* re-allocated, the new values compensate for stepping
354                                                          * within the for loop and may not be valid */
355                                                         j--;
356                                                         dw= dv->dw + j;
357
358                                                         vert_weights_fixed= TRUE;
359                                                 }
360                                                 else { /* all freed */
361                                                         break;
362                                                 }
363                                         }
364                                 }
365                         }
366                 }
367         }
368
369
370         PRINT("BKE_mesh_validate: finished\n\n");
371
372 #        undef REMOVE_EDGE_TAG
373 #        undef REMOVE_FACE_TAG
374
375         if(me) {
376                 if(do_face_free) {
377                         mesh_strip_loose_faces(me);
378                 }
379
380                 if (do_edge_free) {
381                         mesh_strip_loose_edges(me);
382                 }
383
384                 if(do_fixes && do_edge_recalc) {
385                         BKE_mesh_calc_edges(me, TRUE);
386                 }
387         }
388
389         return (verts_fixed || vert_weights_fixed || do_face_free || do_edge_free || do_edge_recalc);
390 }
391
392 static int mesh_validate_customdata(CustomData *data, short do_verbose, const short do_fixes)
393 {
394         int i= 0, has_fixes= 0;
395
396         while(i<data->totlayer) {
397                 CustomDataLayer *layer= &data->layers[i];
398                 CustomDataMask mask= CD_TYPE_AS_MASK(layer->type);
399                 int ok= 1;
400
401                 if((mask&CD_MASK_MESH)==0) {
402                         PRINT("CustomDataLayer type %d which isn't in CD_MASK_MESH is stored in Mehs structure\n", layer->type);
403
404                         if(do_fixes) {
405                                 CustomData_free_layer(data, layer->type, 0, i);
406                                 ok= 0;
407                                 has_fixes= 1;
408                         }
409                 }
410
411                 if(ok)
412                         i++;
413         }
414
415         return has_fixes;
416 }
417
418 #undef PRINT
419
420 static int BKE_mesh_validate_all_customdata(CustomData *vdata, CustomData *edata, CustomData *fdata,
421                                             short do_verbose, const short do_fixes)
422 {
423         int vfixed= 0, efixed= 0, ffixed= 0;
424
425         vfixed= mesh_validate_customdata(vdata, do_verbose, do_fixes);
426         efixed= mesh_validate_customdata(edata, do_verbose, do_fixes);
427         ffixed= mesh_validate_customdata(fdata, do_verbose, do_fixes);
428
429         return vfixed || efixed || ffixed;
430 }
431
432 int BKE_mesh_validate(Mesh *me, int do_verbose)
433 {
434         int layers_fixed= 0, arrays_fixed= 0;
435
436         if(do_verbose) {
437                 printf("MESH: %s\n", me->id.name+2);
438         }
439
440         layers_fixed= BKE_mesh_validate_all_customdata(&me->vdata, &me->edata, &me->fdata, do_verbose, TRUE);
441         arrays_fixed= BKE_mesh_validate_arrays(me,
442                                                me->mvert, me->totvert,
443                                                me->medge, me->totedge,
444                                                me->mface, me->totface,
445                                                me->dvert,
446                                                do_verbose, TRUE);
447
448         return layers_fixed || arrays_fixed;
449 }
450
451 int BKE_mesh_validate_dm(DerivedMesh *dm)
452 {
453         return BKE_mesh_validate_arrays(NULL,
454                                     dm->getVertArray(dm), dm->getNumVerts(dm),
455                                     dm->getEdgeArray(dm), dm->getNumEdges(dm),
456                                     dm->getTessFaceArray(dm), dm->getNumTessFaces(dm),
457                                     dm->getVertDataArray(dm, CD_MDEFORMVERT),
458                                     TRUE, FALSE);
459 }
460
461 void BKE_mesh_calc_edges(Mesh *mesh, int update)
462 {
463         CustomData edata;
464         EdgeHashIterator *ehi;
465         MFace *mf = mesh->mface;
466         MEdge *med, *med_orig;
467         EdgeHash *eh = BLI_edgehash_new();
468         int i, totedge, totface = mesh->totface;
469         int med_index;
470
471         if(mesh->totedge==0)
472                 update= 0;
473
474         if(update) {
475                 /* assume existing edges are valid
476                  * useful when adding more faces and generating edges from them */
477                 med= mesh->medge;
478                 for(i= 0; i<mesh->totedge; i++, med++)
479                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
480         }
481
482         if(mesh->totpoly) {
483                 /* mesh loops (bmesh only) */
484                 MPoly *mp= mesh->mpoly;
485                 for(i=0; i < mesh->totpoly; i++, mp++) {
486                         MLoop *l= &mesh->mloop[mp->loopstart];
487                         int j, l_prev= (l + (mp->totloop-1))->v;
488                         for (j=0; j < mp->totloop; j++, l++) {
489                                 if (!BLI_edgehash_haskey(eh, l_prev, l->v)) {
490                                         BLI_edgehash_insert(eh, l_prev, l->v, NULL);
491                                 }
492                                 l_prev= l->v;
493                         }
494                 }
495         }
496         else {
497                 /* regular faces (note, we could remove this for bmesh - campbell) */
498                 for (i = 0; i < totface; i++, mf++) {
499                         if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
500                                 BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
501                         if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
502                                 BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
503
504                         if (mf->v4) {
505                                 if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
506                                         BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
507                                 if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
508                                         BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
509                         } else {
510                                 if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
511                                         BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
512                         }
513                 }
514         }
515
516         totedge = BLI_edgehash_size(eh);
517
518         /* write new edges into a temporary CustomData */
519         memset(&edata, 0, sizeof(edata));
520         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
521
522         ehi = BLI_edgehashIterator_new(eh);
523         med = CustomData_get_layer(&edata, CD_MEDGE);
524         for(i = 0; !BLI_edgehashIterator_isDone(ehi);
525                 BLI_edgehashIterator_step(ehi), ++i, ++med) {
526
527                 if(update && (med_orig=BLI_edgehashIterator_getValue(ehi))) {
528                         *med= *med_orig; /* copy from the original */
529                 } else {
530                         BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
531                         med->flag = ME_EDGEDRAW|ME_EDGERENDER|SELECT; /* select for newly created meshes which are selected [#25595] */
532                 }
533
534                 /* store the new edge index in the hash value */
535                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(i));
536         }
537         BLI_edgehashIterator_free(ehi);
538
539         if (mesh->totpoly) {
540                 /* second pass, iterate through all loops again and assign
541                    the newly created edges to them. */
542                 MPoly *mp= mesh->mpoly;
543                 for(i=0; i < mesh->totpoly; i++, mp++) {
544                         MLoop *l= &mesh->mloop[mp->loopstart];
545                         MLoop *l_prev= (l + (mp->totloop-1));
546                         int j;
547                         for (j=0; j < mp->totloop; j++, l++) {
548                                 /* lookup hashed edge index */
549                                 med_index = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
550                                 l_prev->e = med_index;
551                                 l_prev= l;
552                         }
553                 }
554         }
555
556         /* free old CustomData and assign new one */
557         CustomData_free(&mesh->edata, mesh->totedge);
558         mesh->edata = edata;
559         mesh->totedge = totedge;
560
561         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
562
563         BLI_edgehash_free(eh, NULL);
564 }