Алгоритм Брезенхама для построения линии является
очень простым и коротким.
Для работы требуется определить главное и вторичное направление, приращение по этим направлениям и меру коррекции вторичного направления.
При этом, на самом деле, ни кто не требует чтобы какое-либо из направлений (главное или вторичное) было представлено лишь одной осью. Скажем, вторичное направление может быть представлено плоскостью, вдоль которой приращение будет меньше чем по оси главного направления.
Допустим, у нас есть тип 3D-позиции.
struct Vector3i final
{
int32_t x;
int32_t y;
int32_t z;
};
Сам алгоритм Брезенхама стоит выделить в отдельную сущность. Такую сущность можно назвать итератором линии -
LineIterator. Такое имя будет хорошо отражать функциональность.
Будем считать так, что для работы алгоритма мы выбираем главную ось 3D-пространства и вторичную плоскость того же пространства. Такой выбор позволяет лишь немного изменить базовый алгоритм для 2D-пространства.
Суть алгоритма Брезенхама проста, но сильно ветвится из-за изначальной неясности относительно выбора главного и вторичного направлений. Поэтому, чтобы не плодить код, нам будет лучше ввести специальный прокси для доступа не к конкретным полям объекта позиции, а к его главной и вторичным осям.
Пример типа AxisProxyusing 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;
};
Линейный итератор должен знать где он находится, куда ему двигаться, знать приращение по вторичному направлению и как это приращение должно изменяться. Еще итератор должен понимать, какое направление движения является главным, а какое - вторичным. Так как вторичным направлением у нас считается пара осей, приращений тоже должно быть два.
Примерное объявление типа LineIteratorclass 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-пространства. В этом случае оси даже сортировать не надо будет, для инициализации прокси можно будет обойтись одним тернарным оператором.