Benchmark of different drawing algorithms. EFLA 5 wins.

line_drawing.cpp

/*
 * g++ --std=c++11 -O3 -DNUM_TEST_RUNS=50000 -pthread -Wall -Werror -Wextra -pedantic -pedantic-errors line_drawing.cpp -o line_drawing
 */

#include <cstdint> // uint8_t
#include <fstream> // std::ofstream
#include <iostream> // std::cout, std::cerr
#include <limits> // std::numeric_limits<>
#include <memory> // std::unique_ptr
#include <utility> // std::move

#include <chrono>
#include <thread>



/*------------------------------------------------------------------------------
 * Benchmark Setup
------------------------------------------------------------------------------*/
#ifndef NUM_TEST_RUNS
    #define NUM_TEST_RUNS 50000
#endif /* NUM_TEST_RUNS */

#ifndef IMAGE_WIDTH
    #define IMAGE_WIDTH 640
#endif /* IMAGE_WIDTH  */

#ifndef IMAGE_HEIGHT
    #define IMAGE_HEIGHT 480
#endif /* IMAGE_HEIGHT  */

namespace chrono = std::chrono;
typedef chrono::steady_clock hr_clock;
typedef hr_clock::time_point hr_time;
typedef chrono::milliseconds hr_prec;

typedef int16_t coord_shrt_t;
typedef int32_t coord_long_t;
constexpr coord_long_t FIXED_BITS = 16;
constexpr coord_long_t MASK_BITS = 0x8000;


/*------------------------------------------------------------------------------
 * Pixels
------------------------------------------------------------------------------*/
struct Pixel
{
    uint8_t r;
    uint8_t g;
    uint8_t b;
};



/*------------------------------------------------------------------------------
 * Save Images
------------------------------------------------------------------------------*/
int save_ppm(const coord_shrt_t w, const coord_shrt_t h, const Pixel* const pPixels, const char* const pFilename)
{
    std::ofstream f(pFilename, std::ofstream::out | std::ofstream::binary);
    if (!f.good())
    {
        return -1;
    }

    // Print the header
    f << "P6\n" << w << ' ' << h << '\n' << 255 << '\n';

    // iterate through the image height, then the width
    for (coord_shrt_t i = 0; i < h; ++i)
    {
        for(coord_shrt_t j = 0; j < w; ++j)
        {
            const Pixel* const pPixel = &pPixels[w * i + j];
            const uint8_t buffer[3]   = {pPixel->r, pPixel->g, pPixel->b};

            f.write(reinterpret_cast<const char*>(buffer), sizeof(buffer));
        }
    }

    f.close();

    return 0;
}



/*------------------------------------------------------------------------------
 * Create Images
------------------------------------------------------------------------------*/
std::unique_ptr<Pixel[]> create_image(const coord_shrt_t width, const coord_shrt_t height)
{
    std::unique_ptr<Pixel[]> pImg{new Pixel[width * height]};

    if (!pImg)
    {
        std::cerr << "Unable to create an " << width << 'x' << height << " image." << std::endl;
        return pImg;
    }

    for (coord_shrt_t i = 0; i < height; ++i)
    {
        for (coord_shrt_t j = 0; j < width; ++j)
        {
            pImg[width * i + j] = Pixel{0, 0, 0};
        }
    }

    return pImg;
}



/*------------------------------------------------------------------------------
 * Apply Pixels to an Image
------------------------------------------------------------------------------*/
inline void plot_pixel(Pixel* const p, const coord_shrt_t w, coord_shrt_t x, coord_shrt_t y, const Pixel& color)
{
    p[w * y + x] = color;
}



/*------------------------------------------------------------------------------
 * Line Drawing: Bresenham Base Case
------------------------------------------------------------------------------*/
void plot_line_bresenham(Pixel* const pImg, coord_shrt_t w, coord_shrt_t x1, coord_shrt_t y1, coord_shrt_t x2, coord_shrt_t y2, const Pixel& color)
{
    const bool steep = std::abs(x1 - x2) < std::abs(y1 - y2);
    if (steep)
    {
        std::swap(x1, y1);
        std::swap(x2, y2);
    }
    
    if (x1 > x2)
    {
        std::swap(x1, x2);
        std::swap(y1, y2);
    }
    
    const coord_shrt_t dx = x2 - x1;
    const coord_shrt_t dy = y2 - y1;
    const coord_shrt_t dErr = std::abs(dy) * 2;
    const coord_shrt_t yErr = (y2 > y1) ? 1 : -1;
    coord_shrt_t currentErr = 0;
    coord_shrt_t y = y1;

    // This if-statement has been pulled out of the main loop in order to avoid
    // branching on intel CPUs. It makes no difference on ARM.
    if (steep)
    {
        for (coord_shrt_t x = x1; x <= x2; ++x)
        {
            plot_pixel(pImg, w, y, x, color);
            currentErr += dErr;

            if (currentErr > dx)
            {
                y += yErr;
                currentErr -= 2 * dx;
            }
        }
    }
    else
    {
        for (coord_shrt_t x = x1; x <= x2; ++x)
        {
            plot_pixel(pImg, w, x, y, color);
            currentErr += dErr;

            if (currentErr > dx)
            {
                y += yErr;
                currentErr -= 2 * dx;
            }
        }
    }
}



/*------------------------------------------------------------------------------
 * Line Drawing: EFLA (Variant 5)
------------------------------------------------------------------------------*/
void plot_line_efla5(Pixel* pImg, coord_shrt_t width, coord_shrt_t x1, coord_shrt_t y1, coord_shrt_t x2, coord_shrt_t y2, const Pixel& color)
{
    coord_long_t shortLen = y2 - y1;
    coord_long_t longLen  = x2 - x1;
    const bool yLonger    = std::abs(shortLen) > std::abs(longLen);
    
    if (yLonger)
    {
        std::swap(shortLen, longLen);
    }
    
    const coord_long_t decInc = (longLen == 0) ? 0 : (((coord_long_t)shortLen << FIXED_BITS) / longLen);

    if (yLonger)
    {
        const coord_long_t fixedX = (coord_long_t)x1 << FIXED_BITS;
        const coord_long_t longLenY = longLen + y1;
            
        if (longLen > 0)
        {
            for (coord_long_t j = MASK_BITS+fixedX; y1 <= longLenY; ++y1)
            {
                plot_pixel(pImg, width, j >> FIXED_BITS, y1, color);
                j += decInc;
            }
            return;
        }
        
        for (coord_long_t j = MASK_BITS+fixedX; y1 >= longLenY; --y1)
        {
            plot_pixel(pImg, width, j >> FIXED_BITS, y1, color);
            j -= decInc;
        }
        return; 
    }

    const coord_long_t fixedY = (coord_long_t)y1 << FIXED_BITS;
    const coord_long_t longLenX = longLen + x1;
    
    if (longLen > 0)
    {
        for (coord_long_t j = MASK_BITS+fixedY; x1 <= longLenX; ++x1)
        {
            plot_pixel(pImg, width, x1, j >> FIXED_BITS, color);
            j += decInc;
        }
        return;
    }
    
    for (coord_long_t j = MASK_BITS+fixedY; x1 >= longLenX; --x1)
    {
        plot_pixel(pImg, width, x1, j >> FIXED_BITS, color);
        j -= decInc;
    }
}



/*------------------------------------------------------------------------------
 * Line Drawing: Bresenham's (Fixed-Point)
------------------------------------------------------------------------------*/
void plot_line_fixed(Pixel* const pImg, coord_shrt_t w, coord_shrt_t x1, coord_shrt_t y1, coord_shrt_t x2, coord_shrt_t y2, const Pixel& color)
{
    union
    {
        coord_long_t i;
        struct
        {
            coord_shrt_t lo;
            coord_shrt_t hi;
        } fx;
    } f, g;

    // allow lines to be more vertical than horizontal
    if (y1 >= y2 && x1 >= x2)
    {
        std::swap(y1, y2);
        std::swap(x1, x2);
    }    
    
    const coord_long_t dx = x2 - x1;
    const coord_long_t dy = y2 - y1;
    constexpr coord_long_t COORD_SHORT_MAX = std::numeric_limits<coord_shrt_t>::max();
    
    if (dx >= dy)
    {
        const coord_long_t m  = dx ? ((coord_long_t)dy << FIXED_BITS) / dx : 0;
        
        f.i = (coord_long_t)y1 << FIXED_BITS;
        
        for (coord_shrt_t x = x1; x <= x2; ++x, f.i += m)
        {
            g.i = f.i + COORD_SHORT_MAX;
            plot_pixel(pImg, w, x, g.fx.hi, color);
        }
    }
    else
    {
        const coord_long_t m  = dy ? ((coord_long_t)dx << FIXED_BITS) / dy : 0;
        
        f.i = (coord_long_t)x1 << FIXED_BITS;
        
        for (coord_shrt_t y = y1; y <= y2; ++y, f.i += m)
        {
            g.i = f.i + COORD_SHORT_MAX;
            plot_pixel(pImg, w, g.fx.hi, y, color);
        }
    }
}



/*------------------------------------------------------------------------------
 * Benchmark Function
------------------------------------------------------------------------------*/
int run_benchmark(
    const std::string& testName,
    coord_shrt_t w,
    coord_shrt_t h,
    void (*line_callback)(Pixel* const, coord_shrt_t, coord_shrt_t, coord_shrt_t, coord_shrt_t, coord_shrt_t, const Pixel&))
{
    const coord_shrt_t w1 = w - 1;
    const coord_shrt_t h1 = h - 1;
    std::unique_ptr<Pixel[]> img = std::move(create_image(w, h));
    hr_time t1, t2;
    
    t1 = hr_clock::now();
    
    for (unsigned t = 0; t < NUM_TEST_RUNS; ++t)
    {
        for (coord_shrt_t i = 0; i < w; i += 10)
        {
            line_callback(img.get(), w, i, 0, w1-i, h1, Pixel{0, 255, 0});
        }
    
        for (coord_shrt_t i = 0; i < h; i += 10)
        {
            line_callback(img.get(), w, 0, i, w1, h1-i, Pixel{255, 0, 0});
        }
    }

    t2 = hr_clock::now();

    std::cout.precision(std::numeric_limits<double>::digits10);
    std::cout
        << testName << " Benchmark: "
        << chrono::duration_cast< hr_prec >(t2 - t1).count() / 1000.0
        << std::endl;

    const std::string filename = testName + ".ppm";
    return save_ppm(w, h, img.get(), filename.c_str());
}



/*------------------------------------------------------------------------------
 * Main
------------------------------------------------------------------------------*/
int main()
{
    std::thread t1(run_benchmark, "EFLA_5",       IMAGE_WIDTH, IMAGE_HEIGHT, &plot_line_efla5);
    std::thread t2(run_benchmark, "Bresenham_FP", IMAGE_WIDTH, IMAGE_HEIGHT, &plot_line_fixed);
    std::thread t3(run_benchmark, "Bresenham",    IMAGE_WIDTH, IMAGE_HEIGHT, &plot_line_bresenham);
    t1.join();
    t2.join();
    t3.join();
    return 0;
}
<