Проверка пересечения 3D луча и 3D объектов

Пересечение 3D луча и 3D плоскости.

Теория:

Вычисляем скалярное произведение нормали плоскости с направлением луча (луч нормализован). Если произведение равно 0, то луч проходит перпендикулярно плоскости, следовательно пересечения нет. Плоскость задана каноническим уравнением вида:
nx * x + ny * y + nz * z + d = 0, где нормаль плоскости равна: plane.normal = (nx, ny, nz). Луч задан начальной точкой и вектором направления:  ray.start = (xs, ys, zs) и ray.direction = (xd, yd, zd). Координаты точек луча будут вычисляться по формулам:
xp = xs + t * xd, yp = ys + t * yd, zp = zs + t * zd. 
Найдем точку пересечения луча и плоскости, для этого подставим в уравнение плоскости координаты точек луча: 
nx * (xs + t * xd) + ny * (ys + t * yd) + nz * (zs + t * zd) + d = 0 
Выражая параметр t, мы найдем формулу для поиска точки пересечения. dotProduct - скалярное произведение. 


t = - (dotProduct(plane.normal, ray.start) + plane.d) /  dotProduct(plane.normal, ray.direction);


если t < 0, то луч не пересекает плоскость.



Код:

bool intersectPlane(const Plane& plane, const Ray& ray, float* result)
{
   float alpha = dotProduct(plane.normal, ray.direction);


   if(alpha != 0.0f)
   {
      *result = - dotProduct(plane.normal, ray.start) + plane.d;
      *result = *result / alpha;


      return (*result >= 0.0f);
   }


   return false;
}

Пересечение 3D луча и сферы.

Теория:

Пусть нам дана сфера с координатами центра в точке (xc, yc, zc) и радиусом r, тогда сфера описывается формулой:

(x - xc)^2 + (y - yc)^2 + (z - zc)^2 = r^2

подставим сюда, формулы координат луча:

(xs + t * xd - xc)^2 + (ys + t * yd - yc)^2 + (zs + t * zd)^2 = r^2

Открываем скобки:


t^2 * (xd^2 + yd^2 + zd^2) + 2t * ((xs * xd + ys * yd + zs * zd)-(xc * xd + yc * yd + zc * zd)) + xs^2 + ys^2 + zs^2 + xc^2 + yc^2 + zc^2 - r^2 = 0

или

t^2*dotProduct(ray.direction, ray.direction) + 2t * dotProduct(ray.direction, (ray.start - sphere.center)) + dotProduct(ray.start, ray.start)- 2 * dotProduct(ray.start, sphere.center) + dotProduct(sphere.center, sphere.center) - r^2 = 0


Приведем уравнение к виду:

at^2 + bt + c = 0

a = dotProduct(ray.direction, ray.direction)
b = 2*dotProduct(ray.direction, (ray.start - sphere.center))
c = dotProduct(ray.start, ray.start)- 2 * dotProduct(ray.start, sphere.center) + dotProduct(sphere.center, sphere.center) - r^2 = (ray.start - sphere.center)*(ray.start - sphere.center) - r^2


Наименьший положительный корень этого уравнения определяет на луче ближайшую точку пересечения луча со сферой. Направление луча нормировано, поэтому a = 1.

Что бы проверить лежит ли начало луча в сфере:

|ray.start - sphere.center| ^ 2 - sphere.radius^2 < 0, где |x| - длинна вектора.

Код:

bool intersectSphere (const Sphere& sphere, const Ray& ray, float* result)
{
   Vector3D vect(ray.start.x - sphere.center.x,
                 ray.start.y - sphere.center.y, 
                 ray.start.z - sphere.ceneter.z);


   float c = sqr(vect.length) - sqr(sphere.radius);


   if(c < 0.0f)
   {
     *result = 0.0f;
      return true;
   }


   float b = dotProduct(vect, ray.direction);


   float d = sqr(b) - c;


   if (d < 0.0f)
   {
      return (false);
   }


   float root1 = -b - sqrt(c);
   float root2 = -b + sqrt(c);


   if(root1 >= root2)
      *result = root1;
   else
      *result = root2;
  
   return (*result >= 0.0f);
}

Пересечение 3D луча и параллелепипеда (AABB).

Теория:



Прямоугольный параллелепипед со сторонами, параллельными координатным
плоскостям, определяется двумя своими вершинами:  A(rect.minX, rect.minY, rect.minZ) и B(rect.maxX, rect.maxY, rect.maxZ). Рассмотрим сначала плоскости параллельные осям yz. И начнем проверять с координатой ray.position.x луча. Если ray.direction.x = 0, то значит луч параллелен этим плоскостям и, если ray.position.x < rect.minX или ray.position.x > rect.maxX, то значит луч не пересекает параллелепипед. А если луч не параллелен этим плоскостям, то рассчитываем отношения, когда луч пересечет ближнюю и дальнюю плоскости:
t1 =  (rect.minX - ray.position.x) / ray.direction.x
t2 =  (rect.maxX - ray.position.x) / ray.direction.x
если t1 > t2, то меняем их местами. Заводим переменные t_near = t1 и t_far = t2 и дальше рассчитываем аналогично другие две плоскости для Y:

t1 =  (rect.minY - ray.position.y) / ray.direction.y

t2 =  (rect.maxY - ray.position.y) / ray.direction.y

Если t1 > t_near, то t_near = t1

Если t2 < t_far, то t_far = t2

Если t_near > t_far или t_far < 0, то значит луч не пересекает параллелепипед. Проведем аналогичные расчеты и для Z. И если в итоге после всех проведенных расчетов получим, что: 0 < t_near < t_far или 0 < t_far, то значит луч пересечет параллелепипед. В t_near будет параметр луча при котором луч войдет в параллелепипед, а в t_far параметр луча при выходе из параллелепипеда.

Код:


bool intersectRectangle(const Rect& rect, const Ray& ray, float* result)
{
   //Проверим если луч находится внутри параллелепипеда.
   if (ray.position.x >= rect.minX
       && ray.posotion.x <=  rect.maxX
       && ray.positiont.y >= rect.minY
       && ray.position.y <= rect.maxY
       && ray.position.z >= rect.minZ
       && ray.position.z <= rect.maxZ)
   {
      *result = 0.0f;
      return true;
   }


   float t_near = FLT_MIN;
   float t_far = FLT_MAX;
   float t1;
   float t2;
   float tmp;

   if(ray.direction.x != 0.0f)

   {

      t1 = (rect.minX - ray.position.x) / ray.direction.x;

      t2 = (rect.maxX - ray.position.x) / ray.direction.x;

      if(t1 > t2)

      {

         tmp = t1;

         t2 = t1;

         t2 = tmp;         

      }

      

      if(t1 > t_near)

      {

         t_near = t1;

      }

      if(t2 < t_far)

      {

         t_far = t2;

      }

      if(t_near > t_far) return false;

      if(t_far < 0) return false;

   }

   if(ray.direction.y != 0.0f)

   {

      t1 = (rect.minY - ray.position.y) / ray.direction.y;

      t2 = (rect.maxY - ray.position.y) / ray.direction.y;

      if(t1 > t2)

      {

         tmp = t1;

         t2 = t1;

         t2 = tmp;         

      }

      

      if(t1 > t_near)

      {

         t_near = t1;

      }

      if(t2 < t_far)

      {

         t_far = t2;

      }

      if(t_near > t_far) return false;

      if(t_far < 0) return false;

   }

   if(ray.direction.z != 0.0f)

   {

      t1 = (rect.minY - ray.position.y) / ray.direction.y;

      t2 = (rect.maxY - ray.position.y) / ray.direction.y;

      if(t1 > t2)

      {

         tmp = t1;

         t2 = t1;

         t2 = tmp;         

      }

      

      if(t1 > t_near)

      {

         t_near = t1;

      }

      if(t2 < t_far)

      {

         t_far = t2;

      }

      if(t_near >= t_far) return false;

      if(t_far < 0) return false;

   }

   *result = t_near;

   return (*result < t_far && *result >= 0);

}