Differential D13445 Diff 46111 source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc

Changeset View

Standalone View

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc

Show First 20 Lines • Show All 531 Lines • ▼ Show 20 Lines	static void add_edge(const Mesh &mesh,
new_edge.v1 = v1;		new_edge.v1 = v1;
new_edge.v2 = v2;		new_edge.v2 = v2;
const int new_edge_i = new_edges.size();		const int new_edge_i = new_edges.size();
new_to_old_edges_map.append(old_edge_i);		new_to_old_edges_map.append(old_edge_i);
new_edges.append(new_edge);		new_edges.append(new_edge);
loop_edges.append(new_edge_i);		loop_edges.append(new_edge_i);
}		}

		/* Returns true if the vertex is connected only to the two polygons and is not on the boundary. */
		static bool vertex_needs_dissolving(const int vertex,
		const int first_poly_index,
		HooglyBooglyUnsubmitted Done Inline Actions `derived datastructures from the mesh` -> `data structures derived from the mesh` HooglyBoogly: `derived datastructures from the mesh` -> `data structures derived from the mesh`
		const int second_poly_index,
		const Span<VertexType> vertex_types,
		const Span<Vector<int>> vertex_poly_indices)
		HooglyBooglyUnsubmitted Done Inline Actions Sometimes when there's a rather confusing situation like this, I create a bug report with some images if there isn't one already, then you can write something like (see TXXXX) here HooglyBoogly: Sometimes when there's a rather confusing situation like this, I create a bug report with some…
		{
		/* Order is guaranteed to be the same because 2poly verts that are not on the boundary are
		* ignored in `sort_vertex_polys`. */
		return (vertex_types[vertex] != VertexType::Boundary &&
		vertex_poly_indices[vertex].size() == 2 &&
		vertex_poly_indices[vertex][0] == first_poly_index &&
		vertex_poly_indices[vertex][1] == second_poly_index);
		}

		/**
		* Finds 'normal' vertices which are connected to only two polygons and marks them to not be
		* used in the datastructures 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)
		*/
		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)
		{
		for (const int vert_i : IndexRange(mesh.totvert)) {
		if (vertex_poly_indices[vert_i].size() != 2 \|\| vertex_types[vert_i] != VertexType::Normal) {
		continue;
		}
		const int first_poly_index = vertex_poly_indices[vert_i][0];
		const int second_poly_index = vertex_poly_indices[vert_i][1];
		HooglyBooglyUnsubmitted Done Inline Actions Setting the type to "Loose" is a way to make it ignored later on, right? Do you think it would make more sense to have a separate `Ignored` type? I'm not sure myself. HooglyBoogly: Setting the type to "Loose" is a way to make it ignored later on, right? Do you think it would…
		WannesAuthorUnsubmitted Done Inline Actions I think setting it to 'loose' is fine, as it corresponds to what happens. I think of it like the when you hold 'alt' in the node editor to 'detach' a node from a link. In the same way the vertex gets detached in this case from the edge (not actually but that's how it's treated afterwards), and is therefore 'loose'. Wannes: I think setting it to 'loose' is fine, as it corresponds to what happens. I think of it like…
		const int new_edge_index = new_edges.size();
		bool edge_created = false;
		const MPoly &poly = mesh.mpoly[first_poly_index];
		for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
		const MEdge &edge = mesh.medge[loop.e];
		const int v1 = edge.v1;
		const int v2 = edge.v2;
		bool mark_edge = false;
		if (vertex_needs_dissolving(
		HooglyBooglyUnsubmitted Done Inline Actions These checks could be moved to a separate function to avoid the duplication (only v1 vs v2 is different between them. And maybe the function name could give some hint about the meaning of the check HooglyBoogly: These checks could be moved to a separate function to avoid the duplication (only v1 vs v2 is…
		v1, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
		/* This vertex is now 'removed' and should be ignored elsewhere. */
		vertex_types[v1] = VertexType::Loose;
		mark_edge = true;
		}
		HooglyBooglyUnsubmitted Done Inline Actions I don't really understand how putting poly indices in the vert fields of MEdge makes sense. Is there something I'm missing? HooglyBoogly: I don't really understand how putting poly indices in the vert fields of MEdge makes sense. Is…
		WannesAuthorUnsubmitted Done Inline Actions Polygon indices in the input mesh become vertex indices in the dual mesh. I also added a comment to clarify this. Wannes: Polygon indices in the input mesh become vertex indices in the dual mesh. I also added a…
		if (vertex_needs_dissolving(
		v2, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
		/* This vertex is now 'removed' and should be ignored elsewhere. */
		vertex_types[v2] = VertexType::Loose;
		mark_edge = true;
		}
		if (mark_edge) {
		if (!edge_created) {
		MEdge new_edge = MEdge(edge);
		/* The vertex indices in the dual mesh are the polygon indices of the input mesh. */
		new_edge.v1 = first_poly_index;
		new_edge.v2 = second_poly_index;
		new_to_old_edges_map.append(loop.e);
		new_edges.append(new_edge);
		edge_created = true;
		}
		old_to_new_edges_map[loop.e] = new_edge_index;
		}
		}
		}
		}

/**		/**
* Calculate the barycentric dual of a mesh. The dual is only "dual" in terms of connectivity,		* 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		* 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		* same positions. When the option "Keep Boundaries" is selected the connectivity is no
* longer dual.		* longer dual.
*		*
* For the dual mesh of a manifold input mesh:		* For the dual mesh of a manifold input mesh:
* - The vertices are at the centers of the faces of the input mesh.		* - The vertices are at the centers of the faces of the input mesh.
Show All 11 Lines	static void calc_dual_mesh(GeometrySet &geometry_set,

Map<AttributeIDRef, AttributeKind> attributes;		Map<AttributeIDRef, AttributeKind> attributes;
geometry_set.gather_attributes_for_propagation(		geometry_set.gather_attributes_for_propagation(
{GEO_COMPONENT_TYPE_MESH}, GEO_COMPONENT_TYPE_MESH, false, attributes);		{GEO_COMPONENT_TYPE_MESH}, GEO_COMPONENT_TYPE_MESH, false, attributes);

Array<VertexType> vertex_types(mesh_in.totvert);		Array<VertexType> vertex_types(mesh_in.totvert);
Array<EdgeType> edge_types(mesh_in.totedge);		Array<EdgeType> edge_types(mesh_in.totedge);
calc_boundaries(mesh_in, vertex_types, edge_types);		calc_boundaries(mesh_in, vertex_types, edge_types);
		/* Stores the indices of the polygons connected to the vertex. Because the polygons are looped
		* over in order of their indices, the polygon's indices will be sorted in ascending order. (This
		HooglyBooglyUnsubmitted Done Inline Actions +1 for the comment. I'd rather see something more specific than "the way this is created". What about the way it's created? HooglyBoogly: +1 for the comment. I'd rather see something more specific than "the way this is created". What…
		* can change once they are sorted using `sort_vertex_polys`). */
Array<Vector<int>> vertex_poly_indices(mesh_in.totvert);		Array<Vector<int>> vertex_poly_indices(mesh_in.totvert);
Array<Array<int>> vertex_shared_edges(mesh_in.totvert);		Array<Array<int>> vertex_shared_edges(mesh_in.totvert);
Array<Array<int>> vertex_corners(mesh_in.totvert);		Array<Array<int>> vertex_corners(mesh_in.totvert);
create_vertex_poly_map(mesh_in, vertex_poly_indices);		create_vertex_poly_map(mesh_in, vertex_poly_indices);
threading::parallel_for(vertex_poly_indices.index_range(), 512, [&](IndexRange range) {		threading::parallel_for(vertex_poly_indices.index_range(), 512, [&](IndexRange range) {
for (const int i : range) {		for (const int i : range) {
if (vertex_types[i] == VertexType::Loose \|\| vertex_types[i] >= VertexType::NonManifold \|\|		if (vertex_types[i] == VertexType::Loose \|\| vertex_types[i] >= VertexType::NonManifold \|\|
(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {		(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines	static void calc_dual_mesh(GeometrySet &geometry_set,
Vector<std::pair<int, int>> boundary_vertex_to_relevant_face_map;		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		/* 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		* 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		* 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		* edge. The edges coming from preserving the boundaries only get added once anyway, so we
* don't need a hashmap for that. */		* don't need a hashmap for that. */
Array<int> old_to_new_edges_map(mesh_in.totedge);		Array<int> old_to_new_edges_map(mesh_in.totedge);
old_to_new_edges_map.fill(-1);		old_to_new_edges_map.fill(-1);

		/* This is necessary to prevent duplicate edges from being created, but will likely not do
		* anything for most meshes. */
		JacquesLuckeUnsubmitted Done Inline Actions The comment should mention that the mesh is not dissolved in the input mesh, but only in the data structures you derived from it. JacquesLucke: The comment should mention that the mesh is not dissolved in the input mesh, but only in the…
		dissolve_redundant_verts(mesh_in,
		JacquesLuckeUnsubmitted Done Inline Actions This entire loop should be moved to a separate function. It shouldn't clutter this "main" function because it rarely has an impact on the result. JacquesLucke: This entire loop should be moved to a separate function. It shouldn't clutter this "main"…
		vertex_poly_indices,
		vertex_types,
		old_to_new_edges_map,
		new_edges,
		new_to_old_edges_map);

for (const int i : IndexRange(mesh_in.totvert)) {		for (const int i : IndexRange(mesh_in.totvert)) {
if (vertex_types[i] == VertexType::Loose \|\| vertex_types[i] >= VertexType::NonManifold \|\|		if (vertex_types[i] == VertexType::Loose \|\| vertex_types[i] >= VertexType::NonManifold \|\|
		JacquesLuckeUnsubmitted Done Inline Actions It seems like it dissolves an edge, but that edge might not actually include `vert_i`, maybe I'm missing something. JacquesLucke: It seems like it dissolves an edge, but that edge might not actually include `vert_i`, maybe…
(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {		(!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {
/* Bad vertex that we can't work with. */		/* Bad vertex that we can't work with. */
continue;		continue;
}		}

Vector<int> loop_indices = vertex_poly_indices[i];		Vector<int> loop_indices = vertex_poly_indices[i];
Span<int> shared_edges = vertex_shared_edges[i];		Span<int> shared_edges = vertex_shared_edges[i];
Span<int> sorted_corners = vertex_corners[i];		Span<int> sorted_corners = vertex_corners[i];
		JacquesLuckeUnsubmitted Done Inline Actions Is there some guarantee above the order of indices in `vertex_poly_indices`? Would be good to add comments to `vertex_poly_indices` similar variables. JacquesLucke: Is there some guarantee above the order of indices in `vertex_poly_indices`? Would be good to…
if (vertex_types[i] == VertexType::Normal) {		if (vertex_types[i] == VertexType::Normal) {
if (loop_indices.size() <= 2) {		if (loop_indices.size() <= 2) {
/* We can't make a polygon from 2 vertices. */		/* We can't make a polygon from 2 vertices. */
continue;		continue;
}		}

/* Add edges in the loop. */		/* Add edges in the loop. */
for (const int i : shared_edges.index_range()) {		for (const int i : shared_edges.index_range()) {
▲ Show 20 Lines • Show All 195 Lines • Show Last 20 Lines