03.03.2021 12:23
[#1]
[C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
Cześć,
zastanawiam się czy jest możliwe rozwiązanie pewnego problemu.
W skrócie: uzyskać optymalną wydajność wypełniając bufor nie tylko linia po lini ale i kolumna po kolumnie.
Poniżej opis:
Dany jest bufor graficzny (tzn. z przeznaczeniem do trzymania bitmapy)
Problemu nie ma w przypadku wypełniania go poziomo linia po linii, gdyż jest to przypadek 'cache friendly', czyli najlepszy, np. raycastowanie podłogi i sufitu:
Różnica w wydajności pojawia się, gdy taki bufor chcemy uzupełnić pionowo czyli kolumna po kolumnie, np. raycastowanie ścian które tak się właśnie odbywa, tj.
Pytanie jakie się pojawia, to czy można jakoś połaczyć wydajne uzupełnianie linia po lini i kolumna po kolumnie.
Z paru testów, które przeprowadziłem wyszło że jeżeli przedstawi się bufor jako dwuwymiarowy tj. bufor_2**
wypełnianie kolumna po kolumnie jest nawet szybsze niż linia po linii w jednowymiarowym - ale wtedy jest na odwrót czyli wypełnieni takiego dwuwymiarowego bufora linia po lini będzie mało wydajne.
Rozwiązania o których myślałem:
- obrócić bufor o 90 stopni, niestety to zabiera zbyt dużo czasu, przynajmniej algorytmami które sprawdzałem,
chyba że istnieje jakiś mega szybki sposób N(1)
- jakieś przemapowanie bufora tak żeby jakaś tablica zawierała wskażniki do kolejnych pixeli w kolumnie, ale to chyba też nie bedzie 'cache friendly' albo nawet gorzej - nie sprawdzalem w każdym razie
zastanawiam się czy jest możliwe rozwiązanie pewnego problemu.
W skrócie: uzyskać optymalną wydajność wypełniając bufor nie tylko linia po lini ale i kolumna po kolumnie.
Poniżej opis:
Dany jest bufor graficzny (tzn. z przeznaczeniem do trzymania bitmapy)
#define WIDTH 320
#define HEIGHT 256
typedef struct
{
unsigned char r,g,b;
}sRGB;
sRGB* bufor_1;
main()
{
bufor_1 = (sRGB*)malloc(WIDTH*HEIGHT*sizeof(sRGB));
}Problemu nie ma w przypadku wypełniania go poziomo linia po linii, gdyż jest to przypadek 'cache friendly', czyli najlepszy, np. raycastowanie podłogi i sufitu:
main()
{
bufor_1 = (sRGB*)malloc(WIDTH*HEIGHT*sizeof(sRGB));
for (int y = 0; y < HEIGHT; ++y)
{
for (int x = 0; x < WIDTH; ++x)
{
bufor_1[x+y*WIDTH].r = 100;
}
}
}Różnica w wydajności pojawia się, gdy taki bufor chcemy uzupełnić pionowo czyli kolumna po kolumnie, np. raycastowanie ścian które tak się właśnie odbywa, tj.
main()
{
bufor_1 = (sRGB*)malloc(WIDTH*HEIGHT*sizeof(sRGB));
for (int x = 0; x < WIDTH; ++x)
{
for (int y = 0; y < HEIGHT; ++y)
{
bufor_1[x+y*WIDTH].r = 100;
}
}
}Pytanie jakie się pojawia, to czy można jakoś połaczyć wydajne uzupełnianie linia po lini i kolumna po kolumnie.
Z paru testów, które przeprowadziłem wyszło że jeżeli przedstawi się bufor jako dwuwymiarowy tj. bufor_2**
wypełnianie kolumna po kolumnie jest nawet szybsze niż linia po linii w jednowymiarowym - ale wtedy jest na odwrót czyli wypełnieni takiego dwuwymiarowego bufora linia po lini będzie mało wydajne.
Rozwiązania o których myślałem:
- obrócić bufor o 90 stopni, niestety to zabiera zbyt dużo czasu, przynajmniej algorytmami które sprawdzałem,
chyba że istnieje jakiś mega szybki sposób N(1)
- jakieś przemapowanie bufora tak żeby jakaś tablica zawierała wskażniki do kolejnych pixeli w kolumnie, ale to chyba też nie bedzie 'cache friendly' albo nawet gorzej - nie sprawdzalem w każdym razie
03.03.2021 12:37
[#2]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
@mateusz_s, post #1
Tak naprawde to zapisuj grafike w unsigned long = 32 bit, czyli
ULONG *data = malloc( WIDTH*HEIGHT*4);
A potem r,g,b to [0] [1] [2] i 3ke zostawiasz. Oczywiscie "zmarnuje" to troche pamieci ale powinno byc szybsze.
Z drugiej strony odnosnie Twojego kodu to dalbym wczesniej:
int delw = WIDTH *sizeof(sRGB);
for( int x=0; x < WIDTH ; x++ )
{
struct sRGB *p = x*WIDTH;
for( int y=0; y <HEIGHT; y++ )
{
p->r = 100;
p+=delw;
Cos w ten "desen".
Co do wypelnienia poziomego to nigdy nie bedzie tak szybko
ULONG *data = malloc( WIDTH*HEIGHT*4);
A potem r,g,b to [0] [1] [2] i 3ke zostawiasz. Oczywiscie "zmarnuje" to troche pamieci ale powinno byc szybsze.
Z drugiej strony odnosnie Twojego kodu to dalbym wczesniej:
int delw = WIDTH *sizeof(sRGB);
for( int x=0; x < WIDTH ; x++ )
{
struct sRGB *p = x*WIDTH;
for( int y=0; y <HEIGHT; y++ )
{
p->r = 100;
p+=delw;
Cos w ten "desen".
Co do wypelnienia poziomego to nigdy nie bedzie tak szybko
03.03.2021 12:39
[#3]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
@mateusz_s, post #1
Jeżeli chcesz wypełniać w pionie to po prostu musisz wypełniać jednocześnie n-kolumn (n dostosowane do długości linii cache). Możesz też rysować np n kolumn do obróconego bufora a potem przerzucić odwracając. Przy niskiej rozdzielczości jest jakaś szansa że dane będą nawet jeszcze w cache.
Obrót bufora o 90 stopni to prosta transpozycja. Bez problemu można to zrobić w liniowym czasie. Trzeba tylko uważać na dostępy do pamięci i najlepiej zrobić to blokami np 16x16 pikseli (transpozycja pikseli w bloku a potem transpozycja położenia bloku).
Ostatnia aktualizacja: 03.03.2021 12:39:55 przez kiero
Obrót bufora o 90 stopni to prosta transpozycja. Bez problemu można to zrobić w liniowym czasie. Trzeba tylko uważać na dostępy do pamięci i najlepiej zrobić to blokami np 16x16 pikseli (transpozycja pikseli w bloku a potem transpozycja położenia bloku).
Ostatnia aktualizacja: 03.03.2021 12:39:55 przez kiero
03.03.2021 13:13
[#4]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
@stefkos, post #2
A odnośnie tego co napisałeś o trzymaniu kolorów jako 4 bajty rgba,
tak zgadzam się, ale właśnie jak to się będzie miało, jeśli aplikacja będzie działać w trybie
RTG 24 bity? Trzeba wtedy wybrać tryb 32? Nie sprawdzałem jeszcze na Amidze, bo na razie koduje na PC, dopero potem bede portował.. czy to bez różnicy? Bo wtedy jesli tryb jest 24 bity to chyba hardware spodziewa się że kolejne kolory beda zajmować kolejne 3 bajty
tak zgadzam się, ale właśnie jak to się będzie miało, jeśli aplikacja będzie działać w trybie
RTG 24 bity? Trzeba wtedy wybrać tryb 32? Nie sprawdzałem jeszcze na Amidze, bo na razie koduje na PC, dopero potem bede portował.. czy to bez różnicy? Bo wtedy jesli tryb jest 24 bity to chyba hardware spodziewa się że kolejne kolory beda zajmować kolejne 3 bajty
03.03.2021 13:15
[#5]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
@kiero, post #3
znasz może jakiś algorytm? Czy poniższy link to jest to o czym mówisz?
https://stackoverflow.com/questions/848025/rotating-bitmaps-in-code
tutaj gość pokazuje różnice w obrocie uzywajac blokow 1, 8 i 16..
nie jestem pewny czy taki obrót bedzie możliwy 50 razy na sekunde a nwet jesli to czy to
skompensuje róznice miedzy wypelnianiem pionowym
https://stackoverflow.com/questions/848025/rotating-bitmaps-in-code
tutaj gość pokazuje różnice w obrocie uzywajac blokow 1, 8 i 16..
nie jestem pewny czy taki obrót bedzie możliwy 50 razy na sekunde a nwet jesli to czy to
skompensuje róznice miedzy wypelnianiem pionowym
03.03.2021 13:16
[#6]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.
03.03.2021 17:37
[#7]
Re: [C, C++] Bufor graficzny - uzupełnianie poziome i pionowe, ogólny problem.