Поиск ориентированной ограничительной рамки для набора трехмерных точек в Unity - PullRequest
0 голосов
/ 11 октября 2019

У меня есть набор трехмерных точек, или фактически маленьких сфер, которые мне нужно заключить в наименьшую возможную трехмерную коробку с помощью Unity 3D.

В случае, когда ограничивающий прямоугольник можно только перемещать и масштабировать, решение достаточно тривиально, вы просто перебираете все точки и инкапсулируете каждую из них. Но мне также нужно найти наилучшую возможную ориентацию для блока.

Итак, чтобы проиллюстрировать проблему в ASCII, приведем базовый 2D-сценарий только с двумя точками:

Y
| * (0,1)
|
|
|
|               * (1,0)
-------------------- X

ИспользованиеИз регулярно растущей ограничительной рамки вы получите очень большую вмещающую коробку, содержащую в основном пустое пространство, тогда как в этом случае мне понадобится очень тонкая коробка, повернутая на 45 градусов вокруг оси Z. По сути, это просто линия, соединяющая две точки.

Я никогда не знаю, сколько точек нужно сгруппировать. И, как уже упоминалось, он должен работать в 3D.

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

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

GameObject go = points[0];
Bounds b = new Bounds(go.transform.position,go.transform.localScale);

for (int i=1;i<points.Count;i++)
{
    go = points[i];
    b.Encapsulate(new Bounds(go.transform.position, go.transform.localScale));
}

GameObject containingBox = Instantiate(boxPrefab);
containingBox.transform.position = b.center;
containingBox.transform.localScale = b.size;
containingBox.transform.rotation= Quaternion.Identity; //How to calculate?

Ответы [ 3 ]

1 голос
/ 12 октября 2019

Эй, я немного искал и нашел довольно мощную библиотеку, которая предлагает то, что вы ищете, более или менее прямолинейно и даже активно поддерживает типы Unity:

geometry3Sharp

Внедрение в проект Unity так же просто, как

  • Загрузите проект как .zip
  • распакуйте папку geometry3Sharp-master в свойAssets папка
  • В Unity под ProjectSettingsPlayerOther SettingsConfigurationScripting Define Symbols insert

    G3_USING_UNITY;
    

    Так же, как объяснено вREADME:

    geometry3Sharp поддерживает прозрачное преобразование с типами Unity. Чтобы включить это, определите G3_USING_UNITY в своем проекте Unity, добавив эту строку в поле «Определение сценариев символов» в настройках проигрывателя.

Затем вы можете просто вычислить краяориентированной ограничительной рамки для данного массива Vector3 точек, таких как:

using UnityEngine;
using g3;

public class Example : MonoBehaviour
{
    // Just for the demo I used Transforms so I can simply move them around in the scene
    public Transform[] transforms;

    private void OnDrawGizmos()
    {
        // First wehave to convert the Unity Vector3 array
        // into the g3 type g3.Vector3d
        var points3d = new Vector3d[transforms.Length];
        for (var i = 0; i < transforms.Length; i++)
        {
            // Thanks to the g3 library implictely casted from UnityEngine.Vector3 to g3.Vector3d
            points3d[i] = transforms[i].position;
        }

        // BOOM MAGIC!!!
        var orientedBoundingBox = new ContOrientedBox3(points3d);

        // Now just convert the information back to Unity Vector3 positions and axis
        // Since g3.Vector3d uses doubles but Unity Vector3 uses floats
        // we have to explicitly cast to Vector3
        var center = (Vector3)orientedBoundingBox.Box.Center;

        var axisX = (Vector3)orientedBoundingBox.Box.AxisX;
        var axisY = (Vector3)orientedBoundingBox.Box.AxisY;
        var axisZ = (Vector3)orientedBoundingBox.Box.AxisZ;
        var extends = (Vector3)orientedBoundingBox.Box.Extent;

        // Now we can simply calculate our 8 vertices of the bounding box
        var A = center - extends.z * axisZ - extends.x * axisX - axisY * extends.y;
        var B = center - extends.z * axisZ + extends.x * axisX - axisY * extends.y;
        var C = center - extends.z * axisZ + extends.x * axisX + axisY * extends.y;
        var D = center - extends.z * axisZ - extends.x * axisX + axisY * extends.y;

        var E = center + extends.z * axisZ - extends.x * axisX - axisY * extends.y;
        var F = center + extends.z * axisZ + extends.x * axisX - axisY * extends.y;
        var G = center + extends.z * axisZ + extends.x * axisX + axisY * extends.y;
        var H = center + extends.z * axisZ - extends.x * axisX + axisY * extends.y;

        // And finally visualize it
        Gizmos.DrawLine(A, B);
        Gizmos.DrawLine(B, C);
        Gizmos.DrawLine(C, D);
        Gizmos.DrawLine(D, A);

        Gizmos.DrawLine(E, F);
        Gizmos.DrawLine(F, G);
        Gizmos.DrawLine(G, H);
        Gizmos.DrawLine(H, E);

        Gizmos.DrawLine(A, E);
        Gizmos.DrawLine(B, F);
        Gizmos.DrawLine(D, H);
        Gizmos.DrawLine(C, G);

        // And Here we ca just be amazed ;)
    }
}

enter image description here


И, конечно, есть вещинапример,

orientedBoundingBox.Box.Contains(Vector3d)

для определения, находится ли данная точка в этом поле.


Только потому, что Рузим спросил:

Конечно, вы можете слегка изменить верхний скрипт напросто используйте фактические вершины сетки:

public MeshFilter[] meshFilters;

private void OnDrawGizmos()
{
    var vertices = new List<Vector3>();
    foreach (var meshFilter in meshFilters)
    {
        // have to multiply the vertices' positions
        // with the lossyScale and add it to the transform.position 
        vertices.AddRange(meshFilter.sharedMesh.vertices.Select(vertex => meshFilter.transform.position + Vector3.Scale(vertex, meshFilter.transform.lossyScale)));
    }

    var points3d = new Vector3d[vertices.Count];

    for (var i = 0; i < vertices.Count; i++)
    {
        points3d[i] = vertices[i];
    }

    // ...
    // From here the code is the same as above

Который выглядит в основном одинаково

enter image description here

0 голосов
/ 12 октября 2019

Мне удалось решить эту проблему с помощью OpenCV для Unity. Я использовал метод minAreaRect, который вычисляет ограничивающий прямоугольник подгонки вокруг точек в 2D (сначала я спроецировал их на плоскость X / Z).

Этот метод удобно возвращает прямоугольник с центральной точкой, углом и шириной / высотой. С этого момента было довольно легко расширить это до 3D-бокса.

0 голосов
/ 11 октября 2019

Не думайте о коробке, а затем попытайтесь ее адаптировать. В этом случае проще создать коробку. Таким образом, точки сначала, а затем поле.

  1. Найдите две точки, наиболее удаленные друг от друга.

enter image description here

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

enter image description here

Создайте остальные точки коробки. В основном, вы рассчитали направления, по которым они пересекают перпендикулярный паралель противоположной точки. Создание граней бокса на основе его вершин.

enter image description here


Я проиллюстрировал это для 2D здесь, но единственное отличие от 3D - это третий угол, различные смещения угла и больше вершин / граней для работы.


РЕДАКТИРОВАТЬ:

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

Иллюстрация Рузима:

enter image description here

Тем не менее, его иллюстрация немного неправильна, поскольку мое решение не выровнено по оси. Вот что будет достигнуто справа, красным или оранжевым, в зависимости от того, какая точка выбрана в качестве вершины:

enter image description here


Лучшее / правильное решение:

При поиске решения, которое дало бы математически совершенную минимальную ограничивающую рамку, я нашел этот другой (C ++) вопрос и ответы на него . Сейчас у меня нет времени, чтобы прочитать все это и воспроизвести решение здесь для Unity / C #, поэтому я только укажу на это. Может быть, я или другой участник смогу отредактировать копию этого позже.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...