Stippleowanie Voronoiego: Przekształcanie jasności w pole kropel

Przekształcanie jasności w gęstość kropel

Stippling -- renderowanie obrazu jako pole dyskretnych kropel -- jest techniką ręczną stosowaną od wieków w drukarstwie i ilustracji: kropki ułożone są gęsto w ciemnych obszarach, a rozproszone w jasnych, a oko odtwarza kontynuową tonację na podstawie czystej gęstości. Stippling z wagami Voronoi wprowadzony przez Adrian Secorda w 2002 roku automatyzuje ten proces, zamieniając go w problem optymalizacji punktów: dana jest obrazek docelowy i liczba punktów N; ułożone są te N punkty tak, aby ich lokalna gęstość odpowiadała jasności obrazka w każdym miejscu -- gęste gdzie obraz jest ciemny, rzadkie gdzie jest jasny (lub odwrotnie, dla estetyki jasne na czarnym).

Diagramy Voronoiego: każdemu punktowi własna terytorium

Diagram Voronoiego podzielić plane na regiony, jeden dla każdego punktu, tak że każdy punkt w danej regionie jest bliższy danego punktu niż do żadnego innego -- wyobraź sobie, że każdy punkt to sklep a każda region to obszar bliższy do tego sklepu niż do konkurencji. Po otrzymaniu zestawu rozproszonych punktów obliczenie ich diagramu Voronoiego jest dobrze zrozumiałym konstruktowaniem geometrycznym (algorytm Fortune'a linii przecinającej buduje go w O(n log n)); ciekawa część nie polega na samym diagramie, ale na tym, jak algorytm decyduje o położeniu punktów na początku.

Relaksacja Lloyd'a: przesuwanie każdego punktu w kierunku środka masy swojego pola Voronoiego

Algorytm Lloyd'a (1957, pierwotnie opracowany do kwantyzacji sygnału, niezależnie odkryty wielokrotnie od tamtej pory) to iteracyjny cykl tworzący równomierną, organiczną rozpraszanie. Rozpoczynając od losowego rozrzutu punktów:

powtarzaj aż do zbiegania się: oblicz diagram Voronoiego dla bieżących punktów dla każdego punktu p znajdź środek masy jego pola Voronoiego (względem ciężkości lokalnej obrazu, nie tylko powierzchni) przesuń p w kierunku tego zważonego środka masy # centroid pola Voronoiego spowoduje przyciągnięcie punktu w stronę miejsca, gdzie jest najwięcej „ciężkości” wewnątrz tego pola Zważenie połącza to z obrazem źródłowym: zamiast liczyć prosty geometryczny środek masy każdego pola, każdy piksel wewnątrz pola wkłada się do obliczenia środka masy proporcjonalnie do jego ciężkości (lub bardziej precyzyjnie, 1 odejmując jasność), więc piksele czarne liczą pełny udział a białe dla niczego. Punkt znajdujący się w polu Voronoiego, które przekracza teren ciemny, zostanie spowodowany przyciągnięciem do strony ciemnej tego pola; po wielokrotnej iteracji ten efekt przyciągania zagnieżdża się, przyciągając punkty do migracji z terenów jasnych w tereny ciemne, rozmywając miejsca, gdzie obraz jest jasny i skupiając tam, gdzie obraz jest ciemny – dokładnie wzorzec gęstości, który potrzebuje rysunek stipulacyjny.

repeat until converged:
    compute the Voronoi diagram of the current points
    for each point p, find the centroid of its Voronoi cell
        (weighted by local image darkness, not plain area)
    move p toward that weighted centroid
# a cell's centroid pulls its point toward where the "mass" inside that cell is concentrated

Dlaczego relaksacja sprawia, że wzór wygląda organicznie, a nie jak siatkę

Proste losowe umieszczenie N punktów ważonych jasnością powoduje wynik poprawnie ważony, ale widocznie szumowy i grubej – niektóre regiony przypadkowo dostaną zbyt wiele punktów blisko siebie, a inne zbyt mało. Lloyd's relaksacja naprawia to, ponieważ diagram Voronoiego konwergentny ma określone, dowodzone właściwości regularności: sąsiednie komórki tarczą się w kierunku podobnej wielkości pola (po uwzględnieniu wag gęstości), co naciska punkty na lokalnie bliskie równomierną odstępstwa w każdym regionie o przybliżonej stałej jasności. Wynik czyta się jako organicznie równomiernie rozłożony – jak regularność widoczna w pakowaniu sześciokątnym, ale perturbowany wystarczająco przez zmienną gęstość podłoża, aby nadal wyglądać naturalnie, a nie mechanicznie grudkowaty. Kilka iteracji (10-30) jest zwykle wystarczające do widocznego osiągnięcia równowagi; więcej iteracji prowadzi do ograniczonego poprawienia, gdy punkty zbliżają się do ustalonej punktu relaksacji.

Wybór funkcji gęstości

Nie ma żadnych wymogów w algoritmie, które by wymagały, aby pole wagowe pochodziło z fotografii. Podanie mu funkcji matematycznej zamiast tego -- spirali, zestaw concentrycznych fal, pole ucieczki zbioru Mandelbrota lub gęstość symulowanego klasteru gwiazdowego -- powoduje to samo organiczne rozmieszczenie punktów sterowane przez własne wznoszenia i opadania tej funkcji zamiast ciemności obrazu, co jest przyczyną tego, dlaczego ta technika doubles as narzędziem do generowania sztucznej sztuki: oznaczenie wizualne relaksacji Lloyd'a (lokalnie równomiernego, globalnie dopasowanego do gęstości rozmieszczenia) jest takie samo niezależnie od tego, czy gęstość pochodzi z fotografii czy z równania.

koszt i zbieżność w praktyce

Każda iteracja wymaga pełnego odświeżenia diagramu Voronoiego (O(n log n) przy właściwym konstrukcji linii przetwarzania, choć wiele praktycznych implementacji aproksymuje to szybciej na siatkach pikseli, rastrowując bezpośrednio mapę najbliższego punktu opartą na odległości) plus jednego przejścia z wagowym srediistem na każdy komórkowy obszar, O(pikseli) w sumie na każdą iterację, ponieważ każdy piksel jest odwiedzony raz do akumulacji we właściwej komórce. Dla interaktywnych płaszczyzn z kilkuset punktami, aproksymowany diagram Voronoiego obliczany w każdym klatku na siatkach pikseli jest wystarczająco ekonomiczny do relaksacji w czasie rzeczywistym w przeglądarce, co pozwala na animację widoczne przemieszczanie i osiąganie równowagi punktów w czasie rzeczywistym zamiast pokazywania tylko jednej końcowej klatki.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Stippling & Pointillism i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.