Hallo zusammen,

ich hab ein ungewöhnliches Problem und komme einfach nicht weiter.

Ich will die sichtbaren Punkte von einem Würfel "auswerten". Dazu ist es u.a. wichtig, dass ich ein Hintergrundbild "zeichene" und danach den Würfel als "Wireframe" drüberlege. Wobei nicht sichtbare Kanten nicht gezeichnet werden.

Den Hintergrund zeichne ich mit DrawPixel() direkt.

Danach schalte ich die ColorMask auf False und zeichne den Würfel als Quads. Dann schalte ich die ColorMask wieder an und zeichne ihn als "Lines". Somit "sehe" ich nur die sichtbaren Kanten und dazwischen seh ich den Hintergrund - so wie's sein sollte! Das funktioniert alles wunderbar.

Jetzt muss ich aber irgendwie rauskriegen welche Eckpunkte bzw. Kanten denn wirklich "sichtbar" sind.

Hab schon verschiedene Ansätze probiert: Z-Buffer auslesen hilft mir nicht weiter weil der Würfel als Wireframe ja eigentlich immer sichtbar is. Feedback Buffer klappt irgendwie auch nicht.

Hat irgend jemand eine Idee wie ich die sichtbaren Punkte eines Würfels berechnen kann?

Schon mal vielen Dank und heiter weiter,
Lenco

Am besten mit dem Stencilpuffer machen. Also soliden Würfel in den Stencilpuffer, dann den Würfel als Wireframe mit aktivem Stenciltest (nur dort wo nichts im Puffer ist) leicht skaliert rendern. So siehst du dann nur die sichtbaren Kanten.

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Hmmm ... das mit dem Stencil Buffer ist eine gute Idee.

Aber wie kann ich denn die sichtbaren Eckpunkte "berechnen" bzw. wo kann ich auslesen ob ein Eckpunkt sichtbar ist oder nicht.

Ich muss diese Daten hinterher noch weiterverarbeiten und habe einen Algorithmus der als Eingabe die "sichtbaren Vertices" erwartet ...

Gruß,
Lenco

Genauso wie das Backface Culling berechnet wird, nur dass man anstatt der Face-Normalen die Punkt-Normale nimmt. Das Backface Culling besteht in einem Skalarprodukt der jeweiligen Face-Normale mit dem Vektor Kamera=>Face (oder in Deinem Fall: Kamera=>Punkt). Wenn der Winkel zwischen diesen beiden Vektoren kleiner als 90 Grad ist, ist der Punkt ein "BackPunkt".

Nicht vergessen: für das Skalarprodukt muss man die beiden Vektoren normalisieren.

http://wiki.delphigl.com/index.php/Standard_Skalarprodukt

Normalisieren ist doch nicht nötig, wenn der Winkel kleiner 90° ist, ist das Skalarprodukt der Vektoren größer Null. Wenn man also nur wissen will ob ein Punkt vor oder hinter einer Ebene liegt brauch man nur auf größer oder kleiner Null testen.

Hallo zusammen,

erstmal vielen Dank für die bisherigen Antworten. Das hat mir schon ziemlich weitergeholfen. Leider kam ich erst jetzt dazu das wirklich umzusetzen. Hab mein Problem aber leider noch nicht lösen können.

Um das Kernproblem nochmal zusammenfassen:
Ich zeichne einen Würfel mit GL.Lines als Wireframe. Der Würfel ist zu jedem Zeitpunkt vollständig dargestellt.
Würde ich den Würfel als "solide" Zeichnen, würden ja einige "Eckpunkte" des Würfels (je nach Würfelausrichtung) durch die "geschlossenen Würfelseiten" verdeckt. Obwohl bei meinem Wireframe-Würfel immer alle Eckpunkte sichtbar sind, versuche ich nun zu berechnen welche Eckpunkte eigentlich nicht sichtbar sein dürften.

Ausgehend von euren Antworten bin ich nun so vorgegangen:

Um zu bestimmen ob z.B. der Würfeleckpunkt a sichtbar ist:

M = ModelviewMatrix

c = (0,0,0,1) * M^-1 (= ModelviewMatrix invertieren)

Damit sollte in c doch dann die Position der Kamera stehen?!
Mit v = c - a berechne ich die Blickrichtung von der Kamera auf Eckpunkt a.

Um die Punktnormale für a zu bestimmen, berechne ich die Normalen (n1, n2, n3) für die drei Flächen die sich in Eckpunkt a treffen. n1+n2+n3 = n_a sollte dann den Normalenvektor für a ergeben.

Dann berechne ich das Skalarprodukt für n_a (wird vorher normiert) mit v (wird vorher normiert). Da die beiden Vektoren ja normiert sind reicht doch eigentlich:

(n_a.X * v.X) + (n_a.Y * v.Y) + (n_a.Z * v.Z) = cos alpha

Fallunterscheidung: cos alpha >= 0: a sichtbar, sonst a nicht-sichtbar!

Leider scheint das so nicht zu funktionieren. Hab ich da irgendwo einen Denkfehler oder bin ich komplett auf dem Holzweg.

Bin mittlerweile ziemlich verzweifelt und für jeden Tipp dankbar.

Viele Grüße,
Lenco

Einen Denkfehler, ja.

Der Punkt ist sichtbar, wenn min. eine der Flächen, die den Punkt enthält, sichtbar ist. Das heißt du muss jede deiner Normalen (n1,n2,n3) einzeln mit v vergleichen. Und wenn das Ergebnis irgendwo >=0 ist, ist der Punkt sichtbar.

@Lenco: Der Ansatz ist nicht ganz richtig. Du machst Folgendes:

Ich glaube, das steht in unserem Wiki so. Leider ist das nicht ganz richtig. Man vergleicht beim Backface Culling die „Blickrichtungen“ der Kamera und der jeweiligen Fläche. Es müsste Dir zum Beispiel auffallen, dass Du nur eine Blickrichtung hast. Denn das hier:

ist keine Blickrichtung, sondern nur ein Vektor zwischen dem transformierten Kamerapunkt und dem Würfelpunkt. Richtigerweise solltest Du nicht den Punkt (0,0,0) transformieren (den Koordinatenursprung kann man gar nicht rotieren, denn er liegt AUF der Rotationsachse, ganz gleich, welche Rotationsachse Du nimmst), sondern den Blickrichtungsvektor der Kamera, das ist der Vektor (0,0,-1). Denn wenn die Modelviewmatrix z.B. nur eine Rotationsmatrix ist und keine Translation stattgefunden hat, ist der transformierte neue Punkt ebenfalls (0,0,0) und Deine Berechnung ergäbe das gleich Ergebnis wie ohne Transformation und das ist ganz offensichtlich falsch.

Aber wenn man zum Beispiel neben einer Wand steht, dessen Normale jetzt zum Beispiel (1,0,0) ist und man schaut in Richtung (0,0,-1), dann wäre das Skalarprodukt logischerweise 0. Dadurch würde die Wand gecullt werden (wenn nur bei <0 gecullt wird, schaut man eben ganz wenig weg), doch eigentlich kann man sie sehen. Kann man auch ganz leicht im echten Leben testen

Die meisten geometrischen Algorithmen haben irgendwelche Spezialfälle, die man extra behandeln muss. Das Einschalten der kleinen grauen Zellen bleibt einem nicht erspart. Trotzdem muss man immer gewahr sein, dass einer kommt und es besser weiß und sagt "Das ist noch nicht nötig"

Das hat nichts mit Spezialfall zu tun. Ich weiß zwar nicht wie es bei OpenGL tatsächlich gemacht wird, aber ich bin der Meinung beim Backface Culling ist entscheidend welche Seite zum Betrachter hin zeigt. Der Betrachter ist an der Kameraposition, also kommt es darauf an ob der Punkt vor oder hinter der Ebene ist. Ob das Polygon überhaupt im Blickfeld ist, ist eine andere Sache.
Wenn man einen Würfel betrachtet und man sich genau über der Mitte eine Fläche befindet, kann man die Seiten ja auch nicht sehen, weil nach hinten hin der Winkel zwischen den Punkten geringer wird, auch wenn die Kantenlänge gleich ist. Weiter entfernte Dinge erscheinen dadurch kleiner. Wenn man nur die Kanten zeichnet, sieht man eigentlich ganz gut, dass man die Flächen an den Seiten von hinten sehen würde.
Genauso würde ein Polygon was sich hinter einem befindet und zum Betrachter hin zeigt, geculltwerden. Wenn man aber eine Rundumsicht hätte, also in alle Richtungen gleichzeitig blicken könnte, wäre das falsch. Natürlich geht das bei OpenGL nicht, aber je größer der Blickfeldwinkel ist, desto häufiger werden die Fehler.
Mein Beispiel sollte also nicht irgendeine Ausnahme darstellen, sondern aufzeigen das die Methode fehlerhaft ist. Wirklich exakt wäre die Lösung mit der Blickrichtung nur wenn der Punkt der Fläche die getestet wird, genau in der Blickfeldmitte ist, also der Vektor von der Kamera zum Punkt in die selbe Richtung wie die Blickrichtung zeigt.

Also um das mal zusammenzufassen: Ich bin der Meinung er macht das schon ganz richtig so (mein Änderungsvorschlag oben mit einbezogen). Abgesehen davon, dass man die Kameraposition auch direkt aus der Matrix ablesen kann, aber vielleicht macht er das ja auch und hat das nur der Übersichtlichkeit so geschrieben, kA.

OpenGL unterscheidet nach dem Umlaufsinn der Punkte des Polygons (default: die Punkte von Frontfaces habe einen Umlaufsinn gegen den Uhrzeigersinn).
Quelle: http://www710.univ-lyon1.fr/~jciehl/Public/OpenGL_PG/ch03.html#id37717
(nach „Indicates which polygons should be discarded“ suchen)


Dazu kann ich nichts sagen, denn ich weiß nicht, welchen Punkt (Kamerapunkt? Cullingpunkt?) und welche Ebene (Polygon-Ebene? Kamera-Ebene?) Du meinst.


Da stimme ich Dir zu, aber das geht mit der Methode mit den Blickrichtungen auch.


Das finde ich ja auch richtig so. Was sich hinter mir befindet, sehe ich normalerweise nicht.


Weder Du noch ich noch eine Kamera können in alle Richtungen schauen. Die Blickwinkelmethode deckt alle Fälle ab, wo der errechnete Winkel größer oder gleich Null ist, das sind ganze 180 Grad, Bereiche in Grad ausgedrückt: [0,+90°] und [0,-90°], wobei die Grenzbereiche tolerant behandelt werden, weil +/-90 Grad noch ein möglicher Fall ist. Damit cullt er mehr als Du cullen würdest und das ist der eigentliche springende Punkt dabei. Ich bin der Meinung, dass hier die Blickrichtungen das Entscheidende sind und daher glaube ich, dass der Threadstarter das nicht richtig gemacht hat. Allerdings gebe ich zu, dass das eine ziemlich akademische Erörterung ist, denn vor dem Backface Culling kommt das Frustum Culling und dieses würde alles was sich hinter mir befindet ohnehin eliminieren. Und dann ist es sowieso egal, ob Du oder ich recht haben und wir könnten genausogut auf ein Bier gehen.


Dann wäre der Winkel Null dh. der Cosinus des Winkels (also das Skalarprodukt) wäre 1 (in Worten: Eins). Wenn die beiden Blickrichtungen einen größeren Winkel einnehmen als Null Grad (dh.: wenn 0 <= Skalarprodukt < 1): siehe oben voriger Punkt. Gecullt wird erst, wenn der Winkel größer als 90 Grad ist bzw. das Skalarprodukt kleiner als Null.


Ob man die Kameraposition aus der Kameramatrix ablesen kann, hängt davon ab, wie diese Matrix erzeugt wurde. Zuerst rotieren, dann verschieben: in diesem Fall hast Du recht. Zuerst verschieben, dann rotieren: in diesem Fall ist die Position nicht mehr einfach ablesbar.


NACHTRAG: mit dem Einschalten der kleinen grauen Zellen oben habe ich nicht Dich gemeint, sondern mich selbst, denn ich habe im ersten Beitrag das Normalisieren des Vektors empfohlen, und das ist in diesem Fall nicht nötig, wie Du ganz richtig bemerkt hast. Finde ich aber gut, dass Du Dich mit Geometrie beschäftigst. Gibt sonst nicht viele hier.
Viele Grüße
Traude

Ein bischen blöd ist, dass nur wir 2 hier diskutieren, eine 3te Meinung wäre vielleicht gut.

Die Seite aus deinem Link lädt bei mir dummerweise (gerade) nicht.
"Umlaufsinn der Punkte" ist sowieso ein bischen schwammig. Im Wiki hier steht das ja auch so. Das ist wie wenn man jemanden einen Ort beschreibt und sagt: "Rechts". Da gibt es auch mehrere Möglichkeiten, wegen "von mir aus oder von dir aus gesehen". Aber egal...

Mit "Ebene" meinte ich, die Ebene auf der das Polygon liegt. Und Punkt ist der Kamerapunkt.

Wenn man die Beleuchtung für einen Punkt berechnet nimmt man ja auch den Vektor von der Lichtquelle zum Punkt und vergleicht ihn mit der Normale des Punktes. Die Normale ist meistens die selbe wie die des Polygons, aber mit Normalmaps auch nicht immer. Aber das zählt beim Backface Culling auch nicht.
Selbst bei Spotlights die eine Richtung und einen Öffnungswinkel haben (und damit der Kamera recht ähnlich sind) wird das so gemacht. Die Abschwächung mit zunehmenden Abstand von der Mitte kommt nur dazu, ersetzt ersteres aber nicht.
Wenn die Lichtquelle hinter dem Polygon ist, wird es natürlich nicht beleuchtet. Wenn es aber davor ist, ist die Beleuchtungsstärke aber immer größer Null. Mal vom Spotlight Lichtkegel abgesehen, das wäre praktisch wie ein Objekt außerhalb des sichtbaren Bereichs, was aber trotzdem vor einem sein kann.
Und von der Lichtquelle zur Kamera ist es kein weiter Weg. Beim einem geht Licht raus, beim anderen rein.

Es geht ja eigentlich auch nicht darum wo mehr gecullt wird. Es soll ja nur das gecullt werden was auch wirklich nicht zu sehn ist. Vielleicht war mein Beispiel von oben mit der Wand nicht gut formuliert. Also mach ich das mal ein bischen konkreter:

Die Koordinaten sind alle im selben Raum, also nichts muss noch transformiert werden.
Also die Kamera befindet sich im Punkt (0,0,0). Und ein Polygon liegt auf der Ebene die durch den Punkt (1,0,0) geht und dessen Normale (-1,0,0) ist. Die Eckpunkte des Polygons sind dann praktischerweise so sortiert das dessen Normale auch (-1,0,0) ist. Dann würde das Polygon in Richtung Betrachter zeigen. Wenn der Betrachter in Richtung (1,0,0) sieht würde er es sehen. Ich denke soweit stimmen wir überein. Die genaue größe des Polygons ist nicht wichtig, sagen wir einfach es ist groß; unendlich in alle Richtungen wäre noch besser, damit es nicht zu übersehen ist.^^
Wenn die Kamera in Richtung (0,0,1) sieht würde man es auch sehen, bei einem unendlich großen Polygon würde es sogar die hälfte des Blickfeldes ausfüllen.
Ach ja, oben ist (0,1,0). Wenn das Sichtfeld der Kamera 90 Grad ist (kann man ja mit gluPerspective schön einstellen) und die Kamera nach (-1,0,2) schaut würde man das Polygon auch sehen, aber des Skalarprodukt der Blickrichtungen und Polygonnormale ist in einem Fall größer Null, im anderen kleiner.

Naja, ich hab' mal ein Bild angehangen, die sollen ja angeblich mehr als 1000 Worte sagen (obwohl dieses sicher gerade mal soviel wie 50 Worte aussagt).
Also das rote ist das Polygon. Der rote Pfeil daran dessen Normale. Der blaue Punkt ist die Kamera mit Blickrichtung in Form des blauen Pfeils. Und die hellblauen Linien grenzen des Sichtfeld ein.
Man sieht, dass das Polygon sichtbar wäre, obwohl die Kamera davon weg schaut.


Und wegen dem Kameraposition aus der Matrix ablesen, meinte ich das "c = (0,0,0,1) * M^-1" genau der 4ten Zeile (oder Spalte?) von M^-1 entspricht.

Hallo,
erstmal vielen vielen Dank für eure Hilfe. Die angesprochenen Änderungen habe ich umgesetzt und nun funktioniert es tatsächlich recht gut!
Das mir einige der Fehlerchen in meinen Formeln nicht aufgefallen sind, liegt einfach daran, dass ich mich mit OpenGL noch nicht besonders gut auskenne - insbesondere die Theorie dahinter bereitet mir immer wieder Kopfzerbrechen.

Zu meiner Schande muss ich gestehen, dass ich nun zwar bestimmen kann welche Würfelseiten sichtbar sind, mir das aber für mein eigentliches Problem nicht 100% weiterhilft weil ich dazu zusätzlich auch noch ein Clipping realisieren müsste, falls sich nämlich verschiedene Wireframe-Würfel überlagern bzw. sogar durchdringen.

Nun habe ich einen völlig anderen Lösungsweg gefällt. Dieser ist zwar wesentlich uneleganter aber er funktioniert und liefert mir die Ergebnisse die ich brauche.

Falls es jemanden interessiert: ich berechne mit GluProject die Fensterkoordinaten der 8 Eckpunkte eines jeden Würfels und lese dann mit glReadPixel den Farbwert an dieser Stelle aus. Falls es der Kantenfarbwert ist, ist der Eckpunkt sichtbar sonst nicht... ich weiß, ich weiß - das ist sehr einfach gedacht und sicherlich nicht halb so elegant wie BackfaceCulling und Clipping umzusetzen aber mir genügt es fürs erste...

Trotzdem nochmals vielen Dank für die hilfreichen Antworten. Sie haben auf jeden Fall sehr zu meinem "verstehen" der Hintergründe und der Mathematik beigetragen.

Lenco