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