我一直在尝试优化如何在四边形球体的顶面和底面中查找四叉树面与其余面的邻居。我尝试了几种方法来确定邻居，最新的方法提高了查找速度，但我想知道是否有更好的方法
方法一：
保留所有四边形使用的所有顶点的所有用户的查找表，然后，对于每个四边形，查找不是与原始四边形共享边顶点的祖先的任何其他四边形（减去角顶点，因为它们被多个共享，非邻居）。这对于少量细分和顶点非常有效，但随着每个细分和顶点的增加，性能变得更糟。请参阅此实现的示例：https : //github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104
方法二：
保留每个细分级别的所有四边形的查找表，按级别索引，然后对于每个四边形，找到相同级别或低一级（父级）的任何其他不是祖先的四边形，并检查它们的边缘顶点以查看它们是否与原始 Quad 的边缘顶点匹配。这比方法 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;
}
有没有人有这方面的经验并愿意分享一些其他优化查找的方法？提前致谢。
我最终做了什么，因为这篇文章没有收到任何回复，是根据一些基本规则分配兄弟邻居，然后对于非兄弟邻居，我找到父四边形，找到他们的邻居孩子，看看是否有他们中的一个与这个四边形共享一条边
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;
}
也许这可以在未来帮助其他人
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句