[OpenGL] Sichtbarkeitstest

[Showball]

Ich bin gerade dabei ein kleinen Egosooter für den DS zu programmieren, und die Hardware vom DS ist nicht gerade mal die beste! Er kann ingesammt 6144 Vertices (d.h. 2048 Quads) und 256 (128x2 Displays) verwalten! Nun muss ich darauf Achten, das ich nicht die 6144 Vertices grenze überschreite! Also wollte ich alles machen was geht, um die anzahl der Vertices so klein wie möglich zu halten! Bisher habe ich es hin bekommen, alle Vertices aus zu lassen, die Hinter mir liegen, also nicht in meinem Sichtfeld liegen! Also, man hat ein 90° Blickwinkel, und ich zeige nur das an was in diesem 90° Winkel liegt! Damit habe ich die Anzahl der Vertices um 75% reduziert, sofern sie gleichmäßig verteilt sind! Aber damit ist noch nicht genug, denn damit habe ich immer noch nicht genug ausgesondert, was ich nicht brauche. Was ist, wenn nun vor mir eine Mauer steht und was dahinter liegt, ist für mich ja nicht sichtbar! Ich habe mir nun den Kopf zerbrochen darüber, gezeichnet und gerechnet, aber mir ist kein Performance schonender Algorythmus eingefallen! Weiß jemand wie man solch einen Sichtbarkeits test machen könnte, oder kennt vileicht emand ein Seite wo dies erklärt wird?

[rapso]

Showball schrieb:

Ich bin gerade dabei ein kleinen Egosooter für den DS zu programmieren, und die Hardware vom DS ist nicht gerade mal die beste! Er kann ingesammt 6144 Vertices (d.h. 2048 Quads) und 256 (128x2 Displays) verwalten!

es sind 1536 quads, 2048 dreiecke.

Nun muss ich darauf Achten, das ich nicht die 6144 Vertices grenze überschreite! Also wollte ich alles machen was geht, um die anzahl der Vertices so klein wie möglich zu halten! Bisher habe ich es hin bekommen, alle Vertices aus zu lassen, die Hinter mir liegen, also nicht in meinem Sichtfeld liegen! Also, man hat ein 90° Blickwinkel, und ich zeige nur das an was in diesem 90° Winkel liegt! Damit habe ich die Anzahl der Vertices um 75% reduziert, sofern sie gleichmäßig verteilt sind! Aber damit ist noch nicht genug, denn damit habe ich immer noch nicht genug ausgesondert, was ich nicht brauche. Was ist, wenn nun vor mir eine Mauer steht und was dahinter liegt, ist für mich ja nicht sichtbar! Ich habe mir nun den Kopf zerbrochen darüber, gezeichnet und gerechnet, aber mir ist kein Performance schonender Algorythmus eingefallen! Weiß jemand wie man solch einen Sichtbarkeits test machen könnte, oder kennt vileicht emand ein Seite wo dies erklärt wird?

das laesst sich auf sehr vielen wegen loesen.
der meiner meinung nach beste weg, weil der nds keine performance zu verschwenden hat und mit float zu rechnen der tod waere, ist PVS.

das war auf lowend systemen eine sehr gelaeufige und simple art ist es offline auszurechnen was von wo zu sehen ist.
es gibt 3 probleme die dabei zu loesen sind
1. wie die welt aufteilen
2. wie speichert man effizient die sichtbarkeit (haengt mit punkt 1 ein wenig zusammen)
3. wie testen was zu sehen ist.

zu 3.
-man kann es analytisch machen und von jedem moeglichen punkt bzw raum ausrechnen (durch schneiden von geometrie) welchen anderen teil man sieht.
- man kann von jedem punkt aus in 6richtungen rendern und sich so merken was zu sehen ist.
- man kann einen raytracer in alle richtungen strahlen verschiessen lassen und jedes dreieck was man trifft, das ist auch sichtbar -> merken

zu 2.
-john carmack hat wohl die am meisten verwendete art 'erfunden', er speichert sich fuer jedes dreieck ein bit das aussagt ob es zu sehen ist oder nicht. das speichert er dann per runlenght, was sehr gute compressionsraten erlaubt und man kann ebenfalls ohne entpacken gleich mittels des komprimierten packetes durch die triangles rauschen.
-wenn man wie du schon weiss dass man auf ne bestimmte anzahl von triangles/quads limitiert ist, kann man sich auch einen index auf diese abspeichern. also u16 QuadIDs[1536];

zu 1.
- aufwendige verfahren generieren mittels solid-bsp convexe raeume und speichern pro raum die daten aus 2.
- simplere verfahren unterteilen die level in ein grid und pruefen und speichern pro grid-eintrag was zu sehen ist.
- einige spiele (gerade heutzutage) bei denen es zu aufwendig waere alles zu testen, merken sich jeden moeglichen besuchten punkt (generiert von leuten die das spielen) und generieren so nur fuer diese punkte solch ein PVS.
- selbst ausrechnen wo der spieler ueberall stehen koennte und fuer diese punkte in gewissen abstaenden die sichtbarkeit pruefen.

bedenke, das ziel ist _nicht_ PERFEKT rauszufinden was zu sehen ist, sondern was allerhoehstwahrscheinlich zu sehen ist (Potential visibility set).

...

alternativen waeren z.b.
- portal system (ist aber sehr von faehigen artist abhaengig)
- software occlusion culling (ist eventuel langsammer auf cpu als es bringt beim nds)
- einfach alles von vorne nach hinten sortieren und die ersten 2000quads zeichnen.

btw. durch backfaceculling kannst du oft auch 50% der primitiven einsparen

[Showball]

Danke für die Antwort, die hat mir sehr weitergeholfen! ich habe zwar nicht alles verstanden (ist noch zu viel fach chinesisch für mich), aber ich glaube ich weiß wie ich das dann mache:

Ich will ja ein Editor schreiben, wo ich die Maps erstelle, wenn ich nun damit eine Map erstelle und sie speichere, dann teste ich, welche Vertices an welchen Positionen sichtbar sind! Meine Camera bewegt sich immer nur in Interger schritten, weil, wie du schon sagtest, floats der tot für den DS währen. Ih gehe nun einfach alle positionen durch. immer x+1 und y+1, eventuell auch z, aber ist nicht unbedingt nötig wenn man im spiel nicht springen oder fallen kann! Dann speichere ich die Daten einfach in einer text datei, wo dann z.b steht:

1,1,0 = 18,2556,392,34

Vor dem "=" ist die camera position (x,y,z) und dahinter sind die vertices die sichtbar sind!

Wenn ich nun etwas anzeigen will i spiel, lade ich einfach diese textdatei, und beim zeichnen überprüfe ich dann immer, ob die vertices die ich zeichnen will, dennn überhaupt sichtbar sind?

habe ich das in etwa richtig verstanden? denn das ist eine echt gute methode um für den sichtbarkeitstest! Und das ist ziehmlich preformant, nur das speicern der maps mit dem Editor dürfte eine weile dauern xD

Nun interessiert mich, wie ich genaues testen machen kann, ob etwas zu sehen st oder nicht, ob es nun preformant ist oder nicht ist ja egal, da das nur einmal gemacht wird, und das mit dem editor, dn der user ja nicht hat un auch nimals haben wirt! Welche mehode ist dafür nun am besten geignet, um heraus zu finden was sichtbar ist oder nicht? Ich habe mal gehört, openGL macht diesen sichtbarkeitstest automatisch, von selbst, kann das sein, also das ich das garnicht mehr brauche?

[Showball]

EDIT::::::

Mir ist da gerade was eingefallen, wenn ich nun eine map von 100x100 cm mache, dann habe ich bei solch einer minni map, o ich gerade mal ein schritt machen kann, schon 10000 zeilen in der texdatei xD

Ich denke das müsste ich dann ein wenig abändern, das ich also immer einen radius in dem ich mich befinde speichere, also ich meine nen quadrat, z.b von 100x100cm, und es wird gespeichert, alles was in diesem quadrat drinne ist, so erspare ich viel platz! Nur auch um einiges ungenauer^^

[rapso]

Showball schrieb:

Ich will ja ein Editor schreiben, wo ich die Maps erstelle, wenn ich nun damit eine Map erstelle und sie speichere, dann teste ich, welche Vertices an welchen Positionen sichtbar sind! Meine Camera bewegt sich immer nur in Interger schritten, weil, wie du schon sagtest, floats der tot für den DS währen. Ih gehe nun einfach alle positionen durch. immer x+1 und y+1, eventuell auch z, aber ist nicht unbedingt nötig wenn man im spiel nicht springen oder fallen kann! Dann speichere ich die Daten einfach in einer text datei, wo dann z.b steht:

1,1,0 = 18,2556,392,34

das solltest du ueberdenken, es reicht wenn du, falls z.b. eine einheit 1cm ist, du nur fuer jede 10cm*10cm oder 50cm*50cm etwas abspeicherst. bei 1cm*1cm werden in 99% der faelle die gleichen primitiven in der liste stehen. du kannst natuerlich fuer jeden punkt die sichtbarkeit ausrechnen und spaeter dann anhand der daten deinen editor entscheiden lassen in welcher aufloesung der die speichert... oder eine noch effizientere idee nutzen.

Vor dem "=" ist die camera position (x,y,z) und dahinter sind die vertices die sichtbar sind!

Wenn ich nun etwas anzeigen will i spiel, lade ich einfach diese textdatei, und beim zeichnen überprüfe ich dann immer, ob die vertices die ich zeichnen will, dennn überhaupt sichtbar sind?

ich hoffe textdatei ist nur symbolisch gedacht, du wirst das schon effizienter speichern wollen. 128*128*16 ist durchaus ein realistisches grid. pro gridelement 1000quads und du bist bei 500mb. deswegen ist es wichtig das effizient zu speichern. aber keine sorge, hat bei z.b. quake super funktioniert, sollte also auf nem ds auch klappen.

habe ich das in etwa richtig verstanden? denn das ist eine echt gute methode um für den sichtbarkeitstest! Und das ist ziehmlich preformant, nur das speicern der maps mit dem Editor dürfte eine weile dauern xD

aus diesem grunde solltest du das nicht beim speichern machen, jedenfalls nicht die aufwendige version, sondern vielleicht nur die nahesten polys ablegen und dann in einem seperaten kompilierungsprozess die level einladen und 'optimieren'.
du wirst schnell auf die idee kommen weitere dinge einzubauen, z.b. lightmaps berechnen, navigationswege, Potentielles kollisions set etc.
das kann dann eine cpu ne nacht lang beschaeftigen.

Nun interessiert mich, wie ich genaues testen machen kann, ob etwas zu sehen st oder nicht, ob es nun preformant ist oder nicht ist ja egal, da das nur einmal gemacht wird, und das mit dem editor, dn der user ja nicht hat un auch nimals haben wirt! Welche mehode ist dafür nun am besten geignet, um heraus zu finden was sichtbar ist oder nicht? Ich habe mal gehört, openGL macht diesen sichtbarkeitstest automatisch, von selbst, kann das sein, also das ich das garnicht mehr brauche?

rapso schrieb:

3. wie testen was zu sehen ist.

zu 3.
-man kann es analytisch machen und von jedem moeglichen punkt bzw raum ausrechnen (durch schneiden von geometrie) welchen anderen teil man sieht.
- man kann von jedem punkt aus in 6richtungen rendern und sich so merken was zu sehen ist.
- man kann einen raytracer in alle richtungen strahlen verschiessen lassen und jedes dreieck was man trifft, das ist auch sichtbar -> merken