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