[WIP] Octree in Pure ECS : BufferArray based with source code (U2020.1a - Entities 0.2)

[Antypodish]

See update V4 in post [#71]( [WIP] Octree in Pure ECS : BufferArray based with source code (U2020.1a - Entities 0.2) page-2#post-5285541) - Octree based on buffer arrays with source code [work in progress]
Upgrade form
Unity 2018.3.0b10 to 2020.1.0a15

See update V4 in post #26 - Octree based on buffer arrays with source code [work in progress]
__**https://www.youtube.com/watch?v=OlGUWbtUBsM**__
See update V3 in post #23 - Octree in Pure ECS : Raycast Stress Test of 500k Cubes V3
**See update V2 in post #20 **

Original Post

Eh. Not going to lie. This one is really tough one for me.
Freshly new to ECS + porting octree scripts from OOP, to Pure ECS, makes not any easier.
Multum of challenges. And testing is not easy at current ECS state. But feasible.

In past few days I managed so far, to make adding octree nodes systems, which grows and shrinks relevant branches of nodes (leafs).

Next, I need rewrite removing nodes (leafs), and merging.
I hoped to be further with that. But here we go.

Unity3d 2018.2 - Pure ECS - Adding Octree Test (T: 2.36 min)

https://www.youtube.com/watch?v=HHsUrQG9KIA

See in video description for few more details, if interested. Similarly describing below.

Scene at the start displays only Classic OOP GameObjecst for references. Helps for debugging.
These GameObjects are not attached to ECS anyhow, other than ECS prefabs.

After starting the game, every created cube, is via Pure ECS.
Video shows adding new entity objects to octree, when clicking on cubes.
Octree grows or shrinks leafs respectively, to the entity node capacity of entity objects.
In the example, capacity per leaf is set to 4 and can be changed at octree initialization.

Current octree is base on point Octree, where raycast detection of near octree objects appears to work. But not shown on the video, as is not complete.
After finishing with removal of leafs for point octree, next stage will be to create boundary based octree, where raycast will test for collisions with leafs. So octree can be penetrated through, to find number of objects in entities nodes (leafs), that raycast penetrates.

If you survived till end, I hope you have found this somehow interesting.

[snacktime]

Would be curious to see the performance you get from using octree for AABB/ray intersection testing. I’m using a simple BVH for that now. Ray length has a significant impact on query performance. As does tuning the dimensions to better fit leaf node bounds size. So I’m seeing anywhere from 20ms to 100ms per 10k queries depending.

My concern with ECS for this is it adds overhead that’s not necessary, or at least I haven’t figured out a way to do a tree structure in ECS that beats just not using ECS.

[Antypodish]

Surly I will be willing to do such tests and post them, when I get to to the decent stage. Specially I am interest myself as well. I will generate at some point 10k, 20k, 50k, 100k leafs to observe the performance. If my pc wont blow up
Also, there will be possibly plenty space to optimize scripts/jobs, to bust performance even further.

[Joachim_Ante_1]

The way we would implement acceleration structure like this is not through Entities with components on it.

We would make a container that lives on the system and the creation of the acceleration structure would be based on the entities that the system processes. You can also use reactive system to make this incremental.

An example of this is boid simulation. That code however rebuilds the acceleration structure every frame. Which is the right choice for boids, but for other use cases something else might be necessary.

I think the purpose of ECS is to give a consistent editing experience / scene storage format. And consistent API to create entities / components. Acceleration structures listen to changes of ecs components and get built / updated based on that.

[snacktime]

Ya that’s pretty much exactly what I did. System for managing updates but the core data is not in Entities.

I started with a NativeMultiHashMap but moved to a NativeList per node for child nodes, the performance difference was not huge but still significant, 20% or so improvement.

Making a tree burst friendly complicates things a bit. Nodes having pointers to their child node list seems to be the cleanest approach that doesn’t have significant performance issues.

[Antypodish]

Thx for expanding upon the subject.

@Joachim_Ante_1

The way we would implement acceleration structure like this is not through Entities with components on it.

We would make a container that lives on the system and the creation of the acceleration structure would be based on the entities that the system processes. You can also use reactive system to make this incremental.

An example of this is boid simulation. That code however rebuilds the acceleration structure every frame. Which is the right choice for boids, but for other use cases something else might be necessary.

I haven’t look deeply into boid example (with fish school), however I did run it once or twice. I can look into it.
But can I apply multi depth relation tree this way?

Providing I understood correctly, rebuilding tree every frame is something I would like to avoid, which I think is unnecessary cost. But I may misunderstood the concept, as I am not familiar with other method. Entity reltion based structure seams to me reasonable at this point. Each node has reference to parent node, 8 children nodes and number of objects entities stored per child. But I am open for other options.

@snacktime

I started with a NativeMultiHashMap but moved to a NativeList per node for child nodes, the performance difference was not huge but still significant, 20% or so improvement.

20% performance bust can be significant for bigger trees.

@snacktime

Making a tree burst friendly complicates things a bit. Nodes having pointers to their child node list seems to be the cleanest approach that doesn’t have significant performance issues.

I believe, entity based structure can potentially benefit from burst compiler. Unless I am wrong? I haven’t used burst as of yet. But I would like to adapt the code, when is functional.

Any further suggestions are more than welcome.

Hence, do you guys suggest, I should look into alternative methods of octree implementation, rather than through entities?
Is using entities for octree an inappropriate / inefficient way of doing this, in your opinion/expertise?

So far my understanding is, having entities allows me to grow/shrink the multi depth level tree, as much as I like, to inf. Well, as long memory allows. While they do nothing on the system, unless tested interaction against them.

[Antypodish]

@Joachim_Ante_1

You can also use reactive system to make this incremental.

I would like put @Joachim_Ante_1 talk here as a reference to Reactive System.
Good talk btw.

https://www.youtube.com/watch?v=swCpyJy4FEs

I implemented something in this sense, however at current state, I attach tag to entity, which triggers the relevant system. This system does something once on given entity and removes the tag.

But surely, I will be considering moving later, to Reactive System instead, on that part.

@Joachim_Ante_1

The way we would implement acceleration structure like this is not through Entities with components on it.

I am going now to investigate boid example. In meantime, is there any other reference to read, about Acceleration Structure. ECS forum search does not comes up with any references for that keywords.

Edit1
Upon some brief reading, just realized that octree is also Acceleration Structure. Or at least is similar in behavior to BVH Acceleration Structure, if my thinking is correct.

Edit2
Attaching example of Boids (fish school) for reference
Unity-Technologies/EntityComponentSystemSamples/Samples/Assets/GameCode/Samples.Boids/
https://github.com/Unity-Technologies/EntityComponentSystemSamples/tree/master/Samples/Assets/GameCode/Samples.Boids

[Antypodish]

Thx guys for an assist so far.

Ok, so I looked into Boid example (see Edit2 in above post).

I see how is implemented (snipped).

private List<PrevCells> m_PrevCells   = new List<PrevCells>();

        struct PrevCells
        {
            public NativeMultiHashMap<int, int> hashMap;
            public NativeArray<int>             cellIndices;
            public NativeArray<Position>        copyTargetPositions;
            public NativeArray<Position>        copyObstaclePositions;
            public NativeArray<Heading>         cellAlignment;
            public NativeArray<Position>        cellSeparation;
            public NativeArray<int>             cellObstaclePositionIndex;
            public NativeArray<float>           cellObstacleDistance;
            public NativeArray<int>             cellTargetPistionIndex;
            public NativeArray<int>             cellCount;
        }

Similar to this, it was my very initial thought, of doing it at very start. However, I din’t knew back then that using List is suitable for ECS. This perhaps cause my bigger confusion. Since I needed to be able, dynamically add and remove node instances.
With saying that, I can refactor my code, to use similar methods.

@Joachim_Ante_1

An example of this is boid simulation. That code however rebuilds the acceleration structure every frame. Which is the right choice for boids, but for other use cases something else might be necessary.

I suppose I don’t need to worry about it, since I need amend the structure, only when node is added/removed.

Hence I conclude, as mentioned, I don’t need entities to store Nodes. Which I makes me think, on decent performance bust, for larger trees.

Never the less, entities allowed me for better initial debugging, which wasn’t easy at first at all. So what I got so far, wasn’t bad.

P.S.
Is List passed into methods by copy, or by reference (like in classic OOP)?

[snacktime]

Spatial reasoning/search is very context specific. You won’t be able to build a single solution that handles frustum culling and AABB/ray intersection for example and does both well. You need to pick a specific end use case and design around that.

A specific use case is also good for learning, because you will be able to find material online about the best choices there much easier then if you have no clear end goal in mind.

[Antypodish]

I can’t argue wit that. What you propose for frustum culling?

[Joachim_Ante_1]

List is only used to seperate different groups of boids based on their settings. Like different boid simulation worlds.

I doesn’t make sense to use List in the internals of an octree or acceleration structure.

[snacktime]

@Joachim_Ante_1

List is only used to seperate different groups of boids based on their settings. Like different boid simulation worlds.

I doesn’t make sense to use List in the internals of an octree or acceleration structure.

For some specific types sure, but generally why not? If you have a tree with high concentrations of leaves under branches at specific depths, what else would work better?

[snacktime]

@Antypodish

I can’t argue wit that. What you propose for frustum culling?

I wouldn’t use a tree there, I’d do something more similar to what the ECS MeshFrustumCullingSystem is doing. It’s taking advantage of burst in a way that makes it performant enough for the average use case without having to use a more complex structure that has more limitations.

[Antypodish]

Uh, I proved myself just how stupid I become.
Now I know nothing.

Right, I will bite this problem with question from different angle. Sorry if that been already answered, but I am trying get un-lost and my head round.

Which ECS collection type should I use, in your humble opinion and expertise, so it can handle dynamically and efficiently expanding and shrinking such collection, as tree branches grows, or shrinks? List is seams suitable for it. But in mentioned case:

@Joachim_Ante_1

I doesn’t make sense to use List in the internals of an octree or acceleration structure.

I a m concerned for List in ECS Job performance. On the side note, I checked List with method, so it is past via reference. List is part of using System.Collections.Generic, while I thought earlier, it is explicit List version for ECS. Which makes me thing, if it can be jobified with Burst at all?

I am sure I got something wrong with my reasoning tho.

On other hand, entities implementation made me think, is a good solution, since I can grow and shrink tree branches without issues.

Please tell me, if I am wrong. But I understand that NativeArrays are not suitable for holding dynamical changing structure (like octree), since they are fixed in size?

Then there is NativeMultiHashMap. How about it? I have no expertise using them.

So again, which ECS based collection should I use in this case? Sorry, I feel quite a bit ECS-Job-confused atm.

[Antypodish]

@snacktime

I wouldn’t use a tree there, I’d do something more similar to what the ECS MeshFrustumCullingSystem is doing. It’s taking advantage of burst in a way that makes it performant enough for the average use case without having to use a more complex structure that has more limitations.

Thx, Definitely I will check upon that.

[Joachim_Ante_1]

So again, which ECS based collection should I use in this case? Sorry, I feel quite a bit ECS-Job-confused atm.

I would use multiple NativeArray to represent the octree. Preallocated with a large enough capacity.
Using offsets etc between the arrays instead of pointers.

[snacktime]

@Joachim_Ante_1

So again, which ECS based collection should I use in this case? Sorry, I feel quite a bit ECS-Job-confused atm.

I would use multiple NativeArray to represent the octree. Preallocated with a large enough capacity.
Using offsets etc between the arrays instead of pointers.

Ok I took your response to mean lists generally, ie including NativeArray.

Ya I punted on single list for my BVH simply because my specific scenario it wasn’t a big gain in performance plus I have highly uneven yet dense distribution. But I might end up going that route anyways just to make it more job friendly, only a single array to pass into jobs.

[Antypodish]

Fair enough. That approach is feasible.
In this case, I need ask one more question on that matter. I think this has been touched somewhere on the forum already. I will search, however;
Lets say I approach size limit of the array, with initially pre-allocated size of 1000. So I would need expand it. Should I allocate new bigger array, and copy elements to it? I see that NativeArray has CopyFrom () and slice Slice (). I suppose I can use CopyFrom from smaller array to bigger one. This process would be rather very occasionally not every frame.
I understand Slice is to extract part of array, but not use to make it bigger. The last thought came, as Slice () one of overloads has start and length parameters. Presumably start + length should not be bigger than length of an array.

[Joachim_Ante_1]

Yes thats reasonable as a fallback for robustness etc.

But of course you want to pre-allocate it at a size so that this won’t happen in practice. Resizing of large arrays can easily lead to performance spikes.

[Antypodish]

Ok that superb. Thx bunch again.

Also, found the relevant discussion just from yesterday, which I was looking for.

NativeArray.CopyTo to larger managed array
https://discussions.unity.com/t/712102/7

@dartriminis

The current NativeArray.CopyTo(T[ ]) is not a single memory copy, it copies each element to the destination individually. Even if they adjusted the method to allow copying to an array of a larger size, your method would still be faster (in most cases) since it is a single memory copy. That said, it would definitely be nice to see something like this in the Unity library.

@LennartJohansen

Joachim Ante confirmed that in 2018.3 all the copy functions use the memory copy internally.

Just on side note:
I do indeed understand implications of resizing large arrays and I will try be careful about this.
Just as an example, the case I may want NOT to make too big array at initialization, is when I want to have lets say 100 or 1000 octrees. Some of them small, some big and some very big. I.e. 100, 10k, 100k. So wouldn’t make sense, to make all of them of the size 100k. And even 100k not guarantees, if I don’t want any bigger one in some other cases. Just want to make future proof, if that makes sense.

Edit1

@snacktime

Ok I took your response to mean lists generally, ie including NativeArray.

Ya I punted on single list for my BVH simply because my specific scenario it wasn’t a big gain in performance plus I have highly uneven yet dense distribution. But I might end up going that route anyways just to make it more job friendly, only a single array to pass into jobs.

I am glad that discussion benefits others as well

Edit2

I found source to second quotation, so I would like to attach it here as well for reference, from

Is there a utility method for faster copying of NativeArray?
https://discussions.unity.com/t/710506/11

@Joachim_Ante_1

18.3 has CopyTo implemented via memcpy for all codepaths including copy to .NET arrays.

Which is preceded by post

@tertle

You can use NativeSlice

            var array1 = new NativeArray<int>(100, Allocator.Temp);
            var array2 = new NativeArray<int>(50, Allocator.Temp);
  
            var slice1 = new NativeSlice<int>(array1, 25, 50);
            var slice2 = new NativeSlice<int>(array2);
  
            slice1.CopyFrom(slice2);
  
            // array1 index from 25 -> 75 is now equal to array 2

It’s very fast.
To create a slice it just grabs the pointer from the NativeArray and offsets it.
CopyFrom/CopyTo uses MemCopy.