为四球面边确定四叉树邻居的有效方法

Question

我一直在努力优化如何在四元球体的顶面和底面中查找四元树面的邻居以及其他面的邻居。我尝试了几种方法来确定邻居，最新的方法提高了查找速度，但我想知道是否有更好的

方法1:

保留所有四边形使用的所有顶点的所有用户的查找表，然后，对于每个四边形，查找与原始四边形共享边顶点的非祖先的任何其他四边形(减去角顶点，因为这些顶点由多个非邻居共享(。这对于数量较少的细分和顶点非常有效，但随着细分和顶点数量的增加，性能会变得更差。请参阅此实现的示例：https://github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104

方法2:

保留每个细分级别的所有四边形的查找表，按级别进行索引，然后对于每个四边形，查找同一级别或少一级别(父级别(的任何其他非祖先四边形，并检查它们的边顶点以查看它们是否与原始四边形的边顶点匹配。这比方法1效果更好，但如果细分级别太深，仍然会受到影响。这看起来像下面的代码片段：

public Quad FindNeighbor(Quad quad, EdgeType edge)
{
Vector3[] edgeVerts = quad.GetWorldVerts(quad.GetEdgeVerts(edge));
int level = quad.GetLevel(); // neighbors can only be equal or 1 lower level
List<Quad> potentialNeighbors = Quads[level].Where(n => n != quad).ToList();
if (potentialNeighbors.Any())
{
foreach (Quad potentialNeighbor in potentialNeighbors)
{
var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
if (topEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
if (bottomEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
if (leftEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
if (rightEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
}
}
if (level > 0)
{
// if we made it this far we haven't found a neighbor yet so try 1 level lower Quads
potentialNeighbors = Quads[level - 1].Where(n => n != quad.GetParent()).ToList();
if (potentialNeighbors.Any())
{
foreach (Quad potentialNeighbor in potentialNeighbors)
{
var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
if (topEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
if (bottomEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
if (leftEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
if (rightEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
}
}
}
return null;
}

有没有人对此有经验，并愿意分享优化查找的其他方法？提前谢谢。

Answer 1

由于这篇文章没有收到任何回复，我最终所做的是根据一些基本规则分配兄弟邻居，然后对于非兄弟邻居，我找到父四元组，让他们的邻居孩子，看看他们中是否有人与这个四元组共享边缘

private void AddNeighbors()
{
switch (QuadType)
{
case QuadType.BottomLeft:
// add siblings
AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });
// add non-siblings
AddNeighbor(EdgeType.Bottom, () =>
{
return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
});
AddNeighbor(EdgeType.Left, () =>
{
return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
});
break;
case QuadType.BottomRight:
// add siblings
AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });
// add non-siblings
AddNeighbor(EdgeType.Bottom, () =>
{
return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
});
AddNeighbor(EdgeType.Right, () =>
{
return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
});
break;
case QuadType.TopLeft:
// add siblings
AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });
// add non-siblings
AddNeighbor(EdgeType.Top, () =>
{
return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
});
AddNeighbor(EdgeType.Left, () =>
{
return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
});
break;
case QuadType.TopRight:
// add siblings
AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });
// add non-siblings
AddNeighbor(EdgeType.Top, () =>
{
return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
});
AddNeighbor(EdgeType.Right, () =>
{
return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
});
break;
}
}

这似乎工作得很快，因为所有兄弟邻居都是直接分配的，并且非兄弟邻居的定位仅限于在4个四边形的4个边上迭代。这是HasSharedEdge方法：

public bool HasSharedEdge(EdgeType edge, Quad quad)
{
var topLeft = quad.ToWorldVert(quad.TopLeft);
var topRight = quad.ToWorldVert(quad.TopRight);
var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
var bottomRight = quad.ToWorldVert(quad.BottomRight);
// shared Top edge
if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
{
return true;
}
// shared Bottom edge
if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
{
return true;
}
// shared Left edge
if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
{
return true;
}
// shared Right edge
if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
{
return true;
}
return false;
}

也许这可以帮助未来的其他人