Ergonomic z-order layers for 2D graphics (and UI?)

[alice-i-cecile]

What problem does this solve or what need does it fill?

Currently, we can control the relative position of 2D sprites by manually setting their z-value. This technically works, but requires setting and updating magic numbers scattered throughout the codebase.

When creating a game, you'll often want to specify things like "all in-game UI elements occur on top" or "units are drawn above terrain". Layers provide a sensible, comprehensible way to think about this in a single place.

What solution would you like?

To me, a good solution to this has the following properties:

1. A single, central source of truth which controls the relative positions of different varieties of sprites.
2. Easy initialization of freshly created sprites on a specific layer.
3. Ability to move sprites between layers. You should be able to move sprites to a specific layer, up / down one layer, and to the top or bottom-most layer.
4. Support for nested sublayers.
5. Changing the position of one layer doesn't require changes to any other layer.
6. Layer names must be unique.

I'm not exactly sure what such a solution would look like in practice; I plan to explore it in the comments below. Others are very welcome to comment with proposed solutions as well.

In addition, we need explicit, well-documented rules for what happens to sibling sprites that overlap and share a z-value.

What alternative(s) have you considered?

If a good-enough solution can be created without touching engine code, adding an example to the examples folder would likely be entirely sufficient to resolve this issue.

Additional context

This could be useful for customizing the ordering of various UI elements as well (see #254), depending on the exact pattern we use for constructing it. A builder pattern can obviate the need for this (especially if we have a single rooted tree), but 2D graphics can be used to create sprites in much more diverse fashions.

[alice-i-cecile]

Enum-based layers

The natural starting point is an enum, as we have a fixed number of cases to handle. If we derive Ord, we get a nice automatic ordering that follows the order laid out in the code. Add in a nice function to convert that ordering to a z coordinate value and I think we have a basic solution.

This implies that we want a Layers trait, that users can derive for their own enum.

Working through the criteria:

1. Yes, update your custom layer enum.
2. Yes, add a get_z method to the Layers trait, or have a From or Into impl to handle the conversion.
3. Moving sprites to a specific layer is trivial via 2. We would need a reverse conversion method to find the layer that a particular sprite is on, as well as a layer_above, layer_below, top_layer and bottom_layer method. We could use the DoubleEndedIter trait for this, which would get us all that functionality and more.
4. The natural way to do this would be to use a nested enum. This would need to be declared separately. I'm not entirely sure we could get the derive trick working with this.
5. This works perfectly: reorganize your code and everything updates automatically.
6. We get this for free.

Conclusions

1. An enum-based solution would likely fulfill all or almost all of our functional criteria in practice.
2. We should be able to expose this to our end users ergonomically with a derive.
3. There's too much useful, moderately complex functionality for this to be ergonomic to write by hand, as discussed in the alternatives suggestion above.
4. These could not be dynamically constructed at run time, likely seriously limiting their usefulness for a UI solution.
5. The compile-time checking of layer names is very convenient, and is likely nearly unique to this solution.

[alice-i-cecile]

Double-ended struct layers

Building on the idea that most of the functionality that we want is covered by the DoubleEndedIter trait, we could instead use a Layers struct that uses something like VecDeque for its internal storage.

Criteria:

1. Yes, initialize your Layers struct with global visibility (probably as a resource?), and then manually construct the list with string literals.
2. This would require a way to lookup layers by name. This could be done with a hashmap, but it's probably faster to just linearly search through the dozen or so layers.
3. Exactly the same as the Enum solution above. No issues here.
4. Nested sublayers would be a bit tricky, but basically feasible. You'd probably need a custom data structure, rather than using a VecDeque, but that's not too bad since performance concerns are completely negligible.
5. This works just fine :)
6. We'd have to enforce this upon creation / layer insertion.

Conclusions

1. This is a bit simpler than the enum solution for the end user (just make a resource of the appropriate type), but probably a bit harder to implement.
2. We may want to make this a parametric struct if we expect users to regularly need multiple different versions of this, so then it plays nicely with the resource querying system. This comes with other problems (namely how do they interact?), so this is probably wrong. You may want to have two identical 2dLayers and UiLayers structs though.
3. Implementing nested sublayers is almost certainly easier than the enum solution.
4. Unlike the enum-based solution, you can create and modify these at run time. This is a bit of a loss for the "single source of truth" aspect, but can provide useful functionality during gameplay
5. Conclusion 4 makes it much more suitable for solving the UI ordering problem.

[alice-i-cecile]

HashMap-based layers

The idea is obvious: store a HashMap from Layer to f32 (the z value), then look it up when you want to use it.

Criteria:

1. Not really. You have to set the z-values manually, which is error-prone and doesn't immediately reveal the relative order of the layers.
2. Yes.
3. Moving sprites to a specific layer is trivial. Moving it to a layer above / below requires a bit of code, but is still pretty easy with a search of the values.
4. You could probably get this working, but it would need a wrapper.
5. You can technically do this by subdividing the f32s, nearly without end, and then picking a value between your previous two keys. This is something of a hack however, and frustrating to do by hand.
6. You would have to enforce this in a wrapper struct: default behavior is just to overwrite if the user attempts to add a duplicate key.

Conclusions

1. You could probably get away with this for simple projects, but it seems less robust than other solutions.
2. Manually handling z-values really sucks when you only ever care about relative ordering.
3. The ordering of the declared struct and the ordering of the layers doesn't automatically match, which makes it much harder to understand at a glance.
4. Even if this was the underlying data representation, you'd still likely want a convenience wrapper.
5. Nested sublayers is definitely the hardest criteria to meet.

[alice-i-cecile]

This is discussed further in #1211, with a working implementation for UI only.

[tigregalis]

I made a proof of concept that involved automatic subdivision of Z-space evenly among its children (and their children, and so on).

The API was a Layer component to which you gave it a specific "thickness" (defined in terms of its "front" and "back" Z coordinates in world space), and a "depth" (its order relative to its siblings), and used the Parent/Children relationships to subdivide that thickness among each of its children, and the order defined by the depth for the children, to update the entity's GlobalTransform component.

Something like:

struct Layer {
    front: f32, // this is only relevant to the root layer
    back: f32, // this is only relevant to the root layer
    depth: f32, // this is only relevant to non-root layers
}

#[derive(Bundle)]
struct LayerBundle {
    transform: Transform,
    global_transform: GlobalTransform,
    layer: Layer,
}

An illustration of this (before I tried implementing it, so not exactly what I made):

Cons are that it wasn't particularly ergonomic (I might have avoided using Parent/Child relationships and instead defined my own relationships), doesn't easily address each of your 6 criteria (but could probably be adapted to), and you'll eventually run into floating point precision issues with enough nesting of layers (maybe around 20 levels deep?), plus I wasn't sure of the performance.

However, I'm wondering now whether this can simply be data passed to and processed by the shader instead, i.e. just provide the metadata and let the GPU paint the layers correctly. I think this is feasible, and would be more performant than the other solutions, and may inform a possible API.

[Davier]

I made a proof of concept that involved automatic subdivision of Z-space evenly among its children (and their children, and so on).

That was tried in #1211 and the floating points precision issues already appeared for about 10 layers (with 100 to 150 entities). I don't think it's viable, unfortunately.

[tigregalis]

I made a proof of concept that involved automatic subdivision of Z-space evenly among its children (and their children, and so on).

That was tried in #1211 and the floating points precision issues already appeared for about 10 layers (with 100 to 150 entities). I don't think it's viable, unfortunately.

What approach do you make use of now?

[Davier]

Entities are part of stacking contexts. In the default case a context contains an entity and its children, but it can get arbitrarily complex using the ZIndex::Auto property. Stacking contexts are cached, and rebuild/sorted when any entity that is part of it changes. When any context is changed, the z transform of all UI entities is reset, each at a constant interval over the previous. I could not find a simple way to make incremental updates to transforms.

[Kolsky]

What solution would you like?
...
4. Support for nested sublayers

May I ask how nested sublayers are laid out? Can they be nested many levels deep or only one level, what relations exist between children and parent except additional convenient separation, may a parent be a logical element of its children set or it should have a special treatment? Sorry for dumb questions, I'm not on good terms with UI, but they're important for me in implementing enum-based PoC.

[alice-i-cecile]

@Kolsky these are great questions! Let me think about the options:

1. Nesting levels: IMO nesting indefinitely is desired: you want to be able to freely move and insert layer-trees appropriately.
2. Parent and child shared behavior: For the MVP, I expect that layers would just be a tie-breaker for determining which sprite is layered on top of the others. Down the line, I would expect users to want to be able to mass-manipulate all entities on a specific layer in flexible ways, so being able to extract the entity <-> layer information is important in both directions. See Entity groups #1592 for a broader discussion of this sort of design.
3. Can a parent be a member of its child set: I'm not sure I understand what you're asking here, but I'm very much leaning towards no. My broader vision here is that you want a tree structure for the layers, with each entity with a sprite (or similar) component belonging to exactly one layer.

As a heads up, I expect that relations (vaguely described in #1627 and #1527) will serve as an excellent tool for implementing this, although prototypes are very welcome to see if it's worth pursuing. In discussion with @BoxyUwU, the general approach would be:

1. Each layer is an entity with the Layer marker component and a nice LayerLabel field (see e.g. SystemLabel for how this should be done).
2. Each entity with a Sprite component also has an InLayer relation that points to a specific layer.
3. One layer has a RootLayer marker component, marking the root of the layer tree.
4. Each layer describes its connections in the hierarchy using parent / child relations that are specialized for layers (i.e. don't set transforms automatically).
5. You can add components to each Layer entity such as Transparency to set properties of all entities associated with that layer, and extend this behavior with your own systems.

For now, you'd be able to comfortably implement the same design using components that wrap an Entity (see Bevy's parent-child code for an example), rather than the yet-to-be-written Relation type, and easily migrate once Relations land.

[Kolsky]

So I've made a procedural macro for enums, it's available at https://github.com/Kolsky/syn_derive_layers.
You can nest it as much as you need to by deriving Layers, which can be applied to enums with unit (has the name only) or unnamed 1-tuple variants containing other Layers enum, and the trait itself is unsafe to implement manually. Also there is a Root marker trait, it can only be applied at the top level. The first enum variant, if any, can only be the unit one, if enum isn't Root. With that saying:

1. Any impl of Layers automatically gets fns to_num and try_from_num: they assign ordinal number based on field order, as you would expect from generalized numeral system. Note that, however, A::C(C::E).to_num() from enum A { B, C(C), D } isn't equal to C::E.to_num() from enum C { E, F }, as there is no assumption whether C is contained in A or any other enum.
2. If type T isn't marked as Root, its first variant is a parent layer which can be constructed with T::try_from_num(0).unwrap(). T: ! is exception, though it cannot be constructed anyway.
3. As Layers fns are essentially pure and the size is constant, array mapping can be easily built if you would require Copy for it.

get_z is fairly trivial with f32::from_bits. Compile error messages may be a bit cryptic at times, but I've tried to make them clear enough. The rest is also trivial, as @alice-i-cecile have said already. Hope this helps.

[Davier]

I think using enums is problematic since they are static, we should probably support a dynamic number of layers. I would even argue for a total ordering between every Sprite entity to ensure there is no z fighting.

Do we want to use the same z ordering system for sprites and UI? If so an implementation of the z-index property like in #1211 is a good candidate.

[StarArawn]

@alice-i-cecile I just ran across this issue when dealing with an isometric tilemap rendering bug. I don't think the proposed solutions here address the issue of having multiple passes(different shaders).

Currently in bevy 2D passes are treated as a group of render calls that are sorted by z values. There is no mechanism for sorting draw calls across passes(I'm not sure we should allow this as well because of slowdowns..). One solution is to rely on the depth buffer. That might have issues with transparency though..

With isometric rendering you'll want to render tiles from the bottom layer up and from the top down.

[alice-i-cecile]

You're totally right 🤔 I'd written this before the fancy rendering infrastructure was in place (or I knew anything about rendering), but this needs to be carefully considered.

[colepoirier]

If using InLayer relations, I believe we could store the z-order of the layers or the effective Ord of the InLayer relations in a struct LayerOrder(Vec<Entity>). This allows for easy insertion between layers and reordering relative to other layers. The solution for how to do this in ‘reality‘ i.e. the transform is probably set for each ‘tier’ of sublayers some maximum number of layers that can be allocated between that and the next layer in that same tier, and error if this maximum is exceeded. This seems like a statistical distribution binning problem so someone with a stats background or able to think this through better than me could probably come up with a solution that would work in 99.999% of cases. I believe this solution would also take into account the float precision issue bjorn encountered. Indeed, we probably need someone with a numerical analysis background to give insight into how to solve this problem because floating point and IEEE754.

[alice-i-cecile]

I wrote up a quick user-implementable workaround for this today:

enum Layer {
   Background(i8),
   Foreground(i8),
}

fn update_z_coordinate_based_on_layer(query: Query<(&mut Transform, &Layer), Changed<Layer>){
  for (mut transform, layer) {
    transform.translation.z = match layer {
      Layer::Background(order_in_layer) => -1. + order_in_layer as f32 / 1000.,
      Layer::Foreground(order_in_layer) => 0. + order_in_layer as f32 / 1000.,
    }
  }
}

The strategy is pretty simple: just slice up your z space. It still relies on a bit of global ordering, but it should be relatively efficient and the performance should be fine.

[colepoirier]

I wrote up a quick user-implementable workaround for this today:

enum Layer {
   Background(i8),
   Foreground(i8),
}

fn update_z_coordinate_based_on_layer(query: Query<(&mut Transform, &Layer), Changed<Layer>){
  for (mut transform, layer) {
    transform.translation.z = match layer {
      Layer::Background(order_in_layer) => -1. + order_in_layer as f32 / 1000.,
      Layer::Foreground(order_in_layer) => 0. + order_in_layer as f32 / 1000.,
    }
  }
}

The strategy is pretty simple: just slice up your z space. It still relies on a bit of global ordering, but it should be relatively efficient and the performance should be fine.

I like this a lot! I think we will need something more sophisticated to handle runtime insertion of layers between two layers that are sequential.

For example in pseudo-code:

fn insert_layer_between() {
    // layers that already exist
    // let layer_a = Layer::Foreground(1);
    // let layer_b = Layer::Foreground(2);

    // I want to insert layer_c between layer_a and layer_b, how would I do that, especially if there were not just two layers but dozens
    let layer_c = Layer::insert_after(layer_a);
}

After the insertion of layer_c, it should have the value of Layer::Foreground(2), and layer_b would have the value of Layer::Foreground(3), or more properly expressed an internal value of n+1… or something. I hope this demonstrates the complex problem I’m thinking about adequately.

[alice-i-cecile]

I absolutely agree @colepoirier; you'll need to be able to reshuffle all of the coordinates to accommodate new layers if needed, and you'll want to space things out by default.

I also think sublayers are also critical (at least one layer). These are really critical when working with similar flows in graphics programs IME.

[colepoirier]

I also think sublayers are also critical (at least one layer). These are really critical when working with similar flows in graphics programs IME.

I think a sane default of 'subspace' would be... 10? Or perhaps a recursive subspace of that divides in two, and has a depth of.. 3? 4? 8? Idk, I wonder how we would determine optimal defaults experimentally, and how/if the defaults could be configured for layer-heavy apps like 2d CAD and 2d drawing? I also wonder what existing layering implementations do and how we can learn from them (i.e. html layers, photoshop/illustrator layer UX and internal implementation, or their FOSS alternatives). Are there other existing applications that use this kind of complex layering that you think would be good to look at to aid our design process?

I also have the intuition that this effectively a data structure problem that has analogues in different domains, and therefore is perhaps a well-know problem that has an existing optimal design. Hopefully someone will provide us with the generic name of this data structure so we can look at the existing computer science solutions for this 🙏

[colepoirier]

I also have the intuition that this effectively a data structure problem that has analogues in different domains, and therefore is perhaps a well-know problem that has an existing optimal design. Hopefully someone will provide us with the generic name of this data structure so we can look at the existing computer science solutions for this pray

It looks like the data structure we should use is something like skip-lists or tries.

[colepoirier]

It looks like the data structure we should use is something like skip-lists or tries.

The obvious just occurred to me: some kind of binary tree.

[colepoirier]

I came across a user-facing API design I really like here:

/// Relative Z-Axis Reference to one Layer `Above` or `Below` another
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub enum RelZ {
    Above,
    Below,
}
impl RelZ {
    pub fn other(&self) -> Self {
        match *self {
            RelZ::Above => RelZ::Below,
            RelZ::Below => RelZ::Above,
        }
    }
}

Upon seeing this I immediately thought that this would in fact be the optimal Layer/z-index ordering design for our user facing API. What do you think?

I'm not convinced that other is the optimal method name; my strong positive sentiment here is focused on the simple Above|Below relative ordering API.

[jomala]

Is there not also a requirement that I don't think has been mentioned, that the z allocated to the layer should not change between frames unless the layers is moved (or removed)? If that's right, I don't think that the allocation of values is the issue - the question is just how to set up the interface so that it's easy to work with, which is probably as hard/easy as other problems like handling named phases.

The one extra problem what to do in really offbeat scenarios when you're getting close to the smallest differences that f32 can represent, but doing an emergency reallocation of depths in that case is probably sufficient.

[arnemileswinter]

The way i solved Pokémon-gen-3-style Y-sorting in 2D was the following:

Decide which layers you have, for me it was
GROUND_LAYER = 0
UNIT_LAYER = 1
SKY_LAYER = 2
UI_LAYER = 3

Notice that theres a maximum of 8 (maybe even less due to visual debuggers / UI)

now create a camera for each of them. Make sure to add a RenderLayer::layer(XXX_LAYER) Component for each camera.
Adjust the camera's priority to be the same as your XXX_LAYER so that the images stack upon another.
Make sure that your non-0 priority cameras have no ClearColorConfig, else you'll only see the highest-priority camera.

Now my floor tiles also get the RenderLayer::layer(GROUND_LAYER) component, units and sky objects accordingly.

For Y-Sorting on my UNIT_LAYER i simply created a system that aligns the translation's z axis with the y axis. something like: Query<&mut Transform, (Changed<Transform>, With<YSorted>)>. When querying them, set your entity's
transform.translation.z = transform.translation.y.

[Ygg01]

Has there been any ideas how to solve this issues? Was hoping to use this for isometric 2d game.

[magras]

I came across a user-facing API design I really like here:

/// Relative Z-Axis Reference to one Layer `Above` or `Below` another
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub enum RelZ {
    Above,
    Below,
}
impl RelZ {
    pub fn other(&self) -> Self {
        match *self {
            RelZ::Above => RelZ::Below,
            RelZ::Below => RelZ::Above,
        }
    }
}

Upon seeing this I immediately thought that this would in fact be the optimal Layer/z-index ordering design for our user facing API. What do you think?

I'm not convinced that other is the optimal method name; my strong positive sentiment here is focused on the simple Above|Below relative ordering API.

Not sure what relation it describes. There is neither equality (for total order) nor incomparability (for partial order). I think this will work only in the simplest cases.

I'm not an expert, but after some research I believe there are two main techniques to draw a complex sprite scene:

1. Draw sprites in any order and use the depth buffer to make decision on a per pixel basis. As @StarArawn noted, it can't handle translucent sprites by itself.
2. Draw sprites sorted topologically. Partial order can create cycles, making it impossible to sort.

Total order doesn't work because sometimes you need a third sprite, which will tell that it's behind this one and in front of that one, to order two directly incomparable sprites.

[deifactor]

Being a little cheeky here and plugging my extol_sprite_layer crate, which lets you specify the layer as a type that's convertible to an f32 and also optionally does y-sorting.

That being said, I'd like to see something land in Bevy itself for this. Rather than designing the one layer system to rule them all, I'd like to see one that handles one particular case well and see how that goes. I'm biased because of my use case, of course, but I think handling the 2d graphics sprite layer is simple: you don't need to arbitrarily subdivide layers or support runtime layer creation, so the simple enum-based approach works fine.

[deifactor]

Also, re @magras, I'm not sure what you mean about a partial order creating cycles. A partial order can't have cycles by definition. The sequence produced by a topological sort can be non-unique if there are incomparable elements, but it'll still satisfy the property that if a < b, then a appears before b in the sort. If your sprite layers do have cycles then I don't think there's anything sensible to do.

[magras]

@deifactor, yes, I was wrong. Didn't notice partial order requires transitivity too. Thank you for the correction.

I wanted to say that it's possible to describe a cyclic relation like red > green > blue > red which will break topological sort. That will require some handling in the engine and probably will create questions from unqualified users like me. You could say that the situation is no different from the total order, but I believe that it's well known that violating transitivity for total order will break sorting algorithms.

I'm not sure if topological sort and depth maps should be a part of the core, but I'm frustrated that what I imagined as a simple sprite game turned into tinkering with renderer, assets and manual sorting of sprites.

[feelingsonice]

Any updates to this?

[pablo-lua]

I'm thinking about this, and I think that might be good if we can set the Layer to be hidden or be show at anytime, simply by disabling the Layer somehow
like, hide(layer) would hide all the sprites that are in the given layer for example.

[NthTensor]

Entity-Backed Layers

Layers are hard for the same reason that using 3d transforms for 2d games feels weird. My thesis is that we should introduce layers at the same time that we transition to a Transform2d (see #8268). This opens up a big class of possibilities relating to how we even represent the location of entities in the first place.

Here is my proposal: A layer is an entity with a component

struct Layer {
    depth: f32
}

depth indicates the z-distance between this layer and the one on top of it. Layers can have other layers as children, or entities with a Transform2d component.

The z-layout system walks down the layer tree and determines the actual z-depth of each entity:

• All entities have a Depth(f32) component that gets updated (much like Transform/GlobalTransform).
• Layers/entities with no ancestor layer are assigned z-depth 0.
• Child entities are assigned the same z-depth as their closest ancestor layer.
• Child layers get a z-depth above the parent layer.
• Child layers are ordered according to the hierarchy (children are already ordered).
• The z-distance between one layer and the next is always the lower layer's layer.depth.
• The z-distance between two sibling layers is total_depth := self.depth + children.map(|c| c.total_depth()).sum().

A separate system can then go through to propagate Transform2d and expose Depth in the GlobalTransform. If more than one root layer is detected we can emit a warning.

Criteria

A single, central source of truth which controls the relative positions of different varieties of sprites.

Yes. It's the ECS.

Easy initialization of freshly created sprites on a specific layer.

You use something like layer.push_children(entity)

Ability to move sprites between layers. You should be able to move sprites to a specific layer, up / down one layer, and to the top or bottom-most layer.

You use something like entity.set_parent(layer)

Support for nested sublayers.

Yes, it is tree-structured.

Changing the position of one layer doesn't require changes to any other layer.

Yes, the z-layout system will move everything for you automatically.

Layer names must be unique.

This one is kinda iffy. Layers are uniquely identified by their entity, and you can attach whatever components you want to identify them. Use enums, use Name. Its flexible.

[tbillington]

All entities have a Depth(f32) component that gets updated (much like Transform/GlobalTransform).

Being pedantic but I think this needs better specification, "All entities" is way too broad imo. eg Would this be restricted to entities with a Transform2d, or both a Transform2d and Visibility etc.

[NthTensor]

Fair point. I was envisioning the z-layout system would only operate on nodes with depth and layer/transform2d. We can use a similar thing to how transform works to ensure all ancestors of an entity with a depth also have a depth.

[MushineLament]

I hope he can control the display order of all 'images', including' nodes', to replace the cumbersome 'Index'. And as a 'Component', it facilitates the modification of display order. (Machine Translation)