Odczyt i przetwarzanie chmury punktów

Witam,

problem jest taki:

-dane wejściowe są w pliku ascii, format: X, Y, Z
plik waży ok. 14GB
ilość współrzędnych 350M do 400M punktów, współrzędne są zapisane w typie float.

-wyświetlanie w OpenGL C#

Z uwagi że do tej pory nie miałem styczności z tak dużą ilością danych zastanawiam się jak można by podejść do problemów, których na tą chwilę widzę dwa:

1. odczyt z ASCII, aktualnie robię testy i okaże się co udało mi się osiągnąć,
2. wyświetlenie danych, to poważniejszy i główny problem.
   Nie ma możliwości ażeby wyświetlić wszystkie dane na raz (mam tutaj na myśli wyświetlenie i obracanie takim modelem),
   potrzebny jest jakiś mechanizm który w zależności od zoom-a jaki zostanie wybrany odpowiednio wyświetlił wcześniej posortowane/przygotowane dane.
   Myślę o czymś takim:

   • jeśli będzie zadane maksymalne powiększenie to wiadomo, wyświetlam wszystkie punkty w zadanym zakresie widocznym w oknie.

   • jeśli będę zmniejszał powiększenie to należy usuwać powiedzmy 50% (konkretnie ile, będzie można dobrać doświadczalnie) punktów przy każdym pomniejszeniu,
     algorytm: klastrowanie k-means?
     pytanie jak robić takie odsiewanie, na płaszczyźnie wiadomo a w przestrzeni 3D?

     Pewnie są jakieś gotowe rozwiązania/biblioteki tych problemów, proszę o jakieś sugestie bo nie chciałbym wymyślać koła na nowo.

Pozdrawiam.

Czy jest to jakiś problem akademicki? Co to za dane? Ja bym najpierw pomyślał na odfiltrowaniu części danych. bo to będzie nie do ogarnięcia. Nie jest problem trywialny.
Ale 14gb to jest jakieś pierdyliady takich punktów. Na jakim komputerze chcesz to robić? Tam potrzeba troszkę tego ramu.

Nie jest to problem teoretyczny ale konkretne zadanie.
Mój sprzęt to:
Procesor: Core(TM) i7-1165G7 @ 2.80GHz
Ram: 32G, win11

Wiem że muszę to jakoś przesiać, tylko nie wiem jak do tego podejść.
Ktoś doświadczony w takim temacie chyba się znajdzie?

S4t napisał(a):

Czy jest to jakiś problem akademicki? Co to za dane? Ja bym najpierw pomyślał na odfiltrowaniu części danych. bo to będzie nie do ogarnięcia. Nie jest problem trywialny.
Ale 14gb to jest jakieś pierdyliady takich punktów. Na jakim komputerze chcesz to robić? Tam potrzeba troszkę tego ramu.

+1

miliard punktów to w ogóle nie ma sensu wyświetlać na medium ekranowym (drukarce też nie). To będzie cały biały ekran / czarna kartka
Więc podnoszę pogląd @S4t : co to za dane, jakie "okna" z nich chcesz wyświetlac itd...

14g puntów bym trzymał w jakiejś szybkiej strukturze ram-dysk - jaka, to zależy od dziedziny (selekcja wg dziedziny / wymiaru 1d, 2d, 3d itd), a podwijał rękawki i zabierał się do pracy nad podzbiorem.

Jak ktoś miał drukować w Windows 16 bit, miał Petzolda w ręce, to mentalnie mógł się przygotować na drukowanie "bandami"

Janko M. napisał(a):

Wiem że muszę to jakoś przesiać, tylko nie wiem jak do tego podejść.
Ktoś doświadczony w takim temacie chyba się znajdzie?

Jak na razie, to ukrywasz naturę tych danych

To są dane typu punkty ze skanu 3D/LIDAR-a, czegoś takiego? Możesz spróbować zobaczyć jak to robi CloudCompare (http://cloudcompare.org/), który działa dość wydajnie dla tego typu danych, i większych, aczkolwiek jest napisany w C++, ale w OpenGL.

Obiektem skanowania są drewniane belki.
Użyłem CloudCompare, wczytanie danych trwało u mnie 9min, później sama wizualizacja działała bardzo sprawnie.
Myślę że wstępnie należałoby odfiltrować jakoś dane wejściowe, stworzyć nowy mniejszy plik i dopiero później zabierać się za wyświetlanie.
Samo filtrowanie nie musi być w C#, mogło by to być narzędzie używane w celu jednorazowego przetworzenia danych źródłowych.

@Janko M.:

A te belki w jaki sposób tworzą zbiorowość, wg jakiej zasady, co je łączy / wyklucza? Bo przynajmniej na mój poranny intelekt, to niewiele rozjaśniłeś.
Co tu wizualizować?

Co to belka, sztuk jeden, to rozumiem.

Jeśli dane są równomiernie rozłożone to możesz rozważyć zastosowanie spatial hashingu, jest to chyba najprostszy sposób dzielenia przestrzeni 3d na mniejsze części.

ZrobieDobrze napisał(a):

@Janko M.:

Co to belka, sztuk jeden, to rozumiem.

Jedna belka == jeden plik ze współrzędnymi.
Belka jak to belka, posiada pęknięcia promieniowe, sęki, kształt prostopadłościenny, mam to co wychodzi z tartaku.
Nie chodzi o jakąś super dokładność przy wyświetlaniu, żaden chirurg zdalnie nie będzie robił na takim obiekcie operacji.
Użytkownik ma mieć możliwość zobaczenia obiektu, taki bajer prawdę powiedziawszy.

Janko M. napisał(a):

ZrobieDobrze napisał(a):

@Janko M.:

Co to belka, sztuk jeden, to rozumiem.

Jedna belka == jeden plik ze współrzędnymi.
Belka jak to belka, posiada pęknięcia promieniowe, sęki, kształt prostopadłościenny, mam to co wychodzi z tartaku.
Nie chodzi o jakąś super dokładność przy wyświetlaniu, żaden chirurg zdalnie nie będzie robił na takim obiekcie operacji.
Użytkownik ma mieć możliwość zobaczenia obiektu, taki bajer prawdę powiedziawszy.

Czyli masz skan o ZNACZNIE większej rozdzielczości, niż faktycznie potrzebujesz.

Na próbę - podejście naiwne:

1. Spróbuj odrzucić co drugi punkt i sprawdź, czy wynik był istotnie gorszy (prawdopodobnie nie będzie).
2. Spróbuj brać pod uwagę tylko co dziesiąty punkt, co setny i tak dalej - i sprawdź, kiedy wynik przestanie być zadowalający.

To tyle, jeżeli chodzi o podejście naiwne.
Nieco bardziej rozsądnie - zakrąglić współrzędne punktów do jakiejś rozsądnej precyzji (do pełnych mm? do dziesiątych mm? to już zależy od potrzeb i od realiów. Być może poszczególne osie trzeba zakrąglać z różną precyzją?), pogrupować i odrzucić duplikaty (których pewnie będzie wiele). Powierzchnia belki 10x10x200cm zeskanowana z precyzją 1mm to 800 tysięcy punktów - wobec 400 milionów, które masz obecnie.

Jeśli trochę znasz C++ możesz poeksperymentować z pcl https://pcl.readthedocs.io/en/latest/voxel_grid.html
A nawet jak nie znasz to warto poczytać i obejrzeć filmiki o tym jakie mają funkcje/sposoby na przetwarzanie chmur punktów.

Wykonałem odfiltrowanie polegające na tym że uwzględniłem co N-ty punkt.
Wszystko byłoby pięknie gdyby nie pęknięcia, tam po takim odsianiu efekt nie jest dobry.
Pozostaje więc tylko jakoś rozwiązać ten problem.
Póki co czytam o pcl.

Janko M. napisał(a):

Wykonałem odfiltrowanie polegające na tym że uwzględniłem co N-ty punkt.
Wszystko byłoby pięknie gdyby nie pęknięcia, tam po takim odsianiu efekt nie jest dobry.
Pozostaje więc tylko jakoś rozwiązać ten problem.
Póki co czytam o pcl.

Chyba odsiewanie co N-ty jest zbyt naiwne. Na pewno możesz odsiać punkty, które mają taką samą wartość i zostawić tylko graniczne

Moze zrobic teselacje, kontrola zlozonosci pozwoli okreslic ile docelowo ma byc wierzcholkow wyjsciowo.