Guten Morgen.
Ja, so etwas könnte ich jetzt gut brauchen. Könntest Du es mir irgendwie zukommen lassen, hier reinhängen vielleicht?


Was die Kollisionsberechnungen angeht, habe ich jetzt eine steile Lernkurve hinter mir. So locker vom Hocker, wie ich es anfangs dachte geht das gar nicht. Zum Beispiel das http://wiki.delphigl.com/index.php/Werkzeugkiste#Schnittpunkt_einer_Kugel_mit_einer_Linie_.28Polygonkante.29.

Dieses Ding ist bloß die Spitze eines Eisberges, die dahinter steckende Theorie braucht ein wenig mehr Beschäftigung mit der Materie.

Nur um das nochmal klar zu stellen: es geht um eine Kollision einer Kugel mit einer Polygonkante, wobei zu berücksichtigen ist, dass die Kugel vor der Kollision abgefangen werden muss, weil das Eindringen in die Polygonkante nicht erwünscht ist.

Ich habe ursprünglich mit einer Ebene experimentiert - was sich anschließend als falsch erwiesen hat - und bin dann auf die Idee gekommen, die Polygonkante mit einem Zylinder zu ummanteln, wo man ebenfalls auf ellenlange Ableitungen kommt. Die Theorie sieht einfach und nett aus, die mathematische Ableitung dahinter ist aber ganz schön heavy. Gestern habe ich mich mal in die Vorlagen vertieft, die erin verwendet hat.

Imho hat erin die Lösung von Kasper Fauerby genommen, die auf dem 3D Level bleibt und nicht die Lösung von Jorrit Rouwe.

Wenn man z.B. wissen will, wo diese Funktion "Schnittpunkt einer_Kugel mit einer_Linie" herkommt, so sollte man bei Fauerby nachsehen. Aber auch Fauerby hat die Ableitungen nicht dabei und hat in seiner Abhandlung auch nicht wirklich viel Literatur angegeben. Von den Literatur-Links, die Rouwe angegeben hat, ist im Internet nur noch einer zu finden, und der verweist vielfach nur auf Artikel oder Bücher, die so adhoc nicht zur Verfügung stehen.

Daher hier nur ganz kurz angerissen:
Quelle (lt. Kollisionstutorial Nr.2, ganz unten): http://www.peroxide.dk/papers/collision/collision.pdf, Autor Kasper Fauerby, Abschnitt 3.4 "The sweep test":

Hier beschäftigt er sich als erstes mit der Kollision mit den Polygon-Eckpunkten, denn die Kollision mit den Kanten leitet sich dann daraus ab.

Die Kugel hat einen möglichen Kollisionspartner (ein Polygon) erkannt und testet jetzt, ob sie mit den Eckpunkten kollidieren wird. Zusätzlich Info: die Kugel ist in Bewegung. Zu einem Beginnzeitpunkt t0 (wo der Kugelmittelpunkt einen festgelegten Wert hat) konstruiert sie einen Strahl, aber NICHT vom Kugelmittelpunkt zum Zielpunkt, denn sie fliegt ja gar nicht auf den Punkt zu. Die Sache ist ein wenig komplizierter, siehe http://wiki.delphigl.com/index.php/Tutorial_Kollision2#Kollision_mit_den_Ecken_und_Kanten. Man sollte sich das Bild im Tutorial dazu ansehen, da sieht man auf einem Blick, worauf es ankommt.

Und weil das etwas komplizierter ist, ist die Mathe dahinter ebenfalls komplizierter. Die Entfernung zwischen dem augenblicklichen Kugelmittelpunkt und dem Zielpunkt ist lt. Fauerby (C(t) - p), C(t) heißt übrigens Center, nämlich Spherecenter, in Abhängigkeit von der Zeit und p ist die statische Polygonecke.

Die Ortsveränderung von C abhängig von der Zeit: C(t) = basePoint + t*velocity, t liegt im Intervall [0,1]

Fauerby schreibt jetzt: "Wenn jemals die Distanz zwischen dem bewegten Kugelzentrum und dem Vertex genau 1 ist, dann findet die Kollision statt." Das ist m.E. aber falsch und die Begründung, warum er jetzt die folgende Gleichung aufstellt, fand ich ziemlich fadenscheinig: (C(t)-p) * (C(t)-p) = 1². Oder sagen wir, nach Fauerbys Begründung habe ich es nicht verstanden.

Aber dazu ist etwas in unserem Wiki zu finden: http://wiki.delphigl.com/index.php/Standard_Skalarprodukt. Wenn Ihr dort ein wenig runterscrollt, findet ihr eine standfestere Begründung und dort ist auch ein Beispiel "Kugel - Ray - Intersection" von Delphic (wo ich auch hinkomme - Nico ist schon dort gewesen ).

So. Jetzt wissen wir, was es mit (C(t)-p) * (C(t)-p) = 1² auf sich hat. Und jetzt setzen wir für C(t) ein (C(t) = basePoint + t*velocity, siehe oben). Hier erhalten wir eine Formel, die sich zu einer quadratischen Gleichung auswächst mit der einzigen Variable namens "t". Dieses t ermöglicht es uns, den zukünftigen Kollisionspunkt zu errechnen.
Die Entwicklung von (C(t)-p) * (C(t)-p) = 1² zu dieser quadratischen Gleichung findet ihr auch in Nicos Wiki-Artikel.


@erin: ich habe es aufgegeben, eine alternative Kollisionsberechnung aufzustellen, Du hast ja schon eine Berechnung, die State Of the Art ist. Hab nur ein bissel gebraucht, um draufzukommen. Ich werde also Deine Kollisionsberechnung implementieren, denn das Programm fürs Benchmarking habe ich schon geschrieben. Und ich habe heute nachmittag wieder eine schöne Beschäftigung.

Hoffentlich ist mein Post jetzt nicht zu wirr ausgefallen.

Viele Grüße
Traude

Du hast auf alle Fälle, denen Zeit gespart die zweifel an der Methode haben. Du bist bei "Ich finde was einfacherers" losgegangen und bist über "Wie sind die Sachen dort gemacht worden" zu "eigentlich ist die Methode ganz ok" gelangt.
Das würde ich einen erfolgreichen Lernprozess nennen.

Nebenbei ist, denke ich, noch keines unserer Tutorials so im Detail diskutiert worden wie dieses. Was ich persönlich gut finde.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

So ich habe mal etwas in meiner Trickkiste herum gewühlt und meine TexturFont-Unit raußgekramt. Ist etwas unaufgeräumt, läuft aber recht gut. Beim benutzen muss man aber drauf achten, dass das Koordinatenkreuz oben links liegt und in Pixelgenauigkeit nach rechts und unten läuft. Die Textur hab ich mit eingefügt. Es ist eine .tga, ich hoffe das stört niemanden(konvertieren sollte zur Not nicht so schwer sein).
Möchte man die TGlStrings nutzen muss man nach dem Initialisieren der OpenGl die GlStringInit(); ausführen um die Textur zu laden und das Array für die Buchstaben abstände zu setzen. Anschließend kann man beliebig TGLStrings erstellen. Die Fonts benutzen immer AlphaBlending. Man kann die Farbe pro String einstellen (kein Regenbogentext Möglich). Tabspaces und Zeilenumbrüche können genutzt werden. Die Eigenschafft "TrueSpacing" sagt nur aus, ob die Buchstaben je nach Breite zusammengeschoben werden, oder ob sie in einem fixen Raster liegen sollen (so wie im Text-/Codeeditor). Das einstellen einer Textgröße ist auch nicht möglich (Es sei denn man benutzt glScalef();, aber das sieht scheiße aus, wenn die Textur verzogen wird). Italic/bold text ist auch nicht implementiert.

Ich hoffe mal, das es dabei jetzt keinen Ärger gibt. Bei mir lief es immer Einwandfrei. Sollte was daran nicht funktionieren schreibt mich direkt an.

Edit: Ach ja.. die TextureFont.tga muss im selben Verzeichnis liegen wie die Anwendung, oder man passt den Pfad in der Unit einfach an.

_________________
Klar Soweit?

Vielen Dank, Sellmann. Ich habe auch eine solche Textur bei mir gefunden, auf einer Sicherungs-CD. Aber den Programmcode dazu hatte ich nicht mehr.

@Flash: Ich finde der Threadstarter hatte ganz recht. Das ganze durchzukauen kann eigentlich nur im Interesse erins und auch in unserem Interesse sein. Sollte wirklich jemand einen Vorschlag haben, der das Ganze verbessert, würde uns allen das ja auch zugute kommen. Ist auch eine Variante von OpenSource: einen Sourcecode öffentlich evaluieren.

Ach ja, das Fontproblem, eher lästig als kompliziert. Da hat man eine Programmidee, setzt sie mit Delphi schnell um und stellt dann fest: Verflixt, ich brauche ja noch irgendeine Anzeige. Die Lust, sich in solchen Situationen mit Schriften zu bechäftigen, ist eher gering, bei mir jedenfalls.
Gibt es eigentlich keine Delphi-Unit dafür, die sich schnell und unkompliziert installieren und einbinden lässt?

Das nur am Rande. Es ist gut, dass ein Algorithmus auch mal mit einem Benchmark-Test durch die Mangel gedreht wird, denn je weniger Rechenzeit für die Kollision gebraucht wird, desto mehr Reserve hat man für andere Dinge (Erhöhung der Sichtweite, Partikelsysteme usw.) Allerdings ist die Kantenkollision eher bescheiden im Vergleich zur allgegenwärtigen Kollision an Polygonflächen. Ich hab den Rechner mal die Kollisionsarten auszählen lassen, und zwar in verschiedenen Szenerien des Programms Tuxracer. Am häufigsten geht es dabei um die Kollision mit dem Gelände, einem normal triangulierten Mesh. Zwei typische Ergebnisse (die anderen liegen dazwischen):

a) Polygonfläche: 1016 - Kante: 46 - Ecke: 0 (eher sanftes Gelände)
b) Polygonfläche: 3950 - Kante 353 - Ecke: 1 (bizarr, mit Schluchten und steilen Felswänden)

Die Kantenkollision ist mit rund 5 bis 9 % vergleichsweise selten, und da die Flächenkollision vorher abgefangen wird, muss die Kantenkollision auch nur in den übrig bleibenden Fällen berechnet werden. Dabei ist jedoch zu bedenken, dass die Kantenkollision gleich 3 mal oder mehr bei jedem Polygon zu Buche schlägt. Auf jeden Fall ist sie extrem wichtig, denn sie sorgt dafür, dass das Objekt zuverlässig auf der Oberfläche gehalten wird, auch in Grenzsituationen. Also vor allem Genauigkeit. Wenn die Kantenkollision nicht sauber arbeitet, taucht das Objekt irgendwann auf Nimmerwiedersehen in die Unterwelt ab, wo es mit Backface-Culling ziemlich öde aussieht. Schon Rundungsfehler in der Gegend von 0 müssen bedacht werden.

@Traude:

Ich finde es toll, dass du die Algorithmen mal etwas vertiefen willst. Wenn du das in irgendeiner Form beschreiben möchtest, dann würde ich dir empfehlen, von der Eckenkollision auszugehen. Die lässt sich nämlich noch einigermaßen nachvollziehbar herleiten, und das grundsätzliche Vorgehen ist bei der Kantenkollision ähnlich, wenn ich mich recht erinnere. Allerdings deutlich komplizierter.

Wenn es um Performance geht, scheint mir vor allem der Test, ob bei der Flächenkollision die Berührung innerhalb eines Polygons stattfindet, wichtig zu sein. Ich weiß nicht, ob der von mir vorgeschlagene Weg, bei dem auf den Polygonseiten senkrechte Hilfsebenen errichtet werden, der effektivste ist. Hierzu gibt es aber schon regelrechte Untersuchungen (ich hab' die Links im Augenblick nicht parat).

@Erin: Versteh ich das richtig? Hab ich den Kram jetzt umsonst hochgeladen, oder hast du nur überlesen, dass ich eine einfach zu installierende und zu handhabende Delphi Unit für Schriftdarstellung hochgeladen habe? Oder suchst was professionelleres? Dann kannst du doch die Textsuit nehmen. Die hab ich zwar noch nie benutzt, aber nach den Kommentaren im Forum, soll sie echt Klasse sein.

@Traude: Ich weiß nicht ob der Code auch bei anderen ohne weiteres funktioniert. Schaut man sich die Draw(); procedure an, dann springt einem direkt der ImmediatMode ins Gesicht, was nicht die schnellste Methode ist um Text zu zeichnen, allerdings hab ich durch Texte auf diese Weiße trotzdem nie Geschwindigkeitseinbuße gehabe. Deshalb würde ich gerne ein Feedback von dir bekommen, sobald du es ausprobiert hast, ob und wie sich die Unit bei dir bewährt hat.
Ich spiele mit dem Gedanken in nächster Zeit den Text beim Setzen der Caption in ein VBO zu schreiben um etwas performanter zu werden. Auch habe ich mit dem Gedanken gespielt "statischeStrings" erstellen zu können, die sich nach dem Erstellen nicht mehr ändern und deshalb über ein FBO direkt in eine Textur gerendert werden könnten, die auf ein zugeschnittenes Quad gezeichnet wird. so genug Off-Topic. Ich bin tierisch gespannt auf dein Programm und schau täglich mehrmals ob es was neues dazu zulesen gibt.

_________________
Klar Soweit?

Naja, so großartig ist es ja auch wieder nicht. Deine Schrift hab ich noch nicht eingehängt, hauptsächlich deswegen, weil ich auch die glBitmap nicht drinnen haben will. Die FPS schreibe ich im Augenblick noch als Caption ins Fenster. Weil das Fenster bei mir aber gar keinen Titelbalken hat, sieht man die FPS nur auf dem kleinen Button unten auf der Programmleiste.

Um die Schrift einzubauen, muss ich es ein wenig umschreiben. TGA kann ich selber laden. Und keine Sorge, sollten irgendwelche Probleme auftauchen, krieg ich das schon in Griff. Sollte der Immediate Mode zu langsam sein, kann man es ja mit glCallLists realisieren. Das ist mir wirklich kein Problem.

Um Deine Neugier zu befriedigen:

Das Programm besteht aus mehreren Teilen:
------------------------------------------------------------

1) Das Hauptprogramm "KollisionsTest.Dpr": Initialisierung/Finalisierung von nötigen Dingen (z.B. Fenster, Grafik-Library, ShapeManager), Programmhauptschleife und Kontrolle des ShapeManagers.

2) Die Unit Shape3D, die den ShapeManager beinhaltet, der eine Mini-Sammlung von 3D-Formen erzeugen kann. Diesen Formen kann man durch simple Zuweisung einer Matrix eine einfache Animation verpassen. Derzeit funktioniert die Animation so, dass eine Kugel durch ein Dreieck läuft, womit ich die Kollision simulieren kann

3) Die Unit GraphicSupport, die alles macht, was mit OpenGL zusammenhängt, auch das Zeichnen. Ich zeichne übrigens mit glDrawElements, aber ohne VBO, also eigentlich im Immediate Mode und schalte nur die Beleuchtung ein.

4) Die Unit OSSupport, die ein Teil der glPasGUI ist und alles betriebssystemabhängige Zeug übernimmt, also auch den Timer, um den es ja hauptsächlich geht.

5) Eine kleine Unit Math3D, weil ich kein glTranslate/Rotate verwende, sondern alles selber mache (bis auf die Projektion, die soll aber auch in der Endfassung mit einer selbstgebastelten Matrix aus dem Wiki laufen)

Dann gibts noch ein paar Dinge, die von mir sind und die ich noch rausschmeißen muss, eine Unit StdBasicDefs, auch aus der glPasGUI, weil ich meine eigenen Datentypen habe, die hier aber nicht wirklich nötig sind. Für Linux ist noch die glxTest dabei, weil die glx-Unit aus meiner FreePascal-Version 2.2 schon steinalt ist.

Und, na klar, die dglOpenGl.pas braucht man auch.

Und weil das ja langweilig ist bloß drüber zu sprechen, hänge ich Dir den Sourcecode hier rein. Ich habe noch keine Beschreibung dabei. In Delphi: einfach kompilieren und es sollte laufen. In Lazarus: kompilieren im Delphi-Modus. Läuft auf Linux und Windows. Zu sehen ist eine immer wiederkehrende Animation: eine Kugel, die durch ein Dreieck rauscht und bei der Kollision rot wird. Die Implementierung der Kollision ist stecken geblieben, kann man ganz leicht sehen in der Unit "Shape3D.pas", Funktion "TShape3D.Hit", welche die Funktion "TShape3D.HitEdge" aufruft. Da hinein gehört der Code für die Kantenkollision.

PROGRAMM BEENDEN = Escape drücken. Achtung: die dglOpenGL.pas ist nicht mit dabei.

Angezeigt werden 25 FPS (unten, in der Programmleiste). In der Hauptprogrammschleife ist ein Sleep eingebaut (File "KollisionsTest.Dpr", Zeile 127); wenn Du das auskommentierst, läufts nachher ein wenig schneller



Es gibt meines Wissens einen Delphi-Code zur Nehe-Lesson 17, und ich glaube, mich erinnern zu können, dass es irgendwann mal etwas auf Sulaco gab, aber ich habe es nicht mehr gefunden. Genau das möcht ich ja jetzt machen. Vorher würde ich aber noch gern die Kollision hinkriegen.



Hier hätte ich eine mögliche Alternative für den Benchmarking Test anzubieten. Ich habe einen Modeller geschrieben, bei dem ich diese Kollision folgendermaßen gelöst habe: Polygon mittels Matrix nach 2D transformieren und dort um das Polygon hüpfen und schauen, ob der Punkt immer links von mir ist. Das Prinzip ist aber das Gleiche wie bei Dir. Im Gegensatz zur Kantenkollision gibt es diesen Code schon. Ist aber nicht auf Schnelligkeit optimiert, weil die Anwendung damals für meine Zwecke schnell genug war: es ging um das Selektieren von Polygonen mit der Maus.

Viele Grüße
Traude



EDIT: Ich habe das Attachment gelöscht und in meinem nächsten Beitrag wieder hineingestellt, weil die Kantenkollision dazugekommen ist.

Entschuldige, ich hab's überlesen oder - genauer gesagt - eher als spezielle "Spontanhilfe" für Traude aufgefasst. Wenn es schon eine grundsätzliche Lösung gibt, ist es ja gut.

OK, die Implementierung der Kantenkollision scheint jetzt zu funktionieren. Ich stelle das ganze Projekt nochmal hier hinein und dafür habe ich es im vorigen Beitrag gelöscht.

Man sieht also eine Animation, wo eine Kugel gegen eine Dreieckskante läuft, und die Kugel "bemerkt" die Dreieckskante, indem sie rot gefärbt wird (blitzt aber nur ganz kurz auf).

Die Implementierung der Kantenkollision - falls es jemanden interessiert - findet man in der Unit "Shape3D.pas", Methode "TShape3D.HitEdge".

Übrigens: Wenn man den Vektor BtV ("BaseToVertex", das ist der Vektor vom Kugelmittelpunkt zu einem Polygonkantenpunkt) umdreht, also "VertexToBase", erfollgt die Kollision erst, wenn die Kugel die Kante hinter sich gelassen hat, also ins Dreieck eingedrungen ist.

Wenn ich die Schrift fertig eingebaut habe, melde ich mich wieder, aber ich mache dafür einen eigenen Thread im OffTopic auf, denn das hat ja mit Mathe oder Kollision jetzt nichts mehr zu tun.


ACHTUNG: Escape = Programmende.