Jump to content
  • Advertisement

Archived

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

jaggu

A new line algorithm?

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

Hello there, I am doing a 2d game and using DDraw 7. I started implementing a line drawing routine. I could have used Bresenham's Line Algorithm (http://wwwx.cs.unc.edu/~hoff/projec...e/perform0.html) but wondered if I could think a method of my own. I have come up with this method and have no idea if this has been done before. The algorithm is as follows: PROC Line (P1, P2) 1. P1 [x1,y1] and P2 [x2, y2] are end points of the line. 2. Find Mid point M ((x1+x2)/2, (y1+y2)/2) 3. Plot M 4. if M is either equal to P1 or P2 return 5. Call Line (P1, M) 6. Call Line (M, P2) 7. return That is, it recursively subdivides a line until the thickness of the line is 1 pixel. It plots the mid-point at each sub-division. Like Bresenham's line algorithm, this does not use any floating point operations nor multiplication or division. The division in calculation of midpoint can be replaced by a right-shift because its a division by 2. Here's a C implementation of the same: void my_line (BITMAP *b, int x1, int y1, int x2, int y2, int col) { int mx = (x1 + x2) >> 1; int my = (y1 + y2) >> 1; _putpixel16 (b, mx, my, col); // allegro routine if (((mx == x1) && (my == y1)) || ((mx == x2) && (my == y2))) return; my_line (b, x1, y1, mx, my, col); my_line (b, mx, my, x2, y2, col); } I would like to know what you think about the method, how it compares to Bresenham's algorithm and what are its pros and cons. Thank you. [edited by - jaggu on April 18, 2003 3:17:08 PM]

Share this post


Link to post
Share on other sites
Advertisement
Ok. It can work.

But i don''t know why do you think it can be faster than brasenham ?

How can you avoid reccursion calls ?
And that is not memory cashe frendly.

the bresenham (slow version) use some thing:

while( len -- )
{
if( Denominator > 0 )
{
Denominator += OnePart;
MemoryPointer += SomeOneOffset;
}else{
Denominator += AtherPart;
MemoryPointer += SomeAtherOffset;
}

*MemoryPointer = PixelColor;
}



Share this post


Link to post
Share on other sites
P.S.

But if you will go deeper , you will get one of the very fast line drawing algorithm ( not faster than all but very fast)

Share this post


Link to post
Share on other sites
I have used the same algo to test if a line is inside a rectangle.
(Founding the midpoint testing if it is inside the rect,if not then doing recursively two subdivisions with one end point and midpoint,and midpoint with the other end point) for a given number of subdivisions.Also a varation of this algo is used in binary search.



[edited by - lone_ranger on April 18, 2003 4:41:41 AM]

Share this post


Link to post
Share on other sites
The number of recursive calls in your algorithm will be roughly equal to the number of pixels in the line you''re subdividing. That''s a lot of overhead for drawing a single line.

Share this post


Link to post
Share on other sites
The algorithm you''ve proposed won''t be as accurate as the Bresenham line algorithm because when you divide by 2 you keep on losing precision. The Bresenham routine keeps track of the fractional component, so it will be more accurate.

Share this post


Link to post
Share on other sites
It''s been implemented before, but like people have mentioned, the number of recursive calls required makes this algorithm slower when implemented. It may not be noticeable with a couple lines, but the slowdown will be significant when you rasterize many lines. It gets slower if you try antialiasing your lines, and even slower if you do this in 3 dimensions (for example, stepping through a volume in a raycasting algorithm). Furthermore, you sometimes want to keep the order in which you access the pixels; not only is this more memory-coherent, but in volume rendering, you want to access the voxels (3d voxels) in order because the compositing operators are non-commutative.

Share this post


Link to post
Share on other sites
Thank you all for the comments. I will after all implement the Bresenham''s algorithm I did suspect that since it wasnt challenged for a long time, my method wont be good enough!

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!