MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
mesh_clean.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#include "math/defines.h"
11#include "mve/mesh.h"
12#include "mve/mesh_tools.h"
13#include "mve/mesh_info.h"
14#include "fssr/mesh_clean.h"
15
17
18bool
20 std::size_t v1, std::size_t v2, math::Vec3f const& new_vert,
21 std::vector<std::size_t> const& afaces,
22 float acos_threshold = 0.95f)
23{
24 mve::TriangleMesh::FaceList& faces = mesh->get_faces();
25 mve::TriangleMesh::VertexList& verts = mesh->get_vertices();
26
27 /* Test if the hypothetical vertex destroys geometry. */
28 mve::MeshInfo::VertexInfo& vinfo1 = mesh_info[v1];
29 for (std::size_t i = 0; i < vinfo1.verts.size(); ++i)
30 {
31 std::size_t ip1 = (i + 1) % vinfo1.verts.size();
32 if (vinfo1.verts[i] == v2 || vinfo1.verts[ip1] == v2)
33 continue;
34
35 math::Vec3f const& av1 = verts[vinfo1.verts[i]];
36 math::Vec3f const& av2 = verts[vinfo1.verts[ip1]];
37 math::Vec3f n1 = (av1 - verts[v1]).cross(av2 - verts[v1]).normalized();
38 math::Vec3f n2 = (av1 - new_vert).cross(av2 - new_vert).normalized();
39
40 float dot = n1.dot(n2);
41 if (MATH_ISNAN(dot) || dot < acos_threshold)
42 return false;
43 }
44
45 mve::MeshInfo::VertexInfo& vinfo2 = mesh_info[v2];
46 for (std::size_t i = 0; i < vinfo2.verts.size(); ++i)
47 {
48 std::size_t ip1 = (i + 1) % vinfo2.verts.size();
49 if (vinfo2.verts[i] == v1 || vinfo2.verts[ip1] == v1)
50 continue;
51 math::Vec3f const& av1 = verts[vinfo2.verts[i]];
52 math::Vec3f const& av2 = verts[vinfo2.verts[ip1]];
53 math::Vec3f n1 = (av1 - verts[v2]).cross(av2 - verts[v2]).normalized();
54 math::Vec3f n2 = (av1 - new_vert).cross(av2 - new_vert).normalized();
55
56 float dot = n1.dot(n2);
57 if (MATH_ISNAN(dot) || dot < acos_threshold)
58 return false;
59 }
60
61 /* Test succeeded. Assign new vertex position to v1. */
62 verts[v1] = new_vert;
63
64 /* Update faces adjacent to v2 replacing v2 with v1. */
65 for (std::size_t i = 0; i < vinfo2.faces.size(); ++i)
66 for (std::size_t j = 0; j < 3; ++j)
67 if (faces[vinfo2.faces[i] * 3 + j] == v2)
68 faces[vinfo2.faces[i] * 3 + j] = v1;
69
70 /* Delete the two faces adjacent to the collapsed edge. */
71 std::size_t v3 = 0, v4 = 0;
72 for (std::size_t i = 0; i < 3; ++i)
73 {
74 std::size_t fid1 = afaces[0] * 3 + i;
75 std::size_t fid2 = afaces[1] * 3 + i;
76 if (faces[fid1] != v1 && faces[fid1] != v2)
77 v3 = faces[fid1];
78 if (faces[fid2] != v1 && faces[fid2] != v2)
79 v4 = faces[fid2];
80 faces[fid1] = 0;
81 faces[fid2] = 0;
82 }
83
84 /* Update vertex info for vertices adjcent to v2, replacing v2 with v1. */
85 for (std::size_t i = 0; i < vinfo2.verts.size(); ++i)
86 {
87 std::size_t const vert_id = vinfo2.verts[i];
88 if (vert_id != v1 && vert_id != v3 && vert_id != v4)
89 mesh_info[vert_id].replace_adjacent_vertex(v2, v1);
90 }
91
92 /* Update vertex info for v3 and v4: remove v2, remove deleted faces. */
93 mve::MeshInfo::VertexInfo& vinfo3 = mesh_info[v3];
94 vinfo3.remove_adjacent_face(afaces[0]);
95 vinfo3.remove_adjacent_vertex(v2);
96 mve::MeshInfo::VertexInfo& vinfo4 = mesh_info[v4];
97 vinfo4.remove_adjacent_face(afaces[1]);
98 vinfo4.remove_adjacent_vertex(v2);
99
100 /* Update vinfo for v1: Remove v2, remove collapsed faces, add v2 faces. */
101 vinfo1.remove_adjacent_face(afaces[0]);
102 vinfo1.remove_adjacent_face(afaces[1]);
103 for (std::size_t i = 0; i < vinfo2.faces.size(); ++i)
104 if (vinfo2.faces[i] != afaces[0] && vinfo2.faces[i] != afaces[1])
105 vinfo1.faces.push_back(vinfo2.faces[i]);
106 mesh_info.update_vertex(*mesh, v1);
107
108 /* Update vertex info for v2. */
109 vinfo2.faces.clear();
110 vinfo2.verts.clear();
112
113 return true;
114}
115
116/* ---------------------------------------------------------------- */
117
118namespace
119{
120 /*
121 * Returns the ratio of the smallest by the second smallest edge length.
122 */
123 float
124 get_needle_ratio_squared (mve::TriangleMesh::VertexList const& verts,
125 unsigned int const* vid,
126 std::size_t* shortest_edge_v1, std::size_t* shortest_edge_v2)
127 {
128 typedef std::pair<float, int> Edge;
129 Edge edges[3];
130 for (int j = 0; j < 3; ++j)
131 {
132 int const jp1 = (j + 1) % 3;
133 edges[j].first = (verts[vid[j]] - verts[vid[jp1]]).square_norm();
134 edges[j].second = j;
135 }
136 math::algo::sort_values(edges + 0, edges + 1, edges + 2);
137
138 /* Test shortest to second-shortest edge ratio. */
139 float const square_ratio = edges[0].first / edges[1].first;
140 if (shortest_edge_v1 != nullptr && shortest_edge_v2 != nullptr)
141 {
142 *shortest_edge_v1 = vid[edges[0].second];
143 *shortest_edge_v2 = vid[(edges[0].second + 1) % 3];
144 }
145
146 return square_ratio;
147 }
148}
149
150std::size_t
151clean_needles (mve::TriangleMesh::Ptr mesh, float needle_ratio_thres)
152{
153 float const square_needle_ratio_thres = MATH_POW2(needle_ratio_thres);
154 mve::MeshInfo mesh_info(mesh);
155
156 /*
157 * Algorithm to remove slivers with a two long and a very short edge.
158 * The sliver is identified using the ratio of the shortest by the second
159 * shortest edge. An edge collapse of the short edge is performed if it
160 * does not modify the geometry in a negative way, e.g. flips triangles.
161 */
162 mve::TriangleMesh::FaceList& faces = mesh->get_faces();
163 mve::TriangleMesh::VertexList& verts = mesh->get_vertices();
164 std::size_t num_collapses = 0;
165
166 for (std::size_t i = 0; i < faces.size(); i += 3)
167 {
168 /* Skip invalid faces. */
169 if (faces[i] == faces[i + 1] && faces[i] == faces[i + 2])
170 continue;
171
172 /* Skip faces that are no needles. */
173 std::size_t v1, v2;
174 float const needle_ratio_squared
175 = get_needle_ratio_squared(verts, &faces[i], &v1, &v2);
176 if (needle_ratio_squared > square_needle_ratio_thres)
177 continue;
178
179 /* Skip edges between non-simple vertices. */
180 if (mesh_info[v1].vclass != mve::MeshInfo::VERTEX_CLASS_SIMPLE
181 || mesh_info[v2].vclass != mve::MeshInfo::VERTEX_CLASS_SIMPLE)
182 continue;
183
184 /* Find triangle adjacent to the edge, skip non-simple edges. */
185 std::vector<std::size_t> afaces;
186 mesh_info.get_faces_for_edge(v1, v2, &afaces);
187 if (afaces.size() != 2)
188 continue;
189
190 /* Collapse the edge. */
191 math::Vec3f new_v = (verts[v1] + verts[v2]) / 2.0f;
192 if (edge_collapse(mesh, mesh_info, v1, v2, new_v, afaces))
193 num_collapses += 1;
194 }
195
196 /* Cleanup invalid triangles and unreferenced vertices. */
198
199 return num_collapses;
200}
201
202/* ---------------------------------------------------------------- */
203
204std::size_t
206{
207 mve::MeshInfo mesh_info(mesh);
208 mve::TriangleMesh::VertexList& verts = mesh->get_vertices();
209 std::size_t num_collapses = 0;
210 for (std::size_t v1 = 0; v1 < verts.size(); ++v1)
211 {
212 mve::MeshInfo::VertexInfo& vinfo = mesh_info[v1];
214 continue;
215 if (vinfo.verts.size() != 3)
216 continue;
217
218 std::pair<float, std::size_t> edge_len[3];
219 for (std::size_t j = 0; j < vinfo.verts.size(); ++j)
220 edge_len[j] = std::make_pair(
221 (verts[vinfo.verts[j]] - verts[v1]).square_norm(),
222 vinfo.verts[j]);
223 math::algo::sort_values(edge_len + 0, edge_len + 1, edge_len + 2);
224 std::size_t v2 = edge_len[0].second;
225
226 std::vector<std::size_t> afaces;
227 mesh_info.get_faces_for_edge(v1, v2, &afaces);
228 if (afaces.size() != 2)
229 continue;
230
231 /* Edge collapse fails if (v2 - v1) is not coplanar to triangle. */
232 if (edge_collapse(mesh, mesh_info, v1, v2, verts[v2], afaces))
233 num_collapses += 1;
234 }
235
236 /* Cleanup invalid triangles and unreferenced vertices. */
238
239 return num_collapses;
240}
241
242/* ---------------------------------------------------------------- */
243
244std::size_t
245clean_mc_mesh (mve::TriangleMesh::Ptr mesh, float needle_ratio_thres)
246{
247 std::size_t num_collapsed = 0;
248 num_collapsed += clean_needles(mesh, needle_ratio_thres);
249 num_collapsed += clean_caps(mesh);
250 num_collapsed += clean_needles(mesh, needle_ratio_thres);
251 return num_collapsed;
252}
253
Vector class for arbitrary dimensions and types.
Definition vector.h:87
T dot(Vector< T, N > const &other) const
Dot (or scalar) product between self and another vector.
Definition vector.h:542
Vector< T, N > normalized(void) const
Returns a normalized copy of self.
Definition vector.h:456
std::vector< math::Vec3f > VertexList
Definition mesh.h:33
void get_faces_for_edge(std::size_t v1, std::size_t v2, std::vector< std::size_t > *adjacent_faces) const
Returns faces adjacent to both vertices.
Definition mesh_info.cc:172
void update_vertex(TriangleMesh const &mesh, std::size_t vertex_id)
Updates the vertex info for a single vertex.
Definition mesh_info.cc:56
@ VERTEX_CLASS_UNREF
Vertiex without any adjacent triangles.
Definition mesh_info.h:35
@ VERTEX_CLASS_SIMPLE
Vertex with a single closed fan of adjacent triangles.
Definition mesh_info.h:29
std::shared_ptr< TriangleMesh > Ptr
Definition mesh.h:92
std::vector< VertexID > FaceList
Definition mesh.h:97
#define FSSR_NAMESPACE_END
Definition defines.h:14
#define FSSR_NAMESPACE_BEGIN
Definition defines.h:13
#define MATH_ISNAN(x)
Definition defines.h:104
#define MATH_POW2(x)
Definition defines.h:68
std::size_t clean_caps(mve::TriangleMesh::Ptr mesh)
Cleans caps from the mesh by removing vertices with only three adjacent triangles.
std::size_t clean_mc_mesh(mve::TriangleMesh::Ptr mesh, float needle_ratio_thres)
Removes degenerated triangles from the mesh typical for Marching Cubes.
bool edge_collapse(mve::TriangleMesh::Ptr mesh, mve::MeshInfo &mesh_info, std::size_t v1, std::size_t v2, math::Vec3f const &new_vert, std::vector< std::size_t > const &afaces, float acos_threshold=0.95f)
Definition mesh_clean.cc:19
std::size_t clean_needles(mve::TriangleMesh::Ptr mesh, float needle_ratio_thres)
Cleans needles from the mesh by collapsing short edges of degenerated triangles.
void sort_values(T *a, T *b, T *c)
Definition algo.h:208
std::size_t mesh_delete_unreferenced(TriangleMesh::Ptr mesh)
Cleans unreferenced vertices from the mesh.
Per-vertex classification and adjacency information.
Definition mesh_info.h:43
AdjacentVertices verts
Definition mesh_info.h:45
void remove_adjacent_face(std::size_t face_id)
Definition mesh_info.h:140
void remove_adjacent_vertex(std::size_t vertex_id)
Definition mesh_info.h:147