   Optimizing this Code  (Bresenham rasterization integer only)
  HelloI am working on rasterization at the moment.Below is the code of my current integer only bresenham implementation.My aim is to extent this code to a 3d bresenham implementationn like thisBresenham3D{dx = x1-x0;dy = y1-y0;dz = z1-z0;//ASSUMPTION: dx > dy > 0  && dx > dz > 0, thus x_new can be incremented each step// thus the slope is 0 < m < 1while(notyetdone) { Bresenham2DStep(x0,y0,x1,y1, y_new); Bresenham2DStep(x0,z0,x1,z1, z_new); ++x_new;  SetVoxel(x_new,y_new,z_new); }}So basically I am going to decompose the 3d bresenham into 2 projections.This will be the base for my 3d volume rasterizer, which I am going to use to rasterize triangles into voxels, in order to build up a volume data set (Scan conversion of polygons)Thus I am very interested in tuning the hell out of the 2d implementation below.Any suggestions on how to optimize that code are welcome.Thx in advance 14 namespace bresenham 15 {    16void BresenhamStep(/*const int x,*/ int& y, const int dx, const int dy, int& error)   17{ 18    error += dy;1920    if((error<<1) >= dx)  21    { 22   ++y;    23   error -= dx; 24    } 25}    2627 28void BresenhamInit(int x0, int y0, int x1, int y1, BresenhamState& state)   29{ 30    if(x1<x0) 31    { 32   std::swap(x0,x1); 33   std::swap(y0,y1); 34    } 35    // dx >= 0 36    state.dx = x1-x0; 37    state.dy = y1-y0;38 39    state.error = 0; 40    state.idx = 0;   41    state.idy = 1;   42    state.bNegative = false; 43  44    // positive slope 45    if(state.dy>=0) 46    { 47   if(state.dx<state.dy) 48   { 49  std::swap(x0,y0); 50  std::swap(x1,y1); 51  state.idx = 1; 52  state.idy = 0; 53   } 54    } 55    //negative slope 56    else 57    { 58   state.bNegative = true; 59   y0 = -y0; 60   y1 = -y1; 61   if(state.dx<-state.dy) 62   { 63  std::swap(x0,y0); 64  std::swap(x1,y1); 65  state.idx = 1; 66  state.idy = 0; 67   } 68  69    } 70  71    state.dx = x1-x0; 72    state.dy = y1-y0; 73  74    state.p[0] = x0; state.p[1] = y0; 75    state.x1 = x1; 76} 77  78void Bresenham2D( int x0, int y0, int x1, int y1) 79{ 80    BresenhamState state; 81    BresenhamInit(x0,y0,x1,y1,state); 82  83    for(;state.p[0]<=state.x1;++state.p[0]) 84    { 85   if(state.bNegative) 86  Plot(state.p[state.idx],-state.p[state.idy],1); 87   else 88  Plot(state.p[state.idx],state.p[state.idy],1); 89  90   BresenhamStep(/*state.p[0],*/state.p[1],state.dx,state.dy,state.error); 91    } 92} 93 }
  Wow I haven't seen Bresenham in a while. I had to implement this is 8088 ASM for the CGA and VGA cards years ago. Even in ASM it's pretty easy. In any case it looks like you could take the if out of the loop for starters.Edit: The other think I'll add is years ago I saw an algorithm which was supposedly faster than Bresenham. It used the fact that you typically get pixel pattern when drawing a line. I don't remember what it was called or where I saw it. You could probably Google for it. However it was somewhat more complex than Bresenham.[Edited by - polypterus on May 5, 2009 10:04:46 AM]; Some line drawing algorithmsI thinks its the Wu version that polypterus is referring to.   ;  I did replace the following 2 lines with 85   if(state.bNegative) 86  Plot(state.p[state.idx],-state.p[state.idy],1); 87   else 88  Plot(state.p[state.idx],state.p[state.idy],1);Plot(state.p[state.idx],state.p[state.idy]*state.factor,1);factor is 1 or -1 to represent the mirroring that takes place during initialization of the line drawing procedurethis doubled the performance almostI could defere the pixel operations and perform 4 steps in a row and make use of SIMD units to mirror the coordinatesThe last switch here could be eliminated as wellif((error<<1)>=dx){++y;error -= dx;}// new version 30    error += dy; 31    const int a = (error<<1)-dx; 32    const int b = ((~a)&(1<<(sizeof(int)*8-1)))>>(sizeof(int)*8-1); 33    y-=b;  34    error += dx*b;if a >= 0 in its binary representation it would be 0xxxxxxxxxx = 1 otherwise 0Shifting negative values to the right returns negative values thus b = 0 or -1Wu Xiaolin's algorithm is supposed to do anti aliasing and said to be slower (source wikipedia)but nice find, didn t know of that algorithm Any further ideas?thx[Edited by - Basiror on May 6, 2009 2:47:14 AM];  To optimize it a great deal, get rid of that branching. Original Bresenham algorithm was invented in days of 8-bit CPUs with no real pipeline.Somewhat better algorithm uses 16:16 fixed point. Works like this (for case when |dx|<|dy| :int dx=((x1-x0)<<16)/(y1-y0);/// once per line.int x=x0<<16;for(int y=y0;y<y1;++y){ pixels[(x>>16)+y*width]=color;/// once per pixel x+=dx;}(you can make it better yet by incrementing pointer instead of y. Also, you may want to specify coordinates as 16:16 fixed point to begin with, for anti-aliasing and subpixel correctness purposes)edit: evidently, this trivial use of fixed point mathematics is called "Xiaolin Wu's line algorithm". Geez. What's next, a+=b would be Ku Jing's addition? (Ku Jing is random name). Cant they stick to only naming nontrivial things after people? (Brezenham's algorithm is nontrivial).   ;  Hithx for the tip with fixedpoint math, you always learn something new :)it gave me a speedup of 4% over my current solutionA larger speedup could be gained by getting rid of the conditionals in the init procedure, approximately 20% (I just commented the conditionals out to see) 37void Bresenham2DInit(int x0, int y0, int x1, int y1, Bresenham2DState& state) 38{ 39    if(x1<x0) 40    { 41   std::swap(x0,x1); 42   std::swap(y0,y1); 43    } 44    // dx >= 0 45    int dx = x1-x0; 46    state.dy = y1-y0; 47  48    state.idx = 0; 49    state.idy = 1; 5051    state.factor = 1;5253    // positive slope54    if(state.dy>=0)  55    {    56   if(dx<state.dy)   57   {    58  std::swap(x0,y0);  59  std::swap(x1,y1);  60  state.idx = 1;61  state.idy = 0;62   }  63    } 64    //negative slope 65    else 66    { 67   y0 = -y0; 68   y1 = -y1; 69   if(dx<-state.dy) 70   { 71  std::swap(x0,y0); 72  std::swap(x1,y1); 73  state.idx = 1; 74  state.idy = 0; 75   } 76  77   state.factor = -1; 78  79    } 80  81    dx = x1-x0; 82    state.dy = ((y1-y0)<<16)/dx; 83  84    state.p[0] = x0; state.p[1] = (y0<<16); 85    state.x1 = x1; 86} 88void Bresenham2D( int x0, int y0, int x1, int y1) 89{ 90    int p[2]; 91    Bresenham2DState state; 92    Bresenham2DInit(x0,y0,x1,y1,state); 93  94    for(;state.p[0]<=state.x1;++state.p[0]) 95    { 96   p[0] = state.p[0]; 97   p[1] = state.p[1]>>16; 98  99   Plot(p[state.idx],p[state.idy]*state.factor,1);100   state.p[1] +=state.dy;101    }102};  ? How can you measure speedup in % for startup anyway? For sufficiently long lines, speedup in % would be negligible.If you're after speedup for drawing a lot of short lines, you can try sorting the lines by y of top endpoint to start with, to improve cache coherency.Also, for short lines, you can try that, with some branch-less max function:int md=max(abs(y1-y0),abs(x1-x0));int dx=((x1-x0)<<16)/md;int dy=((y1-y0)<<16)/md;int x=x0<<16;int y=y0<<16;while(md>=0){pixels[(x>>16)+(y>>16)*width]=color;/// once per pixelx+=dx;y+=dy;md-=1;}(the loop itself is slower, so for long lines it could well be slower.)   ;  Use vector intrinsics to draw 4 lines at a time and use vector selects to help eliminate all branches. With this approach depending on your architecture it might be more natural to implement the algorithm with floats.;Quote:Original post by Dmytry? How can you measure speedup in % for startup anyway? For sufficiently long lines, speedup in % would be negligible.If you're after speedup for drawing a lot of short lines, you can try sorting the lines by y of top endpoint to start with, to improve cache coherency.Also, for short lines, you can try that, with some branch-less max function:*** Source Snippet Removed ***(the loop itself is slower, so for long lines it could well be slower.)Before it took 50ms with my test program after 48ms thus 4% speedup.SIMD is an  option once i am done with the algorithmYour last version is indeed very easy to implement an to follow, but its only as fast as my current implementation, unfortunately my lines won t be longer than 128 stepsBut due to its simplicity I am going to use it for the SIMD implementationhere some branchless max and abs functions  3 namespace branchless  4 {  5//! computes the absolute value of v without branching  6inline int iabs(int v)  7{  8    // if v is negative mask = 0xFF... thus we compute the 2 complement  9    const int mask = v >>(sizeof(int)*8-1); 10    return (v^mask) - mask; 11}; 12  13//! computes the max of a and b without branching 14inline int imax(int a, int b) 15{ 16    //if a is greater than b mask is 0 otherwise 0xFF... 17    const int mask = (a-b)>>(sizeof(int)*8-1); 18  19    return a +((b-a)&mask); 20}; 21 };Just out of curiosity, did you work on rasterization before?[Edited by - Basiror on May 7, 2009 6:37:47 AM];  Yea. Implemented line, circle, and triangle drawing in assembly almost a decade ago (was 14 back then), and even textured strip rendering.By the way, speaking of branch-less max. There are special instructions for that sort of thing, like conditional mov. Try using a<b?b:a; and look at generated assembly at maximum optimization, it could be branch-less and faster than your code. You can get rid of multiply in line drawing, by the way. Just increment pointer by image width to do y step. Or try implementing Brezenham line drawing with operator? , and also, use variables for dl and ds , which are deltas for stepping the drawing pointer along longest delta and along shortest delta (e.g. for dx>dy>0, dl=1 , ds=width), then you'll need just one inner loop.   