Schnitt Gerade-Kegel

[0x00000001]

Hallo,

ich möchte testen, ob eine Gerade einen Kegel schneidet ( nur ob, nicht wo oder wie )

Vom Kegel habe ich folgendes gegeben: Koordinate der Spitze, Richtungsvektor, Winkel.

Gibt es da vielleicht einen hübschen Lösungsweg?

Ich habe mir schon einen erdacht, finde ihn aber sehr unelegant (und vielleicht ist er sogar falsch; habe es noch nicht getestet). Der Vollständigkeit halber möchte ich ihn noch schildern:
Ich habe zwei Geraden, die Gegebene und die durch die Kegelspitze entlang des Richtungsvektors. Ich möchte jetzt die beiden Punkte auf den Geraden rausbekommen, die sich am nächsten sind. Also berechne ich das Kreuzprodukt der beiden Geraden-Richtungen. Dieser Vektor (n) ist dann die Richtung zwischen den beiden gesuchten Punkten.
Daraus schließe ich folgendes Gleichungssystem:

pos1 + r*dir1 + d*n = pos2 + s*dir2

(In Worten: Ein Punkt auf der gegebenen Geraden plus dem Verbindugnsvektor ergibt einen Punkt auf der Kegelachse )

Durch lösen des LGS nach s kann ich jetzt rauskriegen an welcher Stelle die Gerade der Kegelachse am nächsten kommt. Und ob dieser Punkt dann noch im Kegel liegt oder nicht, dürfte nicht schwer zu errechnen sein.

Die hässliche stelle ist jetzt das Lösen des LGS, ich habe das mit einem Rechner gemacht und die Lösung für 's' ist ca. 1/2 Meter lang.

Also vielleicht weiß ja jemand was, ich habe dazu leider nichts gefunden.

[WebFritzi]

0x00000001 schrieb:

Vom Kegel habe ich folgendes gegeben: Koordinate der Spitze, Richtungsvektor, Winkel.

Da hörts schon auf! Was für einen Richtungsvektor? Was für einen Winkel? Dass ihr immer alle zu dämlich seid, euer Problem ordentlich zu beschreiben... *kopfschüttel*

[0x00000001]

Ist das jetzt eine Verständnisfrage oder ist etwas nicht Definitionskompatibel?

Ich weiß nicht, ob diese Darstellung eines Kegels mathematisch gängig oder sinvoll ist, aber es sind halt die Daten die ich da hab.

Also es geht um einen Kegel im R³. Die Position der Spitze ist...die Position der Spitze halt. Mit "Richtung" meine ich die Ausrichtung der Achse die durch die spitze verläuft und das Zentrum des Kegels darstellt (der Kegel ist immer schön gleichmäßig rund ). Und der Winkel liegt oben an bzw. in der Spitze.

Hier mal ein Bild, extra gemalt.

EDIT:
Ist ja auch egal, wollte nur fragen ob jemand zufällig weiß wie man es am besten berechnet.

[WebFritzi]

Ich habe eine Lösung gefunden. Aber die ist auch widerwärtig. Tausend Substitutionen - also auch ein riesiger Term.
Deine Lösung ist IMHO auch nicht korrekt. Die Gerade kann ja der Richtungsgeraden an einem Punkt am nächsten sein, der nicht im Schnittkreis enthalten ist, aber dann trotzdem noch den Kegel schneiden. Das ist aber nur eine Vermutung. Mag sein, dass deine Lösung trotzdem richtig ist. Hab jetzt keinen Bock, mich noch viel weiter damit zu beschäftigen.

[Windalf]

ohne mir jetzt eine konkrete Lösung überlegen zu wollen...

wenn ich jetzt nicht gerade ein denkfehler drin hab

müsste es eigentlich reichen das 2 mal im 2dfall zu betrachten und zu gucken ob die gerade beide male das dreieck das der kegel im 2dimensionalen bildet schneidet (mal von dem spezialfall abgesehen das die gerade in der einen ebene nur noch ein punkt ist, den man dann extra behandeln müsste)

[0x00000001]

@WebFritzi: trotzdem Danke.

Die Gerade kann ja der Richtungsgeraden an einem Punkt am nächsten sein, der nicht im Schnittkreis enthalten ist, aber dann trotzdem noch den Kegel schneiden.

Stimmt. Aber wenn ich zusätzlich noch teste, ob der Boden des Kegels durchstoßen wird, sollte es auch in diesen Sonderfällen funktionieren.

@Windalf: Ich glaub das geht nicht. Der Körper würde einer vierseitigen Pyramide entsprechen die durch die zwei Dreiecke aufgespannt wird.

PS:
Ich probiers jetzt einfach mal aus. Vielleicht lohnt sich die ganze Schreibarbeit am Ende ja...

[WebFritzi]

0x00000001 schrieb:

@WebFritzi: trotzdem Danke.

Die Gerade kann ja der Richtungsgeraden an einem Punkt am nächsten sein, der nicht im Schnittkreis enthalten ist, aber dann trotzdem noch den Kegel schneiden.

Stimmt. Aber wenn ich zusätzlich noch teste, ob der Boden des Kegels durchstoßen wird, sollte es auch in diesen Sonderfällen funktionieren.

Du hattest vorher nicht gesagt, dass der Kegel einen Boden hat!

Meine Lösung ging so: Nennen wir mal die Spitze s und den Richtungsvektor v. Man nehme sich die Ebene E daher, die s enthält und v als Normalenvektor hat. Gut, diese verschieben wir jetzt in Richtung des Kegelbodens. Es entsteht so eine Ebenenschar. Ist die Gerade parallel zu diesen Ebenen, so ist es relativ leicht festzustellen, ob sie den Kegel schneidet. Ist sie es nicht, so schneidet sie jede der Ebenen in einem Punkt. Diese Schnittpunkte kann man ausrechnen. Und nun prüft man, ob einer dieser Schnittpunkte in dem entsprechenden Schnittkreis liegt. Dabie bekommt man heraus, dass ein bestimmter Radikant größer als Null sein muss. Die Gerade schneidet den Kegel genau dann, wenn dieser Radikant größer oder gleich Null ist.

[japro]

also wenn $\vec{a}$ der richtungsvektor der kegelachse und $\vec{g}$ der richtungsvector der gerade ist, dann schneidet die gerade den kegel auf jeden Fall wenn ${\vec{g}\cdot\vec{a}\over |\vec{a}||\vec{g}|}<\cos\gamma$ wenn $\gamma$ der zwischenwinkel ist.

das sagt mir meine vorstellung. über einen gescheiten beweis muss ich mir noch gedanken machen.

damit sind zwar nicht alle fälle erfasst aber es ist ein ziemlich einfacher erster test, mit dem man sich in bestimmten fällen ein aufwendiges weiters prüfen ersparen kann.

(hmm das gilt aber nur wenn der kegel keinen boden hat )

[0x00000001]

Komisch, dass ihr immer von einem unendlich großen Kegel ausgeht. In meiner Gedankenwelt gibts nur Kegel mit Deckel drauf

Nachdem mir die Mathe für WebFritzi's Verfahren gefehlt hat, habe ich nun meines umgesetzt. Und es funktioniert erstaunlicherweise sogar.
Und für den Fall, dass das mal jemand wieder braucht, hier der Code: (die Vektorfunktionen sollten selbsterklärend sein)

#define VEC3 D3DXVECTOR3

bool Util::KollisionKonusGerade( D3DXVECTOR3* vPos, // Ein Punkt auf der Geraden
					   		D3DXVECTOR3* vDir, // dir Richtung der Geraden
					   		D3DXVECTOR3* vKonusSpitze, // Position der Kegelspitze
					   		D3DXVECTOR3* vKonusDir, // Ausrichtung des Kegels, die Länge dieses Vektors entspricht der Kegelhöhe
					   		float fKonusWinkel ) // Kegelwinkel
{
	// Radius des Bodens:
	float fBodenRadius = D3DXVec3Length( vKonusDir ) * sinf( fKonusWinkel * 0.5f );

	if( !VektorenSenkrecht( vDir, vKonusDir ) )
	{
		// Als erstes mal testen, ob der Strahl den Boden vom Kegel trifft:
		// Schnittpunkt Gerade-Ebene:
		float r = D3DXVec3Dot( vKonusDir, &(((*vKonusSpitze)+(*vKonusDir))-(*vPos)) ) /
				D3DXVec3Dot( vKonusDir, vDir );
		VEC3 vSchnitt = *vPos + r * (*vDir);

		// Schnittpunkt innerhalb des Kreises?
		VEC3 vAbstand = (*vKonusSpitze + *vKonusDir) - vSchnitt;
		if( D3DXVec3Dot( &vAbstand, &vAbstand ) < (fBodenRadius * fBodenRadius) )
			return true;
	}

	if( !VektorenParallel( vDir, vKonusDir ) )
	{
		// Den Punkt auf der Kegelachse berechnen der der Geraden am nächsten ist:
		VEC3 vPunkt;
		VEC3 n;
		D3DXVec3Cross( &n, vDir, vKonusDir );
		float zaehler = -(
						vDir->x * ( n.y * (vPos->z-vKonusSpitze->z) - n.z * (vPos->y-vKonusSpitze->y) ) -
						vDir->y * ( n.x * (vPos->z-vKonusSpitze->z) - n.z * (vPos->x-vKonusSpitze->x) ) +
						vDir->z * ( n.x * (vPos->y-vKonusSpitze->y) - n.y * (vPos->x-vKonusSpitze->x) ) );

		float nenner = vDir->x * (vKonusDir->y * n.z - vKonusDir->z * n.y) -
					   vDir->y * (vKonusDir->x * n.z - vKonusDir->z * n.x) +
					   vDir->z * (vKonusDir->x * n.y - vKonusDir->y * n.x);

		if( nenner == 0.0f )
			return false;

		float r = zaehler / nenner;

		vPunkt = *vKonusSpitze + r * (*vKonusDir);

		// Liegt der Punkt hinter der Kegelspitze?
		if( D3DXVec3Dot( vKonusDir, &(vPunkt-*vKonusSpitze) ) < 0 )
			return false;

        // Abstand Punkt - Gerade:
		VEC3 vTemp;
		float dg = D3DXVec3Length( D3DXVec3Cross( &vTemp, vDir, &(vPunkt-(*vPos)) ) ) / 
				   D3DXVec3Length( vDir );

		// Wenn der Abstand größer als der Bodenradius ist, trifft die Gerade schonmal nicht:
		if( dg > fBodenRadius )
			return false;

        // Senkrechter Abstand des Punktes ( der ja auf der Kegelachse liegt ) zur Kegelspitze:
		float dp = D3DXVec3Length( &(vPunkt - *vKonusSpitze) );

		// Liegt der Punkt vor dem Boden?
		if( dp > D3DXVec3Length( vKonusDir ) )
			return false;

		// Liegt der Punkt denn jetzt im Kegel?
		return( dg < dp * sinf( fKonusWinkel * 0.5f ) );

	}

	return false;
}

Es ist bestimmt nicht sonderlich schnell, aber bei mir ist der Code nicht zeitkritisch also scheiß ich drauf.