注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

豆芽兵的生存探索

因,记录。留下历史,看到未来...

 
 
 

日志

 
 

04_维诺图和碎块(Voronoi Diagrams And Fragments)  

2013-01-08 17:53:01|  分类: 探索实验室 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
导读:这张图是漂亮的3D Voronoi Diagrams。它包含的思想应用非常广泛,跟我们CG特效非常相关的就是做碎块啦。本文介绍了一个RealFlow的插件。后面有关于Voronoi的一些资料。学习后,能不能自己写一个“破碎器”出来呢?
 
04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
 

04_维诺图和碎块(Voronoi Diagrams And Fragments

快速预览:“维诺碎块”

1.       C++命令脚本

2.       通过转换面从物体创建碎块

3.       非常快速

主要开发者: Martin Staudigel

译者:豆芽兵

 

201281日:在很多特效镜头中,碎块是非常重要的一部分。标准的方法是基于一种叫“维诺图”的思路,在两个三个,或更多个轴进行细分。大部分的软件使用2D的方法,将其转换成3D不是一件容易的事。现在,开发人员可以找到免费资料和源代码,但这么多代码中没有真正适合在RealFlow中使用的切分碎块工具。

 

原因是,RealFlow是一种模拟软件。不像建模工具,可以有很多建模的工具。几何操作只有一些原始和基本转换,功能是有限的。布尔操作(Boolean,减去,合并,添加 ,分割等等)就好多了。最困难部分是重新建立模型的原始表面。标准的3D软件,像MayaLightwave,已经提供了布尔操作或类似功能的插件。在RealFlow里,所有的操作都要从头写起,没有现有库或参考方案。

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
 
04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
 

因此给Realflow写基于Voronoi碎块工具要更困难一点。它需要很多努力来实现,凹凸表面重建。除了优化表面,运算速度是另一个问题。

我们的制作的脚本称为“碎块机,FragmentBuilder.这是一个完全独立版本开发,独立于任何第三方库或代码的。

       目前版本应用于“凸曲面”模型(对应于凹曲面模型)是很好的,已经非常快速和稳定。然而仍然有改善的空间,它缺少一种重要的功能,但该插件有一个很好方式,已经能使用于各种各样的物体和场景。在图片上你会看到模拟的截图,有516块,和RealFlow’s新的MultiJoint 系统。破碎时间,大概8秒钟(单核!)在MacPro”Nehalem”,2.26GHz.

       在下面视频中,你可以看到插件的能力。内部解决方案的最大优势是你可以独立在软件中使用,而不要用SD文件导来导去。另外,更有趣的是动态破碎。在这种情况下,碎块在一个特定时间生成,例如交互时。在破碎之前一直是完整的单个物体。基于物体的速度 ,在反应中心碎块很小,随着距离变大,碎块会更大。不幸的是,当前受限于RealFlow还不能做到,因为这些动力学对像物体的路径,无法记录和做缓存。

 

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索

Voronoi图碎块一

该视频演示了一个标准的RealFlow立方体破碎过程。基于Voronoi的中心只有几块,甚至几百块。最耗时的部分是显示碎块到RealFlow视图(也就是绘制过程,耗时),再添加“碎块对像”到节点面板。一旦建立好,他们就与RealFlow自带的模型一样。

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
 

这里,是创建过程中Voronoi区域中心一些说明。这些中心可以显示作为粒子,甚至保存成BIN文件进一步使用。它也能从其它软件导入粒子(如,Maya,3D StudioCinema 4D)或RealFlow emitters,使用他们作为初始设置,来生成碎块

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索

这个视频是,摧毁的柱子,并结合使用的RealFlow的刚体系统(RBDRigid Body Dynamic)。模拟花了一个小时,因为这里,单个的碎块没有被优化,包含有几百万面的多边形。这当然影响模拟时间。

附录:关于沃罗诺伊图

详细信息:http://en.wikipedia.org/wiki/Voronoi_diagram

沃罗诺伊图Voronoi Diagram,也称作Dirichlet tessellation狄利克雷镶嵌 )是由俄国数学家Georgy Fedoseevich Voronoi 建立的空间分割算法。灵感来源于笛卡尔用凸域分割空间的思想。在几何,晶体学建筑学,地理学,气象学,信息系统等许多领域有广泛的应用。

笛卡尔在其《哲学原理》一书中提出了太阳系是由漩涡 (Vortices) 组成的,他的论述展示了空间可以分解为一些凸域,如下图所示,每一个凸域都是围绕一个固定的星体形成的。

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索

尽管笛卡尔没有对这些凸域给出确切的定义,但是其内在的思想我们可以这样理解:对于一个空间 M,假定其中存在着一个结点集 SS 中的任意一个结点都可以对其周围环境——属于空间 M 的点集,施加影响;对于空间 M 中的一组点集,在 S 的所有结点中,它们受一结点 p 的影响最为强烈,那么这组点集就构成了结点 p 的一个作用域。

后来,笛卡尔的空间可以分解为凸域集合的概念自其原有的论述中被单独抽取出来,这一概念已被证实在许多科学领域都具有重要意义。当这一概念被引入到各个科学领域中时,被赋予了种种名称:

在生物学领域称之为中轴变换 (medial axis transform)

在化学、物理学领域,称之为 Wigner-Seitz zones

在晶体学中,称之为作用域 (domains of action)

在气象学、几何学中,称之为泰森多边形 (Thiessen polygons)

数学家 Dirichlet Voronoi 是第一次正式地介绍了这一概念,他们使用这一概念研究二次型:将二次型矩阵中的数据作为结点,结点的作用范围采用欧氏距离来体现。最终这一概念被命名为狄利克雷特镶嵌 (Dirichlet tessellation) 维诺图(Voronoi diagram)

Voronoi 是第一个研究笛卡尔所说的这种结构对偶性质的人,他把所有相邻的结点用线段连接起来,最终得到一个三角形网格。后来,Delaunay 研究二维点集的三角形网格剖分时也得到了与 Voronoi 所得的同样的三角形网格。Delaunay 对这种三角形网格结构中的每一条边给出了严格的限定:存在一个圆过边的两个端点,而且这个圆内不包含点集中的其它点。Voronoi Delaunay 的研究成果表明 Voronoi 的对偶图就是 Delaunay 所构造的那个三角形网格,后来人们就把 Voronoi 图的对偶图称为 Delaunay 镶嵌或 Delaunay 三角化。

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html 上有一个 java applet 程序,演示了二维 Voronoi 图与 Delaunay 三角化的关系。

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索 

可以在这个网站玩一下Voronoi Diagram。上图就是在网站上面生成的。

下面是一幅 3d 维诺图的可视化图片最初那张图片也是:

04_维诺图和碎块(Voronoi Diagrams And Fragments) - 豆芽兵 - 豆芽兵的生存探索
 

下面关于求解问题的内容来自博客园:http://www.cnblogs.com/USTC-fuxm/archive/2011/09/10/2172927.html

第一个要讲的是使用Voronoi图来求解点集中的最大空心圆。下面先给出寻找最大空心圆这个问题的定义:

Find a largest empty circle whose center is in the convex hull of a set of n points, empty in that it contains no points in its interior, and largest in that there is no other circle with strictly larger radius.

这个问题一看就是要是在无限多个点中选择一个点。所以我们的方法很显然就是要先剔除一部分点,使我们的问题在有限多个点中进行寻找。

这时很显然只有在convex中的Voronoi点和Voronoi边喝convex的交点是候选点,于是我们只要在这些点中选择就行了。

关于为什么是这些点?可以看书(computational geometry in c),其实很自然就是那些点,主要不要忘了convex边和Voronoi边的交点和剔除那些在convex外的Voronoi点就行了。

 第二个计算一个点击的最小遍历树(minimum spanning treeMST),其中MST的定义:

a minimum spanning tree of a set of points is a minimum length tree that spans all the points: a shortest tree whose nodes are precisely those in the set.

一个原始的想法就是使用贪婪的算法。首先将所有的边的长度进行排序,然后从头开始加入到树中,保证没有环出现,直到所有的边都遍历过了。

一个很明显的问题就是对所有的边排序,这是一个很庞大的工程。于是和上面的应用的想法一样,我们选择从那些边中选择一些候选边。

一个引理,如果MST is subset of the Delaunay triangulation.这个问题的证明使用的是反证法,也就是存在一条边属于MST,但是不属于Delaunay triangulation,然后利用的是如果一条边ab不属于Delaunay triangulation,就存在一个圆包含ab(ab是直径)的同时,一定还包含其他的点。由三角形的限制,其中的两条边会小于ab的长度,于是树 如果通过连接到那个点而达到b,而不是a,这时树比原来的小,于是和命题的条件不符。如果看不懂,请阅读书computational geometry in c

Voronoi Diagram有很多免费的源代码,但我没找到,如果你有什么发现,希望分享一下。


更多Voronoi Diagram信息请参考:

新浪博客:http://blog.sina.com.cn/s/blog_4b700c4c0102e1gs.html

  评论这张
 
阅读(2993)| 评论(1)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018