I’m working on a diagram toolkit on top of Qt Graphics View Framework and faced a problem: implementing an efficient bring to front mechanism. There’s the ideas and magic behind it.

The easiest way to implement bring to front mechanic is to use QGraphicsItem::collidingItems and set the z value above the maximal z value of all colliding items. Doing so is expensive because we query the scene all the time. For example, imagine we are moving an object across the screen, then we have to perform this operation each time we receive a mouse move event. So let’s do it better: in constant time.

The basic idea

A solution is to store the maximal z value, then use this value when bringing the object to front. This is a step forward to what we want. The first attempt will be:

class DiagramScene
    : public QGraphicsScene
{
public:
...
    void bringToFront(ItemBase *item) { 
        item->setZValue(mDepth); 
        mDepth += STEP;
    }
...
private:
    qreal mDepth;
};

The first issue we face is that qreal is a floating point number and by definition the distribution of values is not linear (see wikipedia). The step STEP used above do not give us next floating point number, we cannot use a constant floating point number to increment.

Computing next floating point number

(We will only consider positive floating point numbers)

Floating point numbers are encoded by a sign bit, an exponent field, and a mantissa (or significand). The floating point number is written where is . One exception is zero which is encoded by all bits set to 0.

This implies that the smallest floating point number has exponent value 0 and mantissa 1, the next has mantissa 2, etc. When the mantissa field is full then we increment the exponent by one and continue.

The interesting point is that the function that maps the integer representation to the floating point representation is monotonous. So if we have two integers such that a < b and interpret them as floats the inequality still holds *reinterpret_cast<float*>(&a) < *reinterpret_cast<float*>(&b)

So now we can write the next float function

float next(float value) {
    int tmp = *reinterpret_cast<int*>(&value);
    tmp++;
    return *reinterpret_cast<float*>(&tmp);
}

However it has to be stressed that qreal is not a float, it is a 32bit or 64bit floating point number depending on platform. We have to select the right type, I do it by meta programming but won’t explain details here.

qreal next(qreal value) {
    auto tmp = *reinterpret_cast<TIntRepr::integer_t*>(&value);
    tmp++;
    return *reinterpret_cast<qreal*>(&tmp);
}

Adding layers

The last enhancement I wanted is to use four layers: bottom, mid, top, and overlay. Each item belongs to a layer and bringing it to front cannot put it above an item in the layer on top of it.

To do so, we use an array of max z values so we have to slice it adequately. Slicing max qreal won’t work, remember the distribution is not linear. However slicing the maximum integer representation will work and will give us slices of same cardinality.

TIntRepr<qreal>::integer_t positiveSplit(int slices)
{
    auto tmp = std::numeric_limits<qreal>::max();
    return (*reinterpret_cast<TIntRepr<qreal>::integer_t*>(&tmp)) / slices;
}

Now we can initialize our array of layers

auto integer_repr = positiveSplit(DIAGRAM_LAYER_MAX);
mDepth[DIAGRAM_BOT_LAYER]     = 0;
tmp  = integer_repr;
mDepth[DIAGRAM_MID_LAYER]     = *reinterpret_cast<qreal*>(&tmp);
tmp += integer_repr;
mDepth[DIAGRAM_TOP_LAYER]     = *reinterpret_cast<qreal*>(&tmp);
tmp += integer_repr;
...

Last thing to do is to ensure that we do not reach another layer, to do so we can keep the initial splits then each time we bring an item to front check that the new z is not in the layer above. This remains constant time. In case we reach another layer, we can perform a normalization step that sets minimal Z values with respect to current stacking.