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
17 /** \file
18 * \ingroup modifiers
19 */
20
21 #include "BLI_utildefines.h"
22
23 #include "BLI_math.h"
24
25 #include "DNA_mesh_types.h"
26 #include "DNA_meshdata_types.h"
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BKE_deform.h"
31 #include "BKE_mesh.h"
32 #include "BKE_particle.h"
33
34 #include "MOD_modifiertypes.h"
35 #include "MOD_solidify_util.h" /* Own include. */
36 #include "MOD_util.h"
37
38 #ifdef __GNUC__
39 # pragma GCC diagnostic error "-Wsign-conversion"
40 #endif
41
42 /* -------------------------------------------------------------------- */
43 /** \name Local Utilities
44 * \{ */
45
46 /**
47 * Similar to #project_v3_v3v3_normalized that returns the dot-product.
48 */
project_v3_v3(float r[3],const float a[3])49 static float project_v3_v3(float r[3], const float a[3])
50 {
51 float d = dot_v3v3(r, a);
52 r[0] -= a[0] * d;
53 r[1] -= a[1] * d;
54 r[2] -= a[2] * d;
55 return d;
56 }
57
angle_signed_on_axis_normalized_v3v3_v3(const float n[3],const float ref_n[3],const float axis[3])58 static float angle_signed_on_axis_normalized_v3v3_v3(const float n[3],
59 const float ref_n[3],
60 const float axis[3])
61 {
62 float d = dot_v3v3(n, ref_n);
63 CLAMP(d, -1, 1);
64 float angle = acosf(d);
65 float cross[3];
66 cross_v3_v3v3(cross, n, ref_n);
67 if (dot_v3v3(cross, axis) >= 0) {
68 angle = 2 * M_PI - angle;
69 }
70 return angle;
71 }
72
73 /** \} */
74
75 /* -------------------------------------------------------------------- */
76 /** \name Main Solidify Function
77 * \{ */
78
79 /* Data structures for manifold solidify. */
80
81 typedef struct NewFaceRef {
82 MPoly *face;
83 uint index;
84 bool reversed;
85 struct NewEdgeRef **link_edges;
86 } NewFaceRef;
87
88 typedef struct OldEdgeFaceRef {
89 uint *faces;
90 uint faces_len;
91 bool *faces_reversed;
92 uint used;
93 } OldEdgeFaceRef;
94
95 typedef struct OldVertEdgeRef {
96 uint *edges;
97 uint edges_len;
98 } OldVertEdgeRef;
99
100 typedef struct NewEdgeRef {
101 uint old_edge;
102 NewFaceRef *faces[2];
103 struct EdgeGroup *link_edge_groups[2];
104 float angle;
105 uint new_edge;
106 } NewEdgeRef;
107
108 typedef struct EdgeGroup {
109 bool valid;
110 NewEdgeRef **edges;
111 uint edges_len;
112 uint open_face_edge;
113 bool is_orig_closed;
114 bool is_even_split;
115 uint split;
116 bool is_singularity;
117 uint topo_group;
118 float co[3];
119 float no[3];
120 uint new_vert;
121 } EdgeGroup;
122
123 typedef struct FaceKeyPair {
124 float angle;
125 NewFaceRef *face;
126 } FaceKeyPair;
127
comp_float_int_pair(const void * a,const void * b)128 static int comp_float_int_pair(const void *a, const void *b)
129 {
130 FaceKeyPair *x = (FaceKeyPair *)a;
131 FaceKeyPair *y = (FaceKeyPair *)b;
132 return (int)(x->angle > y->angle) - (int)(x->angle < y->angle);
133 }
134
135 /* NOLINTNEXTLINE: readability-function-size */
MOD_solidify_nonmanifold_modifyMesh(ModifierData * md,const ModifierEvalContext * ctx,Mesh * mesh)136 Mesh *MOD_solidify_nonmanifold_modifyMesh(ModifierData *md,
137 const ModifierEvalContext *ctx,
138 Mesh *mesh)
139 {
140 Mesh *result;
141 const SolidifyModifierData *smd = (SolidifyModifierData *)md;
142
143 MVert *mv, *mvert, *orig_mvert;
144 MEdge *ed, *medge, *orig_medge;
145 MLoop *ml, *mloop, *orig_mloop;
146 MPoly *mp, *mpoly, *orig_mpoly;
147 const uint numVerts = (uint)mesh->totvert;
148 const uint numEdges = (uint)mesh->totedge;
149 const uint numPolys = (uint)mesh->totpoly;
150 const uint numLoops = (uint)mesh->totloop;
151
152 if (numPolys == 0 && numVerts != 0) {
153 return mesh;
154 }
155
156 /* Only use material offsets if we have 2 or more materials. */
157 const short mat_nrs = ctx->object->totcol > 1 ? ctx->object->totcol : 1;
158 const short mat_nr_max = mat_nrs - 1;
159 const short mat_ofs = mat_nrs > 1 ? smd->mat_ofs : 0;
160 const short mat_ofs_rim = mat_nrs > 1 ? smd->mat_ofs_rim : 0;
161
162 float(*poly_nors)[3] = NULL;
163
164 const float ofs_front = (smd->offset_fac + 1.0f) * 0.5f * smd->offset;
165 const float ofs_back = ofs_front - smd->offset * smd->offset_fac;
166 const float ofs_front_clamped = max_ff(1e-5f, fabsf(smd->offset > 0 ? ofs_front : ofs_back));
167 const float ofs_back_clamped = max_ff(1e-5f, fabsf(smd->offset > 0 ? ofs_back : ofs_front));
168 const float offset_fac_vg = smd->offset_fac_vg;
169 const float offset_fac_vg_inv = 1.0f - smd->offset_fac_vg;
170 const float offset = fabsf(smd->offset) * smd->offset_clamp;
171 const bool do_angle_clamp = smd->flag & MOD_SOLIDIFY_OFFSET_ANGLE_CLAMP;
172 const bool do_flip = (smd->flag & MOD_SOLIDIFY_FLIP) != 0;
173 const bool do_rim = smd->flag & MOD_SOLIDIFY_RIM;
174 const bool do_shell = ((smd->flag & MOD_SOLIDIFY_RIM) && (smd->flag & MOD_SOLIDIFY_NOSHELL)) ==
175 0;
176 const bool do_clamp = (smd->offset_clamp != 0.0f);
177
178 const float bevel_convex = smd->bevel_convex;
179
180 MDeformVert *dvert;
181 const bool defgrp_invert = (smd->flag & MOD_SOLIDIFY_VGROUP_INV) != 0;
182 int defgrp_index;
183 const int shell_defgrp_index = BKE_object_defgroup_name_index(ctx->object,
184 smd->shell_defgrp_name);
185 const int rim_defgrp_index = BKE_object_defgroup_name_index(ctx->object, smd->rim_defgrp_name);
186
187 MOD_get_vgroup(ctx->object, mesh, smd->defgrp_name, &dvert, &defgrp_index);
188
189 const bool do_flat_faces = dvert && (smd->flag & MOD_SOLIDIFY_NONMANIFOLD_FLAT_FACES);
190
191 orig_mvert = mesh->mvert;
192 orig_medge = mesh->medge;
193 orig_mloop = mesh->mloop;
194 orig_mpoly = mesh->mpoly;
195
196 uint numNewVerts = 0;
197 uint numNewEdges = 0;
198 uint numNewLoops = 0;
199 uint numNewPolys = 0;
200
201 #define MOD_SOLIDIFY_EMPTY_TAG ((uint)-1)
202
203 /* Calculate only face normals. */
204 poly_nors = MEM_malloc_arrayN(numPolys, sizeof(*poly_nors), __func__);
205 BKE_mesh_calc_normals_poly(orig_mvert,
206 NULL,
207 (int)numVerts,
208 orig_mloop,
209 orig_mpoly,
210 (int)numLoops,
211 (int)numPolys,
212 poly_nors,
213 true);
214
215 NewFaceRef *face_sides_arr = MEM_malloc_arrayN(
216 numPolys * 2, sizeof(*face_sides_arr), "face_sides_arr in solidify");
217 bool *null_faces =
218 (smd->nonmanifold_offset_mode == MOD_SOLIDIFY_NONMANIFOLD_OFFSET_MODE_CONSTRAINTS) ?
219 MEM_calloc_arrayN(numPolys, sizeof(*null_faces), "null_faces in solidify") :
220 NULL;
221 uint largest_ngon = 3;
222 /* Calculate face to #NewFaceRef map. */
223 {
224 mp = orig_mpoly;
225 for (uint i = 0; i < numPolys; i++, mp++) {
226 /* Make normals for faces without area (should really be avoided though). */
227 if (len_squared_v3(poly_nors[i]) < 0.5f) {
228 MEdge *e = orig_medge + orig_mloop[mp->loopstart].e;
229 float edgedir[3];
230 sub_v3_v3v3(edgedir, orig_mvert[e->v2].co, orig_mvert[e->v1].co);
231 if (fabsf(edgedir[2]) < fabsf(edgedir[1])) {
232 poly_nors[i][2] = 1.0f;
233 }
234 else {
235 poly_nors[i][1] = 1.0f;
236 }
237 if (null_faces) {
238 null_faces[i] = true;
239 }
240 }
241
242 NewEdgeRef **link_edges = MEM_calloc_arrayN(
243 (uint)mp->totloop, sizeof(*link_edges), "NewFaceRef::link_edges in solidify");
244 face_sides_arr[i * 2] = (NewFaceRef){
245 .face = mp, .index = i, .reversed = false, .link_edges = link_edges};
246 link_edges = MEM_calloc_arrayN(
247 (uint)mp->totloop, sizeof(*link_edges), "NewFaceRef::link_edges in solidify");
248 face_sides_arr[i * 2 + 1] = (NewFaceRef){
249 .face = mp, .index = i, .reversed = true, .link_edges = link_edges};
250 if (mp->totloop > largest_ngon) {
251 largest_ngon = (uint)mp->totloop;
252 }
253 /* add to final mesh face count */
254 if (do_shell) {
255 numNewPolys += 2;
256 numNewLoops += (uint)mp->totloop * 2;
257 }
258 }
259 }
260
261 uint *edge_adj_faces_len = MEM_calloc_arrayN(
262 numEdges, sizeof(*edge_adj_faces_len), "edge_adj_faces_len in solidify");
263 /* Count for each edge how many faces it has adjacent. */
264 {
265 mp = orig_mpoly;
266 for (uint i = 0; i < numPolys; i++, mp++) {
267 ml = orig_mloop + mp->loopstart;
268 for (uint j = 0; j < mp->totloop; j++, ml++) {
269 edge_adj_faces_len[ml->e]++;
270 }
271 }
272 }
273
274 /* Original edge to #NewEdgeRef map. */
275 NewEdgeRef ***orig_edge_data_arr = MEM_calloc_arrayN(
276 numEdges, sizeof(*orig_edge_data_arr), "orig_edge_data_arr in solidify");
277 /* Original edge length cache. */
278 float *orig_edge_lengths = MEM_calloc_arrayN(
279 numEdges, sizeof(*orig_edge_lengths), "orig_edge_lengths in solidify");
280 /* Edge groups for every original vert. */
281 EdgeGroup **orig_vert_groups_arr = MEM_calloc_arrayN(
282 numVerts, sizeof(*orig_vert_groups_arr), "orig_vert_groups_arr in solidify");
283 /* vertex map used to map duplicates. */
284 uint *vm = MEM_malloc_arrayN(numVerts, sizeof(*vm), "orig_vert_map in solidify");
285 for (uint i = 0; i < numVerts; i++) {
286 vm[i] = i;
287 }
288
289 uint edge_index = 0;
290 uint loop_index = 0;
291 uint poly_index = 0;
292
293 bool has_singularities = false;
294
295 /* Vert edge adjacent map. */
296 OldVertEdgeRef **vert_adj_edges = MEM_calloc_arrayN(
297 numVerts, sizeof(*vert_adj_edges), "vert_adj_edges in solidify");
298 /* Original vertex positions (changed for degenerated geometry). */
299 float(*orig_mvert_co)[3] = MEM_malloc_arrayN(
300 numVerts, sizeof(*orig_mvert_co), "orig_mvert_co in solidify");
301 /* Fill in the original vertex positions. */
302 for (uint i = 0; i < numVerts; i++) {
303 orig_mvert_co[i][0] = orig_mvert[i].co[0];
304 orig_mvert_co[i][1] = orig_mvert[i].co[1];
305 orig_mvert_co[i][2] = orig_mvert[i].co[2];
306 }
307
308 /* Create edge to #NewEdgeRef map. */
309 {
310 OldEdgeFaceRef **edge_adj_faces = MEM_calloc_arrayN(
311 numEdges, sizeof(*edge_adj_faces), "edge_adj_faces in solidify");
312
313 /* Create link_faces for edges. */
314 {
315 mp = orig_mpoly;
316 for (uint i = 0; i < numPolys; i++, mp++) {
317 ml = orig_mloop + mp->loopstart;
318 for (uint j = 0; j < mp->totloop; j++, ml++) {
319 const uint edge = ml->e;
320 const bool reversed = orig_medge[edge].v2 != ml->v;
321 OldEdgeFaceRef *old_face_edge_ref = edge_adj_faces[edge];
322 if (old_face_edge_ref == NULL) {
323 const uint len = edge_adj_faces_len[edge];
324 BLI_assert(len > 0);
325 uint *adj_faces = MEM_malloc_arrayN(
326 len, sizeof(*adj_faces), "OldEdgeFaceRef::faces in solidify");
327 bool *adj_faces_reversed = MEM_malloc_arrayN(
328 len, sizeof(*adj_faces_reversed), "OldEdgeFaceRef::reversed in solidify");
329 adj_faces[0] = i;
330 for (uint k = 1; k < len; k++) {
331 adj_faces[k] = MOD_SOLIDIFY_EMPTY_TAG;
332 }
333 adj_faces_reversed[0] = reversed;
334 OldEdgeFaceRef *ref = MEM_mallocN(sizeof(*ref), "OldEdgeFaceRef in solidify");
335 *ref = (OldEdgeFaceRef){adj_faces, len, adj_faces_reversed, 1};
336 edge_adj_faces[edge] = ref;
337 }
338 else {
339 for (uint k = 1; k < old_face_edge_ref->faces_len; k++) {
340 if (old_face_edge_ref->faces[k] == MOD_SOLIDIFY_EMPTY_TAG) {
341 old_face_edge_ref->faces[k] = i;
342 old_face_edge_ref->faces_reversed[k] = reversed;
343 break;
344 }
345 }
346 }
347 }
348 }
349 }
350
351 float edgedir[3] = {0, 0, 0};
352 uint *vert_adj_edges_len = MEM_calloc_arrayN(
353 numVerts, sizeof(*vert_adj_edges_len), "vert_adj_edges_len in solidify");
354
355 /* Calculate edge lengths and len vert_adj edges. */
356 {
357 bool *face_singularity = MEM_calloc_arrayN(
358 numPolys, sizeof(*face_singularity), "face_sides_arr in solidify");
359
360 const float merge_tolerance_sqr = smd->merge_tolerance * smd->merge_tolerance;
361 uint *combined_verts = MEM_calloc_arrayN(
362 numVerts, sizeof(*combined_verts), "combined_verts in solidify");
363
364 ed = orig_medge;
365 for (uint i = 0; i < numEdges; i++, ed++) {
366 if (edge_adj_faces_len[i] > 0) {
367 uint v1 = vm[ed->v1];
368 uint v2 = vm[ed->v2];
369 if (v1 == v2) {
370 continue;
371 }
372
373 if (v2 < v1) {
374 SWAP(uint, v1, v2);
375 }
376 sub_v3_v3v3(edgedir, orig_mvert_co[v2], orig_mvert_co[v1]);
377 orig_edge_lengths[i] = len_squared_v3(edgedir);
378
379 if (orig_edge_lengths[i] <= merge_tolerance_sqr) {
380 /* Merge verts. But first check if that would create a higher poly count. */
381 /* This check is very slow. It would need the vertex edge links to get
382 * accelerated that are not yet available at this point. */
383 bool can_merge = true;
384 for (uint k = 0; k < numEdges && can_merge; k++) {
385 if (k != i && edge_adj_faces_len[k] > 0 &&
386 (ELEM(vm[orig_medge[k].v1], v1, v2) != ELEM(vm[orig_medge[k].v2], v1, v2))) {
387 for (uint j = 0; j < edge_adj_faces[k]->faces_len && can_merge; j++) {
388 mp = orig_mpoly + edge_adj_faces[k]->faces[j];
389 uint changes = 0;
390 int cur = mp->totloop - 1;
391 for (int next = 0; next < mp->totloop && changes <= 2; next++) {
392 uint cur_v = vm[orig_mloop[mp->loopstart + cur].v];
393 uint next_v = vm[orig_mloop[mp->loopstart + next].v];
394 changes += (ELEM(cur_v, v1, v2) != ELEM(next_v, v1, v2));
395 cur = next;
396 }
397 can_merge = can_merge && changes <= 2;
398 }
399 }
400 }
401
402 if (!can_merge) {
403 orig_edge_lengths[i] = 0.0f;
404 vert_adj_edges_len[v1]++;
405 vert_adj_edges_len[v2]++;
406 continue;
407 }
408
409 mul_v3_fl(edgedir,
410 (combined_verts[v2] + 1) /
411 (float)(combined_verts[v1] + combined_verts[v2] + 2));
412 add_v3_v3(orig_mvert_co[v1], edgedir);
413 for (uint j = v2; j < numVerts; j++) {
414 if (vm[j] == v2) {
415 vm[j] = v1;
416 }
417 }
418 vert_adj_edges_len[v1] += vert_adj_edges_len[v2];
419 vert_adj_edges_len[v2] = 0;
420 combined_verts[v1] += combined_verts[v2] + 1;
421
422 if (do_shell) {
423 numNewLoops -= edge_adj_faces_len[i] * 2;
424 }
425
426 edge_adj_faces_len[i] = 0;
427 MEM_freeN(edge_adj_faces[i]->faces);
428 MEM_freeN(edge_adj_faces[i]->faces_reversed);
429 MEM_freeN(edge_adj_faces[i]);
430 edge_adj_faces[i] = NULL;
431 }
432 else {
433 orig_edge_lengths[i] = sqrtf(orig_edge_lengths[i]);
434 vert_adj_edges_len[v1]++;
435 vert_adj_edges_len[v2]++;
436 }
437 }
438 }
439 /* remove zero faces in a second pass */
440 ed = orig_medge;
441 for (uint i = 0; i < numEdges; i++, ed++) {
442 const uint v1 = vm[ed->v1];
443 const uint v2 = vm[ed->v2];
444 if (v1 == v2 && edge_adj_faces[i]) {
445 /* Remove polys. */
446 for (uint j = 0; j < edge_adj_faces[i]->faces_len; j++) {
447 const uint face = edge_adj_faces[i]->faces[j];
448 if (!face_singularity[face]) {
449 bool is_singularity = true;
450 for (uint k = 0; k < orig_mpoly[face].totloop; k++) {
451 if (vm[orig_mloop[((uint)orig_mpoly[face].loopstart) + k].v] != v1) {
452 is_singularity = false;
453 break;
454 }
455 }
456 if (is_singularity) {
457 face_singularity[face] = true;
458 /* remove from final mesh poly count */
459 if (do_shell) {
460 numNewPolys -= 2;
461 }
462 }
463 }
464 }
465
466 if (do_shell) {
467 numNewLoops -= edge_adj_faces_len[i] * 2;
468 }
469
470 edge_adj_faces_len[i] = 0;
471 MEM_freeN(edge_adj_faces[i]->faces);
472 MEM_freeN(edge_adj_faces[i]->faces_reversed);
473 MEM_freeN(edge_adj_faces[i]);
474 edge_adj_faces[i] = NULL;
475 }
476 }
477
478 MEM_freeN(face_singularity);
479 MEM_freeN(combined_verts);
480 }
481
482 /* Create vert_adj_edges for verts. */
483 {
484 ed = orig_medge;
485 for (uint i = 0; i < numEdges; i++, ed++) {
486 if (edge_adj_faces_len[i] > 0) {
487 const uint vs[2] = {vm[ed->v1], vm[ed->v2]};
488 uint invalid_edge_index = 0;
489 bool invalid_edge_reversed = false;
490 for (uint j = 0; j < 2; j++) {
491 const uint vert = vs[j];
492 const uint len = vert_adj_edges_len[vert];
493 if (len > 0) {
494 OldVertEdgeRef *old_edge_vert_ref = vert_adj_edges[vert];
495 if (old_edge_vert_ref == NULL) {
496 uint *adj_edges = MEM_calloc_arrayN(
497 len, sizeof(*adj_edges), "OldVertEdgeRef::edges in solidify");
498 adj_edges[0] = i;
499 for (uint k = 1; k < len; k++) {
500 adj_edges[k] = MOD_SOLIDIFY_EMPTY_TAG;
501 }
502 OldVertEdgeRef *ref = MEM_mallocN(sizeof(*ref), "OldVertEdgeRef in solidify");
503 *ref = (OldVertEdgeRef){adj_edges, 1};
504 vert_adj_edges[vert] = ref;
505 }
506 else {
507 const uint *f = old_edge_vert_ref->edges;
508 for (uint k = 0; k < len && k <= old_edge_vert_ref->edges_len; k++, f++) {
509 const uint edge = old_edge_vert_ref->edges[k];
510 if (edge == MOD_SOLIDIFY_EMPTY_TAG || k == old_edge_vert_ref->edges_len) {
511 old_edge_vert_ref->edges[k] = i;
512 old_edge_vert_ref->edges_len++;
513 break;
514 }
515 if (vm[orig_medge[edge].v1] == vs[1 - j]) {
516 invalid_edge_index = edge + 1;
517 invalid_edge_reversed = (j == 0);
518 break;
519 }
520 if (vm[orig_medge[edge].v2] == vs[1 - j]) {
521 invalid_edge_index = edge + 1;
522 invalid_edge_reversed = (j == 1);
523 break;
524 }
525 }
526 if (invalid_edge_index) {
527 if (j == 1) {
528 /* Should never actually be executed. */
529 vert_adj_edges[vs[0]]->edges_len--;
530 }
531 break;
532 }
533 }
534 }
535 }
536 /* Remove zero faces that are in shape of an edge. */
537 if (invalid_edge_index) {
538 const uint tmp = invalid_edge_index - 1;
539 invalid_edge_index = i;
540 i = tmp;
541 OldEdgeFaceRef *i_adj_faces = edge_adj_faces[i];
542 OldEdgeFaceRef *invalid_adj_faces = edge_adj_faces[invalid_edge_index];
543 uint j = 0;
544 for (uint k = 0; k < i_adj_faces->faces_len; k++) {
545 for (uint l = 0; l < invalid_adj_faces->faces_len; l++) {
546 if (i_adj_faces->faces[k] == invalid_adj_faces->faces[l] &&
547 i_adj_faces->faces[k] != MOD_SOLIDIFY_EMPTY_TAG) {
548 i_adj_faces->faces[k] = MOD_SOLIDIFY_EMPTY_TAG;
549 invalid_adj_faces->faces[l] = MOD_SOLIDIFY_EMPTY_TAG;
550 j++;
551 }
552 }
553 }
554 /* remove from final face count */
555 if (do_shell) {
556 numNewPolys -= 2 * j;
557 numNewLoops -= 4 * j;
558 }
559 const uint len = i_adj_faces->faces_len + invalid_adj_faces->faces_len - 2 * j;
560 uint *adj_faces = MEM_malloc_arrayN(
561 len, sizeof(*adj_faces), "OldEdgeFaceRef::faces in solidify");
562 bool *adj_faces_loops_reversed = MEM_malloc_arrayN(
563 len, sizeof(*adj_faces_loops_reversed), "OldEdgeFaceRef::reversed in solidify");
564 /* Clean merge of adj_faces. */
565 j = 0;
566 for (uint k = 0; k < i_adj_faces->faces_len; k++) {
567 if (i_adj_faces->faces[k] != MOD_SOLIDIFY_EMPTY_TAG) {
568 adj_faces[j] = i_adj_faces->faces[k];
569 adj_faces_loops_reversed[j++] = i_adj_faces->faces_reversed[k];
570 }
571 }
572 for (uint k = 0; k < invalid_adj_faces->faces_len; k++) {
573 if (invalid_adj_faces->faces[k] != MOD_SOLIDIFY_EMPTY_TAG) {
574 adj_faces[j] = invalid_adj_faces->faces[k];
575 adj_faces_loops_reversed[j++] = (invalid_edge_reversed !=
576 invalid_adj_faces->faces_reversed[k]);
577 }
578 }
579 BLI_assert(j == len);
580 edge_adj_faces_len[invalid_edge_index] = 0;
581 edge_adj_faces_len[i] = len;
582 MEM_freeN(i_adj_faces->faces);
583 MEM_freeN(i_adj_faces->faces_reversed);
584 i_adj_faces->faces_len = len;
585 i_adj_faces->faces = adj_faces;
586 i_adj_faces->faces_reversed = adj_faces_loops_reversed;
587 i_adj_faces->used += invalid_adj_faces->used;
588 MEM_freeN(invalid_adj_faces->faces);
589 MEM_freeN(invalid_adj_faces->faces_reversed);
590 MEM_freeN(invalid_adj_faces);
591 edge_adj_faces[invalid_edge_index] = i_adj_faces;
592 /* Reset counter to continue. */
593 i = invalid_edge_index;
594 }
595 }
596 }
597 }
598
599 MEM_freeN(vert_adj_edges_len);
600
601 /* Filter duplicate polys. */
602 {
603 ed = orig_medge;
604 /* Iterate over edges and only check the faces around an edge for duplicates
605 * (performance optimization). */
606 for (uint i = 0; i < numEdges; i++, ed++) {
607 if (edge_adj_faces_len[i] > 0) {
608 const OldEdgeFaceRef *adj_faces = edge_adj_faces[i];
609 uint adj_len = adj_faces->faces_len;
610 /* Not that #adj_len doesn't need to equal edge_adj_faces_len anymore
611 * because #adj_len is shared when a face got collapsed to an edge. */
612 if (adj_len > 1) {
613 /* For each face pair check if they have equal verts. */
614 for (uint j = 0; j < adj_len; j++) {
615 const uint face = adj_faces->faces[j];
616 const int j_loopstart = orig_mpoly[face].loopstart;
617 const int totloop = orig_mpoly[face].totloop;
618 const uint j_first_v = vm[orig_mloop[j_loopstart].v];
619 for (uint k = j + 1; k < adj_len; k++) {
620 if (orig_mpoly[adj_faces->faces[k]].totloop != totloop) {
621 continue;
622 }
623 /* Find first face first loop vert in second face loops. */
624 const int k_loopstart = orig_mpoly[adj_faces->faces[k]].loopstart;
625 int l;
626 ml = orig_mloop + k_loopstart;
627 for (l = 0; l < totloop && vm[ml->v] != j_first_v; l++, ml++) {
628 /* Pass. */
629 }
630 if (l == totloop) {
631 continue;
632 }
633 /* Check if all following loops have equal verts. */
634 const bool reversed = adj_faces->faces_reversed[j] != adj_faces->faces_reversed[k];
635 const int count_dir = reversed ? -1 : 1;
636 bool has_diff = false;
637 ml = orig_mloop + j_loopstart;
638 for (int m = 0, n = l + totloop; m < totloop && !has_diff;
639 m++, n += count_dir, ml++) {
640 has_diff = has_diff || vm[ml->v] != vm[orig_mloop[k_loopstart + n % totloop].v];
641 }
642 /* If the faces are equal, discard one (j). */
643 if (!has_diff) {
644 ml = orig_mloop + j_loopstart;
645 uint del_loops = 0;
646 for (uint m = 0; m < totloop; m++, ml++) {
647 const uint e = ml->e;
648 OldEdgeFaceRef *e_adj_faces = edge_adj_faces[e];
649 if (e_adj_faces) {
650 uint face_index = j;
651 uint *e_adj_faces_faces = e_adj_faces->faces;
652 bool *e_adj_faces_reversed = e_adj_faces->faces_reversed;
653 const uint faces_len = e_adj_faces->faces_len;
654 if (e_adj_faces_faces != adj_faces->faces) {
655 /* Find index of e in #adj_faces. */
656 for (face_index = 0;
657 face_index < faces_len && e_adj_faces_faces[face_index] != face;
658 face_index++) {
659 /* Pass. */
660 }
661 /* If not found. */
662 if (face_index == faces_len) {
663 continue;
664 }
665 }
666 else {
667 /* If we shrink #edge_adj_faces[i] we need to update this field. */
668 adj_len--;
669 }
670 memmove(e_adj_faces_faces + face_index,
671 e_adj_faces_faces + face_index + 1,
672 (faces_len - face_index - 1) * sizeof(*e_adj_faces_faces));
673 memmove(e_adj_faces_reversed + face_index,
674 e_adj_faces_reversed + face_index + 1,
675 (faces_len - face_index - 1) * sizeof(*e_adj_faces_reversed));
676 e_adj_faces->faces_len--;
677 if (edge_adj_faces_len[e] > 0) {
678 edge_adj_faces_len[e]--;
679 if (edge_adj_faces_len[e] == 0) {
680 e_adj_faces->used--;
681 edge_adj_faces[e] = NULL;
682 }
683 }
684 else if (e_adj_faces->used > 1) {
685 for (uint n = 0; n < numEdges; n++) {
686 if (edge_adj_faces[n] == e_adj_faces && edge_adj_faces_len[n] > 0) {
687 edge_adj_faces_len[n]--;
688 if (edge_adj_faces_len[n] == 0) {
689 edge_adj_faces[n]->used--;
690 edge_adj_faces[n] = NULL;
691 }
692 break;
693 }
694 }
695 }
696 del_loops++;
697 }
698 }
699 if (do_shell) {
700 numNewPolys -= 2;
701 numNewLoops -= 2 * (uint)del_loops;
702 }
703 break;
704 }
705 }
706 }
707 }
708 }
709 }
710 }
711
712 /* Create #NewEdgeRef array. */
713 {
714 ed = orig_medge;
715 for (uint i = 0; i < numEdges; i++, ed++) {
716 const uint v1 = vm[ed->v1];
717 const uint v2 = vm[ed->v2];
718 if (edge_adj_faces_len[i] > 0) {
719 if (LIKELY(orig_edge_lengths[i] > FLT_EPSILON)) {
720 sub_v3_v3v3(edgedir, orig_mvert_co[v2], orig_mvert_co[v1]);
721 mul_v3_fl(edgedir, 1.0f / orig_edge_lengths[i]);
722 }
723 else {
724 /* Smart fallback. */
725 /* This makes merging non essential, but correct
726 * merging will still give way better results. */
727 float pos[3];
728 copy_v3_v3(pos, orig_mvert_co[v2]);
729
730 OldVertEdgeRef *link1 = vert_adj_edges[v1];
731 float v1_dir[3];
732 zero_v3(v1_dir);
733 for (int j = 0; j < link1->edges_len; j++) {
734 uint e = link1->edges[j];
735 if (edge_adj_faces_len[e] > 0 && e != i) {
736 uint other_v =
737 vm[vm[orig_medge[e].v1] == v1 ? orig_medge[e].v2 : orig_medge[e].v1];
738 sub_v3_v3v3(edgedir, orig_mvert_co[other_v], pos);
739 add_v3_v3(v1_dir, edgedir);
740 }
741 }
742 OldVertEdgeRef *link2 = vert_adj_edges[v2];
743 float v2_dir[3];
744 zero_v3(v2_dir);
745 for (int j = 0; j < link2->edges_len; j++) {
746 uint e = link2->edges[j];
747 if (edge_adj_faces_len[e] > 0 && e != i) {
748 uint other_v =
749 vm[vm[orig_medge[e].v1] == v2 ? orig_medge[e].v2 : orig_medge[e].v1];
750 sub_v3_v3v3(edgedir, orig_mvert_co[other_v], pos);
751 add_v3_v3(v2_dir, edgedir);
752 }
753 }
754 sub_v3_v3v3(edgedir, v2_dir, v1_dir);
755 float len = normalize_v3(edgedir);
756 if (len == 0.0f) {
757 edgedir[0] = 0.0f;
758 edgedir[1] = 0.0f;
759 edgedir[2] = 1.0f;
760 }
761 }
762
763 OldEdgeFaceRef *adj_faces = edge_adj_faces[i];
764 const uint adj_len = adj_faces->faces_len;
765 const uint *adj_faces_faces = adj_faces->faces;
766 const bool *adj_faces_reversed = adj_faces->faces_reversed;
767 uint new_edges_len = 0;
768 FaceKeyPair *sorted_faces = MEM_malloc_arrayN(
769 adj_len, sizeof(*sorted_faces), "sorted_faces in solidify");
770 if (adj_len > 1) {
771 new_edges_len = adj_len;
772 /* Get keys for sorting. */
773 float ref_nor[3] = {0, 0, 0};
774 float nor[3];
775 for (uint j = 0; j < adj_len; j++) {
776 const bool reverse = adj_faces_reversed[j];
777 const uint face_i = adj_faces_faces[j];
778 if (reverse) {
779 negate_v3_v3(nor, poly_nors[face_i]);
780 }
781 else {
782 copy_v3_v3(nor, poly_nors[face_i]);
783 }
784 float d = 1;
785 if (orig_mpoly[face_i].totloop > 3) {
786 d = project_v3_v3(nor, edgedir);
787 if (LIKELY(d != 0)) {
788 d = normalize_v3(nor);
789 }
790 else {
791 d = 1;
792 }
793 }
794 if (UNLIKELY(d == 0.0f)) {
795 sorted_faces[j].angle = 0.0f;
796 }
797 else if (j == 0) {
798 copy_v3_v3(ref_nor, nor);
799 sorted_faces[j].angle = 0.0f;
800 }
801 else {
802 float angle = angle_signed_on_axis_normalized_v3v3_v3(nor, ref_nor, edgedir);
803 sorted_faces[j].angle = -angle;
804 }
805 sorted_faces[j].face = face_sides_arr + adj_faces_faces[j] * 2 +
806 (adj_faces_reversed[j] ? 1 : 0);
807 }
808 /* Sort faces by order around the edge (keep order in faces,
809 * reversed and face_angles the same). */
810 qsort(sorted_faces, adj_len, sizeof(*sorted_faces), comp_float_int_pair);
811 }
812 else {
813 new_edges_len = 2;
814 sorted_faces[0].face = face_sides_arr + adj_faces_faces[0] * 2 +
815 (adj_faces_reversed[0] ? 1 : 0);
816 if (do_rim) {
817 /* Only add the loops parallel to the edge for now. */
818 numNewLoops += 2;
819 numNewPolys++;
820 }
821 }
822
823 /* Create a list of new edges and fill it. */
824 NewEdgeRef **new_edges = MEM_malloc_arrayN(
825 new_edges_len + 1, sizeof(*new_edges), "new_edges in solidify");
826 new_edges[new_edges_len] = NULL;
827 NewFaceRef *faces[2];
828 for (uint j = 0; j < new_edges_len; j++) {
829 float angle;
830 if (adj_len > 1) {
831 const uint next_j = j + 1 == adj_len ? 0 : j + 1;
832 faces[0] = sorted_faces[j].face;
833 faces[1] = sorted_faces[next_j].face->reversed ? sorted_faces[next_j].face - 1 :
834 sorted_faces[next_j].face + 1;
835 angle = sorted_faces[next_j].angle - sorted_faces[j].angle;
836 if (angle < 0) {
837 angle += 2 * M_PI;
838 }
839 }
840 else {
841 faces[0] = sorted_faces[0].face->reversed ? sorted_faces[0].face - j :
842 sorted_faces[0].face + j;
843 faces[1] = NULL;
844 angle = 0;
845 }
846 NewEdgeRef *edge_data = MEM_mallocN(sizeof(*edge_data), "edge_data in solidify");
847 uint edge_data_edge_index = MOD_SOLIDIFY_EMPTY_TAG;
848 if (do_shell || (adj_len == 1 && do_rim)) {
849 edge_data_edge_index = 0;
850 }
851 *edge_data = (NewEdgeRef){.old_edge = i,
852 .faces = {faces[0], faces[1]},
853 .link_edge_groups = {NULL, NULL},
854 .angle = angle,
855 .new_edge = edge_data_edge_index};
856 new_edges[j] = edge_data;
857 for (uint k = 0; k < 2; k++) {
858 if (faces[k] != NULL) {
859 ml = orig_mloop + faces[k]->face->loopstart;
860 for (int l = 0; l < faces[k]->face->totloop; l++, ml++) {
861 if (edge_adj_faces[ml->e] == edge_adj_faces[i]) {
862 if (ml->e != i && orig_edge_data_arr[ml->e] == NULL) {
863 orig_edge_data_arr[ml->e] = new_edges;
864 }
865 faces[k]->link_edges[l] = edge_data;
866 break;
867 }
868 }
869 }
870 }
871 }
872 MEM_freeN(sorted_faces);
873 orig_edge_data_arr[i] = new_edges;
874 if (do_shell || (adj_len == 1 && do_rim)) {
875 numNewEdges += new_edges_len;
876 }
877 }
878 }
879 }
880
881 for (uint i = 0; i < numEdges; i++) {
882 if (edge_adj_faces[i]) {
883 if (edge_adj_faces[i]->used > 1) {
884 edge_adj_faces[i]->used--;
885 }
886 else {
887 MEM_freeN(edge_adj_faces[i]->faces);
888 MEM_freeN(edge_adj_faces[i]->faces_reversed);
889 MEM_freeN(edge_adj_faces[i]);
890 }
891 }
892 }
893 MEM_freeN(edge_adj_faces);
894 }
895
896 /* Create sorted edge groups for every vert. */
897 {
898 OldVertEdgeRef **adj_edges_ptr = vert_adj_edges;
899 for (uint i = 0; i < numVerts; i++, adj_edges_ptr++) {
900 if (*adj_edges_ptr != NULL && (*adj_edges_ptr)->edges_len >= 2) {
901 EdgeGroup *edge_groups;
902
903 int eg_index = -1;
904 bool contains_long_groups = false;
905 uint topo_groups = 0;
906
907 /* Initial sorted creation. */
908 {
909 const uint *adj_edges = (*adj_edges_ptr)->edges;
910 const uint tot_adj_edges = (*adj_edges_ptr)->edges_len;
911
912 uint unassigned_edges_len = 0;
913 for (uint j = 0; j < tot_adj_edges; j++) {
914 NewEdgeRef **new_edges = orig_edge_data_arr[adj_edges[j]];
915 /* TODO check where the null pointer come from,
916 * because there should not be any... */
917 if (new_edges) {
918 /* count the number of new edges around the original vert */
919 while (*new_edges) {
920 unassigned_edges_len++;
921 new_edges++;
922 }
923 }
924 }
925 NewEdgeRef **unassigned_edges = MEM_malloc_arrayN(
926 unassigned_edges_len, sizeof(*unassigned_edges), "unassigned_edges in solidify");
927 for (uint j = 0, k = 0; j < tot_adj_edges; j++) {
928 NewEdgeRef **new_edges = orig_edge_data_arr[adj_edges[j]];
929 if (new_edges) {
930 while (*new_edges) {
931 unassigned_edges[k++] = *new_edges;
932 new_edges++;
933 }
934 }
935 }
936
937 /* An edge group will always contain min 2 edges
938 * so max edge group count can be calculated. */
939 uint edge_groups_len = unassigned_edges_len / 2;
940 edge_groups = MEM_calloc_arrayN(
941 edge_groups_len + 1, sizeof(*edge_groups), "edge_groups in solidify");
942
943 uint assigned_edges_len = 0;
944 NewEdgeRef *found_edge = NULL;
945 uint found_edge_index = 0;
946 bool insert_at_start = false;
947 uint eg_capacity = 5;
948 NewFaceRef *eg_track_faces[2] = {NULL, NULL};
949 NewFaceRef *last_open_edge_track = NULL;
950
951 while (assigned_edges_len < unassigned_edges_len) {
952 found_edge = NULL;
953 insert_at_start = false;
954 if (eg_index >= 0 && edge_groups[eg_index].edges_len == 0) {
955 /* Called every time a new group was started in the last iteration. */
956 /* Find an unused edge to start the next group
957 * and setup variables to start creating it. */
958 uint j = 0;
959 NewEdgeRef *edge = NULL;
960 while (!edge && j < unassigned_edges_len) {
961 edge = unassigned_edges[j++];
962 if (edge && last_open_edge_track &&
963 (edge->faces[0] != last_open_edge_track || edge->faces[1] != NULL)) {
964 edge = NULL;
965 }
966 }
967 if (!edge && last_open_edge_track) {
968 topo_groups++;
969 last_open_edge_track = NULL;
970 edge_groups[eg_index].topo_group++;
971 j = 0;
972 while (!edge && j < unassigned_edges_len) {
973 edge = unassigned_edges[j++];
974 }
975 }
976 else if (!last_open_edge_track && eg_index > 0) {
977 topo_groups++;
978 edge_groups[eg_index].topo_group++;
979 }
980 BLI_assert(edge != NULL);
981 found_edge_index = j - 1;
982 found_edge = edge;
983 if (!last_open_edge_track && vm[orig_medge[edge->old_edge].v1] == i) {
984 eg_track_faces[0] = edge->faces[0];
985 eg_track_faces[1] = edge->faces[1];
986 if (edge->faces[1] == NULL) {
987 last_open_edge_track = edge->faces[0]->reversed ? edge->faces[0] - 1 :
988 edge->faces[0] + 1;
989 }
990 }
991 else {
992 eg_track_faces[0] = edge->faces[1];
993 eg_track_faces[1] = edge->faces[0];
994 }
995 }
996 else if (eg_index >= 0) {
997 NewEdgeRef **edge_ptr = unassigned_edges;
998 for (found_edge_index = 0; found_edge_index < unassigned_edges_len;
999 found_edge_index++, edge_ptr++) {
1000 if (*edge_ptr) {
1001 NewEdgeRef *edge = *edge_ptr;
1002 if (edge->faces[0] == eg_track_faces[1]) {
1003 insert_at_start = false;
1004 eg_track_faces[1] = edge->faces[1];
1005 found_edge = edge;
1006 if (edge->faces[1] == NULL) {
1007 edge_groups[eg_index].is_orig_closed = false;
1008 last_open_edge_track = edge->faces[0]->reversed ? edge->faces[0] - 1 :
1009 edge->faces[0] + 1;
1010 }
1011 break;
1012 }
1013 if (edge->faces[0] == eg_track_faces[0]) {
1014 insert_at_start = true;
1015 eg_track_faces[0] = edge->faces[1];
1016 found_edge = edge;
1017 if (edge->faces[1] == NULL) {
1018 edge_groups[eg_index].is_orig_closed = false;
1019 }
1020 break;
1021 }
1022 if (edge->faces[1] != NULL) {
1023 if (edge->faces[1] == eg_track_faces[1]) {
1024 insert_at_start = false;
1025 eg_track_faces[1] = edge->faces[0];
1026 found_edge = edge;
1027 break;
1028 }
1029 if (edge->faces[1] == eg_track_faces[0]) {
1030 insert_at_start = true;
1031 eg_track_faces[0] = edge->faces[0];
1032 found_edge = edge;
1033 break;
1034 }
1035 }
1036 }
1037 }
1038 }
1039 if (found_edge) {
1040 unassigned_edges[found_edge_index] = NULL;
1041 assigned_edges_len++;
1042 const uint needed_capacity = edge_groups[eg_index].edges_len + 1;
1043 if (needed_capacity > eg_capacity) {
1044 eg_capacity = needed_capacity + 1;
1045 NewEdgeRef **new_eg = MEM_calloc_arrayN(
1046 eg_capacity, sizeof(*new_eg), "edge_group realloc in solidify");
1047 if (insert_at_start) {
1048 memcpy(new_eg + 1,
1049 edge_groups[eg_index].edges,
1050 edge_groups[eg_index].edges_len * sizeof(*new_eg));
1051 }
1052 else {
1053 memcpy(new_eg,
1054 edge_groups[eg_index].edges,
1055 edge_groups[eg_index].edges_len * sizeof(*new_eg));
1056 }
1057 MEM_freeN(edge_groups[eg_index].edges);
1058 edge_groups[eg_index].edges = new_eg;
1059 }
1060 else if (insert_at_start) {
1061 memmove(edge_groups[eg_index].edges + 1,
1062 edge_groups[eg_index].edges,
1063 edge_groups[eg_index].edges_len * sizeof(*edge_groups[eg_index].edges));
1064 }
1065 edge_groups[eg_index].edges[insert_at_start ? 0 : edge_groups[eg_index].edges_len] =
1066 found_edge;
1067 edge_groups[eg_index].edges_len++;
1068 if (edge_groups[eg_index].edges[edge_groups[eg_index].edges_len - 1]->faces[1] !=
1069 NULL) {
1070 last_open_edge_track = NULL;
1071 }
1072 if (edge_groups[eg_index].edges_len > 3) {
1073 contains_long_groups = true;
1074 }
1075 }
1076 else {
1077 /* called on first iteration to clean up the eg_index = -1 and start the first group,
1078 * or when the current group is found to be complete (no new found_edge) */
1079 eg_index++;
1080 BLI_assert(eg_index < edge_groups_len);
1081 eg_capacity = 5;
1082 NewEdgeRef **edges = MEM_calloc_arrayN(
1083 eg_capacity, sizeof(*edges), "edge_group in solidify");
1084 edge_groups[eg_index] = (EdgeGroup){
1085 .valid = true,
1086 .edges = edges,
1087 .edges_len = 0,
1088 .open_face_edge = MOD_SOLIDIFY_EMPTY_TAG,
1089 .is_orig_closed = true,
1090 .is_even_split = false,
1091 .split = 0,
1092 .is_singularity = false,
1093 .topo_group = topo_groups,
1094 .co = {0.0f, 0.0f, 0.0f},
1095 .no = {0.0f, 0.0f, 0.0f},
1096 .new_vert = MOD_SOLIDIFY_EMPTY_TAG,
1097 };
1098 eg_track_faces[0] = NULL;
1099 eg_track_faces[1] = NULL;
1100 }
1101 }
1102 /* #eg_index is the number of groups from here on. */
1103 eg_index++;
1104 /* #topo_groups is the number of topo groups from here on. */
1105 topo_groups++;
1106
1107 MEM_freeN(unassigned_edges);
1108
1109 /* TODO reshape the edge_groups array to its actual size
1110 * after writing is finished to save on memory. */
1111 }
1112
1113 /* Split of long self intersection groups */
1114 {
1115 uint splits = 0;
1116 if (contains_long_groups) {
1117 uint add_index = 0;
1118 for (uint j = 0; j < eg_index; j++) {
1119 const uint edges_len = edge_groups[j + add_index].edges_len;
1120 if (edges_len > 3) {
1121 bool has_doubles = false;
1122 bool *doubles = MEM_calloc_arrayN(
1123 edges_len, sizeof(*doubles), "doubles in solidify");
1124 EdgeGroup g = edge_groups[j + add_index];
1125 for (uint k = 0; k < edges_len; k++) {
1126 for (uint l = k + 1; l < edges_len; l++) {
1127 if (g.edges[k]->old_edge == g.edges[l]->old_edge) {
1128 doubles[k] = true;
1129 doubles[l] = true;
1130 has_doubles = true;
1131 }
1132 }
1133 }
1134 if (has_doubles) {
1135 const uint prior_splits = splits;
1136 const uint prior_index = add_index;
1137 int unique_start = -1;
1138 int first_unique_end = -1;
1139 int last_split = -1;
1140 int first_split = -1;
1141 bool first_even_split = false;
1142 uint real_k = 0;
1143 while (real_k < edges_len ||
1144 (g.is_orig_closed &&
1145 (real_k <=
1146 (first_unique_end == -1 ? 0 : first_unique_end) + (int)edges_len ||
1147 first_split != last_split))) {
1148 const uint k = real_k % edges_len;
1149 if (!doubles[k]) {
1150 if (first_unique_end != -1 && unique_start == -1) {
1151 unique_start = (int)real_k;
1152 }
1153 }
1154 else if (first_unique_end == -1) {
1155 first_unique_end = (int)k;
1156 }
1157 else if (unique_start != -1) {
1158 const uint split = (((uint)unique_start + real_k + 1) / 2) % edges_len;
1159 const bool is_even_split = (((uint)unique_start + real_k) & 1);
1160 if (last_split != -1) {
1161 /* Override g on first split (no insert). */
1162 if (prior_splits != splits) {
1163 memmove(edge_groups + j + add_index + 1,
1164 edge_groups + j + add_index,
1165 ((uint)eg_index - j) * sizeof(*edge_groups));
1166 add_index++;
1167 }
1168 if (last_split > split) {
1169 const uint size = (split + edges_len) - (uint)last_split;
1170 NewEdgeRef **edges = MEM_malloc_arrayN(
1171 size, sizeof(*edges), "edge_group split in solidify");
1172 memcpy(edges,
1173 g.edges + last_split,
1174 (edges_len - (uint)last_split) * sizeof(*edges));
1175 memcpy(edges + (edges_len - (uint)last_split),
1176 g.edges,
1177 split * sizeof(*edges));
1178 edge_groups[j + add_index] = (EdgeGroup){
1179 .valid = true,
1180 .edges = edges,
1181 .edges_len = size,
1182 .open_face_edge = MOD_SOLIDIFY_EMPTY_TAG,
1183 .is_orig_closed = g.is_orig_closed,
1184 .is_even_split = is_even_split,
1185 .split = add_index - prior_index + 1 + (uint)!g.is_orig_closed,
1186 .is_singularity = false,
1187 .topo_group = g.topo_group,
1188 .co = {0.0f, 0.0f, 0.0f},
1189 .no = {0.0f, 0.0f, 0.0f},
1190 .new_vert = MOD_SOLIDIFY_EMPTY_TAG,
1191 };
1192 }
1193 else {
1194 const uint size = split - (uint)last_split;
1195 NewEdgeRef **edges = MEM_malloc_arrayN(
1196 size, sizeof(*edges), "edge_group split in solidify");
1197 memcpy(edges, g.edges + last_split, size * sizeof(*edges));
1198 edge_groups[j + add_index] = (EdgeGroup){
1199 .valid = true,
1200 .edges = edges,
1201 .edges_len = size,
1202 .open_face_edge = MOD_SOLIDIFY_EMPTY_TAG,
1203 .is_orig_closed = g.is_orig_closed,
1204 .is_even_split = is_even_split,
1205 .split = add_index - prior_index + 1 + (uint)!g.is_orig_closed,
1206 .is_singularity = false,
1207 .topo_group = g.topo_group,
1208 .co = {0.0f, 0.0f, 0.0f},
1209 .no = {0.0f, 0.0f, 0.0f},
1210 .new_vert = MOD_SOLIDIFY_EMPTY_TAG,
1211 };
1212 }
1213 splits++;
1214 }
1215 last_split = (int)split;
1216 if (first_split == -1) {
1217 first_split = (int)split;
1218 first_even_split = is_even_split;
1219 }
1220 unique_start = -1;
1221 }
1222 real_k++;
1223 }
1224 if (first_split != -1) {
1225 if (!g.is_orig_closed) {
1226 if (prior_splits != splits) {
1227 memmove(edge_groups + (j + prior_index + 1),
1228 edge_groups + (j + prior_index),
1229 ((uint)eg_index + add_index - (j + prior_index)) *
1230 sizeof(*edge_groups));
1231 memmove(edge_groups + (j + add_index + 2),
1232 edge_groups + (j + add_index + 1),
1233 ((uint)eg_index - j) * sizeof(*edge_groups));
1234 add_index++;
1235 }
1236 else {
1237 memmove(edge_groups + (j + add_index + 2),
1238 edge_groups + (j + add_index + 1),
1239 ((uint)eg_index - j - 1) * sizeof(*edge_groups));
1240 }
1241 NewEdgeRef **edges = MEM_malloc_arrayN(
1242 (uint)first_split, sizeof(*edges), "edge_group split in solidify");
1243 memcpy(edges, g.edges, (uint)first_split * sizeof(*edges));
1244 edge_groups[j + prior_index] = (EdgeGroup){
1245 .valid = true,
1246 .edges = edges,
1247 .edges_len = (uint)first_split,
1248 .open_face_edge = MOD_SOLIDIFY_EMPTY_TAG,
1249 .is_orig_closed = g.is_orig_closed,
1250 .is_even_split = first_even_split,
1251 .split = 1,
1252 .is_singularity = false,
1253 .topo_group = g.topo_group,
1254 .co = {0.0f, 0.0f, 0.0f},
1255 .no = {0.0f, 0.0f, 0.0f},
1256 .new_vert = MOD_SOLIDIFY_EMPTY_TAG,
1257 };
1258 add_index++;
1259 splits++;
1260 edges = MEM_malloc_arrayN(edges_len - (uint)last_split,
1261 sizeof(*edges),
1262 "edge_group split in solidify");
1263 memcpy(edges,
1264 g.edges + last_split,
1265 (edges_len - (uint)last_split) * sizeof(*edges));
1266 edge_groups[j + add_index] = (EdgeGroup){
1267 .valid = true,
1268 .edges = edges,
1269 .edges_len = (edges_len - (uint)last_split),
1270 .open_face_edge = MOD_SOLIDIFY_EMPTY_TAG,
1271 .is_orig_closed = g.is_orig_closed,
1272 .is_even_split = false,
1273 .split = add_index - prior_index + 1,
1274 .is_singularity = false,
1275 .topo_group = g.topo_group,
1276 .co = {0.0f, 0.0f, 0.0f},
1277 .no = {0.0f, 0.0f, 0.0f},
1278 .new_vert = MOD_SOLIDIFY_EMPTY_TAG,
1279 };
1280 }
1281 if (prior_splits != splits) {
1282 MEM_freeN(g.edges);
1283 }
1284 }
1285 if (first_unique_end != -1 && prior_splits == splits) {
1286 has_singularities = true;
1287 edge_groups[j + add_index].is_singularity = true;
1288 }
1289 }
1290 MEM_freeN(doubles);
1291 }
1292 }
1293 }
1294 }
1295
1296 orig_vert_groups_arr[i] = edge_groups;
1297 /* Count new edges, loops, polys and add to link_edge_groups. */
1298 {
1299 uint new_verts = 0;
1300 bool contains_open_splits = false;
1301 uint open_edges = 0;
1302 uint contains_splits = 0;
1303 uint last_added = 0;
1304 uint first_added = 0;
1305 bool first_set = false;
1306 for (EdgeGroup *g = edge_groups; g->valid; g++) {
1307 NewEdgeRef **e = g->edges;
1308 for (uint j = 0; j < g->edges_len; j++, e++) {
1309 const uint flip = (uint)(vm[orig_medge[(*e)->old_edge].v2] == i);
1310 BLI_assert(flip || vm[orig_medge[(*e)->old_edge].v1] == i);
1311 (*e)->link_edge_groups[flip] = g;
1312 }
1313 uint added = 0;
1314 if (do_shell || (do_rim && !g->is_orig_closed)) {
1315 BLI_assert(g->new_vert == MOD_SOLIDIFY_EMPTY_TAG);
1316 g->new_vert = numNewVerts++;
1317 if (do_rim || (do_shell && g->split)) {
1318 new_verts++;
1319 contains_splits += (g->split != 0);
1320 contains_open_splits |= g->split && !g->is_orig_closed;
1321 added = g->split;
1322 }
1323 }
1324 open_edges += (uint)(added < last_added);
1325 if (!first_set) {
1326 first_set = true;
1327 first_added = added;
1328 }
1329 last_added = added;
1330 if (!(g + 1)->valid || g->topo_group != (g + 1)->topo_group) {
1331 if (new_verts > 2) {
1332 numNewPolys++;
1333 numNewEdges += new_verts;
1334 open_edges += (uint)(first_added < last_added);
1335 open_edges -= (uint)(open_edges && !contains_open_splits);
1336 if (do_shell && do_rim) {
1337 numNewLoops += new_verts * 2;
1338 }
1339 else if (do_shell) {
1340 numNewLoops += new_verts * 2 - open_edges;
1341 }
1342 else { // do_rim
1343 numNewLoops += new_verts * 2 + open_edges - contains_splits;
1344 }
1345 }
1346 else if (new_verts == 2) {
1347 numNewEdges++;
1348 numNewLoops += 2u - (uint)(!(do_rim && do_shell) && contains_open_splits);
1349 }
1350 new_verts = 0;
1351 contains_open_splits = false;
1352 contains_splits = 0;
1353 open_edges = 0;
1354 last_added = 0;
1355 first_added = 0;
1356 first_set = false;
1357 }
1358 }
1359 }
1360 }
1361 }
1362 }
1363
1364 /* Free vert_adj_edges memory. */
1365 {
1366 uint i = 0;
1367 for (OldVertEdgeRef **p = vert_adj_edges; i < numVerts; i++, p++) {
1368 if (*p) {
1369 MEM_freeN((*p)->edges);
1370 MEM_freeN(*p);
1371 }
1372 }
1373 MEM_freeN(vert_adj_edges);
1374 }
1375
1376 /* TODO create_regions if fix_intersections. */
1377
1378 /* General use pointer for #EdgeGroup iteration. */
1379 EdgeGroup **gs_ptr;
1380
1381 /* Calculate EdgeGroup vertex coordinates. */
1382 {
1383 float *face_weight = NULL;
1384
1385 if (do_flat_faces) {
1386 face_weight = MEM_malloc_arrayN(numPolys, sizeof(*face_weight), "face_weight in solidify");
1387
1388 mp = orig_mpoly;
1389 for (uint i = 0; i < numPolys; i++, mp++) {
1390 float scalar_vgroup = 1.0f;
1391 int loopend = mp->loopstart + mp->totloop;
1392 ml = orig_mloop + mp->loopstart;
1393 for (int j = mp->loopstart; j < loopend; j++, ml++) {
1394 MDeformVert *dv = &dvert[ml->v];
1395 if (defgrp_invert) {
1396 scalar_vgroup = min_ff(1.0f - BKE_defvert_find_weight(dv, defgrp_index),
1397 scalar_vgroup);
1398 }
1399 else {
1400 scalar_vgroup = min_ff(BKE_defvert_find_weight(dv, defgrp_index), scalar_vgroup);
1401 }
1402 }
1403 scalar_vgroup = offset_fac_vg + (scalar_vgroup * offset_fac_vg_inv);
1404 face_weight[i] = scalar_vgroup;
1405 }
1406 }
1407
1408 mv = orig_mvert;
1409 gs_ptr = orig_vert_groups_arr;
1410 for (uint i = 0; i < numVerts; i++, mv++, gs_ptr++) {
1411 if (*gs_ptr) {
1412 EdgeGroup *g = *gs_ptr;
1413 for (uint j = 0; g->valid; j++, g++) {
1414 if (!g->is_singularity) {
1415 float *nor = g->no;
1416 float move_nor[3] = {0, 0, 0};
1417 bool disable_boundary_fix = (smd->nonmanifold_boundary_mode ==
1418 MOD_SOLIDIFY_NONMANIFOLD_BOUNDARY_MODE_NONE ||
1419 (g->is_orig_closed || g->split));
1420 /* Constraints Method. */
1421 if (smd->nonmanifold_offset_mode == MOD_SOLIDIFY_NONMANIFOLD_OFFSET_MODE_CONSTRAINTS) {
1422 NewEdgeRef *first_edge = NULL;
1423 NewEdgeRef **edge_ptr = g->edges;
1424 /* Contains normal and offset [nx, ny, nz, ofs]. */
1425 float(*normals_queue)[4] = MEM_malloc_arrayN(
1426 g->edges_len + 1, sizeof(*normals_queue), "normals_queue in solidify");
1427 uint queue_index = 0;
1428
1429 float face_nors[3][3];
1430 float nor_ofs[3];
1431
1432 const bool cycle = (g->is_orig_closed && !g->split) || g->is_even_split;
1433 for (uint k = 0; k < g->edges_len; k++, edge_ptr++) {
1434 if (!(k & 1) || (!cycle && k == g->edges_len - 1)) {
1435 NewEdgeRef *edge = *edge_ptr;
1436 for (uint l = 0; l < 2; l++) {
1437 NewFaceRef *face = edge->faces[l];
1438 if (face && (first_edge == NULL ||
1439 (first_edge->faces[0] != face && first_edge->faces[1] != face))) {
1440 float ofs = face->reversed ? ofs_back_clamped : ofs_front_clamped;
1441 /* Use face_weight here to make faces thinner. */
1442 if (do_flat_faces) {
1443 ofs *= face_weight[face->index];
1444 }
1445
1446 if (!null_faces[face->index]) {
1447 /* And normal to the queue. */
1448 mul_v3_v3fl(normals_queue[queue_index],
1449 poly_nors[face->index],
1450 face->reversed ? -1 : 1);
1451 normals_queue[queue_index++][3] = ofs;
1452 }
1453 else {
1454 /* Just use this approximate normal of the null face if there is no other
1455 * normal to use. */
1456 mul_v3_v3fl(face_nors[0], poly_nors[face->index], face->reversed ? -1 : 1);
1457 nor_ofs[0] = ofs;
1458 }
1459 }
1460 }
1461 if ((cycle && k == 0) || (!cycle && k + 3 >= g->edges_len)) {
1462 first_edge = edge;
1463 }
1464 }
1465 }
1466 uint face_nors_len = 0;
1467 const float stop_explosion = 0.999f - fabsf(smd->offset_fac) * 0.05f;
1468 while (queue_index > 0) {
1469 if (face_nors_len == 0) {
1470 if (queue_index <= 2) {
1471 for (uint k = 0; k < queue_index; k++) {
1472 copy_v3_v3(face_nors[k], normals_queue[k]);
1473 nor_ofs[k] = normals_queue[k][3];
1474 }
1475 face_nors_len = queue_index;
1476 queue_index = 0;
1477 }
1478 else {
1479 /* Find most different two normals. */
1480 float min_p = 2;
1481 uint min_n0 = 0;
1482 uint min_n1 = 0;
1483 for (uint k = 0; k < queue_index; k++) {
1484 for (uint m = k + 1; m < queue_index; m++) {
1485 float p = dot_v3v3(normals_queue[k], normals_queue[m]);
1486 if (p <= min_p + FLT_EPSILON) {
1487 min_p = p;
1488 min_n0 = m;
1489 min_n1 = k;
1490 }
1491 }
1492 }
1493 copy_v3_v3(face_nors[0], normals_queue[min_n0]);
1494 copy_v3_v3(face_nors[1], normals_queue[min_n1]);
1495 nor_ofs[0] = normals_queue[min_n0][3];
1496 nor_ofs[1] = normals_queue[min_n1][3];
1497 face_nors_len = 2;
1498 queue_index--;
1499 memmove(normals_queue + min_n0,
1500 normals_queue + min_n0 + 1,
1501 (queue_index - min_n0) * sizeof(*normals_queue));
1502 queue_index--;
1503 memmove(normals_queue + min_n1,
1504 normals_queue + min_n1 + 1,
1505 (queue_index - min_n1) * sizeof(*normals_queue));
1506 min_p = 1;
1507 min_n1 = 0;
1508 float max_p = -1;
1509 for (uint k = 0; k < queue_index; k++) {
1510 max_p = -1;
1511 for (uint m = 0; m < face_nors_len; m++) {
1512 float p = dot_v3v3(face_nors[m], normals_queue[k]);
1513 if (p > max_p + FLT_EPSILON) {
1514 max_p = p;
1515 }
1516 }
1517 if (max_p <= min_p + FLT_EPSILON) {
1518 min_p = max_p;
1519 min_n1 = k;
1520 }
1521 }
1522 if (min_p < 0.8) {
1523 copy_v3_v3(face_nors[2], normals_queue[min_n1]);
1524 nor_ofs[2] = normals_queue[min_n1][3];
1525 face_nors_len++;
1526 queue_index--;
1527 memmove(normals_queue + min_n1,
1528 normals_queue + min_n1 + 1,
1529 (queue_index - min_n1) * sizeof(*normals_queue));
1530 }
1531 }
1532 }
1533 else {
1534 uint best = 0;
1535 uint best_group = 0;
1536 float best_p = -1.0f;
1537 for (uint k = 0; k < queue_index; k++) {
1538 for (uint m = 0; m < face_nors_len; m++) {
1539 float p = dot_v3v3(face_nors[m], normals_queue[k]);
1540 if (p > best_p + FLT_EPSILON) {
1541 best_p = p;
1542 best = m;
1543 best_group = k;
1544 }
1545 }
1546 }
1547 add_v3_v3(face_nors[best], normals_queue[best_group]);
1548 normalize_v3(face_nors[best]);
1549 nor_ofs[best] = (nor_ofs[best] + normals_queue[best_group][3]) * 0.5f;
1550 queue_index--;
1551 memmove(normals_queue + best_group,
1552 normals_queue + best_group + 1,
1553 (queue_index - best_group) * sizeof(*normals_queue));
1554 }
1555 }
1556 MEM_freeN(normals_queue);
1557
1558 /* When up to 3 constraint normals are found. */
1559 if (ELEM(face_nors_len, 2, 3)) {
1560 const float q = dot_v3v3(face_nors[0], face_nors[1]);
1561 float d = 1.0f - q * q;
1562 cross_v3_v3v3(move_nor, face_nors[0], face_nors[1]);
1563 if (d > FLT_EPSILON * 10 && q < stop_explosion) {
1564 d = 1.0f / d;
1565 mul_v3_fl(face_nors[0], (nor_ofs[0] - nor_ofs[1] * q) * d);
1566 mul_v3_fl(face_nors[1], (nor_ofs[1] - nor_ofs[0] * q) * d);
1567 }
1568 else {
1569 d = 1.0f / (fabsf(q) + 1.0f);
1570 mul_v3_fl(face_nors[0], nor_ofs[0] * d);
1571 mul_v3_fl(face_nors[1], nor_ofs[1] * d);
1572 }
1573 add_v3_v3v3(nor, face_nors[0], face_nors[1]);
1574 if (face_nors_len == 3) {
1575 float *free_nor = move_nor;
1576 mul_v3_fl(face_nors[2], nor_ofs[2]);
1577 d = dot_v3v3(face_nors[2], free_nor);
1578 if (LIKELY(fabsf(d) > FLT_EPSILON)) {
1579 sub_v3_v3v3(face_nors[0], nor, face_nors[2]); /* Override face_nor[0]. */
1580 mul_v3_fl(free_nor, dot_v3v3(face_nors[2], face_nors[0]) / d);
1581 sub_v3_v3(nor, free_nor);
1582 }
1583 disable_boundary_fix = true;
1584 }
1585 }
1586 else {
1587 BLI_assert(face_nors_len < 2);
1588 mul_v3_v3fl(nor, face_nors[0], nor_ofs[0]);
1589 disable_boundary_fix = true;
1590 }
1591 }
1592 /* Fixed/Even Method. */
1593 else {
1594 float total_angle = 0;
1595 float total_angle_back = 0;
1596 NewEdgeRef *first_edge = NULL;
1597 NewEdgeRef **edge_ptr = g->edges;
1598 float face_nor[3];
1599 float nor_back[3] = {0, 0, 0};
1600 bool has_back = false;
1601 bool has_front = false;
1602 bool cycle = (g->is_orig_closed && !g->split) || g->is_even_split;
1603 for (uint k = 0; k < g->edges_len; k++, edge_ptr++) {
1604 if (!(k & 1) || (!cycle && k == g->edges_len - 1)) {
1605 NewEdgeRef *edge = *edge_ptr;
1606 for (uint l = 0; l < 2; l++) {
1607 NewFaceRef *face = edge->faces[l];
1608 if (face && (first_edge == NULL ||
1609 (first_edge->faces[0] != face && first_edge->faces[1] != face))) {
1610 float angle = 1.0f;
1611 float ofs = face->reversed ? -ofs_back_clamped : ofs_front_clamped;
1612 /* Use face_weight here to make faces thinner. */
1613 if (do_flat_faces) {
1614 ofs *= face_weight[face->index];
1615 }
1616
1617 if (smd->nonmanifold_offset_mode ==
1618 MOD_SOLIDIFY_NONMANIFOLD_OFFSET_MODE_EVEN) {
1619 MLoop *ml_next = orig_mloop + face->face->loopstart;
1620 ml = ml_next + (face->face->totloop - 1);
1621 MLoop *ml_prev = ml - 1;
1622 for (int m = 0; m < face->face->totloop && vm[ml->v] != i;
1623 m++, ml_next++) {
1624 ml_prev = ml;
1625 ml = ml_next;
1626 }
1627 angle = angle_v3v3v3(orig_mvert_co[vm[ml_prev->v]],
1628 orig_mvert_co[i],
1629 orig_mvert_co[vm[ml_next->v]]);
1630 if (face->reversed) {
1631 total_angle_back += angle * ofs * ofs;
1632 }
1633 else {
1634 total_angle += angle * ofs * ofs;
1635 }
1636 }
1637 else {
1638 if (face->reversed) {
1639 total_angle_back++;
1640 }
1641 else {
1642 total_angle++;
1643 }
1644 }
1645 mul_v3_v3fl(face_nor, poly_nors[face->index], angle * ofs);
1646 if (face->reversed) {
1647 add_v3_v3(nor_back, face_nor);
1648 has_back = true;
1649 }
1650 else {
1651 add_v3_v3(nor, face_nor);
1652 has_front = true;
1653 }
1654 }
1655 }
1656 if ((cycle && k == 0) || (!cycle && k + 3 >= g->edges_len)) {
1657 first_edge = edge;
1658 }
1659 }
1660 }
1661
1662 /* Set normal length with selected method. */
1663 if (smd->nonmanifold_offset_mode == MOD_SOLIDIFY_NONMANIFOLD_OFFSET_MODE_EVEN) {
1664 if (has_front) {
1665 float length_sq = len_squared_v3(nor);
1666 if (LIKELY(length_sq > FLT_EPSILON)) {
1667 mul_v3_fl(nor, total_angle / length_sq);
1668 }
1669 }
1670 if (has_back) {
1671 float length_sq = len_squared_v3(nor_back);
1672 if (LIKELY(length_sq > FLT_EPSILON)) {
1673 mul_v3_fl(nor_back, total_angle_back / length_sq);
1674 }
1675 if (!has_front) {
1676 copy_v3_v3(nor, nor_back);
1677 }
1678 }
1679 if (has_front && has_back) {
1680 float nor_length = len_v3(nor);
1681 float nor_back_length = len_v3(nor_back);
1682 float q = dot_v3v3(nor, nor_back);
1683 if (LIKELY(fabsf(q) > FLT_EPSILON)) {
1684 q /= nor_length * nor_back_length;
1685 }
1686 float d = 1.0f - q * q;
1687 if (LIKELY(d > FLT_EPSILON)) {
1688 d = 1.0f / d;
1689 if (LIKELY(nor_length > FLT_EPSILON)) {
1690 mul_v3_fl(nor, (1 - nor_back_length * q / nor_length) * d);
1691 }
1692 if (LIKELY(nor_back_length > FLT_EPSILON)) {
1693 mul_v3_fl(nor_back, (1 - nor_length * q / nor_back_length) * d);
1694 }
1695 add_v3_v3(nor, nor_back);
1696 }
1697 else {
1698 mul_v3_fl(nor, 0.5f);
1699 mul_v3_fl(nor_back, 0.5f);
1700 add_v3_v3(nor, nor_back);
1701 }
1702 }
1703 }
1704 else {
1705 if (has_front && total_angle > FLT_EPSILON) {
1706 mul_v3_fl(nor, 1.0f / total_angle);
1707 }
1708 if (has_back && total_angle_back > FLT_EPSILON) {
1709 mul_v3_fl(nor_back, 1.0f / total_angle_back);
1710 add_v3_v3(nor, nor_back);
1711 if (has_front && total_angle > FLT_EPSILON) {
1712 mul_v3_fl(nor, 0.5f);
1713 }
1714 }
1715 }
1716 /* Set move_nor for boundary fix. */
1717 if (!disable_boundary_fix && g->edges_len > 2) {
1718 edge_ptr = g->edges + 1;
1719 float tmp[3];
1720 uint k;
1721 for (k = 1; k + 1 < g->edges_len; k++, edge_ptr++) {
1722 MEdge *e = orig_medge + (*edge_ptr)->old_edge;
1723 sub_v3_v3v3(
1724 tmp, orig_mvert_co[vm[e->v1] == i ? e->v2 : e->v1], orig_mvert_co[i]);
1725 add_v3_v3(move_nor, tmp);
1726 }
1727 if (k == 1) {
1728 disable_boundary_fix = true;
1729 }
1730 else {
1731 disable_boundary_fix = normalize_v3(move_nor) == 0.0f;
1732 }
1733 }
1734 else {
1735 disable_boundary_fix = true;
1736 }
1737 }
1738 /* Fix boundary verts. */
1739 if (!disable_boundary_fix) {
1740 /* Constraint normal, nor * constr_nor == 0 after this fix. */
1741 float constr_nor[3];
1742 MEdge *e0_edge = orig_medge + g->edges[0]->old_edge;
1743 MEdge *e1_edge = orig_medge + g->edges[g->edges_len - 1]->old_edge;
1744 float e0[3];
1745 float e1[3];
1746 sub_v3_v3v3(e0,
1747 orig_mvert_co[vm[e0_edge->v1] == i ? e0_edge->v2 : e0_edge->v1],
1748 orig_mvert_co[i]);
1749 sub_v3_v3v3(e1,
1750 orig_mvert_co[vm[e1_edge->v1] == i ? e1_edge->v2 : e1_edge->v1],
1751 orig_mvert_co[i]);
1752 if (smd->nonmanifold_boundary_mode == MOD_SOLIDIFY_NONMANIFOLD_BOUNDARY_MODE_FLAT) {
1753 cross_v3_v3v3(constr_nor, e0, e1);
1754 }
1755 else {
1756 float f0[3];
1757 float f1[3];
1758 if (g->edges[0]->faces[0]->reversed) {
1759 negate_v3_v3(f0, poly_nors[g->edges[0]->faces[0]->index]);
1760 }
1761 else {
1762 copy_v3_v3(f0, poly_nors[g->edges[0]->faces[0]->index]);
1763 }
1764 if (g->edges[g->edges_len - 1]->faces[0]->reversed) {
1765 negate_v3_v3(f1, poly_nors[g->edges[g->edges_len - 1]->faces[0]->index]);
1766 }
1767 else {
1768 copy_v3_v3(f1, poly_nors[g->edges[g->edges_len - 1]->faces[0]->index]);
1769 }
1770 float n0[3];
1771 float n1[3];
1772 cross_v3_v3v3(n0, e0, f0);
1773 cross_v3_v3v3(n1, f1, e1);
1774 normalize_v3(n0);
1775 normalize_v3(n1);
1776 add_v3_v3v3(constr_nor, n0, n1);
1777 }
1778 float d = dot_v3v3(constr_nor, move_nor);
1779 if (LIKELY(fabsf(d) > FLT_EPSILON)) {
1780 mul_v3_fl(move_nor, dot_v3v3(constr_nor, nor) / d);
1781 sub_v3_v3(nor, move_nor);
1782 }
1783 }
1784 float scalar_vgroup = 1;
1785 /* Use vertex group. */
1786 if (dvert && !do_flat_faces) {
1787 MDeformVert *dv = &dvert[i];
1788 if (defgrp_invert) {
1789 scalar_vgroup = 1.0f - BKE_defvert_find_weight(dv, defgrp_index);
1790 }
1791 else {
1792 scalar_vgroup = BKE_defvert_find_weight(dv, defgrp_index);
1793 }
1794 scalar_vgroup = offset_fac_vg + (scalar_vgroup * offset_fac_vg_inv);
1795 }
1796 /* Do clamping. */
1797 if (do_clamp) {
1798 if (do_angle_clamp) {
1799 if (g->edges_len > 2) {
1800 float min_length = 0;
1801 float angle = 0.5f * M_PI;
1802 uint k = 0;
1803 for (NewEdgeRef **p = g->edges; k < g->edges_len; k++, p++) {
1804 float length = orig_edge_lengths[(*p)->old_edge];
1805 float e_ang = (*p)->angle;
1806 if (e_ang > angle) {
1807 angle = e_ang;
1808 }
1809 if (length < min_length || k == 0) {
1810 min_length = length;
1811 }
1812 }
1813 float cos_ang = cosf(angle * 0.5f);
1814 if (cos_ang > 0) {
1815 float max_off = min_length * 0.5f / cos_ang;
1816 if (max_off < offset * 0.5f) {
1817 scalar_vgroup *= max_off / offset * 2;
1818 }
1819 }
1820 }
1821 }
1822 else {
1823 float min_length = 0;
1824 uint k = 0;
1825 for (NewEdgeRef **p = g->edges; k < g->edges_len; k++, p++) {
1826 float length = orig_edge_lengths[(*p)->old_edge];
1827 if (length < min_length || k == 0) {
1828 min_length = length;
1829 }
1830 }
1831 if (min_length < offset) {
1832 scalar_vgroup *= min_length / offset;
1833 }
1834 }
1835 }
1836 mul_v3_fl(nor, scalar_vgroup);
1837 add_v3_v3v3(g->co, nor, orig_mvert_co[i]);
1838 }
1839 else {
1840 copy_v3_v3(g->co, orig_mvert_co[i]);
1841 }
1842 }
1843 }
1844 }
1845
1846 if (do_flat_faces) {
1847 MEM_freeN(face_weight);
1848 }
1849 }
1850
1851 MEM_freeN(orig_mvert_co);
1852 if (null_faces) {
1853 MEM_freeN(null_faces);
1854 }
1855
1856 /* TODO create vertdata for intersection fixes (intersection fixing per topology region). */
1857
1858 /* Correction for adjacent one sided groups around a vert to
1859 * prevent edge duplicates and null polys. */
1860 uint(*singularity_edges)[2] = NULL;
1861 uint totsingularity = 0;
1862 if (has_singularities) {
1863 has_singularities = false;
1864 uint i = 0;
1865 uint singularity_edges_len = 1;
1866 singularity_edges = MEM_malloc_arrayN(
1867 singularity_edges_len, sizeof(*singularity_edges), "singularity_edges in solidify");
1868 for (NewEdgeRef ***new_edges = orig_edge_data_arr; i < numEdges; i++, new_edges++) {
1869 if (*new_edges && (do_shell || edge_adj_faces_len[i] == 1) && (**new_edges)->old_edge == i) {
1870 for (NewEdgeRef **l = *new_edges; *l; l++) {
1871 if ((*l)->link_edge_groups[0]->is_singularity &&
1872 (*l)->link_edge_groups[1]->is_singularity) {
1873 const uint v1 = (*l)->link_edge_groups[0]->new_vert;
1874 const uint v2 = (*l)->link_edge_groups[1]->new_vert;
1875 bool exists_already = false;
1876 uint j = 0;
1877 for (uint(*p)[2] = singularity_edges; j < totsingularity; p++, j++) {
1878 if (((*p)[0] == v1 && (*p)[1] == v2) || ((*p)[0] == v2 && (*p)[1] == v1)) {
1879 exists_already = true;
1880 break;
1881 }
1882 }
1883 if (!exists_already) {
1884 has_singularities = true;
1885 if (singularity_edges_len <= totsingularity) {
1886 singularity_edges_len = totsingularity + 1;
1887 singularity_edges = MEM_reallocN_id(singularity_edges,
1888 singularity_edges_len *
1889 sizeof(*singularity_edges),
1890 "singularity_edges in solidify");
1891 }
1892 singularity_edges[totsingularity][0] = v1;
1893 singularity_edges[totsingularity][1] = v2;
1894 totsingularity++;
1895 if (edge_adj_faces_len[i] == 1 && do_rim) {
1896 numNewLoops -= 2;
1897 numNewPolys--;
1898 }
1899 }
1900 else {
1901 numNewEdges--;
1902 }
1903 }
1904 }
1905 }
1906 }
1907 }
1908
1909 /* Create Mesh *result with proper capacity. */
1910 result = BKE_mesh_new_nomain_from_template(
1911 mesh, (int)(numNewVerts), (int)(numNewEdges), 0, (int)(numNewLoops), (int)(numNewPolys));
1912
1913 mpoly = result->mpoly;
1914 mloop = result->mloop;
1915 medge = result->medge;
1916 mvert = result->mvert;
1917
1918 int *origindex_edge = CustomData_get_layer(&result->edata, CD_ORIGINDEX);
1919 int *origindex_poly = CustomData_get_layer(&result->pdata, CD_ORIGINDEX);
1920
1921 if (bevel_convex != 0.0f) {
1922 /* make sure bweight is enabled */
1923 result->cd_flag |= ME_CDFLAG_EDGE_BWEIGHT;
1924 }
1925
1926 /* Checks that result has dvert data. */
1927 if (shell_defgrp_index != -1 || rim_defgrp_index != -1) {
1928 dvert = CustomData_duplicate_referenced_layer(&result->vdata, CD_MDEFORMVERT, result->totvert);
1929 /* If no vertices were ever added to an object's vgroup, dvert might be NULL. */
1930 if (dvert == NULL) {
1931 /* Add a valid data layer! */
1932 dvert = CustomData_add_layer(
1933 &result->vdata, CD_MDEFORMVERT, CD_CALLOC, NULL, result->totvert);
1934 }
1935 result->dvert = dvert;
1936 }
1937
1938 /* Make_new_verts. */
1939 {
1940 gs_ptr = orig_vert_groups_arr;
1941 for (uint i = 0; i < numVerts; i++, gs_ptr++) {
1942 EdgeGroup *gs = *gs_ptr;
1943 if (gs) {
1944 EdgeGroup *g = gs;
1945 for (uint j = 0; g->valid; j++, g++) {
1946 if (g->new_vert != MOD_SOLIDIFY_EMPTY_TAG) {
1947 CustomData_copy_data(&mesh->vdata, &result->vdata, (int)i, (int)g->new_vert, 1);
1948 copy_v3_v3(mvert[g->new_vert].co, g->co);
1949 mvert[g->new_vert].flag = orig_mvert[i].flag;
1950 }
1951 }
1952 }
1953 }
1954 }
1955
1956 result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
1957
1958 /* Make edges. */
1959 {
1960 uint i = 0;
1961 edge_index += totsingularity;
1962 for (NewEdgeRef ***new_edges = orig_edge_data_arr; i < numEdges; i++, new_edges++) {
1963 if (*new_edges && (do_shell || edge_adj_faces_len[i] == 1) && (**new_edges)->old_edge == i) {
1964 for (NewEdgeRef **l = *new_edges; *l; l++) {
1965 if ((*l)->new_edge != MOD_SOLIDIFY_EMPTY_TAG) {
1966 const uint v1 = (*l)->link_edge_groups[0]->new_vert;
1967 const uint v2 = (*l)->link_edge_groups[1]->new_vert;
1968 uint insert = edge_index;
1969 if (has_singularities && ((*l)->link_edge_groups[0]->is_singularity &&
1970 (*l)->link_edge_groups[1]->is_singularity)) {
1971 uint j = 0;
1972 for (uint(*p)[2] = singularity_edges; j < totsingularity; p++, j++) {
1973 if (((*p)[0] == v1 && (*p)[1] == v2) || ((*p)[0] == v2 && (*p)[1] == v1)) {
1974 insert = j;
1975 break;
1976 }
1977 }
1978 BLI_assert(insert == j);
1979 }
1980 else {
1981 edge_index++;
1982 }
1983 CustomData_copy_data(&mesh->edata, &result->edata, (int)i, (int)insert, 1);
1984 BLI_assert(v1 != MOD_SOLIDIFY_EMPTY_TAG);
1985 BLI_assert(v2 != MOD_SOLIDIFY_EMPTY_TAG);
1986 medge[insert].v1 = v1;
1987 medge[insert].v2 = v2;
1988 medge[insert].flag = orig_medge[(*l)->old_edge].flag | ME_EDGEDRAW | ME_EDGERENDER;
1989 medge[insert].crease = orig_medge[(*l)->old_edge].crease;
1990 medge[insert].bweight = orig_medge[(*l)->old_edge].bweight;
1991 if (bevel_convex != 0.0f && (*l)->faces[1] != NULL) {
1992 medge[insert].bweight = (char)clamp_i(
1993 (int)medge[insert].bweight + (int)(((*l)->angle > M_PI + FLT_EPSILON ?
1994 clamp_f(bevel_convex, 0.0f, 1.0f) :
1995 ((*l)->angle < M_PI - FLT_EPSILON ?
1996 clamp_f(bevel_convex, -1.0f, 0.0f) :
1997 0)) *
1998 255),
1999 0,
2000 255);
2001 }
2002 (*l)->new_edge = insert;
2003 }
2004 }
2005 }
2006 }
2007 }
2008 if (singularity_edges) {
2009 MEM_freeN(singularity_edges);
2010 }
2011
2012 /* DEBUG CODE FOR BUG-FIXING (can not be removed because every bug-fix needs this badly!). */
2013 #if 0
2014 {
2015 /* this code will output the content of orig_vert_groups_arr.
2016 * in orig_vert_groups_arr these conditions must be met for every vertex:
2017 * - new_edge value should have no duplicates
2018 * - every old_edge value should appear twice
2019 * - every group should have at least two members (edges)
2020 * Note: that there can be vertices that only have one group. They are called singularities.
2021 * These vertices will only have one side (there is no way of telling apart front
2022 * from back like on a mobius strip)
2023 */
2024
2025 /* Debug output format:
2026 * <original vertex id>:
2027 * {
2028 * { <old edge id>/<new edge id>, } \
2029 * (tg:<topology group id>)(s:<is split group>,c:<is closed group (before splitting)>)
2030 * }
2031 */
2032 gs_ptr = orig_vert_groups_arr;
2033 for (uint i = 0; i < numVerts; i++, gs_ptr++) {
2034 EdgeGroup *gs = *gs_ptr;
2035 /* check if the vertex is present (may be dissolved because of proximity) */
2036 if (gs) {
2037 printf("%d:\n", i);
2038 for (EdgeGroup *g = gs; g->valid; g++) {
2039 NewEdgeRef **e = g->edges;
2040 for (uint j = 0; j < g->edges_len; j++, e++) {
2041 printf("%u/%d, ", (*e)->old_edge, (int)(*e)->new_edge);
2042 }
2043 printf("(tg:%u)(s:%u,c:%d)\n", g->topo_group, g->split, g->is_orig_closed);
2044 }
2045 }
2046 }
2047 }
2048 #endif
2049
2050 /* Make boundary edges/faces. */
2051 {
2052 gs_ptr = orig_vert_groups_arr;
2053 mv = orig_mvert;
2054 for (uint i = 0; i < numVerts; i++, gs_ptr++, mv++) {
2055 EdgeGroup *gs = *gs_ptr;
2056 if (gs) {
2057 EdgeGroup *g = gs;
2058 EdgeGroup *g2 = gs;
2059 EdgeGroup *last_g = NULL;
2060 EdgeGroup *first_g = NULL;
2061 /* Data calculation cache. */
2062 char max_crease;
2063 char last_max_crease = 0;
2064 char first_max_crease = 0;
2065 char max_bweight;
2066 char last_max_bweight = 0;
2067 char first_max_bweight = 0;
2068 short flag;
2069 short last_flag = 0;
2070 short first_flag = 0;
2071 for (uint j = 0; g->valid; g++) {
2072 if ((do_rim && !g->is_orig_closed) || (do_shell && g->split)) {
2073 max_crease = 0;
2074 max_bweight = 0;
2075 flag = 0;
2076
2077 BLI_assert(g->edges_len >= 2);
2078
2079 if (g->edges_len == 2) {
2080 max_crease = min_cc(orig_medge[g->edges[0]->old_edge].crease,
2081 orig_medge[g->edges[1]->old_edge].crease);
2082 }
2083 else {
2084 for (uint k = 1; k < g->edges_len - 1; k++) {
2085 ed = orig_medge + g->edges[k]->old_edge;
2086 if (ed->crease > max_crease) {
2087 max_crease = ed->crease;
2088 }
2089 if (g->edges[k]->new_edge != MOD_SOLIDIFY_EMPTY_TAG) {
2090 char bweight = medge[g->edges[k]->new_edge].bweight;
2091 if (bweight > max_bweight) {
2092 max_bweight = bweight;
2093 }
2094 }
2095 flag |= ed->flag;
2096 }
2097 }
2098
2099 const char bweight_open_edge = min_cc(
2100 orig_medge[g->edges[0]->old_edge].bweight,
2101 orig_medge[g->edges[g->edges_len - 1]->old_edge].bweight);
2102 if (bweight_open_edge > 0) {
2103 max_bweight = min_cc(bweight_open_edge, max_bweight);
2104 }
2105 else {
2106 if (bevel_convex < 0.0f) {
2107 max_bweight = 0;
2108 }
2109 }
2110 if (!first_g) {
2111 first_g = g;
2112 first_max_crease = max_crease;
2113 first_max_bweight = max_bweight;
2114 first_flag = flag;
2115 }
2116 else {
2117 last_g->open_face_edge = edge_index;
2118 CustomData_copy_data(&mesh->edata,
2119 &result->edata,
2120 (int)last_g->edges[0]->old_edge,
2121 (int)edge_index,
2122 1);
2123 if (origindex_edge) {
2124 origindex_edge[edge_index] = ORIGINDEX_NONE;
2125 }
2126 medge[edge_index].v1 = last_g->new_vert;
2127 medge[edge_index].v2 = g->new_vert;
2128 medge[edge_index].flag = ME_EDGEDRAW | ME_EDGERENDER |
2129 ((last_flag | flag) & (ME_SEAM | ME_SHARP));
2130 medge[edge_index].crease = min_cc(last_max_crease, max_crease);
2131 medge[edge_index++].bweight = max_cc(mv->bweight,
2132 min_cc(last_max_bweight, max_bweight));
2133 }
2134 last_g = g;
2135 last_max_crease = max_crease;
2136 last_max_bweight = max_bweight;
2137 last_flag = flag;
2138 j++;
2139 }
2140 if (!(g + 1)->valid || g->topo_group != (g + 1)->topo_group) {
2141 if (j == 2) {
2142 last_g->open_face_edge = edge_index - 1;
2143 }
2144 if (j > 2) {
2145 CustomData_copy_data(&mesh->edata,
2146 &result->edata,
2147 (int)last_g->edges[0]->old_edge,
2148 (int)edge_index,
2149 1);
2150 if (origindex_edge) {
2151 origindex_edge[edge_index] = ORIGINDEX_NONE;
2152 }
2153 last_g->open_face_edge = edge_index;
2154 medge[edge_index].v1 = last_g->new_vert;
2155 medge[edge_index].v2 = first_g->new_vert;
2156 medge[edge_index].flag = ME_EDGEDRAW | ME_EDGERENDER |
2157 ((last_flag | first_flag) & (ME_SEAM | ME_SHARP));
2158 medge[edge_index].crease = min_cc(last_max_crease, first_max_crease);
2159 medge[edge_index++].bweight = max_cc(mv->bweight,
2160 min_cc(last_max_bweight, first_max_bweight));
2161
2162 /* Loop data. */
2163 int *loops = MEM_malloc_arrayN(j, sizeof(*loops), "loops in solidify");
2164 /* The #mat_nr is from consensus. */
2165 short most_mat_nr = 0;
2166 uint most_mat_nr_face = 0;
2167 uint most_mat_nr_count = 0;
2168 for (short l = 0; l < mat_nrs; l++) {
2169 uint count = 0;
2170 uint face = 0;
2171 uint k = 0;
2172 for (EdgeGroup *g3 = g2; g3->valid && k < j; g3++) {
2173 if ((do_rim && !g3->is_orig_closed) || (do_shell && g3->split)) {
2174 /* Check both far ends in terms of faces of an edge group. */
2175 if (g3->edges[0]->faces[0]->face->mat_nr == l) {
2176 face = g3->edges[0]->faces[0]->index;
2177 count++;
2178 }
2179 NewEdgeRef *le = g3->edges[g3->edges_len - 1];
2180 if (le->faces[1] && le->faces[1]->face->mat_nr == l) {
2181 face = le->faces[1]->index;
2182 count++;
2183 }
2184 else if (!le->faces[1] && le->faces[0]->face->mat_nr == l) {
2185 face = le->faces[0]->index;
2186 count++;
2187 }
2188 k++;
2189 }
2190 }
2191 if (count > most_mat_nr_count) {
2192 most_mat_nr = l;
2193 most_mat_nr_face = face;
2194 most_mat_nr_count = count;
2195 }
2196 }
2197 CustomData_copy_data(
2198 &mesh->pdata, &result->pdata, (int)most_mat_nr_face, (int)poly_index, 1);
2199 if (origindex_poly) {
2200 origindex_poly[poly_index] = ORIGINDEX_NONE;
2201 }
2202 mpoly[poly_index].loopstart = (int)loop_index;
2203 mpoly[poly_index].totloop = (int)j;
2204 mpoly[poly_index].mat_nr = most_mat_nr +
2205 (g->is_orig_closed || !do_rim ? 0 : mat_ofs_rim);
2206 CLAMP(mpoly[poly_index].mat_nr, 0, mat_nr_max);
2207 mpoly[poly_index].flag = orig_mpoly[most_mat_nr_face].flag;
2208 poly_index++;
2209
2210 for (uint k = 0; g2->valid && k < j; g2++) {
2211 if ((do_rim && !g2->is_orig_closed) || (do_shell && g2->split)) {
2212 MPoly *face = g2->edges[0]->faces[0]->face;
2213 ml = orig_mloop + face->loopstart;
2214 for (int l = 0; l < face->totloop; l++, ml++) {
2215 if (vm[ml->v] == i) {
2216 loops[k] = face->loopstart + l;
2217 break;
2218 }
2219 }
2220 k++;
2221 }
2222 }
2223
2224 if (!do_flip) {
2225 for (uint k = 0; k < j; k++) {
2226 CustomData_copy_data(&mesh->ldata, &result->ldata, loops[k], (int)loop_index, 1);
2227 mloop[loop_index].v = medge[edge_index - j + k].v1;
2228 mloop[loop_index++].e = edge_index - j + k;
2229 }
2230 }
2231 else {
2232 for (uint k = 1; k <= j; k++) {
2233 CustomData_copy_data(
2234 &mesh->ldata, &result->ldata, loops[j - k], (int)loop_index, 1);
2235 mloop[loop_index].v = medge[edge_index - k].v2;
2236 mloop[loop_index++].e = edge_index - k;
2237 }
2238 }
2239 MEM_freeN(loops);
2240 }
2241 /* Reset everything for the next poly. */
2242 j = 0;
2243 last_g = NULL;
2244 first_g = NULL;
2245 last_max_crease = 0;
2246 first_max_crease = 0;
2247 last_max_bweight = 0;
2248 first_max_bweight = 0;
2249 last_flag = 0;
2250 first_flag = 0;
2251 }
2252 }
2253 }
2254 }
2255 }
2256
2257 /* Make boundary faces. */
2258 if (do_rim) {
2259 for (uint i = 0; i < numEdges; i++) {
2260 if (edge_adj_faces_len[i] == 1 && orig_edge_data_arr[i] &&
2261 (*orig_edge_data_arr[i])->old_edge == i) {
2262 NewEdgeRef **new_edges = orig_edge_data_arr[i];
2263
2264 NewEdgeRef *edge1 = new_edges[0];
2265 NewEdgeRef *edge2 = new_edges[1];
2266 const bool v1_singularity = edge1->link_edge_groups[0]->is_singularity &&
2267 edge2->link_edge_groups[0]->is_singularity;
2268 const bool v2_singularity = edge1->link_edge_groups[1]->is_singularity &&
2269 edge2->link_edge_groups[1]->is_singularity;
2270 if (v1_singularity && v2_singularity) {
2271 continue;
2272 }
2273
2274 MPoly *face = (*new_edges)->faces[0]->face;
2275 CustomData_copy_data(
2276 &mesh->pdata, &result->pdata, (int)(*new_edges)->faces[0]->index, (int)poly_index, 1);
2277 mpoly[poly_index].loopstart = (int)loop_index;
2278 mpoly[poly_index].totloop = 4 - (int)(v1_singularity || v2_singularity);
2279 mpoly[poly_index].mat_nr = face->mat_nr + mat_ofs_rim;
2280 CLAMP(mpoly[poly_index].mat_nr, 0, mat_nr_max);
2281 mpoly[poly_index].flag = face->flag;
2282 poly_index++;
2283
2284 int loop1 = -1;
2285 int loop2 = -1;
2286 ml = orig_mloop + face->loopstart;
2287 const uint old_v1 = vm[orig_medge[edge1->old_edge].v1];
2288 const uint old_v2 = vm[orig_medge[edge1->old_edge].v2];
2289 for (uint j = 0; j < face->totloop; j++, ml++) {
2290 if (vm[ml->v] == old_v1) {
2291 loop1 = face->loopstart + (int)j;
2292 }
2293 else if (vm[ml->v] == old_v2) {
2294 loop2 = face->loopstart + (int)j;
2295 }
2296 }
2297 BLI_assert(loop1 != -1 && loop2 != -1);
2298 MEdge *open_face_edge;
2299 uint open_face_edge_index;
2300 if (!do_flip) {
2301 if (rim_defgrp_index != -1) {
2302 BKE_defvert_ensure_index(&result->dvert[medge[edge1->new_edge].v1], rim_defgrp_index)
2303 ->weight = 1.0f;
2304 }
2305 CustomData_copy_data(&mesh->ldata, &result->ldata, loop1, (int)loop_index, 1);
2306 mloop[loop_index].v = medge[edge1->new_edge].v1;
2307 mloop[loop_index++].e = edge1->new_edge;
2308
2309 if (!v2_singularity) {
2310 open_face_edge_index = edge1->link_edge_groups[1]->open_face_edge;
2311 if (rim_defgrp_index != -1) {
2312 BKE_defvert_ensure_index(&result->dvert[medge[edge1->new_edge].v2], rim_defgrp_index)
2313 ->weight = 1.0f;
2314 }
2315 CustomData_copy_data(&mesh->ldata, &result->ldata, loop2, (int)loop_index, 1);
2316 mloop[loop_index].v = medge[edge1->new_edge].v2;
2317 open_face_edge = medge + open_face_edge_index;
2318 if (ELEM(medge[edge2->new_edge].v2, open_face_edge->v1, open_face_edge->v2)) {
2319 mloop[loop_index++].e = open_face_edge_index;
2320 }
2321 else {
2322 mloop[loop_index++].e = edge2->link_edge_groups[1]->open_face_edge;
2323 }
2324 }
2325
2326 if (rim_defgrp_index != -1) {
2327 BKE_defvert_ensure_index(&result->dvert[medge[edge2->new_edge].v2], rim_defgrp_index)
2328 ->weight = 1.0f;
2329 }
2330 CustomData_copy_data(&mesh->ldata, &result->ldata, loop2, (int)loop_index, 1);
2331 mloop[loop_index].v = medge[edge2->new_edge].v2;
2332 mloop[loop_index++].e = edge2->new_edge;
2333
2334 if (!v1_singularity) {
2335 open_face_edge_index = edge2->link_edge_groups[0]->open_face_edge;
2336 if (rim_defgrp_index != -1) {
2337 BKE_defvert_ensure_index(&result->dvert[medge[edge2->new_edge].v1], rim_defgrp_index)
2338 ->weight = 1.0f;
2339 }
2340 CustomData_copy_data(&mesh->ldata, &result->ldata, loop1, (int)loop_index, 1);
2341 mloop[loop_index].v = medge[edge2->new_edge].v1;
2342 open_face_edge = medge + open_face_edge_index;
2343 if (ELEM(medge[edge1->new_edge].v1, open_face_edge->v1, open_face_edge->v2)) {
2344 mloop[loop_index++].e = open_face_edge_index;
2345 }
2346 else {
2347 mloop[loop_index++].e = edge1->link_edge_groups[0]->open_face_edge;
2348 }
2349 }
2350 }
2351 else {
2352 if (!v1_singularity) {
2353 open_face_edge_index = edge1->link_edge_groups[0]->open_face_edge;
2354 if (rim_defgrp_index != -1) {
2355 BKE_defvert_ensure_index(&result->dvert[medge[edge1->new_edge].v1], rim_defgrp_index)
2356 ->weight = 1.0f;
2357 }
2358 CustomData_copy_data(&mesh->ldata, &result->ldata, loop1, (int)loop_index, 1);
2359 mloop[loop_index].v = medge[edge1->new_edge].v1;
2360 open_face_edge = medge + open_face_edge_index;
2361 if (ELEM(medge[edge2->new_edge].v1, open_face_edge->v1, open_face_edge->v2)) {
2362 mloop[loop_index++].e = open_face_edge_index;
2363 }
2364 else {
2365 mloop[loop_index++].e = edge2->link_edge_groups[0]->open_face_edge;
2366 }
2367 }
2368
2369 if (rim_defgrp_index != -1) {
2370 BKE_defvert_ensure_index(&result->dvert[medge[edge2->new_edge].v1], rim_defgrp_index)
2371 ->weight = 1.0f;
2372 }
2373 CustomData_copy_data(&mesh->ldata, &result->ldata, loop1, (int)loop_index, 1);
2374 mloop[loop_index].v = medge[edge2->new_edge].v1;
2375 mloop[loop_index++].e = edge2->new_edge;
2376
2377 if (!v2_singularity) {
2378 open_face_edge_index = edge2->link_edge_groups[1]->open_face_edge;
2379 if (rim_defgrp_index != -1) {
2380 BKE_defvert_ensure_index(&result->dvert[medge[edge2->new_edge].v2], rim_defgrp_index)
2381 ->weight = 1.0f;
2382 }
2383 CustomData_copy_data(&mesh->ldata, &result->ldata, loop2, (int)loop_index, 1);
2384 mloop[loop_index].v = medge[edge2->new_edge].v2;
2385 open_face_edge = medge + open_face_edge_index;
2386 if (ELEM(medge[edge1->new_edge].v2, open_face_edge->v1, open_face_edge->v2)) {
2387 mloop[loop_index++].e = open_face_edge_index;
2388 }
2389 else {
2390 mloop[loop_index++].e = edge1->link_edge_groups[1]->open_face_edge;
2391 }
2392 }
2393
2394 if (rim_defgrp_index != -1) {
2395 BKE_defvert_ensure_index(&result->dvert[medge[edge1->new_edge].v2], rim_defgrp_index)
2396 ->weight = 1.0f;
2397 }
2398 CustomData_copy_data(&mesh->ldata, &result->ldata, loop2, (int)loop_index, 1);
2399 mloop[loop_index].v = medge[edge1->new_edge].v2;
2400 mloop[loop_index++].e = edge1->new_edge;
2401 }
2402 }
2403 }
2404 }
2405
2406 /* Make faces. */
2407 if (do_shell) {
2408 NewFaceRef *fr = face_sides_arr;
2409 uint *face_loops = MEM_malloc_arrayN(
2410 largest_ngon * 2, sizeof(*face_loops), "face_loops in solidify");
2411 uint *face_verts = MEM_malloc_arrayN(
2412 largest_ngon * 2, sizeof(*face_verts), "face_verts in solidify");
2413 uint *face_edges = MEM_malloc_arrayN(
2414 largest_ngon * 2, sizeof(*face_edges), "face_edges in solidify");
2415 for (uint i = 0; i < numPolys * 2; i++, fr++) {
2416 const uint loopstart = (uint)fr->face->loopstart;
2417 uint totloop = (uint)fr->face->totloop;
2418 uint valid_edges = 0;
2419 uint k = 0;
2420 while (totloop > 0 && (!fr->link_edges[totloop - 1] ||
2421 fr->link_edges[totloop - 1]->new_edge == MOD_SOLIDIFY_EMPTY_TAG)) {
2422 totloop--;
2423 }
2424 if (totloop > 0) {
2425 NewEdgeRef *prior_edge = fr->link_edges[totloop - 1];
2426 uint prior_flip = (uint)(vm[orig_medge[prior_edge->old_edge].v1] ==
2427 vm[orig_mloop[loopstart + (totloop - 1)].v]);
2428 for (uint j = 0; j < totloop; j++) {
2429 NewEdgeRef *new_edge = fr->link_edges[j];
2430 if (new_edge && new_edge->new_edge != MOD_SOLIDIFY_EMPTY_TAG) {
2431 valid_edges++;
2432 const uint flip = (uint)(vm[orig_medge[new_edge->old_edge].v2] ==
2433 vm[orig_mloop[loopstart + j].v]);
2434 BLI_assert(flip ||
2435 vm[orig_medge[new_edge->old_edge].v1] == vm[orig_mloop[loopstart + j].v]);
2436 /* The vert thats in the current loop. */
2437 const uint new_v1 = new_edge->link_edge_groups[flip]->new_vert;
2438 /* The vert thats in the next loop. */
2439 const uint new_v2 = new_edge->link_edge_groups[1 - flip]->new_vert;
2440 if (k == 0 || face_verts[k - 1] != new_v1) {
2441 face_loops[k] = loopstart + j;
2442 if (fr->reversed) {
2443 face_edges[k] = prior_edge->link_edge_groups[prior_flip]->open_face_edge;
2444 }
2445 else {
2446 face_edges[k] = new_edge->link_edge_groups[flip]->open_face_edge;
2447 }
2448 BLI_assert(k == 0 || medge[face_edges[k]].v2 == face_verts[k - 1] ||
2449 medge[face_edges[k]].v1 == face_verts[k - 1]);
2450 BLI_assert(face_edges[k] == MOD_SOLIDIFY_EMPTY_TAG ||
2451 medge[face_edges[k]].v2 == new_v1 || medge[face_edges[k]].v1 == new_v1);
2452 face_verts[k++] = new_v1;
2453 }
2454 prior_edge = new_edge;
2455 prior_flip = 1 - flip;
2456 if (j < totloop - 1 || face_verts[0] != new_v2) {
2457 face_loops[k] = loopstart + (j + 1) % totloop;
2458 face_edges[k] = new_edge->new_edge;
2459 face_verts[k++] = new_v2;
2460 }
2461 else {
2462 face_edges[0] = new_edge->new_edge;
2463 }
2464 }
2465 }
2466 if (k > 2 && valid_edges > 2) {
2467 CustomData_copy_data(&mesh->pdata, &result->pdata, (int)(i / 2), (int)poly_index, 1);
2468 mpoly[poly_index].loopstart = (int)loop_index;
2469 mpoly[poly_index].totloop = (int)k;
2470 mpoly[poly_index].mat_nr = fr->face->mat_nr + (fr->reversed != do_flip ? mat_ofs : 0);
2471 CLAMP(mpoly[poly_index].mat_nr, 0, mat_nr_max);
2472 mpoly[poly_index].flag = fr->face->flag;
2473 if (fr->reversed != do_flip) {
2474 for (int l = (int)k - 1; l >= 0; l--) {
2475 if (shell_defgrp_index != -1) {
2476 BKE_defvert_ensure_index(&result->dvert[face_verts[l]], shell_defgrp_index)
2477 ->weight = 1.0f;
2478 }
2479 CustomData_copy_data(
2480 &mesh->ldata, &result->ldata, (int)face_loops[l], (int)loop_index, 1);
2481 mloop[loop_index].v = face_verts[l];
2482 mloop[loop_index++].e = face_edges[l];
2483 }
2484 }
2485 else {
2486 uint l = k - 1;
2487 for (uint next_l = 0; next_l < k; next_l++) {
2488 CustomData_copy_data(
2489 &mesh->ldata, &result->ldata, (int)face_loops[l], (int)loop_index, 1);
2490 mloop[loop_index].v = face_verts[l];
2491 mloop[loop_index++].e = face_edges[next_l];
2492 l = next_l;
2493 }
2494 }
2495 poly_index++;
2496 }
2497 }
2498 }
2499 MEM_freeN(face_loops);
2500 MEM_freeN(face_verts);
2501 MEM_freeN(face_edges);
2502 }
2503 if (edge_index != numNewEdges) {
2504 BKE_modifier_set_error(
2505 md, "Internal Error: edges array wrong size: %u instead of %u", numNewEdges, edge_index);
2506 }
2507 if (poly_index != numNewPolys) {
2508 BKE_modifier_set_error(
2509 md, "Internal Error: polys array wrong size: %u instead of %u", numNewPolys, poly_index);
2510 }
2511 if (loop_index != numNewLoops) {
2512 BKE_modifier_set_error(
2513 md, "Internal Error: loops array wrong size: %u instead of %u", numNewLoops, loop_index);
2514 }
2515 BLI_assert(edge_index == numNewEdges);
2516 BLI_assert(poly_index == numNewPolys);
2517 BLI_assert(loop_index == numNewLoops);
2518
2519 /* Free remaining memory */
2520 {
2521 MEM_freeN(vm);
2522 MEM_freeN(edge_adj_faces_len);
2523 uint i = 0;
2524 for (EdgeGroup **p = orig_vert_groups_arr; i < numVerts; i++, p++) {
2525 if (*p) {
2526 for (EdgeGroup *eg = *p; eg->valid; eg++) {
2527 MEM_freeN(eg->edges);
2528 }
2529 MEM_freeN(*p);
2530 }
2531 }
2532 MEM_freeN(orig_vert_groups_arr);
2533 i = numEdges;
2534 for (NewEdgeRef ***p = orig_edge_data_arr + (numEdges - 1); i > 0; i--, p--) {
2535 if (*p && (**p)->old_edge == i - 1) {
2536 for (NewEdgeRef **l = *p; *l; l++) {
2537 MEM_freeN(*l);
2538 }
2539 MEM_freeN(*p);
2540 }
2541 }
2542 MEM_freeN(orig_edge_data_arr);
2543 MEM_freeN(orig_edge_lengths);
2544 i = 0;
2545 for (NewFaceRef *p = face_sides_arr; i < numPolys * 2; i++, p++) {
2546 MEM_freeN(p->link_edges);
2547 }
2548 MEM_freeN(face_sides_arr);
2549 MEM_freeN(poly_nors);
2550 }
2551
2552 #undef MOD_SOLIDIFY_EMPTY_TAG
2553
2554 return result;
2555 }
2556
2557 /** \} */
2558