Compte tenu d'une boîte de sélection, avec définitions telles que liées.min. (x / y / z) , lié.max (x / y / z) , et Deux points dans l'espace 3D (exprimé en tant que vector3 objets), comment puis-je déterminer si la ligne faite par les deux points intersecte la zone de liaison?
5 Réponses :
Vous pouvez vous représenter votre boîte de sélection de 12 triangles (2 pour chacun des 6 faces). Ensuite, vous pouvez vérifier l'intersection de votre ligne avec chacun d'eux. J'ai une fonction d'intersection de ligne-triangle, mais il a été écrit pour mon propre moteur de rendu logiciel, pas pour D3D. Je peux essayer de le convertir si vous avez besoin du code.
Je pourrais faire cela, mais je ne sais pas à quel point ce serait la performance ... Ceci exécute toutes les "mises à jour", tant de fois par seconde, et je ne sais pas comment cela va taire, mais cela vaut certainement la peine d'essayer. Si vous publiez le code pour l'intersection de la ligne / triangle, et je peux obtenir ce travail (et ce n'est pas lent), je vous le donnerai.
Il existe une implémentation en C ++ disponible en ligne ici: Intersection de la boîte de ligne ( http://www.3dkingdoms.com/weekly/weekly.php ? A = 3 )
Un autre lien, avec références (et code) pour beaucoup de tests d'intersection: http: // www .realtimerendering.com / intersections.html
Si vous souhaitez en savoir plus sur les tests d'intersection, celui-ci est la Bible: Détection de collision en temps réel (Amazon)
EDIT: L'algorithme de ce papier ("une boîte de rayons efficace et robuste Algorithme d'intersection ", Amy Williams et Steve Barrlust et R. Keith Morley et Peter Shirley; Journal of Graphics, GPU et Game Tools, vol. 10 (1), 49-54, 2005) semblent particulièrement concis et livrés avec (C ++) code source aussi.
Après avoir converti le code dans le premier lien vers non hideux C ++, il semble fonctionner pour la plupart. Je posterai le code ici pour quelqu'un d'autre qui en a besoin, de sorte qu'ils ne doivent pas aussi la convertir.
Voici une façon de le faire si vous voulez faire les mathématiques vous-même: intersectez la ligne avec chacun des 6 plans créés par la boîte à bornes.
La représentation du vecteur de la ligne est X = B + T * D, où B est un tuple (x, y, z) du point de base (disons, votre premier point) et D est la direction de la ligne, à nouveau exprimé en tuple (DX, DY, DZ). Vous obtenez la direction en soustrayant l'un des points de l'autre, donc si vous avez des points P1 (X1, Y1, Z1) et P2 (x2, Y2, Z2), puis d = p2 - p1 et b = p1, ce qui signifie d = (x2 - x1, Y2 - Y1, Z2 - Z1). Nous appellerons les éléments de ce vecteur DX, DY et DZ.
La représentation paramétrique du plan est x + y + z = c. Donc, convertissez votre boîte de sélection à cette représentation, puis utilisez la représentation paramétrique de votre ligne, par exemple. Les trois équations x = x1 + t dx, y = y1 + t dy, z = z1 + t * dz, pour substituer x, y et z dans votre équation plane. Résoudre pour t. Étant donné que chacun de vos 6 plans va être parallèle à l'avion créé par 2 de l'axe, votre problème devient plus facile. Par exemple, pour l'avion parallèlement au plan créé par l'axe X et Y, votre équation de plan devient simplement Z = C, tandis que c est la coordonnée Z de l'un de vos points de boîte de sélection, et ainsi de suite.
Utilisez maintenant T pour calculer le point d'intersection de la ligne avec votre plan. (Si T est <0 ou> 1, votre ligne se croisit en dehors de P1-P2, si T> = 0 et T <= 1, alors votre ligne intersecte le plan quelque part entre p1 et p2)
Maintenant, vous n'êtes pas encore fait. L'équation plane vous donne un plan, pas un rectangle, le point d'intersection avec le plan peut être en dehors de votre rectangle, mais que vous avez maintenant les coordonnées de votre intersection (x = x1 + t * dx et ainsi de suite), Vous pouvez facilement voir si ce point est à l'intérieur du rectangle de votre boîte de sélection. Votre problème est maintenant réduit pour vérifier si un point dans l'espace 2D est à l'intérieur d'un rectangle de boîte à bornes, qui est trivial à vérifier.
Bien sûr, la première chose à faire si vous utilisez réellement cette solution, vérifiez si la ligne est également alignée sur un axe car dans ce cas, votre code d'intersection devient trivial et cela s'occupera également du problème de la ligne n'échantillonnant pas certains avions, par exemple nombres énormes ou minuscules de t, peut-être même trop ou de sous-flux.
Je parie qu'il y a des moyens plus rapides de faire cela, mais cela fonctionnera.
S'il y a des façons plus rapides de faire cela, j'ai besoin de savoir à leur sujet, car ce code va courir n'importe où jusqu'à 100 fois par seconde, et chaque calcul que j'ajoute ralentit le jeu.
HMMM, en fait, je pense que l'algorithme que vous avez affiché est plus lent que ce que j'ai proposé, car il semble fonctionner avec des vecteurs, par exemple. Faire beaucoup d'ajouts et de quatre multiplications pour chaque appel à la réception, car il n'opère pas que votre boîte à bornes est alignée sur le système de coordonnées, ce qui signifie que vous pouvez lancer deux des trois équations paramétriques pour chaque intersection de l'avion. Je pense que vous pouvez vous échapper avec une seule multiplication par intersection.
Ooops, non, désolé. Jeter ça. Vous avez besoin des trois multiplications pour calculer les coordonnées du succès. Zut.
Voici le code qui semble fonctionner, converti de la réponse de Greg S en C #:
bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit)
{
if (L2.x < B1.x && L1.x < B1.x) return false;
if (L2.x > B2.x && L1.x > B2.x) return false;
if (L2.y < B1.y && L1.y < B1.y) return false;
if (L2.y > B2.y && L1.y > B2.y) return false;
if (L2.z < B1.z && L1.z < B1.z) return false;
if (L2.z > B2.z && L1.z > B2.z) return false;
if (L1.x > B1.x && L1.x < B2.x &&
L1.y > B1.y && L1.y < B2.y &&
L1.z > B1.z && L1.z < B2.z)
{
Hit = L1;
return true;
}
if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
|| (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
|| (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))
|| (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
|| (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
|| (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)))
return true;
return false;
}
bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit)
{
if ((fDst1 * fDst2) >= 0.0f) return false;
if (fDst1 == fDst2) return false;
Hit = P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1));
return true;
}
bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis)
{
if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true;
if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true;
if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true;
return false;
}
Version JavaScript, basée sur SPIKEX Réponse et GLMatrix:
// all args are Vec3, Hit will be filled by this algo
function checkLineBox( B1, B2, L1, L2, Hit)
{
if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
if (L1[0] > B1[0] && L1[0] < B2[0] &&
L1[1] > B1[1] && L1[1] < B2[1] &&
L1[2] > B1[2] && L1[2] < B2[2])
{
vec3.set( L1, Hit);
return true;
}
if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
|| (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
|| (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))
|| (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
|| (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
|| (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)))
return true;
return false;
}
var temp = vec3.create();
function getIntersection( fDst1, fDst2, P1, P2, Hit)
{
if ((fDst1 * fDst2) >= 0) return false;
if (fDst1 == fDst2) return false;
vec3.subtract(P2, P1, temp);
vec3.scale( temp, (-fDst1 / (fDst2 - fDst1)));
vec3.add( temp, P1, Hit);
return true;
}
function inBox(Hit, B1, B2, Axis)
{
if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true;
if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
return false;
}