【CGAL_网格处理】Isotropic Remeshing均匀化网格

原理

算法伪代码如下:

1
2
3
4
5
6
7
8
9
remesh(target_edge_length)
low = 4/5 * target_edge_length
high = 4/3 * target_edge_length
for i = 0 to 10 do
spilt_long_edges(high)
collapse_short_edges(low, high)
equalize_valences()
tangential_relaxation()
project_to_surface()

其中target_edge_length是网格的目标长度。

涉及的三个操作如下:

img

spilt_long_edges

该步骤将所有长于high = 4/3 * target_edge_length的边进行 Edge Spilt 操作。

collapse_short_edges

该步骤将所有短于low = 4/5 * target_edge_length的边进行 Edge Collapse 操作,新增的点位置为边两端点的中点,另外要求新的边不会长于high = 4/3 * target_edge_length

equalize_valences

该步骤目的是平衡顶点的度数,最佳度数 optimal valence 为

  • 内部点:6
  • 边界点:4

通过使用Edge Flip进行顶点度数的增加和减少。

img

tangential_relaxation和project_to_surface

该步骤解决三角形面积问题,实现网格面积的均匀化。

img

以上内容转自:Isotropic Remeshing - 知乎 (zhihu.com)

CGAL代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/remesh.h>
#include <CGAL/Polygon_mesh_processing/border.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <boost/iterator/function_output_iterator.hpp>
#include <CGAL/draw_surface_mesh.h>
#include <iostream>
#include <string>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef boost::graph_traits<Mesh>::halfedge_descriptor halfedge_descriptor;
typedef boost::graph_traits<Mesh>::edge_descriptor edge_descriptor;
namespace PMP = CGAL::Polygon_mesh_processing;

struct halfedge2edge
{
halfedge2edge(const Mesh& m, std::vector<edge_descriptor>& edges)
: m_mesh(m), m_edges(edges)
{}
void operator()(const halfedge_descriptor& h) const
{
m_edges.push_back(edge(h, m_mesh));
}
const Mesh& m_mesh;
std::vector<edge_descriptor>& m_edges;
};

int main(int argc, char* argv[])
{
const std::string filename = "data/simple80_complete.stl";
Mesh mesh;
if (!PMP::IO::read_polygon_mesh(filename, mesh) || !CGAL::is_triangle_mesh(mesh))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
CGAL::draw(mesh, "source mesh");
double target_edge_length = 1;
unsigned int nb_iter = 5;
std::cout << "Split border...";
std::vector<edge_descriptor> border;
PMP::border_halfedges(faces(mesh), mesh, boost::make_function_output_iterator(halfedge2edge(mesh, border)));
PMP::split_long_edges(border, target_edge_length, mesh);
std::cout << "done." << std::endl;
std::cout << "Start remeshing of " << filename
<< " (" << num_faces(mesh) << " faces)..." << std::endl;
PMP::isotropic_remeshing(faces(mesh), target_edge_length, mesh,
CGAL::parameters::number_of_iterations(nb_iter)
.protect_constraints(true)); //i.e. protect border, here
std::cout << "Remeshing done." << std::endl;
CGAL::draw(mesh, "remeshing mesh");
return 0;
}

image-20220811201735314

image-20220811201757939

image-20220811202139485

image-20220811202727607

关键函数

isotropic_remeshing()

1
2
3
4
5
6
template<typename PolygonMesh , typename FaceRange , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::isotropic_remeshing (const FaceRange & faces,
const double & target_edge_length,
PolygonMesh & pmesh,
const NamedParameters & np = parameters::default_values()
)
参数名 解释
pmesh a polygon mesh with triangulated surface patches to be remeshed
faces the range of triangular faces defining one or several surface patches to be remeshed
target_edge_length the edge length that is targeted in the remeshed patch. If 0 is passed then only the edge-flip, tangential relaxation, and projection steps will be done.
np an optional sequence of Named Parameters among the ones listed below

pmesh:可以是Surface_mesh或者Polyhedron_3

faces:可以通过faces(mesh)返回boost::graph_traits<CGAL::Surface_mesh<P>>::face_iterator的序列。其中CGAL::Surface_mesh<P>PolygonMesh

target_edge_length:同上述原理。

对于np参数,如下列出几个常用的

  • number_of_iterations:执行edge splits, edge collapses, edge flips, tangential relaxation and projection to the initial surface的迭代次数。默认值为1。

  • edge_is_constrained_map:包含pmesh的每个边的受约束或不受约束状态的属性映射。默认没有边被约束。

  • protect_constraints:如果为true,在edge_is_constrained_map (或者默认边界) 中的边在重建过程中不进行split和collapsed操作。默认为false。

    注意:如果protect_constraints为true的话,受约束的边不能大于4/3*target_edge_length。因此需要在这执行isotropic_remeshing()之前先执行split_long_edges()进行长边分割。

  • do_splitdo_collapsedo_flipdo_project

    都是布尔类型值。默认都为true。

问题与总结

在测试中,两个模型都是封闭的流形表面,故不存在边界。因此,无论protect_constraints取何值,remeshing后原模型面与面的过渡直线上的边将会变化,致使结果模型的棱边凹凸不平。为了验证上述猜想,使用带边界的三角网格进行如下测试:

image-20220812000806908

image-20220812001121765

image-20220812000833957

可以看到,当将protect_constraints置为true时(第三张图),边界上的边受到了约束,因此remeshing后不如protect_constraints置为false(第二张图)时的均匀。

因此,为了实现闭合网格remeshing前后棱边形状不变,我们可以将棱边上的边属性映射为受约束,而其余边属于映射为不受约束,得到表面网格的edge_is_constrained_map,再置protect_constraints为true,实现对这些边的保护。