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

Question

Евгений Якушов @yevgenyyakushov

Как вычислить 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;
        }
    }
}

Вопрос задан более трёх лет назад
115 просмотров

4 комментария

Подписаться 1 Средний 4 комментария

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

Евгений Якушов , аналогично другим осям пробовал делать?
У Брезенхама есть критерий приращения по оси. И этот критерий одинаков для всех осей, как и само приращение.

Написано более трёх лет назад
Евгений Якушов @yevgenyyakushov Автор вопроса
Для x, y работает все. Попытался для z, но что-то не то, там зависимость от x либо y. Вот этот код даёт более менее правильный Z, НО, есть проблема, когда X примерно одинаковый, допустим, p1.x=50 p2.x=53 и по Y разница в 100 пикселей, там линия получается почти ровная по оси Y и в итоге Z имеет одинаковые значения, пока не произойдёт "ступенька".

if (p1.x == p2.x) { tmp = p1.z + double(p2.z - p1.z) * (double(y - p1.y) / double(p2.y - p1.y)); }else { tmp = p1.z + double(p2.z - p1.z) * (double(x - p1.x) / double(p2.x - p1.x)); }
Написано более трёх лет назад
Евгений Шатунов @MarkusD Куратор тега C++

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

Написано более трёх лет назад

Евгений Якушов @yevgenyyakushov Автор вопроса

Евгений Шатунов, случайно наверное удалил..

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;
        }
    }
}

Написано более трёх лет назад

Евгений Якушов , аналогично другим осям пробовал делать?
У Брезенхама есть критерий приращения по оси. И этот критерий одинаков для всех осей, как и само приращение.
Для x, y работает все. Попытался для z, но что-то не то, там зависимость от x либо y. Вот этот код даёт более менее правильный Z, НО, есть проблема, когда X примерно одинаковый, допустим, p1.x=50 p2.x=53 и по Y разница в 100 пикселей, там линия получается почти ровная по оси Y и в итоге Z имеет одинаковые значения, пока не произойдёт "ступенька".

if (p1.x == p2.x) { tmp = p1.z + double(p2.z - p1.z) * (double(y - p1.y) / double(p2.y - p1.y)); }else { tmp = p1.z + double(p2.z - p1.z) * (double(x - p1.x) / double(p2.x - p1.x)); }
Евгений Якушов, не забывай ставить упоминания пользователей. Я чисто случайно сейчас увидел твой комментарий.
Показывай весь код. Пока выглядит так, что ты неправильно реализовал суть алгоритма.
Евгений Шатунов, случайно наверное удалил..

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; } } }

Answer 1 · 2020-12-19 19:50:11

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

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

Допустим, у нас есть тип 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-пространства. В этом случае оси даже сортировать не надо будет, для инициализации прокси можно будет обойтись одним тернарным оператором.

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

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