9
\$\begingroup\$

I found myself having to implement Bresenham's line drawing algorithm.

I'm looking for feedback on effectivity and code style. Can I reduce the code somehow?

template<typename Callable>
void bresenham(Vec2i p0, Vec2i p1, Callable&& cb){
    const auto swap_xy = std::abs(p1.y - p0.y) > std::abs(p1.x - p0.x);
    if (swap_xy) {
        swap(p0.x, p0.y);
        swap(p1.x, p1.y);
    }

    auto mark = [swap_xy, &cb](Vec2i p) {
        if (swap_xy) {
            cb(Vec2i (p.y, p.x));
        }
        else {
            cb(p);
        }
    };

    const auto d = p1 - p0;
    const auto dx_abs = std::abs(d.x);
    const auto step_y = d.y < 0 ? -1 : 1;
    const auto step_x = d.x < 0 ? -1 : 1;
    auto pen = p0;
    while (pen.x != p1.x) {
        bool skip = false;
        auto error = std::abs(2 * d.y*(pen.x - p0.x) - 2 * d.x*(pen.y - p0.y));
        while (error > dx_abs) {
            pen.y += step_y;
            error -= 2 * dx_abs;
            mark(pen);
            skip = true;
        }
        if (!skip) {
            mark(pen);
        }
        pen.x += step_x;
    }
    mark(p1);
}

The class Vec2i is the equivalent of:

struct Vec2i{
   Vec2i(int ax = 0, int ay = 0) : x(ax), y(ay) {}
   int x,y;
};

with the expected copy constructor and arithmetic operators that one usually associates with a mathematical vector.

I have unit tested this extensively and found no issues. Although I'm a bit worried as most implementations I've seen are much longer (2-3x) and have special handling for a lot of cases, cases that just seem to work in my unit tests.

I accept any type of callback that will be called for each produced position. Some times I need to raster the line, some times I just need to iterate along the line and do things. This seemed appropriate to me.

\$\endgroup\$
7
\$\begingroup\$

That seems good. I really like the callback mechanism to do whatever we want with the marked positions and not one specific action. That makes for a generic tool; good design. I don't have much to say to improve the algorithm itself, but here are my two cents anyway:

  • Do you have a using std::swap; anywhere? Otherwise, I don't think that the unqualified calls to swap will work as intended.

  • While auto is a great tool, there are some times when I don't think that it adds to readability. For example, it took me more time that I would have wanted to see that swap_xy was a bool. That's prone to debate anyway, but I don't think that you will ever replace it by another type and an explicit bool would have highlighted the logic. That's still subjective though.

  • Still pretty subjective, but instead of this:

    auto pen = p0;
    while (pen.x != p1.x) {
        // ...
        pen.x += step_x;
    }
    

    I would have used a for loop since you explicitly have an initialization, a condition and a step. And everyone uses the same variable pen, which isn't used after the loop.

    for (auto pen = p0; pen.x != p1.x; pen.x += step_x) {
        // ...
    }
    
  • Nitpicking again, but I would have factored the multiplication by 2 out of the std::abs in the computation of error:

    auto error = 2 * std::abs(d.y*(pen.x - p0.x) - d.x*(pen.y - p0.y));
    

    By the way, this factorization highlights something else: you actually do not need to keep the multiplication by 2 in error; you only need it for the comparison:

    auto error = std::abs(d.y*(pen.x - p0.x) - d.x*(pen.y - p0.y));
    while (2 * error > dx_abs) {
        pen.y += step_y;
        error -= dx_abs;
        mark(pen);
        skip = true;
    }
    

    Not that it makes a big difference, but it still makes the code a little bit terser.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the review! About factoring the multiplication by 2 out, in the original code, as dx_abs is const then the compiler can eliminate the multiplication in the inner loop (by just calculating the value once before entering the outer loop). In your proposal, I'm not sure that the compiler can remove the multiplication by 2 in the inner most loop. This is probably micro optimisation but it's the original reason for the current formulation. \$\endgroup\$ – Emily L. Jun 12 '15 at 10:57
  • \$\begingroup\$ Ah yeah I forgot about the using std::swap. Our code base has (for legacy reasons, against my recommendation) global using namespace std with all the problems that it entails... so that's why it works. \$\endgroup\$ – Emily L. Jun 12 '15 at 11:00
  • \$\begingroup\$ @EmilyL. Ok, it makes sense then. That said, if the compiler is smart enough, it may transform 2 * error > dx_abs into error > dx_abs / 2 and take advantage of the fact that dx_abs is const to optimize it out (I don't know whether the two are strictly equivalent, but since we deal with multiples of 2, there shouldn't any precision loss in the transformation). \$\endgroup\$ – Morwenn Jun 12 '15 at 11:37
  • \$\begingroup\$ Hmm that is true, I'll have to check if my compiler can do that... :) \$\endgroup\$ – Emily L. Jun 12 '15 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.