网格："Sorting/Reordering" 数组引用另一个的共享条目以提高缓存效率

Question

给定一个顶点数组：{v1, v2, v3, v4, v5, ..., vN}

K 个多边形用块对其进行索引，对于示例 4 边形*：{v7, v2, v51, v16}

_{请注意，两个或多个多边形可能共享同一个顶点。事实上，大多数顶点将由 4-6 个多边形共享（四边形网格为 4 价，三角形网格为 6 价）。}

...我们如何有效地 reorder/sort 顶点数据，例如在读取给定多边形的顶点时减少缓存未命中？我对一种在合理时间内完成的算法感兴趣，而不是对给出最佳结果的算法感兴趣。即使是一些粗略的启发式方法也比这里完全任意的顺序要好。

理想的做法是将 {v1052, v507213, v63252, v3} 变成更像 {v70, v71, v72, v73} 的东西。由于顶点的共享量，如果没有一些异常值，这个理想可能通常无法实现。

当然欢迎成熟的解决方案，但我更感兴趣的只是算法家族的名称，这些算法与在运行时重组用户数据以提高缓存效率有关。我想这样的算法一定存在，尤其是在网格的高效 VBO 表示领域，但我未能提出适当的搜索标准。这还会叫'sorting'吗？

我可以看到可能有两类方法可以解决这个问题：一种是实际处理遍历网格邻居，这对网格表示非常具体，另一种是简单地查看一组的一般访问模式索引或指向另一个条目的数组。后者作为更通用的解决方案对我更有吸引力，即使它可能不那么有效。

更新：

如建议的那样，我尝试只编写一些建议的启发式算法，而不是在算法上对它们进行过多的推测。它给了我一些粗略的基础，帮助我更好地理解问题的本质，但不幸的是结果很差。我将这个问题标记为 C 和 C++，因为我对这些语言的算法研究建议和可能的片段更感兴趣，而不是提供我自己的实现，但这里是我的 C++ 只是为了比较：

#define _SECURE_SCL 0
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <deque>

using namespace std;

static const float pi_f = 3.14159265358979323846f;
enum {poly_size = 3};

class Alloc
{
public:
    Alloc(): head(0)
    {
    }

    ~Alloc()
    {
        purge();
    }

    void purge()
    {
        while (head)
        {
            Pool* next = head->next;
            free(head);
            head = next;
        }
    }

    void* allocate(int size)
    {
        size = (size + 15) & (~0x0f);
        if (head && (head->used + size) < head->capacity)
        {
            void* mem = head->mem + head->used;
            head->used += size;
            return mem;
        }
        int new_pool_size = 4096;
        if (size > new_pool_size)
            new_pool_size = size;
        Pool* new_pool = static_cast<Pool*>(malloc(sizeof(Pool) + new_pool_size));
        new_pool->used = size;
        new_pool->capacity = new_pool_size;
        new_pool->next = head;
        head = new_pool;
        return new_pool->mem;
    }

private:
    struct Pool
    {
        Pool* next;
        int used;
        int capacity;
        char mem[1];
    };
    Pool* head;
};

struct Vertex
{
    Vertex(): x(0), y(0), z(0) {}
    float x, y, z;
};

struct VertexPolys
{
    VertexPolys(): num_polys(0), polys(0) {}
    int num_polys;
    int* polys;
};

struct Poly
{
    Poly()
    {
        vertices[0] = -1;
        vertices[1] = -1;
        vertices[2] = -1;
    }
    int vertices[poly_size];
};

struct IndexSet
{
    explicit IndexSet(int n): num(0), data(n), used(n, false) {}

    void insert(int index)
    {
        if (!used[index])
        {
            data[num++] = index;
            used[index] = true;
        }
    }

    int num;
    vector<int> data;
    vector<char> used;
};

struct Mesh
{
    void reorder_vertices(const vector<int>& new_order)
    {
        assert(new_order.size() == vertices.size());
        vector<int> to_new_order(new_order.size());
        for (size_t i=0; i < new_order.size(); ++i)
            to_new_order[new_order[i]] = i;

        for (size_t i=0; i < polys.size(); ++i)
        {
            Poly& poly = polys[i];
            for (int j=0; j < poly_size; ++j)
                poly.vertices[j] = to_new_order[poly.vertices[j]];
        }
        vector<Vertex> reordered_vertices(vertices.size());
        for (size_t i=0; i < new_order.size(); ++i)
            reordered_vertices[i] = vertices[new_order[i]];
        vertices.swap(reordered_vertices);
    }

    vector<Vertex> vertices;
    vector<Poly> polys;
    vector<VertexPolys> vertex_polys;
};

static void create_sphere(Mesh* mesh, float radius, int rings, int sectors)
{
    const float ring_step = 1.0f / (float)(rings-1);
    const float side_step = 1.0f / (float)(sectors-1);
    const int total_verts = rings * sectors;

    // Create sphere vertices.
    vector<int> indices;
    indices.reserve(total_verts);
    for (int r=0; r < rings; ++r) 
    {
        for (int s=0; s < sectors; ++s) 
        {           
            indices.push_back(mesh->vertices.size());
            const float x = cos(2*pi_f * s * side_step) * sin(pi_f * r * ring_step);
            const float y = sin(-pi_f/2 + pi_f * r * ring_step);
            const float z = sin(2*pi_f * s * side_step) * sin(pi_f * r * ring_step);
            Vertex new_vertex;
            new_vertex.x = x * radius;
            new_vertex.y = y * radius;
            new_vertex.z = z * radius;
            mesh->vertices.push_back(new_vertex);
        }
    }

    // Create sphere triangles.
    for (int r=0; r < rings-1; ++r) 
    {
        for (int s=0; s < sectors-1; ++s) 
        {
            int npv[4] = 
            {
                r * sectors + s,
                r * sectors + (s+1),
                (r+1) * sectors + (s+1),
                (r+1) * sectors + s
            };
            for (int j = 0; j < 4; ++j)
                npv[j] = indices[npv[j] % total_verts];

            Poly new_poly1;
            new_poly1.vertices[0] = npv[0];
            new_poly1.vertices[1] = npv[1];
            new_poly1.vertices[2] = npv[2];
            mesh->polys.push_back(new_poly1);

            Poly new_poly2;
            new_poly2.vertices[0] = npv[2];
            new_poly2.vertices[1] = npv[3];
            new_poly2.vertices[2] = npv[0];
            mesh->polys.push_back(new_poly2);
        }
    }
}

static Mesh create_mesh(Alloc& alloc)
{
    Mesh mesh;
    create_sphere(&mesh, 10.0f, 100, 100);

    // Shuffle the vertex order to make it all random (this tends
    // to reflect a real-world model better which can get very arbitrary
    // in terms of its vertex/polygon creation order).
    vector<int> new_vertex_order(mesh.vertices.size());
    for (size_t j=0; j < mesh.vertices.size(); ++j)
        new_vertex_order[j] = static_cast<int>(j);
    random_shuffle(new_vertex_order.begin(), new_vertex_order.end());
    mesh.reorder_vertices(new_vertex_order);

    // Count the number of polygons connected to each vertex.
    mesh.vertex_polys.resize(mesh.vertices.size());
    for (size_t i=0; i < mesh.polys.size(); ++i)
    {
        const Poly& poly = mesh.polys[i];
        for (int j=0; j < poly_size; ++j)
        {
            const int vertex_index = poly.vertices[j];
            ++mesh.vertex_polys[vertex_index].num_polys;
        }
    }

    // Allocate space for the vertex polygons.
    for (size_t i=0; i < mesh.vertex_polys.size(); ++i)
    {
        VertexPolys& vp = mesh.vertex_polys[i];
        vp.polys = static_cast<int*>(alloc.allocate(vp.num_polys * sizeof(int)));
        vp.num_polys = 0;
    }

    // Form the polygons connected to each vertex.
    for (size_t i=0; i < mesh.polys.size(); ++i)
    {
        const Poly& poly = mesh.polys[i];
        for (int j=0; j < poly_size; ++j)
        {
            const int vertex_index = poly.vertices[j];
            VertexPolys& vp = mesh.vertex_polys[vertex_index];
            vp.polys[vp.num_polys++] = i;
        }
    }
    return mesh;
}

static void output_stats(const Mesh& mesh, const char* type)
{
    // Measure the proximity of each pair of vertices in each polygon.
    int num_optimal = 0;
    float prox_sum = 0.0f;
    for (size_t i=0; i < mesh.polys.size(); ++i)
    {
        const Poly& poly = mesh.polys[i];
        const int prox1 = abs(poly.vertices[1] - poly.vertices[0]);
        const int prox2 = abs(poly.vertices[2] - poly.vertices[1]);
        const int prox3 = abs(poly.vertices[0] - poly.vertices[2]);
        const float poly_prox = (prox1 + prox2 + prox3) / 3.0f;
        prox_sum += poly_prox;
        if (prox1 <= 6 && prox2 <= 6 && prox3 <= 6)
            ++num_optimal;
    }
    cout << "-------------------------------------------------" << endl;
    cout << type << endl;
    cout << "-------------------------------------------------" << endl;
    cout << "-- # Vertices: " << mesh.vertices.size() << endl;
    cout << "-- # Polygons: " << mesh.polys.size() << endl;
    cout << "-- # Optimal Polygons: " << num_optimal << endl;
    cout << "-- Average vertex proximity: " << (prox_sum / mesh.polys.size()) << endl;
}

static void basic_optimization(Mesh& mesh)
{
    IndexSet index_set(static_cast<int>(mesh.vertices.size()));
    for (size_t i=0; i < mesh.polys.size(); ++i)
    {
        const Poly& poly = mesh.polys[i];
        for (int j=0; j < poly_size; ++j)
        {
            const int vertex_index = poly.vertices[j];
            index_set.insert(vertex_index);
        }
    }
    mesh.reorder_vertices(index_set.data);
}

static void breadth_first_optimization(Mesh& mesh)
{
    IndexSet index_set(static_cast<int>(mesh.vertices.size()));
    assert(!mesh.polys.empty());

    deque<int> to_process;
    vector<char> processed(mesh.polys.size(), false);
    to_process.push_back(0);
    processed[0] = true;

    while (!to_process.empty())
    {
        const int poly_index = to_process.front();
        to_process.pop_front();

        const Poly& poly = mesh.polys[poly_index];
        for (int i=0; i < poly_size; ++i)
        {
            const int vertex_index = poly.vertices[i];
            index_set.insert(vertex_index);
            const VertexPolys& vp = mesh.vertex_polys[vertex_index];
            for (int j=0; j < vp.num_polys; ++j)
            {
                if (!processed[vp.polys[j]])
                {
                    to_process.push_back(vp.polys[j]);
                    processed[vp.polys[j]] = true;
                }
            }
        }
    }
    mesh.reorder_vertices(index_set.data);
}

int main()
{
    // Linear Heuristic
    {
        Alloc alloc;
        Mesh mesh = create_mesh(alloc);
        basic_optimization(mesh);
        output_stats(mesh, "Linear Heuristic");
    }

    // Breadth-First Heuristic
    {
        Alloc alloc;
        Mesh mesh = create_mesh(alloc);
        breadth_first_optimization(mesh);
        output_stats(mesh, "Breadth-First Graph Heuristic");
    }
}

结果：

-------------------------------------------------
Linear Heuristic
-------------------------------------------------
-- # Vertices: 10000
-- # Polygons: 19602
-- # Optimal Polygons: 198
-- Average vertex proximity: 67.0118
-------------------------------------------------
Breadth-First Graph Heuristic
-------------------------------------------------
-- # Vertices: 10000
-- # Polygons: 19602
-- # Optimal Polygons: 13
-- Average vertex proximity: 88.9976

问题的本质似乎可以归结为将这个高度连接的二维拓扑网格映射到具有良好局部性的一维 space。这就是为什么我认为这些基本算法不太好：网格的连通性和无缝性使得不可能通过遍历整个网格的启发式方法非常有效地映射网格。

它类似于我们试图获取 3D 网格和 'unfold' 并将其映射到平面 2D space 的纹理图集映射。为了解决这个问题，我们经常需要在网格中引入接缝，以便我们可以将其分解为 2D 连通岛。在这里，我们类似地从 2D 图 space 将其分解为在 1D 内存中具有良好局部性的岛屿 space。

所以我认为最佳算法会以这种方式将网格分解成段（部分），并将这些类型的算法应用于每个段。通过这种方式，我们在给定的网格段内获得良好的 1D 内存局部性，病理情况是每个段边界处的异常值，其中顶点与其他段共享。

如果在选择完全不同的 P 之前，对于给定的质心多边形 P，它只遍历 K 的宽度，其中 K 是一些小数，那么广度优先搜索的变体可以粗略地执行此操作。那会在网格中隔离连接的小二维岛，该网格可以映射到一维内存 space，每个岛内具有良好的局部性（在这些岛的边界处很差）。

不管怎样，我主要是为这种东西寻找正式的算法名称。我仍然不确定这是否会被称为 'sorting' -- 也许我正在寻找错误的东西。

Answer 1

我觉得回答我自己的问题并接受它作为答案有点愚蠢，感谢所有提供的评论！

但我发现了 class 处理这个问题的算法和论文，从 Tom Forsynth 的 线性速度顶点缓存优化 开始，作为一个经常被引用的启发式算法。奇怪的是，他们经常通过实际模拟硬件缓存来解决这些问题。这是一个这样的例子：http://www-etud.iro.umontreal.ca/~blancher/projects/vertex_caching/vertex_caching_eb.pdf

问题显然是 NP 完全问题，但似乎有许多实用的启发式方法可用。

这些技术显然可以大大提高渲染速度，并且应该适用于一般的网格遍历算法（有或没有 GPU 的参与以及渲染上下文的内部或外部）。

我最终绕过了这个问题，而不是通过将网格分割成更小的连接区域来解决它（用紧密打包的小区域 poly/vert/edge 数据改善参考的局部性，而不是改善网格的顺序更大区域内的索引）。但我想在不久的将来尝试这些技术，因为我必须克服许多障碍才能尝试让所有这些小的分段区域为用户无缝拼接，而且只有一个会容易得多在访问多边形顶点或顶点边或边缘多边形时具有更缓存友好内存布局的大网格，例如

由于还没有任何答案，我想我会为任何好奇的人提供我的发现。

网格："Sorting/Reordering" 数组引用另一个的共享条目以提高缓存效率

Meshes: "Sorting/Reordering" Arrays Referencing Shared Entries of Another for Cache Efficiency

c++

algorithm

performance

mesh

更新：