写点什么

FYP完了之后一直想写点什么纪念一下这几个月来的心情。

总的来说这两个月是相当的紧张，倒不是事情多的做不完，而是觉得做的东西价值不高。再怎么做最后可能还是拿个B什么的。所以常常是处在潜意识的焦虑之中。

比如说我的Game Development Project，做个Crowd Rendering的东西。我负责用GPU来render AI。说起来很有气势，什么Epic Battle啊，GPU啊，CUDA啊, 还有parallel AI等等。一开始在班上present initial progress的时候还是信心满满，老师也是对我们这组期望颇高。但后来越做越发现这些东西的局限性。首先是我们用的Unreal Engine做这个游戏demo。它的源码是没有公开的，只有所谓的high level的Unreal Script可以共我们使用。但我做GPU optimization不能看源码，能够optimize的东西是相当的少的。更何况像Unreal Engine这样的大牌，什么东西都是经过千锤百炼的，就算是render 大场面也是可以做到multi threading，非常的高效的。也是因为没经验吧，这些东西都是后来CUDA implementation出来之后才发现的。从来没做过optimization的我，很多东西都缺乏考虑，想什么硬件软件的东西，有没有access to source，什么样的AI 很compute intensive等等，都没什么研究。真的就是在乱搞。唉，这个我们的老师也是有责任的，是他当初把我们带到这个方向的，就连他也没这方面的经验。我们组也做了Billboarding的实验，这个东西不是Unreal Engine自带的，我们是利用particle system来做billboarding，但还有很多东西没怎么解决，比如说怎么做smooth transition from model to billboard。最后的public demo也是做的很无聊，感觉别组做的都比我们的好，什么音乐塔防游戏，用液态效果做的小游戏，3D侦探游戏等等。唉，说道学到什么东西，真正关于CUDA 和Unreal Engine的倒没有多少，只是觉得今后如果还做optimization一定不能optimize scripts,要能access 底层才是最重要的。

FYP算是混完了，也许report写的还不错，也许final presentation还不错。但我还是觉得我做的东西价值不大。就像innovation award presentation上那些judges说的，首先我的东西还有很多其他方面的问题没有解决比如说wireless protocol，这些才是当务之急。其次，我的省电的方式没有考虑到一个很重要的问题，就是cheating。也许我的算法问题不大，但就是这些irrelevant的的，让我的FYP失色不少。我想在Innovation award之前， Ananda和Anand也是没有想到这些问题的吧。我的research，我敢说，在五年之内不会有任何用处。不过，我是觉得，做了这个FYP对我最大的好处是，让我有机会钻研了一下Quake的source code，让我对这个传奇的游戏有了一个近距离了解。所以说我也不枉做了这个FYP。

总结一下，感觉大学四年来最后一年学得东西还是挺多的，也不知道最后能不能凭这些知识或是经验找到份理想的工作，不过能有机会接触Quake engine, GPGPU, Graphic Rendering, Ogre engine, Unreal Engine 和 Unity3D，以这些来结束我的大学生涯还是可以让我今后回味一下的。

另外，还有一个知道让我欣慰的是我跟小猫的感情一直都还不错。快两年半了，能够走这么远，我想小猫也应该跟我一样有成就感吧。加油。

---------------------------------------------------------------------------------------------

昨天跟小猫出去放松了一下，除了大吃大喝，还看了个电影。标题是我最爱的倩女幽魂，是刘亦菲，古天乐主演，叶问大导演叶伟信重拍的。看过之后我不由的想拍拍了。我靠，一个字，烂。叶伟信也就那两下吧，拍叶问的时候不也只是个酱油导演吗，在洪金宝和甄子单的吆喝下，混了个叶问大导演的名号。其实实力也就那样，拍出来的倩女幽魂是相当的铜臭味。本来书生跟女鬼的爱情故事是有一定的社会意义的，就是社会阶级门户思想根深蒂固，人们不能自由恋爱，是一种批判社会的工具。而在叶导演手下经典的倩女幽魂却被改编成了三角恋爱，小倩先跟燕赤霞谈恋爱，因为燕赤霞给小倩喜欢上吃糖果，又因为宁采成给她吃了糖果又喜欢上了宁采成。。WTF, 太俗气了。要搞现代三角爱情片就不要搞名著啊。这部片子拍下来救是典型的二流电影，以为这是迎合年轻人口味。靠，都这样，中国电影永无出头之日了。我觉得现在的中国电影人都是相当的浮躁的，根本没有用心去拍电影，不知道为什么要拍电影，也没有什么思想，甚至逻辑想表达出来。就只知道特效，大牌明星，票房这种东西。韩寒最近也批评刚出的历史片《战国》。也许现在的导演很难把握中国历史片的精髓吧。那就希望他们不要再去糟蹋题材了，也不要糟蹋我们的眼球。

不过，小猫最近好像还是找到了一部好片，叫《前度》。虽然又是什么三角恋的电影，但至少拍的很生活，不像刘亦菲的倩女幽魂。唉，五六月份的cg大片好像挺多了，KungFu panda, Transformer 3, Pirates of Caribbean X等等，应该都会去看的。

付诗一首：

十里平湖霜满天,

寸寸青丝愁华年。

对月形单望相护,

只羡鸳鸯不羡仙

小结优化

貌似这学期所做的事情都是围绕优化这个问题来进行的。那我就来总结一些我接触的优化方式吧。这些优化方式都是从具体的事物上产生，但都可以抽象化到很多地方。
Hierarchical Structure
这个主要说的是事物组织的方式。如果是有等级划分，从大到小，从粗到细，从高到低的话，一个复杂的事物就可以运行的井井有条，这主要要归功于高效的检索。比如说，用Binary Partition Subdivision 做occlusion culling, 如果上面的node 不可见那么下面的node就不用再看了，这样一下子就可以省掉很多多余的运算，很快就能找到哪些是可见的多边形。其实这里的高效是利用了Binary Tree的高效，类似的有Quad Tree和Oct Tree.
Pre-Computation
把所有可以预先计算的东西全都在线下算好，然后在运行程序的时候就可以直接拿来用。这种思想使得很多复杂的东西都可以实时表现出来，比如说3D动画。那些灯光效果可能是用渲染农场渲染了好几天才完成的，放映出来却也就只有好几十秒的事情。但效果是相当的逼真。所以预先计算应该是提高性能所必需的。
Data Compression
现在的电脑磁盘大到不行了，但有一个问题是传输速度还是很慢，一般的就只有20多MB/秒。所以这是一个瓶颈问题。类似的问题还有网络带宽，特别是手机无线网络。解决这些问题的方法可以是将所需要的数据压缩。具体用什么样的方法，格式压缩，需不需要加密的问题就要因人而异了。Quake 的一个一般大的地图，几千个多边形，用run-length compression之后的Bit-Array PVS只有不到3MB。简单的加密可以是xor如果要安全点就要更麻烦了。
Perception-based/Interest Set
这些看起来可能只适合游戏，因为对于一些可信度高的应用来说，是不能对用户的perception也就是感知作出一些假设的。但这里所说的意思其实是，如果有太多的信息，我们是没有必要把所以信息都表现出来，因为用户不能一下子把所有东西都看到。这里其实包含这比较多的UI设计，如果是做应用软件。好的UI设计也是可以很好的减小计算量，而这些在手机上尤为重要。
Adaptive/Progressive
如果一下子不能把想要的东西计算出来，可以先大概的预计一下，勾勒出一个框架，然后再在之前框架的基础上重复计算。之所以要把这个框架先表现出来给用户看，一是可以让他很快的了解结果，二是如果他从框架很明显看出趋势不对得不到想要的结果，就可以直接取消计算，节省资源。比如在radiosity里面使用的Jacobian iteration 每一个轮回都比前一个要更靠近真实值。
Fast Memory
CUDA里面对于不同层次内存的使用是非常讲究的。但一般是速度快的内存都有这样那样的局限比如小或者是只读，所以如何有效的分配内存是一项很深的技术。需要对系统的深入了解，比如BUS 宽度，数据宽度，有几个计算核，每个核的分配是怎样的。如果内存分配恰当，是可以达到几十，几百倍的提速。
Approximation
有时有些问题很难甚至无法解决，我们需要用估算来求出一个大概的答案。估算不是准确的答案，但近似于准确。它不需要很多资源来创造，是很多学术上解决问题的一个方法。

Coroutine

以前也听说过coroutine这个词，当时以为只是helper function的另外一种说法，故没有去研究个所以然。后来做unity3D project的时候有一次看到这个词，在文档里记录的例子是一个等待的程序，如下：

yield WaitForSeconds(5.0);

这个看起来不就是一个简单的wait吗，用一个loop一个timer就可以实现的一个东西而已。我当时这么认为。unity的doc也不是很详细，所以我也就没再去看。可是后来所UDK的时候遇到了一个叫latent function的东西，类似multi-threading吧，可以独立运行，然后在一段时间后返回。latent function也可以实现像sleep这样的功能。这时候我就想难道这个跟coroutine有什么关系，难道这是一个所以游戏引擎编程共有的功能。

UDK的文档里这样描述latent function:

While an actor is executing a latent function, that actor's state execution doesn't continue until the latent function completes. However, other actors, or the VM, may call functions within the actor. The net result is that all UnrealScript functions can be called at any time, even while latent functions are pending.

In traditional programming terms, UnrealScript acts as if each actor in a level has its own "thread" of execution. Internally, Unreal does not use Windows threads, because that would be very inefficient (Windows 95 and Windows NT do not handle thousands of simultaneous threads efficiently). Instead, UnrealScript simulates threads. 

这样看来我可以把coroutine或者latent function理解成一种模拟更高效的线程。在lua的文档里对coroutine解释的很详尽。coroutine的一个关键词是yield，yield相当于一般程序里面的return。区别就在于return是将原来方程的stack context都清除了，下次call这个方程的时候，一个新的stack layer又会建立。而yield把执行权交给calling function同时也save自己的context，下次再被call的时候可以接着之前的context执行。

这样可以模拟多线程。试想有好几个子方程被一个母方程控制在一个loop里面，然后子方程又在自己的loop里面完成一些任务，每loop一次call一次yield。母方程里的loop按顺序resume子方程，这样母方程每loop一次，子方程也一次loop 一次。

用coroutine比用thread的好处是coroutine不需要管理多线程会遇到的一些问题，比如说锁。但坏处我觉得是不能做太复杂的东西，因为这样会消耗大量的stack space，而且管理起来会很复杂。其实一些小的任务用coroutine就绰绰有余了，比如说walk()。

UDK里的latent function应该是coroutine的一个wrapper。它的功能比unity里的coroutine(貌似只能wait）多了两个，MoveTo和FinishAnim， 在使用这些function的时候我完全可以把它当作一个thread，但它是怎么实现的却是不得而知的。