Jak programiści grafiki radzą sobie z renderowaniem wierzchołków, które nie zmieniają obrazu?

10

Tytuł jest więc trochę niezręczny. Dam trochę tła, a następnie zadam pytanie.

Tło : Pracuję jako programista aplikacji internetowych GIS , ale w wolnym czasie bawię się renderowaniem map i ulepszaniem formatów wymiany danych. Pracuję tylko w przestrzeni 2D.

Ciekawym problemem, z jakim się spotkałem, jest to, że podczas renderowania wielokąta w małej skali (oddalone), wiele wierzchołków jest zbędnych. Ekstremalnym przypadkiem byłoby posiadanie wielokąta z 500 000 wierzchołków, który zajmuje tylko jeden piksel. Jeśli wysyłasz te dane do przeglądarki, warto pominąć ~ 499,999 z tych wierzchołków. Jednym ze sposobów na osiągnięcie tego jest renderowanie obrazu na serwerze i wysyłanie go jako PNG: voila, to jest punkt. Czasami jednak chcemy, aby dane były wysyłane do przeglądarki, gdzie mogą być renderowane za pomocą SVG (lub canvas lub webgl), aby mogły być interaktywne.

Problem : Okazuje się, że przy użyciu nowoczesnych zestawów danych geograficznych bardzo łatwo jest przeciążać możliwości renderowania SVG. Starając się poradzić sobie z tymi ograniczeniami, próbuję dowiedzieć się, jak wizualnie bezstratnie zmniejszyć zestaw danych dla danej skali i zasięgu mapy (i, jeśli to konieczne, dla znanej szerokości i wysokości pikseli mapy).

Ogromnie zmniejszyłem rozmiar danych, korzystając tylko z algorytmu Douglasa-Peuckera i wierzę, że udało mi się go uzyskać, aby wielokąty były wierne jednemu pikselowi. Niestety Douglas-Peucker nie zachowuje topologii, więc zmienił sposób renderowania granic między wielokątami. Nie mogłem łatwo znaleźć innych algorytmów do wypróbowania i dostosowania się do celu, ale nie mam dużego tła CS / algorytmu i może ich nie rozpoznam, jeśli je zobaczę.

canisrufus
źródło
1
Google za „Topologicznie spójny Douglas-Peucker”, a znajdziesz linki do streszczeń niektórych artykułów. Niestety musisz zapłacić za pełne artykuły, które widziałem.
Doc Brown
@DocBrown Dziękujemy! Questia wydaje się nawet mieć darmowy okres próbny.
canisrufus

Odpowiedzi:

3

To czego szukasz 2d level of detail algorithms.

Jest wiele udokumentowanych na ten temat w Google, jeśli szukasz tych wyróżnionych terminów.

To pytanie dotyczące przepływu stosu zawiera informacje, których szukasz w renderowaniu 2D na poziomie szczegółowości.

Społeczność
źródło
+1 za bardzo odpowiednie słownictwo. Wygląda na to, że faktycznie stosuję podejście oparte na poziomie szczegółowości, ale potrzebuję algorytmu uproszczenia wielokąta, który odpowiada moim potrzebom. Znaleziono fajny przegląd dla tych 3d. Wydaje mi się, że opracowałem odpowiednią strategię uproszczenia, chociaż nie miałem czasu jej kodować.
canisrufus