Changeset View
Changeset View
Standalone View
Standalone View
source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
| Show First 20 Lines • Show All 530 Lines • ▼ Show 20 Lines | static void add_edge(const Mesh &mesh, | ||||
| 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); | ||||
| } | } | ||||
| /** | /** | ||||
| * Finds 'normal' vertices which are connected to only two polygons and marks them to not be | |||||
| * used in the derived datastructures from the mesh. For each pair of polygons which has such a | |||||
HooglyBoogly: `derived datastructures from the mesh` -> `data structures derived from the mesh` | |||||
| * 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. | |||||
HooglyBooglyUnsubmitted Done Inline ActionsSometimes 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… | |||||
| */ | |||||
| 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]; | |||||
| 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; | |||||
| /* Order is guaranteed to be the same because 2poly verts that are not on the boundary are | |||||
| * ignored in `sort_vertex_polys`. */ | |||||
| if (vertex_types[v1] != VertexType::Boundary && vertex_poly_indices[v1].size() == 2 && | |||||
| vertex_poly_indices[v1][0] == first_poly_index && | |||||
| vertex_poly_indices[v1][1] == second_poly_index) { | |||||
| /* This vertex is now 'removed' and should be ignored elsewhere. */ | |||||
| vertex_types[v1] = VertexType::Loose; | |||||
HooglyBooglyUnsubmitted Done Inline ActionsSetting 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 ActionsI 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… | |||||
| mark_edge = true; | |||||
| } | |||||
| if (vertex_types[v2] != VertexType::Boundary && vertex_poly_indices[v2].size() == 2 && | |||||
| vertex_poly_indices[v2][0] == first_poly_index && | |||||
| vertex_poly_indices[v2][1] == second_poly_index) { | |||||
| /* This vertex is now 'removed' and should be ignored elsewhere. */ | |||||
| vertex_types[v2] = VertexType::Loose; | |||||
| mark_edge = true; | |||||
| } | |||||
HooglyBooglyUnsubmitted Done Inline ActionsThese 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… | |||||
| if (mark_edge) { | |||||
| if (!edge_created) { | |||||
| MEdge new_edge = MEdge(edge); | |||||
| new_edge.v1 = first_poly_index; | |||||
| new_edge.v2 = second_poly_index; | |||||
HooglyBooglyUnsubmitted Done Inline ActionsI 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 ActionsPolygon 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… | |||||
| 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. | ||||
| * - The edges connect the two vertices created from the two faces next to the edge in the input | * - The edges connect the two vertices created from the two faces next to the edge in the input | ||||
| Show All 10 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 of the way this is | |||||
| * created, the indices will be sorted in ascending order. (This can change once they are sorted | |||||
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… | |||||
| * 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. */ | |||||
Done Inline ActionsThe 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, | |||||
Done Inline ActionsThis 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 || | ||||
Done Inline ActionsIt 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]; | ||||
Done Inline ActionsIs 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 193 Lines • Show Last 20 Lines | |||||
derived datastructures from the mesh -> data structures derived from the mesh