Jump to content
  • Advertisement
Sign in to follow this  
staticVoid2

Fastest Line Rasterizer

This topic is 3886 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
Depends on the hardware. If you have access to hardware accelerator, the fastest algorithm consists in sending the appropriate data to the driver.

Otherwise, tell us more about your cache usage.

Share this post


Link to post
Share on other sites
Quote:
Original post by staticVoid2
no hardware acceleration - just the general algorithm, which one is fastest in computers, is it Bresenham's?


Depends on your cache usage. If your render target is very large, then using an intermediary span-buffer or grouping lines together might be a better alternative. If your render target is small, Bresenham should be acceptable.

Though, as I mentioned earlier, using hardware acceleration on any recent computer should be ten to fifty times faster than using Bresenham, anyway.

Share this post


Link to post
Share on other sites
I mean a more generic algorithm not specific to any hardware requirements or cache. written in c++, can you recomend ONE of the fastest algorithms.

Share this post


Link to post
Share on other sites
Bresenham's algorithm has a time complexity which is linear in the number of pixels drawn. This makes it the fastest algorithm in terms of theoretical time complexity.

This is a property of the algorithm, independent of it being written in C++ or not.

As for C++, there is no such thing as a fastest line-drawing algorithm, so your question cannot be answered.

Perhaps you should explain why you are asking this.

Share this post


Link to post
Share on other sites
On hardware where Bresenham is fast, run-sliced line drawing is generally faster than Bresenham for longer lines.

However, I imagine straight DDA is competitive with, if not faster than Bresenham on most CPUs with reciprocal approximation and float-to-int instructions due to a simpler inner loop.

So the answer is, "it depends."

Share this post


Link to post
Share on other sites
can anyone identify what this algorithm is:

void Rasterizer::DrawLine(int x0, int y0, int x1, int y1, char * video_buffer, int mem_pitch, int color) {
int deltay = (y1 - y0);
int deltax = (x1 - x0);

if(absi(deltax) > absi(deltay)) { // absi = absolute value of an int

float m = (float)deltay / (float)deltax; // gradient
double y = y0; // starting point
double x = x0;
int xx; // the sign of x (with direction it is to be incremented)

if(x1 < x0) {
xx = -1;
m = -m;
} else xx = 1;

while(x != x1) {
video_buffer[((int)y * mem_pitch) + (int)x] = color;
y += m;
x += xx;
}

} else {

float m = (float)deltax / (float)deltay; // gradient
double y = y0; // starting point
double x = x0;
int yy; // the sign of y (which direction it is to be incremented)

if(y1 < y0) {
yy = -1;
m = -m;
} else yy = 1;

while(y != y1) {
video_buffer[((int)y * mem_pitch) + (int)x] = color;
x += m;
y += yy;
}

}
}






I just threw it together, it seems to work though i don't know if it has a name?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!