CoolVLViewer/include/boost/gil/extension/rasterization/ellipse.hpp

//
// Copyright 2021 Prathamesh Tagore <[email protected]>
//
// Use, modification and distribution are subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
#ifndef BOOST_GIL_EXTENSION_RASTERIZATION_ELLIPSE_HPP
#define BOOST_GIL_EXTENSION_RASTERIZATION_ELLIPSE_HPP

#include <boost/gil/concepts/pixel.hpp>
#include <boost/gil/extension/rasterization/apply_rasterizer.hpp>
#include <boost/gil/point.hpp>

#include <array>
#include <stdexcept>
#include <vector>

namespace boost { namespace gil {

struct ellipse_rasterizer_t{};

/// \defgroup EllipseRasterization
/// \ingroup Rasterization
/// \brief Ellipse rasterization algorithms.

/// \ingroup EllipseRasterization
/// \brief Performs ellipse rasterization using midpoint algorithm. Initially, program considers
/// origin as center of ellipse and obtains first quadrant trajectory points. After that,
/// it shifts origin to provided co-ordinates of center and then draws the curve.
struct midpoint_ellipse_rasterizer
{
    using type = ellipse_rasterizer_t;

    /// \brief Creates a midpoint ellipse rasterizer
    /// \param center - Point containing positive integer x co-ordinate and y co-ordinate of the
    /// center respectively.
    /// \param semi_axes - Point containing positive integer lengths of horizontal semi-axis
    /// and vertical semi-axis respectively.
    midpoint_ellipse_rasterizer(point<unsigned int> center_point,
        point<unsigned int> semi_axes_values)
        : center(center_point)
        , semi_axes(semi_axes_values)
    {}

    /// \brief Returns a vector containing co-ordinates of first quadrant points which lie on
    /// rasterizer trajectory of the ellipse.
    auto obtain_trajectory() const
        -> std::vector<point_t>
    {
        // Citation : J. Van Aken, "An Efficient Ellipse-Drawing Algorithm" in IEEE Computer
        // Graphics and Applications, vol. 4, no. 09, pp. 24-35, 1984.
        // doi: 10.1109/MCG.1984.275994
        // keywords: {null}
        // url: https://doi.ieeecomputersociety.org/10.1109/MCG.1984.275994
        std::vector<point_t> trajectory_points;
        std::ptrdiff_t x = semi_axes[0], y = 0;

        // Variables declared on following lines are temporary variables used for improving
        // performance since they help in converting all multiplicative operations inside the while
        // loop into additive/subtractive operations.
        long long int const t1 = semi_axes[0] * semi_axes[0];
        long long int const t4 = semi_axes[1] * semi_axes[1];
        long long int t2, t3, t5, t6, t8, t9;
        t2 = 2 * t1, t3 = 2 * t2;
        t5 = 2 * t4, t6 = 2 * t5;
        long long int const t7 = semi_axes[0] * t5;
        t8 = 2 * t7, t9 = 0;

        // Following variables serve as decision parameters and help in choosing the right point
        // to be included in rasterizer trajectory.
        long long int d1, d2;
        d1 = t2 - t7 + t4 / 2, d2 = t1 / 2 - t8 + t5;

        while (d2 < 0)
        {
            trajectory_points.push_back({x, y});
            y += 1;
            t9 += t3;
            if (d1 < 0)
            {
                d1 += t9 + t2;
                d2 += t9;
            }
            else
            {
                x -= 1;
                t8 -= t6;
                d1 += t9 + t2 - t8;
                d2 += t5 + t9 - t8;
            }
        }
        while (x >= 0)
        {
            trajectory_points.push_back({x, y});
            x -= 1;
            t8 -= t6;
            if (d2 < 0)
            {
                y += 1;
                t9 += t3;
                d2 += t5 + t9 - t8;
            }
            else
            {
                d2 += t5 - t8;
            }
        }
        return trajectory_points;
    }

    /// \brief Fills pixels returned by function 'obtain_trajectory' as well as pixels
    /// obtained from their reflection along major axis, minor axis and line passing through
    /// center with slope -1 using colours provided by user.
    /// \param view - Gil view of image on which the elliptical curve is to be drawn.
    /// \param pixel - Pixel value for the elliptical curve to be drawn.
    /// \param trajectory_points - Constant vector specifying pixel co-ordinates of points lying
    ///                            on rasterizer trajectory.
    /// \tparam View - Type of input image view.
    /// \tparam Pixel - Type of pixel. Must be compatible to the pixel type of the image view
    template<typename View, typename Pixel>
    void draw_curve(View& view, Pixel const& pixel,
        std::vector<point_t> const& trajectory_points) const
    {
        using pixel_t = typename View::value_type;
        if (!pixels_are_compatible<pixel_t, Pixel>())
        {
            throw std::runtime_error("Pixel type of the given image is not compatible to the "
                "type of the provided pixel.");
        }

        // mutable center copy
        point<unsigned int> center2(center);
        --center2[0], --center2[1]; // For converting center co-ordinate values to zero based indexing.
        for (point_t pnt : trajectory_points)
        {
            std::array<std::ptrdiff_t, 4> co_ords = {center2[0] + pnt[0],
            center2[0] - pnt[0], center2[1] + pnt[1], center2[1] - pnt[1]
            };
            bool validity[4]{};
            if (co_ords[0] < view.width())
            {
                validity[0] = true;
            }
            if (co_ords[1] >= 0 && co_ords[1] < view.width())
            {
                validity[1] = true;
            }
            if (co_ords[2] < view.height())
            {
                validity[2] = true;
            }
            if (co_ords[3] >= 0 && co_ords[3] < view.height())
            {
                validity[3] = true;
            }

            if (validity[0] && validity[2])
            {
                view(co_ords[0], co_ords[2]) = pixel;
            }
            if (validity[1] && validity[2])
            {
                view(co_ords[1], co_ords[2]) = pixel;
            }
            if (validity[1] && validity[3])
            {
                view(co_ords[1], co_ords[3]) = pixel;
            }
            if (validity[0] && validity[3])
            {
                view(co_ords[0], co_ords[3]) = pixel;
            }
        }
    }

    /// \brief Calls the function 'obtain_trajectory' and then passes obtained trajectory points
    ///        in the function 'draw_curve' for drawing the desired ellipse.
    /// \param view - Gil view of image on which the elliptical curve is to be drawn.
    /// \param pixel - Pixel value for the elliptical curve to be drawn.
    /// \tparam View - Type of input image view.
    /// \tparam Pixel - Type of pixel. Must be compatible to the pixel type of the image view
    template<typename View, typename Pixel>
    void operator()(View& view, Pixel const& pixel) const
    {
        draw_curve(view, pixel, obtain_trajectory());
    }

    point<unsigned int> center;
    point<unsigned int> semi_axes;
};

namespace detail {

template <typename View, typename Rasterizer, typename Pixel>
struct apply_rasterizer_op<View, Rasterizer, Pixel, ellipse_rasterizer_t>
{
    void operator()(
        View const& view, Rasterizer const& rasterizer, Pixel const& pixel)
    {
        rasterizer(view, pixel);
    }
};

} //namespace detail

}} // namespace boost::gil

#endif