النتائج 1 إلى 3 من 3

الموضوع: Bresenham's Line and Circle Algorithms

  1. #1
    elfr3on el3ashk الصورة الرمزية A7med Baraka
    تاريخ التسجيل
    Jun 2008
    الدولة
    Egypt - Cairo
    المشاركات
    4,695
    معدل تقييم المستوى
    10

    Post Bresenham's Line and Circle Algorithms


    End Google Ads 201810 - BS.net 01 -->
    Introduction
    Bresenham is a pretty smart ****** (note the use of the word "is", last I heard he was still working for IBM). This file contains the algorithms he developped for drawing lines and circles on a pixelated display system such as the VGA.
    Line Algorithm
    The basic algorithm works for lines which look like this:

    o------- |
    p1 -------- | deltay
    ------- p2 |
    -------o |
    ----------------------------------
    deltax

    كود:
    where p1 = (x1,y1),
          p2 = (x2, y2),
          x and y are both increasing from p1 to p2,
          deltax = x2 - x1,
          deltay = y2 - y1 and
          deltax >= deltay.


    All other types of lines can be derived from this type. I'll get to this bit later.
    First you need to perform the following intialisation:

    كود:
    x = x1
    y = y1
    d = (2 * deltay) - deltax

    x is the current x ********, you will add 1 to this variable after every pixel you draw until all pixels have been drawn. y is the current y ********. The decision variable is used to determine when to add 1 to this value. d is the decision variable which will be used to keep a track of what to do.
    Now you loop across the screen from x1 to x2 and for each loop perform the following operations for each pixel :

    كود:
    PutPixel(x, y);  { Draw a pixel at the current point }
    if d < 0 then
        d := d + (2 * deltay)
    else
      begin
        d := d + 2 * (deltay - deltax);
        y := y + 1;
      end;
    x := x + 1;

    It's that simple!
    Speeding Up The Line Algorithm
    There are several useful techniques for speeding up Bresenham's line algorithm.
    For starters, notice that all multiplications are by 2. This can be performed with a simple shift left instruction (Shl in Pascal, << in C).
    Next notice that the values you add to the decision variable do not change throughout the loop, so they can be precalculated beforehand.
    One property of lines is that they are symetrical about their mid-points, and we can use this property to speed up the algorithm. Store two x and y values, (xa, ya) and (xb, yb). Have each pair start on either end of the line. For each pass through the loop you draw the pixel at both points, add 1 to xa and subtract one from xb. When d >= 0 add 1 to ya and subtract one from yb. You then only need to loop until xa = xb.
    It's also obvious that if the decision variable becomes the same value it was when it was initialised, then the rest of the line is just copies of the line you have already drawn up to that point. You might be able to speed the algorithm up by keeping an array of how y has been modified and then use this array if the line starts repeating itself. If you are using the Intel registers to store all values then you probably wouldn't get much of a speed increase (in fact it could slow it down), but it would probably be useful for thing like linear texture mapping (discussed below). I've never actually tried implementing this technique, and I would like to hear the results if anyone does.
    Above all remember that these optimisations will only significantly speed up the line drawing algorithm if the whole thing is done in assembly. A profile of the example program at the end of this file showed that 40% of CPU time was spent in the slow PutPixel routine I was using, the loop mechanics and testing the sign of the decision variable.
    Other Uses for the Line Algorithm
    A line can be represented by the equation y = mx + c, where m = deltay / deltax. Note that this is a version of the standard linear equation ax + bx + c = 0. There are many algorithms which use this equation.
    One good use for the Bresenham line algorithm is for quickly drawing filled concave polygons (eg triangles). You can set up an array of minimum and maximum x values for every horizontal line on the screen. You then use Bresenham's algorithm to loop along each of the polygon's sides, find where it's x value is on every line and adjust the min and max values accordingly. When you've done it for every line you simply loop down the screen drawing horizontal lines between the min and max values for each line.
    Another area is in linear texture mapping (see the PC-GPE article on texture mapping). This method involves taking a string of bitmap pixels and stretching them out (or squashing them in) to a line of pixels on the screen. Typically you would draw a vertical line down the screen and use Bresenham's to calculate which bitmap pixel should be drawn at each screen pixel.
    Circle Algorithm
    Circles have the property of being highly symetrical, which is handy when it comes to drawing them on a display screen.

    |y (This diagram is supposed to be a circle, try viewing
    | it in 50 line mode).
    \ ..... /
    . | . We know that there are 360 degrees in a circle. First we
    . \ | / . see that a circle is symetrical about the x axis, so
    . \|/ . only the first 180 degrees need to be calculated. Next
    --.---+---.-- we see that it's also symetrical about the y axis, so now
    . /|\ . x we only need to calculate the first 90 degrees. Finally
    . / | \ . we see that the circle is also symetrical about the 45
    . | . degree diagonal axis, so we only need to calculate the
    / ..... \ first 45 degrees.
    |
    |

    Bresenham's circle algorithm calculates the ********s of the pixels in the first 45 degrees. It assumes that the circle is centered on the origin. So for every pixel (x,y) it calculates we draw a pixel in each of the 8 octants of the circle :

    كود:
    PutPixel(CenterX + X, Center Y + Y)
    PutPixel(CenterX + X, Center Y - Y)
    PutPixel(CenterX - X, Center Y + Y)
    PutPixel(CenterX - X, Center Y - Y)
    PutPixel(CenterX + Y, Center Y + X)
    PutPixel(CenterX + Y, Center Y - X)
    PutPixel(CenterX - Y, Center Y + X)
    PutPixel(CenterX - Y, Center Y - X
    )

    So let's get into the actual algorithm. Given a radius for the circle we perform this initialisation:

    كود:
    d := 3 - (2 * RADIUS)
    x := 0
    y := RADIUS


    Now for each pixel we do the following operations:

    كود:
    Draw the 8 circle pixels
    if d < 0 then
        d := d + (4 * x) + 6
    else
      begin
        d := d + 4 * (x - y) + 10
        y := y - 1;
      end;

    And we keep doing this until x = y. Note that the values added to the decision variable in this algorithm (x and y) are constantly changing, so we cannot precalculate them. The muliplications however are by 4, and we can accomplish this by shifting left twice.
    A Pascal General Line Procedure
    The basic Bresenham line algorithm can be modified to handle all types of lines. In this section assume that deltax = abs(x2 - x1) and deltay = abs(y2 - y1).
    First let's take lines where deltax >= deltay. Now if x1 > x2 then you will need to subtract 1 from x for every pass through the loop. Similarly if y1 > y2 then you will be also need to subtract 1 from y for every pass through the loop where d < 0.
    Lines where deltax < deltay can be handled the same way, you just swap all the deltax's and deltay's around.
    The fastest method of handling all cases is to write a custom routine for each of the 8 line types:

    كود:
    1) x1 <= x2, y1 <= y2, deltax >= deltay
    2) x1 <= x2, y1 <= y2, deltax <  deltay
    3) x1 <= x2, y1 >  y2, deltax >= deltay
    4) x1 <= x2, y1 >  y2, deltax <  deltay
    5) x1 >  x2, y1 <= y2, deltax >= deltay
    6) x1 >  x2, y1 <= y2, deltax <  deltay
    7) x1 >  x2, y1 >  y2, deltax >= deltay
    8) x1 >  x2, y1 >  y2, deltax <  deltay


    This will give you the fastest results, but will also make your code 8 times larger! Alternatively you can declare a few extra variables and use a common inner loop for all lines:
    كود:
    numpixels = number of pixels to draw
              = deltax if deltax >= deltay or
              = deltay if deltax < deltay
    dinc1 = the amount to add to d when d < 0
    dinc2 = the amount to add to d when d >= 0
    xinc1 = the amount to add to x when d < 0
    xinc2 = the amount to add to x when d >= 0
    yinc1 = the amount to add to y when d < 0
    yinc2 = the amount to add to y when d >= 0
    The following is a simple example program which uses this technique:
    كود:
    {
    
    BRESLINE.PAS - A general line drawing procedure.
                   By Mark Feldman
    
    This is a very simple implementation of Bresenham's' line algorithm with
    no optimisations. It can draw about 6000 random lines a second in mode 13h
    on my 486SX33 with sloooooow Paradise Extended VGA.
    
    }
    
    procedure Line(x1, y1, x2, y2 : integer; color : byte);
    var i, deltax, deltay, numpixels,
        d, dinc1, dinc2,
        x, xinc1, xinc2,
        y, yinc1, yinc2 : integer;
    begin
    
      { Calculate deltax and deltay for initialisation }
      deltax := abs(x2 - x1);
      deltay := abs(y2 - y1);
    
      { Initialize all vars based on which is the independent variable }
      if deltax >= deltay then
        begin
    
          { x is independent variable }
          numpixels := deltax + 1;
          d := (2 * deltay) - deltax;
          dinc1 := deltay Shl 1;
          dinc2 := (deltay - deltax) shl 1;
          xinc1 := 1;
          xinc2 := 1;
          yinc1 := 0;
          yinc2 := 1;
        end
      else
        begin
    
          { y is independent variable }
          numpixels := deltay + 1;
          d := (2 * deltax) - deltay;
          dinc1 := deltax Shl 1;
          dinc2 := (deltax - deltay) shl 1;
          xinc1 := 0;
          xinc2 := 1;
          yinc1 := 1;
          yinc2 := 1;
        end;
    
      { Make sure x and y move in the right directions }
      if x1 > x2 then
        begin
          xinc1 := - xinc1;
          xinc2 := - xinc2;
        end;
      if y1 > y2 then
        begin
          yinc1 := - yinc1;
          yinc2 := - yinc2;
        end;
    
      { Start drawing at  }
      x := x1;
      y := y1;
    
      { Draw the pixels }
      for i := 1 to numpixels do
        begin
          PutPixel(x, y, color);
          if d < 0 then
            begin
              d := d + dinc1;
              x := x + xinc1;
              y := y + yinc1;
            end
          else
            begin
              d := d + dinc2;
              x := x + xinc2;
              y := y + yinc2;
            end;
        end;
    end;
    Note that if you are writing a line routine for mode 13h (for example) you can speed it up by converting the inner loop to assembly and including mode 13h specific code. This portion of the above routine works the same but the values are stored in a single variable (screen) which holds the memory address of the current pixel, screeninc1 and screeninc2 are the update values for screen.
    كود:
    var screen : word;
        screeninc1, screeninc2 : integer;
         .
         .
         .
      { Start drawing at  }
      screen := word(y1) * 320 + x1;
      screeninc1 := yinc1 * 320 + xinc1;
      screeninc2 := yinc2 * 320 + xinc2;
    
      { Draw the pixels }
      asm
        { Use as many registers as are available }
        push $A000
        pop es
        mov di, screen
        mov dx, d
        mov al, color
        mov cx, numpixels
        mov bx, dinc1
    
        @bres1:
    
        { Draw the current pixel and compare the decision variable to 0 }
        mov es:[di], al
        cmp dx, 0
        jnl @bres2
    
        { D < 0 }
        add dx, bx { bx = dinc1 }
        add di, screeninc1
        jmp @bres3
    
        @bres2:
    
        { D >= 0 }
        add dx, dinc2
        add di, screeninc2
    
        @bres3:
    
        loop @bres1
      end;


  • #2
    تقنى مشارك
    تاريخ التسجيل
    Dec 2008
    الدولة
    alexandria
    المشاركات
    55
    معدل تقييم المستوى
    202

    افتراضي رد: Bresenham's Line and Circle Algorithms

    شكرا يا بشمهندس على الموضوع بس انا كنت عايزة اتأكد مش دي #cبرضة

  • #3
    elfr3on el3ashk الصورة الرمزية A7med Baraka
    تاريخ التسجيل
    Jun 2008
    الدولة
    Egypt - Cairo
    المشاركات
    4,695
    معدل تقييم المستوى
    10

    افتراضي رد: Bresenham's Line and Circle Algorithms

    yes i think u r right
    but i think its pseudo code more
    u can implement it by any lang, as u need

    thnx for your reply

  • معلومات الموضوع

    الأعضاء الذين يشاهدون هذا الموضوع

    الذين يشاهدون الموضوع الآن: 1 (0 من الأعضاء و 1 زائر)

    المواضيع المتشابهه

    1. يا ريت حد يساعدنى فى command line
      بواسطة fatma mansour في المنتدى linux - لينوكس
      مشاركات: 5
      آخر مشاركة: 05-01-2009, 09:35 PM
    2. Midpoint Circle algorithm
      بواسطة A7med Baraka في المنتدى Java - جافا
      مشاركات: 0
      آخر مشاركة: 03-30-2009, 01:26 AM
    3. Bresenham Line algorithm
      بواسطة A7med Baraka في المنتدى Java - جافا
      مشاركات: 0
      آخر مشاركة: 03-30-2009, 01:21 AM
    4. C++ and STL: Take Advantage of STL Algorithms by Implementing a Custom Iterator
      بواسطة C++ Programming في المنتدى MSDN C++ Lessons
      مشاركات: 0
      آخر مشاركة: 03-29-2009, 02:42 AM
    5. New Line VS2005 Installer's BodyText
      بواسطة C# Programming في المنتدى General topics in C# - CSharp
      مشاركات: 0
      آخر مشاركة: 03-27-2009, 07:21 PM

    الكلمات الدلالية لهذا الموضوع

    مواقع النشر (المفضلة)

    ضوابط المشاركة

    • لا تستطيع إضافة مواضيع جديدة
    • لا تستطيع الرد على المواضيع
    • لا تستطيع إرفاق ملفات
    • لا تستطيع تعديل مشاركاتك
    •  
    "وَقُل رَّبِّ زِدْنِي عِلْمًا"
    أعلانات نصية أستضافة , ريسيلر - Best Hosting | BarakaSoft Web Solutions

    BarakaSoft PageRank RSS RSS 2.0 XML MAP HTML 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 C/C++ | Java | C# | Network | Database | OS | Linux | Windows | Hacker & Security | Photoshop | Flash | Web Development | Free Programs | Mobile App | Free Java Course | Latest Technical News | Internet Programs | Antiviurse Programs | Graphics Programs | Network Programs | Portable Programs | vb Forums Development | Forums Development | CMS(Joomla-nuke-wordpress-mkportal...) | Photo | Anime |