CN106251384B - 使用三角形的递归再分的细分方法 - Google Patents

Abstract

本公开涉及使用三角形的递归再分的细分方法。描述了使用为可以是四边形、三角形或等值线的补片的每个顶点定义的细分因数的细分方法。该方法在计算机图形系统中实现并涉及比较顶点细分因数与阈值。如果定义初始补片的边的左顶点或右顶点的顶点细分因数超过阈值，则边通过将边分成两个部分的新顶点的添加而被再分且两个新补片形成。对在每个最新形成的补片中的每个顶点计算新顶点细分因数，这两个补片都包括最新添加的顶点。对于每个最新形成的补片然后重复该方法，直到没有一个顶点细分因数超过阈值为止。

Description

使用三角形的递归再分的细分方法

背景

细分是在计算机图形中用于将表示在场景中的对象的一组表面分割成一般是三角形的多个更小和更简单的片(被称为基元)的技术，更小和更简单的片更容易渲染。因而产生的细分的表面通常是对原始表面的近似，但这个近似的准确度可通过增加所产生的基元来改进，这又通常导致基元更小。细分/再分的量通常由细节级别(LOD)确定。因此一般使用增加数量的基元，其中需要更高的细节级别，例如因为对象更接近观看者和/或对象具有更复杂的形状。然而，更大数量的三角形的使用增加了渲染场景所需的处理能力。

一般对补片执行再分成三角形基元，补片在形状上是正方形或三角形的(即四边形或三角形)并可弯曲以与它们代表的对象的表面保持一致(并因此可被称为“表面补片”)和/或使位移映射被应用。然而，再分不对弯曲的补片执行而替代地在补片的域中被执行(例如，好像补片是平面的，而不是由例如多项式方程定义)，补片的域可依据(u,v)参数进行定义的并被称为“参量空间”。这意味着细分过程与在最终表面中存在的任何曲率无关。

细分可提前被执行(例如以计算在不同的细节级别处和/或来自不同的视点的场景的多个不同的视图)或可在运行中被执行(例如以提供连续的或视图相关的细节级别)。使用一些现有的细分方法，用户可经历不希望有的视觉伪像，其中虽然所请求的细节级别平稳地改变，但是产生的细分是以间断的方式改变。

下面所述的实施方式仅作为例子被提供，且并不是解决用于执行细分的已知方法和装置的任何缺点或所有缺点的实现的限制。

概述

这个概述被提供来介绍了简化形式的选择的概念，其在下面在详细描述中被进一步描述。这个概述并不打算识别所主张的主题的关键特征或必要特征，也不打算用作在确定所主张的主题的范围时的帮助。

描述了使用为补片的每个顶点定义的细分因数的细分方法，补片可以是四边形、三角形或等值线。该方法在计算机图形系统中实现并涉及比较顶点细分因数与阈值。如果定义初始补片的边的左顶点或右顶点的顶点细分因数超过阈值，则边通过将边分成两个部分的新顶点的添加而被再分且两个新补片形成。对在每个最新形成的补片中的每个顶点计算新顶点细分因数，这两个补片都包括最新添加的顶点。然后对每个最新形成的补片重复该方法，直到没有一个顶点细分因数超过阈值为止。

第一方面提供在计算机图形系统中执行细分的方法，该方法包括：对于包括由边连接并在域空间中定义的左顶点和右顶点的初始补片：将左顶点的顶点细分因数和右顶点的顶点细分因数与阈值进行比较；响应于确定左顶点和右顶点的顶点细分因数中没有一个超过阈值，输出描述初始补片的数据；以及响应于确定左顶点和右顶点的顶点细分因数中有任一个超过阈值，形成将边再分成两个部分的新顶点，计算新顶点的顶点细分因数，分割初始补片以形成包括左顶点和新顶点的第一新补片以及包括右顶点和新顶点的第二新补片，并减小在每个最新形成的补片中的每个顶点的顶点细分因数。

新顶点可平分边。

该方法还可包括：使用每个最新形成的补片作为初始补片重复该方法。对作为初始补片的每个最新形成的补片重复该方法可包括：对作为初始补片的每个最新形成的补片重复该方法，直到在每个补片中的左顶点和右顶点的顶点细分因数不超过阈值为止。

计算新顶点的顶点细分因数可包括：计算左顶点和右顶点的顶点细分因数的平均值；以及设置新顶点的顶点细分因数等于所计算的平均值。左顶点和右顶点的顶点细分因数的平均值可由下式给出：

MEAN(LEFT.TF,RIGHT.TF)＝MIN(AVG(LEFT.TF,RIGHT.TF),MIN(LEFT.TF,RIGHT.TF)+INTERVAL)

其中LEFT.TF是左顶点的顶点细分因数，RIGHT.TF是右顶点的顶点细分因数，AVG()是在括弧内的值的算术平均值，MIN()是在括弧内的值的列表中的最小值，以及INTERVAL是预先定义的参数。

减小在每个最新形成的补片中的每个顶点的顶点细分因数可包括将每个顶点细分因数减小预先定义的参数INTERVAL。参数INTERVAL可以是0.5。

阈值可以等于零。

初始补片可以是由两个顶点定义的等值线补片，所述两个顶点包括左顶点和右顶点。

初始补片可以是三角形补片，且其中三角形补片是三个顶点的有序集合：上顶点、右顶点和左顶点。被分割的补片可以是两个最新形成的补片的父补片，以及其中第一新补片是三个顶点的有序集合：为被添加到父补片的新顶点的上顶点；为父补片的左顶点的右顶点；以及为父补片的上顶点的左顶点；以及其中第二新补片是三个顶点的有序集合：为被添加到父补片的新顶点的上顶点；为父补片的上顶点的右顶点；以及为父补片的右顶点的左顶点。

该方法——其中初始补片是三角形补片——还可包括：接收输入补片；以及从输入补片产生一个或多个初始补片；以及对于多个初始补片中的每个重复该方法。输入补片可以是具有三个顶点的三角形补片，且其中产生一个或多个初始补片可包括：将三个顶点中的每个的顶点细分因数与阈值比较；响应于确定没有一个顶点细分因数超过阈值，输出描述输入补片的数据；以及响应于确定至少一个顶点细分因数超过阈值，形成在三角形的中心处的新顶点，计算新顶点的顶点细分因数，分割输入补片以形成三个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片，以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。新顶点可在三角形的质量中心处形成。输入补片的三个顶点可以是上顶点、左顶点和右顶点，且可使用下式来计算在三角形的中心处的新顶点的顶点细分因数：

MID.TF＝MEAN(TOP.TF,LEFT.TF,RIGHT.TF)

其中MID.TF是新顶点的顶点细分因数，TOP.TF是上顶点的顶点细分因数，LEFT.TF是左顶点的顶点细分因数，以及RIGHT.TF是右顶点的顶点细分因数，以及MEAN()是在括弧内的值的平均值。

可使用下式来计算MEAN(TOP.TF,LEFT.TF,RIGHT.TF)：

MEAN(TOP.TF,LEFT.TF,RIGHT.TF)＝MIN(AVG(TOP.TF,LEFT.TF,RIGHT.TF),MIN(TOP.TF,LEFT.TF,RIGHT.TF)+INTERVAL)

其中AVG()是在括弧内的值的算术平均值，MIN()是在括弧内的值的列表中的最小值，以及INTERVAL是预先定义的参数。

输入补片可以是具有四个顶点的四边形补片，以及其中产生一个或多个初始补片可包括：形成在四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割输入补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片可以是具有四个顶点和中心细分因数的四边形补片，以及其中产生一个或多个初始补片可包括：添加五个新顶点以将输入补片再分成四个子输入四边形补片；计算五个最新添加的顶点中的每个的顶点细分因数；减小在最新形成的四个子输入补片中的每个顶点的顶点细分因数；以及对于每个子输入补片：形成在四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割输入补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片可以是具有三个顶点和中心细分因数的三角形补片，以及其中产生一个或多个初始补片可包括：添加四个新顶点以将输入补片再分成三个子输入四边形补片；计算四个最新添加的顶点中的每个的顶点细分因数；减小在最新形成的三个子输入补片中的每个顶点的顶点细分因数；以及对于每个子输入补片：形成在四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割输入补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片的四个顶点可以是左上顶点、右上顶点、左下顶点和右下顶点，且可使用下式计算在三角形的中心处的新顶点的顶点细分因数：

MID.TF＝MEAN(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF)其中MID.TF是新顶点的顶点细分因数，TLEFT.TF是左上顶点的顶点细分因数，TRIGHT.TF是右上顶点的顶点细分因数，BLEFT.TF是左下顶点的顶点细分因数，BRIGHT.TF是右下顶点的顶点细分因数，以及MEAN()是在括弧内的值的平均值。

可使用下式来计算MEAN(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF)：

MEAN(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF)＝MIN(AVG(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF),MIN(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF)+INTERVAL)

其中AVG()是在括弧内的值的算术平均值，MIN()是在括弧内的值的列表中的最小值，以及INTERVAL是预先定义的参数。

减小在每个最新形成的初始补片中的每个顶点的顶点细分因数可包括将每个顶点细分因数减小预先定义的参数INTERVAL。

第二方面提供包括硬件逻辑的硬件细分单元，硬件逻辑配置成：对于包括由边连接并在域空间中定义的左顶点和右顶点的初始补片：将左顶点的顶点细分因数和右顶点的顶点细分因数与阈值进行比较；响应于确定左顶点和右顶点的顶点细分因数中没有一个超过阈值，输出描述初始补片的数据；以及响应于确定左顶点和右顶点的顶点细分因数中有任一个超过阈值，形成将边再分成两个部分的新顶点，计算新顶点的顶点细分因数，分割初始补片以形成包括左顶点和新顶点的第一新补片以及包括右顶点和新顶点的第二新补片，并减小在每个最新形成的补片中的每个顶点的顶点细分因数。

其中，所述新顶点平分所述边。

硬件逻辑还可以被配置为利用最新形成的补片作为初始补片来重复所述硬件逻辑的操作。

其中，所述硬件逻辑配置成对作为所述初始补片的每个最新形成的补片重复所述硬件逻辑的操作，直到在每个补片中的所述左顶点和所述右顶点的顶点细分因数不超过所述阈值为止。

配置成计算新顶点的顶点细分因数的硬件逻辑可包括配置成执行下列操作的硬件逻辑：计算左顶点和右顶点的顶点细分因数的平均值；以及设置新顶点的顶点细分因数等于所计算的平均值。

其中，所述左顶点和所述右顶点的顶点细分因数的平均值由下式给出：

MEAN(LEFT.TF,RIGHT.TF)＝MIN(AVG(LEFT.TF,RIGHT.TF),MIN(LEFT.TF,RIGHT.TF)+INTERVAL)

其中LEFT.TF是所述左顶点的顶点细分因数，RIGHT.TF是所述右顶点的顶点细分因数，AVG()是在括弧内的值的算术平均值，MIN()是在括弧内的值的列表中的最小值，以及INTERVAL是预先定义的参数。

其中，配置成减小在每个最新形成的补片中的每个顶点的顶点细分因数的所述硬件逻辑包括将每个顶点细分因数减小预先定义的参数INTERVAL。

初始补片可以是由两个顶点(左顶点和右顶点)定义的等值线补片。

初始补片可以是三角形补片，且其中三角形补片是三个顶点的有序集合：上顶点、右顶点和左顶点。被分割的补片可以是两个最新形成的补片的父补片，以及其中第一新补片是三个顶点的有序集合：为被添加到父补片的新顶点的上顶点；为父补片的左顶点的右顶点；以及为父补片的上顶点的左顶点；以及其中第二新补片是三个顶点的有序集合：为被添加到父补片的新顶点的上顶点；为父补片的上顶点的右顶点；以及为父补片的右顶点的左顶点。

硬件细分单元还可包括配置成执行下列操作的硬件逻辑：接收输入补片；从输入补片产生一个或多个初始补片；以及对于多个初始补片中的每个重复所述硬件逻辑的操作。

输入补片可以是具有三个顶点的三角形补片，且其中配置成产生一个或多个初始补片的硬件逻辑可包括配置成执行下列操作的硬件逻辑：将三个顶点中的每个的顶点细分因数与阈值进行比较；响应于确定没有一个顶点细分因数超过阈值，输出描述输入补片的数据；以及响应于确定至少一个顶点细分因数超过阈值，形成在三角形补片的中心处的新顶点，计算新顶点的顶点细分因数，分割输入补片以形成三个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片，以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片可以是具有四个顶点的四边形补片，以及其中配置成产生一个或多个初始补片的硬件逻辑可包括执行下列操作的硬件逻辑：形成在四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割输入补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片可以是具有四个顶点和中心细分因数的四边形补片，以及其中配置成产生一个或多个初始补片的硬件逻辑可包括配置成执行下列操作的硬件逻辑：添加五个新顶点以将输入补片再分成四个子输入四边形补片；计算五个最新添加的顶点中的每个的顶点细分因数；减小在最新形成的四个子输入四边形补片中的每个顶点的顶点细分因数；以及对于每个子输入四边形补片：形成在每个子输入四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割每个子输入四边形补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

输入补片可以是具有三个顶点和中心细分因数的三角形补片，以及其中配置成产生一个或多个初始补片的硬件逻辑可包括配置成执行下列操作的硬件逻辑：添加四个新顶点以将输入补片再分成三个子输入四边形补片；计算四个最新添加的顶点中的每个的顶点细分因数；减小在最新形成的三个子输入四边形补片中的每个顶点的顶点细分因数；以及对于每个子输入四边形补片：形成在每个子输入四边形补片的中心处的新顶点；计算新顶点的顶点细分因数；分割每个子输入四边形补片以形成四个初始补片，每个初始补片是以新顶点作为上顶点的三角形补片；以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数。

第三方面提供了包括如在上面阐述的硬件细分单元的图形处理单元。

另外的方面提供了其上存储有在被执行时使至少一个处理器执行如在上面阐述的方法的计算机可执行程序代码的非暂时性的计算机可读存储介质、包括如在上面阐述的硬件细分单元的图形处理单元、具有在其上编码的定义如在上面阐述的硬件细分单元的计算机可读程序代码的计算机可读存储介质以及具有在其上编码的定义配置成执行如在上面阐述的方法的硬件细分单元的计算机可读程序代码的计算机可读存储介质。

如将对技术人员明显的是，优选特征可以视情况被组合，并可与本发明的任一方面组合。

附图的简要说明

现在将参考附图作为例子描述本发明的实施方式，其中：

图1示出使用各种已知的细分方法的结果；

图2是示出使用具有边细分因数的现有技术方法和使用顶点细分因数的本文所述的方法得到的不同结果的例子的示意图；

图3示出使用本文所述的改进的细分方法得到的示例结果的各种例子；

图4示出使用本文所述的改进的细分方法得到的另外的示例结果；

图5是改进的细分方法的流程图；

图6是示出各种输入补片并示出图5的方法的预处理阶段的示意图；

图7是用于三角形输入补片的图5的方法的预处理阶段的流程图；

图8是用于四边形输入补片的图5的方法的预处理阶段的流程图；

图9是将算法递归地应用于由预处理阶段输出的三个或四个三角形补片中的每个或应用于输入等值线补片的流程图；

图10是示出说明图9的方法的三角形的示意图；

图11是示出说明本文所述的改进的细分方法的三角形的示意图；

图12是本文所述的改进的细分方法的所示例子；

图13是示出可使用本文所述的改进的细分方法产生的三角形类别的示意图；

图14示出使用本文所述的改进的细分方法和已知的细分方法得到的结果之间的比较；

图15是改进的细分方法的另一示例流程图且是对图5所示的方法的变形；

图16是示出图15的方法的示意图；

图17是图15的方法的额外的预处理阶段的流程图；

图18示出使用图15的方法得到的示例结果；

图19是示例性GPU管线的示意图；以及

图20示出可被实现为任何形式的计算和/或电子设备的并可配置成实现本文所述的改进的细分方法的示例性基于计算的设备的各种部件。

共同的参考数字在全部附图中用于指示相似的特征。

详细描述

下面仅作为例子描述本发明的实施方式。这些例子代表实施本发明的、申请人当前已知的最佳方式，虽然它们并不是本发明可被实现的唯一方式。该描述阐述例子的功能和用于构造和操作例子的步骤的顺序。然而，相同或等效的功能和顺序可由不同的例子来实现。

存在多种已知的使用边细分因数(TF)的细分方法，边细分因数对(例如四边形或三角形)补片的每条边进行定义并确定边(和因而补片)应被再分多少次。图1示出当使用不同的边细分因数时因而产生的三角形如何不同，但对每条边是相同的细分因数。

在图1中的前四个例子(a)-(d)示出：

(a)整数分割，对于所有四条边，边TF＝3

(b)整数分割，对于所有四条边，边TF＝4

(c)二次幂整数分割，对于所有四条边，边TF＝3

(d)二次幂整数分割，对于所有四条边，边TF＝4

使用整数分割和二次幂整数分割，沿着每条边的顶点总是均匀地间隔开；然而，不想要的视觉伪像(例如下面解释的)非常可能出现在再分级别改变的且三角形不是很小的地方，但当小多边形带来额外的渲染开销时，使多边形这么小是不合乎需要的。这个效应对二次幂整数分割是特别动态的，因为步长可以大得多。

在图1中的后四个例子(e)-(h)示出(与例子(a)-(d)不同)产生在变化的偏移处的顶点的分数分割方法：

e)奇数分数分割，对于所有四条边，边TF＝3.0

f)奇数分数分割，对于所有四条边，边TF＝4.0

g)偶数分数分割，对于所有四条边，边TF＝3.0

h)偶数分数分割，对于所有四条边，边TF＝4.0

当选择细分方法时，其他考虑因素不仅包括对边细分设置的给定组合产生的三角形的数量(因为细分的模型的渲染成本部分地取决于三角形的数量)，而且包括那些三角形的高宽比。一般，图形系统(软件或硬件)将比渲染具有相同的面积但更高的周长与面积比的(长细)三角形更快地渲染暗示最小周长与面积比的给定屏幕面积(即屏幕像素)的“等边”三角形。此外，当值(例如明暗处理的结果)在顶点处被计算并接着跨三角形被内插时，有更等边形状的三角形应导致更少的伪像。

另一考虑因素是用于产生三角形的模式的算法的复杂度。如果算法可保持简单和/或有规律(例如没有需要不同地被处理的很多“特殊情况”)，这可减小硬件或软件实现成本。

最后合乎需要的考虑因素是在细分模式中的旋转/反射对称性。例如，使用以比如顺时针顺序ABCD给出的顶点并使用适当的细分因数定义的四边形补片产生与具有被列为BCDA的顶点的“等效”四边形相同的最终三角形网将是优选的。一些现有的细分方案不保证这个特性(例如见在图1的例子(e)和(f)中的“奇数”细分方法中的中间正方形)。

在这个描述中，表面补片涉及通常有限的N维表面(或在等值线的情况下，N维曲线段)，其为将参数映射函数应用于有界限的2D域的结果，该2D域是四边形或三角形(或在等值线的情况下，1D线段)。因而产生的表面或等值线可被考虑为N维的，因为它可不仅包括用于笛卡尔(或同质)空间定位的3(或4)维，而且包括其它参数例如纹理坐标。如上所述，表面补片可弯曲以与它们代表的对象的表面保持一致和/或使位移映射被应用。然而，细分(即补片的再分)不在“自然空间”中被执行(即它不对弯曲表面补片执行)而替代地在域空间中(这也可被称为参量空间或参数空间)被执行，其中域中的任何位置可由被称为域空间坐标的两个坐标(u,v)描述，这意味着细分过程与存在于最终表面中的任何曲率无关。

在本文描述了改进的细分方法，且描述这个细分方法时，术语“补片(patch)”用于指形成域的界限的两个、三个或四个顶点(分别对于等值线、三角形或四边形)的有序集合。术语“域(domain)”因此指由补片的顶点形成界限的二维空间。术语“顶点(vertex)”通常用于描述位置加上其它属性，其中这些属性根据上下文而不同。例如，来自域着色器的输入控制点和输出顶点包括3D位置加上其它参数，例如法线、切线、纹理等，而在细分器内的顶点(即在细分方法内使用的顶点)包括域空间坐标和顶点细分因数。在细分器内的这些顶点因此与输入控制点或形成最终三角形的因而产生的N维顶点不相同。

在本文描述了改进的细分方法，其不使用边细分因数而是替代地使用为四边形或三角形的每个角顶点或等值线的每个端顶点定义的细分因数。这些细分因数被称为“顶点细分因数”以将它们与在上面描述的已知方法中使用的边细分因数区分开。如下面详细描述的，当补片的任一顶点细分因数超过规定阈值时，细分(即补片的再分)出现。当新顶点被添加时，这些将边再分成两个部分(其中在各种例子中，这两个部分可相等，使得边被平分)，且该方法递归地作用于三角形补片。

本文所述的改进的细分方法处理在已知的细分方法中产生的一个或多个(和在各种例子中，所有)下面的问题：

·突然的举动(Snapping)——瞬间出现的大量细分的效应。这可不仅引起在动画中的临时视觉伪像，而且导致不连续的渲染时间。这特别是针对“二次幂”方法(例如图1中的例子(c)和(d))的问题。

·破裂——在边界上的边的再分需要是一致的以避免T结。在应用位移映射之后，任何T结将几乎一定导致观看者能够看穿对象的裂缝的出现。

·漂浮——根据顶点的细分因数在域空间中移动顶点的位置导致当位移的量改变时看起来发微光或“漂浮”的几何结构。

·无过/欠细分——例如，32的细分因数需要边被再分成32段。少于此则可导致网没有精制到足以对场景建模。多于此则可导致网太精制并使用太多的计算。

·细三角形——渲染细三角形可导致更多的混叠伪像以及在计算上昂贵，因为三角形的渲染成本不仅取决于它的屏幕像素面积而且在某种程度上取决于它在屏幕像素中的周长的长度。因此渲染由N个“接近等边的”三角形表示的补片比由N个“长细”三角形表示的相同补片通常更有效，尤其是在细三角形随着LOD改变而消失且基本上多余的时候。因此，下面所述的方法目的在于最大化最小的面积与周长比的平方根(Root Area toPerimeter Ratio)。

·空间/时间复杂度——任何细分方法应理想地是简单的和高度并行的并最小化时间和空间复杂度(即执行渲染所花费的时间和实现算法所需的存储区的量)。它也必须不将太多的位添加到顶点的尺寸，因为这增加了对存储器的要求。空间和时间复杂度也影响执行细分所需的硬件的物理面积。

指定在补片的角处的TF导致在细分的补片内的因而产生的三角形的尺寸和形状上的更少的突然变化，因为边的分割未固定(即到由边TF指定的值)，但替代地由在边的每端处的顶点TF确定，且不仅沿着原始边(在参量空间中的1D方向上)平稳地改变以产生在再分级别之间的逐渐过渡，而且也结合其它TF允许它在2D方向上跨补片平稳地改变。这在图2中用图形示出，图2示出，在域空间中在使用已知的方法定义在边(图202)处的细分因数和定义在角(或顶点，图204)处的细分因数之间的差异。第一图202是在具有2和4的边细分因数的两个四边形的情况下使用跨边的所定义的二次幂定义的细分因数的结果。第二图204使用下面所述的方法以及2(关于顶点206、208)和4(关于顶点210-216)的顶点细分因数。

在图3和图4中示出具有四边形和三角形补片的各种整数和分数细分因数的另外的例子。注意，仅为了比较目的，在例子中，给定数字顶点细分因数在已知的基于边的细分方案中近似同等地采用因数的以2为底的对数。在每个例子之下的正文显示以下列顺序的顶点细分因数：对于四边形补片(左上、右上、左下、右下)和对于三角形补片(上、左下、右下)。从这些例子中可看到，在补片内的再分级别之间有逐渐过渡，没有长细三角形被创建，以及顶点放置在域空间中的其最终位置处且当LOD增加时不移动(它们只在域空间中的固定位置处出现或消失)。

如下面所述的，连同基于顶点的细分因数一起，这个改进的细分方法最小化(或消除)不希望有的视觉伪像，因为每个顶点(例如作为到三角形的再分的部分而被添加的每个新顶点)总是被添加在域空间中的其最终位置处。结果是，当细节级别(和因而TF)改变时，顶点不像一些现有技术中的那样在整个表面上“滑动”，这可引起漂浮/摆动伪像。

图5是改进的细分方法的流程图。当补片(被称为输入补片)被馈送到细分器内时，该方法开始。细分器(其可以是硬件细分器)接收输入补片(块502)，其中这个输入补片可以是三角形补片602、四边形补片604或等值线补片606，如图6所示。虽然四边形补片606是在域空间中的正方形(顶点为(0,0)、(1,0)、(0,1)和(1,1))，但是其在自然空间中(即在3D或2D环境内)代表的形状可以是不同的形状。如上所述，细分是在域空间中而不是在自然空间中被执行。

如果输入补片是三角形补片或四边形补片，则在细分算法递归地应用于在输入补片内的三角形补片(块506)之前补片经历“预处理”阶段(块504)。预处理阶段用于确保细分独立于方位，且因此，对等值线补片606是不需要的(因为算法对称地工作，且所以没有任何因而产生的细分的方位相关性)。

如果输入补片是三角形补片602，则预处理阶段(块504)输出一个三角形补片602(其与输入三角形补片相同，且其中不需要细分)或三个三角形补片608-610。如果输入补片是四边形补片604，则预处理阶段(块504)输出四个三角形补片612-615。如果输入补片是等值线补片，则不需要预处理(由于上面阐述的原因)且细分算法递归地应用于输入等值线补片(块508)。

图7-10更详细地示出改进的细分方法的阶段。如所述的该方法使用下面的标记：

·THRES–细分的阈值，其可例如被设置为0.0或0.5，其中顶点TF是到以2为底的对数的细分的量的值。

·VERTEX.TF–顶点的细分因数，其可以是任何实数(虽然在各种例子中，任何负值可被强制限制到零，使得细分因数是非负实数)。在各种例子中，顶点TF是至少0.0(无细分)和至多6.0(最大细分)，其中以2为底的对数的细分的量的值，例如5.0的细分因数相应于32个再分。然而在其它例子中，最大顶点TF可超过6.0(或64，其中未使用以2为底的对数)。

·INTERVAL–在每次迭代之后VERTEX.TF减小的非零数量，其可例如被设置为0.5，其中顶点TF是以2为底的对数的细分的量的值。

·MEAN()–给出二、三或四个顶点细分因数的“平均值”的对称函数。这可以是算术平均或可选的函数，且下面更详细描述一个这样的可选函数。

为了下面的描述的目的，顶点TF是以2为底的对数的细分的量；然而，将认识到，它可以可选地被写为它的实际全值，且在这种情况下，下面阐述的顶点TF的计算以及参数THRES和INTERVAL的值将相应地被修改。然而，因为硬件实现快得多，其中使用以2为底的对数，在到细分器的输入包括实际顶点TF(而不是使用以2为底的对数)的例子中，输入顶点TF可在实现本文所述的改进的细分方法之前转换成以2为底的对数。

图7是三角形输入补片602的预处理阶段504的流程图，且如图6所示，三角形补片的顶点可被标记为“TOP”、“RIGHT”和“LEFT”。哪个顶点是“上”是任意选择的，且这个预处理阶段确保算法是旋转和反射性地对称的(即，使得相同的细分结果被实现，而不考虑顶点在这个预处理阶段中被考虑的顺序)。

如图7所述，当三角形补片(TOP,RIGHT,LEFT)602被馈送到细分器内且任何顶点细分因数大于阈值时，THRES(在块702中的“是”)细分出现。被表示为“MID”的新顶点616在三角形的中心处(例如在质量中心处)形成(块704)，且新MID顶点的顶点TF被计算(在块706中)为：

MID.TF＝MEAN(TOP.TF,LEFT.TF,RIGHT.TF) (1)

其中MID.TF是MID顶点的顶点TF，TOP.TF是TOP顶点的顶点TF，LEFT.TF是LEFT顶点的顶点TF，以及RIGHT.TF是RIGHT顶点的顶点TF。所有四个细分因数(即TOP.TF、LEFT.TF、RIGHT.TF和MID.TF)然后减小了参数INTERVAL(即通过减去INTERVAL，其中以2为底的对数标记被使用)，因为一些细分出现(块708)。

三个三角形补片(MID,RIGHT,LEFT)610、(MID,LEFT,TOP)609和(MID,TOP,RIGHT)608然后形成(块710)，且正是这些三角形补片使用如下所述的细分算法被细分(在块506中)。

如果没有一个顶点细分因数大于阈值THRES(在块702中的“否”)，则没有细分出现。在这种情况下，补片简单地作为一个基元穿过细分器(块712)，以便使该方法没有过度细分。

图8是四边形输入补片604的预处理阶段504的流程图，且如图6所示，四边形补片的顶点可被标记为“TLEFT(或左上)”、“TRIGHT(或右上)”、“BRIGHT(或右下)”和“BLEFT(或左下)”。哪些顶点是“上”和哪些是“下”是任意选择的，且这个预处理阶段确保算法是旋转和反射性地对称的(即，使得相同的细分结果被实现，而不考虑顶点在这个预处理阶段中被考虑的顺序)。

如图8所述，当四边形补片(TLEFT,TRIGHT,BLEFT,BRIGHT)604被馈送到细分器内时，被表示为“MID”的新顶点618在四边形的中心处、即在域空间坐标(0.5,0.5)处形成(块804)，且新MID顶点的顶点TF被计算(在块806中)为：

MID.TF＝MEAN(TLEFT.TF,TRIGHT.TF,BLEFT.TF,BRIGHT.TF) (2)

其中MID.TF是MID顶点的顶点TF，TLEFT.TF是TLEFT顶点的顶点TF等。所有五个细分因数(即TLEFT.TF、TRIGHT.TF、BRIGHT.TF、BLEFT.TF和MID.TF)然后减小了参数INTERVAL(即通过减去INTERVAL，其中以2为底的对数标记被使用)，因为一些细分出现(块808)。

四个三角形补片(MID,TLEFT,TRIGHT)612、(MID,TRIGHT,BRIGHT)613、(MID,BRIGHT,BLEFT)614和(MID,BLEFT,TLEFT)615然后形成(块810)，且正是这些三角形补片使用如下所述的细分方法被细分(在块506中)。

图9是将算法递归地应用于由预处理阶段输出的三个或四个三角形补片中的每个的流程图，且这可参考图10所示的三角形被描述。如图10所示，三角形补片是在顺时针方向上的三个顶点(TOP,RIGHT,LEFT)的有序集合。注意，第一顶点总是“TOP”顶点，且对于初始三角形补片(如由预处理阶段输出的)，这个“TOP”顶点相应于在预处理期间添加的“MID”顶点608、618(块704、804)。

如图9所示，给定三角形补片1000(其在第一次迭代中是初始补片900)，当且仅当下式成立时细分出现：

LEFT.TF>THRES或RIGHT.TF>THRES (3)

其中LEFT.TF是LEFT顶点的顶点TF，且RIGHT.TF是RIGHT顶点的顶点TF(在块902中的“是”)。

如果LEFT.TF>THRES或RIGHT.TF>THRES(在块902中的“是”)，则形成新顶点MID1002(在块904中)，其在域空间(由箭头1004指示)中将边LEFT->RIGHT分成两个部分。新MID顶点的顶点细分因数然后被计算(在块906中)为：

MID.TF＝MEAN(LEFT.TF,RIGHT.TF) (4)

其中MID.TF是MID顶点的顶点TF，LEFT.TF是LEFT顶点的顶点TF，以及RIGHT.TF是RIGHT顶点的顶点TF。为了协定起见，定义MID再分的边的顶点LEFT和RIGHT被表示为MID的“父亲”。

在很多例子中，新顶点MID作为在域空间中的边LEFT->RIGHT的二等分线被添加。然而，在其它例子中，新顶点MID可被添加在一个位置处，该位置在域空间中的边LEFT->RIGHT上但并非绝对地平分它。在各种例子中，沿着边的MID的位置可例如使用父顶点的顶点TF进行加权。

两个子三角形补片(MID,LEFT,TOP)1006和(MID,TOP,RIGHT)1008形成(块908和910)，且在每个三角形补片1006、1008中的所有细分因数减小了参数INTERVAL(块912，即通过减去INTERVAL，其中以2为底的对数标记被使用)。该方法然后在这些补片中的每个上递归。当对在块908或块910中创建的三角形补片执行该方法时，“TOP”顶点相应于被添加(在块904中)以创建补片的“MID”顶点1002，且这对父补片的“TOP”顶点将是不同的(例如补片1000可被考虑为补片1006和1008的父亲，且1000的“TOP”顶点1010与补片1006和1008中的每个的“TOP”顶点1002不同)。

如果在任何阶段没有细分出现(在块902中的“否”)，则基元(其为补片)被添加到缓冲器(块914)，例如到索引缓冲器。

如上所述，图9的方法应用于由预处理阶段(块504)产生的三个或四个三角形补片中的每个并递归地应用于通过那些初始补片的再分而创建的任何补片。

因为顶点细分因数是有限的且INTERVAL是不变的和非零的，最终所有顶点细分因数(在所有三角形补片中)将至多是THRES且该过程将终止。

如可在图10中看到的，最新添加的MID顶点是在被形成(在块908和910中)的这两个补片中的顶点，且在这两个补片中，这个顶点被考虑为“TOP”顶点。当递归成两个子补片时，最新添加的MID顶点的顶点细分因数的当前值必须被使用。在可通过为每个子补片复制顶点TF或有对算法的最后步骤而确保的示例实现中，其中对于任何补片且在它的两个子补片上递归之后，每个顶点TF增加了参数INTERVAL。

在图9中使用的相同算法也可应用于等值线补片(在块508中)，虽然如上所述，不需要预处理，且在等值线补片的情况下，算法应用于线(即等值线和子等值线)而不是如可参考图6所述的三角形。

如果等值线补片(LEFT,RIGHT)606被馈送到细分器(作为初始补片900)，则如果LEFT.TF或RIGHT.TF高于THRES(在块902中的“是”)，线被再分。如果LEFT.TF或RIGHT.TF高于THRES(在块902中的“是”)，则添加在域空间中再分(例如平分)LEFT->RIGHT等值线606(块904)的新MID顶点620。最新添加的MID顶点的顶点TF被计算(在块906中)为：

MID.TF＝MEAN(LEFT.TF,RIGHT.TF) (5)

其中MID.TF是MID顶点的顶点TF，LEFT.TF是LEFT顶点的顶点TF，以及RIGHT.TF是RIGHT顶点的顶点TF。

MID顶点620的添加将原始等值线606分成两个子等值线622、624(在块908和910中形成)，且每个顶点TF减小了2*INTERVAL(在块912中，即通过减去2*INTERVAL，其中以2为底的对数标记被使用)——注意，这比三角形补片产生再分的正确量更快地减小顶点TF。该方法然后在这些子等值线中的每个上递归并在所有顶点细分因数是至多THRES时终止。

上面所述的改进的细分方法使用MEAN()函数。虽然这在一些例子中可以是顶点细分因数的算术平均，这在从一个顶点移动到另一顶点时将导致几何结构的平稳引入，这样的函数将常常导致T结出现和因而针对顶点TF的某些值而破坏(例如在整个补片上的顶点TF中的差异是相当极端的)。因此，在很多例子中，可选的函数如下用于MEAN()：

MEAN(TF1,TF2,…)＝MIN(AVG(TF1,TF2,…),MIN(TF1,TF2,…)+INTERVAL) (6)

其中AVG()是在括弧内的值的列表的算术平均值(例如在上面的例子中的顶点TF1、顶点TF2、…)，且MIN()是在括弧内的值的列表(例如在上面的例子中的顶点TF1、顶点TF2、…)中的最小值。

上面给出的MEAN()函数是确保没有破裂的最接近算术平均值的函数，且这可展示为如下面所阐述的。

如上所述，在细分内的T结可导致破裂，且因此可能希望确保没有T结可在域的内部中或沿着由两个域共用的边产生。本文所述的改进的细分方法通过保证任何边的再分唯一地由边的端顶点的细分因数(且不由其它)定义来确保此。因此，如果边被两个域(即两个相邻域)共用，则域共用它的两个端顶点(和它们的顶点细分因数)，且相同的再分将产生。

如上所述，只有当端顶点细分因数超过阈值时，再分才出现，所以没有额外的再分可出现。唯一的可能问题是如果由于以前的再分的级别未提前发生，再分在它应出现时不出现，且因此为了避免这个问题，必须满足下面的条件(其指的是具有如在图10中所示的标记的顶点的三角形补片1000)：

在TOP->LEFT边上所需的细分暗示在LEFT->RIGHT边上发生的细分

即(TOP.TF>THRES或LEFT.TF>THRES)

＝>(LEFT.TF+INTERVAL>THRES或RIGHT.TF+INTERVAL>THRES)

这个条件在不失去一般性的情况下考虑由于对称性只考虑左手边。

可接着证明上面规定的MEAN()函数满足这个条件：

情况1：如果LEFT.TF>THRES则LEFT>TF+INTERVAL>THRES

情况2：TOP.TF>THRES具有下面的两个子情况：

情况2.1(TOP是如在图10中的补片1000中所示的补片的中间顶点，且这相应于在图6中的顶点616或618)，即TOP.TF＝MEAN(LEFT.TF,RIGHT.TF,…))，因此

THRES<TOP.TF

＝MIN(AVG(LEFT.TF,RIGHT.TF,…),MIN(LEFT.TF,RIGHT.TF,…)+INTERVAL)

<＝MIN(LEFT.TF,RIGHT.TF,…)+INTERVAL

<＝LEFT.TF+INTERVAL

所以LEFT.TF+INTERVAL>THRES。

情况2.2(TOP通过具有LEFT的再分产生，作为端顶点，如在图11中的补片1100中所示，其中TOP 1102通过边LEFT->OTHER的再分产生，即TOP.TF＝MEAN(LEFT.TF,…))，所以

THRES<TOP.TF

＝MIN(AVG(LEFT.TF,…),MIN(LEFT.TF,…)+INTERVAL)

<＝MIN(LEFT.TF,…)+INTERVAL

<＝LEFT.TF+INTERVAL

所以LEFT.TF+INTERVAL>THRES。

在情况2.2中，同一逻辑可应用于TOP.TF＝MEAN(RIGHT.TF,…)(其相应于在图11中所示的反射)以如所希望的得到RIGHT.TF+INTERVAL>THRES。还要注意的是，函数的选择是最佳的，因为超过最小值加上INTERVAL的任何函数将不总是满足这些不等式。因此，MEAN()函数不能是更接近算术平均值的任何函数。

通过使用以2为底的对数标记以及如图12所示的THRES＝0.0和INTERVAL＝0.5以细分因数(2,1,1,1)来细分四边形1202的例子，来进一步描述改进的细分方法。在预处理阶段(块504和图8)中，添加具有细分因数1.25(在块806中计算的算术平均值)的中间顶点1204(在块804中)。形成四个三角形补片(在块810中)，中间顶点作为每个补片的上顶点，将每个TF减小了0.5(在块808中，这可在块810之前或之后被执行)，如在图12中的第二例子1206中所示的。

在每个三角形补片(块506和图9)上的第一递归中，每个下边被再分(在块902中，因为0.5高于阈值THRES＝0.0)，且四个新顶点(具有新顶点TF)和八个新补片形成(在块904-910中)，如在图12的第三例子1208中所示的。所有细分因数然后减小0.5——如在图12中的第四例子1210中所示的INTERVAL(在块912中)的值。

在八个三角形补片的每个上的下一递归中，通过添加新顶点、计算那些新顶点的顶点TF并形成如在图12中的第五例子1212中所示的16个新补片来再分(在块902中，因为0.25高于THRES)八个补片中的每个的下边。所有细分因数然后再次减小0.5(在块912中)，且在另一递归中，进行最后两次再分(如在图12中的最后一个例子1214中所示的)，其中只有左上顶点细分因数(0.5)高于阈值。在这个步骤之后，所有顶点细分因数都是至多0(且如图12所示，顶点TF可以是负的)且该过程终止。

因为上面所述的改进的细分方法独立地处理每个补片，它可以以高并行程度实现。与任何细分方法一样，沿着域边界被共用的顶点可被缓存，使得它们不被复制。因为该方法是递归的，芯片(例如硅)空间和所需的存储器的数量是最小的。下面概述示例要求：

所提出的方法所需的额外顶点成员是每个输入顶点的固定点细分因数。M是输出顶点缓冲器的当前大小，且α()是M的某个函数，取决于缓冲器如何被构造。α()一般是在log(M)和M之间的某个数。

如上所述，当渲染等边三角形或具有高的面积与周长比的平方根那些三角形时，实现要渲染的最小数量的循环。类似地，当面积与周长比的平方根消失、例如使三角形恶化时，最坏性能出现。对于具有边长度a、b和c的给定三角形补片，所提出的方法产生至多四个不同类别的三角形(一直到相似)A(具有以比a:b:c的边)、B(具有以比a:d:c/2的边)、C(具有以比d:b:c/2的边)和D(具有以比a/2:b/2:d的边)，如图13所示。在补片是等值线(即a＝b)的情况下，则B类似于C，且因此只有三个类别。如果补片都是等值线且在上顶点处成直角，则有完全相似性(即只有单个类别的三角形)。在所有情况下，三角形类别的数量是有限的；因此最小的面积与周长比的平方根是有界限的且不能消失，除非补片本身恶化。相反，很多已知的细分方法没有关于面积与周长比的平方根的下限，且实际上消失的三角形大量地出现。

图14示出在使用本文所述的改进的细分方法和已知的细分方法——奇数分数分割(如上面参考图1所述的)得到的结果之间的比较。示出八个单独的比较1401-1408，且每次比较，使用改进的细分方法得到的结果显示在左边，而使用奇数分数分割得到的结果就显示在右边。

如在第一比较1401中所示的，改进的细分方法以比奇数分数分割多两个的基元开始以确保细分独立于方位。如上所述，这四个三角形基元在预处理阶段(块504)中产生。使用在改进的细分方法中的算法的细分(在块506中)通过将两个补片分成类似的三角形而开始，如在第二比较1402中所示的。相反，在奇数分数分割(显示在右边)中，细分以添加12个新的细三角形并接着添加多得多的三角形来开始，所有新的细三角形都几乎是冗余的(因为它们那么细，使得几乎整个域由仅仅两个基元组成，如在第二比较1402中清楚可见的，这意味着这些细三角形在移位之后不将任何细节添加到域的大部分)，如在比较1403中所示的。

如在随后的比较1403-1408中所示的，改进的细分方法继续添加一半面积的相似三角形以近似于在细分因数中的增加。奇数分数分割继续添加过多的最初冗余的细三角形以达到相同的效果。改进的细分方法引入顶点，这些顶点不在域空间中移动。相反，在奇数分数分割中，顶点在老顶点的顶部上开始并向外生长到适当位置内，且因此，几何结构看起来起伏。改进的细分方法稳定在如在最后的比较1408中所示的十字形图案内，而奇数分数分割继续将整行和整列的顶点添加在每个奇数LOD/TF处，这又在域空间中移动所有顶点。

允许用户规定补片的中心TF有时可能是合乎需要的，该中心TF在LOD上不同于补片的中心的角的顶点TF，特别是在动画中。例如，这可用于更好地近似与在四边形或三角形补片之上的纹理相关的高度图，例如，如果该图在动物的刺突的情况下具有在中间的非常快速的跳跃。图15示出添加另一可选的预处理阶段(块1502)的对图5(如上所述)的方法的变形，该预处理阶段实现四边形或三角形补片的中心TF的使用。如图15所示，这个额外的预处理阶段(在块1502中)在上面所述的预处理阶段(在块504中)之前实现，并分割输入补片(其可以是四边形或三角形)。与原始预处理阶段(块504)不同，额外的预处理阶段(块1502)也可应用于等值线；然而它在这个上下文中较不有用。在等值线的情况下，等值线被再分，且最新添加的中间顶点被分配中心TF。再分然后如上所述在两个子等值线(例如LEFT-MID和MID-RIGHT)上继续进行。

可参考图16和17描述额外的预处理阶段(块1502)。图16示出对四边形输入补片1602或三角形输入补片1604的阶段的应用的示意图，以及图17示出额外的预处理阶段的流程图。在中心细分因数被启用的情况下，用户必须向细分器提供每补片中心TF以及每个角顶点的顶点TF(对于三角形补片是三个而对于四边形补片是四个)。

如图16所示，额外的预处理阶段将四边形输入补片1602分成四个四边形补片1606-1609并将三角形输入补片1604分成三个四边形补片1610-1612。为了实现此，预处理四边形输入补片1602需要添加五个新顶点(块1702)：具有中心TF的中心顶点1614(由所有四个子域1606-1609共用)、中上顶点1616、中右顶点1618、中下顶点1620和中左顶点1622。通过采用最新添加的顶点的相邻角TF的MEAN()对每个最新添加的顶点计算(在块1706中)它们的细分因数。在各种例子中，可使用由方程(6)给出的MEAN()函数，因为它导致更一致的细分模式；然而在其它例子中，可使用算术平均值。

预处理三角形输入补片1604需要添加四个新顶点(块1704)：具有中心TF的中心顶点1624(由所有三个子域共用)、中右顶点1626、中下顶点1628和中左顶点1630。通过采用最新添加的顶点的相邻角TF的MEAN()对每个最新添加的顶点给出(如在块1706中计算的)它们的细分因数。如上所述，在各种例子中，可使用由方程(6)给出的MEAN()函数，因为它导致更一致的细分模式；然而在其它例子中，可使用算术平均值。

额外的预处理阶段的最后一个阶段(块1708)减小每个细分因数，且在各种例子中，每个TF减小了2*INTERVAL。TF的这个减小(在输入到块504的原始预处理阶段之前)确保在补片的每条边界边上做出正确数量的再分并指示该细分已出现。

在将原始输入补片再分成三个或四个四边形补片后，在额外的预处理阶段(块1502)中，这三个或四个四边形补片(具有如在块1708中计算的其顶点TF)被输入到原始预处理阶段(块504)，好像它们是原始输入补片一样，且该方法如上所述继续进行。图18示出可使用图15的方法得到的各种示例细分。

由于额外的预处理阶段(块1502和图17)将每个域边再分至少一次的事实，即使使用0.0的TF，任何单个所连接的网也应在有或没有中心TF的情况下完全被细分，以确保没有破裂出现(即，在单个所连接的网络中的所有补片都应使用同一方法，即它们都应使用图5的方法或图15的方法，且没有使用图5的方法的一些输入补片和使用图15的方法的其它输入补片)。

本文所述的改进的细分方法处理在已知的细分方法中产生的上面所述的一个或多个问题。在各种例子中，改进的细分方法可处理上面详述的很多或所有问题，如下：

·无突然的举动——使用改进的细分方法，当细分因数增加时几何结构增加了小增量以产生平滑的过渡。这帮助渲染时间的预测。

·无破裂——如上面展示的，改进的细分方法不产生在域内或沿着域的边界的T结。

·无漂浮——当细分因数增加时，由细分器引入的每个顶点维持其域空间位置且因此没有“漂浮”伪像。

·无过/欠细分——在边的每端处的整数顶点细分因数t相应于2^t个再分。此外，在四边形上的t的平均顶点细分因数大致相应于2^2t个顶点和多达两倍的基元(其为最小的)。类似地，三角形补片相应于

个顶点和多达两倍的基元。

·无细三角形——如上所述，改进的细分方法每补片只产生四个(或更少)类别的三角形，且这限制每补片面积与周长比的平方根的最小值。

·空间/时间复杂度——算法是递归的(如图9所示)，且支持相当大的并行性的每个子域/补片可独立地进行处理。输入顶点需要顶点细分因数的额外固定点值。

此外，本文所述的改进的细分方法在各种例子中具有下面的另外的特质：

·方位无关——通过将补片分成三角形补片的扇，中间顶点作为每个的顶(在预处理阶段中，块504)，对三角形的方位不做出选择，所以将总是产生相同的细分。

·N边形——改进的细分方法可容易适合于通过将补片分成三角形的扇来支持具有N个边的任何多边形补片(在预处理阶段504的变形中)。在每种情况下，对于平均细分因数t，该方法将产生大约

个顶点和多达两倍的基元。

虽然上面的例子(例如在图5中)示出改进的细分方法是针对三角形、四边形和等值线补片来实现的，将认识到，该方法可对那些补片的仅仅子集(例如只对四边形补片、只对三角形补片或只对四边形和三角形补片)实现的。

虽然图5示出包括预处理阶段(块504)和细分算法的递归应用(在块506和508中)的改进的细分方法，将认识到，图9所示的方法可以可选地独立地实现而没有预处理阶段(块504且如图7和图8所示的)，或可选地，预处理阶段(块504)可以用与在图7和图8中所示的不同的方式实现。类似地，在使用中心细分因数(如图15所示)的情况下，该方法可以被实现而没有预处理阶段(块504且如图7和图8所示的)，或可选地，预处理阶段(块504)可以用与在图7和图8中所示的不同的方式实现。

在上面所述的改进的细分方法的另外的变形中，顶点细分因数可以不同地被表示，即通过由一个或多个缩放、转换或其它变换来变换它们。产生更新的顶点细分因数(例如在块708、808和912中)因此不同于减去INTERVAL，例如顶点TF可通过将二增加到它们的幂并通过除以根号2来表示。更一般地，对于任何F(x)——在实数上的可逆函数，细分因数TF’可由TF’＝F(TF)给出。不是减去INTERVAL，下面的函数可用于更新顶点TF(如在块708、808和912中计算的)：

TF’:＝F(F^-1(TF’)-INTERVAL)

在这个例子中，测试条件(而不是由上面的方程(3)给出的条件)将是TF’>F(THRES)或TF’<F(THRES)，其中不等式的选择取决于F是保序的还是反序的。通过由F()共轭，在该方法中没有语义差异。

在例子中，如果TF’＝F(TF)＝2^TF(即在以2为底的对数中不再起作用)，则用于更新顶点TF(例如在块708、808和912中)的函数将是：

测试条件于是为TF’>2⁰＝1，因为2^TF是保序的。

虽然在上面的描述中提供了THRES和INTERVAL的值的特定例子，在另外的例子中，可使用这些参数中的一个或两个的不同值。

在上面的例子中，描述了两个可能的函数MEAN()：算术平均和由上面的方程(6)给出的MEAN()函数。在本文所述的改进的细分方法的另外的示例实现中，另一函数可以可选地用作可以是对称或非对称的MEAN()函数(虽然这将导致方位独立性的失去)。

虽然上面的例子使用THRES和INTERVAL中的每个的单个值以及单个MEAN()函数(例如算术平均和由方程(6)给出的MEAN()函数)，另外的例子可使用THRES和/或MEAN的多个值和/或多个MEAN()函数。

在上面所述的改进的细分方法中，如果LEFT.TF或RIGHT.TF超过THRES，则添加新顶点(以及在“或”被使用的场合，例如在方程(3)中，在其标准含义中，如果LEFT.TF和RIGHT.TF中的一个或两个超过阈值则添加新顶点)。在对上面所述的例子的变形中，细分可以只在LEFT.TF和RIGHT.TF都超过THRES时被执行。

虽然在上面所述的改进的细分方法中，如果LEFT.TF或RIGHT.TF超过THRES则添加新顶点(如在方程(3)中的)，将要认识到的是，在对所述的方法的变形中，如果LEFT.TF或RIGHT.TF超过或等于THRES，则可添加新顶点。

在上面的描述中，再分被描述为递归地被应用(例如在块506和508中)。然而在另外的例子中，该方法可以不递归地被应用，例如它可迭代地被应用(在所有产生的补片上执行下一级别的再分之前，在所有当前补片上执行单个级别的再分)。在另一例子中，可实现另一非递归方法，例如测试在65乘65网格上的每个顶点是否应被包括并接着基于顶点的位置来判断任何被包括的顶点是哪些基元的部分。

在上面所述的例子中，改进的细分方法被描述为在域空间中执行。在对所述方法的另一变形中，可以可选地在域空间之外应用细分。

被输入到改进的细分方法的顶点TF可由单独的应用产生(例如基于观看者离每个顶点的距离，例如顶点的顶点TF可与顶点离眼睛的距离的倒数成比例)。在各种例子中，可提供API，其在将边TF输入到本文所述的方法内之前将边TF转换成顶点TF(例如通过平均在顶点处相接的边的所有边TF)。

本文所述的改进的细分方法可用于在运行中执行细分(例如，当视点在3D场景中改变时)，或可选地，方法可离线地用于对多个不同的视点预先计算三角形。

可在硬件中实现本文所述的改进的细分方法。在各种例子中，可在如图19所示的图形处理单元(GPU)内的硬件细分单元中实现该方法。图19示出可在GPU内的硬件中实现的示例GPU管线1900的示意图。如图19所示，管线1900包括顶点着色器1902，其负责执行每个顶点计算，包括(例如根据顶点离摄像机的位置)计算所有这些的顶点细分因数。在计算顶点TF之前，顶点着色器将顶点变换到自然空间内并可应用一个或多个其它线性变换。顶点着色器1902不知道网拓扑且只知道被馈送到其的当前顶点。

在顶点着色器1902和硬件细分单元(或细分器)1904之间(或在顶点着色器和图19中未示出的可选外壳着色器(optional hull shader)之间，其中管线1900包括在顶点着色器1902和细分器1904之间的一个或多个可选外壳着色器)，补片(即顶点的有序集合)是使用拓扑(其中这可以是存储在用户在引出调用之前选择的细分器中的预先构建的选择)来构建的。这个补片信息被传递到外壳着色器(在被提供的场合)。然而，细分器1904只采用顶点TF，且其余的补片信息被继续传递到域着色器1906。

硬件细分单元(或细分器)1904包括使用所接收的顶点TF来实现上面所述的改进的细分方法(例如，如在图5、7-9、15和17中所示的)的硬件逻辑。与顶点着色器不同，硬件细分单元(和任何可选外壳着色器)每补片而不是每顶点操作。为了简化实现用于计算新顶点TF(例如在块706、806、906和1706中)的方程所需的硬件，计算可在log2中被执行(如在上面所述的例子中)且所以可被实现为加法和减法(或者乘法和除法将被使用)。如上所述，硬件细分单元1904可配置成并行地执行上面描述的方法的方面(例如在块506和608中在不同的补片上的递归，例如，如图9所示)。硬件细分单元1904输出每个新顶点的域空间坐标并将它传递到域着色器1906(例如通过在缓冲器中存储每个补片的细节，如在图9的块914中的)。

域着色器1906充当由细分器1904产生的顶点的第二顶点着色器，并且每顶点(其由细分器产生)被执行一次。域着色器提供域空间位置(u,v)并给出所有补片信息并输出全顶点结构。域着色器使用补片控制点和域空间坐标来构建新顶点并应用任何位移映射(例如通过对在纹理中编码的一些隆起部分或高度图采样)。

在域着色器1906对每个补片的每个所产生的顶点运行之后，顶点被传递到光栅器(未在图19中示出)。一前一后地，基元(以索引缓冲器的形式)从细分器传递到光栅器。

图19的GPU管线1900仅作为例子被示出，且本文所述的使用顶点TF的改进的细分方法可用在任何GPU体系结构中。也将认识到，硬件细分单元1904可用在GPU管线中，除了或代替顶点着色器1902、可选外壳着色器和域着色器1906之外，GPU还包括其它着色器。

上面所述的改进的细分方法可以可选地在软件(或软件和硬件的组合)中实现。图20示出可被实现为计算和/或电子设备的任何形式且可配置成实现上面所述的细分方法的示例性基于计算的设备2000的各种部件。

基于计算的设备2000包括一个或多个处理器2002，其可以是微处理器、控制器或用于处理计算机可执行指令以控制设备的操作以便执行上面描述的改进的细分方法的任何其它适当类型的处理器。在例如片上系统体系结构被使用的一些例子中，处理器2002可包括在硬件(而不是软件或固件)中实现改进的细分方法的一部分的一个或多个固定功能块(也被称为加速器)。可在基于计算的设备处提供包括操作系统2004的平台软件或任何其它适当的平台软件以使应用软件2006能够在设备上执行，且应用软件可包括细分模块2008。这个细分模块2008可例如包括预处理模块(其实现图5或图15的块504)、可选地额外的预处理模块(其实现图15的块1502)和递归细分模块(其实现图5或图15的块506和/或508)。

可使用由基于计算的设备2000访问的任何计算机可读介质提供计算机可执行指令。计算机可读介质可包括例如计算机存储介质，例如存储器2010和通信介质。计算机存储介质(即非临时机器可读介质)，例如存储器2010，包括在任何方法或技术中实现的用于存储信息(例如计算机可读指令、数据结构、程序模块或其它数据)的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于RAM、ROM、EPROM、EEPROM、闪存或其它存储技术、CD-ROM、数字多用途光盘(DVD)或其它光学存储器、盒式磁带、磁带、磁盘存储器或其它磁性存储设备或可用于存储由计算设备访问的信息的任何其它非传输介质。相反，通信介质可体现计算机可读指令、数据结构、程序模块或在已调制数据信号，例如载波或其它传输机构中的其它数据。如在本文定义的，计算机存储介质不包括通信介质。虽然计算机存储介质(即非临时机器可读介质，例如存储器2010)被显示在基于计算的设备2000内，应理解的是，存储器可远程地被分布或定位并经由网络或其它通信链路(例如使用通信接口2012)被访问。

基于计算的设备2000还可包括布置成向可与基于计算的设备2000分离或合并成一整体的显示设备显示信息的输入/输出控制器。显示信息可提供图形用户界面。输入/输出控制器也可布置成接收并处理来自一个或多个设备例如用户输入设备(例如鼠标或键盘)的输入。在实施方式中，显示设备也可充当用户输入设备，如果它是触敏显示设备。输入/输出控制器也可向除了显示设备以外的设备例如本地连接的打印设备输出数据。

术语“处理器”和“计算机”在本文用于指具有处理能力使得它可执行指令的任何设备或其部分。术语“处理器”可例如包括中央处理单元(CPU)、图形处理单元(GPU或VPU)、物理处理单元(PPU)、无线电处理单元(RPU)、数字信号处理器(DSP)、通用处理器(例如通用GPU)、微处理器、设计成加速在CPU外部的任务的任何处理单元等。本领域中的技术人员将认识到，这样的处理能力合并到很多不同的设备内，且因此术语“计算机”包括机顶盒、媒体播放器、数字无线电装置、PC、服务器、移动电话、个人数字助理和很多其它设备。

本领域中的技术人员将认识到，用于存储程序指令的存储设备可分布在网络当中。例如，远程计算机可存储被描述为软件的过程的例子。本地或终端计算机可访问远程计算机并下载软件的一部分或全部以运行程序。可选地，本地计算机可按需要下载软件的片段或执行在本地终端处的一些软件指令和在远程计算机(或计算机网络)处的一些指令。本领域中的技术人员也将认识到，通过利用本领域中的技术人员已知的常规技术，软件指令的全部或一部分可由专用电路(例如DSP、可编程逻辑阵列等)实现。

本文所述的方法可由配置有软件的计算机执行，软件是以存储在有形存储介质上的机器可读形式、例如以包括用于配置计算机来执行所述方法的组成部分的计算机可读程序代码的计算机程序的形式或以包括适合于当程序在计算机上运行时执行本文所述的任何方法的所有步骤的计算机程序代码模块的计算机程序的形式，且其中计算机程序可体现在计算机可读存储介质上。有形(或非临时)存储介质的例子包括磁盘、拇指驱动器、存储卡等，且并不包括传播信号。软件可适合于在并行处理器或串行处理器上执行，使得方法步骤可以按任何适当的顺序或同时被执行。

本文描述的硬件部件可由非临时计算机可读存储介质产生，非临时计算机可读存储介质具有在其上编码的计算机可读程序代码。

意图还包括“描述”或定义实现上面所述的模块、功能、部件或逻辑的硬件的配置的软件，例如HDL(硬件描述语言)软件，如对设计集成电路或对配置可编程芯片使用的，以实现期望功能。也就是说，可提供计算机可读存储介质，其具有存储在其上的用于产生配置成执行本文所述的任何方法的处理单元或用于产生包括本文所述的任何装置的处理单元的计算机可读程序代码。也就是说，计算机系统可配置成从电路元件的定义和用于定义组合那些电路元件的规则的数据产生数字电路的表示，其中非临时计算机可读存储介质可具有存储在其上的处理器可执行指令，其当在这样的计算机系统处被执行时使计算机系统产生如本文所述的处理单元。例如，非临时计算机可读存储介质可具有存储在其上的计算机可读指令，其当在用于产生集成电路的表现形式的计算机系统处被执行时使计算机系统产生如在本文的例子中所述的接收机的处理器的表现形式或产生配置成执行如在本文的例子中所述的方法的处理器的表现形式。处理器的表现形式可以是处理器本身或可用于产生处理器的处理器的表示(例如掩模)。

存储在实现所公开的方面时使用的机器可执行数据的存储器可以是非临时介质。非临时介质可以是易失性的或非易失性的。易失性非临时介质的例子包括基于半导体的存储器，例如SRAM或DRAM。可用于实现非易失性存储器的技术的例子包括光学和磁性存储器技术、闪存、相变存储器、持久性RAM。

对“逻辑(logic)”的特定参考指执行一种或多种功能的结构。逻辑的例子包括布置成执行那些功能的电路。例如，这样的电路可包括晶体管和/或在制造过程中可用的其它硬件元件。作为例子，这样的晶体管和/或其它元件可用于形成实现和/或包含存储器例如寄存器、触发器或锁存器、逻辑运算器例如布尔运算、数学运算器例如加法器、乘法器或移位器和互连的电路或结构。这样的元件可作为定制电路或标准单元库、宏或以其它抽象级被提供。可在特定的布置中使这样的元件互连。逻辑可包括固定功能的电路，且电路可被编程以执行一种或多种功能；这样的编程可从固件或软件更新或控制机制提供。被识别为执行一种功能的逻辑也可包括实现组成功能或子过程的逻辑。在例子中，硬件逻辑具有实现固定功能操作或多个操作、状态机或过程的电路。

如对技术人员将明显的是，本文给出的任何范围或设备值可扩展或改变而不失去所寻求的效应。

将理解的是，上面描述的益处和优点可涉及一个实施方式或可涉及几个实施方式。实施方式不限于解决任何或所有所陈述的问题的那些实施方式或具有任何或全部所陈述的益处和优点的那些实施方式。

对“一(an)”项目的任何参考指的是那些项目中的一个或多个。术语“包括”在本文用于意指包括所识别的方法块或元件，但这样的块或元件并不包括排他列表，且装置可包含额外的块或元件，以及方法可包含额外的操作或元件。此外，块、元件和操作本身并非不隐含地封闭的。

本文描述的方法的步骤可在适当的场合以任何适当的顺序或同时被执行。在附图中的方框之间的箭头示出方法步骤的一个示例顺序，但并不意欲排除其它顺序或平行的多个步骤的执行。此外，单独的块可从任何方法删除而不偏离本文描述的主题的精神和范围。上面描述的任何例子的方面可与所描述的其它例子中的任一个的方面组合以形成另外的例子，而不失去所寻求的效应。在附图的元件被示为由箭头连接的场合，要理解的是，这些箭头示出在元件之间的通信(包括数据和控制消息)的仅仅一个示例流。在元件之间的流可以是在任一方向上或在两个方向上的。

要理解的是，优选实施方式的上述描述仅作为例子被给出，以及各种修改可由本领域中的技术人员做出。虽然上面以某个详细程度或参考一个或多个单独的实施方式描述了各种实施方式，本领域中的技术人员可对所公开的实施方式进行很多变更而不偏离本发明的精神或范围。

Claims (17)

1.一种硬件细分单元，所述硬件细分单元包括硬件逻辑，所述硬件逻辑配置成：对于包括由边连接并在域空间中定义的左顶点和右顶点的初始补片：

将所述左顶点的顶点细分因数和所述右顶点的顶点细分因数与阈值进行比较(902)；

响应于确定所述左顶点和所述右顶点的顶点细分因数中没有一个超过或等于所述阈值，输出描述所述初始补片的数据(914)；以及

响应于确定所述左顶点和所述右顶点的顶点细分因数中有任一个超过或等于所述阈值，形成将所述边再分成两个部分的新顶点(904)，计算所述新顶点的顶点细分因数(906)，分割所述初始补片以形成包括所述左顶点和所述新顶点的第一新补片(908)以及包括所述右顶点和所述新顶点的第二新补片(910)，并减小在每个最新形成的补片中的每个顶点的顶点细分因数(912)。

2.如权利要求1所述的硬件细分单元，其中所述新顶点平分所述边。

3.如权利要求1所述的硬件细分单元，其中所述硬件逻辑还配置成使用每个最新形成的补片作为所述初始补片重复所述硬件逻辑的操作(902-914)。

4.如权利要求3所述的硬件细分单元，其中所述硬件逻辑配置成对作为所述初始补片的每个最新形成的补片重复所述硬件逻辑的操作，直到在每个补片中的所述左顶点和所述右顶点的顶点细分因数不超过所述阈值为止。

5.如权利要求1所述的硬件细分单元，其中配置成计算所述新顶点的顶点细分因数的所述硬件逻辑包括配置成执行下列操作的硬件逻辑：

计算所述左顶点和所述右顶点的顶点细分因数的平均值；以及

设置所述新顶点的顶点细分因数等于所计算的平均值。

6.如权利要求5所述的硬件细分单元，其中所述左顶点和所述右顶点的顶点细分因数的平均值由下式给出：

MEAN(LEFT.TF,RIGHT.TF)＝MIN(AVG(LEFT.TF,RIGHT.TF),MIN(LEFT.TF,RIGHT.TF)+INTERVAL)其中LEFT.TF是所述左顶点的顶点细分因数，RIGHT.TF是所述右顶点的顶点细分因数，AVG()是在括弧内的值的算术平均值，MIN()是在括弧内的值的列表中的最小值，以及INTERVAL是预先定义的参数。

7.如权利要求1所述的硬件细分单元，其中配置成减小在每个最新形成的补片中的每个顶点的顶点细分因数的所述硬件逻辑包括将每个顶点细分因数减小预先定义的参数INTERVAL。

8.如权利要求1所述的硬件细分单元，其中所述初始补片是由所述左顶点和所述右顶点这两个顶点定义的等值线补片。

9.如权利要求1所述的硬件细分单元，其中所述初始补片是三角形补片，且其中所述三角形补片是三个顶点的有序集合：上顶点、所述右顶点和所述左顶点。

10.如权利要求9所述的硬件细分单元，其中被分割的补片是两个最新形成的补片的父补片，以及其中所述第一新补片是三个顶点的有序集合：为被添加到所述父补片的新顶点的上顶点、为所述父补片的左顶点的右顶点以及为所述父补片的上顶点的左顶点；以及其中所述第二新补片是三个顶点的有序集合：为被添加到所述父补片的新顶点的上顶点、为所述父补片的上顶点的右顶点以及为所述父补片的右顶点的左顶点。

11.如权利要求9所述的硬件细分单元，还包括配置成执行下列操作的硬件逻辑：

接收输入补片(502)；

从所述输入补片产生一个或多个初始补片(504)；以及

对于多个初始补片中的每个重复所述硬件逻辑的操作。

12.如权利要求11所述的硬件细分单元，其中所述输入补片是具有三个顶点的三角形补片，且其中配置成产生一个或多个初始补片的所述硬件逻辑包括配置成执行下列操作的硬件逻辑：

将所述三个顶点中的每个顶点的顶点细分因数与阈值进行比较(702)；

响应于确定所述顶点细分因数中没有一个超过所述阈值，输出描述所述输入补片的数据(712)；以及

响应于确定至少一个所述顶点细分因数超过所述阈值，形成在所述三角形补片的中心处的新顶点(704)，计算所述新顶点的顶点细分因数(706)，分割所述输入补片以形成三个初始补片，每个初始补片是以所述新顶点作为上顶点的三角形补片(710)，以及减小在每个最新形成的初始补片中的每个顶点的顶点细分因数(708)。

13.如权利要求11所述的硬件细分单元，其中所述输入补片是具有四个顶点的四边形补片，以及其中配置成产生一个或多个初始补片的所述硬件逻辑包括执行下列操作的硬件逻辑：

形成在所述四边形补片的中心处的新顶点(804)；

计算所述新顶点的顶点细分因数(806)；

分割所述输入补片以形成四个初始补片，每个初始补片是以所述新顶点作为上顶点的三角形补片(810)；以及

减小在每个最新形成的初始补片中的每个顶点的顶点细分因数(808)。

14.如权利要求11所述的硬件细分单元，其中所述输入补片是具有四个顶点和中心细分因数的四边形补片，以及其中配置成产生一个或多个初始补片的所述硬件逻辑包括配置成执行下列操作的硬件逻辑：

添加五个新顶点以将所述输入补片再分成四个子输入四边形补片(1702)；

计算五个最新添加的顶点中的每个顶点的顶点细分因数(1706)；

减小在最新形成的四个子输入四边形补片中的每个顶点的顶点细分因数(1708)；以及

对于每个子输入四边形补片：

形成在所述每个子输入四边形补片的中心处的新顶点(804)；

计算所述新顶点的顶点细分因数(806)；

分割所述每个子输入四边形补片以形成四个初始补片，每个初始补片是以所述新顶点作为上顶点的三角形补片(810)；以及

减小在每个最新形成的初始补片中的每个顶点的顶点细分因数(808)。

15.如权利要求11所述的硬件细分单元，其中所述输入补片是具有三个顶点和中心细分因数的三角形补片，以及其中配置成产生一个或多个初始补片的所述硬件逻辑包括配置成执行下列操作的硬件逻辑：

添加四个新顶点以将所述输入补片再分成三个子输入四边形补片(1704)；

计算四个最新添加的顶点中的每个顶点的顶点细分因数(1706)；

减小在最新形成的三个子输入四边形补片中的每个顶点的顶点细分因数(1708)；以及

对于每个子输入四边形补片：

形成在所述每个子输入四边形补片的中心处的新顶点(804)；

计算所述新顶点的顶点细分因数(806)；

分割所述每个子输入四边形补片以形成四个初始补片，每个初始补片是以所述新顶点作为上顶点的三角形补片(810)；以及

减小在每个最新形成的初始补片中的每个顶点的顶点细分因数(808)。

16.一种图形处理单元，所述图形处理单元包括根据权利要求1-15中的任一项所述的硬件细分单元。

17.一种在计算机图形系统中执行细分的方法，所述方法包括：

对于包括由边连接的并在域空间中定义的左顶点和右顶点的初始补片：

将所述左顶点的顶点细分因数和所述右顶点的顶点细分因数与阈值进行比较(902)；

响应于确定所述左顶点和所述右顶点的顶点细分因数中没有一个超过或等于所述阈值，输出描述所述初始补片的数据(914)；以及

响应于确定所述左顶点和所述右顶点的顶点细分因数中有任一个超过或等于所述阈值，形成将所述边再分成两个部分的新顶点(904)，计算所述新顶点的顶点细分因数(906)，分割所述初始补片以形成包括所述左顶点和所述新顶点的第一新补片(908)以及包括所述右顶点和所述新顶点的第二新补片(910)，并减小在每个最新形成的补片中的每个顶点的顶点细分因数(912)。

Images