NCF参数化建筑论坛

标题: 新开坑，关于OpenMesh基本算法 [打印本页]

作者: panhao1 时间: 2013-8-30 00:12
标题: 新开坑，关于OpenMesh基本算法
开大川最近写python教材。顺便也写点东西来烘托下气氛，拉点人气。
[attach]39863[/attach]
其实mesh很好理解。就是我们所谓的“三角面”。写过Processing（openGL）的都知道要绘制图形。基本都是一个个三角面来绘制的（后面的GL版本支持四边面多边面绘制）。所以大部分的建模平台都是mesh在现实物体。（openGL后面的版本底层也是支持surface和细分的）。Rhino里面GH里面也不例外。主要图元在编辑状态是mesh显示包括tag Text textdot等。

不过写一些mesh的算法最重要的还是照顾那些机器比较水（超频啊混蛋）的童鞋。mesh显示简单物体以及计算都是非常快的，而且比较节省内存（大概是这样）。最最重要的是渲染，贴图也比较方便（大概）然后就是做slic3。转倒模型之类的方便。Mesh格式一大堆（具体可以看3d converter支持的格式）。比较常用的比如dae（skp，kmz） obj 3ds。

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

作者: panhao1 时间: 2013-8-30 01:02
本帖最后由 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
带点图啊喂看不懂啊

作者: claudemit 时间: 2013-8-30 01:51
本帖最后由 claudemit 于 2013-8-30 02:27 编辑

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

作者: xyc44444444 时间: 2013-8-30 08:29
大神的语言果然看不太懂啊……

作者: 风竹 时间: 2013-8-30 08:52
最近学习氛围好浓

作者: 几度天狼 时间: 2013-8-30 09:15
哇哦
好神啊……程序就看不懂了……

作者: wikii 时间: 2013-8-30 11:29
Open mesh 是啥？

作者: zhiaixu2010 时间: 2013-8-30 14:55
潘神要不要这样啊，看看大川写得多通俗啊，直接这么阳春白雪，受不鸟啊...

作者: sgrylicheng 时间: 2013-8-30 15:20
说要来吐槽，我就来了。。。反正意思大概明白，代码一点不懂，大概就是这样啦，（没办法啦，机子水，人也水，只能过来路过一下啦~，手工穷举法的穷逼路过）

作者: wdc63 时间: 2013-8-30 15:57

zhiaixu2010 发表于 2013-8-30 14:55

登录/注册后可看大图

潘神要不要这样啊，看看大川写得多通俗啊，直接这么阳春白雪，受不鸟啊...

哈哈，先学完我的教程再来看潘神的，我的是小学教程，潘神这个是研究生教材

作者: panhao1 时间: 2013-8-30 18:10

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

登录/注册后可看大图

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

选择性粘贴不行么？

作者: Je_t’aime_pass 时间: 2013-8-30 19:24
果断顶起来学习啊

作者: 腹肌王子 时间: 2013-8-31 01:09
向楼猪学习~~~~~~~~~~~~~~~

作者: claudemit 时间: 2013-8-31 20:07

wdc63 发表于 2013-8-30 15:57

登录/注册后可看大图

哈哈，先学完我的教程再来看潘神的，我的是小学教程，潘神这个是研究生教材

我们都等着念完小学呢~

作者: denghua 时间: 2013-8-31 21:50

claudemit 发表于 2013-8-31 20:07

登录/注册后可看大图

我们都等着念完小学呢~

同学你好

作者: claudemit 时间: 2013-9-1 01:24

denghua 发表于 2013-8-31 21:50

登录/注册后可看大图

同学你好

学长求带！

作者: panhao1 时间: 2013-9-1 03:24

denghua 发表于 2013-8-31 21:50

登录/注册后可看大图

同学你好

只是开个新坑罢了坑嘛你懂得

作者: 左手◆23年 时间: 2014-2-14 12:54
感谢楼主分享，赞！

欢迎光临 NCF参数化建筑论坛 (http://bbs.ncf-china.com/)