Scaling, Transforms and Hierarchies - Oh my

(Alec Thilenius) #1

As part of the legion_transform rewrite I sat down to accomplish today (and failed miserably at), I ran into lots of general questions on both transforms, scales and hierarchies (in the context of ECS). Seeing as many people here are far smarter than I, collecting feedback/thoughts seemed pertinent. This is all within the context of legion_transform, but I’m hoping it can be used as a reference impl during the Legion ECS switch for Amethyst.

Scaling

There are several different types of transforms in nalgebra. The current Amethyst Transform component in core uses an Isometry3 along with a non-uniform scale stored as a Vector3 (I’m unclear on why Affine wasn’t used?) The isometry part is lovely, it’s a composition of translation and rotation. No problems there that I know of. However non-uniform scale is often problematic. For example, a non-uniform scaled sphere-collider has to be converted to a convex mesh collider, among a myriad of other issues. I believe there are also performance optimizations to be had with uniforms scaling.

So, first question:
Thoughts on making uniform scaling the default, with some more-painful-to-use escape hatches for non-uniform scaling? The escape hatch can have a lot more constraints on it than the common-case uniform scaled transforms.

Transforms

Edit: Some of this is out of date, see the POC implementation here.

Related to scaling, I’ve been thinking about the Transform component itself. I’ll assume two things for this section: scaling is uniform by default, and transforms are always from their parent space (world-space being a root “parent”). Right now Amethyst has a Transform component (which is an Affine internally), but nalgebra already has several types of transforms each granting compile-time guarantees about the transformation. Given the two invariants above, a Transform component could be any nalgebra type that can convert(...) to a Similary (probably wrapped in an enum). That includes Translation, Rotation, Isometry, and a Similarity itself. Non-uniform scaling would be special-cased with a NonUniformScaleTransform component wrapping an Affine which would have restrictions on what it can do and where it can be placed. I’m unsure how many of these could be enforced at compile time though.

Two WorldTransform components would be defined, both with a single local_to_world: Matrix3/4 in them. One for uniform scaled transforms, and one for affine transforms. This is the only component actually required by things like the rendering system, allowing you to load it manually and save some space. More importantly it is update from any of the above nalgebra transforms by the TransformSystem which is also aware of parent hierarchies. The local_matrix would be create on-demand from the nalgebra types (they all convert(...) to a matrix).

Hierarchies

Edit: This is all out of date, see the POC implementation here.

This one is rather tangential to the rest: how do you implement a hierarchy in an archetypical ECS like Legion. The two ways I’m considering right now (I welcome more ideas) are:

  • Keep a totally separate data-structure ‘alongside’ the World that stores the hierarchy. The advantage here is that traversals can be tuned and optimized. The disadvantage is that keeping the ECS world and this data-structure in-sync isn’t free, and it gets messy. Likewise it means the actual hierarchy is opaque to any other system, it exposes only the query API. This means bespoke serialization for that structure and so on.
  • Store the hierarchy as components in the ECS world with no out-of-band data structures, namely the struct:
    // Entity(0) being a 'null' pointer
    pub struct HierarchyNode {
      parent: Entity,
      previous_sibling: Entity,
      next_sibling: Entity,
      first_child: Entity,
    }
    
    This forms a circular linked-list of siblings, along with pointers to both the parent and children of each (aka both up/down traversal, as well as sibling traversal of the tree).
    I believe this approach would be simpler and more intuitive for users, mutation would be immediate, it’s compact and best of all it’s a part of the ECS World itself. Disadvantage is that jumping around the tree is harder to optimize (cache misses will be more common).

Conclusion

Thoughts, recommendations, links, constructive criticism is all welcome and needed. And a many thanks to anyone who took the time to get this far!

5 Likes
(Alec Thilenius) #2

Woo it’s like crickets out there :cricket: What, people aren’t as excited about hierarchies and space-transforms as me? :stuck_out_tongue:

I created a proof-of-concept implementation of the second hierarchy example above with some passing unit tests on this branch. It requires no allocations outside the maximum of a single component that gets added to any entity in the hierarchy. It’s also always-correct as long as the invariant is respected and O(1) complexity for all traversal directions and mutations.

4 Likes
(Paweł Grabarz) #3

First of all, a BIG Thank You for working on this :slight_smile: We definitelly need this to be solved for legion to be adopted, so this is a huge step! It’s exciting and certainly not crickets :stuck_out_tongue:

Now tackling the non-uniform scaling issue, I’m honestly not sure about this. It sounds like not too big of a deal, but it might be surprising for users to not be able to do that. Can you provide an example of an optimization that would benefit from forbidding non-uniform scaling?

For transforms, I don’t really see a point of using enum, the representation for something as commonly used as transforms should be as uniform as possible, so we can avoid branching all over the place in possibly hot code.

If this is indeed enough to support only uniform scaling, we could probably just use Similarity as a base. Then the possible “escape hatch” would be either local to some very specific systems (like particle systems would likely not use transforms for individual particles anyway), or we can keep a separate “nonuniform scale” component that is ignored for the hierarchy purposes and only applied to the entity itself with certain limitations (like maybe being ignored by physics or something). Although this has a significant disadventage of operation ordering - you would like to be able to rotate post-scale. So, this “escape hatch” approach is potentially a deep rabbit hole.

Now, the second topic - hierarchy structure itself. I like the data to be contained in the entity. You can’t use null entity, because entity 0 is still a valid ID. Also this generally weird way to do it in rust. We have better ways. :slight_smile: If we’ve made it truly “reserved” by design, we could use NonZero type inside Entity and it opens up the possibility to just use Option type where you need it without any cost (the NonZero wrapepd in Option internally uses 0 to mean None without extra memory cost).

So, we would literally just have

pub struct HierarchyNode {
  parent: Option<Entity>,
  previous_sibling: Entity, // points to itself when has no siblings (cycle of 1)
  next_sibling: Entity,
  first_child: Option<Entity>,
}

I feel a bit uneasy when using graph representation to really mean a tree though :stuck_out_tongue: It’s easy to create some absurt structures like node having a parent that it’s also its child (a graph cycle). But i have no better idea here, we don’t want the entities to literally contain other entities, so it seems like a necessity. The right API migh make cycles impossible to happen at runtime, but I think we will need validation step during deserialization.

1 Like
(Kae) #4

First I’d like to echo Pawel’s words of commendment and initiative on this issue. It is much appreciated!

Secondly I would address the question of scale in the common Transform data structure. My stance on this is that because there are valid use-cases for non-uniform scaling, such as Sprite/UI animations, aspect-ratio related scaling solutions etc, there are no grounds for removing three-dimensional scaling in the common Transform struct. Instead, systems that have proven issues with performance can either simply discard the second two dimensions or emit a warning when encountering non-uniform scaling.

Third, on the issue of hierarchy structure, I had a discussion with Alec on Discord previously, but I’ll echo it again: I do not think that embedding an index in component or tag data can result in as good performance as an out-of-World index data structure. I also do not see how a doubly-linked list solves the mutation requirement. This proposed API would require mutable access to both the entity for which the user sets the parent, in addition to the parent entity itself. An out-of-World index could at least be made to have immediate mutations without having such mutation requirements, instead only requiring mutable access to the index itself.

2 Likes
(Alec Thilenius) #5

Thank you both for the thoughtful replies! :grinning:

I should have updated the original issue after the POC push, almost all of what you both address is implemented here already. I wrote a readme with it too, here.

I’ll shelve uniform/non-uniform scaling till the end, but in order of discussion:

@Frizi

I don’t really see a point of using enum

Agreed, I realized that very quickly while writing the POC. It uses a Similary3 for the local transform type.

I like the data to be contained in the entity

I assume you mean as a component ‘of’ the entity? Or do you want to modify Legion itself to support hierarchies? I very much prefer the idea of having 100% of hierarchy data stored inside the ECS itself, which is why I’m fond of the POC implementation. Memory is more fragmented than a separate index would be (aka it will be slightly slower) but jumping around the tree itself and mutating it shouldn’t be a very common operation.

You can’t use null entity

I also realized that very quickly :stuck_out_tongue: We could use a sentinel ‘null’ entity, but I realized that makes things even more confusing as you get all kind of weird graph structures growing out of that one. I also didn’t like the special-case of it, so used Option for everything.

So, we would literally just have…

Close! I tried that. But you can’t have previous/next point to yourself because you have no way of knowing if the thing they point to is your 1 other sibling, or you without doing a double-jump (both involving a query to World get_component (the component has no direct access to it’s owning entity). So I wrapped them in an Option as well for the only-child case.

I feel a bit uneasy when using graph

Ditto. The only guarantees it’s valid are unit tests, which makes me uneasy. Keeping the members of Hierarchy private and validating the mutation API will give decent coverage though.

@kabergstrom

I do not think that embedding an index in component or tag data can result in as good performance as an out-of-World index data structure

This is almost certainly true, simply because of cache locality. We can probably pull some tricks with Legion to sort things, but no way it will ever be as fast as a separate index. With that said, I very much dislike all the edge cases that keeping two totally disparate structures (index and ECS) in-sync creates. I’m still experimenting, but unless a compelling argument can be made as to why tree traversal and mutation is hot-path code, I think erring on the side of an easy to use / maintain API is wise.

For example, the local -> global transform update system will be one of the biggest pressure-points on the hierarchy so it’s worth considering how I imagine it working (most of this is already in the todo on the readme):

  • Each cycle the transform system will pull in modified nodes and propagate a mutation flag down the hierarchy. While doing so it will also track depth and re-tag entities that changed depth. These Legion tags are used for sorting and parallel enumeration.
  • From there the system will par-iter over all dirty Transform || Hierarchy, starting with the tag Depth(0) and going downward each time until no entities are returned by the filter. Fetching a parent global transform for an entity can either be done with a Legion get_component or you can keep a temporary cache of Entity->Matrix4, what ever is tested to be faster.

If full tree traversal needed to happen each frame, especially if it needed to happen multiple times I could see this being a performance issue. I suspect the matrix multiplication alone will vastly outweigh the performance hit of all tree traversals though.

Non-uniform scaling

I’m less opinionated about this one. The only idea I really like here is to use nalgebra types directly and not wrap them in a redundant ‘Transform’ struct that does the same thing. This also means that all operations supported on the transform are maintained/documented by the nalgebra folks (free work :stuck_out_tongue:) and that it’s guaranteed to play nice with the rest of nalgebra. In this case, the nice things about using nalgebra types directly is that if you change this line to

// Was a Similarity3<f32> before
pub type LocalTransform = Affine3<f32>;

then that’s all you need to switch to non-uniform scaling. Both convert up to a Matrix4 so nalgebra and the transform system don’t care which is used.

3 Likes
(Alec Thilenius) #6

Also lots of good food-for-thought in the GDC talk on Unity’s new ECS hierarchical transform system: https://www.gdcvault.com/browse/gdc-19/play/1026171

The parts I like:

I like how they split everything out into separate components that feed into local_to_parent (if parented) then finally local_to_world. The more I think about the local_to_parent idea the more I like it, even though it’s extra memory. It creates a clean separation of concerns. Getting back to my original post, this also allows you to add any combination of nalgebra transforms as components which will feed into the local_to_*. Either a Similiarity, or a Translation or a Translation & Rotation. What ever first your use case best. Their layout also does a nice job of optimizing for the most common case downward. Static entities pay no perf cost, ones without a parent pay no parenting cost, ones without a rotation pay no rotation computation cost and so on. This means most users can also stick with uniform scaling, and (like Unity) Amethyst can put up a big disclaimer that any non-uniform scaled transform could break things.

The parts I dislike (Jk, I like it, see my edit-edit):

How they handled the hierarchy. They store a Child component which is one of their “Dynamic Buffers”, which is basically this in rust:

enum Child {
  // Fixed size, inline
  Direct([Entity; 8]),

  // Heap allocated.
  Overflow(Vec<Entity>),
}

They also need a PreviousParent component, and the hierarchy is stale (read: invalid) between a mutation and system run.

Edit: Might be changing my mind on if I dislike that or not. Going to try and implement it and see how messy it gets.

Edit: Edit:
A double edit, wow such excite, much churn! :grinning: I updated https://github.com/AThilenius/legion_transform (master) with a POC of the way Unity does hierarchies. I like it more than I thought it would. I’m leaning more toward this impl over the linked-list. It’s more compact in memory and faster for child iteration. Readme is update too with an explanation. Next up is the actual transform computation.*

4 Likes
(Paweł Grabarz) #7

This is basically what SmallVec is for.

(Alec Thilenius) #8

I knew there was something for it already! Ty! I’ll switch over when I go to implement the transform stuff.