Punkte und Dreiecke

[Firoball]

Servus,
Ich habe als bekennender Ahnungsloser zum Thema 3d Mesh Erzeugung ein kleines Problem.
Folgende Dinge sind bekannt:
- eine beliebige Menge an Punkten
- jeder Punkt hat einen eindeutigen Index, durch den sich eine Reihenfolge der Punkte ermitteln lässt.

Nun möchte ich aufgrund dieser Information ein Polygon aus vielen Dreiecken erzeugen. Die Normalen sollten dabei nach "oben" zeigen, es müssen also alle Dreicke in gleicher Richtung "gezeichnet" werden. Mein Problem ist aber, wie mache ich das am besten?
Herauskommen soll später mal ein d3dxmesh. Falls es also entsprechende d3d Funktionen gibt, die das erledigen, wäre ich für ein Stichwort / einen Suchbegriff dankbar.
Ansonsten bräuchte ich einen Ansatz für den Algorithmus. Auch hier würde mir dann ein Stichpunkt zum Suchen reichen. Ich nehm aber auch gern ne ausführliche Erklärung :) Das Problem ist doch sicher altbekannt...

Nochmal zur Veranschaulichung was ich vorhab:


Danke für eure Hilfe.

[dowhilefor]

Google mal nach Triangulation, Delauney oder Ear cutting. Interessant könnte auch noch QuickHull sein.

[Firoball]

Danke erstmal...
Ich denke interessant ist auch der Graham Scan, aufwelchen ich während der Recherche gestoßen bin. Damit müsste ich mitn bissl kranken Algorithmen und etwas Vorsicht das Polygon gefüllt bekommen. Ekelhaft wird es dann bei Donut-Polygonen, also sprich Polygone mit Löchern. Und diese können leider vorkommen. Da versagt meine Idee,
Isolierte Punkte sind mir egal, die kann ich einfach mal ignorieren.

[Aramis]

Ich kann Ear Cutting nur empfehlen. Ziemlich einfach zu implementieren und dabei ziemlich flott.

[Firoball]

Ja, Ear Cutting hatte ich mir auch schon angeschaut und das ist definitiv interessant. Gibt es ja aauch recht viel Source Code, den man gut weiterverwenden kann.

Ich seh schon, das Hauptproblem bleiben Löcher. Meine Idee wäre, dass ich einfach einen "unsichtbaren" Schnitt in das Polygon mache, so dass ich keine isolierten Punkte mehr habe. Damit meine ich in etwa sowas wie einen einfachen Schnitt mit der Schere ins Papier. Wenn man das Papier auf den Tisch legt, sieht man den Schnitt (fast) nicht mehr. Ich muss mir halt die Schnittstelle merken und darf später bei der Kollision an dieser Stelle nicht reagieren. Aber das sollte machbar sein.

Das Problem ist: Wo setze ich am sinnvollsten einen Schnitt? Gerade wenn ein Polygon mehrere Löcher hat, kann das etwas tricky werden...

[Chromanoid]

Vielleicht kannst du dir ja mal anschauen was so die General Polygon Clipper library kann.
Ansonsten würde ich für die Kollisionserkennung und Co. vorschlagen alle Polygone in eine Menge von konvexen Polygonen zu unterteilen.

[Firoball]

Die Kollisionserkennung muss ich zum Glück nicht selber schreiben. Ich muss "nur" das Mesh bzw. die Meshes mit Texturen ins D3D Format bekommen. den Rest macht dann die Engine.

Mein Problem ist, dass das Datenformat, in dem die Levelinformationen vorliegen, nicht gerade für eine polygonbasierte 3D Engine gedacht ist... Das wird im weiteren Verlauf noch zu zahllosen Problemen führen, aber ein erster großer Schritt wäre es erstmal, wenn ich meine Daten in viele Faces segmentiert bekomm und die Engine das alles irgendwie darstellt.

[Firoball]

ftp://ftp.cs.unc.edu/pub/users/manocha/ ... ion/README

The algorithm handles simple polygons with holes. The input is
specified as contours. The outermost contour is anti-clockwise, while
all the inner contours must be clockwise. No point should be repeated
in the input. A sample input file 'data_1' is provided.

Das könnte der 6er im Lotto sein. Entspricht genau dem, was ich als Inputdaten habe. Bin schon gespannt was nach dem Anpassen des Codes rauskommt.

ftp://ftp.cs.unc.edu/pub/users/manocha/ ... ngulation/

[Firoball]

Ich wusste nicht, dassman sich so über ein paar bunte Linien freuen kann!
Nach all der Tortur mit Problemen beim Wechseln auf einen Nicht-Standard Compiler und Durchwühlen von unverständlichen 600 Zeilen - Spaghetticode - Funktionen ist das einfach nur... geil...

[Schrompf]

Joa, für Nicht-Programmierer mag das seltsam anmuten, aber ich kann Deine Freude gut nachvollziehen :-)

[Firoball]

Bei komplexeren Gebilden gab es irgendwie unerklärliche Fehlbildungen und teilweise auch Deadlocks.
Da ich die Ursache nicht finden konnte, habe ich nun auf eine Lite-C Version verzichtet udn das ganze per DLL eingebunden.

Eine ziemlich komplizierte Region (aus 3D Sicht eifnach ein Polygon), konvertiert aus Scripten und Leveldateien sieht dann so aus:



Sehr häßliche Dreiecke. Ich hoffe Direct3D macht da dann später nicht die Grätsche. Für meine Zwecke ist es aber egal, wenn das so übel aussieht - die Fläche ist meist eben, manchmal konstant gekippt (also auch eben).

[Firoball]

D3D scheint damit kein Problem zu haben, zumindest solange ich keine Ausleuchtung oder ähnliches vornehm...


Das Skaphander Demo - ohne Wände, und die Texturen sind noch nicht passend skaliert....

[rüp]

Hach, da werden Erinnerungen wach. ;)

[Firoball]

Ich hoffe es ist ok, wenn ich hier regelmäßig die Fortschritte poste.

Bedingt durch den Triangulisieralgorithmus dürfen sich Polygone nicht selbst berühren (entweder einen Punkt mehrfach benutzten, oder zwei positionsgleiche Punkte besitzen).
Das erkenne ich jetzt während dem Erzeugen des Meshes und kürze einfach den Vektor der anliegenden Wand minimal, um den Punkt zu verschieben. Dadurch ist gewährleistet, dass ich den Punkt nie in ein anderes Polygon hineinschiebe.

Die Positionsänderung des Punktes ist dabei so gering, dass man es im Level selbst nicht sieht, der Mesh-Algorithmus aber nicht mehr knallt.

Was noch fehlt ist eine Erkennung von überlagerten Wänden einer Region (das ist oft der Fall bei Schiebetüren). Hier muss auch die gesamte Wand leicht verschoben werden.

Die meisten mir vorliegenden Levels krieg ich mittlerweile auch dargestellt (noch ohne Wände, dafür aber mit korrekt skalierten Texturen), lediglich das Abiventure von kts weigert sich standhaft...

[dowhilefor]

Was noch fehlt ist eine Erkennung von überlagerten Wänden einer Region (das ist oft der Fall bei Schiebetüren). Hier muss auch die gesamte Wand leicht verschoben werden.

Bin mir nicht sicher ob ich das richtig verstehe. Aber eigentlich sind solche Türen nicht teil der Level geometry. Besser wäre es wenn die Türen eigene Entities sind die ein Portal zugeordnet haben dem sie sagen können "an" oder "aus". Auf die weise brauchst du dich nur mit statischer Level geometry beschäftigen und kannst nachträglich eine Tür als Entity einbinden die animiert sein kann und trotzdem, dank dem portal, die sicht behindert wenn sie geschlossen ist.

[Firoball]

Fürs erste wird die gesamte Geometrie ersmtal nur statisch importiert.
Die Ausgangsdaten zeigen mir leider nicht direkt an, dass ein "Objekt" (in diesem Fall sprechen wir eigentlich von einem dynamischen Levelteil, und nicht von einem Objekt - nach der Konvertierung wäre es dann irgendwann mal ein Objekt) dynamisch ist.
Dies kann ich nur durch komplexeres Parsen der Aktionskripte herausfinden. Und dann muss ich je nachdem was mit der entsprechenden Sektion/Wand/Textur gemacht wird, unterschiedlich verfahren. Für den ersten Schuss ist das aber viel zu kompliziert, deswegen soll erstmal alles statisch reingeladen werden können.

Ansonsten hast du das aber schon richtig verstanden.

[Firoball]

Ein paar Bilder.
Ich hab noch ein Problembei der Offsetberechnung der Wandtexturen, und Below Regionen werden vom Wandgenerator noch nicht unterstützt.


An den Säulen sieht man noch Skalierungsfehler (mittlerweile behoben).


Der Himmel wird derzeit nicht getrennt behandelt und sieht deswegen entsprechend komisch aus.


Der Waldlevel aus dem Contestspiel von 1998.

Vergleichsbider - aus etwas anderen Blickwinkeln

[Firoball]

Es gibt kleine Fortschritte.
Ich wurde tatsächlich von einem Engine Bug ausgebremst. Mit der neuen Beta, kontne ich rudimentäre Objekte implementieren. Neue Screens habe ich in den Vorstellungsbereich gepostet, da mein Dreiecksproblem ja mittlerweile gelöst ist.

http://developia.zfx.info/viewtopic.php ... 056#p14056