Intersección entre una línea y una esfera

Question

Estoy tratando de encontrar el punto de intersección entre una esfera y una línea pero, sinceramente, no tengo ni idea de cómo hacerlo. ¿Alguien podría ayudarme en esto?

Answer 1

Encuentra la solución de las dos ecuaciones en (x, y, z) que describen la línea y la esfera.

Puede haber 0, 1 o 2 soluciones.

• 0 implica que no se cruzan
• 1 implica la línea es una tangente a la esfera
• 2 implica la línea pasa a través de la esfera.

Answer 2

Busque "esfera intersección rayo" - la misma prueba se utiliza todo el tiempo en el trazado de rayos y hay un montón de ejemplos en línea, e incluso quite a few here en StackOverflow.

Answer 3

expresar la línea como una función de t:

{ x(t) = x0*(1-t) + t*x1 
{ y(t) = y0*(1-t) + t*y1 
{ z(t) = z0*(1-t) + t*z1 

Cuando t = 0, será en un punto final (x0,y0,z0). Cuando t = 1, estará en el otro punto final (x1,y1,z1).

escribir una fórmula para la distancia al centro de la esfera (al cuadrado) en t (donde (xc,yc,zc) es el centro de la esfera):

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

Resuelva para t cuando f(t) es igual a R^2 (R siendo el radio de la esfera):

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

A = (x0-xc)^2 + (y0-yc)^2 + (z0-zc)^2 - R^2 
B = (x1-xc)^2 + (y1-yc)^2 + (z1-zc)^2 - A - C - R^2 
C = (x0-x1)^2 + (y0-y1)^2 + (z0-z1)^2 

Resuelva A + B*t + C*t^2 = 0 para t. Este es un quadratic equation normal.

Puede obtener hasta dos soluciones. Cualquier solución donde t se encuentre entre 0 y 1 es válida.

Si tiene una solución válida para t, conéctela en las primeras ecuaciones para obtener el punto de intersección.

Supuse que se refería a un segmento de línea (dos puntos finales). Si en cambio quieres una línea completa (longitud infinita), puedes elegir dos puntos a lo largo de la línea (no demasiado cerca) y usarlos. También vamos t ser cualquier valor real, no sólo entre 0 y 1.

Editar: Fijé la fórmula para B. Estaba mezclando los signos. Gracias M Katz, por mencionar que no funcionó.

Answer 4

Puede usar Wolfram Alpha para resolverlo en el sistema de coordenadas donde se centra la esfera.

En este sistema, las ecuaciones son:

Esfera:

 x^2 + y^2 + z^2 = r^2 

línea recta:

x = x0 + Cos[x1] t 
    y = y0 + Cos[y1] t 
    z = z0 + Cos[z1] t 

Then we ask Wolfram Alpha to solve for t: (Inténtelo!)

y después de que se puede cambiar nuevamente a su sistema de coordenadas original (una traducción simple)

Answer 5

Creo que hay una imprecisión en la solución de Markus Jarderot. No estoy seguro de cuál es el problema, pero estoy bastante seguro de que lo traduje fielmente al código, y cuando traté de encontrar la intersección de un segmento de línea que se sabe que cruza a una esfera, obtuve un discriminante negativo (sin soluciones).

Encontré esto: http://www.codeproject.com/Articles/19799/Simple-Ray-Tracing-in-C-Part-II-Triangles-Intersec, que da una derivación similar pero ligeramente diferente.

que resultó en que el siguiente código C# y funciona para mí:

public static Point3D[] FindLineSphereIntersections(Point3D linePoint0, Point3D linePoint1, Point3D circleCenter, double circleRadius) 
    { 
     // http://www.codeproject.com/Articles/19799/Simple-Ray-Tracing-in-C-Part-II-Triangles-Intersec 

     double cx = circleCenter.X; 
     double cy = circleCenter.Y; 
     double cz = circleCenter.Z; 

     double px = linePoint0.X; 
     double py = linePoint0.Y; 
     double pz = linePoint0.Z; 

     double vx = linePoint1.X - px; 
     double vy = linePoint1.Y - py; 
     double vz = linePoint1.Z - pz; 

     double A = vx * vx + vy * vy + vz * vz; 
     double B = 2.0 * (px * vx + py * vy + pz * vz - vx * cx - vy * cy - vz * cz); 
     double C = px * px - 2 * px * cx + cx * cx + py * py - 2 * py * cy + cy * cy + 
        pz * pz - 2 * pz * cz + cz * cz - circleRadius * circleRadius; 

     // discriminant 
     double D = B * B - 4 * A * C; 

     if (D < 0) 
     { 
      return new Point3D[ 0 ]; 
     } 

     double t1 = (-B - Math.Sqrt (D))/(2.0 * A); 

     Point3D solution1 = new Point3D(linePoint0.X * (1 - t1) + t1 * linePoint1.X, 
             linePoint0.Y * (1 - t1) + t1 * linePoint1.Y, 
             linePoint0.Z * (1 - t1) + t1 * linePoint1.Z); 
     if (D == 0) 
     { 
      return new Point3D[] { solution1 }; 
     } 

     double t2 = (-B + Math.Sqrt(D))/(2.0 * A); 
     Point3D solution2 = new Point3D(linePoint0.X * (1 - t2) + t2 * linePoint1.X, 
             linePoint0.Y * (1 - t2) + t2 * linePoint1.Y, 
             linePoint0.Z * (1 - t2) + t2 * linePoint1.Z); 

     // prefer a solution that's on the line segment itself 

     if (Math.Abs(t1 - 0.5) < Math.Abs(t2 - 0.5)) 
     { 
      return new Point3D[] { solution1, solution2 }; 
     } 

     return new Point3D[] { solution2, solution1 }; 
    } 

Answer 6

Aquí es una formulación más concisa utilizando productos internos, a menos de 100 LOC, y no hay enlaces externos. Además, se le preguntó a la pregunta por una línea, no por un segmento de línea.

Suponga que la esfera se centra en C con radio r. La línea se describe por P+l*D donde D*D=1. P y C son puntos, D es un vector, l es un número.

Establecemos PC = P-C, pd = PC*D y s = pd*pd - PC*PC + r*r. Si s < 0 no hay soluciones, si s == 0 hay solo una, de lo contrario, hay dos. Para las soluciones configuramos l = -pd +- sqrt(s), luego lo conectamos al P+l*D.

Answer 7

O puede simplemente encontrar la fórmula de ambos:
línea: (x-x0)/a=(y-y0)/b=(z-z0)/c, que son las ecuaciones simétricas del segmento de línea entre los puntos se pueden encontrar.
esfera: (x-xc)^2+(y-yc)^2+(z-zc)^2 = R^2.

Usa la ecuación simétrica para encontrar la relación entre x y y, y x y z.

Luego inserte y y z en términos de x en la ecuación de la esfera.
Luego encuentra x, y luego puedes encontrar y y z.

Si x le da un resultado imaginario, eso significa que la línea y la esfera no se cruzan.

Answer 8

No tengo suficiente reputación para comentar la respuesta de M Katz, pero su respuesta asume que la línea puede seguir infinitamente en cada dirección. Si solo necesita los puntos de intersección de la línea SEGMENT, necesita que t1 y t2 sean menores que uno (según la definición de una ecuación parametrizada).Por favor, vea mi respuesta en C# a continuación:

 public static Point3D[] FindLineSphereIntersections(Point3D linePoint0, Point3D linePoint1, Point3D circleCenter, double circleRadius) 
    { 

     double cx = circleCenter.X; 
     double cy = circleCenter.Y; 
     double cz = circleCenter.Z; 

     double px = linePoint0.X; 
     double py = linePoint0.Y; 
     double pz = linePoint0.Z; 

     double vx = linePoint1.X - px; 
     double vy = linePoint1.Y - py; 
     double vz = linePoint1.Z - pz; 

     double A = vx * vx + vy * vy + vz * vz; 
     double B = 2.0 * (px * vx + py * vy + pz * vz - vx * cx - vy * cy - vz * cz); 
     double C = px * px - 2 * px * cx + cx * cx + py * py - 2 * py * cy + cy * cy + 
        pz * pz - 2 * pz * cz + cz * cz - circleRadius * circleRadius; 

     // discriminant 
     double D = B * B - 4 * A * C; 

     double t1 = (-B - Math.Sqrt(D))/(2.0 * A); 

     Point3D solution1 = new Point3D(linePoint0.X * (1 - t1) + t1 * linePoint1.X, 
             linePoint0.Y * (1 - t1) + t1 * linePoint1.Y, 
             linePoint0.Z * (1 - t1) + t1 * linePoint1.Z); 

     double t2 = (-B + Math.Sqrt(D))/(2.0 * A); 
     Point3D solution2 = new Point3D(linePoint0.X * (1 - t2) + t2 * linePoint1.X, 
             linePoint0.Y * (1 - t2) + t2 * linePoint1.Y, 
             linePoint0.Z * (1 - t2) + t2 * linePoint1.Z); 

     if (D < 0 || t1 > 1 || t2 >1) 
     { 
      return new Point3D[0]; 
     } 
     else if (D == 0) 
     { 
      return new [] { solution1 }; 
     } 
     else 
     { 
      return new [] { solution1, solution2 }; 
     } 
    } 

Answer 9

que no tienen la reputación de hacer comentarios sobre la solución de Ashavsky, pero el cheque al final necesitaba un poco más ajustes.

if (D < 0) 
    return new Point3D[0]; 
else if ((t1 > 1 || t1 < 0) && (t2 > 1 || t2 < 0)) 
    return new Point3D[0]; 
else if (!(t1 > 1 || t1 < 0) && (t2 > 1 || t2 < 0)) 
    return new [] { solution1 }; 
else if ((t1 > 1 || t1 < 0) && !(t2 > 1 || t2 < 0)) 
    return new [] { solution2 }; 
else if (D == 0) 
    return new [] { solution1 }; 
else 
    return new [] { solution1, solution2 };