How to calculate Z for a line?

Question

Mathematics

I build a line according to the Bresenham algorithm. I have 2 coordinates in 3d system(x, y, z), how to calculate Z for each point of the line?

My code

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

Bresenham's algorithm for drawing a line is very simple and short.
To work, it is required to determine the main and secondary direction, the increment in these directions and the measure of correction of the secondary direction.
At the same time, in fact, no one requires that any of the directions (main or secondary) be represented by only one axis. Let's say the secondary direction can be represented by a plane along which the increment will be less than along the axis of the main direction.
Let's say we have a 3D position type.

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

The Bresenham algorithm itself should be singled out as a separate entity. Such an entity can be called a line iterator - LineIterator. Such a name will reflect the functionality well.
We will assume that for the operation of the algorithm we choose the main axis of the 3D space and the secondary plane of the same space. This choice allows only a slight change in the basic algorithm for 2D space.
The essence of Bresenham's algorithm is simple, but strongly branches due to the initial ambiguity regarding the choice of the main and secondary directions. Therefore, in order not to produce code, it would be better for us to introduce a special proxy for access not to specific fields of the position object, but to its main and secondary axes.

AxisProxy type example

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

A linear iterator must know where it is, where it should move, know the increment in the secondary direction, and how that increment should change. The iterator must also understand which direction of movement is primary and which is secondary. Since we consider a pair of axes as a secondary direction, there should also be two increments.

Sample LineIterator Type Declaration

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

This is a normal progressive iterator, each step of which represents movement along the line specified during construction. Its operators will be very simple.

Iterator operator code example

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

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

With initialization it will be more interesting.

Iterator constructor code example

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

First, the increment step of the axes - is determined m_correction_step, on the basis of which the pointers to the fields of the vector axes are further sorted. Pointers are sorted in descending order of their increment step. It is in this way that the main and secondary directions are determined. The order of the axis pointers is used to initialize the AxisProxy.
The initialization of the two increment values ​​of the secondary direction occurs already with the help of the proxy. Starting from this stage, it is completely indifferent to us which particular axes are chosen as the main or secondary directions.
The function to step along the line will be very simple by working with a proxy object.

Iterator step function example

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

If you remove the field AxisProxy::m_middle_axisfrom the code and remove all the code where it is referenced, then all the remaining code will be a regular line iterator for 2D space. In this case, the axes will not even need to be sorted; to initialize the proxy, one ternary operator can be dispensed with.