Quel est le moyen le plus rapide de trouver le point d'intersection entre un rayon et un polygone?
-
10-07-2019 - |
Question
À peu près comme le demande la question. Réponses de préférence en pseudo-code et référencées. La bonne réponse doit privilégier la vitesse à la simplicité.
La solution
Voir Intersections de rayons, de segments, de plans et de triangles en 3D . Vous pouvez trouver des moyens de trianguler des polygones.
Si vous avez vraiment besoin d'une intersection rayon / polygone, reportez-vous à la section 16.9 du rendu en temps réel (13.8 pour 2e éd.)
Nous calculons d'abord l'intersection entre le rayon et [le plan de la ploygon]
pie_p
, qui se fait facilement en remplaçantx
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, alors le rayon est considéré parallèle au plan du polygone et non intersection se produit. Sinon, le point d'intersection,p
du rayon et le plan du polygone est calculé:p = o + td
. Par la suite, le problème de décider si <=> se trouve à l'intérieur du le polygone est réduit de trois à deux dimentions ...
Voir le livre pour plus de détails.
Autres conseils
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
}
Des chapitres de livre entiers ont été consacrés à cette exigence particulière - il est trop long de décrire ici un algorithme approprié. Je suggère de lire un certain nombre d'ouvrages de référence en infographie, en particulier:
- Introduction au lancer de rayons, éd. Andrew S. Glassner, ISBN 0122861604
function Collision(PlaneOrigin,PlaneDirection,RayOrigin,RayDirection)
return RayOrigin-RayDirection*Dot(PlaneDirection,RayOrigin-PlaneOrigin)/Dot(PlaneDirection,RayDirection)
end
(PlaneDirection est le vecteur unitaire perpendiculaire au plan)