Hi,

Als ich kürzlich, ungläubig die FPS in der Titelleiste anstarrend, mir das Beispielprogramm vom Octree-Tutorial genauer anschaute, entdeckte ich an manchen Stellen, dass an am Bildrand manchmal einige Polygongruppen abgesägt wurden.
Daraufhin inspizierte ich auch das Octree-Tutorial genauer und fand dann die Erklärung:

Und ich dachte schon... Ach keine Ahnung

Allerdings stören mich diese abgesägten Polygone, denn in einem Level wo der Boden bespielsweise nicht aus einer stark tesselierten Oberfläche, sondern z.B. nur aus einem Quad besteht, dürfte es schon ziemlich auffallen, wenn auf einmal der Boden nicht mehr da ist. Meine Frage also: Wie kann man die Funktion "PolygonIn" perfekt machen?

Es geht immernoch um das Vermeiden von dem Effekt, der auf dem Bild sichtbar ist.

Bye,
Frase

P.S.: Ein paar Bilder mehr im Tutorial könnten nicht schaden. Aber ansonsten ist es ein klasse Tutorial.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Die könntest auch die Flächen die die Node nur schneiden als innen liegend annehmen. Dadurch zeichnest du wenige doppelt. Es entstehen aber keine Fehlstellen.
(Denk ich mal... )

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

Die rote Meldung macht sich gut im Tutorial
Und wieso Fehler? Das Lesen des Nachtrags löste zwar bei mir ein mentales Hand-auf-die-Stirn-Schlagen aus, aber ich wäre da von alleine wohl erst sehr viel später darauf gekommen. Und das sehr darf man ruhig so sehr betonen wie Shadow es im Nachtrag gemacht hat

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Meinst du das hier?:


Mir fällt nämlich sonst auch spontan nichts anderes ein.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Genau das. Nur wenn das in dem Beispiel schon drinnen ist, sollte der obige Effekt net auftreten. Sieht eher danach aus, dass die Flächen in genau eine Node sortiert werden.s

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

ich würde polygone, auf die das zutrifft, einfach zerteilen und die reste dann in die entsprechenden quads verteilen. solange die quads nicht allzuklein werden und riesige polygone mit im spiel sind, erhöht das die polygonzahl nicht merklich.

Hi,

ich würde im Moment mehr zu Flashs Lösung tendieren, bzw. zu der, die angeblich in der Octree-Klasse eingebaut ist, im Endeffekt aber nur auf dem Papier vorhanden ist.
Und zwar einmal deswegen, weil mir das Splitten von Polygonen nicht ganz geheuer ist, wenn der Algorithmus dafür von mir kommt ... Auserdem dürfte es leichter zu implementieren sein.
Das einzige, was mich noch verunsichert ist die Reaktion von OpenGL auf doppelt gezeichnete Flächen.
Normalerweise entsteht ja wunderschönes Z-Fighting an den Stellen, wo 2 Polygone an der gleichen Stelle gezeichnet werden. Darum hat ja Sascha in seinem Bomberman-Tutorial die Schatten auch ein bisschen über dem Boden gezeichnet.
...
Ich glaub, ich stand grad ein bisschen auf der Leitung. Man sieht ja vom Z-Fighting gar nichts, wenn die Polygone absolut identisch sind .

Was ist aber, wenn das Dreieck nicht nur in 3 Würfeln, sondern in 4 Würfeln zu sehen ist/sein soll? Wenn das Dreieck so groß ist, dass die drei Eckpunkte gar nicht in 3 Würfel reinpassen? Wenn nur ein Würfel sichtbar ist, der gar keinen Eckpunkt von dem Dreieck enthält, das Dreieck aber trotzdem teilweise durch diesen Würfel geht? Funktioniert das mehrmals Zeichnen dann auch, bzw. wird das Dreieck überhaupt ein einziges Mal gezeichnet? Die Splitting-Methode müsste ja auch diesen Fall abfangen, aber was ist mit der anderen Methode?

EDIT:

Wie einfach ist "einfach"? "einfach zerteilen" klingt so, als ob es das leichteste der Welt wäre. Kann ich mir aber beim besten Willen nicht vorstellen...

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Dein Einwand mit den großen Dreiecken ist durchaus berechtigt und Problematisch. Man müsste zu diesem Zweck bereits beim erstellen des Baums bei Dreiecken die in mehreren Nodes liegen checken, ob diese auch so einen Fall hervorrufen (sollte durch einfache Untersuchung der Nachbarschaftsbeziehungen der Nodes machbar sein).

Zu Nicos "einfach": Ein Tesselierungs Algoithmuss wäre jetzt ma interessant und würde auch gut ins Wiki passen: http://wiki.delphigl.com/index.php/Tesselierung

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

Eine andere Idee ist, die Polygone nicht zu zerteilen und auch nicht mehrfach in den geschnittenen Knoten zu speichern, sondern genau einmal in dem kleinsten Knoten abzulegen, der das Dreieck gerade noch enthält.
In dem Tutorial werden die Dreiecke glaube ich nur auf der untersten Ebene des Baumes gespeichert, aber es ist ja auch durchaus möglich die Dreiecke, die nicht in einen der unteren Knoten passen auf den jeweils höheren Ebenen zu speichern.

Stimmt. Gute Idee. Damit kanns aber auch Polys geben die Quasi immer gezeichnet werden, wenn Sie sich im Zentrum des Baums befinden und dort Grenzen überschneiden. Allerdings wird sich diese Polyanzahl wohl sehr beschränken.

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

Ja klar, aber wenn sie so groß sind,werden sie auch sowieso sichtbar sein. Der ungünstigste Fall ist eine große Fläche, die eine Seite des ganzen Levels bedeckt und daher in den obersten Block kommt, obwohl sie bei Unterteilung dann in jeder Menge kleinster Würfel wäre. Kann ungünstiger sein, aber die Unterteilung bringt auch jede Menge neuer Flächen.

Ob so ein regelmäßiger Occtree generell die beste Lösung ist, ist sowieso fraglich. Es wäre ja auch denkbar, dass sich die inneren Knoten überlappen können und nicht gleich groß sein müssen. Das wichtigste ist ja für das Frustum Culling nur, dass die Knoten jeweils inneinander geschachtelt sind. Die Lage ist ja ansonsten egal.

So ein großes Polygon ist nichtmal das Problem, da es ja trotz der größe nur ein Poly ist. Eventuell verdeckt es sogar andere Polygone was günstig sein kann. Der WorstCase is in dem Fall eher ne Menge kleiner Polys welche die Zentralen Knotengrenzen überschreiten. Die würden dann alle gezeichnet werden, was mies ist.

Bei den unsymetrischen/regelmäßigen Nodes gibts aber auch wieder zig verschiedene Spezialfälle zu beachten, wo wied er andere Polys von NodeA nach NodeB ragen. Es ist schon ganz schön vertrackt. Deshalb ist die lösung mit der Tesselierung der Polys sicherlich die einfachste lösung, auch wenn sie kompiliert zu machen ist. Klingt seltsam is aber vermutlich so.

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

Diese Methode scheint wohl darauf angewiesen zu sein, dass man die Unterteilung an günstigen Ebenen macht. Bei einem normalen Level könnte da einiges an Geometrie hinzukommen. Das betrifft ja dann eigentlich alle Ebenen, dass die Dreiecke mindestens eins hochgestuft werden.
Mit den unsymetrischen Knoten ist es ja eigentlich noch einfacher. Man muß diese ganze Menge nur in mehrere Gruppen zerteilen, so daß das ganze halbwegs balanciert ist. Die Größe der Boxen würden sich ja dann automatisch ergeben. Das Unterteilen in diese Gruppen kann man machen indem man die Gravitation zwischen den Dreiecken simuliert (ungetestet). Alle Flächen die dann auf einem Klumpen sitzen, waren dann vorher wohl schon dicht zusammen, so daß man sie in einen Knoten packen kann.
Wenn man das unterteilt, hat man den Vorteil, dass die paar Flächen nichts kosten, aber Lichter viel feiner abgestimmt werden und z.B. ein kleines Licht in der Mitte einer Fläche weniger Fragment Shader kostet, weil man nicht die ganze Fläche damit render muß. Andererseits ist jedes halbwegs detaillierte Level sowieso schon zwangsläufig gut unterteilt, so daß man sich bei den regelmäßigen Unterteilungen unnatürliche Schnitte in die Geometrie macht. Das finde ich recht unschön an dem Occtree.
Ich persönlich denke, dass ein BSP Baum, in dem man nur die Bounding Boxen der Objekte zur Unterteilung nutzt, also die Objekte ganz läßt, eine sehr gute Wahl ist.

Also von wegen einfach: Besonders kompliziert ist es in jedem Falle nicht Aus einem schon eine weile herumliegendem Code habe ich eine Datei extrahiert, die das zerschnipseln von Dreiecken übernimmt. Was sie nicht macht ist die Texturkoordinaten anpassen, da ich die Funktion damals nur für die Kollisionsbaum-Erzeugung gebraucht habe, aber das dürfte nicht so schwierig werden. Fragen kann ich natürlich beantworten, aber an einigen wesentlichen Stellen sind einige Kommentare untergebracht.
Irgendwie bekomme ich das Attatchment gerade nicht hoch - werde es als Code ablegen:
[code mit mir inzwischen unbekannter herkunnft]

Hehe... Da schaut man einmal nicht in den Thread und schon fängt das zu wachsen an...

Die Dreiecks-Zerschnipsel-Methode ist in etwa so umfangreich, wie ich es befürchtet hab
Ich bin nicht so der Fan von Vektoren und Matrizen usw... Ich find zwar toll, was man damit alles machen kann und freu mich auch schon, wenn wir das mal in der Schule machen, aber im Moment ist mir v.a. die Welt der Matrizen noch etwas unheimlich. Und so hab ich eine konsequente Scheu vor zu großen Ansammlungen Algebra entwickelt...

Im Moment gefällt mir Lars' Idee vom Speichern der Polygone in den nächsthöheren Knoten am Besten. Besonders weil ich die Idee in etwa zeitgleich hatte .

Und dann hätte ich noch etwas zu sagen zu den BSPs... Ich weiß zwar nur ungefähr, wie die Dinger funktionieren, aber AFAIK kennen BSPs doch keine Fließkommawerte und nehmen Vertex-Positionen nur als Ganzzahlen entgegen, weswegen die Vertices erst quantisiert werden müssen. Im Gegenzug sind sie schneller als Octrees.
Octrees können aber die Daten von einem 3D-Programm (Maya, 3DS Max, Blender etc.) aber IMHO direkt verwerten.


Erm... Was wird eigentlich meistens bei einem Octree verwendet? (Methodenmäßig). Das höhere Einstufen von großen Polygonen? Das teselieren? Das Zerschnipseln? Oder einfach gar nichts (wie im Octree-Tutorial)?

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."