近来由于某些门课程设计,重拾了之前本博客中“物理引擎”系列,以C#作为平台重新实现,并且加入了一些可靠的设计模式,从而比以往的设计更加易用。在制作过程中,突然想要用粒子模拟“水”的效果,于是查阅了很多资料,SPH之类的物理算法还在研究,但就水本身的渲染而言,利用Metaball算法则是能够立竿见影的看到效果,下图就是实际效果:

fluid

 

本文谈论的Metaball是2D范畴的,3D范畴的Metaball和2D的Metaball原理是一致的,但是具体的算法及优化上是有一定的差异的。

首先来了解,什么是Metaball?下图来自于Metaball的Wiki页面:

Metaball_contact_sheet

 

Metaball算法,可以创造出多个形状光滑融合的效果,看上去就像是水滴融合一样,通过使用Metaball,可以模拟水面、颜色融合、变形球等等酷炫效果,如果你玩过LocoRoco或者黏黏世界,那么你就一定见过Metaball。

Metaball的原理很简单,Metaball的本质不是球,而是一种空间上的势能,类似于重力势能,每个球以球心为核,向外扩散势能,如下图所示:

1

 

当多个球处于画面之中的时候,这些势能将会叠加,形成下图的效果,我们将叠加的结果用等高线和颜色来进行标识:

2

 

之后,我们再一个高度限制,将这个势能齐头“砍掉”,也就是将所有势能高于某一定值的区域都绘制上颜色,这样就形成了2D平面上的Metaballs:

3

 

势能的公式很简单,通常写作:

f00

其中R为预期半径x0和y0为球中心,当f = 1时,点(x, y)到(x0, y0)的距离等于R。为了避免在实际计算中引入根号运算,该公式通常会被改写为:

f01

该公式的图示如下(图中r为上公示分母的根号,实际上是不能取负值的,这里仅仅为了凸显图形结构):

5

 

而Metaball的渲染公式按照之前的理论则可写为:

f1

其中Pixel表示像素点的取值,这里将结果二值化,在实际渲染中,可以通过根据不同Metaball公式值域取不同的像素颜色值来实现各种酷炫效果,关于这点,在本文中就不加赘述了,读者可以尽情发挥自己的想象力。

根据这一基本原理,我实现了下面这段代码:

这段C#代码使用了WriteableBitmapEx库,基于WPF的帧绘制,objList中包含了所有待绘制的球。

可以看到,由于WPF没有提供使用显卡进行渲染的接口,所以渲染工作完全由CPU来执行,并且我已经利用了C#内置的并行运算库,使计算机的所有核心都能够参与到该Metaball的渲染,但是不幸的是,效率仍然很低,当画面中的Metaball数目超过10个后,就已经卡得不成样子了。关于这个算法的效率,其实很容易分析,由于每个像素都要考虑所有的球,导致球数的增加,会成倍的增加绘制的时间成本,渲染的时间复杂度为:

O(WHN / CoreNumber)

其中W为渲染画布的宽度,H为高度,N为带渲染的Metaball数目,CoreNumber为并行度,也就是可并行使用的CPU数目。

因此,我开始思考如何优化这一算法,首先,我们注意到,势能曲线的降低速度是非常快的,这使得画布上的某一个像素若距离一个Metaball超过一定距离,那么那个Metaball对这个像素的影响则基本可以忽略,因此,我们可以为每个Metaball指定一个“有效区域”,在进行渲染的时候,只渲染有效区域即可,如下图所示的红色方框:

4

 

首先初始化一块缓存画布,然后遍历每个Metaball,每个Metaball将自己的势能权值累加到Cache中的对应位置,当所有Metaball的势能都叠加完成之后,再逐个像素遍历一遍就可以完成渲染。在这一过程中,有很多东西都是可以进一步优化的,例如势能函数,完全可以提前运算出一个离散的势能函数表,需要的时候直接调用即可(因为我们只需要计算从0 -> gridR范围内的势能,gridR之外的势能可以认为是0),并且的对于参数一样的Metaball,甚至连整个红色方框内的势能,都可以提前根据缓存好的势能函数表计算出来,从而避免多次执行平方根运算及过多的乘法运算。这里代码如下:

这样一来,根据这个实现算好的缓存表,按照我们的优化思路,再来看看Metaball的渲染代码:

这段代码非常简单,唯一需要注意的是,第一段代码中,由于可能出现两个Metaball的势能区域重合的情况,所以在对缓存画布的指定位置进行势能叠加的时候要加上锁,以防出现读写冲突,从而影响最终渲染结果。这段代码的时间复杂度为:

O((WH + 4 GridR^2 N) / CoreNumber)

GridR为势能有效半径,可以根据Metaball的大小及总数进行调整,从而达到效率最大化。

在我所制作的Demo中,各参数如下:

W = 500

H = 400

N = 50

GridR = 60

CoreNumber = 8

算法优化后,运算时间将比之前的算法提升至少10倍,再加上缓存表的优化,整个算法的运行时间实际上还要再在此基础上提升数倍,如此一来,原本最多支持10个Metaball的原算法,现如今将可以支持数百个,这样一来 ,通过粒子来模拟液体的渲染效率问题也游刃而解。

关于我文章开篇所提到的物理引擎,将在未来的文章中予以介绍。


 

参考资料:

  1. Exploring Metaballs and Isosurfaces in 2D http://www.stephenwhitmore.com/personal/article_metaballs.html
  2. Metaballs http://en.wikipedia.org/wiki/Metaballs
  3. http://www.grasshopper3d.com/forum/topics/metaball-equation
  4. Increasing real-time performance on canvas’ effects http://stackoverflow.com/questions/17177748/increasing-real-time-performance-on-canvas-effects

说点什么

1 评论 在 "有趣的Metaball — 渲染及优化"

提醒
排序:   最新 | 最旧 | 得票最多

6

wpDiscuz