extension/rasterization/ellipse.hpp

0001 //
0002 // Copyright 2021 Prathamesh Tagore <prathameshtagore@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_ELLIPSE_HPP
0009 #define BOOST_GIL_EXTENSION_RASTERIZATION_ELLIPSE_HPP
0010
0011 #include <boost/gil/concepts/pixel.hpp>
0012 #include <boost/gil/extension/rasterization/apply_rasterizer.hpp>
0013 #include <boost/gil/point.hpp>
0014
0015 #include <array>
0016 #include <stdexcept>
0017 #include <vector>
0018
0019 namespace boost { namespace gil {
0020
0021 struct ellipse_rasterizer_t{};
0022
0023 /// \defgroup EllipseRasterization
0024 /// \ingroup Rasterization
0025 /// \brief Ellipse rasterization algorithms.
0026
0027 /// \ingroup EllipseRasterization
0028 /// \brief Performs ellipse rasterization using midpoint algorithm. Initially, program considers
0029 /// origin as center of ellipse and obtains first quadrant trajectory points. After that,
0030 /// it shifts origin to provided co-ordinates of center and then draws the curve.
0031 struct midpoint_ellipse_rasterizer
0032 {
0033     using type = ellipse_rasterizer_t;
0034
0035     /// \brief Creates a midpoint ellipse rasterizer
0036     /// \param center - Point containing positive integer x co-ordinate and y co-ordinate of the
0037     /// center respectively.
0038     /// \param semi_axes - Point containing positive integer lengths of horizontal semi-axis
0039     /// and vertical semi-axis respectively.
0040     midpoint_ellipse_rasterizer(point<unsigned int> center_point,
0041         point<unsigned int> semi_axes_values)
0042         : center(center_point)
0043         , semi_axes(semi_axes_values)
0044     {}
0045
0046     /// \brief Returns a vector containing co-ordinates of first quadrant points which lie on
0047     /// rasterizer trajectory of the ellipse.
0048     auto obtain_trajectory() const
0049         -> std::vector<point_t>
0050     {
0051         // Citation : J. Van Aken, "An Efficient Ellipse-Drawing Algorithm" in IEEE Computer
0052         // Graphics and Applications, vol. 4, no. 09, pp. 24-35, 1984.
0053         // doi: 10.1109/MCG.1984.275994
0054         // keywords: {null}
0055         // url: https://doi.ieeecomputersociety.org/10.1109/MCG.1984.275994
0056         std::vector<point_t> trajectory_points;
0057         std::ptrdiff_t x = semi_axes[0], y = 0;
0058
0059         // Variables declared on following lines are temporary variables used for improving
0060         // performance since they help in converting all multiplicative operations inside the while
0061         // loop into additive/subtractive operations.
0062         long long int const t1 = semi_axes[0] * semi_axes[0];
0063         long long int const t4 = semi_axes[1] * semi_axes[1];
0064         long long int t2, t3, t5, t6, t8, t9;
0065         t2 = 2 * t1, t3 = 2 * t2;
0066         t5 = 2 * t4, t6 = 2 * t5;
0067         long long int const t7 = semi_axes[0] * t5;
0068         t8 = 2 * t7, t9 = 0;
0069
0070         // Following variables serve as decision parameters and help in choosing the right point
0071         // to be included in rasterizer trajectory.
0072         long long int d1, d2;
0073         d1 = t2 - t7 + t4 / 2, d2 = t1 / 2 - t8 + t5;
0074
0075         while (d2 < 0)
0076         {
0077             trajectory_points.push_back({x, y});
0078             y += 1;
0079             t9 += t3;
0080             if (d1 < 0)
0081             {
0082                 d1 += t9 + t2;
0083                 d2 += t9;
0084             }
0085             else
0086             {
0087                 x -= 1;
0088                 t8 -= t6;
0089                 d1 += t9 + t2 - t8;
0090                 d2 += t5 + t9 - t8;
0091             }
0092         }
0093         while (x >= 0)
0094         {
0095             trajectory_points.push_back({x, y});
0096             x -= 1;
0097             t8 -= t6;
0098             if (d2 < 0)
0099             {
0100                 y += 1;
0101                 t9 += t3;
0102                 d2 += t5 + t9 - t8;
0103             }
0104             else
0105             {
0106                 d2 += t5 - t8;
0107             }
0108         }
0109         return trajectory_points;
0110     }
0111
0112     /// \brief Fills pixels returned by function 'obtain_trajectory' as well as pixels
0113     /// obtained from their reflection along major axis, minor axis and line passing through
0114     /// center with slope -1 using colours provided by user.
0115     /// \param view - Gil view of image on which the elliptical curve is to be drawn.
0116     /// \param pixel - Pixel value for the elliptical curve to be drawn.
0117     /// \param trajectory_points - Constant vector specifying pixel co-ordinates of points lying
0118     ///                            on rasterizer trajectory.
0119     /// \tparam View - Type of input image view.
0120     /// \tparam Pixel - Type of pixel. Must be compatible to the pixel type of the image view
0121     template<typename View, typename Pixel>
0122     void draw_curve(View& view, Pixel const& pixel,
0123         std::vector<point_t> const& trajectory_points) const
0124     {
0125         using pixel_t = typename View::value_type;
0126         if (!pixels_are_compatible<pixel_t, Pixel>())
0127         {
0128             throw std::runtime_error("Pixel type of the given image is not compatible to the "
0129                 "type of the provided pixel.");
0130         }
0131
0132         // mutable center copy
0133         point<unsigned int> center2(center);
0134         --center2[0], --center2[1]; // For converting center co-ordinate values to zero based indexing.
0135         for (point_t pnt : trajectory_points)
0136         {
0137             std::array<std::ptrdiff_t, 4> co_ords = {center2[0] + pnt[0],
0138             center2[0] - pnt[0], center2[1] + pnt[1], center2[1] - pnt[1]
0139             };
0140             bool validity[4]{};
0141             if (co_ords[0] < view.width())
0142             {
0143                 validity[0] = true;
0144             }
0145             if (co_ords[1] >= 0 && co_ords[1] < view.width())
0146             {
0147                 validity[1] = true;
0148             }
0149             if (co_ords[2] < view.height())
0150             {
0151                 validity[2] = true;
0152             }
0153             if (co_ords[3] >= 0 && co_ords[3] < view.height())
0154             {
0155                 validity[3] = true;
0156             }
0157
0158             if (validity[0] && validity[2])
0159             {
0160                 view(co_ords[0], co_ords[2]) = pixel;
0161             }
0162             if (validity[1] && validity[2])
0163             {
0164                 view(co_ords[1], co_ords[2]) = pixel;
0165             }
0166             if (validity[1] && validity[3])
0167             {
0168                 view(co_ords[1], co_ords[3]) = pixel;
0169             }
0170             if (validity[0] && validity[3])
0171             {
0172                 view(co_ords[0], co_ords[3]) = pixel;
0173             }
0174         }
0175     }
0176
0177     /// \brief Calls the function 'obtain_trajectory' and then passes obtained trajectory points
0178     ///        in the function 'draw_curve' for drawing the desired ellipse.
0179     /// \param view - Gil view of image on which the elliptical curve is to be drawn.
0180     /// \param pixel - Pixel value for the elliptical curve to be drawn.
0181     /// \tparam View - Type of input image view.
0182     /// \tparam Pixel - Type of pixel. Must be compatible to the pixel type of the image view
0183     template<typename View, typename Pixel>
0184     void operator()(View& view, Pixel const& pixel) const
0185     {
0186         draw_curve(view, pixel, obtain_trajectory());
0187     }
0188
0189     point<unsigned int> center;
0190     point<unsigned int> semi_axes;
0191 };
0192
0193 namespace detail {
0194
0195 template <typename View, typename Rasterizer, typename Pixel>
0196 struct apply_rasterizer_op<View, Rasterizer, Pixel, ellipse_rasterizer_t>
0197 {
0198     void operator()(
0199         View const& view, Rasterizer const& rasterizer, Pixel const& pixel)
0200     {
0201         rasterizer(view, pixel);
0202     }
0203 };
0204
0205 } //namespace detail
0206
0207 }} // namespace boost::gil
0208
0209 #endif