¿Algoritmo de detección de colisiones de segmentos de línea circular?

Tomando

1. E es el punto inicial del rayo,
2. L es el punto final del rayo,
3. C es el centro de la esfera contra la que estás probando
4. r es el radio de esa esfera

Calcular:
d = L - E (Vector de dirección del rayo, de principio a fin)
f = E - C (Vector desde el centro de la esfera hasta el inicio del rayo)

Entonces la intersección se encuentra mediante...
Sustituyendo:
P = E + t * d
Esta es una ecuación paramétrica:
P _x = E _x + td _x
P _y = E _y + td _y
en
(x - h) ² + (y - k) ² = r ²
(h,k) = centro del círculo.

Nota: Aquí hemos simplificado el problema a 2D, la solución que obtenemos se aplica también en 3D.

Llegar:

1. Expandir x ² - 2xh + h ² + y ² - 2yk + k ² - r ² = 0
2. Enchufe x = e _x + td _x
   y = e _y + td _y
   ( e _x + td _x ) ² - 2( e _x + td _x )h + h ² + ( e _y + td _y ) ² - 2( e _y + td _y )k + k ² - r ² = 0
3. Explotar e _x ² + 2e _x td _x + t ² d _x ² - 2e _x h - 2td _x h + h ² + e _y ² + 2e _y td _y + t ² d _y ² - 2e _y k - 2td _y k + k ² - r ² = 0
4. Grupo t ² ( d _x ² + d _y ² ) + 2t( e _x d _x + e _y d _y - d _x h - d _y k ) + e _x ² + e _y ² - 2e _x h - 2e _y k + h ² + k ² - r ² = 0
5. Finalmente, t ² ( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r ² = 0
   Donde d es el vector d y · es el producto escalar.
6. Y luego, t ² ( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r ² = 0
7. Sea f = e - c t ² ( d · d ) + 2t( d · f ) + f · f - r ² = 0

Entonces obtenemos:
t ² * ( d · d ) + 2t*( f · d ) + ( f · f - r ² ) = 0

Entonces resolviendo la ecuación cuadrática:

float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;

float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
  // no intersection
}
else
{
  // ray didn't totally miss sphere,
  // so there is a solution to
  // the equation.
  
  discriminant = sqrt( discriminant );

  // either solution may be on or off the ray so need to test both
  // t1 is always the smaller value, because BOTH discriminant and
  // a are nonnegative.
  float t1 = (-b - discriminant)/(2*a);
  float t2 = (-b + discriminant)/(2*a);

  // 3x HIT cases:
  //          -o->             --|-->  |            |  --|->
  // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

  // 3x MISS cases:
  //       ->  o                     o ->              | -> |
  // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
  
  if( t1 >= 0 && t1 <= 1 )
  {
    // t1 is the intersection, and it's closer than t2
    // (since t1 uses -b - discriminant)
    // Impale, Poke
    return true ;
  }

  // here t1 didn't intersect so we are either started
  // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  {
    // ExitWound
    return true ;
  }
  
  // no intn: FallShort, Past, CompletelyInside
  return false ;
}

Jul 05 '2009 21:07 bobobobo