342 const int vertex_index,
343 const bool boundary_vertex,
349 if (connected_faces.
size() <= 2 && (!boundary_vertex || connected_faces.
is_empty())) {
355 for (
const int i : connected_faces.
index_range()) {
356 bool first_edge_done =
false;
357 for (
const int corner : faces[connected_faces[i]]) {
358 const int edge = corner_edges[corner];
359 if (edges[edge][0] == vertex_index || edges[edge][1] == vertex_index) {
360 if (!first_edge_done) {
361 face_vertex_corners[i].
first = corner;
362 first_edge_done =
true;
365 face_vertex_corners[i].second = corner;
372 int shared_edge_i = -1;
376 if (boundary_vertex) {
378 for (
const int i : connected_faces.
index_range()) {
379 const int corner_1 = face_vertex_corners[i].
first;
380 const int corner_2 = face_vertex_corners[i].second;
382 corner_verts[corner_1] == vertex_index)
384 shared_edge_i = corner_edges[corner_2];
385 r_sorted_corners[0] = face_vertex_corners[i].
first;
386 std::swap(connected_faces[i], connected_faces[0]);
387 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
391 corner_verts[corner_2] == vertex_index)
393 shared_edge_i = corner_edges[corner_1];
394 r_sorted_corners[0] = face_vertex_corners[i].second;
395 std::swap(connected_faces[i], connected_faces[0]);
396 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
400 if (shared_edge_i == -1) {
403 for (
const int i : connected_faces.
index_range()) {
404 const int corner_1 = face_vertex_corners[i].
first;
405 const int corner_2 = face_vertex_corners[i].second;
407 shared_edge_i = corner_edges[corner_2];
408 r_sorted_corners[0] = face_vertex_corners[i].
first;
409 std::swap(connected_faces[i], connected_faces[0]);
410 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
414 shared_edge_i = corner_edges[corner_1];
415 r_sorted_corners[0] = face_vertex_corners[i].second;
416 std::swap(connected_faces[i], connected_faces[0]);
417 std::swap(face_vertex_corners[i], face_vertex_corners[0]);
425 const int corner_1 = face_vertex_corners.
first().first;
426 const int corner_2 = face_vertex_corners.
first().second;
427 if (corner_verts[corner_1] == vertex_index) {
428 shared_edge_i = corner_edges[corner_2];
429 r_sorted_corners[0] = face_vertex_corners[0].
first;
432 r_sorted_corners[0] = face_vertex_corners[0].second;
433 shared_edge_i = corner_edges[corner_1];
439 r_shared_edges[i] = shared_edge_i;
443 for (; j < connected_faces.
size(); ++j) {
444 const int corner_1 = face_vertex_corners[j].
first;
445 const int corner_2 = face_vertex_corners[j].second;
447 if (corner_edges[corner_1] == shared_edge_i) {
448 r_sorted_corners[i + 1] = face_vertex_corners[j].
first;
449 shared_edge_i = corner_edges[corner_2];
452 if (corner_edges[corner_2] == shared_edge_i) {
453 r_sorted_corners[i + 1] = face_vertex_corners[j].second;
454 shared_edge_i = corner_edges[corner_1];
458 if (j == connected_faces.
size()) {
464 std::swap(connected_faces[i + 1], connected_faces[j]);
465 std::swap(face_vertex_corners[i + 1], face_vertex_corners[j]);
468 if (!boundary_vertex) {
470 r_shared_edges.
last() = shared_edge_i;
634 const bool keep_boundaries,
637 const Span<float3> src_positions = src_mesh.vert_positions();
638 const Span<int2> src_edges = src_mesh.edges();
640 const Span<int> src_corner_verts = src_mesh.corner_verts();
641 const Span<int> src_corner_edges = src_mesh.corner_edges();
649 Array<int> vert_to_face_indices = src_mesh.vert_to_face_map().data;
655 for (const int i : range) {
656 if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
657 (!keep_boundaries && vertex_types[i] == VertexType::Boundary))
662 MutableSpan<int> corner_indices = vert_to_face_indices.as_mutable_span().slice(
663 vert_to_face_offsets[i]);
664 Array<int> sorted_corners(corner_indices.size());
665 bool vertex_ok = true;
666 if (vertex_types[i] == VertexType::Normal) {
667 Array<int> shared_edges(corner_indices.size());
668 vertex_ok = sort_vertex_faces(src_edges,
678 vertex_shared_edges[i] = std::move(shared_edges);
681 Array<int> shared_edges(corner_indices.size() - 1);
682 vertex_ok = sort_vertex_faces(src_edges,
692 vertex_shared_edges[i] = std::move(shared_edges);
697 vertex_types[i] = VertexType::NonManifold;
700 vertex_corners[i] = std::move(sorted_corners);
704 const GroupedSpan<int> vert_to_face_map(vert_to_face_offsets, vert_to_face_indices);
707 for (
const int i : src_faces.index_range()) {
713 if (keep_boundaries) {
715 boundary_edge_midpoint_index.
reinitialize(src_mesh.edges_num);
717 for (
const int i :
IndexRange(src_mesh.edges_num)) {
719 const int2 &edge = src_edges[i];
721 boundary_edge_midpoint_index[i] = vert_positions.
size();
722 vert_positions.append(mid);
727 Vector<int> face_sizes;
728 Vector<int> corner_verts;
729 Vector<int> corner_edges;
730 Vector<int2> new_edges;
732 Vector<int> new_to_old_face_corners_map;
733 Vector<int> new_to_old_edges_map;
735 Vector<std::pair<int, int>> boundary_vertex_to_relevant_face_map;
741 Array<int> old_to_new_edges_map(src_mesh.edges_num);
742 old_to_new_edges_map.fill(-1);
751 old_to_new_edges_map,
753 new_to_old_edges_map);
755 for (
const int i :
IndexRange(src_mesh.verts_num)) {
763 Vector<int> corner_indices = vert_to_face_map[i];
764 Span<int> shared_edges = vertex_shared_edges[i];
765 Span<int> sorted_corners = vertex_corners[i];
767 if (corner_indices.size() <= 2) {
774 const int old_edge_i = shared_edges[i];
775 if (old_to_new_edges_map[old_edge_i] == -1) {
777 new_to_old_edges_map.append(old_edge_i);
778 old_to_new_edges_map[old_edge_i] = new_edges.size();
779 new_edges.append({corner_indices[i], corner_indices[(i + 1) % corner_indices.size()]});
781 corner_edges.append(old_to_new_edges_map[old_edge_i]);
784 new_to_old_face_corners_map.extend(sorted_corners);
813 const int old_edge_i = shared_edges[i];
814 if (old_to_new_edges_map[old_edge_i] == -1) {
816 new_to_old_edges_map.append(old_edge_i);
817 old_to_new_edges_map[old_edge_i] = new_edges.size();
818 new_edges.append({corner_indices[i], corner_indices[i + 1]});
820 corner_edges.append(old_to_new_edges_map[old_edge_i]);
823 new_to_old_face_corners_map.extend(sorted_corners);
830 if (corner_indices.size() >= 2) {
833 src_corner_edges.slice(src_faces[corner_indices.last()]),
838 src_corner_edges.slice(src_faces[corner_indices.first()]),
855 const int last_face_center = corner_indices.last();
856 corner_indices.append(boundary_edge_midpoint_index[edge1]);
857 new_to_old_face_corners_map.append(sorted_corners.
last());
858 const int first_midpoint = corner_indices.last();
859 if (old_to_new_edges_map[edge1] == -1) {
863 new_to_old_edges_map,
866 old_to_new_edges_map[edge1] = new_edges.size() - 1;
867 boundary_vertex_to_relevant_face_map.append(std::pair(first_midpoint, last_face_center));
870 corner_edges.append(old_to_new_edges_map[edge1]);
872 corner_indices.append(vert_positions.size());
874 new_to_old_face_corners_map.append(sorted_corners.
first());
875 boundary_vertex_to_relevant_face_map.append(
876 std::pair(corner_indices.last(), last_face_center));
877 vert_positions.append(src_positions[i]);
878 const int boundary_vertex = corner_indices.last();
880 edge1, first_midpoint, boundary_vertex, new_to_old_edges_map, new_edges, corner_edges);
882 corner_indices.append(boundary_edge_midpoint_index[edge2]);
883 new_to_old_face_corners_map.append(sorted_corners.
first());
884 const int second_midpoint = corner_indices.last();
886 edge2, boundary_vertex, second_midpoint, new_to_old_edges_map, new_edges, corner_edges);
888 if (old_to_new_edges_map[edge2] == -1) {
889 const int first_face_center = corner_indices.first();
893 new_to_old_edges_map,
896 old_to_new_edges_map[edge2] = new_edges.size() - 1;
897 boundary_vertex_to_relevant_face_map.append(std::pair(second_midpoint, first_face_center));
900 corner_edges.append(old_to_new_edges_map[edge2]);
904 face_sizes.append(corner_indices.size());
905 corner_verts.extend(corner_indices);
908 vert_positions.size(), new_edges.size(), face_sizes.size(), corner_verts.size());
911 std::ranges::sort(boundary_vertex_to_relevant_face_map,
912 [](
const auto &a,
const auto &
b) {
return a.first <
b.first; });
916 new_to_old_edges_map,
917 new_to_old_face_corners_map,
918 boundary_vertex_to_relevant_face_map,
920 src_mesh.attributes(),
921 mesh_out->attributes_for_write());
923 mesh_out->vert_positions_for_write().copy_from(vert_positions);
924 mesh_out->edges_for_write().copy_from(new_edges);
926 if (mesh_out->faces_num > 0) {
927 MutableSpan<int> dst_face_offsets = mesh_out->face_offsets_for_write();
928 dst_face_offsets.drop_back(1).copy_from(face_sizes);
931 mesh_out->corner_verts_for_write().copy_from(corner_verts);
932 mesh_out->corner_edges_for_write().copy_from(corner_edges);