Blender  V3.3
Enumerations | Functions
blender::nodes::node_geo_dual_mesh_cc Namespace Reference

Enumerations

enum class  EdgeType : int8_t { Loose = 0 , Boundary = 1 , Normal = 2 , NonManifold = 3 }
 
enum class  VertexType : int8_t { Loose = 0 , Normal = 1 , Boundary = 2 , NonManifold = 3 }
 

Functions

static void node_declare (NodeDeclarationBuilder &b)
 
static EdgeType get_edge_type_with_added_neighbor (EdgeType old_type)
 
static VertexType get_vertex_type_with_added_neighbor (VertexType old_type)
 
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)
 
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)
 
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)
 
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 AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes)
 
static void calc_boundaries (const Mesh &mesh, MutableSpan< VertexType > r_vertex_types, MutableSpan< EdgeType > r_edge_types)
 
static void create_vertex_poly_map (const Mesh &mesh, MutableSpan< Vector< int >> r_vertex_poly_indices)
 
static bool 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)
 
static void boundary_edge_on_poly (const MPoly &poly, const Mesh &mesh, const int vertex_index, const Span< EdgeType > edge_types, int &r_edge)
 
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)
 
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)
 
static bool vertex_needs_dissolving (const int vertex, const int first_poly_index, const int second_poly_index, const Span< VertexType > vertex_types, const Span< Vector< int >> vertex_poly_indices)
 
static void dissolve_redundant_verts (const Mesh &mesh, const Span< Vector< int >> vertex_poly_indices, MutableSpan< VertexType > vertex_types, MutableSpan< int > old_to_new_edges_map, Vector< MEdge > &new_edges, Vector< int > &new_to_old_edges_map)
 
static void calc_dual_mesh (GeometrySet &geometry_set, const MeshComponent &in_component, const bool keep_boundaries)
 
static void node_geo_exec (GeoNodeExecParams params)
 

Enumeration Type Documentation

◆ EdgeType

Enumerator
Loose 
Boundary 
Normal 
NonManifold 

Definition at line 26 of file node_geo_dual_mesh.cc.

◆ VertexType

Enumerator
Loose 
Normal 
Boundary 
NonManifold 

Definition at line 48 of file node_geo_dual_mesh.cc.

Function Documentation

◆ add_edge()

static void blender::nodes::node_geo_dual_mesh_cc::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 
)
static

◆ boundary_edge_on_poly()

static void blender::nodes::node_geo_dual_mesh_cc::boundary_edge_on_poly ( const MPoly poly,
const Mesh mesh,
const int  vertex_index,
const Span< EdgeType edge_types,
int &  r_edge 
)
static

Get the edge on the poly that contains the given vertex and is a boundary edge.

Definition at line 457 of file node_geo_dual_mesh.cc.

References Boundary, MPoly::loopstart, Mesh::medge, mesh, Mesh::mloop, and MPoly::totloop.

◆ boundary_edges_on_poly()

static void blender::nodes::node_geo_dual_mesh_cc::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 
)
static

Get the two edges on the poly that contain the given vertex and are boundary edges. The orientation of the poly is taken into account.

Definition at line 478 of file node_geo_dual_mesh.cc.

References Boundary, MPoly::loopstart, Mesh::medge, mesh, Mesh::mloop, and MPoly::totloop.

◆ calc_boundaries()

static void blender::nodes::node_geo_dual_mesh_cc::calc_boundaries ( const Mesh mesh,
MutableSpan< VertexType r_vertex_types,
MutableSpan< EdgeType r_edge_types 
)
static

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.

Definition at line 206 of file node_geo_dual_mesh.cc.

References BLI_assert, Boundary, blender::MutableSpan< T >::fill(), get_edge_type_with_added_neighbor(), get_vertex_type_with_added_neighbor(), MPoly::loopstart, Loose, Mesh::medge, mesh, Mesh::mloop, Mesh::mpoly, NonManifold, Normal, blender::MutableSpan< T >::size(), Mesh::totedge, MPoly::totloop, Mesh::totpoly, and Mesh::totvert.

Referenced by calc_dual_mesh().

◆ calc_dual_mesh()

static void blender::nodes::node_geo_dual_mesh_cc::calc_dual_mesh ( GeometrySet geometry_set,
const MeshComponent in_component,
const bool  keep_boundaries 
)
static

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.

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 assume 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---

Definition at line 615 of file node_geo_dual_mesh.cc.

References calc_boundaries(), create_vertex_poly_map(), GeometrySet::gather_attributes_for_propagation(), GEO_COMPONENT_TYPE_MESH, MeshComponent::get_for_read(), blender::Array< T, InlineBufferCapacity, Allocator >::index_range(), blender::threading::parallel_for(), Mesh::totedge, and Mesh::totvert.

Referenced by node_geo_exec().

◆ copy_data_based_on_new_to_old_map()

template<typename T >
static void blender::nodes::node_geo_dual_mesh_cc::copy_data_based_on_new_to_old_map ( Span< T data,
MutableSpan< T r_data,
const Span< int >  new_to_old_map 
)
static

Definition at line 110 of file node_geo_dual_mesh.cc.

References data, and blender::MutableSpan< T >::index_range().

Referenced by transfer_attributes().

◆ copy_data_based_on_pairs()

template<typename T >
static void blender::nodes::node_geo_dual_mesh_cc::copy_data_based_on_pairs ( Span< T data,
MutableSpan< T r_data,
const Span< std::pair< int, int >>  new_to_old_map 
)
static

Definition at line 99 of file node_geo_dual_mesh.cc.

References data.

Referenced by transfer_attributes().

◆ copy_data_based_on_vertex_types()

template<typename T >
static void blender::nodes::node_geo_dual_mesh_cc::copy_data_based_on_vertex_types ( Span< T data,
MutableSpan< T r_data,
const Span< VertexType vertex_types,
const bool  keep_boundaries 
)
static

Definition at line 73 of file node_geo_dual_mesh.cc.

References Boundary, data, ELEM, and Normal.

Referenced by transfer_attributes().

◆ create_vertex_poly_map()

static void blender::nodes::node_geo_dual_mesh_cc::create_vertex_poly_map ( const Mesh mesh,
MutableSpan< Vector< int >>  r_vertex_poly_indices 
)
static

Stores the indices of the polygons connected to each vertex.

Definition at line 258 of file node_geo_dual_mesh.cc.

References MPoly::loopstart, mesh, Mesh::mloop, Mesh::mpoly, MPoly::totloop, and Mesh::totpoly.

Referenced by calc_dual_mesh().

◆ dissolve_redundant_verts()

static void blender::nodes::node_geo_dual_mesh_cc::dissolve_redundant_verts ( const Mesh mesh,
const Span< Vector< int >>  vertex_poly_indices,
MutableSpan< VertexType vertex_types,
MutableSpan< int >  old_to_new_edges_map,
Vector< MEdge > &  new_edges,
Vector< int > &  new_to_old_edges_map 
)
static

Finds 'normal' vertices which are connected to only two polygons and marks them to not be used in the data-structures derived from the mesh. For each pair of polygons which has such a vertex, an edge is created for the dual mesh between the centers of those two polygons. All edges in the input mesh which contain such a vertex are marked as 'done' to prevent duplicate edges being created. (See T94144)

Definition at line 552 of file node_geo_dual_mesh.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), MPoly::loopstart, Loose, Mesh::medge, mesh, Mesh::mloop, Mesh::mpoly, blender::nodes::node_geo_extrude_mesh_cc::new_edge(), Normal, blender::Vector< T, InlineBufferCapacity, Allocator >::size(), size(), MPoly::totloop, Mesh::totvert, v1, MEdge::v1, v2, MEdge::v2, and vertex_needs_dissolving().

◆ get_edge_type_with_added_neighbor()

static EdgeType blender::nodes::node_geo_dual_mesh_cc::get_edge_type_with_added_neighbor ( EdgeType  old_type)
static

Definition at line 33 of file node_geo_dual_mesh.cc.

References BLI_assert_unreachable, Boundary, Loose, NonManifold, and Normal.

Referenced by calc_boundaries().

◆ get_vertex_type_with_added_neighbor()

static VertexType blender::nodes::node_geo_dual_mesh_cc::get_vertex_type_with_added_neighbor ( VertexType  old_type)
static

Definition at line 55 of file node_geo_dual_mesh.cc.

References BLI_assert_unreachable, Boundary, Loose, NonManifold, and Normal.

Referenced by calc_boundaries().

◆ node_declare()

static void blender::nodes::node_geo_dual_mesh_cc::node_declare ( NodeDeclarationBuilder b)
static

◆ node_geo_exec()

static void blender::nodes::node_geo_dual_mesh_cc::node_geo_exec ( GeoNodeExecParams  params)
static

◆ sort_vertex_polys()

static bool blender::nodes::node_geo_dual_mesh_cc::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 
)
static

Sorts the polygons connected 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 between 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. If the polygons couldn't be sorted, false is returned.

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.

Definition at line 324 of file node_geo_dual_mesh.cc.

References BLI_assert, Boundary, MLoop::e, blender::Array< T, InlineBufferCapacity, Allocator >::first(), blender::MutableSpan< T >::index_range(), blender::MutableSpan< T >::last(), MPoly::loopstart, Mesh::medge, mesh, Mesh::mloop, Mesh::mpoly, blender::MutableSpan< T >::size(), swap(), MPoly::totloop, MLoop::v, MEdge::v1, and MEdge::v2.

◆ transfer_attributes()

static void blender::nodes::node_geo_dual_mesh_cc::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 AttributeAccessor  src_attributes,
MutableAttributeAccessor  dst_attributes 
)
static

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.

Definition at line 139 of file node_geo_dual_mesh.cc.

References ATTR_DOMAIN_EDGE, ATTR_DOMAIN_FACE, ATTR_DOMAIN_POINT, blender::attribute_math::convert_to_static_type(), copy_data_based_on_new_to_old_map(), copy_data_based_on_pairs(), copy_data_based_on_vertex_types(), blender::bke::cpp_type_to_custom_data_type(), blender::bke::GAttributeReader::domain, blender::bke::GSpanAttributeWriter::finish(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::items(), blender::bke::AttributeAccessor::lookup(), blender::bke::MutableAttributeAccessor::lookup_or_add_for_write_only_span(), blender::bke::GSpanAttributeWriter::span, T, blender::MutableSpan< T >::take_front(), blender::GVArrayCommon::type(), blender::GMutableSpan::typed(), blender::GVArray::typed(), and blender::bke::GAttributeReader::varray.

◆ vertex_needs_dissolving()

static bool blender::nodes::node_geo_dual_mesh_cc::vertex_needs_dissolving ( const int  vertex,
const int  first_poly_index,
const int  second_poly_index,
const Span< VertexType vertex_types,
const Span< Vector< int >>  vertex_poly_indices 
)
static

Definition at line 531 of file node_geo_dual_mesh.cc.

References Boundary, and size().

Referenced by dissolve_redundant_verts().