extension/rasterization/line.hpp

0001 //
0002 // Copyright 2020 Olzhas Zhumabek <anonymous.from.applecity@gmail.com>
0003 //
0004 // Use, modification and distribution are subject to the Boost Software License,
0005 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 #ifndef BOOST_GIL_EXTENSION_RASTERIZATION_LINE_HPP
0009 #define BOOST_GIL_EXTENSION_RASTERIZATION_LINE_HPP
0010
0011 #include <boost/gil/extension/rasterization/apply_rasterizer.hpp>
0012 #include <boost/gil/point.hpp>
0013
0014 #include <cmath>
0015 #include <cstddef>
0016 #include <iterator>
0017 #include <vector>
0018
0019 namespace boost { namespace gil {
0020
0021 struct line_rasterizer_t{};
0022
0023 /// \defgroup Rasterization
0024 /// \brief A set of functions to rasterize shapes
0025 ///
0026 /// Due to images being discrete, most shapes require specialized algorithms to
0027 /// handle rasterization efficiently and solve problem of connectivity and being
0028 /// close to the original shape.
0029
0030 /// \defgroup LineRasterization
0031 /// \ingroup Rasterization
0032 /// \brief A set of rasterizers for lines
0033 ///
0034 /// The main problem with line rasterization is to do it efficiently, e.g. less
0035 /// floating point operations. There are multiple algorithms that on paper
0036 /// should reach the same result, but due to quirks of IEEE-754 they don't.
0037 /// Please select one and stick to it if possible. At the moment only Bresenham
0038 /// rasterizer is implemented.
0039
0040 /// \ingroup LineRasterization
0041 /// \brief Rasterize a line according to Bresenham algorithm
0042 ///
0043 /// Do note that if either width or height is 1, slope is set to zero.
0044 /// reference:
0045 /// https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#:~:text=Bresenham's%20line%20algorithm%20is%20a,straight%20line%20between%20two%20points.
0046 struct bresenham_line_rasterizer
0047 {
0048     using type = line_rasterizer_t;
0049
0050     bresenham_line_rasterizer(point_t start, point_t end)
0051         : start_point(start), end_point(end)
0052     {}
0053
0054     std::ptrdiff_t point_count() const noexcept
0055     {
0056         const auto abs_width = std::abs(end_point.x - start_point.x) + 1;
0057         const auto abs_height = std::abs(end_point.y - start_point.y) + 1;
0058         return abs_width > abs_height ? abs_width : abs_height;
0059     }
0060
0061     template <typename OutputIterator>
0062     void operator()(OutputIterator d_first) const
0063     {
0064         // mutable stack copies
0065         point_t start = start_point;
0066         point_t end = end_point;
0067
0068         if (start == end)
0069         {
0070             // put the point and immediately exit, as later on division by zero will
0071             // occur
0072             *d_first = start;
0073             return;
0074         }
0075
0076         auto width = std::abs(end.x - start.x) + 1;
0077         auto height = std::abs(end.y - start.y) + 1;
0078         bool const needs_flip = width < height;
0079         if (needs_flip)
0080         {
0081             // transpose the coordinate system if uncomfortable angle detected
0082             std::swap(width, height);
0083             std::swap(start.x, start.y);
0084             std::swap(end.x, end.y);
0085         }
0086         std::ptrdiff_t const x_increment = end.x >= start.x ? 1 : -1;
0087         std::ptrdiff_t const y_increment = end.y >= start.y ? 1 : -1;
0088         double const slope =
0089             height == 1 ? 0 : static_cast<double>(height) / static_cast<double>(width);
0090         std::ptrdiff_t y = start.y;
0091         double error_term = 0;
0092         for (std::ptrdiff_t x = start.x; x != end.x; x += x_increment)
0093         {
0094             // transpose coordinate system back to proper form if needed
0095             *d_first++ = needs_flip ? point_t{y, x} : point_t{x, y};
0096             error_term += slope;
0097             if (error_term >= 0.5)
0098             {
0099                 --error_term;
0100                 y += y_increment;
0101             }
0102         }
0103         *d_first++ = needs_flip ? point_t{end.y, end.x} : end;
0104     }
0105
0106     point_t start_point;
0107     point_t end_point;
0108 };
0109
0110 namespace detail {
0111
0112 template <typename View, typename Rasterizer, typename Pixel>
0113 struct apply_rasterizer_op<View, Rasterizer, Pixel, line_rasterizer_t>
0114 {
0115     void operator()(
0116         View const& view, Rasterizer const& rasterizer, Pixel const& pixel)
0117     {
0118         std::vector<point_t> trajectory(rasterizer.point_count());
0119         rasterizer(std::begin(trajectory));
0120
0121         for (auto const& point : trajectory)
0122         {
0123             view(point) = pixel;
0124         }
0125     }
0126 };
0127
0128 } //namespace detail
0129
0130 }} // namespace boost::gil
0131
0132 #endif