svn merge ^/trunk/blender -r47067:47070
[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 /* Used to detect polys (faces) using exactly the same vertices. */
54 /* Used to detect loops used by no (disjoint) or more than one (intersect) polys. */
55 typedef struct SortPoly {
56         int *verts;
57         int numverts;
58         int loopstart;
59         unsigned int index;
60         int invalid; /* Poly index. */
61 } SortPoly;
62
63 /* TODO check there is not some standard define of this somewhere! */
64 static int int_cmp(const void *v1, const void *v2)
65 {
66         return *(int *)v1 > *(int *)v2 ? 1 : *(int *)v1 < *(int *)v2 ? -1 : 0;
67 }
68
69 static int search_poly_cmp(const void *v1, const void *v2)
70 {
71         const SortPoly *sp1 = v1, *sp2 = v2;
72         const int max_idx = sp1->numverts > sp2->numverts ? sp2->numverts : sp1->numverts;
73         int idx = 0;
74
75         /* Reject all invalid polys at end of list! */
76         if (sp1->invalid || sp2->invalid)
77                 return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
78         /* Else, sort on first non-egal verts (remember verts of valid polys are sorted). */
79         while (idx < max_idx && sp1->verts[idx] == sp2->verts[idx])
80                 idx++;
81         return sp1->verts[idx] > sp2->verts[idx] ? 1 : sp1->verts[idx] < sp2->verts[idx] ? -1 :
82                sp1->numverts > sp2->numverts ? 1 : sp1->numverts < sp2->numverts ? -1 : 0;
83 }
84
85 static int search_polyloop_cmp(const void *v1, const void *v2)
86 {
87         const SortPoly *sp1 = v1, *sp2 = v2;
88
89         /* Reject all invalid polys at end of list! */
90         if (sp1->invalid || sp2->invalid)
91                 return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
92         /* Else, sort on loopstart. */
93         return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0;
94 }
95
96 #define PRINT if (do_verbose) printf
97
98 int BKE_mesh_validate_arrays(Mesh *mesh,
99                              MVert *mverts, unsigned int totvert,
100                              MEdge *medges, unsigned int totedge,
101                              MLoop *mloops, unsigned int totloop,
102                              MPoly *mpolys, unsigned int totpoly,
103                              MDeformVert *dverts, /* assume totvert length */
104                              const short do_verbose, const short do_fixes)
105 {
106 #   define REMOVE_EDGE_TAG(_me) { _me->v2 = _me->v1; do_edge_free = TRUE; } (void)0
107 #   define IS_REMOVED_EDGE(_me) (_me->v2 == _me->v1)
108
109 #   define REMOVE_LOOP_TAG(_ml) { _ml->e = INVALID_LOOP_EDGE_MARKER; do_polyloop_free = TRUE; } (void)0
110 #   define REMOVE_POLY_TAG(_mp) { _mp->totloop *= -1; do_polyloop_free = TRUE; } (void)0
111
112         MVert *mv = mverts;
113         MEdge *me;
114         MLoop *ml;
115         MPoly *mp;
116         unsigned int i, j;
117         int *v;
118
119         short do_edge_free = FALSE;
120         short do_polyloop_free = FALSE; /* This regroups loops and polys! */
121
122         short verts_fixed = FALSE;
123         short vert_weights_fixed = FALSE;
124
125         int do_edge_recalc = FALSE;
126
127         EdgeHash *edge_hash = BLI_edgehash_new();
128
129         BLI_assert(!(do_fixes && mesh == NULL));
130
131         PRINT("%s: verts(%u), edges(%u), loops(%u), polygons(%u)\n",
132               __func__, totvert, totedge, totloop, totpoly);
133
134         if (totedge == 0 && totpoly != 0) {
135                 PRINT("    logical error, %u polygons and 0 edges\n", totpoly);
136                 do_edge_recalc = do_fixes;
137         }
138
139         for (i = 1; i < totvert; i++, mv++) {
140                 int j;
141                 int fix_normal = TRUE;
142
143                 for (j = 0; j < 3; j++) {
144                         if (!finite(mv->co[j])) {
145                                 PRINT("    vertex %u: has invalid coordinate\n", i);
146
147                                 if (do_fixes) {
148                                         zero_v3(mv->co);
149
150                                         verts_fixed = TRUE;
151                                 }
152                         }
153
154                         if (mv->no[j] != 0)
155                                 fix_normal = FALSE;
156                 }
157
158                 if (fix_normal) {
159                         PRINT("    vertex %u: has zero normal, assuming Z-up normal\n", i);
160                         if (do_fixes) {
161                                 mv->no[2] = SHRT_MAX;
162                                 verts_fixed = TRUE;
163                         }
164                 }
165         }
166
167         for (i = 0, me = medges; i < totedge; i++, me++) {
168                 int remove = FALSE;
169                 if (me->v1 == me->v2) {
170                         PRINT("    edge %u: has matching verts, both %u\n", i, me->v1);
171                         remove = do_fixes;
172                 }
173                 if (me->v1 >= totvert) {
174                         PRINT("    edge %u: v1 index out of range, %u\n", i, me->v1);
175                         remove = do_fixes;
176                 }
177                 if (me->v2 >= totvert) {
178                         PRINT("    edge %u: v2 index out of range, %u\n", i, me->v2);
179                         remove = do_fixes;
180                 }
181
182                 if (BLI_edgehash_haskey(edge_hash, me->v1, me->v2)) {
183                         PRINT("    edge %u: is a duplicate of %d\n", i,
184                               GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, me->v1, me->v2)));
185                         remove = do_fixes;
186                 }
187
188                 if (remove == FALSE) {
189                         BLI_edgehash_insert(edge_hash, me->v1, me->v2, SET_INT_IN_POINTER(i));
190                 }
191                 else {
192                         REMOVE_EDGE_TAG(me);
193                 }
194         }
195
196         /* Checking loops and polys is a bit tricky, as they are quite intricated...
197          *
198          * Polys must have:
199          * - a valid loopstart value.
200          * - a valid totloop value (>= 3 and loopstart+totloop < me.totloop).
201          *
202          * Loops must have:
203          * - a valid v value.
204          * - a valid e value (corresponding to the edge it defines with the next loop in poly).
205          *
206          * Also, loops not used by polys can be discarded.
207          * And "intersecting" loops (i.e. loops used by more than one poly) are invalid,
208          * so be sure to leave at most one poly/loop!
209          */
210         {
211                 SortPoly *sort_polys = MEM_callocN(sizeof(SortPoly) * totpoly, "mesh validate's sort_polys");
212                 SortPoly *prev_sp, *sp = sort_polys;
213                 int prev_end;
214                 for (i = 0, mp = mpolys; i < totpoly; i++, mp++, sp++) {
215                         sp->index = i;
216
217                         if (mp->loopstart < 0 || mp->totloop < 3) {
218                                 /* Invalid loop data. */
219                                 PRINT("    poly %u is invalid (loopstart: %u, totloop: %u)\n", sp->index, mp->loopstart, mp->totloop);
220                                 sp->invalid = TRUE;
221                         }
222                         else if (mp->loopstart + mp->totloop > totloop) {
223                                 /* Invalid loop data. */
224                                 PRINT("    poly %u uses loops out of range (loopstart: %u, loopend: %u, max nbr of loops: %u)\n",
225                                       sp->index, mp->loopstart, mp->loopstart + mp->totloop - 1, totloop - 1);
226                                 sp->invalid = TRUE;
227                         }
228                         else {
229                                 /* Poly itself is valid, for now. */
230                                 int v1, v2; /* v1 is prev loop vert idx, v2 is current loop one. */
231                                 sp->invalid = FALSE;
232                                 sp->verts = v = MEM_mallocN(sizeof(int) * mp->totloop, "Vert idx of SortPoly");
233                                 sp->numverts = mp->totloop;
234                                 sp->loopstart = mp->loopstart;
235
236                                 /* Test all poly's loops' vert idx. */
237                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++, v++) {
238                                         if (ml->v >= totvert) {
239                                                 /* Invalid vert idx. */
240                                                 PRINT("    loop %u has invalid vert reference (%u)\n", sp->loopstart + j, ml->v);
241                                                 sp->invalid = TRUE;
242                                         }
243
244                                         mverts[ml->v].flag |= ME_VERT_TMP_TAG;
245                                         *v = ml->v;
246                                 }
247
248                                 /* is the same vertex used more then once */
249                                 if (!sp->invalid) {
250                                         v = sp->verts;
251                                         for (j = 0; j < mp->totloop; j++, v++) {
252                                                 if ((mverts[*v].flag & ME_VERT_TMP_TAG) == 0) {
253                                                         PRINT("    poly %u has duplicate vert reference at corner (%u)\n", i, j);
254                                                         sp->invalid = TRUE;
255                                                 }
256                                                 mverts[*v].flag &= ~ME_VERT_TMP_TAG;
257                                         }
258                                 }
259
260                                 if (sp->invalid)
261                                         continue;
262
263                                 /* Test all poly's loops. */
264                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++) {
265                                         v1 = ml->v;
266                                         v2 = mloops[sp->loopstart + (j + 1) % mp->totloop].v;
267                                         if (!BLI_edgehash_haskey(edge_hash, v1, v2)) {
268                                                 /* Edge not existing. */
269                                                 PRINT("    poly %u needs missing edge (%u, %u)\n", sp->index, v1, v2);
270                                                 if (do_fixes)
271                                                         do_edge_recalc = TRUE;
272                                                 else
273                                                         sp->invalid = TRUE;
274                                         }
275                                         else if (ml->e >= totedge) {
276                                                 /* Invalid edge idx.
277                                                  * We already know from previous text that a valid edge exists, use it (if allowed)! */
278                                                 if (do_fixes) {
279                                                         int prev_e = ml->e;
280                                                         ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
281                                                         PRINT("    loop %u has invalid edge reference (%u), fixed using edge %u\n",
282                                                               sp->loopstart + j, prev_e, ml->e);
283                                                 }
284                                                 else {
285                                                         PRINT("    loop %u has invalid edge reference (%u)\n", sp->loopstart + j, ml->e);
286                                                         sp->invalid = TRUE;
287                                                 }
288                                         }
289                                         else {
290                                                 me = &medges[ml->e];
291                                                 if (IS_REMOVED_EDGE(me) || !((me->v1 == v1 && me->v2 == v2) || (me->v1 == v2 && me->v2 == v1))) {
292                                                         /* The pointed edge is invalid (tagged as removed, or vert idx mismatch),
293                                                          * and we already know from previous test that a valid one exists, use it (if allowed)! */
294                                                         if (do_fixes) {
295                                                                 int prev_e = ml->e;
296                                                                 ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
297                                                                 PRINT("    poly %u has invalid edge reference (%u), fixed using edge %u\n",
298                                                                       sp->index, prev_e, ml->e);
299                                                         }
300                                                         else {
301                                                                 PRINT("    poly %u has invalid edge reference (%u)\n", sp->index, ml->e);
302                                                                 sp->invalid = TRUE;
303                                                         }
304                                                 }
305                                         }
306                                 }
307
308                                 /* Now check that that poly does not use a same vertex more than once! */
309                                 if (!sp->invalid) {
310                                         int *prev_v = v = sp->verts;
311                                         j = sp->numverts;
312
313                                         qsort(sp->verts, j, sizeof(int), int_cmp);
314
315                                         for (j--, v++; j; j--, v++) {
316                                                 if (*v != *prev_v) {
317                                                         int dlt = v - prev_v;
318                                                         if (dlt > 1) {
319                                                                 PRINT("    poly %u is invalid, it multi-uses vertex %u (%u times)\n",
320                                                                       sp->index, *prev_v, dlt);
321                                                                 sp->invalid = TRUE;
322                                                         }
323                                                         prev_v = v;
324                                                 }
325                                         }
326                                         if (v - prev_v > 1) { /* Don't forget final verts! */
327                                                 PRINT("    poly %u is invalid, it multi-uses vertex %u (%u times)\n",
328                                                       sp->index, *prev_v, (int)(v - prev_v));
329                                                 sp->invalid = TRUE;
330                                         }
331                                 }
332                         
333                         }
334                 }
335
336                 /* Second check pass, testing polys using the same verts. */
337                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_poly_cmp);
338                 sp = prev_sp = sort_polys;
339                 sp++;
340
341                 for (i = 1; i < totpoly; i++, sp++) {
342                         int p1_nv = sp->numverts, p2_nv = prev_sp->numverts;
343                         int *p1_v = sp->verts, *p2_v = prev_sp->verts;
344                         short p1_sub = TRUE, p2_sub = TRUE;
345                         if (sp->invalid)
346                                 break;
347                         /* Test same polys. */
348 #if 0
349                         /* NOTE: This performs a sub-set test. */
350                         /* XXX This (and the sort of verts list) is better than systematic
351                          *     search of all verts of one list into the other if lists have
352                          *     a fair amount of elements.
353                          *     Not sure however it's worth it in this case?
354                          *     But as we also need sorted vert list to check verts multi-used
355                          *     (in first pass of checks)... */
356                         /* XXX If we consider only "equal" polys (i.e. using exactly same set of verts)
357                          *     as invalid, better to replace this by a simple memory cmp... */
358                         while ((p1_nv && p2_nv) && (p1_sub || p2_sub)) {
359                                 if (*p1_v < *p2_v) {
360                                         if (p1_sub)
361                                                 p1_sub = FALSE;
362                                         p1_nv--;
363                                         p1_v++;
364                                 }
365                                 else if (*p2_v < *p1_v) {
366                                         if (p2_sub)
367                                                 p2_sub = FALSE;
368                                         p2_nv--;
369                                         p2_v++;
370                                 }
371                                 else {
372                                         /* Equality, both next verts. */
373                                         p1_nv--;
374                                         p2_nv--;
375                                         p1_v++;
376                                         p2_v++;
377                                 }
378                         }
379                         if (p1_nv && p1_sub)
380                                 p1_sub = FALSE;
381                         else if (p2_nv && p2_sub)
382                                 p2_sub = FALSE;
383
384                         if (p1_sub && p2_sub) {
385                                 PRINT("    polys %u and %u use same vertices, considering poly %u as invalid.\n",
386                                       prev_sp->index, sp->index, sp->index);
387                                 sp->invalid = TRUE;
388                         }
389                         /* XXX In fact, these might be valid? :/ */
390                         else if (p1_sub) {
391                                 PRINT("    %u is a sub-poly of %u, considering it as invalid.\n", sp->index, prev_sp->index);
392                                 sp->invalid = TRUE;
393                         }
394                         else if (p2_sub) {
395                                 PRINT("    %u is a sub-poly of %u, considering it as invalid.\n", prev_sp->index, sp->index);
396                                 prev_sp->invalid = TRUE;
397                                 prev_sp = sp; /* sp is new reference poly. */
398                         }
399 #else
400                         if (0) {
401                                 p1_sub += 0;
402                                 p2_sub += 0;
403                         }
404                         if ((p1_nv == p2_nv) && (memcmp(p1_v, p2_v, p1_nv * sizeof(*p1_v)) == 0)) {
405                                 if (do_verbose) {
406                                         PRINT("    polys %u and %u use same vertices (%u",
407                                               prev_sp->index, sp->index, *p1_v);
408                                         for (j = 1; j < p1_nv; j++)
409                                                 PRINT(", %u", p1_v[j]);
410                                         PRINT("), considering poly %u as invalid.\n", sp->index);
411                                 }
412                                 sp->invalid = TRUE;
413                         }
414 #endif
415                         else {
416                                 prev_sp = sp;
417                         }
418                 }
419
420                 /* Third check pass, testing loops used by none or more than one poly. */
421                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_polyloop_cmp);
422                 sp = sort_polys;
423                 prev_sp = NULL;
424                 prev_end = 0;
425                 for (i = 0; i < totpoly; i++, sp++) {
426                         /* Free this now, we don't need it anymore, and avoid us another loop! */
427                         if (sp->verts)
428                                 MEM_freeN(sp->verts);
429
430                         /* Note above prev_sp: in following code, we make sure it is always valid poly (or NULL). */
431                         if (sp->invalid) {
432                                 if (do_fixes) {
433                                         REMOVE_POLY_TAG((&mpolys[sp->index]));
434                                         /* DO NOT REMOVE ITS LOOPS!!!
435                                          * As already invalid polys are at the end of the SortPoly list, the loops they
436                                          * were the only users have already been tagged as "to remove" during previous
437                                          * iterations, and we don't want to remove some loops that may be used by
438                                          * another valid poly! */
439                                 }
440                         }
441                         /* Test loops users. */
442                         else {
443                                 /* Unused loops. */
444                                 if (prev_end < sp->loopstart) {
445                                         for (j = prev_end, ml = &mloops[prev_end]; j < sp->loopstart; j++, ml++) {
446                                                 PRINT("    loop %u is unused.\n", j);
447                                                 if (do_fixes)
448                                                         REMOVE_LOOP_TAG(ml);
449                                         }
450                                         prev_end = sp->loopstart + sp->numverts;
451                                         prev_sp = sp;
452                                 }
453                                 /* Multi-used loops. */
454                                 else if (prev_end > sp->loopstart) {
455                                         PRINT("    polys %u and %u share loops from %u to %u, considering poly %u as invalid.\n",
456                                               prev_sp->index, sp->index, sp->loopstart, prev_end, sp->index);
457                                         if (do_fixes) {
458                                                 REMOVE_POLY_TAG((&mpolys[sp->index]));
459                                                 /* DO NOT REMOVE ITS LOOPS!!!
460                                                  * They might be used by some next, valid poly!
461                                                  * Just not updating prev_end/prev_sp vars is enough to ensure the loops
462                                                  * effectively no more needed will be marked as "to be removed"! */
463                                         }
464                                 }
465                                 else {
466                                         prev_end = sp->loopstart + sp->numverts;
467                                         prev_sp = sp;
468                                 }
469                         }
470                 }
471                 /* We may have some remaining unused loops to get rid of! */
472                 if (prev_end < totloop) {
473                         for (j = prev_end, ml = &mloops[prev_end]; j < totloop; j++, ml++) {
474                                 PRINT("    loop %u is unused.\n", j);
475                                 if (do_fixes)
476                                         REMOVE_LOOP_TAG(ml);
477                         }
478                 }
479
480                 MEM_freeN(sort_polys);
481         }
482
483         BLI_edgehash_free(edge_hash, NULL);
484
485         /* fix deform verts */
486         if (dverts) {
487                 MDeformVert *dv;
488                 for (i = 0, dv = dverts; i < totvert; i++, dv++) {
489                         MDeformWeight *dw;
490                         unsigned int j;
491
492                         for (j = 0, dw = dv->dw; j < dv->totweight; j++, dw++) {
493                                 /* note, greater then max defgroups is accounted for in our code, but not < 0 */
494                                 if (!finite(dw->weight)) {
495                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
496                                         if (do_fixes) {
497                                                 dw->weight = 0.0f;
498                                                 vert_weights_fixed = TRUE;
499                                         }
500                                 }
501                                 else if (dw->weight < 0.0f || dw->weight > 1.0f) {
502                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
503                                         if (do_fixes) {
504                                                 CLAMP(dw->weight, 0.0f, 1.0f);
505                                                 vert_weights_fixed = TRUE;
506                                         }
507                                 }
508
509                                 if (dw->def_nr < 0) {
510                                         PRINT("    vertex deform %u, has invalid group %d\n", i, dw->def_nr);
511                                         if (do_fixes) {
512                                                 defvert_remove_group(dv, dw);
513                                                 if (dv->dw) {
514                                                         /* re-allocated, the new values compensate for stepping
515                                                          * within the for loop and may not be valid */
516                                                         j--;
517                                                         dw = dv->dw + j;
518
519                                                         vert_weights_fixed = TRUE;
520                                                 }
521                                                 else { /* all freed */
522                                                         break;
523                                                 }
524                                         }
525                                 }
526                         }
527                 }
528         }
529
530         PRINT("BKE_mesh_validate: finished\n\n");
531
532 #   undef REMOVE_EDGE_TAG
533 #   undef IS_REMOVED_EDGE
534 #   undef REMOVE_LOOP_TAG
535 #   undef REMOVE_POLY_TAG
536
537         if (mesh) {
538                 if (do_polyloop_free) {
539                         BKE_mesh_strip_loose_polysloops(mesh);
540                 }
541
542                 if (do_edge_free) {
543                         BKE_mesh_strip_loose_edges(mesh);
544                 }
545
546                 if (do_edge_recalc) {
547                         BKE_mesh_calc_edges(mesh, TRUE);
548                 }
549         }
550
551         return (verts_fixed || vert_weights_fixed || do_polyloop_free || do_edge_free || do_edge_recalc);
552 }
553
554 static int mesh_validate_customdata(CustomData *data, short do_verbose, const short do_fixes)
555 {
556         int i = 0, has_fixes = 0;
557
558         while (i < data->totlayer) {
559                 CustomDataLayer *layer = &data->layers[i];
560                 CustomDataMask mask = CD_TYPE_AS_MASK(layer->type);
561                 int ok = 1;
562
563                 if ((mask & CD_MASK_MESH) == 0) {
564                         PRINT("CustomDataLayer type %d which isn't in CD_MASK_MESH is stored in Mehs structure\n", layer->type);
565
566                         if (do_fixes) {
567                                 CustomData_free_layer(data, layer->type, 0, i);
568                                 ok = 0;
569                                 has_fixes = 1;
570                         }
571                 }
572
573                 if (ok)
574                         i++;
575         }
576
577         return has_fixes;
578 }
579
580 #undef PRINT
581
582 static int BKE_mesh_validate_all_customdata(CustomData *vdata, CustomData *edata,
583                                             CustomData *ldata, CustomData *pdata,
584                                             short do_verbose, const short do_fixes)
585 {
586         int vfixed = 0, efixed = 0, lfixed = 0, pfixed = 0;
587
588         vfixed = mesh_validate_customdata(vdata, do_verbose, do_fixes);
589         efixed = mesh_validate_customdata(edata, do_verbose, do_fixes);
590         lfixed = mesh_validate_customdata(ldata, do_verbose, do_fixes);
591         pfixed = mesh_validate_customdata(pdata, do_verbose, do_fixes);
592
593         return vfixed || efixed || lfixed || pfixed;
594 }
595
596 int BKE_mesh_validate(Mesh *me, int do_verbose)
597 {
598         int layers_fixed = 0, arrays_fixed = 0;
599
600         if (do_verbose) {
601                 printf("MESH: %s\n", me->id.name + 2);
602         }
603
604         layers_fixed = BKE_mesh_validate_all_customdata(&me->vdata, &me->edata, &me->ldata, &me->pdata, do_verbose, TRUE);
605         arrays_fixed = BKE_mesh_validate_arrays(me,
606                                                 me->mvert, me->totvert,
607                                                 me->medge, me->totedge,
608                                                 me->mloop, me->totloop,
609                                                 me->mpoly, me->totpoly,
610                                                 me->dvert,
611                                                 do_verbose, TRUE);
612
613         if (layers_fixed || arrays_fixed) {
614                 DAG_id_tag_update(&me->id, OB_RECALC_DATA);
615                 return TRUE;
616         }
617         return FALSE;
618 }
619
620 int BKE_mesh_validate_dm(DerivedMesh *dm)
621 {
622         return BKE_mesh_validate_arrays(NULL,
623                                         dm->getVertArray(dm), dm->getNumVerts(dm),
624                                         dm->getEdgeArray(dm), dm->getNumEdges(dm),
625                                         dm->getLoopArray(dm), dm->getNumLoops(dm),
626                                         dm->getPolyArray(dm), dm->getNumPolys(dm),
627                                         dm->getVertDataArray(dm, CD_MDEFORMVERT),
628                                         TRUE, FALSE);
629 }
630
631 void BKE_mesh_calc_edges(Mesh *mesh, int update)
632 {
633         CustomData edata;
634         EdgeHashIterator *ehi;
635         MPoly *mp = mesh->mpoly;
636         MEdge *med, *med_orig;
637         EdgeHash *eh = BLI_edgehash_new();
638         int i, totedge, totpoly = mesh->totpoly;
639         int med_index;
640
641         if (mesh->totedge == 0)
642                 update = FALSE;
643
644         if (update) {
645                 /* assume existing edges are valid
646                  * useful when adding more faces and generating edges from them */
647                 med = mesh->medge;
648                 for (i = 0; i < mesh->totedge; i++, med++)
649                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
650         }
651
652         /* mesh loops (bmesh only) */
653         for (i = 0; i < totpoly; i++, mp++) {
654                 MLoop *l = &mesh->mloop[mp->loopstart];
655                 int j, l_prev = (l + (mp->totloop - 1))->v;
656                 for (j = 0; j < mp->totloop; j++, l++) {
657                         if (!BLI_edgehash_haskey(eh, l_prev, l->v)) {
658                                 BLI_edgehash_insert(eh, l_prev, l->v, NULL);
659                         }
660                         l_prev = l->v;
661                 }
662         }
663
664         totedge = BLI_edgehash_size(eh);
665
666         /* write new edges into a temporary CustomData */
667         memset(&edata, 0, sizeof(edata));
668         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
669
670         med = CustomData_get_layer(&edata, CD_MEDGE);
671         for (ehi = BLI_edgehashIterator_new(eh), i = 0;
672              BLI_edgehashIterator_isDone(ehi) == FALSE;
673              BLI_edgehashIterator_step(ehi), ++i, ++med)
674         {
675                 if (update && (med_orig = BLI_edgehashIterator_getValue(ehi))) {
676                         *med = *med_orig; /* copy from the original */
677                 }
678                 else {
679                         BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
680                         med->flag = ME_EDGEDRAW | ME_EDGERENDER | SELECT; /* select for newly created meshes which are selected [#25595] */
681                 }
682
683                 /* store the new edge index in the hash value */
684                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(i));
685         }
686         BLI_edgehashIterator_free(ehi);
687
688         if (mesh->totpoly) {
689                 /* second pass, iterate through all loops again and assign
690                  * the newly created edges to them. */
691                 MPoly *mp = mesh->mpoly;
692                 for (i = 0; i < mesh->totpoly; i++, mp++) {
693                         MLoop *l = &mesh->mloop[mp->loopstart];
694                         MLoop *l_prev = (l + (mp->totloop - 1));
695                         int j;
696                         for (j = 0; j < mp->totloop; j++, l++) {
697                                 /* lookup hashed edge index */
698                                 med_index = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
699                                 l_prev->e = med_index;
700                                 l_prev = l;
701                         }
702                 }
703         }
704
705         /* free old CustomData and assign new one */
706         CustomData_free(&mesh->edata, mesh->totedge);
707         mesh->edata = edata;
708         mesh->totedge = totedge;
709
710         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
711
712         BLI_edgehash_free(eh, NULL);
713 }