新开坑，关于OpenMesh基本算法

panhao1 · 发表于 2013-8-30 00:12:41

开大川最近写python教材。顺便也写点东西来烘托下气氛，拉点人气。

panhao1 · 发表于 2013-8-30 00:13:32

本帖最后由 panhao1 于 2013-8-30 01:10 编辑

最简单的当然是obj。其实也是maya 到Rhino比较好的一个格式。不过Rhino(openMesh)不支持 >4边的面.玩过CGAL（LINUX下）的应该都比较熟悉。maya建模也要尽量避免5边面。这个贴图类的教材应该有讲（当然可以执行一次cc细分来解决）。不过这都不重要。此贴要讲的是做Mesh修复的（只用到三角面）。

闲话少说。关于mesh的基础知识大家可以先看wiki的介绍然后再看看openGL帮助

先说下算法用处。假设一个mesh有1w个点（i7 3770k的承载能力是10w点同屏不掉帧），1w面。如果一个地方出现了一个面的丢失,也就是破面了。我们就用此算法进行修复。把这个洞补上。导致破面原因很多。比如单位精度误差导致的。多边面细分。以及mesh的点没有缝合好。除了影响渲染材质，还会导致slic3崩溃，或者导出的时候二次破面。。反正该修的就得修，该补就得补。

panhao1 · 发表于 2013-8-30 00:27:11

本帖最后由 panhao1 于 2013-8-30 00:51 编辑

如果mesh的破面和MeshFace尺度比较大的话。最容易的办法是用quadTree来修复。这里切割到破面处的可能性几乎是没有。当然假设切割了也不要紧再迭代一次即可。这种算法本身就很快。所以可以反复执行。最终可以找到破面区域所有的点。然后焊接掉（weld）。

不过我们实际碰到的情况往往是需要给一个tolerance的状况。比如0.01f;这样就比较麻烦了。当然可以暴力穷举得到。对于象棋20倍以上的机器其实也是万点秒算吧（大概）。所以下面就说说如何穷举。

1 新建一个mesh面的线性表（面的索引）。
2 新建一个mesh点的空线性表。.Array一类的吧
3 把原来mesh的MeshFace导入到新的face线性表中，其实就是用原来的face，rhino中直接就是Mesh.Faces
4 通过穷举找到超过tolerance的没有重复的点的集合导入到新的MeshVertices线性表中。
5 这时我们发现新的face表和vertex表不对应。在上一步穷举中我们做一个点的对应表。原来每个vertex对应一个新vertex。
这是一个多（many）对应（few）少的关系。主要目的就是在这一步做到给face一个新索引。
6把新vertex表的vertex实例化。具体的方法当然是喜闻乐见的平均位置。一对一的就直接赋值。一对多的就是求那群旧点的平均。
7清理掉mesh.faces索引中有重复索引的face.
8用新的face和vertices表实例化Mesh。
9 利用三角面的meshFaceNormal的加权平均来计算每个normal。这里会发现如果原来部分meshNormal是反的话。这些新有些normal就是反的。Face索引保持原有的Normal方向。所以执行一次统一法线静态函数，来统一法线方向（底层提供）。
10 赋予新mesh默认材质。

panhao1 · 发表于 2013-8-30 01:01:15

ps
1关于如何剔除重复点。最简单的就是两次循环匹配了 (<O2复杂度）.
2 每次如果一个新vertex被>2次匹配的话需要刷新一下位置。新位置换算为被此vertex索引的全部vertices的平均位置。当然其实不做换算直接忽视新加vertex的位置也是可行的（一直用第一个vertex的位置，最后一起来做平均）。因为tolerance一般是破洞半径的10倍以上。如果实时换算vertex的位置的话，就可以省了第6步。

panhao1 · 发表于 2013-8-30 01:02:55

本帖最后由 panhao1 于 2013-8-30 01:08 编辑

RhinoC# Script案例
private void RunScript(Mesh x, double y, ref object A, ref object B)
{ try{
List<int> mapping = new List<int> ();
List<Point3d> ps = new List<Point3d>();
List<int> MapCount = new List<int> ();

ps.Add(x.Vertices[0]);mapping.Add(0);MapCount.Add(1);
for(int j = 1;j < x.Vertices.Count;j++) {
bool sign = true;
for(int i = 0;i < ps.Count;i++){
if(ps.DistanceTo((Point3d) x.Vertices[j]) < y){
sign = false;mapping.Add(i);
ps += (Point3d) x.Vertices[j];//这样直接加是错误的。应该是做个index备份。不然就会导致新的vertex失效
//添加 ps/=2;（懒人的修复方法）。
MapCount++;
break;}
}
if(sign){mapping.Add(ps.Count);ps.Add(x.Vertices[j]);MapCount.Add(1);}
}

for(int i = 0;i < ps.Count;i++){
ps /= MapCount;//注释掉（懒人修复方法）
}

Mesh mesh = new Mesh();
for(int i = 0;i < ps.Count;i++){
mesh.Vertices.Add(ps);
}

for(int i = 0;i < x.Faces.Count;i++){
if(x.Faces.IsQuad){
int p1 = mapping[x.Faces.A];
int p2 = mapping[x.Faces.B];
int p3 = mapping[x.Faces.C];
int p4 = mapping[x.Faces.D];
if( noRepeat(p1, p2, p3, p4)){
mesh.Faces.AddFace(p1, p2, p3, p4);
}
}
if(x.Faces.IsTriangle){
int p1 = mapping[x.Faces.A];
int p2 = mapping[x.Faces.B];
int p3 = mapping[x.Faces.C];
if( noRepeat(p1, p2, p3)){
mesh.Faces.AddFace(p1, p2, p3);
}
}
}
mesh.Normals.ComputeNormals();
mesh.Compact();
A = mesh;B = MapCount;
}catch(Exception ex){
Print(ex.ToString());

}
}

//<Custom additional code>
bool noRepeat(int a1, int a2, int a3, int a4){
if(a1 == a2)return false;
else if(a1 == a3)return false;
else if(a1 == a4)return false;
else if(a2 == a3)return false;
else if(a2 == a4)return false;
else if(a3 == a4)return false;
else return true;
}
bool noRepeat(int a1, int a2, int a3){
if(a1 == a2)return false;
else if(a1 == a3)return false;
else if(a2 == a3)return false;
else return true;
}

spore42 · 发表于 2013-8-30 01:20:19

带点图啊喂看不懂啊

claudemit · 发表于 2013-8-30 01:51:34

本帖最后由 claudemit 于 2013-8-30 02:27 编辑

进来膜拜潘神
粘贴到网页，所有【i】都丢了。。。

xyc44444444 · 发表于 2013-8-30 08:29:00

大神的语言果然看不太懂啊……

风竹 · 发表于 2013-8-30 08:52:44

帐号		自动登录	找回密码
密码			注册

[建模练习] 新开坑，关于OpenMesh基本算法

相关帖子