12 图形数据结构

某些数据结构在图形应用程序中反复出现，可能是因为它们处理了基本的基本思想，如曲面、空间和场景结构。本章讨论最常见和最有用的几种基本和不相关的数据结构类别：网格结构、空间数据结构、场景图和平铺多维数组。

对于网格，我们讨论了用于存储静态网格和将网格传输到图形API的基本存储方案。我们还讨论了wingededge数据结构（Baumgart，1974）和相关的半边结构，它们对于管理细分发生变化的模型（如细分或模型简化）非常有用。虽然这些方法可以推广到任意多边形网格，但我们在这里只关注三角形网格的简单情况。

接下来，介绍了场景图的数据结构。这种数据结构的各种形式在图形应用程序中无处不在，因为它们在管理对象和转换时非常有用。所有新的图形API都具有支持场景图的特性。

对于空间数据结构，我们讨论了在三维空间边界体层次、层次空间细分和均匀空间细分中组织模型的三种方法，以及使用层次空间细分（BSP树）去除隐藏曲面的方法。同样的方法也用于其他目的，包括几何体剔除和碰撞检测。

最后，介绍了分片多维数组。这种结构最初是为了帮助在需要从磁盘交换图形数据的应用程序中提高分页性能而开发的，现在对于计算机上的内存位置至关重要，无论数组是否适合主内存。

12.1 三角形网格

大多数真实世界的模型都由具有共享顶点的三角形复合体组成。这些通常被称为三角网格、三角网格或三角不规则网络（TIN），有效地处理它们对许多图形程序的性能至关重要。效率的重要性取决于应用程序。网格存储在磁盘和内存中，我们希望将消耗的存储量降至最低。当网格通过网络传输或从CPU传输到图形系统时，它们会消耗带宽，带宽通常比存储更宝贵。在对网格执行操作的应用程序中，除了简单地存储和绘制网格（如细分、网格编辑、网格压缩或其他操作）外，有效地访问邻接信息至关重要。

三角形网格通常用于表示曲面，因此网格不仅仅是不相关三角形的集合，而是通过共享顶点和边相互连接以形成单个连续曲面的三角形网络。这是关于网格的一个重要观点：与相同数量的不相关三角形的集合相比，可以更有效地处理网格。

三角形网格所需的最小信息是一组三角形（三个顶点）及其顶点的位置（在三维空间中）。但许多程序需要在顶点、边或面上存储额外的数据，用于支持纹理映射、着色、动画和其他操作。顶点数据是最常见的：每个顶点都可以具有材质参数、纹理坐标、辐照度以及任何值在整个曲面上发生变化的参数。然后在每个三角形上对这些参数进行线性插值，以定义网格整个曲面上的连续函数。但是，能够存储每条边或每个面的数据有时也很重要。

12.1.1 网格拓扑

网格类似于曲面的想法可以形式化为网格拓扑上的约束，即三角形连接在一起的方式，而不考虑顶点位置。许多算法只能在具有可预测连接性的网格上工作，或者更容易实现。对网格拓扑的最简单和最严格的要求是曲面为流形。流形网格是“水密的”——它没有间隙，将曲面内部的空间与外部的空间分隔开。它在网格上的任何位置看起来都像一个曲面。

流形一词来自拓扑学的数学领域：粗略地说，流形（特别是二维流形，或2流形）是一个曲面，其中任何点周围的一个小邻域都可以平滑为一个平面。反例最清楚地解释了这个想法：如果网格上的一条边有三个三角形与其相连，则边上一个点的邻域与其中一个三角形内部一个点的邻域不同，因为它有一个额外的“鳍”伸出（图12.1）。如果边上正好附着了两个三角形，则边上的点与内部的点一样具有邻域，只是中间有一个折痕。类似地，如果共享一个顶点的三角形处于图12.2中左侧的配置中，则邻域就像两块在中心粘在一起的曲面，如果不将其折叠，就无法将其展平。右侧显示的具有更简单邻域的顶点很好。

许多算法都假设网格是流形的，如果将一个格式不正确的网格作为输入，则最好验证此属性以防止崩溃或无限循环。此验证归结为检查所有边是否为流形，以及通过验证以下条件检查所有顶点是否为流形：

  • 每条边正好由两个三角形共享。
  • 每个顶点周围都有一个完整的三角形环。

图12.1说明了一条边如何通过太多三角形而无法通过第一次测试，图12.2说明了一个顶点如何通过连接两个单独的三角形环而无法通过第二次测试。

流形网格很方便，但有时需要允许网格具有边或边界。这样的网格不是流形——边界上的一个点有一个在一侧被切断的邻域。它们不一定是无懈可击的。然而，我们可以将流形网格的要求放宽到具有边界的流形网格的要求，而不会给大多数网格处理算法带来问题。放宽的条件包括：

  • 每条边由一个或两个三角形使用。
  • 每个顶点都连接到一个边连接的三角形集。

图12.3说明了这些条件：从左到右，有一条边上有一个三角形，一个顶点的相邻三角形位于一个边连接集中，一个顶点上有两个不连接的三角形集。

最后，在许多应用中，能够区分曲面的“正面”或“外部”与“背面”或“内部”非常重要，这就是曲面的方向。对于单个三角形，我们根据顶点列出的顺序定义方向：正面是三角形的三个顶点按逆时针顺序排列的一侧。如果一个连接的网格的所有三角形都有一直的朝向，则该网格的方向一致；如果且仅当每对相邻三角形的方向一致，则该情况成立。

在一对方向一致的三角形中，两个共享顶点以相反的顺序出现在两个三角形的顶点列表中（图12.4）。重要的是方向的一致性，一些系统使用顺时针而不是逆时针顺序定义正面。

任何具有非流形边的网格都无法一致定向。但网格也可能是一个有效的有边界的流形（甚至是流形），但却没有一致的方法来确定三角形的方向，因为它们不是可定向曲面。图12.5所示的M–obius带就是一个例子。然而，这在实践中很少成为问题。

12.1.2 索引化的网格存储

一个简单的三角形网格如图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 ]中，该顶点的位置存储在顶点数组的相应行中；有关示例，请参见图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.1.3 三角形带和三角形扇

索引网格是三角形网格最常见的内存表示形式，因为它们实现了简单性、方便性和紧凑性的良好平衡。它们还通常用于通过网络以及在应用程序和图形管道之间传输网格。在需要更紧凑的应用程序中，三角形顶点索引（在索引网格中，仅在顶点位置占据三分之二的空间）可以使用三角形条和三角形扇更有效地表示。

三角形风扇如图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+2个顶点足以描述n个三角形，这比标准索引网格所需的3n个顶点节省了很多。如果程序是顶点绑定的，长三角形条带将节省大约三倍的时间。

三角形条带似乎只有在条带很长的情况下才有用，但即使相对较短的条带也已经获得了大部分好处。存储空间的节省（仅针对顶点索引）如下所示：

strip length 1 2 3 4 5 6 7 8 16 100 \infty
relative size 1.00 0.67 0.56 0.50 0.47 0.44 0.43 0.42 0.38 0.34 0.33

因此，事实上，随着长条带的增长，回报率会迅速下降。因此，即使对于非结构化网格，也值得使用一些贪婪算法将其聚集成短条。

12.1.4 网格连接的数据结构

索引网格、条带和扇都是静态网格的良好、紧凑的表示形式。但是，它们不允许修改网格。为了高效地编辑网格，需要更复杂的数据结构来高效地回答以下查询：

  • 给定一个三角形，三个相邻的三角形是什么？
  • 给定一条边，哪两个三角形共享它？
  • 给定一个顶点，哪些面共享该顶点？
  • 给定一个顶点，哪些边共享该顶点？

三角形网格、多边形网格和带孔多边形网格有许多数据结构（参考资料请参见本章末尾的注释）。在许多应用中，网格非常大，因此有效的表示非常关键。

最直接的实现（尽管过于臃肿）是有三种类型：顶点、边和三角形，并直接存储所有关系：

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
}

在三角面数组nbr中，第k点的相邻三角形共享顶点k和k+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
}

显而易见，可以直接在数据结构中找到相邻的三角形和三角形的顶点，而且通过仔细使用该三角形邻接信息，也可以在恒定时间内查询有关顶点的连接性。办法是从一个三角面移动到另一个三角面，只访问与相关顶点相邻的三角面。如果三角形t的第k个顶点是顶点v，则三角面t.nbr[k]是沿顺时针方向环绕顶点v的下一个三角面。我们可以使用以下算法遍历与给定顶点相邻的所有三角形：

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
}

在上述结构中，通过从三角形索引t借用两个存储位来存储边缘索引i，从而使总存储需求保持不变。

在这种数据结构中，三角形的邻接数组告诉我们哪个相邻三角形的边与该三角形的三条边共享。有了这些额外的信息，我们总是知道在哪里找到原始三角形，这导致了数据结构的不变量：对于任何三角形t的任何第j条边，

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);
}

这里的顶点遍历是顺时针的，这是必要的，因为结构中省略了prev指针。

由于半边通常成对分配（至少在没有边界的网格中），许多实现可以取消成对指针。例如，在基于数组索引的实现中（如图12.18所示），可以对数组进行排列，使偶数边i始终与边i+1配对，奇数边j始终与边j-1配对。

除了本章所示的简单遍历算法外，所有这三种网格拓扑结构都可以支持各种“网格手术”操作，例如分割或折叠顶点、交换边、添加或删除三角形等。

12.1 场景图

未完待续...