CN117178297A - 微网格，用于计算机图形的结构化几何体 - Google Patents

Abstract

提供了一种μ‑网格(“微网格”)，它是一种几何体的结构化的表示，它利用连贯性来实现紧凑性，并利用其结构来实现具有内在细节级别的高效渲染。微网格是一种规则网格，沿其周边具有二的幂数量的片段，并且其可以覆盖在几何图元的表面上。微网格用于提供使用微网格上感兴趣点的重心坐标能访问的可见性掩模和/或位移映射。

Description

微网格，用于计算机图形的结构化几何体

相关申请的交叉引用

本申请要求2021年9月16日提交的美国临时专利申请第63/245,155号的优先权，其全部内容通过引用并入本文。此外，同时提交的美国申请第17946221(6610-124)号“加速实时光线追踪的三角形可见性测试(Accelerating Triangle Visibility Tests forReal-Time Ray Tracing)”、美国申请第17946515(6610-125)号“用于光线和路径追踪的位移微网格(Displaced Micro-meshes for Ray and path Tracing)”和美国申请第17946563(6610-129)号“位移微网格压缩(Displaced MicroMesh Compression)”中的每个申请的全部内容通过引用并入本文。

技术领域

本技术涉及计算机图形学，并且更具体地涉及有效地存储和访问用于渲染的场景信息。

背景技术

计算机图形系统的设计者继续希望能够大大增加渲染场景中的几何细节级别。在当前可用的渲染系统中，场景由数百万个三角形组成。为了大幅增加细节级别，例如，增加到数十亿个三角形，所涉及的存储成本和处理时间将需要增加对应的因素。

光线追踪是一种众所周知的渲染技术，以其真实感和以非常大、复杂的场景的对数缩放而闻名。然而，光线追踪在创建必要的数据结构(例如包围体层次结构(BVH))和附加几何体的存储方面存在线性成本。光栅化需要线性处理时间以及线性存储要求。一些其他系统，例如虚幻引擎的Nanite^TM，在适度的内存占用中支持高层次的几何细节，并且还可以创建多个级别的细节作为其场景描述的一部分。然而，这些系统需要大量的预处理时间步骤并生成刚性模型，无法支持动画或在线内容创建。Nanite的表示不太适合光线追踪，因为它需要昂贵的(时间和空间)辅助BVH数据结构，此外还需要解压缩其专门的表示。

因此，需要进一步改进用于存储和渲染非常详细的场景的技术。

附图说明

图1A和图1B示出了根据一些实施例的μ-网格的示例。图1A示出了三角形μ-网格，而图1B示出了四边形μ-网格。

图2示出了根据实施例的应用于μ-网格的可见性掩模(VM)。

图3示出了根据实施例的位移映射(DM)和关联的位移μ-网格。

图4A、4B和4C示出了根据示例实施例的位移映射(map)和可见性掩模在μ-三角形上的示例应用。图4A示出了示例位移映射的μ-三角形。图4B示出了示例可见性掩模的μ-三角形。图4C示出了由组合的位移映射和可见性掩模定义的μ-网格。

图5示出了根据实施例的示例μ-网格，其具有顶点、边和面，沿周界和孔具有开放边。

图6A和6B分别示出了根据实施例的T形接头和可出现在μ-网格中的对应孔。

图7A和7B示出了根据实施例应用了均匀μ-网格分辨率的斯坦福的兔子(StanfordBunny)。

图8A和8B示出了根据一些实施例的边抽取控制和分辨率传播的减缓。

图9A-9C示出了根据一些实施例的归约的分辨率控制。图9C示出了没有归约的场景。图9B示出了具有底部抽取的场景。图9A示出了具有底部和侧面抽取的场景。

图10A-10B示出了根据一些实施例的可以在μ-网格中发生的示例T形接头场景。

图11A-11C示出了根据一些实施例的三个T形接头三角形的示例处理。

图12A-12B示出了根据实施例的渲染为高度场的位移映射(DM)。

图13A-13D示出了根据一些实施例的线性和归一化内插位移向量的示例。

图14A-14B示出了根据一些实施例的与棱柱体规格相比的基础和位移。

图15示出了根据一些实施例的零-三角形加位移向量规格。

图16示出了根据一些实施例的显示μ-网格统计与分辨率和DM存储器大小与位移位-深度的表格。

图17A-17B分别示出了根据一些实施例的示例叶图像和相应的1-位可见性掩模(VM)。

图18A和18B示出了根据一些实施例的图17A的叶图像的不同分辨率的2-位VM示例。

图19A-19B示出了根据一些实施例的图18B中所示的VM的两种解释，一种三态(图19A)和一种二态(图19B)。

图20A-20B示出了根据一些实施例的示例半透明苔藓纹理，具有上方阴影掩模(二态)和下方半透明图(三态)。

图21示出了根据一些实施例的镜像建模的示例。

图22示出了根据一些实施例的四个示例VM。

图23A-23B以图形方式示出了根据一些实施例的如何在正方形(图23A)和三角形域(图23B)上描绘四叉树。

图24-25示出了根据一些实施例的基于四叉树的编码方案，其中树的节点紧凑地描述图像。

图26A-26B示出了希尔伯特(Hilbert)遍历顺序(图26A中所示)和莫顿(Morton)顺序(图26B中所示)的示例，莫顿顺序的连贯性低于希尔伯特遍历顺序，但计算成本较低。

图27示出了根据一些实施例的重心坐标和离散重心坐标。

图28示出了根据一些实施例的遍历顺序对不同分辨率的μ-网格的应用。

图29示出了根据一些实施例的图28中所示的递归遍历的伪代码。

图30示出了根据一些实施例的用于从层次结构中的n-1级中的顶点预测和校正n级中的顶点的伪代码，其中每个解码值成为下一级的预测源。图30中示出的公式被称为“公式1”。

图31-32示出了根据一些实施例的公式1中的预测(p)和参考值(r)之间的关系。

图33示出了根据一些实施例的在给定预测(p)、参考(r)、移位(s)和位宽(b)的情况下，在有限次数的运算中确定最佳校正(c)的技术的伪代码。

图34A和34B示出了由使用不同μ-网格类型编码的子三角形共享的边以及由具有不匹配的曲面细分率但相同μ-网格类型的子三角形共享的边的示例。

图35-37示出了根据一些实施例的参考值和预测值之间的差异分布的示例。

图38示出了根据一些示例实施例的用于访问可见性掩模或位移映射的过程的流程图。

图39示出了根据一些示例实施例的用于生成可见性掩模或位移映射的过程的流程图。

图40示出了根据一个或更多个实施例的被配置为创建和/或使用基于微网格的可见性掩模、位移映射等的示例计算机系统。

具体实施方式

非常高质量、高清晰度的内容通常非常连贯，或者局部相似。为了显著提高几何质量，示例实施例提供了μ-网格(也称为“微网格”)，它是几何体的一种结构化的表示，它利用连贯性来实现紧凑性(压缩)并利用其结构来实现具有内在细节级别(LOD)和动画的高效渲染。μ-网格结构可用于光线追踪，以避免大量增加包围体层次结构(BVH)构建成本(时间和空间)，同时保持高效的光线追踪。微网格的结构定义了一种内在的包围结构，其可以直接用于光线追踪，避免创建冗余的包围数据结构。当光栅化时，内在的μ-网格LOD可用于光栅化大小合适的图元。

μ-网格是规则网格，其沿其周边具有二的幂数量的多边形区域。本文的描述集中在将μ-网格表示为具有二的幂的μ-三角形(也称为“微三角形”)的网格。在一些示例实施例中，μ-网格可以是由μ-三角形的规则栅格组成的三角形或四边形，其中栅格维度是二的幂(1、2、4、8等)。图1A和1B示出了根据一些实施例的μ-网格的两个示意性示例。图1A示出了由64个μ-三角形102的栅格构成的三角形μ-网格104。图1B中的四边形网格106在几何上是三角形μ-网格阵列，其中用空心圆(“○”)110a-110f表示的顶点是隐含的，并且源自用实心圆(“●”)108a-108d表示的顶点。

μ-网格的定义是在它们的角处指定顶点位置，与可选的位移向量配对，这些位移向量与位移映射(DM)结合使用。可见性掩模(VM)也可以可选地与μ-网格相关联。在解释时，在一些实施例中，VM将每个关联的μ-三角形分类为不透明、未知或透明。图2显示了枫叶，其轮廓近似VM 202。在所示实施例中，完全被枫叶覆盖的μ-三角形是不透明的(例如204)，没有部分被枫叶覆盖的μ-三角形是透明的(例如206)，而部分被枫叶覆盖的μ-三角形是未知的(既不是不透明的也不是透明的)(例如208)。在一些其他实施例中，VM可以根据可见性状态的不同分类对各个μ-三角形进行分类。

在μ-网格和VM用于光线追踪的示例实施例中，区域202可以与在光线-三角形相交中测试的几何图元相对应。然后，该实现将基于覆盖在区域202上的μ-网格，识别交叉点(命中点)出现在其中的μ-三角形。然后可以使用识别的μ-三角形来计算索引以获得交点处的区域202的场景细节。例如，场景细节可以与对应于如图2所示的枫叶的掩模在所识别的μ-三角形处的特征有关。访问索引只需要覆盖几何图元202的μ-网格的内在参数化，而不需要描述主题三角形(例如，几何图元202)和要存储的主题三角形内的点之间的映射的附加数据。在示例实施例中，在示例实施例中计算索引所需的所有信息是(1)点或等效的小区域(例如，μ-三角形)位于μ-网格中的位置和(2)小区域有多大。这与需要消耗大量存储和带宽的纹理坐标的纹理映射等形成对比。换句话说，与需要纹理坐标等的方法相比，在示例实施例中，命中点的重心坐标直接用于访问掩模，从而避免了与附加坐标相关联的存储、带宽和内存延迟方面的附加成本，并提供对场景信息的更快访问。

DM包含每个μ-网格顶点的标量位移，用于偏移或位移μ-网格的μ-三角形的顶点。μ-网格顶点(有时简称为“μ-顶点”)位置和位移向量在网格面上进行线性插值，然后使用在DM中查找的插值位置、位移向量和标量位移来对μ-顶点进行位移。图3A和3B分别示意性地示出了与基三角形302相关的位移映射和关联的位移μ-网格。

与场景的相同区域相关联的VM和DM可以以可以彼此独立的不同分辨率存储。VM和DM的独立分辨率决定了它们关联的μ-网格的分辨率。因此，当同时指定DM和VM时，μ-网格可能有两种嵌套分辨率。具有相同顶点的两个μ-网格(例如，当它们属于同一几何图元202时)嵌套的意义在于低阶μ-网格的μ-三角形(例如，三角形μ-网格具有每边两个或2²个μ-三角形的数量级)可以被划分以形成更高阶μ-网格的μ-三角形(例如，三角形μ-网格每边具有四个或2⁴个μ-三角形的数量级)，因为两个μ-网格在维度上是二的幂。VM的分辨率通常高于DM。在这种情况下，DM以较粗糙的分辨率位移μ-三角形，然后VM控制位移后的μ-三角形内的μ-三角形的可见性。图4A、4B和4C分别示意性地示出了位移映射的μ-三角形、可见性掩模的μ-三角形和由组合的DM和VM定义的μ-网格。即，图4C所示的μ-网格同时应用了图4A中所示的位移映射和图4B中所示的可见性掩模。

μ-网格的网格、水密性和分辨率传播

复杂对象可以由多组μ-网格表示。要准确地表示一个对象或场景，对该对象或场景的描述是一致的非常重要。可以从检查三角形的网格开始。三角形网格由是三角形的顶点、边和面组成。网格的每条边恰好有两个入射三角形，除非它位于开放网格的周边或网格内部孔的边缘。位于开放网格周边或网格内部孔的边缘的每条边只有一个入射三角形，此处称为半边。图5以粗轮廓显示了半边。

顶点仅出现在边的端点处。结果，图6A中所示的配置表示具有孔(裂纹，例如图6B中所示)的网格并且被称为“T形接头”。顶点③似乎在边②④上，但边②③只有一个入射三角形(即三角形A)。没有定义三角形②③④，这会在μ-网格中引入不一致。一致的网格是一致渲染的先决条件。这种一致性通常被称为水密性。网格的水密采样(渲染)没有间隙、像素漏失或双重命中。

与μ-三角形的网格一样，μ-网格的网格也必须是水密的，以便提供一致的渲染。共享边上的顶点和那些顶点处的可选位移方向必须一致，在逻辑上相同的地方完全相等。共享边上的所有顶点都一致且完全相等的顶点网格可以称为μ-网格的网格的“基础网格”。对于VMμ-三角形的水密性，一致的基础网格就足够了。VMμ-三角形在重心空间中被定义，并且它们的水密性仅取决于一致的网格顶点。但是，在使用DM时，DMμ-三角形的网格也必须一致。例如，如果将μ-网格的网格替换为它们对应的DMμ-三角形，那么μ-三角形必须是一致的。

图7A-7B示出了捕获斯坦福兔子的μ-网格的网格，以及位移映射表面的渲染。请注意，图7A中的μ-网格的网格的所有面的分辨率是相同的，每个μ-网格沿其边具有八个片段(例如，八个μ-三角形)。这种分辨率的一致性是确保水密性所必需的。如果μ-网格的分辨率因网格而异，则可能会引入T形接头(如图6B所示的裂纹)。这种要求在用于表示对象或场景的μ-网格的网格中的所有μ-网格上具有相同分辨率的结果是，较小面积的μ-网格(例如)对于该较小空间区域可能最终具有非最佳数量的(太多)μ-三角形，和/或较大面积的μ-网格面可能最终有太低分辨率(例如，对于该较大的空间区域，μ-三角形太少)。

为了减轻这种繁重要求的影响，引入了降低的边分辨率标志。除了指定μ-网格的分辨率之外，还指定了图元的每个边的标志，以控制它是否被下采样(抽取)两倍。降低的边分辨率标志指示相邻面的分辨率是相同的还是低两倍。通过将边分辨率标志与两个邻居的较高分辨率相关联，不需要存储额外的数据。通过不需要完全通用的边分辨率规范，可以避免复杂且昂贵的拼接算法，以及非重心对齐的μ-三角形的处理。

图8A-8B示出了边抽取控制的行为。图8A示出了大的薄三角形802(第一图元或第一μ-网格)的高分辨率传播到相邻的较小三角形(第二图元或第二μ-网格)804-808，导致它们被过于密集地采样，或过采样。图8B示出了归约相邻的大三角形和较小三角形之间共享边的分辨率的效果。提升中心小三角形804的分辨率以匹配其较高分辨率邻居802的降低分辨率，但分辨率的增加是孤立的，因为可以抽取中心三角形804的其他两条边以匹配其两个邻居806和808的所需分辨率。

裂纹抑制替代方案

如已经描述的，图8A-8B提供了边抽取如何可以用于定义μ-三角形的水密网格，同时允许网格分辨率在整个μ-网格的网格上变化的一个示例。在抽取方案中，根据情况，将四个三角形的组替换为三个、两个或一个三角形。参见图9A-9C。图9A和图9B分别示出了图9C中所示的一组四个三角形被两个三角形和三个三角形替换。注意，在图9C的四个三角形被一个替换的情况下，仅当起始分辨率本身只是四个三角形时才会发生。

在边抽取的替代方案中，可以使用修改的线方程来确保相邻μ-网格之间的水密边界。在这种技术中，对应于μ-网格的三角形的线方程可用于计算光线(或像素中心)与该三角形的交点。当存在T形接头时，给定三角形的顶点并不完全位于它暗示位于的边上。图10A-10B示出了与单个三角形相邻的一组四个三角形，并且以夸张的方式示出了在由四个三角形一组的底部的三个三角形与其单个邻居共享的边的中心的顶点的位置。顶点AB将位于其形成T形接头的边上方或下方，这会留下间隙或双重命中(被访问两次的像素)。在上述使用抽取的解决方案中，沿该边的三个三角形被两个三角形代替，使得T形接头不再存在。在这个使用线方程的方案中，使用额外的/不同的线方程来避免间隙或双重命中。依次讨论三个三角形中的每一个。当处理三角形<A，CA，AB>时，使用边[A，CA]、[CA，AB]和[B，A]的线方程。通过使用方程[B，A]而不是[AB，A]，避免了<A，CA，AB>和[A，B，D]之间的任何间隙(图11A)。当处理中心三角形<CA，BC，AB>时，使用与这些顶点关联的三个常用线方程，并使用第四个线方程[B，A]进行扩充。如果由于量化或舍入而恰好延伸到边[B，A]以下，则第四个线方程会修剪掉中央三角形的尖端(图11B)。对于第三个三角形[AB，BC，B]，也使用了四个线方程：[B，A]、[AB，BC]、[BC，B]加上[AB，CA]。将[AB，CA]添加到线方程中会修剪掉将导致双重命中的三角形的尖端，因为它与三角形<A，CA，AB>重叠。对于图9C所示的配置，需要五个线方程。在图11B的处理中描述的四个线方程增加了方程[A，C]，可以用于修剪顶点CA处的任何“穿透”。最后，在三边都减少的情况下，可以增加第六个线方程[C，B]以在顶点BC处进行修剪。

各向同性采样和四边形

如图8A-8B所示，定义为表示几何体的三角形可能会变细，并且使用μ-网格重心均匀采样方案，样本可能不会均匀分布；他们可能在一个方向上比在另一个方向上更近。均匀采样效率更高，并且不易出现采样或渲染伪像。虽然可以用等边三角形构造大多数μ-网格，但某些几何形状(例如小半径圆柱体)最好进行各向异性采样。四边形固有地适应各向异性，而圆柱体等形式受益于四边形固有的不对称采样能力。在基础网格可能由四边形或四边形和三角形的混合构成的情况下，四边形可以起到这种各向异性的作用。请注意，只有四边形的网格可能存在“细分传播”问题。细化网格的一个面的细分可能需要相邻面的细分以避免引入T形接头。这些面的细分以类似于分辨率传播的方式传播到它们的邻居等等。

细节级别(LOD)

如上所述，μ-网格是规则网格，沿着它们的周边具有二的幂数量的片段。在一些实施例中，硬件或软件可以通过对μ-网格的简单抽取而非常有效地提取水密的、较低的LOD。64μ-三角形网格可以被视为16μ-三角形网格、4-三角形网格或单个三角形，只需省略顶点即可。在其最简单的形式中，均匀抽取微不足道地保持了水密性。使用二的幂抽取还简化了光栅化管线中自适应LOD的渲染。

使用μ-网格结构的应用程序可以有利地利用具有多个LOD的能力。例如，在进行光线追踪时，可以为每条光线指定所需的LOD，作为实例状态、全局状态的一部分，或作为遍历参数的函数，以基于不同的渲染环境自适应地选择不同的LOD。

位移映射

如上所述，μ-网格DM可以是用于计算μ-顶点的位置的标量值的栅格。在同时提交的美国申请No.________(6610-125)“用于光线和路径追踪的位移微网格(DisplacedMicro-meshes for Ray and Path Tracing)”中更详细地描述了位移映射及其示例实现，该申请的全部内容通过引用并入本文。

图12A-12B示出了渲染为高度场的DM。通过线性插值基本三角形的顶点以及图13A-13D的位移方向来计算μ-顶点。位移方向可以可选地被归一化，然后通过从DM检索的位移值进行缩放。

重正化的效果在图13A-13D图中示出，其中纯线性插值是平坦的(图13A-13B中所示)，而重正化可以产生曲线效果(图13C-13D中所示)。

在用位移的细分表面对几何体建模时，重正化在电影工业中被实践。这是因为位移的方向是使用细分表面的法线确定的。当使用位移映射三角形对几何体建模时，这些向量(称为位移向量)是明确指定的。与归一化位移向量一样，存储在DM中的标量位移在0到1的范围内指定/定义。因此，最终位移值必须映射到适合正在建模的几何体的范围。对于基础网格、位移向量和μ-三角形网格，计算所需位移值的范围d_min到d_max。根据d_min和d_max，可以按如下方式计算位移计算中使用的网格范围的尺度(scale)和偏差(bias)：

bias＝d_min (0.1)

scale＝d_max-d_min。

给定位移标量u，以及插值的基本位置和位移方向作为

(可选的)

μ-顶点可以被计算为

如果插值的位移向量没有被重正化，那么可以保留有用的自由度。请注意，重正化从三个自由度减少到两个。下文讨论避免尺度和偏差的替代公式。

棱柱体——可替代的表示

如果插值的位移向量未重正化，则可以导出不使用网格范围的尺度和偏差的替代等效表示。下面提供了可以预先计算对应于等于0.0和1.0的u值的三角形顶点的变换的详细内容：

在此表示中，三角形和形成完全包含μ-网格的棱柱体，并且可以线性地混合这些包围三角形上的重心插值点以计算最终的μ-顶点：

图14A-14B示出了两种表示：基础和位移(在图14A中)对比棱柱体规格(在图14B中)。第三种表示是上述两种表示的组合。这第三种方法很有用，因为它利用了在不重规一化时可用的额外自由度，同时使用了开发人员/用户熟悉的形式的表示。第三种方法在图15中以图形方式显示，在图15中，位移向量被添加到所谓的零三角形1502以形成一三角形1504。等式(0.4)的线性插值变为插值位移向量的加权相加：

数值精度

示例实施例中的μ-网格表示的目标包括紧凑性和精确性。高质量的表示将既紧凑又精确。规格精度的选择反映了这些目标。几何体指定为任意尺度，同时利用基础网格近似于μ-三角形的精细网格这一事实。在示例实施例中，使用32位浮点(例如IEEE浮点)计算基础网格。位移向量使用16位浮点指定，因为它们偏离基础网格。类似地，零-三角形加位移表示可以使用这两个精度。在一些实施例中，棱柱体表示对和三角形都使用32位浮点，因为它们的指定与尺度无关。在建立存储在位移映射中的标量位移值u的精度和格式时可以考虑多个因素。在一些实施例中，选择不动点是因为u映射了重要性一致的空间。在一些实施例中，选择UNORM表示是因为它是标准图形格式，可以映射从0.0到1.0的空间，包括端值。UNORM的形式为u/(2ⁿ-1)，其中u是n位无符号整数。选择精度级别时，需要考虑未压缩DM的大小。在图16所示的表中，位移映射的大小被列举为分辨率的函数。在表中，使用11位UNORM，64μ-三角形网格的DM有效地适合64字节。11位的值对应于FP16尾数(包括隐藏位)。UNORM11是64μ-三角形网格的方便尺寸，并且对应于是FP16的位移向量。

可见性掩模

如上所述，在一些示例实施例中，可见性掩模(VM，有时也称为“不透明微图”)是将μ-三角形分类为不透明、未知或透明的掩模。使用术语可见性是因为光线追踪引擎是可见性引擎并且需要可见性表征来确定光线与什么相交，光线追踪引擎是其中可以使用示例实施例的μ-网格的环境。当光线与μ-网格相交时，μ-网格内的相交地址(location)用于查找该地址的可见性。如果它是不透明的，那么命中是有效的。如果它被屏蔽为透明，则命中被忽略。如果它处于未知状态，则光线追踪引擎可以调用软件来确定如何处理该相交点。例如，在D3D中，调用的软件可能是任意命中着色器。与示例实施例的μ-网格和可见性掩模相比，在传统技术中，单独的三角形被标记为经过阿尔法(alpha)测试，并且如果任何这样的三角形相交则调用软件。在同时提交的美国申请No.________(6610-124)“加速实时光线追踪的三角形可见性测试(Accelerating Triangle Visibility Tests for Real-Time RayTracing)”中更详细地描述了可见性掩模和可见性掩模的示例实现，该申请已通过引用并入。

可见性状态——不透明、透明和未知

与μ-网格一起使用的VM可以是每μ-三角形一个、两个或某个其他数量的位的位掩模。VM的存储要求对应于μ-三角形计数，如图16所示的表格中总结的那样，随VM的分辨率而变化。每μ-三角形1位的VM将每个相应的μ-三角形标记为不透明或透明，并且在光线追踪期间不需要软件干预。图17B示出了图17A所示的叶的分支图像的1位VM。

VM可以是高分辨率的，如图17A-B所示，其中图17A中所示的叶的分支用比图17B中所示的分辨率更高分辨率的VM表示。如果存储器消耗是一个问题，则VM的分辨率可以大大降低。降低分辨率通常是最有效的压缩形式。通过降低分辨率，可以保留完整的渲染保真度。图18A显示了提供64:1压缩的两个128位的可见性掩模1802及1804，且图18B显示了提供1024:1压缩的两个32位的可见性掩模1806和1808。当如图17B中的1位掩模如图18A-18B中所示被下采样时，可以看出掩模的区域代表原始掩模的不透明和透明混合的区域。这些区域在图18B中显示为灰色(例如，μ-三角形1810)。还要注意，在图18B的较低的分辨率中，除了两个VM的轮廓之外，还显示了掩模的μ-三角形。

当使用下采样的VM时，“任意命中”着色器可以用于以与原始掩模相同的保真度解决可见性。如果光线与“灰色”μ-三角形相交(在图18B中)，则调用任意命中着色器以确定结果。在两个降低分辨率的示例中，大多数μ-三角形要么不透明，要么透明。这意味着大多数时候光线相交不需要调用软件来解决相交。2位的可见性掩模编码四种状态，这又提供了一些解释的灵活性。在某些光线追踪的效果中，不需要精确的分辨率。例如，可以使用较低分辨率的代理解决软阴影。为了便于使用此类代理，可以将2位的VM的四种状态定义为透明、未知-透明、未知-不透明和不透明。在这些状态的一个重新映射中，未知-透明与透明相关联，未知-不透明与不透明相关联，并且在这样做时将2位映射解释为不需要软件回退的1位映射，因为没有未知状态。在对这四种状态的第二种解释中，当被击中的μ-三角形被归类为未知中的任何一个时，调用软件。在后一种情况下，大多数光线在没有软件帮助的情况下被解析，但保真度/准确性对于恰好相交的任何所谓的未知μ-三角形得以保留。这两个重新映射在图19A-19B中示出。图19A表示到三个状态的替代2位映射：透明、未知和不透明，而图19B示出了到两个状态的映射：透明和不透明。

2位编码也可用于加速半透明对象的光线追踪。这些对象是透明、不透明和半透明的混合体，其中只有半透明部分需要软件来解析。在渲染不需要软件来跟踪的阴影等的低频/模糊效果时，此类材料也有助于简化在图20A-20B中，阴影和半透明映射用一个例子进行了说明。图20A示出了半透明的苔藓纹理，图20B示出了其上方的阴影掩模和下方的半透明映射。

表示概要

如上所述，μ-网格是几何体的结构化的表示。描述集中在作为μ-三角形的二的幂正则网格中的网格的表示上。在一些实施例中，使用插值的基础网格位置和位移向量和标量(例如，UNORM11)位移来计算μ-三角形的位置。μ-三角形的可见性以独立的μ-三角形分辨率指定，并且可以同时表示二进制可见性和软件解析的可见性。高度结构化的表示有助于紧凑的表示和高效的渲染。在一些实施例中，VM可以应用于通用三角形，有效地将它们视为μ-网格。当不使用位移时，VM使用只需要任何三角形的重心坐标系。

材质、内在参数化、调色板、VM和DM重用以及镜像支持

计算机图形渲染系统经常使用材质系统，其中材质由组合在一起的各种属性组成。材质属性包括控制反光度、反照率颜色以及alpha和位移的纹理映射。常规的阿尔法纹理可以映射到示例实施例的μ-网格VM，并且位移映射对应于示例实施例的μ-网格DM。三角形使用纹理坐标引用常规纹理，其中这些辅助坐标定义三角形和纹理映射之间的映射。创建纹理坐标是图形系统的内容创建管线中的一个重大负担。与传统的纹理映射不同，VM和DM使用三角形的固有坐标系、重心坐标。因此，VM和DM不需要创建或使用纹理坐标。使用内在参数化的想法可用于其他纹理类型，与DM密切对应，其中值像μ-三角形的小平面一样线性插值。此线性插值对应于纹理MIP链的单个级别内的双线性插值。相邻分辨率的μ-网格图之间的线性插值自然支持属性的三线性插值。该方案的一个好处是避免了创建纹理坐标的成本。

如上所述，可以将诸如纹理和VM和DM的资源分组为材质。当渲染对象的实例时，通常将可能不同的材质与每个对象实例相关联。因为VM和DM是帮助定义对象的可见性的材质属性，所以示例实施例中可以包括一种机制以将不同材质(例如，VM和DM的组)与光线追踪实例相关联。当不存在材质考虑时，示例实施例中的三角形可以直接引用其相关联的DM和/或VM。然而，将DM和VM视为材质属性，示例实施例中的每个三角形经由VM和DM的数组的索引引用其关联资源。给定的材质有关联的一对VM和DM的数组。当使用材质调用实例时，会绑定相应的VM和DM数组。

另一种形式的DM重用可能源于常见的CAD构建技术，其中对象组件是彼此的精确镜像，如图21的镜像建模示例中所示。表示对象的三角形网格通常是这样定向的，即从外面看时所有三角形的顶点顺序相同。顶点围绕它们定义的三角形按顺时针(或逆时针)顺序组织。模型构建中使用的镜像操作自然会改变顶点顺序，使镜像三角形看起来朝向相反的方向。要恢复一致的三角形朝向，可以颠倒镜像的顶点顺序。然而，因为DM和VM寻址是从顶点顺序派生的，所以必须知道顶点顺序何时被修改以纠正镜像操作。在示例实施例中，DM(或VM)可以在正常实例和镜像实例之间重复使用，因为映射/掩模寻址可以被配置为考虑镜像。

压缩

μ-网格表示、其内在参数化以及DM和VM的结合在上面进行了描述。当描述非常详细的几何体时，描述尽可能简洁是很重要的。用于实时计算机图形的详细几何体的可行性依赖于能够直接从紧凑表示进行渲染。在以下部分中，讨论VM和DM的压缩。因为两者都是高质量的μ-网格组件，所以可以利用固有的连贯性来压缩它们。DM和VM可以分别被认为是与顶点相关联的数据和与面相关联的数据的表示。这两个数据类可以被理解为要求不同的压缩方案，即无损又有损。在无损方案可以准确表示输入的情况下，允许有损方案将输入近似到测量的公差范围内。有损方案可能会标记出现不精确编码的位置，或指示哪些样本未能无损地编码。

当使用来自压缩表示的数据进行渲染时，示例实施例能够有效地访问所需的数据。当渲染像素时，示例实施例中的关联纹素可以通过计算包含所需纹素数据的压缩块的存储器地址来直接寻址。纹素压缩方案使用固定块大小压缩，这使得对纹素块的直接寻址成为可能。当在一些示例实施例中压缩VM和DM时，固定大小块的层次结构与其中的压缩编码一起使用。

对于固定大小的存储器块，一些μ-网格可能具有太多的μ-三角形而不能存储在一个固定大小的块中。这样的μ-网格可以分为相同或不同大小的子三角形，使得每个子三角形都将其所有μ-三角形存储在存储器中相应的固定大小块中。在一个实施例中，子三角形是基三角形定义的表面的三角形细分。将基三角形或关联的μ-网格分解为子三角形可以由μ-网格的关联内容的可压缩性，以及在某些情况下与μ-网格关联的可见性掩模或位移映射来确定。

可见性掩模压缩

在许多场景中，VM非常连贯，因为它们具有完全不透明的区域和完全透明的区域。参见例如图22中的示例VM。在示例实施例中，VM的压缩首先考虑无损压缩，然后为了满足固定大小和可寻址性要求，将这些算法转换为更灵活的有损方案。渲染期间使用的解压缩算法适用于低成本、固定功能的实现。

VM压缩——四叉树位掩模编码

考虑图22的枫叶，它的形状可以使用正方形树来描述，使得树有效地捕获如图22所示的同质区域。在图23A-23B中，在正方形域(图23A)和三角形域(图23B)上描绘四叉树。可以观察到，在高度连贯的区域中，同质纹素的相对较大区域(正方形或三角形)可以用单个正方形或三角形表示。对于在三角域上定义的μ-网格，使用三角四叉树，但这些算法同样适用于其他分层细分方案。

在图24中，示出了基于四叉树的编码方案，其中树2402的节点紧凑地描述图像。插入了要编码的示例64位图像2404。图像具有已知分辨率，因此细分深度(三个级别)是已知的。三种节点类型(例如，不透明、透明、半透明/未知)用于将区域编码为零和一的混合、全零、全一或四位叶值。第一层的单个节点包含所有64位，因此包括不透明和透明的纹素，从而产生未知的节点类型。在第二层，将64位划分为4x4的方块，并且按照遍历模式从左下方块开始，依次向左上方块、右下方块、右上方块移动来考虑。左下角和右下角的方块分别是全不透明的和全透明的，并且分别被编码为10和11。遍历顺序显示在图24的右下方。在第三层，只进一步拆分混合的第二层方块(既有不透明区域又有透明区域的方块)。因此，对于第三层，在第二层的左上角和右上角的4x4方块分别进一步拆分为四个2x2方块，从而分别在第三层引入了八个新节点。如图右侧所示，层1、2和3的编码可以分别用1位、6位和12位来完成。除了树的三层之外，第三层每个未知节点的2x2方块区域被额外编码为叶节点。因此，如图中右侧所示，64位示例图像2404被编码为35位。

在上面讨论VM时，描述了多于三种节点类型可用于表示诸如透明度或简单的不确定性之类的情况。在这些情况下，在一些实施例中可以使用四种节点类型，不透明、不透明-未知(浓阴影)、透明和透明-未知(软阴影)和八位叶值。图25示出了对图像2504进行编码的四叉树2502。现在，分类为“相同”的节点可以是全部不透明、全部不透明-未知、全部透明-未知或全部透明。此配置中的每个叶节点都需要八位，因为四个纹素中的每一个都需要两位才能描述四种类型中的一种。因此，如图25所示，使用四节点类型配置的64位图像2504的编码总共需要79位。

因为如图24-25所示，图像的无损编码不是固定大小的，所以无损编码不太适合直接用于渲染。具体来说，掩模编码可能比在单个操作中可以有效读取的更大。在下一部分中，将讨论使分层编码方案适应固定位预算算法的技术。

VM压缩——按预算编码

迄今为止所描述的方案允许对两个状态掩模和四个状态掩模进行精确编码，但是编码结果的大小未知，其可能太大。请注意，越靠近根的树的位代表更大的区域。如果以广度优先方式分配固定的存储器，从根到叶，掩模的最大区域自然首先编码，因为越大的区域表示在树的越高级别。例如，如果预算为48位，则除了最后四个2x2掩模值块或图的3/4之外的所有内容被捕获。当渲染算法对编码进行操作时，树的任何被截断的部分都被视为未知。这种比特分配方案的一个有趣结果是它建立了适合固定预算内的掩模分辨率。可以采用任意高分辨率的掩模并进行编码，进行广度优先、贪婪分配，并且可表示的分辨率对应于达到的树编码层。例如，如果用可用位预算达到树的第四层，则主题掩模将信息捕获到4⁴＝256个μ-三角形的分辨率。

VM压缩——游程长度编码

基于树的编码是VM的高效压缩表示，但其结构不适合直接寻址。这种固定预算压缩方案可以很好地支持某些应用。然而，执行点查询的应用程序可能需要更直接的查找机制来避免重复递归重建的低效率。这里描述了一种更适合直接寻址的游程长度编码方案。通常，游程长度编码方案使用符号计数对来更紧凑地描述符号序列。这些符号计数对可以称为“令牌”。出于可寻址的原因，可以使用固定位宽的令牌。

下一部分将讨论可见性掩模到线性符号序列的映射。要查找特定掩模值，需要计算其在序列中的地址(其索引)，然后计算表示其值的令牌。通过对令牌长度的列表执行前缀和来查找令牌，以查找哪个令牌代表在计算出的索引处的值。前缀和是一种已知的高效并行(对数深度)算法，用于查找值序列的和。在计算所有部分和时，计算每个令牌的索引间隔，并针对要查找其令牌值的索引进行测试。

令牌的大小由指定游程长度所需的位数加上指定值序列中的值所需的位数决定。游程位数可以通过扫描令牌序列并找到最长游程并分配位来确定。这种游程位计算方法可能效率低下，因为少数游程可能需要最坏情况下的位数。取而代之的是，选择最佳位数，使用多个令牌来编码比分配的游程位数支持的游程更长的游程。通过这种方式，令牌的总数略有增加，但每令牌的位数减少了较大程度，从而减少了对序列编码所需的总位数。

按顺序指定值所需的位数可以利用游程长度编码的性质。每个游程代表一系列相等的值，只有当值发生变化时游程才会结束。如果对1位的序列(0和1的列表)进行编码，则可以完全避免对值进行编码。记录序列的起始值，并在解析令牌时执行值之间的切换。然而，上面注意到最佳游程位的数量可能少于序列中的最长符号值游程所需的数量。长游程可能需要分成多个具有相同值的游程。为了在对长游程进行编码时容纳重复值，零长度的游程被保留以指示最大游程(2ⁿ-1)后跟一个令牌继续相同的游程值，构成长游程的平衡。请注意，某些游程可能需要多个最大令牌来进行它们的编码。在某些用例中，VM存在两种、三种和四种可能的状态：不透明-透明、不透明-未知/半透明-透明，以及不透明-未知/不透明、未知/透明、透明。上面描述了如何在没有附加位的情况下对两个状态或值进行编码。三个状态可以类似地被编码，使用单个位来指示要转换到其他两个状态中的哪一个。由于始终只有两种可能的下一个状态，因此使用单个位来指示序列中的下一个状态或符号值。当编码游程的长度超过用游程位所能表达的长度时，下一个状态保持不变，这样值位就可以用来指示单个或双长度的长游程，提高长游程编码的效率。最后，在对四个状态序列进行编码时，还有机会对长游程进行编码。为了对四状态序列进行游程长度编码，可以观察三个“下一个状态”。对于这种编码，令牌由一个2位的控制位和n个游程位组成。2位的控制对三种可能的下一个状态进行编码或指示长游程。因为2位的控制对长游程进行编码，所以游程位指定从1到2ⁿ的游程长度。并且在长游程的情况下，n个游程长度位编码最大游程的倍数，l2ⁿ。由于l可以在1到2ⁿ之间变化，因此长游程可以从2ⁿ到2²ⁿ编码，随后可以是长度为1到2ⁿ的游程以完成2ⁿ+1和2²ⁿ+2ⁿ之间的长游程。这很有用，因为它意味着游程位的最佳数量可以更小，从而实现改进的整体压缩。

VM压缩——游程长度编码到预算

当使用游程长度编码的掩模时，对编码流执行前缀和，利用固定大小的令牌。为了有效地执行前缀和，在不需要多次存储器提取的情况下，需要能够在单个操作中读取所有游程长度位、整个流。游程长度编码本质上是可变长度的，因为它们通常是无损的。为了固定在固定的存储器预算内，需要一种方案来减少游程长度编码的大小。由于固定位长的令牌，应该减少令牌的数量以减小流的大小或长度。减少令牌计数意味着引入必须在软件中解决的数据丢失和不确定性。这与通过降低图像分辨率引入的不确定性或未知值非常相似。引入最少不确定性的相邻令牌对被合并。具有长度为1的已知值与一游程未知相邻的一对令牌引入了一个新的未知值，即尽可能少的成本。合并一对长度为一的已知令牌会引入两个未知状态的新掩模条目。随着合并过程的进行，较长的游程可能需要合并以满足给定的预算。合并过程一直持续到游程长度编码的VM符合指定的预算，同时引入最少的未知掩模条目。

重心坐标到序列映射

在一些实施例中，如上所述的游程长度编码用于编码值序列。需要从VM到序列的映射，因为序列是一个列表，一个一维数字列表，而可见性掩模是掩模值的三角形图像。如果序列在空间上是连贯的，则游程长度编码会更有效。如果一个值在空间上靠近序列中的下一个值，则图像的一维遍历更加连贯。对于正方形图像，在示例实施例中主要使用两个遍历顺序，Hilbert和Morton。Hilbert遍历顺序(图26A中所示)是最连贯的，而Morton顺序(图26B中所示)的连贯性稍差但计算成本更低。计算成本很重要，因为频繁的操作采用二维坐标并产生相应掩模值的索引。

对于像示例实施例中的μ-网格这样的规则三角形区域，开发了高度连贯的遍历顺序。图28所示的遍历在本质上类似于Hilbert曲线，但计算起来更简单。从索引到离散重心坐标以及从重心坐标到索引的计算成本低廉。

为了支持描述，首先建立一些标签和术语。见图27，其示出了重心坐标和离散重心坐标。变量u、v和w用作重心坐标。三角形内的任何位置都可以使用三个值中的两个来定位，因为坐标是非负的并且和为一。如果三角形的面积本身是1.0，那么u、v和w就等于通过该点与三角形三个顶点连成的三个子三角形的面积。如果三角形的面积更大或更小，则u、v和w表示比例面积。坐标也可以被解释为从边到其相对顶点的垂直距离，也从0到1变化。

术语离散重心坐标用于指代和解决μ-网格中的各个μ-三角形。这里的μ-三角形使用<u,v,w>三元组命名，其中有效(整数)值随分辨率而变化。在图27中，显示了沿每条边具有四个μ-三角形的μ-网格，总共有16个μ-三角形。每个μ-三角形都有一个名称(标签)，其中元组<u,v,w>的成员总和为二或三。任何一对相邻的三角形在其中一个元组成员中将相差1。另请注意，网格由成排的u、v或w常数的μ-三角形组成。右侧的三角形μ-网格中显示了μ-三角形标签，而左侧的三角形μ-网格中显示了相应的顶点标签。

在对μ-网格进行编码时，遍历μ-网格的μ-三角形。根据一些实施例的用于遍历μ-网格的前四代空间填充曲线的图示在图28中示出。四种遍历模式中的每一种都显示了通过同一三角形的不同分辨率级别的遍历。图29显示了以遍历顺序访问网格的μ-三角形的递归函数的伪代码。虽然在图28中仅示出了前四代(级别)的遍历曲线，但应当理解，递归函数可以在μ-网格层次结构的任何级别对网格进行编码，每个级别提供不同的细节级别(或者换言之，不同的分辨率)。根据一个实施例，μ-网格的栅格的层次结构对于层次结构的每个级别可以具有四次方的分辨率增加。例如，图28显示了三角形区域，其中各个级别的三角形μ-网格数分别为4、16、64和128。同时提交的美国申请No.________(6610-124)“加速用于实时光线追踪的三角形可见性测试(Accelerating Triangle Visibility Tests for Real-Time Ray Tracing)”中提供了μ-网格遍历的详细信息，已通过引用并入。

位移压缩

在示例实施例中，位移量可以以平坦的、未压缩的格式存储，其中可以直接访问任何μ-顶点的UNORM11位移。或者，位移量也可以以使用预测和校正(P&C)机制的压缩格式存储。

位移压缩——预测和校正

示例实施例中的P&C机制依赖于用于形成μ-网格的递归细分。为基三角形指定一组三个基础锚点(或位移量)。在每一级的细分中，新的顶点通过对较低级别的两个相邻顶点进行平均而形成。这就是预测步骤：预测该值为相邻两个顶点的平均值。

下一步通过将预测向上或向下移动到它应该在的位置来校正该预测。当这些移动很小，或者被允许有损存储时，用于校正预测的位数可以小于直接对其进行编码所需的位数。校正因子的位宽在每个级别上都是可变的。

更详细地，对于P&C，为基三角形指定一组基础锚位移。在到下一个最高曲面细分(tessellation)级别的每个细分步骤中，通过平均较低级别中两个相邻(微)顶点的位移量来预测每个新μ-顶点的位移量。该预测步骤将位移量预测为两个(先前接收或先前计算的)相邻位移量的平均值。

P&C技术在这里被描述用于预测和校正标量位移，但是P&C技术不限于此。在一些实施例中，μ-三角形可以具有可以使用P&C被编码和压缩的其他属性或参数。这些属性或参数可以包括例如颜色、亮度、向量位移、可见性、纹理信息、其他表面特征等。例如，解码器可以使用它已经为它已经解码的三角形获得或恢复的属性或参数来预测另一个三角形的属性或参数。在一个实施例中，解码器可以基于为解码器细分的三角形已经获得或恢复的属性或参数来预测子三角形的属性或参数以获得这样的子三角形。编码器可以向解码器发送它自己生成的校正，该校正通过计算预测并将预测与输入值进行比较以获得增量，然后将其作为校正发送给解码器。解码器将接收到的校正应用于预测的属性或参数以重建属性或参数。在一个实施例中，校正可以具有比重建属性或参数更少的位，从而减少编码器需要传送给解码器的位数。在一个实施例中，校正可以包括校正因子和偏移值，其中偏移值被应用于校正因子以增加校正因子的动态范围。在一个实施例中，仔细选择不同曲面细分级别的校正因子和偏移值以确保函数是凸的，从而防止网格中出现裂纹。此外，P&C技术可用于编码除三角形以外的各种形状的μ-网格的此类属性或参数，例如正方形、长方体、矩形、平行四边形和菱形等四边形；五边形、六边形、其他多边形、其他体积等。

在使用P&C技术对位移量进行编码的一些实施例中，基础锚点是无符号的(UNORM11)，而校正是有符号的(二的补码)。偏移值允许以小于全宽的宽度存储校正。偏移值存储在每个级别，具有四个变体(三个子三角形边中每一个的μ-顶点的不同偏移值，以及内部μ-顶点的第四个偏移值)以允许每个子三角形网格边上的顶点彼此独立偏移(例如，使用简单的移位寄存器)，以及从内部顶点到子三角形。每个解码值都成为下一层的预测源。该P&C技术的示例伪代码如图30所示。图30中的伪代码执行以下描述中称为“公式1”的计算。图30中的伪代码中的预测行有允许四舍五入的一个额外的“+1”项，因为这里的除法是修正的截断除法。它等同于精确算术中的prediction＝round((v0<+<v1)/2)，将半整数四舍五入到下一个整数。

更详细地，在越来越深的曲面细分级别，μ-网格的表面趋向于变得越来越自相似——允许编码器使用越来越少的位来编码实际表面和预测表面之间的带符号校正。一个实施例中的编码方案为带符号的校正提供可变长度编码。更多的编码位可以用于粗略校正，更少的编码位用于更精细的校正。因此，在一个实施例中，当对大量μ-三角形的校正正在被编码时，每个μ-三角形的校正位的数量可以很小(例如，在一个实施例中小到单个位)。

位移量的编码和解码的进一步细节在题为“位移的微网格压缩(DisplacedMicroMesh Compression)”的美国申请_______(6610-129)中有所描述，该申请已通过引用并入。注意，在一个实施例中，解码位置在将校正添加到预测时根据无符号算术规则回绕。由软件编码器来避免基于存储值的回绕或者根据结果来确定回绕。下面描述了一种算法，通过该算法编码器可以利用这种回绕来提高质量。

位移压缩——一种用于寻找最接近校正的稳健恒定时间算法

如上所述，从细分级别n到细分级别n+1的校正是具有固定位数b(由子三角形格式和细分级别给定)的带符号整数，并且根据图30中的公式应用。虽然编码器可以用几种不同的方式中的任何一种来计算校正，但编码器的一个常见问题是在给定p(预测)和s(shift[level][type])的情况下找到最小化图30中公式中的d(被解码)和参考(未压缩)值r之间的绝对差的c(校正)的b位值。

这因整数运算的环绕方式而变得复杂(它等效于阿贝尔群(Abelian group)Z/2¹¹Z中的群运算)，但误差度量是在没有环绕的情况下计算的(它不是Z/2¹¹Z中的欧几里德度量)。提供了一个示例以进一步说明这是一个非常重要的问题。

考虑p＝100、r＝1900、s＝0和b＝7的情况，如图31所示。图左手侧附近突出显示的垂直线p表示预测的位移值，垂直线r表示被解码值应接近的参考位移值。请注意，这两条线接近所示的11位空间的相反端。当使用棱柱体最大-最小三角形凸包来定义位移值时，这种情况相对经常发生。

显示了从0到2047的所有UNORM11值的数字线，粗线p和点划线r的地址，以及在p粗线周围较浅的阴影中，对于所有可能的校正的所有可能的d值(因为b＝7，因此可能的校正是从–2^6＝-64到2^6-1＝63的带符号整数，包括本数)。

在该示例中，存在0的偏移和-64到+63的可能校正范围，如标记为p的预测线的左侧和右侧的垂直线所示。解码器最好选择标准欧几里德度量中最接近r线的值。这似乎是+63处最右边的垂直线。然而，当应用环绕算法时，最靠近参考线r的线不是最右边的线，而是在-64最左边的线，因为使用环绕算法，这条最左边的线与参考线r的距离最小。

在这种情况下，解决方案是选择c＝63的校正，给出d＝163的解码值和abs(r-d)＝1737的误差。如果距离度量是Z/2¹¹Z，则解决方案将改为c＝-64，给出d＝36的解码值和183的误差(环绕)。因此，即使使用Z/2¹¹Z的误差度量更容易计算，它也会产生与正确解符号相反的校正，这会导致令人反感的视觉伪影，例如麻点。

接下来，考虑p＝100、r＝1900、s＝6和b＝3的情况，图32中所示。这里，可以看到更少的位和非零偏移。p和r周围的线相距2^s＝32，并环绕范围的两端。偏移被指定为6，并且只有三位校正可以使用，因此校正值相隔64。可能的校正是从–8到7的整数，包括本数，如垂直线所示。

在这种情况下，解决方案是选择c＝-4的校正，给出d＝1892的解码值和abs(r-d)＝8的误差。可以利用环绕行为来在这里获得良好的结果，但通过这样做，可以看出非零偏移可以产生比前一种情况更低的误差，即使位数更少。

其他场景是可能的。之前的场景涉及算术下溢；需要算术上溢的情况也是可能的，以及不涉及上溢或下溢的情况，以及校正获得零误差的情况。

图33给出了给定无符号整数0≤p<2048、0≤r<2048、无符号整数偏移0≤s<11和无符号整数位0≤b≤11，在有限数量的操作中(不管c的b位可能性的数量为何)总是返回c的最佳可能整数值(如果b>0，则在-2^b和2^b-1之间，包括本数，如果b＝0，则等于0)的算法的伪代码。在步骤1-8的图示伪代码中，括号内的非数学斜体文本表示注释，并且取模运算(mod)用于返回正值。

基本上，伪代码算法认识到参考线r必须总是在可表示范围内的两条校正值线之间或与该范围内的校正值线完全重合。该算法在两种不同情况之间翻转(两个极端校正之间的参考值或参考值在两个可表示值之间)，并选择具有较低误差的情况。基本上，在一个实施例中，环绕情况为预测值和参考值接近位限制位移值范围的相对端的情况提供了“捷径”。

位移存储

在一些实施例中，位移量存储在称为位移块的64B或128B粒度块中。单个基三角形的位移块集合称为位移块集。位移块编码8x8(64)、16x16(256)或32x32(1024)μ-三角形的位移量。

在一些实施例中，最大存储器占用位移集将具有覆盖64字节的8×8(64)μ-三角形的均匀未压缩位移块。最小的存储器占用空间来自覆盖64字节的32x32的均匀压缩位移块，其指定每个μ-三角形约0.5位。两者之间大约有16倍的差异。存储器中位移块的大小(64B或128b)与其可以表示的μ-三角形的数量(64、256或1024)配对定义了μ-网格类型。μ-网格类型可以从压缩程度最高到最低排序，给出了用于水密压缩的“压缩比顺序”。在标题为“位移的微网格压缩(Displaced MicroMesh Compression)”的美国申请_______(6610-129)中描述了位移存储的更多细节，该申请已通过引用并入。

压缩机

实时图形应用程序通常需要在可以渲染之前以每帧为基础压缩新生成的数据(例如，物理模拟的输出)。为了满足这一要求，一些实施例采用了一种快速压缩方案，该方案能够以最少的同步对子三角形进行并行编码，同时产生没有裂纹的高质量结果。

该压缩算法的主要设计目标之一是约束校正位宽，使得可用给定的μ-网格类型表示的位移值集合是用更压缩的μ-网格类型可表示的所有值的严格超集。通过将μ-网格类型从压缩最多到最少组织起来，实施例可以继续使用上述P&C方案以“压缩比顺序”直接编码子三角形，从压缩最多的μ-网格类型开始，直到达到所需级别的质量。该方案在最大化压缩的同时实现了并行编码，并且不会沿子三角形共享的边引入不匹配的位移值。

首先，描述了为保证无裂纹压缩而需要实施的约束。其次，提出了一种使用预测和校正方案的单个子三角形的简单编码算法。第三，引入了采用统一曲面细分率(即所有基三角形包含相同数量的μ-三角形)的网格压缩方案。最后，展示了如何扩展此压缩器以处理自适应曲面细分的三角形网格。尽管下文提供了压缩算法的一些描述，但该算法的更多细节在标题为“位移的微网格压缩(Displaced MicroMesh Compression)”的美国申请_______(6610-129)中有所描述，该申请已通过引用并入。

压缩机——无裂纹压缩的约束

图34A示出了两个子三角形共享一条边的情况。两个子三角形都以相同的速率进行曲面细分，但使用不同的μ-网格类型进行编码。在图中，两个三角形之间的空间只是为了更清楚地说明。在所示示例中，为μ-顶点分配了例如“S1”的标志符。此处，字母“S”表示“细分”，而后面的数字表示细分数。因此，可以看到每个子三角形的共享边顶部和底部的“S0”顶点将存储在细分级别零—即以未压缩格式。第一次细分将在细分级别1生成“S1”顶点，而第二次细分将在细分级别2生成“S2”顶点。

为了避免沿共享边出现裂纹，两个三角形的解码位移值必须匹配。S0顶点匹配，因为它们始终未压缩编码。S1顶点和S2顶点将匹配，当且仅当(1)子三角形按“压缩比顺序”编码，以及(2)用压缩更多的μ-网格类型编码的位移值始终可以用压缩更少的μ-网格类型表示。第二个约束意味着对于给定的细分级别，压缩程度较低的μ-网格类型永远不会比压缩程度较高的μ-网格类型使用更少的位。例如，如果右子三角形使用比左子三角形更紧凑的μ-网格类型，则右子三角形将首先被编码。此外，右子三角形的边(即其与右子三角形共享的边)的编码后位移值将被复制以替换左子三角形的位移值。属性(2)确保一旦被压缩，沿左子三角形边的位移值将被无损编码，从而沿共享边创建完美匹配。

图34B示出了在具有不同曲面细分率(2倍差异)但用相同μ-网格类型编码的三角形之间共享边的情况。为了确保在给定级别编码的共享边值两侧的解码位移匹配，也必须在下一个细分级别表示(例如，参见S1-S2和S0-S1顶点对)。在一个实施例中，当且仅当(1)具有更低曲面细分率的子三角形在具有更高曲面细分率的子三角形之前被编码，以及(2)对于给定的μ-网格类型，细分级别N的校正位宽度与级别N-1相比相同或小，这才能实现。换句话说，这后一个属性规定对于μ-网格类型，按细分级别排序的位数应形成单调递减序列。例如，图34B中的左三角形将首先被编码，并且其解码后的位移值将被复制到右手侧三个三角形共享的顶点，然后再进行编码。

总之，当根据一些实施例对三角形网格进行编码时，采用以下对排序的约束以避免网格中的裂纹：

子三角形按曲面细分率升序编码；以及

具有相同曲面细分率的子三角形按压缩比降序编码，

并且在一些实施例中，以下约束被施加于校正位宽配置：

对于给定的μ-网格类型，细分级别永远不会使用比下一级更少的位；以及

对于给定的细分级别，μ-网格类型永远不会比更压缩程度更高的类型使用更少的位。

上述规则说明了代表相同数量的μ-三角形(即相同数量的细分)但具有不同存储要求(例如128B或64B中的1024个μ-三角形)的μ-网格类型。请注意，用于表示位移值的有效位数由其校正位和偏移位的和给出。

压缩器——子三角编码器

根据一些实施例，使用2遍方法来编码具有给定μ-网格类型的子三角形。

第一遍使用上述P&C方案来计算细分级别的无损校正，同时跟踪校正所采用的值的总体范围。然后确定可以用于每个边和内部顶点的最佳偏移值(在一个实施例中总共有4个偏移值)以覆盖具有多个可用校正位的整个范围。对于位于三个子三角形边上的顶点和子三角形的内部顶点，该过程独立执行，每个细分级别总共有4个偏移值。需要这个过程对于每个边的独立性来满足无裂纹压缩的约束。

第二遍再次使用P&C方案对子三角形进行编码，但是这次使用在第一遍中计算的有损校正和偏移值。第二遍使用第一遍结果(以及特别是最大校正范围和可用于校正的位数)来构造有损校正和偏移值——后者允许前者在不偏移的情况下表示比可能更大的数字。这两遍的结果可以按原样使用，或者可以为优化算法提供起点，该优化算法可进一步提高质量和/或压缩比。

P&C方案的硬件实现(参见图30)可以在(整数)上溢或下溢的情况下表现出环绕行为。可以在第2遍中利用此属性以通过“环绕”来表示校正值，如果可用的位数有限，则无法通过其他方式到达校正值。这也意味着基于校正范围的偏移值计算可以利用回绕来获得更高质量的结果(请参阅下面的“通过利用回绕改进偏移值计算(Improving shift valuecomputation by utilizing wrapping)”)。

请注意，此过程本身永远不会失败，并且对于给定的μ-网格类型，始终可以对子三角形进行编码。也就是说，压缩器可以分析此压缩步骤的结果，并通过使用各种度量和/或启发式方法来确定最终的质量是不够的。(参见下面的“在编码成功度量中使用位移方向长度(Using displacement direction lengths in the encoding success metric)”。)在这种情况下，压缩器可以尝试使用压缩较少的μ-网格类型对子三角形进行编码，直到达到预期的质量。此迭代过程可能导致尝试使用无法表示其所有μ-三角形的μ-网格类型对子三角形进行编码。在这种情况下，子三角形递归地分成四个子三角形，直到它可以被编码。

压缩器——通过利用回绕改进偏移值计算

最小化每个顶点类型的每个级别的偏移大小可以提高压缩质量。可表示校正之间的距离(参见图31和图32中所示的可能的解码值)与该级别和顶点类型的偏移次方的2成正比。将偏移减少1会使可表示值的密度加倍，但也会将由最小校正和最大校正表示的跨度的长度减半。由于计算校正的算法可以利用环绕行为，因此在计算覆盖级别和顶点类型的所有校正所需的最小偏移时考虑环绕行为可以提高质量。

例如，考虑校正水平和顶点类型，其中每个参考值和预测值之间的差mod 2048 d_i分布如图35-37。不考虑回绕的算法可能会得出结论，它需要最大可能的偏移来跨越所有这些差异。但是，由于校正可能是负的并且可能会环绕，因此较小的偏移可能会产生更高质量的结果。

一种可能的算法可以如下。从大于1024的(差mod 2048)中减去2048，使得所有回绕的差异wi都在整数–1024...1023范围内(包含本数)。这有效地将所有值置于原始范围的子集中—并转换以前相距甚远的值，因此使它们现在靠得很近。由此产生的明显更小的偏移更接近于参考值。然后在给定级别位宽b的情况下将偏移s计算作为最小数s，使得

2^s(2^b-1)≥max(w_i)

和

-2^s(2^b)≤min(w_i)。

压缩器——在编码成功度量中使用位移范围

描述了一种用于将缩放信息解释为每顶点重要性信号的方法，以及一种用于使用每顶点重要性来修改位移编码器误差度量的方法。这会在需要的地方提高质量，并在质量不那么重要的地方减小尺寸。

如上所述，每个顶点具有一个范围，在该范围内它可以被位移，由位移映射规范给定。例如，对于棱柱体规范，此范围的长度与插值方向向量的长度和插值比例成比例。同时，编码格式的解码输入和输出具有固定的范围和精度(UNORM11值)。这意味着最小值和最大值可能会在网格的不同区域产生不同的绝对位移——因此，与另一部分相比，网格的一个部分给定大小的UNORM11误差可能会导致或多或少的视觉退化。

在一个实施例中，允许例如通过误差度量向编码器提供每网格顶点的重要性(例如，“显著性”)。对于此的一个选项是每个顶点在对象空间中可能的位移范围(例如，棱柱体表示中的距离x比例——这是差异的度量，因此是对象空间中的计算误差)；然而，这也可以是另一个过程的输出，或者由用户引导。网格顶点重要性被线性插值以获得每个μ-网格顶点的“重要性”。然后在误差度量中，每个误差度量元素的压缩与未压缩误差由从元素的μ-网格顶点级别的“重要性”导出的误差度量“重要性”加权。然后将这些累积起来，并将产生的累积误差(现在根据“重要性”级别加权)与误差条件进行比较。以这种方式，压缩器经常为具有较低“重要性”的网格的区域选择更多压缩格式，而为具有较高“重要性”的网格的区域选择较少压缩格式。

压缩器——网格编码器(均匀)

下面的伪代码说明了根据一些实施例的均匀曲面细分网格的编码如何操作：

注意，每个子三角形携带一组参考位移值，它们是压缩的目标值。编码的子三角形和一个或更多个尚未编码的子三角形共享的边被视为“部分编码”。为了确保无裂纹压缩，其解压缩位移值被传播到尚未编码的子三角形，在那里它们替换它们的参考值。

压缩器——网格编码器(自适应)

如下所示，自适应曲面细分网格的编码需要额外的外循环，以便以曲面细分率升序处理子三角形：

包括外环是因为在“流形”或“格式良好”网格的这些动态条件下不存在边仅在两个三角形之间共享的假设。其他技术可以替代外环，但可能导致质量变差。

请注意，当更新与使用2倍高曲面细分率的子三角形共享的边的参考位移时，仅每隔一个顶点受到影响(参见图34B)，而其余顶点被迫使用零校正以便匹配较低分辨率子三角形的共享边上的位移斜率。此外，不能保证从较低分辨率子三角形“接收”更新的位移值的较高分辨率子三角形能够表示此类值。虽然这些情况很少见，但为了避免出现裂纹，可能会强制对更新后的参考值进行无损编码，以便始终与较低分辨率子三角形的边上的对应值匹配。如果这种无损编码不可能，则子三角形将无法编码，并且将来会尝试使用压缩较少的μ-网格类型。

用于生成和使用μ-网格的示例过程和系统

图38是根据一些示例实施例的用于在图像渲染期间使用上述VM和DM的过程3800的流程图。

在示例实施例中，场景中的一个或多个对象可以具有关联的VM和/或DM。如上所述，场景中对象的表面覆盖有如上所述的一个或更多个μ-网格(参见例如图7A)，并且对于每个μ-网格，可见性信息被存储在VM中并且位移信息被存储在DM中，然后这些信息然后被存储以供诸如过程3900的过程在场景渲染期间随后使用。

在操作3802，识别空间上覆盖在几何图元上的μ-网格中的感兴趣的μ-三角形。例如，在光线追踪应用中，响应于系统在光线-三角形相交测试中检测到命中，识别出发生命中的μ-三角形。在另一示例应用中，当在光栅化期间选择纹素时可以发生识别μ-三角形。

在操作3804，访问VM和/或DM以获得命中地址的场景信息。使用经识别的感兴趣的μ-三角形的重心坐标访问VM和/或DM。与传统的纹理映射等相比，示例实施例中的VM和DM的存储方式以及访问VM和DM的方式不需要额外坐标等的存储或处理。VM和DM可以是单独的索引数据结构，每个索引数据结构都可以使用μ-网格内感兴趣的点(或μ-三角形)的重心坐标访问。

如上所述，VM和DM的存储内容和方式不同，但是它们都可以使用覆盖在几何图元上(或者更具体地，在几何图元的表面积上)的μ-网格中的μ-三角形的重心坐标来有效地访问。

在一些实施例中，VM和/或DM可以进一步基于所需的细节级别来访问。在一些实施例中，可以进一步基于除可见性之外的特性来访问VM，例如，诸如材质类型的特性使得能够针对与μ-网格相关联的几何图元的不同类型的材质/表面类型单独定义可见性。

在VM和/或DM索引数据结构中访问的值可以是编码和/或压缩形式，并且可能需要在使用前未编码和/或未压缩。访问的值可用于渲染与访问的兴趣点对应的对象表面区域。

图39是根据一些示例实施例的用于创建上述VM和DM的过程3900的流程图。为场景中的对象创建VM和DM发生在渲染该场景之前。在一些实施例中，过程3900可以与场景的加速度数据结构(例如，BVH)的构建相关联地执行。

在操作3902，一个或更多个μ-网格覆盖在场景中的几何体元素的表面上。表面可以是平面的或弯曲的。作为一个例子，图7A显示了具有多个重叠μ-网格的对象。在一个实施例中，μ-网格是μ-三角形的栅格。

在操作3904，处理一个或更多个μ-网格用于裂纹抑制和/或细节级别(LOD)。上述用于裂纹抑制的一种或更多种技术可用于处理一个或更多个μ-网格用于裂纹抑制。例如，可以在示例实施例中使用上述的边抽取技术或上述的线方程调整。

此外，基于应用的要求、场景的特征和/或正在使用的计算机图形系统的能力，确定所需的细节级别，并相应地确定为获得所需的分辨率几何体表面被细分到的水平的数量。

在操作3906，为几何体元素生成位移映射。如上所述，位移映射提供了各个顶点的位移量和位移方向。可以根据配置参数选择每个网格的表示类型(例如，基础和位移、棱柱体规范、组合)、比例和偏差参数，以及DM的位移向量是否被归一化等。可以在操作3906中使用上述用于DM生成的一种或更多种技术。在一个示例实施例中，位移量可以以平坦的、未压缩的格式存储，其中可以直接访问任何μ-顶点的位移。在另一个实施例中，可以使用上述预测和控制(P&C)技术和用于寻找最接近校正的恒定时间算法来生成和编码位移映射。在一个实施例中，如上所述，用于寻找最接近校正的P&C技术和算法与旨在约束位移编码中的校正位宽的快速压缩方案结合使用。实施例可选择上述均匀网格编码器或自适应网格编码器。

在操作3908，为几何体元素生成可见性掩模。上面描述了生成可见性掩模的技术。可以根据某些预设配置值(例如要识别的可见性状态集合中的任何一个、要用于对可见性状态进行编码的位数等)生成可见性掩模。在将图像映射到μ-网格后，可见性掩模可以根据上述用于可见性掩模的技术之一进行编码。在一个示例实施例中，可以根据上述预算技术的游程长度编码结合上述重心坐标到序列映射来对可见性掩模进行编码和压缩。

在操作3910，压缩的位移映射和可见性掩模被存储以供后续访问。特定场景的可见性掩模和位移映射可以与为该场景生成的BVH相关联地存储，以便它们可以加载到计算机图形系统的存储器中，用于与对应几何体的访问相关联地高效访问。可见性掩模和位移映射可以存储为单独的索引数据结构或可以存储在相同的索引数据结构中，并且索引数据结构可以被配置为仅使用感兴趣的μ-三角形的重心坐标是可访问的。在一些实施例中，可见性掩模和位移映射可以存储在非暂时性计算机可读存储介质中，以在另一个计算机图形系统中使用，而在一些实施例中，映射存储在非暂时性存储介质中，使得在渲染图像时它可以实时加载到计算机图形系统的存储器中。

图40示出了示例实时光线交互式追踪图形系统4000，其使用包括如上所述的诸如BVH和基于μ-网格的VM和DM的加速数据结构的场景或对象的三维(3D)数据来生成图像。

系统4000包括输入设备4010、处理器4020、图形处理单元(GPU)4030、存储器4040和显示器4050。图40所示的系统可以采用任何形状因子，包括但不限于个人计算机、智能手机或其他智能设备、视频游戏系统、可穿戴虚拟或增强现实系统、基于云的计算系统、车载图形系统、片上系统(SoC)等。

处理器4020可以是多核中央处理单元(CPU)，该多核中央处理单元可操作为，作为对输入设备4010的实时交互响应执行应用程序，其输出包括用于在显示器4050上显示的图像。显示器4050可以是任何种类的显示器，例如固定显示器、头戴式显示器(例如显示器眼镜或护目镜)，其他类型的可穿戴显示器、手持显示器、车载显示器等。例如，处理器4020可以基于从输入设备4010接收的输入来执行应用程序(例如，操纵杆、惯性传感器、环境光传感器等)，并指示GPU 4030生成显示应用程序进展的图像以在显示器4050上显示。

基于应用程序在处理器4020上的执行，处理器可以发布指令以供GPU 4030使用存储在存储器4040中的3D数据来生成图像。GPU 4030包括用于加速实时图像生成的专用硬件。例如，由于GPU执行重复和高度并行的特殊计算任务(例如多边形扫描变换)的能力比常规软件驱动的CPU快得多，因此GPU 4030能够实时处理数千或数百万个图形图元(多边形)的信息。例如，与处理器4020不同，处理器4020可以具有多个核，其中该核具有一次可以处理几个软件线程的许多高速缓存存储器，GPU 4030可以包括成百上千个正在并行运行的处理核或“流式多处理器”(SM)4032。

在一个示例实施例中，GPU 4030包括多个可编程高性能处理器，其可以被称为“流式多处理器”(“SM”)4032，以及包括图形图元引擎4034和光栅引擎4036的基于硬件的图形管线。GPU 4030的这些组件被配置为使用称为“扫描变换光栅化”的技术执行实时图像渲染，以在二维显示器4050上显示三维场景。在光栅化中，将3D场景的几何形状构建块(例如，点、线、三角形、四边形、网格等)映射到显示器的像素(通常经由帧缓冲存储器)。

GPU 4030将3D模型的几何形状构建块(即，诸如三角形之类的多边形图元)变换为2D图像的像素，并为每个像素分配初始颜色值。图形管线可以通过定义或调整像素的颜色值，将阴影、透明度、纹理和/或颜色效果应用于图像的各部分。可以对最终像素值进行抗混叠、滤波并提供给显示器4050以进行显示。多年来，许多软件和硬件的进步已经使用光栅化技术以实时图形所需的帧率(即每秒30至60帧)以在一个或更多个显示器4050上的高显示分辨率(例如4096×2160像素或更高)改善了主观图像质量。

SM 4032或者与SM相关联的其他组件(未示出)可以将光线投射到3D模型中，并确定该光线是否以及在何处与模型的几何体相交。光线追踪直接模拟在虚拟环境或场景中行进的光线。光线相交的结果与表面纹理、观察方向和/或照明条件一起用于确定像素颜色值。由SM 4032进行的光线追踪允许计算机生成的图像以与真实世界的照片或视频无法区分开的方式捕获阴影、反射和折射。

给定包括场景的几何体的加速数据结构4042(例如，BVH)，GPU、SM或其他组件执行树搜索，其中光线访问的树中的每个节点针对每个后代分支或叶子都有包围体，并且光线仅访问相应包围体与之相交的后代的分支或叶子。以这种方式，显式地测试仅少量图元用于相交，即驻留在被光线相交的叶节点中的图元。在示例实施例中，一个或更多个基于μ-网格的VM和/或DM 4044也与BVH 4042中定义的至少一些几何体相关联地存储在存储器4040中。如上所述，基于μ-网格的VM和DM用于能够以有效的方式渲染与场景的几何体相关联的高度详细的信息。根据一些实施例，处理器4020和/或GPU 4030可以执行过程3800以响应于光线命中BVH的几何体元素，有效地查找相关联的VM和/或DM，从而能够以提高的效率和准确性渲染场景。

根据一些实施例，一个或更多个基于μ-网格的VM和/或DM 4044可以在它们可用于渲染之前由处理器4020生成。例如，一个或更多个基于μ-网格的VM和/或DM 4044可以根据由处理器4020执行的过程3900来生成。用于过程3800、3900和与生成和/或使用基于μ-网格的VM和DM相关联的其他过程的指令，和/或基于μ-网格的VM和DM可以存储在连接到处理器4020和/或GPU 4030的一个或更多个非暂时性存储器中。

应用本文公开的一种或更多种技术生成的图像可以显示在监视器或其他显示设备上。在一些实施例中，显示设备可以直接耦合到生成或渲染图像的系统或处理器。在其他实施例中，显示设备可以例如经由网络间接地耦合到系统或处理器。此类网络的示例包括因特网、运动电信网络、WIFI网络以及任何其他有线和/或无线联网系统。当显示设备间接耦合时，由系统或处理器生成的图像可以通过网络流传输到显示设备。这种流传输允许例如在服务器上或在数据中心中执行渲染图像的例如视频游戏或其他应用程序，并且渲染的图像可以被传送到与服务器或数据中心物理上分离的一个或更多个用户设备(例如计算机、视频游戏控制台、智能手机、其他移动设备等)上并在其上显示。因此，本文公开的技术可以应用于增强流传输的图像并增强流传输图像的服务，例如NVIDIA GeForce Now(GFN)、Google Stadia等。

此外，应用本文公开的一种或更多种技术生成的图像可以用于训练、测试或证明用于识别现实世界中的对象和环境的深度神经网络(DNN)。这样的图像可以包括道路、工厂、建筑物、城市环境、农村环境、人类、动物以及任何其他物理对象或真实世界环境的场景。这样的图像可以用于训练、测试或认证在机器或机器人中使用的DNN，以操纵、处理或修改现实世界中的物理对象。此外，此类图像可用于训练、测试或认证在自主车辆中使用的DNN，以在现实世界中导航和移动车辆。另外，应用本文公开的一种或更多种技术生成的图像可以用于向这些机器、机器人和车辆的用户传达信息。

此外，应用本文公开的一种或更多种技术生成的图像可用于显示或传达关于虚拟环境的信息，例如虚拟实境、全域或真实环境的数字双胞胎。此外，应用本文公开的一种或更多种技术生成的图像可用于在各种设备上显示或传达信息，包括个人计算机(例如膝上型电脑)、物联网(IoT)设备、手持设备(例如，智能手机)、车辆、机器人或任何包含显示器的设备。

如同明确提出一样，以上引用的所有专利和出版物均以引用方式并入。尽管已经结合当前被认为是最实际和优选的实施例描述了本发明，但是应当理解，本发明不限于所公开的实施例，相反，本发明旨在覆盖包括在所附权利要求书的精神和范围内的各种修改和等同布置。

Claims (19)

1.一种非暂时性计算机可读存储介质，其存储指令，当所述指令由包括存储器的计算机系统的处理器执行时，使所述计算机系统执行操作，所述操作包括：

识别覆盖在对象的表面上的区域上的微三角形栅格中的感兴趣的微三角形；以及

在所述存储器中并基于所述微三角形栅格内的所述感兴趣的微三角形的位置，访问存储在索引数据结构中的值，

其中所述值表示在与所述感兴趣的微三角形的位置相对应的地址处的表面的特征。

2.根据权利要求1所述的非暂时性计算机可读存储介质，其中所述索引数据结构至少存储多个微三角形中的每个微三角形的可见性状态，其中所述可见性状态指示不透明可见性状态和透明可见性状态中的至少一个。

3.根据权利要求1所述的非暂时性计算机可读存储介质，其中所述索引数据结构至少存储多个微三角形中的每个微三角形的位移。

4.根据权利要求3所述的非暂时性计算机可读存储介质，其中所述位移包括位移方向和位移值。

5.根据权利要求1所述的非暂时性计算机可读存储介质，其中访问存储在索引数据结构中的值包括：基于所述感兴趣的微三角形的重心坐标来确定所述数据结构中的地址。

6.根据权利要求1所述的非暂时性计算机可读存储介质，其中所述区域包括一个或更多个三角形形状的区域，所述索引数据结构包括用于每个微三角形的一组位，其中用于多个微三角形中的相应微三角形的各组位按照所述多个微三角形的预先配置的遍历路径的顺序排列。

7.根据权利要求6所述的非暂时性计算机可读存储介质，其中所述预先配置的遍历路径与所述区域的空间填充曲线相对应。

8.根据权利要求1所述的非暂时性计算机可读存储介质，其中识别空间上覆盖在区域上的微三角形栅格中的感兴趣的微三角形包括：

确定所需的细节级别；

获得对所述微三角形栅格的访问，其中所述微三角形栅格被识别为与相应栅格的层次结构中的所需的细节级别相对应的栅格，每个栅格具有不同的细节级别并且具有布置为覆盖所述区域的不同大小的三角形。

9.根据权利要求1所述的非暂时性计算机可读存储介质，其中当所述指令由所述处理器执行时，使所述计算机系统执行操作，所述操作进一步包括：

在所述存储器中并基于所述微三角形栅格内的所述感兴趣的微三角形的位置，访问存储在第二索引数据结构中的第二值，其中所述第一值是可见性状态并且所述第二值是位移状态；以及

根据所述可见性状态和所述位移状态，渲染与对应于所述感兴趣的微三角形的位置的地址相对应的像素。

10.一种数据结构，其包括多组位，每组位与多个微三角形中的一个或更多个微三角形的相应组相对应，所述多个微三角形被连续布置以在空间上覆盖对象的表面上的区域，所述多组位根据所述多个微三角形的预先配置的遍历顺序排列，并且所述每组位被配置为表示与感兴趣的微三角形的位置相对应的地址处的区域的特征。

11.根据权利要求10所述的数据结构，被配置为使用与所述多个微三角形中的微三角形相关联的重心坐标来访问。

12.根据权利要求10所述的数据结构，其中所述多组位中的位表示所述表面上的所述区域的可见性信息，其中所述可见性信息包括所述区域的每个纹素的不透明状态和透明状态中的至少一个。

13.根据权利要求10所述的数据结构，其中所述多组位中的位表示所述表面上的所述区域的位移信息，其中所述位移信息包括所述区域的每个纹素的位移值和位移方向。

14.一种形成索引数据结构的方法，所述索引数据结构被配置为提供对表示在与感兴趣的微三角形的位置相对应的地址处的对象的表面的一个或更多个特征的值的访问，所述方法包括：

将可见性状态分配给在空间上覆盖在所述表面上的区域上的微三角形栅格中的每个微三角形，其中所述可见性状态包括不透明状态和透明状态中的至少一个；

基于所述每个微三角形的重心坐标和所述微三角形栅格的预先配置的遍历顺序来编码所述索引数据结构；以及

将经编码的索引数据结构存储在存储器中。

15.根据权利要求14所述的方法，其中将经编码的索引数据结构存储在存储器中包括：将经编码的索引数据结构与在存储于所述存储器中的包围体层次结构中存储的对象相关联。

16.一种形成索引数据结构的方法，所述索引数据结构被配置为提供对表示在与感兴趣的微三角形的位置相对应的地址处的对象的表面的一个或更多个特征的值的访问，所述方法包括：

确定在空间上覆盖在所述表面上的区域上的微三角形栅格中的每个微三角形的每个微顶点的位移量和位移方向，其中所述位移量相对于基三角形被指定；

基于所述每个微三角形的重心坐标和微三角形栅格的预先配置的遍历顺序来编码所述索引数据结构；以及

将经编码的索引数据结构存储在存储器中。

17.根据权利要求15所述的方法，其中确定每个微三角形的每个微顶点的位移量和位移方向包括：通过基于相邻顶点的预测来确定微三角形顶点，并且所述编码包括编码针对相应预测的微顶点的预测的校正。

18.根据权利要求16所述的方法，其中确定每个微三角形的每个微顶点的位移量和位移方向还包括：在一个或更多个微网格中执行边抽取。

19.一种形成表示几何体的数据结构的方法，包括用至少一个处理器执行操作，所述操作包括：

定义平面或扭曲的几何图元的区域；

为不同的区域分配不同的可见性指示符；

基于所述区域的预定序列编码所述可见性指示符；以及

将包括经编码的可见性指示符的数据结构存储在存储器中。