algorithm - 圆线段碰撞检测算法？

Question

我有一条从 A 到 B 的直线和一个位于 C 的半径为 R 的圆。

检查直线是否与圆相交的好算法是什么？它发生在沿圆圈边缘的什么坐标处？

Answer 1

服用

1. E是射线的起点，
2. L是射线的终点，
3. C 是您要测试的球体的中心
4. r 是那个球体的半径

计算:
d = L - E(射线的方向向量，从开始到结束)
f = E - C(从中心球体到光线起点的向量)

然后通过..找到交集
堵漏:
P = E + t * d
这是一个参数方程:
P_x = E_x + td_x
P_y = E_y + td_y
进入
(x - h)² + (y - k)² = r²
(h,k) = 圆心。

Note: We've simplified the problem to 2D here, the solution we get applies also in 3D

获得:

1. 展开x² - 2xh + h² + y² - 2yk + k² - r² = 0
2. 插入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. 展开e_x² + 2e_xtd_x + t²d _x² - 2e_xh - 2td_xh + h² +e_y² + 2e_ytd_y + t²d _y² - 2e_yk - 2td_yk + k² - r ² = 0
4. 组t²( d_x² + d_y² ) +2t( e_xd_x + e_yd_y - d_xh - d_yk ) +e_x² + e_y² -2e_xh - 2e_yk + h² + k² - r² = 0
5. 最后，t²( d · d ) + 2t( e · d - < strong>d · c ) + e · e - 2( e · c ) + c · c - r² = 0
   其中，d 是向量 d，· 是点积。
6. 然后，t²( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r² = 0
7. 让 f = e - ct²( d · d ) + 2t( d · f ) + f · f - r² = 0

所以我们得到:
t² * (d · d) + 2t*( f · d ) + ( f · f - r² ) = 0

所以求解二次方程:

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 ;
}