CN103824276A - 用于处理图形的方法和设备 - Google Patents

Abstract

本发明涉及用于处理图形的方法和设备。一种用于基于区块的图形渲染系统的基元列举和分类布置，其中可以针对渲染目标区的至少两个不同组的子区域准备基元列表。确定使用可以准备基元列表的渲染目标区的所述至少两个不同组的子区域其中至少两个组的子区域来列举基元以便于渲染的两个或更多备选解决方案（S62）。成本函数然后用于针对每个确定的备选基元列举解决方案评价用于列举基元的成本（S63）且然后基于成本评价来选择将使用的基元列举布置。优选实施方式使用自适应成本函数，该自适应成本函数在使用中可以基于在使用中实际体验的基元列举处理的成本的分析而被修改。

Description

用于处理图形的方法和设备

技术领域

本发明涉及用于处理图形的方法和设备，且尤其涉及在基于区块的图形处理系统中使用的方法和设备。

背景技术

如现有技术所已知，图形处理通常通过首先将被显示场景分割成很多小的基本成分或“基元（primitive）”实施，该基元然后经历所需的图形处理操作。图形“基元”通常是诸如三角形的简单多边形形式，且通常通过定义其顶点来描述。

很多图形处理系统使用所谓的“基于区块”的渲染。在基于区块的渲染中，二维渲染输出或目标（即渲染处理的输出，诸如将被显示的输出帧）被渲染为通常被称为“区块”的很多较小面积子区域。区块均被单独渲染（典型地一个接着一个）。渲染的区块然后重新组合以提供完整的渲染输出（例如用于显示的帧）。在这种配置中，渲染目标（输出）典型地（通过面积）分割成规则大小和形状的渲染区块（它们通常例如是方形或矩形），但是这并不关键。

通常用于“区块化”或“基于区块”的渲染的其他术语包括“组块”（渲染区块被称为“组块”）或“块式”渲染。为方便起见，此处使用术语“区块”和“区块化”，但是应当理解，这些术语旨在涵盖所有备选和等价术语和技术。

这些基于区块的渲染的优点在于，不必针对给定区块处理在该区块中不出现的基元，且因此在处理区块时可以被忽略。这允许针对给定渲染输出必须的整体图形处理量减小。

在基于区块的渲染系统中，相应地通常希望能够识别且知道在给定渲染区块中实际存在的这些基元，从而例如避免在区块中实际不存在的不必要渲染基元。为了促进这点，已知针对每个渲染区块准备针对该渲染区块被渲染的基元（例如将在区块中出现的基元）的列表。这种“基元列表”（也可以称为“区块列表”）（例如通过参考基元指示器）识别针对讨论区块渲染的基元。

针对被渲染的每个区块准备基元列表的处理基本涉及确定针对给定渲染区块应当渲染的基元。该处理通常通过（在所需精确度水平）确定贯穿讨论区块（即，在讨论区块中（至少部分地）出现）的基元且然后准备这些基元的列表以用于被图形处理系统未来使用而实施。（此处应当注意，当基元落到多于一个区块时（这将是很常见的情况），该基元被包括在用于该基元所处的每个区块的区块列表中）。实际上，每个区块可以被认为具有箱（基元列表），被发现落在区块内（即贯穿）的任意基元被放置在所述箱中（并且实际上，以这种方式基于逐个区块分类基元的处理常被称为“装箱”）。

如本领域所已知，例如取决于针对区块化和渲染处理的不同部分的效率优化，可以按照变化的精度水平实施确定针对任何给定渲染应当列举（渲染）的基元的处理。例如，按照最精确水平，可以精确地确定给定基元将至少部分出现在哪些区块中，以及该基元然后被包括在仅用于这些区块的基元列表中。这通常被称为“精确”装箱。

图1说明精确装箱处理。如图1所示，为了渲染目的，以将被显示的帧1的形式的渲染目标被分割成16个规则大小的区块2。然后针对帧中的每个基元确定该基元实际出现（落在）哪个或哪些区块内。基元被添加到用于它所处的每个区块的基元列表。因而，采用图1示出的示例，基元3被添加到用于区块4的基元列表中，基元5被包括在用于区块6和7的基元列表中，基元8被包括在用于区块9、10、11和12的基元列表中，且基元13被包括在用于区块12的基元列表中。（此处应当注意，为了清楚目的，图1仅示出少数区块和基元。本领域技术人员应当意识到，在实际图形处理操作中，将典型地可以存在大量更多的基元和区块。）

还知道使用比精确装箱实现的精度更低的精度准备基元列表。这例如对于简化基元列表的准备是有用的。一个普遍的“较不精确”装箱技术是“边界框”装箱。在这种情况中，沿着基元或一组基元绘制所谓的“边界框”，且然后确定边界框覆盖的区块。然后针对边界框（至少部分）覆盖的每个区块列举（装箱）边界框代表（即被边界框包含）的基元或多个基元。

一旦已经以这种方式针对每个渲染区块准备将被渲染的基元的列表（基元列表），基元列表被存储以用于例如允许系统在渲染讨论区块时识别哪些基元需要被考虑（且渲染）。

已经发现这种基于区块的渲染布置很好地工作，因为例如它们可以帮助避免仍针对基元不存在的渲染目标的区域处理所述基元。

然而，与需要准备和存储识别针对每个区块渲染的基元相关的一个缺点在于，根据针对例如给定的将被渲染帧的基元的分布，针对帧使用的不同区块的基元列表可以具有不同大小，因为可以是针对不同帧用于区块的基元列表。这意味着例如与其他区块或渲染输出相比，给定渲染输出或区块可以具有用于存储其（多个）基元列表的明显不同的存储器需求。

申请人在其英国专利No.2433014中提出了一种改进的基于区块的渲染系统，其准备用于单个渲染区块的基元列表以及用于包含多于一个区块的渲染目标区的基元列表（即，包含将被生成的输出的多于一个的渲染区块（且由此实际上更大区域）的基元列表）。换句话说，也准备除了单个渲染区块之外的基元的列表，能够且将会共同用于多个渲染区块的基元列表可以被准备。

如申请人早先的专利中所讨论，准备不同渲染目标“区域”基元列表具有很多优点，诸如允许用于基元列表的存储器数量变化，且促进更好的控制以及针对基元列举处理的存储器使用需求的知识。

在申请人早先的专利中，基元基本分类成用于渲染目标的不同大小区域的基元列表，从而限制将列举给定基元的不同基元列表的数目。这帮助控制基元列表所需的存储器的数量。

然而，申请人现在意识到，至少在某些情形中，对于其早先专利中描述的方案的一些添加和变型可能是有利的。

发明内容

根据本发明的第一方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的方法，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标区的至少两个不同组的子区域准备指示将被处理的基元的系统基元列表，所述渲染目标区的所述两个不同组的子区域其中至少一个组包含比单个渲染区块大的所述渲染目标区的子区域，该方法包括以下步骤：

针对将被渲染的基元：

确定所述基元需要被列举以渲染所述基元的所述渲染目标区的所述至少两个不同组的子区域其中至少两个组的子区域；

使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区子区域的基元列表中列举所述基元的成本；以及

基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区子区域其中一些子区域以列举所述基元，且在这些所选子区域的基元列表中包括所述基元。

根据本发明的第二方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的设备，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标区的至少两个不同组的子区域准备指示将被处理的基元的系统基元列表，所述渲染目标区的所述两个不同组的子区域其中至少一个组包含比单个渲染区块大的所述渲染目标区的子区域，所述设备包括：

装置，其针对将被渲染的基元，确定所述基元需要被列举以渲染所述基元的所述渲染目标区的所述至少两个不同组的子区域其中至少两个组的子区域；

装置，其使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区子区域的基元列表中列举所述基元的成本；以及

装置，其基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区子区域其中一些子区域以列举所述基元，且在这些所选子区域的基元列表中包括所述基元。

根据本发明的第三方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的方法，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标的大小不同的区域准备指示将被处理的基元的系统基元列表，该方法包括以下步骤：

针对将被渲染的基元：

确定所述基元需要被列举以渲染所述基元的所述渲染目标的大小不同的区域其中的区域；

使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区域的基元列表中列举所述基元的成本；以及

基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区域其中一个区域以列举所述基元，且在这些所选区域的基元列表中包括所述基元。

根据本发明的第四方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的设备，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标的大小不同的区域准备指示将被处理的基元的系统基元列表，该设备包括：

装置，其针对将被渲染的基元确定所述基元需要被列举以渲染所述基元的所述渲染目标的大小不同的区域其中的区域；

装置，其使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区域的基元列表中列举所述基元的成本；以及

装置，其基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区域其中一个区域以列举所述基元，且在这些所选区域的基元列表中包括所述基元。

本发明涉及基于区块的图形处理系统，其使用用于渲染目标的多组子区域的基元列表（即，使用用于渲染目标（即，渲染处理的所计划的输出，诸如将被显示的帧）的不同大小区域的基元列表），就像在申请人较早的英国申请中一样。然而，在本发明中，基于在不同的可能基元列表中包括基元的成本的评价而选择在其中列举基元的基元列表。如下面进一步讨论，这可以具有很多优点。

申请人已经意识到，在支持多个不同渲染目标区基元列表的系统中，可以存在可能受列举给定基元的渲染目标区子区域的选择影响的很多因素。例如，尽管从存储器容量视角可以更有效地在较高水平（即，在包含渲染目标的较大区域（区）的基元列表中）存储给定基元，另一方面，因为基元仅可以被写入且存储在单个基元列表中，基元可能在使用中需要从列表读取更多次，因为它将需要针对基元列表相关的每个渲染区块被读取。在用于单个渲染区块的基元列表中包括基元将减小从基元列表读取基元的潜在不必要的数目，但是要求基元被写入且存储在更多的基元列表中。

图6说明这点且示出分割成用于渲染目的的4×4个渲染区块92且通过可以准备基元列表的三组不同大小的渲染目标区子区域（分别在图6a、6b和6c中示出）叠加的渲染目标91。如下面所讨论，可以准备基元列表的渲染目标子区域的这些组实际上布置为以层级方式提供叠加渲染目标91的逐渐更大的渲染目标子区域的三个层。

图6还示出被输出到渲染目标91且具有为其得出的边界框93的基元90。用于基元90的边界框93用于确定基元90应当列举在哪个渲染目标子区域中。

如图6a所示，在该示例中，可以准备基元列表的渲染目标子区域的第一层（组）包含每个均覆盖（且匹配）一个渲染区块（即尺寸为1×1个渲染区块）的子区域94。如果基元90在该层（该组的渲染目标子区域）中被列举，它将在用于9个渲染目标子区域的基元列表中被列举，因而在渲染该基元时需要9个基元命令写入和9个基元命令读取。

图6b示出渲染目标子区域的第二层（组），其中准备基元列表的每个渲染目标子区域95包含2×2个渲染区块。按照层级在该层中列举基元90将要求针对4个2×2渲染区块渲染目标子区域中的每一个列举基元，因而要求4个命令写入和16个命令读取（因为4个2×2渲染目标子区域总共覆盖16个渲染区块）。

图6c示出层级中的最高层，其中存在包含全部渲染目标区的单个渲染目标子区域96，即，存在包含渲染目标区的4×4个渲染区块的一个子区域。按照层级在该层中列举基元将要求1个命令写入和16个命令读取（因为4×4渲染目标子区域总共覆盖16个渲染区块）。

从这里可以看出，根据基元90以渲染目标子区域的哪个组（即层）来列举，渲染基元所需的写入和读取操作的数目将变化。因而，根据列举基元的渲染目标子区域，在用于列举（装箱）基元的成本方面将存在差异。本发明通过在确定如何列举基元以便于渲染时使用成本函数，考虑这点。申请人发现这可能导致例如用于基元列举（装箱）和渲染处理的存储器带宽和功耗方面的明显节省。

如上面所讨论，本发明可应用于基于区块的图形处理系统，其中，为了渲染目的，渲染目标（例如将被显示的帧）被分割成若干渲染区块（在逐个区块的基础上处理）。在本发明中，为了渲染目的渲染目标（输出）被分割成的区块可以是任意合适和希望的这种区块。如本领域所已知，渲染区块的大小和形状通常通过图形处理器被配置成使用且处理的区块配置来指示。

如本领域所已知，渲染区块优选地全都具有相同的大小和形状（即规则大小和形状的区块被优选地使用），不过这不是必须的。区块优选地是方形或矩形的。区块的大小和数目按需选择。在优选布置中，每个区块在大小方面是16×16或32×32个采样位置（然而渲染目标被分割成与被使用的渲染输出大小和形状所需一样多的区块）。

可以准备基元列表的渲染目标子区域的组可以按需布置且配置。渲染目标子区域组其中至少一个组应当包含如下的子区域，即，该子区域包含多于一个渲染区块（大于单个渲染区块）。

在一个优选实施方式中，子区域组其中一个组包含对应于各个渲染区块的子区域（大小为1（1×1）个渲染区块）（即，使得每个渲染区块将具有除了该渲染区块之外的针对该渲染区块准备的基元列表）。

在这种情况中，子区域组将包含：一组子区域，其中该组的每个子区域对应于相应的单个渲染区块；以及一个或更多（且优选地多于一个）组的子区域，其中该组的每个子区域对应于（包含）多于一个渲染区块。

子区域组其中一个组不必包含对应于各个渲染区块的子区域（即大小为1（1×1）个渲染区块）。因而，在另一优选实施方式中，渲染目标子区域的全部组包含如下的子区域，即，该子区域包含多于一个渲染区块（大于单个渲染区块）。在这种情况中，子区域组将包含两个或更多组的子区域，其中所述组的每个子区域对应于（包含）多于一个渲染区块。

子区域的每个不同组中的子区域应当包含渲染目标的不同区域，即，每个不同组的子区域应当与可以准备基元列表的其他组的渲染目标子区域中的子区域具有不同大小的子区域。

在优选实施方式中，渲染目标子区域且优选地每个渲染目标子区域包含一组连续的渲染区块（或部分区块）。更优选地，渲染目标子区域或每个渲染目标子区域形成渲染目标的规则形状区域。渲染目标子区域优选地是矩形（包括方形）。然而，同样这不是必须的，且如有需要，可以使用更多的不规则子区域形状，例如“L”形或三角形（多个）子区域。同样，这种不规则形状对于列举更不常见或不规则形状和/或大小的基元可能是有用的。

多于一个渲染区块的每个子区域可以且在一个优选实施方式中确实包含整数数目的渲染区块。对于非方形渲染目标，多于一个渲染区块的每个子区域优选地包含整数数目的渲染区块，但是优选地在x和y方向中存在不同数目的子区域（例如，宽屏图像可能被映射到最低水平的32×16个子区域，较高水平的16×8个子区域等。）

例如，还可以针对包含渲染区块的一部分（例如包含一个半区块或三又四分之三个区块等）的渲染目标子区域准备基元列表。包含分数个渲染区块的这种渲染目标子区域对于指定的例如不常见或不规则的基元形状和/或大小可能是希望的，因为它们可以允许这种基元被更有效地在基元列表中列举。它们还针对具有不常见和/或非方形形状的渲染目标是有用的，因为在这种情况中，优选的是将渲染目标分割成不是整数数目的渲染区块的子区域。

每一组的子区域优选地包含覆盖整个渲染目标的足够的子区域，即包含渲染目标被分割的所有相应渲染区块。因而，给定组的渲染目标子区域将包含多个子区域，当合适时，能够针对该组中的多个渲染目标子区域其中任一个子区域准备基元列表（即，将存在多个基元列表，每个基元列表对应于该组的渲染目标子区域的给定子区域）。

给定组的渲染目标子区域中的每个渲染目标子区域可以不同（例如在其大小和/或形状方面），但是在优选实施方式中，给定组的渲染目标子区域中的渲染目标子区域全都具有相同的大小，且优选地也具有彼此相同的形状（即，优选地覆盖相同数目的渲染区块）。

给定组的渲染目标子区域的每个子区域优选地包含与讨论的组的其他渲染目标子区域不同的组的渲染区块。类似地，渲染目标子区域的给定组中的每一个渲染目标子区域优选地覆盖渲染目标的不同部分（区域）。

在尤其优选的实施方式中，可以准备基元列表的渲染目标子区域组布置为使得渲染目标被多个层的子区域组有效地叠加（每个层是子区域的一个组）。每一层应当且优选地确实具有与其他层大小不同的可以准备基元列表的子区域。层（子区域的组）更优选地具有不断减小的分辨率水平（即，其子区域包含增加数目的渲染区块）。这些布置例如可以允许渲染目标被多个不同分辨率层的子区域有效地覆盖，每个这种“层”由一组多个子区域组成，其中每个子区域包含相同数目的渲染区块，且不同“层”中的子区域包含不同数目的渲染区块。

这种布置有效地允许针对渲染目标的不断减小的分辨率水平（即分割成子区域）准备基元列表。这允许准备基元列表的分辨率变化且可控。

在尤其优选的布置中，可以准备基元列表的渲染目标子区域组以层级方式布置，即，使得每个组中的子区域的数目随着子区域组变化而不断变化。子区域组最优选地布置为使得它们在发展组时有效地形成金字塔结构。

渲染目标区和/或被包括在子区域中的渲染区块的数目优选地随着从最低组（其可以且在一个优选实施方式中是基础的单个渲染区块子区域组）提升子区域组而不断增加。在一个优选实施方式中，子区域组布置为使得每个连续组中的子区域具有4倍于子区域的直接在先组的面积（和/或与它们中的渲染区块一样多），即，使得如果子区域的最低（基础）组是单个渲染区块子区域，则存在4（2×2）个渲染区块子区域的组、16（4×4）个渲染区块子区域的组等，优选地高达包含涵盖整个渲染目标的单个子区域组。最优选地，实际上存在三个或更多的这种层。

类似地，在优选实施方式中，子区域分层层级组优选地布置为使得实际上可以针对整个渲染目标、针对分割成4个子区域的渲染目标区、针对分割成16个子区域的渲染目标区、针对分割成64个子区域的渲染目标区等准备基元列表，直到其分割成各个渲染区块。

（通过在每个连续水平上以因子4改变子区域是用于在水平改变时增加大小的尤其方便的布置。然而，这不是必须的，且如有需要可以使用其他布置。）

基元可能需要被列举以渲染基元的渲染目标区的子区域的（可以准备基元列表的子区域组的）确定可以以任意合适和所需的方式实施。本质上，如本领域技术人员所意识到，该处理将需要识别基元（可能地）落在渲染目标的哪些子区域内。针对将基元分类和装箱到区块列表和渲染目标区的中使用的已知任意技术（诸如精确装箱、或边界框装箱、或其间的任何技术）可以用于该处理。优选地，使用边界框装箱。

优选地，例如优选地基于渲染目标中基元（优选地用于基元的边界框）的确定位置做出将被渲染的基元可能落在其内的渲染目标子区域的初始确定。

因而，在优选实施方式中，用于渲染目标中的基元的位置被确定且与渲染目标被分割的子区域相比较，以确定基元可能或应当在渲染目标子区域组的哪些子区域中被列举（例如在其中出现）。

最优选地，当确定单独在给定组的子区域中列举基元时，基元需要被列举以渲染基元的该给定组的子区域的各个子区域被确定（即，基元可能落在其中的给定组的子区域中的子区域被确定）。这优选地针对一个或更多其他组的子区域重复。因而，在尤其优选的实施方式中，基元可能地落在其中的子区域组中至少两个组的子区域被确定（例如基于用于基元的边界框）。

可以相对于系统支持（且可以准备基元列表）的每个组的渲染目标子区域测试基元（例如使用其边界框），且在任意事件中，相对于至少两个组的子区域（至少两个组的子区域中的子区域）应当测试基元。然而，在系统支持例如多于两个组的子区域的情况中，如有需要，基元仅相对于可能的子区域组中的一些组而非全部组进行测试。

一旦基元可能需要被列举的子区域被确定，然后，如上面所讨论，成本函数然后用于评价列举用于这些渲染目标子区域的基元的成本。

用于评价在确定的渲染目标子区域的基元列表中列举基元的成本的成本函数可以按需选择和配置。成本函数优选地配置成考虑且优选地试图优化存储器带宽和/或图形处理器和其中存储基元列表的存储器之间的性能（例如，优选地任意反应时间）。用于基元列举操作的存储器带宽可以例如通过试图增加（最大化）用于基元列举操作的缓冲命中率而优化。因而，成本函数优选地针对系统考虑（期望和/或测量的）缓存缺失率。

成本函数优选地考虑（且基于）在基元列表中写入基元与从基元列表读取基元的相对成本。这是需要考虑的重要因素，因为申请人意识到，如上面所讨论，列举基元的渲染目标子区域“水平”（大小）可以尤其影响基元将被写入基元列表或从基元列表读取的次数。因而，例如根据在讨论的图形处理系统中向和从基元列表写入和读取基元的相对成本，在较高或较低的基元列表水平（即针对较大或较小的渲染目标子区域）列举基元将可能是优选的。而且，从和向基元列表读取和写入基元的相对成本可以在不同系统之间变化（可以是系统相关的）。

因而，在尤其优选的实施方式中，成本函数考虑（基于）用于向讨论的（多个）基元列表写入基元的成本。优选地或替代地（且也优选地）考虑（基于）从讨论的（多个）基元列表读取基元的成本。

如上面所讨论，申请人意识到，如果希望减小在基元列举操作中使用的总存储器带宽，例如，则在基元被写入到的列表的数目和基元列举的渲染目标子区域的大小之间存在需要打破的平衡（这将确定基元需要可能不必要地被读取的次数）。如果基元在较低水平（针对较小渲染目标子区域）列举，其必须被写入到较大数目的基元列表中，但是如果它以较高水平（针对较大渲染目标子区域）写入，它将被重读很多次，因为用于子区域的列表将针对该子区域所覆盖的每个渲染区块被重复使用。使用考虑读取和写入成本二者的成本函数帮助优化这种平衡。

用于将基元写入多个基元列表的写入成本优选地基于用于将基元写入一个基元列表的（多个）预定成本乘以基元将被写入的基元列表的数目。

给定基元将被列举在其中的（多个）基元列表，用于读取基元的读取成本优选地基于用于从一个基元列表读取基元的（多个）预定成本乘以基元将被读取的渲染区块的数目（渲染区块的数目将是基元将在其中列举的（多个）基元列表所覆盖的渲染区块的数目）。

在优选实施方式中，读取成本考虑读取基元列表本身的成本和读取用于基元的顶点的成本。因而，基础读取成本优选地基于基元列表读取成本加上每个渲染区块的顶点读取成本。

一次写入或读取基元的基础成本例如可以基于可能影响这些操作的成本的任意合适的参数，诸如且优选地是，用于被讨论的系统的缓存大小和性能、存储器延迟时间等。这种成本例如可以被估算，或它们例如也可以或取代地例如通过测试系统（例如使用合适测试数据的统计分析）被提前和/或在使用时确定。

如有需要，成本函数还可以考虑将影响基元读取和写入成本的其他因素。例如，如果读取操作一次（例如通过使用覆盖单元（coverage mask））读取渲染区块组，如有需要，这可以通过修改相对读取成本考虑。

读取和写入成本优选地依赖于渲染目标子区域的大小（面积）（即，渲染目标子区域覆盖的渲染区块的数目）（且基于后者变化）。申请人意识到，读取和写入成本将依赖于渲染目标子区域的大小，因为渲染目标子区域的大小（即它覆盖多少渲染区块）将关系到例如在它被渲染时针对基元读取的命令和顶点的可缓存性。例如，在基元列表仅用于单渲染区块子区域时，它将仅读取一次，且因此在缓存读取数据时没有益处。然而，覆盖多于一个渲染区块的渲染目标子区域将被读取多于一次（即针对它们覆盖的每个渲染区块），且因此将有利地缓存该数据。这种缓存的使用将使得对于较大渲染目标子区域，读取和写入成本相对低，且使得成本函数优选地考虑这点。

因而，在优选实施方式中，针对不同大小的子区域，“基础”读取和/或写入成本（或多个成本）不同。

在尤其优选的实施方式中，成本函数使用用于每个给定渲染目标子区域（基元列表）的预定“总”成本，且然后将针对被考虑（即，基元将被写入到）的每个基元列表的这些成本求和。如上面所讨论，用于在给定渲染目标子区域的基元列表中列举基元的总成本优选地基于且尤其优选地是基于用于讨论的基元列表的读取和写入成本的求和。优选地，针对不同大小的子区域，“总”成本不同。

在给定基元列表（用于给定渲染目标子区域）中列举基元的基础预定读取和写入和/或总成本（或多个成本）可以且在优选实施方式中被存储以在需要时被图形处理系统使用。更优选地，存在用于各个基元列表的（多个）成本的查找表。

例如存储在成本函数查找表中的预定“基础”成本值（成本函数系数值）可以按需确定。在优选实施方式中，通过很多将被渲染的基准渲染输出（例如帧）的统计分析来确定（生成）一组这种值。这些预定值然后优选地用作至少例如存储在查找表中以用于被图形处理系统使用的初始值。

可以简单地一直继续使用这些初始生成的成本函数值，且在一个优选实施方式中，确实如此。在这种情况中，相应地存在被使用的一组存储的预定成本函数值（系数）。

然而，在尤其优选的实施方式中，成本函数系数的存储初始值可以是且优选地在使用中更新（修改）。这具有这样的优点，例如，使用的成本函数值可以适应于使用它的指定处理器实施方式（例如硬件本身，缓存的大小、遇到的实际反应时间等），而不是固定到用于得出初始成本函数值的“测试”系统。它还具有这样的优点，成本函数可以在使用中适应于当前系统条件，诸如例如当实施初始测试时可能不容易访问且/或可能在使用中动态变化的运行时间问题，系统上的其他负载、被渲染的指定内容等。

使用自适应成本函数操作因而例如允许成本函数操作适应于提供对于使用它的实际系统上的实际内容的更优选解决方案（而不是固定为可以在得出初始成本函数数据时做出的假设）。系统还可以例如当渲染内容和/或存储器子系统负载在使用中变化时实时地重复优化自身。使用自适应成本函数操作还应当允许操作在较宽范围的硬件系统和较宽范围的负载条件上更好地执行，且甚至进一步改善基元列举（装箱）的效率。

本发明的这些布置例如还可以用于动态地优化系统中的功耗，其中读取和写入功率成本不相同（例如读取可能命中缓存而写入通常必须去往主存储器）。

因而，在尤其优选的实施方式中，使用自适应成本函数。

存储的成本函数值的更新可以以任意所需和合适的方式实施。优选地，在使用中实际遇到的例如从和向基元列表读取和/或写入基元的成本被评价，且然后如有必要基于此更新成本函数（存储的成本函数值）。阈值测试例如可以用于确定是否从存储值得出足以保证更新存储值的“实际”成本值。

因而，优选地存在从渲染处理到用于在使用中调节成本函数操作的成本函数操作设置的反馈循环。这实际上然后可以通过在使用中测量基元列举（装箱）的“真实”成本增强成本函数的精确度。

在使用中遇到的实际读取和写入成本等可以按需确定和评价。例如，在图形处理系统包括性能计数器时，这些计数器可以且优选地例如基于涉及成本函数测量系统的事件而评价通过采样性能计数器来体验的实际成本。例如，图形区块化单元的性能计数器可以用于测量区块化单元的指针缓存和写入缓冲器中的缺失率以评价使用中体验的实际写入成本。类似地，基元列表读取器的性能计数器可以用于确定当从基元列表读取基元时体验的缺失率和反映延时。

因而，在尤其优选的实施方式中，性能计数器用于评价（测量）使用中且优选地运行时系统体验的读取和写入成本（性能），且该信息然后用于优选地通过适当地（且在必要时）更新在成本函数使用的成本值来更新成本函数操作。

例如通过性能计数器指示的测量的使用性能可以被处理且用于按需调节成本函数操作。例如，它可以在软件或硬件或在二者的组合中处理。

例如，用于图形处理器的驱动器可以读取性能计数器且例如相应地更新成本函数值。备选地或附加地，图形处理系统可以配置成使用性能计数器的硬件采样和读取以及成本函数更新。这将可能地允许更详细和“生动”的性能信息被使用。例如，如有需要，还可以使用图形处理单元中的管理微控制器以用于此目的。

例如，在正常处理中，即，当系统渲染用于输出到渲染目标的真实数据时，系统的性能可以被测量，且在优选实施方式中，确实如此。

在尤其优选的实施方式中，系统还可以或取代地且优选地还生成针对评价基元列表处理性能和成本函数操作目的专门处理的测试基元。通过使用测试基元来评价系统的性能，可以实现更精确和潜在较不侵入的自适应成本函数布置。

因而，在尤其优选的实施方式中，用于测试目的的虚拟基元可以被包括（注入到）在将被渲染的基元流中。虚拟基元例如可以是随机注入的不可见基元，或针对单个“真实”基元猜测的子区域水平的多个渲染目标组。在后一种情况中，测试处理优选地确定子区域层级水平的哪个组应当被选择用于基元且传递基元的一个拷贝以用于渲染。任意不可见虚拟（测试）基元优选地从发送用于渲染的基元流去除（一旦必要的成本函数信息被确定）。优选地，仅针对虚拟（测试）基元收集写入成本和读取成本信息。

虚拟（测试）基元优选地以与“真实”基元相同的方式被压缩和处理。它们可以用于向基元列表读取器发送很多边带信息，诸如用于指定虚拟基元的统计的写入地址和/或更新的成本函数系数值。基元列表读取器例如可以配置成有条件地直接将更好选择写回到区块化单元的成本函数系数表，因而关闭硬件中的反馈循环。

鉴于测量系统性能的成本函数的更新可以具有任意合适和所需形式。在尤其优选实施例中，基于测量性能修改各个成本函数系数值（诸如且优选地写入、读取和/或总成本值）。例如且优选地，存储在成本函数表中的成本函数系数值可以且优选地基于测量性能更新。

如有需要，对于成本函数的其他修改也是可能的或取代地完成。例如，在优选实施方式中，子区域层级水平的一个或更多渲染目标组可以且优选地基于测量性能启用或禁用（即，允许使用或不允许使用）。这允许系统在任意时间自适应地选择子区域的哪个渲染目标组（层级水平）被使用。单组子区域（层级水平）或多组子区域（层级水平）例如可以按需禁用。这种机制可以通过例如将用于将被禁用的一组子区域（层级水平）的成本函数系数值设置成这种高值来实现，从而确保成本操作将绝不选择该水平。

还可以配置成本函数操作以同样或取代地考虑用于已知将例如随着列举处理进行随着时间遇到的基元列举处理的写入和/或读取操作（或其他成本）中的变化。例如，申请人意识到，对于一些基元列举处理编码方案，用于列举基元的写入和/或读取成本可以随着列举处理进行而变化。例如，当在基元列表中列举基元时使用基于增量（差异）的压缩方案时，其中针对给定列表（箱）列举初始基元将比向列表（箱）写入稍后基元需要更多将要编码的字节（因为增量压缩方案将意味着较少的字节将在列表中写入稍后基元），则向基元列表写入基元的成本将比初始创建列表时（临时）更高，但是然后一旦可以使用增量压缩方案则减小。

在优选实施方式中，成本函数操作相应地配置成考虑将随着列表处理进行针对基元列举处理出现的成本中的这种已知的变化，诸如且优选地，将随着基元列举处理进行出现的写入和/或读取成本中的已知变化。在优选实施方式中，这通过将用于子区域组（层级水平）的成本函数系数值设置为适当值以计算这些成本来实现。

因而，在优选实施方式中，用于子区域组的基元的（例如且优选地写入）成本被设置为在讨论的子区域组的列表（箱）被创建和存储之前使用的初始值，但是然后随着基元列举处理进行（随时间）变化（且优选地减小）。这优选地针对可以准备基元列表的每个子区域组完成。

类似地，在优选实施方式中，用于可以准备基元列表的子区域组（层级水平）（且优选地针对子区域的每一组（针对每个层级水平））的成本系数值被设置为在用于被讨论的子区域组的列表被创建之前使用的初始值，且然后变化，且在优选实施方式中，随着基元列举处理（随时间）进行从初始值减小到另一不同（较低）值或多个值。

因而，在优选实施方式中，用于子区域组的基元的（例如且优选地写入）成本被设置为在讨论的子区域组的列表（箱）被创建和存储之前使用的初始值，但是然后一旦列表包含指定选择数目的基元（例如至少一个基元）则变化（且优选地减小）。这优选地针对可以准备基元列表的每个子区域组完成。

类似地，在优选实施方式中，用于可以准备基元列表的子区域组（层级水平）（且优选地针对子区域的每一组（针对每个层级水平））的成本系数值被设置为在用于被讨论的子区域组的列表被创建之前使用的初始值，且然后变化，且在优选实施方式中，一旦讨论的子区域组的基元列表包含指定选择数目的基元，则从初始值减小到另一不同（较低）值或多个值。

在优选实施方式中，例如用于给定子区域组的写入成本类似地在重写使用基于增量的压缩方案时并不“开放”（针对基元列举处理是缓存的）的基元列表时临时增加，以考虑这一事实：重写不被缓存（已经使用）的列表的成本可能高于写入到已经缓存的列表的成本，例如因为如果基元列表不被缓存，它可能必须重读原先的数据项以计算将要使用的新增量（差异），或系统在该事件中返回到写入启动时的非压缩数据。

并且使用成本函数评价以选择基元应当被包括在哪个基元列表中，如有需要，其他标准可以应用于基元列举处理。

例如，用于基元列表的存储器容量需求应当被考虑。例如，将对于允许基元被包括的基元列表的数目（诸如基元列表的最大数目）存在限制。因而，在优选实施方式中，基元（以及优选地每个基元）不被列举在多于选择的优选预定（阈值）数目的基元列表中。这例如可以促进更精确的控制以及基元（区块）列表的存储器使用需求的知识。这例如可以通过在渲染目标子区域组的每个连续水平（层）测试基元来实现，以确定在该讨论水平（子区域组）基元需要被包括在多少不同基元列表中。在优选实施方式中，当使用时基元可以被包括在其中的基元列表的最大数目是4。

就需要渲染的每个渲染区块而言，每个基元应当仅在一个基元列表中列出。

在尤其优选实施方式中，仅针对目标渲染子区域中的一个组（即在（层级的）子区域分辨率组的一个水平）列举每个基元，即，对于将列举基元的所有渲染目标子区域，针对渲染目标子区域的（水平（大小）的）相同组列举基元。

成本函数评价可以以任意所需和适当方式使用以选择和确定基元应当被包括在哪个渲染目标子区域的基元列表中。在尤其优选实施方式中，处理使用成本函数来确定用于针对讨论的基元的两个或更多可能基元列举（装箱）解决方案列举基元的成本，且然后选择具有最低确定成本的基元列举（装箱）解决方案。因而，基元列举（装箱）处理优选地确定用于针对多个不同基元装箱（列举）解决方案的装箱（列举）基元的成本，且基于此确定最佳列举（装箱）解决方案（即实际上且优选地，具有成本函数确定的最低成本的列举（装箱）解决方案，承受可能在基元列举处理上存在的任意其他限制）。

在成本函数基于向存储器写入基元列表命令且然后在屏蔽基元时读回它们的成本时，该处理实际上将基于将基元列举命令写入到存储器且然后在屏蔽基元时读回它们的成本的模型发现列举基元的“最廉价”方式。

用于被考虑的每个基元列举（装箱）的成本优选地如上面所讨论通过使用存储的预定成本值来确定，该存储的预定成本值然后例如乘以针对讨论的解决方案将在其中列举基元的基元列表数目和/或针对讨论的解决方案将在其中列举基元的基元列表覆盖的渲染区块的数目。

可以看出，在这些布置中，本发明实际上确定用于渲染基元的两个或更多备选装箱（基元列举）布置（解决方案）、使用成本函数确定这些装箱布置的成本且然后基于成本评价选择装箱布置其中一个。

因而，根据本发明的第五方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表的方法，该列表表达生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对渲染目标区的至少两个不同组的子区域准备指示将被处理的基元的系统基元列表，所述渲染目标区的两个不同组的子区域其中至少一个组包含比单个渲染区块大的渲染目标区的子区域，该方法包括以下步骤：

针对将被渲染的基元：

使用可以准备基元的渲染目标区的至少两个不同组的子区域其中至少两个组的子区域来确定用于列举渲染基元的两个或更多备选解决方案；

针对每个确定的备选基元列举解决方案，使用成本函数来评价在用于已经确定基元需要被列举以用于渲染基元的渲染目标区子区域的基元列表中列举基元的成本；

基于成本函数评价选择确定的备选基元列举解决方案其中一个；以及

在已经确定基元需要被列举以用于所选基元列举方案的渲染目标区子区域的基元列表中包括基元。

根据本发明的第六方面，提供一种在基于区块的图形处理系统中分类图形基元以用于渲染到表达将生成的渲染目标的不同区的列表的设备，其中渲染目标分割成多个渲染区块，用于渲染目的，且其中系统基元列表指示将被处理的基元可以针对渲染目标区的至少两个不同组的子区域准备，渲染目标区的两个不同组的子区域其中至少一个组包含比单个渲染区块更大的渲染目标区的子区域，该设备包括：

装置，其针对将被渲染的基元，使用可以准备基元的渲染目标区的至少两个不同组的子区域其中至少两个组的子区域来确定用于列举渲染基元的两个或更多备选解决方案；

装置，其针对每个确定的备选基元列举解决方案，使用成本函数来评价在用于已经确定基元需要被列举以用于渲染基元的渲染目标区子区域的基元列表中列举基元的成本；

装置，其基于成本函数评价选择确定的备选基元列举解决方案其中一个；以及

装置，其在已经确定基元需要被列举以用于所选基元列举方案的渲染目标区子区域的基元列表中包括基元。

本领域技术人员应当意识到，当合适时，本发明的这些方面可以且优选地确实包括此处描述的本发明的优选和可选特征其中一个或更多或全部。因而，例如，成本函数优选地考虑用于被确定的装箱布置的相应写入和读取成本和/或优选地使用自适应成本函数等。

如上面所讨论，在尤其优选实施方式中，系统被限制为使得基元将仅针对单组渲染目标子区域（即，在单个渲染目标子区域层级水平）列举（装箱）。在这种情况中，考虑的基元列举（装箱）解决方案相应地优选地均对应于针对渲染目标子区域的各个不同组（在各个不同渲染目标子区域层级水平）列举基元。

因而，在本发明的这些方面和布置的尤其优选实施方式中，成本函数评价处理确定在可用渲染目标子区域等级水平的两个或更多中的每一个且在优选实施方式中在其每一个处完整（且排他地）列举基元的成本，且然后选择具有最低确定成本的渲染目标子区域组（水平）。因而，基元列举（装箱）处理优选地确定用于在多个渲染目标子区域层级组（水平）其中一个完整（且排他地）装箱（列举）基元的成本，且然后基于此确定最佳装箱解决方案。

当每个基元被限制为仅在单组渲染目标子区域（在单个渲染目标子区域层级水平）列举时，则在尤其优选实施方式中，用于每组渲染目标子区域层级水平的基元列表（箱）的总成本被存储，且然后乘以针对该组（在该水平）基元被包括的列表（箱）的数目，以确定针对该组（在该水平）列举（装箱）基元的总成本。这然后针对被考虑的每个装箱子区域组（层级水平）重复，且然后针对确定为具有最低成本的组（在该水平）列举基元（承受任意其他限制，诸如针对允许基元被包括的不同基元列表的数目的限制）。

因而，在尤其优选实施方式中，用于基元的基元列举（装箱）处理包含：确定用于基元的边界框；针对渲染目标子区域组的一些或全部组（且至少两个组）计算需要包含边界框的子区域的数目；在成本函数中使用确定的子区域数目以估算用于针对该子区域组列举（装箱）基元的成本；选择具有最低估算成本的子区域组为列举基元的子区域组；以及向用于该组渲染目标子区域的合适渲染目标子区域基元列表写入基元。

尽管在这种布置中可以测试每一个可能的装箱解决方案，例如，基元可以列举的子区域组，申请人意识到这可能并不总是可实践的，例如因为在面积/功率或时间方面可能太昂贵。因而，在优选实施方式中，以这种方式测试一些（且至少两个）但非全部可能的装箱解决方案（例如且优选地子区域组）。

从上文还应当意识到，给定基元将典型地仅包括在用于覆盖基元所处的渲染目标区的所选（所选数目的）渲染目标子区域的基元列表中，即，基元将在（至少）一个但非全部的用于覆盖基元所处的渲染目标区的所有渲染目标子区域的单独基元列表中。

尽管上面已经尤其参考给定基元的处理描述了本发明，本领域技术人员应当意识到，这些处理应当针对渲染输出（例如将被显示的帧）中的每个基元执行以允许准备用于渲染输出的基元列表的完整组。因而，系统优选地以本发明的方式、例如以一个接一个的方式依此分类多个基元且优选地用于渲染输出的所有基元。

尽管针对给定渲染目标被分割或可以分割的每一个子区域准备基元列表并不必须，在尤其优选实施方式中，针对可以准备基元列表的每个渲染目标子区域准备基元列表。（然而，应当注意，在一些情况中，在该布置中，例如取决于基元如何在渲染目标中分布以及它判定在哪个基元列表中存储基元，基元列表可能且可以为空（即不包含基元））。

各个基元列表和它们中的基元可以以任意所需和合适方式布置且可以包括任意所需和合适数据。列表优选地被布置且以已经在现有技术中用于这种列表的方式包含数据。因而，它们例如优选地包括用于列表中的每个基元的顶点和/或命令等的标识符以及标记或指示。（因而，除非上下文要求，此处对于基元列表中基元的写入、列表、装箱、读取等的引用表示用于基元列表中（代表和/或与基元相关的）基元的适当命令、数据等的写入等。）

基元优选地以所需渲染顺序（第一个到最后一个）在每个列表中列举（排序），因为这允许基元以先进先出的基础从列表读出。如本领域所已知，基元将通常以它们被渲染的顺序生成。在这种情况中，基元可以简单地且优选地以它们生成的顺序在每个列表中列举。

一旦所有基元被分类且如上面所讨论针对渲染目标子区域准备基元列表，如本领域所已知，渲染区块则使用基元列表处理和渲染，以确定针对每一个区块需要处理哪个基元。

该渲染处理可以且优选地以与已知基于区块的渲染系统类似的方式渲染。因而，优选地，每个渲染区块被单独处理和渲染，即单独的各个区块被一个接一个地渲染。这种渲染例如通过连续或并行的方式渲染各个区块可以以任意所需方式实施。如本领域所已知，一旦所有区块被渲染，它们则可以例如在帧缓冲器中重新组合以用于显示。

因而，本发明优选地包含：一旦准备基元列表，基于逐个区块渲染基元以生成渲染输出；使用基元列表以确定针对将被渲染的每一个区块渲染哪个基元（以确定针对哪个区块应当渲染哪个基元）。

本领域技术人员应当意识到，因为每个渲染区块被处理且渲染，将必须检查包括（覆盖）讨论的渲染区块的所有渲染目标子区域的基元列表，以确定必须针对该区块被处理和渲染的基元。

这种基元列表检查和针对给定渲染区块渲染的基元的识别可以按需实施。在优选实施方式中，基元列表被提供到基元选择单元，该基元选择单元从基元列表选择将被渲染的下一基元且然后向渲染单元（例如流水线）提供该基元以用于渲染。

基元选择单元可以具有任意适当形式。在优选实施方式中，它可以包含区块读取单元。

更优选地，不同基元列表，例如覆盖给定渲染区块的不同水平（分辨率）列表被并行（即同时）提供到基元选择单元，基元选择单元然后从列表之一选择需要处理的下一基元。

基元从给定渲染区块选择的基元列表组（即基于选择单元应当读取以识别用于给定区块的渲染的基元的基元列表组）例如可以通过在适当时向图形处理器（例如基元选择单元）发送该数据以任意所需方式指示（例如向基元选择单元）。在优选实施方式中，当新区块将被渲染为例如“新区块”命令的一部分或与之相关（告知渲染单元开始渲染新区块的命令）时，该信息被发送。因而，每个渲染区块优选地以某种方式与将用于区块的基元列表组相关。当然，其他布置也是可能的。

指示针对给定渲染区块将使用哪个渲染列表的信息可以以任意适当和所需形式提供。在优选实施方式中，提供对相关基元列表的指示或标记组。在另一优选实施方式中，提供对基元列表的指针或标记组的变化，以允许系统识别且改变在将渲染新区块时需要改变的基元列表。例如还可以准备将使用的基元列表和区块的xy位置之间的预定关系组，该关系然后可以用于基于区块的x、y坐标确定用于区块的基元列表。例如，渲染区块的x、y位置可以用于索引到指定针对每个区块位置使用的基元列表的查找表。当然，其他布置也是可能的。

可以以任意所需和合适方式从用于区块的基元列表（例如通过基元选择单元）选择被渲染的下一基元。

在尤其优选实施方式中，基元生成和分类处理能够索引或添加对于基元的索引，因为优选地它们被包括在基元列表中，且该索引然后例如被基元选择单元使用以选择接下来将要处理的基元。索引优选地通过连续对基元编号完成，因为优选地它们被包括在基元列表中。在优选实施方式中，分配给基元的索引仅在列举基元的子区域组（层级水平）变化（即不同于用于前一基元的子区域组（层级水平））时变化（例如递增）。

当列举（装箱）基元时基元的这种索引帮助用于区块的渲染处理，因为它例如将促进以正确的顺序渲染基元。尤其是，针对每个基元给出的（分类）索引可以用于选择用于渲染的下一正确（所需）基元，由此例如允许在渲染基元时重构所需基元顺序，且帮助确保基元可以且取自不同基元列表以便于按照所需（正确）顺序（典型地首次生成它们的顺序）进行渲染。

在本发明的尤其优选实施方式中，（多个）基元列表可以且优选地通过图形处理器或在图形处理器中，最优选地通过基元选择单元缓存，即，基元列表可以且优选地存储在图形处理器的本地可更快速访问的存储器中。因而，本发明的设备和方法优选地包括缓存（多个）基元列表的装置或步骤。这种缓存可以在基元列表方面减小带宽使用。

尽管上面已经参考用于渲染目标子区域的基元列表的存储描述了本发明，本发明还将或取代地可以在类似基础上存储其他图形数据。例如，存在其他形式的图形数据，诸如图形（例如渲染、设置、诸如剪切参数和基元类型参数（例如基元是否是点、线、三角或方形））和可以在每个渲染区块或每个渲染目标子区域基础上指定被指定或能够被指定的区块命令（例如最终区块命令）。

申请人意识到，能够在渲染目标子区域基础上以类似于上面讨论的基元列表的方式（选择性）存储这些类型的数据可能同样是有利的。

例如，如果指定参数或命令用于每一个渲染区块，可能优选的是，将它存储在共同用于整个渲染目标的单个基元（或其他）列表中。另一方面，对于仅一个或少量渲染区块需要的命令和数据，优选地可以仅在涵盖这些渲染区块的（多个）渲染目标子区域方面，例如，以在包含相关渲染区块的层级中的较低水平存储它。

因而，本发明的系统还可以优选地以上面针对准备基元列表描述的方式（例如且优选地，在用于渲染目标的子区域的单独“列表”中）存储不同于基元的数据和命令。

在这些布置中，图形数据（例如命令或设置）例如可以存储在例如用于渲染目标子区域的单独的“命令”列表中。然而，在尤其优选的实施方式中，该图形数据被包括在用于子区域的基元列表中，即，使得一个且优选地每个基元列表可以且将包括基元列表以及诸如基元列表内散布的参数、设置和/或命令之类的其他图形数据。

在尤其优选实施方式中，该其他图形数据以类似于基元的方式被索引，因为这将同样允许以正确的顺序使用数据。同样，单独的索引可以用于该数据，但是最优选地，它在基元索引内被索引，即，例如使得系统（其中例如在渲染最开始的三个基元之后指行命令）将渲染基元1、2、3，然后执行命令4，然后渲染基元5、6且依此类推。

应当注意，尽管此处对于“基元”的引用主要旨在表示诸如三角形、栅格、线或点等“简单”多边形形式的图形基元，如本领域所已知（且在优选实施方式中，确实表示诸如三角、方形、线或点的“简单”多边形形式的图形基元），本发明还可应用于诸如图形组件或基元之类旨在代表场景或较小多边形组（诸如一组连续三角形）中较大对象的较大图形对象或基元。例如，可能希望将一组多个独立的多边形处理且分类为单个图形对象或基元。这种较大“复杂”基元（“元基元”）可以等价地以本发明的方式针对渲染目标子区域列出。因而除非上下文需要，此处对于“基元”等的引用应当被相应地解释。

如有需要，用于自适应地调谐本发明的成本函数操作的性能测量也可以用于有效地调谐提供优先级仲裁或服务质量支持的系统中的存储器子系统。例如，具有若干主存储器和从存储器的缓存可以配置成基于性能统计优化一个或更多主存储器和/或从存储器。例如，可以向针对具有最多基元的渲染目标子区域组（水平）的读取和写入给出优先级。

本发明可应用于任意形式和配置的图形处理器和渲染器，诸如具有“流水线式”布置的渲染器（在这种情况中，渲染器将是渲染流水线的形式）。

本发明相应地扩展到包括根据此处描述的本发明的方面中的任意一个或更多个的方法或根据该方法操作的设备。承受实施上面讨论的指定功能所必要的任意硬件，这种图形处理器可以包括图形处理器所包括的通用功能单元其中任意一个或更多个或全部。

本发明的各个功能可以以任意所需和合适的方式实施。例如，本发明的功能可以按需以硬件或软件实施。因而，例如，本发明的各个功能元件和“装置”可以包含可操作为执行各种功能等的合适的处理器或多个处理器、控制器或多个控制器、功能单元、电路、处理逻辑、微处理器布置等，诸如适当地专用硬件元件或处理电路和/或可以编程为以所需方式操作的可编程硬件元件或处理电路。

各个功能元件可以按需彼此分离或可以共享电路（例如通过相同的处理器和/或处理电路执行）。

在一个优选实施方式中，本发明的设备包含配置成以所需方式操作的专用（不可编程）处理电路。在另一优选实施方式中，它包含编程为以所需方式操作的可编程处理电路。

在尤其优选实施方式中，在生成和输出被写入为（例如，到用于显示设备的帧缓冲器的）渲染输出的图形数据的单个图形处理平台上实施本发明的功能。

在一些实施方式中，本发明的数据处理系统、图形处理系统、数据处理器、图形处理器、处理电路、设备等可以与存储器和/或存储此处描述的诸如基元数据、基元列表、成本函数以及成本函数参数（因素）等之类的数据的一个或更多存储器设备和/或用于执行此处描述的处理的存储软件通信。数据处理系统、图形处理系统、数据处理器、图形处理器、处理电路、设备等还可以与基于基元列表显示图像的显示器等通信。

此处还应当注意，如本领域技术人员应当意识到，本发明的各个功能等可以被复制且在给定处理器上并行实施。例如，可以存在并行操作的多个区块化单元和/或基元选择单元。

本领域技术人员还应当意识到，适当时本发明的所有描述方面和实施方式可以包括此处描述的优选和可选特征其中任意一个或更多个。

根据本发明的方法可以至少部分地使用例如计算机程序的软件实施。因而可以看出，当从其他方面查看时，本发明提供计算机软件，当安装在数据处理装置上时该计算机软件专门调适为实施此处描述的方法，该计算机程序元件包含当程序元件在数据处理装置上运行时用于执行此处描述的方法的计算机软件代码部分，且计算机程序包含调适为当程序在数据处理系统上运行时执行此处描述的（多个）方法的所有步骤的代码装置。数据处理系统可以是微处理器、可编程FPGA（现场可编程门阵列）等。

本发明还扩展为包含这种软件的计算机软件载体：当用于操作图形处理器、渲染器或包含数据处理装置的微处理器系统时，该软件与所述数据处理器装置、所述处理器、渲染器或系统结合导致实施本发明的方法的步骤。这种计算机软件载体可以是诸如ROM芯片、CD ROM、RAM、闪存或磁盘之类的物理存储介质，或可以是诸如电线上的电子信号、诸如到卫星的光学信号或无线电信号等的信号。

还应当意识到，并不是本发明的方法的所有步骤都需要通过计算机软件实施且因而从更宽的方面，本发明提供计算机软件且这种软件安装到计算机软件载体上以用于实施此处提及的方法的步骤其中至少一个。

本发明还相应地适当地实施为与计算机系统一同使用的计算机程序产品。这种实施方式可以包含固定在诸如非瞬时计算机可读介质（例如磁盘、CD ROM、ROM、RAM、闪存或硬盘）这样的有形介质上的一系列计算机可读指令。它还可以包含一系列计算机可读指令，该一系列计算机可读指令可以通过包括但不限于光学或模拟通信线的有形介质或使用包括但不限于微波、红外或其他传输技术的无线技术无形地经由调制解调器或其他接口设备发送到计算机系统。该一系列计算机可读指令实施本公开中之前描述的全部或部分功能。

本领域技术人员将意识到，这种计算机指令可以以很多编程语言编写以用于与很多计算机架构或操作系统一同使用。而且，这种指令可以使用现今或未来的任意存储器技术存储，所述存储器技术包括但不限于半导体、磁性、或光学，或使用现今或未来的任意通信技术传输，所述通信技术包括但不限于光学、红外或微波。可以预期，这种计算机程序产品可以分布为具有辅助印刷或电子文档（例如紧缩套装软件）的可移动介质，使用计算机系统（例如在系统ROM或固定磁盘上）预载或通过网络（例如因特网或万维网）从服务器或电子公告板分布。

附图说明

现在将仅通过示例的方式且参考附图描述本发明的很多实施方式，附图中：

图1示意性示出基于区块的图形处理布置；

图2示意性示出可以根据本发明操作的图形处理器的布置；

图3示意性示出根据本发明的用于向基元列表分配基元的处理的实施方式；

图4示意性示出将被渲染的帧中的基元组；

图5示意性示出渲染目标的子区域组的分层布置的实施方式；

图6示意性示出针对不同组的渲染目标子区域列举基元的效果；以及

图7示意性示出用于非方形渲染目标的渲染目标子区域组的优选布置。

贯穿附图，在合适时，相似的参考数字用于相似的特征。

具体实施方式

现在将参考图2、3、4和5描述本发明的优选实施方式。

图2示意性示出可以根据本发明操作的图形处理器20。图形处理器20包括几何处理器21和渲染器22，二者均可以访问存储器23。如本领域所已知，存储器23可以与几何处理器21和渲染器22一起“在芯片上的”或可以是可以被几何处理器21和渲染器22访问的外部存储器。

尤其是，且如图2所示，存储器23存储一组原始的几何形状数据24（如本领域所已知，其例如通过图形处理器驱动器或在图形计处理器20的主机系统（微处理器）上允许的API提供）、一组变换的几何形状数据25（同样如本领域所已知，其是针对原始的几何形状24实施的各种变形和处理操作的结果）以及一组基元列表26。基元列表26包含如本领域所已知的用于相应基元的数据、命令等，且根据本发明而被准备。下面将详细描述该处理。

变换的几何形状数据25例如包含如本领域所已知的变换的顶点（顶点数据）等。

几何处理器21尤其包含可编程顶点着色器27和基元列表构建单元28。可编程顶点着色器27将存储在存储器23中的原始的几何形状数据24作为其输入且处理该数据以提供包含准备用于渲染输出（例如将被显示的帧）中的2D布置形式的几何数据的变换的几何形状数据25（它然后存储在存储器23中）。可编程顶点著色器27和它实施的处理可以具有任意合适的形式且可以是本领域技术已知的任意合适且希望的这种处理。

基元列表构建单元28实施向随后被渲染器22使用的基元列表分配基元的本发明的处理以识别应当针对将被渲染的每个区块而被渲染的基元以生成渲染输出（在该实施方式中是将被渲染以便于显示的帧）。为此，基元列表构建单元28将源自可编程顶点着色器27的变换的且处理的顶点（几何形状）数据25（即帧中基元的位置）作为其输入、使用该数据构建基元列表、且在存储器23中将这些列表存储为基元列表26。下面将详细描述该处理。

渲染器22包括基元选择单元29、基元列表缓存30、顶点选择单元31、顶点数据缓存32、栅格化单元33、渲染单元34和区块缓冲器35。

在该实施方式中，栅格化单元33、渲染单元34和区块缓冲器35以针对图形处理系统中的这种单元的通常的方式操作。因而，栅格化单元33将基元和其顶点作为其输入、栅格化基元成片段且将这些片段提供到渲染单元34。渲染单元34则针对片段执行很多渲染处理，诸如纹理映射、混合、着色等，且生成渲染的片段数据，它存储在区块缓冲器35中以用于提供到输出渲染目标（诸如用于显示的帧缓冲器）。

渲染器22的基元选择单元29确定接下来渲染哪个基元。这通过考虑存储在存储器23中的基元列表26且从这些列表之一选择将要渲染的下一个基元来完成。下面将详细描述该选择处理。

基元选择单元29还在基元列表缓存30中放置一个或更多基元列表。

基元选择单元29向顶点选择单元31提供它针对下一渲染已经选择的基元。响应于此，顶点选择单元31从存储在存储器23中的变换的几何数据25检索用于讨论的基元的适当的变换的顶点数据，且然后将基元（即，其变换的顶点数据）提供到栅格化单元33以用于处理。如有需要，顶点选择单元31可以在顶点数据缓存32中缓存从存储器23检索的顶点数据。

如上面所讨论，栅格化单元33然后栅格化基元成片段，且将这些片段提供到渲染单元34以用于渲染。渲染单元34针对片段执行很多渲染处理，诸如纹理映射、混合、着色等，以生成用于代表基元的片段的渲染片段数据且将渲染片段数据存储在区块缓冲器35中用于提供到输出渲染目标（诸如用于显示的帧缓冲器）。

现在将参考图3、4和5更详细描述基元列表构建单元28的操作和基元列表26的准备。

如上面所讨论，本发明可应用于其中渲染目标（被将被渲染的帧）被渲染为多个相应渲染区块的渲染系统。再者，与渲染目标被分割成区块以用于渲染目的一样，渲染目标区实际上也分割成其中可以是或可以准备单独（不同）基元列表（即，将被渲染的基元列表）的多个组的子区域。

图4和5说明可以用于本实施方式的可以准备基元列表的渲染目标子区域组的布置的优选实施方式。

图4示出分割成用于渲染目的的多个的单个渲染区块51的渲染目标50（例如，将被显示的帧）。（应当注意，图4没有示出渲染目标50分割成的所有的单个的渲染区块51，仅示出这些渲染区块中的少数几个。这是为了清晰目的。然而，整个渲染目标50实际上被分割成相等的渲染区块51。）

在该实施方式中，可以针对每个渲染区块分别准备基元列表（即，存在对于每个渲染区块51排他的基元列表）。因而，系统具有可以准备基元的第一组的渲染目标区子区域58，其中该组中的每个子区域58对应于各个单个渲染区域51。

与各个渲染区块51和渲染目标子区域58一样，渲染目标50也可以被如下的渲染目标子区域组叠加，即，上述渲染目标子区域组的相应子区域包含不同组的多个渲染区块51。这些组的多个渲染区块子区域实际上在渲染目标50上叠加以提供具有总渲染目标区的不同（区）分割的层。

因而，如图4所示，存在16个渲染目标子区域52的组（层），每个该子区域包含2×2个渲染区块51。存在包含4个子区域53的另一较低分辨率组（层），每个该子区域包含4×4个渲染区块。最后，存在包含覆盖整个渲染目标区（且因而包含渲染目标的8×8个渲染区块）的一个子区域54的子区域组。

从图4可以看出，该布置的效果在于，渲染目标50利用渲染目标区子分割的不断增加的层级来叠加。这在图5中示意性示出。因而，存在包含涵盖整个渲染目标区50的8×8个渲染区块的一个子区域54的组的最高水平层。然后存在4个4×4渲染区块子区域53的组，然后存在16个2×2渲染区块子区域52的组且最后是包含64个单个渲染子区域58的组。图5还以粗线以说明目的示出针对渲染目标子区域的每个组（渲染目标子区域层级组中的每一层（水平））基元80将被考虑落在其中的渲染目标子区域。

图4还以说明目的示出将被渲染且相应地需要分配给基元列表以用于渲染的三个基元55、56和57。

（同样，本领域技术人员应当理解，实际上，任意给定渲染输出（例如将被渲染的帧）将典型地包含不同于图4所示的三个基元的更多基元。然而，用于简单和清晰目的，图4仅示出3个基元。）

如上面所讨论，且如本领域所已知，在将被渲染的渲染目标50被分割成用于渲染目的的较小渲染区块51的系统中，系统必须能够识别针对每个渲染区块应当渲染哪个基元。如本领域所已知，这通过提供所谓的基元列表完成，该基元列表针对每个渲染区块识别应当针对该基元区块渲染的基元。

如上面所讨论，本发明提供优于现有基元列表准备处理的改进，因为与允许基元列表针对与渲染目标被分割以用于渲染目的的各个渲染区块对应的渲染目标区（子区域）准备基元列表一样，本发明还针对包含多于一个渲染区块的渲染目标子区域准备基元列表，即，共同用于多个渲染区块的基元列表。

在本实施方式中，基元列表构建单元28准备用于每个独立渲染区块子区域58的基元列表、用于每个2×2渲染区块子区域52的单独基元列表、用于每个4×4渲染区块子区域53的单独基元列表、以及用于覆盖整个渲染目标50的8×8渲染区块子区域54的单独基元列表。为此，基元列表构建单元28进而获取每个基元，确定用于该基元的位置，将基元位置与子区域58、52、53和54（覆盖的渲染目标区）的位置进行比较,且然后以下面讨论的方式向用于子区域的各个基元列表26分配基元。

基元列表构建单元28确定每个基元以及相应地给定基元将落在其内且在该实施方式中使用边界框装箱技术贯穿的子区域的位置。因而，如本领域所已知，基元列表构建单元28使用它通过可编程顶点着色器27针对给定基元设置的确定的变换的顶点位置，以构建用于基元的边界框且然后识别基元的边界框落在（贯穿）哪个子区域。该处理可以诸如通过现有技术中针对该目的已知的技术以任意合适和所需方式实施。用于基元的边界框优选地例如通过基元列表构建单元生成为基元列举处理的一部分，但是其他布置当然也是可行的。

本领域技术人员应当意识到，如有需要，可以使用用于将基元确定和定位在渲染目标内且涉及子区域的其他技术。例如，如本领域所已知，可以等同地使用精确装箱技术。

在本实施方式中，如上面所讨论，基元列表构建单元28针对用于给定基元的不同可能基元列举（装箱）解决方案使用成本函数评价以确定在哪个基元列表（其渲染目标子区域的基元列表）中列举基元。本质上，如下面进一步讨论，基元列表构建单元28使用渲染目标子区域的不同可能组（即，在不同可能层级水平）估算列举用于渲染的基元的成本，且然后使用估算的成本来确定列举（装箱）基元的渲染目标子区域组（层级水平）。

为此，基元列表构建单元28使用用于在相应子区域中且在相应子区域组的水平列举基元的可编程成本的查找表316，且然后使用乘法器阵列来得出针对子区域的每个相应组（水平）列举（装箱）基元的大致成本。一旦完成该操作，则它选择具有最低确定成本的子区域组（水平）作为用于基元的列举（装箱）解决方案，且在（用于所选择组的子区域的适当渲染目标子区域）适当基元列表中相应地列举基元。

图3说明该处理。如图3所示，基元列表构建单元28将源自用于讨论的基元的可编程顶点着色器27的变换的基元位置数据作为其输入（步骤S60），且首先计算用于被考虑的基元的边界框（步骤S61）。

在本实施方式中，用于每个基元的边界框被确定为简单的矩形。当然，其他布置也是可能的。

用于基元的边界框可以以任意所需和适当方式生成。在本实施方式中，用于基元的输出顶点被分类以发现基元的极点X和Y值，且初始边界框被计算。

然后，针对每一组的渲染目标子区域（即，被考虑的每个层级水平），基元列表构建单元28确定基元边界框将落在其中的子区域组中的子区域（的数目）（步骤S62）。（这是在针对讨论的子区域组列举基元时基元将需要列举以适当渲染基元的基元列表的数目）。该确定可以使用任意合适和所需的技术完成。在本实施方式中，通过以考虑（比较）的水平将边界框位置量化为子区域的分辨率来完成这点。所以，对于2×2渲染区块子区域，例如，（以渲染区块的）子区域的X和Y位置被除以2，所以从（13,11）→（15,19）的边界框应当是2×2区块子区域中的(6,5)→(7,9)。使用简单的偏移操作执行分割，这在硬件中较为便宜。

基元列表构建单元28然后使用成本函数来估算与针对被考虑的每个相应组的渲染目标子区域（等级水平）列举（装箱）基元相关的总读取和写入成本（步骤S63）。然后基于针对不同装箱解决方案的预定成本而选择列举（装箱）基元的子区域组（层级水平）（在本实施方式中，具有最低估算成本的装箱解决方案），且在用于所选组的子区域（层级水平）的适当子区域基元列表（通过基元的边界框确定）中包括基元（步骤S64）。

这针对渲染输出的每个基元重复（步骤S65）。

应当意识到在本实施方式中，基元列表构建单元考虑单独针对每个子区域组（层级水平）装箱基元的成本，其效果是：每个基元将仅针对单个子区域组（即，在渲染输出子区域层级的组中的单个水平）列举（装箱）。（例如，如果基元边界框在子区域组层级的层级水平A落在6个子区域中，则它将例如在水平A或在水平A+1列举，而不针对水平A+1中的4个子区域并且水平A中的一个或更多其他子区域列举）。这帮助简化装箱处理且使得它更有效。当然，其他布置也是可能的。

基元列表构建单元28使用的成本函数具有两个分量：向用于讨论的子区域组的（多个）基元列表写入基元的成本；以及在基元列表选择单元29中从基元列表读回基元的成本。用于给定组的子区域列举（装箱）解决方案的写入成本依赖于基元应当被写入到该组子区域的基元列表（箱）的数目N。读取成本依赖于针对讨论的渲染输出子区域组（在层级水平）被N个箱覆盖的渲染区块的数目。

因而成本函数基本如下确定用于针对给定组的子区域列举基元的成本：

写入基元的成本＝针对子区域组写入的基元列表（箱）的数目×每个列表（箱）的写入成本。

从基元列表读取基元的成本＝（每个渲染区块的列表读取成本＋每个渲染区块的顶点读取成本）×（每个列表（在每个箱中）覆盖的区块的数目×针对子区域组写入的基元列表（箱）的数目）。

所以，针对给定组的子区域（针对给定基元列举（装箱）解决方案））列举基元的总成本是：

总成本＝针对子区域组写入的列表（箱）的数目×（每个列表（箱）的写入成本＋（（每个渲染区块的列表读取成本＋每个渲染区块的顶点读取成本）×每个列表（箱）的区块的数目））。

为了简化使用中成本函数确定，本实施方式使用预定值来代表用于给定组的渲染目标子区域（层级水平）的每个基元列表（箱）的成本。因而，给定装箱解决方案（即，用于针对给定组的渲染目标子区域列举基元）的总成本如下确定：

总成本＝写入的基元列表（箱）的数目×用于讨论的子区域组（层级水平）的每个基元列表（箱）的总成本。

用于给定组的子区域的每个基元列表（箱）的总成本被存储在存储器23中的查找表36中以被基元列表构建单元28使用。查找表中的初始值通过很多基准渲染输出（例如图像）的分析生成。这些初始值然后在使用中修改，如下面进一步讨论。初始确定值还设置为缺省值以在需要时用作系统的复位值。

本实施方式针对用于每个相应组的渲染目标子区域的基元列表使用以下基本成本：

层级水平	每个基元列表（箱）的成本
		0（1×1渲染区块子区域）	2.375
1（2×2渲染区块子区域）	3.5
		2（4×4渲染区块子区域）	8
3（8×8渲染区块子区域）	26
		4（16×16渲染区块子区域）	98
5（32×32渲染区块子区域）	386
		6（64×64渲染区块子区域）	1538
7（128×128渲染区块子区域）	6146
		8（256×256渲染区块子区域）	24578
9（512×512渲染区块子区域）	98306
		10（1024×1024渲染区块子区域）	393218
11（2048×2048渲染区块子区域）	1572870
		12（4096×4096渲染区块子区域）	6291460

此处应当注意，尽管在本实施方式中，每个基元列表（每个箱）的渲染区块的数目针对每个相应相的渲染目标子区域（层级水平）增加4，在成本函数评价中使用的每个基元列表（箱）每次并不简单地增加4。这是因为缓存用于涵盖多于一个渲染区块的子区域的列表可能是有利的（因为它们被确保在基元选择单元29中读取多次），且因此用于具有较大面积子区域的子区域组的读取和写入成本可以比具有较小面积子区域的子区域组的成本低。

尽管如上面所讨论，本实施方式中基于读取和写入成本的概念确定成本函数成本值（因子），成本函数成本值（因子）可以以很多方方式确定。例如，它们也可以或取代地基于给定组的校正基元中基元的平均大小。

从上面可以看出，基元列表构建单元28通过使用成本函数计算用于渲染目标子区域的多个不同组中的每一个组（层级水平）的列举（装箱）基元的成本，来确定每个基元应当进入的渲染目标子区域的哪个组（哪个层级水平），且然后选择具有最低成本函数值的解决方案。这样，基元列举构建单元实际上基于向存储器写入基元（基元命令）的成本模型来发现列举（装箱）每个基元到单个组的渲染目标子区域（层级水平）的“最廉价”的方式，且然后在栅格化和渲染（着色）期间读回它们。

本实施方式中的成本计算处理可以通过以下伪代码示意性表达：

如上所述，尽管本实施方式支持13个基元列举层级水平（子区域组），在本实施方式中，每个基元并不针对13个层级水平中的每一个被测试。而是，仅层级水平其中一些且优选地8个而非全部在任何一次被启用（即可用于列举基元）。这帮助控制用于基元列表的存储器需求。当前启用的层级水平（且因此基元应当相对于其被测试）可以被选择且例如按需指示为用于基元列表构建单元28的工作描述符的一部分。

如上面所讨论，在本实施方式中，在成本函数中使用的可编程成本的查找表36中的初始成本值通过适当测试渲染输出（例如测试图像）数据的统计分析确定。然而，成本函数处理的精确度通过测量使用中列举（装箱）基元的成本且在适当时使用确定的成本更新成本函数系数值来提高。

为了测量使用中体验的成本，本实施方式使用两个不同技术。

第一个这种技术可以被认为是“非侵入式监控”。在这种情况中，基元列表构建单元28使用其性能计数器（其在任意事件中存在以监控基元列表构建单元的性能）以测量其指针缓存和写入缓冲器中的缺失率，以确定在使用中体验的在基元列表中写入命令的实际成本。基元选择单元29还使用其性能计数器来确定与从基元列表读取基元相关的缺失率和反应延时。这些统计然后例如在软件或硬件或二者的组合中处理，且在计算基元列举装箱解决方案成本时用于调节成本函数查找表中的成本。例如，图形处理器驱动器可以配置成获得该信息且在需要时使用它来修改成本函数查找表中的成本值。

本实施方式还能够实施使用中体验的实际成本的更“侵入式”监控。为此，基元列表构建单元28可以向基元命令流注入虚拟基元，且然后收集恰好关于这些基元的写入成本信息。基元选择单元29还收集仅用于这些虚拟基元的读取成本信息。虚拟基元然后从发送的基元流去除以用于栅格化和渲染（着色）。

在该布置中，虚拟基元可以是随机注入的不可见基元，或多边形列表构建单元28可以注入针对单个真实基元猜测的多个组的子区域层级水平。在后一种情况中，之前体验的成本将被收集，且基元选择单元然后确定应当在渲染目标子区域的哪个组（哪个层级水平）列举基元，同时还传递基元的一个拷贝到栅格器和渲染器以用于渲染。

在这些布置中，虚拟基元以与真实基元相同的方式被压缩和处理，且所以可以用于向基元选择单元29发送很多边带信息，诸如用于指定虚拟基元的写入地址统计或甚至是更新的成本函数系数。基元选择单元29例如可以有条件地将装箱解决方案的更好选择直接地写回到基元列表构建单元，因而关闭硬件中的反馈循环。

在这些布置中，到成本函数和成本函数查找表的自适应反馈的强度可以是从相对微小、低速率调节在查找表中的各个成本函数系数到动态地启用或禁用整个组的渲染目标子区域（层级水平）。在后一种情况中，例如，反馈可以用于将针对给定组的渲染目标子区域（层级水平）的成本函数值设置为实际绝不使用该子区域组的高值。

从基元选择单元29收集的统计例如还可以用于有效地调谐提供优选级仲裁和服务质量支持的子系统中的存储器子系统。

为了说明性目的，现在将相对于图4中示出的基元描述基元测试处理的操作。

首先获取图4中示出的基元55，基元列表构建单元28将确定：如果仅针对该组子区域列举基元55，基元55将需要针对多少单区块子区域58、多少2×2区块子区域52、多少4×4区块子区域53和多少8×8区块子区域54列举。在这种情况中，基元列表构建单元28将相应地计算基元55将需要针对6个单区块子区域58（因为边界框装箱被使用）或2个2×2区块子区域52或2个4×4区块子区域列举或针对8×8区块子区域54列举一次。

基元列表构建单元28然后将在每一组的子区域水平使用确定数目的子区域以使用上面讨论的成本函数来估算在相应组的子区域水平列举基元55的成本。在这种情况中，成本估算将如下：

对于单区块子区域58水平：6×2.375=14.25；

对于2×2区块子区域52水平：2×3.5=7；

对于4×4区块子区域53水平：2×8=16；且

对于8×8区块子区域54水平：1×26=26。

基元列表构建单元28将相应地选择2×2区块子区域52水平为列表基元55的水平，且相应地向用于基元55落在其内的相应2个2×2区块子区域52的基元列表添加基元55。

类似地，对于图4中示出的基元56，基元列表构建单元28将确定：如果仅针对该组子区域列举基元56，基元56将需要针对多少单区块子区域58、多少2×2区块子区域52、多少4×4区块子区域53和多少8×8区块子区域54列举。在这种情况中，基元列表构建单元28将相应地计算基元56将需要针对4个单区块子区域58或1个2×2区块子区域52或1个4×4区块子区域列举或针对8×8区块子区域54列举一次。

基元列表构建单元28然后将在每一组的子区域水平使用确定数目的子区域以使用上面讨论的成本函数来估算在相应组的子区域水平列举基元56的成本。在这种情况中，成本估算将如下；

对于单区块子区域58水平：4×2.375=9.5；

对于2×2区块子区域52水平：1×3.5=3.5；

对于4×4区块子区域53水平：1×8=8；且

对于8×8区块子区域54水平：1×26=26。

基元列表构建单元28将同样相应地选择2×2区块子区域52水平为列表基元56的水平，且相应地向用于基元56落在其内的相应2×2区块子区域52的基元列表添加基元56。

在图4中示出的基元57的情况中，基元列表构建单元28将确定：如果仅针对该组子区域列举基元57，基元57将需要针对多少单区块子区域58、多少2×2区块子区域52、多少4×4区块子区域53和多少8×8子区域54列举。在这种情况中，基元列表构建单元28将相应地计算基元57将需要针对4个单区块子区域58或4个2×2区块子区域52或1个4×4区块子区域列举或针对8×8区块子区域54列举一次。

基元列表构建单元28然后将在每一组的子区域水平使用确定数目的子区域以使用上面讨论的成本函数来估算在相应组的子区域水平列举基元57的成本。在这种情况中，成本估算将如下；

对于单区块子区域58水平：4×2.375=9.5；

对于2×2区块子区域52水平：4×3.5=14；

对于4×4区块子区域53水平：1×8=8；且

对于8×8区块子区域54水平：1×26=26。

基元列表构建单元28将相应地选择4×4区块子区域53水平为列表基元57的水平，且相应地向用于基元57落在其内的相应4×4区块子区域53的基元列表添加基元57。

上述处理通过基元列表构建单元28针对将被依次渲染的渲染输出中的每一个基元重复，直到针对渲染目标可以分割到成的子区域组中的每个子区域生成完整的基元列表26。

基元列表构建单元28在基元列表26中以它从可编程顶点着色器27接收基元的顺序布置基元。这意味着，只要考虑每个独立基元列表26，如本领域所已知，列表中的基元是它们生成的顺序，该顺序典型地对应于渲染基元的所需顺序。（如本领域所已知，当生成用于渲染的基元时，它们通常通过主机驱动器或API以其希望渲染基元的顺序生成且被以该顺序被提供到图形处理器）。因而，当基元列表构建单元28按照基元被接收的顺序获得基元时，只要考虑每个独立基元列表，它将以渲染顺序在各个区块列表中放置基元。）

在适当基元列表或多个列表中放置基元的同时，基元列表构建单元28还向基元列表26中的基元分配且关联用于该基元的索引。基元列表构建单元28具有用于该目的的计数器，且简单地分配给基元，因为这些基元以计数器的当前计数被渲染。本实施方式可以配置为针对每个新基元递增索引，或者仅在新的子区域组中列举基元时改变（递增）（即当基元被列举的层级水平改变（即，不同于用于在先基元的子区域组（层级水平））分配给基元的索引。

这样，每个基元以它被基元列表构建单元28接收的顺序（即，通过主驱动器或API等提供基元的顺序，即希望渲染基元的顺序）被编号（在该实施方式中为递增顺序）。如下面进一步讨论，基元列表构建单元28向每个基元分配的索引被基元选择单元29使用，以识别且从存储器23中的基元列表26选择用于渲染的下一基元。

当基元被放置在基元列表26中时，基元的这种索引可能是需要的，因为如本领域所已知且如上面所讨论，它在图形处理系统中通常是需要以指定顺序渲染基元。这在仅存在单个基元列表（从其获取用于渲染的基元）时是没有问题的，因为在该情况中，如上面所讨论，基元将以它们被提供到图形处理器的顺序即渲染的所需顺序被包括在基元列表中。然而，如本实施方式所述，当用于渲染的下一基元可能需要从多于一个基元列表选择时，以渲染的正确顺序选择基元可能不是那么直接。以如上讨论的方式索引基元帮助减轻这种困难，因为如下面进一步讨论，它允许基元选择单元29识别基元被提供到图形处理器以用于渲染的顺序且相应地以该顺序选择下一基元。

一旦基元列表构建单元28完成构建用于被渲染的渲染输出（例如帧）的基元列表26且将这些列表存储在存储器23中，则渲染器22可以渲染输出（例如帧）。现在将描述该处理。

如上面所讨论，在本实施方式中，通过逐个区块地渲染的基础针对渲染区块执行渲染处理，即渲染输出的每个渲染区块51依次分别被渲染，且渲染的区域相组合以提供整体渲染输出（例如用于显示的帧）。

因而，渲染器22首先被提供有将被渲染区块的识别且使用它来适当地配置自身。尤其是，应用于将被渲染的渲染区块的存储的基元列表26，即在本实施方式中，将被渲染的相应渲染区块排他性的基元列表，用于包括将被渲染的渲染区块的2×2渲染区块子区域的基元列表，用于包括被渲染的渲染区块的4×4渲染区块子区域的基元列表以及用于覆盖整个渲染目标（且因此必须覆盖当前被渲染的相应渲染区块）的8×8渲染区块子区域的基元列表被识别。在本实施方式中，应用于被渲染区块的存储的基元列表通过将对于相关基元列表的指针包括在当最初渲染区块时发送的“新区块”命令中来指示。（当然，其他布置也是可能的）。

渲染器然后前进到渲染讨论的区块。

渲染处理中的第一阶段是基元选择单元29选择将被渲染的基元。为此，基元选择单元29读取被确定为应用于当前渲染的区块的存储的基元列表26，即在本实施方式中，如上面所讨论，被渲染的各个渲染区块排他性的基元列表26、用于包括被渲染区块的2×2渲染区块子区域的基元列表、用于包括被渲染区块的4×4渲染区块子区域的基元列表以及覆盖整个渲染目标的8×8渲染区块子区域的基元列表。基元列表通过基元选择单元29以先进先出的顺序读取，即，使得实际上列表中的第一基元被读取，且然后，一旦发送用于渲染的基元，列表中的第二基元被读取且依此类推。

为了选择将要渲染的下一基元，基元选择单元29确定在用于被渲染区域的每个基元列表中分配给将被渲染的下一基元的索引、比较这些索引且选择最低索引基元为被渲染的下一基元（如上面所讨论，因为基元以升序被基元列表构建单元28索引，即，使得最低编号的基元是用于所需渲染顺序的被渲染的下一基元）。

因而，基元选择单元29将读入用于讨论的单渲染区块子区域的基元列表中下一基元的索引、用于相关2×2渲染区块子区域的基元列表中下一基元的索引、用于适当4×4渲染区块子区域的基元列表中下一基元的索引且依此类推，比较这些索引且选择具有用于下次渲染的最低索引的基元。（基元选择单元29仅需要在任何一次从每个基元列表读取一个基元（下一基元）的索引，因为如上面所讨论，在各个基元列表内，基元已经以正确的渲染顺序列举）。实际上，基元可以被认为在先进先出的基础上从存储的基元列表依次逐个地流传输到基元选择单元。

一旦基元选择单元29选择了将被渲染的基元，它将该基元传递到顶点选择单元31。顶点选择单元31然后从存储在存储器23中的变换的几何形状数据25检索用于讨论的基元的顶点的适当的变换的几何形状数据，且将该数据提供到栅格化单元33。基元然后被栅格化且渲染，且如上面所讨论且如本领域所已知，所得的渲染的基元数据在区块缓冲器35中适当存储。

该处理然后重复，即，基元选择单元29同样读取每个相关基元列表的下一基元的索引、选择具有最低索引的基元且将该基元提供到顶点选择单元31，且依此类推。

该处理对于针对给定渲染区块（被包括在适于区块的基元列表26中）需要渲染的所有基元重复，直到区块的所有基元已经被渲染（且所以区块缓冲器包含用于讨论的区块的所有渲染数据）。如本领域所已知，渲染的区块数据然后被写出（导出）到外部存储器，诸如主存储器（未示出）中的帧缓冲器。

渲染器22然后以相同的方式渲染下一渲染区块且依此类推，直到用于渲染输出的所有独立渲染区块都被渲染（且写入到外部存储器，诸如帧缓冲器）。

一旦用于渲染输出的所有区块被渲染，如本领域所已知，渲染区块的被组合的组则可以作为渲染输出提供到例如用于显示的显示设备。该处理然后针对将生成的下一渲染输出（例如帧）重复，且依此类推。

如上面所讨论，渲染器22还包括基元列表缓存30和顶点数据缓存32。

尽管这些缓存在图2中用于说明目的单独示出，实际上，基元列表和顶点数据可以在图形处理器的通用目的L2缓存中缓存。

基元选择单元29配置成在基元列表缓存30中存储从主存储器23读取的一个或更多基元列表26。尤其是，基元选择单元29偏好从存储器23检索且在基元列表缓存30中存储应用于包含多于一个渲染区块（例如，基元选择单元29知道它将要求后续渲染区块）的子区域的基元列表。这帮助避免由于基元选择单元29必须重复地从存储器23检索它将针对多个渲染区块要求的基元列表导致的延迟和反应延时。

顶点选择单元31可以类似地在顶点数据缓存32中缓存它从存储器23中的变换的几何形状数据25检索的顶点数据，同样尤其是当可以识别顶点数据将再次被基元所要求（例如因为已知针对涵盖多个渲染区块的渲染输出子区域列举基元）。

在本实施方式中，基元列表缓存30和顶点数据缓存32中缓存的数据的存储且尤其是替换基于基元列表和/或顶点数据应用且存储的子区域层级组中的水平，使得与已知例如向单个渲染区块或仅几个渲染区域应用基元列表和顶点数据相比，例如应用于层级的较高水平的基元列表和顶点数据（即因此将用于在将被渲染的输出中的更多渲染区块）偏向于在缓存中被缓存和维持。

因而，例如，当顶点选择单元31从存储器23中的变换的几何形状数据25读取变换的顶点时，将知道该顶点数据被应用到的基元在什么水平被列举（即，基元所来自的基元列表），且可以使用该信息来例如确定是否缓存顶点数据（例如，如上面所讨论，基于是否可能对后续渲染区块重复使用该顶点数据）。

渲染器22处理渲染输出的渲染区块的顺序可以按需选择。然而，在优选实施方式中，以Morton或类似顺序处理区块，因为这例如促进渲染器22中基元列表和顶点数据的更有效缓存。

尽管上面尤其参考了针对渲染目标的子区域准备基元列表描述了本实施方式，还可以且实际上优选地存储可以以类似方式在子区域的基础上使用的其他数据。这种数据例如可以包含渲染设置、区块命令、剪切参数等。如果例如这种命令用于每个渲染区块以在应用于所有渲染区块的列表中布置命令，或备选地如果命令仅应用于少数渲染区块以在层级的较低水平存储命令，则将是有利的。优选地，该数据还存储在针对每个渲染目标子区域准备的相应基元列表中或与之相关，适当时且最优选地以上面针对基元讨论的类似方式索引。

类似地，尽管上面参考其中渲染目标是方形的情形描述了本实施方式，本实施方式可以等同地应用于非方形、例如矩形渲染目标。在这种情况中，子区域将仍涉及方形渲染区块组，但是允许覆盖不存在的渲染区块（即实际上超出渲染目标的边缘）。

图7说明这种情况且示出渲染目标100，该渲染目标100大小为3×8个渲染区块且被4组渲染目标子区域叠加：包含每个对应于单渲染区块的3×8子区域的第一组101、包含大小均为2×2渲染区块的2×4子区域的第二组子区域102、包含大小均为4×4渲染区块的两个子区域的第三组子区域103以及最后包含大小为8×8渲染区块的单个子区域的子区域“最高级”水平组104。可以看出，使用的较大面积的子区域组超出渲染目标100的边缘（且所以涵盖不存在的渲染区块）。

还可以例如修改与列举（装箱）基元相关的成本以考虑已知随时间将遇到的写入和/或读取（或其他成本）中的变化。例如，在基元列表处理使用其写入和/或读取成本可以在基元列表中列举基元时变化的编码方法的情形，诸如其中针对给定列表（箱）列举初始基元的基于增量（差异）的压缩方案，将比向该列表（箱）写入稍后基元更昂贵（更多的字节需要被编码）（因为增量压缩方案将意味着将需要较少的字节来在列表中写入稍后的基元），然后与针对给定子区域组（且优选地其中每一组）列举基元相关的成本应当设置为比初始创建基元列表时高（以考虑当首次写入列表（箱）时写入成本的临时增加），但是一旦列表已经创建且包含基元，则减小。因而，一旦用于讨论的子区域组的列表（箱）被创建且存储（例如包含（至少）一个基元），例如在给定层级水平用于基元的写入成本可以降低。

类似地，例如用于给定子区域组的写入成本在重写使用基于增量的压缩方案时并不“开放”（针对基元列表构建单元缓存）的基元列表时临时增加，以考虑这一事实：重写不被缓存（已经使用）的列表的成本可能高于写入到已经缓存的列表的成本，例如因为如果基元列表不被缓存，它可能必须重读原先的数据项以计算将要使用的新增量（差异），或系统在该事件中返回到写入启动时的非压缩数据。

本领域技术人员应当意识到，本实施方式（以及本发明）可以按需在任意基于区块的渲染系统中实施。本实施方式以及本发明的各种组件和功能可以类似地按需地且使用本领域已知的任意适当技术实施。

从上文可以看出，本发明在其优选实施方式中至少提供用于基于区块的渲染系统的改善的基元列举和分类布置，其尤其促进存储器带宽的更有效使用且可以减小用于基元列举（装箱）处理的反映延迟等。

在本发明的优选实施方式中，这通过考虑不同的可能基元列举布置的相对成本且然后基于成本评价选择将要使用的基元列举布置来完成。

优选实施方式使用自适应成本函数，该自适应成本函数在使用中可以基于在使用中实际体验的基元列举处理的成本分析来修改。这则允许系统例如在渲染内容和存储器子系统负载变化时实时地重新优化。

Claims (22)

1.一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的方法，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标区的至少两个不同的子区域组准备指示将被处理的基元的系统基元列表，所述渲染目标区的所述两个不同的子区域组中的至少一个子区域组包括比单个渲染区块大的所述渲染目标区的子区域，该方法包括以下步骤：

针对将被渲染的基元：

确定所述基元需要被列举以渲染所述基元的所述渲染目标区的所述至少两个不同的子区域组中的至少两个子区域组的子区域；

使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区子区域的基元列表中列举所述基元的成本；以及

基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区子区域的一些子区域以列举所述基元，且在这些所选子区域的基元列表中包括所述基元。

2.根据权利要求1所述的方法，该方法包括以下步骤：

针对将被渲染的基元：

确定用于渲染所述基元的两个或更多备选基元列举解决方案；

使用成本函数确定这些备选基元列举解决方案中的每一个的成本；

基于所述成本函数评价来选择所确定的备选基元列举解决方案中的一个；以及

在针对所选的基元列举方案已经确定所述基元将被列举的所述渲染目标区子区域的基元列表中包括所述基元。

3.根据权利要求2所述的方法，其中，所考虑的基元列举解决方案每一个均对应于针对各个不同的渲染目标子区域组来列举所述基元。

4.根据权利要求2或3所述的方法，其中，所述成本函数使用存储的预定成本值，所述预定成本值然后将乘以针对讨论中的基元列举解决方案所述基元将在其中列举的基元列表的数目，以确定用于被考虑的每个基元列举解决方案的成本。

5.根据前述权利要求中任一项所述的方法，其中，可以准备基元列表的渲染目标子区域组布置为使得所述渲染目标被多层的子区域组叠加，每一层是一个子区域组，且具有与其它层大小不同的可以准备基元列表的子区域。

6.根据前述权利要求中任一项所述的方法，其中，所述成本函数使用针对每个不同渲染目标子区域大小的预定总成本且然后对用于被考虑的每个基元列表的这些成本求和。

7.根据权利要求6所述的方法，其中，所述针对每个不同渲染目标子区域大小的预定总成本可以在使用中修改。

8.根据前述权利要求中任一项所述的方法，所述方法包括：基于从和向在准备和使用所述基元列表时遇到的所述基元列表读取和/或写入所述基元的成本而调节使用的所述成本函数的操作。

9.根据权利要求8所述的方法，所述方法包括：通过更新在所述成本函数中使用的成本值来调节成本函数操作。

10.根据权利要求8或9所述的方法，所述方法包括：通过针对渲染目标子区域组中的一个或更多个子区域组启用或禁用基元的列举来调节所述成本函数操作。

11.一种在基于区块的图形处理系统中分类图形基元以用于渲染到列表中的设备，所述列表表达将生成的渲染目标的不同区，其中渲染目标被分割成用于渲染目的的多个渲染区块，且其中可以针对所述渲染目标区的至少两个不同的子区域组准备指示将被处理的基元的系统基元列表，所述渲染目标区的所述两个不同的子区域组中的至少一个子区域组包含比单个渲染区块大的所述渲染目标区的子区域，所述设备包括被配置成执行以下步骤的处理电路：

针对将被渲染的基元，确定所述基元需要被列举以渲染所述基元的所述渲染目标区的所述至少两个不同的子区域组中的至少两个子区域组的子区域；

使用成本函数来评价在用于已经确定所述基元需要被列举的所述渲染目标区子区域的基元列表中列举所述基元的成本；以及

基于成本函数评价而选择已经确定所述基元需要被列举以渲染所述基元的所述渲染目标区子区域中的一些子区域以列举所述基元，且在这些所选子区域的基元列表中包括所述基元。

12.根据权利要求11所述的设备，所述设备包括被配置成执行以下步骤的处理电路：

针对将被渲染的基元：

确定用于渲染所述基元的两个或更多备选基元列举解决方案；

使用成本函数确定这些备选基元列举解决方案中的每一个的成本；

基于所述成本函数评价来选择所确定的备选基元列举解决方案中的一个；以及

在针对所选的基元列举方案已经确定所述基元将被列举的所述渲染目标区子区域的基元列表中包括所述基元。

13.根据权利要求12所述的设备，其中，所考虑的基元列举解决方案每一个均对应于针对各个不同的渲染目标子区域组来列举所述基元。

14.根据权利要求12或13所述的设备，其中，所述成本函数使用存储的预定成本值，所述预定成本值然后将乘以针对讨论中的基元列举解决方案所述基元将在其中列举的基元列表的数目，以确定用于被考虑的每个基元列举解决方案的成本。

15.根据权利要求11至14中任一项所述的设备，其中，可以准备基元列表的渲染目标子区域组布置为使得所述渲染目标被多层的子区域组叠加，每一层是一个子区域组，且具有与其它层大小不同的可以准备基元列表的子区域。

16.根据权利要求11至15中任一项所述的设备，其中，所述成本函数使用针对每个不同渲染目标子区域大小的预定总成本且然后对用于被考虑的每个基元列表的这些成本求和。

17.根据权利要求16所述的设备，其中，所述针对每个不同渲染目标子区域大小的预定总成本可以在使用中修改。

18.根据权利要求11至17中任一项所述的设备，所述设备包括被配置成执行以下步骤的处理电路：基于从和向在准备和使用所述基元列表时遇到的所述基元列表读取和/或写入所述基元的成本而调节使用的所述成本函数的操作。

19.根据权利要求18所述的设备，所述设备包括：通过更新在所述成本函数中使用的成本值来调节成本函数操作。

20.根据权利要求18或19所述的设备，所述设备包括：通过针对渲染目标子区域组中的一个或更多个子区域组启用或禁用基元的列举来调节所述成本函数操作。

21.一种图形处理器，所述图形处理器包括根据权利要求11至20中任一项所述的设备。

22.一种包括计算机软件代码的计算机程序，当所述程序在数字处理装置上运行时，所述计算机软件代码用于执行根据权利要求1至10中任一项所述的方法。

Images