Code: Alles auswählen
x:=round(mVec3[i].x/NEAREST);
y:=round(mVec3[i].y/NEAREST);
z:=round(mVec3[i].z/NEAREST);
index:=abs(((x xor y) xor (y xor z)) mod 50000);
Hash.SetIndex(index);
D.h. du hasht jeden Vektor einmal und schaust dann, ob der Hash-Wert schon in der Hashtabelle vorliegt?Zudomon hat geschrieben:Ich benutze das Hashing z.B. um zu schauen, welche Vertexe die gleiche Postition im Raum haben um diese dann zu verschmelzen.
O(log n) im Average-Case ist aber ... ziemlich grottig. Zum Glück gibts ab TR1 die unordered_map, mit O(1) im Average-Case ;)Schrompf hat geschrieben:Vektor-Hashing zusammen mit einem Hash-Container (die ja üblicherweise O(log n)-Zugriffskomplexität haben) kann sich da durchaus lohnen.
Ich hashe den Vektor, und schaue, ob dieser schon vorhanden ist, wenn nicht, wird der mit eingefügt... dabei werden gleich Maps für die Indexdaten erstellt, die ja dann umgeändert werden müssen.eXile hat geschrieben:D.h. du hasht jeden Vektor einmal und schaust dann, ob der Hash-Wert schon in der Hashtabelle vorliegt?Zudomon hat geschrieben:Ich benutze das Hashing z.B. um zu schauen, welche Vertexe die gleiche Postition im Raum haben um diese dann zu verschmelzen.
Ich bin auf dem Gebiet nicht erfahren, aber könnte man als Hash-Funktion nicht den Algorthmus nehmen, mit dem man die Position eines Pixels in einer Cubemap bestimmt, und es damit eindimensional machen? Eine Cubemap ist schließlich eine eindimensionale Liste von Pixeln, die man als sechs zweidimensionale Flächen betrachtet und über einen dreidimensionalen Vektor adressiert. Die Singularitäten sind auch kleiner als bei Kugelkoordinaten und schnell ist es noch dazu (man erinnere sich an den Performance-Schub durch Normalizing Cubemaps zurück) … die Wahrscheinlichkeit einer Kollision hängt dann davon ab, wie hoch man die Auflösung der Cubemap wählt.eXile hat geschrieben:An MadMax:
Im Grunde reicht es ja aus, nicht die Vektoren oder Polarkoordinaten, sondern die Kugelkoordinaten zu betrachten. Dann hat man es nämlich mit einem zweidimensionalem Problem zu tun.
Dann konstruiere ich einfach einen Eingabevektor, welcher nicht genau zwischen zwei vorhandenen Vektoren liegt, sondern um ein Epsilon daneben. Wenn man dabei das Machine-Epsilon für floats nimmt: Viel Spaß mit einer 2^23x2^23 Textur, um den Vektor korrekt zuzuordnen.Zudomon hat geschrieben:Mir fällt da auch noch was ein... man nehme eine leere Cubemap, die müsste als Maximalauflösung so detailliert sein, dass sie alle Vektoren auflösen kann. In der trägt man nun jeden Vektor ein, den Index als Farbe... dann durchläuft man die Cubemap und vergrößert das ganze per Dilatation. Bedeutet, dass da, wo noch kein Index gesetzt ist, die Dilatation zum tragen kommt, ansonsten behält man einfach den Index an der Stelle bei.
Wenn so jeder Texel gefüllt wurde, braucht man nur noch mit dem suchenden Vektor in die Cubemap und bekommt den Index des am nächsten liegenden Vektors zurück. Das ganze könnte man jetzt geschickt auf GPU auslagern und somit tausende Vektoren ermitteln. Die Eingabevektoren bräuchten nicht normalisiert sein und wenn ich mich nicht irre, hat man ein Laufzeit von O(1) :D
Wenn ich die Winkel theta und phi gleichmäßig unterteile, kriege ich eine gleichmäßige Unterteilung von theta und phi, aber noch keinen Algorithmus :P. Was meinst du genau?MadMax hat geschrieben:Wen du schon so fragst O(1) das bekomme ich wen ich einfach die winkel theta und phi gleichmäßig unterteile.
Ich verstehe das Problem nicht. Solange die unterschiede der Ausgangsvektoren groß genug sind, um von der Cubemap erfasst zu werden, hat man zwar eine gewisse Quantisierung, wie bei Shadowmaps auch, aber man erhält für jeden Eingabevektor einen Index zurück. Da ist es egal, um wie viele Epsilons der verschoben wird. ;)eXile hat geschrieben:Dann konstruiere ich einfach einen Eingabevektor, welcher nicht genau zwischen zwei vorhandenen Vektoren liegt, sondern um ein Epsilon daneben. Wenn man dabei das Machine-Epsilon für floats nimmt: Viel Spaß mit einer 2^23x2^23 Textur, um den Vektor korrekt zuzuordnen.Zudomon hat geschrieben:... Die Eingabevektoren bräuchten nicht normalisiert sein und wenn ich mich nicht irre, hat man ein Laufzeit von O(1) :D
Vielleicht solltest du dir nochmal genau anschauen, wie mein Algo aussieht! Denn hier muss nichts geprüft werden, man hat die Texturkoordinate, welche den Eingangsvektor darstellt, sampelt damit die Cubemap und erhält den Index des Vektors, welcher ( Quantisierung beachten! ) am ehesten in die selbe Richtung zeigt, wie der Eingangsvektor.EyDu hat geschrieben:Baut mein eine Cubemap auf, hat man allerdings ein kleines Speicherproblem: Angenommen, ein Punkt ist gleich einem anderen, wenn dieser eine Abweichung von < epsilon/2 hat. Sind wir aber mal großzügig und testen gegen Würfelgrößen mit der Kantenlänge epsilon. Hat man dazu noch die Ausdehnung si der Achsen i=1,..,n , so muss jede Achse ui=si/epsilon Unterteilungen enthalten. Damit erhält man für die gesamte Cubemap u1*u2*...*un Würfel. Zum Testen, ob ein Punkt bereits enthalten ist, müssten noch alle (3^n)-1 Würfel betrachtet werden, da ein Punkt natürlich am Rand eines Würfels liegen kann. Viel Problematischer ist allerdings, dass damit der Test nicht von der Anzahl N der Punkte abhängt sondern von der Verteilung der Punkte! Löst man das Problem über ein Dictionary (oder für die C++'ler eine Map), dann könnte man den Ansatz wahrscheinlich noch retten.
Mit diesem Satz wollte ich eigentlich darauf Aufmerksam machen, was gegeben sein muss. Das man mit diesem Ansatz nicht unendlich detailliert auflösen kann, sollte klar sein.Zudomon hat geschrieben:... man nehme eine leere Cubemap, die müsste als Maximalauflösung so detailliert sein, dass sie alle Vektoren auflösen kann.
Aber man kennt doch nicht a-priori die Ausgangsvektoren. Wenn der Algorithmus für alle Ausgangsvektoren funktionieren soll, muss das Nyquist-Shannon-Abtasttheorem beachtet werden. Somit kann der Speicherbedarf enorm ansteigen.Zudomon hat geschrieben:Ich verstehe das Problem nicht. Solange die unterschiede der Ausgangsvektoren groß genug sind, um von der Cubemap erfasst zu werden, hat man zwar eine gewisse Quantisierung, wie bei Shadowmaps auch, aber man erhält für jeden Eingabevektor einen Index zurück. Da ist es egal, um wie viele Epsilons der verschoben wird. ;)
Ja, was ist denn gefordert? Am Anfang wolltest du ein gutes Hashing für deine Vektoren, nun ist die Diskussion völlig unklar. MadMax ist dazugekommen mit seinem Problem, und irgendwie scheinen eure Probleme ähnlich zu sein. Es ist aber unklar, wer hier was will. Irgendwie habe ich grade ein schlechtes Gefühl, dass hier nur Wissen in fremden Namen abgezapft wird ...Zudomon hat geschrieben: Die Frage ist einfach, will man O(1) und wenn ja, ist man bereit, dafür einige Dinge in Kauf zu nehmen, wie etwa Quantisierung.
Aber vielleicht sollte man erstmal wissen, was GENAU hier gefordert ist, bzw. was realisiert werden soll.
Ja wie soll er denn sich deinen Algorithmus anschauen, wenn du nur wage Beschreibungen - geschweige denn Quellcode oder Pseudocode - angibst.Zudomon hat geschrieben: Vielleicht solltest du dir nochmal genau anschauen, wie mein Algo aussieht! Denn hier muss nichts geprüft werden, man hat die Texturkoordinate, welche den Eingangsvektor darstellt, sampelt damit die Cubemap und erhält den Index des Vektors, welcher ( Quantisierung beachten! ) am ehesten in die selbe Richtung zeigt, wie der Eingangsvektor.
Bei meinem Ansatz wird auch nicht getestet, ob ein Vektor schon enthalten ist, denn ich bin davon ausgegangen, dass man eine bestimmte Anzahl vorgegebener Richtungen hat. Diese werden dann vorher in die Cubemap eingetragen, diese anschließend angepasst, und dann fröhlich reingesampelt.
Ja, aber ich kann für jede deiner Auflösungen bis zur Grenze aus obigen Abtasttheorem dir eine Eingabe geben, so dass dein Algorithmus zusammenbricht. Irgendwie ist der Ablauf unklar. Man hat ja keine Auflösung + Eingangsvektoren gegeben, sondern nur Eingangsvektoren, und dann wird daraus eine Maximalauflösung bestimmt. Ansonsten verfehlt der Algorithmus sein Ziel und liefert nicht im jedem Falle korrekte Daten.Mit diesem Satz wollte ich eigentlich darauf Aufmerksam machen, was gegeben sein muss. Das man mit diesem Ansatz nicht unendlich detailliert auflösen kann, sollte klar sein.Zudomon hat geschrieben:... man nehme eine leere Cubemap, die müsste als Maximalauflösung so detailliert sein, dass sie alle Vektoren auflösen kann.
Wie meinst du, dass hier Wissen mit fremden Namen abgezapft wird?eXile hat geschrieben:Ja, was ist denn gefordert? Am Anfang wolltest du ein gutes Hashing für deine Vektoren, nun ist die Diskussion völlig unklar. MadMax ist dazugekommen mit seinem Problem, und irgendwie scheinen eure Probleme ähnlich zu sein. Es ist aber unklar, wer hier was will. Irgendwie habe ich grade ein schlechtes Gefühl, dass hier nur Wissen in fremden Namen abgezapft wird ...Zudomon hat geschrieben: Die Frage ist einfach, will man O(1) und wenn ja, ist man bereit, dafür einige Dinge in Kauf zu nehmen, wie etwa Quantisierung.
Aber vielleicht sollte man erstmal wissen, was GENAU hier gefordert ist, bzw. was realisiert werden soll.
Ich habe versucht, den Algo vom Prinzip her zu beschreiben, es kann sein, dass mir das nicht sehr gut gelungen ist, ich bin aber gerne bereit das nochmal genauer zu erklären. Da allerdings die Beschreibung von EyDu absolut überhaupt nichts mit meiner Beschreibung zu tun hatte und ich davon ausging, dass er sich aber auf diese bezog, deswegen hatte ich das geschrieben. Wenn das etwas böse rüberkam, dann will ich mich dafür entschuldigen. :oops:eXile hat geschrieben:Ja wie soll er denn sich deinen Algorithmus anschauen, wenn du nur wage Beschreibungen - geschweige denn Quellcode oder Pseudocode - angibst.Zudomon hat geschrieben: Vielleicht solltest du dir nochmal genau anschauen, wie mein Algo aussieht! Denn hier muss nichts geprüft werden, man hat die Texturkoordinate, welche den Eingangsvektor darstellt, sampelt damit die Cubemap und erhält den Index des Vektors, welcher ( Quantisierung beachten! ) am ehesten in die selbe Richtung zeigt, wie der Eingangsvektor.
Bei meinem Ansatz wird auch nicht getestet, ob ein Vektor schon enthalten ist, denn ich bin davon ausgegangen, dass man eine bestimmte Anzahl vorgegebener Richtungen hat. Diese werden dann vorher in die Cubemap eingetragen, diese anschließend angepasst, und dann fröhlich reingesampelt.
