有趣的Metaball — 渲染及优化

有趣的Metaball — 渲染及优化
近来由于某些门课程设计,重拾了之前本博客中“物理引擎”系列,以C#作为平台重新实现,并且加入了一些可靠的设计模式,从而比以往的设计更加易用。在制作过程中,突然想要用粒子模拟“水”的效果,于是查阅了很多资料,SPH之类的物理算法还在研究,但就水本身的渲染而言,利用Metaball算法则是能够立竿见影的看到效果,下图就是实际效果:   本文谈论的Metaball是2D范畴的,3D范畴的Metaball和2D的Metaball原理是一致的,但是具体的算法及优化上是有一定的差异的。 首先来了解,什么是Metaball?下图来自于Metaball的Wiki页面:   Metaball算法,可以创造出多个形状光滑融合的效果,看上去就像是水滴融合一样,通过使用Metaball,可以模拟水面、颜色融合、变形球等等酷炫效果,如果你玩过LocoRoco或者黏黏世界,那么你就一定见过Metaball。 Metaball的原理很简单,Metaball的本质不是...

A*算法 – 介绍

A*算法 – 介绍
这学期学校开了人工智能课程,留了一项小作业,就是使用A*算法解决八数码问题,觉得挺有意思,于是就写下这篇文章来与大家分享。其实我很久很久以前就已经听闻过A*算法的大名了,但是鉴于当时的理解能力不足(懒?),就不了了之了。 记得当年第一次见到A*这个名字的时候,感觉非常的高端洋气,于是在气势上就输给了它,所以大家在继续阅读这篇文章的时候一定要放松,这个算法的确很著名,而且也的确非常的高效,但是它并不复杂,而且非常容易理解。 首先说下A*算法的作用:找到一条从起始状态到最终状态的最短路径。不知道大家看到这个作用有没有联想到什么?具有同样作用的一个算法“BFS广度优先搜索”在我之前的博客中介绍过,如果你不知道,可以点击这里回顾一下这个算法。 BFS通过“一层一层”地扩展节点,以此确保在发现目标状态的时候整个搜索树的深度最低,这是一种非常盲目的搜索方法,因为如果解的深度较深的话,我们有时候不得不搜索过所有的节点才能找到目标,而A*算法则不然,我编一个故事说明BFS和A*算法的区别: 王尼玛同学去食堂吃饭,但

快速幂运算

快速幂运算
最近看到的一些题里有利用快速矩阵幂来求快速解递归函数(比如Fibonacci数列),在很久之前看和RSA算法里也涉及到了快速求幂的算法,所以今天就想一块来介绍一下。 在介绍开始之前,先对本文的算法做一个声明,下文所提到的幂运算的指数n,满足条件n >= 0,这一点非常重要。 首先幂运算,大家其实都很好理解,其实就是: 无非就是把一个数自乘n次,所以我们通常计算数字的幂的算法就是: (代码1) [crayon-59c23030c17e3360403505/] 这个算法很简单,其复杂度是O(n)的,一般来说,这样的复杂度并不会使我们困惑,但是一般应用幂运算的地方,指数都会非常非常的大,比如1 000 000 000这个级别的,这时候我们会遇到两个问题,第一个就是我们不能再用int来存储整数,必须用高精度整数类型来进行存储,另一个就是在指数是如此变态的数量级之下,我们的计算量会骤然上升,结果也会异常惊人的大。 快速幂算法就是为了解决这个问题而发明的,其实它本身很简单,就是利用二分法,在具体介绍...

队列与BFS搜索

队列(queue)是一种简单的数据结构,它所遵循的规则是先进先出(First in First out, FIFO),对比LIFO的数据结构“栈”,你可以阅读[这篇文章]。这里所说的队列和我们现实中的队列是一样的,就比如说公交车排队,早到的,排在靠前位置的人自然可以优先上车(假设大家都很文明),利用这种特性,人们可以用来管理各种各样需要按照先后循序的事物,比如银行,因为银行的服务窗口有限,不能同时给所有人提供服务,所以利用计算机提供一个队列系统,给客户一个排队号码,计算机系统可以根据这个排队号码的大小来决定为谁优先提供服务。 按照和栈类似的介绍方法,为了使代码的表意更加明确,我使用C++标准库提供的队列适配器queue来构造队列这种数据结构。 使用queue需要引用头文件: [crayon-59c23030c1c0d703995727/] 初始化一个空的队列: [crayon-59c23030c1c12300561667/] 令一个元素进入队尾: [crayon-59c23030c1c1438