c algorithm optimization... use if block or pointers?

[noninterleaved]

I'm writing a scan-line converting algo for a graphics class... and I was wondering,would it be better to use if's for the "special" cases, like slope > 1, negative slope, etc... or would it be better to store all the points in an array, and do funny stuff with the indexes at the beginning. So basically we are talking about doing a single if at the beginning, but forcing the loop to do indirections on the memory, or is it better to just keep doing the if in the loop??

any thoughts??

 

[HigherGround]

here's a variation of bresenham line algorithm, which does not use either preallocated memory nor does it use conditionals

some assumptions:

1. we are drawing a line from (0,0) to (x1, y1), where both x1 and y1 are >= 0. This is trivial to achive since you have control over the reference coordinate system. (i.e drawing a line from (4, 3) to (-3, -1) is the same as drawing a line from (0, 0) to (7, 4). This assumes correct frame buffer address translation.

2. some definitions:

m - adjusted slope ( int )
d - deviation
frame_buffer - starting address of the frame buffer ( it's architecture dependent if you have direct access to frame buffer memory )
curr_frame_buffer - current frame buffer address
max_y - maximum vertical indice value this frame buffer can achive ( i.e. in the 640x480 frame buffer, max_y is 480 ) also assuming that the frame starts at address 0x00000000 in this case it would span to adress 0X0004B000. Obviously assuming that each entry in fb is 1 byte.
mask - bit mask used instead of conditionals.

3. right shift has to be arithmetic not logical

here's the pseudo implementaion in C/(C++ comments 🙂 )

int column; // current frame buffer column
int mask; // helper mask that will help eliminate conditionals
int m = y1*2;
float d = -x1;
void *curr_frame_buffer = frame_buffer; // obviously void* has to be replaced by a valid type
double value_mask = x1<1;
*curr_frame_buffer = 1; // (0,0) pixel filled, again curr_frame_buffer has to be a valid type
for(column=1; column<=x1; column++) // start at 1 since we already set pixel (0,0)
{
d += m; // bump deviation by the adjusted slope
curr_frame_buffer += max_y; // move the address by one column to the right ( assuming 0,0 live on the left size of the fb)
mask = ~(d>>31); // right shift ( remember that arithmetic shifts recycle the most significant bit ) and complement the result
d -= (value_mask&amp;mask ) // deviation set
curr_frame_buffer += (1&amp;mask); // check the deviation derived offset to see if we need to bump the pixel by one
*curr_frame_buffer = 1; // set a pixel
}

neat, notice the code has no conditionals, hence branch prediction on the CPU is eliminated.