边学边翻译，督促自己不能落下，同时也留点记忆
某些数据结构在图形应用程序中反复出现，可能是因为它们处理了基本的基本思想，如曲面、空间和场景结构。本章讨论最常见和最有用的几种基本和不相关的数据结构类别：网格结构、空间数据结构、场景图和平铺多维数组。 对于网格，我们讨论了用于存储静态网格和将网格传输到图形API的基本存储方案。我们还讨论了wingededge数据结构（Baumgart，1974）和相关的半边结构，它们对于管理细分发生变化的模型（如细分或模型简化）非常有用。虽然这些方法可以推广到任意多边形网格，但我们在这里只关注三角形网格的简单情况。 接下来，介绍了场景图的数据结构。这种数据结构的各种形式在图形应用程序中无处不在，因为它们在管理对象和转换时非常有用。所有新的图形API都具有支持场景图的特性。 对于空间数据结构，我们讨论了在三维空间边界体层次、层次空间细分和均匀空间细分中组织模型的三种方法，以及使用层次空间细分（BSP树）去除隐藏曲面的方法。同样的方法也用于其他目的，包括几何体剔除和碰撞检测。 最后，介绍了分片多维数组。这种结构最初是为了帮助在需要从磁盘交换图形数据的应用程序中提高分页性能而开发的，现在对于计算机上的内存位置至关重要，无论数组是否适合主内存。
大多数真实世界的模型都由具有共享顶点的三角形复合体组成。这些通常被称为三角网格、三角网格或三角不规则网络（TIN），有效地处理它们对许多图形程序的性能至关重要。效率的重要性取决于应用程序。网格存储在磁盘和内存中，我们希望将消耗的存储量降至最低。当网格通过网络传输或从CPU传输到图形系统时，它们会消耗带宽，带宽通常比存储更宝贵。在对网格执行操作的应用程序中，除了简单地存储和绘制网格（如细分、网格编辑、网格压缩或其他操作）外，有效地访问邻接信息至关重要。 三角形网格通常用于表示曲面，因此网格不仅仅是不相关三角形的集合，而是通过共享顶点和边相互连接以形成单个连续曲面的三角形网络。这是关于网格的一个重要观点：与相同数量的不相关三角形的集合相比，可以更有效地处理网格。 三角形网格所需的最小信息是一组三角形（三个顶点）及其顶点的位置（在三维空间中）。但许多程序需要在顶点、边或面上存储额外的数据，用于支持纹理映射、着色、动画和其他操作。顶点数据是最常见的：每个顶点都可以具有材质参数、纹理坐标、辐照度以及任何值在整个曲面上发生变化的参数。然后在每个三角形上对这些参数进行线性插值，以定义网格整个曲面上的连续函数。但是，能够存储每条边或每个面的数据有时也很重要。
网格类似于曲面的想法可以形式化为网格拓扑上的约束，即三角形连接在一起的方式，而不考虑顶点位置。许多算法只能在具有可预测连接性的网格上工作，或者更容易实现。对网格拓扑的最简单和最严格的要求是曲面为流形。流形网格是“水密的”——它没有间隙，将曲面内部的空间与外部的空间分隔开。它在网格上的任何位置看起来都像一个曲面。 流形一词来自拓扑学的数学领域：粗略地说，流形（特别是二维流形，或2流形）是一个曲面，其中任何点周围的一个小邻域都可以平滑为一个平面。反例最清楚地解释了这个想法：如果网格上的一条边有三个三角形与其相连，则边上一个点的邻域与其中一个三角形内部一个点的邻域不同，因为它有一个额外的“鳍”伸出（图12.1）。如果边上正好附着了两个三角形，则边上的点与内部的点一样具有邻域，只是中间有一个折痕。类似地，如果共享一个顶点的三角形处于图12.2中左侧的配置中，则邻域就像两块在中心粘在一起的曲面，如果不将其折叠，就无法将其展平。右侧显示的具有更简单邻域的顶点很好。 许多算法都假设网格是流形的，如果将一个格式不正确的网格作为输入，则最好验证此属性以防止崩溃或无限循环。此验证归结为检查所有边是否为流形，以及通过验证以下条件检查所有顶点是否为流形：
- 每条边正好由两个三角形共享。
- 每个顶点周围都有一个完整的三角形环。 图12.1说明了一条边如何通过太多三角形而无法通过第一次测试，图12.2说明了一个顶点如何通过连接两个单独的三角形环而无法通过第二次测试。 流形网格很方便，但有时需要允许网格具有边或边界。这样的网格不是流形——边界上的一个点有一个在一侧被切断的邻域。它们不一定是无懈可击的。然而，我们可以将流形网格的要求放宽到具有边界的流形网格的要求，而不会给大多数网格处理算法带来问题。放宽的条件包括：
- 每条边由一个或两个三角形使用。
- 每个顶点都连接到一个边连接的三角形集。 图12.3说明了这些条件：从左到右，有一条边上有一个三角形，一个顶点的相邻三角形位于一个边连接集中，一个顶点上有两个不连接的三角形集。 最后，在许多应用中，能够区分曲面的“正面”或“外部”与“背面”或“内部”非常重要，这就是曲面的方向。对于单个三角形，我们根据顶点列出的顺序定义方向：正面是三角形的三个顶点按逆时针顺序排列的一侧。如果一个连接的网格的所有三角形都有一直的朝向，则该网格的方向一致；如果且仅当每对相邻三角形的方向一致，则该情况成立。 在一对方向一致的三角形中，两个共享顶点以相反的顺序出现在两个三角形的顶点列表中（图12.4）。重要的是方向的一致性，一些系统使用顺时针而不是逆时针顺序定义正面。 任何具有非流形边的网格都无法一致定向。但网格也可能是一个有效的有边界的流形（甚至是流形），但却没有一致的方法来确定三角形的方向，因为它们不是可定向曲面。图12.5所示的M–obius带就是一个例子。然而，这在实践中很少成为问题。
一个简单的三角形网格如图12.6所示。您可以将这三个三角形存储为独立的实体，每个实体的形式如下：
Triangle{
vector3 vectexPosition[3]
}
这将导致存储顶点b三次，其他顶点各两次，总共存储九个点（三个三角形中每个三角形有三个顶点）。或者，您可以安排共享公共顶点并仅存储四个，从而形成共享顶点网格。从逻辑上讲，此数据结构具有指向包含顶点数据的顶点的三角形：
Triangle{
Vertex v[3]
}
Vertex{
vector3 position // or other vertex data
}
请注意，数组v是指向顶点对象的引用或者指针，顶点不包含在三角形中。 在实现中，顶点和三角形通常存储在数组中，三角形到顶点的引用通过存储数组索引来处理：
IndexedMesh {
int tInd[nt][3]
vector3 verts[nv]
}
第i个三角形的第k个顶点的索引位于tInd\left [ i \right ] \left [ k \right ]tInd[i][k]中，该顶点的位置存储在顶点数组的相应行中；有关示例，请参见图12.8。这种存储共享顶点网格的方法是索引三角形网格。 单独的三角形或共享的顶点都能很好地工作。共享顶点是否有空间优势？单独的三角形或共享的顶点都能很好地工作。共享顶点是否有空间优势？如果我们的网格具有$n_{v}$顶点和$n_{t}$三角形，并且假设浮点数、指针和整数的数据都需要相同的存储（一个可疑的假设），则空间要求如下：
- 三角形：每个三角形三个矢量，共$9n_{t}$存储单元；
- 索引网格：每个顶点一个向量，每个三角形三个整数，共$3n_{v}+3n_{t}$存储单元； 相对存储需求取决于$n_{t}$与$n_{v}$的比率。 根据经验，大型网格的每个顶点都连接到大约六个三角形（尽管在极端情况下可能有任意数量）。由于每个三角形连接到三个顶点，这意味着在一个大网格中，三角形的数量通常是顶点的两倍：$n_{t}\approx 2n_{v}$。通过这种替换，我们可以得出结论，三角形结构的存储需求为$18n_{v}$，索引网格的存储需求为$9n_{v}$。使用共享顶点将存储需求减少约两倍；对于大多数实现来说，这似乎在实践中是成立的。
索引网格是三角形网格最常见的内存表示形式，因为它们实现了简单性、方便性和紧凑性的良好平衡。它们还通常用于通过网络以及在应用程序和图形管道之间传输网格。在需要更紧凑的应用程序中，三角形顶点索引（在索引网格中，仅在顶点位置占据三分之二的空间）可以使用三角形条和三角形扇更有效地表示。 三角形风扇如图12.9所示。在索引网格中，三角形数组将包含[(0,1,2),(0,2,3),(0,3,4),(0,4,5)]。我们存储了12个顶点索引，尽管只有6个不同的顶点。在三角形风扇中，所有三角形共享一个公共顶点，其他顶点生成一组三角形，就像可折叠风扇的叶片一样。图中的扇形可以用序列[0,1,2,3,4,5]来指定：第一个顶点建立中心，随后每对相邻顶点（1-2=,2-3=等）创建一个三角形。 三角形带是一个类似的概念，但它适用于更大范围的网格。在这里，顶点在线性条带中交替添加，如图12.10所示。图中的三角形条带可以由序列[0 1 2 3 4 5 6 7]指定，并且三个相邻顶点（0-1-2、1-2-3等）的每个子序列创建一个三角形。为了保持方向一致，其他三角形的顺序都需要颠倒。在本例中，这将导致三角形(0，1，2)，(2，1，3)，(2，3，4)，(4，3，5)等。对于引入的每个新顶点，将忘记最旧的顶点，并交换剩余两个顶点的顺序。有关更大的示例，请参见图12.11。 在条带和扇形中，n+2n+2个顶点足以描述nn个三角形，这比标准索引网格所需的3n3n个顶点节省了很多。如果程序是顶点绑定的，长三角形条带将节省大约三倍的时间。 三角形条带似乎只有在条带很长的情况下才有用，但即使相对较短的条带也已经获得了大部分好处。存储空间的节省（仅针对顶点索引）如下所示： 因此，事实上，随着长条带的增长，回报率会迅速下降。因此，即使对于非结构化网格，也值得使用一些贪婪算法将其聚集成短条。
索引网格、条带和扇都是静态网格的良好、紧凑的表示形式。但是，它们不允许修改网格。为了高效地编辑网格，需要更复杂的数据结构来高效地回答以下查询：
- 给定一个三角形，三个相邻的三角形是什么？
- 给定一条边，哪两个三角形共享它？
- 给定一个顶点，哪些面共享该顶点？
- 给定一个顶点，哪些边共享该顶点？ 三角形网格、多边形网格和带孔多边形网格有许多数据结构（参考资料请参见本章末尾的注释）。在许多应用中，网格非常大，因此有效的表示非常关键。 最直接的实现（尽管过于臃肿）是有三种类型：顶点、边和三角形，并直接存储所有关系：
Triangle{
Vertex v[3]
Edge e[3]
}
Edge{
Vertex v[2]
Triangle t[2]
}
Vertex{
Triangle t[]
Edge e[]
}
这让我们可以直接查找上述连通性问题的答案，但由于这些信息都是相互关联的，因此存储的信息比实际需要的多。此外，在顶点中存储连接性有助于可变长度的数据结构（因为顶点可以有任意数量的邻居），而这些结构的实现效率通常较低。与其承诺显式存储所有这些关系，不如定义一个类接口来回答这些问题，在这个类接口后面可以隐藏一个更高效的数据结构。事实证明，我们只能存储部分连接，并在需要时高效地恢复其他信息。 Edge和Triangle类中的固定大小数组表明，在其中存储连接信息将更有效。事实上，对于多边形网格，多边形具有任意数量的边和顶点，只有边具有固定大小的连接信息，这导致许多传统网格数据结构基于边。但对于仅三角形网格，在（数量较少的）面中存储连接性很有吸引力。 一个好的网格数据结构应该合理紧凑，并允许有效地回答所有邻接查询。高效意味着恒定的时间：查找邻居的时间不应取决于网格的大小。我们将研究三种网格数据结构，一种基于三角形，另一种基于边。
我们可以创建一个基于三角面的紧凑网格数据结构，方法是在每个三角形中存储三个相邻三角形的指针，以及在每个顶点存储任意一个相邻三角形的指针。
Triangle{
Triangle nbr[3];
Vertex v[3];
}
Vertex{
// ...per-vertex data...
Triangle t; // any adjacent tri
}
在三角面数组nbrnbr中，第kk点的相邻三角形共享顶点kk和k+1k+1。这种数据结构称为为三角面邻接结构。此数据结构中网格可以通过标准的索引数组以及两个额外的数组来进行表示，一个数组存储每个三角面的三个领域，另一个数组存储每个顶点的单个领域三角面（参见图12.13的示例）。
Mesh{
// ...per-vertex data ...
int tInd[nt][3]; // veretx index
int tNbr[nt][3]; // indices of neighbor triangles
int vTri[nv]; // index of any adjacent triangle
}
显而易见，可以直接在数据结构中找到相邻的三角形和三角形的顶点，而且通过仔细使用该三角形邻接信息，也可以在恒定时间内查询有关顶点的连接性。办法是从一个三角面移动到另一个三角面，只访问与相关顶点相邻的三角面。如果三角形tt的第kk个顶点是顶点v，则三角面t.nbr[k]t.nbr[k]是沿顺时针方向环绕顶点vv的下一个三角面。我们可以使用以下算法遍历与给定顶点相邻的所有三角形：
TrianglesOfVertex(v){
t = v.t;
do{
find i such that (t.v[i] == v)
t = t.nbr[i]
}while(t != v.t)
}
此操作以恒定的时间查找每个后续三角形，即使需要搜索以查找每个三角形顶点列表中中心顶点的位置，但顶点列表的大小是恒定的，因此搜索需要恒定的时间。然而，这种搜索很尴尬，需要额外的分支。 稍加改进就可以避免这些搜索。问题是，一旦我们跟随一个指针从一个三角形到下一个三角形，我们就不知道是从哪条路来的：我们必须搜索三角形的顶点，找到回上一个三角形的顶点。为了解决这个问题，我们不需要存储指向相邻三角形的指针，而是可以通过存储带有指针的索引来存储指向这些三角形特定边的指针：
Triangle{
Edge nbr[3];
Vertex v[3];
}
Edge{ // the i-th edge of triangle t
Triangle t;
int i; // in {0,1,2}
}
Vertex{
// ... per-vertex data ...
Edge e; // any edge leaving vertex
}
在上述结构中，通过从三角形索引tt借用两个存储位来存储边缘索引i，从而使总存储需求保持不变。 在这种数据结构中，三角形的邻接数组告诉我们哪个相邻三角形的边与该三角形的三条边共享。有了这些额外的信息，我们总是知道在哪里找到原始三角形，这导致了数据结构的不变量：对于任何三角形tt的任何第jj条边， $$ t.nbr[j].t.nbr[t.nbr[j].i].t == t $$ 知道我们通过哪条边进入，可以让我们立即知道要通过哪条边，以便继续围绕顶点进行遍历，从而得到一个简化的算法：
TrianglesOfVertex(v){
{t,i} == v.e;
do{
{t,i} = t.nbr[i];
i = (i+1) mod 3;
}while(t != v.e.t);
}
三角形邻居结构非常紧凑。对于只有顶点位置的网格，我们每个顶点存储四个数字（三个坐标和一条边），每个面存储六个数字（三个顶点索引和三条边），总共$4n_{v}+6n_{t}\approx 16n_{v}$，每个顶点的存储容量为$16n_{v}$，而基本索引网格的存储容量为$9n_{v}$。 此处介绍的三角形邻域结构仅适用于流形网格，因为它取决于返回起始三角形以终止顶点邻域的遍历，这不会发生在没有完整三角形循环的边界顶点上。然而，通过引入合适的哨兵值（例如−1） 对于边界三角形的邻域，请注意边界顶点指向最逆时针的邻域三角形，而不是任何任意三角形。
翼边数据结构是一种广泛使用的网格数据结构，它在边而不是面上存储连通性信息。如图12.14和12.15所示，这种数据结构使Edge成为数据结构的一等公民。 在翼边数据结构中，每条边存储指向它连接的两个顶点（头部和尾部顶点）、它所属的两个面（左侧和右侧面）的指针，最重要的是，指向其左侧和右侧面的逆时针遍历中的下一条边和前一条边（图12.16）。每个顶点和面还存储指向与其相连的单个任意边的指针：
Edge{
Edge lprev,lnext,rprev,rnext;
Vertex head,tail;
Face left,right;
}
Face{
// ... per-face data...
Edge e; // any adjacent edge
}
Vertex{
// ... per-vertex data ...
Edge e; // any adjacent edge
}
翼边数据结构支持对面或顶点的边进行恒定时间访问，从这些边可以找到相邻的顶点或面：
EdgesOfVertex(v){
e = v.e;
do{
if (e.tail == v)
e = e.lprev;
else
e = e.rprev;
}while(e != v.e)
}
EdgesOfFace(f){
e = f.e;
do{
if (e.left = f)
e = e.lnext;
else
e = e.rnext;
}while (e != f.e);
}
这些相同的算法和数据结构在不是三角形的多边形网格中也同样有效；这是基于边缘的结构的一个重要优点。 与任何数据结构一样，翼边数据结构也会进行各种时间与空间上的权衡。例如，我们可以删除prev引用。这使得顺时针绕面或逆时针绕顶点移动更加困难，但当我们需要知道前一条边时，我们总可以沿着圆中的后续边移动，直到回到原始边。这样可以节省空间，但会使某些操作变慢。（有关这些权衡的更多信息，请参见章节注释）。
翼边结构非常优雅，但它还有一个尴尬之处，那就是在移动到下一个边缘之前，需要不断检查边缘的方向。这个检查直接类似于我们在三角形邻域结构的基本版本中看到的搜索：我们正在寻找我们是从头部还是从尾部进入当前边缘。解决方案也几乎无法区分：我们不是存储每条边的数据，而是存储每条半边的数据。共享一条边的两个三角形各有一条半边，两条半边的方向相反，每个半边的方向与自己的三角形一致。 通常存储在边中的数据在两条半边之间分割。每个半边都指向其边上的面和其头部的顶点，并且每个半边都包含其面的边指针。它还指向边另一侧的邻居，从中可以找到另一半的信息。与带翼边一样，半边可以包含指向其面周围的上半边和下半边的指针，或者仅指向下半边。我们将展示使用单个指针的示例。
HEdge{
HEdge pair,next;
Vertex v;
Face f;
}
Face{
// ... per-face data ...
HEdge h; // any h-edge of this face
}
Vertex{
// ... per-vertex data
HEdge h; // any h-edge pointing toward this vertex
}
遍历半边结构就像遍历有翼边结构，只是我们不再需要检查方向，我们按照对指针访问对面的边。
EdgesOfVertex(v){
h = v.h;
do{
h = h.pair.next;
} while (h != v.h);
}
EdgesOfFace(f){
h = f.h;
do{
h = h.next;
} while (h != f.h);
}
这里的顶点遍历是顺时针的，这是必要的，因为结构中省略了prevprev指针。 由于半边通常成对分配（至少在没有边界的网格中），许多实现可以取消成对指针。例如，在基于数组索引的实现中（如图12.18所示），可以对数组进行排列，使偶数边ii始终与边i+1i+1配对，奇数边jj始终与边j-1j−1配对。 除了本章所示的简单遍历算法外，所有这三种网格拓扑结构都可以支持各种“网格手术”操作，例如分割或折叠顶点、交换边、添加或删除三角形等。
###12.2 场景图
三角形网格管理构成场景中对象的三角形集合，但图形应用程序中的另一个普遍问题是将对象排列在所需的位置。正如我们在第7章中看到的，这是通过转换来完成的，但是复杂的场景可以包含大量的转换，并且很好地组织它们可以使场景更容易操作。大多数场景都属于分层结构，并且可以使用场景图根据这个层次结构来管理转换。
为了激发场景图数据结构，我们将使用如图12.19所示的铰链摆。考虑一下我们如何画钟摆的顶部:
$$
M_1=rotate(\theta)\
M_2=translate(p) \
M_3=M_2M_1\
Apply~~ M_3 to inupper~~ pendulum
$$
底部比较复杂，但我们可以利用它在局部坐标系的b点上附在上摆的底部。首先，我们旋转较低的钟摆，使其与初始位置成o角。然后，我们移动它，使它的顶部铰链在点b。现在它在上摆的局部坐标中的适当位置，然后它可以沿着那个坐标系移动。下摆的复合变换是
$$
M_a=rotate(\theta)\
M_b=translate(p) \
M_c=M_bM_a\
M_d=M_3M_c\
Apply~~ M_dall pointsto inall pointslower pendulum
$$
因此，我们不仅看到下摆存在于它自己的局部坐标系中，而且坐标系统本身也随着上摆的坐标系移动。
我们可以在数据结构中对钟摆进行编码，使这些坐标系问题的管理更容易，如图12.20所示。适用于一个对象的适当矩阵只是链中所有矩阵的乘积数据结构根的对象。例如，考虑一个轮渡模型，其中有一辆汽车可以在轮渡的甲板上自由移动，每个车轮都相对于汽车移动，如图12.21所示。
和钟摆一样，每个物体都应该由从根到物体的路径上的矩阵的乘积进行变换:
- ferry 变换使用$M_0$;
- 车身改造利用$M_0M_1$进行;
- 左轮变换使用$M_0M_1M_2$进行:
- 左轮变换使用$M_0M_1M_3$。
栅格化的有效实现可以通过使用矩阵堆栈实现，矩阵堆栈是许多api支持的数据结构。使用推和弹出操作操作矩阵堆栈，从矩阵乘积的右侧添加和删除矩阵。例如,调用 $$ push(M_0)\ push(M_1)\ push(M_2)\ $$ 创建活动矩阵$M = M_0M_1M_2$。随后调用pop()剥离最后添加的矩阵，使活动矩阵变为M = MoM1。结合矩阵堆栈和场景图的递归遍历，我们得到 ~~ function traverse(node) push(Mlocal) dwaw object using composite matrix from stack traverse(left child) traverse(right child) pop() ~~ 场景图有许多变体，但都遵循上述基本思想。
射线跟踪的一个优雅的特性是，它允许非常自然的转换应用，而不改变几何图形的表示。基本例化的思想是在显示对象之前通过转换矩阵扭曲对象上的所有点。例如，如果我们分别用z和y的比例因子(2,1)变换单位圆(在2D中)，然后旋转它45°，并在z方向上移动一个单位，结果是一个椭圆，偏心为2，沿着(r = -y)方向以(0,1)为中心的长轴(图12.22)。使实体成为“实例”的关键是我们存储圆和复合变换矩阵。因此，椭圆的显式构造被保留为呈现时的未来操作。 在射线追踪中实例化的优点是我们可以选择做交集的空间。如果基对象是由一组点组成的，其中一个点是p，那么转换后的对象是由矩阵M转换后的点集合组成的，其中示例点被转换为Mp。如果我们有一条射线atb它与经过变换的物体相交，我们可以用反变换的射线与未经过变换的物体相交(图12.23)。在未转换的空间中进行计算有两个潜在的优势(即图12.23的右侧):
- 未转换的对象可能有一个更简单的交叉例程，例如，一个球体对一个椭球体。
- 许多经过转换的对象可以共享同一个未经过转换的对象，从而减少存储，例如，汽车的交通堵塞，其中单个汽车只是几个基本(未经过转换)模型的转换。 如7.2.2节所述，表面法向量变换不同。记住这一点，并使用图12.23所示的概念，我们可以确定射线和由矩阵m转换的对象的交集。如果我们创建一个类型为surface的实例类，我们需要创建一个hit函数:
instance::hit(ray a + tb，real to，real t1, hit-record rec)
ray r' = M-'a +tM-lb
If (base-object->hit(r'， to, ti, rec))then
Trec.n = (m - 1)rec.n
return true
else
return false
关于这个函数的一个优雅的地方是，参数rec.t不需要更改，因为它在任何空间中都是相同的。还要注意，我们不需要计算或存储矩阵M。 这就引出了一个非常重要的问题:射线方向b不能被限制为单位长度的向量，否则以上的基础结构都不起作用。由于这个原因，不将射线方向限制为单位向量是有用的。
关在许多(如果不是全部)图形应用程序中，快速定位特定空间区域中的几何对象的能力非常重要。射线追踪器需要找到与射线相交的物体;交互式应用程序在一个环境中导航需要找到从任何给定的视点可见的对象;游戏和物理模拟需要检测物体碰撞的时间和地点。所有这些需求都可以通过各种空间数据结构来支持，这些空间数据结构旨在组织空间中的对象，以便有效地查找它们。 关在本节中，我们将讨论三种空间数据结构的一般类别的示例。将对象分组成层次结构的结构是对象划分方案:对象被划分为不相交的组，但组最终可能在空间上重叠。将空间划分为不相交区域的结构是空间分区方案:空间被划分为单独的分区，但一个对象可能必须与多个分区相交。空间划分方案可以是规则的，即将空间划分为形状一致的块;也可以是不规则的，即自适应地将空间划分为不规则的块，其中有更多更小的物体。 关在讨论这些结构时，我们将使用光线跟踪作为主要动机，尽管它们也都可以用于视图剔除或碰撞检测。在第4章，所有对象在检查交叉时循环。对于N个对象，这是一个O(N)线性搜索，因此对于大型场景来说比较慢。与大多数搜索问题一样，光线与物体的交集可以使用“分治”技术在次线性时间内计算，前提是我们可以创建一个有序的数据结构作为预处理。有很多技术可以做到这一点。 关本节将详细讨论其中的三种技术:边界容量层次(Rubin & Whitted, 1980;一点点,1980;Goldsmith & Salmon, 1987)，统一空间细分(Cleary, Wyvill, Birtwistle， & Vatti, 1983;藤,田中，岩田，1986;Amanatides & Woo, 1987)和二进制空间划分(Glassner, 1984;詹森,1986;Havran, 2000)。前两种策略的一个例子如图12.24所示。
关大多数相交-加速方案的一个关键操作是计算射线与边界框的相交(图12.25)。这与传统的交叉测试不同，因为我们不需要知道射线击中盒子的位置;我们只需要知道它是否击中盒子 关为了建立射线盒交点算法，我们首先考虑方向向量具有正x和y分量的2D射线。之后我们可以将其推广到任意3D射线上。2D边界框由两条水平线和两条垂直线定义: $$ x = x_{min}\ x = x_{max}\ y = y_{min}\ y = y_{max} $$ 以这些线为界的点可以用区间符号表示: $$ (x,y) \in [x_{min},x_{max}]\times [y_{min},y_{max}] $$ 如图12.26所示，可以用这些间隔来表示交集检验。首先，我们计算射线到达直线r = Tmin处的射线参数 $$ t_{xmin} = \frac{x_{min}-x_e}{x_d} $$ 然后我们对txmax、tymin和tymax进行类似的计算。当且仅当区间[txmin, txmax]和[tymin, tymax]重叠时，射线才会击中方框;也就是说，它们的交集是非空的。在伪代码中，这种算法是
xmin = (Tmin - Te)/rd
txmax = (xmax − xe)/xd
tymin = (ymin − ye)/yd
tymax = (ymax − ye)/yd
if (txmin > tymax) or (tymin > txmax) then
return false
else
return true
if语句可能看起来不明显。要了解它的逻辑，请注意，如果第一个区间完全位于第二个区间的右边或左边，则没有重叠。 我们必须解决的第一件事是当xd或yd为负数时的情况。如果xd是负的，那么射线会在到达xmin之前到达xmax。因此，计算txmin和txmax的代码扩展为
if (x_d ≥ 0) then
txmin = (xmin − xe)/xd
txmax = (xmax − xe)/xd
else
txmin = (xmax − xe)/xd
txmax = (xmin − xe)/xd
必须对y的情况进行类似的代码展开。一个主要的问题是，水平和垂直射线的yd和xd值分别为零。这将导致被0除，这可能是一个问题。然而，在直接解决这个问题之前，我们要检查IEEE浮点计算是否为我们优雅地处理了这些情况。回顾1.5节中关于除零的规则:对于任何正实数a $$ +a/0=+\infty -a/0=-\infty $$ 考虑一条垂直射线的情况，其中xd = 0, yd > 0。我们可以计算 $$ t_{xmin}=\frac{x_{min}-x_e}{0}\ t_{xmax}=\frac{x_{max}-x_e}{0} $$ 有三种可能:
- xe ≤ xmin (no hit)
- xmin < xe < xmax (hit);
- xmax ≤ xe (no hit).
对于第一种情况，我们有
$$
t_{xmin}=\frac{Positive
number}{0};\ t_{xmax}=\frac{Positivenumber}{0}. $$ 这将产生区间(txmin, txmin)=(∞，∞)。该间隔将不会与任何间隔重叠，因此将没有命中，正如所希望的那样.对于第二种情况，我们有 $$ t_{xmin}=\frac{Negativenumber}{0};\ t_{xmax}=\frac{Positivenumber}{0}. $$ 这将产生区间(txmin, txmin)=(−∞，∞)，它将与所有的区间重叠，从而产生所需的命中。第三种情况的结果是区间 (−∞，−∞)，没有命中。因为这些箱子能正常工作，所以我们不需要特别检查。通常情况下，IEEE浮点约定是我们的盟友。然而，这种方法仍然有一个问题 考虑代码段: $$ if (x_d \ge 0) ~~then \ tmin = (xmin − xe)/xd \ tmax = (xmax − xe)/xd \ else \ tmin = (xmax − xe)/xd \ tmax = (xmin − xe)/xd \ $$ 当xd =−0时，此代码将崩溃。这可以通过测试xd的互惠来克服(Williams, Barrus, Morley， & Shirley, 2005):
a=1/xd
if (x_d \ge 0) ~~then
tmin =a(xmin − xe)
tmax = a(xmax − xe)
else
tmin = a(xmax − xe)
tmax = a(xmin − xe)
分层边界框的基本思想可以通过在所有对象周围放置一个轴向3D边界框的常见策略看到，如图12.27所示。击中边界框的光线实际上比暴力搜索的计算成本要高，因为与边框的交点测试不是免费的。然而，错过盒子的射线比暴力搜索便宜。通过将对象集划分到一个框中，并在每个分区周围放置一个框，可以使这种边界框具有层次性，如图12.28所示。图12.29所示的层次结构的数据结构可能是一个树，大的边界框位于根，两个较小的边界框分别作为左右子树。它们依次指向一个由三个三角形组成的列表。
if(ray hits root box) then
if(ray hits left subtree box) then
此算法相关的一些观察结果是，两个子树之间没有几何顺序，没有理由不让射线击中两个子树。实际上，这两个子树没有理由不重叠。 这种数据层次结构的一个关键点是，保证一个框绑定层次结构中位于它下面的所有对象，但不保证它们包含空间上与它重叠的所有对象，如图12.29所示。这使得这种几何搜索比对严格有序一维数据的传统二分搜索更复杂。读者可能会注意到几种可能的优化方法。我们推迟优化，直到我们有一个完整的分级算法。 如果我们将树限制为二叉，并要求树中的每个节点都有边界框，那么这个遍历代码自然会扩展。此外,假设所有节点都是树中的叶子，并且包含一个原语，或者它们包含一个或两个子树。 bvh-node类的类型应该是表面的，应当实现surface:: hit。数据应该很简单:
class bvh-node subclass of surface
virtual bool hit(ray e + td, real t0, real t1, hit-record rec)
virtual box bounding-box()
surface-pointer left
surface-pointer right
box bbox
然后可以以面向对象的方式递归调用遍历代码:
function bool bvh-node::hit(ray a + tb, real t0, real t1,hit-record rec)
if (bbox.hitbox(a + tb, t0, t1)) then
hit-record lrec, rrec
left-hit = (left != NULL) and (left → hit(a + tb, t0, t1, lrec))
right-hit = (right != NULL) and (right → hit(a+tb, t0, t1, rrec))
if (left-hit and right-hit) then
if (lrec.t < rrec.t) then
rec = lrec
else
rec = rrec
return true
else if (left-hit) then
rec = lrec
return true
else if (right-hit) then
rec = rrec
return true
else
return false
else
return false
注意，因为左右指向曲面，而不是专门指向bvh节点，所以我们可以让虚函数负责区分内部节点和叶节点;将调用适当的命中函数。注意，如果正确构建了树，我们可以消除left为NULL的检查。如果我们想要消除检查权限为NULL，我们可以替换NULL权限具有冗余的左指针的指针。这将结束左检查两次，但将消除整个树的检查。这样做是否值得，将取决于树形结构的细节 这里有许多为边界卷层次结构构建树的方法。使树二叉，大致平衡，并且兄弟子树的盒子不重叠太多是很方便的。完成这一任务的一种启发式方法是在将曲面分成两个子列表之前，沿着一个轴对其进行排序。如果坐标轴由x = 0 y = 1 z = 2的整数定义，我们有
function bvh-node::create(object-array A, int AXIS)
N = A.length
if (N= 1) then
left = A[0]
right = NULL
bbox = bounding-box(A[0])
else if (N= 2) then
left-node = A[0]
right-node = A[1]
bbox = combine(bounding-box(A[0]), bounding-box(A[1]))
else
sort A by the object center along AXIS
left= new bvh-node(A[0..N/2 − 1], (AXIS +1) mod 3)
right = new bvh-node(A[N/2..N−1], (AXIS +1) mod 3)
bbox = combine(left → bbox, right → bbox)
每次仔细选择AXIS可以提高树的质量。做到这一点的一种方法是选择这样的轴，使两个子树的边界框的体积之和最小化。这一改变与在轴线上旋转相比，对于由同位分布的小物体组成的场景影响不大，但对于表现不佳的场景却有很大帮助。这段代码还可以通过只进行分区而不是完全排序来提高效率。 另一种可能更好的构建树的方法是让子树包含大致相同的空间，而不是相同数量的对象。 为此，我们根据空间对列表进行分区
function bvh-node::create(object-array A, int AXIS)
N = A.length
if (N = 1) then
left = A[0]
right = NULL
bbox = bounding-box(A[0]
else if (N = 2) then
left = A[0]
right = A[1]
bbox = combine(bounding-box(A[0]), bounding-box(A[1]))
else
find the midpoint m of the bounding box of A along AXIS
partition A into lists with lengths k and (N − k) surrounding m
left = new bvh-node(A[0..k], (AXIS +1) mod 3)
right = new bvh-node(A[k + 1..N − 1], (AXIS +1) mod 3)
bbox = combine(left → bbox, right → bbox
尽管这会导致不平衡的树，但它允许轻松地遍历空空间，并且构建成本更低，因为分区比排序更便宜
减少交叉测试的另一种策略是划分空间。这与分层边界卷划分对象的方法有本质的不同:
- 在分层边界卷中，每个对象属于两个兄弟节点中的一个，而空间中的一个点可能在两个兄弟节点中。
- 在空间细分中，空间中的每个点只属于一个节点，而对象可能属于多个节点。 在均匀空间细分中，场景被分割成轴向的盒子。这些盒子的大小都是一样的，尽管它们不一定是立方体。射线穿过这些盒子，如图12.30所示。当击中一个对象时，遍历结束。 网格本身应该是曲面的子类，应该实现为曲面指针的3D数组。对于空单元格，这些指针为NULL。对于只有一个对象的单元格，指针指向该对象。对于有多个对象的单元格，指针可以指向一个列表、另一个网格或另一个数据结构，如边界卷层次结构。 这种遍历是以增量的方式完成的。规律性来自于射线击中每组平行平面的方式，如图12.31所示。要了解这种遍历是如何工作的，首先考虑二维情况，其中射线方向具有正的r和y分量，并从网格外开始。假设网格由点(Tmin: 9min)和(Smax: 9max)划分。网格有nr X ny单元格。 我们要做的第一件事是找到被射线e + td击中的第一个单元格的索引(i, j)然后，我们需要以适当的顺序遍历单元格。的该算法的关键部分是找到初始单元格(i,j)并决定是增加i还是j(图12.32)。注意，当我们检查单元格中与对象的交集时，我们将t的范围限制在单元格内(图12.33)。大多数实现使类型为“指向曲面的指针”的3D数组。改善。根据遍历的位置，数组可以按12.5节讨论的那样平铺。
我们还可以在分层数据结构中划分空间，例如二叉空间分区树(BSP树)。这类似于第12.4节中用于可见性排序的BSP树，但最常见的是使用轴对齐的切割平面，而不是多边形对齐的切割平面。 该结构中的一个节点包含一个切割平面和一个左右子树。每个子树包含切割平面一侧的所有对象。经过平面的对象存储在两个子树中。假设切割平面在z = D处与yz平面平行，则节点类为曲面的bsp-node类子类
虚bool hit(ray e + td, real to, real t1, hit-record rec)
虚拟框限定框()
surface-pointer左
surface-pointer正确
真正的维
我们稍后将其推广到y和z切割平面。然后可以以面向对象的样式递归地调用交集代码。该代码考虑图12.34所示的四种情况。就我们的目的而言，这些射线的原点是一个参数点: $$ p = a+t_0b. $$ 这四种情况是:
- 射线只与左子树相互作用，我们不需要测试它与切割平面的交点。当rp < D和rt <0时。
- 射线将根据左侧子树进行测试，如果没有命中，则根据右侧子树进行测试。我们需要找到射线参数atr = D，这样我们就可以确保只测试子树中的交点。这种情况发生在rp < D和rt > 0时。 3.这种情况类似于情况1，发生在tp > D和r > 0。
- 这种情况类似于情况2，发生在rp > D和rt <0时。 处理这些情况的结果遍历代码:
function bool bsp-node::hit(ray a + tb, real to, real ti, hit-record rec)
Tp = Ta + tozь
如果(Tp < D)那么
if (xb < 0) then
return (left �= NULL) and (left→hit(a + tb, t0, t1, rec))
t = (D − xa)/xb
if (t>t1) then
return (left �= NULL) and (left→hit(a + tb, t0, t1, rec))
if (left �= NULL) and (left→hit(a + tb, t0, t, rec)) then
return true
return (right �= NULL) and (right→hit(a + tb, t, t1, rec))
else
analogous code for cases 3 and 4
这是非常干净的代码。然而，为了启动它，我们需要击中一些包含边界框的根对象，这样我们就可以初始化遍历t0和t1。我们必须解决的一个问题是切割平面可以沿着任何轴。我们可以向bsp-node类添加一个整数索引轴。如果我们允许对点使用索引操作符，这将导致对上面的代码进行一些简单的修改，例如， $$ xp = xa + t0xb $$ 会变为： $$ up = a[axis] + t0b[axis] $$ 这将导致一些额外的数组索引，但不会生成更多的分支。 虽然处理单个bsp-节点比处理bvh-节点要快，但单个曲面可能存在于多个子树中这一事实意味着有更多的节点，并且可能需要更高的内存使用量。树木建得有多“好”决定了哪种树更快。构建树类似于构建BVH树。我们可以选择坐标轴在循环中分裂，我们可以每次分裂一半，或者我们可以试着在分裂的方式上更复杂一些
空间数据结构可用于解决的另一个几何问题是，在视域变化的场景中确定对象的可见性顺序 如果我们要制作一个由平面多边形组成的固定场景的多个图像，从不同的视角(游戏等应用经常如此)，我们可以使用与前一节中讨论的射线相交方法密切相关的二进制空间划分方案。不同之处在于，对于可见性排序，我们使用非轴向对齐的分割平面，因此平面可以b与多边形重合。这导致了一个优雅的算法，称为BSP树算法，从前到后排列曲面。BSP树的关键方面是它使用预处理来创建对任何视点都有用的数据结构。因此，当视点更改时，使用相同的数据结构而不更改。
BSP树算法是画家算法的一个例子。画家的算法从后往前绘制每个对象，每个新的多边形可能会透支之前的多边形，如图12.35所示。它可以实现如下:
sort objects back to front relative to viewpoint
for each object do
draw object on screen
第一步(排序)的问题是，多个对象的相对顺序并不总是定义得很好，即使每个对象对的顺序都是这样。这个问题如图12.36所示，其中三个三角形形成一个循环 BSP树算法适用于任何由多边形组成的场景，其中没有多边形穿过任何其他多边形定义的平面。然后通过预处理步骤来放宽这个限制。在接下来的讨论中，假设三角形是唯一的基元，但这些想法可以扩展到任意多边形。 BSP树的基本思想可以用两个三角形来说明，T1和T2。我们首先回忆(见2.7.3节)包含T1的平面的隐式平面方程:f1(p)=0。我们希望利用的隐式平面的关键性质是，对于平面一侧的所有点p+， f1(p+) > 0;对于平面另一侧的所有点p−，f1(p−)< 0。利用这个性质，我们可以找出T2在平面的哪一边同样，这里假设T2的三个顶点都在平面的同一侧。为了便于讨论，假设T2在平面的f1(p) < 0的一边。然后，我们可以对任意眼点e按正确的顺序画出T1和T2
if (f1(e) < 0) then
draw T1
draw T2
else
draw T2
draw T1
这样做的原因是，如果T2和e在包含Ti的平面的同一侧，从e上看，T2不可能完全或部分被Ti挡住，所以先画Ti是安全的。如果e和T2在包含Ti的平面的相对两侧，那么T2不能完全或部分阻挡Ti，相反的绘制顺序是安全的(图12.37)。 这个观察结果可以推广到许多物体，只要它们没有一个跨越Ti所定义的平面。如果我们使用一个以Ti为根的二叉树数据结构，树的负分支包含所有顶点为fi(p) < O的三角形，树的正分支包含所有顶点为fi(p) > 0的三角形。我们可以按适当的顺序画
function draw(bsptree tree,point e)
if(tree.empty) then
return
if(ftree.root(e)<) then
这段代码的优点是它适用于任何视点e，因此树可以预先计算。请注意，如果每个子树本身是一棵树，其中根三角形将其他三角形相对于包含它的平面分为两组，那么代码将照常工作。通过在更高一级终止递归调用，可以略微提高效率，但代码仍然很简单。图12.38显示了这段代码的树形图。如2.7.5节所述，在包含三个非共线点a、b、c的平面上，点p的隐式方程为 $$ F (p) = (b - a) x (c - a)) - (p - a) = 0。(12.1) $$ 它可以更快地存储形式的隐式方程(A, B,C, D) $$ f（r， y， z） = Ar + By + Cz + D = 0。(12.2) $$ 式(12.1)和式(12.2)是等价的，当你回想起隐式方程的梯度是三角形的法线时就很清楚了。的梯度
式(12.2)是n = (A, B, C)也就是法向量n = (B - A) x (C - A) 我们可以通过代入平面上的任意一点来解出D，例如，a: D=-阿拉 - 比亚 - 察 = - n。 这暗示了以下形式: $$ f (p) = n p- na= n - (p-a) = 0 $$ 这与式(12.1)相同，只要你记得n是用叉乘计算的。您使用哪种形式的平面方程，以及您是否只存储顶点，n和顶点，还是n, D和顶点，这可能是一个品味的问题——一个经典的时间存储权衡，将通过分析得到最好的解决。对于调试，使用式(12.1)可能是最好的。 阻止上述代码正常工作的唯一问题是，不能保证三角形可以在三角形的一侧唯一分类 平面或其他。它可以在平面的一边有两个顶点，在另一边有第三个顶点。也可以是平面上的顶点。这是通过使用平面将三角形分割成更小的三角形来处理的。
如果数据集中没有任何三角形交叉彼此的平面，那么所有三角形都在所有其他三角形的一边，可以使用上面的代码使用以下算法构建一个BSP树:
树根=节点(Tj)
市中心E[2,。, N)
tree-root.add (T。)
函数加法(三角T)
如果 （f（a） <0 和 f（b） <0 和 f（c） < 0），则
if(负子树为空)则负子树=节点(T)
其他的
negative-subtree。添加(T)
else if (f(a) > 0 and f(b) > 0 and f(c) > 0)则如果正子树为空则正子树= node(T)
其他的
positive-subtree。添加(T)
其他的
我们认为这种情况是不可能的
我们唯一需要修正的是三角形穿过划分平面的情况，如图12.39所示。为了简单起见，假设三角形的顶点a和b在平面的一边，顶点c在另一边。在这种情况下，我们可以找到交点A和B，并将三角形切割成三个新的有顶点的三角形 $$ Ti = (a, b, a)， T2= (b, b, A)， T3 = (A, B, c)， $$ 如图12.40所示。顶点的顺序很重要，这样法线的方向就和原始三角形的方向一样。如果我们假设f(c) < O，下面的代码可以将这三个三角形添加到树中，假设正子树和负子树不是空的: $$ positive-subtree = node(T_1)\ positive-subtree = node(T_2)\ negative-subtree = node(T_3) $$ 当一个顶点非常接近分裂平面时，一个困扰原始实现的精度问题就会出现。例如，如果我们在分裂平面的一侧有两个顶点，而另一个顶点在另一侧的距离非常小，我们将创建一个与旧三角形几乎相同的新三角形，一个是长条三角形，一个几乎为零大小的三角形。最好是将其作为特殊情况进行检测，而不是将其分成三个新的三角形。人们可能认为这种情况很少发生，但因为许多模型都有带有共享顶点的镶嵌平面和三角形，所以这种情况经常发生，因此必须谨慎处理。完成这一任务的一些简单操作是
fuction add(triangle T)
FA= f（a）
fb = f(b)
FC = f（c）
if (abs(fa) <E) then
前= 0
if (abs(fb) <E) then
FB =0
if (abs(fc) <E) then
fc=0
如果(fa <0 and fb< 0 and fc <0)则
如果(负子树为空)则
negative-subtree =节点(T)
其他的
negative-subtree.add (T)
Else if (fa >0 and fb >0 and fc 0) then
if(正子树为空)则正子树=节点(T)
其他的
positive-subtree.add (T)
其他的
把三角形切成三个三角形，每边加一个
它取f值在平面e范围内的任何顶点，并将其计算为正或负。常数e是用户选择的一个小的正实数。上面的技术是一个罕见的实例，在这个实例中，测试浮点相等性是有用的，而且有效，因为零值是设置的，而不是计算的。比较与计算的浮点值是否相等几乎是不可取的，但我们不这样做。
填写最后一种情况的细节“将三角形切成三个三角形并添加到缓存边”是直接的，但繁琐。我们应该利用BSP树构造作为一个预处理过程，其中最高的效率不是关键。相反，我们应该尝试有一个干净紧凑的代码。一个很好的技巧是，通过确保c在平面的一边，其他两个顶点在另一边，将许多情况合并为一个。这很容易通过互换来实现。在最后的else语句中填充细节(为了简单起见，假设子树是非空的)给出
if (fa* fc >0) then
掉期（FB， FC） 掉期（B，C）
掉期（FA， FB） 掉期（A， B）
Else if (fb* fc>0) then
swap(fa, fc) swap(a, c) swap(fa, fb) swap(a, b) compute a compute b
Ti = (a, b, a) T2 = (b, b, a) T3 = (a, b, c)如果(fc > 0)
负子树.add(Ti)
negative-subtree.add (T2)
positive-subtree.add (T3)
其他positive-subtree.add (Ti)
positive-subtree.add (T2)
negative-subtree.add (T3)
这段代码利用了这样一个事实:如果a和b的符号相同，那么它们的乘积就是正的——因此，第一个if语句。如果交换了顶点，我们必须进行两次交换以保持顶点的逆时针顺序。注意，只有一个顶点可能正好位于平面上，在这种情况下，上面的代码将会成功，但是其中一个生成的三角形的面积为零。这可以通过忽略可能性来处理，这不是那么危险，因为栅格化代码必须处理屏幕空间中的零面积三角形(即边对三角形)。您还可以添加一个不向树中添加零面积三角形的检查。最后，你可以引入一种特殊情况，当fa, fb和fc中恰好有一个为零时，这就把三角形切成了两个三角形。 为了计算A和B，需要一个线段和隐式平面交点。例如，连接a和c的参数线是 $$ p(t) = a +t(c - a) $$ 与平面n - p+D = 0的交点可以通过将p(t)代入平面方程得到: $$ n- （a +t（c - a）） +D = 0， $$ 求解t: $$ n-a+D。 n - (c $$ 称这个解为tA，我们可以写出A的表达式: $$ A = A +tA(c - A) $$ 一个萨玛拉尔计算会得到B。
创建树的效率比遍历树的效率要小得多，因为它是一个预处理过程。遍历BSP树所需的时间与树中节点的数量成正比。(这棵树是否平衡并不重要。)每个三角形都有一个节点，包括由于拆分而创建的三角形。这个数字取决于三角形被添加到树中的顺序。例如，在图12.41中，如果Ti是根，树中会有两个节点，但如果T2是根，则会有更多的节点，因为T会被拆分。 要找到添加到树中的三角形的“最佳”顺序是很困难的。对于N个三角形，有N个!可能的顺序。所以尝试所有的点菜通常是不可行的。或者，可以从随机排列集合中尝试一些预定数量的排序，并将最佳排序保留到最终的树中。 上面描述的分割算法将一个三角形分割成三个三角形。把一个三角形分成一个三角形和一个凸四边形会更有效。如果所有的输入模型都只有三角形，那么这样做可能就不值得了，但对于适应任意多边形的实现来说，这样做很容易。
有效地利用内存层次结构是现代架构设计算法的关键任务。确保多维数组的数据以“良好”的排列方式排列是通过平铺(有时也称为砖砌)来完成的。一个传统的二维数组被存储为一个ID数组和一个索引机制;例如，一个N × N的数组存储在一个长度为N,N的ID数组中，二维索引(r, y)(从(0,0)到(N- -1, Ny -1))映射到一维索引(从0到N,Ny -1)使用公式 $$ index = x+N_xy. $$ 图12.42显示了该内存的布局示例。这种布局的一个问题是，尽管在同一行中的两个相邻数组元素在内存中彼此相邻，但在同一列中的两个相邻元素将在内存中被N个元素分隔开。这可能导致大n的内存局部性较差。对此的标准解决方案是使用tile使行和列的内存局部性更相等。如图12.43所示，其中使用了2 x 2瓷砖。下一节将讨论为这样一个数组建立索引的详细信息。在此之后，我们将介绍一个更复杂的示例，即在3D数组上使用两层平铺。 一个关键问题是瓷砖的尺寸。实际上，它们应该与机器上的内存单元大小相似。例如，如果我们在一台具有128字节缓存线的机器上使用16位(2字节)数据值，那么缓存线中正好可以容纳8 x 8块。然而，使用32位浮点数(将32个元素放入缓存线中)，5 x 5的tile有点太小，6 x 6的tile有点太大。因为还有一些更粗的内存单元，比如页面，所以具有类似逻辑的分层平铺可能很有用。
如果我们假设一个N, x N，数组分解为正方形的N x N块瓷砖(图12.44)，那么所需的瓷砖数量为 $$ B_x = N_x/n B_y = N_y/n $$ 这里，我们假设n除以n, n，完全正确。如果不是这样，则应该填充数组。例如，如果N = 15和N = 4，则N应更改为16。要计算出这样一个数组的索引公式，我们首先找到tile的索引(bz, by)，它给出了tile的行/列(tile本身形成了一个2D数组): $$ b_x = x/n b_y = y/n $$ 其中为整数除法，如:12 5 = 2。如果我们按照图12.42所示的顺序排列瓷砖，那么瓷砖的第一个元素(bz, by)的索引为 $$ index = n2(B-by + bz)。 $$ 该tile中的内存像传统的2D数组一样排列，如图12.43所示。贴图内的部分偏移量(r'， y')为 $$ R ' = R mod n， Y = Y mod n， $$ 其中mod是余数运算符，例如:12 mod 5 = 2。因此，贴图内部的偏移量为 $$ offset= y'n +r。 $$ 因此，在具有n × n个瓦的Nx × Ny数组中寻找1D索引元素(x, y)的完整公式为 $$ index = n^2(B_xb_y + b_x) + y'n+x'\ = n^2((N_x ÷ n)(y ÷ n) + x ÷ n)+(y mod n)n + (x mod n). $$ 该表达式包含许多整数乘、除和模操作，在某些处理器上代价很高。当n是2的幂时，这些操作可以转换为位移位和按位逻辑操作。然而，如上所述，理想的大小并不总是2的幂。有些乘法运算可以转换为移位/加法运算，但除法和模运算的问题更大。可以增量地计算索引，但这需要跟踪计数器，需要进行大量比较，并且分支预测性能很差。 然而，有一个简单的解决方案;注意，索引表达式可以写成 $$ index = Fx(x) + Fy(y),\ Fx(x) = n2(x ÷ n)+(x mod n),\ Fy(y) = n2(Nx ÷ n)(y ÷ n)+(y mod n)n\ $$ 我们将Fx和Fy制表，并使用x和y找到数据数组的索引。这些表将分别由Nx和Ny元素组成。表的总大小将适合处理器的主数据缓存，即使是非常大的数据集大小
有效地利用TLB也成为影响算法性能的一个关键因素。通过在$n \times n\times n$个单元格中创建m × m × m块，同样的技术可以用于提高3D数组中的TLB命中率。例如，一个40 × 20 × 19的体积可以分解为4 × 2 × 2的大块砖，即2 × 2 × 2的大块砖，即5 × 5 × 5的单元格。这对应于m = 2和n = 5。因为19不能被mn = 10分解，所以需要一层填充。经验上有用的大小对于16位数据集是m = 5，对于浮点数据集是m = 6。 可以用该表达式计算任意(x, y, z)三元组的数据数组的最终索引: $$\begin{aligned} index &= ((x ÷ n) ÷ m)n^3m^3((N_z ÷ n) ÷ m)((N_y ÷ n) ÷ m)\ &+((y ÷ n) ÷ m)n^3m^3((N_z ÷ n) ÷ m)\ &+((z ÷ n) ÷ m)n^3m^3\ &+((x ÷ n)\mod m)n^3m^2\ &+((y ÷ n)\mod m)n^3m\ &+((z ÷ n)\mod m)n^3\ &+(x\mod (n^2))n^2\ &+(y\mod n)n\ &+(z\mod n)\ \end{aligned}$$ 其中Nx、Ny和Nz分别是数据库的大小 注意，与更简单的二维单级情况一样，这个表达式可以写成 $$ index = F_x(x) + F_y(y) + F_z(z),~~~~~当 \ \begin{aligned} \ F_x(x) &= ((x ÷ n) ÷ m)n^3m^3((N_z ÷ n) ÷ m)((N_y ÷ n) ÷ m)\ &+((x ÷ n)\mod m)n^3m^2\ &+(x\mod n)n^2,\ F_y(y) &= ((y ÷ n) ÷ m)n^3m^3((N_z ÷ n) ÷ m)\ &+((y ÷ n)\mod m)n^3m +\ &+(y\mod n)n,\ F_z(z) &= ((z ÷ n) ÷ m)n^3m^3\ &+((z ÷ n)\mod m)n^3\ &+(z\mod n)\ \end{aligned}$$
- 平铺真的对性能有那么大的影响吗? 在一些体渲染应用程序中，两层平铺策略带来的性能差异高达十倍。当数组不适合mai 可有效防止图像编辑等应用中的抖动。
- 如何将列表存储在翼边结构中 对于大多数应用程序来说，对引用使用数组和索引是可行的。但是，如果要执行许多删除操作，那么使用链表和指针是明智的
对翼边数据结构的讨论是基于 晴光Shene(2003)。有更小的网格数据结构比翼边。使用这种结构的权衡在有向边-中讨论 三角形网格的可扩展表示(Campagna, Kobbelt， & Seidel， 1998)。平铺阵列的讨论是基于对体积的交互式射线跟踪 可视化(Parker等人，1999)。Charles Loop (Loop, 2000)在一份技术报告中讨论了类似于三角形邻接结构的结构。关于流形的讨论可以在
- 存储为四个独立三角形的简单四面体与存储为翼边数据结构的四面体的内存差异是什么?
- 画一个自行车的场景图
- n维数组的单层平铺需要多少查找表?
- 给定N个三角形，可以添加到生成的BSP树的最小三角形数是多少?最大数量是多少