Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Feb 28th, 2014  |  syntax: C++  |  size: 14.35 KB  |  views: 5  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef intersection_h
  2. #define intersection_h
  3.  
  4. #include "mymath/mymath.h"
  5.  
  6. //forward declarations
  7. class sphere;
  8. class plane;
  9. class aabb;
  10. class frustum;
  11.  
  12. namespace inner
  13. {
  14.   static bool is_on_right_side( sphere* a, plane* b );
  15.   static bool is_on_right_side( aabb* a, plane* b );
  16.  
  17.   static bool is_inside( aabb* a, sphere* b );
  18.   static bool is_inside( aabb* a, aabb* b );
  19.   static bool is_inside( sphere* a, aabb* b );
  20.   static bool is_inside( sphere* a, sphere* b );
  21.  
  22.   static bool intersect( sphere* a, sphere* b );
  23.   static bool intersect( sphere* a, plane* b );
  24.   static bool intersect( plane* a, plane* b );
  25.   static bool intersect( aabb* a, aabb* b );
  26.   static bool intersect( aabb* a, sphere* b );
  27.   static bool intersect( aabb* a, plane* b );
  28. }
  29.  
  30. //generic abstract shape class
  31. //needed so that any shape can intersect any other shape
  32. class shape
  33. {
  34.   public:
  35.     //needed for frustum culling
  36.     virtual bool is_on_right_side( plane* p ) = 0;
  37.  
  38.     //needed for bvh construction, order matters
  39.         bool is_inside( shape* s ){ return s->_is_inside(this); }
  40.         virtual bool _is_inside( shape* s ) = 0;
  41.  
  42.     virtual bool __is_inside( sphere* a ) = 0;
  43.         virtual bool __is_inside( aabb* a ) = 0;
  44.  
  45.         //for intersection test
  46.     virtual bool intersects( shape* s ) = 0;
  47.  
  48.     //specific intersections
  49.     virtual bool _intersect( sphere* s ) = 0;
  50.     virtual bool _intersect( plane* s ) = 0;
  51.     virtual bool _intersect( aabb* s ) = 0;
  52. };
  53.  
  54. class sphere : public shape
  55. {
  56.   public:
  57.     //define a sphere by a center and a radius
  58.     mm::vec3 center;
  59.     float radius;
  60.  
  61.     bool is_on_right_side( plane* p )
  62.     {
  63.       return inner::is_on_right_side( this, p );
  64.     }
  65.  
  66.         bool _is_inside( shape* a )
  67.     {
  68.           return a->__is_inside(this);
  69.     }
  70.  
  71.         bool __is_inside( sphere* a )
  72.     {
  73.       return inner::is_inside( this, a );
  74.     }
  75.  
  76.     bool __is_inside( aabb* a )
  77.     {
  78.       return inner::is_inside( this, a );
  79.     }
  80.  
  81.     bool intersects( shape* s )
  82.     {
  83.       return s->_intersect( this );
  84.     }
  85.  
  86.     bool _intersect( sphere* s )
  87.     {
  88.       return inner::intersect( this, s );
  89.     }
  90.  
  91.     bool _intersect( plane* s )
  92.     {
  93.       return inner::intersect( this, s );
  94.     }
  95.  
  96.     bool _intersect( aabb* s )
  97.     {
  98.       return inner::intersect( s, this );
  99.     }
  100.  
  101.     sphere( mm::vec3 c = mm::vec3(), float r = float() ) : center( c ), radius( r ) {}
  102. };
  103.  
  104. class plane : public shape
  105. {
  106.   public:
  107.     //define a plane by a normal and a point
  108.     mm::vec3 normal, point;
  109.     float d; //cache -(normal dot point)
  110.  
  111.         bool _is_inside( shape* a )
  112.         {
  113.                 //not implemented
  114.                 assert(false);
  115.                 return false;
  116.         }
  117.  
  118.         bool __is_inside( sphere* a )
  119.         {
  120.                 //not implemented
  121.                 assert(false);
  122.                 return false;
  123.         }
  124.  
  125.         bool __is_inside( aabb* a )
  126.         {
  127.                 //not implemented
  128.                 assert(false);
  129.                 return false;
  130.         }
  131.  
  132.         bool is_on_right_side( plane* p )
  133.         {
  134.                 //not implemented
  135.                 assert(false);
  136.                 return false;
  137.         }
  138.  
  139.     //define a plane by 3 points
  140.     void set_up( const mm::vec3& a, const mm::vec3& b, const mm::vec3& c )
  141.     {
  142.       mm::vec3 tmp1, tmp2;
  143.  
  144.       tmp1 = a - b;
  145.       tmp2 = c - b;
  146.  
  147.       normal = mm::normalize( mm::cross( tmp2, tmp1 ) );
  148.       point = a;
  149.       d = -mm::dot( normal, point );
  150.     }
  151.  
  152.     //signed distance
  153.     float distance( const mm::vec3& p )
  154.     {
  155.       return d + mm::dot( normal, p );
  156.     }
  157.  
  158.     bool intersects( shape* s )
  159.     {
  160.       return s->_intersect( this );
  161.     }
  162.  
  163.     bool _intersect( sphere* s )
  164.     {
  165.       return inner::intersect( s, this );
  166.     }
  167.  
  168.     bool _intersect( plane* s )
  169.     {
  170.       return inner::intersect( this, s );
  171.     }
  172.  
  173.     bool _intersect( aabb* s )
  174.     {
  175.       return inner::intersect( s, this );
  176.     }
  177.  
  178.     //define a plane by a normal and a point
  179.     plane( const mm::vec3& n = mm::vec3(), const mm::vec3& p = mm::vec3() ) : normal( n ), point( p )
  180.     {
  181.       d = -mm::dot( n, p );
  182.     }
  183.  
  184.     plane( const mm::vec3& a, const mm::vec3& b, const mm::vec3& c )
  185.     {
  186.       set_up( a, b, c );
  187.     }
  188. };
  189.  
  190. class aabb : public shape
  191. {
  192.   public:
  193.     mm::vec3 pos; //center of the aabb
  194.     mm::vec3 extents; //half-width/height of the aabb
  195.     mm::vec3 min, max; //minimum/maximum apex of the aabb
  196.  
  197.     //returns the vertices of the triangles of the aabb in counter clockwise order
  198.     std::vector<mm::vec3> get_vertices()
  199.     {
  200.       std::vector<mm::vec3> v;
  201.  
  202.       //left
  203.       v.push_back( mm::vec3( min.x, max.yz ) );
  204.       v.push_back( mm::vec3( min.x, max.y, min.z ) );
  205.       v.push_back( mm::vec3( min.xyz ) );
  206.  
  207.       v.push_back( mm::vec3( min.xyz ) );
  208.       v.push_back( mm::vec3( min.xy, max.z ) );
  209.       v.push_back( mm::vec3( min.x, max.yz ) );
  210.  
  211.       //front
  212.       v.push_back( mm::vec3( min.xy, max.z ) );
  213.       v.push_back( mm::vec3( max.x, min.y, max.z ) );
  214.       v.push_back( mm::vec3( max.xyz ) );
  215.  
  216.       v.push_back( mm::vec3( max.xyz ) );
  217.       v.push_back( mm::vec3( min.x, max.yz ) );
  218.       v.push_back( mm::vec3( min.xy, max.z ) );
  219.  
  220.       //right
  221.       v.push_back( mm::vec3( max.xy, min.z ) );
  222.       v.push_back( mm::vec3( max.xyz ) );
  223.       v.push_back( mm::vec3( max.x, min.y, max.z ) );
  224.  
  225.       v.push_back( mm::vec3( max.x, min.y, max.z ) );
  226.       v.push_back( mm::vec3( max.x, min.yz ) );
  227.       v.push_back( mm::vec3( max.xy, min.z ) );
  228.  
  229.       //back
  230.       v.push_back( mm::vec3( max.xy, min.z ) );
  231.       v.push_back( mm::vec3( max.x, min.yz ) );
  232.       v.push_back( mm::vec3( min.xyz ) );
  233.  
  234.       v.push_back( mm::vec3( min.xyz ) );
  235.       v.push_back( mm::vec3( min.x, max.y, min.z ) );
  236.       v.push_back( mm::vec3( max.xy, min.z ) );
  237.  
  238.       //top
  239.       v.push_back( mm::vec3( min.x, max.y, min.z ) );
  240.       v.push_back( mm::vec3( min.x, max.yz ) );
  241.       v.push_back( mm::vec3( max.xyz ) );
  242.  
  243.       v.push_back( mm::vec3( max.xyz ) );
  244.       v.push_back( mm::vec3( max.xy, min.z ) );
  245.       v.push_back( mm::vec3( min.x, max.y, min.z ) );
  246.  
  247.       //bottom
  248.       v.push_back( mm::vec3( max.x, min.y, max.z ) );
  249.       v.push_back( mm::vec3( min.xy, max.z ) );
  250.       v.push_back( mm::vec3( min.xyz ) );
  251.  
  252.       v.push_back( mm::vec3( min.xyz ) );
  253.       v.push_back( mm::vec3( max.x, min.yz ) );
  254.       v.push_back( mm::vec3( max.x, min.y, max.z ) );
  255.  
  256.       return v;
  257.     }
  258.  
  259.     mm::vec3 get_pos_vertex( const mm::vec3& n )
  260.     {
  261.       mm::vec3 res = min;
  262.  
  263.       if( n.x >= 0 )
  264.         res.x = max.x;
  265.  
  266.       if( n.y >= 0 )
  267.         res.y = max.y;
  268.  
  269.       if( n.z >= 0 )
  270.         res.z = max.z;
  271.  
  272.       return res;
  273.     }
  274.  
  275.     void expand( const mm::vec3& p )
  276.     {
  277.       min = mm::min( min, p );
  278.       max = mm::max( max, p );
  279.       extents = ( max - min ) / 2.0f;
  280.       pos = min + extents;
  281.     }
  282.  
  283.     mm::vec3 get_neg_vertex( const mm::vec3& n )
  284.     {
  285.       mm::vec3 res = max;
  286.  
  287.       if( n.x >= 0 )
  288.         res.x = min.x;
  289.  
  290.       if( n.y >= 0 )
  291.         res.y = min.y;
  292.  
  293.       if( n.z >= 0 )
  294.         res.z = min.z;
  295.  
  296.       return res;
  297.     }
  298.  
  299.     bool is_on_right_side( plane* p )
  300.     {
  301.       return inner::is_on_right_side( this, p );
  302.     }
  303.  
  304.     bool _is_inside( shape* a )
  305.     {
  306.           return a->__is_inside(this);
  307.     }
  308.  
  309.         bool __is_inside( sphere* a )
  310.     {
  311.       return inner::is_inside( this, a );
  312.     }
  313.  
  314.     bool __is_inside( aabb* a )
  315.     {
  316.       return inner::is_inside( this, a );
  317.     }
  318.  
  319.     bool intersects( shape* s )
  320.     {
  321.       return s->_intersect( this );
  322.     }
  323.  
  324.     bool _intersect( sphere* s )
  325.     {
  326.       return inner::intersect( this, s );
  327.     }
  328.  
  329.     bool _intersect( plane* s )
  330.     {
  331.       return inner::intersect( this, s );
  332.     }
  333.  
  334.     bool _intersect( aabb* s )
  335.     {
  336.       return inner::intersect( s, this );
  337.     }
  338.  
  339.     void reset_minmax()
  340.     {
  341.       min = mm::vec3( FLT_MAX );
  342.       max = mm::vec3( -FLT_MAX );
  343.     }
  344.  
  345.         aabb()
  346.         {
  347.                 reset_minmax();
  348.         }
  349.  
  350.     aabb( const mm::vec3& p, const mm::vec3& e ) : pos( p ), extents( e )
  351.     {
  352.       min = pos - extents;
  353.       max = pos + extents;
  354.     }
  355. };
  356.  
  357. //haxx
  358. #ifdef _WIN32
  359. #undef FAR
  360. #endif
  361.  
  362. class frustum : public shape
  363. {
  364.   public:
  365.     shape* planes[6];
  366.  
  367.     enum type
  368.     {
  369.       TOP = 0, BOTTOM, LEFT, RIGHT, NEAR, FAR
  370.     };
  371.  
  372.     frustum()
  373.     {
  374.       for( int c = 0; c < 6; ++c )
  375.         planes[c] = new plane();
  376.     }
  377.  
  378.         bool _is_inside( shape* a )
  379.         {
  380.                 //not implemented
  381.                 assert(false);
  382.                 return false;
  383.         }
  384.  
  385.         bool __is_inside( sphere* a )
  386.         {
  387.                 //not implemented
  388.                 assert(false);
  389.                 return false;
  390.         }
  391.  
  392.         bool __is_inside( aabb* a )
  393.         {
  394.                 //not implemented
  395.                 assert(false);
  396.                 return false;
  397.         }
  398.  
  399.         bool is_on_right_side( plane* p )
  400.         {
  401.                 //not implemented
  402.                 assert(false);
  403.                 return false;
  404.         }
  405.  
  406.     void set_up( const mm::camera<float>& cam )
  407.     {
  408.       mm::vec3 nc = cam.pos - cam.view_dir * cam.get_frame()->near_ll.z;
  409.       mm::vec3 fc = cam.pos - cam.view_dir * cam.get_frame()->far_ll.z;
  410.  
  411.       mm::vec3 right = -mm::normalize( mm::cross( cam.up_vector, cam.view_dir ) );
  412.  
  413.       float nw = cam.get_frame()->near_lr.x - cam.get_frame()->near_ll.x;
  414.       float nh = cam.get_frame()->near_ul.y - cam.get_frame()->near_ll.y;
  415.  
  416.       float fw = cam.get_frame()->far_lr.x - cam.get_frame()->far_ll.x;
  417.       float fh = cam.get_frame()->far_ul.y - cam.get_frame()->far_ll.y;
  418.  
  419.       //near top left
  420.       mm::vec3 ntl = nc + cam.up_vector * nh - right * nw;
  421.       mm::vec3 ntr = nc + cam.up_vector * nh + right * nw;
  422.       mm::vec3 nbl = nc - cam.up_vector * nh - right * nw;
  423.       mm::vec3 nbr = nc - cam.up_vector * nh + right * nw;
  424.  
  425.       mm::vec3 ftl = fc + cam.up_vector * fh - right * fw;
  426.       mm::vec3 ftr = fc + cam.up_vector * fh + right * fw;
  427.       mm::vec3 fbl = fc - cam.up_vector * fh - right * fw;
  428.       mm::vec3 fbr = fc - cam.up_vector * fh + right * fw;
  429.  
  430.       static_cast<plane*>( planes[TOP] )->set_up( ntr, ntl, ftl );
  431.       static_cast<plane*>( planes[BOTTOM] )->set_up( nbl, nbr, fbr );
  432.       static_cast<plane*>( planes[LEFT] )->set_up( ntl, nbl, fbl );
  433.       static_cast<plane*>( planes[RIGHT] )->set_up( nbr, ntr, fbr );
  434.       static_cast<plane*>( planes[NEAR] )->set_up( ntl, ntr, nbr );
  435.       static_cast<plane*>( planes[FAR] )->set_up( ftr, ftl, fbl );
  436.     }
  437.  
  438.     bool intersects( shape* s )
  439.     {
  440.       for( int c = 0; c < 6; ++c )
  441.       {
  442.         if( !s->is_on_right_side( ( plane* )planes[c] ) )
  443.           return false;
  444.       }
  445.  
  446.       return true;
  447.     }
  448.  
  449.     virtual bool _intersect( sphere* s )
  450.     {
  451.       for( int c = 0; c < 6; ++c )
  452.       {
  453.         if( !inner::intersect( s, ( plane* )planes[c] ) )
  454.           return false;
  455.       }
  456.  
  457.       return true;
  458.     }
  459.  
  460.     virtual bool _intersect( plane* s )
  461.     {
  462.       for( int c = 0; c < 6; ++c )
  463.       {
  464.         if( !inner::intersect( s, ( plane* )planes[c] ) )
  465.           return false;
  466.       }
  467.  
  468.       return true;
  469.     }
  470.  
  471.     virtual bool _intersect( aabb* s )
  472.     {
  473.       for( int c = 0; c < 6; ++c )
  474.       {
  475.         if( !inner::intersect( s, ( plane* )planes[c] ) )
  476.           return false;
  477.       }
  478.  
  479.       return true;
  480.     }
  481. };
  482.  
  483. namespace inner
  484. {
  485.   //only tells if the sphere is on the right side of the plane!
  486.   bool is_on_right_side( sphere* a, plane* b )
  487.   {
  488.     float dist = b->distance( a->center );
  489.  
  490.     if( dist < -a->radius )
  491.       return false;
  492.  
  493.     return true;
  494.   }
  495.  
  496.   //only tells if the sphere is on the right side of the plane!
  497.   bool is_on_right_side( aabb* a, plane* b )
  498.   {
  499.     if( b->distance( a->get_pos_vertex( b->normal ) ) < 0 )
  500.       return false;
  501.  
  502.     return true;
  503.   }
  504.  
  505.   bool intersect( sphere* a, sphere* b )
  506.   {
  507.     mm::vec3 diff = a->center - b->center;
  508.     float dist = mm::dot( diff, diff );
  509.  
  510.     float rad_sum = b->radius + a->radius;
  511.  
  512.     if( dist > rad_sum * rad_sum ) //squared distance check
  513.       return false;
  514.  
  515.     return true;
  516.   }
  517.  
  518.   //checks if a sphere intersects a plane
  519.   bool intersect( sphere* a, plane* b )
  520.   {
  521.     float dist = b->distance( a->center );
  522.  
  523.     if( abs( dist ) <= a->radius )
  524.       return true;
  525.  
  526.     return false;
  527.   }
  528.  
  529.   bool intersect( plane* a, plane* b )
  530.   {
  531.     mm::vec3 vector = mm::cross( a->normal, b->normal );
  532.  
  533.     //if the cross product yields a null vector
  534.     //then the angle is either 0 or 180
  535.     //that is the two normals are parallel
  536.     // sin(alpha) = 0
  537.     // ==> |a| * |b| * sin(alpha) = 0
  538.     if( mm::equal( vector, mm::vec3( 0 ) ) )
  539.       return false;
  540.  
  541.     return true;
  542.   }
  543.  
  544.   bool intersect( aabb* a, aabb* b )
  545.   {
  546.     mm::vec3 t = b->pos - a->pos;
  547.  
  548.     if( abs( t.x ) > ( a->extents.x + b->extents.x ) )
  549.       return false;
  550.  
  551.     if( abs( t.y ) > ( a->extents.y + b->extents.y ) )
  552.       return false;
  553.  
  554.     if( abs( t.z ) > ( a->extents.z + b->extents.z ) )
  555.       return false;
  556.  
  557.     return true;
  558.   }
  559.  
  560.   bool intersect( aabb* a, sphere* b )
  561.   {
  562.     //square distance check between spheres and aabbs
  563.     mm::vec3 vec = b->center - mm::clamp( b->center - a->pos, a->min, a->max );
  564.  
  565.     float sqlength = mm::dot( vec, vec );
  566.  
  567.     if( sqlength > b->radius * b->radius )
  568.       return false;
  569.  
  570.     return true;
  571.   }
  572.  
  573.   bool intersect( aabb* a, plane* b )
  574.   {
  575.     mm::vec3 p = a->get_pos_vertex( b->normal );
  576.     mm::vec3 n = a->get_neg_vertex( b->normal );
  577.  
  578.     float dist_p = b->distance( p );
  579.     float dist_n = b->distance( n );
  580.  
  581.     if( ( dist_n > 0 && dist_p > 0 ) ||
  582.         ( dist_n < 0 && dist_p < 0 ) )
  583.       return false;
  584.  
  585.     return true;
  586.   }
  587.  
  588.   //is a inside b?
  589.   bool is_inside( sphere* a, aabb* b )
  590.   {
  591.           mm::vec3 spheremax = a->center + a->radius;
  592.           mm::vec3 spheremin = a->center - a->radius;
  593.  
  594.           if( lessThanEqual(spheremax, b->max) && greaterThanEqual(spheremin, b->min) )
  595.                   return true;
  596.  
  597.           return false;
  598.   }
  599.  
  600.   //is a inside b?
  601.   bool is_inside( aabb* a, sphere* b )
  602.   {
  603.     mm::vec3 minvec = a->min - b->center;
  604.         mm::vec3 maxvec = a->max - b->center;
  605.         float sqrmaxlength = mm::dot(maxvec, maxvec);
  606.         float sqrminlength = mm::dot(minvec, minvec);
  607.         float sqrradius = b->radius * b->radius;
  608.  
  609.         if( sqrmaxlength <= sqrradius && sqrminlength <= sqrradius )
  610.                 return true;
  611.  
  612.         return false;
  613.   }
  614.  
  615.   //is a inside b?
  616.   bool is_inside( aabb* a, aabb* b )
  617.   {
  618.     if( mm::greaterThan( a->min, b->min ) && mm::lessThan( b->max, a->max ) )
  619.       return true;
  620.  
  621.     return false;
  622.   }
  623.  
  624.   //is a inside b?
  625.   bool is_inside( sphere* a, sphere* b )
  626.   {
  627.         mm::vec3 spheredist = b->center - a->center;
  628.  
  629.     if( mm::dot(spheredist, spheredist) <= b->radius * b->radius )
  630.       return true;
  631.  
  632.     return false;
  633.   }
  634. }
  635.  
  636. #endif