Пересечение двух OBB

[AndreyMust19]

Нужно выяснить пересекаются ли 2 параллелепипеда. Их глобальные параметры:
* Координаты центра (Vector3)
* Повороты (Quaternion)
* Размер в виде вектора-диагонали (Vector3)
Вставить коллайдеры и проверить столкновение - не подходит, т. к. проверка на пересечения должна выполняться в редакторе, а не во время игры.

Нашел несколько ссылок и кода, но они не подходят.
http://gdlinks.hut.ru/cdfaq/obb.shtml
Здесь используется матрица поворотов 3x3 (а не кватернион) неясно относительно какой оси. Не описан метод Transpose.

http://www.gamedev.ru/articles/?id=30109
Обнаружение столкновений 2-х движущихся OBB (а мне нужно статичных). Поворот параллелепипеда, видимо, опять матрицей поворота (POINT3D Orientation[3]), но этот Orientation нигде в коде не используются.

Хотелось бы найти подходящие методы Unity-классов или код, использующий этот кватернион или углы Эйлера.
Определять область пересечения (точка, линия, плоскость) - не надо. Только сам факт.

[Zaicheg]

С геометрией у меня туго, но для прямоугольных параллелепипедов наверное подойдёт простой Bounds.Intersects.

[Ert Donuell]

Делаете проекции на три плоскости и проверяете на каждой пересечение.

[AndreyMust19]

Zaicheg

подойдёт простой Bounds.Intersects.

А я думал это свойство класса Collider, а не отдельный класс. А оказалось все намного проще.
Вот только подозрительно что среди полей класса Bounds только center и size, а rotation - нет. Сдается что метод Bounds.Intersect не учитывает поворот "ящика", а проверяет пересечение AABB (ящик с ребрами, параллельными осям X, Y, Z).

http://unity3d.com/support/documentatio ... ounds.html
Ну точно:

An axis-aligned bounding box, or AABB

Скрытый текст: показать

Кстати, метод Gismoz.DrawWireCube тоже рисует AABB. Придется рисовать ящик линиями.

Ert Donuell

Делаете проекции на три плоскости и проверяете на каждой пересечение.

Такой алгоритм и используется. Только в каждом найденном мной примере кода поворот OBB хранится в матрице 3x3, а в Unity доступен только Кватернион и Углы Эйлера. А в матрице синусы/косинусы.

[seaman]

а в Unity доступен только Кватернион и Углы Эйлера

Может я что не понял, но вот это что?:
http://unity3d.com/support/documentation/ScriptReference/Matrix4x4.html

[AndreyMust19]

Нет, кажется это не та структура. Это матрица 4-го порядка, а нужна третьего. Если даже это искомая структура, то почему не написано для чего используется 4-ый столбец и 4-ая строка.

Вот если бы вы нашли метод, переводящий Quaternion в Matrix3x3... уже не надо.

[seaman]

Четвертая строка (или столбец - в DX и OGL они меняются местами) - определяет проекционное преобразование. Вообще Вам лучше почитать что-то по математике, например тут:
http://www.gamedev.ru/code/articles/faq_matrix_quat
По конкретному вопросу:
http://www.gamedev.ru/code/articles/faq_matrix_quat?page=5#kak_mne_perevesti_kvaternion_v_m

[AndreyMust19]

По конкретному вопросу:
http://www.gamedev.ru/code/articles/faq ... ernion_v_m

Спасибо что потрудились и нашли, но

Вот если бы вы нашли метод, переводящий Quaternion в Matrix3x3... уже не надо.

Зато код проверил.

[AndreyMust19]

Наконец-то написал. Осталось привести все в нормальный вид, убрать мусор и можно тестировать.

Испробовал алгоритм с матрицей поворотов - врет. Вместо этого нахожу координаты углов OBB и по осям проверяю их пересечение.

[AndreyMust19]

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

using UnityEngine;
using System.Collections;

public class OBB : MonoBehaviour {

        // исходные параметры
        readonly public Vector3 pos;
        readonly public Quaternion rot;
        readonly public Vector3 size;
        // производные параметры
        readonly public Vector3[] bounds = new Vector3[8]; // углы
        readonly public float len; // длина диагонали
       
        // ПЕРЕЧИСЛЕНИЯ
        public enum obb_axis { x, y, z };
        // грани по осям (': uint' - бестолку, Unity пофигу на указаный класс перечисления)
        enum face {
                PosX, NegX, PosY, NegY, PosZ, NegZ
        };
        // грани по сторонам редактора
        enum face_dir {
                right, left, top, bottom, forward, back
        };

       
       
        protected OBB(Transform ts, Vector3 sizeValue) {
                pos = ts.position; rot = ts.rotation;
                bounds = EvaluateBoundsOBB(ts, sizeValue);
                size = sizeValue;
                len = sizeValue.magnitude;
        }
       
       
        // вычислить координаты углов параллелепипеда
        /*
                1 - Transform объекта,
                2 - Vector3 с размерами по направляющим осям x, y, z
        */
public static Vector3[] EvaluateBoundsOBB(Transform trans, Vector3 sizeValue) {
                Vector3[] b = new Vector3[8];
                // вектора направл. осей осей
                Vector3 x = trans.right, y = trans.up, z = trans.forward;
                // пихаем в них половины векторов-размеров
                x *= 0.5f*sizeValue.x;
                y *= 0.5f*sizeValue.y;
                z *= 0.5f*sizeValue.z;
                // верхняя грань
                b[0] = -x + y + z;
                b[1] = -x + y - z;
                b[2] = x + y - z;
                b[3] = x + y + z;
                // нижняя грань
                b[4] = -x - y + z;
                b[5] = -x - y - z;
                b[6] = x - y - z;
                b[7] = x - y + z;
                return b;
        }      


static public bool TestIntersectionAxis(OBB obb1, OBB obb2, obb_axis name_axis) {
        // [F,A] номера углов A, принадлежащих F грани
        uint[,] angles = new uint[6,4] { // const
                { 2,3,6,7 }, { 0,1,4,5 },
                { 0,1,2,3 }, { 4,5,6,7 },
                { 0,3,4,7 }, { 0,1,4,5 }
        };
        int axis = (int)name_axis; // переводим имя оси в номер
        // предпологаем что первый OBB левее по оси, чем второй
        if (obb1.pos[axis] > obb2.pos[axis]) {
                // Мы ошиблись. Меняем их местами
                OBB obb_temp = obb1;
                obb1 = obb2; obb2 = obb_temp;
        }
        // ВЫЯСНЯЕМ - ЕСТЬ ЛИ ПЕРЕСЕЧЕНИЕ ПО ОСИ name_axis
        uint i = 0;
        // запоминаем номера граней в зависимости от оси
        uint face1 = 0, face2 = 0;
        if (axis == 0 /*X*/) { face1 = (uint)face.PosX /*0*/; face2 = (uint)face.NegX /*1*/; };
        if (axis == 1 /*Y*/) { face1 = (uint)face.PosY /*2*/; face2 = (uint)face.NegY /*3*/; };
        if (axis == 2 /*Z*/) { face1 = (uint)face.PosZ /*4*/; face2 = (uint)face.NegZ /*5*/; };
        // ищем самые правые углы для 1-ого OBB и самые левые - для второго OBB
        // первые углы
        float close_angle1, close_angle2;
        close_angle1 = obb1.bounds[angles[face1,i]][axis];
        close_angle2 = obb2.bounds[angles[face2,i]][axis];
        // остальные 3
        for (i = 1; i < 4; i++) {
                float new_angle1 = obb1.bounds[angles[face1,i]][axis];
                float new_angle2 = obb2.bounds[angles[face2,i]][axis];
                if (new_angle1 > close_angle1) close_angle1 = new_angle1;
                if (new_angle2 < close_angle2) close_angle2 = new_angle2;
        }
        // если крайний угол 2-го OBB левее, чем у 1-го, значит есть пересечение
        if ((obb1.pos[axis]+close_angle1) > (obb2.pos[axis]+close_angle2)) return true;
        return false;
        }
               

        static public bool TestIntersection(OBB obb1, OBB obb2) {
               
                // если расстояние между центрами OBB больше, чем сумма их половин диагоналей, то они по любому не могут пересечься
                if (Vector3.Distance(obb1.pos, obb2.pos) > (0.5f*obb1.len+0.5f*obb2.len)) return false;
               
                if (TestIntersectionAxis(obb1, obb2, obb_axis.x) && TestIntersectionAxis(obb1, obb2, obb_axis.y) && TestIntersectionAxis(obb1, obb2, obb_axis.z)) return true;
                return false;
        }
       

// проверка наложения 2-х зон
static public bool TestIntersection2(OBB obb1, OBB obb2) {
        //WalkZone z1 = this[n1]; WalkZone z2 = this[n2];

        Matrix3x3 A, B;
        A = Convert.QuaternionToMatrix3x3(obb1.rot.x, obb1.rot.y, obb1.rot.z, obb1.rot.w);
        B = Convert.QuaternionToTransposeMatrix3x3(obb2.rot.x, obb2.rot.y, obb2.rot.z, obb2.rot.w);
        // смещение в мировой системе координат
        Vector3 v = obb2.pos - obb1.pos;
        // смещение в системе координат первого OBB
        Vector3 T = A.TransformVector(v);       //A * v;
        // матрица поворота A относительно B
        Matrix3x3 R = A * B;
               
        float ra, rb, t;
        uint i, k;
        float[] a = {obb1.size.x, obb1.size.y, obb1.size.z};
        float[] b = {obb2.size.x, obb2.size.y, obb2.size.z};
        //система координат А
        for( i=0 ; i<3 ; i++ )
        {
                ra = obb1.size[(int)i];
                rb = obb2.size[0]*Mathf.Abs(R[i,0]) + obb2.size[1]*Mathf.Abs(R[i,1]) + obb2.size[2]*Mathf.Abs(R[i,2]);
                t = Mathf.Abs(T[(int)i]);
//Debug.Log(t - (ra+rb));
                if ( t > ra + rb ) return false;
        }
        //система координат B
        for( k=0 ; k<3 ; k++ )
        {
                ra = a[0]*Mathf.Abs(R[0,k]) + a[1]*Mathf.Abs(R[1,k]) + a[2]*Mathf.Abs(R[2,k]);
                rb = b[(int)k];
                t = Mathf.Abs( T[0]*R[0,k] + T[1]*R[1,k] + T[2]*R[2,k] );
//Debug.Log(t - (ra+rb));
                if ( t > (ra + rb) ) return false;
        }
        //9 векторных произведений
        //L = A0 x B0
        ra = a[1]*Mathf.Abs(R[2,0]) + a[2]*Mathf.Abs(R[1,0]);
        rb = b[1]*Mathf.Abs(R[0,2]) + b[2]*Mathf.Abs(R[0,1]);
        t = Mathf.Abs( T[2]*R[1,0] - T[1]*R[2,0] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A0 x B1
        ra = a[1]*Mathf.Abs(R[2,1]) + a[2]*Mathf.Abs(R[1,1]);
        rb = b[0]*Mathf.Abs(R[0,2]) + b[2]*Mathf.Abs(R[0,0]);
        t = Mathf.Abs( T[2]*R[1,1] - T[1]*R[2,1] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;
 
        //L = A0 x B2
        ra = a[1]*Mathf.Abs(R[2,2]) + a[2]*Mathf.Abs(R[1,2]);
        rb = b[0]*Mathf.Abs(R[0,1]) + b[1]*Mathf.Abs(R[0,0]);
        t = Mathf.Abs( T[2]*R[1,2] - T[1]*R[2,2] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A1 x B0
        ra = a[0]*Mathf.Abs(R[2,0]) + a[2]*Mathf.Abs(R[0,0]);
        rb = b[1]*Mathf.Abs(R[1,2]) + b[2]*Mathf.Abs(R[1,1]);
        t = Mathf.Abs( T[0]*R[2,0] - T[2]*R[0,0] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A1 x B1
        ra = a[0]*Mathf.Abs(R[2,1]) + a[2]*Mathf.Abs(R[0,1]);
        rb = b[0]*Mathf.Abs(R[1,2]) + b[2]*Mathf.Abs(R[1,0]);
        t = Mathf.Abs( T[0]*R[2,1] - T[2]*R[0,1] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A1 x B2
        ra = a[0]*Mathf.Abs(R[2,2]) + a[2]*Mathf.Abs(R[0,2]);
        rb = b[0]*Mathf.Abs(R[1,1]) + b[1]*Mathf.Abs(R[1,0]);
        t = Mathf.Abs( T[0]*R[2,2] - T[2]*R[0,2] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A2 x B0
        ra = a[0]*Mathf.Abs(R[1,0]) + a[1]*Mathf.Abs(R[0,0]);
        rb = b[1]*Mathf.Abs(R[2,2]) + b[2]*Mathf.Abs(R[2,1]);
        t = Mathf.Abs( T[1]*R[0,0] - T[0]*R[1,0] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A2 x B1
        ra = a[0]*Mathf.Abs(R[1,1]) + a[1]*Mathf.Abs(R[0,1]);
        rb = b[0] *Mathf.Abs(R[2,2]) + b[2]*Mathf.Abs(R[2,0]);
        t = Mathf.Abs( T[1]*R[0,1] - T[0]*R[1,1] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        //L = A2 x B2
        ra = a[0]*Mathf.Abs(R[1,2]) + a[1]*Mathf.Abs(R[0,2]);
        rb = b[0]*Mathf.Abs(R[2,1]) + b[1]*Mathf.Abs(R[2,0]);
        t = Mathf.Abs( T[1]*R[0,2] - T[0]*R[1,2] );
//Debug.Log(t - (ra+rb));
        if ( t > (ra + rb) ) return false;

        return true;
        }
}
 

EvaluateBoundsOBB - вычисляет коор-ты углов относительно центра
TestIntersectionAxis - проверяет пересечение проекций по оси x, y или z
TestIntersection - работает
TestIntersection2 - врет, не пойму почему
Алгоритм для этой функции (с матрицей поворотов) брал отсюда:
http://gdlinks.hut.ru/cdfaq/obb.shtml#howitworks

Вот еще файлы с функциями, исп-ми TestIntersection2:

Convert.cs

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

using UnityEngine;
//using System.Collections;

public class Convert : MonoBehaviour {

       
        public static Matrix3x3 QuaternionToMatrix3x3(float x, float y, float z, float w) {
                Matrix3x3 m = new Matrix3x3();
                float wx, wy, wz, xx, yy, yz, xy, xz, zz;
                xx = x * x;  xy = x * y;  xz = x * z;
                yy = y * y;  yz = y * z;  zz = z * z;
                wx = w * x;  wy = w * y;  wz = w * z;

                m[0,0] = 1.0f - 2*(yy + zz);
                m[1,0] = 2*(xy - wz);
                m[2,0] = 2*(xz + wy);

                m[0,1] = 2*(xy + wz);
                m[1,1] = 1.0f - 2*(xx + zz);
                m[2,1] = 2*(yz - wx);

                m[0,2] = 2*(xz - wy);
                m[1,2] = 2*(yz + wx);
                m[2,2] = 1.0f - 2*(xx + yy);
                return m;
    }

       
        public static Matrix3x3 QuaternionToTransposeMatrix3x3(float x, float y, float z, float w) {
                Matrix3x3 m = new Matrix3x3();
                float wx, wy, wz, xx, yy, yz, xy, xz, zz;
                xx = x * x;  xy = x * y;  xz = x * z;
                yy = y * y;  yz = y * z;  zz = z * z;
                wx = w * x;  wy = w * y;  wz = w * z;

                m[0,0] = 1.0f - 2*(yy + zz);
                m[0,1] = 2*(xy - wz);
                m[0,2] = 2*(xz + wy);

                m[1,0] = 2*(xy + wz);
                m[1,1] = 1.0f - 2*(xx + zz);
                m[1,2] = 2*(yz - wx);

                m[2,0] = 2*(xz - wy);
                m[2,1] = 2*(yz + wx);
                m[2,2] = 1.0f - 2*(xx + yy);
                return m;
    }
}

Matrix3x3.cs

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

using UnityEngine;
/*
        Этот класс взят из Pathfinding-AStar 2.95
        LoadZero - записать нулевую матрицу
        LoadIdentity - записывает единичную матрицу
        TransformVector - перемножение матрицы на вектор
        * - перемножение 2-х матриц
*/


public class Matrix3x3
        {
                private static readonly float[,] MatrixZero = new float[,] {
                        {0.0f, 0.0f, 0.0f},
                        {0.0f, 0.0f, 0.0f},
                        {0.0f, 0.0f, 0.0f}
                };
                private static readonly float[,] MatrixIdentify = new float[,] {
                        {1.0f, 0.0f, 0.0f},
                        {0.0f, 1.0f, 0.0f},
                        {0.0f, 0.0f, 1.0f}
                };
                public float[,] m;
       
                public Matrix3x3()
                {        
                        LoadZero();
                }
               
                public Matrix3x3(float[,] mat) {
                        m = mat;
                }
       
                public float this[uint row, uint col]
                {
                        get {
                                if (row < 4 && col < 4) return m[row,col];
                                return 0.0f;
                        }
                        set {
                                if (row < 4 && col < 4) m[row,col] = value;
                        }
                }
               
                public void LoadZero()
                {
                        m = MatrixZero;
                }

                public void LoadIdentity()
                {
                        m = MatrixIdentify;
                }
               
                public Vector3 TransformVector (Vector3 V)
                {
                        Vector3 vt = new Vector3(0,0,0);
                        vt.x = ( V.x * m[0,0] ) + ( V.y * m[1,0] ) + ( V.z * m[2,0] );
                        vt.y = ( V.x * m[0,1] ) + ( V.y * m[1,1] ) + ( V.z * m[2,1] );
                        vt.z = ( V.x * m[0,2] ) + ( V.y * m[1,2] ) + ( V.z * m[2,2] );
                        return vt;
                }
       
// перемножение матриц
/*
           n
           --
    R  =  \   A x B
    ij     /   rj   ir
           --
                r=1  
n - количество строк/столбцов
*/
                public static Matrix3x3 operator *( Matrix3x3 A, Matrix3x3 B )
                {
                        Matrix3x3 mat = new Matrix3x3();
                        // 1 строка
                        mat.m[0,0] = A.m[0,0] * B.m[0,0] + A.m[1,0] * B.m[0,1] + A.m[2,0] * B.m [0,2];
                        mat.m[0,1] = A.m[0,1] * B.m[0,0] + A.m[1,1] * B.m[0,1] + A.m[2,1] * B.m [0,2];
                        mat.m[0,2] = A.m[0,2] * B.m[0,0] + A.m[1,2] * B.m[0,1] + A.m[2,2] * B.m [0,2];
                        // 2 строка              
                        mat.m[1,0] = A.m[0,0] * B.m[1,0] + A.m[1,0] * B.m[1,1] + A.m[2,0] * B.m [1,2];
                        mat.m[1,1] = A.m[0,1] * B.m[1,0] + A.m[1,1] * B.m[1,1] + A.m[2,1] * B.m [1,2];
                        mat.m[1,2] = A.m[0,2] * B.m[1,0] + A.m[1,2] * B.m[1,1] + A.m[2,2] * B.m [1,2];
                        // 3 строка
                        mat.m[2,0] = A.m[0,0] * B.m[2,0] + A.m[1,0] * B.m[2,1] + A.m[2,0] * B.m [2,2];
                        mat.m[2,1] = A.m[0,1] * B.m[2,0] + A.m[1,1] * B.m[2,1] + A.m[2,1] * B.m [2,2];
                        mat.m[2,2] = A.m[0,2] * B.m[2,0] + A.m[1,2] * B.m[2,1] + A.m[2,2] * B.m [2,2];
                        return mat;
                }
        }

        /*
        // математическое произведение
                private void M3xM3(float[,] m1, float[,] m2, float[,] M) {
                M[0,0] = m1[0,0] * m2[0,0]; M[1,0] = m1[1,0] * m2[1,0]; M[2,0] = m1[2,0] * m2[2,0];
                M[0,1] = m1[0,1] * m2[0,1]; M[1,1] = m1[1,1] * m2[1,1]; M[2,1] = m1[2,1] * m2[2,1];
                M[0,2] = m1[0,2] * m2[0,2]; M[1,2] = m1[1,2] * m2[1,2]; M[2,2] = m1[2,2] * m2[2,2];
        }
        */

По-моему первая реализация уже выигрывает по скорости и объему кода.

[AndreyMust19]

Вы удивитесь, но если проекции двух OBB пересекаются по всем 3-м осям (по X, Y, Z), они все равно могут не пересекаться физически.
Пример - на рисунке:



Выяснил что правельнее проверять проекции не на глобальные оси, а на локальные и их векторные произведения.
И если кто-нибудь посмотрел бы код OBB.cs, то заметил что { 0,1,4,5 } в нем повторяется дважды, а вместо повторения должно стоять { 1,2,5,6 }.

[Neodrop]

Позвольте спросить, а зачем этот вывих мозга?

Можно использовать GeometryUtility.TestPlanesAABB
Это полностью решит задачу. Это нативный, оптимизированный и самый быстрый метод определения попадания чего-либо в коробку (Frustrum - раструб камеры). Построить его плёвая задача, равно как и прикрутить к вашей проблеме.

[AndreyMust19]

Потому что GeometryUtility.TestPlanesAABB, это другое тело.
Способ обнаружения пересечения двух AABB и OBB - отличается.

[Neodrop]

Какая фигура? Какие координаты Plane скормите, такая и будет. Параллелепипед - без всяких проблем. Не стоит говорить не обдумав. Плохая карма однако.