2

我正在尝试构建一个 .PLY 解析器，以将存储为 .ply 文件的 3d 模型加载到半边数据结构网格中。

抱歉这个大问题，我很冗长，我想确保我列出了所有细节。正因为如此，我将立即重申我的最终目标，以便用户可以在阅读大量文本之前了解我想要什么。

1) 什么是从 .PLY 文件的顶点和面列表中记忆半边的好散列

或者

2) 有没有更好的方法从 .PLY 文件中的数据填充我的半边结构？

.PLY 文件列出了顶点，然后是网格的面。显而易见的解决方案是先填写顶点表，然后使用面列表生成边表。问题是每条边都有一个伙伴边，所以对于四边形网格，我加载的第一个四边形将需要 8 个半边。这最初不是问题，只需为面部创建四个半边并反转每个边以使其伙伴成为半边。这里的问题是，这会创建 4 个悬垂的半边，这些边与 4 个不同的面相关联。

所以有两种攻击方法：首先为人脸生成所有边，然后尝试配对伙伴边。我真的不喜欢这种方法，它似乎在编程上效率较低，因为它将涉及大量搜索和排序。

第二：按照第一个说明进行：从指定的第一个面开始并生成创建多边形所需的边，并在创建边时创建它们的双胞胎。但是，我们将记住边列表，因此所有边都将散列到一个表中。然后，当我们为其他面生成边时，如果已经生成了一条边（因为它是先前加载的面的伙伴边），我们将简单地将指针从表格中取出。

这就是我卡住的地方。我需要一个智能散列函数来记忆我的边缘列表。需要尽量减少碰撞以提高效率。我现在想到的方案是根据创建它们的两个顶点命名*边，IE 边 01 和 10 是双胞胎。最坏的情况会创建一个哈希表，其中所有顶点都可能被连接，最终大小为 2^n，其中 n = 顶点数，这是完全不可接受的。我的目标是使哈希值接近实际边数（= 每个面的边数之和），同时仍尽量减少碰撞。

*注意：因为半边执行“仅逆时针”绘制方案，所以不可能发生名称冲突。通过基于绘制它们的两个顶点命名边，我们确保所有名称对于单个半边都是唯一的。

4

2 回答 2

3

我很啰嗦

您可能想对此有所了解。

拥有一条边的一个简单方法是通过它的两个顶点的索引。为了使其唯一，首先采用较小的索引，然后采用较大的索引。像这样的东西：

uint hash(const Vertex& v1, const Vertex& v2)
{
    int i1 = v1.index;
    int i2 = v2.index;
    if (i1 > i2)
        swap(i1, i2);
    return (i1 | (i2 << 16));
}

在此哈希表指向的实际数据中，您可能希望跟踪您已经看到的哪一对以及您期望的哪一对（相反的一对）。

于 2009-02-17T10:05:58.393 回答
0

您是否在边缘存储索引或引用？如果你使用incides，不会像这样的微不足道的哈希函数

19 * index0 + 7 * index1

“足够好”？如果你的散列应该是对称的，我会选择两个索引的简单异或，但由于半边确实是定向的，你最好使用非对称散列并专门寻找成对的边方向。

因为实际上比较两条边是一个相对便宜的操作（即比生成复杂的散列便宜），碰撞并不像你想象的那么可怕。

也就是说，根据我的经验。准备好在这里被真正的哈希专家烧毁。:-)

作为旁注：您可能希望确保您的哈希表实现与删除相得益彰，因为从表中删除您找到的任何配对边可能会有所回报。

于 2009-02-17T10:05:31.590 回答