小结优化

貌似这学期所做的事情都是围绕优化这个问题来进行的。那我就来总结一些我接触的优化方式吧。这些优化方式都是从具体的事物上产生，但都可以抽象化到很多地方。
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
有时有些问题很难甚至无法解决，我们需要用估算来求出一个大概的答案。估算不是准确的答案，但近似于准确。它不需要很多资源来创造，是很多学术上解决问题的一个方法。