当年的PS2项目SMB的开发小结，现在看来感触颇多，发出来缅怀一下那种奋斗的精神。
<一> 描画：
1.关于贴图ID：
最初用到的每张新的贴图，都会在TextureManager中生成新的实例。但是，假设模型A和模型B都用到贴图A，那么贴图A实际上只需要一份实例，否则就会带来内存的极大浪费，以及VRAM的大量无用upload。
为了鉴定这些物理上其实相同的贴图，我们对每张贴图都附加了一个全局唯一的ID，然后用这个ID来判断需要生成的每张贴图，如果该贴图ID已经存在，则直接返回已存在贴图的引用。
通过这个技术，我们把贴图upload时间缩短了70%以上。
2.关于VRAM管理
贴图在VRAM中以BLOCK为最小单位存放，但是存放顺序却不是连续的，所以需要对齐数据。
贴图的尺寸的拉伸方法是：
若 width < PageWidth 且 height <= PageHeight
把小于 BlockWidth/Height 的 width/height 拉伸为 BlockWidth/Height
把 width/height 按照较大者，拉伸为方形 （width=height）
否则
把小于 PageWidth/Height 的 width/height 拉伸为 PageWidth/Height
若 width > 64
把 width 按照64对齐
贴图的对齐方法是：（注意贴图width/height已经拉伸过）
若 贴图size > PageSize(2048word)
按照Page对齐
否则
按照 贴图size对齐
最初的代码始终按照Page对齐，而由于存在大量小贴图，导致VRAM的浪费。
修正这个问题后，我们把贴图upload时间再次缩短了30%左右，至此简单BG的upload时间几乎为0。
3.复杂BG导致描画超时的处理
由于大量复杂BG的存在，以及2-4分屏的加剧，描画曾经一度严重超时，下面是SMB2 RACE Stage2的统计数据：
4 player, total 6 monkeys:
------------------------------
CPU max: 43643, min: 26291
3D max: 38090, min: 20310
2D max: 2940, min: 1916
Logic max: 4525, min: 2004
可以看出，复杂的BG不仅直接导致描画超时，而且也对CPU速度严重影响，这主要是由于texture的upload/bind，大量dma数据的打包，material的设置等等。总的来说主要是avdisp_material占据了大部分时间。
虽然我们采用了减面，减贴图size，减少upload时间，采用ClipBox等大量手段，最终仍未解决多分屏下复杂BG的描画问题（虽然CPU时间由于优化碰撞检测已大大提高）。最终采用了SkySphere。
失败的主要原因有很多，包括GC所使用的模型的polygon数和排列方式，以及material/texture均不适合PS显示，当然这对于移植来说是不可避免的问题，可是最重要的原因是：
场景未能高效率管理，即缺少BSP/Octree一类的管理算法。GC原版就缺乏这种算法，而由于种种限制我们也没有增加这些算法，但是这确实是可能的。
4.关于模型的LOD
以GOLF为例，GOLF的每个场景中存在大量树（经常超过100棵），描画树占据大量时间。而有些树距离Camera很远，明显不需要用高精度去描画，所以我们使用了LOD。
最后，我们对于每种树都制作了3种LOD，根据OBJ中心距离Camera的位置选取LOD级别，解决了GOLF超时的问题，而且数据的小幅度变大事实证明也是无关紧要的。
此外，在描画MainGame的Bumper/Switch，Boat的Tree/Hunt等场合，也成功应用了LOD。
顺便提一下，适当降低FarClip的距离，降低粒子系统的粒子数目，也是提高速度的好办法。
5.减面，减贴图size及遇到的一些问题
关于减面：一般来说polygon数减少会直接提高性能，但是polygon的排列也非常重要。出现过很多polygon数减少而性能反而下降的情况。我们未能总结出一般规律，但是，重新减一次面，或者用lightwave减面，是一个办法。
另外减面后，会导致coli数据和显示不对应的问题。而减面所带来的巨大工作量，也是需要考虑的。
最后，关于程序减面，我们做了一些实验，但是目前仅能用于不带贴图的模型，还无法投入实用。
关于减贴图size：我们用观察法手工减的贴图size，而减色则是用的GenShock。手工减size浪费时间，而且由于贴图数据经常变化，也导致重复劳动。可是，我们缺乏减size的一般算法。目前，在原始数据阶段就减size，比导出数据后再减更好。
另外贴图width的限制是：
PSMCT32 2的倍数
PSMCT24 8的倍数
PSMCT16/16S 4的倍数
PSMT8/8H/4/4HH/4HL 8的倍数
6.OBJ的CLIP带来的思考
最初模型的CLIP采用了sphere方式的CLIP，由于考虑到大量模型的形状更趋近于box而非sphere，我们统计了模型数据的position数据，并求取了BoundingBox，以此作为CLIP的依据。
然而，情况却并非想象：我们已经充分优化了CLIP本身的效率，速度的仍然提高微乎其微，我们每frame也就多CLIP掉一两个Object。为什么？因为GC原版划分出的Object实在太大了，这样大的Obj，无论Camera如何偏转，几乎都会落在View Frustum内。
我们想到了按照Material来CLIP，因为Obj总分成若干个Material，所以每个Material会更小。然而我们再次失败了，因为Material的划分，是依据贴图和材质的分布，而不是空间的分布，Material的形状千奇百怪，根本无法提高CLIP率。
最后的教训就是：必须要有场景管理，哪怕是最简单的形式，都能大大提高效率。比如把OBJ按照空间分布划分成SphereTree，用父子关系的层次球来CLIP，简单而且有效。可是由于GC原版就缺乏这种算法，以及模型格式转换的巨大难度，我们的时间已经不足以实现它了！
7.我们放弃了什么？
GC原版拥有丰富的特效和属性，其中很多是PS2无法或难以实现的，我们大约放弃了以下特效：
多层贴图（Multi-Texture）：
我们基本上是选取其中的DetailMap，而放弃其他贴图。某些模型选取了EnvironmentMap。例如Shoot中的子弹。其实使用MultiPass可能实现，但是对于本来就超时的PS2，就不可能了。
灯光贴图（LightMap）：
直接放弃，因为没法做Modulate。
高光贴图（SpecularMap）：
我们使用Vertex Lighting代替，
Specular = Cs*sum[Ls*(N.H)P*Atten*Spot]
Cs：材质的Specular
Ls：光源的Specular
P：材质的Power/Shiness，PS2取了固定值
N：顶点normal
H：中间向量
H = norm(norm(Cp - Vp) + Ldir)
Cp：Camera的位置。
Vp：顶点的位置。
Ldir：从顶点到光源的向量
简化公式：H = norm((0,0,1) + Ldir)
凹凸贴图（BumpMap）：
GC原版虽然支持，但并未真正使用，直接放弃。
阴影贴图（ShadowMap）：
我们一律用PolyShadow代替，即用一个圆形的polygon代表影子，然后根据物体的位置和方向，决定影子polygon的大小和浓度等。
实时生成的环境贴图（realtime-created EnvironmentMap）：
这个放弃了，虽然我们支持预渲染的环境贴图，但是由于实时生成环境贴图需要把几乎整个场景额外描画一次，为了避免超时只好放弃了。
贴图扭曲（Texture Twist）
PS2无法支持pixel级别的操作（VU大约相当于VertexShader），所以这个效果只能放弃，导致我们在表现水/蒸汽等时，效果大打折扣。
在Z-Test，AlphaBlend等方面：
由于PS2的性能限制，不得不做了简化。
在TextureAddressMode方面：
由于PS2本身缺乏对Mirror的支持，以及Repeat数的限制，对原始数据做了大量修改，工作量十分巨大。
8.材质的简化与排序
由于放弃了多贴图及很多效果，材质就可以得到简化。
同时由于希望减少texture的切换次数，我们把Material对于textureID进行了排序，这包括Material内部和Material之间的排序，即把相同的texture调用尽可能排列在一起。
最终结果是将texture的切换次数减少了50%以上。
9.关于DMA打包
DMA打包同样占据大量CPU时间。尽可能提高一次访问的字节数，是提高打包效率的关键。
举一例：
inline void pglPacketAdd4Vectors( const f32 *vector
{
*((u128*)_dma_curFifo->writePtr)++ = *((u128*)vector)++;
*((u128*)_dma_curFifo->writePtr)++ = *((u128*)vector)++;
*((u128*)_dma_curFifo->writePtr)++ = *((u128*)vector)++;
*((u128*)_dma_curFifo->writePtr)++ = *(u128*)vector;
}
当然这要求数据必须是连续而且对齐的，这需要我们修改数据为对DMA友好的格式。
此外，打包时光照参数可以进行预计算，即在光照属性改变时，一次性计算光源参数，并在打包前把光源参数乘以材质参数，然后再执行打包。
10.关于60frame到30frame的转换
我们最终采用了逻辑每frame走两次，描画每frame走一次的方法；这样刷新率实际为每秒30frame。
由于减少了描画次数，效率得到了提高，但是带来了一个问题：
当逻辑判断放在描画的代码中时，某些基于时间戳的判断可能变得无法成立，比如描画时判断timer是否等于某值，timer
更新在逻辑的代码里（每frame更新两次，即减2），如果该值为奇数，则判断永远无法成立。
我们认为最好的方法是把逻辑代码和描画代码完全分开，可是对于已有的source，则可能只好修改判断值了，或者把等于的判断改为小于等于，也是一种解决方法。
<二> 碰撞检测：
1.场景相关性切分及树状结构的优点
碰撞检测需要遍历场景的三角形，最终执行的是以三角形为基本单位的计算。可是，大量的三角形并不可能产生碰撞，计算这些碰撞浪费大量时间，需要快速排除它们。
这要求用于碰撞的场景polygon数据，必须按照某种数据结构存储，然后根据position和数据节点的位置关系，可以快速排除整个节点。
GC原版采用了固定切分的方法：沿Y轴方向俯视，把场景在XOZ平面上切割为256*256个同样大小的格子。这样，如果pos不落在某个格子，那么这个格子所有polygon立刻被排除。
这种分发有重大缺陷，它没有考虑到场景的polygon分布情况，即切分是场景无关的。那么如果polygon在场景中的分布极不均匀，密集于小范围区域内，则会导致某个格子里存在大量polygon，而其他格子却几乎空白的情况，这大大降低了切分带来的好处。
我们采用了Octree及Quadtree，来执行场景相关性切分，即从包括整个场景的root节点开始（所有polygon均在此节点内），递归把节点切分为8/4等分，然后不断把父节点的polygon传递给子节点，而子节点分别判断这些polygon是否在本节点内。依次递推，直到节点所含polygon数达到最小值，或者树的深度达到最大值，或者切分带来的效益达到最小值。
使用时，由于每个节点均拥有BoundingBox，可以轻易执行pos与节点的位置关系判断，如果pos在节点外，该节点被抛弃，否则判断pos位于哪一个子节点内，然后递归访问下去，直到到达叶节点，此时取出叶节点内的polygon列表，即为必须执行碰撞判断的polygon。
这样，在polygon密集的小范围区域，切分也会密集；而在稀疏区域，切分也会稀疏，即充分考虑了场景的polygon分布。
最终我们使用这种方法，消除了大部分的CPU超时。
2.使用Octree及Quadtree遇到的问题
a.从原始压缩格式和预先Transform的coli数据，解析出三角形信息，是极为困难的。
b.由于很多场景形状趋于扁平，这种场景便退化为Quadtree，这样存储容量和效率都较高。
c.快速移动的物体可能会在2个frame中穿越整个节点，而导致碰撞出错。也就是节点必须规定最小size，一般我们至少采用1.5*rad（球半径），而且Quadtree的问题相对较少（Y方向不切分）。
d.由于额外的数据结构信息要写入coli数据，内存用量的增加和Load场景时的BuildTree时间，都是不容忽视的。我们通过给工具增加很多控制参数，根据不同的场景情况制定切分的等级，解决了这些问题。容量过大的场景切分较少，而在容量足够时，则增加切分，以提高碰撞效率。
e.可以采取一系列技巧以提高树的访问效率，比如：
u8 idx = 0;
if( y < center.y idx += 4;
if( x > center.x idx += 2;
if( z > center.z idx += 1;
然后child_node[idx]就可以访问到对应的子节点。
采用Hash表可以进一步提高访问效率，但是我们未采用。
3.为什么不用BSP?
涉及portal,PVS等等技术难点，而且凸cluster，CSG，和AxisAlign的限制也使得应用BSP变得极其困难。
总的来说，BSP涉及艰深的几何算法，然而它的确是目前最高效的场景管理方法。即使花费1年左右的时间，制作通用的BSP编译器，也是非常值得的。
4.用于碰撞的polygon的预先Transform
由于和三角形的碰撞通常要转换到三角形的本地坐标系进行，那么假如对三角形的顶点进行预先Transform，则可以提高效率（此时只需要把pos变换到该坐标系）。
最终采用的预变换格式为：
typedef struct {
Vec pos;
Vec normal;
s16 xang;
s16 yang;
s16 zang;
u16 flag;
Vec2D lpos[2];
Vec2D lnml[2];
} ********;
pos是一个3D顶点，normal,x/y/zang定义了本地坐标系，而lpos，lnml是变换到本地的另外两个三角形的顶点。变换采用CalcPoint函数（即Vector*Matrix）。
5.关于基本碰撞函数
基本碰撞函数的优化也是非常重要的，在已经确定了必须参与碰撞的三角形的最小集合后，就是实际的碰撞效率了。我们通过使用VU汇编，使效率得到了更进一步的提升。
<三> 逻辑/一般代码优化：
1.关于Message修正
建议把Message从source中分离到script内，并且按照机种和语言版本分类。
2.关于定位瓶颈，CATS和DebugWindow
最初定位瓶颈的工具是：perf_timer（代码段执行时间统计），perf_bar（每frame的CPU,GPU时间的条状表示）。然后，我们采用注释掉代码段和插入计时代码的手段，寻找瓶颈。
这的确解决了一些问题（比如由此发现了贴图upload的问题），但是效率和准确性很差。
后来我们使用了DebugWindow，它是我们自己编写的具有GUI的Debug工具，通过运行时可以即时呼出的DebugWindow，以及提供的很多开关和数据显示，我们找出了如贴图的VRAM对齐等问题。然而由于DebugWindow的介入时间太晚，所以作用已经很小了。
最后说说CATS，它是Metrowerks公司提供的专业分析工具，可以提供精细到每行代码级别的时间分析，可以自动分析出最浪费时间的函数调用或代码段，我们在项目的后期拿到这个工具，并整理出了完整的需要优化的函数清单。
总结一下：应该尽早采用高质量的Debug工具，这可以节约很多时间。
3.inline的优缺点
通过把大量函数改写为inline函数，大约带来2%不到的性能提高。
但是inline函数常常带来莫名其妙的BUG，且给调试带来困难。
4.代码级别优化带来多少性能提高？
除了改写VU汇编外，其他手段带来的提高大约不超过5%。
5.奇怪BUG总结
a.出现死机BUG，为了查出死机位置，在某处添加printf，然而死机却因此消失了。
事实证明大部分是由于数组访问越界引起，推荐在该处上方的代码中寻找问题。
b.程序指针莫名其妙地跳转到不相关的函数中。（比如从足球的代码跳到保龄球）
这是函数调用堆栈破坏导致的，其原因常常是一些有BUG的数学函数（比如某函数未考虑0）。
<四> 其他小建议：
1.关于Schedule
作为个人的建议，我感觉Schedule的制定非常不合理：
a.工作的条目和工作量完全考虑不足，实际做了才发现很多难点和新的工作。
b.时间定得极为短，而且每项工作需要多少时间，几乎是强迫性填写，几乎没有任何参考价值。
c.虽然Schedule分配了每个人的工作，但没有遵守的情况较多。
d.不应该把加班时间预先计算在开发时间内。
e.没有充分考虑程序人员与美术人员的协调。
2.关于库和文档
作为个人的建议，我感觉应该认真总结出库和文档。
例如我们此次PS2底层出现非常多问题，难以想象每次开始新项目都去考虑那些基本的功能是否出现BUG，甚至重写底层。我认为要积累一个BUG很少的库，尤其是PS2，这有很多好处。
而且为了作为以后开发的参考，以及预防开发人员流失的损失，我认为良好的文档和总结也是必要的。
以上看似浪费时间，其实却是节约时间，特别是随着项目规模的增大，更是如此。
