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