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é.Quel est le moyen le plus rapide pour trouver le point d'intersection entre un rayon et un polygone?
Quel est le moyen le plus rapide pour trouver le point d'intersection entre un rayon et un polygone?
Répondre
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 remplacementx
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 sip
est à l'intérieur du polygone est réduite de trois à deux dimentions ...
Voir le livre pour plus de détails.
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
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
}
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)
- 1. Quel est le moyen le plus rapide de trouver un fichier dans Zend Studio pour Eclipse?
- 2. NSMutableArray. Quel est le moyen le plus rapide pour le convertir en un tableau C simple?
- 3. Meilleur/le plus simple/le moyen le plus rapide d'obtenir un chemin relatif entre deux fichiers?
- 4. Quel est le moyen le plus rapide d'apprendre l'objectif-c pour un développeur expérimenté en PHP?
- 5. Quel est le moyen le plus rapide pour combiner deux fichiers xml en un
- 6. Quel est le moyen le plus rapide pour supprimer un grand dossier dans Windows?
- 7. Quel est le moyen le plus rapide pour télécharger un énorme ensemble de données à appengine?
- 8. Le moyen le plus rapide pour trouver la distance minimale entre les points
- 9. Quel est le moyen le plus rapide pour lire/écrire sur le disque dans .NET?
- 10. Quel est le moyen le plus rapide de détecter un hôte inaccessible en Java?
- 11. Quel est le moyen le plus rapide de générer un ensemble unique en .net 2
- 12. Quel est le moyen le plus rapide de remplir un tableau avec des nombres en PHP?
- 13. Trouver un point dans un polygone complexe
- 14. Quel est le moyen le plus simple et le plus rapide pour mesurer les performances HD en utilisant Python?
- 15. Dans jQuery, quel est le moyen le plus rapide de sélectionner un groupe d'éléments?
- 16. Quel est le moyen le plus rapide de parcourir un objet Excel Range à l'envers?
- 17. Un éditeur pour un objet de données en swing, quel est le moyen le plus simple?
- 18. Quel est le moyen le meilleur et le plus rapide pour écrire dans le fichier Excel en utilisant C#?
- 19. Quel est le moyen le plus rapide de ColdFusion pour obtenir le premier et le dernier jour du trimestre?
- 20. Quel est le moyen le plus rapide de commencer avec le framework Kohana PHP?
- 21. Le moyen le plus rapide de partager des objets de données entre un serveur Java et un client C#
- 22. Le moyen le plus rapide pour supprimer un arbre de répertoires dans un fichier batch
- 23. Dans .Net, quel est le moyen le plus rapide pour trouver récursivement tous les fichiers d'un répertoire racine?
- 24. Quel est le moyen le plus rapide pour déterminer si une URL existe en PHP?
- 25. Le moyen le plus rapide/le plus court de construire un arbre unique en Ruby?
- 26. Quel est le moyen le plus rapide de copier mon tableau?
- 27. algorithme le plus rapide pour obtenir le changement moyen
- 28. Quel est le moyen le plus rapide de dédupliquer une chaîne en C# (ASP.net)
- 29. Quel est le moyen le plus rapide d'interroger à partir d'une base de données EAV historique?
- 30. Quel est le moyen le plus rapide de vérifier si un site web est en Perl ou C?
Ce fut plus d'une question de référence générale, mais il est vrai que surfer doux a l'algorithme le plus à jour. –