CN101276479A - 图像处理方法和系统 - Google Patents

Abstract

根据本发明的一个实施例，通过增加所发出的通过具有高对比度颜色的相邻像素的射线的数目同时维持所发出的通过不具有高对比度颜色的相邻像素的射线的数目，射线跟踪图像处理系统可以呈现抗锯齿的图像，同时最小化图像处理系统所经历的工作量的增加。另外，根据本发明的另一实施例，通过维持所发出的通过具有低对比度颜色的相邻像素的射线的数目同时增加所发出的通过不具有低对比度颜色的相邻像素的射线的数目，图像处理系统可以减少在执行射线跟踪时经历的工作量，同时维持所呈现的图像的质量。

Description

图像处理方法和系统

技术领域

本发明的实施例一般地涉及图像处理领域。

背景技术

从三维场景呈现二维图像的过程通常被称作图像处理。随着现代计算机工业的发展，图像处理也在发展。图像处理发展的一个具体的目标是使得三维场景的二维仿真或呈现尽可能逼真。呈现逼真的图像的一个限制是现代显示器通过使用像素来显示图像。

像素是在显示器上可被照亮的最小的空间区域。大多数现代的计算机显示器使用成百上千个或数百万个像素的组合来组成整个显示或呈现的场景。各个像素被安排在栅格模式中，并且总体上覆盖显示器的整个观看区域。每个个体像素可以被照亮以呈现供观看的最终画面。

一种用于在使用像素的二维显示器上呈现真实世界三维场景的技术称为光栅化(rasterization)。光栅化是将二维图像表示为矢量格式(在场景内的几何对象的数学表示)并且将图像转化为各个像素以便在显示器上显示。光栅化在快速呈现图形和使用相对较低的计算功率量方面是有效的；然而，光栅化受到一些缺陷的制约。例如，光栅化通常缺乏逼真性，因为它不是基于光的物理特性的，相反，光栅化是基于场景中的三维几何对象投影在二维平面上的形状的。而且，利用光栅化呈现场景所需的计算功率直接随要呈现的场景的复杂度的增加而增大。当图像处理变得越逼真时，所呈现的场景也变得越复杂。因此，光栅化随着图像处理的发展而受到制约，因为光栅化直接随复杂度而增大。

另一种用于在使用像素的二维显示器上呈现真实世界三维场景的技术称为射线跟踪。射线跟踪技术跟踪其行为与光线类似的虚射线在要在计算机屏幕上呈现的三维场景中的传播。射线源自坐在计算机屏幕后的观看者的眼睛，并且朝着三维场景横穿构成计算机屏幕的像素。每个被跟踪的射线前进到场景中并且可以与场景内的对象相交。如果射线与场景中的对象相交，则使用对象的特性和若干其它贡献因素来计算颜色和光的量，或者如果不相交，则暴露射线。接着，使用这些计算来确定被跟踪的射线所经过的像素的最终颜色。

对于单个场景，跟踪射线的过程被执行多次。例如，针对显示器中的每个像素，可以跟踪单个射线。一旦已经跟踪足够数量的射线以确定构成计算机屏幕的二维显示的所有像素的颜色，则可以在计算机屏幕上将三维场景的二维合成显示给观看者。

射线跟踪通常呈现比光栅化更逼真的真实世界三维场景。这一部分是因为射线跟踪模拟了光在真实世界环境中的行进和行为的方式而不是像光栅化所做的那样简单地将三维形状投影到二维平面上这一事实。因此，使用射线跟踪来呈现的图形更精确地在显示器上描述了在真实世界中人眼所习惯看到的东西。

而且，在场景变得更加复杂时，射线跟踪对场景复杂度的增加的处理也优于光栅化。射线跟踪随着场景复杂度呈对数增大。这是由于即使场景变得更加复杂也可以将相同数量的射线投射入场景。由此，射线跟踪不会像光栅化那样在场景变得复杂时受到关于计算功率需求的问题的制约。

射线跟踪的一个主要缺陷是呈现场景所需的大量计算以及由此产生的处理功率。在需要快速呈现的时候，这会导致问题。例如，当图像处理系统出于例如在游戏控制台中的动画目的要呈现图形时。由于针对射线跟踪的增加的计算需求，很难足够快地呈现动画使得其看起来是逼真的(逼真的动画大约每秒二十到二十四帧)。

因此，需要更有效的技术和设备来执行射线跟踪。

发明内容

本发明的实施例一般地提供了用于执行射线跟踪的方法和装置。

本发明的一个实施例提供了一种通过执行具有自适应抗锯齿的射线跟踪来呈现三维场景的图像的方法。该方法一般地包括：基于发出到场景的初始的一组射线来识别像素的高对比度区域；以及发出附加的一组射线到一个或多个高对比度区域。

根据本发明的另一个实施例，提供了一种包含程序的计算机可读介质。该程序在被执行时会执行一般地包括以下步骤的操作：基于发出到三维场景的初始的一组射线来识别像素的高对比度区域；以及发出附加的一组射线到一个或多个高对比度区域。

根据本发明的另一个实施例，提供了一种图像处理系统。该图像处理系统一般地包括：存储器设备，其被配置为存储像素帧中的每个像素的颜色信息；以及处理单元，其被配置为基于发出到三维场景的初始的一组射线来识别像素的高对比度区域，以及发出附加的一组射线到一个或多个高对比度区域。

附图说明

图1是描述根据本发明的一个实施例的示例性计算机处理器的框图。

图2说明了根据本发明的一个实施例的多内核处理单元网络。

图3A-3C是说明根据本发明的一个实施例的存储器收件箱(inbox)的各方面的框图；

图4是根据本发明的一个实施例的将通过图像处理系统呈现的示例性三维场景。

图5A-5C说明了根据本发明的一个实施例的将通过图像处理系统呈现的二维空间和通过图像处理系统创建的对应的空间索引。

图6、9和12是说明根据本发明的实施例的执行射线跟踪的示例性方法的流程图。

图7是根据本发明的一个实施例的将通过图像处理系统呈现的示例性三维空间。

图8A-8D说明了根据本发明的一个实施例的执行射线跟踪的方法。

图10、11、13和14说明了根据本发明的实施例的将通过射线跟踪图像处理系统呈现的帧中的示例性像素。

具体实施方式

本发明的实施例提供用以提高射线跟踪图像处理系统的性能的方法和装置。本发明的一个实施例提供用于使得图像处理系统呈现抗锯齿的图像同时最小化与抗锯齿相关联的工作量增加的技术。根据本发明的一个实施例，通过自适应抗锯齿，可以呈现抗锯齿的二维图像，同时最小化工作量增加。根据本发明的一个实施例，图像处理系统可以通过检测容易存在锯齿的区域(例如，高对比度区域)并且发出附加射线到那些区域来自适应地对图像进行抗锯齿处理。图像处理系统可以通过以下步骤来检测高对比度区域：发出初始射线到三维场景，基于初始射线的相交来确定像素的初始颜色，以及接着对像素的初始颜色进行比较。于是，图像处理系统可以通过增加所发出的经过高对比度区域的像素的射线的数目来自适应地执行抗锯齿。通过仅增加发出到高对比度区域(即，可能由于锯齿化而失真的区域)中的三维场景的射线的数目，可以呈现抗锯齿的图像，同时最小化工作量的增加。

根据本发明的另一实施例，可以减少射线跟踪图像处理系统经历的工作量，同时可以维持最终图像的质量。根据本发明的一个实施例，通过减少发出到可能具有低对比度的三维场景的区域的射线的数目同时维持发出到不具有低对比度的三维场景的射线的数目，可以获得工作量的减少且不会降低图像质量。这可以称作是自适应地对低对比度区域中的三维场景进行子采样以减少初始发出的射线。可以减少发出到低对比度区域的射线的数目且不降低质量，因为相对于初步射线所确定的颜色，所发出的通过低对比度区域的像素的附加射线可以对像素的颜色进行微小的(不可觉察的)改变。通过维持发出到不具有低对比度的三维场景的区域的射线的数目同时减少发出到低对比度区域的射线的数目，可以维持通过射线跟踪图像处理系统呈现的图像的质量，同时可以减少图像处理系统经历的工作量。

在下文中，参考本发明的实施例。然而，应该理解本发明不限于特定的所描述的实施例。相反，下面的特征和单元的任意组合被考虑用于实现和实践本发明，无论这些特征和单元是否与不同的实施例相关。此外，在各种实施例中，本发明提供了相对于现有技术的众多优点。然而，尽管本发明的实施例可以实现相对于其它可能的解决方案和/或现有技术的优点，但是是否由给定的实施例获得特定的优点不构成对本发明的限制。因此，以下方面、特征、实施例和优点仅是说明性的，并且除非在权利要求中特别指出，否则不应认为是所附权利要求的单元或限制。类似地，对“本发明”的引用不应该解释为此处公开的任何发明主题的概括，并且除非在权利要求中特别指出，否则不应认为是所附权利要求的单元或限制。

本发明的一个实施例实现为用于与诸如下面描述的图像处理系统之类的计算机系统一起使用的程序产品。该程序产品的程序限定了实施例的功能(包括此处描述的方法)并且可以包含在各种各样的计算机可读介质上。示例性的计算机可读介质包括但不限于：(i)永久性地存储在不可写的存储介质(例如，计算机内的只读存储器设备，诸如可由CD-ROM驱动器读取的CD-ROM盘)上的信息；(ii)存储在可写的存储介质(例如，软盘驱动器内的软盘或硬盘驱动器)上的可更改的信息；以及(iii)通过通信介质，诸如通过计算机或电话网络，传送给计算机的信息，其中通信介质包括无线通信。后一实施例特别地包括从互联网和其它网络下载的信息。这样的计算机可读介质，当承载涉及本发明的功能的计算机可读指令时，表示本发明的实施例。

一般而言，被执行以实现本发明的实施例的例程可以是操作系统的一部分或者是特定的应用、组件、程序、模块、对象或者指令序列。本发明的计算机程序典型地包括多个指令，其将被本地计算机转换成机器可读的格式并且因此变为可执行的指令。同样，程序包括变量和数据结构，其要么本地地驻留在程序中，要么可以在存储器中或在存储设备上找到。另外，可以基于此后描述的各种程序在本发明的特定实施例中所针对的应用来识别这些程序。然而，应该明白以下的任何具体的编程术语仅是为了方便而使用的，并且因此不应将本发明限制为仅用于由这样的术语所标识和/或暗示的任何特定的应用。

示例性多内核处理单元

图1说明了根据本发明的一个实施例的多内核处理单元100。多内核处理单元100包括多个基本吞吐量引擎105(BTE)。BTE 105可以包含多个处理线程和内核高速缓存(例如，L1高速缓存)。位于每个BTE内的处理线程可以有权访问共享的多内核处理单元存储器高速缓存110(例如，共享的L2高速缓存)。

BTE 105还可以有权访问多个收件箱115。收件箱115可以是存储器映射的地址空间，这将在下文针对图3进行进一步描述。收件箱115可以被映射到位于每个BTE 105内的处理线程。位于每个BTE内的每个线程可以具有存储器映射的收件箱并且有权访问所有的其它存储器映射的收件箱115。收件箱115构成了供BTE 105使用的低等待时间且高带宽的通信网络。

BTE可以使用收件箱115作为网络以和每个其它的BTE进行通信并且在各BTE上重新分配数据处理工作。对于某些实施例，在通信网络中可以使用单独的发件箱，例如用来接收BTE 105的处理结果。对于其它实施例，收件箱115还可以用作发件箱，例如，其中一个BTE 105将处理功能的结果直接写到将使用该结果的另一BTE105的收件箱中。

图像处理系统的总性能可能与BTE能够多好地划分和重新分配工作紧密相关。收件箱115的网络可以用于收集和分配工作到另外的BTE，而不破坏具有无帧到帧一致性的BTE通信数据分组的共享多内核处理单元高速缓存110。可以呈现每帧数百万个三角形的图像处理系统可以包括以这种方式连接的多个BTE 105。

在本发明的一个实施例中，一个BTE 105的线程可以被指定给工作量管理器。图像处理系统可以使用各种软件和硬件组件来从三维场景呈现二维图像。如下面针对图6进一步描述的那样，根据本发明的一个实施例，图像处理系统可以使用工作量管理器来用图像处理系统发出的射线遍历空间索引。空间索引可以实现为树类型数据结构，用于将相对较大的三维场景划分成较小的有界体积(bounding volume)，下文将针对图4对空间索引进行进一步描述。使用射线跟踪方法进行图像处理的图像处理系统可以使用空间索引来快速地确定射线-有界体积相交。在本发明的一个实施例中，工作量管理器可以使用空间索引来执行射线-有界体积相交测试。

在本发明的一个实施例中，多内核处理器单元100上的多内核处理单元BTE 105的其它线程可以是矢量吞吐量引擎。在工作量管理器确定射线-有界体积相交之后，工作量管理器可以经由收件箱115发出(发送)射线到多个矢量吞吐量引擎中的一个。根据本发明的一个实施例，并且在下面将针对图6进行进一步描述，于是矢量吞吐量引擎可以确定射线是否与该有界体积内包含的图元相交。矢量吞吐量引擎还可以执行与确定射线经过的像素的颜色相关的操作。

图2说明了根据本发明的一个实施例的多内核处理单元的网络200。图2还说明了本发明的一个实施例，其中多内核处理单元100的BTE之一的线程是工作量管理器205。根据本发明的一个实施例，多内核处理单元的网络200中的每个多内核处理单元220_1-N可以包含一个工作量管理器205_1-N。根据本发明的另一个实施例，多内核处理单元的网络200中的每个处理器220还可以包含多个矢量吞吐量引擎210。

根据本发明的一个实施例，工作量管理器220_1-N可以使用高速总线225，以与其它多内核处理单元220的其它工作量管理器220_1-N和/或矢量吞吐量引擎210通信。每个矢量吞吐量引擎210可以使用高速总线225来与工作量管理器205的其它矢量吞吐量引擎210通信。工作量管理器205可以使用高速总线225来收集图像处理相关的任务并且将其分配到其它工作量管理器205，和/或将任务分配到其它矢量吞吐量引擎210。使用高速总线225可以允许工作量管理器205_1-N进行通信，而不影响具有与工作量管理器205通信相关的数据分组的高速缓存230。

低等待时间的高带宽通信网络

如上所述，图像处理系统的总性能可能与BTE能够多好地划分和重新分配工作紧密相关。根据本发明的一个实施例，高速缓存内的存储器空间(称为存储器收件箱)可被用于将工作分配到单个处理器线程。在使用多个处理器(每个均具有多个线程)的图像处理系统中，收件箱的集合可以被称为低等待时间的高带宽通信网络。

在诸如BTE 105之类的多线程处理器中，存储器收件箱可以被指定给给定线程(此处称为所有者线程)。在本发明的一个实施例中，用于收件箱的存储器空间可以从共享存储器高速缓存110排他地分配给所有者线程。通过排他地将高速缓存中的存储器空间指定给所有者线程，所有者线程可以维持足够的存储器空间以高速缓存其自己的指令和数据，而不会使其它竞争线程置换所有者线程的指令和数据。因此，通过将所有者线程的数据和指令维持在指定的高速缓存的收件箱部分并且减少在从高级别的存储器获取用于所有者线程的数据和指令的同时停止所有者线程的可能性，存储器收件箱可以改进所有者线程的执行。此外，通过将高速缓存中的存储器空间指定给所有者线程，打算用于目标线程的数据或指令可以仅存储在分配给线程的收件箱中。因此，打算用于目标线程的数据或指令不存储到整个共享存储器高速缓存110中，而是仅存储在分配给目标线程的收件箱中。

此外，收件箱存储器可以被其它线程使用以有效地与所有者线程通信。例如，在另一线程具有要被提供给某个收件箱的所有者线程的数据和/或指令的情况下，则该另一线程可以将数据和/或指令发送给其中数据和/或指令可以被所有者线程获取的收件箱。类似地，在某些情况下，所有者线程可以使用收件箱作为用于与其它线程交换信息的发件箱。例如，为了与另一线程交换信息，所有者线程可以将信息放在收件箱中并且向该另一线程发送通知，表明数据和/或指令的位置，由此允许该另一线程获取信息。可选地，所有者线程可以直接将信息提供给该另一线程的收件箱。因此，收件箱存储器可以用于简化发送线程和接收线程之间的通信，同时防止供其它线程使用的数据和/或指令的置换。

图3A是根据本发明的一个实施例的多内核处理单元100中的存储器收件箱302…318的框图。存储器收件箱302…318的描述意指概念视图，并且因此不限于任何特定的物理配置。如所描述的，在每个内核(例如，BTE 105)中执行的线程(例如，线程T0-T7)可以有权经由共享的L2高速缓存接口322访问共享的L2高速缓存110。此外，共享的L2高速缓存接口322还可供线程T0-T7使用以访问对应的存储器收件箱302…318。如上面所描述的，在某些情况下，每个收件箱302…318可以被指定给对应的线程T0-T7。因此，收件箱0302可以被指定给线程T0，并且以此类推。如下文将描述的，通过将给定的收件箱指定给给定线程，可以不限制所有者线程对指定收件箱的访问，而可以限制其它线程的访问。示例性限制将在下文进行更具体的描述。

图3B是描述从存储器收件箱(例如，收件箱302…308)和共享的L2高速缓存110传输到处理内核(例如，BTE 105)以及从处理内核(例如，BTE 105)传送到存储器收件箱(例如，收件箱302…308)和共享的L2高速缓存110的数据路径的框图。如上文所描述的，存储器收件箱302…308和共享的L2高速缓存110可以经由共享的L2高速缓存接口322进行访问。在BTE 105中执行的线程从收件箱302…308或从共享的L2高速缓存110获取数据的情况下，所获取的数据可以放置在用于BTE 105的L1高速缓存312中。用于该线程的指令可以从发出单元332发出。在某些情况下，BTE 105可以被配置为同时执行多个线程。因此，发出单元332可以被配置为发出用于多个线程的指令。在某些情况下，BTE 105可以提供多个执行单元334…338，其可以用于在BTE 105中同时执行线程。执行单元334…338可以包括定点执行单元334、浮点执行单元336和分支执行单元338。

在某些情况下，线程可以更新或产生(例如，由同一线程或由另一线程)稍后要访问的数据。在被更新的数据将稍后被访问的情况下，线程可以将更新的数据放置在L1高速缓存312中。此外，在期望的情况下，更新的数据可以被放置在L2高速缓存110或收件箱302…308中，以便经由共享的L2高速缓存接口322更新线程。在某些情况下，如前面所描述的，经由共享的L2高速缓存接口322直接访问给定收件箱(例如，收件箱0 302)可以限于拥有该给定收件箱的线程(例如线程T0)。

在本发明的一个实施例中，存储器收件箱内的存储器空间可以被映射到全局存储器地址(例如，包括L1高速缓存312、L2高速缓存110和主存储器的所有级别的存储器以及所有线程可以使用相同的全局存储器地址来访问给定的存储器收件箱)。因此，在本发明的一个实施例中，为了访问收件箱存储器空间，所有者线程可以仅将期望的信息读取或写入到对应于收件箱存储器空间的全局存储器地址。不拥有存储器收件箱并且试图经由全局存储器地址直接访问收件箱的线程可能被拒绝访问收件箱。相反，可以提供其它形式的访问给其它不拥有存储器收件箱的线程，例如，经由发送给收件箱的打包消息。

同样，在本发明的一个实施例中，存储在存储器收件箱中的信息可能不是可高速缓存的。例如，当L1高速缓存312、L2高速缓存110和其它存储器级别中的信息可以由多内核处理单元100自动高速缓存时，从而从给定存储器地址请求的信息在被访问时可以自动从主存储器读取并且保存在高速缓存级别312、110之一中。相比而言，给定收件箱中的可全局寻址存储器可以仅位于收件箱中并且可以不在存储器层级的不同级别(例如，主存储器、共享的L2高速缓存存储器110或L1高速缓存存储器)之间移动，并且无需复制到收件箱外部的新的地址空间。因此，所有者线程对收件箱的访问可以针对收件箱存储器被直接且快速地执行，而不需等待从存储器层级的另一级别读取信息和/或在读取期间进行转换。收件箱存储器的不可高速缓存性还可以应用到下文描述的对收件箱的打包访问中。此外，在本发明的替代性实施例中，存储在收件箱中的信息可以被高速缓存在存储器层级的其它级别中。

对存储器收件箱的指定

在本发明的一个实施例中，存储器收件箱可以从共享的存储器高速缓存110来提供(例如，L2高速缓存110的一部分可以保留用于收件箱存储器115。)图3C是描述根据本发明的一个实施例的从共享的L2高速缓存110划分出的收件箱存储器115的框图。

如所描述的，每个收件箱302、304等的大小和位置可以由收件箱控制寄存器340控制。每个收件箱302、304等的状态(例如，启用和禁用)可以经由收件箱状态寄存器362来表明和/或修改。在一个实施例中，对收件箱控制寄存器340的访问可以是无限制的。可选地，在某些情况中，对收件箱控制寄存器的访问可以是受限的，例如，限于被许可的线程的子集(例如，所有者线程、所有者线程的父线程、特别指派的控制线程、以及/或者操作系统核心线程)。在一个实施例中，收件箱控制寄存器340可以包括开始地址寄存器342、348…354，大小寄存器344、350…356和所有者线程标识寄存器346、352…358。

在一个实施例中，开始地址寄存器342、348…354可以表明每个收件箱302、304等的开始地址。大小寄存器344、350…358可以表明对应的收件箱302、304等的大小。用于收件箱的存储器空间可以因此占用从对应的开始地址开始且范围为所表明的收件箱大小的每个地址。该大小可以以任意方式来表明，例如，作为以字节为单位的绝对大小或者作为固定大小的整数倍数(例如，大小寄存器344、350…358中的大小可以表明以千字节为单位的大小)。

在一个实施例中，所有者线程标识寄存器346、352…358可以标识哪个线程(例如，线程T0、T1…TN)拥有给定的收件箱302、304等。尽管针对线程和对应的收件箱1、2…N进行了描述，但是本发明的实施例可以使用任何类型的线程和/或收件箱标识符(例如，数字、地址等)。在本发明的一个实施例中，收件箱标识符寄存器可以用于将对对应的收件箱内的存储器地址的直接访问限于所有者线程。在某些情况中，还可以允许有限选择的其它线程进行直接访问，例如所有者线程的父线程、特定的控制线程和/或操作系统核心线程。在一个实施例中，可以使用访问控制电路360来提供受限的访问。

通过将共享的存储器高速缓存110的部分指定给收件箱，可以形成低等待时间的高带宽通信网络。共享的存储器高速缓存110的剩余部分可以保持不指定并且因此可用于存储与处理线程间通信无关的信息。共享的存储器高速缓存110的剩余部分可用于存储被图像处理系统用来执行射线跟踪(下面将参考图5进一步说明)的几何特性和数据结构。

仅使用收件箱来进行处理线程之间的通信并且使用共享的存储器高速缓存110的剩余部分来存储几何特性和数据结构的好处在于：无论有多少通信相关的信息传到收件箱，都不会消耗整个的存储器高速缓存。因此，如下面将进一步描述的，通信相关的信息将不会置换存储在共享的存储器高速缓存110的剩余部分内的几何特性和数据结构。由此，在跟踪随后的射线或者呈现随后的帧时可能被重用的数据(对象几何特性和数据结构)可以保留在高速缓存中，而在跟踪随后的射线或者呈现随后的帧时不可能被重用的数据(数据处理工作)将不保留在高速缓存中。

示例性三维场景

图4是要由图像处理系统呈现的示例性三维场景405。在三维场景405内可以是对象420。图4中的对象420具有不同的几何形状。尽管在图4中仅示出了4个对象420，但是典型的三维场景中的对象数目可以更多或者更少。通常，三维场景将具有比图4中示出的更多的对象。

如从图4中可以看出的，对象具有变化的几何形状和大小。例如，图4中的一个对象是金字塔420_A。图4中的其他对象是盒子420_B-D。在很多现代的图像处理系统中，对象通常被分解成较小的几何形状(例如，正方形、圆形、三角形等)。于是，较大的对象由多个较小的简单的几何形状进行表示。这些较小的几何形状通常被称为图元。

在场景405中还说明了光源425_A-B。光源可以照亮位于场景405中的对象420。此外，取决于光源425和对象420在场景405中的位置，光源可以使得阴影投在场景405中的对象上。

三维场景405可以由图像处理系统呈现在二维画面中。图像处理系统还可以使得二维画面显示在显示器410上。显示器410可以使用不同颜色的多个像素430来呈现最终的二维画面。

图像处理系统用于将三维场景420呈现到二维画面中的一种方法被称为射线跟踪。射线跟踪通过图像处理系统从观看者415的角度“发出”或“射出”射线到三维场景420中来实现。该射线具有与光线类似的特性和行为。

在图4中可以看到一条射线440，其源自观看者415的位置并且行进经过三维场景405。当射线440从观看者415向三维场景405行进时，射线440通过其中图像处理系统将呈现最终二维画面的平面。在图4中，该平面由显示器410表示。射线440通过平面或显示器410的点由像素435来表示。

如前面简单描述的那样，多数图像处理系统使用数千个(或者数百万个)像素的栅格430(帧)来在显示器410上呈现最终场景。每个个体像素可以显示不同的颜色以在显示器410上呈现最终的合成二维画面。使用射线跟踪图像处理方法从三维场景呈现二维画面的图像处理系统将计算发出的一条或多条射线在三维场景中碰到的颜色。于是，图像处理系统将该射线碰到的颜色指定给射线在其从观看者到三维场景的路径上经过的像素。

每像素发出的射线的数目可以变化。一些像素可以具有发出的多条射线，以便呈现特定的场景。在该情况下，像素的最终颜色由来自该像素发出的所有射线的每个颜色贡献来确定。其他像素可以仅具有发出的单个射线以确定二维画面中的像素的所得颜色。一些像素可以不具有任何图像处理系统发出的射线，在该情况下它们的颜色可以由图像处理系统内的算法进行确定、近似或者指定。

为了确定二维画面中的像素435的最终颜色，图像处理系统必须确定射线440是否与场景内的对象相交。如果射线没有与场景内的对象相交，其可以被指定默认的背景颜色(例如，蓝色或黑色，表示白天或黑夜的天空)。相反地，当射线440行进经过三维场景时，射线440可能撞击对象。当射线撞击场景内的对象时，可以将对象的颜色指定给射线经过的像素。然而，对象的颜色在其被指定到像素之前必须被确定。

多种因素可能对原始射线440所撞击的对象的颜色做出贡献。例如，三维场景内的光源可以照亮对象。此外，对象的物理特性可以对对象的颜色做出贡献。例如，如果对象具有反射性或者是透明的，则其他的非光源对象可以对对象的颜色做出贡献。

为了确定来自三维场景内的其他对象的影响，可以从原始射线440与对象的交点发出辅助射线。例如，一种类型的辅助射线可以是阴影射线。可以使用阴影射线来确定到原始射线440与对象的交点的光的贡献。另一种类型的辅助射线可以是透射射线。可以使用透射射线来确定哪种颜色或者光可以透射经过对象体。此外，第三种类型的辅助射线可以是反射射线。可以使用反射射线来确定哪种颜色或光可以反射到对象上。

如上所述，一种类型的辅助射线可以是阴影射线。每个阴影射线可以被从原始射线和对象的交点跟踪到三维场景405内的光源。如果射线到达光源且在到达光源之前没有碰到另外的对象，则光源将照亮在原始射线撞击对象的点处原始射线所撞击的对象。

例如，阴影射线441_A可以从原始射线440与对象420_A的交点处发出，并且可以在朝着光源425_A的方向上行进。阴影射线441_A到达光源425_A而没有碰到场景405内的任何其他对象420。由此，光源425_A将照亮在原始射线440与对象420_A的交点处的对象420_A。

其他阴影射线可以具有其自己的在原始射线撞击对象的点与被三维场景内的其他对象阻挡的光源之间的路径。如果阻挡在原始射线撞击在对象上的点与光源之间的路径的对象是不透明的，则光源将不照亮在原始射线撞击对象的点处的对象。因此，光源可能不对原始射线的颜色做出贡献，并且因此也不对将在二维画面上呈现的像素的颜色做出贡献。然而，如果该对象是半透明的或透明的，则光源可以照亮在原始射线撞击对象的点处的对象。

例如，阴影射线441_B可以从原始射线440与对象420_A的交点处发出，并且可以在朝着光源425_B的方向上行进。在该例子中，阴影射线441_B的路径被对象420_D阻挡。如果对象420_D是不透明的，则光源425_B将不照亮在原始射线440与对象420_A的交点处的对象420_A。然而，如果对象420_D对于阴影射线是半透明的或透明的，则光源425_B可以照亮在原始射线440与对象420_A的交点处的对象420_A。

另一种类型的辅助射线是透射射线。如果与原始射线相交的对象具有半透明的或者透明的属性(例如，玻璃)，则可以由图像处理系统发出透射射线。透射射线相对于原始射线撞击对象的角度以一个角度来行进经过该对象。例如，观察到透射射线444行进经过与原始射线440相交的对象420_A。

另一种类型的辅助射线是反射射线。如果与原始射线相交的对象具有反射属性(例如，金属涂层)，则可以由图像处理系统发出反射射线以确定哪种颜色或者光可能被对象反射。反射射线相对于原始射线和对象相交的角度以一个角度从该对象穿出。例如，反射射线443可以由图像处理系统发出以确定哪种颜色或者光可能被与原始射线440相交的对象420_A反射。

所有辅助射线(例如，阴影射线、透射射线、反射射线等)的颜色和光的总贡献将产生原始射线经过的像素的最终颜色。

示例性的Kd-Tree

当执行射线跟踪时，碰到的一个问题是快速且有效地确定发出的射线是否与要呈现的场景内的任何对象相交。本领域的普通技术人员已知的一种使得射线相交确定更加有效的方法是使用空间索引。空间索引将三维场景或世界分成较小的体积(相对于整个三维场景较小)，这些较小的体积可以包含图元也可以不包括图元。于是，图像处理系统可以使用这些较小体积的已知边界来确定射线是否可能与包含在较小的体积内的图元相交。如果射线与包含图元的体积相交，则可以相对于该体积内包含的图元的已知位置和维度，使用射线的轨迹来运行射线相交测试。如果射线不与特定的体积相交，则不需要相对于该体积内包含的图元来运行射线-图元相交测试。此外，如果射线与不包含图元的有界体积相交，则不需要相对于该有界体积运行射线-图元相交测试。因此，通过减少可能是必要的射线-图元相交测试的数目，空间索引的使用极大地提高了射线跟踪图像处理系统的性能。不同的空间索引加速数据结构的一些例子是八叉树、k维树(kd-Tree)以及二进制空间划分树(BSP树)。尽管存在若干不同的空间索引结构，但是为了易于描述本发明的实施例，在下面的例子中将使用kd-tree。然而，本领域的普通技术人员将容易认识到本发明的实施例可以应用到任何不同类型的空间索引。

kd-tree使用轴线校准的有界体积来将整个场景或空间划分成较小的体积。也就是说，kd-tree可以通过使用平行于已知轴的分割平面来细分场景所包含的三维空间。分割平面将较大的空间划分成较小的有界体积。较小的有界体积一起组成了场景中的整个空间。将较大的有界体积划分(细分)成两个较小的有界体积的确定可以由图像处理系统通过使用kd-tree构造算法来做出。

用于确定何时将有界体积划分成较小的体积的一个标准可以是有界体积内包含的图元的数目。也就是说，只要有界体积包含多于预定阈值的图元，则可以继续树构造算法来通过画出多个分割平面来细分体积。用于确定何时将有界体积划分成较小的体积的另一个标准可以是有界体积内包含的空间量。此外，继续划分有界体积的决定还可以基于创建有界体积的平面可以与多少图元相交。

对场景的划分可以通过由节点、分支和叶子构成的二叉树结构来表示。树内的每个内部节点可以表示相对较大的有界体积，而节点可以包含到子节点的分支，子节点可以表示在由分割平面划分了相对较大的有界体积之后所得的两个相对较小的分块体积。在轴线校准的kd-tree中，每个内部节点可以仅包含两个到其他节点的分支。内部节点可以包含到一个或两个叶子节点的分支(即，指针)。叶子节点是不再进一步细分到更小的体积并且包含到图元的指针的节点。内部节点还可以包含到其他被进一步细分的内部节点的分支。内部节点还可以包含用于确定沿着哪个轴画出分割平面以及沿着轴的哪里画出分割平面所需的信息。

示例性的有界体积

图5A-5C说明了将由图像处理系统和对应的kd-tree呈现的二维空间。为了简单起见，使用二维场景来说明kd-tree的构建，然而kd-tree还可以用于表示三维场景。在图5A-5C的二维说明中，示出了分割线，而不是在三维结构中将使用的分割平面，并且示出了有界区域而不是在三维结构中将使用的有界体积。然而，本领域的普通技术人员将很快认识到这些概念可以容易地应用到包含对象的三维场景。

图5A说明了将在显示器510上显示的最终画面中呈现的包含图元510的二维场景505。表示场景的整个体积的最大体积是由有界体积1(BV₁)所包围的。在对应的kd-tree中，这可以通过顶层节点550(也称为根节点或世界节点)来表示。在图像处理系统的一个实施例中，当有界体积包含例如多于两个的图元时，图像处理系统可以继续将有界体积划分成较小的有界体积。如先前所述，继续将有界体积划分成较小的有界体积的决定可以基于很多因素，然而为了易于说明，在本例子中，继续划分有界体积的决定仅基于图元的数目。如从图5A可以看出的，BV₁包含六个图元，因此kd-tree构造算法可以将BV₁划分成较小的有界体积。

图5B说明了与图5A中说明的相同的二维场景505。然而，在图5B中，树构造算法已将BV₁划分成两个较小的有界体积BV₂和BV₃。对BV₁的划分通过在点x₁处沿着x轴画出分割平面SP₁515来实现。对BV₁的这种划分也在kd-tree中反映为在内部节点或父节点BV₁550之下的两个节点555和560，分别对应于BV₂和BV₃。表示BV₁的内部节点现在可以存储沿着哪个轴画出分割平面(即，x轴)以及沿着轴的哪里画出分割平面(即，在点x₁处)所需的信息，诸如但不限于指向在BV₁以下的两个节点(例如，BV₂和BV₃)的指针。

kd-tree构造算法可以继续划分有界体积BV₃，因为其包含多于预定阈值的图元(例如，多于两个图元)。然而，kd-tree构造算法可以不继续划分有界体积BV₂，因为有界体积BV₂包含少于或等于预定阈值的图元(例如，仅两个图元510_A)。不再进一步划分或细分的节点(诸如BV₂)被称为叶子节点。

图5C说明了与图5B中说明的相同的二维场景505。然而，在图5C中，kd-tree构造算法已将BV₃划分成两个较小的有界体积BV₄和BV₅。kd-tree构造算法已经使用在点y₁处的沿着y轴的划分平面划分了BV₃。因为BV₃已经被划分成两个子节点，所以其现在可以被称为内部节点。对BV₃的划分也在kd-tree中反映为两个叶子节点565和570，分别对应于BV₄和BV₅。BV₄和BV₅是叶子节点，因为它们表示的体积不被进一步划分成较小的有界体积。两个叶子节点BV₄和BV₅位于内部节点BV₃的下面，BV₃表示在kd-tree中被划分的有界体积。

表示BV₃的内部节点可以存储沿着哪个轴画出分割平面(即，y轴)以及沿着轴的哪里画出分割平面(即，在点y₁处)所需的信息，诸如但不限于指向两个叶子节点(即，BV₄和BV₅)的指针。

kd-tree构造算法现在可以停止划分有界体积，因为位于场景内的所有的有界体积包含少于或等于可被包围在有界体积内的最大预定数目的图元。叶子节点可以包含指向被包围在每个叶子节点表示的有界体积内的图元的指针。例如，叶子节点BV₂可以包含指向图元510_A的指针，叶子节点BV₄可以包含指向图元510_B的指针，而叶子节点BV₅可以包含指向图元510_C的指针。

所得的kd-tree结构或者其他空间索引结构，可以被存储在共享的存储器高速缓存110中。kd-tree和对应的包括kd-tree的数据的大小可以针对共享的存储器高速缓存110的存储而被进行最优化。

迭代射线跟踪算法

根据本发明的一个实施例，将射线跟踪算法从递归算法转换成迭代算法可以使得能够在多个处理单元之间有效地分布与射线跟踪有关的工作量。与递归的射线跟踪算法不同，迭代的射线跟踪算法可以允许单独的处理单元执行与确定单个像素的颜色有关的操作并且允许有效地使用处理器资源(例如，存储器高速缓存)。在多个处理单元之间有效地分布工作量可以提高射线跟踪图像处理系统的性能。

一种用于执行射线跟踪的算法在下列意义上可以是递归的：其发出原始射线到三维场景中并且在发出后续的原始射线到三维场景中之前完成与发出的原始射线相关的所有射线跟踪操作(例如，跟踪所有的辅助射线和执行所有的射线-对象相交测试)。

例如，图像处理系统可以使用递归的射线跟踪算法来从三维场景呈现二维图像。使用递归的射线跟踪算法的图像处理系统可以使用处理单元来执行射线跟踪。处理器可被用于将射线行进经过空间索引，并且确定射线是否与空间索引的有界体积内的任何对象相交。如果射线与有界体积内包含的对象相交，则图像处理系统(使用同一处理器)可以发出辅助射线到三维场景以确定它们是否与任何对象相交，并且因此对与原始射线相交的对象的颜色做出贡献。当执行与确定辅助射线是否与三维场景内的对象相交的确定有关的操作时，处理器可以在处理器的存储器高速缓存中存储用于限定原始射线的信息。

如果处理单元确定辅助射线与三维场景内的对象相交，则图像处理系统可以发出更多的辅助射线到场景中以确定那些辅助射线是否与对象相交并且对与原始射线相交的对象的颜色做出贡献。当执行用于确定辅助射线是否与三维场景内的对象相交的计算时，处理器可以在处理器的存储器高速缓存中存储以前的辅助射线信息。通过发出越来越多的辅助射线到场景中，图像处理系统可以最终确定来自辅助射线的对与原始射线相交的对象的颜色的总贡献。根据与原始射线相交的对象的颜色和由辅助射线作出的颜色贡献，可以最终确定原始射线经过的像素的颜色。

尽管递归的射线跟踪算法确定了原始射线经过的像素的颜色，但在每次图像处理系统发出更多的辅助射线到三维场景中时，递归的射线跟踪图像处理系统将限定了以前的射线(例如，原始射线或以前的辅助射线)的信息放置到处理单元的存储器高速缓存中。图像处理系统可以将射线信息存储在高速缓存中，以便释放执行与确定后续的辅助射线是否与三维场景内的对象相交有关的计算所需的寄存器。因此，针对单个的像素，递归的射线跟踪图像处理系统可以将大量的(与高速缓存的大小相关)信息放置到处理器存储器高速缓存中。

通过将大量的射线信息存储在处理器的存储器高速缓存中，在处理器的存储器高速缓存中只有很少的空间或者没有空间用于限定三维场景内的对象的信息(即，对象几何数据)。该信息可能需要频繁地从主存储器读取到存储器高速缓存中以便执行用于确定原始射线或辅助射线是否与三维场景内的对象相交的操作(由此，发生高速缓存“冲突”(trashing))。因此，使用递归的射线跟踪技术的图像处理系统的限制可能受到从主存储器中读取信息以及将其放置在处理器的存储器高速缓存中的访问时间的限制。

然而，根据本发明的实施例，射线跟踪算法可以被划分成迭代的射线跟踪算法。迭代的射线跟踪算法可以允许单独的处理单元执行射线跟踪算法的各部分。通过允许单独的处理单元执行射线跟踪算法的各部分，可以减少需要高速缓存的信息量(例如，原始射线和辅助射线)。此外，根据本发明的实施例，迭代的射线跟踪算法可以结合低等待时间高带宽通信网络和共享的存储器高速缓存110一起使用，以便提高射线跟踪图像处理系统的性能。

根据本发明的实施例，如上面针对图3A-3C所描述的，收件箱的低等待时间高带宽通信网络可以用于传递或发送数据处理信息(例如，限定原始射线和辅助射线的信息)，这些信息在跟踪后续的射线或者呈现后续帧时很少使用。另外，根据本发明的实施例，射线跟踪图像处理系统可以使用共享的一致存储器高速缓存来存储在跟踪后续的射线或者执行针对后续帧的射线跟踪时可能被图像处理系统使用的信息。

图6是说明根据本发明的一个实施例的可以用在多处理器图像处理系统中的分块的并且因此迭代的射线跟踪算法或方法600的流程图。方法600开始于步骤605，在该步骤中图像处理系统发出原始射线到三维场景。原始射线在其行进到三维场景中时可以经过像素。原始射线可以用于确定原始射线经过的像素的颜色。

接着，在步骤610处，图像处理系统可以使用工作量管理器205处理单元来遍历(traverse)空间索引(例如，kd-tree)。空间索引可以被存储在图像处理系统的共享的存储器高速缓存110内。遍历kd-tree可以包括执行确定原始射线是否与由空间索引内的节点限定的有界体积相交的计算。此外，遍历空间索引可以包括选取到限定了与射线相交的有界体积的节点的分支。工作量管理器205可以使用坐标和发出的射线(例如，原始射线)的轨迹来确定射线是否与空间索引中的节点限定的有界体积相交。工作量管理器205可以继续遍历空间索引，直到原始射线与仅包含图元的有界体积(即，叶子节点)相交。

在步骤615处，在工作量管理器205已经使得原始射线遍历到叶子节点之后，工作量管理器205可以将原始射线和限定叶子节点的信息发送给矢量吞吐量引擎210。工作量管理器205可以将限定原始射线和叶子节点的信息(例如，射线的轨迹、原始射线经过的像素、叶子节点限定的有界体积等)发送给矢量吞吐量引擎210。工作量管理器205可以通过将限定射线和相交叶子节点的信息写入矢量吞吐量引擎210的收件箱来将信息发送给矢量吞吐量引擎210。

通过将像素信息与限定原始射线的信息相耦合，在矢量吞吐量引擎210确定射线与对象相交并且因此确定像素的颜色的情况下将不需要将原始射线发送回工作量管理器205。根据本发明的一个实施例，矢量吞吐量引擎210可以使用像素信息从而通过对对应于像素的帧缓冲器内的存储器位置进行写入(例如，存储在共享的存储器高速缓存110中)来更新像素的颜色。通过在辅助射线与三维场景内的对象相交时更新像素颜色，可以减少需要存储(例如，在高速缓存存储器中)的与同一像素相关的射线的数目。

在工作量管理器205向矢量吞吐量引擎210发送原始射线信息之后，图像处理系统可以发出后续的原始射线到三维场景。在工作量管理器205已经将原始射线发送给矢量吞吐量引擎210之后，工作量管理器205可以立即开始使得该后续发出的原始射线遍历空间索引。因此，工作量管理器205可以使得射线连续地遍历空间索引，而不是如在递归的射线跟踪算法中那样等待直到完成关于原始射线是否与对象相交的确定。此外，工作量管理器205可以在矢量吞吐量引擎210确定以前发出的射线是否与叶子节点限定的有界体积内的对象相交时使得射线连续地遍历空间索引。根据本发明的一个实施例，矢量吞吐量引擎210可以负责执行射线-图元相交测试。也就是说，矢量吞吐量引擎210可以确定射线是否与叶子节点限定的有界体积内包含的任何图元相交。

由此，在步骤620，在其收件箱中接收射线和叶子节点信息的矢量吞吐量引擎210可以执行射线-图元相交测试以确定射线是否与叶子节点限定的有界体积内的任何图元相交。限定图元的几何特性可以存储在共享的存储器高速缓存110中，并且因此可以不需要从主存储器读取几何特性。通过在共享的存储器高速缓存110中存储图元的几何特性，迭代的射线跟踪算法可以不需要像在递归的射线跟踪算法中那样从主存储器读取几何特性。如果矢量吞吐量引擎210确定原始射线与叶子节点限定的有界体积内包含的图元相交，则矢量吞吐量引擎210可以前进到步骤630。

在步骤630处，矢量吞吐量引擎210可以确定在原始射线与图元的交点处的相交图元的颜色。例如，图元的颜色可以存储在共享的存储器高速缓存110中并且矢量吞吐量引擎210可以从共享的存储器高速缓存210中读取颜色信息。

在确定在射线-图元交点处的图元的颜色之后，矢量吞吐量引擎210可以更新射线所经过的像素的颜色。这可以例如通过对对应于原始射线所经过的像素的帧缓冲器内的存储器位置进行写入来实现。通过在确定射线-图元相交时并且在确定与原始射线相关的所有辅助射线的颜色贡献之前更新像素信息，可以减少需要存储在存储器高速缓存中的信息量。相比而言，在递归的射线跟踪算法中，可能直到已经确定来自辅助射线的所有颜色贡献才在帧缓冲器中存储像素的颜色，其增加了可能需要在处理器的存储器高速缓存中存储的信息量。

在更新像素颜色之后，矢量吞吐量引擎210可以前进到步骤635，在该步骤中矢量吞吐量引擎210可以生成辅助射线。如前面针对图4所描述的，射线跟踪图像处理系统可以使用辅助射线确定对相交对象并且因此对原始射线所经过的像素的附加颜色贡献。辅助射线可以例如是反射射线、透射(折射)射线或者阴影射线。生成辅助射线可以包括例如基于原始射线的轨迹、相交对象的表面特性以及原始射线与相交对象的相交角度来确定辅助射线的轨迹。

在生成辅助射线之后，在步骤640中矢量吞吐量引擎210向工作量管理器205发送辅助射线。矢量吞吐量引擎210可以通过将限定辅助射线(例如，轨迹、限定原始射线所经过的像素的信息等)的信息放置在工作量管理器205的收件箱115中来向工作量管理器205发送辅助射线。根据本发明的一个实施例，矢量吞吐量引擎210可以向使得射线遍历空间索引的工作量管理器205发送辅助射线。然而，根据本发明的另外的实施例，图像处理系统可以包含多个工作量管理器，并且矢量吞吐量引擎210可以向没有使得射线遍历空间索引的工作量管理器发送辅助射线。

在向工作量管理器205发送辅助射线之后，矢量吞吐量引擎210可以从收件箱获取限定可以等待到完成射线-图元相交测试的射线的其他信息。在矢量吞吐量引擎210的收件箱中等待的射线可能先前已经由工作量管理器205使其遍历空间索引。因此，矢量吞吐量引擎210可以执行更多的射线-图元相交测试以确定射线(即，原始的或辅助的)是否与叶子节点所限定的有界体积内的对象相交。因此，矢量吞吐量引擎210可以连续地执行与射线-图元相交测试相关的操作，确定图元颜色、更新像素颜色以及生成辅助射线。

在从矢量吞吐量引擎210接收辅助射线之后，工作量管理器205可以执行步骤610和615(如上面所描述的)以确定辅助射线是否与叶子节点相交。

返回到步骤625，如果矢量吞吐量引擎210确定射线没有与叶子节点限定的有界体积内包含的图元相交，则矢量吞吐量引擎210可以给原始射线所经过的像素指定三维场景的背景颜色。背景颜色可以被指定给像素，因为原始射线没有与三维场景内包含的任何图元相交。然而，根据本发明的其他实施例，如果射线没有与叶子节点有界体积内包含的任何图元相交，则矢量吞吐量引擎210可以将射线发送回工作量管理器205，使得工作量管理器205可以再次使得射线遍历空间索引以确定射线是否与包含图元的任何其他叶子节点相交。

迭代的射线跟踪算法的示例性使用

图7说明了根据本发明的一个实施例的从图像处理系统发出到三维场景505的示例性射线。为了清楚起见，三维场景505与图5A-5C中用于说明kd-tree的构造的三维场景相同。由此，对应于三维场景505的kd-tree与针对图5A-5C构造的kd-tree相同。如在图7中所示的，观看者705表示可以由图像处理系统发出到三维场景505的多个原始射线710_1-4的起点。当每个原始射线710_1-4被发出到三维场景中时，原始射线可以首先经过像素栅格(帧)715中的对应的像素。尽管在图7中仅说明了四个像素715和四个原始射线710_1-4来从三维场景呈现最终的二维图像，但是可能需要更多的像素并且可能发出更多的原始射线。

可以由图像处理系统发出第一原始射线710₁并且该第一原始射线710₁经过第一像素715₁。第一原始射线710₁可以在交点I₁处与有界体积4相交。为了便于理解，该例子中的图像处理系统可以符合从像素715的栅格的顶部开始发出射线的模式，并且连续发出射线，每个像素一条射线，向下移动像素的栅格直到已经针对像素栅格中的每个像素发出了射线。

还可以由图像处理系统发出第二原始射线710₂和第三原始射线710₃，其分别经过第一像素715₂和第三像素715₃。第二原始射线710₂和第三原始射线710₃还可以分别在第二交点I₂和第三交点I₃处与BV₄相交。因此，第一原始射线710₁、第二原始射线710₂和第三原始射线710₃都与相同的有界体积相交。此外，还可以由图像处理系统发出第四原始射线710₄并且可以经过第四像素715₄。与前三个原始射线710_1-3不同，第四原始射线710₄可以在交点I₄处与有界体积5(BV₅)相交。

图8A说明了使得第一原始射线710₁遍历空间索引805(例如，kd-tree)。此外，如阴影框205所表明的，图8A说明了工作量管理器205执行与使得第一原始射线710₁遍历空间索引805相关的操作。工作量管理器205可以通过选取到限定与射线相交的有界体积的节点的分支直到到达叶子节点(如图8中通过加黑的分支和节点所示)来使得射线遍历空间索引805。如图7中所示，原始射线710₁与BV₄相交，由此工作量管理器205将使得第一原始射线710₁遍历到限定BV₄的叶子节点。在使得射线遍历到叶子节点之后，工作量管理器205可以向矢量吞吐量引擎210发送第一原始射线710₁(例如，发送限定第一原始射线710₁的信息和限定第一原始射线所经过的像素715₁的信息)和限定相交叶子节点(即，BV₄)的信息。

根据本发明的实施例，在工作量管理器205向矢量吞吐量引擎210发送第一原始射线710₁之后，工作量管理器205可以开始使第二原始射线710₂遍历空间索引。因此，在矢量吞吐量引擎210确定射线是否与由于遍历到叶子节点而限定的有界体积内的对象相交的同时，工作量管理器205可以持续地使得射线遍历空间索引805。

图8B说明了第一原始射线710₁行进通过有界体积4(BV₄)。此外，如阴影框所表明的，图8B说明了在矢量吞吐量引擎210已经接收限定第一原始射线710₁的信息和限定有界体积BV₄的信息之后，矢量吞吐量引擎210执行射线-图元相交测试。如针对图6所描述的，矢量吞吐量引擎210可以执行射线-图元相交测试以确定原始射线710₁是否与有界体积BV₄内包含的图元相交。

矢量吞吐量引擎210可以执行第一原始射线710₁相对于有界体积BV₄内的第一对象720以及相对于有界体积BV₄内的第二对象725的测试。如图8B所示的，矢量吞吐量引擎210可以确定第一原始射线710₁与第一对象720相交。

如前面针对方法600所描述的，在确定第一原始射线710₁与对象相交之后，矢量吞吐量引擎210可以确定在第一原始射线710₁与第一对象720的交点处的第一对象720的颜色。在确定在交点处的对象720的颜色之后，矢量吞吐量引擎210可以更新第一原始射线710₁所经过的像素715₁的颜色(例如，通过对对应于像素715₁的帧缓冲器存储器位置进行写入)。

在确定交点处的对象720的颜色之后，矢量吞吐量引擎210可以生成辅助射线。例如，如图8C所说明的，矢量吞吐量引擎210可以生成反射射线730和透射(折射)射线735。两种辅助射线(730和735)源自第一原始射线710₁与对象720的交点。如上文所描述的，辅助射线可以用于确定对第一原始射线710₁与对象720的交点处的对象的附加颜色贡献。辅助射线的生成可以包括确定每个辅助射线的轨迹以及标记辅助射线，使得来自辅助射线的附加颜色贡献可以用于更新第一原始射线710₁所经过的像素715₁的颜色。

在生成辅助射线(730和735)之后，矢量吞吐量引擎210可以经由收件箱向工作量管理器205发送辅助射线(730和735)。接收辅助射线(730和735)的工作量管理器205可以使用限定辅助射线(即，辅助射线的轨迹)的信息来遍历空间索引805。例如，图8D中的阴影框说明了可以利用由矢量吞吐量引擎210生成的辅助射线(例如，730)来遍历空间索引805的工作量管理器205。工作量管理器205可以使得辅助射线遍历到叶子节点。在已经使得辅助射线遍历到叶子节点之后，工作量管理器205可以向矢量吞吐量引擎210发送辅助射线和限定与辅助射线相交的有界体积的信息来确定辅助射线是否与和辅助射线相交的有界体积内的任何对象相交。

当矢量吞吐量引擎210确定原始射线或辅助射线撞击三维场景内的对象时，可以在帧缓冲器内更新原始射线所经过的像素的颜色。根据本发明的实施例，与一个原始射线相关的以及因此与原始射线所经过的像素相关的所有辅助射线可以在三维场景内进行跟踪，并且它们的颜色贡献可以被保存在帧缓冲器中，以便确定像素的最终颜色。然而，根据本发明的其他实施例，对与原始射线相关的有限数目的辅助射线可以在三维场景中进行跟踪以便确定像素的颜色。通过限制在三维场景内跟踪的并且因此对像素的颜色做出贡献的辅助射线的数目，可以减少用于确定像素的最终颜色所必需的处理量。

用于自适应抗锯齿的颜色缓冲器对比度阈值

图像处理系统的(例如，射线跟踪图像处理系统)的一个公共问题是锯齿。锯齿通常是指在对信号进行采样时引起的失真。在射线跟踪图像处理中，待采样的原始信号是三维场景，并且在图像处理系统呈现的二维图像中可能有明显的锯齿。在呈现的图像中例如在存在高对比度的区域中可能存在更加突出的锯齿。高对比度区域可以沿着三维场景内的对象的边缘出现。锯齿可能被显示为沿着三维场景中的对象的边缘的参差不齐的边。

图像处理系统可以使用各种技术，通常称为抗锯齿，来减小最终呈现的图像中的锯齿。一种抗锯齿技术是增加取自原始信号的采样数，并且接着对采样结果进行平均。这种技术可以通过获取采样信号的更精确表示来减小锯齿失真。在射线跟踪图像处理系统中，增加采样数可能使得必须针对帧中的每个像素发出更多的射线到三维场景。这些附加射线可以与三维场景内的对象相交并且通过来自这些附加射线的总的颜色贡献可以得到对每个像素的颜色的更精确的确定。针对帧内的像素的更精确的颜色确定可以减小最终呈现的图像中的锯齿(例如，参差不齐的边)。

尽管增加针对帧中的每个像素的射线的数目可以减小锯齿引起的失真，但是针对帧中的每个像素发出附加射线到三维场景可能显著地增加呈现最终图像所必需的工作量。更大的工作量会增大射线跟踪图像处理系统用于从三维场景呈现最终二维图像所需的时间量。呈现图像所需的增大的时间量可能在结合其他系统(例如，游戏系统)使用图像处理系统来提供动画时导致明显的分辨率或响应损失。

然而，本发明的实施例提供了用于图像处理系统在最小化(或者，减小)工作量增加的同时呈现抗锯齿的图像的技术。根据本发明的一个实施例，通过提供自适应抗锯齿，可以在最小化工作量的增加的同时呈现抗锯齿的二维图像。根据本发明的一个实施例，图像处理系统可以通过检测可能易于存在锯齿的区域(例如，高对比度区域)和发出附加射线到这些区域中而使得图像自适应地抗锯齿。图像处理系统可以通过以下步骤来检测高对比度区域：发出初始射线到三维场景，基于初始射线的相交来确定像素的初始颜色，以及接着对像素的初始颜色进行比较来检测高对比度区域。于是，图像处理系统可以通过增加所发出的经过高对比度区域中的像素的射线的数目来自适应地执行抗锯齿。通过仅增加发出到高对比度区域(即，很可能存在锯齿引起的失真的区域)中的三维场景的射线的数目，可以在最小化工作量的增加的同时呈现抗锯齿的图像。

图9是说明根据本发明的一个实施例的执行射线跟踪和自适应抗锯齿的示例性方法900的流程图。方法900开始于步骤905，在该步骤中图像处理系统(例如，工作量管理器205)可以发出初始射线到三维场景。当初始射线向三维场景行进或行进到三维场景中时，它们会经过多个像素。

根据本发明的实施例，图像处理系统可以针对每个像素发出恒定数目的初始射线到三维场景。尽管该恒定数目的初始射线在不同的实现之间或者在不同的帧之间可以变化，但是针对任何给定帧中的每个像素发出的初始射线的数目可以是恒定的，例如，针对特定帧中的每个像素。每个初始射线可以经过每个像素内的特定点。因此，针对每个像素发出的射线可以创建它们经过像素时的点的模式。

例如，图10说明了一系列的像素1005，图像处理系统可以发出多个初始射线通过这些像素。图10还说明了可以从其发出射线的观察点1000和可以由图像处理系统(例如，由工作量管理器205)发出的示例性射线1010。一系列像素1005中的5个像素(即，像素1015、1020、1025、1030和1035)可以是一起组成帧的较大的像素栅格(例如，图4的栅格430)的一部分。

在图10说明的例子中，可以发出恒定数目即5个初始射线经过一系列像素1005中的每个像素。初始射线可以通过其来经过每个像素的点的模式1040在图10中由每个像素内的阴影圈来表示。

在针对帧中的每个像素发出初始射线之后，或者在图像处理系统发出初始射线到三维场景时，图像处理系统可以前进到步骤910，其中图像处理系统可以执行初始射线的射线跟踪操作。这可以包括例如(例如，利用工作量管理器205)使得初始射线遍历具有表示三维场景内的有界体积的节点的空间索引805，(例如，利用矢量吞吐量引擎210)针对初始射线执行射线-图元相交测试，以及(例如，利用矢量吞吐量引擎210)更新对应于三维场景内与初始射线相交的对象的像素的颜色。图像处理系统可以通过将颜色信息保存在例如帧缓冲器中来更新像素的颜色。帧缓冲器(颜色缓冲器)可以是二维存储器空间(例如，在存储器高速缓存110或者其他合适的存储器设备内)，其中图像处理系统可以存储针对帧内的每个像素的颜色信息。

一旦帧缓冲器中存在足够信息量，图像处理系统就可以识别高对比度区域。足够信息量可以是这样的信息量，其可以允许图像处理系统确定三维场景内是否存在高对比度区域。例如，两个像素可以构成足够的信息量，因为图像处理系统可以对这两个像素的颜色进行比较以便确定是否存在高对比度区域。然而，本发明的其他实施例针对像素数目可以具有不同的阈值，其中所述像素在确定帧缓冲器中存在足够信息量之前具有初始颜色。例如，本发明的一个实施例可以等待直到帧缓冲器内的每个像素具有初始颜色。

像素的初始颜色可以是由初始射线与三维场景内的对象的相交或者初始射线与三维场景的背景的相交所确定的颜色。因此，初始颜色可能不是像素的最终颜色。可以通过跟踪响应于初始射线与三维场景中的对象的相交所生成的所有辅助射线以及计算来自与这些辅助射线相交的对象对像素的颜色贡献来确定像素的最终颜色。此外，对最终颜色的确定还可以包括执行如下所述的利用附加射线的射线跟踪。上文针对图6描述的迭代的射线跟踪算法使得图像处理系统能够使用像素的初始颜色来确定像素是否包含高对比度颜色，而不是等待像素的最终颜色来确定像素颜色是否是高对比度的。

通过使用像素的初始颜色来确定高对比度区域而不是等待直到像素的最终颜色，图像处理系统可以相对较早地在执行针对帧的射线跟踪的同时确定哪里存在高对比度区域。像素的初始颜色可以是对像素的最终颜色的好的近似，并且因此可以是对高对比度区域的好的指示。通过相对较早地确定哪里存在高对比度区域，图像处理系统可以在执行其他初始射线和/或辅助射线的射线跟踪的同时开始对帧的部分进行自适应抗锯齿。相对于在开始抗锯齿图像之前进行等待直到像素具有最终颜色而言，这种并行的抗锯齿和射线跟踪可以减少呈现抗锯齿的射线跟踪图像所需的时间。

如果在帧缓冲器中不存在足够的信息量，则图像处理系统可以继续执行射线跟踪操作并且更新帧缓冲器内的像素的颜色，直到在帧缓冲器内存在足够的信息量。如果帧缓冲器内存在足够的信息量，则图像处理系统可以前进到步骤920以识别高对比度区域。

为了识别高对比度区域，图像处理系统可以对帧缓冲器内的相邻像素进行比较并且确定相邻像素是否具有高对比度颜色。每个像素的初始颜色可以被存储在例如帧缓冲器内。因此，图像处理系统可以通过检查存储在帧缓冲器内的颜色信息来对像素的颜色进行比较。此外，根据本发明的实施例，在开始像素的颜色比较之前可以设置阈值对照。阈值可以限定可构成高对比度的两个像素之间的颜色差异程度。

如果被比较的像素的颜色的差异不超过阈值对照(即，颜色的区别没有达到构成高对比度的程度)，则图像处理系统可以移动或者前进到下一像素以将下一像素与该下一像素的相邻像素进行比较以确定这些像素是否具有高对比度颜色。通过前进到帧中的下一像素，当颜色比较表明像素不具有高对比度颜色时，图像处理系统有效地将所发出的经过像素的射线的数目限制为所发出的经过像素的初始射线的数目。

例如，在步骤920中，图像处理系统可以基于初始颜色来确定像素1015和像素1020不具有构成高对比度的颜色。因此，图像处理系统可以不将对应的区域识别为高对比度并且可以继续进行而不发出附加射线通过像素1015。相对于无论像素1015和像素1020之间的对比量如何都发出附加射线通过像素1015的抗锯齿图像处理系统而言，不发出附加射线通过像素1015的步骤使得抗锯齿图像处理系统的工作量的增加减到最小。

如果图像处理系统确定颜色的差异超过阈值(即，像素的颜色差异达到构成高对比度的程度)，则图像处理系统可以前进到步骤930以确定要发出到三维场景的附加射线的轨迹。可以确定附加射线的轨迹，使得它们可以给被比较的像素提供附加颜色信息，并且因此在高对比度区域中提供抗锯齿。可以基于被比较像素的位置和所发出的通过被比较像素的初始射线的轨迹来确定附加射线的轨迹。

例如，可以发出附加射线，使得它们经过可以较好地区分锯齿影响可能最突出之处的像素颜色的点处的像素。例如，如果两个像素具有的颜色的不同足以构成高对比度，则图像处理系统可以发出更多的射线到三维场景，其靠近或者沿着被比较的两个像素的边缘。此外，图像处理系统可以发出附加射线行进通过先前发出的初始射线没有经过的像素内的点。通过确定最可能存在锯齿的区域中的每个像素的最终颜色，这些轨迹可以得到更好的抗锯齿。

例如，在步骤920图像处理系统可以确定像素1025和像素1030具有的初始颜色的不同足以达到构成高对比度的程度。因此，在步骤930中，图像处理系统可以确定要发出到三维场景的附加射线的轨迹，以便确定像素1025和像素1030的最终颜色。例如，图11说明了三个点，通过这些点图像处理系统可以发出三条新的射线到三维场景。这三个新的点在图11中示为在像素1025和像素1030二者内或边缘的阴影圈，而初始射线经过的点在图11中示为不带阴影的圈。附加射线(例如，射线1105、射线1110和射线1115)的轨迹可以是使得它们经过这些新的点并且进入三维场景。

在确定附加射线的轨迹之后，图像处理系统可以前进到步骤940，以发出附加射线到三维场景。接着，图像处理系统可以执行针对附加射线的射线跟踪操作以便确定附加射线是否可以与三维场景内的对象相交。与附加射线相交的对象可以帮助更精确地确定高对比度像素(例如，像素1025和像素1030)的最终颜色。与附加射线相交的对象(以及与响应于附加射线和对象的相交而生成的辅助射线相交的对象)的颜色可以例如和与初始射线(以及响应于对象和初始射线的相交而生成的辅助射线)相交的对象的颜色进行组合或平均。这种对每个像素的颜色的平均可以帮助更加精确地确定像素(例如，像素1025和像素1030)的最终颜色并且可以减少最终呈现的图像中的锯齿失真。

图像处理系统可以在发出附加射线到三维场景之前识别所有的高对比度区域，或者在图像处理系统正在针对高对比度颜色评估其他区域(像素)时，图像处理系统可以针对所识别的高对比度区域发出附加射线到三维场景。

例如，在发出附加射线到三维场景之后或同时，图像处理系统可以前进到帧中的下一像素。于是，图像处理系统可以评估帧中的下一像素，以便通过评估下一像素和该下一像素的相邻像素是否具有高对比度颜色来确定在三维场景中是否存在另外的高对比度区域。

通过检查存储在帧缓冲器中的每个像素的初始颜色来确定高对比度区域和仅发出附加射线到高对比度区域，图像处理系统可以呈现抗锯齿的图像，同时维持相对减少的工作量。工作量的减少是与下面的抗锯齿射线跟踪图像处理系统相比而言的：该系统可以发出附加射线通过帧中的每个像素而不是仅具有高对比度的帧区域中的像素。

针对减少发出的射线的自适应子采样

如上文所描述的，由射线跟踪图像处理系统发出到三维场景的射线的数目与图像处理系统经历的工作量直接相关。越多的射线被发出到三维场景，则射线跟踪图像处理系统经历的工作量越大。因此，发出到三维场景的射线的数目的任何减少可以减少射线跟踪图像处理系统经历的工作量并且可以减少从三维场景呈现二维图像所必需的时间，因此提高性能。当结合系统(例如，视频游戏系统)使用图像处理系统来提供需要每秒呈现多个帧(例如，每秒60帧)的动画时，可能期望减少呈现二维图像所必需的时间。然而，减少发出到三维场景的射线的数目的副作用可能是降低图像处理系统呈现的最终图像的质量。

然而，根据本发明的一个实施例，可以在维持最终图像的质量的同时减少射线跟踪图像处理系统经历的工作量。通过减少发出到具有相对较低的对比度的三维场景区域的射线的数目，同时维持发出到具有相对较高的对比度的三维场景的射线的数目。这可以称为自适应地对低对比度区域中的三维场景进行子采样以减少初始发出的射线的数目。可以减少发出到低对比度区域的射线的数目而不降低质量，因为相对于初步射线所确定的颜色而言，发出附加射线通过低对比度区域的像素对像素的颜色的改变可能是微小的(不可觉察的)。通过维持发出到不具有低对比度的三维场景区域的射线的数目同时减少发出到低对比度区域的射线的数目，可以维持射线跟踪图像处理系统呈现的图像质量，同时减少图像处理系统经历的工作量。

图12是说明根据本发明一个实施例的在自适应地对具有低对比度的三维场景区域进行子采样的同时执行射线跟踪的示例性方法1200的流程图。方法1200可以开始于步骤1205，在该步骤中图像处理系统可以发出多条初步射线到三维场景。这些初步射线可以被图像处理系统用于确定帧内的像素的初始颜色。根据本发明的一个实施例，图像处理系统可以针对每个像素发出单条初步射线到三维场景。

例如，图13说明了一系列像素1305，图像处理系统可以发出多条初步射线通过这些像素。图13还说明了，可以从其发出射线的观察点1300以及可由图像处理系统(例如，由工作量管理器205)发出的示例性初步射线(在图13中示为虚线箭头)。在一系列像素1305中的5个像素(即，像素1315、1320、1325、1330和1335)可以是一起组成帧的较大的像素栅格(例如，图4的栅格430)的一部分。在图13示出的每个像素(即，像素1315、1320、1325、1330和1335)内是初步射线所经过的示例性的点1340。

接下来在步骤1210中，图像处理系统可以执行初步射线的射线跟踪来确定帧内的每个像素的初始颜色。这可以包括例如(例如，利用工作量管理器205)使得初步射线遍历具有表示三维场景内有界体积的节点的空间索引，(例如，利用矢量吞吐量引擎210)执行利用初步射线的射线-图元相交测试，以及(例如，利用矢量吞吐量引擎210)更新对应于与初步射线相交的三维场景内的对象的像素的颜色。图像处理系统可以通过将颜色信息保存在例如帧缓冲器中来更新像素的颜色。帧缓冲器可以是二维存储器空间(例如，在存储器高速缓存110或者其他合适的存储器设备内)，其中可以存储针对帧内的每个像素的颜色信息。

一旦帧缓冲器中存在足够的信息量，图像处理系统就可以识别低对比度区域。足够的信息量可以是这样的信息量，其可以允许图像处理系统确定三维场景内是否存在低对比度区域。例如，两个像素可以构成用于确定是否存在低对比度区域的足够的信息量，因为图像处理系统可以对这两个像素的颜色进行比较以便确定这些像素是否包含低对比度颜色。然而，本发明的其他实施例针对像素数目可以具有不同的阈值，其中所述像素在确定帧缓冲器中存在足够的信息量之前具有初始颜色。例如，本发明的一个实施例可以等待直到帧缓冲器内的每个像素具有初始颜色。

像素的初始颜色可以是由初始射线与三维场景内的对象的相交或者初始射线与三维场景的背景的相交所确定的颜色。因此，初始颜色可能不是像素的最终颜色。可以通过跟踪响应于初始射线与三维场景中的对象的相交所生成的所有辅助射线以及计算来自与这些辅助射线相交的对象对像素的颜色贡献来确定像素的最终颜色。此外，对最终颜色的确定还可以包括执行如下所述的利用附加射线的射线跟踪。上文针对图6描述的迭代的射线跟踪算法使得图像处理系统能够使用像素的初始颜色来确定像素是否包含低对比度颜色，而不是等待像素的最终颜色来确定像素颜色是高对比度的还是低对比度的。

通过使用像素的初始颜色来确定低对比度区域而不是等待直到像素的最终颜色，图像处理系统可以相对较早地在执行针对帧的射线跟踪的同时确定哪里存在低对比度区域。这是因为辅助射线对像素的颜色贡献相对较小的改变量，并且因此像素的初始颜色可以非常接近像素的最终颜色。通过相对较早地确定哪里存在低对比度区域，图像处理系统可以相对较早地在射线跟踪过程中确定哪里需要发出附加射线，由此减少用于呈现图像的总时间。

如果在帧缓冲器中不存在足够的信息量，则图像处理系统可以继续执行射线跟踪操作并且更新帧缓冲器内的像素的颜色，直到在帧缓冲器内存在足够的信息量。

一旦在帧缓冲器中存在足够的信息，图像处理系统就可以前进到步骤1215，在该步骤中图像处理系统可以例如通过对帧内的相邻像素的颜色进行比较来识别帧内的低对比度区域。每个像素的初始颜色可以被存储在例如帧缓冲器中。因此，图像处理系统可以通过检查存储在帧缓冲器内的颜色信息来对相邻像素的颜色进行比较。关于像素是否具有低对比度颜色的确定可以基于阈值颜色差异。阈值颜色差异可以限定在像素的颜色仍被认为是低对比度的情况下两个像素的颜色之间的最大差异量。如果两个像素具有相同或者相似(在阈值差异所确定的范围内相似)的颜色，则图像处理系统可以将对应的帧区域识别为低对比度并且移动到评估帧的其他区域(像素)以确定是否存在其他低对比度区域。

图像处理系统可以在进入步骤1220之前识别所有的低对比度区域，或者可以在图像处理系统正在检查帧内的其他区域的颜色时进入步骤1220。在步骤1220处，图像处理系统可以基于前面的对低对比度区域的识别来确定像素是否在低对比度区域中，如果是这样，则图像处理系统可以前进到步骤1225，在该步骤中可以基于利用初步射线执行的射线跟踪(例如，与初步射线相交的对象或者与根据初步射线与对象/图元的相交而生成的辅助射线相交的对象)来确定像素的最终颜色。通过在不发出附加射线到场景的情况下确定低对比度区域中的像素的最终颜色，图像处理系统可以减少图像处理系统所经历的工作量。这种工作量的减少是与下面的射线跟踪图像处理系统相比而言的：该系统无论两个像素是否包含低对比度颜色都可以针对每个像素发出恒定数目的射线到三维场景(例如，可以针对每个像素发出不止一条射线的系统)。此外，通过针对包含低对比度的像素不发出附加射线到场景，图像处理系统没有降低呈现的图像的质量，因为发出附加射线对低颜色对比度区域中的图像质量只有微小的(不可觉察)的提高。

然而，如果图像处理系统在步骤1220处确定像素不在低对比度区域中，则图像处理系统可以前进到步骤1230以发出附加射线通过像素以及基于初步射线和附加射线来确定像素的最终颜色。图像处理系统可以通过对初步射线碰到的颜色、在初步射线与对象相交之后生成的辅助射线碰到的颜色和附加射线碰到的颜色进行组合来确定非低对比度区域中的像素的最终颜色，其中辅助射线在附加射线与对象相交之后生成。

图像处理系统可以在步骤1230处发出附加射线到三维场景以更加精确地确定非低对比度区域中的像素的最终颜色。通过针对不具有相同或相似颜色的像素发出附加射线到三维场景，图像处理系统呈现的图像不会损失非低对比度区域中的质量。在发出附加射线到三维场景之后，图像处理系统可以开始利用附加射线执行射线跟踪以确定附加射线对像素的附加颜色贡献。

例如，图14说明了一系列像素1305中的5个像素(1315、1320、1325、1330和1335)。图14还说明了(经由每个像素内的无阴影的圈和虚线箭头)图像处理系统先前发出单条初步射线以经过一系列像素中的每个像素(例如1340)。在步骤1210处，图像处理系统可能已经针对这些初步射线执行了射线跟踪，确定了初步射线与三维场景的对象或背景相交，并且利用基于这些相交的初始颜色信息更新了帧缓冲器。

在利用五个像素(1315、1320、1325、1330和1335)的初始颜色信息更新了帧缓冲器之后，图像处理系统可以开始方法1200中的一系列步骤以便确定像素是否包含低对比度颜色(即，相同或类似的颜色)。如果它们不包含相同或类似的颜色，则图像处理系统可以发出附加射线到三维场景以进一步确定一系列像素1305内的像素的颜色。

例如，图像处理系统可以通过利用初步射线执行射线跟踪来确定像素1315和像素1320具有相同或类似的颜色，因此图像处理系统可以只基于初步射线确定像素1315和像素1320的最终颜色而不需要发出附加射线通过像素。类似地，图像处理系统可以确定像素1320和像素1325具有相同或类似的颜色，因此不需要发出附加射线通过像素1320和像素1325以便确定它们的最终颜色。

然而，在此期间图像处理系统可以在步骤1215处确定像素1330和像素1335不具有相同或类似的颜色。因此，图像处理系统可以发出附加射线通过像素1330和像素1335。在图14中通过实线箭头示出了示例性的附加射线，并且在图14中通过阴影圈示出了附加射线经过像素1330和像素1335的附加点的示例性模式。

附加射线的轨迹可以使得附加射线给像素提供附加颜色信息。因此，附加射线的轨迹可以使得附加射线经过与初步射线不同的像素点，如图14所示。

附加射线可以帮助更精确地确定像素1330和像素1335的颜色，其可以维持图像处理系统呈现的图像的质量。

结论

根据本发明的一个实施例，通过增加所发出的通过具有高对比度颜色的相邻像素的射线的数目同时维持所发出的通过不具有高对比度颜色的相邻像素的射线的数目，射线跟踪图像处理系统可以呈现抗锯齿的图像同时最小化图像处理系统所经历的工作量的增加。另外，根据本发明的另一实施例，通过维持所发出的通过具有低对比度颜色的相邻像素的射线的数目同时增加所发出的通过不具有低对比度颜色的相邻像素的射线的数目，图像处理系统可以减少在执行射线跟踪时经历的工作量，同时维持所呈现的图像的质量。

尽管上文针对本发明的特定实施例，但是在不偏离本发明的基本范围的情况下可以设计本发明的其他的和另外的实施例，并且本发明的范围由所附权利要求确定。

Claims (14)

1.一种通过执行具有自适应抗锯齿的射线跟踪呈现三维场景的图像的方法，包括：

基于发出到所述场景的初始的一组射线来识别像素的高对比度区域；以及

发出附加的一组射线到一个或多个所述高对比度区域。

2.根据权利要求1所述的方法，其中附加射线仅被发出到高对比度区域。

3.根据权利要求1所述的方法，其中基于初始的一组射线来识别像素的高对比度区域包括：

发出初始射线，其经过相邻像素并且进入三维场景；

通过利用所述初始射线执行射线跟踪来确定所述相邻像素的初始颜色；以及

对所述相邻像素的初始颜色进行比较以便确定所述初始颜色是否是高对比度的。

4.根据权利要求3所述的方法，其中发出附加的一组射线到一个或多个所述高对比度区域包括：

发出至少一个附加射线到所述三维场景，其经过所述相邻像素中的至少一个；

利用所述附加射线执行射线跟踪；以及

通过对所述相邻像素中的所述至少一个的初始颜色和基于利用所述附加射线执行射线跟踪的结果得到的对该相邻像素的颜色贡献进行组合来确定该相邻像素的最终颜色。

5.根据权利要求3所述的方法，其中确定相邻像素的初始颜色包括：

发出第一初始射线到所述三维场景，其中所述第一初始射线经过所述相邻像素中的第一像素；

利用所述第一初始射线执行射线跟踪以确定所述第一像素的初始颜色；

发出第二初始射线到所述三维场景，其中所述第二初始射线经过所述相邻像素中的第二像素；以及

利用所述第二初始射线执行射线跟踪以确定所述第二像素的初始颜色。

6.根据权利要求5所述的方法，其中确定所述相邻像素的所述初始颜色是否是高对比度的包括：

对所述第一像素的初始颜色和所述第二像素的初始颜色进行比较；以及

如果所述第一像素的初始颜色和所述第二像素的初始颜色的差异程度超过了颜色阈值，则所述第一像素的初始颜色和所述第二像素的初始颜色是高对比度颜色。

7.根据权利要求4所述的方法，其中所述至少一个附加射线的轨迹是基于所述相邻像素的位置确定的。

8.根据权利要求7所述的方法，其中所述附加射线经过所述第一像素中靠近所述第一像素和所述第二像素的边界的点。

9.一种包含程序的计算机可读介质，该程序在被执行时，完成用于实现根据权利要求1-8中任意一项所述的方法中的步骤的操作。

10.一种图像处理系统，包括：

存储器设备，其被配置为存储像素帧中的每个像素的颜色信息；以及

处理单元，其被配置为基于发出到三维场景的初始的一组射线来识别像素的高对比度区域，以及发出附加的一组射线到一个或多个所述高对比度区域。

11.根据权利要求10所述的图像处理系统，其中附加射线仅被发出到高对比度区域。

12.根据权利要求10所述的图像处理系统，其中所述处理单元通过以下步骤实现基于初始的一组射线来识别像素的高对比度区域：

发出初始射线，其经过相邻像素并且进入所述三维场景；

通过利用所述初始射线执行射线跟踪来确定所述相邻像素的初始颜色；

将所述初始颜色存储在对应于所述相邻像素的存储器设备内的存储器位置中；以及

对所述相邻像素的初始颜色进行比较以便确定所述初始颜色是否是高对比度的。

13.根据权利要求12所述的图像处理系统，其中发出附加的一组射线到一个或多个所述高对比度区域包括：

发出至少一个附加射线到所述三维场景，其经过所述相邻像素中的至少一个；

利用所述附加射线执行射线跟踪；

通过对所述相邻像素中的所述至少一个的初始颜色和基于利用所述附加射线执行射线跟踪的结果得到的对该相邻像素的颜色贡献进行组合来确定该相邻像素的最终颜色；以及

将所述相邻像素中的所述至少一个的所述最终颜色存储在所述存储器设备内的对应的存储器位置中。

14.根据权利要求13所述的图像处理系统，其中所述至少一个附加射线的轨迹是基于所述相邻像素的位置确定的。

Images