3D-Vektor hashing

Einstiegsfragen, Mathematik, Physik, künstliche Intelligenz, Engine Design
Antworten
Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

3D-Vektor hashing

Beitrag von Zudomon » 26.03.2009, 14:13

Hallo!

Ich würde gerne eine Art Hashing machen, das Problem ist nur, eine schöne Verteilfunktion für 3D-Vektoren zu finden... :?

Im moment habe ich das ganze so implementiert:

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);
Erstmal wird hier jede Vektorkomponente in einen Integer umgewandelt. Das "/NEAREST" ermöglicht mir einen kleinen Offset zu berücksichtigen. "index:=abs(((x xor y) xor (y xor z)) mod 50000);" ist meine Verteilfunktion, die garantiert noch verbessert werden könnte... aber ich weiß halt nicht, wie man das richtig gut machen könnte. Vor allem sollte die Verteilfunktion gerade bei symetrischen Objekten gut streuen.

Hat jemand vielleicht eine gute Idee?

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 26.03.2009, 14:42

Die drei Vektoren als Bit-Ketten einfach aneinander klatschen und dann eine Hash-Funktion deiner Wahl drüber jagen? Ist meiner Meinung nach zumindest einen Versuch wert ...

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 26.03.2009, 15:13

Danke für den Tipp! Hat super geklappt, jetzt ist es schön gleichverteilt :D

MadMax
Beiträge: 59
Registriert: 24.01.2003, 14:31
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von MadMax » 29.03.2009, 00:55

Hi das interesiert mich auch. Ich brauch ein möglichst effizeinte Hash Tabele über Richtungen(Vektoren der Länge 1). Kenne mich in diesem Bereich aber gar nich aus könntest du mal deine Code und dein Erfahrung darüber posten.

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 29.03.2009, 12:11

De-facto ist es völlig egal, wie die Daten aussehen. Die Beweise bzgl. der Laufzeit von Hashtabellen machen keine Vorraussetzungen, was die Eingangsdaten angeht - entscheidend ist nur, dass die Hashfunktion eine Gleichverteilung der zu hashenden Werte annimmt (der Erwartungswert von n Einfüge-/Lösch-/Zugriffsoperationen ist kleiner/gleich (1+Belegungsfaktor/2)*n). Es ist völlig egal, dass dabei "mehrere" Felder auftreten - diese sind schließlich nur in unserem Anschauungsbereich, d.h. der Interpretation der Daten vorhanden. Die Interpretation ist aber völlig egal.
Somit liegt das Problem nur noch in der Wahl einer geeigneten Hashfunktion. Der Link oben gibt einen guten Überblick.

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 29.03.2009, 14:21

Ich würde nur sehr ungern den ganzen Quellcode und meine individuelle Lösung dazu posten...

Vom Prinzip her ist es ja nur eine Datenreduktion, statt dann eine Schleife mit mehreren Tausend Elementen zu durchlaufen, sind es dann nur noch eine Handvoll Elemente.
Kollisionen vermeide ich, indem ich direkt ein zweidimensionales dynamisches Array verwende. In Delphi muss ein 2D-Array nicht Rechteckig sein.

Meine Erfahrung bei dem Vektor-Hashing:
Ich benutze das Hashing z.B. um zu schauen, welche Vertexe die gleiche Postition im Raum haben um diese dann zu verschmelzen. In 600ms kann ich so über 786.000 Vertexe auf gleichheit prüfen... Wie Effizient das ist, kann man sich ganz leicht vor Augen führen, indem man mal ausrechnet, wie viele Vergleiche auf naivem Wege gemacht werden müssten: Bei 4 Vektoren, müsste man den ersten Vektor mit 3 anderen vergleichen... dann den zweiten mit 2 andere, den dritten mit einem anderen, also 3 + 2 + 1 = 6 Vergleiche... Wenn man nun allerdings 786000 Vektoren nimmt, dann müsste man 308.897.611.776 Vergleiche durchführen!! Habe das mal gerade getestet... also bei mir schafft der etwa 125 Millionen Vektoren pro Sekunde zu vergleichen, also würde er die 308 Milliarden in etwa 41 Minuten schaffen. Wobei ich bei den 600ms sogar noch einen kleinen Distanzfaktor mit beachte. :D

Zudo

Benutzeravatar
Schrompf
Moderator
Beiträge: 3960
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Schrompf » 29.03.2009, 15:09

Vektor-Hashing zusammen mit einem Hash-Container (die ja üblicherweise O(log n)-Zugriffskomplexität haben) kann sich da durchaus lohnen. Wir haben für Assimp eine räumliche Sortierung benutzt, die die Vektoren anhand ihres Abstands zu einer fiktiven Ebene einordnet. Also praktisch nur ein linearer Hash anstatt eines 3D-Hashes wie bei Dir. Mit einer binären Suche in diesem sortierten Feld kommen wir damit auch auf O(log n) - funktioniert für die meisten Datensätze prima, weil die Referenzebene dafür richtig schief in die Landschaft gehängt wurde, fällt aber im schlimmsten Fall auf lineare Komplexität zurück.

Welche Version jetzt die bessere ist, kann ich nicht beurteilen. Deine Version wird wahrscheinlich den Großteil der Zeit in den Allokationen in der HashMap verbrauchen - wenn ich mich recht erinnere, war Delphi doch auch eine manuell speicherverwaltete Sprache? Falls ja, könntest Du durch einen Custom Allocator wahrscheinlich noch ne Menge rausholen. Ist aber aus der Entfernung schwer zu sagen.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

MadMax
Beiträge: 59
Registriert: 24.01.2003, 14:31
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von MadMax » 29.03.2009, 15:33

Mein Problem ist das ich sagen wir mal 1000 Richtungsvektoren habe. Die Aufgabe ist nun für einen gegeben Vektor(auch normiert) zu entscheiden in welchem er am ähnlichsten ist. Atm mach ich das über eine Schleife und das Dot Produkt. Allerdings ist das sehr sehr langsam. Kann ich das irgenwie über einen Hash lösen ?

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 29.03.2009, 15:38

Ich glaube, in besser oder schlechter brauch man das garnicht einteilen, weil es hier letztlich ja nur noch darum geht, ob man derlei Optimierungen benutzt, oder nicht.

Wegen der Speicherverwaltung kann ich nicht viel sagen... ich weiß nur, dass das reallocieren sehr langsam ist... aber schlimm ist das in meinem Fall nicht. Denn ich mache mir ein 2D Array mit 65536 Elementen ( ebend den Index, der durch die Hashfunktion auftauchen kann ) und in der zweiten Dimension habe ich 2 Elemente... ( da muss man natürlich schauen, was im Endeffekt der effektivste Wert ist )
Wenn nun durch Kollisionen die Grenze errreicht ist, wird da einfach die Länge der Zeile in dem 2D-Array verdoppelt...

Hab gerade gemessen... also das erstellen des 2 x 65536 Arrays dauert 5ms.... hmmm... das ist natürlich doch recht langsam... wobei hier die Größe ( in dem Fall die 2 ) garnicht ausschlaggebend ist... also mit 1 oder 4 ist es etwa genauso schnell... aber der Flaschenhals ist das im Moment nicht.

@Schrompf
Kannst du mir erklären, was du mit Custom Allocator meinst?

@MadMax
Hmm... das hört sich garnicht so einfach an... also mit Hashing wüsste ich das auf anhieb nicht zu lösen. Vielleicht könnte man da eine Art Quadtree bauen, der auf die Kugeloberfläche projeziert ist. Man könnte ja jeden Vektor in Polarkoordinaten umrechnen und dann daraus einen Quadtree bauen...

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 29.03.2009, 16:57

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.
D.h. du hasht jeden Vektor einmal und schaust dann, ob der Hash-Wert schon in der Hashtabelle vorliegt?
Schrompf hat geschrieben:Vektor-Hashing zusammen mit einem Hash-Container (die ja üblicherweise O(log n)-Zugriffskomplexität haben) kann sich da durchaus lohnen.
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 ;)

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. Das Problem ist: Man kann eine Kugel nicht entrollen, d.h. die Standard-Algorithmen im zweidimensionalem funktionieren nicht. In einer zweidimensionalen Darstellung gibt es somit immer Singularitäten, welche nicht in eine euklidische Geometrie passen.
Da ist man IMHO mit einem Hash-Algorithmus an einer ganz falschen Adresse, schließlich sagt der Hashwert nichts über die Eingabewerte aus, also erst recht keine "Ähnlichkeit" (das wäre für jeden Hash-Algorithmus auch ziemlich tötlich).
Der richtige Ansatz wird eine Art Sortierung sein, sodass der Algorithmus in O(log(n)) Zeit eine binäre Suche durchführen kann. Nur bin ich im Augenblick am grübeln, wonach man am besten sortiert (es handelt sich dabei ein sphärische Geometrie).

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 29.03.2009, 17:56

eXile hat geschrieben:
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.
D.h. du hasht jeden Vektor einmal und schaust dann, ob der Hash-Wert schon in der Hashtabelle vorliegt?
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.

Benutzeravatar
Krishty
Establishment
Beiträge: 7090
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Krishty » 29.03.2009, 18:42

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.
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.

Gruß, Ky
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 30.03.2009, 12:54

Der ganze Kram mit Kugelkoordinaten, etc. ist nicht geeignet, da man Singularitäten erhält. In solchen Fall nimmt man eine Dimension mehr dazu - bzw. hier lässt man einfach die Runterrechnung auf Kugelkoordinaten sein ;)

Ich habe nach langem Suchen endlich den Fachbegriff für solche Probleme gefunden:
http://en.wikipedia.org/wiki/Nearest_neighbor_search

Ich hoffe, das hilft dir weiter - denn was will man mehr, als O(log(n)) ;)

MadMax
Beiträge: 59
Registriert: 24.01.2003, 14:31
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von MadMax » 30.03.2009, 14:45

Wen du schon so fragst O(1) :-) das bekomme ich wen ich einfach die winkel theta und phi gleichmäßig unterteile.

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 30.03.2009, 15:05

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

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 30.03.2009, 17:06

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
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.
MadMax hat geschrieben:Wen du schon so fragst O(1) das bekomme ich wen ich einfach die winkel theta und phi gleichmäßig unterteile.
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?

EyDu
Beiträge: 87
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von EyDu » 30.03.2009, 17:14

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.

Wie eXile schon richtig bemerkte, handelt es sich hierbei um eine NN-Suche. Typischerweise werden dazu kd-Bäume verwendet, damit lassen sich die Suchen schnell lösen. Ich habe zu Hause sicherlich um die 10 Papers dazu liegen, da ich den Spaß für die Uni gerade selber brauche. Wenn Bedarf dazu besteht, stelle ich die Links auch gerne online.

Da die meisten hier gerne mit der GPU arbeiten, empfehle ich mal diesen Artikel.

Viele Grüße,
Sebastian

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 30.03.2009, 17:59

eXile hat geschrieben:
Zudomon hat geschrieben:... Die Eingabevektoren bräuchten nicht normalisiert sein und wenn ich mich nicht irre, hat man ein Laufzeit von O(1) :D
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.
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. ;)

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.
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.
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.
Zudomon hat geschrieben:... man nehme eine leere Cubemap, die müsste als Maximalauflösung so detailliert sein, dass sie alle Vektoren auflösen kann.
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.

MfG
Zudo

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 30.03.2009, 18:33

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. ;)
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: 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, 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: 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 wie soll er denn sich deinen Algorithmus anschauen, wenn du nur wage Beschreibungen - geschweige denn Quellcode oder Pseudocode - angibst.
Zudomon hat geschrieben:... man nehme eine leere Cubemap, die müsste als Maximalauflösung so detailliert sein, dass sie alle Vektoren auflösen kann.
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.
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.

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 30.03.2009, 19:43

Hallo,

also um hier ein wenig Ordnung in die Sache zu bringen:
Ich hatte ja den Thread erstellt. Mein Problem war, dass ich nicht wusste, wie man 3D-Vektoren gleich verteilen kann. Dann hattest du mir ja gesagt, mittels Hashfunktion und das war schon die Lösung, das Thema war dann für mich erledigt.
MadMax wollte ja dann aus einer gegebenen Anzahl von Vektoren den finden, welcher mit einem Eingangsvektor verglichen, in die ähnlichste Richtung zeigt. Beide meiner Lösungswege ( also als Quadtree über die Polarkoordinaten oder als Indezierte Cubemap ) waren auf dieses Problem bezogen.
Die Lösung mit der Cubemap ist nur für relativ geringe und gleichverteilte Vektoren geeignet.
eXile hat geschrieben:
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, 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 ...
Wie meinst du, dass hier Wissen mit fremden Namen abgezapft wird?

Was GENAU gefordert ist, das müsste uns MadMax sagen. Ich fand es nur nicht gut, das hier mein Lösungsansatz direkt so angegriffen wurde, denn ich denke, wenn dieser für MadMax ausreichen würde, dann wäre es ja eine sehr schnelle Lösung.
eXile hat geschrieben:
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 wie soll er denn sich deinen Algorithmus anschauen, wenn du nur wage Beschreibungen - geschweige denn Quellcode oder Pseudocode - angibst.
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:

MfG
Zudomon

Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 14:27

Re: 3D-Vektor hashing

Beitrag von eXile » 30.03.2009, 23:12

Ah OK, dann sind ja eigentlich alle Fragen beantwortet ... bin selber durch den Thread etwas verwirrt worden :lol:

MadMax
Beiträge: 59
Registriert: 24.01.2003, 14:31
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von MadMax » 30.03.2009, 23:17

Ganz ruhig ich hatte nicht vor hier irgend wem Wissen abzuzapfen oder etwas in der Art. Habe mich aber denke ich etwas unklar ausgedrückt. Ich kann ja mal kurz mein Problem genauer schildern:

Ich muss die Lichtverteilung über einer Voll kugel Speichern. Dazu gehe ich wie Folgt vor ich bestimme möglichst uniforme Sampels auf der Kugel und rechne daraus dan die verschieden Richtungen aus. Wen ich jetzt einen Strahl in die Kugle schieße möchte ich wissen zu welchem Sampel er am besten passt. Das beste Ergebniss bekomme ich mit Zufällig gewählten Punkten auf der Kugel. Um dan aber herauszufinden zu welchem sampel der Strahl am besten passt berechnen ich eben die cosinus similarity des Strahls mit jedem Sampel und speicher den Strhal unter dem besten Ergebniss.

Wen ich statt zufälliger Punkte einfach nur die Winkel uniform aufteile habe ich eine O(1) Algo. ich muss ja nur den Strahl in Kugelkordinaten umrechen und dan berechen zu welchem winkel abschnitt er gehört.

Benutzeravatar
Schrompf
Moderator
Beiträge: 3960
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Schrompf » 30.03.2009, 23:32

Wenn es nur um diffuses Licht (also keinen Glanz oder sonstwie gesteigerte BRDFs) geht, könnten Dich evtl. Spherical Harmonics interessieren. Die funktionieren wie eine Fourier-Transformation, nur auf der Oberfläche einer Kugel. Und schlaue Menschen haben nachgewiesen, dass man bereit mit SHs zweiter Ordnung (also 9 Koeffizienten) rein diffuses Licht mit ~6% Fehler abgebildet bekommt. Du bekommst also mit 9xRGB die komplette Lichtsituation in alle Richtungen für einen Punkt abgebildet.

Für Deine Zwecke würde sich aber vielleicht wirklich eine CubeMap empfehlen. Eine 64er, die Du vorher etwas weichzeichnest, dürfte dafür schon völlig reichen.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.

Benutzeravatar
Zudomon
Establishment
Beiträge: 2127
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von Zudomon » 30.03.2009, 23:39

Im Endeffekt kann man sich eine SH auch als eine kompimierte Cubemap vorstellen. Nur das man ebend diese, wie Schrompf schon sagt, mit 9 Koeffizienten darstellen kann, statt, wenn man 64 CubeMap nimmt, 64x64x6 Texel dafür braucht. Ich habe auch mal gehört, dass man mit Wavelets noch bessere Ergebnisse als bei SH erzielen kann, vor allem, wenn man höhere Frequenzen haben möchte. Kann aber sein das ich mich irre. ;)

MadMax
Beiträge: 59
Registriert: 24.01.2003, 14:31
Kontaktdaten:

Re: 3D-Vektor hashing

Beitrag von MadMax » 31.03.2009, 00:07

Ja Sh habe ich schon implementiert und Wavlets kommen demnächst aber trotzdem brauche ich auch eine vernünftige möglichkeit für genau das Problem.

Antworten