用于图形处理中的阴影光线的树遍历的开始节点确定

摘要

至少一个处理器可将场景的多个图元组织在分层数据结构中，其中多个包围体与所述分层数据结构的多个节点相关联。所述至少一个处理器可将所述多个包围体中的每一者的表示光栅化到存储器中的离屏呈现目标。所述至少一个处理器可至少部分基于所述离屏呈现目标中映射到所述场景中的光线的像素而将与所述像素相关联的所述分层数据结构的非根节点确定为开始节点，以开始所述分层数据结构的遍历。所述至少一个处理器可从所述开始节点开始遍历所述分层数据结构，以确定所述场景中的所述光线是否与所述多个图元中的一者相交。

说明书

技术领域

本公开涉及图形处理，包含遍历分层数据结构以确定用于阴影光线追踪的光线-图元相交。

背景技术

在计算机图形中，阴影呈现是基于场景的特定位置是否由光源照射而将阴影添加到三维(3D)场景的技术。图形处理单元(GPU)可通过从3D场景的特定位置朝向光源发出称为阴影光线的向量来对所述位置执行此阴影呈现。如果GPU确定阴影光线与场景几何形状中的图元相交，则GPU可确定源位置处于阴影中且不由光源照射。

为了加速寻找阴影光线-图元相交的过程，GPU可将3D场景的场景几何形状布置在分层地分组场景图元(例如，三角形)的加速数据结构(ADS)中。GPU可通过对场景图元的层次执行阴影光线相交测试而以递归方式遍历ADS，从而确定阴影光线与场景的图元相交。如果GPU基于ADS的遍历确定从特定位置发出的阴影光线与图元相交，则GPU可确定特定位置由至少图元遮蔽光源。

发明内容

在一个方面中，本公开涉及一种方法。所述方法包含通过至少一个处理器将场景的多个图元组织在分层数据结构中，其中多个包围体与分层数据结构的多个节点相关联。所述方法进一步包含通过至少一个处理器将多个包围体中的每一者的表示光栅化到离屏呈现目标。所述方法进一步包含通过至少一个处理器并至少部分基于与离屏呈现目标中的第一光线相交的像素，将与像素相关联的分层数据结构的非根节点确定为开始节点以开始分层数据结构的遍历。所述方法进一步包含通过至少一个处理器从开始节点开始遍历分层数据结构，以确定场景中的第二光线是否与多个图元中的一者相交。

在另一方面中，本公开涉及一种经配置以处理图形数据的设备。所述设备包含存储器。所述设备进一步包含至少一个处理器，其经配置以：将场景的多个图元组织在分层数据结构中，其中多个包围体与所述分层数据结构的多个节点相关联；将所述多个包围体中的每一者的表示光栅化到存储器中的离屏呈现目标；至少部分基于与所述离屏呈现目标中的第一光线相交的像素，将与所述像素相关联的分层数据结构的非根节点确定为开始节点以开始所述分层数据结构的遍历；及从所述开始节点开始遍历所述分层数据结构，以确定所述场景中的第二光线是否与所述多个图元中的一者相交。

在另一方面中，本公开涉及一种设备。所述设备包含用于将场景的多个图元组织在分层数据结构中的装置，其中多个包围体与所述分层数据结构的多个节点相关联。所述设备进一步包含用于将多个包围体中的每一者的表示光栅化到离屏呈现目标的装置。所述设备进一步包含用于至少部分基于与离屏呈现目标中的第一光线相交的像素，将与所述像素相关联的分层数据结构的非根节点确定为开始节点以开始所述分层数据结构的遍历的装置。所述设备进一步包含用于从开始节点开始遍历分层数据结构，以确定场景中的第二光线是否与多个图元中的一者相交的装置。

在另一方面中，本公开涉及一种存储指令的计算机可读存储媒体。所述指令在执行时致使一或多个可编程处理器：将场景的多个图元组织在分层数据结构中，其中多个包围体与所述分层数据结构的多个节点相关联；将所述多个包围体中的每一者的表示光栅化到存储器中的离屏呈现目标；至少部分基于与所述离屏呈现目标中的第一光线相交的像素，将与所述像素相关联的分层数据结构的非根节点确定为开始节点以开始所述分层数据结构的遍历；及从所述开始节点开始遍历所述分层数据结构，以确定所述场景中的第二光线是否与所述多个图元中的一者相交。

在附图及以下描述中阐述本公开的一或多个方面的细节。本公开的其它特征、目标及优点将从所述描述及图式以及权利要求书中显而易见。

附图说明

图1是说明可经配置以实施本公开的一或多个方面的实例计算装置的框图。

图2是更详细地说明图1的CPU、GPU及系统存储器的实例实施方案的框图。

图3是说明GPU可对其执行阴影光线追踪的实例图形场景及图形场景到包围体中的实例划分的概念图。

图4说明具有与图3中所示的实例包围体及图元相关联的节点的实例分层数据结构。

图5是说明光栅化到实例离屏呈现目标的包围体的实例表示的框图。

图6是说明用于确定用于遍历实例分层树状结构以发现阴影光线-图元相交的开始节点的实例过程的流程图。

具体实施方式

一般来说，本公开描述用于GPU通过确定朝向场景的光源的阴影光线是否与布置在ADS等分层数据结构中的图元相交来更有效地执行图形场景的阴影呈现。代替从根节点遍历分层数据结构，GPU可替代地从根节点以外的节点开始分层数据结构的遍历，由此减少GPU可执行的光线相交测试的次数。GPU可通过利用来自其图形处理管线的着色器单元将与分层数据结构的内节点及叶节点相关联的包围体的子集光栅化到离屏呈现目标，确定从其开始遍历的分层数据结构的非根节点。GPU可从离屏呈现目标确定从其开始分层数据结构的遍历的内部非根节点，由此减少GPU可执行以遍历分层数据结构的阴影光线相交测试的次数。因为与执行光线相交测试相比，光栅化到离屏呈现目标的计算成本相对较低，所以GPU可通过光栅化到离屏呈现目标及与从根节点遍历分层数据结构相比，确定从其开始分层数据结构的遍历的内部非根节点来实现阴影呈现性能的显著提高。

根据本公开的方面，GPU可将场景的多个图元组织在分层数据结构中，其中多个包围体与所述分层数据结构的多个节点相关联。GPU可进一步将多个包围体中的每一者的表示光栅化到存储器中的离屏呈现目标。GPU可至少部分基于与离屏呈现目标中的第一光线相交的像素，进一步将与所述像素相关联的分层数据结构的非根节点确定为开始节点以开始所述分层数据结构的遍历。GPU可进一步从开始节点开始遍历分层数据结构，以确定场景中的第二光线是否与多个图元中的一者相交。

图1是说明可经配置以实施本公开的一或多个方面的实例计算装置的框图。如图1中所示，装置2可为计算装置，包含但不限于，视频装置、媒体播放器、机顶盒、移动电话及所谓的智能电话等无线手持机、个人数字助理(PDA)、台式计算机、膝上型计算机、游戏控制台、视频会议单元、平板计算机、家用电器、工业电器、查询一体机等。在图1的实例中，装置2可包含中央处理单元(CPU)6、系统存储器10及GPU 12。装置2还可包含显示处理器14、收发器模块3、用户接口4及显示器8。收发器模块3及显示处理器14两者可为与CPU 6及/或GPU12相同的集成电路(IC)的一部分，两者可在包含CPU 6及/或GPU 12的一或多个IC的外部，或可形成于在包含CPU 6及/或GPU 12的IC外部的IC中。

为清楚起见，装置2可包含图1中未展示的额外模块或单元。举例来说，装置2可包含扬声器及麦克风(其均未在图1中展示)以在装置2为移动无线电话或扬声器(其中装置2为媒体播放器)的实例中实现电话通信。装置2还可包含摄像机。此外，装置2中所展示的各种模块及单元可不必在装置2的每个实例中。举例来说，在其中装置2是台式计算机或经装备以与外部用户接口或显示器介接的其它装置的实例中，用户接口4及显示器8可在装置2的外部。

用户接口4的实例包含但不限于轨迹球、鼠标、键盘及其它类型的输入装置。用户接口4还可为触摸屏并且可作为显示器8的一部分并入。收发器模块3可包含允许装置2与另一装置或网络之间的无线或有线通信的电路。收发器模块3可包含调制器、解调器、放大器及用于有线或无线通信的其它此种电路。

CPU 6可为经配置以处理计算机程序的指令以供执行的微处理器，例如中央处理单元(CPU)。CPU 6可包括控制装置2的操作的通用或专用处理器。用户可将输入提供到装置2，以使CPU 6执行一或多个软件应用程序。在CPU 6上执行的软件应用程序可包含例如，操作系统、文字处理器应用程序、电子邮件应用程序、电子数据表应用程序、媒体播放器应用程序、视频游戏应用程序、图形用户接口应用程序或另一程序。另外，CPU 6可执行GPU驱动程序22以控制GPU 12的操作。用户可通过一或多个输入装置(未展示)将输入提供到装置2，所述输入装置例如键盘、鼠标、麦克风、触摸板或通过用户接口4耦合到装置2的另一输入装置。

在CPU 6上执行的软件应用程序可包含指示CPU 6以使图形数据呈现到显示器8的一或多个图形呈现指令。在一些实例中，软件应用程序指令可符合图形应用程序编程接口(API)，例如开放图形库API、开放图形库嵌入系统(OpenGL ES)API、Direct3DAPI、X3D API、RenderMan API、WebGL API或任何其它公共或专有标准图形API。为了处理图形呈现指令，CPU 6可将一或多个图形呈现命令发布到GPU 12(例如，通过GPU驱动程序22)以使GPU 12执行图形数据的呈现中的一些或全部。在一些实例中，待呈现的图形数据可包含例如点、线、三角形、四边形、三角条带等图形图元的列表。

GPU 12可经配置以执行图形操作，从而将一或多个图形图元呈现到显示器8。因此，当CPU 6上执行的软件应用程序中的一者需要图形处理时，CPU 6可将图形命令及图形数据提供到GPU 12以向显示器8呈现。图形数据可包含例如，绘制命令、状态信息、图元信息、纹理信息等。在一些情况下，GPU 12可内置有高度并行结构，所述高度并行结构提供比CPU 6更高效的复杂图形相关操作的处理。举例来说，GPU 12可包含经配置以通过并行方式对多个顶点或像素进行操作的多个处理元件，例如着色器单元。在一些情况下，GPU 12的高度并行性质允许GPU 12比使用CPU 6直接将场景绘制到显示器8更快速地将图形图像(例如，GUI及二维(2D)及/或三维(3D)图形场景)绘制到显示器8上。

在一些情况下，GPU 12可集成到装置2的主板中。在其它情况下，GPU 12可存在于安装在装置2的主板中的端口内的图形卡上，或可以其它方式并入在经配置以与装置2交互操作的外围装置内。GPU 12可包含一或多个处理器，例如，一或多个微处理器、专用集成电路(ASIC)、现场可编程门阵列(FPGA)、数字信号处理器(DSP)或其它等效的集成或离散逻辑电路。GPU 12还可包含一或多个处理器核心，使得GPU 12可被称为多核处理器。

GPU 12可直接耦合到图形存储器40。因此，GPU 12可在不使用总线的情况下从图形存储器40读取数据并将数据写入到所述图形存储器。换句话说，GPU 12可使用本地存储装置，即图形存储器40，而不是片外存储器局部地处理数据。此种图形存储器40可被称为片上存储器。这允许GPU 12通过消除GPU 12通过总线读取及写入数据的需要而以更有效的方式操作，其中通过总线操作可经历繁重的总线业务。然而，在一些情况下，GPU 12可不包含单独的存储器，而是替代地通过总线利用系统存储器10。图形存储器40可包含一或多个易失性或非易失性存储器或存储装置，例如，随机存取存储器(RAM)、静态RAM(SRAM)、动态RAM(DRAM)、可擦除可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)、闪存存储器、磁性数据媒体或光学存储媒体。

在一些实例中，GPU 12可将完全形成的图像存储在系统存储器10中。显示处理器14可从系统存储器10检索图像，并且输出使显示器8的像素照亮以显示所述图像的值。显示器8可为显示由GPU 12产生的图像内容的装置2的显示器。显示器8可为液晶显示器(LCD)、有机发光二极管显示器(OLED)、阴极射线管(CRT)显示器、等离子显示器或另一类型的显示装置。

根据本公开的方面，GPU 12可将场景的多个图元组织在分层数据结构中，其中多个包围体与所述分层数据结构的多个节点相关联。GPU 12可进一步将多个包围体中的每一者的表示光栅化到存储器中的离屏呈现目标。GPU 12可至少部分基于与离屏呈现目标中的第一光线相交的像素，进一步将与所述像素相关联的分层数据结构的非根节点确定为开始节点以开始所述分层数据结构的遍历。GPU 12可进一步从开始节点开始遍历分层数据结构，以确定场景中的第二光线是否与多个图元中的一者相交。

图2是更详细地说明图1的CPU 6、GPU 12及系统存储器10的实例实施方案的框图。如图2中所示，CPU 6可包含至少一个软件应用程序18、图形API 20及GPU驱动程序22，其中的每一者可为在CPU 6上执行的一或多个软件应用程序或服务。

可用于CPU 6及GPU 12的存储器可包含系统存储器10及帧缓冲器16。帧缓冲器16可为系统存储器10的一部分或可与系统存储器10分离，并且可存储所呈现的图像数据。

软件应用程序18可为利用GPU 12的功能性的任何应用程序。举例来说，软件应用程序18可为GUI应用程序、操作系统、便携式制图应用程序、用于工程或艺术应用的计算机辅助设计程序、视频游戏应用程序或使用2D或3D图形的另一类型的软件应用程序。

软件应用程序18可包含指示GPU 12呈现图形用户接口(GUI)及/或图形场景的一或多个绘制指令。举例来说，绘制指令可包含定义待通过GPU 12呈现的一或多个图形图元的集合的指令。在一些实例中，绘制指令可共同地定义用于GUI中的多个开窗表面的全部或部分。在额外实例中，绘制指令可共同地定义图形场景的全部或部分，所述图形场景包含在由应用程序定义的模型空间或世界空间内的一或多个图形对象。

软件应用程序18可通过图形API 20调用GPU驱动程序22，以将一或多个命令发布到GPU 12以用于将一或多个图形图元呈现为可显示的图形图像。举例来说，软件应用程序18可通过图形API 20调用GPU驱动程序22以将图元定义提供到GPU 12。在一些情况下，可采用例如，三角形、矩形、三角扇、三角条带等绘制图元的列表的形式将图元定义提供到GPU12。

提供到GPU 12的图元定义可包含指定与待呈现的图元相关联的一或多个顶点的顶点信息。顶点信息可包含每一顶点的位置坐标，且在一些情况下，包含与顶点相关联的其它属性，例如色彩坐标、法向量及纹理坐标。图元定义还可包含图元类型信息(例如，三角形、矩形、三角扇、三角条带等)、缩放信息、旋转信息等。

基于由软件应用程序18发布到GPU驱动程序22的指令，GPU驱动程序22可调配指定供GPU 12执行的一或多个操作以便呈现图元的一或多个命令。当GPU 12从CPU 6接收到命令时，处理器集群46可执行图形处理管线以解码命令，且可配置图形处理管线以执行所述命令中指定的操作。举例来说，图形处理管线的命令引擎可读取图元数据，并将数据汇编成供图形处理管线中的其它图形管线级使用的图元。在执行指定操作之后，GPU 12将所呈现数据输出到与显示装置相关联的帧缓冲器16。

帧缓冲器16存储用于GPU 12的目标像素。每个目标像素可与唯一屏幕像素位置相关联。在一些实例中，帧缓冲器16可存储每个目标像素的色彩分量及目标阿尔法值。举例来说，帧缓冲器16可存储每个像素的红、绿、蓝、阿尔法(RGBA)分量，其中“RGB”分量对应于色彩值且“A”分量对应于目标阿尔法值。帧缓冲器16还可存储每个目标像素的深度值。以此方式，帧缓冲器16可据称存储图形数据(例如，表面)。尽管将帧缓冲器16及系统存储器10说明为单独的存储器单元，但在其它实例中，帧缓冲器16可为系统存储器10的一部分。一旦GPU12已将帧的全部像素呈现到帧缓冲器16中，帧缓冲器可将已加工帧输出到显示器8以供显示。

处理器集群46可包含一或多个可编程处理单元42及/或一或多个固定功能处理单元44。可编程处理单元42可包含例如，经配置以执行从CPU 6下载到GPU 12上的一或多个着色器程序的可编程着色器单元。在一些实例中，可编程处理单元42可被称为“着色器处理器”或“统一着色器”，且可执行几何、顶点、像素或其它着色操作以呈现图形。着色器单元可各自包含用于提取及解码操作的一或多个组件、用于执行算术计算的一或多个ALU、一或多个存储器、高速缓存器及寄存器。

GPU 12可通过向可编程处理单元42发送执行图形处理管线中的顶点着色器级、镶嵌级、几何着色器级、光栅化级及片段着色器级中的一或多者的命令，指定可编程处理单元42执行例如顶点着色、外壳着色、域着色、几何着色、片段着色等的多种着色操作。在一些实例中，GPU驱动程序22可致使在CPU 6上执行的编译程序编译一或多个着色器程序，并将经编译着色器程序下载到GPU 12内含有的可编程处理单元42上。

可以高级着色语言来编写着色器程序，例如OpenGL着色语言(GLSL)、高级着色语言(HLSL)、用于图形的C(Cg)着色语言、OpenCL C核等。经编译着色器程序可包含控制GPU12内的可编程处理单元42的操作的一或多个指令。举例来说，着色器程序可包含顶点着色器程序，其可由可编程处理单元42执行以执行顶点着色器级的功能；镶嵌着色器程序，其可由可编程处理单元42执行以执行镶嵌级的功能；几何着色器程序，其可由可编程处理单元42执行以执行几何着色器级的功能；及/或片段着色器程序，其可由可编程处理单元42执行以执行片段着色器级的功能。顶点着色器程序可控制可编程顶点着色器单元或统一着色器单元的执行，且包含指定一或多个每顶点操作的指令。

处理器集群46还可包含固定功能处理单元44。固定功能处理单元44可包含经硬接线以执行某些功能的硬件逻辑电路。尽管可例如通过一或多个控制信号配置固定功能处理单元44以执行不同功能，但固定功能硬件通常并不包含能够接收用户编译的程序的程序存储器。在一些实例中，处理器集群46中的固定功能处理单元44可包含例如，执行例如深度测试、剪切测试、阿尔法混合、低分辨率深度测试等的光栅操作的处理单元，以执行图形处理管线的光栅化级的功能。

图形存储器40是物理地集成到GPU 12的集成电路中的片上存储装置或存储器。因为图形存储器40为片上存储器，因此与通过系统总线从系统存储器10读取值或将值写入到所述系统存储器相比，GPU 12可能够更快速地从图形存储器40读取值或将值写入到所述图形存储器。

根据本公开的方面，处理器集群46可执行上述操作来执行图形处理管线以呈现包含模型空间或世界空间内的一或多个图形对象的三维(3D)图形场景，包含呈现构成3D场景中的一或多个图形对象的多个图元。处理器集群46还可通过追踪从光源穿过3D图形场景的像素的光路径来执行3D图形场景的光线追踪，以确定3D图形场景的哪些像素由光源照射。

作为执行3D图形场景的光线追踪的一部分，处理器集群46可执行3D图形场景的阴影呈现以确定不由光源照射(及因此处于阴影中)的3D图形场景的表面。此类表面可处于阴影中，因为一或多个实心表面阻止由光源发出的光线到达那些表面。为了确定3D图形场景中的特定位置是否由表面遮蔽光源，处理器集群46可在光源的方向上从特定位置投射称为阴影光线的向量。如果处理器集群46确定从所述位置投射的阴影光线与位于所述位置与光源之间的图元相交，则处理器集群46可认为阴影光线源自的位置被遮蔽光源。

为了确定源自3D图形场景的特定位置及朝向3D图形场景的光源的特定阴影光线是否与3D图形场景中的图元相交，GPU 12可将3D图形场景中的图元组织到分层地分组场景图元(例如，三角形)的分层结构，例如，加速数据结构(ADS)41中。GPU 12可将ADS 41存储在图形存储器40、系统存储器10中，处理器集群46的着色器存储器(未展示)中，或共享系统/图形存储器(未展示)中。关于图3及4更详细地论述GPU 12如何使用ADS 41来确定阴影光线-图元相交的细节。

图3是说明GPU 12可对其执行阴影光线追踪的实例图形场景及图形场景到包围体中的实例划分的概念图。如图3所示，图形场景50可为包含图元52A到52E(下文称为“图元52”)的2D或3D图形场景。作为阴影映射过程的一部分，针对图形场景50中的特定位置，GPU12可确定朝向光源的源自特定位置的阴影光线是否与图元52中的一者相交。如果GPU 12确定阴影光线与位于光源与阴影光线源自的位置之间的图元相交，则阴影光线源自的位置由相交图元遮蔽光源，且因此不由光源照射。

GPU 12可通过划分图形场景50、分层地布置图形场景50的划分部分，及以递归方式遍历图形场景50的划分部分的分层来系统地确定图元52中的图元是否与特定阴影光线相交。GPU 12可在概念上将图元52分成包围体56A到56E(“包围体56”)中。包围体56可为轴对准的包围盒(AABB)，其可为具有最小化区域的包围盒，所包围图元的全部点可处于所述最小化区域内。包围盒可为轴对准的，使得盒子的边缘可平行于坐标轴(例如，x、y及z轴)。

包围体56A可为界定图形场景50的全部图元52的包围盒。包围体56B及56C可为包围体56A的子集，因为包围体56B及56C界定由包围体56A界定的场景50的部分的子集。包围体56B可界定图元52A及52B，且包围体56C可界定图元52C、52D及52E。包围体56D及56E可为包围体56C的子集，并且可界定由包围体56B界定的场景50的部分的子集。包围体56D可界定图元52C及52D，并且包围体56E可界定图元52E。

在图3中所展示的实例中，GPU 12可将图元52分成五个包围体56A到56E。GPU 12不限于五个包围体56A到56E，但是可取决于场景及场景中的图元的数目来使用多于或少于五个包围体56A到56E。在一些实例中，GPU 12可相应地产生额外的包围体作为包围体56B的子集，以分别界定图元52A及52B。在一些实例中，CPU 6还可经配置以将图元52分成包围体56。

包围体56可布置成分层结构，使得GPU 12可遍历分层结构以确定可能的阴影光线-图元相交。图4说明具有与图3中所示的包围体56及图元52相关联的节点的实例分层数据结构。如上所述，场景的场景图元可组织到例如ADS 41的分层结构中，并且GPU 12可遍历ADS 41以确定可能的阴影光线-图元相交。如图4中所示，ADS 41的一个实例可为包围体分层(BVH)树60，其中与图形场景50的包围体56及图元52相关联的BVH树60的节点62A到62E(“节点62”)分层地布置成树状结构。

具体来说，GPU 12可布置BVH树60，使得与包围另一包围体的包围体相关联的节点可为与所包围的包围体相关联的节点的父节点。在图3的实例中，因为包围体56C包围作为包围体56C的子集的包围体56D及56E，所以与包围体56C相关联的节点62C分别可为与包围体56D及56E相关联的节点62D及62E的父节点。因此，相应地，根节点62A可与包围体56相关联，内节点62C可与包围体56C相关联，及叶节点62B、62D及62E可与包围体56B、56D及56E相关联。

BVH树60的除根节点62A以外的节点可被称为BVH树60的非根节点。举例来说，内节点62C及叶节点62B、62D及62E可被称为BVH树60的非根节点。叶节点62B、62D及62E可各自与图元52的至少一个图元连接。举例来说，叶节点62B可与图元52A及52B连接，因为与叶节点62D相关联的包围体56B包围图元52A及52B，叶节点62D可与图元52C及52D连接，因为与叶节点62D相关联的包围体56D包围图元52C及52D，及叶节点62E可与图元52E连接，因为与叶节点62E相关联的包围体56E包围图元52E。BVH树60可被视为非平衡二叉树，因为分层数据结构60的每一非叶节点最多具有两个子节点，还因为叶节点62B、62D及62E可具有不相等的深度。

通过针对与BVH树60的节点62相关的包围体56执行光线-盒相交测试，GPU 12可遍历BVH树60以确定阴影光线是否与图元52的图元相交。通过针对与根节点62A相关联的包围体56A执行光线-盒相交测试，GPU 12可开始对BVH树60的遍历。如果GPU 12确定阴影光线与包围体56A相交，则GPU 12可继续遍历BVH树60到节点62B，并且GPU 12可针对与节点62B相关联的包围体56B执行光线-盒相交测试。

如果GPU 12确定阴影光线并不与包围体56B相交，则GPU 12可以递归方式遍历BVH树，上到节点62A且下到节点62C，并且GPU 12可针对与节点62C相关联的包围体56C执行光线-盒相交测试。如果GPU 12确定阴影光线与包围体56C相交，则GPU 12可继续遍历BVH树60到节点62D，并且GPU 12可针对与节点62D相关联的包围体56D执行光线-盒相交测试。如果GPU确定阴影光线与包围体56D相交，则GPU 12可针对连接到节点62D的图元执行光线-图元相交测试。

因此，GPU 12可针对图元52C执行光线-图元相交测试，并且还可针对图元52D执行光线-图元相交测试以确定阴影光线是否与图元52C或图元52D相交。GPU 12可根据针对图元52D的光线-图元相交测试确定阴影光线的确与图元52D相交。在确定阴影光线的确与图元(例如，图元52D)相交之后，GPU 12可确定图形场景50中阴影光线源自的位置被遮蔽光源。

如果GPU 12确定阴影光线并不与图元52D相交，则GPU 12可继续以递归方式遍历BVH树60，上到节点62C且下到62E，并且GPU 12可针对与节点62E相关联的包围体56E执行光线-盒相交测试。GPU 12可基于光线-盒相交测试确定阴影光线是否与包围体56E相交，并且在进行确定之后，可结束针对阴影光线的BVH树60的遍历。

如果可从非根节点，例如内节点62C或叶节点62B、62D及62E中的一者开始遍历BVH树60，则相对于从根节点62A开始BVH树60的遍历，GPU 12可减少其执行的光线相交测试的次数，由此提高确定与光线相交的图元的效率。GPU 12可通过确定与BVH树60的非根(内)节点相关联的包围体与特定阴影光线相交而从BVH树60的非根节点开始BVH树60的遍历。GPU12可将包围体56的至少一个子集光栅化到图形存储器40中的离屏呈现目标。GPU 12可基于将多个包围体56光栅化到离屏呈现目标而将BVH树60的非根节点确定为BVH树60中的开始节点以开始BVH树60的遍历。GPU 12可从开始节点开始遍历BVH树60以确定与光线54相交的图元。

为了使用阴影光线执行图形场景，例如图形场景50的阴影呈现，GPU 12可从图形场景50的光源的角度呈现BVH树60的包围体56的至少一部分的表示。当从光源的角度呈现包围体56的至少一部分的表示时，如果源自那些位置的阴影光线与图元52的图元相交，则GPU 12可确定图形场景50中的位置不由光源照射。

如上所述，GPU 12可遍历分层结构，例如BVH树60，以确定源自图形场景50内的特定位置的阴影光线是否与图元52的图元相交。如果GPU 12通过BVH树60的遍历确定阴影光线与图元52的图元相交，则GPU 12可确定阴影光线源自的图形场景50内的特定位置不由图形场景50的光源照射。GPU 12通常可通过执行阴影光线与同节点52相关联的包围体56之间的光线-盒相交测试及/或阴影光线与图元52之间的光线-相交测试来从根节点62A遍历BVH树60，以确定特定位置是否由场景50的光源照射。

然而，BVH树的深度可为多个层。举例来说，如果BVH树包含16层，则GPU 12可能够通过从BVH树的非根节点开始，而不是从BVH树的根开始BVH树的遍历而更有效地确定阴影光线是否与图元相交。因为GPU 12可使用在处理器集群46上运行的像素着色器程序及/或顶点着色器程序来快速地将像素光栅化到离屏呈现目标及快速地对离屏呈现目标中的像素进行采样，所以GPU 12可利用这些着色器程序的性能特征来确定从其开始BVH树的遍历的非根节点。

图5是说明光栅化到实例离屏呈现目标的包围体的实例表示的框图。对于BVH树的指定数目的顶层，GPU 12可使用在处理器集群46上执行的其图形处理管线的像素着色器及/或顶点着色器来从光源的视角将与BVH树的节点相关联的包围体的表示光栅化到图形存储器或系统存储器10中的离屏呈现目标。GPU 12可用投影矩阵变换包围体的表示，使得GPU 12从图形场景50的特定光源的视角光栅化包围体的表示。

如果图形场景50包含多个光源，则针对每个光源一次，GPU 12可多次执行包围体的表示到离屏呈现目标的此光栅化。GPU 12可针对每个光源用不同投影矩阵执行此光栅化，使得从每个光源的视角光栅化包围体的表示。

在一些实例中，GPU 12可仅将BVH树的指定顶层光栅化到离屏呈现目标，使得给定16层BVH树，GPU 12可光栅化与仅BVH树的顶层，例如5到6层相关联的包围体的表示。因此，在一些实例中，GPU 12可将与少于BVH树的全部非根节点相关联的包围体的表示光栅化到离屏呈现目标64。

如图5中所示，GPU 12可从图形场景50的光源的角度将与BVH树60的节点62B到62E相关联的图形场景50的包围体56B到56E的表示66A到66D(“表示66”)光栅化到离屏呈现目标64。GPU 12可用透视矩阵光栅化表示66。GPU 12可将离屏呈现目标64存储在图形存储器40、系统存储器10或任何其它合适的存储器中。

GPU 12可投射包围体56B到56E，并且GPU 12的处理器集群46的着色器单元可将与BVH树60的非根节点62B到62E相关联的包围体56B到56E的表示光栅化为二维或三维表示，例如多边形、立方体等。举例来说，GPU 12的硬件光栅化器可将包围体56中的每一者扫描转换成呈现目标64中的像素。在一个实例中，GPU 12可将多个平面阴影立方体光栅化到离屏呈现目标64，作为包围体56B到56E的表示66。GPU 12还可通过透视矩阵缩放及平移表示66中的每一者，使得从光源的视角光栅化表示66。在一些实例中，与图形场景50中的包围体56B到56E相比，GPU 12可以相对较低的分辨率将包围体56B到56E的表示66光栅化。以此方式，GPU 12可另外提高其确定光线-图元相交的性能。

GPU 12可使不同色彩值与BVH树60的节点62中的每一者相关联，并且针对包围体56的每个包围体，可将具有与BVH树60的节点相关联的色彩值的像素块光栅化为表示66的包围体的相关联表示，所述节点与相应包围体相关联。以此方式，GPU 12还可以不同色彩将包围体56B到56E的表示66中的每一者光栅化，使得表示66中的每一者的色彩可表示指示BVH树60中的相关联节点的节点索引。

通过执行所投射的包围体56B到56E的标准深度测试，及通过将不同色彩值分配给表示66的像素以表示所投射的包围体56B到56E的不同深度，GPU 12可确定表示66的色彩。GPU 12可使分配给表示66的像素的色彩值与BVH树60的节点62相关联。以此方式，GPU 12可通过对像素的色彩值进行采样来确定与呈现目标64中的像素相关联的BVH树60中的节点。作为将表示66光栅化到呈现目标64的一部分，GPU 12可确定阴影光线到呈现目标64中的像素的映射，使得针对呈现目标64中的像素，GPU 12可将其映射为可能与一或多个阴影光线，例如，源自位置72A的阴影光线70A或源自位置72B的阴影光线70B相交。在一些实例中，呈现目标64可具有在像素与阴影光线之间的一对一映射。在其它实例中，如果以相对较低的分辨率(相较于对应包围体56的分辨率)将表示66光栅化到呈现目标64，则可将像素映射到多个阴影光线。

为了确定源自图形场景中的特定位置的特定阴影光线的潜在阴影光线-图元相交，GPU 12可针对每个光线确定映射到阴影光线的呈现目标64中的像素位置。给定具有原点及方向的阴影光线，GPU 12可基于光源的投影矩阵将阴影光线映射到呈现目标64中的像素位置。针对所述像素位置，GPU 12可对像素的色彩值进行采样，并且将与所采样色彩值相关联的节点确定为开始节点以开始BVH树60的遍历。

在图5的实例中，GPU 12可确定像素76A是呈现目标64中映射到阴影光线70A的像素。GPU 12可对呈现目标64中的像素76A进行采样以确定像素76A的色彩值，确定像素76A的所采样色彩值同与节点62B的节点索引相关联的色彩值相同，并且由此可以使像素76A与节点62B相关联。因此，GPU 12可将节点62B设定为用于遍历BVH树60的开始节点，并且可从节点62B开始BVH树60的遍历。

当GPU 12从节点62B开始遍历BVH树60时，GPU 12可首先针对与节点62B相关联的包围体56B执行阴影光线-盒相交测试。如果GPU 12确定阴影光线70A与包围体56B相交，则GPU 12可针对连接到节点62D的图元52A执行光线-图元相交测试。如果GPU 12确定阴影光线70A并不与图元52A相交，则GPU 12可以递归方式遍历BVH树60，上至节点62B，并且可针对连接到节点62B的图元52B执行光线-图元相交测试。GPU 12可根据针对图元52B的光线-图元相交测试确定阴影光线70A并不与图元52B相交。因为GPU 12从内节点62B开始BVH树60的遍历并且确定阴影光线70A并不与任一图元52A或52B相交，则GPU 12可结束针对阴影光线70A的BVH树60的遍历。GPU 12因此可确定位置72A是阴影光线70A由图形场景50的光源照射(及未被遮蔽光源)的位置，因为阴影光线70A并不与场景50中的任何图元相交。如可看出，用于确定图元是否与阴影光线70A相交的BVH树60的遍历可包含相较于需要GPU 12从根节点开始遍历BVH树60的情况，执行相对较少的光线-盒相交测试。

在一些实例中，取决于视角，当投射在屏幕上时，任何两个节点的包围体的表示可重叠。在这种情况下，BVH树60的遍历可从两个重叠包围体的最低共同祖先开始，所述包围体可不是根节点。如果包围体的两个表示重叠及如果光线在两个包围体的重叠区中相交，则GPU 12可确定与包围体相关联的节点的最低共同祖先节点，并且可从与包围体相关联的节点的最低共同祖先节点开始BVH树60的遍历，所述包围体由两个重叠的表示表示。举例来说，当将表示66光栅化到呈现目标64时，GPU 12可确定表示66C及表示66D在区域69中重叠，其中表示66C与节点62D相关联及表示66D与节点62E相关联，并且其中节点62D及节点62E处于BVH树60中的同一层。GPU 12可确定与节点62D及62E的最低共同祖先节点相关联的色彩值，并且可将区域69(即，重叠区)中的像素的色彩值设定成与节点62D及62E的最低共同祖先节点相关联的相同色彩值。在此实例中，GPU 12可确定节点62C是节点62D及62E的最低共同祖先节点，并且可将区域69中的像素的色彩值设定成与节点62C相关联的表示66B的色彩值。如果特定光线映射到区域69内的像素位置，则GPU可从节点62C，而不是根节点62A开始BVH树60的遍历，以确定任何可能的光线-图元相交。

举例来说，如果GPU 12确定从位置72B发出的阴影光线70A映射到位于区域69内的像素76B，则GPU 12可通过对映射像素76B的色彩进行采样及确定样本像素的色彩值与同节点62C相关联的色彩值相同来确定从不为根节点62A的节点62C开始BVH树60的遍历。因为节点62C与由呈现目标64中的表示66B表示的包围体56C相关联，所以GPU 12可针对与节点62C相关联的包围体56C执行光线-盒相交测试。

如果GPU 12确定阴影光线70B与包围体56C相交，则GPU 12可遍历BVH树60到节点62D。GPU 12可针对与节点62D相关联的包围体56D执行光线-盒相交测试。如果GPU确定阴影光线70B与包围体56D相交，则GPU 12可针对连接到节点62D的图元52C执行光线-图元相交测试。如果GPU确定阴影光线70B并不与图元52C相交，则GPU 12可以递归方式遍历BVH树60，上至节点62D，并且可针对连接到节点62D的图元52D执行光线-图元相交测试。GPU 12可根据针对图元52D的光线-图元相交测试确定阴影光线70B的确与图元52D相交。

当GPU 12确定阴影光线70B与图元52中的一者相交时，GPU 12可确定阴影光线70B来自的位置72B被遮蔽图形场景50的光源(不由所述光源照射)，并且可结束针对阴影光线70B的BVH树60的遍历。如可看出，GPU 12可通过将图形场景50的表示呈现到呈现目标64中，及从呈现目标64对像素进行采样以确定从其开始BVH树60的遍历的非根节点来加速BVH树60的遍历。

图6是说明用于确定用于遍历实例分层树状结构以发现阴影光线-图元相交的开始节点的实例过程的流程图。如图6中所示，所述过程可包含通过至少一个处理器，例如CPU6或GPU 12将图形场景(例如，图形场景50)的多个图元52组织在分层数据结构(例如，BVH树60)中，其中多个包围体56是分层数据结构的相关联节点62(702)。所述过程可进一步包含通过CPU 6或GPU 12将多个包围体56中的每一者的表示光栅化到离屏呈现目标64(704)。所述过程可进一步包含通过CPU 6或GPU 12及至少部分基于离屏呈现目标64中映射到图形场景50中的光线的像素，将与像素相关联的分层数据结构的非根节点确定为开始节点以开始分层数据结构的遍历(706)。所述过程可进一步包含通过CPU 6或GPU 12从开始节点开始遍历分层数据结构的节点的集合，以确定图形场景50中的光线是否与多个图元52中的一者相交(718)。

至少一个处理器可通过从多个位置中的每一者发出阴影光线，及根据上述过程确定阴影光线中的每一者的可能阴影光线-图元相交来执行图形场景50中的多个位置的阴影呈现。如果至少一个处理器确定图形场景50中的特定位置被遮蔽光源，因为从特定位置发出的阴影光线与图形场景50中的图元相交，则至少一个处理器可修改所述特定位置的像素值。举例来说，至少一个处理器可将特定位置的色彩值修改成黑色值或指示特定位置被遮蔽光源的另一合适色彩值。

此外，通过将多个包围体56中的每一者的表示光栅化到离屏呈现目标64，及基于离屏呈现目标64中映射到阴影光线的像素而确定从其开始分层数据结构的遍历的分层数据结构的非根节点，所述过程通过确定非根开始节点而在如何更有效地遍历分层数据结构的图形处理时提供基础技术问题的技术解决方案，由此使至少一个处理器能够更有效地执行场景的阴影呈现。

在一些实例中，将多个包围体56中的每一者的表示光栅化到离屏呈现目标64可进一步包含：通过CPU 6或GPU 12使多个色彩值中的不同色彩值与分层数据结构的多个节点62中的每一者相关联；及针对多个包围体56中的每个包围体，通过CPU 6或GPU12光栅化具有与分层数据结构的节点中的一者相关联的不同色彩值中的一者的像素块，所述节点与相应包围体相关联。

在一些实例中，将与像素相关联的分层数据结构的非根节点确定为开始节点以开始分层数据结构的遍历可进一步包含：通过CPU 6或GPU 12确定与像素的像素色彩值相关联的分层数据结构的节点；及通过CPU 6或GPU 12将与像素色彩值相关联的分层数据结构的节点设定为开始节点以开始分层数据结构的遍历。

在一些实例中，所述过程可进一步包含：通过CPU 6或GPU 12确定包围体中的第一包围体的第一表示覆盖包围体中的第二包围体的第二表示，其中第一包围体与分层数据结构的第一节点相关联且第二包围体与分层数据结构的第二节点相关联；及通过CPU6或GPU12将第一表示及第二表示的重叠区中的一或多个像素的色彩值设定成与第一节点及第二节点的最低共同祖先节点相关联的节点色彩值。

在一些实例中，所述过程可进一步包含响应于确定光线与多个图元52中的一者相交，通过CPU 6或GPU 12确定光线从其朝向光源发出的图形场景50中的位置被遮蔽光源，其中光线包括阴影光线。在一些实例中，将多个包围体56中的每一者的表示光栅化到离屏呈现目标64可进一步包含：通过CPU 6或GPU 12将与少于分层数据结构的全部非根节点相关联的多个包围体56的表示光栅化到离屏呈现目标64。

在一些实例中，将多个包围体56中的每一者的表示光栅化到离屏呈现目标64可进一步包含：通过CPU 6或GPU 12将多个平面阴影立方体光栅化到离屏呈现目标64，作为多个包围体56中的每一者的表示；及通过CPU 6或GPU 12缩放及平移多个平面阴影立方体中的每一者以匹配相应包围体的形状。在一些实例中，所述过程可进一步包含呈现场景以供显示装置显示。

在一或多个实例中，所描述功能可用硬件、软件、固件或其任何组合来实施。如果实施于软件中，则可将功能作为一或多个指令或代码存储在计算机可读媒体上或经由计算机可读媒体传输。计算机可读媒体可包含计算机数据存储媒体或通信媒体，通信媒体包含促进计算机程序从一个位置到另一位置的传送的任何媒体。数据存储媒体可为可由一或多个计算机或一或多个处理器存取以检索用于实施本公开中描述的技术的指令、代码及/或数据结构的任何可用媒体。借助于实例而非限制，此类计算机可读媒体可包括RAM、ROM、EEPROM、CD-ROM或其它光盘存储装置、磁盘存储装置或其它磁性存储装置，或可用于携带或存储呈指令或数据结构形式的所需程序代码且可由计算机存取的任何其它媒体。并且，适当地将任何连接称作计算机可读媒体。举例来说，如果使用同轴缆线、光纤缆线、双绞线、数字订户线(DSL)或红外线、无线电及微波等无线技术从网站、服务器或其它远程源传输软件，则所述同轴缆线、光纤缆线、双绞线、DSL或红外线、无线电及微波等无线技术包含在媒体的定义中。如本文中所使用，磁盘及光盘包含压缩光盘(CD)、激光光盘、光学光盘、数字多功能光盘(DVD)、软磁盘及蓝光光盘，其中磁盘通常以磁性方式再现数据，而光盘用激光以光学方式再现数据。以上各项的组合也应包含在计算机可读媒体的范围内。

代码可由一或多个处理器执行，所述一或多个处理器例如，一或多个数字信号处理器(digital signal processor，DSP)、通用微处理器、专用集成电路(applicationspecific integrated circuit，ASIC)、现场可编程逻辑阵列(field programmable logicarray，FPGA)或其它等效的集成或离散逻辑电路。因此，如本文中所使用的术语“处理器”及“处理单元”可指前述结构或适于实施本文中所描述的技术的任何其它结构中的任一者。另外，在一些方面中，本文中所描述的功能性可在配置用于编码及解码的专用硬件及/或软件模块内提供，或并入在组合编解码器中。而且，所述技术可完全实施于一或多个电路或逻辑元件中。

本公开的技术可实施于各种装置或设备中，所述装置或设备包含无线手持机、集成电路(IC)或一组IC(即，芯片组)。本公开中描述各种组件、模块或单元是为了强调经配置以执行所公开的技术的装置的功能方面，但未必需要由不同硬件单元实现。相反，如上所述，各种单元可结合合适的软件及/或固件组合在编解码器硬件单元中，或由互操作硬件单元的集合来提供，所述硬件单元包含如上文所描述的一或多个处理器。描述了各种实例。这些及其它实例在所附权利要求书的范围内。