Patch #34204: [Render Animation] Fails with "Error: Specified sample_fmt is not suppo...
[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 #include "DNA_object_types.h"
37
38 #include "BLO_sys_types.h"
39
40 #include "BLI_edgehash.h"
41 #include "BLI_math_base.h"
42 #include "BLI_utildefines.h"
43
44 #include "BKE_deform.h"
45 #include "BKE_depsgraph.h"
46 #include "BKE_DerivedMesh.h"
47 #include "BKE_mesh.h"
48
49 #include "MEM_guardedalloc.h"
50
51 #define SELECT 1
52
53 typedef union {
54         uint32_t verts[2];
55         int64_t edval;
56 } EdgeUUID;
57
58 typedef struct SortFace {
59         EdgeUUID                es[4];
60         unsigned int    index;
61 } SortFace;
62
63 /* Used to detect polys (faces) using exactly the same vertices. */
64 /* Used to detect loops used by no (disjoint) or more than one (intersect) polys. */
65 typedef struct SortPoly {
66         int *verts;
67         int numverts;
68         int loopstart;
69         unsigned int index;
70         int invalid; /* Poly index. */
71 } SortPoly;
72
73 static void edge_store_assign(uint32_t verts[2],  const uint32_t v1, const uint32_t v2)
74 {
75         if (v1 < v2) {
76                 verts[0] = v1;
77                 verts[1] = v2;
78         }
79         else {
80                 verts[0] = v2;
81                 verts[1] = v1;
82         }
83 }
84
85 static void edge_store_from_mface_quad(EdgeUUID es[4], MFace *mf)
86 {
87         edge_store_assign(es[0].verts, mf->v1, mf->v2);
88         edge_store_assign(es[1].verts, mf->v2, mf->v3);
89         edge_store_assign(es[2].verts, mf->v3, mf->v4);
90         edge_store_assign(es[3].verts, mf->v4, mf->v1);
91 }
92
93 static void edge_store_from_mface_tri(EdgeUUID es[4], MFace *mf)
94 {
95         edge_store_assign(es[0].verts, mf->v1, mf->v2);
96         edge_store_assign(es[1].verts, mf->v2, mf->v3);
97         edge_store_assign(es[2].verts, mf->v3, mf->v1);
98         es[3].verts[0] = es[3].verts[1] = UINT_MAX;
99 }
100
101 static int int64_cmp(const void *v1, const void *v2)
102 {
103         const int64_t x1 = *(const int64_t *)v1;
104         const int64_t x2 = *(const int64_t *)v2;
105
106         if (x1 > x2) {
107                 return 1;
108         }
109         else if (x1 < x2) {
110                 return -1;
111         }
112
113         return 0;
114 }
115
116 static int search_face_cmp(const void *v1, const void *v2)
117 {
118         const SortFace *sfa = v1, *sfb = v2;
119
120         if (sfa->es[0].edval > sfb->es[0].edval) {
121                 return 1;
122         }
123         else if (sfa->es[0].edval < sfb->es[0].edval) {
124                 return -1;
125         }
126
127         else if (sfa->es[1].edval > sfb->es[1].edval) {
128                 return 1;
129         }
130         else if (sfa->es[1].edval < sfb->es[1].edval) {
131                 return -1;
132         }
133
134         else if (sfa->es[2].edval > sfb->es[2].edval) {
135                 return 1;
136         }
137         else if (sfa->es[2].edval < sfb->es[2].edval) {
138                 return -1;
139         }
140
141         else if (sfa->es[3].edval > sfb->es[3].edval) {
142                 return 1;
143         }
144         else if (sfa->es[3].edval < sfb->es[3].edval) {
145                 return -1;
146         }
147
148         return 0;
149 }
150
151 /* TODO check there is not some standard define of this somewhere! */
152 static int int_cmp(const void *v1, const void *v2)
153 {
154         return *(int *)v1 > *(int *)v2 ? 1 : *(int *)v1 < *(int *)v2 ? -1 : 0;
155 }
156
157 static int search_poly_cmp(const void *v1, const void *v2)
158 {
159         const SortPoly *sp1 = v1, *sp2 = v2;
160         const int max_idx = sp1->numverts > sp2->numverts ? sp2->numverts : sp1->numverts;
161         int idx = 0;
162
163         /* Reject all invalid polys at end of list! */
164         if (sp1->invalid || sp2->invalid)
165                 return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
166         /* Else, sort on first non-egal verts (remember verts of valid polys are sorted). */
167         while (idx < max_idx && sp1->verts[idx] == sp2->verts[idx])
168                 idx++;
169         return sp1->verts[idx] > sp2->verts[idx] ? 1 : sp1->verts[idx] < sp2->verts[idx] ? -1 :
170                sp1->numverts > sp2->numverts ? 1 : sp1->numverts < sp2->numverts ? -1 : 0;
171 }
172
173 static int search_polyloop_cmp(const void *v1, const void *v2)
174 {
175         const SortPoly *sp1 = v1, *sp2 = v2;
176
177         /* Reject all invalid polys at end of list! */
178         if (sp1->invalid || sp2->invalid)
179                 return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
180         /* Else, sort on loopstart. */
181         return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0;
182 }
183
184 #define PRINT if (do_verbose) printf
185
186 int BKE_mesh_validate_arrays(Mesh *mesh,
187                              MVert *mverts, unsigned int totvert,
188                              MEdge *medges, unsigned int totedge,
189                              MFace *mfaces, unsigned int totface,
190                              MLoop *mloops, unsigned int totloop,
191                              MPoly *mpolys, unsigned int totpoly,
192                              MDeformVert *dverts, /* assume totvert length */
193                              const short do_verbose, const short do_fixes)
194 {
195 #   define REMOVE_EDGE_TAG(_me) { _me->v2 = _me->v1; do_edge_free = TRUE; } (void)0
196 #   define IS_REMOVED_EDGE(_me) (_me->v2 == _me->v1)
197
198 #   define REMOVE_LOOP_TAG(_ml) { _ml->e = INVALID_LOOP_EDGE_MARKER; do_polyloop_free = TRUE; } (void)0
199 #   define REMOVE_POLY_TAG(_mp) { _mp->totloop *= -1; do_polyloop_free = TRUE; } (void)0
200
201         MVert *mv = mverts;
202         MEdge *me;
203         MLoop *ml;
204         MPoly *mp;
205         unsigned int i, j;
206         int *v;
207
208         short do_edge_free = FALSE;
209         short do_face_free = FALSE;
210         short do_polyloop_free = FALSE; /* This regroups loops and polys! */
211
212         short verts_fixed = FALSE;
213         short vert_weights_fixed = FALSE;
214         int msel_fixed = FALSE;
215
216         int do_edge_recalc = FALSE;
217
218         EdgeHash *edge_hash = BLI_edgehash_new();
219
220         BLI_assert(!(do_fixes && mesh == NULL));
221
222         PRINT("%s: verts(%u), edges(%u), loops(%u), polygons(%u)\n",
223               __func__, totvert, totedge, totloop, totpoly);
224
225         if (totedge == 0 && totpoly != 0) {
226                 PRINT("\tLogical error, %u polygons and 0 edges\n", totpoly);
227                 do_edge_recalc = do_fixes;
228         }
229
230         for (i = 1; i < totvert; i++, mv++) {
231                 int fix_normal = TRUE;
232
233                 for (j = 0; j < 3; j++) {
234                         if (!finite(mv->co[j])) {
235                                 PRINT("\tVertex %u: has invalid coordinate\n", i);
236
237                                 if (do_fixes) {
238                                         zero_v3(mv->co);
239
240                                         verts_fixed = TRUE;
241                                 }
242                         }
243
244                         if (mv->no[j] != 0)
245                                 fix_normal = FALSE;
246                 }
247
248                 if (fix_normal) {
249                         PRINT("\tVertex %u: has zero normal, assuming Z-up normal\n", i);
250                         if (do_fixes) {
251                                 mv->no[2] = SHRT_MAX;
252                                 verts_fixed = TRUE;
253                         }
254                 }
255         }
256
257         for (i = 0, me = medges; i < totedge; i++, me++) {
258                 int remove = FALSE;
259                 if (me->v1 == me->v2) {
260                         PRINT("\tEdge %u: has matching verts, both %u\n", i, me->v1);
261                         remove = do_fixes;
262                 }
263                 if (me->v1 >= totvert) {
264                         PRINT("\tEdge %u: v1 index out of range, %u\n", i, me->v1);
265                         remove = do_fixes;
266                 }
267                 if (me->v2 >= totvert) {
268                         PRINT("\tEdge %u: v2 index out of range, %u\n", i, me->v2);
269                         remove = do_fixes;
270                 }
271
272                 if (BLI_edgehash_haskey(edge_hash, me->v1, me->v2)) {
273                         PRINT("\tEdge %u: is a duplicate of %d\n", i,
274                               GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, me->v1, me->v2)));
275                         remove = do_fixes;
276                 }
277
278                 if (remove == FALSE) {
279                         BLI_edgehash_insert(edge_hash, me->v1, me->v2, SET_INT_IN_POINTER(i));
280                 }
281                 else {
282                         REMOVE_EDGE_TAG(me);
283                 }
284         }
285
286         if (mfaces && !mpolys) {
287 #               define REMOVE_FACE_TAG(_mf) { _mf->v3 = 0; do_face_free = TRUE; } (void)0
288 #               define CHECK_FACE_VERT_INDEX(a, b) \
289                                         if (mf->a == mf->b) { \
290                                                 PRINT("    face %u: verts invalid, " STRINGIFY(a) "/" STRINGIFY(b) " both %u\n", i, mf->a); \
291                                                 remove = do_fixes; \
292                                         } (void)0
293 #               define CHECK_FACE_EDGE(a, b) \
294                                         if (!BLI_edgehash_haskey(edge_hash, mf->a, mf->b)) { \
295                                                 PRINT("    face %u: edge " STRINGIFY(a) "/" STRINGIFY(b) \
296                                                       " (%u,%u) is missing egde data\n", i, mf->a, mf->b); \
297                                                 do_edge_recalc = TRUE; \
298                                         } (void)0
299
300                 MFace *mf;
301                 MFace *mf_prev;
302
303                 SortFace *sort_faces = MEM_callocN(sizeof(SortFace) * totface, "search faces");
304                 SortFace *sf;
305                 SortFace *sf_prev;
306                 unsigned int totsortface = 0;
307
308                 PRINT("No Polys, only tesselated Faces\n");
309
310                 for (i = 0, mf = mfaces, sf = sort_faces; i < totface; i++, mf++) {
311                         int remove = FALSE;
312                         int fidx;
313                         unsigned int fv[4];
314
315                         fidx = mf->v4 ? 3 : 2;
316                         do {
317                                 fv[fidx] = *(&(mf->v1) + fidx);
318                                 if (fv[fidx] >= totvert) {
319                                         PRINT("\tFace %u: 'v%d' index out of range, %u\n", i, fidx + 1, fv[fidx]);
320                                         remove = do_fixes;
321                                 }
322                         } while (fidx--);
323
324                         if (remove == FALSE) {
325                                 if (mf->v4) {
326                                         CHECK_FACE_VERT_INDEX(v1, v2);
327                                         CHECK_FACE_VERT_INDEX(v1, v3);
328                                         CHECK_FACE_VERT_INDEX(v1, v4);
329
330                                         CHECK_FACE_VERT_INDEX(v2, v3);
331                                         CHECK_FACE_VERT_INDEX(v2, v4);
332
333                                         CHECK_FACE_VERT_INDEX(v3, v4);
334                                 }
335                                 else {
336                                         CHECK_FACE_VERT_INDEX(v1, v2);
337                                         CHECK_FACE_VERT_INDEX(v1, v3);
338
339                                         CHECK_FACE_VERT_INDEX(v2, v3);
340                                 }
341
342                                 if (remove == FALSE) {
343                                         if (totedge) {
344                                                 if (mf->v4) {
345                                                         CHECK_FACE_EDGE(v1, v2);
346                                                         CHECK_FACE_EDGE(v2, v3);
347                                                         CHECK_FACE_EDGE(v3, v4);
348                                                         CHECK_FACE_EDGE(v4, v1);
349                                                 }
350                                                 else {
351                                                         CHECK_FACE_EDGE(v1, v2);
352                                                         CHECK_FACE_EDGE(v2, v3);
353                                                         CHECK_FACE_EDGE(v3, v1);
354                                                 }
355                                         }
356
357                                         sf->index = i;
358
359                                         if (mf->v4) {
360                                                 edge_store_from_mface_quad(sf->es, mf);
361
362                                                 qsort(sf->es, 4, sizeof(int64_t), int64_cmp);
363                                         }
364                                         else {
365                                                 edge_store_from_mface_tri(sf->es, mf);
366                                                 qsort(sf->es, 3, sizeof(int64_t), int64_cmp);
367                                         }
368
369                                         totsortface++;
370                                         sf++;
371                                 }
372                         }
373
374                         if (remove) {
375                                 REMOVE_FACE_TAG(mf);
376                         }
377                 }
378
379                 qsort(sort_faces, totsortface, sizeof(SortFace), search_face_cmp);
380
381                 sf = sort_faces;
382                 sf_prev = sf;
383                 sf++;
384
385                 for (i = 1; i < totsortface; i++, sf++) {
386                         int remove = FALSE;
387
388                         /* on a valid mesh, code below will never run */
389                         if (memcmp(sf->es, sf_prev->es, sizeof(sf_prev->es)) == 0) {
390                                 mf = mfaces + sf->index;
391
392                                 if (do_verbose) {
393                                         mf_prev = mfaces + sf_prev->index;
394
395                                         if (mf->v4) {
396                                                 PRINT("\tFace %u & %u: are duplicates (%u,%u,%u,%u) (%u,%u,%u,%u)\n",
397                                                       sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3, mf->v4,
398                                                       mf_prev->v1, mf_prev->v2, mf_prev->v3, mf_prev->v4);
399                                         }
400                                         else {
401                                                 PRINT("\tFace %u & %u: are duplicates (%u,%u,%u) (%u,%u,%u)\n",
402                                                       sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3,
403                                                       mf_prev->v1, mf_prev->v2, mf_prev->v3);
404                                         }
405                                 }
406
407                                 remove = do_fixes;
408                         }
409                         else {
410                                 sf_prev = sf;
411                         }
412
413                         if (remove) {
414                                 REMOVE_FACE_TAG(mf);
415                         }
416                 }
417
418                 MEM_freeN(sort_faces);
419
420 #               undef REMOVE_FACE_TAG
421 #               undef CHECK_FACE_VERT_INDEX
422 #               undef CHECK_FACE_EDGE
423         }
424
425         /* Checking loops and polys is a bit tricky, as they are quite intricated...
426          *
427          * Polys must have:
428          * - a valid loopstart value.
429          * - a valid totloop value (>= 3 and loopstart+totloop < me.totloop).
430          *
431          * Loops must have:
432          * - a valid v value.
433          * - a valid e value (corresponding to the edge it defines with the next loop in poly).
434          *
435          * Also, loops not used by polys can be discarded.
436          * And "intersecting" loops (i.e. loops used by more than one poly) are invalid,
437          * so be sure to leave at most one poly per loop!
438          */
439         {
440                 SortPoly *sort_polys = MEM_callocN(sizeof(SortPoly) * totpoly, "mesh validate's sort_polys");
441                 SortPoly *prev_sp, *sp = sort_polys;
442                 int prev_end;
443                 for (i = 0, mp = mpolys; i < totpoly; i++, mp++, sp++) {
444                         sp->index = i;
445
446                         if (mp->loopstart < 0 || mp->totloop < 3) {
447                                 /* Invalid loop data. */
448                                 PRINT("\tPoly %u is invalid (loopstart: %u, totloop: %u)\n", sp->index, mp->loopstart, mp->totloop);
449                                 sp->invalid = TRUE;
450                         }
451                         else if (mp->loopstart + mp->totloop > totloop) {
452                                 /* Invalid loop data. */
453                                 PRINT("\tPoly %u uses loops out of range (loopstart: %u, loopend: %u, max nbr of loops: %u)\n",
454                                       sp->index, mp->loopstart, mp->loopstart + mp->totloop - 1, totloop - 1);
455                                 sp->invalid = TRUE;
456                         }
457                         else {
458                                 /* Poly itself is valid, for now. */
459                                 int v1, v2; /* v1 is prev loop vert idx, v2 is current loop one. */
460                                 sp->invalid = FALSE;
461                                 sp->verts = v = MEM_mallocN(sizeof(int) * mp->totloop, "Vert idx of SortPoly");
462                                 sp->numverts = mp->totloop;
463                                 sp->loopstart = mp->loopstart;
464
465                                 /* Test all poly's loops' vert idx. */
466                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++, v++) {
467                                         if (ml->v >= totvert) {
468                                                 /* Invalid vert idx. */
469                                                 PRINT("\tLoop %u has invalid vert reference (%u)\n", sp->loopstart + j, ml->v);
470                                                 sp->invalid = TRUE;
471                                         }
472
473                                         mverts[ml->v].flag |= ME_VERT_TMP_TAG;
474                                         *v = ml->v;
475                                 }
476
477                                 /* is the same vertex used more then once */
478                                 if (!sp->invalid) {
479                                         v = sp->verts;
480                                         for (j = 0; j < mp->totloop; j++, v++) {
481                                                 if ((mverts[*v].flag & ME_VERT_TMP_TAG) == 0) {
482                                                         PRINT("\tPoly %u has duplicate vert reference at corner (%u)\n", i, j);
483                                                         sp->invalid = TRUE;
484                                                 }
485                                                 mverts[*v].flag &= ~ME_VERT_TMP_TAG;
486                                         }
487                                 }
488
489                                 if (sp->invalid)
490                                         continue;
491
492                                 /* Test all poly's loops. */
493                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++) {
494                                         v1 = ml->v;
495                                         v2 = mloops[sp->loopstart + (j + 1) % mp->totloop].v;
496                                         if (!BLI_edgehash_haskey(edge_hash, v1, v2)) {
497                                                 /* Edge not existing. */
498                                                 PRINT("\tPoly %u needs missing edge (%u, %u)\n", sp->index, v1, v2);
499                                                 if (do_fixes)
500                                                         do_edge_recalc = TRUE;
501                                                 else
502                                                         sp->invalid = TRUE;
503                                         }
504                                         else if (ml->e >= totedge) {
505                                                 /* Invalid edge idx.
506                                                  * We already know from previous text that a valid edge exists, use it (if allowed)! */
507                                                 if (do_fixes) {
508                                                         int prev_e = ml->e;
509                                                         ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
510                                                         PRINT("\tLoop %u has invalid edge reference (%u), fixed using edge %u\n",
511                                                               sp->loopstart + j, prev_e, ml->e);
512                                                 }
513                                                 else {
514                                                         PRINT("\tLoop %u has invalid edge reference (%u)\n", sp->loopstart + j, ml->e);
515                                                         sp->invalid = TRUE;
516                                                 }
517                                         }
518                                         else {
519                                                 me = &medges[ml->e];
520                                                 if (IS_REMOVED_EDGE(me) || !((me->v1 == v1 && me->v2 == v2) || (me->v1 == v2 && me->v2 == v1))) {
521                                                         /* The pointed edge is invalid (tagged as removed, or vert idx mismatch),
522                                                          * and we already know from previous test that a valid one exists, use it (if allowed)! */
523                                                         if (do_fixes) {
524                                                                 int prev_e = ml->e;
525                                                                 ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
526                                                                 PRINT("\tPoly %u has invalid edge reference (%u), fixed using edge %u\n",
527                                                                       sp->index, prev_e, ml->e);
528                                                         }
529                                                         else {
530                                                                 PRINT("\tPoly %u has invalid edge reference (%u)\n", sp->index, ml->e);
531                                                                 sp->invalid = TRUE;
532                                                         }
533                                                 }
534                                         }
535                                 }
536
537                                 /* Now check that that poly does not use a same vertex more than once! */
538                                 if (!sp->invalid) {
539                                         int *prev_v = v = sp->verts;
540                                         j = sp->numverts;
541
542                                         qsort(sp->verts, j, sizeof(int), int_cmp);
543
544                                         for (j--, v++; j; j--, v++) {
545                                                 if (*v != *prev_v) {
546                                                         int dlt = v - prev_v;
547                                                         if (dlt > 1) {
548                                                                 PRINT("\tPoly %u is invalid, it multi-uses vertex %u (%u times)\n",
549                                                                       sp->index, *prev_v, dlt);
550                                                                 sp->invalid = TRUE;
551                                                         }
552                                                         prev_v = v;
553                                                 }
554                                         }
555                                         if (v - prev_v > 1) { /* Don't forget final verts! */
556                                                 PRINT("\tPoly %u is invalid, it multi-uses vertex %u (%u times)\n",
557                                                       sp->index, *prev_v, (int)(v - prev_v));
558                                                 sp->invalid = TRUE;
559                                         }
560                                 }
561                         
562                         }
563                 }
564
565                 /* Second check pass, testing polys using the same verts. */
566                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_poly_cmp);
567                 sp = prev_sp = sort_polys;
568                 sp++;
569
570                 for (i = 1; i < totpoly; i++, sp++) {
571                         int p1_nv = sp->numverts, p2_nv = prev_sp->numverts;
572                         int *p1_v = sp->verts, *p2_v = prev_sp->verts;
573                         short p1_sub = TRUE, p2_sub = TRUE;
574                         if (sp->invalid)
575                                 break;
576                         /* Test same polys. */
577 #if 0
578                         /* NOTE: This performs a sub-set test. */
579                         /* XXX This (and the sort of verts list) is better than systematic
580                          *     search of all verts of one list into the other if lists have
581                          *     a fair amount of elements.
582                          *     Not sure however it's worth it in this case?
583                          *     But as we also need sorted vert list to check verts multi-used
584                          *     (in first pass of checks)... */
585                         /* XXX If we consider only "equal" polys (i.e. using exactly same set of verts)
586                          *     as invalid, better to replace this by a simple memory cmp... */
587                         while ((p1_nv && p2_nv) && (p1_sub || p2_sub)) {
588                                 if (*p1_v < *p2_v) {
589                                         if (p1_sub)
590                                                 p1_sub = FALSE;
591                                         p1_nv--;
592                                         p1_v++;
593                                 }
594                                 else if (*p2_v < *p1_v) {
595                                         if (p2_sub)
596                                                 p2_sub = FALSE;
597                                         p2_nv--;
598                                         p2_v++;
599                                 }
600                                 else {
601                                         /* Equality, both next verts. */
602                                         p1_nv--;
603                                         p2_nv--;
604                                         p1_v++;
605                                         p2_v++;
606                                 }
607                         }
608                         if (p1_nv && p1_sub)
609                                 p1_sub = FALSE;
610                         else if (p2_nv && p2_sub)
611                                 p2_sub = FALSE;
612
613                         if (p1_sub && p2_sub) {
614                                 PRINT("\tPolys %u and %u use same vertices, considering poly %u as invalid.\n",
615                                       prev_sp->index, sp->index, sp->index);
616                                 sp->invalid = TRUE;
617                         }
618                         /* XXX In fact, these might be valid? :/ */
619                         else if (p1_sub) {
620                                 PRINT("\t%u is a sub-poly of %u, considering it as invalid.\n", sp->index, prev_sp->index);
621                                 sp->invalid = TRUE;
622                         }
623                         else if (p2_sub) {
624                                 PRINT("\t%u is a sub-poly of %u, considering it as invalid.\n", prev_sp->index, sp->index);
625                                 prev_sp->invalid = TRUE;
626                                 prev_sp = sp; /* sp is new reference poly. */
627                         }
628 #else
629                         if (0) {
630                                 p1_sub += 0;
631                                 p2_sub += 0;
632                         }
633                         if ((p1_nv == p2_nv) && (memcmp(p1_v, p2_v, p1_nv * sizeof(*p1_v)) == 0)) {
634                                 if (do_verbose) {
635                                         PRINT("\tPolys %u and %u use same vertices (%u",
636                                               prev_sp->index, sp->index, *p1_v);
637                                         for (j = 1; j < p1_nv; j++)
638                                                 PRINT(", %u", p1_v[j]);
639                                         PRINT("), considering poly %u as invalid.\n", sp->index);
640                                 }
641                                 sp->invalid = TRUE;
642                         }
643 #endif
644                         else {
645                                 prev_sp = sp;
646                         }
647                 }
648
649                 /* Third check pass, testing loops used by none or more than one poly. */
650                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_polyloop_cmp);
651                 sp = sort_polys;
652                 prev_sp = NULL;
653                 prev_end = 0;
654                 for (i = 0; i < totpoly; i++, sp++) {
655                         /* Free this now, we don't need it anymore, and avoid us another loop! */
656                         if (sp->verts)
657                                 MEM_freeN(sp->verts);
658
659                         /* Note above prev_sp: in following code, we make sure it is always valid poly (or NULL). */
660                         if (sp->invalid) {
661                                 if (do_fixes) {
662                                         REMOVE_POLY_TAG((&mpolys[sp->index]));
663                                         /* DO NOT REMOVE ITS LOOPS!!!
664                                          * As already invalid polys are at the end of the SortPoly list, the loops they
665                                          * were the only users have already been tagged as "to remove" during previous
666                                          * iterations, and we don't want to remove some loops that may be used by
667                                          * another valid poly! */
668                                 }
669                         }
670                         /* Test loops users. */
671                         else {
672                                 /* Unused loops. */
673                                 if (prev_end < sp->loopstart) {
674                                         for (j = prev_end, ml = &mloops[prev_end]; j < sp->loopstart; j++, ml++) {
675                                                 PRINT("\tLoop %u is unused.\n", j);
676                                                 if (do_fixes)
677                                                         REMOVE_LOOP_TAG(ml);
678                                         }
679                                         prev_end = sp->loopstart + sp->numverts;
680                                         prev_sp = sp;
681                                 }
682                                 /* Multi-used loops. */
683                                 else if (prev_end > sp->loopstart) {
684                                         PRINT("\tPolys %u and %u share loops from %u to %u, considering poly %u as invalid.\n",
685                                               prev_sp->index, sp->index, sp->loopstart, prev_end, sp->index);
686                                         if (do_fixes) {
687                                                 REMOVE_POLY_TAG((&mpolys[sp->index]));
688                                                 /* DO NOT REMOVE ITS LOOPS!!!
689                                                  * They might be used by some next, valid poly!
690                                                  * Just not updating prev_end/prev_sp vars is enough to ensure the loops
691                                                  * effectively no more needed will be marked as "to be removed"! */
692                                         }
693                                 }
694                                 else {
695                                         prev_end = sp->loopstart + sp->numverts;
696                                         prev_sp = sp;
697                                 }
698                         }
699                 }
700                 /* We may have some remaining unused loops to get rid of! */
701                 if (prev_end < totloop) {
702                         for (j = prev_end, ml = &mloops[prev_end]; j < totloop; j++, ml++) {
703                                 PRINT("\tLoop %u is unused.\n", j);
704                                 if (do_fixes)
705                                         REMOVE_LOOP_TAG(ml);
706                         }
707                 }
708
709                 MEM_freeN(sort_polys);
710         }
711
712         BLI_edgehash_free(edge_hash, NULL);
713
714         /* fix deform verts */
715         if (dverts) {
716                 MDeformVert *dv;
717                 for (i = 0, dv = dverts; i < totvert; i++, dv++) {
718                         MDeformWeight *dw;
719
720                         for (j = 0, dw = dv->dw; j < dv->totweight; j++, dw++) {
721                                 /* note, greater then max defgroups is accounted for in our code, but not < 0 */
722                                 if (!finite(dw->weight)) {
723                                         PRINT("\tVertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
724                                         if (do_fixes) {
725                                                 dw->weight = 0.0f;
726                                                 vert_weights_fixed = TRUE;
727                                         }
728                                 }
729                                 else if (dw->weight < 0.0f || dw->weight > 1.0f) {
730                                         PRINT("\tVertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
731                                         if (do_fixes) {
732                                                 CLAMP(dw->weight, 0.0f, 1.0f);
733                                                 vert_weights_fixed = TRUE;
734                                         }
735                                 }
736
737                                 if (dw->def_nr < 0) {
738                                         PRINT("\tVertex deform %u, has invalid group %d\n", i, dw->def_nr);
739                                         if (do_fixes) {
740                                                 defvert_remove_group(dv, dw);
741                                                 if (dv->dw) {
742                                                         /* re-allocated, the new values compensate for stepping
743                                                          * within the for loop and may not be valid */
744                                                         j--;
745                                                         dw = dv->dw + j;
746
747                                                         vert_weights_fixed = TRUE;
748                                                 }
749                                                 else { /* all freed */
750                                                         break;
751                                                 }
752                                         }
753                                 }
754                         }
755                 }
756         }
757
758 #   undef REMOVE_EDGE_TAG
759 #   undef IS_REMOVED_EDGE
760 #   undef REMOVE_LOOP_TAG
761 #   undef REMOVE_POLY_TAG
762
763         if (mesh) {
764                 if (do_face_free) {
765                         BKE_mesh_strip_loose_faces(mesh);
766                 }
767
768                 if (do_polyloop_free) {
769                         BKE_mesh_strip_loose_polysloops(mesh);
770                 }
771
772                 if (do_edge_free) {
773                         BKE_mesh_strip_loose_edges(mesh);
774                 }
775
776                 if (do_edge_recalc) {
777                         BKE_mesh_calc_edges(mesh, TRUE);
778                 }
779         }
780
781         if (mesh && mesh->mselect) {
782                 MSelect *msel;
783                 int free_msel = FALSE;
784
785                 for (i = 0, msel = mesh->mselect; i < mesh->totselect; i++, msel++) {
786                         int tot_elem = 0;
787
788                         if (msel->index < 0) {
789                                 PRINT("\tMesh select element %d type %d index is negative, "
790                                       "resetting selection stack.\n", i, msel->type);
791                                 free_msel = TRUE;
792                                 break;
793                         }
794
795                         switch (msel->type) {
796                                 case ME_VSEL:
797                                         tot_elem = mesh->totvert;
798                                         break;
799                                 case ME_ESEL:
800                                         tot_elem = mesh->totedge;
801                                         break;
802                                 case ME_FSEL:
803                                         tot_elem = mesh->totface;
804                                         break;
805                         }
806
807                         if (msel->index > tot_elem) {
808                                 PRINT("\tMesh select element %d type %d index %d is larger than data array size %d, "
809                                       "resetting selection stack.\n", i, msel->type, msel->index, tot_elem);
810
811                                 free_msel = TRUE;
812                                 break;
813                         }
814                 }
815
816                 if (free_msel) {
817                         MEM_freeN(mesh->mselect);
818                         mesh->mselect = NULL;
819                         mesh->totselect = 0;
820                 }
821         }
822
823         PRINT("%s: finished\n\n", __func__);
824
825         return (verts_fixed || vert_weights_fixed || do_polyloop_free || do_edge_free || do_edge_recalc || msel_fixed);
826 }
827
828 static int mesh_validate_customdata(CustomData *data, short do_verbose, const short do_fixes)
829 {
830         int i = 0, has_fixes = 0;
831
832         PRINT("%s: Checking %d CD layers...\n", __func__, data->totlayer);
833
834         while (i < data->totlayer) {
835                 CustomDataLayer *layer = &data->layers[i];
836                 CustomDataMask mask = CD_TYPE_AS_MASK(layer->type);
837                 int ok = 1;
838
839                 if ((mask & CD_MASK_MESH) == 0) {
840                         PRINT("\tCustomDataLayer type %d which isn't in CD_MASK_MESH is stored in Mesh structure\n", layer->type);
841
842                         if (do_fixes) {
843                                 CustomData_free_layer(data, layer->type, 0, i);
844                                 ok = 0;
845                                 has_fixes = 1;
846                         }
847                 }
848
849                 if (ok)
850                         i++;
851         }
852
853         PRINT("%s: Finished\n\n", __func__);
854
855         return has_fixes;
856 }
857
858 #undef PRINT
859
860 static int BKE_mesh_validate_all_customdata(CustomData *vdata, CustomData *edata,
861                                             CustomData *ldata, CustomData *pdata,
862                                             short do_verbose, const short do_fixes)
863 {
864         int vfixed = 0, efixed = 0, lfixed = 0, pfixed = 0;
865
866         vfixed = mesh_validate_customdata(vdata, do_verbose, do_fixes);
867         efixed = mesh_validate_customdata(edata, do_verbose, do_fixes);
868         lfixed = mesh_validate_customdata(ldata, do_verbose, do_fixes);
869         pfixed = mesh_validate_customdata(pdata, do_verbose, do_fixes);
870
871         return vfixed || efixed || lfixed || pfixed;
872 }
873
874 int BKE_mesh_validate(Mesh *me, int do_verbose)
875 {
876         int layers_fixed = 0, arrays_fixed = 0;
877
878         if (do_verbose) {
879                 printf("MESH: %s\n", me->id.name + 2);
880         }
881
882         layers_fixed = BKE_mesh_validate_all_customdata(&me->vdata, &me->edata, &me->ldata, &me->pdata, do_verbose, TRUE);
883         arrays_fixed = BKE_mesh_validate_arrays(me,
884                                                 me->mvert, me->totvert,
885                                                 me->medge, me->totedge,
886                                                 me->mface, me->totface,
887                                                 me->mloop, me->totloop,
888                                                 me->mpoly, me->totpoly,
889                                                 me->dvert,
890                                                 do_verbose, TRUE);
891
892         if (layers_fixed || arrays_fixed) {
893                 DAG_id_tag_update(&me->id, OB_RECALC_DATA);
894                 return TRUE;
895         }
896         return FALSE;
897 }
898
899 int BKE_mesh_validate_dm(DerivedMesh *dm)
900 {
901         return BKE_mesh_validate_arrays(NULL,
902                                         dm->getVertArray(dm), dm->getNumVerts(dm),
903                                         dm->getEdgeArray(dm), dm->getNumEdges(dm),
904                                         dm->getTessFaceArray(dm), dm->getNumTessFaces(dm),
905                                         dm->getLoopArray(dm), dm->getNumLoops(dm),
906                                         dm->getPolyArray(dm), dm->getNumPolys(dm),
907                                         dm->getVertDataArray(dm, CD_MDEFORMVERT),
908                                         TRUE, FALSE);
909 }
910
911 /**
912  * Calculate edges from polygons
913  *
914  * \param mesh  The mesh to add edges into
915  * \param update  When true create new edges co-exist
916  */
917 void BKE_mesh_calc_edges(Mesh *mesh, int update)
918 {
919         CustomData edata;
920         EdgeHashIterator *ehi;
921         MPoly *mp;
922         MEdge *med, *med_orig;
923         EdgeHash *eh = BLI_edgehash_new();
924         int i, totedge, totpoly = mesh->totpoly;
925         int med_index;
926
927         if (mesh->totedge == 0)
928                 update = FALSE;
929
930         if (update) {
931                 /* assume existing edges are valid
932                  * useful when adding more faces and generating edges from them */
933                 med = mesh->medge;
934                 for (i = 0; i < mesh->totedge; i++, med++)
935                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
936         }
937
938         /* mesh loops (bmesh only) */
939         for (mp = mesh->mpoly, i = 0; i < totpoly; mp++, i++) {
940                 MLoop *l = &mesh->mloop[mp->loopstart];
941                 int j, l_prev = (l + (mp->totloop - 1))->v;
942                 for (j = 0; j < mp->totloop; j++, l++) {
943                         if (!BLI_edgehash_haskey(eh, l_prev, l->v)) {
944                                 BLI_edgehash_insert(eh, l_prev, l->v, NULL);
945                         }
946                         l_prev = l->v;
947                 }
948         }
949
950         totedge = BLI_edgehash_size(eh);
951
952         /* write new edges into a temporary CustomData */
953         CustomData_reset(&edata);
954         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
955
956         med = CustomData_get_layer(&edata, CD_MEDGE);
957         for (ehi = BLI_edgehashIterator_new(eh), i = 0;
958              BLI_edgehashIterator_isDone(ehi) == FALSE;
959              BLI_edgehashIterator_step(ehi), ++i, ++med)
960         {
961                 if (update && (med_orig = BLI_edgehashIterator_getValue(ehi))) {
962                         *med = *med_orig; /* copy from the original */
963                 }
964                 else {
965                         BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
966                         med->flag = ME_EDGEDRAW | ME_EDGERENDER | SELECT; /* select for newly created meshes which are selected [#25595] */
967                 }
968
969                 /* store the new edge index in the hash value */
970                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(i));
971         }
972         BLI_edgehashIterator_free(ehi);
973
974         if (mesh->totpoly) {
975                 /* second pass, iterate through all loops again and assign
976                  * the newly created edges to them. */
977                 for (mp = mesh->mpoly, i = 0; i < mesh->totpoly; mp++, i++) {
978                         MLoop *l = &mesh->mloop[mp->loopstart];
979                         MLoop *l_prev = (l + (mp->totloop - 1));
980                         int j;
981                         for (j = 0; j < mp->totloop; j++, l++) {
982                                 /* lookup hashed edge index */
983                                 med_index = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
984                                 l_prev->e = med_index;
985                                 l_prev = l;
986                         }
987                 }
988         }
989
990         /* free old CustomData and assign new one */
991         CustomData_free(&mesh->edata, mesh->totedge);
992         mesh->edata = edata;
993         mesh->totedge = totedge;
994
995         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
996
997         BLI_edgehash_free(eh, NULL);
998 }