Search Unity

  1. Unity 2019.1 is now released.
    Dismiss Notice

[WIP] Octree in Pure ECS : BufferArray based with source code

Discussion in 'Data Oriented Technology Stack' started by Antypodish, Aug 21, 2018.

  1. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    See update V4 in post #26 - Octree based on buffer arrays with source code [work in progress]



    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)


    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. ;)
     
    Last edited: Jan 9, 2019
  2. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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.
     
  3. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    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.
     
  4. Joachim_Ante

    Joachim_Ante

    Unity Technologies

    Joined:
    Mar 16, 2005
    Posts:
    4,571
    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.
     
    The5 and Antypodish like this.
  5. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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.
     
  6. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Thx for expanding upon the subject.

    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.

    20% performance bust can be significant for bigger trees.

    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.
     
  7. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    I would like put @Joachim_Ante talk here as a reference to Reactive System.
    Good talk btw.



    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.


    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-Technologi.../master/Samples/Assets/GameCode/Samples.Boids
     
    Last edited: Aug 21, 2018
  8. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    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).

    Code (CSharp):
    1. private List<PrevCells> m_PrevCells   = new List<PrevCells>();
    2.  
    3.         struct PrevCells
    4.         {
    5.             public NativeMultiHashMap<int, int> hashMap;
    6.             public NativeArray<int>             cellIndices;
    7.             public NativeArray<Position>        copyTargetPositions;
    8.             public NativeArray<Position>        copyObstaclePositions;
    9.             public NativeArray<Heading>         cellAlignment;
    10.             public NativeArray<Position>        cellSeparation;
    11.             public NativeArray<int>             cellObstaclePositionIndex;
    12.             public NativeArray<float>           cellObstacleDistance;
    13.             public NativeArray<int>             cellTargetPistionIndex;
    14.             public NativeArray<int>             cellCount;
    15.         }
    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.

    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)?
     
    Last edited: Aug 21, 2018
  9. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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.
     
    DavidSWu likes this.
  10. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    I can't argue wit that. What you propose for frustum culling?
     
  11. Joachim_Ante

    Joachim_Ante

    Unity Technologies

    Joined:
    Mar 16, 2005
    Posts:
    4,571
    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.
     
  12. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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?
     
  13. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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.
     
  14. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Uh, I proved myself just how stupid I become.
    Now I know nothing. :p

    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:

    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.
     
  15. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Thx, Definitely I will check upon that.
     
  16. Joachim_Ante

    Joachim_Ante

    Unity Technologies

    Joined:
    Mar 16, 2005
    Posts:
    4,571
    >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.

     
  17. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,160
    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.
     
  18. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    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.
     
  19. Joachim_Ante

    Joachim_Ante

    Unity Technologies

    Joined:
    Mar 16, 2005
    Posts:
    4,571
    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 likes this.
  20. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    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://forum.unity.com/threads/nativearray-copyto-to-larger-managed-array.546113/#post-3603065

    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

    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://forum.unity.com/threads/is-...r-copying-of-nativearray.543888/#post-3595609

    Which is preceded by post

     
    Last edited: Aug 22, 2018
  21. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Finally some update (V2) on a progress.

    This my 3rd redesign of octree for ECS. :p It was/is nightmare to make it work correctly. Vast of testing and debugging has been already taken. And still not sure if is 100% correct. Then last part I got missing, is removing octree nodes. So I need to code it up.

    This time removed entities per octree node. Based on NativeArrays and index offsetting. Visible entities are initial prefabs, then just optional meshes with a position and rendering. Each Octree node (leaf) holds the position and entity.
    Ray is projected on the whole tree, to traverse and get entity id. Then entity id can be passed to other system, to control highlight of the blocks.



    After one minute, I switch to visual representation of octree tree.

    Also, I have noticed weird Debug.DrawLine behaviour. Ray works correctly, to detect intersections, but rendered green ray in editor, is a bit off, for some reason, having position offset. Even exactly same values of origin and direction are passed to octree intersection and DrawLine.

    Further, I see quite a bit space for improvement, but point is of getting it working first.
     
    Last edited: Aug 31, 2018
  22. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
  23. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Test V3

    ECS with custom octree and generated 500k Cubes 1x1x1.
    Using raycasting for stress test at 15FPS.
    Main performance hit, is due to rendering and drawing.
    Culling is not implemented.

    Searching Octree with raycast has almost no impact.
    Unnoticeable anyway in profiler data.
    Alone, is hovering around 1000ms threshold.

    Entities cubes play only role in visual aspect. Octree can works fine, without creating any entity.



    Unity3d 2018.2.6
    Entities prev 11
     
    Last edited: Sep 5, 2018
  24. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,247
    You seem to have a working system and all that and I don't know your implementation works, but wouldn't the ideal approach be to design an OctTree as it's own native container (that can be used in burst jobs.)

    e.g. Create a NativeOctree (and NativeOctree.Concurrent being write only)

    Internally I'd imagine the memory layout would be implemented similar to the NativeMultiHashMap
     
  25. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Thx.

    Possibly you are right. However, I am not too confident yet, to go that route.
    I would need study, of how to create custom native containers.
    I looked briefly into not so long ago. But that was it for now.

    So far, I took advise from @Joachim_Ante to replace entity based octree. So the result is what you see.
    And I am happy finally at this stage, since it is working again, even was very bumpy road.

    If I get my head round, of how custom native containers works, I may consider take step further.
    If that will result with performance bust.

    I still have quite of cleanup to do. Lots of debugging bit and bobs here and there.
    And improve upon system organization, etc.

    I think Burst should work now with current octree, but haven't test it yet to be honest. Unless I missed something.

    Any advice on Native custom containers?

    PS. I am bit upset, as I forgot record mouse cursor :p So can not see properly when I am hovering over blue cubes. Sorry for that. Next one should be better.
     
    MD_Reptile and Zoey_O like this.
  26. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Update V4 - Octree based on buffer arrays with source code [work in progress]

    So far I did Octree working with ECS, using NativeArrays. I was quite happy with results. But there was few small things, which I haven't fully complete yet. However, since then I haven't touch it much, as I had what I needed at that point.

    Later in a year 2018 we had introduced buffer arrays into ECS. Hence my though was, how to utilize them with Octree. I needed multiple octree to my project, with different structures. Making such, based on purely native arrays, is quite challenging. Yet since BufferArrays, now it is possible, to have each octree structure, per entity. Please don't get confused with octree node per entity. Nodes are stored in buffer arrays, not in entities.

    And this exactly what I have attempted past few days. I started converting octree, so each entity can have own octree structure, holding whatever desired size of tree. Currently project is in progress, but so far it uses systems, and bunch buffer arrays. This project is again inspired by OOP Unity-Technologies/UnityOctree.

    I have implemented 4 types of collision checks. Two are checks, if boundary returns collision (instances), and if ray returns collision. These are the fastest checks, just to validate, if ray intersection, or boundary occur.
    Other 2 checks, return (for now) list of intersected / overlapped instances. Also, system returns nearest instance ID, and its distance. This can be used, to for example make highlighting blocks, as I did in previous updates.
    Octree atm stores instances IDs, which must be unique. These IDs can be paired (but not necessarily) with relevant entities, or entities versions, to construct entity. Then it can be used for whatever is needed in ECS.

    upload_2019-1-6_3-59-19.png

    And because you guys been so cool, here it is so far project with source code, if anyone is interested.
    Antypodish/ECS-Octree

    Shown example uses systems, to generate 100 instances in the octree, and then remove roughly 50 of them.

    This is brief files structure, where mainly ECS part is of the concern. Rest are intermediate stages. But I need to admit, linearization was quite a pain in backside.

    upload_2019-1-6_4-2-35.png

    For now, I have list with things to do. Is far from being optimized.
    At the current stage, I am using systems single threaded only, to check collisions, and to generate actual Game Objects, rather than ECS Mesh Renderers, as I did in previews updates. But this is mainly, so I can debug the systems with ease. It will be converted eventually.

    This is just my short list TODO:
    TODO:
    • Bounds vectors-floats to check.
    • Comply with Burst.
    • Replace collision check List, with BufferArray.
    • Convert GameObjects into ECS mesh renderings.
    • Implement multithreading into systems, for multiple parallel octrees checks.
    • Convert some integers to bytes, and uInt, where applicable.

    Things I need to confirm / check, if standard Unity bounds, are burst-able. I know they use Vector3. I think I have seen in past bounds, with float3, but I need recheck. Otherwise, I will build again my own, as I did in past.


    Anyone interested for a comments, suggestions, or critique, you are most welcome.
     
    siggigg, SugoiDev, Sylmerria and 2 others like this.
  27. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    May I ask you guys for a little advise?

    lets imagine we have some octree structure, with many nodes.
    We want check for collision using multiple raycast.

    I am just thinking, how to best approach this little bit.


    • I can have single entity storing data in buffer, with multiple rays and feed into IJobParallelFor, iterating through element, to get many possible jobified collisions. This approach is best for many raycasts per single a octree. Mind, each octree structure is an entity.
    OR (merging two points together)
    • I can have many entities, storing ray data each and I can feed through IJobParallelFor, or Process Job, iterating through these entities. Then I can have ray pair to target user selected octree entity. This approach is good for pair of any single raycast per single octree.
    OR
    • I can have many entities, storing ray data each and I can feed through IJobParallelFor, or Process Job, iterating through these entities. Then I can have each ray targeting any available of octrees. This approach is good for any single raycast, per all octrees.


    Any thoughts?

    PS.
    I may end up with making all suggested approaches tho.

    Edit:
    I realized, I can merge nicely 1st and 2nd point, as just pair of ray entity / octree entity.
    That of course removes initially mentioned buffer array, in first point.
     
    Last edited: Jan 7, 2019
  28. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Anyway .. so far I got 1000 (1k) rays (each as an entity), against single octree with 47 blocks, using IJobParallelFor and burst, while moving mouse about. approx 5 threads in action.

    In this approach each ray entity, holds information about target octree entity. Even tho, I have only one octree entity (with its structure), in the scene atm. Hence two birds in one hand, in respect to my previous post.

    Not shown on following screenshot, but results return instance ID, and stores in corresponding ray entity. Also, number of intersections also is stored, with closest entity distance.

    upload_2019-1-7_6-1-1.png

    Now I need make a system, with single ray, checking against multiple octrees. That means, I can iterate job instead by rays, like in discussed approach, but by octrees. So for example you have mouse ray, and test many smaller octree structures on threads.
     
    Last edited: Jan 7, 2019
  29. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,247
    It's an, hmm, interesting~~ choice to continue to go back to using entities to create an octree after Joachim earlier discusses in this thread.

    I'm curious why? It seems you went away from this approach at some point then back to it with your most recent iteration.
     
    Last edited: Jan 7, 2019
  30. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,561
    Seems like a cool use for ECS - I'll keep an eye on this project! Good luck!
     
  31. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    True we had discussions before. For which I highly appreciate. But bear in mind, halve year ago, we didn't had BufferArryas. We had instead FixedArray, which was on the way to go away.

    Again, bear in mind, I use only entity per octree structure, where nodes are saved in buffers, not in nodes.
    As per post #21 indicates I had primarly octree nodes made of entities.
    Hence initially point of discussion was, weather store octree nodes as per entities, if that makes sense? Of course want to avoid using entities as individual octree nodes.

    Then NativeArrays works perfectly fine, for single to few octrees. And that worked for me so far.
    Also project proved, is doable.

    However, If I have multiple octrees structures which are changing dynamically, NativeArrays become very awkward to manage. Including resizing and moving all data, by given offset. We can talk even in milions of elements per native array, for certain situations. BufferArrays mainly solve that issue.

    The point is, I need many octrees in my project. Not 5, nor 10, but in 100s. Some small, of few dozens nodes, some big, of +10ks nodes. Again, managing NativeArrays dynamically for such mechanics, is not very convenient. Risking potentially performance hits (short lags), when resizing arrays and shifting data.

    Still could potentially create mechanism, which converts buffer arrays into Native Array, if I find it to prove for Octree significant gain, over BufferArrays.

    However, seams reasonably performance trade of, for maintainability.

    Plus entities also allows nice filtering.

    Does that explains @tertle, why I took that route? Let me know, if it makes sense, or my reasoning is broken :)
    Remember, I am always open for suggestions.
     
  32. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Yep definitely, and thx. ;)

    Extra bonus is such in current iteration, that instances don't have to be necessarily boxes 1x1x1m. Should work with any box shape of Bounds. However, I haven't tested properly other sizes and dimensions.

    Octree Loosnes also should be now supported, which haven't been supported in previous iteration based on NativeArrays. Again, I haven't tested it thoroughly.

    Focusing for now on 1x1x1 instances as blocks.
     
  33. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,247
    You've mentioned this a few times actually. I'm very curious what type of project your working on that requires that many octrees, it's very fascinating. Are you able to share details or not ready to discuss that yet?
     
  34. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    I can discuss sure.
    But before then, I would advise look into my signature WIP project. This will give you initial idea.
    For now just in brief regarding the project; I want have every construct represented in octree form. Including turrets and potential buildings.

    From that point, you should have better overview, of what I am trying to achieve, and from that point, you may have relevant questions, which I am happy to answer.

    There are certain part of the project, which I don't disclose details atm. But octree as well will be utilized. I did already initial prototypes of sub system few months back.
     
  35. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,247
    Cool project, especially the construction.

    I still don't understand this. Especially the need for multiple (100s) of octrees.
     
    e199 likes this.
  36. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Yep, I hope it end up cool, as it sounds now however :)

    I have tons of ways to utilise octrees in my project. It will become handy for example, when calculating blocks projectiles hits, explosions, with batch ray, penetrations and more. I can have many different constructs on the scene. Each can be small as few blocks, to as big, as many thousands blocks. Some representing static buildings, other vehicles, and I got few more types, for now not disclosing.

    Also, I can simply use octree, to partiate a space into sectors, for searching near constructs, or type of constructs. Instead iterating through all available constructs, and checking each distances. And many more usages.

    That saying, I could easily reach 100s of different octrees structures, with being small as few dozens, to thousands of nodes, for more complex structures. I can of course reuse same octrees structures, for same types of constructs.

    On thee hands, I can check fr bear bounding boxes of constructs or objects, before getting even to more complex calculations.

    And these are only some of my ideas, to utilise them in my project :)

    Mind, I don't need to move octree structures, for any of above. They simply stay in 0 origin. Neither I need to rotate them. If anything, I can calculate relative translation to ray for example.

    Does that throw some lights on the octree usage concept?
    Or you maybe have / know better solution (s)? I am happy to hear anyone out.
     
    Last edited: Jan 7, 2019
  37. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Little update adding this time ray highlight.

    Now octree is fully ECS.
    Conducted massive clean up. And added some extras.

    Most relevant systems are burst complaint. There may be still a bit room to work on that.
    Implemented ray, highlighting blocks, for confirming working raycast.
    There is in total 8 example systems. 4 for Ray-Octree, and 4 for Bounds-Octree.
    Where 2 of each are checking only if is colliding, and other two of each, returns list of colliding instances.
    In case of Ray-Octree examples, nearest collision instance is returned, along with its ID and distance.
    One example should be run at the time. Multiple example at the same time were not tested.

    Instances now hold additional information, allowing to store either single ID, which must be unique per tree, or using this ID as Entity index, with conjunction of Entity version. Otherwise version can be ignored.

    TODO:
    * Optimize examples

    Just screenshot
    upload_2019-1-9_8-21-26.png

    And current source code structure
    upload_2019-1-9_8-24-46.png



    Source code updated as well.
    Antypodish/ECS-Octree
    https://github.com/Antypodish/ECS-Octree

    Edit:
    Now quick question.
    My highlight systems simply swap renderer, with relevant material.
    Code (CSharp):
    1. Unity.Rendering.MeshInstanceRenderer renderer = Bootstrap.highlightRenderer ;
    2. ecb.SetSharedComponent <MeshInstanceRenderer> ( entity, renderer ) ;
    For which, I am aware is not ideal, but works well, since I ever swap mostly only one renderer per frame.
    i know there is at least one thread about applying color shader, or relevant.
    Latest topic here
    https://forum.unity.com/threads/sou...ialpropertyblock-support.603553/#post-4037692
    And here
    https://forum.unity.com/threads/mat...shinstancerenderersystem.562369/#post-3773455
    I would need look more deeper into this topic. Not sure yet, if the option is suitable for this application.

    Any thought, or suggestions?
     
    Last edited: Jan 9, 2019
  38. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Bounding octree test, and a bit doddle visualization :)

    upload_2019-1-10_4-14-40.png

    Mainly did work around clearing debugging and updating examples, where added selector, so example can be a bit easier selected, with additional explanations.
    upload_2019-1-10_4-21-26.png

    upload_2019-1-10_4-19-20.png

    Code updated.

    From this point, I am not expecting spending much more on this mini project.
    But I will, try to complete rest of TODO list.
    However, I may potentially add something from time to time.

    Still using for example EntityCommandBuffer with injection. Which technically should be replaced / removed.

    I hope anyone will find something useful of it.
    I am happy on feedback however, so project can be reasonably improved.
     
  39. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,561
    So I guess I'm wondering if you can make an interesting example of a use case for this project, like for instance, a minecraft-like voxel renderer? Not necessarily a full blown game with mechanics, but some kind of fps fly through demo where it allows you to add/remove voxels? Is that something you plan to do?
     
  40. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    I am in process of implementing it into my game. When I got proven working concept I will share results. But I may not necessary share the code from Tha point.

    But yes, you can use potentially, to add blocks, with a little of additional coding. In fact, I did already, in past simple ECS blocks builder, using one of my older octree systems.

    I will see how it goes, and weather decide to share code example.
     
    MD_Reptile likes this.
  41. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Did resolved critical error, which found in bigger octrees.

    Plus another quick vid update with 100k entities.
    It takes moment to load all 100k.


    Mesh Instance Renderer system, takes easily 30ms.
    While tree check of 100k, takes mostly up to 2ms single threaded. But of course debug is active, and running in editor. So should be expecting much faster response.
    Having multiple trees of 1k or 10k, would allow to utilize multi threading, if right mode is selected.

    OctreeExample_Selector.cs now have two variables, which allows quickly change number of instances / entities to add / remove, at startup.

    Code updated.
     
    Last edited: Jan 11, 2019
    Guerro323 and FROS7 like this.
  42. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Further debuging octree, to support regular dimensions of meshes.
    This test concentrates on placing 4 types of blocks in octree. Cube 1x1x1 and boxes 3x1x1, 1x3x1, 1x1x3 of sizes.

    Following test is not planned to be added to current project. But progress is to ensure, that it can be achieved, without errors. It was quite tricky for me, to get to that point, due to numerous of challenges to overcome.
    I hope, that major issues were resolved now.



    Code not yet updated. Will be at some point.
     
    MD_Reptile likes this.
  43. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Just quick one.
    Testing multiple shapes capability.
    But still got one snag, which trying to replicate.

     
    NeatWolf likes this.
  44. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    For those still wondering, why I choose entities with buffer arrays, to make octree, here is recent more practical application, from my main prototype.



    Just short info:
    So basically there are 4 separate octrees on the scene, representing rigid bodies each. But in fact only 3 are visible by the camera in this example. Each octree is also represented by its own entity, while each octree nodes are stored in their corresponding Buffer Arrays.

    Octree ray / boundary checks, are done by pure ECS. Creation and removal is mix of pure and hybrid ECS, since I need send information to OOP, to add / remove colliders and adjust RigidBody mass and center of mass accordingly.

    Further, rendering is done on ECS side as previously described, and physics is on Classic OOP physX side, using my own tweening mechanics, using NativeArrays.

    I haven't found any octree related bugs past few weeks, while I have been a bit short in time, hence I haven't updated code.
    If I catch anything, I will post update.
     
  45. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,247
    You realize you have a bunch [12] of errors soon as the scene starts playing? And you get more [7] errors as your demo continues. You have errors hidden for some reason.

    Off-topic but the block building in pretty sweet.
     
    Antypodish likes this.
  46. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,561
    I figure they must not be serious, perhaps even printed from debug logs, as the system seems to work fine.

    Looks cool! I'm wondering what your plan is when this system is further along, are you making some type of "lego" style game where parts are going to be connected together like in this video?

    Keep at it!
     
    Antypodish likes this.
  47. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Thx guys for a feedback.

    I would replay earlier, but my mobile hate forum pages, with more than 40 posts. It freezes :p

    I use Debug.LogWarning and Debug.LogError, to monitor more critical aspects of systems, where previously had bugs. Now are fixed I hope.
    But these are just in case, something will show up again and brakes, while giving me extra clues. Of course, in such case, these systems have burst disabled. I forgot to enable them, since most of them were shown anyway, on my previous videos.

    For example

    upload_2019-2-7_15-32-14.png

    I just noticed spelling error in debug log, but never mind ... lol

    I got few "A Native Collection has not been disposed" errors at startup, but I was lazy to simply add dispose, at program exit (OnDestroyManager). :p However these are only related to one system, which is outside octree project itself. (now resolved)

    Yep, since these are just my debug logs.
    I will turn them off, when I am happy and certain, it works 100%. Or at least 99.999% ;)

    You can check out my signature first link, for details.
    [WIP] Hovercrafts Sandbox Prototype [ECS based]

    But basically I am replicating my OOP based prototype, I did before, into ECS.
    From there, I want build game onward in ECS.
     
    Last edited: Feb 7, 2019
    MD_Reptile likes this.
  48. MD_Reptile

    MD_Reptile

    Joined:
    Jan 19, 2012
    Posts:
    2,561
    Ahh ok cool, reminds me a lot of games like "TerraTech" and Nition's "Scraps" (both made in unity!).
     
  49. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    4,569
    Yep, while matching well, however, I take my inspiration from (mostly) From The Depths (Unity), Minecraft (Feed The Beast: Industrial Mod Packs) and Factorio.
     
    MD_Reptile likes this.
  50. DavidSWu

    DavidSWu

    Joined:
    Jun 20, 2016
    Posts:
    86
    This is very interesting, thank you for sharing your work.
    I wonder how this compares performance wise with the PhysX MultiBox pruning tree. I do not know how that is implemented but I am guessing that it is an OBB or AABB with a good number of children per node (depending on cache size and branch performance).
    It may not be a fair comparison as the MultiBox system is probably optimized for collisions and rays while an octree can be better for CSG like operations.