hierarchy example?

[dakom]

Just wondering if you happen to have a hierarchy example to look at, e.g. for implementing a scene graph. Specifically:

• walking from parents to children entities, and mutating their components (e.g. to set transforms)
• getting a parent from a child (e.g. until finding the mesh that contains a primitive)
• removing / adding nodes

Thanks!

[zicklag]

I'm interested in this too. I'm going to be attempting to implement Amethyst's transform hierarchy with Legion, but I have to have something to replace Specs Hierarchy. If there isn't anything existing that demonstrates a hierarchy in Legion then I'll attempt to make one myself and I'll post back here if it works.

[dakom]

I wonder if it makes sense to use a tree structure from another crate, like indextree - simply passing it in when creating an entity?

Heading to bed now, maybe I'll learn something in my dreams :)

[dakom]

Looking into it a bit more, I don't think it needs a separate tree management, I think the ECS itself can be used. Will play around a bit tomorrow hopefully and see if I can get a working proof of concept...

[kabergstrom]

https://docs.unity3d.com/Packages/[email protected]/manual/transform_system.html

Here's Unity's docs for its design.

[dakom]

Will play around a bit tomorrow hopefully and see if I can get a working proof of concept...

I'm not going to attempt a PoC with legion right now, but it might help to share some of the ideas from a chat with @kabergstrom on discord (hope that's alright! and that it's indeed you, hehe. it's good insight and can be useful as a reference here...)

As per this [unity doc above], you just need to guarantee that parents are processed before their children. First, you can process entities with no Parent component. Then, there are many approaches, but one idea is to create a sorted data structure with a few properties:

• a "depth" number for each entity index that indicates how many parents they have
• the entity's chunk id and the index of the entity within the chunk

You will end up with something like a sorted Vec<(depth, chunk_id, entity_chunk_index)> sorted first by depth, then chunk_id, then entity_chunk_index. Then you can just iterate over the vec and you will get as linear memory access as possible

[zicklag]

@dakom, @AThilenius is working on a Legion transform hierarchy here: https://github.com/AThilenius/legion_transform. :tada:

[AThilenius]

Sorry I didn't even see this issue, ty for the mention @zicklag!

I'm waiting on feedback from @TomGillen, but iff (with two 'f's) Legion Tags work how I think they do (ie. filtering by tag value is O(1)), then the way I implemented hierarchies should be fairly efficient (O(n) for both computation and memory-space). Jumping around trees is always hard on caches, that's unavoidable without upfront costs, so it will always be slower than ripping through an array.

As for guaranteeing that parents are computed first (and that only Transforms affected by mutation are re-computed), the approach I made-up™ is to build a forest of hierarchies that need updating. Each tree in the forest is independent, and each Entity only exists in at most one place in one tree. Advantage here being that exploring the forest (aka re-computing global_matrix for affected Transforms) is trivially parallelizable.

[CleanCut]

This issue can probably be closed as @AThilenius's legion_transform probably more than fills the request for "a hierarchy example to look at". 😄