Merge branch 'blender2.7'
[blender.git] / source / blender / blenkernel / intern / mesh_validate.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2011 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file \ingroup bke
21  */
22
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <limits.h>
28
29 #include "CLG_log.h"
30
31 #include "DNA_mesh_types.h"
32 #include "DNA_meshdata_types.h"
33 #include "DNA_object_types.h"
34
35 #include "BLI_sys_types.h"
36
37 #include "BLI_utildefines.h"
38 #include "BLI_edgehash.h"
39 #include "BLI_math_base.h"
40 #include "BLI_math_vector.h"
41
42 #include "BKE_deform.h"
43 #include "BKE_mesh.h"
44
45 #include "DEG_depsgraph.h"
46
47 #include "MEM_guardedalloc.h"
48
49 /* loop v/e are unsigned, so using max uint_32 value as invalid marker... */
50 #define INVALID_LOOP_EDGE_MARKER 4294967295u
51
52 static CLG_LogRef LOG = {"bke.mesh"};
53
54 /** \name Internal functions
55  * \{ */
56
57 typedef union {
58         uint32_t verts[2];
59         int64_t edval;
60 } EdgeUUID;
61
62 typedef struct SortFace {
63         EdgeUUID     es[4];
64         unsigned int index;
65 } SortFace;
66
67 /* Used to detect polys (faces) using exactly the same vertices. */
68 /* Used to detect loops used by no (disjoint) or more than one (intersect) polys. */
69 typedef struct SortPoly {
70         int *verts;
71         int numverts;
72         int loopstart;
73         unsigned int index;
74         bool invalid;  /* Poly index. */
75 } SortPoly;
76
77 static void edge_store_assign(uint32_t verts[2],  const uint32_t v1, const uint32_t v2)
78 {
79         if (v1 < v2) {
80                 verts[0] = v1;
81                 verts[1] = v2;
82         }
83         else {
84                 verts[0] = v2;
85                 verts[1] = v1;
86         }
87 }
88
89 static void edge_store_from_mface_quad(EdgeUUID es[4], MFace *mf)
90 {
91         edge_store_assign(es[0].verts, mf->v1, mf->v2);
92         edge_store_assign(es[1].verts, mf->v2, mf->v3);
93         edge_store_assign(es[2].verts, mf->v3, mf->v4);
94         edge_store_assign(es[3].verts, mf->v4, mf->v1);
95 }
96
97 static void edge_store_from_mface_tri(EdgeUUID es[4], MFace *mf)
98 {
99         edge_store_assign(es[0].verts, mf->v1, mf->v2);
100         edge_store_assign(es[1].verts, mf->v2, mf->v3);
101         edge_store_assign(es[2].verts, mf->v3, mf->v1);
102         es[3].verts[0] = es[3].verts[1] = UINT_MAX;
103 }
104
105 static int int64_cmp(const void *v1, const void *v2)
106 {
107         const int64_t x1 = *(const int64_t *)v1;
108         const int64_t x2 = *(const int64_t *)v2;
109
110         if (x1 > x2) {
111                 return 1;
112         }
113         else if (x1 < x2) {
114                 return -1;
115         }
116
117         return 0;
118 }
119
120 static int search_face_cmp(const void *v1, const void *v2)
121 {
122         const SortFace *sfa = v1, *sfb = v2;
123
124         if (sfa->es[0].edval > sfb->es[0].edval) {
125                 return 1;
126         }
127         else if (sfa->es[0].edval < sfb->es[0].edval) {
128                 return -1;
129         }
130
131         else if (sfa->es[1].edval > sfb->es[1].edval) {
132                 return 1;
133         }
134         else if (sfa->es[1].edval < sfb->es[1].edval) {
135                 return -1;
136         }
137
138         else if (sfa->es[2].edval > sfb->es[2].edval) {
139                 return 1;
140         }
141         else if (sfa->es[2].edval < sfb->es[2].edval) {
142                 return -1;
143         }
144
145         else if (sfa->es[3].edval > sfb->es[3].edval) {
146                 return 1;
147         }
148         else if (sfa->es[3].edval < sfb->es[3].edval) {
149                 return -1;
150         }
151
152         return 0;
153 }
154
155 /* TODO check there is not some standard define of this somewhere! */
156 static int int_cmp(const void *v1, const void *v2)
157 {
158         return *(int *)v1 > *(int *)v2 ? 1 : *(int *)v1 < *(int *)v2 ? -1 : 0;
159 }
160
161 static int search_poly_cmp(const void *v1, const void *v2)
162 {
163         const SortPoly *sp1 = v1, *sp2 = v2;
164         const int max_idx = sp1->numverts > sp2->numverts ? sp2->numverts : sp1->numverts;
165         int idx;
166
167         /* Reject all invalid polys at end of list! */
168         if (sp1->invalid || sp2->invalid)
169                 return sp1->invalid ? (sp2->invalid ? 0 : 1) : -1;
170         /* Else, sort on first non-equal verts (remember verts of valid polys are sorted). */
171         for (idx = 0; idx < max_idx; idx++) {
172                 const int v1_i = sp1->verts[idx];
173                 const int v2_i = sp2->verts[idx];
174                 if (v1_i != v2_i) {
175                         return (v1_i > v2_i) ? 1 : -1;
176                 }
177         }
178         return sp1->numverts > sp2->numverts ? 1 : sp1->numverts < sp2->numverts ? -1 : 0;
179 }
180
181 static int search_polyloop_cmp(const void *v1, const void *v2)
182 {
183         const SortPoly *sp1 = v1, *sp2 = v2;
184
185         /* Reject all invalid polys at end of list! */
186         if (sp1->invalid || sp2->invalid)
187                 return sp1->invalid && sp2->invalid ? 0 : sp1->invalid ? 1 : -1;
188         /* Else, sort on loopstart. */
189         return sp1->loopstart > sp2->loopstart ? 1 : sp1->loopstart < sp2->loopstart ? -1 : 0;
190 }
191 /** \} */
192
193
194
195 /* -------------------------------------------------------------------- */
196 /** \name Mesh Validation
197  * \{ */
198
199 #define PRINT_MSG(...) if(do_verbose) CLOG_INFO(&LOG, 1, __VA_ARGS__)
200
201 #define PRINT_ERR(...) do { \
202                 is_valid = false; \
203                 if (do_verbose) { CLOG_ERROR(&LOG, __VA_ARGS__); } \
204         } while(0)
205
206 /**
207  * Validate the mesh, \a do_fixes requires \a mesh to be non-null.
208  *
209  * \return false if no changes needed to be made.
210  */
211 bool BKE_mesh_validate_arrays(
212         Mesh *mesh,
213         MVert *mverts, unsigned int totvert,
214         MEdge *medges, unsigned int totedge,
215         MFace *mfaces, unsigned int totface,
216         MLoop *mloops, unsigned int totloop,
217         MPoly *mpolys, unsigned int totpoly,
218         MDeformVert *dverts, /* assume totvert length */
219         const bool do_verbose, const bool do_fixes,
220         bool *r_changed)
221 {
222 #define REMOVE_EDGE_TAG(_me) { _me->v2 = _me->v1; free_flag.edges = do_fixes; } (void)0
223 #define IS_REMOVED_EDGE(_me) (_me->v2 == _me->v1)
224
225 #define REMOVE_LOOP_TAG(_ml) { _ml->e = INVALID_LOOP_EDGE_MARKER; free_flag.polyloops = do_fixes; } (void)0
226 #define REMOVE_POLY_TAG(_mp) { _mp->totloop *= -1; free_flag.polyloops = do_fixes; } (void)0
227
228         MVert *mv = mverts;
229         MEdge *me;
230         MLoop *ml;
231         MPoly *mp;
232         unsigned int i, j;
233         int *v;
234
235         bool is_valid = true;
236
237         union {
238                 struct {
239                         int verts : 1;
240                         int verts_weight : 1;
241                         int loops_edge : 1;
242                 };
243                 int as_flag;
244         } fix_flag;
245
246         union {
247                 struct {
248                         int edges : 1;
249                         int faces : 1;
250                         /* This regroups loops and polys! */
251                         int polyloops : 1;
252                         int mselect : 1;
253                 };
254                 int as_flag;
255         } free_flag;
256
257         union {
258                 struct {
259                         int edges : 1;
260                 };
261                 int as_flag;
262         } recalc_flag;
263
264         EdgeHash *edge_hash = BLI_edgehash_new_ex(__func__, totedge);
265
266         BLI_assert(!(do_fixes && mesh == NULL));
267
268         fix_flag.as_flag = 0;
269         free_flag.as_flag = 0;
270         recalc_flag.as_flag = 0;
271
272         PRINT_MSG("verts(%u), edges(%u), loops(%u), polygons(%u)",
273                   totvert, totedge, totloop, totpoly);
274
275         if (totedge == 0 && totpoly != 0) {
276                 PRINT_ERR("\tLogical error, %u polygons and 0 edges", totpoly);
277                 recalc_flag.edges = do_fixes;
278         }
279
280         for (i = 0; i < totvert; i++, mv++) {
281                 bool fix_normal = true;
282
283                 for (j = 0; j < 3; j++) {
284                         if (!isfinite(mv->co[j])) {
285                                 PRINT_ERR("\tVertex %u: has invalid coordinate", i);
286
287                                 if (do_fixes) {
288                                         zero_v3(mv->co);
289
290                                         fix_flag.verts = true;
291                                 }
292                         }
293
294                         if (mv->no[j] != 0)
295                                 fix_normal = false;
296                 }
297
298                 if (fix_normal) {
299                         PRINT_ERR("\tVertex %u: has zero normal, assuming Z-up normal", i);
300                         if (do_fixes) {
301                                 mv->no[2] = SHRT_MAX;
302                                 fix_flag.verts = true;
303                         }
304                 }
305         }
306
307         for (i = 0, me = medges; i < totedge; i++, me++) {
308                 bool remove = false;
309
310                 if (me->v1 == me->v2) {
311                         PRINT_ERR("\tEdge %u: has matching verts, both %u", i, me->v1);
312                         remove = do_fixes;
313                 }
314                 if (me->v1 >= totvert) {
315                         PRINT_ERR("\tEdge %u: v1 index out of range, %u", i, me->v1);
316                         remove = do_fixes;
317                 }
318                 if (me->v2 >= totvert) {
319                         PRINT_ERR("\tEdge %u: v2 index out of range, %u", i, me->v2);
320                         remove = do_fixes;
321                 }
322
323                 if ((me->v1 != me->v2) && BLI_edgehash_haskey(edge_hash, me->v1, me->v2)) {
324                         PRINT_ERR("\tEdge %u: is a duplicate of %d", i,
325                                   POINTER_AS_INT(BLI_edgehash_lookup(edge_hash, me->v1, me->v2)));
326                         remove = do_fixes;
327                 }
328
329                 if (remove == false) {
330                         if (me->v1 != me->v2) {
331                                 BLI_edgehash_insert(edge_hash, me->v1, me->v2, POINTER_FROM_INT(i));
332                         }
333                 }
334                 else {
335                         REMOVE_EDGE_TAG(me);
336                 }
337         }
338
339         if (mfaces && !mpolys) {
340 #               define REMOVE_FACE_TAG(_mf) { _mf->v3 = 0; free_flag.faces = do_fixes; } (void)0
341 #               define CHECK_FACE_VERT_INDEX(a, b) \
342                                         if (mf->a == mf->b) { \
343                                                 PRINT_ERR("    face %u: verts invalid, " STRINGIFY(a) "/" STRINGIFY(b) " both %u", i, mf->a); \
344                                                 remove = do_fixes; \
345                                         } (void)0
346 #               define CHECK_FACE_EDGE(a, b) \
347                                         if (!BLI_edgehash_haskey(edge_hash, mf->a, mf->b)) { \
348                                                 PRINT_ERR("    face %u: edge " STRINGIFY(a) "/" STRINGIFY(b) \
349                                                           " (%u,%u) is missing edge data", i, mf->a, mf->b); \
350                                                 recalc_flag.edges = do_fixes; \
351                                         } (void)0
352
353                 MFace *mf;
354                 MFace *mf_prev;
355
356                 SortFace *sort_faces = MEM_callocN(sizeof(SortFace) * totface, "search faces");
357                 SortFace *sf;
358                 SortFace *sf_prev;
359                 unsigned int totsortface = 0;
360
361                 PRINT_ERR("No Polys, only tessellated Faces");
362
363                 for (i = 0, mf = mfaces, sf = sort_faces; i < totface; i++, mf++) {
364                         bool remove = false;
365                         int fidx;
366                         unsigned int fv[4];
367
368                         fidx = mf->v4 ? 3 : 2;
369                         do {
370                                 fv[fidx] = *(&(mf->v1) + fidx);
371                                 if (fv[fidx] >= totvert) {
372                                         PRINT_ERR("\tFace %u: 'v%d' index out of range, %u", i, fidx + 1, fv[fidx]);
373                                         remove = do_fixes;
374                                 }
375                         } while (fidx--);
376
377                         if (remove == false) {
378                                 if (mf->v4) {
379                                         CHECK_FACE_VERT_INDEX(v1, v2);
380                                         CHECK_FACE_VERT_INDEX(v1, v3);
381                                         CHECK_FACE_VERT_INDEX(v1, v4);
382
383                                         CHECK_FACE_VERT_INDEX(v2, v3);
384                                         CHECK_FACE_VERT_INDEX(v2, v4);
385
386                                         CHECK_FACE_VERT_INDEX(v3, v4);
387                                 }
388                                 else {
389                                         CHECK_FACE_VERT_INDEX(v1, v2);
390                                         CHECK_FACE_VERT_INDEX(v1, v3);
391
392                                         CHECK_FACE_VERT_INDEX(v2, v3);
393                                 }
394
395                                 if (remove == false) {
396                                         if (totedge) {
397                                                 if (mf->v4) {
398                                                         CHECK_FACE_EDGE(v1, v2);
399                                                         CHECK_FACE_EDGE(v2, v3);
400                                                         CHECK_FACE_EDGE(v3, v4);
401                                                         CHECK_FACE_EDGE(v4, v1);
402                                                 }
403                                                 else {
404                                                         CHECK_FACE_EDGE(v1, v2);
405                                                         CHECK_FACE_EDGE(v2, v3);
406                                                         CHECK_FACE_EDGE(v3, v1);
407                                                 }
408                                         }
409
410                                         sf->index = i;
411
412                                         if (mf->v4) {
413                                                 edge_store_from_mface_quad(sf->es, mf);
414
415                                                 qsort(sf->es, 4, sizeof(int64_t), int64_cmp);
416                                         }
417                                         else {
418                                                 edge_store_from_mface_tri(sf->es, mf);
419                                                 qsort(sf->es, 3, sizeof(int64_t), int64_cmp);
420                                         }
421
422                                         totsortface++;
423                                         sf++;
424                                 }
425                         }
426
427                         if (remove) {
428                                 REMOVE_FACE_TAG(mf);
429                         }
430                 }
431
432                 qsort(sort_faces, totsortface, sizeof(SortFace), search_face_cmp);
433
434                 sf = sort_faces;
435                 sf_prev = sf;
436                 sf++;
437
438                 for (i = 1; i < totsortface; i++, sf++) {
439                         bool remove = false;
440
441                         /* on a valid mesh, code below will never run */
442                         if (memcmp(sf->es, sf_prev->es, sizeof(sf_prev->es)) == 0) {
443                                 mf = mfaces + sf->index;
444
445                                 if (do_verbose) {
446                                         mf_prev = mfaces + sf_prev->index;
447
448                                         if (mf->v4) {
449                                                 PRINT_ERR("\tFace %u & %u: are duplicates (%u,%u,%u,%u) (%u,%u,%u,%u)",
450                                                           sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3, mf->v4,
451                                                           mf_prev->v1, mf_prev->v2, mf_prev->v3, mf_prev->v4);
452                                         }
453                                         else {
454                                                 PRINT_ERR("\tFace %u & %u: are duplicates (%u,%u,%u) (%u,%u,%u)",
455                                                           sf->index, sf_prev->index, mf->v1, mf->v2, mf->v3,
456                                                           mf_prev->v1, mf_prev->v2, mf_prev->v3);
457                                         }
458                                 }
459
460                                 remove = do_fixes;
461                         }
462                         else {
463                                 sf_prev = sf;
464                         }
465
466                         if (remove) {
467                                 REMOVE_FACE_TAG(mf);
468                         }
469                 }
470
471                 MEM_freeN(sort_faces);
472
473 #               undef REMOVE_FACE_TAG
474 #               undef CHECK_FACE_VERT_INDEX
475 #               undef CHECK_FACE_EDGE
476         }
477
478         /* Checking loops and polys is a bit tricky, as they are quite intricate...
479          *
480          * Polys must have:
481          * - a valid loopstart value.
482          * - a valid totloop value (>= 3 and loopstart+totloop < me.totloop).
483          *
484          * Loops must have:
485          * - a valid v value.
486          * - a valid e value (corresponding to the edge it defines with the next loop in poly).
487          *
488          * Also, loops not used by polys can be discarded.
489          * And "intersecting" loops (i.e. loops used by more than one poly) are invalid,
490          * so be sure to leave at most one poly per loop!
491          */
492         {
493                 SortPoly *sort_polys = MEM_callocN(sizeof(SortPoly) * totpoly, "mesh validate's sort_polys");
494                 SortPoly *prev_sp, *sp = sort_polys;
495                 int prev_end;
496
497                 for (i = 0, mp = mpolys; i < totpoly; i++, mp++, sp++) {
498                         sp->index = i;
499
500                         if (mp->loopstart < 0 || mp->totloop < 3) {
501                                 /* Invalid loop data. */
502                                 PRINT_ERR("\tPoly %u is invalid (loopstart: %d, totloop: %d)",
503                                           sp->index, mp->loopstart, mp->totloop);
504                                 sp->invalid = true;
505                         }
506                         else if (mp->loopstart + mp->totloop > totloop) {
507                                 /* Invalid loop data. */
508                                 PRINT_ERR("\tPoly %u uses loops out of range (loopstart: %d, loopend: %d, max nbr of loops: %u)",
509                                           sp->index, mp->loopstart, mp->loopstart + mp->totloop - 1, totloop - 1);
510                                 sp->invalid = true;
511                         }
512                         else {
513                                 /* Poly itself is valid, for now. */
514                                 int v1, v2; /* v1 is prev loop vert idx, v2 is current loop one. */
515                                 sp->invalid = false;
516                                 sp->verts = v = MEM_mallocN(sizeof(int) * mp->totloop, "Vert idx of SortPoly");
517                                 sp->numverts = mp->totloop;
518                                 sp->loopstart = mp->loopstart;
519
520                                 /* Ideally we would only have to do that once on all vertices before we start checking each poly, but
521                                  * several polys can use same vert, so we have to ensure here all verts of current poly are cleared. */
522                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++) {
523                                         if (ml->v < totvert) {
524                                                 mverts[ml->v].flag &= ~ME_VERT_TMP_TAG;
525                                         }
526                                 }
527
528                                 /* Test all poly's loops' vert idx. */
529                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++, v++) {
530                                         if (ml->v >= totvert) {
531                                                 /* Invalid vert idx. */
532                                                 PRINT_ERR("\tLoop %u has invalid vert reference (%u)", sp->loopstart + j, ml->v);
533                                                 sp->invalid = true;
534                                         }
535                                         else if (mverts[ml->v].flag & ME_VERT_TMP_TAG) {
536                                                 PRINT_ERR("\tPoly %u has duplicated vert reference at corner (%u)", i, j);
537                                                 sp->invalid = true;
538                                         }
539                                         else {
540                                                 mverts[ml->v].flag |= ME_VERT_TMP_TAG;
541                                         }
542                                         *v = ml->v;
543                                 }
544
545                                 if (sp->invalid)
546                                         continue;
547
548                                 /* Test all poly's loops. */
549                                 for (j = 0, ml = &mloops[sp->loopstart]; j < mp->totloop; j++, ml++) {
550                                         v1 = ml->v;
551                                         v2 = mloops[sp->loopstart + (j + 1) % mp->totloop].v;
552                                         if (!BLI_edgehash_haskey(edge_hash, v1, v2)) {
553                                                 /* Edge not existing. */
554                                                 PRINT_ERR("\tPoly %u needs missing edge (%d, %d)", sp->index, v1, v2);
555                                                 if (do_fixes)
556                                                         recalc_flag.edges = true;
557                                                 else
558                                                         sp->invalid = true;
559                                         }
560                                         else if (ml->e >= totedge) {
561                                                 /* Invalid edge idx.
562                                                  * We already know from previous text that a valid edge exists, use it (if allowed)! */
563                                                 if (do_fixes) {
564                                                         int prev_e = ml->e;
565                                                         ml->e = POINTER_AS_INT(BLI_edgehash_lookup(edge_hash, v1, v2));
566                                                         fix_flag.loops_edge = true;
567                                                         PRINT_ERR("\tLoop %u has invalid edge reference (%d), fixed using edge %u",
568                                                                   sp->loopstart + j, prev_e, ml->e);
569                                                 }
570                                                 else {
571                                                         PRINT_ERR("\tLoop %u has invalid edge reference (%u)", sp->loopstart + j, ml->e);
572                                                         sp->invalid = true;
573                                                 }
574                                         }
575                                         else {
576                                                 me = &medges[ml->e];
577                                                 if (IS_REMOVED_EDGE(me) || !((me->v1 == v1 && me->v2 == v2) || (me->v1 == v2 && me->v2 == v1))) {
578                                                         /* The pointed edge is invalid (tagged as removed, or vert idx mismatch),
579                                                          * and we already know from previous test that a valid one exists, use it (if allowed)! */
580                                                         if (do_fixes) {
581                                                                 int prev_e = ml->e;
582                                                                 ml->e = POINTER_AS_INT(BLI_edgehash_lookup(edge_hash, v1, v2));
583                                                                 fix_flag.loops_edge = true;
584                                                                 PRINT_ERR("\tPoly %u has invalid edge reference (%d, is_removed: %d), fixed using edge %u",
585                                                                           sp->index, prev_e, IS_REMOVED_EDGE(me), ml->e);
586                                                         }
587                                                         else {
588                                                                 PRINT_ERR("\tPoly %u has invalid edge reference (%u)", sp->index, ml->e);
589                                                                 sp->invalid = true;
590                                                         }
591                                                 }
592                                         }
593                                 }
594
595                                 if (!sp->invalid) {
596                                         /* Needed for checking polys using same verts below. */
597                                         qsort(sp->verts, sp->numverts, sizeof(int), int_cmp);
598                                 }
599                         }
600                 }
601
602                 /* Second check pass, testing polys using the same verts. */
603                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_poly_cmp);
604                 sp = prev_sp = sort_polys;
605                 sp++;
606
607                 for (i = 1; i < totpoly; i++, sp++) {
608                         int p1_nv = sp->numverts, p2_nv = prev_sp->numverts;
609                         const int *p1_v = sp->verts, *p2_v = prev_sp->verts;
610
611                         if (sp->invalid) {
612                                 /* break, because all known invalid polys have been put at the end by qsort with search_poly_cmp. */
613                                 break;
614                         }
615
616                         /* Test same polys. */
617                         if ((p1_nv == p2_nv) && (memcmp(p1_v, p2_v, p1_nv * sizeof(*p1_v)) == 0)) {
618                                 if (do_verbose) {
619                                         // TODO: convert list to string
620                                         PRINT_ERR("\tPolys %u and %u use same vertices (%d",
621                                                   prev_sp->index, sp->index, *p1_v);
622                                         for (j = 1; j < p1_nv; j++)
623                                                 PRINT_ERR(", %d", p1_v[j]);
624                                         PRINT_ERR("), considering poly %u as invalid.", sp->index);
625                                 }
626                                 else {
627                                         is_valid = false;
628                                 }
629                                 sp->invalid = true;
630                         }
631                         else {
632                                 prev_sp = sp;
633                         }
634                 }
635
636                 /* Third check pass, testing loops used by none or more than one poly. */
637                 qsort(sort_polys, totpoly, sizeof(SortPoly), search_polyloop_cmp);
638                 sp = sort_polys;
639                 prev_sp = NULL;
640                 prev_end = 0;
641                 for (i = 0; i < totpoly; i++, sp++) {
642                         /* Free this now, we don't need it anymore, and avoid us another loop! */
643                         if (sp->verts)
644                                 MEM_freeN(sp->verts);
645
646                         /* Note above prev_sp: in following code, we make sure it is always valid poly (or NULL). */
647                         if (sp->invalid) {
648                                 if (do_fixes) {
649                                         REMOVE_POLY_TAG((&mpolys[sp->index]));
650                                         /* DO NOT REMOVE ITS LOOPS!!!
651                                          * As already invalid polys are at the end of the SortPoly list, the loops they
652                                          * were the only users have already been tagged as "to remove" during previous
653                                          * iterations, and we don't want to remove some loops that may be used by
654                                          * another valid poly! */
655                                 }
656                         }
657                         /* Test loops users. */
658                         else {
659                                 /* Unused loops. */
660                                 if (prev_end < sp->loopstart) {
661                                         for (j = prev_end, ml = &mloops[prev_end]; j < sp->loopstart; j++, ml++) {
662                                                 PRINT_ERR("\tLoop %u is unused.", j);
663                                                 if (do_fixes)
664                                                         REMOVE_LOOP_TAG(ml);
665                                         }
666                                         prev_end = sp->loopstart + sp->numverts;
667                                         prev_sp = sp;
668                                 }
669                                 /* Multi-used loops. */
670                                 else if (prev_end > sp->loopstart) {
671                                         PRINT_ERR("\tPolys %u and %u share loops from %d to %d, considering poly %u as invalid.",
672                                                   prev_sp->index, sp->index, sp->loopstart, prev_end, sp->index);
673                                         if (do_fixes) {
674                                                 REMOVE_POLY_TAG((&mpolys[sp->index]));
675                                                 /* DO NOT REMOVE ITS LOOPS!!!
676                                                  * They might be used by some next, valid poly!
677                                                  * Just not updating prev_end/prev_sp vars is enough to ensure the loops
678                                                  * effectively no more needed will be marked as "to be removed"! */
679                                         }
680                                 }
681                                 else {
682                                         prev_end = sp->loopstart + sp->numverts;
683                                         prev_sp = sp;
684                                 }
685                         }
686                 }
687                 /* We may have some remaining unused loops to get rid of! */
688                 if (prev_end < totloop) {
689                         for (j = prev_end, ml = &mloops[prev_end]; j < totloop; j++, ml++) {
690                                 PRINT_ERR("\tLoop %u is unused.", j);
691                                 if (do_fixes)
692                                         REMOVE_LOOP_TAG(ml);
693                         }
694                 }
695
696                 MEM_freeN(sort_polys);
697         }
698
699         BLI_edgehash_free(edge_hash, NULL);
700
701         /* fix deform verts */
702         if (dverts) {
703                 MDeformVert *dv;
704                 for (i = 0, dv = dverts; i < totvert; i++, dv++) {
705                         MDeformWeight *dw;
706
707                         for (j = 0, dw = dv->dw; j < dv->totweight; j++, dw++) {
708                                 /* note, greater than max defgroups is accounted for in our code, but not < 0 */
709                                 if (!isfinite(dw->weight)) {
710                                         PRINT_ERR("\tVertex deform %u, group %d has weight: %f", i, dw->def_nr, dw->weight);
711                                         if (do_fixes) {
712                                                 dw->weight = 0.0f;
713                                                 fix_flag.verts_weight = true;
714                                         }
715                                 }
716                                 else if (dw->weight < 0.0f || dw->weight > 1.0f) {
717                                         PRINT_ERR("\tVertex deform %u, group %d has weight: %f", i, dw->def_nr, dw->weight);
718                                         if (do_fixes) {
719                                                 CLAMP(dw->weight, 0.0f, 1.0f);
720                                                 fix_flag.verts_weight = true;
721                                         }
722                                 }
723
724                                 if (dw->def_nr < 0) {
725                                         PRINT_ERR("\tVertex deform %u, has invalid group %d", i, dw->def_nr);
726                                         if (do_fixes) {
727                                                 defvert_remove_group(dv, dw);
728                                                 fix_flag.verts_weight = true;
729
730                                                 if (dv->dw) {
731                                                         /* re-allocated, the new values compensate for stepping
732                                                          * within the for loop and may not be valid */
733                                                         j--;
734                                                         dw = dv->dw + j;
735
736                                                 }
737                                                 else { /* all freed */
738                                                         break;
739                                                 }
740                                         }
741                                 }
742                         }
743                 }
744         }
745
746 #   undef REMOVE_EDGE_TAG
747 #   undef IS_REMOVED_EDGE
748 #   undef REMOVE_LOOP_TAG
749 #   undef REMOVE_POLY_TAG
750
751         if (mesh) {
752                 if (free_flag.faces) {
753                         BKE_mesh_strip_loose_faces(mesh);
754                 }
755
756                 if (free_flag.polyloops) {
757                         BKE_mesh_strip_loose_polysloops(mesh);
758                 }
759
760                 if (free_flag.edges) {
761                         BKE_mesh_strip_loose_edges(mesh);
762                 }
763
764                 if (recalc_flag.edges) {
765                         BKE_mesh_calc_edges(mesh, true, false);
766                 }
767         }
768
769         if (mesh && mesh->mselect) {
770                 MSelect *msel;
771
772                 for (i = 0, msel = mesh->mselect; i < mesh->totselect; i++, msel++) {
773                         int tot_elem = 0;
774
775                         if (msel->index < 0) {
776                                 PRINT_ERR("\tMesh select element %u type %d index is negative, "
777                                           "resetting selection stack.\n", i, msel->type);
778                                 free_flag.mselect = do_fixes;
779                                 break;
780                         }
781
782                         switch (msel->type) {
783                                 case ME_VSEL:
784                                         tot_elem = mesh->totvert;
785                                         break;
786                                 case ME_ESEL:
787                                         tot_elem = mesh->totedge;
788                                         break;
789                                 case ME_FSEL:
790                                         tot_elem = mesh->totface;
791                                         break;
792                         }
793
794                         if (msel->index > tot_elem) {
795                                 PRINT_ERR("\tMesh select element %u type %d index %d is larger than data array size %d, "
796                                           "resetting selection stack.\n", i, msel->type, msel->index, tot_elem);
797
798                                 free_flag.mselect = do_fixes;
799                                 break;
800                         }
801                 }
802
803                 if (free_flag.mselect) {
804                         MEM_freeN(mesh->mselect);
805                         mesh->mselect = NULL;
806                         mesh->totselect = 0;
807                 }
808         }
809
810         PRINT_MSG("%s: finished\n\n", __func__);
811
812         *r_changed = (fix_flag.as_flag || free_flag.as_flag || recalc_flag.as_flag);
813
814         BLI_assert((*r_changed == false) || (do_fixes == true));
815
816         return is_valid;
817 }
818
819 static bool mesh_validate_customdata(
820         CustomData *data, CustomDataMask mask, const uint totitems,
821         const bool do_verbose, const bool do_fixes,
822         bool *r_change)
823 {
824         bool is_valid = true;
825         bool has_fixes = false;
826         int i = 0;
827
828         PRINT_MSG("%s: Checking %d CD layers...\n", __func__, data->totlayer);
829
830         while (i < data->totlayer) {
831                 CustomDataLayer *layer = &data->layers[i];
832                 bool ok = true;
833
834                 if (CustomData_layertype_is_singleton(layer->type)) {
835                         const int layer_tot = CustomData_number_of_layers(data, layer->type);
836                         if (layer_tot > 1) {
837                                 PRINT_ERR("\tCustomDataLayer type %d is a singleton, found %d in Mesh structure\n",
838                                           layer->type, layer_tot);
839                                 ok = false;
840                         }
841                 }
842
843                 if (mask != 0) {
844                         CustomDataMask layer_typemask = CD_TYPE_AS_MASK(layer->type);
845                         if ((layer_typemask & mask) == 0) {
846                                 PRINT_ERR("\tCustomDataLayer type %d which isn't in the mask\n",
847                                           layer->type);
848                                 ok = false;
849                         }
850                 }
851
852                 if (ok == false) {
853                         if (do_fixes) {
854                                 CustomData_free_layer(data, layer->type, 0, i);
855                                 has_fixes = true;
856                         }
857                 }
858
859                 if (ok) {
860                         if (CustomData_layer_validate(layer, totitems, do_fixes)) {
861                                 PRINT_ERR("\tCustomDataLayer type %d has some invalid data\n", layer->type);
862                                 has_fixes = do_fixes;
863                         }
864                         i++;
865                 }
866         }
867
868         PRINT_MSG("%s: Finished (is_valid=%d)\n\n", __func__, (int)!has_fixes);
869
870         *r_change = has_fixes;
871
872         return is_valid;
873 }
874
875 /**
876  * \returns is_valid.
877  */
878 bool BKE_mesh_validate_all_customdata(
879         CustomData *vdata, const uint totvert,
880         CustomData *edata, const uint totedge,
881         CustomData *ldata, const uint totloop,
882         CustomData *pdata, const uint totpoly,
883         const bool check_meshmask,
884         const bool do_verbose, const bool do_fixes,
885         bool *r_change)
886 {
887         bool is_valid = true;
888         bool is_change_v, is_change_e, is_change_l, is_change_p;
889         int tot_uvloop, tot_vcolloop;
890         CustomDataMask mask = check_meshmask ? CD_MASK_MESH : 0;
891
892         is_valid &= mesh_validate_customdata(vdata, mask, totvert, do_verbose, do_fixes, &is_change_v);
893         is_valid &= mesh_validate_customdata(edata, mask, totedge, do_verbose, do_fixes, &is_change_e);
894         is_valid &= mesh_validate_customdata(ldata, mask, totloop, do_verbose, do_fixes, &is_change_l);
895         is_valid &= mesh_validate_customdata(pdata, mask, totpoly, do_verbose, do_fixes, &is_change_p);
896
897         tot_uvloop = CustomData_number_of_layers(ldata, CD_MLOOPUV);
898         tot_vcolloop = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
899         if (tot_uvloop > MAX_MTFACE) {
900                 PRINT_ERR("\tMore UV layers than %d allowed, %d last ones won't be available for render, shaders, etc.\n",
901                           MAX_MTFACE, tot_uvloop - MAX_MTFACE);
902         }
903         if (tot_vcolloop > MAX_MCOL) {
904                 PRINT_ERR("\tMore VCol layers than %d allowed, %d last ones won't be available for render, shaders, etc.\n",
905                           MAX_MCOL, tot_vcolloop - MAX_MCOL);
906         }
907
908         /* check indices of clone/stencil */
909         if (do_fixes && CustomData_get_clone_layer(ldata, CD_MLOOPUV) >= tot_uvloop) {
910                 CustomData_set_layer_clone(ldata, CD_MLOOPUV, 0);
911                 is_change_l = true;
912         }
913         if (do_fixes && CustomData_get_stencil_layer(ldata, CD_MLOOPUV) >= tot_uvloop) {
914                 CustomData_set_layer_stencil(ldata, CD_MLOOPUV, 0);
915                 is_change_l = true;
916         }
917
918         *r_change = (is_change_v || is_change_e || is_change_l || is_change_p);
919
920         return is_valid;
921 }
922
923 /**
924  * Validates and corrects a Mesh.
925  *
926  * \returns true if a change is made.
927  */
928 bool BKE_mesh_validate(Mesh *me, const bool do_verbose, const bool cddata_check_mask)
929 {
930         bool is_valid = true;
931         bool changed;
932
933         if (do_verbose) {
934                 CLOG_INFO(&LOG, 0, "MESH: %s", me->id.name + 2);
935         }
936
937         is_valid &= BKE_mesh_validate_all_customdata(
938                 &me->vdata, me->totvert,
939                 &me->edata, me->totedge,
940                 &me->ldata, me->totloop,
941                 &me->pdata, me->totpoly,
942                 cddata_check_mask,
943                 do_verbose, true,
944                 &changed);
945
946         is_valid &= BKE_mesh_validate_arrays(
947                 me,
948                 me->mvert, me->totvert,
949                 me->medge, me->totedge,
950                 me->mface, me->totface,
951                 me->mloop, me->totloop,
952                 me->mpoly, me->totpoly,
953                 me->dvert,
954                 do_verbose, true,
955                 &changed);
956
957         if (changed) {
958                 DEG_id_tag_update(&me->id, ID_RECALC_GEOMETRY);
959                 return true;
960         }
961         else {
962                 return false;
963         }
964 }
965
966 /**
967  * Checks if a Mesh is valid without any modification. This is always verbose.
968  *
969  * \see  #DM_is_valid to call on derived meshes
970  *
971  * \returns is_valid.
972  */
973 bool BKE_mesh_is_valid(Mesh *me)
974 {
975         const bool do_verbose = true;
976         const bool do_fixes = false;
977
978         bool is_valid = true;
979         bool changed = true;
980
981         is_valid &= BKE_mesh_validate_all_customdata(
982                 &me->vdata, me->totvert,
983                 &me->edata, me->totedge,
984                 &me->ldata, me->totloop,
985                 &me->pdata, me->totpoly,
986                 false,  /* setting mask here isn't useful, gives false positives */
987                 do_verbose, do_fixes, &changed);
988
989         is_valid &= BKE_mesh_validate_arrays(
990                 me,
991                 me->mvert, me->totvert,
992                 me->medge, me->totedge,
993                 me->mface, me->totface,
994                 me->mloop, me->totloop,
995                 me->mpoly, me->totpoly,
996                 me->dvert,
997                 do_verbose, do_fixes,
998                 &changed);
999
1000         BLI_assert(changed == false);
1001
1002         return is_valid;
1003 }
1004
1005 /**
1006  * Check all material indices of polygons are valid, invalid ones are set to 0.
1007  * \returns is_valid.
1008  */
1009 bool BKE_mesh_validate_material_indices(Mesh *me)
1010 {
1011         MPoly *mp;
1012         const int max_idx = max_ii(0, me->totcol - 1);
1013         const int totpoly = me->totpoly;
1014         int i;
1015         bool is_valid = true;
1016
1017         for (mp = me->mpoly, i = 0; i < totpoly; i++, mp++) {
1018                 if (mp->mat_nr > max_idx) {
1019                         mp->mat_nr = 0;
1020                         is_valid = false;
1021                 }
1022         }
1023
1024         if (!is_valid) {
1025                 DEG_id_tag_update(&me->id, ID_RECALC_GEOMETRY);
1026                 return true;
1027         }
1028         else {
1029                 return false;
1030         }
1031 }
1032
1033 /** \} */
1034
1035
1036 /* -------------------------------------------------------------------- */
1037 /** \name Mesh Stripping (removing invalid data)
1038  * \{ */
1039
1040 /* We need to keep this for edge creation (for now?), and some old readfile code... */
1041 void BKE_mesh_strip_loose_faces(Mesh *me)
1042 {
1043         MFace *f;
1044         int a, b;
1045
1046         for (a = b = 0, f = me->mface; a < me->totface; a++, f++) {
1047                 if (f->v3) {
1048                         if (a != b) {
1049                                 memcpy(&me->mface[b], f, sizeof(me->mface[b]));
1050                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
1051                         }
1052                         b++;
1053                 }
1054         }
1055         if (a != b) {
1056                 CustomData_free_elem(&me->fdata, b, a - b);
1057                 me->totface = b;
1058         }
1059 }
1060
1061 /* Works on both loops and polys! */
1062 /* Note: It won't try to guess which loops of an invalid poly to remove!
1063  *       this is the work of the caller, to mark those loops...
1064  *       See e.g. BKE_mesh_validate_arrays(). */
1065 void BKE_mesh_strip_loose_polysloops(Mesh *me)
1066 {
1067         MPoly *p;
1068         MLoop *l;
1069         int a, b;
1070         /* New loops idx! */
1071         int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__);
1072
1073         for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
1074                 bool invalid = false;
1075                 int i = p->loopstart;
1076                 int stop = i + p->totloop;
1077
1078                 if (stop > me->totloop || stop < i) {
1079                         invalid = true;
1080                 }
1081                 else {
1082                         l = &me->mloop[i];
1083                         i = stop - i;
1084                         /* If one of the poly's loops is invalid, the whole poly is invalid! */
1085                         for (; i--; l++) {
1086                                 if (l->e == INVALID_LOOP_EDGE_MARKER) {
1087                                         invalid = true;
1088                                         break;
1089                                 }
1090                         }
1091                 }
1092
1093                 if (p->totloop >= 3 && !invalid) {
1094                         if (a != b) {
1095                                 memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b]));
1096                                 CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1);
1097                         }
1098                         b++;
1099                 }
1100         }
1101         if (a != b) {
1102                 CustomData_free_elem(&me->pdata, b, a - b);
1103                 me->totpoly = b;
1104         }
1105
1106         /* And now, get rid of invalid loops. */
1107         for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) {
1108                 if (l->e != INVALID_LOOP_EDGE_MARKER) {
1109                         if (a != b) {
1110                                 memcpy(&me->mloop[b], l, sizeof(me->mloop[b]));
1111                                 CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1);
1112                         }
1113                         new_idx[a] = b;
1114                         b++;
1115                 }
1116                 else {
1117                         /* XXX Theoretically, we should be able to not do this, as no remaining poly
1118                          *     should use any stripped loop. But for security's sake... */
1119                         new_idx[a] = -a;
1120                 }
1121         }
1122         if (a != b) {
1123                 CustomData_free_elem(&me->ldata, b, a - b);
1124                 me->totloop = b;
1125         }
1126
1127         /* And now, update polys' start loop index. */
1128         /* Note: At this point, there should never be any poly using a striped loop! */
1129         for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
1130                 p->loopstart = new_idx[p->loopstart];
1131         }
1132
1133         MEM_freeN(new_idx);
1134 }
1135
1136 void BKE_mesh_strip_loose_edges(Mesh *me)
1137 {
1138         MEdge *e;
1139         MLoop *l;
1140         int a, b;
1141         unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__);
1142
1143         for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) {
1144                 if (e->v1 != e->v2) {
1145                         if (a != b) {
1146                                 memcpy(&me->medge[b], e, sizeof(me->medge[b]));
1147                                 CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
1148                         }
1149                         new_idx[a] = b;
1150                         b++;
1151                 }
1152                 else {
1153                         new_idx[a] = INVALID_LOOP_EDGE_MARKER;
1154                 }
1155         }
1156         if (a != b) {
1157                 CustomData_free_elem(&me->edata, b, a - b);
1158                 me->totedge = b;
1159         }
1160
1161         /* And now, update loops' edge indices. */
1162         /* XXX We hope no loop was pointing to a striped edge!
1163          *     Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */
1164         for (a = 0, l = me->mloop; a < me->totloop; a++, l++) {
1165                 l->e = new_idx[l->e];
1166         }
1167
1168         MEM_freeN(new_idx);
1169 }
1170 /** \} */
1171
1172
1173
1174 /* -------------------------------------------------------------------- */
1175 /** \name Mesh Edge Calculation
1176  * \{ */
1177
1178 /* make edges in a Mesh, for outside of editmode */
1179
1180 struct EdgeSort {
1181         unsigned int v1, v2;
1182         char is_loose, is_draw;
1183 };
1184
1185 /* edges have to be added with lowest index first for sorting */
1186 static void to_edgesort(
1187         struct EdgeSort *ed,
1188         unsigned int v1, unsigned int v2,
1189         char is_loose, short is_draw)
1190 {
1191         if (v1 < v2) {
1192                 ed->v1 = v1; ed->v2 = v2;
1193         }
1194         else {
1195                 ed->v1 = v2; ed->v2 = v1;
1196         }
1197         ed->is_loose = is_loose;
1198         ed->is_draw = is_draw;
1199 }
1200
1201 static int vergedgesort(const void *v1, const void *v2)
1202 {
1203         const struct EdgeSort *x1 = v1, *x2 = v2;
1204
1205         if (x1->v1 > x2->v1) return 1;
1206         else if (x1->v1 < x2->v1) return -1;
1207         else if (x1->v2 > x2->v2) return 1;
1208         else if (x1->v2 < x2->v2) return -1;
1209
1210         return 0;
1211 }
1212
1213
1214 /* Create edges based on known verts and faces,
1215  * this function is only used when loading very old blend files */
1216
1217 static void mesh_calc_edges_mdata(
1218         MVert *UNUSED(allvert), MFace *allface, MLoop *allloop,
1219         MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly,
1220         const bool use_old,
1221         MEdge **r_medge, int *r_totedge)
1222 {
1223         MPoly *mpoly;
1224         MFace *mface;
1225         MEdge *medge, *med;
1226         EdgeHash *hash;
1227         struct EdgeSort *edsort, *ed;
1228         int a, totedge = 0;
1229         unsigned int totedge_final = 0;
1230         unsigned int edge_index;
1231
1232         /* we put all edges in array, sort them, and detect doubles that way */
1233
1234         for (a = totface, mface = allface; a > 0; a--, mface++) {
1235                 if (mface->v4) totedge += 4;
1236                 else if (mface->v3) totedge += 3;
1237                 else totedge += 1;
1238         }
1239
1240         if (totedge == 0) {
1241                 /* flag that mesh has edges */
1242                 (*r_medge) = MEM_callocN(0, __func__);
1243                 (*r_totedge) = 0;
1244                 return;
1245         }
1246
1247         ed = edsort = MEM_mallocN(totedge * sizeof(struct EdgeSort), "EdgeSort");
1248
1249         for (a = totface, mface = allface; a > 0; a--, mface++) {
1250                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
1251                 if (mface->v4) {
1252                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
1253                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
1254                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
1255                 }
1256                 else if (mface->v3) {
1257                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
1258                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
1259                 }
1260         }
1261
1262         qsort(edsort, totedge, sizeof(struct EdgeSort), vergedgesort);
1263
1264         /* count final amount */
1265         for (a = totedge, ed = edsort; a > 1; a--, ed++) {
1266                 /* edge is unique when it differs from next edge, or is last */
1267                 if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) totedge_final++;
1268         }
1269         totedge_final++;
1270
1271         medge = MEM_callocN(sizeof(MEdge) * totedge_final, __func__);
1272
1273         for (a = totedge, med = medge, ed = edsort; a > 1; a--, ed++) {
1274                 /* edge is unique when it differs from next edge, or is last */
1275                 if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) {
1276                         med->v1 = ed->v1;
1277                         med->v2 = ed->v2;
1278                         if (use_old == false || ed->is_draw) med->flag = ME_EDGEDRAW | ME_EDGERENDER;
1279                         if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
1280
1281                         /* order is swapped so extruding this edge as a surface wont flip face normals
1282                          * with cyclic curves */
1283                         if (ed->v1 + 1 != ed->v2) {
1284                                 SWAP(unsigned int, med->v1, med->v2);
1285                         }
1286                         med++;
1287                 }
1288                 else {
1289                         /* equal edge, we merge the drawflag */
1290                         (ed + 1)->is_draw |= ed->is_draw;
1291                 }
1292         }
1293         /* last edge */
1294         med->v1 = ed->v1;
1295         med->v2 = ed->v2;
1296         med->flag = ME_EDGEDRAW;
1297         if (ed->is_loose) med->flag |= ME_LOOSEEDGE;
1298         med->flag |= ME_EDGERENDER;
1299
1300         MEM_freeN(edsort);
1301
1302         /* set edge members of mloops */
1303         hash = BLI_edgehash_new_ex(__func__, totedge_final);
1304         for (edge_index = 0, med = medge; edge_index < totedge_final; edge_index++, med++) {
1305                 BLI_edgehash_insert(hash, med->v1, med->v2, POINTER_FROM_UINT(edge_index));
1306         }
1307
1308         mpoly = allpoly;
1309         for (a = 0; a < totpoly; a++, mpoly++) {
1310                 MLoop *ml, *ml_next;
1311                 int i = mpoly->totloop;
1312
1313                 ml_next = allloop + mpoly->loopstart;  /* first loop */
1314                 ml = &ml_next[i - 1];                  /* last loop */
1315
1316                 while (i-- != 0) {
1317                         ml->e = POINTER_AS_UINT(BLI_edgehash_lookup(hash, ml->v, ml_next->v));
1318                         ml = ml_next;
1319                         ml_next++;
1320                 }
1321         }
1322
1323         BLI_edgehash_free(hash, NULL);
1324
1325         *r_medge = medge;
1326         *r_totedge = totedge_final;
1327 }
1328
1329 /**
1330  * If the mesh is from a very old blender version,
1331  * convert mface->edcode to edge drawflags
1332  */
1333 void BKE_mesh_calc_edges_legacy(Mesh *me, const bool use_old)
1334 {
1335         MEdge *medge;
1336         int totedge = 0;
1337
1338         mesh_calc_edges_mdata(
1339                 me->mvert, me->mface, me->mloop, me->mpoly,
1340                 me->totvert, me->totface, me->totloop, me->totpoly,
1341                 use_old, &medge, &totedge);
1342
1343         if (totedge == 0) {
1344                 /* flag that mesh has edges */
1345                 me->medge = medge;
1346                 me->totedge = 0;
1347                 return;
1348         }
1349
1350         medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
1351         me->medge = medge;
1352         me->totedge = totedge;
1353
1354         BKE_mesh_strip_loose_faces(me);
1355 }
1356
1357
1358 /**
1359  * Calculate edges from polygons
1360  *
1361  * \param mesh: The mesh to add edges into
1362  * \param update: When true create new edges co-exist
1363  */
1364 void BKE_mesh_calc_edges(Mesh *mesh, bool update, const bool select)
1365 {
1366         CustomData edata;
1367         EdgeHashIterator *ehi;
1368         MPoly *mp;
1369         MEdge *med, *med_orig;
1370         EdgeHash *eh;
1371         unsigned int eh_reserve;
1372         int i, totedge, totpoly = mesh->totpoly;
1373         int med_index;
1374         /* select for newly created meshes which are selected [#25595] */
1375         const short ed_flag = (ME_EDGEDRAW | ME_EDGERENDER) | (select ? SELECT : 0);
1376
1377         if (mesh->totedge == 0)
1378                 update = false;
1379
1380         eh_reserve = max_ii(update ? mesh->totedge : 0, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly));
1381         eh = BLI_edgehash_new_ex(__func__, eh_reserve);
1382
1383         if (update) {
1384                 /* assume existing edges are valid
1385                  * useful when adding more faces and generating edges from them */
1386                 med = mesh->medge;
1387                 for (i = 0; i < mesh->totedge; i++, med++)
1388                         BLI_edgehash_insert(eh, med->v1, med->v2, med);
1389         }
1390
1391         /* mesh loops (bmesh only) */
1392         for (mp = mesh->mpoly, i = 0; i < totpoly; mp++, i++) {
1393                 MLoop *l = &mesh->mloop[mp->loopstart];
1394                 int j, v_prev = (l + (mp->totloop - 1))->v;
1395                 for (j = 0; j < mp->totloop; j++, l++) {
1396                         if (v_prev != l->v) {
1397                                 void **val_p;
1398                                 if (!BLI_edgehash_ensure_p(eh, v_prev, l->v, &val_p)) {
1399                                         *val_p = NULL;
1400                                 }
1401                         }
1402                         v_prev = l->v;
1403                 }
1404         }
1405
1406         totedge = BLI_edgehash_len(eh);
1407
1408         /* write new edges into a temporary CustomData */
1409         CustomData_reset(&edata);
1410         CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
1411
1412         med = CustomData_get_layer(&edata, CD_MEDGE);
1413         for (ehi = BLI_edgehashIterator_new(eh), i = 0;
1414              BLI_edgehashIterator_isDone(ehi) == false;
1415              BLI_edgehashIterator_step(ehi), ++i, ++med)
1416         {
1417                 if (update && (med_orig = BLI_edgehashIterator_getValue(ehi))) {
1418                         *med = *med_orig; /* copy from the original */
1419                 }
1420                 else {
1421                         BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
1422                         med->flag = ed_flag;
1423                 }
1424
1425                 /* store the new edge index in the hash value */
1426                 BLI_edgehashIterator_setValue(ehi, POINTER_FROM_INT(i));
1427         }
1428         BLI_edgehashIterator_free(ehi);
1429
1430         if (mesh->totpoly) {
1431                 /* second pass, iterate through all loops again and assign
1432                  * the newly created edges to them. */
1433                 for (mp = mesh->mpoly, i = 0; i < mesh->totpoly; mp++, i++) {
1434                         MLoop *l = &mesh->mloop[mp->loopstart];
1435                         MLoop *l_prev = (l + (mp->totloop - 1));
1436                         int j;
1437                         for (j = 0; j < mp->totloop; j++, l++) {
1438                                 /* lookup hashed edge index */
1439                                 med_index = POINTER_AS_INT(BLI_edgehash_lookup(eh, l_prev->v, l->v));
1440                                 l_prev->e = med_index;
1441                                 l_prev = l;
1442                         }
1443                 }
1444         }
1445
1446         /* free old CustomData and assign new one */
1447         CustomData_free(&mesh->edata, mesh->totedge);
1448         mesh->edata = edata;
1449         mesh->totedge = totedge;
1450
1451         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
1452
1453         BLI_edgehash_free(eh, NULL);
1454 }
1455
1456 void BKE_mesh_calc_edges_loose(Mesh *mesh)
1457 {
1458         MEdge *med = mesh->medge;
1459         for (int i = 0; i < mesh->totedge; i++, med++) {
1460                 med->flag |= ME_LOOSEEDGE;
1461         }
1462         MLoop *ml = mesh->mloop;
1463         for (int i = 0; i < mesh->totloop; i++, ml++) {
1464                 mesh->medge[ml->e].flag &= ~ME_LOOSEEDGE;
1465         }
1466 }
1467
1468 /**
1469  * Calculate/create edges from tessface data
1470  *
1471  * \param mesh: The mesh to add edges into
1472  */
1473
1474 void BKE_mesh_calc_edges_tessface(Mesh *mesh)
1475 {
1476         CustomData edgeData;
1477         EdgeSetIterator *ehi;
1478         MFace *mf = mesh->mface;
1479         MEdge *med;
1480         EdgeSet *eh;
1481         int i, *index, numEdges, numFaces = mesh->totface;
1482
1483         eh = BLI_edgeset_new_ex(__func__, BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(numFaces));
1484
1485         for (i = 0; i < numFaces; i++, mf++) {
1486                 BLI_edgeset_add(eh, mf->v1, mf->v2);
1487                 BLI_edgeset_add(eh, mf->v2, mf->v3);
1488
1489                 if (mf->v4) {
1490                         BLI_edgeset_add(eh, mf->v3, mf->v4);
1491                         BLI_edgeset_add(eh, mf->v4, mf->v1);
1492                 }
1493                 else {
1494                         BLI_edgeset_add(eh, mf->v3, mf->v1);
1495                 }
1496         }
1497
1498         numEdges = BLI_edgeset_len(eh);
1499
1500         /* write new edges into a temporary CustomData */
1501         CustomData_reset(&edgeData);
1502         CustomData_add_layer(&edgeData, CD_MEDGE, CD_CALLOC, NULL, numEdges);
1503         CustomData_add_layer(&edgeData, CD_ORIGINDEX, CD_CALLOC, NULL, numEdges);
1504
1505         med = CustomData_get_layer(&edgeData, CD_MEDGE);
1506         index = CustomData_get_layer(&edgeData, CD_ORIGINDEX);
1507
1508         for (ehi = BLI_edgesetIterator_new(eh), i = 0;
1509              BLI_edgesetIterator_isDone(ehi) == false;
1510              BLI_edgesetIterator_step(ehi), i++, med++, index++)
1511         {
1512                 BLI_edgesetIterator_getKey(ehi, &med->v1, &med->v2);
1513
1514                 med->flag = ME_EDGEDRAW | ME_EDGERENDER;
1515                 *index = ORIGINDEX_NONE;
1516         }
1517         BLI_edgesetIterator_free(ehi);
1518
1519         /* free old CustomData and assign new one */
1520         CustomData_free(&mesh->edata, mesh->totedge);
1521         mesh->edata = edgeData;
1522         mesh->totedge = numEdges;
1523
1524         mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
1525
1526         BLI_edgeset_free(eh);
1527 }
1528
1529 /** \} */