blender
/
blender
136
404
Fork 586
Code Issues 6.2k Pull Requests 753 Projects 19 Wiki Activity

Merge branch 'refactor-mesh-position-generic' into refactor-mesh-corners-generic

This commit is contained in:
Hans Goudey 2022-12-13 18:44:17 -06:00
parent 8e2dae3f8d 9c081829ae
commit d2fd7fc176
12 changed files with 590 additions and 770 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

1
intern/cycles/blender/util.h
View File

@ -113,6 +113,7 @@ static inline BL::Mesh object_to_mesh(BL::BlendData & /*data*/,
if ((bool)mesh && subdivision_type == Mesh::SUBDIVISION_NONE) {
if (mesh.use_auto_smooth()) {
mesh.calc_normals_split();
mesh.split_faces(false);
}

8
source/blender/blenkernel/BKE_mesh.h
View File

@ -255,14 +255,6 @@ void BKE_mesh_texspace_get_reference(struct Mesh *me,
float **r_size);
void BKE_mesh_texspace_copy_from_object(struct Mesh *me, struct Object *ob);
/**
* Split faces based on the edge angle and loop normals.
* Matches behavior of face splitting in render engines.
*
* \note Will leave #CD_NORMAL loop data layer which is used by render engines to set shading up.
*/
void BKE_mesh_split_faces(struct Mesh *mesh, bool free_loop_normals);
/**
* Create new mesh from the given object at its current state.
* The owner of this mesh is unknown, it is up to the caller to decide.

262
source/blender/blenkernel/intern/mesh.cc
View File

@ -1811,268 +1811,6 @@ void BKE_mesh_calc_normals_split(Mesh *mesh)
BKE_mesh_calc_normals_split_ex(mesh, nullptr, ensure_corner_normal_layer(*mesh));
}
/* Split faces helper functions. */
struct SplitFaceNewVert {
struct SplitFaceNewVert *next;
int new_index;
int orig_index;
const float *vnor;
};
struct SplitFaceNewEdge {
struct SplitFaceNewEdge *next;
int new_index;
int orig_index;
int v1;
int v2;
};
/**
* Detect necessary new vertices, and update loop vertex indices accordingly.
* \warning Leaves mesh in invalid state.
* \param lnors_spacearr: Mandatory because trying to do the job in simple way without that data is
* doomed to fail, even when only dealing with smooth/flat faces one can find cases that no simple
* algorithm can handle properly.
*/
static int split_faces_prepare_new_verts(Mesh &mesh,
const MLoopNorSpaceArray &lnors_spacearr,
SplitFaceNewVert **new_verts,
MemArena &memarena)
{
const int loops_len = mesh.totloop;
int verts_len = mesh.totvert;
MutableSpan<int> corner_verts = mesh.corner_verts_for_write();
BKE_mesh_vertex_normals_ensure(&mesh);
float(*vert_normals)[3] = BKE_mesh_vertex_normals_for_write(&mesh);
BitVector<> verts_used(verts_len, false);
BitVector<> done_loops(loops_len, false);
BLI_assert(lnors_spacearr.data_type == MLNOR_SPACEARR_LOOP_INDEX);
for (int loop_idx = 0; loop_idx < loops_len; loop_idx++) {
if (done_loops[loop_idx]) {
continue;
}
const MLoopNorSpace &lnor_space = *lnors_spacearr.lspacearr[loop_idx];
const int vert_idx = corner_verts[loop_idx];
const bool vert_used = verts_used[vert_idx];
/* If vert is already used by another smooth fan, we need a new vert for this one. */
const int new_vert_idx = vert_used ? verts_len++ : vert_idx;
if (lnor_space.flags & MLNOR_SPACE_IS_SINGLE) {
/* Single loop in this fan... */
BLI_assert(POINTER_AS_INT(lnor_space.loops) == loop_idx);
done_loops[loop_idx].set();
if (vert_used) {
corner_verts[loop_idx] = new_vert_idx;
}
}
else {
for (const LinkNode *lnode = lnor_space.loops; lnode; lnode = lnode->next) {
const int ml_fan_idx = POINTER_AS_INT(lnode->link);
done_loops[ml_fan_idx].set();
if (vert_used) {
corner_verts[ml_fan_idx] = new_vert_idx;
}
}
}
if (!vert_used) {
verts_used[vert_idx].set();
/* We need to update that vertex's normal here, we won't go over it again. */
/* This is important! *DO NOT* set vnor to final computed lnor,
* vnor should always be defined to 'automatic normal' value computed from its polys,
* not some custom normal.
* Fortunately, that's the loop normal space's 'lnor' reference vector. ;) */
copy_v3_v3(vert_normals[vert_idx], lnor_space.vec_lnor);
}
else {
/* Add new vert to list. */
SplitFaceNewVert *new_vert = static_cast<SplitFaceNewVert *>(
BLI_memarena_alloc(&memarena, sizeof(*new_vert)));
new_vert->orig_index = vert_idx;
new_vert->new_index = new_vert_idx;
new_vert->vnor = lnor_space.vec_lnor; /* See note above. */
new_vert->next = *new_verts;
*new_verts = new_vert;
}
}
return verts_len - mesh.totvert;
}
/* Detect needed new edges, and update accordingly loops' edge indices.
* WARNING! Leaves mesh in invalid state. */
static int split_faces_prepare_new_edges(Mesh *mesh,
SplitFaceNewEdge **new_edges,
MemArena *memarena)
{
const int num_polys = mesh->totpoly;
int num_edges = mesh->totedge;
MutableSpan<MEdge> edges = mesh->edges_for_write();
MutableSpan<int> corner_verts = mesh->corner_verts_for_write();
MutableSpan<int> corner_edges = mesh->corner_edges_for_write();
const Span<MPoly> polys = mesh->polys();
BitVector<> edges_used(num_edges, false);
EdgeHash *edges_hash = BLI_edgehash_new_ex(__func__, num_edges);
const MPoly *mp = polys.data();
for (int poly_idx = 0; poly_idx < num_polys; poly_idx++, mp++) {
int corner_i_prev = mp->loopstart + mp->totloop - 1;
for (int loop_idx = 0; loop_idx < mp->totloop; loop_idx++) {
void **eval;
if (!BLI_edgehash_ensure_p(
edges_hash, corner_verts[corner_i_prev], corner_verts[loop_idx], &eval)) {
const int edge_idx = corner_edges[corner_i_prev];
/* That edge has not been encountered yet, define it. */
if (edges_used[edge_idx]) {
/* Original edge has already been used, we need to define a new one. */
const int new_edge_idx = num_edges++;
*eval = POINTER_FROM_INT(new_edge_idx);
corner_edges[corner_i_prev] = new_edge_idx;
SplitFaceNewEdge *new_edge = (SplitFaceNewEdge *)BLI_memarena_alloc(memarena,
sizeof(*new_edge));
new_edge->orig_index = edge_idx;
new_edge->new_index = new_edge_idx;
new_edge->v1 = corner_verts[corner_i_prev];
new_edge->v2 = corner_verts[loop_idx];
new_edge->next = *new_edges;
*new_edges = new_edge;
}
else {
/* We can re-use original edge. */
edges[edge_idx].v1 = corner_verts[corner_i_prev];
edges[edge_idx].v2 = corner_verts[loop_idx];
*eval = POINTER_FROM_INT(edge_idx);
edges_used[edge_idx].set();
}
}
else {
/* Edge already known, just update loop's edge index. */
corner_edges[corner_i_prev] = POINTER_AS_INT(*eval);
}
corner_i_prev = loop_idx;
}
}
BLI_edgehash_free(edges_hash, nullptr);
return num_edges - mesh->totedge;
}
/* Perform actual split of vertices. */
static void split_faces_split_new_verts(Mesh *mesh,
SplitFaceNewVert *new_verts,
const int num_new_verts)
{
const int verts_len = mesh->totvert - num_new_verts;
float(*vert_normals)[3] = BKE_mesh_vertex_normals_for_write(mesh);
/* Normals were already calculated at the beginning of this operation, we rely on that to update
* them partially here. */
BLI_assert(!BKE_mesh_vertex_normals_are_dirty(mesh));
/* Remember new_verts is a single linklist, so its items are in reversed order... */
for (int i = mesh->totvert - 1; i >= verts_len; i--, new_verts = new_verts->next) {
BLI_assert(new_verts->new_index == i);
BLI_assert(new_verts->new_index != new_verts->orig_index);
CustomData_copy_data(&mesh->vdata, &mesh->vdata, new_verts->orig_index, i, 1);
if (new_verts->vnor) {
copy_v3_v3(vert_normals[i], new_verts->vnor);
}
}
}
/* Perform actual split of edges. */
static void split_faces_split_new_edges(Mesh *mesh,
SplitFaceNewEdge *new_edges,
const int num_new_edges)
{
const int num_edges = mesh->totedge - num_new_edges;
MutableSpan<MEdge> edges = mesh->edges_for_write();
/* Remember new_edges is a single linklist, so its items are in reversed order... */
MEdge *new_med = &edges[mesh->totedge - 1];
for (int i = mesh->totedge - 1; i >= num_edges; i--, new_med--, new_edges = new_edges->next) {
BLI_assert(new_edges->new_index == i);
BLI_assert(new_edges->new_index != new_edges->orig_index);
CustomData_copy_data(&mesh->edata, &mesh->edata, new_edges->orig_index, i, 1);
new_med->v1 = new_edges->v1;
new_med->v2 = new_edges->v2;
}
}
void BKE_mesh_split_faces(Mesh *mesh, bool free_loop_normals)
{
const int num_polys = mesh->totpoly;
if (num_polys == 0) {
return;
}
BKE_mesh_tessface_clear(mesh);
MLoopNorSpaceArray lnors_spacearr = {nullptr};
/* Compute loop normals and loop normal spaces (a.k.a. smooth fans of faces around vertices). */
BKE_mesh_calc_normals_split_ex(mesh, &lnors_spacearr, ensure_corner_normal_layer(*mesh));
/* Stealing memarena from loop normals space array. */
MemArena *memarena = lnors_spacearr.mem;
SplitFaceNewVert *new_verts = nullptr;
SplitFaceNewEdge *new_edges = nullptr;
/* Detect loop normal spaces (a.k.a. smooth fans) that will need a new vert. */
const int num_new_verts = split_faces_prepare_new_verts(
*mesh, lnors_spacearr, &new_verts, *memarena);
if (num_new_verts > 0) {
/* Reminder: beyond this point, there is no way out, mesh is in invalid state
* (due to early-reassignment of loops' vertex and edge indices to new,
* to-be-created split ones). */
const int num_new_edges = split_faces_prepare_new_edges(mesh, &new_edges, memarena);
/* We can have to split a vertex without having to add a single new edge... */
const bool do_edges = (num_new_edges > 0);
/* Reallocate all vert and edge related data. */
CustomData_realloc(&mesh->vdata, mesh->totvert, mesh->totvert + num_new_verts);
mesh->totvert += num_new_verts;
if (do_edges) {
CustomData_realloc(&mesh->edata, mesh->totedge, mesh->totedge + num_new_edges);
mesh->totedge += num_new_edges;
}
/* Update normals manually to avoid recalculation after this operation. */
mesh->runtime->vert_normals = (float(*)[3])MEM_reallocN(mesh->runtime->vert_normals,
sizeof(float[3]) * mesh->totvert);
/* Perform actual split of vertices and edges. */
split_faces_split_new_verts(mesh, new_verts, num_new_verts);
if (do_edges) {
split_faces_split_new_edges(mesh, new_edges, num_new_edges);
}
}
/* NOTE: after this point mesh is expected to be valid again. */
/* CD_NORMAL is expected to be temporary only. */
if (free_loop_normals) {
CustomData_free_layers(&mesh->ldata, CD_NORMAL, mesh->totloop);
}
/* Also frees new_verts/edges temp data, since we used its memarena to allocate them. */
BKE_lnor_spacearr_free(&lnors_spacearr);
#ifdef VALIDATE_MESH
BKE_mesh_validate(mesh, true, true);
#endif
}
/* **** Depsgraph evaluation **** */
void BKE_mesh_eval_geometry(Depsgraph *depsgraph, Mesh *mesh)

6
source/blender/editors/include/ED_mesh.h
View File

@ -581,6 +581,12 @@ void ED_mesh_report_mirror_ex(struct wmOperator *op, int totmirr, int totfail, c
*/
struct Mesh *ED_mesh_context(struct bContext *C);
/**
* Split all edges that would appear sharp based onface and edge sharpness tags and the auto smooth
* angle.
*/
void ED_mesh_split_faces(struct Mesh *mesh);
/* mesh backup */
typedef struct BMBackup {
struct BMesh *bmcopy;

12
source/blender/editors/mesh/CMakeLists.txt
View File

@ -10,6 +10,7 @@ set(INC
../../bmesh
../../depsgraph
../../draw
../../geometry
../../gpu
../../imbuf
../../makesdna
@ -76,6 +77,17 @@ if(WITH_GMP)
add_definitions(-DWITH_GMP)
endif()
if(WITH_TBB)
add_definitions(-DWITH_TBB)
list(APPEND INC_SYS
${TBB_INCLUDE_DIRS}
)
list(APPEND LIB
${TBB_LIBRARIES}
)
endif()
blender_add_lib(bf_editor_mesh "${SRC}" "${INC}" "${INC_SYS}" "${LIB}")

43
source/blender/editors/mesh/mesh_data.cc
View File

@ -14,6 +14,7 @@
#include "DNA_view3d_types.h"
#include "BLI_array.hh"
#include "BLI_index_mask_ops.hh"
#include "BLI_math.h"
#include "BLI_utildefines.h"
@ -42,6 +43,8 @@
#include "ED_uvedit.h"
#include "ED_view3d.h"
#include "GEO_mesh_split_edges.hh"
#include "mesh_intern.h" /* own include */
using blender::Array;
@ -1471,3 +1474,43 @@ Mesh *ED_mesh_context(bContext *C)
return (Mesh *)data;
}
void ED_mesh_split_faces(Mesh *mesh)
{
using namespace blender;
Array<MEdge> edges(mesh->edges());
const Span<MPoly> polys = mesh->polys();
const Span<MLoop> loops = mesh->loops();
const float split_angle = (mesh->flag & ME_AUTOSMOOTH) != 0 ? mesh->smoothresh : float(M_PI);
BKE_edges_sharp_from_angle_set(edges.data(),
edges.size(),
loops.data(),
loops.size(),
polys.data(),
BKE_mesh_poly_normals_ensure(mesh),
polys.size(),
split_angle);
threading::parallel_for(polys.index_range(), 1024, [&](const IndexRange range) {
for (const int poly_i : range) {
const MPoly &poly = polys[poly_i];
if (!(poly.flag & ME_SMOOTH)) {
for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
edges[loop.e].flag |= ME_SHARP;
}
}
}
});
Vector<int64_t> split_indices;
const IndexMask split_mask = index_mask_ops::find_indices_based_on_predicate(
edges.index_range(), 4096, split_indices, [&](const int64_t i) {
return edges[i].flag & ME_SHARP;
});
if (split_mask.is_empty()) {
return;
}
geometry::split_edges(*mesh, split_mask);
}

4
source/blender/editors/object/object_bake_api.c
View File

@ -55,6 +55,7 @@
#include "WM_api.h"
#include "WM_types.h"
#include "ED_mesh.h"
#include "ED_object.h"
#include "ED_screen.h"
#include "ED_uvedit.h"
@ -670,7 +671,8 @@ static Mesh *bake_mesh_new_from_object(Depsgraph *depsgraph,
Mesh *me = BKE_mesh_new_from_object(depsgraph, object, false, preserve_origindex);
if (me->flag & ME_AUTOSMOOTH) {
BKE_mesh_split_faces(me, true);
ED_mesh_split_faces(me);
CustomData_free_layers(&me->ldata, CD_NORMAL, me->totloop);
}
return me;

2
source/blender/geometry/CMakeLists.txt
View File

@ -19,6 +19,7 @@ set(SRC
intern/fillet_curves.cc
intern/mesh_merge_by_distance.cc
intern/mesh_primitive_cuboid.cc
intern/mesh_split_edges.cc
intern/mesh_to_curve_convert.cc
intern/mesh_to_volume.cc
intern/point_merge_by_distance.cc
@ -34,6 +35,7 @@ set(SRC
GEO_fillet_curves.hh
GEO_mesh_merge_by_distance.hh
GEO_mesh_primitive_cuboid.hh
GEO_mesh_split_edges.hh
GEO_mesh_to_curve.hh
GEO_mesh_to_volume.hh
GEO_point_merge_by_distance.hh

13
source/blender/geometry/GEO_mesh_split_edges.hh Normal file
View File

@ -0,0 +1,13 @@
/* SPDX-License-Identifier: GPL-2.0-or-later */
#pragma once
#include "BLI_index_mask.hh"
struct Mesh;
namespace blender::geometry {
void split_edges(Mesh &mesh, IndexMask mask);
} // namespace blender::geometry

503
source/blender/geometry/intern/mesh_split_edges.cc Normal file
View File

@ -0,0 +1,503 @@
/* SPDX-License-Identifier: GPL-2.0-or-later */
#include "BLI_array_utils.hh"
#include "BLI_devirtualize_parameters.hh"
#include "BLI_index_mask.hh"
#include "BKE_attribute.hh"
#include "BKE_attribute_math.hh"
#include "BKE_mesh.h"
#include "BKE_mesh_mapping.h"
#include "GEO_mesh_split_edges.hh"
namespace blender::geometry {
/* Naively checks if the first vertices and the second vertices are the same. */
static inline bool naive_edges_equal(const MEdge &edge1, const MEdge &edge2)
{
return edge1.v1 == edge2.v1 && edge1.v2 == edge2.v2;
}
template<typename T>
static void copy_to_new_verts(MutableSpan<T> data, const Span<int> new_to_old_verts_map)
{
const Span<T> old_data = data.drop_back(new_to_old_verts_map.size());
MutableSpan<T> new_data = data.take_back(new_to_old_verts_map.size());
array_utils::gather(old_data, new_to_old_verts_map, new_data);
}
static void add_new_vertices(Mesh &mesh, const Span<int> new_to_old_verts_map)
{
CustomData_realloc(&mesh.vdata, mesh.totvert, mesh.totvert + new_to_old_verts_map.size());
mesh.totvert += new_to_old_verts_map.size();
bke::MutableAttributeAccessor attributes = mesh.attributes_for_write();
for (const bke::AttributeIDRef &id : attributes.all_ids()) {
if (attributes.lookup_meta_data(id)->domain != ATTR_DOMAIN_POINT) {
continue;
}
bke::GSpanAttributeWriter attribute = attributes.lookup_for_write_span(id);
if (!attribute) {
continue;
}
attribute_math::convert_to_static_type(attribute.span.type(), [&](auto dummy) {
using T = decltype(dummy);
copy_to_new_verts(attribute.span.typed<T>(), new_to_old_verts_map);
});
attribute.finish();
}
if (float3 *orco = static_cast<float3 *>(CustomData_get_layer(&mesh.vdata, CD_ORCO))) {
copy_to_new_verts<float3>({orco, mesh.totvert}, new_to_old_verts_map);
}
if (int *orig_indices = static_cast<int *>(CustomData_get_layer(&mesh.vdata, CD_ORIGINDEX))) {
copy_to_new_verts<int>({orig_indices, mesh.totvert}, new_to_old_verts_map);
}
}
static void add_new_edges(Mesh &mesh,
const Span<MEdge> new_edges,
const Span<int> new_to_old_edges_map)
{
bke::MutableAttributeAccessor attributes = mesh.attributes_for_write();
/* Store a copy of the IDs locally since we will remove the existing attributes which
* can also free the names, since the API does not provide pointer stability. */
Vector<std::string> named_ids;
Vector<bke::WeakAnonymousAttributeID> anonymous_ids;
for (const bke::AttributeIDRef &id : attributes.all_ids()) {
if (attributes.lookup_meta_data(id)->domain != ATTR_DOMAIN_EDGE) {
continue;
}
if (!id.should_be_kept()) {
continue;
}
if (id.is_named()) {
named_ids.append(id.name());
}
else {
anonymous_ids.append(bke::WeakAnonymousAttributeID(&id.anonymous_id()));
}
}
Vector<bke::AttributeIDRef> local_edge_ids;
for (const StringRef name : named_ids) {
local_edge_ids.append(name);
}
for (const bke::WeakAnonymousAttributeID &id : anonymous_ids) {
local_edge_ids.append(id.get());
}
/* Build new arrays for the copied edge attributes. Unlike vertices, new edges aren't all at the
* end of the array, so just copying to the new edges would overwrite old values when they were
* still needed. */
struct NewAttributeData {
const bke::AttributeIDRef &local_id;
const CPPType &type;
void *array;
};
Vector<NewAttributeData> dst_attributes;
for (const bke::AttributeIDRef &id : local_edge_ids) {
bke::GAttributeReader attribute = attributes.lookup(id);
if (!attribute) {
continue;
}
const CPPType &type = attribute.varray.type();
void *new_data = MEM_malloc_arrayN(new_edges.size(), type.size(), __func__);
attribute_math::convert_to_static_type(type, [&](auto dummy) {
using T = decltype(dummy);
const VArray<T> src = attribute.varray.typed<T>();
MutableSpan<T> dst(static_cast<T *>(new_data), new_edges.size());
array_utils::gather(src, new_to_old_edges_map, dst);
});
/* Free the original attribute as soon as possible to lower peak memory usage. */
attributes.remove(id);
dst_attributes.append({id, type, new_data});
}
int *new_orig_indices = nullptr;
if (const int *orig_indices = static_cast<const int *>(
CustomData_get_layer(&mesh.edata, CD_ORIGINDEX))) {
new_orig_indices = static_cast<int *>(
MEM_malloc_arrayN(new_edges.size(), sizeof(int), __func__));
array_utils::gather(Span(orig_indices, mesh.totedge),
new_to_old_edges_map,
{new_orig_indices, new_edges.size()});
}
CustomData_free(&mesh.edata, mesh.totedge);
mesh.totedge = new_edges.size();
CustomData_add_layer(&mesh.edata, CD_MEDGE, CD_CONSTRUCT, nullptr, mesh.totedge);
mesh.edges_for_write().copy_from(new_edges);
if (new_orig_indices != nullptr) {
CustomData_add_layer(&mesh.edata, CD_ORIGINDEX, CD_ASSIGN, new_orig_indices, mesh.totedge);
}
for (NewAttributeData &new_data : dst_attributes) {
attributes.add(new_data.local_id,
ATTR_DOMAIN_EDGE,
bke::cpp_type_to_custom_data_type(new_data.type),
bke::AttributeInitMoveArray(new_data.array));
}
}
/**
* Merge the new_edge into the original edge.
*
* NOTE: This function is very specific to the situation and makes a lot of assumptions.
*/
static void merge_edges(const int orig_edge_i,
const int new_edge_i,
MutableSpan<int> new_corner_edges,
Vector<Vector<int>> &edge_to_loop_map,
Vector<MEdge> &new_edges,
Vector<int> &new_to_old_edges_map)
{
/* Merge back into the original edge by undoing the topology changes. */
BLI_assert(edge_to_loop_map[new_edge_i].size() == 1);
const int loop_i = edge_to_loop_map[new_edge_i][0];
new_corner_edges[loop_i] = orig_edge_i;
/* We are putting the last edge in the location of new_edge in all the maps, to remove
* new_edge efficiently. We have to update the topology information for this last edge
* though. Essentially we are replacing every instance of last_edge_i with new_edge_i. */
const int last_edge_i = new_edges.size() - 1;
if (last_edge_i != new_edge_i) {
BLI_assert(edge_to_loop_map[last_edge_i].size() == 1);
const int last_edge_loop_i = edge_to_loop_map[last_edge_i][0];
new_corner_edges[last_edge_loop_i] = new_edge_i;
}
/* We can now safely swap-remove. */
new_edges.remove_and_reorder(new_edge_i);
edge_to_loop_map.remove_and_reorder(new_edge_i);
new_to_old_edges_map.remove_and_reorder(new_edge_i);
}
/**
* Replace the vertex of an edge with a new one, and update the connected loops.
*
* NOTE: This only updates the loops containing the edge and the old vertex. It should therefore
* also be called on the adjacent edge.
*/
static void swap_vertex_of_edge(MEdge &edge,
const int old_vert,
const int new_vert,
MutableSpan<int> corner_verts,
const Span<int> connected_loops)
{
if (edge.v1 == old_vert) {
edge.v1 = new_vert;
}
else if (edge.v2 == old_vert) {
edge.v2 = new_vert;
}
else {
BLI_assert_unreachable();
}
for (const int loop_i : connected_loops) {
if (corner_verts[loop_i] == old_vert) {
corner_verts[loop_i] = new_vert;
}
/* The old vertex is on the loop containing the adjacent edge. Since this function is also
* called on the adjacent edge, we don't replace it here. */
}
}
/** Split the vertex into duplicates so that each fan has a different vertex. */
static void split_vertex_per_fan(const int vertex,
const int start_offset,
const int orig_verts_num,
const Span<int> fans,
const Span<int> fan_sizes,
const Span<Vector<int>> edge_to_loop_map,
MutableSpan<MEdge> new_edges,
MutableSpan<int> corner_verts,
MutableSpan<int> new_to_old_verts_map)
{
int fan_start = 0;
/* We don't need to create a new vertex for the last fan. That fan can just be connected to the
* original vertex. */
for (const int i : fan_sizes.index_range().drop_back(1)) {
const int new_vert_i = start_offset + i;
new_to_old_verts_map[new_vert_i - orig_verts_num] = vertex;
for (const int edge_i : fans.slice(fan_start, fan_sizes[i])) {
swap_vertex_of_edge(
new_edges[edge_i], vertex, new_vert_i, corner_verts, edge_to_loop_map[edge_i]);
}
fan_start += fan_sizes[i];
}
}
/**
* Get the index of the adjacent edge to a loop connected to a vertex. In other words, for the
* given polygon return the unique edge connected to the given vertex and not on the given loop.
*/
static int adjacent_edge(const Span<int> corner_verts,
const Span<int> corner_edges,
const int loop_i,
const MPoly &poly,
const int vertex)
{
const int adjacent_loop_i = (corner_verts[loop_i] == vertex) ?
bke::mesh_topology::poly_loop_prev(poly, loop_i) :
bke::mesh_topology::poly_loop_next(poly, loop_i);
return corner_edges[adjacent_loop_i];
}
/**
* Calculate the disjoint fans connected to the vertex, where a fan is a group of edges connected
* through polygons. The connected_edges vector is rearranged in such a way that edges in the same
* fan are grouped together. The r_fans_sizes Vector gives the sizes of the different fans, and can
* be used to retrieve the fans from connected_edges.
*/
static void calc_vertex_fans(const int vertex,
const Span<int> new_corner_verts,
const Span<int> new_corner_edges,
const Span<MPoly> polys,
const Span<Vector<int>> edge_to_loop_map,
const Span<int> loop_to_poly_map,
MutableSpan<int> connected_edges,
Vector<int> &r_fan_sizes)
{
if (connected_edges.size() <= 1) {
r_fan_sizes.append(connected_edges.size());
return;
}
Vector<int> search_edges;
int total_found_edges_num = 0;
int fan_size = 0;
const int total_edge_num = connected_edges.size();
/* Iteratively go through the connected edges. The front contains already handled edges, while
* the back contains unhandled edges. */
while (true) {
/* This edge has not been visited yet. */
int curr_i = total_found_edges_num;
int curr_edge_i = connected_edges[curr_i];
/* Gather all the edges in this fan. */
while (true) {
fan_size++;
/* Add adjacent edges to search stack. */
for (const int loop_i : edge_to_loop_map[curr_edge_i]) {
const int adjacent_edge_i = adjacent_edge(
new_corner_verts, new_corner_edges, loop_i, polys[loop_to_poly_map[loop_i]], vertex);
/* Find out if this edge was visited already. */
int i = curr_i + 1;
for (; i < total_edge_num; i++) {
if (connected_edges[i] == adjacent_edge_i) {
break;
}
}
if (i == total_edge_num) {
/* Already visited this edge. */
continue;
}
search_edges.append(adjacent_edge_i);
curr_i++;
std::swap(connected_edges[curr_i], connected_edges[i]);
}
if (search_edges.is_empty()) {
break;
}
curr_edge_i = search_edges.pop_last();
}
/* We have now collected all the edges in this fan. */
total_found_edges_num += fan_size;
BLI_assert(total_found_edges_num <= total_edge_num);
r_fan_sizes.append(fan_size);
if (total_found_edges_num == total_edge_num) {
/* We have found all the edges, so this final batch must be the last connected fan. */
break;
}
fan_size = 0;
}
}
/**
* Splits the edge into duplicates, so that each edge is connected to one poly.
*/
static void split_edge_per_poly(const int edge_i,
const int new_edge_start,
MutableSpan<Vector<int>> edge_to_loop_map,
MutableSpan<int> corner_edges,
MutableSpan<MEdge> new_edges,
MutableSpan<int> new_to_old_edges_map)
{
if (edge_to_loop_map[edge_i].size() <= 1) {
return;
}
int new_edge_index = new_edge_start;
for (const int loop_i : edge_to_loop_map[edge_i].as_span().drop_front(1)) {
const MEdge new_edge(new_edges[edge_i]);
new_edges[new_edge_index] = new_edge;
new_to_old_edges_map[new_edge_index] = edge_i;
edge_to_loop_map[new_edge_index].append({loop_i});
corner_edges[loop_i] = new_edge_index;
new_edge_index++;
}
/* Only the first loop is now connected to this edge. */
edge_to_loop_map[edge_i].resize(1);
}
static void mesh_edge_split(Mesh &mesh, const IndexMask mask)
{
/* Flag vertices that need to be split. */
Array<bool> should_split_vert(mesh.totvert, false);
const Span<MEdge> edges = mesh.edges();
for (const int edge_i : mask) {
const MEdge edge = edges[edge_i];
should_split_vert[edge.v1] = true;
should_split_vert[edge.v2] = true;
}
/* Precalculate topology info. */
Array<Vector<int>> vert_to_edge_map = bke::mesh_topology::build_vert_to_edge_map(edges,
mesh.totvert);
Vector<Vector<int>> edge_to_loop_map = bke::mesh_topology::build_edge_to_loop_map_resizable(
mesh.corner_edges(), mesh.totedge);
Array<int> loop_to_poly_map = bke::mesh_topology::build_loop_to_poly_map(mesh.polys(),
mesh.totloop);
/* Store offsets, so we can split edges in parallel. */
Array<int> edge_offsets(edges.size());
Array<int> num_edge_duplicates(edges.size());
int new_edges_size = edges.size();
for (const int edge : mask) {
edge_offsets[edge] = new_edges_size;
/* We add duplicates of the edge for each poly (except the first). */
const int num_connected_loops = edge_to_loop_map[edge].size();
const int num_duplicates = std::max(0, num_connected_loops - 1);
new_edges_size += num_duplicates;
num_edge_duplicates[edge] = num_duplicates;
}
const Span<MPoly> polys = mesh.polys();
MutableSpan<int> corner_verts = mesh.corner_verts_for_write();
MutableSpan<int> corner_edges = mesh.corner_edges_for_write();
Vector<MEdge> new_edges(new_edges_size);
new_edges.as_mutable_span().take_front(edges.size()).copy_from(edges);
edge_to_loop_map.resize(new_edges_size);
/* Used for transferring attributes. */
Vector<int> new_to_old_edges_map(IndexRange(new_edges.size()).as_span());
/* Step 1: Split the edges. */
threading::parallel_for(mask.index_range(), 512, [&](IndexRange range) {
for (const int mask_i : range) {
const int edge_i = mask[mask_i];
split_edge_per_poly(edge_i,
edge_offsets[edge_i],
edge_to_loop_map,
corner_edges,
new_edges,
new_to_old_edges_map);
}
});
/* Step 1.5: Update topology information (can't parallelize). */
for (const int edge_i : mask) {
const MEdge &edge = edges[edge_i];
for (const int duplicate_i : IndexRange(edge_offsets[edge_i], num_edge_duplicates[edge_i])) {
vert_to_edge_map[edge.v1].append(duplicate_i);
vert_to_edge_map[edge.v2].append(duplicate_i);
}
}
/* Step 2: Calculate vertex fans. */
Array<Vector<int>> vertex_fan_sizes(mesh.totvert);
threading::parallel_for(IndexRange(mesh.totvert), 512, [&](IndexRange range) {
for (const int vert : range) {
if (!should_split_vert[vert]) {
continue;
}
calc_vertex_fans(vert,
corner_verts,
corner_edges,
polys,
edge_to_loop_map,
loop_to_poly_map,
vert_to_edge_map[vert],
vertex_fan_sizes[vert]);
}
});
/* Step 2.5: Calculate offsets for next step. */
Array<int> vert_offsets(mesh.totvert);
int total_verts_num = mesh.totvert;
for (const int vert : IndexRange(mesh.totvert)) {
if (!should_split_vert[vert]) {
continue;
}
vert_offsets[vert] = total_verts_num;
/* We only create a new vertex for each fan different from the first. */
total_verts_num += vertex_fan_sizes[vert].size() - 1;
}
/* Step 3: Split the vertices.
* Build a map from each new vertex to an old vertex to use for transferring attributes later. */
const int new_verts_num = total_verts_num - mesh.totvert;
Array<int> new_to_old_verts_map(new_verts_num);
threading::parallel_for(IndexRange(mesh.totvert), 512, [&](IndexRange range) {
for (const int vert : range) {
if (!should_split_vert[vert]) {
continue;
}
split_vertex_per_fan(vert,
vert_offsets[vert],
mesh.totvert,
vert_to_edge_map[vert],
vertex_fan_sizes[vert],
edge_to_loop_map,
new_edges,
corner_verts,
new_to_old_verts_map);
}
});
/* Step 4: Deduplicate edges. We loop backwards so we can use remove_and_reorder. Although this
* does look bad (3 nested loops), in practice the inner loops are very small. For most meshes,
* there are at most 2 polygons connected to each edge, and hence you'll only get at most 1
* duplicate per edge. */
for (int mask_i = mask.size() - 1; mask_i >= 0; mask_i--) {
const int edge = mask[mask_i];
int start_of_duplicates = edge_offsets[edge];
int end_of_duplicates = start_of_duplicates + num_edge_duplicates[edge] - 1;
for (int duplicate = end_of_duplicates; duplicate >= start_of_duplicates; duplicate--) {
if (naive_edges_equal(new_edges[edge], new_edges[duplicate])) {
merge_edges(
edge, duplicate, corner_edges, edge_to_loop_map, new_edges, new_to_old_edges_map);
break;
}
for (int other = start_of_duplicates; other < duplicate; other++) {
if (naive_edges_equal(new_edges[other], new_edges[duplicate])) {
merge_edges(
other, duplicate, corner_edges, edge_to_loop_map, new_edges, new_to_old_edges_map);
break;
}
}
}
}
/* Step 5: Resize the mesh to add the new vertices and rebuild the edges. */
add_new_vertices(mesh, new_to_old_verts_map);
add_new_edges(mesh, new_edges, new_to_old_edges_map);
BKE_mesh_tag_edges_split(&mesh);
}
} // namespace blender::geometry

9
source/blender/makesrna/intern/rna_mesh_api.c
View File

@ -177,9 +177,9 @@ static void rna_Mesh_flip_normals(Mesh *mesh)
DEG_id_tag_update(&mesh->id, 0);
}
static void rna_Mesh_split_faces(Mesh *mesh, bool free_loop_normals)
static void rna_Mesh_split_faces(Mesh *mesh, bool UNUSED(free_loop_normals))
{
BKE_mesh_split_faces(mesh, free_loop_normals != 0);
ED_mesh_split_faces(mesh);
}
static void rna_Mesh_update_gpu_tag(Mesh *mesh)
@ -237,8 +237,9 @@ void RNA_api_mesh(StructRNA *srna)
func = RNA_def_function(srna, "split_faces", "rna_Mesh_split_faces");
RNA_def_function_ui_description(func, "Split faces based on the edge angle");
RNA_def_boolean(
func, "free_loop_normals", 1, "Free Loop Normals", "Free loop normals custom data layer");
/* TODO: This parameter has no effect anymore, since the internal code does not need to
* compute temporary CD_NORMAL loop data. It should be removed for next major release (4.0). */
RNA_def_boolean(func, "free_loop_normals", 1, "Free Loop Normals", "Deprecated, has no effect");
func = RNA_def_function(srna, "calc_tangents", "rna_Mesh_calc_tangents");
RNA_def_function_flag(func, FUNC_USE_REPORTS);

497
source/blender/nodes/geometry/nodes/node_geo_edge_split.cc
View File

@ -1,14 +1,8 @@
/* SPDX-License-Identifier: GPL-2.0-or-later */
#include "BLI_array_utils.hh"
#include "BLI_task.hh"
#include "DNA_mesh_types.h"
#include "BKE_attribute_math.hh"
#include "BKE_mesh.h"
#include "BKE_mesh_mapping.h"
#include "BKE_mesh_runtime.h"
#include "GEO_mesh_split_edges.hh"
#include "node_geometry_util.hh"
@ -21,493 +15,6 @@ static void node_declare(NodeDeclarationBuilder &b)
b.add_output<decl::Geometry>(N_("Mesh"));
}
/* Naively checks if the first vertices and the second vertices are the same. */
static inline bool naive_edges_equal(const MEdge &edge1, const MEdge &edge2)
{
return edge1.v1 == edge2.v1 && edge1.v2 == edge2.v2;
}
template<typename T>
static void copy_to_new_verts(MutableSpan<T> data, const Span<int> new_to_old_verts_map)
{
const Span<T> old_data = data.drop_back(new_to_old_verts_map.size());
MutableSpan<T> new_data = data.take_back(new_to_old_verts_map.size());
array_utils::gather(old_data, new_to_old_verts_map, new_data);
}
static void add_new_vertices(Mesh &mesh, const Span<int> new_to_old_verts_map)
{
CustomData_realloc(&mesh.vdata, mesh.totvert, mesh.totvert + new_to_old_verts_map.size());
mesh.totvert += new_to_old_verts_map.size();
MutableAttributeAccessor attributes = mesh.attributes_for_write();
for (const AttributeIDRef &id : attributes.all_ids()) {
if (attributes.lookup_meta_data(id)->domain != ATTR_DOMAIN_POINT) {
continue;
}
GSpanAttributeWriter attribute = attributes.lookup_for_write_span(id);
if (!attribute) {
continue;
}
attribute_math::convert_to_static_type(attribute.span.type(), [&](auto dummy) {
using T = decltype(dummy);
copy_to_new_verts(attribute.span.typed<T>(), new_to_old_verts_map);
});
attribute.finish();
}
if (float3 *orco = static_cast<float3 *>(CustomData_get_layer(&mesh.vdata, CD_ORCO))) {
copy_to_new_verts<float3>({orco, mesh.totvert}, new_to_old_verts_map);
}
if (int *orig_indices = static_cast<int *>(CustomData_get_layer(&mesh.vdata, CD_ORIGINDEX))) {
copy_to_new_verts<int>({orig_indices, mesh.totvert}, new_to_old_verts_map);
}
}
static void add_new_edges(Mesh &mesh,
const Span<MEdge> new_edges,
const Span<int> new_to_old_edges_map)
{
MutableAttributeAccessor attributes = mesh.attributes_for_write();
/* Store a copy of the IDs locally since we will remove the existing attributes which
* can also free the names, since the API does not provide pointer stability. */
Vector<std::string> named_ids;
Vector<WeakAnonymousAttributeID> anonymous_ids;
for (const AttributeIDRef &id : attributes.all_ids()) {
if (attributes.lookup_meta_data(id)->domain != ATTR_DOMAIN_EDGE) {
continue;
}
if (!id.should_be_kept()) {
continue;
}
if (id.is_named()) {
named_ids.append(id.name());
}
else {
anonymous_ids.append(WeakAnonymousAttributeID(&id.anonymous_id()));
}
}
Vector<AttributeIDRef> local_edge_ids;
for (const StringRef name : named_ids) {
local_edge_ids.append(name);
}
for (const WeakAnonymousAttributeID &id : anonymous_ids) {
local_edge_ids.append(id.get());
}
/* Build new arrays for the copied edge attributes. Unlike vertices, new edges aren't all at the
* end of the array, so just copying to the new edges would overwrite old values when they were
* still needed. */
struct NewAttributeData {
const AttributeIDRef &local_id;
const CPPType &type;
void *array;
};
Vector<NewAttributeData> dst_attributes;
for (const AttributeIDRef &id : local_edge_ids) {
GAttributeReader attribute = attributes.lookup(id);
if (!attribute) {
continue;
}
const CPPType &type = attribute.varray.type();
void *new_data = MEM_malloc_arrayN(new_edges.size(), type.size(), __func__);
attribute_math::convert_to_static_type(type, [&](auto dummy) {
using T = decltype(dummy);
const VArray<T> src = attribute.varray.typed<T>();
MutableSpan<T> dst(static_cast<T *>(new_data), new_edges.size());
array_utils::gather(src, new_to_old_edges_map, dst);
});
/* Free the original attribute as soon as possible to lower peak memory usage. */
attributes.remove(id);
dst_attributes.append({id, type, new_data});
}
int *new_orig_indices = nullptr;
if (const int *orig_indices = static_cast<const int *>(
CustomData_get_layer(&mesh.edata, CD_ORIGINDEX))) {
new_orig_indices = static_cast<int *>(
MEM_malloc_arrayN(new_edges.size(), sizeof(int), __func__));
array_utils::gather(Span(orig_indices, mesh.totedge),
new_to_old_edges_map,
{new_orig_indices, new_edges.size()});
}
CustomData_free(&mesh.edata, mesh.totedge);
mesh.totedge = new_edges.size();
CustomData_add_layer(&mesh.edata, CD_MEDGE, CD_CONSTRUCT, nullptr, mesh.totedge);
mesh.edges_for_write().copy_from(new_edges);
if (new_orig_indices != nullptr) {
CustomData_add_layer(&mesh.edata, CD_ORIGINDEX, CD_ASSIGN, new_orig_indices, mesh.totedge);
}
for (NewAttributeData &new_data : dst_attributes) {
attributes.add(new_data.local_id,
ATTR_DOMAIN_EDGE,
bke::cpp_type_to_custom_data_type(new_data.type),
bke::AttributeInitMoveArray(new_data.array));
}
}
/**
* Merge the new_edge into the original edge.
*
* NOTE: This function is very specific to the situation and makes a lot of assumptions.
*/
static void merge_edges(const int orig_edge_i,
const int new_edge_i,
MutableSpan<int> new_corner_edges,
Vector<Vector<int>> &edge_to_loop_map,
Vector<MEdge> &new_edges,
Vector<int> &new_to_old_edges_map)
{
/* Merge back into the original edge by undoing the topology changes. */
BLI_assert(edge_to_loop_map[new_edge_i].size() == 1);
const int loop_i = edge_to_loop_map[new_edge_i][0];
new_corner_edges[loop_i] = orig_edge_i;
/* We are putting the last edge in the location of new_edge in all the maps, to remove
* new_edge efficiently. We have to update the topology information for this last edge
* though. Essentially we are replacing every instance of last_edge_i with new_edge_i. */
const int last_edge_i = new_edges.size() - 1;
if (last_edge_i != new_edge_i) {
BLI_assert(edge_to_loop_map[last_edge_i].size() == 1);
const int last_edge_loop_i = edge_to_loop_map[last_edge_i][0];
new_corner_edges[last_edge_loop_i] = new_edge_i;
}
/* We can now safely swap-remove. */
new_edges.remove_and_reorder(new_edge_i);
edge_to_loop_map.remove_and_reorder(new_edge_i);
new_to_old_edges_map.remove_and_reorder(new_edge_i);
}
/**
* Replace the vertex of an edge with a new one, and update the connected loops.
*
* NOTE: This only updates the loops containing the edge and the old vertex. It should therefore
* also be called on the adjacent edge.
*/
static void swap_vertex_of_edge(MEdge &edge,
const int old_vert,
const int new_vert,
MutableSpan<int> corner_verts,
const Span<int> connected_loops)
{
if (edge.v1 == old_vert) {
edge.v1 = new_vert;
}
else if (edge.v2 == old_vert) {
edge.v2 = new_vert;
}
else {
BLI_assert_unreachable();
}
for (const int loop_i : connected_loops) {
if (corner_verts[loop_i] == old_vert) {
corner_verts[loop_i] = new_vert;
}
/* The old vertex is on the loop containing the adjacent edge. Since this function is also
* called on the adjacent edge, we don't replace it here. */
}
}
/** Split the vertex into duplicates so that each fan has a different vertex. */
static void split_vertex_per_fan(const int vertex,
const int start_offset,
const int orig_verts_num,
const Span<int> fans,
const Span<int> fan_sizes,
const Span<Vector<int>> edge_to_loop_map,
MutableSpan<MEdge> new_edges,
MutableSpan<int> corner_verts,
MutableSpan<int> new_to_old_verts_map)
{
int fan_start = 0;
/* We don't need to create a new vertex for the last fan. That fan can just be connected to the
* original vertex. */
for (const int i : fan_sizes.index_range().drop_back(1)) {
const int new_vert_i = start_offset + i;
new_to_old_verts_map[new_vert_i - orig_verts_num] = vertex;
for (const int edge_i : fans.slice(fan_start, fan_sizes[i])) {
swap_vertex_of_edge(
new_edges[edge_i], vertex, new_vert_i, corner_verts, edge_to_loop_map[edge_i]);
}
fan_start += fan_sizes[i];
}
}
/**
* Get the index of the adjacent edge to a loop connected to a vertex. In other words, for the
* given polygon return the unique edge connected to the given vertex and not on the given loop.
*/
static int adjacent_edge(const Span<int> corner_verts,
const Span<int> corner_edges,
const int loop_i,
const MPoly &poly,
const int vertex)
{
const int adjacent_loop_i = (corner_verts[loop_i] == vertex) ?
bke::mesh_topology::poly_loop_prev(poly, loop_i) :
bke::mesh_topology::poly_loop_next(poly, loop_i);
return corner_edges[adjacent_loop_i];
}
/**
* Calculate the disjoint fans connected to the vertex, where a fan is a group of edges connected
* through polygons. The connected_edges vector is rearranged in such a way that edges in the same
* fan are grouped together. The r_fans_sizes Vector gives the sizes of the different fans, and can
* be used to retrieve the fans from connected_edges.
*/
static void calc_vertex_fans(const int vertex,
const Span<int> new_corner_verts,
const Span<int> new_corner_edges,
const Span<MPoly> polys,
const Span<Vector<int>> edge_to_loop_map,
const Span<int> loop_to_poly_map,
MutableSpan<int> connected_edges,
Vector<int> &r_fan_sizes)
{
if (connected_edges.size() <= 1) {
r_fan_sizes.append(connected_edges.size());
return;
}
Vector<int> search_edges;
int total_found_edges_num = 0;
int fan_size = 0;
const int total_edge_num = connected_edges.size();
/* Iteratively go through the connected edges. The front contains already handled edges, while
* the back contains unhandled edges. */
while (true) {
/* This edge has not been visited yet. */
int curr_i = total_found_edges_num;
int curr_edge_i = connected_edges[curr_i];
/* Gather all the edges in this fan. */
while (true) {
fan_size++;
/* Add adjacent edges to search stack. */
for (const int loop_i : edge_to_loop_map[curr_edge_i]) {
const int adjacent_edge_i = adjacent_edge(
new_corner_verts, new_corner_edges, loop_i, polys[loop_to_poly_map[loop_i]], vertex);
/* Find out if this edge was visited already. */
int i = curr_i + 1;
for (; i < total_edge_num; i++) {
if (connected_edges[i] == adjacent_edge_i) {
break;
}
}
if (i == total_edge_num) {
/* Already visited this edge. */
continue;
}
search_edges.append(adjacent_edge_i);
curr_i++;
std::swap(connected_edges[curr_i], connected_edges[i]);
}
if (search_edges.is_empty()) {
break;
}
curr_edge_i = search_edges.pop_last();
}
/* We have now collected all the edges in this fan. */
total_found_edges_num += fan_size;
BLI_assert(total_found_edges_num <= total_edge_num);
r_fan_sizes.append(fan_size);
if (total_found_edges_num == total_edge_num) {
/* We have found all the edges, so this final batch must be the last connected fan. */
break;
}
fan_size = 0;
}
}
/**
* Splits the edge into duplicates, so that each edge is connected to one poly.
*/
static void split_edge_per_poly(const int edge_i,
const int new_edge_start,
MutableSpan<Vector<int>> edge_to_loop_map,
MutableSpan<int> corner_edges,
MutableSpan<MEdge> new_edges,
MutableSpan<int> new_to_old_edges_map)
{
if (edge_to_loop_map[edge_i].size() <= 1) {
return;
}
int new_edge_index = new_edge_start;
for (const int loop_i : edge_to_loop_map[edge_i].as_span().drop_front(1)) {
const MEdge new_edge(new_edges[edge_i]);
new_edges[new_edge_index] = new_edge;
new_to_old_edges_map[new_edge_index] = edge_i;
edge_to_loop_map[new_edge_index].append({loop_i});
corner_edges[loop_i] = new_edge_index;
new_edge_index++;
}
/* Only the first loop is now connected to this edge. */
edge_to_loop_map[edge_i].resize(1);
}
static void mesh_edge_split(Mesh &mesh, const IndexMask mask)
{
/* Flag vertices that need to be split. */
Array<bool> should_split_vert(mesh.totvert, false);
const Span<MEdge> edges = mesh.edges();
for (const int edge_i : mask) {
const MEdge edge = edges[edge_i];
should_split_vert[edge.v1] = true;
should_split_vert[edge.v2] = true;
}
/* Precalculate topology info. */
Array<Vector<int>> vert_to_edge_map = bke::mesh_topology::build_vert_to_edge_map(edges,
mesh.totvert);
Vector<Vector<int>> edge_to_loop_map = bke::mesh_topology::build_edge_to_loop_map_resizable(
mesh.corner_edges(), mesh.totedge);
Array<int> loop_to_poly_map = bke::mesh_topology::build_loop_to_poly_map(mesh.polys(),
mesh.totloop);
/* Store offsets, so we can split edges in parallel. */
Array<int> edge_offsets(edges.size());
Array<int> num_edge_duplicates(edges.size());
int new_edges_size = edges.size();
for (const int edge : mask) {
edge_offsets[edge] = new_edges_size;
/* We add duplicates of the edge for each poly (except the first). */
const int num_connected_loops = edge_to_loop_map[edge].size();
const int num_duplicates = std::max(0, num_connected_loops - 1);
new_edges_size += num_duplicates;
num_edge_duplicates[edge] = num_duplicates;
}
const Span<MPoly> polys = mesh.polys();
MutableSpan<int> corner_verts = mesh.corner_verts_for_write();
MutableSpan<int> corner_edges = mesh.corner_edges_for_write();
Vector<MEdge> new_edges(new_edges_size);
new_edges.as_mutable_span().take_front(edges.size()).copy_from(edges);
edge_to_loop_map.resize(new_edges_size);
/* Used for transferring attributes. */
Vector<int> new_to_old_edges_map(IndexRange(new_edges.size()).as_span());
/* Step 1: Split the edges. */
threading::parallel_for(mask.index_range(), 512, [&](IndexRange range) {
for (const int mask_i : range) {
const int edge_i = mask[mask_i];
split_edge_per_poly(edge_i,
edge_offsets[edge_i],
edge_to_loop_map,
corner_edges,
new_edges,
new_to_old_edges_map);
}
});
/* Step 1.5: Update topology information (can't parallelize). */
for (const int edge_i : mask) {
const MEdge &edge = edges[edge_i];
for (const int duplicate_i : IndexRange(edge_offsets[edge_i], num_edge_duplicates[edge_i])) {
vert_to_edge_map[edge.v1].append(duplicate_i);
vert_to_edge_map[edge.v2].append(duplicate_i);
}
}
/* Step 2: Calculate vertex fans. */
Array<Vector<int>> vertex_fan_sizes(mesh.totvert);
threading::parallel_for(IndexRange(mesh.totvert), 512, [&](IndexRange range) {
for (const int vert : range) {
if (!should_split_vert[vert]) {
continue;
}
calc_vertex_fans(vert,
corner_verts,
corner_edges,
polys,
edge_to_loop_map,
loop_to_poly_map,
vert_to_edge_map[vert],
vertex_fan_sizes[vert]);
}
});
/* Step 2.5: Calculate offsets for next step. */
Array<int> vert_offsets(mesh.totvert);
int total_verts_num = mesh.totvert;
for (const int vert : IndexRange(mesh.totvert)) {
if (!should_split_vert[vert]) {
continue;
}
vert_offsets[vert] = total_verts_num;
/* We only create a new vertex for each fan different from the first. */
total_verts_num += vertex_fan_sizes[vert].size() - 1;
}
/* Step 3: Split the vertices.
* Build a map from each new vertex to an old vertex to use for transferring attributes later. */
const int new_verts_num = total_verts_num - mesh.totvert;
Array<int> new_to_old_verts_map(new_verts_num);
threading::parallel_for(IndexRange(mesh.totvert), 512, [&](IndexRange range) {
for (const int vert : range) {
if (!should_split_vert[vert]) {
continue;
}
split_vertex_per_fan(vert,
vert_offsets[vert],
mesh.totvert,
vert_to_edge_map[vert],
vertex_fan_sizes[vert],
edge_to_loop_map,
new_edges,
corner_verts,
new_to_old_verts_map);
}
});
/* Step 4: Deduplicate edges. We loop backwards so we can use remove_and_reorder. Although this
* does look bad (3 nested loops), in practice the inner loops are very small. For most meshes,
* there are at most 2 polygons connected to each edge, and hence you'll only get at most 1
* duplicate per edge. */
for (int mask_i = mask.size() - 1; mask_i >= 0; mask_i--) {
const int edge = mask[mask_i];
int start_of_duplicates = edge_offsets[edge];
int end_of_duplicates = start_of_duplicates + num_edge_duplicates[edge] - 1;
for (int duplicate = end_of_duplicates; duplicate >= start_of_duplicates; duplicate--) {
if (naive_edges_equal(new_edges[edge], new_edges[duplicate])) {
merge_edges(
edge, duplicate, corner_edges, edge_to_loop_map, new_edges, new_to_old_edges_map);
break;
}
for (int other = start_of_duplicates; other < duplicate; other++) {
if (naive_edges_equal(new_edges[other], new_edges[duplicate])) {
merge_edges(
other, duplicate, corner_edges, edge_to_loop_map, new_edges, new_to_old_edges_map);
break;
}
}
}
}
/* Step 5: Resize the mesh to add the new vertices and rebuild the edges. */
add_new_vertices(mesh, new_to_old_verts_map);
add_new_edges(mesh, new_edges, new_to_old_edges_map);
BKE_mesh_tag_edges_split(&mesh);
}
static void node_geo_exec(GeoNodeExecParams params)
{
GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh");
@ -526,7 +33,7 @@ static void node_geo_exec(GeoNodeExecParams params)
return;
}
mesh_edge_split(*geometry_set.get_mesh_for_write(), mask);
geometry::split_edges(*geometry_set.get_mesh_for_write(), mask);
}
});