blender
/
blender
129
397
Fork 572
Code Issues 6.2k Pull Requests 745 Projects 19 Wiki Activity

Geometry Nodes: Dual Mesh Node 

This node calculates the dual of the input mesh. This means that faces
get replaced with vertices and vertices with faces. In principle this
only makes sense when the mesh in manifold, but there is an option to
keep the (non-manifold) boundaries of the mesh intact.

Attributes are propagated:
 - Point domain goes to face domain and vice versa
 - Edge domain and Face corner domain gets mapped to itself
Because of the duality, when the mesh is manifold, the attributes get
mapped to themselves when applying the node twice.

Thanks to Leul Mulugeta (@Leul) for help with the
ascii diagrams in the code comments.

Note that this does not work well with some non-manifold geometry,
like an edge connected to more than 2 faces, or a vertex connected to
only two faces, while not being in the boundary. This is because there
is no good way to define the dual at some of those points. This type
of non-manifold vertices are just removed for this reason.

Differential Revision: https://developer.blender.org/D12949
This commit is contained in:
Wannes Malfait 2021-12-01 11:11:50 -05:00 committed by Hans Goudey
parent 1757840843
commit d54a08c8af
7 changed files with 849 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

1
release/scripts/startup/nodeitems_builtins.py
View File

@ -141,6 +141,7 @@ def mesh_node_items(context):
yield NodeItem("GeometryNodeLegacySubdivisionSurface", poll=geometry_nodes_legacy_poll)
yield NodeItemCustom(draw=lambda self, layout, context: layout.separator())
yield NodeItem("GeometryNodeDualMesh")
yield NodeItem("GeometryNodeMeshBoolean")
yield NodeItem("GeometryNodeMeshToCurve")
yield NodeItem("GeometryNodeMeshToPoints")

1
source/blender/blenkernel/BKE_node.h
View File

@ -1555,6 +1555,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
#define GEO_NODE_INPUT_ID 1134
#define GEO_NODE_SET_ID 1135
#define GEO_NODE_ATTRIBUTE_DOMAIN_SIZE 1136
#define GEO_NODE_DUAL_MESH 1137
/** \} */

1
source/blender/blenkernel/intern/node.cc
View File

@ -5891,6 +5891,7 @@ static void registerGeometryNodes()
register_node_type_geo_curve_trim();
register_node_type_geo_delete_geometry();
register_node_type_geo_distribute_points_on_faces();
register_node_type_geo_dual_mesh();
register_node_type_geo_edge_split();
register_node_type_geo_image_texture();
register_node_type_geo_input_curve_handles();

1
source/blender/nodes/NOD_geometry.h
View File

@ -95,6 +95,7 @@ void register_node_type_geo_curve_to_points(void);
void register_node_type_geo_curve_trim(void);
void register_node_type_geo_delete_geometry(void);
void register_node_type_geo_distribute_points_on_faces(void);
void register_node_type_geo_dual_mesh(void);
void register_node_type_geo_edge_split(void);
void register_node_type_geo_image_texture(void);
void register_node_type_geo_input_curve_handles(void);

1
source/blender/nodes/NOD_static_types.h
View File

@ -347,6 +347,7 @@ DefNode(GeometryNode, GEO_NODE_CURVE_TO_MESH, 0, "CURVE_TO_MESH", CurveToMesh, "
DefNode(GeometryNode, GEO_NODE_CURVE_TO_POINTS, def_geo_curve_to_points, "CURVE_TO_POINTS", CurveToPoints, "Curve to Points", "")
DefNode(GeometryNode, GEO_NODE_DELETE_GEOMETRY, def_geo_delete_geometry, "DELETE_GEOMETRY", DeleteGeometry, "Delete Geometry", "")
DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "")
DefNode(GeometryNode, GEO_NODE_DUAL_MESH, 0, "DUAL_MESH", DualMesh, "Dual Mesh", "")
DefNode(GeometryNode, GEO_NODE_FILL_CURVE, def_geo_curve_fill, "FILL_CURVE", FillCurve, "Fill Curve", "")
DefNode(GeometryNode, GEO_NODE_FILLET_CURVE, def_geo_curve_fillet, "FILLET_CURVE", FilletCurve, "Fillet Curve", "")
DefNode(GeometryNode, GEO_NODE_IMAGE_TEXTURE, def_geo_image_texture, "IMAGE_TEXTURE", ImageTexture, "Image Texture", "")

1
source/blender/nodes/geometry/CMakeLists.txt
View File

@ -113,6 +113,7 @@ set(SRC
nodes/node_geo_curve_trim.cc
nodes/node_geo_delete_geometry.cc
nodes/node_geo_distribute_points_on_faces.cc
nodes/node_geo_dual_mesh.cc
nodes/node_geo_edge_split.cc
nodes/node_geo_image_texture.cc
nodes/node_geo_input_curve_handles.cc

843
source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc Normal file
View File

@ -0,0 +1,843 @@
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#include "BLI_task.hh"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "BKE_attribute_math.hh"
#include "BKE_mesh.h"
#include "node_geometry_util.hh"
namespace blender::nodes::node_geo_dual_mesh_cc {
static void node_declare(NodeDeclarationBuilder &b)
{
b.add_input<decl::Geometry>("Mesh").supported_type(GEO_COMPONENT_TYPE_MESH);
b.add_input<decl::Bool>("Keep Boundaries")
.default_value(false)
.description(
"Keep non-manifold boundaries of the input mesh in place by avoiding the dual "
"transformation there");
b.add_output<decl::Geometry>("Dual Mesh");
}
enum class EdgeType : int8_t {
Loose = 0, /* No polygons connected to it. */
Boundary = 1, /* An edge connected to exactly one polygon. */
Normal = 2, /* A normal edge (connected to two polygons). */
NonManifold = 3, /* An edge connected to more than two polygons. */
};
static EdgeType get_edge_type_with_added_neighbor(EdgeType old_type)
{
switch (old_type) {
case EdgeType::Loose:
return EdgeType::Boundary;
case EdgeType::Boundary:
return EdgeType::Normal;
case EdgeType::Normal:
case EdgeType::NonManifold:
return EdgeType::NonManifold;
}
BLI_assert_unreachable();
return EdgeType::Loose;
}
enum class VertexType : int8_t {
Loose = 0, /* Either no edges connected or only loose edges connected. */
Normal = 1, /* A normal vertex. */
Boundary = 2, /* A vertex on a boundary edge. */
NonManifold = 3, /* A vertex on a non-manifold edge. */
};
static VertexType get_vertex_type_with_added_neighbor(VertexType old_type)
{
switch (old_type) {
case VertexType::Loose:
return VertexType::Normal;
case VertexType::Normal:
return VertexType::Boundary;
case VertexType::Boundary:
case VertexType::NonManifold:
return VertexType::NonManifold;
}
BLI_assert_unreachable();
return VertexType::Loose;
}
/* Copy only where vertex_types is 'normal'. If keep boundaries is selected, also copy from
* boundary vertices. */
template<typename T>
static void copy_data_based_on_vertex_types(Span<T> data,
MutableSpan<T> r_data,
const Span<VertexType> vertex_types,
const bool keep_boundaries)
{
if (keep_boundaries) {
int out_i = 0;
for (const int i : data.index_range()) {
if (ELEM(vertex_types[i], VertexType::Normal, VertexType::Boundary)) {
r_data[out_i] = data[i];
out_i++;
}
}
}
else {
int out_i = 0;
for (const int i : data.index_range()) {
if (vertex_types[i] == VertexType::Normal) {
r_data[out_i] = data[i];
out_i++;
}
}
}
}
template<typename T>
static void copy_data_based_on_pairs(Span<T> data,
MutableSpan<T> r_data,
const Span<std::pair<int, int>> new_to_old_map)
{
for (const std::pair<int, int> &pair : new_to_old_map) {
r_data[pair.first] = data[pair.second];
}
}
/* Copy using the map. */
template<typename T>
static void copy_data_based_on_new_to_old_map(Span<T> data,
MutableSpan<T> r_data,
const Span<int> new_to_old_map)
{
for (const int i : r_data.index_range()) {
const int old_i = new_to_old_map[i];
r_data[i] = data[old_i];
}
}
/**
* Transfers the attributes from the original mesh to the new mesh using the following logic:
* - If the attribute was on the face domain it is now on the point domain, and this is true
* for all faces, so we can just copy these.
* - If the attribute was on the vertex domain there are three cases:
* - It was a 'bad' vertex so it is not in the dual mesh, and we can just ignore it
* - It was a normal vertex so it has a corresponding face in the dual mesh to which we can
* transfer.
* - It was a boundary vertex so it has a corresponding face, if keep_boundaries is true.
* Otherwise we can just ignore it.
* - If the attribute was on the edge domain we lookup for the new edges which edge it originated
* from using `new_to_old_edges_map`. We have to do it in this reverse order, because there can
* be more edges in the new mesh if keep boundaries is on.
* - We do the same thing for face corners as we do for edges.
*
* Some of the vertices (on the boundary) in the dual mesh don't come from faces, but from edges or
* vertices. For these the `boundary_vertex_to_relevant_face_map` is used, which maps them to the
* closest face.
*/
static void transfer_attributes(
const Map<AttributeIDRef, AttributeKind> &attributes,
const Span<VertexType> vertex_types,
const bool keep_boundaries,
const Span<int> new_to_old_edges_map,
const Span<int> new_to_old_face_corners_map,
const Span<std::pair<int, int>> boundary_vertex_to_relevant_face_map,
const GeometryComponent &src_component,
GeometryComponent &dst_component)
{
for (Map<AttributeIDRef, AttributeKind>::Item entry : attributes.items()) {
const AttributeIDRef attribute_id = entry.key;
ReadAttributeLookup src_attribute = src_component.attribute_try_get_for_read(attribute_id);
if (!src_attribute) {
continue;
}
AttributeDomain out_domain;
if (src_attribute.domain == ATTR_DOMAIN_FACE) {
out_domain = ATTR_DOMAIN_POINT;
}
else if (src_attribute.domain == ATTR_DOMAIN_POINT) {
out_domain = ATTR_DOMAIN_FACE;
}
else {
/* Edges and Face Corners. */
out_domain = src_attribute.domain;
}
const CustomDataType data_type = bke::cpp_type_to_custom_data_type(
src_attribute.varray.type());
OutputAttribute dst_attribute = dst_component.attribute_try_get_for_output_only(
attribute_id, out_domain, data_type);
if (!dst_attribute) {
continue;
}
attribute_math::convert_to_static_type(data_type, [&](auto dummy) {
using T = decltype(dummy);
VArray_Span<T> span{src_attribute.varray.typed<T>()};
MutableSpan<T> dst_span = dst_attribute.as_span<T>();
if (src_attribute.domain == ATTR_DOMAIN_FACE) {
dst_span.take_front(span.size()).copy_from(span);
if (keep_boundaries) {
copy_data_based_on_pairs(span, dst_span, boundary_vertex_to_relevant_face_map);
}
}
else if (src_attribute.domain == ATTR_DOMAIN_POINT) {
copy_data_based_on_vertex_types(span, dst_span, vertex_types, keep_boundaries);
}
else if (src_attribute.domain == ATTR_DOMAIN_EDGE) {
copy_data_based_on_new_to_old_map(span, dst_span, new_to_old_edges_map);
}
else {
copy_data_based_on_new_to_old_map(span, dst_span, new_to_old_face_corners_map);
}
});
dst_attribute.save();
}
}
/**
* Calculates the boundaries of the mesh. Boundary polygons are not computed since we don't need
* them later on. We use the following definitions:
* - An edge is on a boundary if it is connected to only one polygon.
* - A vertex is on a boundary if it is on an edge on a boundary.
*/
static void calc_boundaries(const Mesh &mesh,
MutableSpan<VertexType> r_vertex_types,
MutableSpan<EdgeType> r_edge_types)
{
BLI_assert(r_vertex_types.size() == mesh.totvert);
BLI_assert(r_edge_types.size() == mesh.totedge);
r_vertex_types.fill(VertexType::Loose);
r_edge_types.fill(EdgeType::Loose);
/* Add up the number of polys connected to each edge. */
for (const int i : IndexRange(mesh.totpoly)) {
const MPoly &poly = mesh.mpoly[i];
for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
r_edge_types[loop.e] = get_edge_type_with_added_neighbor(r_edge_types[loop.e]);
}
}
/* Update vertices. */
for (const int i : IndexRange(mesh.totedge)) {
const EdgeType edge_type = r_edge_types[i];
if (edge_type == EdgeType::Loose) {
continue;
}
const MEdge &edge = mesh.medge[i];
if (edge_type == EdgeType::Boundary) {
r_vertex_types[edge.v1] = get_vertex_type_with_added_neighbor(r_vertex_types[edge.v1]);
r_vertex_types[edge.v2] = get_vertex_type_with_added_neighbor(r_vertex_types[edge.v2]);
}
else if (edge_type >= EdgeType::NonManifold) {
r_vertex_types[edge.v1] = VertexType::NonManifold;
r_vertex_types[edge.v2] = VertexType::NonManifold;
}
}
/* Normal verts are on a normal edge, and not on boundary edges or non-manifold edges. */
for (const int i : IndexRange(mesh.totedge)) {
const EdgeType edge_type = r_edge_types[i];
if (edge_type == EdgeType::Normal) {
const MEdge &edge = mesh.medge[i];
if (r_vertex_types[edge.v1] == VertexType::Loose) {
r_vertex_types[edge.v1] = VertexType::Normal;
}
if (r_vertex_types[edge.v2] == VertexType::Loose) {
r_vertex_types[edge.v2] = VertexType::Normal;
}
}
}
}
/**
* Stores the indices of the polygons connected to each vertex.
*/
static void create_vertex_poly_map(const Mesh &mesh,
MutableSpan<Vector<int>> r_vertex_poly_indices)
{
for (const int i : IndexRange(mesh.totpoly)) {
const MPoly &poly = mesh.mpoly[i];
for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
r_vertex_poly_indices[loop.v].append(i);
}
}
}
/**
* Sorts the polygons connnected to the given vertex based on polygon adjacency. The ordering is
* so such that the normals point in the same way as the original mesh. If the vertex is a
* boundary vertex, the first and last polygon have a boundary edge connected to the vertex. The
* `r_shared_edges` array at index i is set to the index of the shared edge bewteen the i-th and
* (i+1)-th sorted polygon. Similarly the `r_sorted_corners` array at index i is set to the
* corner in the i-th sorted polygon.
*
* How the faces are sorted (see diagrams below):
* (For this explanation we'll assume all faces are oriented clockwise)
* (The vertex whose connected polygons we need to sort is "v0")
*
* Normal case: Boundary Vertex case:
* v1 ----- v2 ----- v3 | | |
* | f3 | f0 | v2 ---- v4 --------- v3---
* | | | | / ,-' |
* v8 ----- v0 ----- v4 | f0 / f1 ,-' |
* | f2 | f1 | | / ,-' |
* | | | | / ,-' |
* v7 ----- v6 ----- v5 | / ,-' f2 |
* | /,-' |
* v0 ------------------ v1---
*
* - First we get the two corners of each face that have an edge which contains v0. A corner is
* simply a vertex followed by an edge. In this case for the face "f0" for example, we'd end up
* with the corners (v: v4, e: v4<->v0) and (v: v0, e: v0<->v2). Note that if the face was oriented
* counter-clockwise we'd end up with the corners (v: v0, e: v0<->v4) and (v: v2, e: v0<->v2)
* instead.
* - Then we need to choose one polygon as our first. If "v0" is not on a boundary we can just
* choose any polygon. If it is on a boundary some more care needs to be taken. Here we need to
* pick a polygon which lies on the boundary (in the diagram either f0 or f2). To choose between
* the two we need the next step.
* - In the normal case we use this polygon to set `shared_edge_i` which indicates the index of the
* shared edge between this polygon and the next one. There are two possible choices: v0<->v4 and
* v2<->v0. To choose we look at the corners. Since the edge v0<->v2 lies on the corner which has
* v0, we set `shared_edge_i` to the other edge (v0<->v4), such that the next face will be "f1"
* which is the next face in clockwise order.
* - In the boundary vertex case, we do something similar, but we are also forced to choose the
* edge which is not on the boundary. If this doesn't line up with orientation of the polygon, we
* know we'll need to choose the other boundary polygon as our first polygon. If the orientations
* don't line up there as well, it means that the mesh normals are not consistent, and we just have
* to force an orientation for ourselves. (Imagine if f0 is oriented counter-clockwise and f2 is
* oriented clockwise for example)
* - Next comes a loop where we look at the other faces and find the one which has the shared
* edge. Then we set the next shared edge to the other edge on the polygon connected to "v0", and
* continue. Because of the way we've chosen the first shared edge the order of the faces will have
* the same orientation as that of the first polygon. (In this case we'd have f0 -> f1 -> f2 -> f3
* which also goes around clockwise).
* - Every time we determine a shared edge, we can also add a corner to `r_sorted_corners`. This
* will simply be the corner which doesn't contain the shared edge.
* - Finally if we are in the normal case we also need to add the last "shared edge" to close the
* loop.
*/
static void sort_vertex_polys(const Mesh &mesh,
const int vertex_index,
const bool boundary_vertex,
const Span<EdgeType> edge_types,
MutableSpan<int> connected_polygons,
MutableSpan<int> r_shared_edges,
MutableSpan<int> r_sorted_corners)
{
if (connected_polygons.size() <= 2 && (!boundary_vertex || connected_polygons.size() == 0)) {
return;
}
/* For each polygon store the two corners whose edge contains the vertex. */
Array<std::pair<int, int>> poly_vertex_corners(connected_polygons.size());
for (const int i : connected_polygons.index_range()) {
const MPoly &poly = mesh.mpoly[connected_polygons[i]];
bool first_edge_done = false;
for (const int loop_index : IndexRange(poly.loopstart, poly.totloop)) {
const MLoop &loop = mesh.mloop[loop_index];
if (mesh.medge[loop.e].v1 == vertex_index || mesh.medge[loop.e].v2 == vertex_index) {
if (!first_edge_done) {
poly_vertex_corners[i].first = loop_index;
first_edge_done = true;
}
else {
poly_vertex_corners[i].second = loop_index;
break;
}
}
}
}
int shared_edge_i = -1;
/* Determine first polygon and orientation. For now the orientation of the whole loop depends
* on the one polygon we chose as first. It's probably not worth it to check every polygon in
* the loop to determine the 'average' orientation. */
if (boundary_vertex) {
/* Our first polygon needs to be one which has a boundary edge. */
for (const int i : connected_polygons.index_range()) {
const MLoop &first_loop = mesh.mloop[poly_vertex_corners[i].first];
const MLoop &second_loop = mesh.mloop[poly_vertex_corners[i].second];
if (edge_types[first_loop.e] == EdgeType::Boundary && first_loop.v == vertex_index) {
shared_edge_i = second_loop.e;
r_sorted_corners[0] = poly_vertex_corners[i].first;
std::swap(connected_polygons[i], connected_polygons[0]);
std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
break;
}
if (edge_types[second_loop.e] == EdgeType::Boundary && second_loop.v == vertex_index) {
shared_edge_i = first_loop.e;
r_sorted_corners[0] = poly_vertex_corners[i].second;
std::swap(connected_polygons[i], connected_polygons[0]);
std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
break;
}
}
if (shared_edge_i == -1) {
/* The rotation is inconsistent between the two polygons on the boundary. Just choose one
* of the polygon's orientation. */
for (const int i : connected_polygons.index_range()) {
const MLoop &first_loop = mesh.mloop[poly_vertex_corners[i].first];
const MLoop &second_loop = mesh.mloop[poly_vertex_corners[i].second];
if (edge_types[first_loop.e] == EdgeType::Boundary) {
shared_edge_i = second_loop.e;
r_sorted_corners[0] = poly_vertex_corners[i].first;
std::swap(connected_polygons[i], connected_polygons[0]);
std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
break;
}
if (edge_types[second_loop.e] == EdgeType::Boundary) {
shared_edge_i = first_loop.e;
r_sorted_corners[0] = poly_vertex_corners[i].second;
std::swap(connected_polygons[i], connected_polygons[0]);
std::swap(poly_vertex_corners[i], poly_vertex_corners[0]);
break;
}
}
}
}
else {
/* Any polygon can be the first. Just need to check the orientation.*/
const MLoop &first_loop = mesh.mloop[poly_vertex_corners[0].first];
const MLoop &second_loop = mesh.mloop[poly_vertex_corners[0].second];
if (first_loop.v == vertex_index) {
shared_edge_i = second_loop.e;
r_sorted_corners[0] = poly_vertex_corners[0].first;
}
else {
r_sorted_corners[0] = poly_vertex_corners[0].second;
shared_edge_i = first_loop.e;
}
}
BLI_assert(shared_edge_i != -1);
for (const int i : IndexRange(connected_polygons.size() - 1)) {
r_shared_edges[i] = shared_edge_i;
/* Look at the other polys to see if it has this shared edge. */
int j = i + 1;
for (; j < connected_polygons.size(); ++j) {
const MLoop &first_loop = mesh.mloop[poly_vertex_corners[j].first];
const MLoop &second_loop = mesh.mloop[poly_vertex_corners[j].second];
if (first_loop.e == shared_edge_i) {
r_sorted_corners[i + 1] = poly_vertex_corners[j].first;
shared_edge_i = second_loop.e;
break;
}
if (second_loop.e == shared_edge_i) {
r_sorted_corners[i + 1] = poly_vertex_corners[j].second;
shared_edge_i = first_loop.e;
break;
}
}
BLI_assert(j != connected_polygons.size());
std::swap(connected_polygons[i + 1], connected_polygons[j]);
std::swap(poly_vertex_corners[i + 1], poly_vertex_corners[j]);
}
if (!boundary_vertex) {
/* Shared edge between first and last polygon. */
r_shared_edges.last() = shared_edge_i;
}
}
/**
* Get the edge on the poly that contains the given vertex and is a boundary edge.
*/
static void boundary_edge_on_poly(const MPoly &poly,
const Mesh &mesh,
const int vertex_index,
const Span<EdgeType> edge_types,
int &r_edge)
{
for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
if (edge_types[loop.e] == EdgeType::Boundary) {
const MEdge &edge = mesh.medge[loop.e];
if (edge.v1 == vertex_index || edge.v2 == vertex_index) {
r_edge = loop.e;
return;
}
}
}
}
/**
* Get the two edges on the poly that contain the given vertex and are boundary edges. The
* orientation of the poly is taken into acount.
*/
static void boundary_edges_on_poly(const MPoly &poly,
const Mesh &mesh,
const int vertex_index,
const Span<EdgeType> edge_types,
int &r_edge1,
int &r_edge2)
{
bool edge1_done = false;
/* This is set to true if the order in which we encounter the two edges is inconsistent with the
* orientation of the polygon. */
bool needs_swap = false;
for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
if (edge_types[loop.e] == EdgeType::Boundary) {
const MEdge &edge = mesh.medge[loop.e];
if (edge.v1 == vertex_index || edge.v2 == vertex_index) {
if (edge1_done) {
if (needs_swap) {
r_edge2 = r_edge1;
r_edge1 = loop.e;
}
else {
r_edge2 = loop.e;
}
return;
}
r_edge1 = loop.e;
edge1_done = true;
if (loop.v == vertex_index) {
needs_swap = true;
}
}
}
}
}
static void add_edge(const Mesh &mesh,
const int old_edge_i,
const int v1,
const int v2,
Vector<int> &new_to_old_edges_map,
Vector<MEdge> &new_edges,
Vector<int> &loop_edges)
{
MEdge new_edge = MEdge(mesh.medge[old_edge_i]);
new_edge.v1 = v1;
new_edge.v2 = v2;
const int new_edge_i = new_edges.size();
new_to_old_edges_map.append(old_edge_i);
new_edges.append(new_edge);
loop_edges.append(new_edge_i);
}
/**
* Calculate the barycentric dual of a mesh. The dual is only "dual" in terms of connectivity,
* i.e. applying the function twice will give the same vertices, edges, and faces, but not the
* same positions. When the option "Keep Boundaries" is selected the connectivity is no
* longer dual.
*
* For the dual mesh of a manifold input mesh:
* - The vertices are at the centers of the faces of the input mesh.
* - The edges connect the two vertices created from the two faces next to the edge in the input
* mesh.
* - The faces are at the vertices of the input mesh.
*
* Some special cases are needed for boundaries and non-manifold geometry.
*/
static void calc_dual_mesh(GeometrySet &geometry_set,
const MeshComponent &in_component,
const bool keep_boundaries)
{
const Mesh &mesh_in = *in_component.get_for_read();
Map<AttributeIDRef, AttributeKind> attributes;
geometry_set.gather_attributes_for_propagation(
{GEO_COMPONENT_TYPE_MESH}, GEO_COMPONENT_TYPE_MESH, false, attributes);
Array<VertexType> vertex_types(mesh_in.totvert);
Array<EdgeType> edge_types(mesh_in.totedge);
calc_boundaries(mesh_in, vertex_types, edge_types);
Array<Vector<int>> vertex_poly_indices(mesh_in.totvert);
Array<Array<int>> vertex_shared_edges(mesh_in.totvert);
Array<Array<int>> vertex_corners(mesh_in.totvert);
create_vertex_poly_map(mesh_in, vertex_poly_indices);
threading::parallel_for(vertex_poly_indices.index_range(), 512, [&](IndexRange range) {
for (const int i : range) {
if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
/* Bad vertex that we can't work with. */
continue;
}
MutableSpan<int> loop_indices = vertex_poly_indices[i];
Array<int> sorted_corners(loop_indices.size());
if (vertex_types[i] == VertexType::Normal) {
Array<int> shared_edges(loop_indices.size());
sort_vertex_polys(
mesh_in, i, false, edge_types, loop_indices, shared_edges, sorted_corners);
vertex_shared_edges[i] = shared_edges;
}
else {
Array<int> shared_edges(loop_indices.size() - 1);
sort_vertex_polys(
mesh_in, i, true, edge_types, loop_indices, shared_edges, sorted_corners);
vertex_shared_edges[i] = shared_edges;
}
vertex_corners[i] = sorted_corners;
}
});
Vector<float3> vertex_positions(mesh_in.totpoly);
for (const int i : IndexRange(mesh_in.totpoly)) {
const MPoly poly = mesh_in.mpoly[i];
BKE_mesh_calc_poly_center(
&poly, &mesh_in.mloop[poly.loopstart], mesh_in.mvert, vertex_positions[i]);
}
Array<int> boundary_edge_midpoint_index;
if (keep_boundaries) {
/* Only initialize when we actually need it. */
boundary_edge_midpoint_index.reinitialize(mesh_in.totedge);
/* We need to add vertices at the centers of boundary edges. */
for (const int i : IndexRange(mesh_in.totedge)) {
if (edge_types[i] == EdgeType::Boundary) {
float3 mid;
const MEdge &edge = mesh_in.medge[i];
mid_v3_v3v3(mid, mesh_in.mvert[edge.v1].co, mesh_in.mvert[edge.v2].co);
boundary_edge_midpoint_index[i] = vertex_positions.size();
vertex_positions.append(mid);
}
}
}
Vector<int> loop_lengths;
Vector<int> loops;
Vector<int> loop_edges;
Vector<MEdge> new_edges;
/* These are used to transfer attributes. */
Vector<int> new_to_old_face_corners_map;
Vector<int> new_to_old_edges_map;
/* Stores the index of the vertex in the dual and the face it should get the attribute from. */
Vector<std::pair<int, int>> boundary_vertex_to_relevant_face_map;
/* Since each edge in the dual (except the ones created with keep boundaries) comes from
* exactly one edge in the original, we can use this array to keep track of whether it still
* needs to be created or not. If it's not -1 it gives the index in `new_edges` of the dual
* edge. The edges coming from preserving the boundaries only get added once anyway, so we
* don't need a hashmap for that. */
Array<int> old_to_new_edges_map(mesh_in.totedge);
old_to_new_edges_map.fill(-1);
for (const int i : IndexRange(mesh_in.totvert)) {
if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
/* Bad vertex that we can't work with. */
continue;
}
Vector<int> loop_indices = vertex_poly_indices[i];
Span<int> shared_edges = vertex_shared_edges[i];
Span<int> sorted_corners = vertex_corners[i];
if (vertex_types[i] == VertexType::Normal) {
if (loop_indices.size() <= 2) {
/* We can't make a polygon from 2 vertices. */
continue;
}
/* Add edges in the loop. */
for (const int i : shared_edges.index_range()) {
const int old_edge_i = shared_edges[i];
if (old_to_new_edges_map[old_edge_i] == -1) {
/* This edge has not been created yet. */
MEdge new_edge = MEdge(mesh_in.medge[old_edge_i]);
new_edge.v1 = loop_indices[i];
new_edge.v2 = loop_indices[(i + 1) % loop_indices.size()];
new_to_old_edges_map.append(old_edge_i);
old_to_new_edges_map[old_edge_i] = new_edges.size();
new_edges.append(new_edge);
}
loop_edges.append(old_to_new_edges_map[old_edge_i]);
}
new_to_old_face_corners_map.extend(sorted_corners);
}
else {
/**
* The code handles boundary vertices like the vertex marked "V" in the diagram below.
* The first thing that happens is ordering the faces f1,f2 and f3 (stored in
* loop_indices), together with their shared edges e3 and e4 (which get stored in
* shared_edges). The ordering could end up being clockwise or counterclockwise, for this
* we'll asume that the ordering f1->f2->f3 is chosen. After that we add the edges in
* between the polygons, in this case the edges f1--f2, and f2--f3. Now we need to merge
* these with the boundary edges e1 and e2. To do this we create an edge from f3 to the
* midpoint of e2 (computed in a previous step), from this midpoint to V, from V to the
* midpoint of e1 and from the midpoint of e1 to f1.
*
* | | | | | |
* v2 ---- v3 --------- v4--- v2 ---- v3 -------- v4---
* | f3 / ,-' | | / ,-'|
* | / f2 ,-' | | / ,-' |
* e2 | /e3 ,-' e4 | ====> M1-f3-/--f2-.,-' |
* | / ,-' | ====> | / ,-'\ |
* | / ,-' f1 | | / ,-' f1 |
* | /,-' | | /,-' | |
* V-------------------- v5--- V------------M2----- v5---
*/
/* Add the edges in between the polys. */
for (const int i : shared_edges.index_range()) {
const int old_edge_i = shared_edges[i];
if (old_to_new_edges_map[old_edge_i] == -1) {
/* This edge has not been created yet. */
MEdge new_edge = MEdge(mesh_in.medge[old_edge_i]);
new_edge.v1 = loop_indices[i];
new_edge.v2 = loop_indices[i + 1];
new_to_old_edges_map.append(old_edge_i);
old_to_new_edges_map[old_edge_i] = new_edges.size();
new_edges.append(new_edge);
}
loop_edges.append(old_to_new_edges_map[old_edge_i]);
}
new_to_old_face_corners_map.extend(sorted_corners);
/* Add the vertex and the midpoints of the two boundary edges to the loop. */
/* Get the boundary edges. */
int edge1;
int edge2;
if (loop_indices.size() >= 2) {
/* The first boundary edge is at the end of the chain of polygons. */
boundary_edge_on_poly(mesh_in.mpoly[loop_indices.last()], mesh_in, i, edge_types, edge1);
boundary_edge_on_poly(mesh_in.mpoly[loop_indices.first()], mesh_in, i, edge_types, edge2);
}
else {
/* If there is only one polygon both edges are in that polygon. */
boundary_edges_on_poly(
mesh_in.mpoly[loop_indices[0]], mesh_in, i, edge_types, edge1, edge2);
}
const int last_face_center = loop_indices.last();
loop_indices.append(boundary_edge_midpoint_index[edge1]);
new_to_old_face_corners_map.append(sorted_corners.last());
const int first_midpoint = loop_indices.last();
if (old_to_new_edges_map[edge1] == -1) {
add_edge(mesh_in,
edge1,
last_face_center,
first_midpoint,
new_to_old_edges_map,
new_edges,
loop_edges);
old_to_new_edges_map[edge1] = new_edges.size() - 1;
boundary_vertex_to_relevant_face_map.append(std::pair(first_midpoint, last_face_center));
}
else {
loop_edges.append(old_to_new_edges_map[edge1]);
}
loop_indices.append(vertex_positions.size());
/* This is sort of arbitrary, but interpolating would be a lot harder to do. */
new_to_old_face_corners_map.append(sorted_corners.first());
boundary_vertex_to_relevant_face_map.append(
std::pair(loop_indices.last(), last_face_center));
vertex_positions.append(mesh_in.mvert[i].co);
const int boundary_vertex = loop_indices.last();
add_edge(mesh_in,
edge1,
first_midpoint,
boundary_vertex,
new_to_old_edges_map,
new_edges,
loop_edges);
loop_indices.append(boundary_edge_midpoint_index[edge2]);
new_to_old_face_corners_map.append(sorted_corners.first());
const int second_midpoint = loop_indices.last();
add_edge(mesh_in,
edge2,
boundary_vertex,
second_midpoint,
new_to_old_edges_map,
new_edges,
loop_edges);
if (old_to_new_edges_map[edge2] == -1) {
const int first_face_center = loop_indices.first();
add_edge(mesh_in,
edge2,
second_midpoint,
first_face_center,
new_to_old_edges_map,
new_edges,
loop_edges);
old_to_new_edges_map[edge2] = new_edges.size() - 1;
boundary_vertex_to_relevant_face_map.append(std::pair(second_midpoint, first_face_center));
}
else {
loop_edges.append(old_to_new_edges_map[edge2]);
}
}
loop_lengths.append(loop_indices.size());
for (const int j : loop_indices) {
loops.append(j);
}
}
Mesh *mesh_out = BKE_mesh_new_nomain(
vertex_positions.size(), new_edges.size(), 0, loops.size(), loop_lengths.size());
MeshComponent out_component;
out_component.replace(mesh_out, GeometryOwnershipType::Editable);
transfer_attributes(attributes,
vertex_types,
keep_boundaries,
new_to_old_edges_map,
new_to_old_face_corners_map,
boundary_vertex_to_relevant_face_map,
in_component,
out_component);
int loop_start = 0;
for (const int i : IndexRange(mesh_out->totpoly)) {
mesh_out->mpoly[i].loopstart = loop_start;
mesh_out->mpoly[i].totloop = loop_lengths[i];
loop_start += loop_lengths[i];
}
for (const int i : IndexRange(mesh_out->totloop)) {
mesh_out->mloop[i].v = loops[i];
mesh_out->mloop[i].e = loop_edges[i];
}
for (const int i : IndexRange(mesh_out->totvert)) {
copy_v3_v3(mesh_out->mvert[i].co, vertex_positions[i]);
}
memcpy(mesh_out->medge, new_edges.data(), sizeof(MEdge) * new_edges.size());
BKE_mesh_normals_tag_dirty(mesh_out);
geometry_set.replace_mesh(mesh_out);
}
static void node_geo_exec(GeoNodeExecParams params)
{
GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh");
const bool keep_boundaries = params.extract_input<bool>("Keep Boundaries");
geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) {
if (geometry_set.has_mesh()) {
const MeshComponent &component = *geometry_set.get_component_for_read<MeshComponent>();
calc_dual_mesh(geometry_set, component, keep_boundaries);
}
});
params.set_output("Dual Mesh", std::move(geometry_set));
}
} // namespace blender::nodes::node_geo_dual_mesh_cc
void register_node_type_geo_dual_mesh()
{
namespace file_ns = blender::nodes::node_geo_dual_mesh_cc;
static bNodeType ntype;
geo_node_type_base(&ntype, GEO_NODE_DUAL_MESH, "Dual Mesh", NODE_CLASS_GEOMETRY, 0);
ntype.declare = file_ns::node_declare;
ntype.geometry_node_execute = file_ns::node_geo_exec;
nodeRegisterType(&ntype);
}