Testen, ob ein Liniensegment einer Kugel schneidet

Question

Ich versuche, ob ein Liniensegment zu bestimmen (das heißt zwischen zwei Punkten) eine Kugel schneidet. Ich bin nicht in der Position des Schnittes interessiert nur, ob das Segment die Kugeloberfläche schneidet. Hat jemand irgendwelche Vorschläge, was die effizienteste Algorithmus hierfür wäre? (Ich frage mich, ob es irgendwelche Algorithmen sind, die einfacher als die übliche ray-Kugel Schnittalgorithmen, da ich in der Schnittposition nicht interessiert bin)

Answer 1

Ich weiß nicht, was der normale Weg, es zu tun, aber wenn Sie wissen wollen, ob es schneidet, ist hier, was ich tun würde.

Generell gilt ... avoid tun sqrt () oder andere kostspielige Operationen. Wenn möglich, befassen sich mit dem Quadrat des Radius.

1. Sie fest, ob der Startpunkt innerhalb des Radius der Kugel ist. Wenn Sie wissen, dass dies nie der Fall ist, dann diesen Schritt überspringen. Wenn Sie innen sind, wird Ihr Strahl die Kugel schneiden.

Von hier an Ihrem Ausgangspunkt ist außerhalb der Sphäre.

2. Nun, stellen Sie sich die kleine Box, die Kugel passt. Wenn Sie außerhalb der Box sind, überprüfen Sie die x-Richtung, y-Richtung und z-Richtung des Strahls, um zu sehen, wenn sie die Seite der Box schneidet, dass Ihr Strahl beginnt bei. Dies sollte ein einfaches Zeichen zu überprüfen, oder einen Vergleich gegen Null. Wenn Sie außerhalb der sind und sich von ihm entfernt, werden Sie nie schneiden es.

Von hier aus sind Sie in der komplizierteren Phase. Ihr Ausgangspunkt ist zwischen der imaginären Box und der Kugel. Sie können eine vereinfachte Ausdruck mit Kalkül und Geometrie erhalten.

Der Kern von dem, was Sie tun wollen, ist festzustellen, ob der kürzeste Abstand zwischen dem Strahl und der Kugel kleiner als der Radius der Kugel ist.

Lassen Sie Ihren ray dargestellt wird durch (x0 + i t, y0 + j t, z0 + k t) und das Zentrum Ihrer Kugel sein bei (Xs, Ys, Zs ). So wollen wir t so finden, dass es die kürzeste geben würde (xS - x0 - i t, Ys - y0 - j t, zS - z0 - k t).

Let x = xS - X0, y = yX - y0, z = zS - z0, D = Betrag des Vektors squared

D = x ^ 2 -2 * x i t + (i * t) ^ 2 + y ^ 2 - 2 * y j t + (j * t) ^ 2 + z ^ 2 - 2 * z K t + (k * t) ^ 2

D = (i ^ 2 + j ^ 2 + k ^ 2) t ^ 2 - (x i + y j + z k) * 2 * t + (x ^ 2 + y ^ 2 + z ^ 2)

dD / dt = 0 = 2 * t * (i ^ 2 + j ^ 2 + k ^ 2) - 2 * (x i + y j + z * k)

t = (x i + y j + z * k) / (i ^ 2 + j ^ 2 + k ^ 2)

Stecker t zurück in die Gleichung für D = .... Ist das Ergebnis kleiner als oder gleich dem Quadrat des Radius der Kugel, haben Sie eine Kreuzung. Wenn er größer ist, dann gibt es keinen Schnittpunkt.

Answer 2

Wenn Sie nur daran interessiert sind, wenn zu wissen, ob es schneidet oder nicht, dann Ihr grundlegender Algorithmus wird wie folgt aussehen ...

Betrachten Sie den Vektor Ihrer ray Linie haben, A -.> B

Sie wissen, dass der kürzeste Abstand zwischen diesem Vektor und dem Mittelpunkt der Kugel an der Kreuzung des Strahlvektors auftritt, und einen Vektor, der bei 90 Grad dazu ist, die durch den Mittelpunkt der Kugel geht.

Sie haben also zwei Vektoren, die Gleichungen von denen voll vollständig definiert. Sie können auf den Schnittpunkt der Vektoren unter Verwendung von linearer Algebra trainieren, und damit die Länge der Linie (oder effizienter das Quadrat der Länge der Linie) und testen, ob diese kleiner ist als der Radius (oder das Quadrat des Radius ) Ihre Kugel.

Answer 3

Diese Seite eine exakte Lösung für dieses Problem hat. Im Wesentlichen man die Gleichung für die Linie in die Gleichung für die Kugel substituiert, berechnet dann die Diskriminante der resultierenden quadratischen. Die Werte der Diskriminanzfunktion zeigen Schnitt.

Answer 4

sorta Sie arbeiten müssen, dass die Position trotzdem, wenn Sie Genauigkeit wollen. Der einzige Weg, Geschwindigkeit algorithmisch zu verbessern, ist von Ray-sphere Kreuzung zu Bounding-ray-Box Kreuzung zu schalten.

Oder Sie könnten tiefer gehen und versuchen, und sqrt und andere innere Funktionsaufrufe verbessern

http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection