第３０卷第５期 ２０１０年５月 计算机应用 Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ Ｖ０ｌ＿３Ｏ Ｎｏ．５ Ｍａｙ ２０１０ 文章编号：１００１—９０８１（２０１０）０５—１３９８—０４ 基于ＧＰＵ粒子系统的大规模场景高效雨雪实时模拟 文治中 ，刘直芳 ，李 纲 ，粱（ｗｚｚ＿３８１０２４＠１６３．ｃｏｍ） 威 （１．四川大学计算机学院，成都６１００６５；２．四川大学视觉合成图形图像技术国防重点学科实验室，成都６１００６５） 摘要：粒子系统实现的雨雪效果能有效增强三维场景的真实感，传统基于中央处理器（ＣＰＵ）运算模拟的粒子系 统占用了大量ＣＰＵ运算时间，难以达到实时模拟的要求。为此提出了一种基于图形处理器的（ＧＰＵ）运算的粒子系统 来模拟的雨雪场景。该方法通过在ＧＰＵ中重复使用消亡粒子在视点坐标系内生成新粒子，并在几何着色器中将粒子 的点坐标转换为矩形坐标，将ＣＰＵ从复杂庞大的几何运算中解放出来，从而大幅增加了场景绘制的微粒数，使雨雪场 景模拟的实时性和逼真度得到增强。 关键词：图形处理器；粒子系统；视点坐标系；几何着色器；雨雪场景 中图分类号：ＴＰ３９１．９ 文献标志码：Ａ Ｒｅａｌｔｉｍｅ ｓｉｍｕｌａｔｉｏｎ ｏｆ ｒａｉｎ ａｎｄ ｓｎｏｗ ｉｎ ｌａｒｇｅ－ｓｃａｌｅ ｓｃｅｎｅ ｂａｓｅｄ ｏｎ ＧＰＵ ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ ＷＥＮ Ｚｈｉ．ｚｈｏｎｇ ，ＬＩＵ Ｚｈｉ．ｆａｎｇ 一，ＬＩ Ｇａｎｇ 一，ＬＩＡＮＧ Ｗｅｉ （１．Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｓｗｈｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ Ｓ￣ｈｕａｎ ６１００６５，Ｃｈｉｎａ； ２．Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｆｕｎｄａｍｅｎｔａｌ Ｓｙｎｔｈｅｔｉｃ Ｖｉｓｉｏｎ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｍａｇｅ ｆｏｒ Ｎａｔｉｏｎａｌ Ｄｅｆｅｎｓｅ，Ｓｉｃｈｕａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ Ｓｉｃｈｕａｎ ６１００６５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ ｅｆｆｅｃｔ ｏｆ ｒａｉｎ ａｎｄ ｓｎｏｗ ｓｃｅｎｅｒｙ ｒｅａｌｉｚｅｄ ｂｙ ｍｅａｎｓ ｏｆ ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ ｃａｎ ｂｅ ｇｒｅａｔｌｙ ｅｎｈａｎｃｅｄ．Ｔｒａｄｉｔｉｏｎａｌｌｙ，ｔｈｅ ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ＣＰＵ ｗｉｌｌ ｏｃｃｕｐｙ ａ ｃｏｎｓｉｄｅｒａｂｌｅ ａｍｏｕｎｔ ｏｆ ＣＰＵ ｏｐｅｒａｔｉｏｎ ｔｉｍｅ ＳＯ ｔｈａｔ ｉｔ ｉｓ ｈａｒｄ ｔｏ ｓａｔｉｓｆｙ ｔｈｅ ｎｅｅｄ ｏｆ ｒｅａｈｉｍｅ ｓｉｍｕｌａｔｉｏｎ．Ｔｏ ｒｅｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ，ａ ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ＧＰＵ ｗａｓ ｐｕｔ ｆｏｒｗａｒｄ ｔｏ ｓｉｍｕｌａｔｅ ｒａｉｎ ａｎｄ ｓｎｏｗ ｓｃｅｎｅｒｙ．Ｉｎ ｔｈｉｓ ｓｙｓｔｅｍ，ｄｅａｄ ｔｉｍｅ ｐａｒｔｉｃｌｅｓ ｗｅｒｅ ｒｅｕｓｅｄ ｔｏ ｆｏｒｍ ｎｅｗ ｐａｒｔｉｃｌｅｓ ｉｎ ｔｈｅ ｅｙｅ ｃｏｏｒｄｉｎａｔｅｓ． Ｉｎ ｔｈｅ ｍｅａｎｔｉｍｅ，ｐｏｉｎｔ ｐｏｓｉｔｉｏｎ ｏｆ ｐａｒｔｉｃｌｅｓ ｗａｓ ｔｒａｎｓｆｏｒｍｅｄ ｔｏ ｒｅｃｔａｎｇｌｅ ｐｏｓｉｔｉｏｎ ｉｎ ｔｈｅ Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ，ＳＯ ａｓ ｔｏ ｒｅｌｉｅｖｅ ＣＰＵ ｆｒｏｍ ｔｈｅ ｃｏｍｐｌｅｘ ｖｏｌｕｍｉｎｏｕｓ ｇｅｏｍｅｔｒｙ ｏｐｅｒａｔｉｏｎ．Ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐａｒｔｉｃｌｅｓ ｉｎ ｔｈｅ ｓｃｅｎｅｒｙ ｗａｓ ｌａｒｇｅｌｙ ｉｎｃｒｅａｓｅｄ，ａｎｄ ｔｈｕｓ ｅｎｈａｎｃｉｎｇ ｔｈｅ ｒｅａｈｉｍｅ ｅｆｆｅｃｔ ａｎｄ ｆｉｄｅｌｉｔｙ ｏｆ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：Ｇｒａｐｈｉｃ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ（ＧＰＵ）；ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ；ｖｉｅｗ ｃｏｏｒｄｉｎａｔｅ；ｇｅｏｍｅｔｒｙ ｓｈａｄｅｒ；ｒａｉｎ ａｎｄ ｓｎｏｗ ｓｃｅｎｅ ０ 引言 近年来图形处理器（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ，ＧＰＵ）的并 模拟。 本文提出一种完全基于ＧＰＵ的雨雪粒子模拟系统。由 ＧＰＵ负责粒子运动状态的更新和绘制，而ＣＰＵ只负责初始粒 子的创建。一旦粒子被创建，所有的运算和绘制全部在ＧＰＵ 行及浮点计算能力、数据传输带宽得到迅猛提升，其运算能力 已大大超过ＣＰＵ。许多以前无法在ＣＰＵ上实时计算的算法， 目前在ＧＰＵ已经可以实现。 中完成，从而大大降低了ＣＰＵ和系统总线的负荷，让ＣＰＵ可 以空闲出来做其他仿真运算。同时，本文提出将粒子模拟放 在视点坐标系中进行，这样可以处理任意大规模场景下的雨 雪模拟。同时为了进一步提高ＧＰＵ的模拟效率，使用了现代 Ｒｅｅｖｅｓ在１９８３年所提出使用粒子系统来模拟雨、雪、烟、 火焰、爆炸等由不规则对象构成的实时系统…。雨雪现象的 模拟是粒子系统的一个典型应用。传统的雨雪粒子系统 。 都是通过ＣＰＵ完成，粒子速度、位置等属性的更新都由ＣＰＵ ＧＰＵ所提供的几何着色器（Ｇｅｏｍｅｔｙ Ｓｈａｄｅｒ）来完成粒子的几 ｒ何生成。 负责运算，占用大量ＣＰＵ时间和系统资源。ＣＰＵ完成计算 后，还需通过系统总线将粒子数据传输到ＧＰＵ进行绘制，大 １ 相关背景 本文提出基于ＧＰＵ粒子系统的雨雪绘制算法，充分运用 大增加了总线传输的压力。传统方法中ＣＰＵ的计算能力，系 统总线的带宽都是限制粒子系统效率的瓶颈，系统只能实时 模拟数万个粒子。 利用ＧＰＵ强大的并行浮点运算能力，通过ＧＰＵ可编程 ＧＰＵ的可编程性和强大的运算能力，并通过始终将雨雪粒子 限制在视点坐标系，使得本算法特别适合于大规模场景的雨 雪绘制。为此，先简要介绍粒子系统、ＧＰＵ的可编程技术和 Ｇｅｏｍｅｔｙｒ Ｓｈａｄｅｒ几何生成技术。 １．１粒子系统模型 管线将粒子速度和位置更新等耗时的运算从ＣＰＵ转移到 ＧＰＵ，由ＧＰＵ完成整个粒子系统的模拟和绘制，从而将三维 场景可生成的粒子数目提升至百万级 。 。张汉清等人 利 用ＧＰＵ强大的浮点运算能力，可实现一百万个粒子的实时 收稿日期：２００９—１０—１５；修回日期：２００９—１２—１８。 对于基于粒子系统的雨雪绘制算法来说，每个粒子均包 含出现的位置、生存时问、速度等属性。粒子系统通过对上述 基金项目：国家８６３计划项目（２００７ＡＡ０１Ｚ３２８；２００９ＡＡ０１Ｚ３３２）；国家自然科学基金资助项目（６０８３２０１１）。 作者简介：文治中（１９８３一），男（朝鲜族），四川西昌人，硕士研究生，主要研究方向：虚拟现实、计算机仿真； 刘直芳（１９７４一），女，四川达 州人，副研究员，博士，主要研究方向：图像处理、视频监控、虚拟现实； 李纲（１９７８一），男，四川南充人，博士研究生，主要研究方向：三维绘 制、虚拟现实系统；粱威（１９８６一），女，四川大邑人，硕士研究生，主要研究方向：图像处理、视频监控。 第５期 文治中等：基于ＧＰＵ粒子系统的大规模场景高效雨雪实时模拟 １３９９ 的粒子属性进行实时运算更新来模拟雨、雪的运动。粒子系 统在每帧都需要进行如下运算： １）产生新粒子并生成粒子的初始属性； ２）删除超过生存时间或符合消亡条件的粒子； ３）根据运动规律计算粒子的速度、位置等属性； ４）绘制粒子。 传统的粒子系统将步骤１）～３）交由ＣＰＵ运算，导致 ＣＰＵ负荷过大，即使在ＣＰＵ没有其他负荷的条件下，其最大 而目前在ＧＰＵ中维护一个动态数据结构的开销是相当大的， 从而限制了ＧＰＵ粒子系统的效率。本文提出一种新的粒子 生命周期控制方法，重复利用消亡的粒子来生成新粒子，这便 使得初始粒子一旦生成后，其生命周期为无限长，避免了使用 动态数据结构来维护新粒子的生成和旧粒子的消亡。 ３）粒子在逻辑上只是一个点，对粒子的属性的更新都只 需要对这个点进行即可。但在绘制的时候，粒子是由一个矩 形来表示。以前基于ＧＰＵ的雨雪粒子系统在处理这种表达 可以模拟的粒子数目也只能达到数万。 １．２ ＧＰＵ的可编程技术 在ＧＰＵ中，渲染管线负责将由内存中读取的几何对象 （点、线和多边形）进行一系列的矩阵变换，最后将三维的几 何对象绘制至二维的图像输出端。绘制过程如图１所示。 图１ 固定管线渲染过程 以前的渲染管线不具备可编程性，管线中所有的功能都 被固化到硬件上，用户只能通过一些简单的函数打开或关闭 渲染管线中的某个功能（例如，打开或关闭 混合）。而现代 的图形管线具备了很强的可编程性，用户可完全控制渲染管 线中的几个模块。渲染管线的可编程性极大扩展了ＧＰＵ的 功能，使得将原来由ＣＰＵ承担的运算迁移到ＧＰＵ成为可能。 １．３ Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ几何生成技术 Ｇｅｏｍｅｔｙｒ Ｓｈａｄｅｒ是现代ＧＰＵ对渲染管线的可编程性的 又一次扩展。位于Ｖｅｒｔｅｘ Ｓｈａｄｅｒ和Ｆｒａｇｍｅｎｔ Ｓｈａｄｅｒ之问的 Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ，可在输入顶点的基础上生成新的顶点甚至 新的图元，大大扩展了ＧＰＵ的功能。 由于Ｖｅｒｔｅｘ Ｓｈａｄｅｒ每一次运行只能处理一个顶点数据， 并且每次只能输出一个顶点的结果。在绘制大规模场景时， 几何图形的绘制任务量非常庞大，如果仅仅依靠Ｖｅｒｔｅｘ Ｓｈａｄｅｒ来完成效率较低。Ｇｅｏｍｅｔｙｒ Ｓｈａｄｅ能根据顶点的信息 来批量地处理几何图形，即可对Ｖｅｒｔｅｘ Ｓｈａｄｅｒ输出的顶点数 据进行函数处理，快速批量地产生出新的多边形的顶点数据， 从而将ＣＰＵ从复杂庞大的几何运算中解放出来。大爆炸、粒 子效果、瀑布流水等复杂又关联的场景都可以用Ｇｅｏｍｅｔｙｒ Ｓｈａｄｅｒ很逼真地表现出来。 ２基于ＧＰＵ粒子系统的雨雪绘制 ２．１算法概要 本文提出一个适合于大规模场景的基于ＧＰＵ的雨雪粒 子系统，相比已有的基于ＧＰＵ的粒子系统来说，本文系统的 特点如下所示。 １）传统的粒子系统生成的粒子都生成在世界坐标系中。 这种方法在于经过投影变换后，最后落在视域内的粒子只是 整个场景中粒子的一小部分。这样即使整个粒子系统可以模 拟数百万的粒子，但对用户可见的粒子可能只有数万个。同 时，对于用户不可见的粒子，系统仍然需要在每帧对其属性进 行计算和更新，从而大大浪费了ＣＰＵ／ＧＰＵ的资源。本文提 出将粒子的生成限制在视点坐标系内，凡是生成的粒子都是 可见的粒子，从而大大节约了ＣＰＵ／ＧＰＵ的计算资源。 ２）目前基于ＧＰＵ的粒子系统只是简单的将１．１节中描 述的计算由ＣＰＵ移植到ＧＰＵ中，ＧＰＵ需要负责粒子整个生 命周期的控制，即要负责新粒子的生成和消亡粒子的删除。 方式的不统一时，均采用矩形来表达粒子以适应绘制需要。 这种方法的缺点在于把一个逻辑上只需要一个点表达的粒子 使用矩形的四个顶点来表示，使得在更新粒子的属性时对矩 形的四个顶点都要进行重复的运算，从而大大增加了ＧＰＵ的 计算量。本文通过使用Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ来解决粒子表达不 统一这个问题。粒子在进入Ｖｅｒｔｅｘ Ｓｈａｄｅｒ阶段使用点的表示 方法，在Ｖｅｒｔｅｘ Ｓｈａｄｅｒ中完成粒子属性的更新计算；再通过 Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ来将粒子的点表达转换为矩形表达，最后进 入Ｆｒａｇｍｅｎｔ Ｓｈａｄｅｒ来完成绘制。 ２．２粒子的生成 透视投影决定了观察者所能观察到的视野有限。传统的 基于粒子系统在世界坐标系中生成和更新粒子，造成了极大 的资源浪费。本文将粒子的生成和运动放在视点坐标系内， 使粒子系统中所有的粒子始终可见，避免粒子在不可见区域 内生成和更新所造成的资源浪费。具体实现思想如下。 １）在当前裁剪空间中随机地生成粒子：裁剪空间中任意 一点的坐标可以表示为（ ，Ｙ， ，１），其中 ，Ｙ∈［一１，１］， ∈ ［０，１］。因此只需要在［一１，１］中随机生成 ，Ｙ，在［０，１］中随 机生成ｚ，即可构成一个当前裁剪空间中的一个随机粒子。 ２）将裁剪空间中随机生成的粒子（ ，Ｙ，ｚ，１）通过如下方 程反投影回视点坐标系（ Ｙ ， ，１）： ：Ｍ 其中 为透视投影矩阵的逆矩阵。 粒子首先是在裁剪空间中生成再逆投影回视点坐标系 中，从而保证了生成的粒子在当前视点的投影参数下是可见 的。 粒子的初始位置等属性将作为输入传人ＧＰＵ进行模拟 和绘制。需要注意的是初始粒子的创建是本文实现的粒子系 统中唯一由ＣＰＵ参与的运算，一旦初始粒子被传人ＧＰＵ， ＣＰＵ将不负责处理任何与粒子更新、绘制的相关工作。 ２．３粒子运动的更新 从雨雪粒子的物理运动规律来说，当粒子接近地面时，在 垂直方向将以近似匀速运动的方式下落，因此，可近似地认为 粒子在垂直方向是以匀速下落的方式运动。同时，粒子在下 落过程中，会受到风向（可能随时变化）的影响而偏离垂直下 落的方向。本文将风对粒子的影响看作一个水平方向的受 力。因此，粒子的运动可以看作是由一个垂直方向的匀速运 动和水平方向的变速运动所构成。综上所述，粒子在ｔ 时刻 的位置Ｐ 可以由ｔ 时刻的位置Ｐ 求得： Ｐ ：Ｐ —ｌ＋（ ｄ…＋ ｋ 。 ｄ）（ｔ 一ｔ 一１） （２） 其中 是粒子在垂直方向的下落速度， …ｋ 是在ｋ时刻时风 在水平方向的速度。 式（２）中当前时刻的粒子位置是根据上一个时刻的粒子 计算机应用 位置计算得到的，这就要求在整个粒子模拟过程中保存上一 个时刻粒子的位置，这个在ＣＰＵ中非常容易实现的功能，但 在ＧＰＵ中却需要使用到Ｒｅｎｄｅｒ—Ｔｏ—Ｔｅｘｔｕｒｅ，Ｐｉｘｅｌ Ｂｕｆｆｅｒ等技 第３Ｏ卷 决这个表达不统一的问题。在Ｖｅｒｔｅｘ Ｓｈａｄｅｒ中，主要负责粒 子的更新运行，即根据式（６）来进行计算，这时将粒子作为一 个点来处理。位置更新后的粒子将进入Ｇｅｏｍｅｔｙｒ Ｓｈａｄｅｒ，在 这里完成粒子的几何生成，即将一个点扩展为一个矩形以便 完成绘制。 粒子由点表达向矩形表达的转换也是在视点坐标系下完 成的，以保证生成的粒子矩形始终朝向用户。本文定义如下 术。为了减轻ＧＰＵ的负荷，本文使用了一种近似的方法来更 新粒子的位置，即只根据粒子的初始位置和当前时刻的风速： Ｐ＾＝Ｐ０＋（ ｄ…＋ ｋｉ ｄ）（ 一ｔ０） （３） 使用式（３）避免了对上一个时刻粒子位置的保存，其输 入固定是粒子的初始位置这个静态的数据，其实现效率大大 高于式（２）。在实际应用中，由于大量雨雪粒子的存在以及 两个互相垂直的向量来构成粒子对应的矩形所在的平面： 不断变化的风速的影响，用户觉察不到式（３）带来的误差。 ２．４粒子生命周期的控制 本文提出一种新的粒子生命周期控制方法，其基本思想 是对消亡的粒子进行回收利用，即根据消亡的粒子生成一个 新粒子，避免了在ＧＰＵ上维护一个动态数据结构的开销。 从式（２）和（３）中都可看出，一个粒子运动一段时间后， 即ｔ 足够大时，粒子都会运动至当前的视锥体以外，由一个可 见粒子变成不可见粒子。传统的粒子系统中，认为这个粒子 消亡而需从粒子系统中删除。在本文中不删除这样的粒子， 而是将这个粒子重新更新位置属性，将其变为一个可见粒子 而重新开始一个新的生命周期。 具体算法实现思想为：由于粒子的运动由两个互不干扰 的垂直和水平方向运动构成，而垂直方向粒子是匀速运动，因 此当一个粒子的初始位置产生后，便可以在垂直方向计算得 到如下两个时间（如图２所示）。 １）ｔ ：粒子在当前深度下，由视锥体的最顶端下落到最底 垂 ＋一＋ 端所花的时间，即图２中粒子从Ｔｏｐ位置ｐ 。。下落到Ｂｏｔｔｏｍ位 置Ｐｂｏｔｔ 的时问： ： （４） ｄ… ２）ｔ ：粒子从Ｐ 。 下落到初始位置Ｐ， 所花的时间： ｆ ： 三 （５） Ｖｄｏｗ ｔ 和ｔ 都在粒子生成时由ＣＰＵ负责计算，然后和粒子的 初始位置一起作为输入传递进ＧＰＵ，在其后的整个模拟过程 中不需要进行改变。 将ｔ 和ｔ 和式（３）相结合，就可以得到带有粒子重复利 用的粒子位置更新方程： 一 （ ＋ ）［ｆｒｏｃ（ ） ］ （６） 其中ｆｒａｃ（ａ）函数是取ｎ的小数部分。通过式（６）可以看到， 当粒子运动到 位置时，即ｔ 一ｔ。：ｔ 一ｔ 时，在垂直方向 粒子将又回到Ｐ 的位置，这可以看成是粒子在Ｐ 。 位置消 亡的一刹那，又被重新生成在Ｐ 位置。通过如上的机制，就 实现了消亡粒子的再利用。从式（６）中也可以看到，粒子在整 个模拟过程中的位置由粒子的初始位置就可以计算得到。本 文提出的算法在初始粒子生成后，就可以交由ＧＰＵ完成所有 的模拟，避免了使用高耗费的动态数据结构删除粒子。 ２．５粒子的几何生成 如上所述，粒子在运动更新和绘制时采用的是两种不同 的表达方式。在更新阶段，粒子是使用一个点来进行表示，而 在绘制时，粒子则被表示为一个矩形（不一定是正方形，否则 直接使用ｐｏｉｎｔ ｓｐｒｉｔｅ即可完成表达方式的统一）。 本文通过分别使用Ｖｅｒｔｅｘ Ｓｈａｄｅｒ和Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ来解 ＶＩ＝ ， ： ×（０，０，１） 粒子对应的矩形的四个顶点就可以根据这两个互相垂直 的向量计算得到。例如，对于矩形的左上角点： Ｐ 。 ：Ｐ 一（ Ｓ ＋ Ｓｙ） 其中Ｓ ，Ｓ 是由用户定义的粒子的大小。用相同的方法可以 生成粒子的其他３个顶点。 ｌ ／ｐ ／／ ／／ 擎・ ’粒子初始位量 运 视点 ＼＼ 明 ｒ方 向 —Ｚ 、、 Ｉ ￣ｏｔｔｏ 图２粒子的重复利用 ３ 实验结果 本文方法实验硬件环境为：Ｉｎｔｅｌ Ｐｅｎｔｉｕｍ Ｄｕａｌ—Ｃｏｒｅ Ｅ２１８０ ２．０ ＧＨｚ处理器，４ ＧＢ内存，ＮＶＩＤＩＡ ＧＴＸ２６０显卡，显卡显存 ８９６ ＭＢ，操作系统为Ｗｉｎｄｏｗｓ ＸＰ ＳＰ３，开发工具为 ＶｉｓｕａｌＳｔｕｄｉｏ２００８与ＯｐｅｎＳｃｅｎｅＧｒａｐｈ ２．８．２，运行场景为首都 机场三维场景在２５００×１ ６００的大小绘制。获得实验数据如 表１。 表１ 三维雨雪场景渲染性能比较 从表１数据可知，本文的算法效率大幅领先于基于ＣＰＵ 的粒子系统，基于ＣＰＵ的粒子系统仅能有效渲染（帧率为 １５ ｆ０ｓ）８万左右的粒子，而本文算法也明显优于传统的基于 ＧＰＵ的粒子系统，该算法可在大规模场景内渲染３００万左右 的粒子。程序运行截图如图３所示。 第５期 文治中等：基于ＧＰＵ粒子系统的大规模场景高效雨雪实时模拟 ｌ４０１ 对大规模场景的实时模拟效率显著提升，达到了较好的效果。 本文的方法在视点移动时粒子的运动未考虑视点运动带来的 影响，导致的模拟的效果略显不真实，今后还需进一步改进。 参考文献： ［Ｉ】 ＲＥＥＶＥＳ Ｗ Ｔ．Ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍｓ—ａ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｍｏｄｅｌｉｎｇ ａ ｃｌａｓｓ ｏｆ （ａ）雨效果 （ｂ）雪效果 ｆｕｚｚｙ ｏｂｊｅｃｔｓ【ｊ］．Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，１９８３，１７（３）：３５９—３７６． 谢剑斌，郝建新，蔡宣平，等．基于粒子系统的雨点和雪花降落 模拟生成［Ｊ］．中国图象图形学报，１９９９，４（９）：７３４—７３８． 罗维佳，都金康，谢顺平．基于粒子系统的三维场地降雨实时模 拟【Ｊ］．中国图象图形学报，２００４，９（４）：４９５—５００． ｖａｎ ｄｅｒ ＢＵＲＧ Ｊ．Ｂｕｉｌｄｉｎｇ ａｎ ａｄｖａｎｃｅｄ ｐａｒｔｉｃｌｅ ｓｙｓｔｅｍ［Ｊ］．Ｇａｍｅ Ｄｅｖｅｌｏｐｅｒ Ｍａｇａｚｉｎｅ，２０００，３（２）：４４—５０． （ｃ）雪效果近景 李建明，吴云龙，何荣盛，等．基于粒子系统和ＧＰＵ加速的喷泉 实时仿真［Ｊ】．系统仿真学报，２００９，２１（１０）：３１３９—３１４１． ＬＩＮＤＨＯＬＭ Ｅ．Ａ ｕｓｅｒ—ｐｒｏｇｒａｍｍａｂｌｅ ｖｅｒｔｅｘ ｅｎｇｉｎｅ【Ｃ】／／Ｐｒｏｃｅｅｄ— ｉｎｇｓ ｏｆ ｔｈｅ ２８ｔｈ Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｎｔｅｒ－ ａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００１：１４９—１５８． Ｉ．ＡＴＴＡ Ｌ．Ｇａｍｅ ｄｅｖｅｌｏｐｅｒｓ ｃｏｎｆｅｒｅｎｃｅ：Ｂｕｉｌｄｉｎｇ ａ ｍｉｌｌｉｏｎ ｐａｒｔｉｃｌｅ 图３ 大规模场景实时仿真截图 ４ 结语 本文在ＧＰＵ中重复使用消亡粒子在视点坐标系内生成 ＿ 寸新粒子，通过Ｇｅｏｍｅｔｒｙ Ｓｈａｄｅｒ将粒子的点坐标转换为矩形坐 标进行绘制，提高了ＧＰＵ运算效率，使之能快速批量地绘制 出多边形，进一步将ＣＰＵ从复杂庞大的几何运算中解放出来， （上接第１３３２页） ｓｙｓｔｅｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｇａｍｅ Ｄｅｖｅｌｏｐｅｒｓ Ｃｏｎｆｅｒｅｎｃｅ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ：Ｔｈｉｎｋ Ｓｅｒｖｉｃｅｓ Ｇａｍｅ Ｇｒｏｕｐ．２００４：５４—６Ｏ． 为优先权度量，使得面片的优先权由其确定性度量，而不依赖 原方法的时间复杂度仅在系数上有所区别，因此本文用实验 于其局部信息。同时算法中混淆系数的计算，使得目标面片 的优先权计算与匹配相结合，算法整体框架不同于类似算法， 而总计算量增加的比例不大。实验结果证明了此方法的合理 性，且视觉效果更自然，提高了修复图像的质量。由于算法固 有的贪婪性，以及采样填充的纹理合成方法本身的特点，该类 方法对于遮挡或缺乏自相似性的复杂自然图像的修补仍然遇 到困难，还需要更多的先验知识的约束或者图像结构的其他 描述手段。 参考文献： 『１］ ＣＲＩＭＩＮＩＳＩ Ａ，ＰＲＥＺ Ｐ，ＴＯＹＡＭＡ Ｋ．Ｒｅｇｉｏｎ ｆｉｌｌｉｎｇ ａｎｄ ｏｂｊｅｃｔ ｒｅ－ ｍｏｖａｌ ｂｙ ｅｘｅｍｐｌａｒ—ｂａｓｅｄ ｉｍａｇｅ ｉｎｐａｉｎｔｉｎｇ［Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，２００４，１３（９）：１２００—１２１２． ｍａｇｅ ｒｅｐａｉｒｉｎｇ：Ｒｏｂｕｓｔ ｉｍａｇｅ ｓｙｎｔｈｅｓｉｓ ｂｙ ａ— ［２］ ＪＩＡ Ｊ，ＴＡＮＧ Ｃ—Ｋ．Ｉ数据进一步说明，如表１所示，其中运行时间以分钟为单位。 对比表１中本文方法与Ｃｒｉｍｉｎｉｓｉ算法的运行时间，可算出图 １的Ｃ值为０．８９。在多次实验中发现Ｃ值的范围大约为 ０．８－４）．９，所以本文算法的总计算量比Ｃｒｉｍｉｎｉｓｉ算法大约多 ２０％～３０％，而不是二倍。该实验在ＰＩＶ ２．０ ＧＨｚ ＣＰＵ，２ ＧＢ 内存的ＰＣ机上运行，采用ｃ＃作为开发环境。 ｄａｐｔｉｖｅ ＮＤ ｔｅｎｓｏｒ ｖｏｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ— （ａ）测试图像 （ｂ）Ｃｒｉｍｉｎｉｓｉ算法修复结果 ｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｐｒｅｓｓ，２００３：６４３—６５０． ＤＲＯＲＩ Ｉ，ＣＯＨＥＮ－ＯＲ Ｄ，ＹＥＳＨＵＲＵＮ Ｈ．Ｆｒａｇｍｅｎｔ—ｂａｓｅｄ ｉｍａｇｅ ｃｏｍｐｌｅｔｉｏｎ［Ｊ］．ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｇｒａｐｈｉｃｓ，２００３，２２（３）：３０３ —３１２． ＳＵＮ ＪＩＡＮ，ＹＵＡＮ ＬＵ，ＪＩＡ ＪＩＡＹＡ，ｅｔ ａ１．Ｉｍａｇｅ ｃｏｍｐｌｅｔｉｏｎ ｗｉｔｈ ｓｔｒｕｃｔｕｒｅ ｐｒｏｐａｇａｔｉｏｎ【Ｃ］／／ＡＣＭ ＳＩＧＧＲＡＰＨ ２００５：Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ．Ｎｅｗ （ｃ）Ｈａｙｓ算法修复结果 （ｄ）本文算法修复结果 Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００５：８６ｌ一８６８． 图２图像２的修复效果比较 表１ Ｃｒｉｍｉｎｉｓｉ算法与本文方法运行时间比较 ＨＡＹＳ Ｊ，ＥＦＲＯＳ Ａ Ａ．Ｓｃｅｎｅ ｃｏｍｐｌｅｔｉｏｎ ｕｓｉｎｇ ｍｉｌｌｉｏｎｓ ｏｆ ｐｈｏｔｏ－ ｒａｐｈｓ［Ｃ］／／ＡＣＭ ＳＩＧＧＲＡＰＨ ２００７：Ｉｎｔｅｒｇｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００７：４． 图像像素个数 图１ ８００×６００ 图２ ８００×６００ １ ２６０ ８１５５ 运 斋高 ｉ １ ５４１ １０４５５ ＫＯＭＯＤＡＫＩＳ Ｎ．Ｉｍａｇｅ ｃｏｍｐｌｅｔｉｏｎ ｕｓｉｎｇ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ【Ｃ］／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００６ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ－ ｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍ— ｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００６：４４２—４５２． ４ 结语 基于以Ｃｒｉｍｉｎｉｓｉ算法为代表的算法的优势与不足，本文 掘弃使用轮廓点附近的信息定义优先权的方法，提出一种新 的思路，以源区域中“有且只有一个”面片与目标面片相似作 ＺＨＡＮＧ ＹＵＮＪＵＮ，ＸＩＡＯ ＪＩＡＮＧＪＩＡＮ，ＳＨＡＨ Ｍ．Ｒｅｇｉｏｎ ｃｏｍｐｌｅ・ ｔｉｏｎ ｉｎ ａ ｓｉｎｇｌｅ ｉｍａｇｅ【Ｃ／ＯＬ］／／ＥＵＲＯＧＲＡＰＨＩＣＳ ２００４．Ｇｒｅｎｏ— ｂｌｅ，Ｆｒａｎｃｅ：［Ｓ．ｎ．］，２００４【２００９一Ｏ８—２２】．ｈｔｔｐ：／／ｅｉｔｅｓｅｅｒｘ． ｉｓｔ．ｐｓｕ．ｅｄｕ／ｖｉｅｗｄｏｃ／ｄｏｗｎｌｏａｄ？ｄｏｉ＝１０．１．１．９．４６２６＆ｒｅｐ： ｒｅｐｌ＆ｔｙｐｅ：ｐｄｆ．