超级并行计算及其基础软件
本年度，我们重点研发了用于众核CPU/GPU异质架构的编程语言SPAP（Same Program for All Processors），并在此基础上研究了众核CPU/GPU异质架构下的基础数据结构如存储可扩展的kd树、包围体层次结构、数据并行的八叉树、线空间层次结构、四维超棱台（hyper-trapezoids）的层次结构、高维矩阵的双聚类结构等，相关成果被收录或发表在ACM Transactions on Graphics（SIGGRAPH 2010）、IEEE Transactions on Visualization and Computer Graphics，Computer Graphics Forum(Eurographics Symposium on Rendering 2010)上，主要包括：
用于众核CPU/GPU异质架构的编程语言SPAP：最新的商业计算系统，如桌面计算机或便携计算机上通常都配备了多核CPU和具有大规模并行计算能力的众核GPU，如果这种异构计算能力能够被充分利用起来，将使这些系统上运行的应用的性能得到数量级的提升，然而现有的并行编程语言或者是专门为CPU或GPU设计的，或者如OpenCL虽然能将代码编译到CPU和GPU上，但程序员常常还是需要为不同处理器开发不同的代码，这是因为各处理器之间处理模式的异构性。我们提出了一种基于容器的用于异构平台的并行编程语言SPAP，通过提供一系列的类似标准模板类（Standard Template Library,STL）的容器，实现了CPU和GPU的行为一致性——程序员可见的SPAP容器行为和串行环境下的对应容器是一致的。这使得可以以类似传统编程的开发模式完成异构平台下的程序开发，这大大缩短了学习时间并简化了编程过程。SPAP同时还提供了各种容器的处理器相关的优化实现，使得同一程序可以在CPU和GPU上实现优化运行。
存储可扩展的kd树和包围体层次结构：kd树和包围体层次结构（Bounding Volume Hierarchy, BVH）是光线跟踪、碰撞检测、物理模拟等应用中非常重要的基础加速结构，现有的GPU并行架构下的kd树和包围体层次结构为了尽可能利用并行计算能力几乎都是基于广度优先搜索（Breadth-First Search, BFS）的顺序构造，这造成了大量的存储开销，算法的可伸缩性通常受制于GPU的存储器容量，我们提出了用一种新的部分广度优先搜索（Partial BFS），在尽可能利用并行性的同时将存储可扩展性提高了一个数量级。
数据并行的八叉树：我们提出了一种新的在并行处理架构下的八叉树构造方法，能够实时为复杂空间数据，如点云，构造层次加速结构，并立利用按层的遍历来实现并行度的最大化，这使得人们第一次可以在实时应用中完成从点云到网格的重建，比现有串行方法速度高出两个数量级以上。我们的方法可以在运行时完成从动态点云数据的表面重建，并可用于实时的流体仿真计算。
线空间层次结构：带有散射介质（participating media）的场景绘制是计算机图形学中一个极具挑战性的问题，尤其是当要考虑复杂遮挡和光线在场景中的弹射的情况下，我们提出了一种新的建立在光线和视线的6维Plücker坐标空间的层次结构，称之为线空间层次。在这一空间中，寻找最近直线的操作就变成了寻找面的最近点的操作，并可以用上述线空间层次结构来大大加速。这就提高了散射介质绘制中最为费时的收集各个光线上的光能的计算的效率。在同样的绘制指向下，我们提出的新方法可比现有最有效的方法的速度提高两个数量级，而消耗的空间则要降低一个数量级。
四维超棱台层次结构：在高质量渲染领域，微多边形的光线跟踪一直是一个重要的性能瓶颈。我们提出了一种基于四维超棱台的包围体层次结构，投影到三维空间中就是有朝向的包围盒（oriented bounding box）。这一数据结构可以用来在GPU上实现高效的微多边形焦距模糊和运动模糊效果。我们第一次证明了在微多边形构成的场景中光线跟踪可以比光栅化更为高效，这打破了人们一直以来对这两种微多边形采样方法的看法。
高维矩阵的双聚类结构：预计算光能传输是近年来取得很大成功的复杂光源下场景绘制的重要算法，现有的全频预计算光能传输受制于光能传输矩阵的巨大规模，往往可伸缩性不强，我们提出了一种基于高维光能传输矩阵双聚类（biclustering）的压缩方法，能够利用光能传输矩阵固有的数据相关性实现高效的压缩，从而能以交互的绘制速率在表现出以前从未在交互式应用中出现过的全频环境光照下的表面细节。
