确定四边形球面边缘的四边形树邻居的有效方法？

Question

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

方法一：

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

方法二：

查找table每个细分级别的所有四边形，按级别索引，然后对于每个四边形，查找相同级别或少一级（父级）的任何其他四边形't ancestors 并检查它们的边顶点，看看它们是否与原始 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;
}

有没有人有这方面的经验，愿意分享一些其他优化查找的方法？提前致谢。

Answer 1

由于此 post 未收到任何响应，我最终所做的是根据一些基本规则分配同级邻居，然后为 non-sibling 邻居找到parent 四边形，获取他们的邻居 children 并查看它们中是否有任何一个与该四边形共享一条边

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;
    }
}

这似乎工作得很快，因为所有兄弟邻居都是直接分配的，并且 non-sibling 邻居的定位仅限于迭代 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;
}

也许这对以后的其他人有帮助

确定四边形球面边缘的四边形树邻居的有效方法？

efficient way to determine Quad Tree neighbors for Quad Sphere Face edges?

quadtree

unity3d