如何索引二十面体的面？

Question

我正在编写一个模拟作用于横跨球体表面的网格.网格本身是一个细分的二十面体 (然而事先不知道细分的级别)

使用正方形网格,很容易找到相邻的单元格,因为它们沿x轴或y轴都是正负1.但是对于这些三角形来说情况并非如此,我的思绪很难想象一种索引细胞的方法.

我可以使用任何类型的坐标系来寻址二十面体的面,这至少可以让3个单元格与二十面体中的任意单元相邻吗？

Answer 1

实际上,您希望将几何体预处理为特定的数据结构,以便快速查找三角形的邻居.

如果这是您唯一的要求,那么很容易"自己动手".例如,对于每个三角形,您将存储其三个边,作为指向边结构的指针或作为边表的索引.然后,对于每个边,您将存储其两个相邻的三角形(再次作为指针或三角形索引).

此设置允许您轻松地从三角形到每个边缘,然后从边缘结构中找到另一个相邻三角形.

有三角形表面的更先进的数据结构允许进行更有趣的操作,例如双连接边缘列表或翼边数据结构.

如果您想使用预制库,GTS库将满足您的需求,甚至更多.

Answer 2

对于二十面体的每一面，您可以将三角形映射到网格，每个网格正方形分为两部分，例如（索引的十六进制编号以方便格式化）：

 A
 +
 |\
 |0\
 +--+
 |\2|\
 |1\|3\
 +--+--+
 |\5|\7|\
 |4\|6\|8\
 +--+--+--+
 |\A|\C|\E|\
 |9\|B\|D\|F\
 +--+--+--+--+
B             C

对于被细分 n 次的边，该边有 4 ⁿ个三角形，因此您可以为二十面体的每条边创建一个该大小的数组，以存储用于模拟的每个三角形的数据。

对三角形的引用可以存储为（边，行，列）

行索引和列索引都是从 0 开始的。列索引基于行中三角形的数量（即每个网格正方形 2 个）。

如果你有边、行和列，你可以计算边的数组索引，如下所示：

index = (row * row) + column

因此，您可以将数据存储在二维数组中并像这样访问它：

value = data[side][(row * row) + column]

具有偶数列的三角形的相邻三角形：

(side, row, column - 1)
(side, row, column + 1)
(side, row + 1, column + 1)

具有奇数列的三角形的相邻三角形：

(side, row, column - 1)
(side, row, column + 1)
(side, row - 1, column - 1)

这使您可以轻松地引用细分三角形网格中的三角形，而无需显式存储邻接信息。

问题在于如何将其组织成二十面体。计算对相邻三角形的引用后，您需要验证新的引用是否在边的边界内：

int rows = 1 << subdivision_count;
if(row >= rows)
{
    // compute (side, row, column) in adjacent side of icosahedron to B-C edge
}
else if(column < 0)
{
    // compute (side, row, column) in adjacent side of icosahedron to A-B edge
}
else if(column >= ((row * 2) + 1))
{
    // compute (side, row, column) in adjacent side of icosahedron to A-C edge
}

您必须存储每条边的邻接信息以及边的类型（AB、BC、AC）。

您必须找出 9 种不同的可能映射，每种映射对应一种边缘类型组合。例如，如果相邻三角形与AC边相交，并且该边与相邻边的AB边相匹配，则

side = adjacent side (from table)
row = row
column = column - ((row * 2) + 1)

ETC

在某些方面，这是一种更复杂的方法，但在其他方面则更简单。这一切的优点是：

• 无需存储各个三角形的邻接信息，仅存储二十面体边的邻接信息
• 如果您存储每条边的 A、B、C 的 3D 位置，则可以为给定（边、行、列）参考的三角形计算 3D 三角形坐标，因此也无需为每个三角形存储这些位置