一种动画电影虚拟三维场景的空间加速结构及其创建与更新方法

摘要

本发明公开一种动画电影虚拟三维场景的空间加速结构及其创建与更新方法，属于三维动画电影渲染技术领域。KD-tree、BVH、均匀栅格等现有空间加速结构及其创建与更新方法存在的主要问题是，要求每帧全部重建空间加速结构，导致空间加速结构的维护开销巨大。本发明提供的空间加速结构及其创建与更新方法将动画电影虚拟三维场景的几何对象分为静态几何对象和动态几何对象，并分别创建其图元的空间加速结构，通过指针将它们链接起来，每帧只需更新发生变化的动态几何对象的图元的加速结构，使得空间加速结构的维护开销能减少60％～80％。本发明主要应用于三维动画电影渲染领域。

说明书

技术领域

本发明涉及三维动画电影渲染技术，具体是一种动画电影虚拟三维场景的空间加速结构及其创建与更新方法，使用该空间加速结构及其创建与更新方法可以减少利用光线跟踪软件渲染三维动画电影的时间。

背景技术

三维动画电影作为近年来新兴的计算机艺术，发展势头非常迅猛，已经在许多行业得到了广泛的应用。为了在三维动画电影中获得很好的真实感，必须使用能实现全局光照效果的渲染方法。全局光照的基本任务是使用预先组织好的三维场景生成具有完全真实感的图像。为了达到这一目的，必须模拟光线在场景中进行传播所发生的各种物理现象(即进行光线跟踪计算)，如多次的反射、阴影、焦散等。这不仅需要对场景中各种物体的几何特性和材质属性的精确描述，还需要求解计算多次反射、折射带来的无限维积分的问题。这使得全局光照计算成为一个极度复杂的问题，全局光照计算的复杂性使得渲染一幅真实感图像需要很长的时间。

对动画电影虚拟三维场景进行有效的组织，创建高效的空间加速结构，可以快速排除与光线不相交的图元，使得光线与图元之间的求交效率大大提高，从而加快了光线跟踪计算的速度。光线跟踪中常用的空间加速结构包括：KD-tree、BVH、均匀栅格等。一般来说，KD-tree的加速性能最高。动画电影虚拟三维场景属于动态场景，场景中的某些几何对象会随时间运动、变形、出现或者消失。如果直接在动画电影虚拟三维场景中使用上述空间加速结构进行光线跟踪，则需要对空间加速结构进行逐帧全部重建，否则会导致空间加速结构的质量显著降低甚至出现错误。对于大型动画电影虚拟三维场景来说，创建高效的场景空间加速结构非常耗时。在使用光线跟踪软件渲染三维动画时，逐帧全部重建场景的空间加速结构将会导致三维动画的总渲染时间大大增加。所以避免逐帧全部重建场景的空间加速结构是加快三维动画渲染速度的一条有效途径。

发明内容

本发明的目的在于提供一种动画电影虚拟三维场景的空间加速结构及其创建与更新方法，每帧仅重建和更新动画电影虚拟三维场景中发生变化的几何对象(在本发明中称为动态几何对象)的图元的空间加速结构，其他几何对象的图元的空间加速结构保持不变，避免了逐帧全部重建动画电影虚拟三维场景的空间加速结构，减少了三维动画的总渲染时间。在本发明中，将动态几何对象的图元称为动态图元，将静态几何对象的图元称为静态图元。

本发明提供一种动画电影虚拟三维场景的空间加速结构(ST00)，该空间加速结构(ST00)为树形拓扑，如图3所示，它的每个非叶子结点(A001)的数据结构定义如图1所示，它的每个叶子结点(A002)的数据结构定义如图2所示。图3中的结点(301)为图1所示的非叶子结点，图3中的结点(302)为图2所示的叶子结点。

如图1所示，所述的非叶子结点(A001)包含一个静态图元包围盒变量(101)(变量名为staticAABB)，一个动态图元包围盒变量(102)(变量名为dynamicAABB)，一个指向左孩子结点的指针变量(103)(变量名为leftChildPtr)，一个指向右孩子结点的指针变量(104)(变量名为rightChildPtr)，一个指向动态图元加速结构(A003)的指针变量(105)(变量名为dynamicOAccerStruPtr)。

如图2所示，所述的叶子结点(A002)包含一个静态图元包围盒变量(201)(变量名为staticAABB)，一个动态图元包围盒变量(202)(变量名为dynamicAABB)，一个指向动态图元加速结构(A003)的指针变量(203)(变量名为dynamicOAccerStruPtr)，一个静态图元列表变量(204)(变量名为staticPrimitiveList)。

本发明中所述的动态图元加速结构(A003)为树形拓扑，它的每个非叶子结点(A004)的数据结构如图4所示，它的每个叶子结点(A005)的数据结构定义如图5所示。图3中的结点(303)和结点(305)为图4所示的非叶子结点，图3中的结点(304)为图5所示的叶子结点。

如图4所示，所述的非叶子结点(A004)包含一个动态图元包围盒变量(401)(变量名为dynamicAABB)，一个指向左孩子结点的指针变量(402)(变量名为leftChildPtr)，一个指向右孩子结点的指针变量(403)(变量名为rightChildPtr)。

如图5所示，所述的叶子结点(A005)包含一个动态图元包围盒变量(501)(变量名为dynamicAABB)，一个动态图元列表变量(502)(变量名为dynamicPrimitiveList)。

本发明提供一种动画电影虚拟三维场景的空间加速结构(ST00)的创建方法，所述方法包括以下步骤：

步骤(S101)、根据动画电影虚拟三维场景的场景图以及场景几何对象随时间的运动、变形、出现、消失等控制信息，将所有不随时间发生运动、变形、出现、消失等变化的场景几何对象标记为静态几何对象(A006)，将其他的场景几何对象标记为动态几何对象(A007)；

步骤(S102)、将所有静态几何对象(A006)当作一个静态场景，并将所有静态几何对象(A006)的图元存放在一个静态图元列表(A008)中；

步骤(S103)、将所有动态几何对象(A007)存放在一个动态几何对象列表(306)中，为每个动态几何对象(A007)创建一个动态图元列表并进行关联，再将每个动态几何对象的图元存放在与之关联的动态图元列表中；

步骤(S104)、对静态图元列表(A008)中的所有图元，创建表面积启发KD-tree空间加速结构(A009)；

步骤(S105)、遍历KD-tree空间加速结构(A009)：(a)对于KD-tree空间加速结构(A009)中的每个非叶子结点N_i，创建一个图1所示的非叶子结点N₁，将N_i的包围盒赋值给N₁的staticAABB变量，将N₁的dynamicAABB变量的长、宽、高分量均赋值为-1，将N₁的dynamicOAccerStruPtr变量赋值为空指针null；(b)对于KD-tree空间加速结构(A009)的每个叶子结点N_l，创建一个图2所示的叶子结点N₀，将N_l的包围盒赋值给N₀的staticAABB变量，将N_l的图元列表变量赋值给N₀的staticPrimitiveList变量，将N₀的dynamicAABB变量的长、宽、高分量均赋值为-1，将N₀的dynamicOAccerStruPtr变量赋值为空指针null；(c)根据KD-tree空间加速结构(A009)中各结点的拓扑关系，设置与KD-tree空间加速结构(A009)的各非叶子结点一一对应的所有新创建的图1所示的非叶子结点的指向左孩子结点的指针变量(103)的值和指向右孩子结点的指针变量(104)的值，最终得到图3所示的由圆形结点组成的树状结构(A010)，树状结构(A010)的每个非叶子结点具有如图1所示的数据结构，树状结构(A010)的每个叶子结点具有如图2所示的数据结构。

步骤(S106)、计算动态几何对象列表(306)中的每个动态几何对象(A011)的包围盒；对于每个动态几何对象(A011)，遍历树状结构(A010)，记录遍历到的满足如下条件的结点N_c：

条件(A012)：当结点N_c为非叶子结点时，结点N_c的静态图元包围盒变量(101)表示的包围盒能够完全包围动态几何对象(A011)的包围盒，当结点N_c为叶子结点时，结点N_c的静态图元包围盒变量(201)表示的包围盒能够完全包围动态几何对象(A011)的包围盒；

当找到满足条件(A012)的结点N_c后，则停止遍历，并把结点N_c加入一个集合(A013)中，再将结点N_c与动态几何对象(A011)相关联；如果遍历完树状结构(A010)的所有结点后，未找到满足条件(A012)的结点，则将树状结构(A010)的根结点加入集合(A013)中，并将树状结构(A010)的根结点与动态几何对象(A011)相关联。

步骤(S107)、对集合(A013)中的每个结点N_s，找出与之关联的所有动态几何对象；根据与这些动态几何对象相关联的动态图元列表，找到这些动态几何对象的所有图元，创建这些图元的表面积启发KD-tree空间加速结构(A014)，并将其根结点N_root的地址赋值给结点N_s的dynamicOAccerStruPtr变量(即结点N_s的dynamicOAccerStruPtr变量指向结点N_root，图3中的结点(307)和结点(308)就是这种情形)，将结点N_root的包围盒赋值给结点N_s的dynamicAABB变量。

经过以上步骤就可以创建出图3所示的动画电影虚拟三维场景的空间加速结构。

本发明提供一种动画电影虚拟三维场景的空间加速结构(ST00)的更新方法，所述方法包括以下步骤：

步骤(S201)、根据动画电影虚拟三维场景的场景图以及场景几何对象随时间的运动、变形、出现、消失等控制信息，判断动态几何对象列表(306)中的每个动态几何对象(B001)在当前帧中是否发生变化，如果发生了变化，则将该动态几何对象(B001)标记为“发生变化”，否则，将该动态几何对象(B001)标记为“未发生变化”；

步骤(S202)、对每个被标记为“发生变化”的动态几何对象(B001)，首先找出与之关联的树状结构(A010)中的结点，解除该结点与该动态几何对象(B001)的关联，并将该结点加入集合(B002)中；

步骤(S203)、对每个被标记为“发生变化”的动态几何对象(B001)，遍历树状结构(A010)，记录遍历到的满足如下条件的结点N_d：

条件(B003)：当结点N_d为非叶子结点时，结点N_d的静态图元包围盒变量(101)表示的包围盒能够完全包围动态几何对象(B001)的包围盒，当结点N_d为叶子结点时，结点N_d的静态图元包围盒变量(201)表示的包围盒能够完全包围动态几何对象(B001)的包围盒；

当找到满足条件(B003)的结点N_d后，则停止遍历，并把结点N_d加入一个集合(B002)中，再将结点N_d与动态几何对象(B001)相关联；如果遍历完树状结构(A010)的所有结点后，未找到满足条件(B003)的结点，则将树状结构(A010)的根结点加入集合(B002)中，并将树状结构(A010)的根结点与动态几何对象(B001)相关联。

步骤(S204)、对集合(B002)中的每个结点N_t，找出与之关联的所有动态几何对象；根据与这些动态几何对象相关联的动态图元列表，找到这些动态几何对象的所有图元，创建这些图元的表面积启发KD-tree空间加速结构(B004)，并将其根结点N_r的地址赋值给结点N_t的dynamicOAccerStruPtr变量(即结点N_t的dynamicOAccerStruPtr变量指向结点N_r，图3中的结点(307)和结点(308)就是这种情形)，将结点N_r的包围盒赋值给结点N_t的dynamicAABB变量。

执行以上步骤，可以实现在每帧中更新动画电影虚拟三维场景的空间加速结构，从而保证动画电影虚拟三维场景的空间加速结构的质量。

有益效果

本发明提供了一种动画电影虚拟三维场景的空间加速结构及其创建与更新方法。本发明中所述的空间加速结构的优点在于：在各帧之间只需要更新发生变化的动态几何对象的图元的空间加速结构，其他几何对象的图元的空间加速结构保持不变，避免了逐帧全部重建场景的空间加速结构带来的时间开销；本发明所述的方法对静态场景创建表面积启发KD-tree空间加速结构，保证了静态场景部分的光线跟踪的效率；本发明所述方法对包含于同一静态图元包围盒内的动态几何对象的图元创建表面积启发KD-tree空间加速结构，并且链接到树状结构(A010)的相应结点上，使得各帧间动态几何对象的图元的空间加速结构的更新变得灵活、有效，在渲染动画电影虚拟三维场景时，空间加速结构的维护开销能减少60％～80％。

附图说明

图1是动画电影虚拟三维场景的空间加速结构的非叶子结点的数据结构；图2是动画电影虚拟三维场景的空间加速结构的叶子结点的数据结构；图3是动画电影虚拟三维场景的空间加速结构的拓扑结构；图4动态图元加速结构的非叶子结点的数据结构；图5是动态图元加速结构的叶子结点的数据结构。

具体实施方式

为了使本发明的特征和优点更加清楚明白，下面结合具体实施例对本发明作进一步的描述。

考虑人行走在大街上的动画电影虚拟三维场景，场景中的街道、建筑物、路灯、天空、树木、花草等几何对象属于静态几何对象，场景中的人、车等几何对象属于动态几何对象。执行以下步骤可以完成本发明提供的动画电影虚拟三维场景的空间加速结构的创建：

步骤(A1)、首先根据动画电影虚拟三维场景的场景图以及几何对象随时间的运动、变形、出现、消失等控制信息将所有场景几何对象分类为静态几何对象和动态几何对象，把所有静态几何对象的图元存放在静态图元列表中，把所有动态几何对象存放在动态几何对象列表(Q001)中，为每个动态几何对象创建一个动态图元列表并进行关联，再将每个动态几何对象的图元存放在与之关联的动态图元列表中。

步骤(A2)、对静态图元列表中的所有图元，创建表面积启发KD-tree空间加速结构(Z001)；遍历KD-tree空间加速结构(Z001)：(a)对于KD-tree空间加速结构(Z001)中的每个非叶子结点N_i，创建一个图1所示的非叶子结点N₁，将N_i的包围盒赋值给N₁的staticAABB变量，将N₁的dynamicAABB变量的长、宽、高分量均赋值为-1，将N₁的dynamicOAccerStruPtr变量赋值为空指针null；(b)对于KD-tree空间加速结构(Z001)的每个叶子结点N_l，创建一个图2所示的叶子结点N₀，将N_l的包围盒赋值给N₀的staticAABB变量，将N_l的图元列表变量赋值给N₀的staticPrimitiveList变量，将N₀的dynamicAABB变量的长、宽、高分量均赋值为-1，将N₀的dynamicOAccerStruPtr变量赋值为空指针null；(c)根据KD-tree空间加速结构(Z001)中各结点的拓扑关系，设置与KD-tree空间加速结构(Z001)的各非叶子结点一一对应的所有新创建的图1所示的非叶子结点的指向左孩子结点的指针变量(103)的值和指向右孩子结点的指针变量(104)的值，最终得到图3所示的由圆形结点组成的树状结构(Z002)，树状结构(Z002)的每个非叶子结点具有如图1所示的数据结构，树状结构(Z002)的每个叶子结点具有如图2所示的数据结构。

步骤(A3)、计算动态几何对象列表(Q001)中的每个动态几何对象(Z003)的包围盒；对于每个动态几何对象(Z003)，遍历树状结构(Z002)，记录遍历到的满足如下条件的结点N_c：

条件(Z004)：当N_c为非叶子结点时，N_c的静态图元包围盒变量(101)表示的包围盒能够完全包围动态几何对象(Z003)的包围盒，当N_c为叶子结点时，N_c的静态图元包围盒变量(201)表示的包围盒能够完全包围动态几何对象(Z003)的包围盒；

当找到满足条件(Z004)的结点N_c后，停止遍历，并把N_c加入一个集合(Z005)中，再将N_c与动态几何对象(Z003)相关联；如果遍历完树状结构(Z002)的所有结点后，未找到满足条件(Z004)的结点，则将树状结构(Z002)的根结点加入集合(Z005)中，并将树状结构(Z002)的根结点与动态几何对象(Z003)相关联。

步骤(A4)、对集合(Z005)中的每个结点N_s，找出与之关联的所有动态几何对象，根据与这些动态几何对象相关联的动态图元列表，找到这些动态几何对象的所有图元，创建这些图元的表面积启发KD-tree空间加速结构(Z006)，并将其根结点N_root的地址赋值给Ns的dynamicOAccerStruPtr变量(即N_s的dynamicOAccerStruPtr变量指向N_root，图3中的结点(307)和结点(308)就是这种情形)，将N_root的包围盒赋值给N_s的dynamicAABB变量。

在渲染每帧图像时，执行以下步骤可以完成对本发明的动画电影虚拟三维场景的空间加速结构的更新：

步骤(B1)根据动画电影虚拟三维场景的场景图以及场景几何对象随时间的运动、变形、出现、消失等控制信息，判断动态几何对象列表(Q001)中的每个动态几何对象(Z007)在当前帧中是否发生变化，如果发生了变化，则将该动态几何对象标记为“发生变化”，否则，将该动态几何对象标记为“未发生变化”；

步骤(B2)对每个被标记为“发生变化”的动态几何对象(Z007)，首先找出与之关联的树状结构(Z002)中的结点，解除该结点与该动态几何对象(Z007)的关联，并将该结点加入集合(Z008)中；

步骤(B3)对每个被标记为“发生变化”的动态几何对象(Z007)，执行类似于步骤(A3)中遍历树状结构(Z002)的过程，将找到的结点与该动态几何对象相关联，并将找到的结点加入集合(Z008)中；

步骤(B4)对集合(Z008)中的所有结点，执行类似于步骤(A4)中的过程，完成动画电影虚拟三维场景的空间加速结构的更新。

执行以上步骤，可以实现在每帧中更新动画电影虚拟三维场景的空间加速结构，从而保证动画电影虚拟三维场景的空间加速结构的质量和正确性。