Trojúhelník - optimalizace – C / C++ – Fórum – Programujte.com

ahoj,

prosím, někdo zkušený, zběhlý.. potřeboval bych poradit, jak zrychlit vykreslování trojůhelníků!
(nechci slyšet nic o OpenGL apod., je to jen hračka)

každý trojúhelník je dán třemi body X, Y, Z, a je mu přiřazena barva.
trojůhelník je kreslen na obrazovku na X,Y, s přidělenou barvou (která je stínovaná podle Z)
zároveň se do tabulky ZTABLE zapisují hodnoty Z pro každé X,Y, to je z toho důvodu, aby se na obrazovce objevil pouze ten trojúhelník, který je nejblíž (má nejvyšší Z)

tadyta hračka mi běží akt. na 45 FPS (starodávnej semptron 2600 z roku 05), složitější hračky ale už dost trpí právě na ty přepočty..

#include <SDL/SDL.h>
#include <stdlib.h>
#include <ctime>
#include <cmath>
                          
SDL_Surface *screen;
int time0, time1, FPS, cnt=0;
char nadpis[32];

int ztable[800*600];

void triangl(int x1, int y1, int z1,
             int x2, int y2, int z2, 
             int x3, int y3, int z3,
             int rr, int gg, int bb){
  Uint16 *pix;
  Uint16 *pxl;
  Uint16 pit;
  int x,y,vy1,vy2;
  int vz1,vz2,z,c,r,g,b;

  pxl=(Uint16 *)screen->pixels;
  pit=screen->pitch/2;

  if (x3<x1) {
    x = x1; x1 = x3; x3 = x;
    y = y1; y1 = y3; y3 = y;
    z = z1; z1 = z3; z3 = z;
  }
  if (x2<x1) {
    x = x1; x1 = x2; x2 = x;
    y = y1; y1 = y2; y2 = y;
    z = z1; z1 = z2; z2 = z;
  }
  if (x3<x2) {
    x = x2; x2 = x3; x3 = x;
    y = y2; y2 = y3; y3 = y;
    z = z2; z2 = z3; z3 = z;
  }

  for (x=x1; x<x2; x++) {
    vy1 =int(float(x-x1)/(x1-x2)*(y1-y2))+y1;
    vy2 =int(float(x-x1)/(x1-x3)*(y1-y3))+y1;
    vz1 =int(float(x-x1)/(x1-x2)*(z1-z2))+z1;
    vz2 =int(float(x-x1)/(x1-x3)*(z1-z3))+z1;
    if (vy1>vy2) {
      y = vy1; vy1 = vy2; vy2 = y;
      z = vz1; vz1 = vz2; vz2 = z;
    }
    for (y=vy1; y<=vy2; y++) {
      pix = pxl + y*pit + x;
      z = int(float(y-vy1)/(vy1-vy2)*(vz1-vz2))+vz1;
      if (ztable[y*800+x]<z) {
        ztable[y*800+x]=z;
        r =  rr*z/1024;
        g =  gg*z/1024;
        b =  bb*z/1024;
        c = b + (g<<5) + (r<<11);
        *pix=c; }
    }
  }
  if (x2==x3) {
    if (y2>y3) {
      y = y2; y2 = y3; y3 = y;
      z = z2; z2 = z3; z3 = z; }
    for (y=y2; y<=y3; y++) {  
      z =int(float(y-y2)/(y2-y3)*(z2-z3))+z2;
      pix = pxl + y*pit + x;
      if (ztable[y*800+x]<z) {
        ztable[y*800+x]=z;
        r =  rr*z/1024;
        g =  gg*z/1024;
        b =  bb*z/1024;
        c = b + (g<<5) + (r<<11);
        *pix=c; }
    }
  } else
  for (x=x2; x<=x3; x++) {
    vy1 =int(float(x-x2)/(x2-x3)*(y2-y3))+y2;
    vy2 =int(float(x-x1)/(x1-x3)*(y1-y3))+y1;
    vz1 =int(float(x-x2)/(x2-x3)*(z2-z3))+z2;
    vz2 =int(float(x-x1)/(x1-x3)*(z1-z3))+z1;
    if (vy1>vy2) {
      y = vy1; vy1 = vy2; vy2 = y;
      z = vz1; vz1 = vz2; vz2 = z;
    }
    for (y=vy1; y<=vy2; y++) {
      pix = pxl + y*pit + x;
      z =int(float(y-vy1)/(vy1-vy2)*(vz1-vz2))+vz1;
      if (ztable[y*800+x]<z) {
        ztable[y*800+x]=z;
        r =  rr*z/1024;
        g =  gg*z/1024;
        b =  bb*z/1024;
        c = b + (g<<5) + (r<<11);
        *pix=c; }
    }
  }
}

class tbl {
          public:
          int SIN;
          int COS;
          void reset(int n);}; 
        
void tbl::reset(int n){
  SIN = int( sin( double(n)*M_PI/180 ) * 16384);
  COS = int( cos( double(n)*M_PI/180 ) * 16384);
}

tbl t[360];

class bod {
            public:
            int x,y,z; 
            void reset(int rx, int ry, int rz, int size);
            void rotate(int xa, int ya, int za);
            void rotate(bod  b, int xa, int ya, int za);
            void morph(bod sc, bod tg, int step, int steps);
            int xx,yy,zz,ss;
            int nx,ny,nz;
            int tx,ty,tz;
           };

void bod::reset(int rx, int ry, int rz, int size){
  xx = rx; yy = ry; zz = rz; ss=size;
  z = nz+2048;
  if (z<0) z=1;
  x = (nx*ss/z);
  y = (ny*ss/z);
  z = 512-(nz/2);
  if (z<0) z=0;
  if (z>511) z=511;
}

void bod::rotate(int xa, int ya, int za){
  // podle osy x
  ty = (yy * t[xa].COS - zz * t[xa].SIN) >> 14;
  tz = (zz * t[xa].COS + yy * t[xa].SIN) >> 14;
  // podle osy y
  tx = (xx * t[ya].COS - tz * t[ya].SIN) >> 14; 
  nz = (tz * t[ya].COS + xx * t[ya].SIN) >> 14; 
  // podle osy z
  nx = (tx * t[za].COS - ty * t[za].SIN) >> 14; 
  ny = (ty * t[za].COS + tx * t[za].SIN) >> 14; 
  z = nz+2048;
  if (z<0) z=1;
  x = (nx*ss/z);
  y = (ny*ss/z);
  z = 512-(nz);
  if (z<0) z=0;
  if (z>1023) z=1023;
};

void bod::rotate(bod b, int xa, int ya, int za){
  rotate(xa, ya, za);
  b.reset(nx, ny, nz, ss);
}

void bod::morph (bod sc, bod tg, int step, int steps) {
  if (step<0) return;
  if (step>steps) return;
  xx = sc.xx+((tg.xx-sc.xx) * step / steps);
  yy = sc.yy+((tg.yy-sc.yy) * step / steps);
  zz = sc.zz+((tg.zz-sc.zz) * step / steps);
  ss = sc.ss+((tg.ss-sc.ss) * step / steps);
  reset(xx,yy,zz,ss);
}

bod krychle[8];
int ctverec[6][4]={{0,1,2,3},{0,1,4,5},{0,2,4,6},{2,3,6,7},{1,3,5,7},{4,5,6,7}};
int r[6]={31,0,31,31,0,0};
int g[6]={63,63,0,0,63,0};
int b[6]={0,31,31,0,0,31};

int main(int argc, char *argv[]){
  int n;
  int x1,y1,z1;
  int x2,y2,z2;
  int x3,y3,z3;
  int x4,y4,z4;
  int r1,g1,b1;
  int r2,g2,b2;
  int r3,g3,b3;
  int r4,g4,b4;
  int xa=0,ya=0,za=0;

  srand(time(0));

  for (n=0; n<360; n++) t[n].reset(n);

  for (n=0; n<12; n++) krychle[n].reset(512-1024*(n%2), 512-1024*((n/2)%2), 512-1024*((n/4)%4), 500);

  Uint8* keys; 
  srand(time(0));
  if( SDL_Init(SDL_INIT_VIDEO) < 0 ){
    printf("Inicializace SDL se nezdařila: %s", SDL_GetError());
    exit(1);
  }

  atexit(SDL_Quit);
  screen = SDL_SetVideoMode(800, 600, 16, SDL_SWSURFACE);//|SDL_FULLSCREEN);

  if ( screen == NULL ){
    printf("Vytvoření okna se nezdařilo: %s", SDL_GetError());
    exit(1);
  }
  SDL_WM_SetCaption("3D",  NULL);  

  bool hraj = true;
  SDL_Event event;
  Uint16 *pix;
  Uint16 *pxl;
  Uint16 pit;
  pxl=(Uint16 *)screen->pixels;
  pit=screen->pitch/2;
  while(hraj){                     
    time0=SDL_GetTicks();
    while(SDL_PollEvent(&event)){
      if(event.type == SDL_QUIT) hraj = false;
      if(event.type == SDL_KEYUP){
        if(event.key.keysym.sym == SDLK_ESCAPE) hraj = false; }
      
  }
    SDL_FillRect(screen, NULL, 0);
    for (n=0; n<800*600; n++)
      ztable[n]=0;
    for (n=0; n<8; n++)  
      krychle[n].rotate(xa,ya,za);
    for (n=0; n<6; n++){  
      y1=(300+krychle[ctverec[n][0]].y);
      x1=(400+krychle[ctverec[n][0]].x);
      z1=(krychle[ctverec[n][0]].z);

      y2=(300+krychle[ctverec[n][1]].y);
      x2=(400+krychle[ctverec[n][1]].x);
      z2=(krychle[ctverec[n][1]].z);

      y3=(300+krychle[ctverec[n][2]].y);
      x3=(400+krychle[ctverec[n][2]].x);
      z3=(krychle[ctverec[n][2]].z);

      y4=(300+krychle[ctverec[n][3]].y);
      x4=(400+krychle[ctverec[n][3]].x);
      z4=(krychle[ctverec[n][3]].z);

      triangl(x1,y1,z1,x2,y2,z2,x3,y3,z3,r[n],g[n],b[n]);
      triangl(x2,y2,z2,x3,y3,z3,x4,y4,z4,r[n],g[n],b[n]);
    }
    
    xa = (xa + 2)%360;
    ya = (ya + 1)%360;
    za = (za + 1)%360;
    SDL_Flip(screen); 
    time1=SDL_GetTicks();
    FPS+=1000/(time1-time0);
    cnt++;
    if ((cnt%10)==0) {
      cnt=0;
      FPS/=10;
      sprintf(nadpis,"3D, %i FPS",FPS);
      SDL_WM_SetCaption(nadpis,  NULL);
      FPS=0;
    }
  }
}

díík!

joo ještě jsem zapomněl, je to dělaný do 16BPP, odpovídá tomu i 16bitový zápis barev.. 

teda, to je ostuda, fakt...... nikdo nic jo? hm,, no už jsem si sobě splodil rychlejší vykreslovač sám,, zrychlení více než 2×

Uint16 *pix;
Uint16 *pxl;
Uint16 pit;


void line (int x1, int x2, int y, int z1, int z2, int rr, int gg, int bb){
  int x,z,r,g,b;
  if (x1>x2) {
    x=x1; x1=x2; x2=x;
    z=z1; z1=z2; z2=z;
  }
  pix=pxl + y*pit + x1;
  if (ztable[y*800+x1]<z1) {
    ztable[y*800+x1]=z1;
    *pix=((bb*z1)>>20) + (((gg*z1)>>20)<<5) + (((rr*z1)>>20)<<11);
  }
  if (x1==x2) return;
  z=(z1-z2)/(x1-x2);
  for (x=x1+1; x<=x2; x++){
    z1+=z;
    pix++;
    if (ztable[y*800+x]<z1) {
      ztable[y*800+x]=z1;
      *pix=((bb*z1)>>20) + (((gg*z1)>>20)<<5) + (((rr*z1)>>20)<<11);
    }
  }

}

void triangl(int x1, int y1, int z1,
             int x2, int y2, int z2, 
             int x3, int y3, int z3,
             int rr, int gg, int bb){
  int x,y,z;
  int kx1, kx2, mx1, mx2; 
  int kz1, kz2, mz1, mz2;

  if (y3<y1) {
    x = x1; x1 = x3; x3 = x;
    y = y1; y1 = y3; y3 = y;
    z = z1; z1 = z3; z3 = z;
  }
  if (y2<y1) {
    x = x1; x1 = x2; x2 = x;
    y = y1; y1 = y2; y2 = y;
    z = z1; z1 = z2; z2 = z;
  }
  if (y3<y2) {
    x = x2; x2 = x3; x3 = x;
    y = y2; y2 = y3; y3 = y;
    z = z2; z2 = z3; z3 = z;
  }

  if (y1==y2) line(x1,x2,y1,z1<<10,z2<<10,rr,gg,bb);
  else {
    mx1=x1<<10;
    mx2=x1<<10;
    kx1=((x1-x2)<<10)/(y1-y2);
    kx2=((x1-x3)<<10)/(y1-y3);
    mz1=z1<<10;
    mz2=z1<<10;
    kz1=((z1-z2)<<10)/(y1-y2);
    kz2=((z1-z3)<<10)/(y1-y3);
    for(y=y1; y<=y2; y++) {
      line( mx1>>10, mx2>>10, y, mz1, mz2, rr,gg,bb);
      mx1+=kx1;
      mx2+=kx2;      
      mz1+=kz1;
      mz2+=kz2;      
      }
  }
  if (y2==y3) return;

  mx1=x2<<10;
  kx1=((x2-x3)<<10)/(y2-y3);
  kx2=((x1-x3)<<10)/(y1-y3);
  mx2=(x1<<10)+((y2-y1)*kx2);
  mz1=z2<<10;
  kz1=((z2-z3)<<10)/(y2-y3);
  kz2=((z1-z3)<<10)/(y1-y3);
  mz2=(z1<<10)+((y2-y1)*kz2);

  for(y=y2+1; y<=y3; y++) {
    mx1+=kx1;
    mx2+=kx2;
    mz1+=kz1;
    mz2+=kz2;
    line( mx1>>10, mx2>>10, y, mz1, mz2, rr,gg,bb);
    }
}

#3 PiKey
> teda, to je ostuda, fakt...... nikdo nic jo? hm,, no už jsem si sobě splodil rychlejší vykreslovač sám,, zrychlení více než 2×

Kdybys myslel dopředu, tak jsi ten první program udělal mnohem horší a pak se to určitě dalo zrchlit třeba 100x. A ostuda by byla ještě mnohem větší.

Jinak než začneš mluvit o ostudě, zkus se zamyslet nad tím, kolik lidí má chuť analyzovat docela dlouhý program a hledat v něm potenciál ke zrychlení. Občas se sice někdo najde, ale obvykle je lepší co nejlépe ohraničit svůj problém, zapsat ho sem a jasně formulovat, s čím máš problém (už to mnohdy přinese řešení problému). Nejspíš pak dostaneš i více odpovědí.

#4 ondra.holub
"Kdybys myslel dopředu, tak jsi ten první program udělal mnohem horší a pak se to určitě dalo zrchlit třeba 100x. A ostuda by byla ještě mnohem větší."

!! dobré !! bod + :)

jinak s tou ostudou to nesmíš brát tak vážně (vlastně nic co vyplodím by se nemělo brát vážně)..

spíš bych byl rád, kdyby to někdo prolít očima a řekl: "hele, tadyten výpočet" nebo "tadyto volání je v C zbytečně složitě překládáno, když místo abc napíšeš dbaght uhlmt tak tenhle konkrétní výpočet / volání / cokoliv proběhne za 1/3 času procesoru"

něco jako když jsem podobý kejkle dělal v pythonu a pak mi někdo řekl že if not (self.rect[0] in range (0, 640)) : je pomalé a if not (0 <= self.rect[0] <= 640) : je lepší a hned byl framerate o poznání vyšší

Optimalizovat by to chtělo hlavně funkci line()

• místo stálého dereferencování ztable[y*800+x]   si spočítat ukazatel na začátek řádky a pak ho inkrementovat stejně jako to máš u *pix
• výpočet barvy bych skusil provádět pomocí sčítání místo násobení, stejně jako to děláš pro výpočet z
  (ale přínos je potřeba změřit, jestli někjaký bude)
• sklon Z v závislostni na posunu x o 1 je pro trojůhelník všude stejný a není nutné ho počítat pro každou čáru.Navíc je lepší ho počítat přez delší rozsah - např definiční body trojuhelnika které jsou na x ose od sebe nejvice vzdaleny.
  (Obdobně to samozřejmně platí i pro závislost na posunu dle y o 1 což by možná šlo využít ve funkci triangl)

Co se týká funkce triangl

• Sklon trojuhelnika k nějaké ose je vsude stejný(viz výše) takže by nemnělo být nutné počítat mz2, mnělo by stačit do funkce line předat jen mz1 a sklon dle osy x(viz výše)
• Volání funkce a předávání parametrů stojí nemalou režiji. Někdy pomůže označit funkci jako inline(ale to je jen nápověda pro překladač a ten to může ignorovat) ale spíš je nutné ten kód rozepsat. Myslím že po zjednodušení funkce line by šlo to kreslení vodorovné čáry napsat do funkce triangl přímo, tak složité makro moc nedoporučuju. Možná bych pro přehlednost vyrazil tu část kódu která vykresluje pouze první bod a vykreslení provedl jen pomcí cyklu.

Rejp, rejp - nic osobního :) Na čtení není ten zdroják nic moc, sem tam nějakej komentář nebo lepší pojmenování funkce(line?) by nebylo od věci, nakonec jsem se tím ale jakžtakž prokousal a vypadá to jako moje pokusy z pascalu, no škoda že už jsem ty zdrojáky v průběhu času ztratil. - no teď se vážně cítím jako stařík, fňuk fňuk nostalgie.

Jinak to vypadá dost dobře, obzvlášť použití posunu pro nahrazení desetinných výpočtů pomocí posunu se mi moc líbí to mne tenkrát myslím nenapadlo.

P.S. Jako u všech optimalizací, je třeba přínos změřit. některé se mohou projevit málo nebo vůbec a nebo třeba jen v "ostré" verzi bez ladících informací které sami osobě mají velkou režiji.Vliv se může mšnit také v závislosti na optimalizaci.

#6 Ovrscout
uh,, dík,, mrknu na to,, dneska už ne mám toho plný zuby :))

nicméně ANO, je to víceméně pokračování mých zapomenutých pokusů z pascalu 

ten posun místo floatu je starej fígl, viz třeba ta tabulka sinů a cosinů, ve hře co teď páchám používám i tabulku arctanu a druhé odmocniny 

tak si s tim zase zítra budu hrát