Duda colisión circulo linea.

[Erkosone]

Hola, estoy montando un rudimentario sistema de colisiones para un pequeño motor de renderizado 3d, el caso es que estoy planteando el tema de la forma mas sencilla posible, todos los objetos a una misma altura y el suelo plano, así tengo una percepción un poco mas tirando a las 2d.

Mi pregunta es, alguien sería tan amable de explicar de una forma sencilla 'dentro de lo que cabe' sobre como determinar si existe intersección entre una linea con coordenadas 'x0,y0,z0' <-> 'x1,y1,z1'   y una esfera de radio 'r' ?

Encuentro varios ejemplos por la red pero pocas explicaciones claras sobre el procedimiento explicado para torpes, digo que no son claras "desde mi propia ignorancia" claro está.

Un saludo y gracias de antemano por si alguien se tomase la molestia de explicar el desarrollo de este calculo.

[Gallo]

Ahora mismo no recuerdo la formula, pero la explicación es sencilla.

Encuentra la distancia entre la recta y el centro de la esfera  (distancia entre punto y recta), si la distancia es menor o igual al radio es que hay interesección.

http://es.wikipedia.org/wiki/Distancia_de_un_punto_a_una_recta

Si quieres encontrar el punto de intersección, debes encontrar el punto a lo largo de la recta que está a una distancia igual al radio, de estos habrá 1 si es tangente y 2 si pasa por dentro de la esfera.



Me gustaría ayudarte mas pero las mates no son lo mio, ademas no se suelen programar cada dia estas cosas, yo me haría o buscaría una lib que hiciera cálculos básicos como los que he mencionado y usaría los conceptos para calcular lo que necesites.

Saludos

[Erkosone]

Gracias por tu respuesta Gallo, el concepto es sencillo y el desarrollo del mismo también pero mi problema es de base, no se realmente el por que de estos cálculos y es ahí donde llegado el momento de aplicarlo en otro ámbito comienzo a tener lagunas, por ejemplo si lo tuviera completamente claro en 2d a la hora de aplicarlo en 3d me costaría mucho menos.

Lo dicho, gracias por el link, voy a leer mas sobre el tema haber si consigo entender el proceso.

[Erkosone]

Para el que venga detrás y necesite la misma información la dejo aquí ya que lo mío me ha costado encontrar algo decente y sobre todo entendible..

Primero un magnifico vídeo donde un profesor explica muy detalladamente el proceso aritmético para trabajar con sistemas de ecuaciones no lineales por el método de substitución para encontrar el punto o los puntos de intersección entre un circulo y una linea en un plano 2d.
De verdad que el vídeo es estupendo, muy recomendable darle un vistazo amigos.
http://www.youtube.com/watch?v=a-aJgGYjWOw

Y un ejemplo de código aplicado en lenguaje VB.NET que puede ser portado a otros lenguajes con muy poco esfuerzo:

--------------------------------------------------------------------------
The FindLineCircleIntersections function calculates the points of intersection between a line and a circle. It takes as parameters a circle's center point and radius, and two points on the line. It uses ByRef parameters to return the coordinates of the points of intersection. The function returns the number of points of intersection (0, 1, or 2).
To fund the points of intersection, the code considers the line as generated by the equations:

    X(t) = x1 + (x2 - x1) * t
    Y(t) = y1 + (y2 - y1) * t
Where t ranges from 0 to 1 to draw the line segment.

The code plugs these equations into the equation for a circle:

    (X - Cx)^2 + (Y - Cy)^2 = radius^2
It then solves for t by using the quadratic formula. The result is 0, 1, or 2 values for t. It plugs those values back into the equations for the line to get the points of intersection.


Private Function FindLineCircleIntersections(ByVal cx As _
    Single, ByVal cy As Single, ByVal radius As Single, _
    ByVal x1 As Single, ByVal y1 As Single, ByVal x2 As _
    Single, ByVal y2 As Single, ByRef ix1 As Single, ByRef _
    iy1 As Single, ByRef ix2 As Single, ByRef iy2 As _
    Single) As Integer
    Dim dx As Single
    Dim dy As Single
    Dim A As Single
    Dim B As Single
    Dim C As Single
    Dim det As Single
    Dim t As Single

    dx = x2 - x1
    dy = y2 - y1

    A = dx * dx + dy * dy
    B = 2 * (dx * (x1 - cx) + dy * (y1 - cy))
    C = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) - _
        radius * radius

    det = B * B - 4 * A * C
    If (A <= 0.0000001) Or (det < 0) Then
        ' No real solutions.
        Return 0
    ElseIf det = 0 Then
        ' One solution.
        t = -B / (2 * A)
        ix1 = x1 + t * dx
        iy1 = y1 + t * dy
        Return 1
    Else
        ' Two solutions.
        t = (-B + Sqrt(det)) / (2 * A)
        ix1 = x1 + t * dx
        iy1 = y1 + t * dy
        t = (-B - Sqrt(det)) / (2 * A)
        ix2 = x1 + t * dx
        iy2 = y1 + t * dy
        Return 2
    End If
End Function

If you need to know, a point of intersection lies on the line segment if 0 <= t <= 1 and on an extension of the segment otherwise.