请选择 进入手机版 | 继续访问电脑版

开源计算机图形学社区(Open Source Computer Graphics Community) |OpenGPU Forum (2007-2013)| OpenGPU Project

 找回密码
 注册
搜索
查看: 3550|回复: 12

关于Position based dynamics [复制链接]

Rank: 12Rank: 12Rank: 12

注册时间
2016-3-13
积分
897
发表于 2016-3-14 01:31:44 |显示全部楼层

发现很多人对PBD很感兴趣。我从事基于物理的模拟的研究已经超过五年了。期间看过不少这方面的文档,就想写一篇关于这个topic的综述。首先我绝非什么牛人。只是博士论文刚好涉及于此罢了。五年半的博士生涯只有一篇Eurographics 稍微拿得出手。跟浙大很多狂发Siggraph的牛人差距实在不是一点半点。那为什么还是要不自量力的写这篇文章呢?一来自己马上就要走向工作,以后很可能要远离学术研究,而且从事的工作也很可能与基于物理的模拟很远,还是希望能留下些什么,对自己的五年半的辛苦是个交代,也是希望能更多的帮助以后将要或正在从事这个研究的人。二来大牛们似乎不愿意出来分享自己的心得成果,我这也是抛砖引玉。以后我会逐渐把自己研究生涯总结的经验教训,有用的代码发布出来(绝大部分其实是别人写的,我只是整理而已)。第一次写难免有所不足,欢迎大家指正,后期我会逐渐修改。

我的论述主要集中在 soft body dynamics 比如 cloth。因为这是最开始pbd提出的应用领域。其他在rigid body fluid的应用没有涉及。。在这里必须要先指出的是两篇state of the art 论文

l  Jan Bender, MatthiasMüller and Miles Macklin, "Position-Based Simulation Methods in ComputerGraphics", In Tutorial Proceedings of Eurographics, 2015

l  Jan Bender, MatthiasMüller, Miguel A. Otaduy, Matthias Teschner and Miles Macklin, "A Surveyon Position-Based Simulation Methods in Computer Graphics", ComputerGraphics Forum 33, 6, 2014


作者Jan Bender在里面写得非常详尽。建议大家细读。那为什么我还要写这篇文章呢?因为我觉得Jan Bender关于PBD的发展脉络写得还是有点难以理解。这也不奇怪,因为发布论文要严谨,批评与赞誉都要有理有节,有时候有些话就不能写得太清楚。我这里用自己的研究经验和不严谨的语言组织一下,可能会更加清楚。有不对的地方,非常欢迎大家改正。

提到PBD,就必须提及这个技术是怎么来的,干什么的,怎么用的,有什么优缺点。


这里不得不先说说柔性物体的形变模拟。最开始的柔性物体模拟是采用基于力的模拟方法,也就是Force-based。就是一个物体的形变是靠弹性力平衡外作用力来产生的。怎么描述弹性力呢?计算物理中的continuum mechanics就提出了很多模型, 比如StVk, Neo-Hookean等等。这些材料在形变后的弹性力是可以推导出来的。很方便使用。后来大家发现了对于特殊的物体有简单的材料模型,虽然不精确,但是很简单,计算速度快。这就是用于衣服的mass-spring system。好了,现在我们有了弹性力了。我们就需要进行模拟,也就是timestepping: 给定当前状态和外力,计算下一个时刻的状态。这时候大概就有两种方法:显式(explicit)和隐式(implicit)。两种方法各有优劣。explicit每次步进的计算量非常小。但是很不稳定,所以时间步进长度必须很小。implicitunconditionally stable,但是每次步进可以很大。现在的问题来了,我们能不能使用explicit步进的同时可以使用很大时间步进长度,并且保持绝对的稳定呢?这就是PBD的来源。但是在此之前不得不提到最早的一篇文章:
Deformation Constraints in aMassSpringModelto Describe Rigid Cloth Behavior, Provot et. al. 1995
这篇文章其实是最早提出使用PBD。虽然作者并没有意识到,而且最开始希望解决的并不是上面提到的问题。而是一个类似的情况: super elongation。就是布料模拟的时候,固定点周围的spring形变过大。这是不自然的,因为我们平时看到的衣服不会有这么大的形变。要想减小这个形变就必须加大弹性系数,但是加大弹性系数就必须减小步进的长度(因为这里使用的是explicit time stepping, implicit time steping1997年才由largesteps in cloth simulation 引入。)所以作者提出不加大弹性系数而直接用几何方法改变spring的长度:对于一个spring,如果其长度过长,就把两个端点想中间移动。这种方法简单,实用。后来虽然有些改进,但是都不大。

到了2005年,出现了一篇革命性的文章:

MeshlessDeformations Based on Shape Matching 2005

作者 Matthias Muller 是领域中的绝对大牛。这篇文章第一次明确提出用geometry-driven 而不是 physics-driven的方法来模拟弹性形变。其中心思想是:

1,计算机图形学对基于物理的模拟有一定特殊性:就是精确度不是重点,重点是时间和稳定性。

2 弹性形变的物体会倾向于回到没有形变的状态。

也就是说,一个物体加了外力发生了形变,当我们撤掉这个外力后,物体会回到原来未形变的状态。注意,未形变状态不是指原来的状态,而已可以有一个平移和旋转(论文中的polar decomposition就是用来求出这个平移和旋转的)。我们可以通过控制回到原来未形变状态的快慢来控制物体的软硬。这个方法非常简单,速度很快。使得在游戏中模拟弹性形变成为可能。

到了2007年,又出现了一篇革命性的文章:

Positionbased dynamics 2007

也就是正式的PBD

这篇文章与上一篇文章的最大区别在于:pbd 可以模拟更多的形变效果。它定义了一系列的约束constraints。通过apply这些constraints就可模拟不同的形变效果。而shape matching其实可以看做一种特殊的constraints。两者关系紧密,又有所不同。所以学界一般把他们分开讨论。

那么什么是PBD呢?其实非常简单PBD核心就两步:

1,通过外力的explicit 步进求到一个暂时的形变位置x'

2,通过对apply每个约束改变这个暂时的形变位置得到一个最终的形变位置x.

那什么是约束呢?其实就是这个物体形变的一些规则。比如布料,我们直观上它会拉长和弯曲。我们自然认为内部弹性力会使得布料不拉长和不弯曲。那么我们就希望一条边的长度不变,一个dihedral angle的大小保持不变。这里会有一个非常重要的观察。如果这些约束都被满足了的话,这个物体不是很僵硬而且几乎不形变么?答案是:是的。那我们怎么控制软硬呢?关键就在我们求解每个约束上了。我们是使用迭代算法,所以如果这个迭代收敛的话,物体就僵硬,否则就软。这其实就是PBD的一大难点:到底是收敛好还是不收敛好呢?我们是很难控制的,只能去调试。当然大家也提出了很多方法来解决这个问题。

这以后,学术界几乎可以分为两个方向,一个直接继承shape matching, 一个直接继承pbd。在我看来,其实两个方法是可以归纳为一个方法的。但因为shape matching 有其特殊性,所以大家才单独讨论。

以后的发展方向其实就是两个:

1,如何使得速度更快。

2,如何可以模拟更多更好的效果。

先说shape matching。紧接着的文章就是加速。有两篇:

FastLSM:fast lattice shape matching for robust real-time deformation 2007

其实就是指当物体是regular lattice的情况下可以加速。

Fastadaptive shape matching deformations 2008

其实是使用hierarchical octree来加速。

总的来说就是当模拟的物体具有一定regular的时候进行加速。

还有使用multi-resolution的方法加速:

Fastand stable cloth simulation based on multi-resolution shape matching 2013

然后就是模拟更多的behavior了:

Robustreal-time deformation of incompressible surface meshes 2011

提出新的方法在只有表面网格的情况下模拟不可压缩性。同时也提出新的加速算法应用于不规则网格。

还有增加数值稳定性:

Solidsimulation with oriented particles 2011

至于PBD,其实也是大致朝着这两个方向发展:

提高速度:

multi-resolution加速:

Hierarchical positionbased dynamics 2008

然后是GPU加速

ScalablePartitioning for Parallel Position Based Dynamics 2015

这里多说一句,我们在apply constraints 的时候,通常使用gaussian sidel的方法,就是一个接一个的处理约束,下一个约束的处理是在上一个约束处理后的结果上进行的。这样比jacobi的方法收敛性更快。但是gaussian sidel的方法不是并行的。因为约束与约束之间有耦合。这样就没有办法用GPU加速。而这篇文章就是提出一个方法把独立的约束找出来以便可以并行处理。

这里再提一个最新的方法,是wang huamin老师提出来的。wang老师是这方面的绝对大牛哇:

AChebyshev semi-iterative approach for accelerating projective andposition-based dynamics 2015

其核心思想很简单:我们步进的时候是从x_n开始,得到一个x'_n, 然后在x'_napply约束,得到最终形变 x_{n+1}那么x_{n-1}的信息就没有使用了。如果我们把x_{n-1}的信息也带入进去,是不是可以提高收敛度呢。wang 老师就提出了这么一种算法把x_{n-1}的信息带入进去。

这里不得不提到的是strain limiting

Continuum-basedstrain limiting 2009

Multi-resolutionisotropic strain limiting 2010

虽然跟pbd不同,但其实核心思想是一样的,就是先改变位置,再加入约束。这两篇文章跟provot 1995的思想很相近。

然后另一条路就是不同的behavior了。一个pbd模型的形变效果和收敛速度取决于采用的constraints。最开始的pbd: position based dynamics 2007只提出了几种约束:

1, stretch

2, bending

3, collison

4, cloth balloon

能够模拟的效果有限。而且bend constraint的收敛性很慢。

后来就有人提出isometric bending constriant A quadratic bending model for inextensible surfaces 2006),其实就是在原来的bending constraint上假设各条边的长度不变。这样dihedral angle关于四个点就是线性关系。这个约束就好求解多了。而且收敛性大幅提高。

现在我们就想问能不能模拟更复杂的behavior呢?比如shearing

StrainBased Dynamics 2014

就提出用green strain来当constraint。并提出怎样修改green strain使得收敛性更好而且约束之间更独立。

Position-BasedSimulation of Continuous Materials 2014

提出用continuum mechanics中的能量函数充当constraints。这样就可以近似模拟不同的材料的behavior了。

最近有一篇文章提出用pbd来模拟rod:

position based elastic rod 2014

现在就有一个重要的问题。position-based dynamics force-baseddynamics 到底有什么区别?它们的结果究竟有何不同?

这里就有三篇很重要的论文:

l  Example-based elasticmaterial 2011

l  Fast simulation ofmass-spring systems 2013

l  Projective dynamics: fusingconstraint projections for fast simulation 2014

第一篇提出force-based dynamics可以看作是对一个函数的优化。

第二篇提出 large steps in cloth simulation 1997 里面提出的implicit timesteppingone step backward Euler stepping)可以看作是对这个优化只进行一步newton迭代。对于mass-springsystem, 通过修改这个优化函数我们可以使得其minimization 不变而计算复杂度变低很多:也即是说在小得多的计算量下得到相同或更好的结果,而最终收敛结果是完全一致的。

第三篇是在第二篇的基础上推广到更多模型,包括volumetric模型。

然后在

JanBender, Matthias Müller and Miles Macklin, "Position-Based SimulationMethods in Computer Graphics", In Tutorial Proceedings of Eurographics,2015

中有一个重要结论,就是pbd可以看做force-based dynamics 的一种特殊情况:stiffness趋近于无穷大。这是一个非常重要的结论。因为它指明了以后pbd的研究方向:如何用pbd更加精确的模拟force-baed dynamics

PBD发展到现在,可以说已经很成熟了。但是还是有很多问题没有解决。

1 物体形变的软硬不光取决于弹性系数,还取决于时间步长和是否收敛。一方面我们希望收敛,因为我们要apply constraints。如果不收敛,形变可能会很奇怪。另一方面,我们不希望完全收敛,因为完全收敛的模拟会显得太僵硬。

2,时间步长也是一个重大问题。对于force-baseddynamics, 不管时间步长选择多少,当物体静止下来后,其形变都是一样的(稳定状态)。但是对于pbd来讲,步长越长,物体越软。现在通常的解决办法是把步长固定下来,因为在游戏中我们通常使用固定步长(1/60s)。所以是可以接受的。但是有时候我们往往希望可以动态调节步长以节约开销。


3,网格的离散化也会影响形变。其实即便是force-baseddynamics, 网格的离散化也会影响形变,粗网格的形变跟细网格的形变当然不一样。但是,当一个网格的密度已经足够大了以后,继续refine这个网格是不会对结果产生影响的。因为这个网格已经足够密了。对于pbd, 却完全不是这样,不断加细一个网格并不会收敛到一个特定的结果。就跟mass-spring system一样。这样就产生一个麻烦。对于force-based dynamics, 我们可以使用adaptive mesh。就是当feature很多的时候使用细网格,反之使用粗网格。但是如果pbd,这种adaptive mesh就可能产生很大的问题:稍微refine一下形变结果就相差很远。但是我想这个问题应该可以解决。如果有人想在这个方向进一步研究,我们可以深入讨论一下。

Rank: 8Rank: 8

注册时间
2014-5-28
积分
164
发表于 2016-3-14 14:31:28 |显示全部楼层
本帖最后由 kxiaocai 于 2016-3-14 14:32 编辑

点赞 ~~

使用道具 举报

Rank: 8Rank: 8

注册时间
2014-5-28
积分
164
发表于 2016-3-14 14:44:56 |显示全部楼层
关于shape matching method, 2000年Thomas Jakobsen提出来position correction (Thomas, Jakobsen. "Advanced character physics." IO Interactive, 2DK-1463 Copenhagen K, Denmark (2000).); Müller给进一步发扬了。

另外,觉得shape matching跟之前的As-rigid-as-possible的一系列文章在想法上也有一定的联系。

使用道具 举报

Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20

注册时间
2010-3-27
积分
6093
发表于 2016-3-14 15:59:30 |显示全部楼层
最近在学习,有大牛关注,回两句,理解不正确的请见谅。
1.我觉得Jan Bender, MatthiasMüller 以上两位不止是理论上有,还实现出产品(代码),这才是牛的地方,不像国内的XX论文,理论一大堆,就是没有实现过,让人看了白看(可能比较愚钝)。还是那句话,Talk is cheap,Show me your code!
2.楼主介绍的两篇文章我也读过,的确是PBD的必读。里面居然谈到Gauss-Seidel方法收敛慢,涉及到多重网格法(multi-grid method)
3.里面的刚体约束,我没有太理解Position-Based Rigid Body Dynamics,求解答。

使用道具 举报

Rank: 13Rank: 13Rank: 13Rank: 13

注册时间
2012-8-22
积分
1076
发表于 2016-3-15 17:08:58 |显示全部楼层
挺好的文章,个人认为projective dynamics在接下来的时间内会很快的发展并逐步代替position based dynamics。

pbd明显的问题是物体的stiffness受迭代的控制。

btw,projective dynamics其实核心思想很简明。在做能量优化时,传统的隐式方式是通过求解一个线性方程组,也就是牛顿法,而projective dynamics里利用梯度下降法代替牛顿法,明显提高了效率。

使用道具 举报

Rank: 9Rank: 9Rank: 9

注册时间
2016-3-8
积分
211
发表于 2016-3-16 10:36:29 |显示全部楼层
我就是楼主所说的“也是希望能更多的帮助以后将要或正在从事这个研究的人”,确实给我很大的帮助。

不知道楼主能不能针对physically-based cloth simulation再开一个帖子谈一谈呢。

使用道具 举报

Rank: 12Rank: 12Rank: 12

注册时间
2016-3-13
积分
897
发表于 2016-3-16 15:43:06 |显示全部楼层
stanleyerror 发表于 2016-3-16 10:36
我就是楼主所说的“也是希望能更多的帮助以后将要或正在从事这个研究的人”,确实给我很大的帮助。

不知道 ...

cloth simulation 是一个非常非常大的题目,发展比pdb要久远的多。我现在的能力有限,恐怕还没办法对这么大的一个问题做一个全面的survey。以后等积累多了慢慢可以试试看看。
因为我觉得一个好的survey一定要了解一个问题的最开始和最新的论文。而且要指出其不同时间的发展方向和解决的难点。也就是要有一个清晰的脉络。最好能有自己的思考和对未来发展的判断。
写这个帖子我心中都比较忐忑。生怕自己有什么遗漏和偏差,给人造成不好的影响就是罪过了。如果大家感兴趣,我会尽量努力。也希望有大牛能提供帮助。

使用道具 举报

Rank: 12Rank: 12Rank: 12

注册时间
2016-3-13
积分
897
发表于 2016-3-16 15:59:59 |显示全部楼层
pramanc 发表于 2016-3-15 17:08
挺好的文章,个人认为projective dynamics在接下来的时间内会很快的发展并逐步代替position based dynamics ...

在我看来,projective dynamics 的核心在于提出一个二次的能量。最终求解还是牛顿法,只是hessian矩阵固定所以可以提前分解。核心思想跟fast mass-spring很相近。
但是跟fast mass-spring 相比他有很大的问题。
fast mass-spring可以理论保证绝对收敛到原来的mass-spring system。就是说模拟结果可以完全一致。projective dynamics 确没有相同的性质。
其实在fast mass-spring出来后我就一直在思考如果推广到volumetric上。当时想了很多办法。最简单的是推广到corotational FEM上。也提出了一个模型。但是后来发现如果poisson 分量过大的话,收敛些太差,速度很慢。
projective dynamic 也存在一个问题,他没有办法精确模拟任意的弹性材料模型。比如StVk他就没有办法精确模拟。
另一个问题在于他需要求解线性方程组。虽然可以预先分解。但是这个求解不是gpu-friendly的。也就是说很难用GPU进一步加速。对于超大规模问题还是有限。
还有一个问题就是他的时间步长必须预先设定。虽然有合理应用。但是adpative time step是更加期望的。

使用道具 举报

Rank: 13Rank: 13Rank: 13Rank: 13

注册时间
2015-6-17
积分
1131
发表于 2016-3-16 20:41:18 |显示全部楼层
ljb 发表于 2016-3-14 15:59
最近在学习,有大牛关注,回两句,理解不正确的请见谅。
1.我觉得Jan Bender, MatthiasMüller 以上两位不 ...

Jan Bender, MatthiasMüller   是一个人吧,没有第2套code阿?

使用道具 举报

Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20

注册时间
2010-3-27
积分
6093
发表于 2016-3-17 17:32:42 |显示全部楼层

请选择你心目中的男神?
这家伙什么也没有留下

使用道具 举报

Rank: 13Rank: 13Rank: 13Rank: 13

注册时间
2011-3-11
积分
1042
发表于 2016-3-22 19:37:48 |显示全部楼层
其实我的男神是Projective Dynamic的Ladislav Kavan, 不错的帖子。 希望物理仿真的帖子越来越多

使用道具 举报

Rank: 9Rank: 9Rank: 9

注册时间
2014-3-13
积分
363
发表于 2017-6-29 11:59:15 |显示全部楼层
有幸能读到这篇总结。
我从上个月开始,研究布料模拟的相关算法,论文也是找了一大堆,但是没有仔细去总结过(因为创业团队,要以结果为导向)。看了你这篇文章,感觉受益颇多。
另外想问一下,关于另外一篇:Extended Position Based Dynamics,是否有做过了解?这篇论文介绍了PBD本身的不足:stiffness由iterationNum限制。我读了论文,但是对于其中关键的地方都不能了解,在实现的时候就无从下手。

使用道具 举报

Rank: 12Rank: 12Rank: 12

注册时间
2009-9-18
积分
542
发表于 2017-7-6 08:58:05 |显示全部楼层
先顶后看

使用道具 举报

最近看过此主题的会员

您需要登录后才可以回帖 登录 | 注册

‹‹
我的工具栏

关于我们|手机版|Archiver|开源计算机图形学社区(Open Source Computer Graphics Community) | OpenGPU Project | OpenGPU Forum (2007-2013)

GMT+8, 2017-11-23 18:57 , Processed in 0.244018 second(s), 12 queries .

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部