摘要: 1．本文的创新点本文针对实时植物绘制提出了一种新的环境光遮挡算法的框架， 此方法利用植物器官分布成簇的几何特性，将植物器官进行聚类，将环境光遮挡问题分解为类间和类内两种环境光遮挡问题来解决，实现了分而治之的方法。将植物器官聚成有限的几个类即可得到满意的效果，在类别小的情况下，本文的计算复杂度为O(n)，而传统方法的计算复杂度为O(n2)。 实验表明，对于含有巨量数据的植物，使用本文的方法预处理时间只有几十秒，而已有的的方法需要几十小时至上万小时。并且本文提出的方法通过调节参数，可以灵活实现不用的环境光遮挡效果。2．实现方法本文中的方法在Windows XP操作系统下实现，开发环境是Visual C++ .net 2005,硬件平台是PC机，配置为Pentium?4 2.8GHz CPU, 512M内存。所有的预处理工作都由CPU完成，在实时渲染过程中，环境光遮挡值由顶点着色器(Vertex Shader)作为参数传送到GPU。在实现过程中，我们还应用了高动态范围图像渲染(High Dynamic Range Image Rendering)来加强环境光遮挡绘制效果。本文中的环境光遮挡计算框架包含三个步骤：植物器官聚类，类内环境光遮挡计算和类间环境光遮挡计算。我们利用植物结构的特点来克服计算的复杂性。从对植物几何形态和拓扑结构的观察我们做如下假设：一株树中的器官生长经常会出现成簇的情形，借用模式识别的术语，我们将每一簇称为一类。每一个植物器官不仅会被本类内的其他器官遮挡，而且会被其他类内的器官遮挡。因此我们可以区别定义两种不同的环境光遮挡信息：类间环境光遮挡值和类内环境光遮挡值。我们的环境光遮挡算法框架的步骤为： 1． 首先，使用树状数据结构将植物的器官进行层次化组织。数据结构的每个叶子节点存储了器官的聚类结果中的一类。 每一类包含了几何上距离相近，拓扑关联的一组植物器官，密集和紧致是聚类的准则。 2． 在第二步，计算每个几何顶点的类内可见值。类内可见值的计算只在同一类中的器官几何对象中进行。 3． 在第三步，计算每个几何顶点的类间可见值。类间可见值的计算需要考虑一类内的顶点和其他类中几何对象之间的关系。最终的合成在实时渲染中进行。类内可见值和类间可见值由顶点着色器(Vertex Shader)作为环境光遮挡参数传送到GPU，通过调节环境光遮挡方程，我们可以实现不同的环境光遮挡效果。我们将本文提出的方法与用GPU实现的标准环境光遮挡方法（称为HAO）做了运行时间的比较。表1是两种方法预处理时间的比较，表2是分类需要的时间。

树种	顶点数	面片数	类内计算时间（秒）	类间计算时间（秒）	HAO计算时间（小时）
细棕榈	132775	69847	0.0183	1.124	2.26
胡桃	703692	402686	0.0954	19.535	72.66
野樱桃	9180007	5534495	1.245	77.629	13696.07

表1 环境光遮挡预处理时间

树种	类个数	分类时间（分种）
细棕榈	3	2.883
胡桃	8	4.166
野樱桃	2	2.430

表2 分类时间
3．结论本文的方法预处理时间即使在没有应用GPU加速的情况下还要比传统方法快很多，即使加上分类时间，本文中的方法也远比HAO方法高效。并且在保证计算效率的前提下，本文中的方法可以产生与传统方法可比的视觉效果。4．本文的主要贡献本文中我们提出并且实现了一种新的环境光遮挡框架，此算法适用于具有大量随机分布的器官的植物。这种方法对处理具有不同拓扑结构以及形态的植物都很有效。本文中的方法简单，流程清晰，比以往的方法更容易实现。此方法的主要贡献在于预处理过程的效率很高，对于包含大量器官的植物也能在有限的时间内完成。此方法的贡献还包括提出了新的植物器官聚类方法，并且可以通过调节几个参数实现多种环境光遮挡效果。本文中的方法可以推广到其他类型对象的环境光遮挡绘制，例如粒子系统，包含许多流星的场景等等。