Merging r41246 through r41535 from trunk into soc-2011-tomato
[blender.git] / source / blender / blenkernel / intern / mesh_validate.c
index 35a23a17115afae7ddaccebb20bef0e64e4dc755..0dac4b8cd808c251cba3d0c45d73e94942ee3b59 100644 (file)
@@ -1,6 +1,4 @@
-/**
- * $Id$
- *
+/*
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
  * ***** END GPL LICENSE BLOCK *****
  */
 
+/** \file blender/blenkernel/intern/mesh_validate.c
+ *  \ingroup bke
+ */
+
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 #define SELECT 1
 
-typedef struct SortFace {
-       unsigned int v[4];
-       unsigned int index;
-} SortFace;
-
 typedef union {
        uint32_t verts[2];
        int64_t edval;
 } EdgeUUID;
 
+typedef struct SortFace {
+//     unsigned int    v[4];
+       EdgeUUID                es[4];
+       unsigned int    index;
+} SortFace;
+
 static void edge_store_assign(uint32_t verts[2],  const uint32_t v1, const uint32_t v2)
 {
        if(v1 < v2) {
@@ -66,24 +70,26 @@ static void edge_store_assign(uint32_t verts[2],  const uint32_t v1, const uint3
        }
 }
 
-static void edge_store_from_mface_quad(EdgeUUID es[3], MFace *mf)
+static void edge_store_from_mface_quad(EdgeUUID es[4], MFace *mf)
 {
        edge_store_assign(es[0].verts, mf->v1, mf->v2);
        edge_store_assign(es[1].verts, mf->v2, mf->v3);
        edge_store_assign(es[2].verts, mf->v3, mf->v4);
-       edge_store_assign(es[2].verts, mf->v4, mf->v1);
+       edge_store_assign(es[3].verts, mf->v4, mf->v1);
 }
 
-static void edge_store_from_mface_tri(EdgeUUID es[3], MFace *mf)
+static void edge_store_from_mface_tri(EdgeUUID es[4], MFace *mf)
 {
        edge_store_assign(es[0].verts, mf->v1, mf->v2);
        edge_store_assign(es[1].verts, mf->v2, mf->v3);
        edge_store_assign(es[2].verts, mf->v3, mf->v1);
+       es[3].verts[0] = es[3].verts[1] = UINT_MAX;
 }
 
-static int uint_cmp(const void *v1, const void *v2)
+static int int64_cmp(const void *v1, const void *v2)
 {
-       const unsigned int x1= GET_INT_FROM_POINTER(v1), x2= GET_INT_FROM_POINTER(v2);
+       const int64_t x1= *(const int64_t *)v1;
+       const int64_t x2= *(const int64_t *)v2;
 
        if( x1 > x2 ) return 1;
        else if( x1 < x2 ) return -1;
@@ -94,31 +100,33 @@ static int search_face_cmp(const void *v1, const void *v2)
 {
        const SortFace *sfa= v1, *sfb= v2;
 
-       if              (sfa->v[0] > sfb->v[0]) return 1;
-       else if (sfa->v[0] < sfb->v[0]) return -1;
+       if      (sfa->es[0].edval > sfb->es[0].edval) return 1;
+       else if (sfa->es[0].edval < sfb->es[0].edval) return -1;
 
-       if              (sfa->v[1] > sfb->v[1]) return 1;
-       else if (sfa->v[1] < sfb->v[1]) return -1;
+       else if (sfa->es[1].edval > sfb->es[1].edval) return 1;
+       else if (sfa->es[1].edval < sfb->es[1].edval) return -1;
 
-       if              (sfa->v[2] > sfb->v[2]) return 1;
-       else if (sfa->v[2] < sfb->v[2]) return -1;
+       else if (sfa->es[2].edval > sfb->es[2].edval) return 1;
+       else if (sfa->es[2].edval < sfb->es[2].edval) return -1;
 
-       if              (sfa->v[3] > sfb->v[3]) return 1;
-       else if (sfa->v[3] < sfb->v[3]) return -1;
+       else if (sfa->es[3].edval > sfb->es[3].edval) return 1;
+       else if (sfa->es[3].edval < sfb->es[3].edval) return -1;
+       else                                                                              return 0;
 
-       return 0;
 }
 
-int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge *medges, int totedge, MFace *mfaces, int totface, const short do_verbose, const short do_fixes)
+#define PRINT if(do_verbose) printf
+
+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)
 {
-#      define PRINT if(do_verbose) printf
 #      define REMOVE_EDGE_TAG(_med) { _med->v2= _med->v1; do_edge_free= 1; }
 #      define REMOVE_FACE_TAG(_mf) { _mf->v3=0; do_face_free= 1; }
 
 //     MVert *mv;
        MEdge *med;
        MFace *mf;
-       int i;
+       MFace *mf_prev;
+       unsigned int i;
 
        int do_face_free= FALSE;
        int do_edge_free= FALSE;
@@ -130,34 +138,34 @@ int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge
        SortFace *sort_faces= MEM_callocN(sizeof(SortFace) * totface, "search faces");
        SortFace *sf;
        SortFace *sf_prev;
-       int totsortface= 0;
+       unsigned int totsortface= 0;
 
        BLI_assert(!(do_fixes && me == NULL));
 
-       PRINT("ED_mesh_validate: verts(%d), edges(%d), faces(%d)\n", totvert, totedge, totface);
+       PRINT("%s: verts(%u), edges(%u), faces(%u)\n", __func__, totvert, totedge, totface);
 
        if(totedge == 0 && totface != 0) {
-               PRINT("    locical error, %d faces and 0 edges\n", totface);
+               PRINT("    locical error, %u faces and 0 edges\n", totface);
                do_edge_recalc= TRUE;
        }
 
        for(i=0, med= medges; i<totedge; i++, med++) {
                int remove= FALSE;
                if(med->v1 == med->v2) {
-                       PRINT("    edge %d: has matching verts, both %d\n", i, med->v1);
+                       PRINT("    edge %u: has matching verts, both %u\n", i, med->v1);
                        remove= do_fixes;
                }
                if(med->v1 >= totvert) {
-                       PRINT("    edge %d: v1 index out of range, %d\n", i, med->v1);
+                       PRINT("    edge %u: v1 index out of range, %u\n", i, med->v1);
                        remove= do_fixes;
                }
                if(med->v2 >= totvert) {
-                       PRINT("    edge %d: v2 index out of range, %d\n", i, med->v2);
+                       PRINT("    edge %u: v2 index out of range, %u\n", i, med->v2);
                        remove= do_fixes;
                }
 
                if(BLI_edgehash_haskey(edge_hash, med->v1, med->v2)) {
-                       PRINT("    edge %d: is a duplicate of, %d\n", i, GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, med->v1, med->v2)));
+                       PRINT("    edge %u: is a duplicate of, %d\n", i, GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, med->v1, med->v2)));
                        remove= do_fixes;
                }
 
@@ -172,57 +180,60 @@ int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge
        for(i=0, mf=mfaces, sf=sort_faces; i<totface; i++, mf++) {
                int remove= FALSE;
                int fidx;
+               unsigned int fv[4];
 
                fidx = mf->v4 ? 3:2;
                do {
-                       sf->v[fidx]= *(&mf->v1 + fidx);
-                       if(sf->v[fidx] >= totvert) {
-                               PRINT("    face %d: 'v%d' index out of range, %d\n", i, fidx + 1, sf->v[fidx]);
+                       fv[fidx]= *(&(mf->v1) + fidx);
+                       if(fv[fidx] >= totvert) {
+                               PRINT("    face %u: 'v%d' index out of range, %u\n", i, fidx + 1, fv[fidx]);
                                remove= do_fixes;
                        }
                } while (fidx--);
 
                if(remove == FALSE) {
                        if(mf->v4) {
-                               if(mf->v1 == mf->v2) { PRINT("    face %d: verts invalid, v1/v2 both %d\n", i, mf->v1); remove= do_fixes; }
-                               if(mf->v1 == mf->v3) { PRINT("    face %d: verts invalid, v1/v3 both %d\n", i, mf->v1); remove= do_fixes;  }
-                               if(mf->v1 == mf->v4) { PRINT("    face %d: verts invalid, v1/v4 both %d\n", i, mf->v1); remove= do_fixes;  }
+                               if(mf->v1 == mf->v2) { PRINT("    face %u: verts invalid, v1/v2 both %u\n", i, mf->v1); remove= do_fixes; }
+                               if(mf->v1 == mf->v3) { PRINT("    face %u: verts invalid, v1/v3 both %u\n", i, mf->v1); remove= do_fixes;  }
+                               if(mf->v1 == mf->v4) { PRINT("    face %u: verts invalid, v1/v4 both %u\n", i, mf->v1); remove= do_fixes;  }
 
-                               if(mf->v2 == mf->v3) { PRINT("    face %d: verts invalid, v2/v3 both %d\n", i, mf->v2); remove= do_fixes;  }
-                               if(mf->v2 == mf->v4) { PRINT("    face %d: verts invalid, v2/v4 both %d\n", i, mf->v2); remove= do_fixes;  }
+                               if(mf->v2 == mf->v3) { PRINT("    face %u: verts invalid, v2/v3 both %u\n", i, mf->v2); remove= do_fixes;  }
+                               if(mf->v2 == mf->v4) { PRINT("    face %u: verts invalid, v2/v4 both %u\n", i, mf->v2); remove= do_fixes;  }
 
-                               if(mf->v3 == mf->v4) { PRINT("    face %d: verts invalid, v3/v4 both %d\n", i, mf->v3); remove= do_fixes;  }
+                               if(mf->v3 == mf->v4) { PRINT("    face %u: verts invalid, v3/v4 both %u\n", i, mf->v3); remove= do_fixes;  }
                        }
                        else {
-                               if(mf->v1 == mf->v2) { PRINT("    faceT %d: verts invalid, v1/v2 both %d\n", i, mf->v1); remove= do_fixes; }
-                               if(mf->v1 == mf->v3) { PRINT("    faceT %d: verts invalid, v1/v3 both %d\n", i, mf->v1); remove= do_fixes; }
+                               if(mf->v1 == mf->v2) { PRINT("    faceT %u: verts invalid, v1/v2 both %u\n", i, mf->v1); remove= do_fixes; }
+                               if(mf->v1 == mf->v3) { PRINT("    faceT %u: verts invalid, v1/v3 both %u\n", i, mf->v1); remove= do_fixes; }
 
-                               if(mf->v2 == mf->v3) { PRINT("    faceT %d: verts invalid, v2/v3 both %d\n", i, mf->v2); remove= do_fixes; }
+                               if(mf->v2 == mf->v3) { PRINT("    faceT %u: verts invalid, v2/v3 both %u\n", i, mf->v2); remove= do_fixes; }
                        }
 
                        if(remove == FALSE) {
                                if(totedge) {
                                        if(mf->v4) {
-                                               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; }
-                                               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; }
-                                               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; }
-                                               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; }
+                                               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; }
+                                               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; }
+                                               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; }
+                                               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; }
                                        }
                                        else {
-                                               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; }
-                                               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; }
-                                               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; }
+                                               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; }
+                                               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; }
+                                               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; }
                                        }
                                }
 
-                               sort_faces[totsortface].index = i;
+                               sf->index = i;
 
                                if(mf->v4) {
-                                       qsort(sf->v, 4, sizeof(unsigned int), uint_cmp);
+                                       edge_store_from_mface_quad(sf->es, mf);
+
+                                       qsort(sf->es, 4, sizeof(int64_t), int64_cmp);
                                }
                                else {
-                                       qsort(sf->v, 3, sizeof(unsigned int), uint_cmp);
-                                       sf->v[3] = UINT_MAX;
+                                       edge_store_from_mface_tri(sf->es, mf);
+                                       qsort(sf->es, 3, sizeof(int64_t), int64_cmp);
                                }
 
                                totsortface++;
@@ -243,53 +254,28 @@ int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge
        for(i=1; i<totsortface; i++, sf++) {
                int remove= FALSE;
                /* on a valid mesh, code below will never run */
-               if(memcmp(sf->v, sf_prev->v, sizeof(sf_prev->v)) == 0) {
-                       /* slow, could be smarter here */
-                       MFace *mf= mfaces + sf->index;
-                       MFace *mf_prev= mfaces + sf_prev->index;
-
-                       EdgeUUID eu[4];
-                       EdgeUUID eu_prev[4];
+               if(memcmp(sf->es, sf_prev->es, sizeof(sf_prev->es)) == 0) {
+                       mf= mfaces + sf->index;
 
-                       if(mf->v4) {
-                               edge_store_from_mface_quad(eu, mf);
-                               edge_store_from_mface_quad(eu_prev, mf_prev);
-
-                               if(
-                                       ELEM4(eu[0].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval, eu_prev[3].edval) &&
-                                       ELEM4(eu[1].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval, eu_prev[3].edval) &&
-                                       ELEM4(eu[2].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval, eu_prev[3].edval) &&
-                                       ELEM4(eu[3].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval, eu_prev[3].edval)
-                               ) {
-                                       PRINT("    face %d & %d: are duplicates ", sf->index, sf_prev->index);
-                                       PRINT("(%d,%d,%d,%d) ", mf->v1, mf->v2, mf->v3, mf->v4);
-                                       PRINT("(%d,%d,%d,%d)\n", mf_prev->v1, mf_prev->v2, mf_prev->v3, mf_prev->v4);
-                                       remove= do_fixes;
+                       if(do_verbose) {
+                               mf_prev= mfaces + sf_prev->index;
+                               if(mf->v4) {
+                                       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);
                                }
-                       }
-                       else {
-                               edge_store_from_mface_tri(eu, mf);
-                               edge_store_from_mface_tri(eu_prev, mf);
-                               if(
-                                       ELEM3(eu[0].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval) &&
-                                       ELEM3(eu[1].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval) &&
-                                       ELEM3(eu[2].edval, eu_prev[0].edval, eu_prev[1].edval, eu_prev[2].edval)
-                               ) {
-                                       PRINT("    face %d & %d: are duplicates ", sf->index, sf_prev->index);
-                                       PRINT("(%d,%d,%d) ", mf->v1, mf->v2, mf->v3);
-                                       PRINT("(%d,%d,%d)\n", mf_prev->v1, mf_prev->v2, mf_prev->v3);
-                                       remove= do_fixes;
+                               else {
+                                       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);
                                }
                        }
-               }
 
-               if(remove) {
-                       REMOVE_FACE_TAG(mf);
-                       /* keep sf_prev incase next face also matches*/
+                       remove= do_fixes;
                }
                else {
                        sf_prev= sf;
                }
+
+               if(remove) {
+                       REMOVE_FACE_TAG(mf);
+               }
        }
 
        BLI_edgehash_free(edge_hash, NULL);
@@ -297,7 +283,6 @@ int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge
 
        PRINT("BKE_mesh_validate: finished\n\n");
 
-#       undef PRINT
 #       undef REMOVE_EDGE_TAG
 #       undef REMOVE_FACE_TAG
 
@@ -318,10 +303,57 @@ int BKE_mesh_validate_arrays(Mesh *me, MVert *UNUSED(mverts), int totvert, MEdge
        return (do_face_free || do_edge_free || do_edge_recalc);
 }
 
+static int mesh_validate_customdata(CustomData *data, short do_verbose, const short do_fixes)
+{
+       int i= 0, has_fixes= 0;
+
+       while(i<data->totlayer) {
+               CustomDataLayer *layer= &data->layers[i];
+               int mask= 1 << layer->type;
+               int ok= 1;
+
+               if((mask&CD_MASK_MESH)==0) {
+                       PRINT("CustomDataLayer type %d which isn't in CD_MASK_MESH is stored in Mehs structure\n", layer->type);
+
+                       if(do_fixes) {
+                               CustomData_free_layer(data, layer->type, 0, i);
+                               ok= 0;
+                               has_fixes= 1;
+                       }
+               }
+
+               if(ok)
+                       i++;
+       }
+
+       return has_fixes;
+}
+
+#undef PRINT
+
+int BKE_mesh_validate_all_customdata(CustomData *vdata, CustomData *edata, CustomData *fdata, short do_verbose, const short do_fixes)
+{
+       int vfixed= 0, efixed= 0, ffixed= 0;
+
+       vfixed= mesh_validate_customdata(vdata, do_verbose, do_fixes);
+       efixed= mesh_validate_customdata(edata, do_verbose, do_fixes);
+       ffixed= mesh_validate_customdata(fdata, do_verbose, do_fixes);
+
+       return vfixed || efixed || ffixed;
+}
+
 int BKE_mesh_validate(Mesh *me, int do_verbose)
 {
-       printf("MESH: %s\n", me->id.name+2);
-       return BKE_mesh_validate_arrays(me, me->mvert, me->totvert, me->medge, me->totedge, me->mface, me->totface, do_verbose, TRUE);
+       int layers_fixed= 0, arrays_fixed= 0;
+
+       if(do_verbose) {
+               printf("MESH: %s\n", me->id.name+2);
+       }
+
+       layers_fixed= BKE_mesh_validate_all_customdata(&me->vdata, &me->edata, &me->fdata, do_verbose, TRUE);
+       arrays_fixed= BKE_mesh_validate_arrays(me, me->mvert, me->totvert, me->medge, me->totedge, me->mface, me->totface, do_verbose, TRUE);
+
+       return layers_fixed || arrays_fixed;
 }
 
 int BKE_mesh_validate_dm(DerivedMesh *dm)