style cleanup: follow style guide for formatting of if/for/while loops, and else...
[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; }
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; }
110 #       define REMOVE_POLY_TAG(_mp) { _mp->totloop *= -1; do_polyloop_free = TRUE; }
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                                         *v = ml->v;
244                                 }
245
246                                 if (sp->invalid)
247                                         continue;
248
249                                 /* Test all poly's loops. */
250                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++) {
251                                         v1 = ml->v;
252                                         v2 = mloops[sp->loopstart + (j + 1) % mp->totloop].v;
253                                         if (!BLI_edgehash_haskey(edge_hash, v1, v2)) {
254                                                 /* Edge not existing. */
255                                                 PRINT("    poly %u needs missing edge (%u, %u)\n", sp->index, v1, v2);
256                                                 if (do_fixes)
257                                                         do_edge_recalc = TRUE;
258                                                 else
259                                                         sp->invalid = TRUE;
260                                         }
261                                         else if (ml->e >= totedge) {
262                                                 /* Invalid edge idx.
263                                                  * We already know from previous text that a valid edge exists, use it (if allowed)! */
264                                                 if (do_fixes) {
265                                                         int prev_e = ml->e;
266                                                         ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
267                                                         PRINT("    loop %u has invalid edge reference (%u), fixed using edge %u\n",
268                                                               sp->loopstart + j, prev_e, ml->e);
269                                                 }
270                                                 else {
271                                                         PRINT("    loop %u has invalid edge reference (%u)\n", sp->loopstart + j, ml->e);
272                                                         sp->invalid = TRUE;
273                                                 }
274                                         }
275                                         else {
276                                                 me = &medges[ml->e];
277                                                 if (IS_REMOVED_EDGE(me) || !((me->v1 == v1 && me->v2 == v2) || (me->v1 == v2 && me->v2 == v1))) {
278                                                         /* The pointed edge is invalid (tagged as removed, or vert idx mismatch),
279                                                          * and we already know from previous test that a valid one exists, use it (if allowed)! */
280                                                         if (do_fixes) {
281                                                                 int prev_e = ml->e;
282                                                                 ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(edge_hash, v1, v2));
283                                                                 PRINT("    poly %u has invalid edge reference (%u), fixed using edge %u\n",
284                                                                           sp->index, prev_e, ml->e);
285                                                         }
286                                                         else {
287                                                                 PRINT("    poly %u has invalid edge reference (%u)\n", sp->index, ml->e);
288                                                                 sp->invalid = TRUE;
289                                                         }
290                                                 }
291                                         }
292                                 }
293
294                                 /* Now check that that poly does not use a same vertex more than once! */
295                                 if (!sp->invalid) {
296                                         int *prev_v = v = sp->verts;
297                                         j = sp->numverts;
298
299                                         qsort(sp->verts, j, sizeof(int), int_cmp);
300
301                                         for (j--, v++; j; j--, v++) {
302                                                 if (*v != *prev_v) {
303                                                         int dlt = v - prev_v;
304                                                         if (dlt > 1) {
305                                                                 PRINT("    poly %u is invalid, it multi-uses vertex %u (%u times)\n",
306                                                                       sp->index, *prev_v, dlt);
307                                                                 sp->invalid = TRUE;
308                                                         }
309                                                         prev_v = v;
310                                                 }
311                                         }
312                                         if (v - prev_v > 1) { /* Don’t forget final verts! */
313                                                 PRINT("    poly %u is invalid, it multi-uses vertex %u (%u times)\n",
314                                                       sp->index, *prev_v, (int)(v - prev_v));
315                                                 sp->invalid = TRUE;
316                                         }
317                                 }
318                         
319                         }
320                 }
321
322                 /* Second check pass, testing polys using the same verts. */
323                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_poly_cmp);
324                 sp = prev_sp = sort_polys;
325                 sp++;
326
327                 for (i = 1; i < totpoly; i++, sp++) {
328                         int p1_nv = sp->numverts, p2_nv = prev_sp->numverts;
329                         int *p1_v = sp->verts, *p2_v = prev_sp->verts;
330                         short p1_sub = TRUE, p2_sub = TRUE;
331                         if (sp->invalid)
332                                 break;
333                         /* Test same polys. */
334 #if 0
335                         /* NOTE: This performs a sub-set test. */
336                         /* XXX This (and the sort of verts list) is better than systematic
337                          *     search of all verts of one list into the other if lists have
338                          *     a fair amount of elements.
339                          *     Not sure however it's worth it in this case?
340                          *     But as we also need sorted vert list to check verts multi-used
341                          *     (in first pass of checks)... */
342                         /* XXX If we consider only "equal" polys (i.e. using exactly same set of verts)
343                          *     as invalid, better to replace this by a simple memory cmp... */
344                         while ((p1_nv && p2_nv) && (p1_sub || p2_sub)) {
345                                 if (*p1_v < *p2_v) {
346                                         if (p1_sub)
347                                                 p1_sub = FALSE;
348                                         p1_nv--;
349                                         p1_v++;
350                                 }
351                                 else if (*p2_v < *p1_v) {
352                                         if (p2_sub)
353                                                 p2_sub = FALSE;
354                                         p2_nv--;
355                                         p2_v++;
356                                 }
357                                 else {
358                                         /* Equality, both next verts. */
359                                         p1_nv--;
360                                         p2_nv--;
361                                         p1_v++;
362                                         p2_v++;
363                                 }
364                         }
365                         if (p1_nv && p1_sub)
366                                 p1_sub = FALSE;
367                         else if (p2_nv && p2_sub)
368                                 p2_sub = FALSE;
369
370                         if (p1_sub && p2_sub) {
371                                 PRINT("    polys %u and %u use same vertices, considering poly %u as invalid.\n",
372                                       prev_sp->index, sp->index, sp->index);
373                                 sp->invalid = TRUE;
374                         }
375                         /* XXX In fact, these might be valid? :/ */
376                         else if (p1_sub) {
377                                 PRINT("    %u is a sub-poly of %u, considering it as invalid.\n", sp->index, prev_sp->index);
378                                 sp->invalid = TRUE;
379                         }
380                         else if (p2_sub) {
381                                 PRINT("    %u is a sub-poly of %u, considering it as invalid.\n", prev_sp->index, sp->index);
382                                 prev_sp->invalid = TRUE;
383                                 prev_sp = sp; /* sp is new reference poly. */
384                         }
385 #else
386                         if (0) {
387                                 p1_sub += 0;
388                                 p2_sub += 0;
389                         }
390                         if ((p1_nv == p2_nv) && (memcmp(p1_v, p2_v, p1_nv * sizeof(*p1_v)) == 0)) {
391                                 if (do_verbose) {
392                                         PRINT("    polys %u and %u use same vertices (%u",
393                                               prev_sp->index, sp->index, *p1_v);
394                                         for (j = 1; j < p1_nv; j++)
395                                                 PRINT(", %u", p1_v[j]);
396                                         PRINT("), considering poly %u as invalid.\n", sp->index);
397                                 }
398                                 sp->invalid = TRUE;
399                         }
400 #endif
401                         else {
402                                 prev_sp = sp;
403                         }
404                 }
405
406                 /* Third check pass, testing loops used by none or more than one poly. */
407                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_polyloop_cmp);
408                 sp = sort_polys;
409                 prev_sp = NULL;
410                 prev_end = 0;
411                 for (i = 0; i < totpoly; i++, sp++) {
412                         /* Free this now, we don't need it anymore, and avoid us another loop! */
413                         if (sp->verts)
414                                 MEM_freeN(sp->verts);
415
416                         /* Note above prev_sp: in following code, we make sure it is always valid poly (or NULL). */
417                         if (sp->invalid) {
418                                 if (do_fixes) {
419                                         REMOVE_POLY_TAG((&mpolys[sp->index]));
420                                         /* DO NOT REMOVE ITS LOOPS!!!
421                                          * As already invalid polys are at the end of the SortPoly list, the loops they
422                                          * were the only users have already been tagged as "to remove" during previous
423                                          * iterations, and we don’t want to remove some loops that may be used by
424                                          * another valid poly! */
425                                 }
426                         }
427                         /* Test loops users. */
428                         else {
429                                 /* Unused loops. */
430                                 if (prev_end < sp->loopstart) {
431                                         for (j = prev_end, ml = &mloops[prev_end]; j < sp->loopstart; j++, ml++) {
432                                                 PRINT("    loop %u is unused.\n", j);
433                                                 if (do_fixes)
434                                                         REMOVE_LOOP_TAG(ml);
435                                         }
436                                         prev_end = sp->loopstart + sp->numverts;
437                                         prev_sp = sp;
438                                 }
439                                 /* Multi-used loops. */
440                                 else if (prev_end > sp->loopstart) {
441                                         PRINT("    polys %u and %u share loops from %u to %u, considering poly %u as invalid.\n",
442                                               prev_sp->index, sp->index, sp->loopstart, prev_end, sp->index);
443                                         if (do_fixes) {
444                                                 REMOVE_POLY_TAG((&mpolys[sp->index]));
445                                                 /* DO NOT REMOVE ITS LOOPS!!!
446                                                  * They might be used by some next, valid poly!
447                                                  * Just not updating prev_end/prev_sp vars is enough to ensure the loops
448                                                  * effectively no more needed will be marked as "to be removed"! */
449                                         }
450                                 }
451                                 else {
452                                         prev_end = sp->loopstart + sp->numverts;
453                                         prev_sp = sp;
454                                 }
455                         }
456                 }
457                 /* We may have some remaining unused loops to get rid of! */
458                 if (prev_end < totloop) {
459                         for (j = prev_end, ml = &mloops[prev_end]; j < totloop; j++, ml++) {
460                                 PRINT("    loop %u is unused.\n", j);
461                                 if (do_fixes)
462                                         REMOVE_LOOP_TAG(ml);
463                         }
464                 }
465
466                 MEM_freeN(sort_polys);
467         }
468
469         BLI_edgehash_free(edge_hash, NULL);
470
471         /* fix deform verts */
472         if (dverts) {
473                 MDeformVert *dv;
474                 for (i=0, dv= dverts; i<totvert; i++, dv++) {
475                         MDeformWeight *dw;
476                         unsigned int j;
477
478                         for (j=0, dw= dv->dw; j < dv->totweight; j++, dw++) {
479                                 /* note, greater then max defgroups is accounted for in our code, but not < 0 */
480                                 if (!finite(dw->weight)) {
481                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
482                                         if (do_fixes) {
483                                                 dw->weight= 0.0f;
484                                                 vert_weights_fixed= TRUE;
485                                         }
486                                 }
487                                 else if (dw->weight < 0.0f || dw->weight > 1.0f) {
488                                         PRINT("    vertex deform %u, group %d has weight: %f\n", i, dw->def_nr, dw->weight);
489                                         if (do_fixes) {
490                                                 CLAMP(dw->weight, 0.0f, 1.0f);
491                                                 vert_weights_fixed= TRUE;
492                                         }
493                                 }
494
495                                 if (dw->def_nr < 0) {
496                                         PRINT("    vertex deform %u, has invalid group %d\n", i, dw->def_nr);
497                                         if (do_fixes) {
498                                                 defvert_remove_group(dv, dw);
499                                                 if (dv->dw) {
500                                                         /* re-allocated, the new values compensate for stepping
501                                                          * within the for loop and may not be valid */
502                                                         j--;
503                                                         dw= dv->dw + j;
504
505                                                         vert_weights_fixed= TRUE;
506                                                 }
507                                                 else { /* all freed */
508                                                         break;
509                                                 }
510                                         }
511                                 }
512                         }
513                 }
514         }
515
516         PRINT("BKE_mesh_validate: finished\n\n");
517
518 #       undef REMOVE_EDGE_TAG
519 #       undef IS_REMOVED_EDGE
520 #       undef REMOVE_LOOP_TAG
521 #       undef REMOVE_POLY_TAG
522
523         if (mesh) {
524                 if (do_polyloop_free) {
525                         mesh_strip_loose_polysloops(mesh);
526                 }
527
528                 if (do_edge_free) {
529                         mesh_strip_loose_edges(mesh);
530                 }
531
532                 if (do_edge_recalc) {
533                         BKE_mesh_calc_edges(mesh, TRUE);
534                 }
535         }
536
537         return (verts_fixed || vert_weights_fixed || do_polyloop_free || do_edge_free || do_edge_recalc);
538 }
539
540 static int mesh_validate_customdata(CustomData *data, short do_verbose, const short do_fixes)
541 {
542         int i= 0, has_fixes= 0;
543
544         while (i<data->totlayer) {
545                 CustomDataLayer *layer= &data->layers[i];
546                 CustomDataMask mask= CD_TYPE_AS_MASK(layer->type);
547                 int ok= 1;
548
549                 if ((mask&CD_MASK_MESH)==0) {
550                         PRINT("CustomDataLayer type %d which isn't in CD_MASK_MESH is stored in Mehs structure\n", layer->type);
551
552                         if (do_fixes) {
553                                 CustomData_free_layer(data, layer->type, 0, i);
554                                 ok= 0;
555                                 has_fixes= 1;
556                         }
557                 }
558
559                 if (ok)
560                         i++;
561         }
562
563         return has_fixes;
564 }
565
566 #undef PRINT
567
568 static int BKE_mesh_validate_all_customdata(CustomData *vdata, CustomData *edata,
569                                             CustomData *ldata, CustomData *pdata,
570                                             short do_verbose, const short do_fixes)
571 {
572         int vfixed= 0, efixed= 0, lfixed = 0, pfixed = 0;
573
574         vfixed= mesh_validate_customdata(vdata, do_verbose, do_fixes);
575         efixed= mesh_validate_customdata(edata, do_verbose, do_fixes);
576         lfixed= mesh_validate_customdata(ldata, do_verbose, do_fixes);
577         pfixed= mesh_validate_customdata(pdata, do_verbose, do_fixes);
578
579         return vfixed || efixed || lfixed || pfixed;
580 }
581
582 int BKE_mesh_validate(Mesh *me, int do_verbose)
583 {
584         int layers_fixed= 0, arrays_fixed= 0;
585
586         if (do_verbose) {
587                 printf("MESH: %s\n", me->id.name+2);
588         }
589
590         layers_fixed= BKE_mesh_validate_all_customdata(&me->vdata, &me->edata, &me->ldata, &me->pdata, do_verbose, TRUE);
591         arrays_fixed= BKE_mesh_validate_arrays(me,
592                                                me->mvert, me->totvert,
593                                                me->medge, me->totedge,
594                                                me->mloop, me->totloop,
595                                                me->mpoly, me->totpoly,
596                                                me->dvert,
597                                                do_verbose, TRUE);
598
599         if (layers_fixed || arrays_fixed) {
600                 DAG_id_tag_update(&me->id, OB_RECALC_DATA);
601                 return TRUE;
602         }
603         return FALSE;
604 }
605
606 int BKE_mesh_validate_dm(DerivedMesh *dm)
607 {
608         return BKE_mesh_validate_arrays(NULL,
609                                         dm->getVertArray(dm), dm->getNumVerts(dm),
610                                         dm->getEdgeArray(dm), dm->getNumEdges(dm),
611                                         dm->getLoopArray(dm), dm->getNumLoops(dm),
612                                         dm->getPolyArray(dm), dm->getNumPolys(dm),
613                                         dm->getVertDataArray(dm, CD_MDEFORMVERT),
614                                         TRUE, FALSE);
615 }
616
617 void BKE_mesh_calc_edges(Mesh *mesh, int update)
618 {
619         CustomData edata;
620         EdgeHashIterator *ehi;
621         MPoly *mp = mesh->mpoly;
622         MEdge *med, *med_orig;
623         EdgeHash *eh = BLI_edgehash_new();
624         int i, totedge, totpoly = mesh->totpoly;
625         int med_index;
626
627         if (mesh->totedge==0)
628                 update= 0;
629
630         if (update) {
631                 /* assume existing edges are valid
632                  * useful when adding more faces and generating edges from them */
633                 med= mesh->medge;
634                 for (i= 0; i<mesh->totedge; i++, med++)
635                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
636         }
637
638         /* mesh loops (bmesh only) */
639         for (i=0; i < totpoly; i++, mp++) {
640                 MLoop *l= &mesh->mloop[mp->loopstart];
641                 int j, l_prev= (l + (mp->totloop-1))->v;
642                 for (j=0; j < mp->totloop; j++, l++) {
643                         if (!BLI_edgehash_haskey(eh, l_prev, l->v)) {
644                                 BLI_edgehash_insert(eh, l_prev, l->v, NULL);
645                         }
646                         l_prev= l->v;
647                 }
648         }
649
650         totedge = BLI_edgehash_size(eh);
651
652         /* write new edges into a temporary CustomData */
653         memset(&edata, 0, sizeof(edata));
654         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
655
656         ehi = BLI_edgehashIterator_new(eh);
657         med = CustomData_get_layer(&edata, CD_MEDGE);
658         for (i = 0; !BLI_edgehashIterator_isDone(ehi);
659                 BLI_edgehashIterator_step(ehi), ++i, ++med) {
660
661                 if (update && (med_orig=BLI_edgehashIterator_getValue(ehi))) {
662                         *med= *med_orig; /* copy from the original */
663                 }
664                 else {
665                         BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
666                         med->flag = ME_EDGEDRAW|ME_EDGERENDER|SELECT; /* select for newly created meshes which are selected [#25595] */
667                 }
668
669                 /* store the new edge index in the hash value */
670                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(i));
671         }
672         BLI_edgehashIterator_free(ehi);
673
674         if (mesh->totpoly) {
675                 /* second pass, iterate through all loops again and assign
676                  * the newly created edges to them. */
677                 MPoly *mp= mesh->mpoly;
678                 for (i=0; i < mesh->totpoly; i++, mp++) {
679                         MLoop *l= &mesh->mloop[mp->loopstart];
680                         MLoop *l_prev= (l + (mp->totloop-1));
681                         int j;
682                         for (j=0; j < mp->totloop; j++, l++) {
683                                 /* lookup hashed edge index */
684                                 med_index = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, l_prev->v, l->v));
685                                 l_prev->e = med_index;
686                                 l_prev= l;
687                         }
688                 }
689         }
690
691         /* free old CustomData and assign new one */
692         CustomData_free(&mesh->edata, mesh->totedge);
693         mesh->edata = edata;
694         mesh->totedge = totedge;
695
696         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
697
698         BLI_edgehash_free(eh, NULL);
699 }