Autor Wątek: Optymalizacja pow  (Przeczytany 2627 razy)

Offline .Dexter.

  • Użytkownik

# Listopad 10, 2013, 14:30:00
Czy da się jakoś zoptymalizować pow dla wykładnika, który nie jest liczbą całkowitą? Robię sobie przekształcenie które wymaga obliczania w każdym obiegu pętli czegoś takiego:

float number = someCalculation();
float exponent = 1.f/2.2f;
float poweredNumber = powf(number,exponent);


Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xender

  • Użytkownik

# Listopad 10, 2013, 18:04:28
Jeśli to korekcja gamma koloru (wykładnik 1/2.2 widziałem tylko w tym kontekście), to:
0. Niepotrzebnie teoretyzujesz pytanie. ;)
1. Można to aproksymować np. wielomianem, bo dziedzina jest raczej wąska.
2. Przestrzeń sRGB (wykorzystywana w monitorach i często w formatach zapisu grafiki) nie jest dokładnie tym samym, co korekcja gamma (jest liniowa dla pewnego zakresu najmniejszych wartości - do doczytania w internecie).
3. API graficzne, jak DX czy GL mają wbudowaną korekcję sRGB, trzeba tylko kontrolować, gdzie jest właczona, a gdzie nie, żeby nie potraktować danych RGB jako sRGB lub odwrotnie (co prowadzi do błędów).

Chyba, że nie trafiłem z tą gammą, to sorry - wtedy można aproksymować potęgowanie np. wielomianami pod warunkiem, że dziedzina jest pewnym zakresem liczb - funkcja wykładnicza rośnie szybciej, niż jakakolwiek wielomianowa, więc poza tym zakresem szybko się rozjedzie.

Wreszcie - na pewno potrzebujesz tu optymalizacji?

A, jeszcze jedno - jeśli dane wejściowe dla "jakichś obliczeń" różnią się o jakiś stały krok w kolejnych iteracjach, to można spróbować znaleźć analitycznie rozwiązanie, które będzie polegało na obliczeniu wyniku dla pierwszej iteracji i pętli, która będzie brała wynik iteracji poprzedniej i liczyła kolejny wynik inkrementalnie - czasem robi się tak z sinusem i cosinusem.
« Ostatnia zmiana: Listopad 10, 2013, 18:09:12 wysłana przez Xender »

Offline .Dexter.

  • Użytkownik

# Listopad 10, 2013, 20:23:34
Blisko, robię przeliczanie przestrzeni kolorów RGB<->XYZ. http://www.brucelindbloom.com/Eqn_XYZ_to_RGB.html tutaj, gamma companding, dla sRGB przy punkcie jasności D65 gamma wynosi 2.2.

Myślałem już o lookup table, ale chyba to niemożliwe dlatego szukam czegoś innego. A to czy na pewno potrzebuję tej optymalizacji to tak. Przepatrzyłem cały algorytm, komentowałem bloki kodu i okazuje się, że to jest właśnie wąskie gardło. Bez tego potęgowania działa o wiele wiele szybciej.

Offline ackg

  • Użytkownik

# Listopad 10, 2013, 23:27:52
Lookup table może się okazać dobrym rozwiązaniem. Na szybko przykład:

Utworzenie tablicy:
const size_t srgbLookupSize = 10000;
std::array<float, srgbLookupSize> srgbLookup;
const float maxLookupIndex = static_cast<float>(srgbLookupSize - 1);
const float exponent = 1.0f / 2.2f;

for (size_t i = 0; i < srgbLookupSize; ++i) {
float number = static_cast<float>(i) / maxLookupIndex;
srgbLookup[i] = std::pow(number, exponent);
}

Odczyt:
if (number >= 1.0f) {
poweredNumber = 1.0f;
} else {
poweredNumber = srgbLookup[static_cast<size_t>(number * maxLookupIndex + 0.5f)];
}

Sprawdź czy będzie działać szybciej. Jak potrzebujesz naprawdę dużą dokładność, std::array trzeba by zamienić na std::vector.

Offline Xender

  • Użytkownik

  • +3
# Listopad 11, 2013, 00:07:06
Jeśli korzystasz z DX lub GL, to możesz spróbować konwersji automatycznej - po prostu wynik shadera (liniowe RGB, we float), przy rendertargecie sRGB zostanie przekonwertowany automatycznie.
Przy uploadzie/downloadzie/kopiowaniu tekstur trzeba doczytać - na wiki GL jest napisane, że glCopyTexImage2D na format sRGB nie konwertuje automatycznie (!).
Tutaj jest trochę o tym (szczególnie linki na dole): http://http.developer.nvidia.com/GPUGems3/gpugems3_ch24.html

Rozumiem, że liczysz na floatach? Może po prostu interpolacja wielomianem - da się (chyba nawet analitycznie) wyliczyć maksymalną niedokładność (i zrobić tak, aby była ona poniżej błędu zaokrąglenia).

Albo ew. lookup table + interpolacja wielomianowa pomiędzy N najbliższymi punktami (dla N=2 będzie to interpolacja liniowa). Nie pamiętam, czy lookup table + jakaś lepsza interpolacja niż liniowa miało swoją nazwę.

A, no i na tej stronie, co zalinkowałeś (i na Wiki również) jest napisane, że gamma=1/2.2 to w uproszczonej wersji, bez dolnego zakresu liniowego - we wzorze z nim jest już 1/2.4. Jestes pewien, że powinno być u Ciebie 1/2.2, a nie 1/2.4?

Ale jeśli jesteś w stanie przełknąć całkiem duży błąd (wykładni 1/2), to sqrt() może być szybsze.

A swoją drogą - nie lepiej/produktywniej/szybciej zamiast komentować bloki użyć profilera?

@up - beż żadnej interpolacji to nie będzie zbyt dokładne i zje o wiele więcej pamięci, niż wersja z interpolacją. A dobrze by było, aby zajmowało jej jak najmniej - cache. To 10000 wygląda mi całkiem podejrzanie.

Dorobienie do tego interpolacji liniowej jest raczej proste:
if (number >= 1.0f) {
poweredNumber = 1.0f;
} else {
float scaled_number = number * maxLookupIndex;
size_t idx = static_cast<size_t>();
float t = scaled_number - idx;
float p0 = srgbLookup[idx];
float p1 = srgbLookup[idx + 1];
poweredNumber = lerp(p0, p1, t);
}

Jakby interpolacja liniowa była za mało dokładna (rozdzielczość, za duży błąd bądź nieciągłosć pochodnej), to można interpolować wielomianowo (chyba spline'ami, np. Hermite'a czy Catmulla-Rom'a).

Offline ackg

  • Użytkownik

# Listopad 11, 2013, 01:45:20
Jeśli to ma być do wyświetlania real time, to faktycznie nie ma teraz sensu robić tego na CPU. Już nawet stosunkowo leciwe karty mają obsługę sprzętową sRGB, bez dodatkowego narzutu. Wystarczy wczytywać tekstury i tworzyć bufory jako sRGB. Jedynie problem może pojawić się przy automatycznym generowaniu mipmap, bo specyfikacja (OGL) nie precyzuje, czy skalowanie ma być z uwzględnieniem sRGB, ale z tego co wiem większość implementacji to uwzględnia (z glCopyTexImage2D nie wiem jak jest).

To 10000 rozmiar tablicy to przesadziłem. Nie wiem jaka to ma być dokładność, ale jeśli i tak na koniec jest to konwertowane do bajta, to już np. tablica o rozmiarze 1024 będzie miała 4 razy większy zakres niż kolor końcowy. Można też już po konwersji do bajta skorygować tablicą 256 elementową.

Co do tego czy gamma powinna być 2.2 czy 2.4 - zmienia się ona w zależności od natężenia koloru, dla zera wynosi 1, dla wartości maksymalnej wynosi 2.4, z medianą właśnie około 2.2. Dlatego przy takim przybliżonym obliczeniu wartość 2.2 jest prawidłowa dla całego zakresu. Dokładniejsze przekształcenie w zależności od natężenia (za wiki):
float linearToSRGB(float linear)
{
const float a = 0.055f;

if (linear <= 0.0f) {
return 0.0f;
}
if (linear >= 1.0f) {
return 1.0f;
}
if (linear <= 0.0031308f) {
return 12.92f * linear;
}
return (1.0f + a) * std::pow(linear, 1.0f / 2.4f) - a;
}

Offline .Dexter.

  • Użytkownik

# Listopad 11, 2013, 11:29:22
Jasne, że lepiej użyć profilera, ale moja metoda ma zaledwie kilka linijek, dlatego spróbowałem "na piechotę" ;)
Co do tego czy powinno być 2.2 czy 2.4 to jestem pewny że 2.2 wystarczy do moich zastosowań. Dzięki - posprawdzam to co napisaliście :)

Offline Xender

  • Użytkownik

  • +1
# Listopad 11, 2013, 16:38:09
To 10000 rozmiar tablicy to przesadziłem. Nie wiem jaka to ma być dokładność, ale jeśli i tak na koniec jest to konwertowane do bajta, to już np. tablica o rozmiarze 1024 będzie miała 4 razy większy zakres niż kolor końcowy. Można też już po konwersji do bajta skorygować tablicą 256 elementową.
To też nie do końca tak będzie - jedna pozycja tablicy odpowiada argumentowi funkcji, a nie wartości zwracanej - więc niezależnie od tego, że mamy 256 możliwych wartości zwracanych, nadal mamy <rozdzielczość floata od 0.0f do 1.0f> możliwych argumentów.

Można pewnie wyliczyć, ile próbek potrzebujemy dla danej funkcji, interpolacji, błędu i rozdzielczości wyjściowej, ale dla funkcji wykładniczej niekoniecznie będzie to proste "4x rozdzielczość wyniku to już spory zapas".

I tak nawet interpolacja liniowa powinna poprawić wynik / umożliwić zmniejszenie lookup table.

Offline voytech

  • Użytkownik

# Listopad 11, 2013, 21:58:08
Co do tego czy powinno być 2.2 czy 2.4 to jestem pewny że 2.2 wystarczy do moich zastosowań.

Oczywiście, że wystarczy. Pojedynczy pow(x, 2.2) to aproksymacja funkcji założonej z częścią liniową w dolnym zakresie i częścią nieliniową w górnym zakresie z wykładnikiem 2.4. Dokładne przekształcenia wyglądają tak:

(linear -> sRGB)  x < .04045 ? x/12.92 : pow((x+.055)/1.055, 2.4)          ≈       pow(x, 2.2)
(sRGB -> linear)  x < .0031308 ? x*12.92 : (1.055*pow(x,1/2.4)) -0.05       ≈       pow(x, 1/2.2)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +1
# Listopad 11, 2013, 22:58:00
Cytuj
Czy da się jakoś zoptymalizować pow dla wykładnika, który nie jest liczbą całkowitą?
Jak najbardziej. FPU nie posiada instrukcji "pow" i policzenie jej wymaga dość długiej sekwencji operacji, zwłaszcza jeżeli dodatkowo chce się uwzględniać przypadki szczególne (jak potęgowanie liczb ujemnych). Dlatego dobrym pomysłem może być napisanie tego akurat fragmentu w assemblerze.

Cytuj
Lookup table może się okazać dobrym rozwiązaniem.
Informacja dość nieaktualna. Dostęp do pamięci może być droższy niż sama funkcja.