эффективный способ определения соседей Quad Tree для граней Quad Sphere Face? - PullRequest
Новая
       27

эффективный способ определения соседей Quad Tree для граней Quad Sphere Face?

0 голосов
/ 20 ноября 2018

Я пытался оптимизировать то, как я ищу соседей для граней Дерева Четырех в верхних и нижних гранях моей Квадратной Сферы с остальными гранями.Я попробовал несколько способов определить соседей, где последний улучшил скорость поиска, но мне интересно, есть ли что-нибудь лучше

Метод 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;
}

Есть ли кто-нибудь, кто имеет опыт с этим и готов поделиться некоторыми другими средствами оптимизации поиска?Заранее спасибо.

1 Ответ

0 голосов
/ 23 ноября 2018

То, что я в итоге сделал, так как этот пост не получил никаких ответов, - это назначение соседей по сестрам на основе некоторых базовых правил, а затем для соседей, не являющихся братьями и сестрами, я нахожу родительский квад, получаю их соседних детей ипосмотрим, разделяет ли кто-либо из них ребро с этим квадом 

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

Может быть, это может помочь кому-то еще в будущем

...