Versuchen zu optimieren-line-vs Zylinder Kreuzung
Mein Gehirn Schmelzen über einen line-segment-vs-Zylinder-Kreuzung routine, die ich gearbeitet habe.
///Line segment VS <cylinder>
//- cylinder (A, B, r) (start point, end point, radius)
//- line has starting point (x0, y0, z0) and ending point (x0+ux, y0+uy, z0+uz) ((ux, uy, uz) is "direction")
//=> start = (x0, y0, z0)
// dir = (ux, uy, uz)
// A
// B
// r
// optimize? (= don't care for t > 1)
//<= t = "time" of intersection
// norm = surface normal of intersection point
void CollisionExecuter::cylinderVSline(const Ogre::Vector3& start, const Ogre::Vector3& dir, const Ogre::Vector3& A, const Ogre::Vector3& B, const double r,
const bool optimize, double& t, Ogre::Vector3& normal) {
t = NaN;
//Solution : http://www.gamedev.net/community/forums/topic.asp?topic_id=467789
double cxmin, cymin, czmin, cxmax, cymax, czmax;
if (A.z < B.z) { czmin = A.z - r; czmax = B.z + r; } else { czmin = B.z - r; czmax = A.z + r; }
if (A.y < B.y) { cymin = A.y - r; cymax = B.y + r; } else { cymin = B.y - r; cymax = A.y + r; }
if (A.x < B.x) { cxmin = A.x - r; cxmax = B.x + r; } else { cxmin = B.x - r; cxmax = A.x + r; }
if (optimize) {
if (start.z >= czmax && (start.z + dir.z) > czmax) return;
if (start.z <= czmin && (start.z + dir.z) < czmin) return;
if (start.y >= cymax && (start.y + dir.y) > cymax) return;
if (start.y <= cymin && (start.y + dir.y) < cymin) return;
if (start.x >= cxmax && (start.x + dir.x) > cxmax) return;
if (start.x <= cxmin && (start.x + dir.x) < cxmin) return;
}
Ogre::Vector3 AB = B - A;
Ogre::Vector3 AO = start - A;
Ogre::Vector3 AOxAB = AO.crossProduct(AB);
Ogre::Vector3 VxAB = dir.crossProduct(AB);
double ab2 = AB.dotProduct(AB);
double a = VxAB.dotProduct(VxAB);
double b = 2 * VxAB.dotProduct(AOxAB);
double c = AOxAB.dotProduct(AOxAB) - (r*r * ab2);
double d = b * b - 4 * a * c;
if (d < 0) return;
double time = (-b - sqrt(d)) / (2 * a);
if (time < 0) return;
Ogre::Vector3 intersection = start + dir * time; ///intersection point
Ogre::Vector3 projection = A + (AB.dotProduct(intersection - A) / ab2) * AB; ///intersection projected onto cylinder axis
if ((projection - A).length() + (B - projection).length() > AB.length()) return; ///THIS IS THE SLOW SAFE WAY
//if (projection.z > czmax - r || projection.z < czmin + r ||
//projection.y > cymax - r || projection.y < cymin + r ||
//projection.x > cxmax - r || projection.x < cxmin + r ) return; ///THIS IS THE FASTER BUGGY WAY
normal = (intersection - projection);
normal.normalise();
t = time; ///at last
}Ich dachte, dieser Weg, um die Geschwindigkeit der Entdeckung, ob die Projektion der Schnittpunkt liegt innerhalb des Zylinders der Länge. Jedoch, es funktioniert nicht und ich kann nicht wirklich bekommen, weil es scheint so logisch :
wenn der projizierte Punkt x -, y-oder z-Koordinate nicht innerhalb des Zylinders Grenzen, es sollte sein, als außerhalb. Es scheint jedoch, dass dies nicht funktioniert in der Praxis.
Jede Hilfe wäre sehr geschätzt werden!
Cheers,
Bill Kotsias
Edit : Es scheint, dass die Probleme steigen mit den Grenz-Fällen ich.e, wenn der Zylinder parallel zu einer der Achsen. Rundungsfehler kommen in die Gleichung, und die "Optimierung" nicht mehr funktioniert korrekt.
Vielleicht, wenn die Logik ist richtig ist, die Probleme verschwinden durch einfügen von ein wenig Toleranz wie :
if (projection.z > czmax - r + 0.001 || projection.z < czmin + r - 0.001 || ... etc...InformationsquelleAutor Bill Kotsias | 2010-11-02
Du musst angemeldet sein, um einen Kommentar abzugeben.
Des Zylinders ist kreisförmig, richtig? Könnte man Koordinaten umrechnen, so dass die Mittellinie des Zylinders wirkt als die Z-Achse. Dann haben Sie ein 2D-problem von sich überschneidenden eine Linie mit einem Kreis. Die Schnittpunkte werden in Bezug auf einen parameter geht von 0 bis 1 entlang der Länge der Zeile, so können Sie berechnen, Ihre Positionen in diesem Koordinatensystem und vergleichen Sie die Ober-und Unterseite des Zylinders.
Sollten Sie in der Lage sein, es zu tun alle in die geschlossene form. Keine Toleranzen. Und sicher, Sie bekommen Singularitäten und imaginären Lösungen. Sie scheinen gedacht zu haben, der all dies, so dass ich denke, ich bin nicht sicher, was die Frage ist.
InformationsquelleAutor Mike Dunlavey
Dies ist, was ich benutze, vielleicht hilft es:
InformationsquelleAutor Ruud van Gaal
Mike ' s Antwort ist gut. Für jede knifflige Form man am besten aus, finden Sie die Transformationsmatrix T, die Karten, die es in einen schönen aufrechten version, in diesem Fall eine glatte Zylinder mit dem radius 1. Höhe 1, würde den job zu erledigen schön. Herauszufinden, Ihre neue Linie, die in diesem neuen Raum, führen Sie die Berechnung, konvertieren zurück.
Allerdings, wenn Sie schauen, um zu optimieren (und es klingt wie Sie sind), es gibt wahrscheinlich Lasten, die Sie tun können.
Zum Beispiel, berechnen Sie den kürzesten Abstand zwischen zwei Linien, die-wahrscheinlich mit dem Punkt-Produkt der Regel-stellen Sie sich vor der Teilnahme an zwei Linien, die von einem thread. Dann, wenn in diesem thread ist die kürzeste von allen möglichen threads, dann wird es senkrecht zu beiden Linien, so Faden.LineA = Thread.LineB = 0
Wenn der kürzeste Abstand größer als der radius der Zylinder, es ist ein Fräulein.
Könnten Sie definieren den Ort der Zylinder mit x -, y -, z -, und thrash, die ganze Sache als ein schreckliches quadratischen Gleichung, und optimieren durch die Berechnung der diskriminante ersten und der Rückkehr kein-Treffer-wenn dieser negativ ist.
Definieren den Ort, nehmen einen beliebigen Punkt P=(x,y,z). legen Sie es als eine senkrecht auf der Mittellinie Ihrer Zylinder, und betrachten Sie die Größe im Quadrat. wenn das gleich R^2, Punkt.
Dann werfen Sie Ihre Linie {s = U + lamda*V} in das Chaos, und Sie würden am Ende mit etwas Hintern hässlich quadratische in lamda. aber das wäre wahrscheinlich schneller als Matrizen hantieren, es sei denn, Sie können Holen Sie sich die hardware, es zu tun (ich vermute, OpenGL hat eine Funktion, um die hardware zu tun, diese superfast).
Es hängt alles davon ab, wie viel Optimierung Sie wollen; ich persönlich würde mit Mike ' s Antwort, es sei denn, es war ein wirklich guter Grund, nicht zu.
PS könnte Man mehr helfen, wenn Sie erklären, die Technik, die Sie verwenden, anstatt nur dumping code, so dass es dem Leser überlassen, herauszufinden, was Sie tun.
InformationsquelleAutor P i
Haben Sie darüber nachgedacht, es auf diese Weise?
Eines Zylinders ist im wesentlichen ein "fettes" line-segment so ein Weg, dies zu tun wäre, finden Sie den nächsten Punkt auf Linie, segment, Zylinder center-line) , line segment (the line segment, das Sie testen für Kreuzung).
Von dort aus kontrollieren Sie den Abstand zwischen diesem am nächsten Punkt, und die andere Strecke, und vergleichen Sie mit dem radius.
Zu diesem Zeitpunkt haben Sie eine "Pille vs Line-Segment" zu testen, aber Sie könnte wahrscheinlich einige Flugzeug-tests zu "chop off" der Kappen auf die Pille um einen Zylinder zu machen.
Schießen aus der Hüfte ein bisschen aber so hoffe es hilft (:
InformationsquelleAutor Alan Wolfe