Quel est le moyen le plus rapide pour trouver le point d'intersection entre un rayon et un polygone?

Question

Autant que la question le demande. Réponses de préférence en pseudo code et référencées. La réponse correcte devrait valoriser la vitesse par rapport à la simplicité.

Answer 1

Voir Intersections of Rays, Segments, Planes and Triangles in 3D. Vous pouvez trouver des moyens de trianguler des polygones.

Si vous avez vraiment besoin d'intersection rayon/polygone, c'est sur 16.9 de Real-Time Rendering (13.8 pour 2nd ed).

Nous avons d'abord calculer l'intersection entre le rayon et [le plan de la ploygon] pie_p, qui est facilement réalisé par le remplacement x par le rayon.

n_p DOT (o + td) + d_p = 0 <=> t = (-d_p - n_p DOT o)/(n_p DOT d) 

Si le dénominateur |n_p DOT d| < epsilon, où epsilon est très petit nombre , le rayon est considéré parallèle au plan du polygone et pas d'intersection se produit. Sinon, le point d'intersection , p, du rayon et le plan polygonal est calculé: p = o + td. Par la suite, le problème de décider si p est à l'intérieur du polygone est réduite de trois à deux dimentions ...

Voir le livre pour plus de détails.

Answer 2

Des chapitres entiers du livre ont été consacrés à cette exigence particulière - il est trop long de décrire un algorithme approprié ici. Je suggère de lire un certain nombre de travaux de référence en infographie, en particulier:

• Introduction à Ray Tracing, ed. Andrew S. Glassner, ISBN 0122861604

Answer 3

struct point 
{ 
    float x 
    float y 
    float z 
} 

struct ray 
{ 
    point R1 
    point R2 
} 

struct polygon 
{ 
    point P[] 
    int count 
} 

float dotProduct(point A, point B) 
{ 
    return A.x*B.x + A.y*B.y + A.z*B.z 
} 

point crossProduct(point A, point B) 
{ 
    return point(A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x) 
} 

point vectorSub(point A, point B) 
{ 
    return point(A.x-B.x, A.y-B.y, A.z-B.z) 
} 

point scalarMult(float a, Point B) 
{ 
    return point(a*B.x, a*B.y, a*B.z) 
} 

bool findIntersection(ray Ray, polygon Poly, point& Answer) 
{ 
    point plane_normal = crossProduct(vectorSub(Poly.P[1], Poly.P[0]), vectorSub(Poly.P[2], Poly.P[0])) 

    float denominator = dotProduct(vectorSub(Ray.R2, Poly.P[0]), plane_normal) 

    if (denominator == 0) { return FALSE } // ray is parallel to the polygon 

    float ray_scalar = dotProduct(vectorSub(Poly.P[0], Ray.R1), plane_normal) 

    Answer = vectorAdd(Ray.R1, scalarMult(ray_scalar, Ray.R2)) 

    // verify that the point falls inside the polygon 

    point test_line = vectorSub(Answer, Poly.P[0]) 
    point test_axis = crossProduct(plane_normal, test_line) 

    bool point_is_inside = FALSE 

    point test_point = vectorSub(Poly.P[1], Answer) 
    bool prev_point_ahead = (dotProduct(test_line, test_point) > 0) 
    bool prev_point_above = (dotProduct(test_axis, test_point) > 0) 

    bool this_point_ahead 
    bool this_point_above 

    int index = 2; 
    while (index < Poly.count) 
    { 
     test_point = vectorSub(Poly.P[index], Answer) 
     this_point_ahead = (dotProduct(test_line, test_point) > 0) 

     if (prev_point_ahead OR this_point_ahead) 
     { 
      this_point_above = (dotProduct(test_axis, test_point) > 0) 

      if (prev_point_above XOR this_point_above) 
      { 
       point_is_inside = !point_is_inside 
      } 
     } 

     prev_point_ahead = this_point_ahead 
     prev_point_above = this_point_above 
     index++ 
    } 

    return point_is_inside 
}

Answer 4

function Collision(PlaneOrigin,PlaneDirection,RayOrigin,RayDirection) 
    return RayOrigin-RayDirection*Dot(PlaneDirection,RayOrigin-PlaneOrigin)/Dot(PlaneDirection,RayDirection) 
end 

(PlaneDirection est le vecteur unitaire qui est perpendiculaire au plan)