1

I read in stackoverflow before about Bresenham algorithm use for a particular environment like low-language, but I have to compare it in my report so any ideal for my report. How can I prove Bresenham is faster than DDA. Now I created a simple paint on winform C# and the time when I draw with 2 different method is likely equal, sometime DDA is faster. Here is my code in both method

Bresenham Algorithm

        List<Point> vertices = new List<Point>();

        int deltaX = xN - x0; int signX = deltaX >= 0 ? 1 : -1;
        int deltaY = yN - y0; int signY = deltaY >= 0 ? 1 : -1;
        if (deltaX == deltaY && deltaX * deltaY == 0) return vertices;

        // |dy|/|dx| < 1 => |dy| < |dx| => m < 1
        if (Math.Abs(deltaX) > Math.Abs(deltaY))
        {

            int _2deltaX = deltaX * 2 * signX;
            int _2deltaY = deltaY * 2 * signY;
            int p0 = _2deltaY - deltaX * signX;
           
            // create array to contain vertices
            vertices.Add(new Point(x0, y0));

            int xCurrent = x0;
            int yCurrent = y0;
            while (true)
            {
                if (count >= (Math.Abs(deltaX) + 1)) return vertices;

                if (p0 < 0)
                {
                    xCurrent += signX;

                    // pk + 1 = pk + 2.∆y.signX
                    p0 = p0 + _2deltaY;
                }
                else
                {
                    xCurrent += signX;
                    yCurrent += signY;

                    // pk+1= pk + 2.∆y.signX - 2.∆x.signY
                    p0 = p0 + _2deltaY - _2deltaX;
                }
                vertices.Add(new Point(xCurrent, yCurrent));
            }
        }
        // |dy|/|dx| > 1 => |dy| > |dx| => m > 1
        else if (Math.Abs(deltaX) <= Math.Abs(deltaY))
        {

            int _2deltaX = deltaX * 2 * signX;
            int _2deltaY = deltaY * 2 * signY;
            int p0 = _2deltaX - deltaY * signY;

            // create array to contain vertices
            vertices.Add(new Point(x0, y0));

            int xCurrent = x0;
            int yCurrent = y0;
            while (true)
            {
                if (count >= (Math.Abs(deltaY) + 1)) return vertices;

                if (p0 < 0)
                {
                    yCurrent += signY;

                    // pk + 1 = pk + 2.∆x.signY
                    p0 = p0 + _2deltaX;
                }
                else
                {
                    xCurrent += signX;
                    yCurrent += signY;

                    // pk+1= pk + 2.∆x.signY - 2.∆y.signX
                    p0 = p0 + _2deltaX - _2deltaY;
                }
                vertices.Add(new Point(xCurrent, yCurrent));

            }

        }

        return vertices;

DDA Algorithm

        List<Point> vertices = new List<Point>();

        int deltaX = xN - x0; int signX = deltaX >= 0 ? 1 : -1;
        int deltaY = yN - y0; int signY = deltaY >= 0 ? 1 : -1;
        if (deltaX == deltaY && deltaX * deltaY == 0) return vertices;

        
        int step = Math.Abs(deltaX) > Math.Abs(deltaY) ? Math.Abs(deltaX) : Math.Abs(deltaY);

        // x(k + 1) = xk + x'
        double stepX = deltaX * 1.0 / step;
        double stepY = deltaY * 1.0 / step;

        vertices.Add(new Point(x0, y0));

        double xCurrent = x0;
        double yCurrent = y0;


        for (int i = 0; i < step; i++)
        {

            xCurrent += stepX;
            yCurrent += stepY;

            vertices.Add(new Point((int)Math.Round(xCurrent), (int)Math.Round(yCurrent)));
        }
     
        return vertices;
  • Try adding a line of code to the loop in each algorithm to actually add the points to the vertex array - maybe there's some JIT optimisation happening in the simpler DDA loop than is being applied in the Bresenham loop, and that's changing the results. – Matthew Watson Nov 23 '21 at 09:32
  • Yeah in my draw function I did it, I use forreach and us gl.Vertex() for each point in vertices and the time is not different too much – Minh Nguyen Nov 23 '21 at 09:39
  • I count time when draw function end, and count time in algorithm too, 2 results doesnt show Bresenham is faster than DDA – Minh Nguyen Nov 23 '21 at 09:41
  • I think it might be helpful to not just put points in a list, but change values in a 2D array or bitmap. That way you avoid some potential overhead, and have a better chance of verifying that the algorithms produce a similar output. For example, your DDA algorithm does not add any vertices to the list in the loop. – JonasH Nov 23 '21 at 09:55
  • Oh sorry, when I edit code I deleted it. So you mean bresenham helpful when we use putPixel(glVertex in SharpGL) in the algorithm instead of add in list? – Minh Nguyen Nov 23 '21 at 10:00
  • `Vertices.add(new Point(...))` takes much longer than everything else. That's what you're measuring. Also, Bresnham's might not actually be faster on your CPU. Also, it's tough to do benchmarks properly in a JIT-compiled language. – Matt Timmermans Nov 23 '21 at 12:52
  • If I replace Vertices.add(new Point(...)) by gl.Vertex(X,Y) it works faster than DDA right? – Minh Nguyen Nov 23 '21 at 13:19
  • DDA is faster then Bresenham for many years now ... Bresenham was a thing in low level graphics on old CPU architectures ... pipelining and CAHCHEs changes the behaviour ... so DDA got faster IIRC from i80386. Also [integer based DDA](https://stackoverflow.com/a/24682318/2521214) is not using any multiplication nor division and making much cleared more manageable code easily portable to any dimensionality putting Bresenham to garbage where it belongs... Also FPU and floating point computation on CPU got much faster too in recent years so Brunchless float DDA is also faster.. – Spektre Nov 24 '21 at 09:18
  • Also note that conversion from `double` to `integer` is probably the bottleneck of your DDA ... – Spektre Nov 24 '21 at 09:22
  • Thank you too much, but what is bottleneck, I don't get it. – Minh Nguyen Nov 24 '21 at 14:53
  • @MinhNguyen botleneck is the slowest operation in your program as one `line` program is using double/int conversion and the other is not its not a fair comparison however DDA beats it anyway... – Spektre Nov 24 '21 at 19:48
  • Thank you, many things to study – Minh Nguyen Nov 25 '21 at 12:17

0 Answers0