Search Unity

[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:
    5,411
    I am, glad finding useful :)

    I haven't run comparison, neither I had plan to.
    To be honest, not sure how I would test raycasting of physX vs ECS octree based approach.
    I suspect method would be, to to place n * 10 thousands of objects in the scene, for each approach, and test raycast then.

    In my case, each octree is static structure stored in own entity. Meaning octree physically never moves, nor rotates. Each octree entity, has buffer arrays, holding structure of nodes. Every node, which is always AABB, stores reference to entity as an option. Technically, don't have to be entity reference. Can be any arbitrary index, to something you like. I.e. to array.
    I would suspect, some similar approach is taken with physX. Then testing OBB vs AABB
    Only thing is moving, is ray for casting, or collision test boundary.

    But in this case, these referenced entities, has mesh component and transform, allowing for rendering.
    Then I take ray cast from mouse, and translate its position and rotation (as per last video), relative to the entity (s) mesh. That relative rotation of ray, is actually applied for the octree.

    To be honest, I am not familiar with MultiBox. But yes, I haven't been optimizing it for boxes / mesh collisions. Providing I got term right, CSG (Constructive Solid Geometry) probably is better fit, for voxel structures is such case.
     
    Last edited: Feb 16, 2019
    MD_Reptile likes this.
  2. DavidSWu

    DavidSWu

    Joined:
    Jun 20, 2016
    Posts:
    121
    It is smart to focus on a specialized solution to your problems. PhysX has to support a general solution that will gracefully handle all sorts of objects and any sort of sparse or dense situation.
    So given time, smarts and diligence I expect that you could outperform them within your problem domain.
    Especially with ECS being compiled down to optimized C++, managed, garbage collected code (even with IL2CPP) has always been a limitation for custom low-level solutions.
    Additionally, your API layer could be a lot more efficient as you can handle the interactions that you want and need and not try to support general purpose callbacks on Unity's main thread.

    It would be nice if Unity as a whole was not such a thread hostile an environment. You can't even do UnityWebRequests completely in a background thread. (most of the heavy lifting is in a background thread, but you still have to bounce back and forth between threads if you want to parse your response in the background).
     
    Last edited: Feb 20, 2019
  3. Liburia

    Liburia

    Joined:
    Jun 24, 2013
    Posts:
    10
    Hey. I'm looking at the Linearized octree MonoBevaiour file BoundsOctree.cs and I can't figure out how you can get a node on demand.

    Let's say I want to get the node that intersects a ray. How would I do it in your system?
     
  4. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,411
    Hi,

    Linearized part is only for testing and debugging as intermediate stage to ECS.
    Shouldn't really be used.

    But if you want look into it, it follows similar principles, as
    OOP-TestingStage/Originals/

    You can see in TestOctree_origin.cs line 116
    Code (CSharp):
    1. bool isColliding = boundsOctree.IsColliding ( ray, out i_instanceIndex, 1000 ) ;
    But there is also GetColliding with ray.
    See in BoundsOctree_origin.cs, line 142
    Code (CSharp):
    1. public void GetColliding(List<T> collidingWith, Ray checkRay, float maxDistance = float.PositiveInfinity)
    So in BoundOctree.cs, line 390, corresponding method is
    Code (CSharp):
    1. public void _GetOctreeColliding ( ref List <int> l_collidingWith, Ray checkRay, out int i_nearestIndex, out float f_nearestDistance, float f_maxDistance = float.PositiveInfinity )

    Just small notice, I found bug with ECS, which I fixed, but forgot to update OOP Linearzied (debugging) version. Hence it is still there in OOP. (But not in original files.)
     
    Liburia likes this.
  5. Liburia

    Liburia

    Joined:
    Jun 24, 2013
    Posts:
    10
    Thank you. I think I understand how you get nodes without iterating. "l_nodeInstancesIndex" is a fully flattened array of all node indices with the size of the maximum depth octree. The ones not existing are set to -1, and you can access the one you want since it's full depth/max size, therefore allowing you to just calculate the needed index.
     
  6. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,411
    Nearly.

    Only that you need take note, there are nodes and instances.
    Nodes are representing structure of the octree.
    Each node, can have 8 children nodes.

    Instances are representing objects (see Originals files).
    In original scripts, when you for example raycast, objects were returned, then you could pass into dictionary, or whatever you needed to do with an objects.
    But ECS don't work with objects. So I used instances storing integers.
    In my project, I modified instance list, to store entities values, both index and version.
    When you raycast through octree nodes, this instance (s) are returned.
    You can use them for whatever you like.
    For example Dictionary, or list.
    You may need to ensure, that instances ints are unique, when instances to nodes are added.

    Each node can have n number of instances (default 1).
    Line 74 in BoundOctree.cs
    Code (CSharp):
    1. const int numInstancesAllowed = 1 ;
    But once value is set, it stays constant per octree.
    So every node can accept up to n objects.
    When exceeding that number, octree node splits, into 8 child nodes.
    Providing minimum node size is not exceeded.

    So yes, children nodes indexes are simply stored in the list, as well as instances ints.
    If I remember correct, you can access first instance of the node, by passing node index, multiplied by numInstancesAllowed. Then you can get further instances of the node (if more than one allowed) by adding offset +1, +2, +3 etc.

    Similarly node children. But this is a bit more complex. But children are grouped of 8, "somewhere" (where spare space was available) in the list.

    Lists length only grows when needed.
     
    Liburia likes this.
  7. Sylmerria

    Sylmerria

    Joined:
    Jul 2, 2012
    Posts:
    237
    @Antypodish Do you have plans for update inject and co ? Nice work by the way
     
  8. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,411
    Thx for mentioning injects.
    Probably I will do at some point. However, it wasn't my priority atm.
     
    Sylmerria likes this.