Blender V5.3
MOD_skin.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/* Implementation based in part off the paper "B-Mesh: A Fast Modeling
10 * System for Base Meshes of 3D Articulated Shapes" (Zhongping Ji,
11 * Ligang Liu, Yigang Wang)
12 *
13 * Note that to avoid confusion with Blender's BMesh data structure,
14 * this tool is renamed as the Skin modifier.
15 *
16 * The B-Mesh paper is current available here:
17 * http://www.math.zju.edu.cn/ligangliu/CAGD/Projects/BMesh/
18 *
19 * The main missing features in this code compared to the paper are:
20 *
21 * - No mesh evolution. The paper suggests iteratively subdivision-surfacing the
22 * skin output and adapting the output to better conform with the
23 * spheres of influence surrounding each vertex.
24 *
25 * - No mesh fairing. The paper suggests re-aligning output edges to
26 * follow principal mesh curvatures.
27 *
28 * - No auxiliary balls. These would serve to influence mesh
29 * evolution, which as noted above is not implemented.
30 *
31 * The code also adds some features not present in the paper:
32 *
33 * + Loops in the input edge graph.
34 *
35 * + Concave surfaces around branch nodes. The paper does not discuss
36 * how to handle non-convex regions; this code adds a number of
37 * cleanup operations to handle many (though not all) of these
38 * cases.
39 */
40
41#include <algorithm>
42
43#include "MEM_guardedalloc.h"
44
45#include "BLI_array_utils.hh"
46#include "BLI_bitmap.hh"
47#include "BLI_enum_flags.hh"
48#include "BLI_heap_simple.hh"
49#include "BLI_math_geom_c.hh"
50#include "BLI_math_matrix_c.hh"
51#include "BLI_stack_c.hh"
52#include "BLI_vector.hh"
53
54#include "BLT_translation.hh"
55
56#include "DNA_mesh_types.h"
57#include "DNA_meshdata_types.h"
58#include "DNA_modifier_types.h"
59#include "DNA_screen_types.h"
60
62#include "BKE_deform.hh"
63#include "BKE_lib_id.hh"
64#include "BKE_mesh.hh"
65#include "BKE_mesh_mapping.hh"
66#include "BKE_modifier.hh"
67
69#include "UI_resources.hh"
70
71#include "RNA_access.hh"
72#include "RNA_prototypes.hh"
73
74#include "WM_types.hh" /* For skin mark clear operator UI. */
75
76#include "MOD_ui_common.hh"
77
78#include "bmesh.hh"
79
80namespace blender {
81
82/* -------------------------------------------------------------------- */
85
87{
88 BMIter iter;
89 BMFace *f;
90 BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
91 f->no[0] = FLT_MAX;
92 }
93}
94
96{
97 BMIter iter;
98 BMFace *f;
99 BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
100 if (f->no[0] == FLT_MAX) {
102 }
103 }
104}
105
109static void vert_array_face_normal_update(BMVert **verts, int verts_len)
110{
111 for (int i = 0; i < verts_len; i++) {
113 }
114
115 for (int i = 0; i < verts_len; i++) {
117 }
118}
119
121
122struct EMat {
123 float mat[3][3];
124 /* Vert that edge is pointing away from, no relation to
125 * edge[0] */
127};
128
136
137struct Frame {
138 /* Index in the vertex array */
140 /* Location of each corner */
141 float co[4][3];
142 /* Indicates which corners have been merged with another
143 * frame's corner (so they share a vertex index) */
144 struct {
145 /* Merge to target frame/corner (no merge if frame is null) */
146 Frame *frame;
147 int corner;
148 /* checked to avoid chaining.
149 * (merging when we're already been referenced), see #39775 */
150 uint is_target : 1;
151 } merge[4];
152
153 /* For hull frames, whether each vertex is detached or not */
154 bool inside_hull[4];
155 /* Whether any part of the frame (corner or edge) is detached */
157};
158
159#define MAX_SKIN_NODE_FRAMES 2
160struct SkinNode {
163
165
166 /* Used for hulling a loop seam */
168};
169
175
176static void add_poly(SkinOutput *so, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4);
177
178/* -------------------------------------------------------------------- */
181
182static bool is_quad_symmetric(BMVert *quad[4], const SkinModifierData *smd)
183{
184 const float threshold = 0.0001f;
185 const float threshold_squared = threshold * threshold;
186 int axis;
187
188 for (axis = 0; axis < 3; axis++) {
189 if (smd->symmetry_axes & (1 << axis)) {
190 float a[3];
191
192 copy_v3_v3(a, quad[0]->co);
193 a[axis] = -a[axis];
194
195 if (len_squared_v3v3(a, quad[1]->co) < threshold_squared) {
196 copy_v3_v3(a, quad[2]->co);
197 a[axis] = -a[axis];
198 if (len_squared_v3v3(a, quad[3]->co) < threshold_squared) {
199 return true;
200 }
201 }
202 else if (len_squared_v3v3(a, quad[3]->co) < threshold_squared) {
203 copy_v3_v3(a, quad[2]->co);
204 a[axis] = -a[axis];
205 if (len_squared_v3v3(a, quad[1]->co) < threshold_squared) {
206 return true;
207 }
208 }
209 }
210 }
211
212 return false;
213}
214
215/* Returns true if the quad crosses the plane of symmetry, false otherwise */
216static bool quad_crosses_symmetry_plane(BMVert *quad[4], const SkinModifierData *smd)
217{
218 int axis;
219
220 for (axis = 0; axis < 3; axis++) {
221 if (smd->symmetry_axes & (1 << axis)) {
222 bool left = false, right = false;
223 int i;
224
225 for (i = 0; i < 4; i++) {
226 if (quad[i]->co[axis] < 0.0f) {
227 left = true;
228 }
229 else if (quad[i]->co[axis] > 0.0f) {
230 right = true;
231 }
232
233 if (left && right) {
234 return true;
235 }
236 }
237 }
238 }
239
240 return false;
241}
242
243#ifdef WITH_BULLET
244
245/* Returns true if the frame is filled by precisely two faces (and
246 * outputs those faces to fill_faces), otherwise returns false. */
247static bool skin_frame_find_contained_faces(const Frame *frame, BMFace *fill_faces[2])
248{
249 BMEdge *diag;
250
251 /* See if the frame is bisected by a diagonal edge */
252 diag = BM_edge_exists(frame->verts[0], frame->verts[2]);
253 if (!diag) {
254 diag = BM_edge_exists(frame->verts[1], frame->verts[3]);
255 }
256
257 if (diag) {
258 return BM_edge_face_pair(diag, &fill_faces[0], &fill_faces[1]);
259 }
260
261 return false;
262}
263
264#endif
265
266/* Returns true if hull is successfully built, false otherwise */
267static bool build_hull(SkinOutput *so, Frame **frames, int totframe)
268{
269#ifdef WITH_BULLET
270 BMesh *bm = so->bm;
271 BMOperator op;
272 BMIter iter;
273 BMOIter oiter;
274 BMVert *v;
275 BMFace *f;
276 BMEdge *e;
277 int i, j;
278
280
281 for (i = 0; i < totframe; i++) {
282 for (j = 0; j < 4; j++) {
283 BM_elem_flag_enable(frames[i]->verts[j], BM_ELEM_TAG);
284 }
285 }
286
287 /* Deselect all faces so that only new hull output faces are
288 * selected after the operator is run */
290
292 bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE), "convex_hull input=%hv", BM_ELEM_TAG);
293 BMO_op_exec(bm, &op);
294
296 BMO_op_finish(bm, &op);
297 return false;
298 }
299
300 /* Apply face attributes to hull output */
301 BMO_ITER (f, &oiter, op.slots_out, "geom.out", BM_FACE) {
303 if (so->smd->flag & MOD_SKIN_SMOOTH_SHADING) {
305 }
306 f->mat_nr = so->mat_nr;
307 }
308
309 /* Mark interior frames */
310 BMO_ITER (v, &oiter, op.slots_out, "geom_interior.out", BM_VERT) {
311 for (i = 0; i < totframe; i++) {
312 Frame *frame = frames[i];
313
314 if (!frame->detached) {
315 for (j = 0; j < 4; j++) {
316 if (frame->verts[j] == v) {
317 frame->inside_hull[j] = true;
318 frame->detached = true;
319 break;
320 }
321 }
322 }
323 }
324 }
325
326 /* Also mark frames as interior if an edge is not in the hull */
327 for (i = 0; i < totframe; i++) {
328 Frame *frame = frames[i];
329
330 if (!frame->detached && (!BM_edge_exists(frame->verts[0], frame->verts[1]) ||
331 !BM_edge_exists(frame->verts[1], frame->verts[2]) ||
332 !BM_edge_exists(frame->verts[2], frame->verts[3]) ||
333 !BM_edge_exists(frame->verts[3], frame->verts[0])))
334 {
335 frame->detached = true;
336 }
337 }
338
339 /* Remove triangles that would fill the original frames -- skip if
340 * frame is partially detached */
342 for (i = 0; i < totframe; i++) {
343 Frame *frame = frames[i];
344 if (!frame->detached) {
345 BMFace *fill_faces[2];
346
347 /* Check if the frame is filled by precisely two
348 * triangles. If so, delete the triangles and their shared
349 * edge. Otherwise, give up and mark the frame as
350 * detached. */
351 if (skin_frame_find_contained_faces(frame, fill_faces)) {
352 BM_elem_flag_enable(fill_faces[0], BM_ELEM_TAG);
353 BM_elem_flag_enable(fill_faces[1], BM_ELEM_TAG);
354 }
355 else {
356 frame->detached = true;
357 }
358 }
359 }
360
361 /* Check if removing triangles above will create wire triangles,
362 * mark them too */
363 BMO_ITER (e, &oiter, op.slots_out, "geom.out", BM_EDGE) {
364 bool is_wire = true;
365 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
367 is_wire = false;
368 break;
369 }
370 }
371 if (is_wire) {
373 }
374 }
375
376 BMO_op_finish(bm, &op);
377
379
380 return true;
381#else
382 UNUSED_VARS(so, frames, totframe);
383 return false;
384#endif
385}
386
387/* Returns the average frame side length (frames are rectangular, so
388 * just the average of two adjacent edge lengths) */
389static float frame_len(const Frame *frame)
390{
391 return (len_v3v3(frame->co[0], frame->co[1]) + len_v3v3(frame->co[1], frame->co[2])) * 0.5f;
392}
393
394static void merge_frame_corners(Frame **frames, int totframe)
395{
396 float dist, side_a, side_b, thresh, mid[3];
397 int i, j, k, l;
398
399 for (i = 0; i < totframe; i++) {
400 side_a = frame_len(frames[i]);
401
402 /* For each corner of each frame... */
403 for (j = 0; j < 4; j++) {
404
405 /* Ensure the merge target is not itself a merge target */
406 if (frames[i]->merge[j].frame) {
407 continue;
408 }
409
410 for (k = i + 1; k < totframe; k++) {
411 BLI_assert(frames[i] != frames[k]);
412
413 side_b = frame_len(frames[k]);
414 thresh = min_ff(side_a, side_b) / 2.0f;
415
416 /* Compare with each corner of all other frames... */
417 for (l = 0; l < 4; l++) {
418 if (frames[k]->merge[l].frame || frames[k]->merge[l].is_target) {
419 continue;
420 }
421
422 /* Some additional concerns that could be checked
423 * further:
424 *
425 * + Vertex coords are being used for the
426 * edge-length test, but are also being
427 * modified, might cause symmetry problems.
428 *
429 * + A frame could be merged diagonally across
430 * another, would generate a weird (bad) T
431 * junction
432 */
433
434 /* Check if corners are near each other, where
435 * 'near' is based in the frames' minimum side
436 * length */
437 dist = len_v3v3(frames[i]->co[j], frames[k]->co[l]);
438 if (dist < thresh) {
439 mid_v3_v3v3(mid, frames[i]->co[j], frames[k]->co[l]);
440
441 copy_v3_v3(frames[i]->co[j], mid);
442 copy_v3_v3(frames[k]->co[l], mid);
443
444 frames[k]->merge[l].frame = frames[i];
445 frames[k]->merge[l].corner = j;
446 frames[i]->merge[j].is_target = true;
447
448 /* Can't merge another corner into the same
449 * frame corner, so move on to frame k+1 */
450 break;
451 }
452 }
453 }
454 }
455 }
456}
457
459 int v, SkinNode *frames, GroupedSpan<int> emap, const Span<int2> edges, int *tothullframe)
460{
461 SkinNode *f;
462 Frame **hull_frames;
463 int hull_frames_num, i;
464
465 (*tothullframe) = emap[v].size();
466 hull_frames = MEM_new_array_zeroed<Frame *>(*tothullframe, __func__);
467 hull_frames_num = 0;
468 for (i = 0; i < emap[v].size(); i++) {
469 const int2 &edge = edges[emap[v][i]];
470 f = &frames[bke::mesh::edge_other_vert(edge, v)];
471 /* Can't have adjacent branch nodes yet */
472 if (f->totframe) {
473 hull_frames[hull_frames_num++] = &f->frames[0];
474 }
475 else {
476 (*tothullframe)--;
477 }
478 }
479
480 return hull_frames;
481}
482
484
485/* -------------------------------------------------------------------- */
488
489static void node_frames_init(SkinNode *nf, int totframe)
490{
491 int i;
492
493 nf->totframe = totframe;
494 memset(nf->frames, 0, sizeof(nf->frames));
495
496 nf->flag = SkinNodeFlag(0);
497 for (i = 0; i < 2; i++) {
498 nf->seam_edges[i] = -1;
499 }
500}
501
502static void create_frame(
503 Frame *frame, const float co[3], const float radius[2], const float mat[3][3], float offset)
504{
505 float rx[3], ry[3], rz[3];
506 int i;
507
508 mul_v3_v3fl(ry, mat[1], radius[0]);
509 mul_v3_v3fl(rz, mat[2], radius[1]);
510
511 add_v3_v3v3(frame->co[3], co, ry);
512 add_v3_v3v3(frame->co[3], frame->co[3], rz);
513
514 sub_v3_v3v3(frame->co[2], co, ry);
515 add_v3_v3v3(frame->co[2], frame->co[2], rz);
516
517 sub_v3_v3v3(frame->co[1], co, ry);
518 sub_v3_v3v3(frame->co[1], frame->co[1], rz);
519
520 add_v3_v3v3(frame->co[0], co, ry);
521 sub_v3_v3v3(frame->co[0], frame->co[0], rz);
522
523 mul_v3_v3fl(rx, mat[0], offset);
524 for (i = 0; i < 4; i++) {
525 add_v3_v3v3(frame->co[i], frame->co[i], rx);
526 }
527}
528
529static float half_v2(const float v[2])
530{
531 return (v[0] + v[1]) * 0.5f;
532}
533
534static void end_node_frames(int v,
535 SkinNode *skin_nodes,
536 const Span<float3> vert_positions,
537 const VArray<float2> &radius,
538 GroupedSpan<int> emap,
539 EMat *emat)
540{
541 const float2 rad = radius[v];
542 float mat[3][3];
543
544 if (emap[v].is_empty()) {
545 float avg = half_v2(rad);
546
547 /* For solitary nodes, just build a box (two frames) */
548 node_frames_init(&skin_nodes[v], 2);
549 skin_nodes[v].flag |= (CAP_START | CAP_END);
550
551 /* Hardcoded basis */
552 zero_m3(mat);
553 mat[0][2] = mat[1][0] = mat[2][1] = 1;
554
555 /* Caps */
556 create_frame(&skin_nodes[v].frames[0], vert_positions[v], rad, mat, avg);
557 create_frame(&skin_nodes[v].frames[1], vert_positions[v], rad, mat, -avg);
558 }
559 else {
560 /* For nodes with an incoming edge, create a single (capped) frame */
561 node_frames_init(&skin_nodes[v], 1);
562 skin_nodes[v].flag |= CAP_START;
563
564 /* Use incoming edge for orientation */
565 copy_m3_m3(mat, emat[emap[v][0]].mat);
566 if (emat[emap[v][0]].origin != v) {
567 negate_v3(mat[0]);
568 }
569
570 Frame *frame = &skin_nodes[v].frames[0];
571
572 /* End frame */
573 create_frame(frame, vert_positions[v], rad, mat, 0);
574
575 /* The caps might need to have their normals inverted. So check if they
576 * need to be flipped when creating faces. */
577 float normal[3];
578 normal_quad_v3(normal, frame->co[0], frame->co[1], frame->co[2], frame->co[3]);
579 if (dot_v3v3(mat[0], normal) < 0.0f) {
580 skin_nodes[v].flag |= FLIP_NORMAL;
581 }
582 }
583}
584
585/* Returns 1 for seam, 0 otherwise */
586static int connection_node_mat(float mat[3][3], int v, GroupedSpan<int> emap, EMat *emat)
587{
588 float axis[3], angle, ine[3][3], oute[3][3];
589 EMat *e1, *e2;
590
591 e1 = &emat[emap[v][0]];
592 e2 = &emat[emap[v][1]];
593
594 if (e1->origin != v && e2->origin == v) {
595 copy_m3_m3(ine, e1->mat);
596 copy_m3_m3(oute, e2->mat);
597 }
598 else if (e1->origin == v && e2->origin != v) {
599 copy_m3_m3(ine, e2->mat);
600 copy_m3_m3(oute, e1->mat);
601 }
602 else {
603 return 1;
604 }
605
606 /* Get axis and angle to rotate frame by */
607 angle = angle_normalized_v3v3(ine[0], oute[0]) / 2.0f;
608 cross_v3_v3v3(axis, ine[0], oute[0]);
609 normalize_v3(axis);
610
611 /* Build frame matrix (don't care about X axis here) */
612 copy_v3_v3(mat[0], ine[0]);
613 rotate_normalized_v3_v3v3fl(mat[1], ine[1], axis, angle);
614 rotate_normalized_v3_v3v3fl(mat[2], ine[2], axis, angle);
615
616 return 0;
617}
618
619static void connection_node_frames(int v,
620 SkinNode *skin_nodes,
621 const Span<float3> vert_positions,
622 const VArray<float2> &radius,
623 GroupedSpan<int> emap,
624 EMat *emat)
625{
626 const float2 rad = radius[v];
627 float mat[3][3];
628 EMat *e1, *e2;
629
630 if (connection_node_mat(mat, v, emap, emat)) {
631 float avg = half_v2(rad);
632
633 /* Get edges */
634 e1 = &emat[emap[v][0]];
635 e2 = &emat[emap[v][1]];
636
637 /* Handle seam separately to avoid twisting */
638 /* Create two frames, will be hulled to neighbors later */
639 node_frames_init(&skin_nodes[v], 2);
640 skin_nodes[v].flag |= SEAM_FRAME;
641
642 copy_m3_m3(mat, e1->mat);
643 if (e1->origin != v) {
644 negate_v3(mat[0]);
645 }
646 create_frame(&skin_nodes[v].frames[0], vert_positions[v], rad, mat, avg);
647 skin_nodes[v].seam_edges[0] = emap[v][0];
648
649 copy_m3_m3(mat, e2->mat);
650 if (e2->origin != v) {
651 negate_v3(mat[0]);
652 }
653 create_frame(&skin_nodes[v].frames[1], vert_positions[v], rad, mat, avg);
654 skin_nodes[v].seam_edges[1] = emap[v][1];
655
656 return;
657 }
658
659 /* Build regular frame */
660 node_frames_init(&skin_nodes[v], 1);
661 create_frame(&skin_nodes[v].frames[0], vert_positions[v], rad, mat, 0);
662}
663
664static SkinNode *build_frames(const Span<float3> vert_positions,
665 int verts_num,
666 const VArray<float2> &radius,
667 GroupedSpan<int> emap,
668 EMat *emat)
669{
670 int v;
671
672 SkinNode *skin_nodes = MEM_new_array_zeroed<SkinNode>(verts_num, __func__);
673
674 for (v = 0; v < verts_num; v++) {
675 if (emap[v].size() <= 1) {
676 end_node_frames(v, skin_nodes, vert_positions, radius, emap, emat);
677 }
678 else if (emap[v].size() == 2) {
679 connection_node_frames(v, skin_nodes, vert_positions, radius, emap, emat);
680 }
681 else {
682 /* Branch node generates no frames */
683 }
684 }
685
686 return skin_nodes;
687}
688
690
691/* -------------------------------------------------------------------- */
694
695static void calc_edge_mat(float mat[3][3], const float a[3], const float b[3])
696{
697 const float z_up[3] = {0, 0, 1};
698 float dot;
699
700 /* X = edge direction */
701 sub_v3_v3v3(mat[0], b, a);
702 normalize_v3(mat[0]);
703
704 dot = dot_v3v3(mat[0], z_up);
705 if (dot > -1 + FLT_EPSILON && dot < 1 - FLT_EPSILON) {
706 /* Y = Z cross x */
707 cross_v3_v3v3(mat[1], z_up, mat[0]);
708 normalize_v3(mat[1]);
709
710 /* Z = x cross y */
711 cross_v3_v3v3(mat[2], mat[0], mat[1]);
712 normalize_v3(mat[2]);
713 }
714 else {
715 mat[1][0] = 1;
716 mat[1][1] = 0;
717 mat[1][2] = 0;
718 mat[2][0] = 0;
719 mat[2][1] = 1;
720 mat[2][2] = 0;
721 }
722}
723
725 float mat[3][3];
727 int e;
728};
729
730static void build_emats_stack(BLI_Stack *stack,
731 BLI_bitmap *visited_e,
732 EMat *emat,
733 GroupedSpan<int> emap,
734 const Span<int2> edges,
735 const VArray<bool> &is_root,
736 const Span<float3> vert_positions)
737{
738 EdgeStackElem stack_elem;
739 float axis[3], angle;
740 int i, e, v, parent_v, parent_is_branch;
741
742 BLI_stack_pop(stack, &stack_elem);
743 parent_v = stack_elem.parent_v;
744 e = stack_elem.e;
745
746 /* Skip if edge already visited */
747 if (BLI_BITMAP_TEST(visited_e, e)) {
748 return;
749 }
750
751 /* Mark edge as visited */
752 BLI_BITMAP_ENABLE(visited_e, e);
753
754 /* Process edge */
755
756 parent_is_branch = ((emap[parent_v].size() > 2) || is_root[parent_v]);
757
758 v = bke::mesh::edge_other_vert(edges[e], parent_v);
759 emat[e].origin = parent_v;
760
761 /* If parent is a branch node, start a new edge chain */
762 if (parent_is_branch) {
763 calc_edge_mat(emat[e].mat, vert_positions[parent_v], vert_positions[v]);
764 }
765 else {
766 /* Build edge matrix guided by parent matrix */
767 sub_v3_v3v3(emat[e].mat[0], vert_positions[v], vert_positions[parent_v]);
768 normalize_v3(emat[e].mat[0]);
769 angle = angle_normalized_v3v3(stack_elem.mat[0], emat[e].mat[0]);
770 cross_v3_v3v3(axis, stack_elem.mat[0], emat[e].mat[0]);
771 normalize_v3(axis);
772 rotate_normalized_v3_v3v3fl(emat[e].mat[1], stack_elem.mat[1], axis, angle);
773 rotate_normalized_v3_v3v3fl(emat[e].mat[2], stack_elem.mat[2], axis, angle);
774 }
775
776 /* Add neighbors to stack */
777 for (i = 0; i < emap[v].size(); i++) {
778 /* Add neighbors to stack */
779 copy_m3_m3(stack_elem.mat, emat[e].mat);
780 stack_elem.e = emap[v][i];
781 stack_elem.parent_v = v;
782 BLI_stack_push(stack, &stack_elem);
783 }
784}
785
786static EMat *build_edge_mats(const VArray<bool> &is_root,
787 const Span<float3> vert_positions,
788 const int verts_num,
789 const Span<int2> edges,
790 GroupedSpan<int> emap,
791 bool *has_valid_root)
792{
793 BLI_Stack *stack;
794 EMat *emat;
795 EdgeStackElem stack_elem;
796 BLI_bitmap *visited_e;
797 int i, v;
798
799 stack = BLI_stack_new(sizeof(stack_elem), "build_edge_mats.stack");
800
801 visited_e = BLI_BITMAP_NEW(edges.size(), "build_edge_mats.visited_e");
802 emat = MEM_new_array_zeroed<EMat>(edges.size(), __func__);
803
804 /* Edge matrices are built from the root nodes, add all roots with
805 * children to the stack */
806 for (v = 0; v < verts_num; v++) {
807 if (is_root[v]) {
808 if (emap[v].size() >= 1) {
809 const int2 &edge = edges[emap[v][0]];
810 calc_edge_mat(stack_elem.mat,
811 vert_positions[v],
812 vert_positions[bke::mesh::edge_other_vert(edge, v)]);
813 stack_elem.parent_v = v;
814
815 /* Add adjacent edges to stack */
816 for (i = 0; i < emap[v].size(); i++) {
817 stack_elem.e = emap[v][i];
818 BLI_stack_push(stack, &stack_elem);
819 }
820
821 *has_valid_root = true;
822 }
823 else if (edges.is_empty()) {
824 /* Vertex-only mesh is valid, mark valid root as well (will display error otherwise). */
825 *has_valid_root = true;
826 break;
827 }
828 }
829 }
830
831 while (!BLI_stack_is_empty(stack)) {
832 build_emats_stack(stack, visited_e, emat, emap, edges, is_root, vert_positions);
833 }
834
835 MEM_delete(visited_e);
836 BLI_stack_free(stack);
837
838 return emat;
839}
840
842
843/* -------------------------------------------------------------------- */
846
847/* Returns number of edge subdivisions, taking into account the radius
848 * of the endpoints and the edge length. If both endpoints are branch
849 * nodes, at least two intermediate frames are required. (This avoids
850 * having any special cases for dealing with sharing a frame between
851 * two hulls.) */
852static int calc_edge_subdivisions(const Span<float3> vert_positions,
853 const VArray<float2> &radius,
854 const VArray<bool> &is_loose,
855 const int2 &edge,
856 const Span<int> degree)
857{
858 /* prevent memory errors #38003. */
859#define NUM_SUBDIVISIONS_MAX 128
860
861 float avg_radius;
862 const bool v1_branch = degree[edge[0]] > 2;
863 const bool v2_branch = degree[edge[1]] > 2;
864 int subdivisions_num;
865
866 /* If either end is a branch node marked 'loose', don't subdivide
867 * the edge (or subdivide just twice if both are branches) */
868 if ((v1_branch && is_loose[edge[0]]) || (v2_branch && is_loose[edge[1]])) {
869 if (v1_branch && v2_branch) {
870 return 2;
871 }
872
873 return 0;
874 }
875
876 avg_radius = half_v2(radius[edge[0]]) + half_v2(radius[edge[1]]);
877
878 if (avg_radius != 0.0f) {
879 /* possible (but unlikely) that we overflow INT_MAX */
880 float subdivisions_num_fl;
881 const float edge_len = len_v3v3(vert_positions[edge[0]], vert_positions[edge[1]]);
882 subdivisions_num_fl = (edge_len / avg_radius);
883 if (subdivisions_num_fl < NUM_SUBDIVISIONS_MAX) {
884 subdivisions_num = int(subdivisions_num_fl);
885 }
886 else {
887 subdivisions_num = NUM_SUBDIVISIONS_MAX;
888 }
889 }
890 else {
891 subdivisions_num = 0;
892 }
893
894 /* If both ends are branch nodes, two intermediate nodes are
895 * required */
896 if (subdivisions_num < 2 && v1_branch && v2_branch) {
897 subdivisions_num = 2;
898 }
899
900 return subdivisions_num;
901
902#undef NUM_SUBDIVISIONS_MAX
903}
904
905/* Take a Mesh and subdivide its edges to keep skin nodes
906 * reasonably close. */
907static Mesh *subdivide_base(const Mesh *orig)
908{
909 int subd_num;
910 int i, j, k, u, v;
911 float radrat;
912
913 const bke::AttributeAccessor orig_attributes = orig->attributes();
914 const VArray<float2> orig_radius = *orig_attributes.lookup_or_default<float2>(
915 "skin_modifier_radius", bke::AttrDomain::Point, float2(0.25f));
916 const VArray<bool> orig_loose = *orig_attributes.lookup_or_default<bool>(
917 "skin_modifier_loose", bke::AttrDomain::Point, false);
918 const Span<float3> orig_vert_positions = orig->vert_positions();
919 const Span<int2> orig_edges = orig->edges();
920 const MDeformVert *origdvert = orig->deform_verts().data();
921 int orig_vert_num = orig->verts_num;
922 int orig_edge_num = orig->edges_num;
923
924 /* Get degree of all vertices */
925 Array<int> degree(orig_vert_num, 0);
926 array_utils::count_indices(orig_edges.cast<int>(), degree);
927
928 /* Per edge, store how many subdivisions are needed */
929 Array<int> edge_subd(orig_edge_num, 0);
930 for (i = 0, subd_num = 0; i < orig_edge_num; i++) {
931 edge_subd[i] += calc_edge_subdivisions(
932 orig_vert_positions, orig_radius, orig_loose, orig_edges[i], degree);
933 BLI_assert(edge_subd[i] >= 0);
934 subd_num += edge_subd[i];
935 }
936
937 /* Allocate output mesh */
939 orig, orig_vert_num + subd_num, orig_edge_num + subd_num, 0, 0);
940
941 MutableSpan<float3> out_vert_positions = result->vert_positions_for_write();
942 MutableSpan<int2> result_edges = result->edges_for_write();
943 bke::MutableAttributeAccessor attributes = result->attributes_for_write();
945 "skin_modifier_radius", bke::AttrDomain::Point);
946 MDeformVert *outdvert = nullptr;
947 if (origdvert) {
948 outdvert = result->deform_verts_for_write().data();
949 }
950
951 /* Copy original vertex data */
953 vert_interp.copy(0, 0, orig_vert_num);
954
955 /* Subdivide edges */
956 int result_edge_i = 0;
957 for (i = 0, v = orig_vert_num; i < orig_edge_num; i++) {
958 struct VGroupData {
959 /* Vertex group number */
960 int def_nr;
961 float w1, w2;
962 };
963 VGroupData *vgroups = nullptr, *vg;
964 int vgroups_num = 0;
965
966 const int2 &edge = orig_edges[i];
967
968 if (origdvert) {
969 const MDeformVert *dv1 = &origdvert[edge[0]];
970 const MDeformVert *dv2 = &origdvert[edge[1]];
971 vgroups = MEM_new_array_zeroed<VGroupData>(dv1->totweight, __func__);
972
973 /* Only want vertex groups used by both vertices */
974 for (j = 0; j < dv1->totweight; j++) {
975 vg = nullptr;
976 for (k = 0; k < dv2->totweight; k++) {
977 if (dv1->dw[j].def_nr == dv2->dw[k].def_nr) {
978 vg = &vgroups[vgroups_num];
979 vgroups_num++;
980 break;
981 }
982 }
983
984 if (vg) {
985 vg->def_nr = dv1->dw[j].def_nr;
986 vg->w1 = dv1->dw[j].weight;
987 vg->w2 = dv2->dw[k].weight;
988 }
989 }
990 }
991
992 u = edge[0];
993 radrat = (half_v2(outnode.span[edge[1]]) / half_v2(outnode.span[edge[0]]));
994 if (isfinite(radrat)) {
995 radrat = (radrat + 1) / 2;
996 }
997 else {
998 /* Happens when skin is scaled to zero. */
999 radrat = 1.0f;
1000 }
1001
1002 /* Add vertices and edge segments */
1003 for (j = 0; j < edge_subd[i]; j++, v++) {
1004 float r = (j + 1) / float(edge_subd[i] + 1);
1005 float t = powf(r, radrat);
1006
1007 /* Interpolate vertex coord */
1009 out_vert_positions[v], out_vert_positions[edge[0]], out_vert_positions[edge[1]], t);
1010
1011 /* Interpolate skin radii */
1012 interp_v2_v2v2(outnode.span[v], orig_radius[edge[0]], orig_radius[edge[1]], t);
1013
1014 /* Interpolate vertex group weights */
1015 for (k = 0; k < vgroups_num; k++) {
1016 float weight;
1017
1018 vg = &vgroups[k];
1019 weight = interpf(vg->w2, vg->w1, t);
1020
1021 if (weight > 0) {
1022 BKE_defvert_add_index_notest(&outdvert[v], vg->def_nr, weight);
1023 }
1024 }
1025
1026 result_edges[result_edge_i][0] = u;
1027 result_edges[result_edge_i][1] = v;
1028 result_edge_i++;
1029 u = v;
1030 }
1031
1032 if (vgroups) {
1033 MEM_delete(vgroups);
1034 }
1035
1036 /* Link up to final vertex */
1037 result_edges[result_edge_i][0] = u;
1038 result_edges[result_edge_i][1] = edge[1];
1039 result_edge_i++;
1040 }
1041
1042 outnode.finish();
1043
1044 return result;
1045}
1046
1048
1049/* -------------------------------------------------------------------- */
1052
1053/* Can be either quad or triangle */
1054static void add_poly(SkinOutput *so, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4)
1055{
1056 BMVert *verts[4] = {v1, v2, v3, v4};
1057 BMFace *f;
1058
1059 BLI_assert(!ELEM(v1, v2, v3, v4));
1060 BLI_assert(!ELEM(v2, v3, v4));
1061 BLI_assert(v3 != v4);
1062 BLI_assert(v1 && v2 && v3);
1063
1064 f = BM_face_create_verts(so->bm, verts, v4 ? 4 : 3, nullptr, BM_CREATE_NO_DOUBLE, true);
1066 if (so->smd->flag & MOD_SKIN_SMOOTH_SHADING) {
1068 }
1069 f->mat_nr = so->mat_nr;
1070}
1071
1072static void connect_frames(SkinOutput *so, BMVert *frame1[4], BMVert *frame2[4])
1073{
1074 BMVert *q[4][4] = {
1075 {frame2[0], frame2[1], frame1[1], frame1[0]},
1076 {frame2[1], frame2[2], frame1[2], frame1[1]},
1077 {frame2[2], frame2[3], frame1[3], frame1[2]},
1078 {frame2[3], frame2[0], frame1[0], frame1[3]},
1079 };
1080 int i;
1081 bool swap;
1082
1083 /* Check if frame normals need swap */
1084#if 0
1085 {
1086 /* simple method, works mostly */
1087 float p[3], no[3];
1088 sub_v3_v3v3(p, q[3][0]->co, q[0][0]->co);
1089 normal_quad_v3(no, q[0][0]->co, q[0][1]->co, q[0][2]->co, q[0][3]->co);
1090 swap = dot_v3v3(no, p) > 0;
1091 }
1092#else
1093 {
1094 /* comprehensive method, accumulate flipping of all faces */
1095 float cent_sides[4][3];
1096 float cent[3];
1097 float dot = 0.0f;
1098
1099 for (i = 0; i < 4; i++) {
1100 mid_v3_v3v3v3v3(cent_sides[i], UNPACK4_EX(, q[i], ->co));
1101 }
1102 mid_v3_v3v3v3v3(cent, UNPACK4(cent_sides));
1103
1104 for (i = 0; i < 4; i++) {
1105 float p[3], no[3];
1106 normal_quad_v3(no, UNPACK4_EX(, q[i], ->co));
1107 sub_v3_v3v3(p, cent, cent_sides[i]);
1108 dot += dot_v3v3(no, p);
1109 }
1110
1111 swap = dot > 0;
1112 }
1113#endif
1114
1115 for (i = 0; i < 4; i++) {
1116 if (swap) {
1117 add_poly(so, q[i][3], q[i][2], q[i][1], q[i][0]);
1118 }
1119 else {
1120 add_poly(so, q[i][0], q[i][1], q[i][2], q[i][3]);
1121 }
1122 }
1123}
1124
1125static void output_frames(BMesh *bm, SkinNode *sn, const MDeformVert *input_dvert)
1126{
1127 Frame *f;
1128 int i, j;
1129
1130 /* Output all frame verts */
1131 for (i = 0; i < sn->totframe; i++) {
1132 f = &sn->frames[i];
1133 for (j = 0; j < 4; j++) {
1134 if (!f->merge[j].frame) {
1135 BMVert *v = f->verts[j] = BM_vert_create(bm, f->co[j], nullptr, BM_CREATE_NOP);
1136
1137 if (input_dvert) {
1138 MDeformVert *dv = static_cast<MDeformVert *>(
1140
1141 BLI_assert(dv->totweight == 0);
1142 BKE_defvert_copy(dv, input_dvert);
1143 }
1144 }
1145 }
1146 }
1147}
1148
1149#define PRINT_HOLE_INFO 0
1150
1151static void calc_frame_center(float center[3], const Frame *frame)
1152{
1153 add_v3_v3v3(center, frame->verts[0]->co, frame->verts[1]->co);
1154 add_v3_v3(center, frame->verts[2]->co);
1155 add_v3_v3(center, frame->verts[3]->co);
1156 mul_v3_fl(center, 0.25f);
1157}
1158
1159/* Does crappy fan triangulation of face, may not be so accurate for
1160 * concave faces */
1161static int isect_ray_poly(const float ray_start[3],
1162 const float ray_dir[3],
1163 BMFace *f,
1164 float *r_lambda)
1165{
1166 BMVert *v, *v_first = nullptr, *v_prev = nullptr;
1167 BMIter iter;
1168 float best_dist = FLT_MAX;
1169 bool hit = false;
1170
1171 BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
1172 if (!v_first) {
1173 v_first = v;
1174 }
1175 else if (v_prev != v_first) {
1176 float dist;
1177 bool curhit;
1178
1179 curhit = isect_ray_tri_v3(
1180 ray_start, ray_dir, v_first->co, v_prev->co, v->co, &dist, nullptr);
1181 if (curhit && dist < best_dist) {
1182 hit = true;
1183 best_dist = dist;
1184 }
1185 }
1186
1187 v_prev = v;
1188 }
1189
1190 *r_lambda = best_dist;
1191 return hit;
1192}
1193
1194/* Reduce the face down to 'n' corners by collapsing the edges;
1195 * returns the new face.
1196 *
1197 * The orig_verts should contain the vertices of 'f'
1198 */
1199static BMFace *collapse_face_corners(BMesh *bm, BMFace *f, int n, BMVert **orig_verts)
1200{
1201 int orig_len = f->len;
1202
1203 BLI_assert(n >= 3);
1204 BLI_assert(f->len > n);
1205 if (f->len <= n) {
1206 return f;
1207 }
1208
1209 /* Collapse shortest edge for now */
1210 while (f->len > n) {
1211 BMFace *vf;
1212 BMEdge *shortest_edge;
1213 BMVert *v_safe, *v_merge;
1214 BMOperator op;
1215 BMIter iter;
1216 int i;
1217 BMOpSlot *slot_targetmap;
1218
1219 shortest_edge = BM_face_find_shortest_loop(f)->e;
1220 BMO_op_initf(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE), "weld_verts");
1221
1222 slot_targetmap = BMO_slot_get(op.slots_in, "targetmap");
1223
1224 /* NOTE: could probably calculate merges in one go to be
1225 * faster */
1226
1227 v_safe = shortest_edge->v1;
1228 v_merge = shortest_edge->v2;
1229 mid_v3_v3v3(v_safe->co, v_safe->co, v_merge->co);
1230 BMO_slot_map_elem_insert(&op, slot_targetmap, v_merge, v_safe);
1231 BMO_op_exec(bm, &op);
1232 BMO_op_finish(bm, &op);
1233
1234 /* Find the new face */
1235 f = nullptr;
1236 BM_ITER_ELEM (vf, &iter, v_safe, BM_FACES_OF_VERT) {
1237 bool wrong_face = false;
1238
1239 for (i = 0; i < orig_len; i++) {
1240 if (orig_verts[i] == v_merge) {
1241 orig_verts[i] = nullptr;
1242 }
1243 else if (orig_verts[i] && !BM_vert_in_face(orig_verts[i], vf)) {
1244 wrong_face = true;
1245 break;
1246 }
1247 }
1248
1249 if (!wrong_face) {
1250 f = vf;
1251 break;
1252 }
1253 }
1254
1255 BLI_assert(f);
1256 }
1257
1258 return f;
1259}
1260
1261/* Choose a good face to merge the frame with, used in case the frame
1262 * is completely inside the hull. */
1264{
1265 BMFace *f, *isect_target_face, *center_target_face;
1266 BMIter iter;
1267 float frame_center[3];
1268 float frame_normal[3];
1269 float best_isect_dist = FLT_MAX;
1270 float best_center_dist = FLT_MAX;
1271
1272 calc_frame_center(frame_center, frame);
1273 normal_quad_v3(frame_normal,
1274 frame->verts[3]->co,
1275 frame->verts[2]->co,
1276 frame->verts[1]->co,
1277 frame->verts[0]->co);
1278
1279 /* Use a line intersection test and nearest center test against
1280 * all faces */
1281 isect_target_face = center_target_face = nullptr;
1282 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1283 float dist, poly_center[3];
1284 int hit;
1285
1286 /* Intersection test */
1287 hit = isect_ray_poly(frame_center, frame_normal, f, &dist);
1288 if (hit && dist < best_isect_dist) {
1289 isect_target_face = f;
1290 best_isect_dist = dist;
1291 }
1292
1293 /* Nearest test */
1294 BM_face_calc_center_median(f, poly_center);
1295 dist = len_v3v3(frame_center, poly_center);
1296 if (dist < best_center_dist) {
1297 center_target_face = f;
1298 best_center_dist = dist;
1299 }
1300 }
1301
1302 f = isect_target_face;
1303 if (!f || best_center_dist < best_isect_dist / 2) {
1304 f = center_target_face;
1305 }
1306
1307 /* This case is unlikely now, but could still happen. Should look
1308 * into splitting edges to make new faces. */
1309#if PRINT_HOLE_INFO
1310 if (!f) {
1311 printf("no good face found\n");
1312 }
1313#endif
1314
1315 return f;
1316}
1317
1318/* Use edge-length heuristic to choose from eight possible face bridges */
1319static void skin_choose_quad_bridge_order(BMVert *a[4], BMVert *b[4], int best_order[4])
1320{
1321 int orders[8][4];
1322 float shortest_len;
1323 int i, j;
1324
1325 /* Enumerate all valid orderings */
1326 for (i = 0; i < 4; i++) {
1327 for (j = 0; j < 4; j++) {
1328 orders[i][j] = (j + i) % 4;
1329 orders[i + 4][j] = 3 - ((j + i) % 4);
1330 }
1331 }
1332
1333 shortest_len = FLT_MAX;
1334 for (i = 0; i < 8; i++) {
1335 float len = 0;
1336
1337 /* Get total edge length for this configuration */
1338 for (j = 0; j < 4; j++) {
1339 len += len_squared_v3v3(a[j]->co, b[orders[i][j]]->co);
1340 }
1341
1342 if (len < shortest_len) {
1343 shortest_len = len;
1344 memcpy(best_order, orders[i], sizeof(int[4]));
1345 }
1346 }
1347}
1348
1349static void skin_fix_hole_no_good_verts(BMesh *bm, Frame *frame, BMFace *split_face)
1350{
1351 BMFace *f;
1352 BMVert *verts[4];
1353 BMOIter oiter;
1354 BMOperator op;
1355 int i, best_order[4];
1356 BMOpSlot *slot_targetmap;
1357
1358 BLI_assert(split_face->len >= 3);
1359
1360 /* Extrude the split face */
1362 BM_elem_flag_enable(split_face, BM_ELEM_TAG);
1364 &op,
1366 "extrude_discrete_faces faces=%hf",
1367 BM_ELEM_TAG);
1368 BMO_op_exec(bm, &op);
1369
1370 /* Update split face (should only be one new face created
1371 * during extrusion) */
1372 split_face = nullptr;
1373 BMO_ITER (f, &oiter, op.slots_out, "faces.out", BM_FACE) {
1374 BLI_assert(!split_face);
1375 split_face = f;
1376 }
1377
1378 BMO_op_finish(bm, &op);
1379
1380 Vector<BMVert *> vert_buf;
1381
1382 if (split_face->len == 3) {
1383 BMEdge *longest_edge;
1384
1385 /* Need at least four ring edges, so subdivide longest edge if
1386 * face is a triangle */
1387 longest_edge = BM_face_find_longest_loop(split_face)->e;
1388
1390 BM_elem_flag_enable(longest_edge, BM_ELEM_TAG);
1391
1394 "subdivide_edges edges=%he cuts=%i quad_corner_type=%i",
1396 1,
1398 }
1399 else if (split_face->len > 4) {
1400 /* Maintain a dynamic vert array containing the split_face's
1401 * vertices, avoids frequent allocations in #collapse_face_corners(). */
1402 vert_buf.reinitialize(split_face->len);
1403
1404 /* Get split face's verts */
1407 split_face,
1408 reinterpret_cast<void **>(vert_buf.data()),
1409 split_face->len);
1410
1411 /* Earlier edge split operations may have turned some quads
1412 * into higher-degree faces */
1413 split_face = collapse_face_corners(bm, split_face, 4, vert_buf.data());
1414 }
1415
1416 /* `split_face` should now be a quad. */
1417 BLI_assert(split_face->len == 4);
1418
1419 /* Account for the highly unlikely case that it's not a quad. */
1420 if (split_face->len != 4) {
1421 /* Reuse `vert_buf` for updating normals. */
1422 vert_buf.reinitialize(split_face->len);
1425 split_face,
1426 reinterpret_cast<void **>(vert_buf.data()),
1427 split_face->len);
1428
1429 vert_array_face_normal_update(vert_buf.data(), split_face->len);
1430 return;
1431 }
1432
1433 /* Get split face's verts */
1434 // BM_iter_as_array(bm, BM_VERTS_OF_FACE, split_face, (void **)verts, 4);
1435 BM_face_as_array_vert_quad(split_face, verts);
1436 skin_choose_quad_bridge_order(verts, frame->verts, best_order);
1437
1438 /* Delete split face and merge */
1439 BM_face_kill(bm, split_face);
1440 BMO_op_init(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE), "weld_verts");
1441 slot_targetmap = BMO_slot_get(op.slots_in, "targetmap");
1442 for (i = 0; i < 4; i++) {
1443 BMO_slot_map_elem_insert(&op, slot_targetmap, verts[i], frame->verts[best_order[i]]);
1444 }
1445 BMO_op_exec(bm, &op);
1446 BMO_op_finish(bm, &op);
1447
1449}
1450
1451/* If the frame has some vertices that are inside the hull (detached)
1452 * and some attached, duplicate the attached vertices and take the
1453 * whole frame off the hull. */
1455{
1456 int i, attached[4], totattached = 0;
1457
1458 /* Get/count attached frame corners */
1459 for (i = 0; i < 4; i++) {
1460 if (!frame->inside_hull[i]) {
1461 attached[totattached++] = i;
1462 }
1463 }
1464
1465 /* Detach everything */
1466 for (i = 0; i < totattached; i++) {
1467 BMVert **av = &frame->verts[attached[i]];
1468 (*av) = BM_vert_create(bm, (*av)->co, *av, BM_CREATE_NOP);
1469 }
1470}
1471
1472static void quad_from_tris(BMEdge *e, BMFace *adj[2], BMVert *ndx[4])
1473{
1474 BMVert *tri[2][3];
1475 BMVert *opp = nullptr;
1476 int i, j;
1477
1478 BLI_assert(adj[0]->len == 3 && adj[1]->len == 3);
1479
1480#if 0
1481 BM_iter_as_array(bm, BM_VERTS_OF_FACE, adj[0], (void **)tri[0], 3);
1482 BM_iter_as_array(bm, BM_VERTS_OF_FACE, adj[1], (void **)tri[1], 3);
1483#else
1484 BM_face_as_array_vert_tri(adj[0], tri[0]);
1485 BM_face_as_array_vert_tri(adj[1], tri[1]);
1486#endif
1487
1488 /* Find what the second tri has that the first doesn't */
1489 for (i = 0; i < 3; i++) {
1490 if (!ELEM(tri[1][i], tri[0][0], tri[0][1], tri[0][2])) {
1491 opp = tri[1][i];
1492 break;
1493 }
1494 }
1495 BLI_assert(opp);
1496
1497 for (i = 0, j = 0; i < 3; i++, j++) {
1498 ndx[j] = tri[0][i];
1499 /* When the triangle edge cuts across our quad-to-be,
1500 * throw in the second triangle's vertex */
1501 if (ELEM(tri[0][i], e->v1, e->v2) &&
1502 (tri[0][(i + 1) % 3] == e->v1 || tri[0][(i + 1) % 3] == e->v2))
1503 {
1504 j++;
1505 ndx[j] = opp;
1506 }
1507 }
1508}
1509
1510static void add_quad_from_tris(SkinOutput *so, BMEdge *e, BMFace *adj[2])
1511{
1512 BMVert *quad[4];
1513
1514 quad_from_tris(e, adj, quad);
1515
1516 add_poly(so, quad[0], quad[1], quad[2], quad[3]);
1517}
1518
1520{
1521 BMIter iter;
1522 BMEdge *e;
1523 HeapSimple *heap;
1524 float score;
1525
1526 heap = BLI_heapsimple_new();
1527
1528 /* Edges may be tagged by earlier operations,
1529 * clear them as tagged edges are deleted, see: #165789. */
1531
1532 /* Build heap */
1533 BM_ITER_MESH (e, &iter, so->bm, BM_EDGES_OF_MESH) {
1534 BMFace *adj[2];
1535
1536 /* Only care if the edge is used by exactly two triangles */
1537 if (BM_edge_face_pair(e, &adj[0], &adj[1])) {
1538 if (adj[0]->len == 3 && adj[1]->len == 3) {
1539 BMVert *quad[4];
1540
1543
1544 /* Construct quad using the two triangles adjacent to
1545 * the edge */
1546 quad_from_tris(e, adj, quad);
1547
1548 /* Calculate a score for the quad, higher score for
1549 * triangles being closer to coplanar */
1550 score = ((BM_face_calc_area(adj[0]) + BM_face_calc_area(adj[1])) *
1551 dot_v3v3(adj[0]->no, adj[1]->no));
1552
1553 /* Check if quad crosses the axis of symmetry */
1554 if (quad_crosses_symmetry_plane(quad, smd)) {
1555 /* Increase score if the triangles form a
1556 * symmetric quad, otherwise don't use it */
1557 if (is_quad_symmetric(quad, smd)) {
1558 score *= 10;
1559 }
1560 else {
1561 continue;
1562 }
1563 }
1564
1565 /* Don't use the quad if it's concave */
1566 if (!is_quad_convex_v3(quad[0]->co, quad[1]->co, quad[2]->co, quad[3]->co)) {
1567 continue;
1568 }
1569
1570 BLI_heapsimple_insert(heap, -score, e);
1571 }
1572 }
1573 }
1574
1575 while (!BLI_heapsimple_is_empty(heap)) {
1576 BMFace *adj[2];
1577
1578 e = static_cast<BMEdge *>(BLI_heapsimple_pop_min(heap));
1579
1580 if (BM_edge_face_pair(e, &adj[0], &adj[1])) {
1581 /* If both triangles still free, and if they don't already
1582 * share a border with another face, output as a quad */
1583 if (!BM_elem_flag_test(adj[0], BM_ELEM_TAG) && !BM_elem_flag_test(adj[1], BM_ELEM_TAG) &&
1584 !BM_face_share_face_check(adj[0], adj[1]))
1585 {
1586 add_quad_from_tris(so, e, adj);
1590 }
1591 }
1592 }
1593
1594 BLI_heapsimple_free(heap, nullptr);
1595
1597}
1598
1600 int verts_num,
1601 GroupedSpan<int> emap,
1602 const Span<int2> edges)
1603{
1604 Frame **hull_frames;
1605 int v, tothullframe;
1606
1607 for (v = 0; v < verts_num; v++) {
1608 /* Only check branch nodes */
1609 if (!skin_nodes[v].totframe) {
1610 hull_frames = collect_hull_frames(v, skin_nodes, emap, edges, &tothullframe);
1611 merge_frame_corners(hull_frames, tothullframe);
1612 MEM_delete(hull_frames);
1613 }
1614 }
1615}
1616
1617static void skin_update_merged_vertices(SkinNode *skin_nodes, int verts_num)
1618{
1619 int v;
1620
1621 for (v = 0; v < verts_num; v++) {
1622 SkinNode *sn = &skin_nodes[v];
1623 int i, j;
1624
1625 for (i = 0; i < sn->totframe; i++) {
1626 Frame *f = &sn->frames[i];
1627
1628 for (j = 0; j < 4; j++) {
1629 if (f->merge[j].frame) {
1630 /* Merge chaining not allowed */
1631 BLI_assert(!f->merge[j].frame->merge[f->merge[j].corner].frame);
1632
1633 f->verts[j] = f->merge[j].frame->verts[f->merge[j].corner];
1634 }
1635 }
1636 }
1637 }
1638}
1639
1640static void skin_fix_hull_topology(BMesh *bm, SkinNode *skin_nodes, int verts_num)
1641{
1642 int v;
1643
1644 for (v = 0; v < verts_num; v++) {
1645 SkinNode *sn = &skin_nodes[v];
1646 int j;
1647
1648 for (j = 0; j < sn->totframe; j++) {
1649 Frame *f = &sn->frames[j];
1650
1651 if (f->detached) {
1652 BMFace *target_face;
1653
1655
1656 target_face = skin_hole_target_face(bm, f);
1657 if (target_face) {
1658 skin_fix_hole_no_good_verts(bm, f, target_face);
1659 }
1660 }
1661 }
1662 }
1663}
1664
1665static void skin_output_end_nodes(SkinOutput *so, SkinNode *skin_nodes, int verts_num)
1666{
1667 int v;
1668
1669 for (v = 0; v < verts_num; v++) {
1670 SkinNode *sn = &skin_nodes[v];
1671 /* Assuming here just two frames */
1672 if (sn->flag & SEAM_FRAME) {
1673 BMVert *v_order[4];
1674 int i, order[4];
1675
1676 skin_choose_quad_bridge_order(sn->frames[0].verts, sn->frames[1].verts, order);
1677 for (i = 0; i < 4; i++) {
1678 v_order[i] = sn->frames[1].verts[order[i]];
1679 }
1680 connect_frames(so, sn->frames[0].verts, v_order);
1681 }
1682 else if (sn->totframe == 2) {
1683 connect_frames(so, sn->frames[0].verts, sn->frames[1].verts);
1684 }
1685
1686 if (sn->flag & CAP_START) {
1687 if (sn->flag & FLIP_NORMAL) {
1688 add_poly(so,
1689 sn->frames[0].verts[0],
1690 sn->frames[0].verts[1],
1691 sn->frames[0].verts[2],
1692 sn->frames[0].verts[3]);
1693 }
1694 else {
1695 add_poly(so,
1696 sn->frames[0].verts[3],
1697 sn->frames[0].verts[2],
1698 sn->frames[0].verts[1],
1699 sn->frames[0].verts[0]);
1700 }
1701 }
1702 if (sn->flag & CAP_END) {
1703 add_poly(so,
1704 sn->frames[1].verts[0],
1705 sn->frames[1].verts[1],
1706 sn->frames[1].verts[2],
1707 sn->frames[1].verts[3]);
1708 }
1709 }
1710}
1711
1712static void skin_output_connections(SkinOutput *so, SkinNode *skin_nodes, const Span<int2> edges)
1713{
1714 for (const int e : edges.index_range()) {
1715 SkinNode *a, *b;
1716 a = &skin_nodes[edges[e][0]];
1717 b = &skin_nodes[edges[e][1]];
1718
1719 if (a->totframe && b->totframe) {
1720 if ((a->flag & SEAM_FRAME) || (b->flag & SEAM_FRAME)) {
1721 Frame *fr[2] = {&a->frames[0], &b->frames[0]};
1722 BMVert *v_order[4];
1723 int i, order[4];
1724
1725 if ((a->flag & SEAM_FRAME) && (e != a->seam_edges[0])) {
1726 fr[0]++;
1727 }
1728 if ((b->flag & SEAM_FRAME) && (e != b->seam_edges[0])) {
1729 fr[1]++;
1730 }
1731
1732 skin_choose_quad_bridge_order(fr[0]->verts, fr[1]->verts, order);
1733 for (i = 0; i < 4; i++) {
1734 v_order[i] = fr[1]->verts[order[i]];
1735 }
1736 connect_frames(so, fr[0]->verts, v_order);
1737 }
1738 else {
1739 connect_frames(so, a->frames[0].verts, b->frames[0].verts);
1740 }
1741 }
1742 }
1743}
1744
1746 SkinNode *skin_nodes,
1747 int verts_num,
1748 const SkinModifierData *smd)
1749{
1750 BMIter iter, eiter;
1751 BMVert *v;
1752 int i, j, k, skey;
1753
1754 if (smd->branch_smoothing == 0) {
1755 return;
1756 }
1757
1758 /* Mark all frame vertices */
1760 for (i = 0; i < verts_num; i++) {
1761 for (j = 0; j < skin_nodes[i].totframe; j++) {
1762 Frame *frame = &skin_nodes[i].frames[j];
1763
1764 for (k = 0; k < 4; k++) {
1766 }
1767 }
1768 }
1769
1770 /* Add temporary shape-key layer to store original coordinates. */
1773 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1774 copy_v3_v3(
1775 static_cast<float *>(CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, skey)),
1776 v->co);
1777 }
1778
1779 /* Smooth vertices, weight unmarked vertices more strongly (helps
1780 * to smooth frame vertices, but don't want to alter them too
1781 * much) */
1782 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1783 BMEdge *e;
1784 float avg[3];
1785 float weight = smd->branch_smoothing;
1786 int totv = 1;
1787
1789 weight *= 0.5f;
1790 }
1791
1792 copy_v3_v3(avg, v->co);
1793 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1794 BMVert *other = BM_edge_other_vert(e, v);
1795
1796 add_v3_v3(avg,
1797 static_cast<float *>(
1798 CustomData_bmesh_get_n(&bm->vdata, other->head.data, CD_SHAPEKEY, skey)));
1799 totv++;
1800 }
1801
1802 if (totv > 1) {
1803 mul_v3_fl(avg, 1.0f / float(totv));
1804 interp_v3_v3v3(v->co, v->co, avg, weight);
1805 }
1806 }
1807
1808 /* Done with original coordinates */
1810
1811 BMFace *f;
1812 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1814 }
1815}
1816
1817/* Returns true if all hulls are successfully built, false otherwise */
1819 SkinNode *skin_nodes,
1820 int verts_num,
1821 GroupedSpan<int> emap,
1822 const Span<int2> edges)
1823{
1824 bool result = true;
1825 int v;
1826
1827 for (v = 0; v < verts_num; v++) {
1828 SkinNode *sn = &skin_nodes[v];
1829
1830 /* Branch node hulls */
1831 if (!sn->totframe) {
1832 Frame **hull_frames;
1833 int tothullframe;
1834
1835 hull_frames = collect_hull_frames(v, skin_nodes, emap, edges, &tothullframe);
1836 if (!build_hull(so, hull_frames, tothullframe)) {
1837 result = false;
1838 }
1839
1840 MEM_delete(hull_frames);
1841 }
1842 }
1843
1844 return result;
1845}
1846
1852
1853static BMesh *build_skin(SkinNode *skin_nodes,
1854 int verts_num,
1855 GroupedSpan<int> emap,
1856 const Span<int2> edges,
1857 const MDeformVert *input_dvert,
1858 SkinModifierData *smd,
1859 eSkinErrorFlag *r_error)
1860{
1861 SkinOutput so;
1862 int v;
1863
1864 so.smd = smd;
1865 BMeshCreateParams create_params{};
1866 create_params.use_toolflags = true;
1867 so.bm = BM_mesh_create(&bm_mesh_allocsize_default, &create_params);
1868 so.mat_nr = 0;
1869
1870 /* BMESH_TODO: bumping up the stack level (see MOD_array.cc) */
1872 BMO_push(so.bm, nullptr);
1874
1875 if (input_dvert) {
1877 }
1878
1879 /* Check for mergeable frame corners around hulls before
1880 * outputting vertices */
1881 skin_merge_close_frame_verts(skin_nodes, verts_num, emap, edges);
1882
1883 /* Write out all frame vertices to the mesh */
1884 for (v = 0; v < verts_num; v++) {
1885 if (skin_nodes[v].totframe) {
1886 output_frames(so.bm, &skin_nodes[v], input_dvert ? &input_dvert[v] : nullptr);
1887 }
1888 }
1889
1890 /* Update vertex pointers for merged frame corners */
1891 skin_update_merged_vertices(skin_nodes, verts_num);
1892
1893 if (!skin_output_branch_hulls(&so, skin_nodes, verts_num, emap, edges)) {
1894 *r_error |= SKIN_ERROR_HULL;
1895 }
1896
1897 /* Merge triangles here in the hope of providing better target
1898 * faces for skin_fix_hull_topology() to connect to */
1899 hull_merge_triangles(&so, smd);
1900
1901 /* Using convex hulls may not generate a nice manifold mesh. Two
1902 * problems can occur: an input frame's edges may be inside the
1903 * hull, and/or an input frame's vertices may be inside the hull.
1904 *
1905 * General fix to produce manifold mesh: for any frame that is
1906 * partially detached, first detach it fully, then find a suitable
1907 * existing face to merge with. (Note that we do this after
1908 * creating all hull faces, but before creating any other
1909 * faces).
1910 */
1911 skin_fix_hull_topology(so.bm, skin_nodes, verts_num);
1912
1913 skin_smooth_hulls(so.bm, skin_nodes, verts_num, smd);
1914
1915 skin_output_end_nodes(&so, skin_nodes, verts_num);
1916 skin_output_connections(&so, skin_nodes, edges);
1917 hull_merge_triangles(&so, smd);
1918
1920 BMO_pop(so.bm);
1921
1922 return so.bm;
1923}
1924
1926{
1927 int *orig = static_cast<int *>(
1928 CustomData_add_layer(&mesh->face_data, CD_ORIGINDEX, CD_CONSTRUCT, mesh->faces_num));
1929 std::fill_n(orig, mesh->faces_num, ORIGINDEX_NONE);
1930}
1931
1932/*
1933 * 0) Subdivide edges (in caller)
1934 * 1) Generate good edge matrices (uses root nodes)
1935 * 2) Generate node frames
1936 * 3) Output vertices and polygons from frames, connections, and hulls
1937 */
1938static Mesh *base_skin(Mesh *origmesh, SkinModifierData *smd, eSkinErrorFlag *r_error)
1939{
1940 Mesh *result;
1941 BMesh *bm;
1942 EMat *emat;
1943 SkinNode *skin_nodes;
1944 bool has_valid_root = false;
1945
1946 const bke::AttributeAccessor attributes = origmesh->attributes();
1947 const VArray<float2> radius = *attributes.lookup_or_default<float2>(
1948 "skin_modifier_radius", bke::AttrDomain::Point, float2(0.25f));
1949 const VArray<bool> is_root = *attributes.lookup_or_default<bool>(
1950 "skin_modifier_root", bke::AttrDomain::Point, false);
1951
1952 const Span<float3> vert_positions = origmesh->vert_positions();
1953 const Span<int2> edges = origmesh->edges();
1954 const MDeformVert *dvert = origmesh->deform_verts().data();
1955 const int verts_num = origmesh->verts_num;
1956
1957 Array<int> vert_to_edge_offsets;
1958 Array<int> vert_to_edge_indices;
1960 edges, verts_num, vert_to_edge_offsets, vert_to_edge_indices);
1961
1962 emat = build_edge_mats(is_root, vert_positions, verts_num, edges, vert_to_edge, &has_valid_root);
1963 skin_nodes = build_frames(vert_positions, verts_num, radius, vert_to_edge, emat);
1964 MEM_delete(emat);
1965 emat = nullptr;
1966
1967 bm = build_skin(skin_nodes, verts_num, vert_to_edge, edges, dvert, smd, r_error);
1968
1969 MEM_delete(skin_nodes);
1970
1971 if (!has_valid_root) {
1972 *r_error |= SKIN_ERROR_NO_VALID_ROOT;
1973 }
1974
1975 if (!bm) {
1976 return nullptr;
1977 }
1978
1979 result = BKE_mesh_from_bmesh_for_eval_nomain(bm, nullptr, origmesh);
1981
1983
1984 return result;
1985}
1986
1988{
1989 Mesh *result;
1990
1991 /* Skin vertex radius attribute is required. */
1992 if (!mesh->attributes().contains("skin_modifier_radius")) {
1993 return mesh;
1994 }
1995
1997 result = base_skin(mesh, smd, r_error);
1998
1999 BKE_id_free(nullptr, mesh);
2000 return result;
2001}
2002
2004
2005/* -------------------------------------------------------------------- */
2008
2009static void init_data(ModifierData *md)
2010{
2011 SkinModifierData *smd = reinterpret_cast<SkinModifierData *>(md);
2013
2014 /* Enable in editmode by default. */
2016}
2017
2019{
2020 eSkinErrorFlag error = eSkinErrorFlag(0);
2021 Mesh *result = final_skin(reinterpret_cast<SkinModifierData *>(md), mesh, &error);
2022
2023 if (error & SKIN_ERROR_NO_VALID_ROOT) {
2026 ctx->object,
2027 md,
2028 "No valid root vertex found (you need one per mesh island you want to skin)");
2029 }
2030 if (error & SKIN_ERROR_HULL) {
2031 error &= ~SKIN_ERROR_HULL;
2032 BKE_modifier_set_error(ctx->object, md, "Hull error");
2033 }
2034 BLI_assert(error == 0);
2035
2036 if (result == nullptr) {
2037 return mesh;
2038 }
2039 return result;
2040}
2041
2042static void required_data_mask(ModifierData * /*md*/, CustomData_MeshMasks *r_cddata_masks)
2043{
2044 r_cddata_masks->vmask |= CD_MASK_MDEFORMVERT;
2045}
2046
2047static void panel_draw(const bContext * /*C*/, Panel *panel)
2048{
2049 ui::Layout &layout = *panel->layout;
2051
2052 PointerRNA ob_ptr;
2053 PointerRNA *ptr = modifier_panel_get_property_pointers(panel, &ob_ptr);
2054
2055 PointerRNA op_ptr;
2056
2057 layout.use_property_split_set(true);
2058
2059 layout.prop(ptr, "branch_smoothing", UI_ITEM_NONE, std::nullopt, ICON_NONE);
2060
2061 ui::Layout *row = &layout.row(true, IFACE_("Symmetry"));
2062 row->prop(ptr, "use_x_symmetry", toggles_flag, std::nullopt, ICON_NONE);
2063 row->prop(ptr, "use_y_symmetry", toggles_flag, std::nullopt, ICON_NONE);
2064 row->prop(ptr, "use_z_symmetry", toggles_flag, std::nullopt, ICON_NONE);
2065
2066 layout.prop(ptr, "use_smooth_shade", UI_ITEM_NONE, std::nullopt, ICON_NONE);
2067
2068 row = &layout.row(false);
2069 row->op("OBJECT_OT_skin_armature_create", IFACE_("Create Armature"), ICON_NONE);
2070 row->op("MESH_OT_customdata_skin_add", std::nullopt, ICON_NONE);
2071
2072 row = &layout.row(false);
2073 op_ptr = row->op("OBJECT_OT_skin_loose_mark_clear",
2074 IFACE_("Mark Loose"),
2075 ICON_NONE,
2077 UI_ITEM_NONE);
2078 RNA_enum_set(&op_ptr, "action", 0); /* SKIN_LOOSE_MARK */
2079 op_ptr = row->op("OBJECT_OT_skin_loose_mark_clear",
2080 IFACE_("Clear Loose"),
2081 ICON_NONE,
2083 UI_ITEM_NONE);
2084 RNA_enum_set(&op_ptr, "action", 1); /* SKIN_LOOSE_CLEAR */
2085
2086 layout.op("OBJECT_OT_skin_root_mark", IFACE_("Mark Root"), ICON_NONE);
2087 layout.op("OBJECT_OT_skin_radii_equalize", IFACE_("Equalize Radii"), ICON_NONE);
2088
2089 modifier_error_message_draw(layout, ptr);
2090}
2091
2092static void panel_register(ARegionType *region_type)
2093{
2095}
2096
2098 /*idname*/ "Skin",
2099 /*name*/ N_("Skin"),
2100 /*struct_name*/ "SkinModifierData",
2101 /*struct_size*/ sizeof(SkinModifierData),
2102 /*srna*/ &RNA_SkinModifier,
2105 /*icon*/ ICON_MOD_SKIN,
2106
2107 /*copy_data*/ BKE_modifier_copydata_generic,
2108
2109 /*deform_verts*/ nullptr,
2110 /*deform_matrices*/ nullptr,
2111 /*deform_verts_EM*/ nullptr,
2112 /*deform_matrices_EM*/ nullptr,
2113 /*modify_mesh*/ modify_mesh,
2114 /*modify_geometry_set*/ nullptr,
2115
2116 /*init_data*/ init_data,
2117 /*required_data_mask*/ required_data_mask,
2118 /*free_data*/ nullptr,
2119 /*is_disabled*/ nullptr,
2120 /*update_depsgraph*/ nullptr,
2121 /*depends_on_time*/ nullptr,
2122 /*depends_on_normals*/ nullptr,
2123 /*foreach_ID_link*/ nullptr,
2124 /*foreach_tex_link*/ nullptr,
2125 /*free_runtime_data*/ nullptr,
2126 /*panel_register*/ panel_register,
2127 /*blend_write*/ nullptr,
2128 /*blend_read*/ nullptr,
2129 /*foreach_cache*/ nullptr,
2130 /*foreach_working_space_color*/ nullptr,
2131};
2132
2134
2135} // namespace blender
#define ORIGINDEX_NONE
support for deformation groups and hooks.
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition BLI_bitmap.hh:39
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition BLI_bitmap.hh:63
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition BLI_bitmap.hh:80
A min-heap / priority queue ADT.
#define IFACE_(msgid)
Read Blender memory allocation and freeing.
#define NUM_SUBDIVISIONS_MAX
#define MAX_SKIN_NODE_FRAMES
Definition MOD_skin.cc:159
#define UI_ITEM_NONE
#define UNPACK4(a)
#define UNUSED_VARS(...)
#define UNPACK4_EX(pre, a, post)
#define INIT_DEFAULT_STRUCT_AFTER(struct_dst, member)
#define ELEM(...)
#define BM_ALL_NOLOOP
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_FLAG_DEFAULTS
#define CD_MASK_MDEFORMVERT
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
void reinitialize(const int64_t new_size)
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
void copy(int src_index, int dst_index, int count) const
GSpanAttributeWriter convert_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
#define powf(x, y)
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ENUM_OPERATORS(Layer::Flags)
void count_indices(Span< int > indices, MutableSpan< int > counts)
int edge_other_vert(const int2 edge, const int vert)
Definition BKE_mesh.hh:370
GroupedSpan< int > build_vert_to_edge_map(Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
BMesh Iterators.
MINLINE float min_ff(float a, float b)
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
bool BMO_error_occurred_at_level(BMesh *bm, eBMOpErrorLevel level)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
BMFace * BM_face_create_verts(BMesh *bm, BMVert **vert_arr, const int len, const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
ModifierTypeInfo modifierType_Skin
Definition MOD_skin.cc:2097
static Frame ** collect_hull_frames(int v, SkinNode *frames, GroupedSpan< int > emap, const Span< int2 > edges, int *tothullframe)
Definition MOD_skin.cc:458
void BM_data_layer_free_n(BMesh *bm, CustomData *data, int type, int n)
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
static void skin_update_merged_vertices(SkinNode *skin_nodes, int verts_num)
Definition MOD_skin.cc:1617
void BM_data_layer_add(BMesh *bm, CustomData *data, int type)
static void skin_choose_quad_bridge_order(BMVert *a[4], BMVert *b[4], int best_order[4])
Definition MOD_skin.cc:1319
void * CustomData_bmesh_get(const CustomData *data, void *block, eCustomDataType type)
void BM_mesh_elem_toolflags_ensure(BMesh *bm)
Definition bmesh_mesh.cc:78
void BKE_modifier_set_error(const Object *ob, ModifierData *md, const char *format,...) ATTR_PRINTF_FORMAT(3
void rotate_normalized_v3_v3v3fl(float out[3], const float p[3], const float axis[3], float angle)
PointerRNA * modifier_panel_get_property_pointers(Panel *panel, PointerRNA *r_ob_ptr)
int CustomData_number_of_layers(const CustomData *data, eCustomDataType type)
void BM_mesh_free(BMesh *bm)
BMesh Free Mesh.
void mid_v3_v3v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:253
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
void copy_m3_m3(float m1[3][3], const float m2[3][3])
static void vert_face_normal_mark_update(BMVert *v)
Definition MOD_skin.cc:95
static void skin_set_orig_indices(Mesh *mesh)
Definition MOD_skin.cc:1925
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition stack.cc:141
static void vert_array_face_normal_update(BMVert **verts, int verts_len)
Definition MOD_skin.cc:109
static void skin_fix_hull_topology(BMesh *bm, SkinNode *skin_nodes, int verts_num)
Definition MOD_skin.cc:1640
static void init_data(ModifierData *md)
static bool quad_crosses_symmetry_plane(BMVert *quad[4], const SkinModifierData *smd)
Definition MOD_skin.cc:216
bool BMO_op_initf(BMesh *bm, BMOperator *op, int flag, const char *fmt,...)
static Mesh * subdivide_base(const Mesh *orig)
Definition MOD_skin.cc:907
BMLoop * BM_face_find_shortest_loop(BMFace *f)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
void RNA_enum_set(PointerRNA *ptr, const char *name, int value)
static BMesh * build_skin(SkinNode *skin_nodes, int verts_num, GroupedSpan< int > emap, const Span< int2 > edges, const MDeformVert *input_dvert, SkinModifierData *smd, eSkinErrorFlag *r_error)
Definition MOD_skin.cc:1853
ATTR_WARN_UNUSED_RESULT const BMVert * v
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
static void vert_face_normal_mark_set(BMVert *v)
Definition MOD_skin.cc:86
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static Mesh * base_skin(Mesh *origmesh, SkinModifierData *smd, eSkinErrorFlag *r_error)
Definition MOD_skin.cc:1938
BMLoop * BM_face_find_longest_loop(BMFace *f)
MINLINE void mul_v3_fl(float r[3], float f)
static void required_data_mask(ModifierData *, CustomData_MeshMasks *r_cddata_masks)
void BMO_push(BMesh *bm, BMOperator *op)
BMESH OPSTACK PUSH.
static float half_v2(const float v[2])
Definition MOD_skin.cc:529
static BMFace * skin_hole_target_face(BMesh *bm, Frame *frame)
Definition MOD_skin.cc:1263
static int calc_edge_subdivisions(const Span< float3 > vert_positions, const VArray< float2 > &radius, const VArray< bool > &is_loose, const int2 &edge, const Span< int > degree)
Definition MOD_skin.cc:852
@ SUBD_CORNER_STRAIGHT_CUT
bool BM_face_share_face_check(BMFace *f_a, BMFace *f_b)
void modifier_error_message_draw(ui::Layout &layout, PointerRNA *ptr)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
@ BM_CREATE_NO_DOUBLE
Definition bmesh_core.hh:36
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
float BM_face_calc_area(const BMFace *f)
static int connection_node_mat(float mat[3][3], int v, GroupedSpan< int > emap, EMat *emat)
Definition MOD_skin.cc:586
static void create_frame(Frame *frame, const float co[3], const float radius[2], const float mat[3][3], float offset)
Definition MOD_skin.cc:502
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
static void skin_smooth_hulls(BMesh *bm, SkinNode *skin_nodes, int verts_num, const SkinModifierData *smd)
Definition MOD_skin.cc:1745
static void calc_frame_center(float center[3], const Frame *frame)
Definition MOD_skin.cc:1151
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:62
@ SEAM_FRAME
Definition MOD_skin.cc:132
@ CAP_START
Definition MOD_skin.cc:130
@ FLIP_NORMAL
Definition MOD_skin.cc:133
static void skin_fix_hole_no_good_verts(BMesh *bm, Frame *frame, BMFace *split_face)
Definition MOD_skin.cc:1349
static void panel_register(ARegionType *region_type)
@ SKIN_ERROR_NO_VALID_ROOT
Definition MOD_skin.cc:1848
@ SKIN_ERROR_HULL
Definition MOD_skin.cc:1849
static bool build_hull(SkinOutput *so, Frame **frames, int totframe)
Definition MOD_skin.cc:267
bool BM_vert_in_face(BMVert *v, BMFace *f)
static EMat * build_edge_mats(const VArray< bool > &is_root, const Span< float3 > vert_positions, const int verts_num, const Span< int2 > edges, GroupedSpan< int > emap, bool *has_valid_root)
Definition MOD_skin.cc:786
MINLINE void negate_v3(float r[3])
static float frame_len(const Frame *frame)
Definition MOD_skin.cc:389
const BMAllocTemplate bm_mesh_allocsize_default
Definition bmesh_mesh.cc:26
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
bool BMO_op_callf(BMesh *bm, int flag, const char *fmt,...)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
static bool is_quad_symmetric(BMVert *quad[4], const SkinModifierData *smd)
Definition MOD_skin.cc:182
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
static void add_quad_from_tris(SkinOutput *so, BMEdge *e, BMFace *adj[2])
Definition MOD_skin.cc:1510
static Mesh * modify_mesh(ModifierData *md, const ModifierEvalContext *ctx, Mesh *mesh)
Definition MOD_array.cc:873
bool isect_ray_tri_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void BKE_id_free(Main *bmain, void *idv)
@ eModifierTypeFlag_SupportsEditmode
@ eModifierTypeFlag_AcceptsMesh
static void skin_output_end_nodes(SkinOutput *so, SkinNode *skin_nodes, int verts_num)
Definition MOD_skin.cc:1665
static Mesh * final_skin(SkinModifierData *smd, Mesh *mesh, eSkinErrorFlag *r_error)
Definition MOD_skin.cc:1987
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
static void output_frames(BMesh *bm, SkinNode *sn, const MDeformVert *input_dvert)
Definition MOD_skin.cc:1125
static BMFace * collapse_face_corners(BMesh *bm, BMFace *f, int n, BMVert **orig_verts)
Definition MOD_skin.cc:1199
MINLINE void mul_v3_v3fl(float r[3], const float a[3], float f)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
MINLINE float normalize_v3(float n[3])
void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[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])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
static void connect_frames(SkinOutput *so, BMVert *frame1[4], BMVert *frame2[4])
Definition MOD_skin.cc:1072
static int isect_ray_poly(const float ray_start[3], const float ray_dir[3], BMFace *f, float *r_lambda)
Definition MOD_skin.cc:1161
unsigned int BLI_bitmap
Definition BLI_bitmap.hh:15
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static void node_frames_init(SkinNode *nf, int totframe)
Definition MOD_skin.cc:489
static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd)
Definition MOD_skin.cc:1519
void BM_face_kill(BMesh *bm, BMFace *f)
static void calc_edge_mat(float mat[3][3], const float a[3], const float b[3])
Definition MOD_skin.cc:695
void interp_v2_v2v2(float r[2], const float a[2], const float b[2], float t)
Mesh * BKE_mesh_from_bmesh_for_eval_nomain(BMesh *bm, const CustomData_MeshMasks *cd_mask_extra, const Mesh *me_settings)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
static void build_emats_stack(BLI_Stack *stack, BLI_bitmap *visited_e, EMat *emat, GroupedSpan< int > emap, const Span< int2 > edges, const VArray< bool > &is_root, const Span< float3 > vert_positions)
Definition MOD_skin.cc:730
void BKE_defvert_add_index_notest(MDeformVert *dv, int defgroup, float weight)
Definition deform.cc:861
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
PanelType * modifier_panel_register(ARegionType *region_type, ModifierType type, PanelDrawFn draw)
void BKE_defvert_copy(MDeformVert *dvert_dst, const MDeformVert *dvert_src)
Definition deform.cc:130
void bmesh_edit_begin(BMesh *, BMOpTypeFlag)
BMesh Begin Edit.
Mesh * BKE_mesh_new_nomain_from_template(const Mesh *me_src, int verts_num, int edges_num, int faces_num, int corners_num)
static void panel_draw(const bContext *, Panel *panel)
MINLINE float interpf(float target, float origin, float t)
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
void zero_m3(float m[3][3])
static bool skin_output_branch_hulls(SkinOutput *so, SkinNode *skin_nodes, int verts_num, GroupedSpan< int > emap, const Span< int2 > edges)
Definition MOD_skin.cc:1818
void BMO_op_init(BMesh *bm, BMOperator *op, int flag, const char *opname)
BMESH OPSTACK INIT OP.
static void skin_hole_detach_partially_attached_frame(BMesh *bm, Frame *frame)
Definition MOD_skin.cc:1454
static void merge_frame_corners(Frame **frames, int totframe)
Definition MOD_skin.cc:394
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool BM_face_is_normal_valid(const BMFace *f)
void bmesh_edit_end(BMesh *bm, BMOpTypeFlag type_flag)
BMesh End Edit.
BLI_INLINE void BMO_slot_map_elem_insert(BMOperator *op, BMOpSlot *slot, const void *element, void *val)
static void add_poly(SkinOutput *so, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4)
Definition MOD_skin.cc:1054
@ BMO_ERROR_CANCEL
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
void BMO_pop(BMesh *bm)
BMESH OPSTACK POP.
BMesh * BM_mesh_create(const BMAllocTemplate *allocsize, const BMeshCreateParams *params)
BMesh Make Mesh.
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static void end_node_frames(int v, SkinNode *skin_nodes, const Span< float3 > vert_positions, const VArray< float2 > &radius, GroupedSpan< int > emap, EMat *emat)
Definition MOD_skin.cc:534
int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len)
Iterator as Array.
static void skin_merge_close_frame_verts(SkinNode *skin_nodes, int verts_num, GroupedSpan< int > emap, const Span< int2 > edges)
Definition MOD_skin.cc:1599
static void quad_from_tris(BMEdge *e, BMFace *adj[2], BMVert *ndx[4])
Definition MOD_skin.cc:1472
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BM_mesh_delete_hflag_tagged(BMesh *bm, const char hflag, const char htype)
static SkinNode * build_frames(const Span< float3 > vert_positions, int verts_num, const VArray< float2 > &radius, GroupedSpan< int > emap, EMat *emat)
Definition MOD_skin.cc:664
static void skin_output_connections(SkinOutput *so, SkinNode *skin_nodes, const Span< int2 > edges)
Definition MOD_skin.cc:1712
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void * CustomData_add_layer(CustomData *data, eCustomDataType type, eCDAllocType alloctype, int totelem)
static void connection_node_frames(int v, SkinNode *skin_nodes, const Span< float3 > vert_positions, const VArray< float2 > &radius, GroupedSpan< int > emap, EMat *emat)
Definition MOD_skin.cc:619
void * CustomData_bmesh_get_n(const CustomData *data, void *block, eCustomDataType type, int n)
void BKE_modifier_copydata_generic(const ModifierData *md, ModifierData *md_dst, int flag)
#define swap(a, b)
Definition sort.cc:61
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
float mat[3][3]
Definition MOD_skin.cc:123
BMVert * verts[4]
Definition MOD_skin.cc:139
struct blender::Frame::@371212255071010251171227334026130127022052335373 merge[4]
bool inside_hull[4]
Definition MOD_skin.cc:154
float co[4][3]
Definition MOD_skin.cc:141
struct MDeformWeight * dw
ui::Layout * layout
SkinModifierSymmetryAxis symmetry_axes
Frame frames[MAX_SKIN_NODE_FRAMES]
Definition MOD_skin.cc:161
SkinNodeFlag flag
Definition MOD_skin.cc:164
SkinModifierData * smd
Definition MOD_skin.cc:172
void use_property_split_set(bool is_sep)
PointerRNA op(wmOperatorType *ot, std::optional< StringRef > name, int icon, wm::OpCallContext context, eUI_Item_Flag flag)
void prop(PointerRNA *ptr, PropertyRNA *prop, int index, int value, eUI_Item_Flag flag, std::optional< StringRef > name_opt, int icon, std::optional< StringRef > placeholder=std::nullopt)
Layout & row(bool align)
#define N_(msgid)