Самое быстрое 3D обнаружение столкновений между двумя ориентированными ограничивающими рамками (OBB)

10

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

Я собирался сделать столкновение, используя дерево. Создайте AABB для широкофазы, затем, если это проходит проверку, сталкивается ли каждый OBB в дереве с другим деревом.

Я нашел несколько вещей в Интернете, но я не мог понять их полностью. Что я прошу, так это веб-сайт или ресурс, который хорошо объясняет столкновения 3D OBB?

Я узнал, что GJK быстрее, чем SAT, и кажется, что он может сказать мне, как далеко ящики проникают друг в друга. Я нашел кое-что из GJK, но они не были коробками; вместо этого, более сложные и запутанные вещи.

Я просто хочу иметь возможность сделать OBB из 3 векторов: центр, размер и вращение каждой оси. Тогда сможете проверить столкновения с ними. Заранее спасибо за все, что вы публикуете.

java collision-detection lwjgl andrew3ds
источник

Вы уверены, что вам нужны ограничительные коробки? Если у вас есть дерево костей, и у вас есть центры и приблизительное представление об объеме каждой кости, ограничивающие сферы легче и намного быстрее реализовать.

johnwbyrd

0

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

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

Стив Н
источник

0

Вот фактический рабочий пример AABB, который прямо из моего игрового движка:

using System;
using OpenTK;
using OpenTK.Graphics.OpenGL;

namespace GrimoireEngine.Framework.Maths
{
    public struct BoundingBox : IEquatable<BoundingBox>
    {
        public Vector3 Min;
        public Vector3 Max;

        public const int CornerCount = 8;

        public static Vector3 MaxVector3
        {
            get
            {
                return new Vector3(float.MaxValue);
            }
        }

        public static Vector3 MinVector3
        {
            get
            {
                return new Vector3(float.MinValue);
            }
        }

        public static BoundingBox Identity
        {
            get
            {
                return new BoundingBox(Vector3.Zero, Vector3.One);
            }
        }

        public static BoundingBox Zero
        {
            get
            {
                return new BoundingBox();
            }
        }

        public BoundingBox(Vector3 min, Vector3 max)
        {
            Min = min;
            Max = max;
        }

        public BoundingBox(
            float minX, float minY, float minZ,
            float maxX, float maxY, float maxZ)
            : this(
                new Vector3(minX, minY, minZ),
                new Vector3(maxX, maxY, maxZ))
        { }

        public bool Collides(BoundingBox box)
        {
            if (box.Max.X < Min.X
                || box.Min.X > Max.X
                || box.Max.Y < Min.Y
                || box.Min.Y > Max.Y
                || box.Max.Z < Min.Z
                || box.Min.Z > Max.Z)
            {
                return false;
            }
            if (box.Min.X >= Min.X
                && box.Max.X <= Max.X
                && box.Min.Y >= Min.Y
                && box.Max.Y <= Max.Y
                && box.Min.Z >= Min.Z
                && box.Max.Z <= Max.Z)
            {
                return true;
            }
            return true;
        }

        public ContainmentType Contains(BoundingBox box)
        {
            if (box.Max.X < Min.X
                || box.Min.X > Max.X
                || box.Max.Y < Min.Y
                || box.Min.Y > Max.Y
                || box.Max.Z < Min.Z
                || box.Min.Z > Max.Z)
            {
                return ContainmentType.Disjoint;
            }
            if (box.Min.X >= Min.X
                && box.Max.X <= Max.X
                && box.Min.Y >= Min.Y
                && box.Max.Y <= Max.Y
                && box.Min.Z >= Min.Z
                && box.Max.Z <= Max.Z)
            {
                return ContainmentType.Contains;
            }
            return ContainmentType.Intersects;
        }

        public bool Collides(BoundingFrustum frustum)
        {
            int i;
            bool contained;
            Vector3[] corners = frustum.GetCorners();
            for (i = 0; i < corners.Length; i++)
            {
                if (corners[i].X < Min.X
                    || corners[i].X > Max.X
                    || corners[i].Y < Min.Y
                    || corners[i].Y > Max.Y
                    || corners[i].Z < Min.Z
                    || corners[i].Z > Max.Z)
                {
                    contained = false;
                }
                else if (corners[i].X == Min.X
                         || corners[i].X == Max.X
                         || corners[i].Y == Min.Y
                         || corners[i].Y == Max.Y
                         || corners[i].Z == Min.Z
                         || corners[i].Z == Max.Z)
                {
                    contained = true;
                }
                else
                {
                    contained = true;
                }
                if (contained == false)
                {
                    break;
                }
            }
            if (i == corners.Length)
            {
                return true;
            }
            if (i != 0)
            {
                return true;
            }
            i++;
            for (; i < corners.Length; i++)
            {
                if (corners[i].X < Min.X
                    || corners[i].X > Max.X
                    || corners[i].Y < Min.Y
                    || corners[i].Y > Max.Y
                    || corners[i].Z < Min.Z
                    || corners[i].Z > Max.Z)
                {
                    contained = false;
                }
                else if (corners[i].X == Min.X
                         || corners[i].X == Max.X
                         || corners[i].Y == Min.Y
                         || corners[i].Y == Max.Y
                         || corners[i].Z == Min.Z
                         || corners[i].Z == Max.Z)
                {
                    contained = true;
                }
                else
                {
                    contained = true;
                }
                if (contained != true)
                {
                    return true;
                }
            }
            return true;
        }

        public ContainmentType Contains(BoundingFrustum frustum)
        {
            int i;
            ContainmentType contained;
            Vector3[] corners = frustum.GetCorners();
            for (i = 0; i < corners.Length; i++)
            {
                if (corners[i].X < Min.X
                    || corners[i].X > Max.X
                    || corners[i].Y < Min.Y
                    || corners[i].Y > Max.Y
                    || corners[i].Z < Min.Z
                    || corners[i].Z > Max.Z)
                {
                    contained = ContainmentType.Disjoint;
                }
                else if (corners[i].X == Min.X
                         || corners[i].X == Max.X
                         || corners[i].Y == Min.Y
                         || corners[i].Y == Max.Y
                         || corners[i].Z == Min.Z
                         || corners[i].Z == Max.Z)
                {
                    contained = ContainmentType.Intersects;
                }
                else
                {
                    contained = ContainmentType.Contains;
                }
                if (contained == ContainmentType.Disjoint)
                {
                    break;
                }
            }
            if (i == corners.Length)
            {
                return ContainmentType.Contains;
            }
            if (i != 0)
            {
                return ContainmentType.Intersects;
            }
            i++;
            for (; i < corners.Length; i++)
            {
                if (corners[i].X < Min.X
                    || corners[i].X > Max.X
                    || corners[i].Y < Min.Y
                    || corners[i].Y > Max.Y
                    || corners[i].Z < Min.Z
                    || corners[i].Z > Max.Z)
                {
                    contained = ContainmentType.Disjoint;
                }
                else if (corners[i].X == Min.X
                         || corners[i].X == Max.X
                         || corners[i].Y == Min.Y
                         || corners[i].Y == Max.Y
                         || corners[i].Z == Min.Z
                         || corners[i].Z == Max.Z)
                {
                    contained = ContainmentType.Intersects;
                }
                else
                {
                    contained = ContainmentType.Contains;
                }
                if (contained != ContainmentType.Contains)
                {
                    return ContainmentType.Intersects;
                }
            }
            return ContainmentType.Contains;
        }

        public bool Collides(BoundingSphere sphere)
        {
            if (sphere.Center.X - Min.X >= sphere.Radius
                && sphere.Center.Y - Min.Y >= sphere.Radius
                && sphere.Center.Z - Min.Z >= sphere.Radius
                && Max.X - sphere.Center.X >= sphere.Radius
                && Max.Y - sphere.Center.Y >= sphere.Radius
                && Max.Z - sphere.Center.Z >= sphere.Radius)
            {
                return true;
            }
            double dmin = 0;
            double e = sphere.Center.X - Min.X;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return false;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.X - Max.X;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return false;
                    }
                    dmin += e * e;
                }
            }
            e = sphere.Center.Y - Min.Y;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return false;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.Y - Max.Y;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return false;
                    }
                    dmin += e * e;
                }
            }
            e = sphere.Center.Z - Min.Z;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return false;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.Z - Max.Z;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return false;
                    }
                    dmin += e * e;
                }
            }
            return dmin <= sphere.Radius * sphere.Radius;
        }

        public ContainmentType Contains(BoundingSphere sphere)
        {
            if (sphere.Center.X - Min.X >= sphere.Radius
                && sphere.Center.Y - Min.Y >= sphere.Radius
                && sphere.Center.Z - Min.Z >= sphere.Radius
                && Max.X - sphere.Center.X >= sphere.Radius
                && Max.Y - sphere.Center.Y >= sphere.Radius
                && Max.Z - sphere.Center.Z >= sphere.Radius)
            {
                return ContainmentType.Contains;
            }
            double dmin = 0;
            double e = sphere.Center.X - Min.X;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return ContainmentType.Disjoint;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.X - Max.X;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return ContainmentType.Disjoint;
                    }
                    dmin += e * e;
                }
            }
            e = sphere.Center.Y - Min.Y;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return ContainmentType.Disjoint;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.Y - Max.Y;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return ContainmentType.Disjoint;
                    }
                    dmin += e * e;
                }
            }
            e = sphere.Center.Z - Min.Z;
            if (e < 0)
            {
                if (e < -sphere.Radius)
                {
                    return ContainmentType.Disjoint;
                }
                dmin += e * e;
            }
            else
            {
                e = sphere.Center.Z - Max.Z;
                if (e > 0)
                {
                    if (e > sphere.Radius)
                    {
                        return ContainmentType.Disjoint;
                    }
                    dmin += e * e;
                }
            }
            return dmin <= sphere.Radius * sphere.Radius ? ContainmentType.Intersects : ContainmentType.Disjoint;
        }

        public bool Collides(Vector3 point)
        {
            if (point.X < Min.X
                || point.X > Max.X
                || point.Y < Min.Y
                || point.Y > Max.Y
                || point.Z < Min.Z
                || point.Z > Max.Z)
            {
                return false;
            }
            if (point.X == Min.X
                || point.X == Max.X
                || point.Y == Min.Y
                || point.Y == Max.Y
                || point.Z == Min.Z
                || point.Z == Max.Z)
            {
                return true;
            }
            return true;
        }

        public ContainmentType Contains(Vector3 point)
        {
            ContainmentType result;
            if (point.X < Min.X
                || point.X > Max.X
                || point.Y < Min.Y
                || point.Y > Max.Y
                || point.Z < Min.Z
                || point.Z > Max.Z)
            {
                result = ContainmentType.Disjoint;
            }
            else if (point.X == Min.X
                     || point.X == Max.X
                     || point.Y == Min.Y
                     || point.Y == Max.Y
                     || point.Z == Min.Z
                     || point.Z == Max.Z)
            {
                result = ContainmentType.Intersects;
            }
            else
            {
                result = ContainmentType.Contains;
            }
            return result;
        }

        public bool Equals(BoundingBox other)
        {
            return (Min == other.Min) && (Max == other.Max);
        }

        public override bool Equals(object obj)
        {
            return (obj is BoundingBox) && Equals((BoundingBox)obj);
        }

        public Vector3[] GetCorners()
        {
            return new[] {
                new Vector3(Min.X, Max.Y, Max.Z),
                new Vector3(Max.X, Max.Y, Max.Z),
                new Vector3(Max.X, Min.Y, Max.Z),
                new Vector3(Min.X, Min.Y, Max.Z),
                new Vector3(Min.X, Max.Y, Min.Z),
                new Vector3(Max.X, Max.Y, Min.Z),
                new Vector3(Max.X, Min.Y, Min.Z),
                new Vector3(Min.X, Min.Y, Min.Z)
            };
        }

        public override int GetHashCode()
        {
            return Min.GetHashCode() + Max.GetHashCode();
        }

        public bool Intersects(BoundingBox box)
        {
            if ((Max.X >= box.Min.X) && (Min.X <= box.Max.X))
            {
                if ((Max.Y < box.Min.Y) || (Min.Y > box.Max.Y))
                {
                    return false;
                }
                return (Max.Z >= box.Min.Z) && (Min.Z <= box.Max.Z);
            }
            return false;
        }

        public bool Intersects(BoundingFrustum frustum)
        {
            return frustum.Intersects(this);
        }

        public bool Intersects(BoundingSphere sphere)
        {
            if (sphere.Center.X - Min.X > sphere.Radius
                && sphere.Center.Y - Min.Y > sphere.Radius
                && sphere.Center.Z - Min.Z > sphere.Radius
                && Max.X - sphere.Center.X > sphere.Radius
                && Max.Y - sphere.Center.Y > sphere.Radius
                && Max.Z - sphere.Center.Z > sphere.Radius)
            {
                return true;
            }
            double dmin = 0;
            if (sphere.Center.X - Min.X <= sphere.Radius)
            {
                dmin += (sphere.Center.X - Min.X) * (sphere.Center.X - Min.X);
            }
            else if (Max.X - sphere.Center.X <= sphere.Radius)
            {
                dmin += (sphere.Center.X - Max.X) * (sphere.Center.X - Max.X);
            }
            if (sphere.Center.Y - Min.Y <= sphere.Radius)
            {
                dmin += (sphere.Center.Y - Min.Y) * (sphere.Center.Y - Min.Y);
            }
            else if (Max.Y - sphere.Center.Y <= sphere.Radius)
            {
                dmin += (sphere.Center.Y - Max.Y) * (sphere.Center.Y - Max.Y);
            }
            if (sphere.Center.Z - Min.Z <= sphere.Radius)
            {
                dmin += (sphere.Center.Z - Min.Z) * (sphere.Center.Z - Min.Z);
            }
            else if (Max.Z - sphere.Center.Z <= sphere.Radius)
            {
                dmin += (sphere.Center.Z - Max.Z) * (sphere.Center.Z - Max.Z);
            }
            return dmin <= sphere.Radius * sphere.Radius;
        }

        public PlaneIntersectionType Intersects(Plane plane)
        {
            Vector3 positiveVertex;
            Vector3 negativeVertex;
            if (plane.Normal.X >= 0)
            {
                positiveVertex.X = Max.X;
                negativeVertex.X = Min.X;
            }
            else
            {
                positiveVertex.X = Min.X;
                negativeVertex.X = Max.X;
            }
            if (plane.Normal.Y >= 0)
            {
                positiveVertex.Y = Max.Y;
                negativeVertex.Y = Min.Y;
            }
            else
            {
                positiveVertex.Y = Min.Y;
                negativeVertex.Y = Max.Y;
            }
            if (plane.Normal.Z >= 0)
            {
                positiveVertex.Z = Max.Z;
                negativeVertex.Z = Min.Z;
            }
            else
            {
                positiveVertex.Z = Min.Z;
                negativeVertex.Z = Max.Z;
            }
            float distance = plane.Normal.X * negativeVertex.X + plane.Normal.Y * negativeVertex.Y + plane.Normal.Z * negativeVertex.Z + plane.D;
            if (distance > 0)
            {
                return PlaneIntersectionType.Front;
            }
            distance = plane.Normal.X * positiveVertex.X + plane.Normal.Y * positiveVertex.Y + plane.Normal.Z * positiveVertex.Z + plane.D;
            if (distance < 0)
            {
                return PlaneIntersectionType.Back;
            }
            return PlaneIntersectionType.Intersecting;
        }

        public float? Intersects(Ray ray)
        {
            return ray.Intersects(this);
        }

        public static bool operator ==(BoundingBox a, BoundingBox b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(BoundingBox a, BoundingBox b)
        {
            return !a.Equals(b);
        }

        public override string ToString()
        {
            return "{{Min:" + Min + " Max:" + Max + "}}";
        }

        public void DrawImmediate()
        {
            GL.Begin(PrimitiveType.LineLoop);
            GL.Vertex3(Max.X, Max.Y, Min.Z);
            GL.Vertex3(Min.X, Max.Y, Min.Z);
            GL.Vertex3(Min.X, Min.Y, Min.Z);
            GL.Vertex3(Max.X, Min.Y, Min.Z);
            GL.End();
            GL.Begin(PrimitiveType.LineLoop);
            GL.Vertex3(Max.X, Min.Y, Max.Z);
            GL.Vertex3(Max.X, Max.Y, Max.Z);
            GL.Vertex3(Min.X, Max.Y, Max.Z);
            GL.Vertex3(Min.X, Min.Y, Max.Z);
            GL.End();
            GL.Begin(PrimitiveType.LineLoop);
            GL.Vertex3(Max.X, Max.Y, Min.Z);
            GL.Vertex3(Max.X, Max.Y, Max.Z);
            GL.Vertex3(Min.X, Max.Y, Max.Z);
            GL.Vertex3(Min.X, Max.Y, Min.Z);
            GL.End();
            GL.Begin(PrimitiveType.LineLoop);
            GL.Vertex3(Max.X, Min.Y, Max.Z);
            GL.Vertex3(Min.X, Min.Y, Max.Z);
            GL.Vertex3(Min.X, Min.Y, Min.Z);
            GL.Vertex3(Max.X, Min.Y, Min.Z);
            GL.End();
        }
    }
}

Просто удалите другие методы типа Bounding.

Krythic
источник

3

Это не похоже на OOB для меня, но AABB, который, кажется, не то, что искал OP?

Tyyppi_77

@ Tyyppi_77 Заголовок вопроса гласит «Алгоритм быстрой границы». Это проблема с неоднозначными вопросами.

Krythic

3

Похоже, что вопросительный орган довольно четко указывает на то, что OP спрашивает о OOB: «Я просто хочу иметь возможность сделать OBB».

Tyyppi_77

-2

Молли Ракет навсегда твой друг.

http://mollyrocket.com/849

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

Возможно, вы думаете о запросе коллизий Scene Graph? Где вы проверяете, входит ли объект в QuadTree или Octree, и вы быстро перестраиваете свой график.

moonshineTheleocat
источник

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

andrew3ds

1

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

MichaelHouse

Ой. Хитбокс - это то, что вы хотели. Хит-боксы - это не обязательно деревья, и не совсем AAB. Это в основном невидимые сетки столкновений, прикрепленные к костям. Библиотека физики, которую вы использовали ранее, может легко помочь вам в этом. Но да, GTK все еще может работать довольно хорошо в такой системе. Особенно, если вы хотите знать, что сделал, что.

СамогонТелеокат

Самое быстрое 3D обнаружение столкновений между двумя ориентированными ограничивающими рамками (OBB)

Ответы: