Ich arbeite aktuell ja an dem port von Karmarama, von Objekt Pascal zu C++. Wobei es kein 1zu1 Port ist sondern ich überwiegend die Sachen portiere aber einiges auch einfach abänder oder hinzugefügt/entfernt habe.
Da sind wir dann auch schon fast beim Thema.
Ich habe mich entschlossen meine Formate zu optimieren, um die Ladeperformance sowie CPU Last beim Laden zu minimieren und noch 1-2 andere Aspekte zu beachten.
Ich habe bisher das normale OS Filesystem verwendet, da ich nur ne handvoll Files hatte und somit das vfs dann nicht realisiert hatte.
Ausser dem Modelformat waren alle genutzten Formate unverändert und schon bekannte Formate.
Das Modelformat ist eher ein SceneGraph format und hat alle Daten der Scene enthalten und teilte sich in Header,NodeChunks,NodeData.
Der Ladevorgang war sehr zerstückelt, da das Format mehere read zugriffe brauchte.
Nun habe ich mir einige Gedanken gemacht und möchte diese mal mit anderen teilen und vieleicht eine Disskusion in gange bringen.

Ich habe ein paar Papers im netzt gelesen, wie man für Spiele optimieren kann, damit diese z.B. auf Console(PS2,xbox,PS3,xbox360,Wii) laufen können und sogar noch geschwindigkeit bringen. Die Papers Handelten von Virtual Filesystem, Serialisierung und Kompression.

VFS(Virtual Filesystem) hat den Grundgedanken, ein eigenes Dateisystem zu bieten, welches einheitlich an der Spieleschnittstelle anliegt.
Dabei können viele Features, implementierungen statt finden z.B. mountpoints(Ressourcen, wie cdrom, als eine Datei/Ordnerstruktur abbilden), OS basierte schranken zu umgehene(z.B. flache und auf sehr wenig Datein ausgelegte FS wie auf Wii).
Hier kommen auch oft Kompressionen zum Einsatz, diese haben 2 Vorteile.
Man kann die Daten kleiner machen und die zugriffszeiten der HDD,DVD,Internet sehr stark verbessern.
Ein Test, den ich im Internet gefunden habe, hat sich mit den HDD und DVD zugriffszeiten beschäftigt und eine zlib kompressions hat die streamfähigkeit erhalten, lief echtzeit und hat die leserate bei beiden um ~40% erhöht.
Kompression ist also schonmal eine sehr gute Optimierungsmöglichkeit.
VFS haben in der regel alle Daten in archiven hinterlegt, also mehere Daten liegen in einer reellen Datei.
Dies hat auch Vorteile, denn es müssen weniger Dateien offen gehalten werden(der cache wird nicht mit meheren unnützen Daten gefüttert und die Daten liegen nebeneinander was die lesezeit erhöht) und stösst nicht eventuell an grenzen des OS Filesystem.
Allerdings verliert man die oft sehr stark optimierte Dateiindizierung vom echtem Dateisystem.
Solche Archive sollten nicht größer sein, als ein Layer von einer DVD(sprünge zwischen layern sind sehr teuer ~100ms) oder 4GB.
Es gibt sogar Empfehlungen, der Anordnung von Daten im Archive für CDs/DVDs(der Zugriffshäufigkeit angepasst, um den Lesekopf weniger seeken zu lassen).
Für HDD wohl eher nicht so wichtig, wenn man nicht gerade mehr als 1GB hat(für ältere Platten mit kleinerem Cache wiederum schon).
Hierfür wird in der Regel ein praxistest ausgenutzt und die Häufigkeit der Dateizugriffe und Reihenfolge gemessen und dann das Archive angepasst.

Nun haben wir einige möglichkeiten der Optimierung auf der Dateiebene kennen gelernt und nun kommen die Daten selber.
Wenn man Daten ausliest kann man sehr viel falsch machen, für die gleiche Datei mit den gleichen Inhalt kann ich völlig unterschiedliche Ladezeiten haben.
Man sollte erstmal darauf achten, dass die Zugriffsschicht auf die OS calls möglichst wenig zusätzliche arbeit verrichtet, also nicht Klassen über Klassen die von einander abgeleitet sind und in jeden schritt noch zusätzliche prüfungen mit sich bringt.
Kapselung, der OS Dateisystem API, ja aber nicht in jeder Abgeleiteten Klasse die vorgänger methoden aufrufen und noch selber den Datenstrom validieren.
Die in Freepascal,gcc mitgelieferten stream klassen sind sehr performant und ich würde da nicht noch was eigenes drüber packen.
Dann ist das nächste Problem der read() Befehl, grundsätzlich gilt, je mehr readbefehle ein Dateiformat braucht, des so langsamer und unbrauchbarer ist es für schnelle Ladezeiten und vermutlich auch CPU lastiger. Ideal sind 2-3 readbefehle pro Datei und unter 2 read ist auch nicht ganz optimal.
In der Regel Teilt man ein Format in 2 Teile Header und Daten. Der Header validiert mindestens das Dateiformat, also ein Muster, was dem Loader sagt ich bin wirklich das was du suchst(siehe FourCC). Erst wenn dies der Fall ist werden die Daten gelesen oder die Datei geschlossen und macht noch eventuell bekannt, dass eine Falsche Datei übergeben wurde.
Das Ziel sollte also sein, die Daten so zu designen, dass man nicht noch großartig Prüfungen und Entscheidungen treffen muss.
Meine ersten Optimierungscchritte in dem Bereich war das umsortieren der Daten, damit man größere records/struct mit einen hieb laden kann und die dynamischen Teile dann durch eine Size Variable mit jeweils einen weiterem read laden konnte und dann im Code den pointer korrekt getypecastet habe.
Ein sehr guter Ansatz, zum einsparen von read Aufrufen, ist die Serialisierung.
Hierbei wird ein Objekt im ganzen in die Datei geschrieben und kann auch mit einen ruck wieder herraus gelesen werden(1 einziges read für die ganzen Daten).
Dabei müssen aber einige Dinge beachtet werden, Pointer müssen zu offsets umgewandelt und beim laden wieder zu pointer umgewandelt werden(beim speichern p1=@MyObj; p2=@MyObj.MyArray; offsetMyArray=AddrToNumber(p2-p1); beim laden speicher holen @MyObj.MyArray=@MyObj.MyArray+@MyObj;).
Alles dynamische muss also auf ein großen zusammenhängenden Block sortiert werden und die Pointer angepasst werden.
Wir haben eine verschwendung von Speicherplatz, da Arrays(z.B. String) im Speicher ein festen Speicherverbrauch haben(z.B. 256Byte bei standard String) aber in der Nutzung weniger braucht("Hallo"=6Byte+längenvariable).
Ein Problem dabei sind Pointergrößen, denn je nach System sind die 32,64,... Bit groß.
Wenn der Code auf einen 64Bit Sytem ausgeführt wird, dann stimmen die für die pointer reservierten plätze nicht mehr.
Eine Lösung wäre z.B. neben den "echten"(Speicher korrekt) struct/record noch ein "unechten"(Datei korrekt) zu haben.
Hierbei müsste man dann nur die dynamischen stellen durch 2 oder 4Byte große variablen ersetzt.
Dann wird ganz normal Speicher geholt,die daten mit dem Dateiechten record geparst, ein Speicherechter record/struct alloziiert, Dateiechter in Speicherechten kopiert und dann anhand des Dateiechten offsets die Speicherechten Pointer geschrieben. Also das record/struct in 2 ausführungen gehalten und im RelocateData() Methode ein weiterer compilerpfad eingebaut(ifdef 64BIT...).
edit:
2. Möglichkeit ist die größte Bit Architektur zu bestimmen z.B. 128Bit und dann alle pointer als 128bit variable zu belegen.
Diesmal dann eine Struktur mit Compilerflags( ifdef 32bit pointer bla; int reserved1; int reserved2; int reserved3; endif ifdef 64bit pointer bla; int reserved1; int reserved2; endif ... ).

Endian Probleme gibt es auch noch also anordnung der bytes im Speicher.

editende:

Ich selber nutzte für mein neues Format eine ähnliche Variante.
Mein Standard Header(1read) und ein Data Teil(1read) also schon mal nur 2 reads und alles ist im Speicher.
Also ich hab nun ein Speicherbereich, wo meine Daten drin liegen aber was da ist weiß ich noch nicht ganz(nur dass der erste Teil meinen definierten struct/record entspricht).
Ich benutze ein struct/record, in dem der Übersichtlichkeit zu gute alle fixen Daten am Anfang stehen und alle dynamischen am Ende.
Die Dynamischen Daten liegen dann hinter dem struct/record und die dynamischen variablen haben ein offset auf die Daten.
Also rufe ich noch eine RelocateData() methode auf, die dann die offets zu korrekten Pointern umrechnet(sehr schmerzlose Addition) und fertig, die Daten sind geladen und verarbeitet. Ich habe in meinen Fall z.B. String zu 32byte landen char arrays definiert und damit sind die nicht mehr dynamisch.
Allerdings brauch ich diese nur für den Namen von einem Property und für den HashFilename(der jeweilige Manager nutzt diesen Namen um die Ressource ausfindig zu machen) für Materials. Im Anhang hab ich mal den letzten Header meines Modelformates ran gehangen, für ein besseres Verständnis des Aufbaus(keine release version normals fehlen z.B.).
TKar_Mesh ist das interne Mesh, welches von einer Context Klasse zur verfügung gestellt wird. Bisher hab ich nur OpenGL und daher erstellt er ein TKar_MeshOGL, welches auf VBO arbeitet. Also können die Vertice,Color,Texcoord,...-daten 1zu1 OpenGL zum frass vorgeworfen werden und
damit spare ich wieder Zeit.
Meine Daten werden später in einen zlib komprimierten Archive lagern, aktuell überlege ich noch, ob ein Indizierter Baum mit in das Archiv kommt.

Was kennt Ihr noch für Optimierungsmöglichkeiten, welche nutzt Ihr, was haltet Ihr von den Vorgestellten Möglichkeiten ?

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Ok, das war jetzt viel

Also, zunächst einmal, ein normaler ObjectPascal-String belegt nur soviel im Speicher, wie er braucht (siehe das Problem, wenn man einen String kontinuierlich um ein Zeichen verlängert). Turbo Pascal hat als Standard noch den ShortString, der tatsächlich 256 Bytes belegt, aber das ist veraltet. Heute wird AnsiString als Standard verwendet, der ist dynamisch lang.

Was du mit den Offsets sagtest: Ich habe mal ein ähnliches Problem gehabt und das gelöst, indem ich jedem Objekt vor dem Speichern eine ID zugewiesen habe, die dann in allen Verweisen anstatt des Pointers gespeichert wurde. Das funktioniert eigentlich wunderbar, nur bei sehr vielen Objekten kann das Lookup natürlich irgendwann sehr langsam werden.
Deine Offsets klingen deutlich performanter, wenngleich die Implementation unangenehm sein dürfte.

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Ich behelfe mich im Augenblick mit einem nicht optimalen selbstgebastelten Loader und einem ebenso selbstgebastelten OBJ-Importer. Nach Beendigung meines derzeitigen Projekts habe ich vor, mich mehr mit Shadern zu befassen und dann werde ich den ModelLoader und das zugehörige 3D-Objekt so umschreiben, dass das Laden möglichst schnell geht, das bedeutet, das das Format an die Anforderungen der Grafik-Library angepasst wird. Beim Laden werde ich Streams verwenden.

Kompression verwende ich derzeit nicht, aber ich habe vor es zu verwenden: Waveletkompression von parametrisierten Meshes, wegen der guten Kompressionsrate und weil man sich da die Texturkoordinaten und möglicherweise auch die Faces ersparen kann, weil beides in dem Format implizit enthalten ist. Die Punktnormalen sind dann eben "on the fly" zu generieren. Ein Nachteil davon ist, dass zusätzliche Daten (z.B. Animationsdaten wie Bone-Indices oder -gewichte) nicht mit dem Mesh mitkomprimiert werden können.
Traude

Das klingt sehr interessant, gibt es dazu Papers, Links auf die du dich stützt ?
Ich kenne mich nur mit dem Haar Wavelet aus.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Ich habe den ganzen letzten Sommer und Herbst damit verbracht, Dokumente zu sammeln. Ich habe eine ganze Bibliothek darüber zusammengetragen, aber die drei informativsten Unterlagen (mithilfe derer ich auch in der Lage war, Pascal Sourcecode zu erstellen) waren folgende (leider alles in Englisch):

1)Thema Wavelet Transformation
Es gibt im deutschen Sprachraum eine Website (http://ainc.de), die meine erste Station war. Ich glaube, Du kennst sie, Du hast das mal erwähnt. Der Autor hat dort zwar das Haar Wavelet sehr gut erklärt, aber er hat selbst zugegeben, dass das Haar Wavelet nicht optimal für die Bildverarbeitung ist und hat dessen Unzulängichkeiten nachträglich beim Laden "geschönt". Sein Sourcecode war zwar Pascal/Delphi aber nicht sehr gut lesbar. Daher habe ich nach anderen Quellen gesucht. Gefunden habe ich ein Papier von Wim Sweldens (und anderen) mit den Titel "Building your own wavelets at home", die Grundlage für seinen Vortrag bei der Siggraph96. Wim Sweldens ist der Erfinder des Lifting Scheme; etwas besseres habe ich im Netz nicht gefunden obwohl ich wochenlang gesucht habe. Es ist fast so etwas wie die "Bibel" des Lifting Schemes und Achtung der Titel klingt nur so treuherzig, es ist ein tonnenschweres Dokument: http://www.multires.caltech.edu/teaching/courses/waveletcourse/athome.pdf

2) Thema ZeroTree Encoding
Wenn man das Wavelet glücklich erstellt hat, hat man erst die Phase der Vorbereitung für die Kompression hinter sich. Die eigentliche Kompression geht mit einer QuadTree-Konstruktion vor sich. Achtung: JPeg2000 verwendet KEIN ZeroTree Encoding.

Hier habe ich zwei Unterlagen anzubieten, die erste ist eine hervorragende sehr gut verständliche Einführung in das Thema. Er hat zwar Pseudo-SourceCode dabei, aber für ZeroTree Sourcecode habe ich noch ein besseres, das zweite unten angeführte.

***http://pagesperso-orange.fr/polyvalens/clemens/ezw/ezw.html
***http://www.uwec.edu/walkerjs/media/imagecompchap.pdf


3) Mesh Parametrisierung
Hier biete ich nur eine Übersicht an. Wenn Du dich nicht sehr damit beschäftigen magst: in dem Dokument ab Seite 15 ist eine bildlich dargestellte Übersicht wo man auf einen Blick den aktuellen State of the Art sehen kann. Damit beschäftige ich mich im Augenblick. Ob ich da durchsteige, kann ich noch nicht sagen, es ist mathematisch ziemlich aufwendig.

http://www.cs.stevens.edu/~quynh/courses/cs638-papers/mesh-parameterizations/sheffer_param_survey06.pdf


Das Schöne an den Wavelets ist, dass man damit nicht nur Bilder komprimieren kann, sondern auch Meshes. Die Meshes müssen dafür in die 2D-Ebene gebracht werden. Du kennst doch bestimmt diese seltsamen bunten Bilder von Meshes (sind auch in der Parametrisierungs-Übersicht ab Seite 15 zu sehen). Es ist ein Bild-artiges Array, wo eben nicht Bilddaten drinstehen, sondern Vertices aber dargestellt als Bild. Und weil die Vertices durch die Parametrisierung genau wie die Pixel eines Fotos sich jetzt in in einem Context (eben ihrem Mesh) befinden, sind die Daten redundant geworden, was nichts anderes heißen soll, als dass man eine gute Chance hat, aus zwei benachbarten Vertices denjenigen zu finden, der zwischen ihnen liegt. Das ist genau analog zu dem Vorgang, wenn Du ein Bild größer skalieren möchtest und das einzufügende Pixel finden willst. Eigentlich könnte man diese Daten auch mit JPeg komprimieren, aber z.B. ein LOD geht glaub ich nur mit Wavelets.

Ich werde mir die Papers mal morgen reinziehen, ich hab auch dieses Semester in der Vorlesung Jpeg2000 gehabt(war nicht da aber es gibt ja die folien ^^).
Der Prof kennt das Format, hat auch mit dran gearbeitet und hat wohl im Foliensatz ein paar Wavelet transformationen mit drin.
Ich hab mein neues Modelformat implementiert und auch den exporter geschrieben sowie schon ein paar stellen aufpoliert.

Ich hab die Informationen in das Bild rein kopiert und wie man sehen kann, dauert das laden aktuell ~3ms, für ein Model mit 15000 Triangle.
Aktuell liegt das zeug noch nicht in einen VBO, was man dann noch mit in die Zeit einrechnen müsste.
Es fehlen Texturkoordinate und Texturen aber Texturen(dds mit dxt1 und dxt5 bei mir) werden ja bei anderen Formaten(obj,3ds,..) genauso geladen und können eher vernachlässigt werden.
Die schlimmsten Zeitfresser werden bei mir die Materials sein, da diese Scriptbasiert sind(bisher noch LUA) aber dies ist ein anderen Modul in Karmarama und wird auch noch angepasst(wohl ne eigene mini scriptsprache).
Jetzt habe ich erstmal vor, dass ganze in ein zlib archiv zu packen und zu sehen was es so ausmacht.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Damit ich das recht verstehe: Du möchtest grundsätzlich eine Szene laden und implementierst ein Script, mit dem sich von außen z.B. steuern läßt, ob Du jetzt eine Karosserie mit rotem/blauem/etc. Lack kriegst? Oder ein mattes/spiegelndes Glas? Es wäre doch schneller, den Loader mit geeigneten Parametern loszuschicken, womit er das z.B. aus einem während des Ladens zur Verfügung stehendem Speicherbereich laden kann?

Im Modelformat steht drinne, welches Face welches Material verwendet und eine Liste mit Ressourcennamen.
Er lädt dann die entsprechenden Materials, welche Script Datein sind und führt diese aus.
Im Script stehen drinne, welche Texturen und Shader geladen werden sollen bzw. entfernt werden sollen und die vorgehensweise beim zeichnen.
sky.mat zeigt ein gutes Beispiel, wo Texturen,Shader geladen werden und beim zeichnen dann neben den binden noch eine Uniform Worldtime gesetzt wird.
Alternativ kann man das nur Hardcoden(erklär mal nen Grafik designer, dass er c++ programmieren soll) oder alle Uniforms bei jeden Shader mit binden(erklär mal den User, dass die 2FPS vollig korrekt sind, da zig unnutze variablen/konstangen gebunden werden).
Unreal engine und ID Tech engine haben früher noch asm artige materialfiles genutzt, die waren schnell geparst aber sehr unflexibel.
Heute nutzen beide Scriptsprachen für ihre Materials.

Ich habe die nacht und tag über mal probiert das Testmodel durch kompression zu optimieren.
Einsatz fand zlib und LZBRS, sowie Meshfiles in verschiedenen größen(700kb,2.1mb,10mb).
Beide haben ziemlich gleich kompremiert(~350kb,~750kb,~2,4MB) aber waren erschreckend lahm.
Die Lesezeiten unkompremiert(3-5ms,9ms,27-30ms) waren im vergleich zu kompremiert(zlib:700kb test=5ms 10mb test=60ms LZBRS 700kb test=27ms 10mb test=90ms) schneller, vorallem weil bei den zlib test ich schon die Daten im Speicher hatte. Die Zeitverbesserung bei kompremierten Daten ist wohl kaum noch zu verbessern, darum ist es ziemlich blöd.
Meine Idee ist nun LZBRS in mein archivesystem zu implementieren und die Ladezeiten durch vorhersagen zu verbessern.
Ich kann zur laufzeit einfach prüfen, ob z.B. neue Models geradezu kommen werden, wenn ich weiter laufen würde(Octree sind hilfreich).
Erstellt wird dann eine Vorhersage, welche Models wohl wirklich geladen werden müssen und kann diese schon mal in ein Modelcache packen.
Das passiert in einen Thread und der User kann bestimmen, wie groß der Modelcache sein soll.
Wenn der Cache größer ist, dann ist die Trefferwarscheinlichkeit größer.
Die Daten werden je nach Cachegröße verarbeitet,ein kleiner Cache entpackt die Daten nicht sondern werden nur rein kopiert, damit der Cache mehr Files inne tragen kann und ein größerer Cache entpackt die kleinsten Files schon.
Trifft man auf eine Anfrage und es liegt im Cache, dann hat man nur die entpackzeit+memcpy oder bei größeren Caches und wenig treffern nur ein memcpy.
Ist das Model geladen, dann kommen die Material anfragen, diese können wieder parallel zur gameloop verarbeitet werden(thread).
Dabei werden alle noch benötigten Materials aus dem archive gezogen(unkompremiert aber als bytecode) und ausgeführt.
Dann die benötigten Texturen aus dem Archive gezogen(alle files sind DXT1/DXT5 kompremierte DDS files und werden nicht nochmal kompremiert) und wenn sie geladen sind, dann werden die Flächen beim nächsten renderloop mit Texturen dargestellt.

Mal sehen wann ich das Implementiere, erstmal will ich noch VBO einbauen, dann ne eigene Material scriptsprache schreiben und dann das SceneGraph Format noch abtippen(schon fertig ausgedacht hier rumliegen). Dann könnte ich mich an ein Versuch ran machen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Ich hab mich nun mal mit Mesh parametrisierung auseinander gesetzt und auch noch ein paar andere dinge probiert.
Gestern hab ich mal mit rle auf den vertice rumgespielt und auch mal geguckt, wie sich eine haar wavelet transformationen auswirkt.
Die Werte werden ja durch mehrfaches wiederholen der Transformation immer kleiner/größer und durch das umsortieren der kleinen Werte treten immer wahrscheinlicher gleichheiten auf. Mein versucht hat erst rle(370kb zu 310kb), rle mit einmaliger transformationen(370kb zu 310kb) und rle mit verlustbehafteter transformationen(370kb zu 301kb bei clamping von <0.1 auf 0) beinhaltet.
Wie sah meine Transformation aus ?
Ich habe nur den Vertex und Normalteil aus dem Format verwendet(der rest ist nicht sonderlich groß ausser indices).
Also float *v1,*v2=0; für vektor1 und vektor2, floats bieten sich an, da die transformation sowieso floats erzeugt.
Aus x1,y1,yz1,x2,y2,z2 wird dann newx,newy,newz,differencex,dify,difz.
Meine trasformation geht alle vektoren einmal durch und errechnet die neuen werte, dann läuft ein sortierprozess, der die newX/Y/Z an den anfang transporitert(newx1,newx2,newx3,...newy1,newy2,newy2....) und die differenzen an das Ende packt(difx1,difx2,...dify1,dify2,...difz1...).
Bei floats zu verarbeiten hat den Vorteil, dass keine Daten verloren gehen, byteverarbeitung schon oder man hat mehr Daten(5,2 s=3.5 d=1.5 also aus 2byte werden 2floats ergo 4mal so groß).
Bei Bilder wird hier nun angesetzt und das Rauschen entfernt(wenn es denn ein echtes Bild war) und bringt ne menge 0 mit sich(hohe kompression).
Das Problem beim Mesh ist, dass der Wertebereich auch größer ist(byte=0..255,float -.,...*10^x - +.,...*10^x) und damit mehere durchläufe gebraucht werden, bis die signale maximiert(Signal) und minimiert(differenz) sind. Bei meinem Test bin ich von 301kb auf 299kb gekommen, als ich von einen durchgang auf 9 erhöht hatte. Meine Schranke lag bei 0.1 und ist eigentlich schon ziemlich Hoch und für solche eine riesen rechenlast 70kb von 370kb weg zu kompremieren ist keine Lösung für meine Anforderungen.
Ich werde mein zeug einfach mit dem Algo meines Kumpels kompremieren und das erwähnte Precaching im VFS einbauen.
Dann brauch ich nur einen kompressionsalgo und muss nicht zur laufzeit noch großartig rechenen.

Bei der Thematik ist das Packen ja nicht im Mittelpunkt, sondern das Entpacken und somit kann das Packen auch lange dauern, solange das entpacken fix läuft. Haar Wavelet muss ja für jeden Durchgang, den man vorher gemacht hat auch beim entpacken wieder gehen und das kostet "irre viel" Zeit.

Die Mesh parametriesierung hab ich auch verworfen gehabt.
Ich hab ein ziemlich gutes Paper gefunden und dachte mir, ich linke es mal.
http://citeseer.ist.psu.edu/gu02geometry.html
Die Schritte sind grob erklärt nicht der Hit.
Mesh so aufschneiden, dass es in 2D projeziert werden kann(Algo ist im Paper erklärt).
Vertice in den 2D Raum projezieren(Signal liegt im geometriebild und differenz in der Normalmap).
Bei der rekonstruktion wird eine 2x2 matrix aus den Daten gelesen und die Daten durch 2 Triangle(4eck) als Mesh dargestellt.
Zum Schluss wird noch die Normalmap mit Shader drüber gebügelt.

Die Variante ist hochgradig verlustbehaftet, hat redundanz(an den rändern der geometrymap) und die Daten des rekonstruierten Bildes haben nicht mehr viel mit dem Orginal zu tun(ausser das das Model dem orginal sehr ähnlich aussieht). Durch Mipmaps bekommt man eine sehr sehr gute LOD für 1/3 mehr Platz dazu.

Niedrig Polygonierte Meshes macht man damit völlig kaputt(kompression sind sehr gut sichtbar) aber hoch aufgelöste Meshes werden sehr gut runter optimiert.
Das gleiche ohne geometriemap machen ja auch die Spielefirmen für ihre Models. Hochpolygoniertes Model erstellen, runter reduzieren, wo es die Möglichkeit gibt(die differenz gering ist und wo rauschen auftritt) und die differenz zwischen orginal und ziel signal als Normalmap hinterlegen.

Ich bin gestern auf eine lustiges kompressionsverfahren gestossen.
Dabei hat man die Vertice durch ein Binärbaum beschrieben.
Also ein maximalen Span aufgebaut(das gleiche wie eine boundingbox) und dann angefangen binärketten zu generieren.
0 für die eine Seite 1 für die andere Seite der BoundingBox, dann die neue kleine BoundingBox wieder geteilt 0 für die eine seite 1 für die andere.
Wichtig ist dabei, wie nah ist das Vertice am Zentrum der BB und wie tief möchte man gehen.
Wenn man z.B. sagt 24 Schritte darf er machen, dann muss das Vertice an das Zentrum der aktuellen BB angepasst werden, dann hat man die Daten von 12Byte auf 3Byte pro Vertice gekürzt(natürlich ebenfalls verlustbehaftet).
Das Problem ist allerdings, man braucht dann 24 Schritte, um das Mesh wieder in eine nutzbare Form zu bringen.
Vorstellbar wäre hier beim entpacken ein Baum parallel zu generieren, der z.B. beim ersten bit dann beide Knoten erstell und die Werte für diese dort hinein legt. Beim 2. Bit für das eine Node die 2 Subnodes erstellt und so weiter. Dann könnte man dem Baum die 24Bit geben und er liefert ein Wert zurück, wenn Nodes schon existieren spart er zeit
Ein Vertice besteht aus 3 floats, also 12byte und damit 128bit möglichen Schritten(verlust ohne kompression).
Wenn man also seinen Baum erstellt, dann legt man eine Schranke, wie bei Wavelet transformation, fest und wenn alle Vertice angepasst wurden guckt man nach dem Tiefstem Node und nutzt die Bitlänge für alle.
Normals kann man auch auf den Weg optimieren, die richtungsvektoren werden einfach als positionsvektoren interpretiert und dann funtzt der Algo ebenfalls. Blöd ist nur, dass man dann für OpenGL noch die Normals wieder Normalisieren sollte(oder im Vertexshader).
Bei diesem Verfahren muss man allerdings immer probieren und entscheiden, ob das Ergebnis weiter zusammengestaucht oder wieder höher aufgelöst werden soll(bei der parametrisierung von Mesh ebenfalls die frage, ob 65x65 oder doch lieber 127x127).

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Auf Gamasutra gab es dazu auch mal einen Artikel - gar nicht so lange her - der sich mit der Thematik beschäftigt hatte. Es ging hierbei vor allem um Spiele mit großen Arealen wie GTA die ihre Welt bekanntlich in Segmenten aufteilen und dann bei Bedarf die jeweils benötigten Elemente nachzuladen. Was im Artikel aber gleich zu Anfang hervorgehoben wurde war, das die Positionen im Dateisystem aller Dateien zu jeder Zeit für einen schnellen Zugriff verfügbar sein sollten.

Damit der Overhead nicht zu groß wird müssen die Namen der einzelnen Dateien in der finalen Version entsprechend numeriert sein um platzsparend gespeichert werden zu können.

Ich denke das kannst du dir bei deinem VFS auch zu nutzen machen und einen Vorteil von ziehen

//edit: Lesenswerte Artikel:
http://www.gamasutra.com/view/feature/1 ... g_pt_2.php
http://www.gamasutra.com/view/feature/1 ... _games.php

_________________
(\__/)
(='.'=)
(")_(")

Ich hab mich nochmal mit der Kompression beschäftigt und wohl die beste Lösung für verlustfreie float Kompression und vorallem mit sehr kurzen entpackzeiten behaftete Verfahren gefunden.
http://www.cs.unc.edu/~isenburg/papers/ils-lcpfpg-05.pdf
Ich habs mir intensiv durchgelesen und auch mal ein bischen drüber nachgedacht aber halte eine Umsetzung ziemlich schwer.
Grob gesagt, wird die beschaffenheit von Float/Double ausgenutzt und natürlich der Fakt, dass Modeldaten nicht Sinnfrei im raum verteilt sind.
Als erstes werden die Extremwerte gesucht, also eine Boundingbox gezogen, nun werden alle Punkte relativ zur Boundingbox betrachtet.
Dadurch werden alle Zahlen erstmal Positiv(vorzeichenbit kann wech) und nun beginnt der komplizierte Teil.
Das Float wird in 3 einzelteilen zerlegt ein integer für Vorzeichen, eines für Exponent udn eines für die Mantisse(simples bitshifting und benutzen von and/& ).
Nun werden die Exponenten angepasst, man braucht ja nur selten die vollen 8bit des Exponenten und den rest hab ich dann nicht mehr verstanden ^^.
Irgendwie werden die Mantisse und Exponenten reduziert, ohne die Werte zu verfälschen und deswegen nutzt man auch ein Integer zum rechnen.
Die dekompression über simples bitshifting und and/& und ist extrem schnell(im Test ist die rede von ~900.000 Vertice die sekunde).
Das Kompressionsverhältnis ist meist 1 vertice pro float, also sehr beeindruckend für verlustlos.
Die Technik hat auch Vorteile, da man beim packen auf 32bit pro vertice einfach die Daten kompremmiert lassen kann und über ein vertexshader onthefly entpacken.
Dies würde auch weniger VRam und höheren Durchsatz auf der Grafikkarte zufolge haben.
Leider fehlt mir die Zeit, um mich in der Thematik so Sattelfest zu bekommen, dass ich eine implementierung erstellen könnte.

edit:
Eine Verlustbehaftete Variante wäre allerdings ziemlich easy zu coden.
Boundingbox finden, die Werte zu integer Elementen aufsplitten, position der BB drauf addieren(Vorzeichen bit fällt nun weg).
Wir legen eine Maximale Genauigkeit fest(die BB gibt uns infos über den Wertebereich also von bis Wert).
Man sagt 3 floats müssen in einem unterkommen also darf Mantisse und Exponent nur 10 11 11 oder in anderer Kombination auftreten.
Eine Analyse der Vertice auf jeder Einzelnen Achse könnte hier nochmal optimierung bringen(2k Vertice die überwiegend auf der y und x aber wenig auf z verteilt sind wäre eine höhere bitzahl für x und y besser(als Beispiel ein Strassenschild)).
Durch den Schwellwert, z.B. 3stellen nach dem Komma, können wir nun die maximal benötigte Bitzahl für den Exponenten errechnen(durch BB kennen wir den Wertebereich vor dem Komma und durch unseren Schwellwert legen wir den Nachkommabereich fest).
Den rest Spendieren wir der Mantisse und packen nun alle Daten in ein neu Konstruiertes Float.
Beim Entpacken brauchen wir folgendes Informationen:
-offset durch die BB
-größe der Mantisse
-größe des Exponenten
-wenn man kein statisches bitverhältnis hat dann noch bitcount für x,bitcount für y und z
Dies kann man am Anfang der Komprimierten Daten als 3float und 4byte(mantisse,x,y,z) mitgeben(exponente kann durch 32-mantisse errechnet werden).
Nun kann man die 3 floats einfach als Transformation vor dem zeichnen setzen und die 4 byte dem Vertexshader übergben(einmal beim starten, da die sich nie wieder ändern).
Die Daten werden in ein VBO mit 1xFloat größe pro vertice gespeichert.
Wenn nun der VS am drücker ist, gibt er uns das Float aus dem VBO, wir erzeugen x,y,z durch die übergebenen Werte.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Ich hab mich nochmal mit verlustbehafteter kompression von floats beschäftigt.
Idee:
Vertex und Normal werden in 3 floats gepackt also von 6floats auf 3 reduziert
TexCoords werden von 2floats auf 1 float gepackt
Vertice,Normal,Texcoords gepackt auf 4floats(vorher
Man kann also die 3 Informationen in einen 4float VertexBuffer unterbringen und per vertexshader onthefly entpacken oder die Daten beim Laden konvertieren.

Wie wird gepackt?
Wir betrachten Vertice,Normals,Texcoords einzelnen, da wir so bessere Ergebnisse erzielen.
Als allererstes wird eine Boundingbox um die Elemente gezogen.
Nun kennen wir den kleinsten und größten floatwert.
Jetzt fügen wir ein offset hinzu und verschieben alle Werte in den positiven Bereich.
Also fallen nun 3floats für den Offset(für Vert,Norm,Texcoord brauchen wir jeweils einen) an und brauchen nun für jedes Float in den Daten 1 Bit weniger(Vorzeichenbit fällt weg).
Bis jetzt haben wir keinen verlust aber schonmal eine Kompression.
12floats für die Offsets der 3 Datenströme also 48Bytes=384Bits mehr an Daten aber für jedes Float in den Daten brauchen wir 1 Bit weniger.
Wenn wir Also 100 Vertice/Normals/Texcoords haben, dann sind das 800floats=800Bit und 800-384=416Bit eingespart(52Byte=13floats).
Das sind ~ 1/32, also ziemlich lächerlich aber dieses gewonnende Bit kann man später gut gebrauchen.
Nun kommt die verlustbehaftete Kompression.
Wir Teilen die Boundingbox, von jeden Datenstrom, in 2 oder 4 Teile(auf der Achse, die den größten Wertebereich hat).
Hier bei schaut man sich die konzentration der floatwerte an(Histogram) und teilt die Bereiche möglichst so auf, dass hohe floatkonzentrationen ein sehr kleinen Bereich erhalten und Bereiche, mit wenig floatwerten, ein möglichst großen Wertebereich abdeckt.
Wenn man ein Menschenmodel hat, dann ist die höchste konzentration z.B. im Kopf als Bereich 1 ist Kopf,Bereich 2 sind Schultern und Arme(arme sind hier mal gerade ausgestreckt),3. Bereich Brust und 4. Beine.
Jetzt kommt der verlust ins Spiel, wir speichern die Daten nicht mehr als Float sondern als ganze Zahlen.
Hier bei sind die ersten 2 Bit der Index auf den Bereich(0..3) und folgende Bit ganzzahlige positive Zahlen.
Die Zahlen werden wie folgt berechnet. Floatwert-Bereichstartwert(erster möglicher Wert in den zugehörigen Bereich)=bereichswert
Nun wird anhand der bitverteilung für die einzelnen floats weiter gerechnet.
Wenn wir für X 15Bit haben dann können wir also 2^16-1 als maximalwert darstellen.
speicherx=round(bereichswert/(2^16-1));
Nun das gleiche nochmal für Y und Z, mit deren verfügbaren Bitgrößen und wir haben die Vertice kodiert.
Das ganze noch für Normals und TexCoords, mit deren Boundinboxen und Wertebereichen.

Eine Normalverteilung würde so aussehen
2Bit(Blocknr),15Bit(X),15Bit(Y),15Bit(Z),2Bit(Blocknr),15Bit(NormX),16Bit(NormY),16Bit(NormZ),2Bit(BlockNr),15Bit(TexCoord),15Bit(TexCoord)
Zusätzlich zu den Daten müssen wir noch die Bereiche für Vert,Norm und Texcoord, sowie Bitoffset,Bitsize speichern(einmal pro model).

Der Ladeprozess sieht so aus, Daten aus der Datei auslesen und in ein 4x float vertexbuffer binden.
Vor dem Zeichnen wird dann ein Vertexshader gebunden, der aus gl_Position dann Position,Normal und Texcoord rausholt.
Der Vertexshader bekommt beim compilieren die Bereiche und Bitverteilungsdaten zugewiesen.
Die echten Daten können jeweils durch ein Bitshifting(Wert wird ans ende geshiftet),and(wird mit maximalwert verundet, alle anderen bits werden 0),einer multiplikation(floatwert für ein Intervall des Bereichs) und addition(erster möglicher Wert des Bereiches).
Für jeden Verts,Normals,Texcoords kommt noch jeweils ein bitshifting und and für die Blocknr hinzu.

Wem das zu langsam ist, der kann das ganze auch beim Laden machen.

Ich habe mal ein paar berechnungen gemacht und Datenverlust tritt ab der 3-4 Nachkommastelle auf, wenn die Floats ziemlich gleich verteilt sind.
Wann die Fehler enstehen hängt aber von Wertebreich eines Models ab und wie die Verteilung der Float darin sind.

Atachment:
Y-Achse=Blau hat den größten Wertebreich und muss also auf Y-Achse unterteilt werden.
Die Bereiche werden der Anzahl an Vertice, im verhältnis, zugewiesen.
Der Bereich 4 hat die wenigsten Vertice und damit ist es nicht so schlimm, wenn dort fehler in der Nachkommastelle auftreten(hat wenig auswirkungen auf den gesammten Fehlerwert.
Bereich 1,2 und 3 sind sehr klein und haben somit eine viel höhere genauigkeit und damit auch kleinere Fehlerwerte.
Für Normals und Texcoors kann man das gleiche Schema verwenden ist nur nicht so einfach vorzustellen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004