Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

jho

2D Line drawing algo

This topic is 6439 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

I''m looking for a 2D line drawing algorithm, is Bresenham line the fastest? Also, I was wondering how I can implement a line thicker than 1 pixel thick.

Share this post


Link to post
Share on other sites
Advertisement
Yep - Bresenham is the fastest.

For thicker lines - why don''t you plot an extra pixel - just above/below/left/right an original Bresenham pixel

Share this post


Link to post
Share on other sites
The original Bresenham''s algorithm runs a bit faster if you use a symmetric implementation -- that is, start at both ends and work towards the middle. You''re only dealing with the error term for half of the length of the line that way. Also, you might want to look up the Symmetric Double Step algorithm for something different.

-Ironblayde
 Aeon Software

The following sentence is true.
The preceding sentence is false.

Share this post


Link to post
Share on other sites
Can you point me to a URL with optimized source code that works for lines of any slope? I have done this few years ago but I can''t find my code anymore..

Share this post


Link to post
Share on other sites

It would be interesting to compare a DDA line algorithm to Bresenham''s on today''s processors. With DDA you don''t have to do that exrta comparison in the loop so you can remove a potential pipeline stall. Fixed point or float would be another optimizing option. Also you can unroll the DDA by accumulating n variables and n-stepping them (keeping them independent of each other) again to keep the pipeline full.

Additionally I think DDA is a little easier to implement.

What do you think?

Share this post


Link to post
Share on other sites
I must come back on my previous post.

I think neocron is right when he says bresenham might not be the fastest now, due to the slow compare function nowadays.

Since there''s a limit to the width & height of your screen, it''s easy to make lookup tables for your divides needed for pre-calculating your interpolation values.

jho: What''s your programming language, and what do you need it for? How fast must it be, and are you prepared to go into assembly?

Share this post


Link to post
Share on other sites
baskuenen: I want source code in C/C++, but I can read pascal just fine. No ASM because it is for a multi platform project.

It''s not for a homework assignment if you''re worry about that! I''m just trying to get rid of my GDI calls right now and use my own pixel manipulation to compare performance.


Share this post


Link to post
Share on other sites
The DDA algorithm still tends to be slower because of the large clock delay in the execution of FMUL instructions. (And it''ll probably be even worse when the P4''s come out) Whereas the all-integer instruction set of a Bresenham implementation pipelines very nicely, with low cycle delay. Also branch prediction and speculative execution pretty much eliminate the penalty of the compare vs. any other integer instruction. However, these same developments have very much reduced the benefits of the symetric and multi-step line drawing algorithms, as the memory motion costs begin to dominate over actual actual execution costs, especially in the reduced register set of an x86 processor. Also, you really do not want to do lookup tables for line drawing. The cache miss costs of the lookup table colliding with the actual surface buffer would not be worth the few (if any) actual processor cycles saved.

For some hard numbers the following simulation was run:
On PII-300 running a virtual 640x480x32 screen (i.e. a segment of memory 640x480x4 bytes large not actually hooked to a screen buffer of any sort), several thousand random lines were generated, with DDA, Bresenham and Symmetric Two Step. The seed was saved so that the same lines were drawn for each algorithm. The results were run three times and the times for each were averaged. The DDA algorithm took an average of 163 ms per trial, The Bresenham algorithm took 63ms, and Symmetric Two step took 70ms. (The resolution of the timer was only approximately 10ms.) Generating generating the random numbers with a call to a stub function took average of 13ms.

Share this post


Link to post
Share on other sites
That''s some interesting stuff SiCrane; I always wonder about things like that. I''m familiar with caching, branch prediction, pipelining, etc. but I learned assembly on the MIPS architecture so I don''t know how any of it is implemented for Intel processors. Are there any books you recommend for learning that sort of thing?

-Ironblayde
 Aeon Software

The following sentence is true.
The preceding sentence is false.

Share this post


Link to post
Share on other sites

Hi all,

Here''s a snippet of code from my DDA line inner loop. ''xinc'' is in fixed point 16.16 ''yinc'' is in fixed point 16.16 and includes the width of the screen (so no muls). Of course you have to determine the x-major, or y-major orientation then the dy/dx (or dx/dy) before using this loop (just like bresenham).

    
for( int ix=0; ix<nLineLen; ix++ )
{
// Set the (x,y) point on the screen to color
*(pDst + (yaccum>>16) + (xaccum>>16)) = color;
xaccum += xinc;
yaccum += yinc;
}


You can see that you can add an xaccum2, yaccum2, and multiply xinc and yinc by two to get a better pipeline fill (as well as effectively unrolling the loop - remember to inc ix by two and account for odd line lengths)

You could use floats instead (so you don''t have to do the two right shifts) but remember to use an optimized cast and NOT just (int) or floor() to get the integer value of the screen (x,y) coordinate.

Additionally you could MIX float and int to get more parallelism and hopefully more speed. If anyone has an example of this I''d love to see it.

Hope this helps,
Karen









Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!