I’ll be the first to admit, this is a post I wrote mainly to scratch an itch of mine and so may have an audience of approximately 1. Fortunately in my previous life as a physicist I found that approximations can actually encompass many orders of magnitude, so perhaps we’re on to a winner here? Let’s find out.

Introduction

Here’s the problem – in my day job I work on writing software that allows placing objects in (nominally) 2D space. There’s also a third dimension to consider though – the stacking order of objects is also relevant, as it determines which objects appear on top of others. This ordering is usually known as the z-index.

When adding objects or updating their stacking order, it’s nice to be able to only update the object itself, and not the (potentially thousands) of other objects around it. Therefore we need a strategy to pick new z-indices for new objects that won’t conflict with other ones (which also implies using arbitrary-precision indices – see this post from Figma for more on this topic).

For example, in the following case there are 2 objects already present, and we want to add a new one on top of both existing objects, where all z-indices are bounded between zero and one. It’s clear we need and , but which should we pick?

The simplest strategy just places the next object in the middle of the gap between the right-most object and , e.g.:

This looks good! We then add 10 more objects, and the sequence of new z-indices goes like 0.6, 0.8, 0.9, 0.95, 0.975, 0.9875… which is less good – the objects all start being bunched up near , even when there’s plenty of perfectly-good z-axis barely even touched!

This is not just mathematically unsatisfactory, it’s just plain rude to have our objects crammed together when they don’t need to be – surely there’s a better solution?

Simulation

To help find one, let’s write some code – the following is a simple class that allows adding and removing objects from a collection, and uses some provided strategy to create new z-indices:

class ZIndices:
    def __init__(self, get_new_index: Callable[[float, int], float]) -> None:
        self.indices = []
        self.get_new_index = get_new_index

    def add(self):
        N = len(self.indices)
        if N == 0:
            max_index = 0
        else:
          max_index = self.indices[-1]

        new_index = self.get_new_index(max_index, len(self.indices))
        self.indices.append(new_index)

    def remove(self, pos: int):
        if len(self.indices) == 0:
            return
        self.indices.pop(pos)

The simple strategy above might be written as:

def get_new_index(max_index: float, N: float) -> float:
  return 0.5 * (1 + max_index)

We then randomly add and remove objects from this collection for some period of time, and at the end look at the distribution of z-indices.

Initial results

I’ve chosen in the following plots to view the z-indices of the objects as samples from a probability distribution, then plot the effective cumulative distribution function (CDF). If they were all spaced evenly along the z-axis, then the CDF would be a straight line from (0,0) to (1,1).

Any deviation from this straight line indicates a poorly-performing z-index strategy. As we see below, our initial strategy performs as poorly as possible:

Improvements

This is unfortunate. Perhaps we can make some small tweaks – for example, rather than placing the next object in the middle of the gap, we can bias it towards the left of the gap? This corresponds to reducing the ‘weighting’ of the 1 factor in the average – let’s replace it with some variable :

This is a definite improvement – z-indices are no longer crammed towards the right-hand side. However they are still distributed non-uniformly, and also exhibit an f-dependent cutoff – what we need is to spread out new z-indices at different rates depending on the current number of objects :

There are lots of options here – I chose to make a function of such that it starts at some ‘base’ level , and changes with over some scale . I also added some nonlinearity on the sound scientific basis that nothing fun ever happens when everything is linear (just ask everyone that’s ever written a neural network):

This is all well and good, but now I’ve just made myself a 2-parameter problem to deal with. Fortunately these simulations are quick, so we can just run a bunch over a 2D parameter space. We calculate a ‘score’ for each approach based on the area between the measured CDF and the ideal straight-line CDF.

Interestingly the score landscape in this space looks quite smooth, and has a clear minimum at non-zero values of both and (finding non-trivial minima is basically this entire blog).

Picking the optimal values from this (pretty coarse) grid search gives a surprisingly good result:

Yes, there is still some unoccupied room above , but frankly anyone that wants a z-index that high is just trying to compensate for something.

Extensions

This was a pretty satisfying exercise, but there are many other avenues of investigation:

• Can we search over the space of nonlinear functions?
• How much do user modifications of z-index matter, for example ‘move to front’/’back’? (Spoiler: a lot)
• Does the optimal z-index strategy depend on the expected number of objects? The ratio of insertions to deletions?
• Is there some probabilistic Bayesian method that adapts based on the most probable next sequence of actions?

I’m sure this kind of thing has come up before – if you know, leave a comment!

If you want to take a look at some of the code and play with the simulations live, check out the canvas I made here:

Finally, if you’ve read this far you’ve probably enjoyed this post. If you also like to write Typescript/WebGL/React professionally, you might enjoy working with me. Get in touch from my About page if you’d like to know more!