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

Refactor: Replace old Mesh edge split implementation 

Recently a new geometry node for splitting edges was added in D16399.
However, there was already a similar implementation in mesh.cc that was
mainly used to fake auto smooth support in Cycles by splitting sharp
edges and edges around sharp faces.

While there are still possibilities for optimization in the new code,
the implementation is safer and simpler, multi-threaded, and aligns
better with development plans for caching topology on Mesh and other
recent developments with attributes.

This patch removes the old code and moves the node implementation to
the geometry module so it can be used in editors and RNA. The "free
loop normals" argument is deprecated now, since it was only an internal
optimization exposed for Cycles.

The new mesh `editors` function creates an `IndexMask` of edges to
split by reusing some of the code from the corner normal calculation.

This change will help to simplify the changes in D16530 and T102858.

Differential Revision: https://developer.blender.org/D16732
This commit is contained in:
Hans Goudey 2022-12-13 18:39:36 -06:00
parent ae7ef8bcc6
commit 75ad8da1ea
Notes: blender-bot 2023-05-30 20:42:17 +02:00 
Referenced by commit efc2e5134f, Fix #104841: Split function for Cycles for sharp edges ignores attribute
Referenced by issue #107930, Baking of normals show different results between versions
Referenced by commit efbcfd8703, Mesh: Remove deprecated argumen to split_faces API function
Referenced by issue #108415, Regression : cycles motion blur glitch on alembic hair
12 changed files with 577 additions and 756 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

@ -254,14 +254,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.

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

@ -1836,267 +1836,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<MLoop> loops = mesh.loops_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 = loops[loop_idx].v;
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) {
loops[loop_idx].v = 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) {
loops[ml_fan_idx].v = 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<MLoop> loops = mesh->loops_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++) {
MLoop *ml_prev = &loops[mp->loopstart + mp->totloop - 1];
MLoop *ml = &loops[mp->loopstart];
for (int loop_idx = 0; loop_idx < mp->totloop; loop_idx++, ml++) {
void **eval;
if (!BLI_edgehash_ensure_p(edges_hash, ml_prev->v, ml->v, &eval)) {
const int edge_idx = ml_prev->e;
/* 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);
ml_prev->e = 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 = ml_prev->v;
new_edge->v2 = ml->v;
new_edge->next = *new_edges;
*new_edges = new_edge;
}
else {
/* We can re-use original edge. */
edges[edge_idx].v1 = ml_prev->v;
edges[edge_idx].v2 = ml->v;
*eval = POINTER_FROM_INT(edge_idx);
edges_used[edge_idx].set();
}
}
else {
/* Edge already known, just update loop's edge index. */
ml_prev->e = POINTER_AS_INT(*eval);
}
ml_prev = ml;
}
}
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;
@ -1464,3 +1467,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

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

@ -0,0 +1,490 @@
/* 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<MLoop> new_loops,
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_loops[loop_i].e = 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_loops[last_edge_loop_i].e = 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<MLoop> loops,
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 (loops[loop_i].v == old_vert) {
loops[loop_i].v = 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<MLoop> new_loops,
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, new_loops, 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(Span<MLoop> loops, const int loop_i, const MPoly &poly, const int vertex)
{
const int adjacent_loop_i = (loops[loop_i].v == vertex) ?
bke::mesh_topology::poly_loop_prev(poly, loop_i) :
bke::mesh_topology::poly_loop_next(poly, loop_i);
return loops[adjacent_loop_i].e;
}
/**
* 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<MLoop> new_loops,
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_loops, 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<MLoop> new_loops,
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});
new_loops[loop_i].e = new_edge_index;
new_edge_index++;
}
/* Only the first loop is now connected to this edge. */
edge_to_loop_map[edge_i].resize(1);
}
void split_edges(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.loops(), 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<MLoop> loops = mesh.loops_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, loops, 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,
loops,
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,
loops,
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, loops, 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, loops, 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

@ -174,9 +174,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)
@ -234,8 +234,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);

484
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,480 +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<MLoop> new_loops,
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_loops[loop_i].e = 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_loops[last_edge_loop_i].e = 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<MLoop> loops,
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 (loops[loop_i].v == old_vert) {
loops[loop_i].v = 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<MLoop> new_loops,
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, new_loops, 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(Span<MLoop> loops, const int loop_i, const MPoly &poly, const int vertex)
{
const int adjacent_loop_i = (loops[loop_i].v == vertex) ?
bke::mesh_topology::poly_loop_prev(poly, loop_i) :
bke::mesh_topology::poly_loop_next(poly, loop_i);
return loops[adjacent_loop_i].e;
}
/**
* 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<MLoop> new_loops,
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_loops, 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<MLoop> new_loops,
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});
new_loops[loop_i].e = 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.loops(), 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<MLoop> loops = mesh.loops_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, loops, 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,
loops,
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,
loops,
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, loops, 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, loops, 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");
@ -513,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);
}
});