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

Строю линию по алгоритму Брезенхэма. У меня есть 2 координаты в 3d системе(x, y, z), как вычислить Z для каждой точки линии?
Мой код
void Frame::customLine(int idSegment, intCoord &p1, intCoord &p2, QMap<int, QVector<intCoord>> &boundMap)
{
    const int deltaX = abs(p2.x - p1.x);
    const int deltaY = abs(p2.y - p1.y);
    //const double deltaZ = (abs(p1.z) + abs(p2.z)) / deltaY;

    const int signX = p1.x < p2.x ? 1 : -1;
    const int signY = p1.y < p2.y ? 1 : -1;

    int error = deltaX - deltaY;

    int x = p1.x,
        y = p1.y;

    double tmp;

    while(x != p2.x || y != p2.y)
    {
        const int error2 = error * 2;
        /*
        if(error2 > -deltaY)
        {
            tmp = p1.z + double(p2.z - p1.z) * double(double(x - p1.x) / double(p2.x - p1.x));
        }
        if(error2 < deltaX)
        {
            tmp += p1.z + double(p2.z - p1.z) * double(double(y - p1.y) / double(p2.y - p1.y));
        }
        tmp /= 2;
        */
        
        if (p1.x == p2.x)
        {
            tmp = p1.z + double(p2.z - p1.z) * double(double(y - p1.y) / double(p2.y - p1.y));
        }else
        {
            tmp = p1.z + double(p2.z - p1.z) * double(double(x - p1.x) / double(p2.x - p1.x));
        }
        

        if (tmp >= buffZ[x][y])
        {
            buffFrame[x][y] = idSegment;
            screen.setPixelColor(x, y, 4278190080); // Black
            buffZ[x][y] = tmp;
        }

        if (boundMap.find(x) == boundMap.end())
        {
            intCoord boundCoord;
            boundCoord.y = y;
            boundCoord.z = tmp;
            boundMap.insert(x, {boundCoord, boundCoord});
        }else{
            if (boundMap[x][0].y > y)
            {
                boundMap[x][0].y = y;
                boundMap[x][0].z = tmp;
            }else if(boundMap[x][1].y < y)
            {
                boundMap[x][1].y = y;
                boundMap[x][1].z = tmp;
            }
        }

        if(error2 > -deltaY)
        {
            error -= deltaY;
            x += signX;
        }
        if(error2 < deltaX)
        {
            error += deltaX;
            y += signY;
        }
    }
}
  • Вопрос задан
  • 100 просмотров
Решения вопроса 1
@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-пространства. В этом случае оси даже сортировать не надо будет, для инициализации прокси можно будет обойтись одним тернарным оператором.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы