Wie finde ich die größte Kugel, die in einen Kegelstumpf passt?

12

Wie finden Sie die größte Kugel, die Sie perspektivisch zeichnen können?

Von oben gesehen wäre das:

Bildbeschreibung hier eingeben

Hinzugefügt: Auf dem Kegelstumpf rechts habe ich vier Punkte markiert, von denen ich glaube, dass wir etwas wissen. Wir können alle acht Ecken des Frusums und die Zentren des nahen und des fernen Endes entfernen. Wir kennen also Punkt 1, 3 und 4. Wir wissen auch, dass Punkt 2 dieselbe Entfernung von 3 wie 4 von 3 hat. Dann können wir den nächsten Punkt auf der Linie 1 bis 4 zu Punkt 2 berechnen, um die zu erhalten Center? Aber die eigentliche Mathematik und der eigentliche Code entgehen mir.

Ich möchte möglichst große Modelle zeichnen (die ungefähr kugelförmig sind und für die ich eine Miniball-Begrenzungskugel habe).

Update: Ich habe versucht, den von Bobobobo und Nathan Reed vorgeschlagenen Incircle -on-Two-Planes-Ansatz zu implementieren :

function getFrustumsInsphere(viewport,invMvpMatrix) {
    var midX = viewport[0]+viewport[2]/2,
        midY = viewport[1]+viewport[3]/2,
        centre = unproject(midX,midY,null,null,viewport,invMvpMatrix),
        incircle = function(a,b) {
            var c = ray_ray_closest_point_3(a,b);
            a = a[1]; // far clip plane
            b = b[1]; // far clip plane
            c = c[1]; // camera
            var A = vec3_length(vec3_sub(b,c)),
                B = vec3_length(vec3_sub(a,c)),
                C = vec3_length(vec3_sub(a,b)),
                P = 1/(A+B+C),
                x = ((A*a[0])+(B*a[1])+(C*a[2]))*P,
                y = ((A*b[0])+(B*b[1])+(C*b[2]))*P,
                z = ((A*c[0])+(B*c[1])+(C*c[2]))*P;
            c = [x,y,z]; // now the centre of the incircle
            c.push(vec3_length(vec3_sub(centre[1],c))); // add its radius
            return c;
        },
        left = unproject(viewport[0],midY,null,null,viewport,invMvpMatrix),
        right = unproject(viewport[2],midY,null,null,viewport,invMvpMatrix),
        horiz = incircle(left,right),
        top = unproject(midX,viewport[1],null,null,viewport,invMvpMatrix),
        bottom = unproject(midX,viewport[3],null,null,viewport,invMvpMatrix),
        vert = incircle(top,bottom);
    return horiz[3]<vert[3]? horiz: vert;
}

Ich gebe zu, dass ich es fliege; Ich versuche, 2D-Code anzupassen , indem ich ihn auf drei Dimensionen ausdehne. Die insphere wird nicht korrekt berechnet. Der Mittelpunkt der Kugel scheint jedes Mal auf der Linie zwischen der Kamera und der linken oberen Ecke zu liegen und zu groß (oder zu nah) zu sein. Gibt es offensichtliche Fehler in meinem Code? Funktioniert der Ansatz, wenn er fixiert ist?

Wille
quelle
Muss sich die Kugel wie im Bild ganz auf der anderen Seite der Fernebene befinden?
Mikael Högström
@ MikaelHögström Ich stell sie mir vor, um so groß wie möglich zu sein?
Wird
Hmm, ich denke, es hängt von Ihrem Zweck ab ... Wenn Sie eine Kugel mit einer Hälfte jenseits der Fernebene zeichnen, dann wäre das größer, aber vielleicht widerspricht das Ihrem Zweck?
Mikael Högström
@ MikaelHögström aha ich verstehe deine frage; ja ich will das ganze modell gezeichnet haben, kein fernes flugzeug durchschneiden.
Wird

Antworten:

12

Ich gehe davon aus, dass Ihr Kegelstumpf symmetrisch ist, da Ihre Zeichnung dies zu suggerieren scheint. Es gibt drei Einschränkungen (zwei, wenn Ihr Kegelstumpf 2D ist):

A. Die Kugel kann nicht größer sein als der Abstand zwischen der nahen und der fernen Ebene

Wenn Dder Nah-Fern-Abstand ist, ist die erste Einschränkung einfach:

R  D / 2

B. die Kugel nicht breiter werden kann als die Seitenebenen

Angenommen, die andere Einschränkung αist der halbe Winkel des Kegelstumpfs und Ldie halbe Breite der fernen Ebene, wie in dieser Zeichnung gezeigt:

Kegelstumpf

Die erste Formel wird durch Trigonometrie im Dreieck angegeben. Die zweite ergibt sich aus der Summe der Winkel eines Dreiecks. Was uns die zweite Einschränkung gibt:

R  L tan((π - 2α) / 4)

Wenn Ihr Kegelstumpf 3D ist, haben Sie eine dritte Einschränkung mit neuen Lund αWerten.

Endergebnis

Der RWert, den Sie suchen, ist der minder drei Grenzen.

Wie bekomme ich die Parameter?

Wenn Sie das Kegelstumpf im Blickfeld oder im Weltraum entfernen können, können Sie L, D und α folgendermaßen berechnen, wobei die PPunkte von der nahen Ebene und die QPunkte von der fernen Ebene stammen:

formula2

Pfeile bedeuten Vektoren, "." Ist das Skalarprodukt und || gibt die Länge eines Vektors an. Ersetzen Sie Q2mit Q3und P2mit P3, um L und α in der vertikalen Dimension zu erhalten.

sam hocevar
quelle
Wie bestimmen Sie aus dem Kegelstumpf (berechnet durch Entfernen der Projektionspunkte, um nah und fern zu werden) das Sichtfeld? Und in 3D gibt es nur zwei Möglichkeiten, nicht drei, oder? Meine Versuche, Ihren Algorithmus in Code umzusetzen, geben mir immer ein sehr großes R.
Will
@Will Ich habe eine zweite Zeichnung mit Formeln hinzugefügt, die hoffentlich helfen werden.
Sam Hocevar
2

In 2D: Betrachten Sie den Kegelstumpf als Dreieck (2D)

Bildbeschreibung hier eingeben

Sie wollen dann die finden incircle des Dreiecks.

Als 3D-Problem müssen Sie die Kugel einer quadratischen Pyramide finden.

Wenn ich die Formel hätte, würde ich sie hier ausdrucken, aber leider kenne ich die Formel nicht.

Bobobobo
quelle
2
Es reicht wahrscheinlich aus, den Umkreis des vertikalen oder horizontalen Kegelstumpfes in 2D zu finden, je nachdem, welcher das kleinere Sichtfeld aufweist, zumindest für "Standard" -Kegelstümpfe (nicht geschert oder so).
Nathan Reed
1

Die größtmögliche Kugel sollte die entfernte Ebene (mit den Begriffen für Sichtstörungen hier) genau in der Mitte berühren. Es würde auch die obere / untere oder die linke / rechte Ebene berühren, abhängig davon, welcher FoV-Winkel kleiner ist. Ich muss sagen, dass ich keinen tatsächlichen mathematischen Beweis für diese Annahmen habe, aber sie sollten stimmen. Vielleicht hat jemand eine Idee, wie man das beweisen kann.

Eine Kugel kann durch ihren Mittelpunkt und einen Radius definiert werden. Cx und Cy ist dasselbe wie die Mitte des Flugzeugs.

Cz und der Radius können durch Lösen eines Gleichungssystems basierend auf den oben aufgeführten Annahmen erhalten werden.

T ist entweder die untere / obere Ebene oder die linke / rechte Ebene (siehe oben) mit t1, t2 und t3 als normalisiertem Normalenvektor und t4 als Abstand vom Ursprung. f ist die Mitte des Flugzeugs.

t1 * cx + t2 * cy + t3 * cz - t4 = r

-fz + cz = r

t1 * cx + t2 * cy + t3 * cz - t4 = -fz + cz

t1 * cx + t2 * cy + fz - t2 = + cz - t3 * cz

t1 * cx + t2 * cy - fz - t2 = cz * (1 - t3)

cz = (t1 · cx + t2 · cy - fz - t2) / (1 - t3)

r wird dann durch Einfügen von cz berechnet: -fz + cz = r

Sie können alle Flugzeuge mit der Projektionsmatrix abrufen. (In diesem Fall nicht ViewProjection)

danach müssen Sie die Kugel an die richtige Stelle verschieben: C '= invers (Ansicht) * C

Luis W
quelle
1

Ich versuche, etwas Ähnliches zu tun, und in meinem Fall ist Geschwindigkeit wichtiger als Genauigkeit, solange die Kugel nicht außerhalb der Grenzen des Kegelstumpfs existiert.

Wenn Sie den kürzesten Abstand zwischen Liniensegeln (oder Flächen in 3d) berechnen, kann der kürzeste gefundene Abstand als Durchmesser eines Kreises / einer Kugel verwendet werden, der / die vollständig im Kegelstumpf liegt. Der Ursprung des Kreises / der Kugel könnte einfach der Durchschnitt aller Eckpunkte (Summe & Division) sein. Es wäre ziemlich schnell und würde auch für alle Arten von konvexen Polyedern funktionieren.

Der einzige Nachteil ist, dass der Kreis oder die Kugel nicht unbedingt der größtmögliche Kreis oder die größtmögliche Fläche sein muss. Bei einem Kegelstumpf mit viel Volumen und einer sehr kurzen Kante würde sich der Kreis / die Kugel viel weniger als möglich den Kegelstumpfraum teilen.

Eine andere Idee

Wenn Sie die Inspiration eines 3D-Betrachtungsstumpfs wünschen und die Perspektivmatrix haben, die zum Konstruieren dieses Stumpfs verwendet wird, können Sie diese Matrix einfach auf der Inspiration eines Einheitswürfels verwenden, und dies sollte eine perfekte Inspiration für den Stumpf sein. (Der Durchmesser der Insphäre eines Würfels ist die Länge einer der Würfelkanten, der Mittelpunkt ist die Mitte des Würfels, die den Durchschnitt der Scheitelpunkte des Würfels darstellt.)

null
quelle