Search Unity

  1. Improved Prefab workflow (includes Nested Prefabs!), 2D isometric Tilemap and more! Get the 2018.3 Beta now.
    Dismiss Notice
  2. The Unity Pro & Visual Studio Professional Bundle gives you the tools you need to develop faster & collaborate more efficiently. Learn more.
    Dismiss Notice
  3. Let us know a bit about your interests, and if you'd like to become more directly involved. Take our survey!
    Dismiss Notice
  4. Don't miss out on the Unite LA Keynote for the latest information from Unity! Set a reminder!
    Dismiss Notice
  5. Improve your Unity skills with a certified instructor in a private, interactive classroom. Watch the overview now.
    Dismiss Notice
  6. Want to see the most recent patch releases? Take a peek at the patch release page.
    Dismiss Notice

Looking for efficient OBB - AABB 3D Collider Solutions.

Discussion in 'Physics' started by Antypodish, Aug 8, 2018.

  1. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    1,528
    Hi galls and folks.

    I am learning on ECS with Job system and trying to implement simple OBB (Oriented Bounding Box) and AABB (Axis Alligned Bounding Box) collision detection for 3D Boxes. This means, I can not use native Unity Colliders components.

    At the moment, I have written my own script, but it seams is not most performant algorithm. I can collide (intersect) 800 boxes pairs at the same time, with 25-30 fps on single core using OOP. Yet I do wonder, if anybody has any details, on Unity Collision system, to squeeze most of it.

    Or maybe, what should I change, in my scripts. I am sure it can be optimized. Yet not entirely sure how.

    Here is my quite vauge test version of script.
    It dosen't have to be complex.

    Code (CSharp):
    1. using UnityEngine;
    2.  
    3. /// <summary>
    4. /// 3D Box collision
    5. /// </summary>
    6. public class SeprateAxisTheorem : MonoBehaviour {
    7.  
    8.     /// <summary>
    9.     /// AABB - Axis Alligned Bounding Box
    10.     /// </summary>
    11.     Transform tr_cubeAABB ;
    12.  
    13.     /// OBB - Oriented Bounding Box
    14.     Transform tr_cubeOBB ;
    15.  
    16.     // BoxCollider col_cubeAABB ;
    17.     BoxCollider col_cubeOBB ;
    18.  
    19.     public class BoundingsAxis
    20.     {
    21.         public Vector3 V3_min ;
    22.         public Vector3 V3_max ;
    23.     }
    24.  
    25.     // Use this for initialization
    26.     void Start ()
    27.     {
    28.         tr_cubeAABB = this.transform.Find ( "StaticCube" ) ;
    29.         tr_cubeOBB = this.transform.Find ( "DynamicCube" ) ;
    30.  
    31.         BoundingsAxis axisAABB = new BoundingsAxis () ;
    32.         BoundingsAxis axisOBB = new BoundingsAxis () ;
    33.          
    34.         // col_cubeAABB = tr_cubeAABB.GetComponent <BoxCollider> () ;
    35.         col_cubeOBB = tr_cubeOBB.GetComponent <BoxCollider> () ;
    36.  
    37.     }
    38.  
    39.     // Update is called once per frame
    40.     void FixedUpdate ()
    41.     {
    42.         Vector3 [] V3_minMaxAABB = _MinMaxAABB ( tr_cubeAABB ) ;
    43.         Vector3 [] V3_minMaxOBB = _MinMaxOBB ( tr_cubeOBB, col_cubeOBB.bounds ) ;
    44.  
    45.         // Debug.Log ( _AABBCollision3D ( V3_minMaxAABB, V3_minMaxOBB ) ? "1" : "0" ) ;
    46.  
    47.  
    48.         // check first, if Simple AAB2OOB collision occures
    49.         if ( _AABB2AABBCollisionTest ( V3_minMaxAABB, V3_minMaxOBB ) )
    50.         {
    51.  
    52.             Vector3[] aabbCorners = _CornersAABB ( tr_cubeAABB ) ;
    53.             Vector3[] obbCorners = _CornersOBB ( tr_cubeOBB ) ;
    54.  
    55.             // then consider axis rotation in calculations
    56.             bool isColliding = _ABB2OBBCollisionTest ( aabbCorners, obbCorners ) ;
    57.  
    58.             if ( isColliding )
    59.             {
    60.                 // Debug.Log ( "AABB + OBB" ) ;
    61.             }
    62.             else
    63.             {
    64.                 // Debug.Log ( "ABB + AABB" ) ;
    65.             }
    66.         }
    67.  
    68.     }
    69.  
    70.     private Vector3 [] _CornersAABB ( Transform tr )
    71.     {
    72.         //BoxCollider boxCollider = tr.GetComponent <BoxCollider> () ;
    73.         //Bounds bunds = boxCollider.bounds ;
    74.  
    75.         Vector3 [] a_corners = new Vector3 [8] ;
    76.  
    77.         a_corners[0] = tr.position + new Vector3 (-tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ;
    78.         a_corners[1] = tr.position + new Vector3 (tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ;
    79.         a_corners[2] = tr.position + new Vector3 (tr.localScale.x, -tr.localScale.y, tr.localScale.z) * 0.5f ;
    80.         a_corners[3] = tr.position + new Vector3 (-tr.localScale.x, -tr.localScale.y, tr.localScale.z) * 0.5f ;
    81.         a_corners[4] = tr.position + new Vector3 (-tr.localScale.x, tr.localScale.y, -tr.localScale.z) * 0.5f ;
    82.         a_corners[5] = tr.position + new Vector3 (tr.localScale.x, tr.localScale.y, -tr.localScale.z) * 0.5f ;
    83.         a_corners[6] = tr.position + new Vector3 (tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ;
    84.         a_corners[7] = tr.position + new Vector3 (-tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ;
    85.  
    86.         return a_corners ;
    87.     }
    88.  
    89.     private Vector3 [] _CornersOBB ( Transform tr )
    90.     {
    91.         //BoxCollider boxCollider = tr.GetComponent <BoxCollider> () ;
    92.         //Bounds bunds = boxCollider.bounds ;
    93.  
    94.         Vector3 [] a_corners = new Vector3 [8] ;
    95.  
    96.         a_corners[0] = tr.position + tr.rotation * ( new Vector3 (-tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ) ;
    97.         a_corners[1] = tr.position + tr.rotation * ( new Vector3 (tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ) ;
    98.         a_corners[2] = tr.position + tr.rotation * ( new Vector3 (tr.localScale.x, -tr.localScale.y, tr.localScale.z) * 0.5f ) ;
    99.         a_corners[3] = tr.position + tr.rotation * ( new Vector3 (-tr.localScale.x, -tr.localScale.y, tr.localScale.z) * 0.5f ) ;
    100.         a_corners[4] = tr.position + tr.rotation * ( new Vector3 (-tr.localScale.x, tr.localScale.y, -tr.localScale.z) * 0.5f ) ;
    101.         a_corners[5] = tr.position + tr.rotation * ( new Vector3 (tr.localScale.x, tr.localScale.y, -tr.localScale.z) * 0.5f ) ;
    102.         a_corners[6] = tr.position + tr.rotation * ( new Vector3 (tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ) ;
    103.         a_corners[7] = tr.position + tr.rotation * ( new Vector3 (-tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ) ;
    104.  
    105.         return a_corners ;
    106.     }
    107.  
    108.     private Vector3 [] _MinMaxAABB ( Transform tr )
    109.     {
    110.  
    111.         //Vector3 V3_min = bounds.min ;
    112.         //Vector3 V3_max = bounds.max ;
    113.         Vector3 V3_min = tr.position + new Vector3 (-tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ;
    114.         Vector3 V3_max = tr.position + new Vector3 (tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ;
    115.  
    116.         // Debug.DrawLine ( V3_min - Vector3.forward * 50, V3_min + Vector3.forward * 100, Color.red ) ;
    117.         //Debug.DrawLine ( V3_max - Vector3.forward * 50, V3_max + Vector3.forward * 100, Color.red ) ;
    118.         /// Debug.DrawLine ( V3_min - Vector3.right * 50, V3_min + Vector3.right * 100, Color.blue ) ;
    119.         //Debug.DrawLine ( V3_max - Vector3.right * 50, V3_max + Vector3.right * 100, Color.blue ) ;
    120.  
    121.         // pass properties to an array
    122.         Vector3 [] V3_a = new Vector3 [2] ;
    123.         V3_a [0] = V3_min ;
    124.         V3_a [1] = V3_max ;
    125.  
    126.         return V3_a ;
    127.  
    128.     }
    129.     private Vector3 [] _MinMaxOBB ( Transform tr, Bounds bounds )
    130.     {
    131.  
    132.         Vector3 V3_min = bounds.min ;
    133.         Vector3 V3_max = bounds.max ;
    134.         //Vector3 V3_min = tr.position +  tr.rotation * ( new Vector3 (-tr.localScale.x, -tr.localScale.y, -tr.localScale.z) * 0.5f ) ;
    135.         //Vector3 V3_max = tr.position +  tr.rotation * ( new Vector3 (tr.localScale.x, tr.localScale.y, tr.localScale.z) * 0.5f ) ;
    136.  
    137.         // Debug.DrawLine ( V3_min - Vector3.forward * 50, V3_min + Vector3.forward * 100, Color.red ) ;
    138.         // Debug.DrawLine ( V3_max - Vector3.forward * 50, V3_max + Vector3.forward * 100, Color.red ) ;
    139.         // Debug.DrawLine ( V3_min - Vector3.right * 50, V3_min + Vector3.right * 100, Color.blue ) ;
    140.         // Debug.DrawLine ( V3_max - Vector3.right * 50, V3_max + Vector3.right * 100, Color.blue ) ;
    141.  
    142.         // pass properties to an array
    143.         Vector3 [] V3_a = new Vector3 [2] ;
    144.         V3_a [0] = V3_min ;
    145.         V3_a [1] = V3_max ;
    146.  
    147.         return V3_a ;
    148.     }
    149.  
    150.     /// <summary>
    151.     /// Axis Alligned Bounding Box collision 3D
    152.     /// Returns true if collides
    153.     /// </summary>
    154.     /// <param name="V3_minMaxAABB"></param>
    155.     /// <param name="V3_minMaxOBB"></param>
    156.     /// <returns></returns>
    157.     private bool _AABB2AABBCollisionTest ( Vector3 [] V3_minMaxAABB, Vector3 [] V3_minMaxOBB )
    158.     {
    159.         // 0 index is a min bounding vector
    160.         // 1 index is a max bounding vector
    161.                  
    162.         if ( !_ABBAxisIsColliding ( V3_minMaxOBB [0].x, V3_minMaxOBB [1].x, V3_minMaxAABB [0].x, V3_minMaxAABB [1].x ) // is not colliding X
    163.             || !_ABBAxisIsColliding ( V3_minMaxOBB [0].y, V3_minMaxOBB [1].y, V3_minMaxAABB [0].y, V3_minMaxAABB [1].y ) // is not colliding Y
    164.             || !_ABBAxisIsColliding ( V3_minMaxOBB [0].z, V3_minMaxOBB [1].z, V3_minMaxAABB [0].z, V3_minMaxAABB [1].z ) // is not colliding Z
    165.             )
    166.         {
    167.             return false ;
    168.         }
    169.          
    170.         // is colliding
    171.         return true ;
    172.     }
    173.  
    174.     // is not colliding with selected axis
    175.     private bool _ABBAxisIsColliding ( float f_minAABB, float f_maxAABB, float f_minOBBx, float f_maxOBB )
    176.     {
    177.         if ( f_maxOBB >= f_minAABB && f_minOBBx <= f_maxAABB )
    178.         {
    179.             return true ;
    180.         }
    181.  
    182.         return false ;
    183.     }
    184.  
    185.     // aCorn and bCorn are arrays containing all corners (vertices) of the two OBBs
    186.     private static bool _IntersectsWhenProjected ( Vector3[] aCorn, Vector3[] bCorn, Vector3 V3_axis )
    187.     {
    188.  
    189.         // Handles the cross product = {0,0,0} case
    190.         if( V3_axis == Vector3.zero )
    191.             return true;
    192.  
    193.         float aMin = float.MaxValue;
    194.         float aMax = float.MinValue;
    195.         float bMin = float.MaxValue;
    196.         float bMax = float.MinValue;
    197.  
    198.         // Define two intervals, a and b. Calculate their min and max values
    199.         for( int i = 0; i < 8; i++ )
    200.         {
    201.             //Debug.DrawLine ( aCorn [i], aCorn [i] + V3_axis * 100, Color.blue ) ;
    202.             //Debug.DrawLine ( bCorn [i], bCorn [i] + V3_axis * 100, Color.red ) ;
    203.  
    204.             float aDist = Vector3.Dot( aCorn[i], V3_axis );
    205.             aMin = ( aDist < aMin ) ? aDist : aMin;
    206.             aMax = ( aDist > aMax ) ? aDist : aMax;
    207.             float bDist = Vector3.Dot( bCorn[i], V3_axis );
    208.             bMin = ( bDist < bMin ) ? bDist : bMin;
    209.             bMax = ( bDist > bMax ) ? bDist : bMax;
    210.         }
    211.  
    212.         // One-dimensional intersection test between a and b
    213.         float longSpan = Mathf.Max( aMax, bMax ) - Mathf.Min( aMin, bMin );
    214.         float sumSpan = aMax - aMin + bMax - bMin;
    215.                  
    216.  
    217.         return longSpan < sumSpan; // Change this to <= if you want the case were they are touching but not overlapping, to count as an intersection
    218.     }
    219.  
    220.  
    221.     private bool _ABB2OBBCollisionTest ( Vector3 [] aabbCorners, Vector3 [] obbCorners )
    222.     {
    223.  
    224.         Vector3 V3_frwAABB = Vector3.forward ;
    225.         Vector3 V3_frwOBB = tr_cubeOBB.rotation * Vector3.forward ;
    226.         Vector3 V3_frwFrw = Vector3.Cross ( V3_frwAABB, V3_frwOBB ) ;
    227.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_frwFrw ) ) return false ;
    228.         // Debug.Log ( "1" ) ;
    229.  
    230.         Vector3 V3_upAABB = Vector3.up ;
    231.         Vector3 V3_upFrw = Vector3.Cross ( V3_upAABB, V3_frwOBB ) ;
    232.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_upFrw ) ) return false ;
    233.         // Debug.Log ( "2" ) ;
    234.  
    235.         Vector3 V3_rightAABB = Vector3.right ;
    236.         Vector3 V3_rightFrw = Vector3.Cross ( V3_rightAABB, V3_frwOBB ) ;
    237.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_rightFrw ) ) return false ;
    238.         // Debug.Log ( "3" ) ;
    239.  
    240.         Vector3 V3_upOBB = tr_cubeOBB.rotation * Vector3.up ;
    241.         Vector3 V3_upUp = Vector3.Cross ( V3_upAABB, V3_upOBB ) ;
    242.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_upUp ) ) return false ;
    243.         //Debug.Log ( "4" ) ;
    244.          
    245.         Vector3 V3_frwUp = Vector3.Cross ( V3_frwAABB, V3_upOBB ) ;
    246.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_frwUp ) ) return false ;
    247.         //Debug.Log ( "5" ) ;
    248.  
    249.         Vector3 V3_rightUp = Vector3.Cross ( V3_rightAABB, V3_upOBB ) ;
    250.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_rightUp ) ) return false ;
    251.         //Debug.Log ( "6" ) ;
    252.  
    253.         Vector3 V3_rightOBB = tr_cubeOBB.rotation * Vector3.right ;
    254.         Vector3 V3_frwRight = Vector3.Cross ( V3_frwAABB, V3_rightOBB ) ;
    255.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_frwRight ) ) return false ;
    256.         //Debug.Log ( "7" ) ;
    257.  
    258.         Vector3 V3_upRight = Vector3.Cross ( V3_upAABB, V3_rightOBB ) ;
    259.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_upRight ) ) return false ;
    260.         //Debug.Log ( "8" ) ;
    261.          
    262.         Vector3 V3_rightRight = Vector3.Cross ( V3_rightAABB, V3_rightOBB ) ;
    263.         if ( !_IntersectsWhenProjected ( aabbCorners, obbCorners, V3_rightRight ) ) return false ;
    264.         //Debug.Log ( "9" ) ;
    265.          
    266.         return true ;
    267.     }
    [\spoiler]

    Any assistance would be most welcome


    Edit:
    What I have should mention, I am using SAT (Separate Axis Theorem)
     
    Last edited: Aug 8, 2018