Distanz / Nähe der Vertices eines Meshes zueinander
-
Hallo zusammen.
Folgendes:
In einem 3d-Mesh sollen für jeden Vertex die geographischen Nachbarn gefunden werden. Straight forward könnte man einfach für jeden Vertex die Distanz zu allen anderen messen und Nachbarn in eine Liste eintragen, wenn die Distanz unterhalb eines gewissen Schwellwertes liegt. Soweit sogut, bei ~100k Vertices durchaus etwas zeitraubend. Wie könnte man das Mesh sinnvoll aufteilen, um nur die nähere Umgebung miteinzubeziehen?grüße
Martin
-
Da es ja ein Mesh ist, sollten die benachbarten Vertices auf den Polygonen zu finden sein, die auch den Referenzvertex beinhalten.
-
erstell ein volume (sprich: 3d array) welches die ausmasse des meshes hat und ein elementausmass welches dem schwellenwert von dir entspricht. dann musst du fuer jedes vertex nur alle 26 nachbarelemente (+das wo sich das vertex befindet) (bzw die darin einsortierten vertices) testen
-
wenn du wirklich nur die "unmittelbar angrenzenden" vertices willst würde ich auch einfach über die indices schauen welche vertices an meinen angrenzen
dabei kann es natürlich sein dass wenn ich die nachbarn eines vertex V suche er auf einer face liegt die riesengroß ist und die nachbarn auf der face von V liegen ganz weit weg wobei andere vertices welche sich nicht eine face mit V teilen viel näher sind
wenn du also wirklich alle vertices wissen willst die um V herum liegen gibt es algorithmen die man dazu verwenden kann, das ganze fällt in die kategorie geometrische algorithmen weil sie eben ausnutzen dass deine daten bestimmte geometrische kriterien erfüllen
hier ist eine zusammenfassung: http://en.wikipedia.org/wiki/Computational_geometry
was du willst ist schätze ich mal
Range searching: Preprocess a set of points, in order to efficiently count the number of points inside a query region.
ich hab das als "bereichssuche" gelernt, dabei baut man sich für 3d einen baum auf der je nach höhe einmal nach x, y und dann z sortiert ist und kann dadurch in 3d die punkte in einem recktecksbereich in O(3 * n^(2/3) + R) finden und der baum wid aufgbaut in 3n * log(n) wobei du das halt nur ein mal machen musst
naja mit den keywords müsstest du eigentlich irgendwas nützliches googeln können
-
KD-Baum!
-
Eine andere Möglichkeit würde in folgendem Artikel beschrieben werden.
"A simple GPU-based approach for 3D Voronoi diagram construction and visualization"
-
Danke euch für die Keywords, ich mach mich mal auf die Suche.
Und ja, Vesuvio, das Range searching kommt meinem Ziel sehr nahe. Eben weil die Vertices an den Kanten meines Referenzvertex eben nicht unbedingt die geographisch nächsten sein müssen, sondern auch, je nach Face, weiter weg sein könnten...