Faces in einem eigenen 3D-Renderre korrekt zeichnen

[CPU]

Hallo,

aus Interesse und Zeitvertreib habe ich mir einen kleinen "3D-Renderer" gebaut. Man kann damit Punkte in einem Raum zeichnen lassen und das Modell mit der Maus rotieren. Sehr schön. Allerdings habe ich mit den Flächen (Faces) ein Problem. Ich schildere mal mein Vorgehen:

Für Vielecke mit drei Ecken ist das alles kein Problem, man verbindet die Punkte einfach und füllt den Zwischenraum:

    // q enthalte die Punkte
    a.beginPath();
    a.moveTo(q[0].x, q[0].y);
    a.lineTo(q[1].x, q[1].y);
    a.lineTo(q[2].x, q[2].y);
    /* a.lineTo(q[3].x, q[3].y); */
    a.closePath();
    a.fill();

Wenn man jedoch vier Punkte (oder mehr) hat und die Reihenfolge nicht bekannt ist und man einfach blauäugig die Punkte verbindet (man kommentiere dazu oben noch die Zeile "a.lineTo(q[3].x, q[3].y);" aus), dann kann z.B. so etwas heraus kommen:



Also musste ich mir etwas einfallen lassen, wie ich die Punkte erst ordne und dann nacheinander zeichne. Alles weitere habe ich dann im 2D-Raum überlegt und gelöst, da ja die 3D-Punkte in dieser Phase, in der das Problem auftritt, bereits auf 2D-Punkte abgebildet sind.

Ich habe mir überlegt den Mittelpunkt der vier Punkte zu berechnen (X- und Y-Koordinaten aufsummieren und durch Anzahl Punkte teilen) und dann diesen zu klonen und die Y-Koordinate null zu setzen (so dass dieser Punkt dann auf der gleichen X-Korrdinate sitzt und eine vertikale Linie bildet). Und dann berechne ich einfach nur den Winkel zwischen diesem "Vektor" (Mittelpunkt -> veränderter Mittelpunkt) und dem Vektor auf den aktuell betrachteten Punkt (Mittelpunkt -> betrachteter Punkt). Somit bekomme ich für jeden Punkt einen Winkel. Und wenn ich die jetzt aufsteigend sortiere "gehe" ich einmal im Urzeigersinn die Punkte ab und habe meine Sortierung:



Schön. Ich dachte ich wäre fertig, aber dann kam folgendes: ich habe mal ein komplexeres 3D-Modell aus Blender reingeladen und das hat erstaunlicherweise auf Anhieb funktionert (also musste da etwas nicht stimmen :-)).

Sehet selber das Problem in den unteren zwei Bildern:



Man kann deutlich erkennen, dass dort mit (wirklich) leicht verändertem Blickwinkel sich die Reihenfolge der Punkte ändert und somit die Form der Fläche sich verändert und das Bild dann "flackert", wenn man es denn bewegt.

So und hier bin ich nun und frage mich, was ich tun kann und ob man überhaupt etwas machen kann? Habt Ihr irgendwelche Einfälle?

Viele Grüße,
CPU

P.S.: Bitte nicht verwirren lassen - das 3D-Modell ist noch etwas bunt ;-)

 

[Tigerass 2.0]

Normalerweise bestehen 3d objekte doch auch nur aus dreiecken dachte ich? Und ich erinnere mich dunkel daran, dass es noch etwas mit normalenvektoren und so gab. Aber so viel zeit wie du möchte ich auch gerne haben . Mit was programmierst du?

 

[CPU]

Normalerweise bestehen 3d objekte doch auch nur aus dreiecken dachte ich? Und ich erinnere mich dunkel daran, dass es noch etwas mit normalenvektoren und so gab.

Das ist die mathematische Seite. Auf der "technischen" ist der ganze Kram z.B. in OBJ-Dateien (sind am einfachsten). Hier mal ein Ausschnitt:

...
f 350 352 380 386
f 381 353 351 387
f 324 380 352
f 353 381 325
f 400 388 414 402
f 415 389 401 403
...

Man sieht, dass es neben Dreiecken auch Vierecke gibt.

Aber so viel zeit wie du möchte ich auch gerne haben . Mit was programmierst du?

Im moment besteht mein Projekt aus ~400 Zeilen Javascript mit HTML5-Canvas.

Hat denn keiner eine Idee, was ich machen könnte?

Viele Grüße,
CPU

 

[Nai]

Wenn ich mich recht erinnere dann sind bei OBJ die Vertexe in einer bestimmten Reihenfolge und es gibt nur konvexe Flächen, dadurch kann man das ganze relativ leicht triangulieren. Dh wenn man folgende Vertexe einer Oberfläche hat:
V1 V2 V3 V4 V5
und das Triangulieren will nimmt man folgende Reihenfolge
T1: V1 V2 V3
T2: V1 V3 V4
T3: V1 V4 V5

 

[Tigerass 2.0]

Stimmt! Das kommt mir sehr bekannt vor. Normalenvektoren können dir dann auch erstmal egal sein, dann siehst du dein tris halt von beiden seiten. Hast du schon daran gedacht wie es mit überlappungen aussieht? Also wenn ein tris von einem anderen bedeckt/abgeschnitten wird? Besonders wenn du Normalenvektoren nicht berücksichtigst, könnte das zum Doppeltem Problem werden.

 

[CPU]

Hallo,

Wenn ich mich recht erinnere dann sind bei OBJ die Vertexe in einer bestimmten Reihenfolge und es gibt nur konvexe Flächen, dadurch kann man das ganze relativ leicht triangulieren. Dh wenn man folgende Vertexe einer Oberfläche hat:
V1 V2 V3 V4 V5
und das Triangulieren will nimmt man folgende Reihenfolge
T1: V1 V2 V3
T2: V1 V3 V4
T3: V1 V4 V5

Aber ich habe doch in aller Regel nur 4 Punkte gegeben (V1-V4). Lasse ich dann einfach T3 weg?

Okay, ich habe das mal eingebaut und herausgefunden, dass etwas mit dem "Z-Index" nicht stimmt (andere Elemente werden vorne gezeichnet, obwohl sie hinten liegen). Ich werde mich da nochmal hinter klemmen. Aber zunächst Danke, das hat mir geholfen.

Da dieses Projekt eher ein "Zeitvertreib" ist, als etwas produktives noch eine Frage - wo wir gerade bei 3D sind: gibt es für Java (nicht JavaScript!) eine einfache 3D-Bibliothek? Ich kenne natürlich JMonkey und Jogl, aber ich brauche etwas sehr flexibles (simpel portierbar von Platform zu Platform), ohne immer wieder neue native Bibiliotheken einzubinden? Eine pure Java-Bibliothek etwa? Gibt es so etwas?

Viele Grüße,
CPU

 

[Nai]

Aber ich habe doch in aller Regel nur 4 Punkte gegeben (V1-V4). Lasse ich dann einfach T3 weg?

Ja, in dem Fall weglassen.

Allerdings kann bei dem Obj File Format eine Surface aus beliebig vielen Vertices bestehen. Demnach sollte dein Obj-Loader dies auch beim Ladevorgang beachten, wenn du alle Obj Dateien fehlerfrei darstellen willst. Hier würde es sich anbieten, dass dein Loader dynamisch schaut wieviele Vertices die Surface hat und dann dementsprechend den Algorithmus, den ich dir an dem einfachen Beispiel vorgestellt habe, anwendet um die Surface zu triangulieren.

 

[Hancock]

Also irgendwie ist da die .obj Spezifikation nicht ganz eindeutig, eine Liste von Vertices wird "irgendwie" "counter-clockwise" gezeichnet. Das ist solange eindeutig, solange sich alle Punkte in einer Ebene befinden und alle tatsächlich linksrum angeordnet sind.
Persönlich würde ich einfach den Triangle-Fan-Algorithmus http://msdn.microsoft.com/en-us/library/windows/desktop/bb206271(v=vs.85).aspx verwenden, das sollte "korrekte" Ergebnisse liefern.