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