《用于光线跟踪中的图元相交的系统和方法》由会员分享，可在线阅读，更多相关《用于光线跟踪中的图元相交的系统和方法（6页珍藏版）》请在金锄头文库上搜索。
1、用于光线跟踪中的图元相交的系统和方法专利名称：用于光线跟踪中的图元相交的系统和方法用于光线跟踪中的图元相交的系统和方法相关串请的交叉应用本申请要求2010年4月29日递交的、标题为“SYSTEMS AND METHODS FOR PRIMITIVE INTERSECTION IN RAY TRACING” 的美国临时专利申请号 61/329，265 的优先权并且为了一切目的通过参考的方式将该申请整体并入本文。技术领域下文概括而言涉及例如在渲染3D场景的2D表示时可以使用的光线跟踪系统，并且更具体而言涉及用于测试光线与表面的相交的方法(“相交测试”)的改进。背景技术：利用光线跟踪来从3D场景描述
2、渲染照片级的2D图像是在计算机图形领域公知的。光线跟踪通常涉及获得由几何形状构成的场景描述，其描述场景中的结构的表面，并且可以被称为图元。常见的图元形状是三角形。从观察点(“照相机”)将虚拟光线跟踪成场景；发出每个光线以传播经过2D表示的相应像素，该光线可能对该2D表示具有影响。测试光线与场景图元的相交，以便确定每个光线的最靠近的相交图元(如果有的话)。在确定给定光线的相交之后，与该图元相关联的着色器确定接下来发生什么。例如如果该图元是镜子的一部分，则发出反射光线以确定光是否从光源击中相交点，或者在更复杂的情况中，表面下反射，以及散射可以被建模，这可能导致相交测试出不同光线的发出。作为另一个实
3、例，如果对象的表面粗糙而不平滑，则该对象的着色器可以发出光线来建模该表面上的漫反射。这样，找到光线与图元之间的相交是在确定是否以及什么类型的光能量可以借助给定光线到达像素时的步骤。当发现图元与光线相交，并且要执行用于该相交的着色器时，基于在该图元上发现相交的位置来定义光线的相交点。该相交点可以作为当对该相交着色时着色器可以投射的子光线的原点。用于检测光线与表面之间的有效相交的算法仍然希望得到改进。图I描述了在定义要渲染的场景中的对象或表面时可以使用的多个三角形图元的基于顶点的表不的实例；图2描述了这样一种情况，在该情况中，在光线与特定表面(例如由图元定义的表面)的相交测试期间，取决于正在进行相
4、交测试的表面与光线的相对方向，光线和边缘的相对位置可以夹在该表面的不同侧上；图3描述了一种过程，通过该过程基于使用几何图元的边缘的相交测试过程来测试该几何图元与光线的相交；图4和图5描述了一种情况，其中由多个图元共用相同的边缘，并且用于定义该边缘的顶点的重新排序使得沿一致的方向或者根据场景范围内的规矩来测试该边缘；图6描述了一种通过使用顶点对中的顶点的相对位置来确定一致方向的方法；图7描述了用于确定定义了边缘的顶点的相对优先级(precedence)或方向的总体过程；图8描述了可以生成的数据结构并且该数据结构包括可用于一致地定向在相交测试期间使用的边缘的信息；图9描述了可以在其中实施本文所述的
5、方案的系统；以及图10描述了在本文所公开的方案的实施中可以使用的示例性系统构造。具体实施方式下文主要涉及使用光线跟踪作为渲染3D场景的2D表示的机制。通常由设计内容如视频游戏、运动图像、动画广告、工业模型、架构特征(如建筑物)等等的艺术家创建(指定)要渲染的3D场景。艺术家可以是人或使用创作工具的人或者甚至可以自身主要是由软件驱动的。为了产生表不3D场景的内容,艺术家面临大量挑战。一方面,艺术家描述场景和在其中的对象的边界(表面)。这种物理边界的描述可以很详细。例如使用计算机辅助设计(CAD)设计的汽车的有用的模型需要汽车的组件的精确的规格以及它们彼此的空间关系。艺术家还描述场景对象的表面应该
6、看起来如何和如何工作。例如，汽车的准确的模型应该将窗户玻璃表示得与前灯玻璃不同、与涂漆面不同。例如在视频游戏中，艺术家将皮肤表面建模得与头发表面不同，诸如此类。因此，在渲染领域中采用的一种构想是提供物理场景模型，并且将表面信息与该场景模型的不同部分相关联。例如，场景模型可以包含对象，该对象包括人、车辆和建筑物。 场景的物理模型将这些对象的表面描述为例如线框模型，其可以包括大量彼此互相连接的图元形状以描述表面的边界。该物理模型通常缺少关于物体的表面的视觉外观的信息。然后，将信息和编程与特定表面和/或描述它们的外观的特定表面的部分相关联。该信息可以包括表面的纹理，而与该表面相关联的编程通常意在对光
7、打在该表面上时该表面具有什么效果进行建模。例如，编程使得能够对玻璃、闪亮表面、起伏表面等等进行建模。因此将该编程和信息与描述那些表面的物理模型的部分捆绑或相关联。例如，可以将编程与特定图元相关联或捆绑。对于特定图元或场景对象的这种编程和其他描述或它们的一部分可以一般性地称为用于该图元或对象的“着色器”。为了清楚起见，下文的描述主要使用由简单平面形状(如三角形)的网格表示被渲染的场景对象的实例。但是，可以利用其他方法，如参数方法，如贝塞尔补丁来描述可以执行相交测试的对象。在由该方法(例如图元的网格)定义表面(如对象的表面)的场景中，可以测试光线的相交。可以通过使用多种相交测试中的任意一种，如重心
8、坐标测试或 Mdller-Trumbore算法来确定光线与图元(例如三角形)之间的相交。通常以浮点进行这种测试。所有浮点计算具有有限的精度并且仅可以表示特定数字。因此，不考虑浮点测试中使用的精度，结果的表示中的不准确是不可避免的。在场景中可以相交的图元和其他对象还“存在”于3空间位置处。因此，光线、这些场景表面以及它们之间的相交点存在于该场景中不能由给定精度的数字精确地表示的点处。不管使用单还是双精度浮点(或者甚至一些更精确的数字内插)都是这种情况，因为计算机仅有将数字表示到有限的精度的能力。至少出于数字表示的精度越高则表示该数字所需要的数据越多的实际原因来说也是这样。当处理复杂场景时，需要额
9、外的信息字节来表示场景中的每个顶点可能导致对于该场景数据需要数十或数百兆字节的额外存储。在光线相交测试的情况中，所导致的一种不准确是光线与图元之间的击打点可能不准确。当发现光线与表面相交时，可以使用该表面与该光线之间的相交点作为投射其他光线的原点。但是，可能并不总是检测到的光线与表面之间的每个相交都是感兴趣的相交在场景空间中可以使用特定精度的浮点tuplet例如单精度或双精度来表示相交点。如本领域的普通技术人员已知的,可以生成相交点的重心坐标和相交距离。可以根据在边缘测试期间计算的“体积”来找到重心坐标。这些坐标被称为U、v和W。坐标的和还可以提供“d”的值，也可以通过考虑光线方向与三角形法线
10、的点积来计算“d”。可以对输出的重心坐标进行归一化以使得un+vn+wn = I (例如un = u/d, vn = v/d,wn_w/d)。通常仅需要输出两个重心坐标u和V，因为第三个坐标是冗余的。由于浮点数字表示和浮点计算的属性，光线与三角形图元(并且更普遍地两个或更多个相邻图元可能共用一个边缘的任意图元)的相交测试的结果可能取决于给定测试中所涉及的光线和对象的相对方向。一种特定的情形是在多个图元共用一个边缘处例如两个三角形共用一个边缘处。有时候，在相交测试期间可能在该边缘处“发现”实际上并不存在的裂缝。下文的公开内容的一些方面涉及降低该光线相交测试期间这种类型的伪像。总言之，相交点(子光
11、线的原点)抽象地表不确定已与光线相交的表面上的一个点，并且理想地将作为由于着色而导致的新光线的确切原点。但是，仅可以将该点表达到有限的精度，因为计算机以有限的精度表示真实数字。当实现这些模型时，该不精确可能导致不准确和视觉伪像。因此，所存储的用于描述该点的数据可能并且确实经常具有误差，该误差使得相交点偏离所相交的场景(图元)的表面。图I描述了可以针对与光线20的相交而测试的几何图形的示意性实例。所描绘的几何图形可以由在大量顶点之间确定的边缘组成。所描绘的顶点包括顶点I到7。当然在所描绘的7个顶点之间可以画出各种各样的边缘，并且可以强制哪个顶点将由边缘连接的规矩。可以例如部分地基于顶点的列表次序
12、(例如列表次序可以是存储多个顶点的次序) 来确定该规矩。因此如图所示，连接顶点I和顶点2 ;依次连接顶点2和3 ;并且可以由一个边缘将顶点3连接到顶点I来形成闭合形状从而定义三角形10。为了降低存储空间要求， 可以使用三角形条带，三角形条带使得能够使用附加顶点与以前的顶点一起定义附加图元 (例如三角形)。在这里，接下来增加顶点4并且产生了三角形11。描述了盘绕次序(WO) 22和盘绕次序(WO) 23 ;盘绕次序通常随着条带中的每个附加图元而改变。在定义图元的法线时可以使用盘绕次序。通常，图元典型地被认为具有可以由“右手法则”定义的法线，手指按照所考虑的图元的盘绕次序并且大拇指指向法线方向。图
13、I描述了该附加图元(基于顶点5和6增加三角形12和13)。图I还描述了6可以由其他机制如三角形条带或其他方法定义附加图元。具体而言，增加顶点7，并且顶点 7与顶点I和3结合形成三角形15，三角形15被描述为具有盘绕次序24。因此，在三角形 10与三角形15之间共用边缘25。如果边缘25被用于按照盘绕次序22所定义的来测试三角形10并且按照盘绕次序24所定义的来测试三角形15，则在三角形10与三角形15之间将沿不同方向测试边缘25。更普遍地，可以用各种各样的方式定义要进行相交测试的场景几何图形。在边缘存在于两个几何图形元素之间的情况中，本文所述的方案的实现使得能够沿相同的方向测试边缘。边缘可以是
14、两个顶点之间的直线或者包括任意数量的控制点的任意曲线。为了说明清楚起见，将边缘分别描绘和描述为由两个顶点定义的线段。但是，该说明不是限制性的。图2描述了边缘25与光线20。鉴于浮点中固有的有限精度，光线20与边缘25的两个示例性的可能的交叉点30和31 (即在3D空间中随着光线20靠近边缘25，至少部分地取决于浮点算术，可以确定光线20在边缘25的任意一侧通过边缘25)。具体的相交测试方法可以具有该基于边缘的测试的不同的实现。但是在原型的实例中，该测试确定在由被测试的图元的顶点定义的平面内该光线在边缘25的哪一侧。该光线交叉点30和31都不能表示“实际的”点。但是通过沿相同的相对方向或朝向对边
15、缘25进行测试，每当在图元测试中使用时，任意不准确变得更加一致。使得潜在的不准确更加一致就使得异常更不可能。该公开内容公开了可用于使得沿一致的方向测试该边缘的各种各样的方法。一个实例是建立用于在两个顶点之间进行区分的全场景的规矩，以便识别给定边缘(其可以是线段或复杂曲线)的“开始”和“结束”。全场景的规矩的一个实例是建立这样一种规矩，在该规矩中将基于一个边缘两端的两个顶点的相对位置来给定该边缘的方向。该相对位置使用的一个实例是(I)基于哪个顶点沿在X坐标中具有更大(更小)的值来排序端接顶点； 如果在X中相等，则在Y中排序；如果在Y中相等，则在Z中排序。作为被测试的坐标平面的排序，XYZ坐标平面
16、是示例性的。该实现是为了建立用于对场景进行测试要遵守的规矩(该规矩可以随着场景而改变，只要在相同的规矩下测试相同的边缘，但是为了清楚起见，假设一旦建立了该规矩就将遵守该规矩。)参考图3来描述可以在其中实施该方法的环境。图3描述了顶点数据的源50以及图元定义数据的源52。根据该数据源，对将要被用作为到相交测试的输入的边缘的定义定义为54 (例如如针对图I所述的)。在测试该边缘之前，基于定义要测试的边缘的末端的顶点之间建立的优先级来定向(56)边缘。此后，测试(58)该边缘。在一些情况中，该边缘测试的结果可能指示无法与被测试的图元(例如图元15的测试边缘25)相交。如果这样， 那么可以测试(64)下一个图元，可以从源52获得该下一个图元的图元定义数据。但是，如果不能确定没有相交，则仍然不能确定肯定的相交(例如因为有更多边缘待测试)，并且因此，可以进行测试以确定是否有更多边缘待测试(62)。如果不是，那么测试(64)下一个图元。如果仍
