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