Design survey: Transform architecture

[alice-i-cecile]

This discussion is intended to collect issues and proposals in a central place, in order to provide an overview of the rather complex set of concerns that we should slowly try to untangle.

If you have additional challenges or constraints, please post them and I'll update this list. If you have design proposals, please post them here!

Current challenges

1. There is severe code duplication between Transform and GlobalTransform.
   1. Discussion in [Merged by Bors] - Split bevy_hierarchy out from bevy_transform #4168.
2. The "transform propagation system" for inheriting transforms cannot be readily extended because Transform is not provided as an associated type in any form for GlobalTransform or vice versa.
   1. Users cannot opt-out of inheriting Transform, or any of its constituents.
3. Code cannot work with "either Transform or GlobalTransform" without a custom enum wrapper.
4. Users commonly struggle to understand the distinction and relation between Transform and GlobalTransform, and which one they should be modifying or reading for their various use cases.
   1. This has improved with better docs, and could be improved further.
   2. Meddling with GlobalTransform almost never has the desired results, and meddling with the transform values of UI elements, while extremely tempting, tends to lead to either no effect or very strange behavior.
5. Non-uniform scaling is of questionable value, and is likely to have performance costs.
   1. Could Bevy support non-Euclidean geometry? #4207
   2. Revert transform back to using Mat4 #1755
6. Transforms cannot be easily extended to support other types with other behaviors, data representations or improved ergonomics.
   1. f64 (Ability to set Transform fundamental native type to f64 or fixed-point types #1680)
   2. Discretized coordinates: both grid-like and fixed point (Ability to set Transform fundamental native type to f64 or fixed-point types #1680)
   3. UI: Consistent Hierarchies rfcs#53, Change 'components' to 'bundles' where it makes sense semantically #1257
   4. 2D: Scale sprite z level by their scale #4156, Enhance 2D Transform/Vec2 Quality of Life #2548
   5. Non-Euclidean transforms: Could Bevy support non-Euclidean geometry? #4207
7. The ergonomics (and performance) of working with the full Transform when you only need to mutate a single constituent (such as the translation) is debatable.
   1. Inspired the contentious Component Bundle Queries #2252, which was ultimately rejected for being confusing to users.

Constraints

1. Regardless of their coordinate system, all Transform types must ultimately be renderable.
2. Performance is very important, at least in some applications.
3. Avoiding heavy abuse of generics and formal mathematical constructs in public APIs (see nalgebra) is important to ergonomics and accessibility.
4. Different types of transforms will commonly be blended within the same game, depending on the object type.

[alice-i-cecile]

Use macros to reduce Transform and GlobalTransform code duplication

This reduces the immediate pain, but significantly increases developer complexity. Macros don't always play nicely with tooling, and are intimidating for many new developers.

[alice-i-cecile]

Common RenderTransform representation

1. Store a Mat4 or Affine3A in a RenderTransform component.
2. Allow users to use their own transformlike components by supplying them to the rendering plugin, but enforce Into<RenderTransform>.
3. Use the RenderTransform to handle rendering.

First raised in #4207 by @finegeometer.

[james7132]

OpenGL makes it easy to work with geometries whose Transforms are nicely represented as Mat4s, such as spherical or hyperbolic geometry. In #4207, those are the only geometries I suggest supporting, for that reason. So this isn't a problem, because I was only asking about those geometries for which it isn't a problem!

I replied in that thread how one might be able to achieve the goals they want without forking any of the rendering crates. The sole exceptions to this are mid-pipeline depth sorting for transparent objects and shadow projections, which I'm not sure we can achieve without making the render plugins generic over the space they operate over or exposing function pointer parameters for handling this.

[finegeometer]

Now that I understand the rendering architecture a bit better, I think I have a clearer understanding of the design space.

Users work with Transform. Rendering works with Mat4. So somewhere along the line, a conversion has to happen.

When should this conversion happen? There are four choices:

1. Do the conversion in the app world.
2. Do the conversion during the Extract step.
3. Do the conversion in the render world.
4. Some combination of the above.

The status quo is option 4 — option 2 for meshes; option 3 for cameras and point lights.
In my understanding, this proposal is option 1, but I'm not confident I'm interpreting the proposal in the same way as @alice-i-cecile.

In terms of ease-of-replacing-Transform, I think option 1 is better than option 2, which is better than option 3. But I could be missing something, or there could be other considerations which lead to a different preference order.

[james7132]

Option 1 might be workable if and only if we can justify the cost in blocking all other systems reliant on a GlobalTransform equivalent. As we're already doing composition, adding the cost of a matrix multiply alongside conversion into a Mat4 may increase transform propagation time significantly. Main benefit here is that the Mat4/Affine3A representation is available to everything, not just rendering. Could also regain some time back by leveraging SIMD acceleration. This propagation only blocks the systems dependent on it, not the entire ECS schedule.

Option 2 shifts that to a exclusive stage that blocks both normal game simulation and rendering. IMO this is not a viable option in any case.

Option 3 is, performance wise, the most appealing, as it keeps a minimal representation in the app world, has a simple clone-to-extract process, and conversion into a GPU friendly format does not block game simulation in any way with pipelining. However, customizing it's calculation will require either generics or function pointers of some kind.

[superdump]

I’m not sure why you say Option 3 is the most appealing. As I recall, transform propagation is faster when using Mat4s and fastest when using Affine3A. Overall performance with serial rendering depends on end to end time taken to process a frame. Pipelining makes it more about minimising the maximum processing time of simulation and rendering, because the one that takes longer is the bottleneck. If rendering is the bottleneck then offloading work from the render app to the main app could improve frame rate.

[superdump]

I feel like Transform should use a separate representation and be suitable for editing. For that it should have lossless setting/getting of values. @cart has said they want this multiple times.

I feel that the internal representation of GlobalTransform should rather be optimal for internal use as it has associated performance costs.

That said, as the ‘spawn something at the global position of another thing, orientated correctly’ requires supporting some use cases to get information from the global transform so we need to make sure those are also supported.

We should be aware of what other engines support as expectations will be that we can at least support the same functionality. To my understanding, Unity uses a separate representation for local transforms and affine matrix representation for global.

I feel that supporting non-affine global transforms does not have to be a requirement of the core of bevy and rather a plugin could provide support for spherical and hyperbolic geometries and rendering. I feel that if they can be supported without significantly negatively affecting performance for affine geometries then we definitely can but it seems that only sorting affine geometries is the external expectation and doing so does provide significant performance benefits.

[alice-i-cecile]

Dedicated 2D Transform type

[james7132]

pub struct Transform2D {
  pub translation: Vec2,
  pub mat2: Mat2,
  pub depth: f32,
}

A few notes:

• This would effectively be glam::Affine2 with an additional depth parameter.
• Scale and rotation are encoded in the Mat2.
• 2D transforms are where non-uniform scale is definitely desirable. See: https://www.youtube.com/watch?v=haa7n3UGyDc
• One open question is whether depth should be inheritable/composable. IMO depth in 2D should be treated as a near static layer, so a child should typically have a depth that is independent of it's parents.
• This implementation has zero SIMD acceleration.

[CptPotato]

An alternative representation would be this:

pub struct Transform2D {
  pub translation: Vec2,
  pub scale: Vec2,
  pub rotation: f32,
  pub depth: f32,
}

The main difference is that it is more in line with the current Transform layout. And by keeping scale and rotation separate, relative rotation can be applied without having it affect scale over time (and vice versa).

[james7132]

One potential problem is that any rotation using a 1D rotation requires trig function usage (sin/cos) when propagating. Unless we are hyper aggressive in how optimize that, this may have a heavy performance penalty. Some common methods for simplifying this would be to include a big LUT and use linear interpolation to approximate, but even this is not optimal.

An alternative, to steal the 3D quaternion idea, is to use a dedicated complex number to encode rotation instead. This would be closed under any rotation operation. You won't get any unbounded f32 values provided stick to values on the unit-circle, and it'd be near trivial to make a 2D rotation matrix out of it.

[CptPotato]

Good point. I mainly thought about it from an UX standpoint for when you want to read or adjust the scale/rotation. If it's a matrix you have to decompose the Mat2, adjust rot/scale and then create the Mat2 again.

I also considered using a Vec3 for the rotation: rotation angle + pre computed cos and sin (updated on assignment).
Though, now that I think about it, this would basically be your proposed solution plus having the user add an additional component that holds the raw rotation & scale separately for the entities where it is required.

[superdump]

@cart had been pretty clear previously about wanting to have a separate representation for Transform for local, parent-relative transforms for editing so that what the user sees in the editor is what the user gets after setting a value. That suggests that for user-facing Transform, the Affine2 or otherwise matrix representation is out.

[alice-i-cecile]

Dedicated UI Transform type

Goals:

1. Focused on rectangular layouts.
2. No rotation
3. 2D only
4. Some sort of z-layering solution

Currently, we're storing Transform, GlobalTransform, Size, and CalculatedSize, but only using the latter two. This is both inefficient and misleading.

[james7132]

pub struct RectTransform {
  pub position: Vec2,
  pub size: Size,
}

pub struct GlobalRectTransform {
  pub position: Vec2,
  pub size: Size,
  pub depth: u32,
}

Some notes:

• Position and size are driven by the layouting algorithm for UI.
• Position is in the top-left corner of the rect relative to the position of the entity's parent. Propagation is simple addition. Negative position values are allowed, though probably will never be generated by the layoutting algorithm.
• Size is in absolute units and cannot be scaled. When propagating, it's copied verbatim.
• Depth is a two part value. The upper two bytes contains the "canvas depth", which is a root level depth defined by the root node. The lower two bytes are incremented every time we go down a parent-child layer in the UI hierarchy. This enables us to have 65536 possible layers within a canvas, while having up to 65536 different layered canvases across a screen. This is using a u32 instead of a u16 because the struct is already 4-aligned from the f32 values, might as well use those two bytes instead of letting it be padding.

Open questions:

• Can we get away with integer values here? or do we need to use f32?
• Can we SIMD accelerate this?

[alice-i-cecile]

Coordinate traits

[alice-i-cecile]

Orientation trait

[alice-i-cecile]

Heritable trait

[james7132]

Assuming we have a Heritable trait defined as the following:

pub trait Heritable {
   type Source: Component;
   
   fn inherit(&mut self, parent: &Self, child: &Self::Source);
}

impl Heritable for GlobalTransform {
   type Source = Transform;
   ...
}

impl Heritable for ComputedVisibility {
   type Source =  Visibility;
   ...
}

There are a few things to note with this initial set of assumptions if we are to generalize the existing transform_propagate_system.

• Root queries are no longer sufficient unless we allow skipping levels. transform_propagate_system relies on every Entity from the root to the leaf to have the inheritable components.
• Allowing skipping levels requires full hierarchy traversals for all inheritance systems, not just the hierarchies with the components present, which would negatively impact performance.
• Top down inheritance is the only mode supported. Bottoms-up composition (i.e. AABBs as a BVH) isn't well supported. This could be supported via a different trait if need be.

I definitely think we should have a trait like this if we are to add additional transform systems for 2D and UI use cases as the hierarchy traversal and inheritance patterns almost all the same across them.

[finegeometer]

I don't know what the best inheritance abstraction will be. But here's a useful generalization of what we do for Transform.

Let T be a monoid. In other words:

• T is a type.
• T : Mul<Rhs = T, Output = T>
• For every possible a, b, and c of type T, a * (b * c) and (a * b) * c have the same result.
• There is a designated value I of type T, called the identity.
• For every possible a of type T, the expressions I * a, a, and a * I have the same result.

T is our generalization of Transform. Exercise: confirm for yourself that these five conditions hold for T = Transform, up to floating point error.

Our generalization of GlobalTransform will be struct Inherited<T>(T);.

Our generalization of transform_propagate_system will be a system with the following behavior:

• For every entity e:
  • Get the T values for each ancestor of e (including e itself), in order from root to e.
  • Multiply the Ts, in order. (The product of zero Ts is defined to be the identity, I.)
  • Set e's Inherited<T> to the result.

Note that this is a description of the intended behavior; the implementation could certainly be more efficient than what I described.

---

I don't suggest this as a final design, but as a starting point for discussion. In particular, I know that @cart has expressed concerns about Inherited<T> in a comment on #4168, but I'm having trouble understanding them.

[james7132]

That definition seems to be congruent with the overall trait design that I provided above parent * child can be expressed as child.inherit(&parent, &source), assuming the trait is properly implemented. Though this is built with traits and associated types instead of a generic struct Inherited<T>, though it wouldn't be unreasonable to build such a struct using the associated type.

If you haven't already seen it, I whipped up a preliminary implementation of this in #4216.