Ответы пользователя Евгений Шатунов

Как вычислить Z для линии?

Евгений Шатунов @MarkusD Куратор тега C++

все время мелю чепуху :)

Алгоритм Брезенхама для построения линии является очень простым и коротким.
Для работы требуется определить главное и вторичное направление, приращение по этим направлениям и меру коррекции вторичного направления.

При этом, на самом деле, ни кто не требует чтобы какое-либо из направлений (главное или вторичное) было представлено лишь одной осью. Скажем, вторичное направление может быть представлено плоскостью, вдоль которой приращение будет меньше чем по оси главного направления.

Допустим, у нас есть тип 3D-позиции.

struct Vector3i final
{
	int32_t x;
	int32_t y;
	int32_t z;
};

Сам алгоритм Брезенхама стоит выделить в отдельную сущность. Такую сущность можно назвать итератором линии - LineIterator. Такое имя будет хорошо отражать функциональность.
Будем считать так, что для работы алгоритма мы выбираем главную ось 3D-пространства и вторичную плоскость того же пространства. Такой выбор позволяет лишь немного изменить базовый алгоритм для 2D-пространства.
Суть алгоритма Брезенхама проста, но сильно ветвится из-за изначальной неясности относительно выбора главного и вторичного направлений. Поэтому, чтобы не плодить код, нам будет лучше ввести специальный прокси для доступа не к конкретным полям объекта позиции, а к его главной и вторичным осям.

Пример типа AxisProxy

using AxisPointer = int32_t Vector3i::*;

class AxisProxy final
{
public:
    AxisProxy( AxisPointer major_axis, AxisPointer middle_axis, AxisPointer minor_axis)
        : m_major_axis{ major_axis }
        , m_middle_axis{ middle_axis }
        , m_minor_axis{ minor_axis }
    {}

public:
    inline int32_t& AccessMajorAxis( Vector3i& value ) const               { return value.*m_major_axis; };
    inline int32_t& AccessMiddleAxis( Vector3i& value ) const              { return value.*m_middle_axis; };
    inline int32_t& AccessMinorAxis( Vector3i& value ) const               { return value.*m_minor_axis; };

    inline const int32_t& AccessMajorAxis( const Vector3i& value ) const   { return value.*m_major_axis; };
    inline const int32_t& AccessMiddleAxis( const Vector3i& value ) const  { return value.*m_middle_axis; };
    inline const int32_t& AccessMinorAxis( const Vector3i& value ) const   { return value.*m_minor_axis; };

private:
    AxisPointer    m_major_axis    = &Vector3i::x;
    AxisPointer    m_middle_axis   = &Vector3i::y;
    AxisPointer    m_minor_axis    = &Vector3i::z;
};

Линейный итератор должен знать где он находится, куда ему двигаться, знать приращение по вторичному направлению и как это приращение должно изменяться. Еще итератор должен понимать, какое направление движения является главным, а какое - вторичным. Так как вторичным направлением у нас считается пара осей, приращений тоже должно быть два.

Примерное объявление типа LineIterator

class LineIterator final
{
public:
    LineIterator( const Vector3i from, const Vector3i to );

public:
    const Vector3i& operator ++ ();
    const Vector3i operator ++ ( int );

    inline const Vector3i& operator * () const     { return m_current_point; };
    inline const Vector3i* operator -> () const    { return &m_current_point; };

private:
    static inline const int32_t GetCorrectionStepAxis( const int32_t value )   { return std::abs( value ) << 1; };
    static inline const int32_t GetShiftStepAxis( const int32_t value )        { return ( value > 0 ) - ( value < 0 ); };

    void PerformLineStep();

private:
    Vector3i   m_current_point;            // Current position at line.
    Vector3i   m_correction_step;            // Values to change the point corrections.
    Vector3i   m_shift_step;                // The shift step for current point in each iteration.
    int32_t    m_middle_axis_correction;    // The marker for middle axis correction.
    int32_t    m_minor_axis_correction;    // The marker for minor axis correction.
    AxisProxy  m_axis_proxy;                // Point fields proxy.
};

Это - обычный поступательный итератор, каждый шаг которого отображает движение вдоль заданной при конструировании линии. Его операторы будут очень простыми.

Пример кода операторов итератора

const Vector3i& LineIterator::operator ++ ()
{
    PerformLineStep();
    return m_current_point;
}

const Vector3i LineIterator::operator ++ ( int )
{
    Vector3i current_point{ m_current_point };
    PerformLineStep();
    return current_point;
}

С инициализацией будет уже поинтереснее.

Пример кода конструктора итератора

LineIterator::LineIterator( const Vector3i from, const Vector3i to )
    : m_current_point{ from }
{
    const Vector3i line_delta{ to - from };

    m_correction_step  = { GetCorrectionStepAxis( line_delta.x ), GetCorrectionStepAxis( line_delta.y ), GetCorrectionStepAxis( line_delta.z ) };
    m_shift_step       = { GetShiftStepAxis( line_delta.x ), GetShiftStepAxis( line_delta.y ), GetShiftStepAxis( line_delta.z ) };

    AxisPointer axis[3] = { &Vector3i::x, &Vector3i::y, &Vector3i::z };
    std::sort(
        std::begin( axis ), std::end( axis ),
        [this]( const AxisPointer left, const AxisPointer right ) -> bool
        {
            return m_correction_step.*left > m_correction_step.*right;
        }
    );
    m_axis_proxy = { axis[0], axis[1], axis[2] };

    m_middle_axis_correction   = m_axis_proxy.AccessMiddleAxis( m_correction_step ) - ( m_axis_proxy.AccessMajorAxis( m_correction_step ) >> 1 );
    m_minor_axis_correction    = m_axis_proxy.AccessMinorAxis( m_correction_step ) - ( m_axis_proxy.AccessMajorAxis( m_correction_step ) >> 1 );
}

Сперва определяется шаг приращения осей - m_correction_step, на базе которого далее производится сортировка указателей на поля осей вектора. Сортируются указатели по убыванию шага их приращения. Именно таким образом определяется главное и вторичное направления. Порядок указателей осей используется для инициализации экземпляра AxisProxy.
Инициализация двух значений приращения вторичного направления происходит уже с помощью прокси. Начиная с этого этапа нам совершенно безразлично, какие именно оси выбраны в качестве главного или вторичного направлений.

Функция выполнения шага вдоль линии будет очень простой за счет работы с прокси-объектом.

Пример функции шага итератора

void LineIterator::PerformLineStep()
{
    if( m_middle_axis_correction > 0 )
    {
        m_middle_axis_correction -= m_axis_proxy.AccessMajorAxis( m_correction_step );
        m_axis_proxy.AccessMiddleAxis( m_current_point ) += m_axis_proxy.AccessMiddleAxis( m_shift_step );
    }

    if( m_minor_axis_correction > 0 )
    {
        m_minor_axis_correction -= m_axis_proxy.AccessMajorAxis( m_correction_step );
        m_axis_proxy.AccessMinorAxis( m_current_point ) += m_axis_proxy.AccessMinorAxis( m_shift_step );
    }

    m_middle_axis_correction += m_axis_proxy.AccessMiddleAxis( m_correction_step );
    m_minor_axis_correction += m_axis_proxy.AccessMinorAxis( m_correction_step );
    m_axis_proxy.AccessMajorAxis( m_current_point ) += m_axis_proxy.AccessMajorAxis( m_shift_step );
}

Если убрать поле AxisProxy::m_middle_axis из кода и удалить весь код, где на него есть ссылки, то весь оставшийся код будет представлять из себя обычный итератор линии для 2D-пространства. В этом случае оси даже сортировать не надо будет, для инициализации прокси можно будет обойтись одним тернарным оператором.

Войдите на сайт