Search Unity

Struggling to understand how to implement voxel engine in ECS

Discussion in 'Data Oriented Technology Stack' started by norman784, Jul 31, 2018.

  1. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Hi, I tried for a few days but I still struggling to wrap my head around on how to implement voxel engine in ECS, as far I think my engine is pretty good except the mesh generation.

    Let me explain myself on how I implemented so far:

    - Data: just a float array with a size, initially I create an entity for each float a BlockData with the float value, a position and lastly add a tag MidifiedBlockTag. All this happens in a bootstrapMonoBehaviour.
    - ProcessModifiedBlockSystem: simple system that checks the BlockData value to see if the block is empy or not, then apply the respective tag to each Entity (EmptyBlockTag and CheckBlockVisibilityTag).
    - CheckBlockVisibilitySystem: Check if the Block is visible (there are at least one empty block in top, bottom, north, south, east, west of this entity). For visible blocks fires a Job that checks witch face is visible and add a tag with that information VisibleFaces {bool top, bottom, north ...}.
    - RenderVisibleBlocksSystem: Heres where I struggle, because I can try to process and generate the triangles for each block, but how do I group them, I need to chunkify this data also, but was trying to do one mesh first then jump into trying to work with multiple meshes. So the main idea was to group somehow the blocks, create the triangles for each block, then put them all together and pass it somehow to the chunk mesh.

    Thanks.
     
  2. dartriminis

    dartriminis

    Joined:
    Feb 3, 2017
    Posts:
    154
    You could use a SharedComponent to group the voxels by chunk. Then you can filter your ComponentGroups to get all the voxels in a particular chunk, and (bonus) they'll be contiguous in memory.

    Alternatively, instead of having an entity per voxel, you could have entity for chunk. Each chunk would have an array of voxels, and your systems would operate on chunks in place of voxels.

    Hope that helps point you in the right direction.
     
  3. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Thanks.

    How can I have an array of voxels inside a chunk? with NativeArray? I mean having a component with a NativeArray with the float values or maybe some reference to the block entities. (Also about this topic can I use this unmanaged collections inside a component? but how I dispose them later? I didn't see any method on the component data to do this, or I need to do when the entity is destroyed?)

    Could you provide me some pseudocode or pseudo implementation?

    Are you saying that I can create a shared component an use as a chunk and assign them to each entity inside that chunk, how? (besides I don't get it how to achieve them, if I think as GameObjects they will be nested and will be easier to know the parent of each voxel) I'm slow to catching this concepts but I really want to understand them. (I finished this weekend every video linked in the ECS repo and some others I found on youtube, but the repo ones I think don't cover at least in deep what I want to do, saw older posts here from months ago talking about voxels and terrain generation but only talk and no code at all).

    And about having one entity per voxel I don't think there will be an issue, because I later on can optimize them and also each entity can manage their own input (like adding or subtracting values to it, to be full, half or empty block), but that is just my goal, but I'm not so far done to start doing that part.

    PD: seems that every time I've an answer I've get more and more questions.

    Questions (just a summary of my questions above)
    1 - How can I have an array of voxels inside a chunk? (maybe with NativeArrays)
    2 - Can I have unmanaged collections inside a component?
    3 - If 2 is true, how can I dispose them?
    4 - Could you provide me some pseudocode or pseudo implementation? (as example / reference)
    5 - Are you saying that I can create a shared component an use as a chunk and assign them to each entity inside that chunk, how?

    Regards
     
  4. dartriminis

    dartriminis

    Joined:
    Feb 3, 2017
    Posts:
    154
    1. & 4. You can use a regular MonoBehaviour with a NativeArray:
    Code (CSharp):
    1. public class Chunk : MonoBehaviour
    2. {
    3.     public NativeArray<float> Voxels;
    4.     public Awake()        => Voxels = new NativeArray<float>(...);
    5.     public OnDestroy() => Voxels.Dispose();
    6. }
    7.  
    8. public class SomeChunkSystem
    9. {
    10.     private struct ChunkGroup
    11.     {
    12.         public readonly int Length;
    13.         public ComponentArray<Chunk> Chunks;
    14.     }
    15.  
    16.     [Inject] private ChunkGroup _chunkGroup;
    17. }
    Or, you could create one large array, and a Chunk could be an index in to that array.
    Code (CSharp):
    1. public struct Chunk : IComponentData
    2. {
    3.     public int Start;
    4. }
    5.  
    6. public class SomeChunkSystem
    7. {
    8.     public NativeArray<float> Voxels;
    9.     OnCreateManager   => Voxels = new NativeArray<float>(...);
    10.     OnDestroyManager => Voxels.Dispose();
    11.  
    12.     private struct ChunkGroup
    13.     {
    14.         public readonly int Length;
    15.         public ComponentDataArray<Chunk> Chunks;
    16.     }
    17.  
    18.     [Inject] private ChunkGroup _chunkGroup;
    19. }
    2. Not an IComponentData or ISharedComponentData, you'd have to use a MonoBehaviour.

    5. If you define a Chunk as:
    Code (csharp):
    1.  public struct Chunk : ISharedComponentData { int Id; }
    then when you create your block entities, just add this shared component to each entity:
    Code (csharp):
    1. var e = entityManager.CreateEntitiy(blockArchetype);
    2. entityManager.SetSharedComponentData(e, new Chunk { Id = ... });
    Take a peek at the MeshInstanceRendererSystem entities package for a good example on filtering by shared components.
     
  5. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Thanks, definitely you gave me a lot to play with now, will check this and come back later to share my experience or ask more questions.
     
  6. Fabrice_Lete

    Fabrice_Lete

    Unity Technologies

    Joined:
    May 5, 2018
    Posts:
    15
    During our last hackweek a small team implemented a voxel engine in pure ECS, using one entity per block. Please note that this was more an experiment and a stress test than something we would recommend.

    Even if we could handle a pretty large amount of blocks this way, all the proximity queries became a little awkward. Since there is no guarantee over the order of entities, finding the "block on the left of block X" isn't as easy as indexing an array. The approach suggested by @dartriminis sounds promising.
     
    Creepgin and starikcetin like this.
  7. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    I didn't have time yet to try what @dartriminis suggested, but I don't find too much issues if you could just create a hash array for the entities, this is how I was approaching (take into account that I didn't get so far and I was playing with only a few blocks).

    Code (CSharp):
    1. public class ProcessNonEmptyBlockPositionSystem: JobComponentSystem
    2. {
    3.     private class BlockBarrier: BarrierSystem {}
    4.  
    5.     private struct VisibleBlocks
    6.     {
    7.         [ReadOnly] public SubtractiveComponent<EmptyBlockTag> Empty;
    8.         [ReadOnly] public ComponentDataArray<BlockData> Data;
    9.         public EntityArray Entities;
    10.         public readonly int Length;
    11.     }
    12.  
    13.     private struct CheckBlockVisibilityJob : IJobParallelFor
    14.     {
    15.         public EntityArray Entities;
    16.         [ReadOnly] public ComponentDataArray<BlockData> CurrentBlock;
    17.         [ReadOnly] public NativeHashMap<int3, float> Neighbors;
    18.         [ReadOnly] public EntityCommandBuffer.Concurrent CommandBuffer;
    19.  
    20.         private bool IsFaceVisible(BlockData block, string visibleFace)
    21.         {
    22.             int3 position;
    23.          
    24.             switch (visibleFace)
    25.             {
    26.                 case "top": position = new int3(block.Position.x, block.Position.y + 1, block.Position.z); break;
    27.                 case "bottom": position = new int3(block.Position.x, block.Position.y - 1, block.Position.z); break;
    28.                 case "east": position = new int3(block.Position.x + 1, block.Position.y, block.Position.z); break;
    29.                 case "west": position = new int3(block.Position.x - 1, block.Position.y, block.Position.z); break;
    30.                 case "sourht": position = new int3(block.Position.x, block.Position.y, block.Position.z + 1); break;
    31.                 case "north": position = new int3(block.Position.x, block.Position.y, block.Position.z - 1); break;
    32.                 default: return false;
    33.             }
    34.          
    35.             return Neighbors.TryGetValue(position, out var value) && value > 0.09f;
    36.         }
    37.      
    38.         public void Execute(int index)
    39.         {
    40.             CommandBuffer.RemoveComponent<CheckBlockVisibilityTag>(Entities[index]);
    41.          
    42.             var top = IsFaceVisible(CurrentBlock[index], "top");
    43.             var bottom = IsFaceVisible(CurrentBlock[index], "bottom");
    44.             var north = IsFaceVisible(CurrentBlock[index], "north");
    45.             var south = IsFaceVisible(CurrentBlock[index], "south");
    46.             var east = IsFaceVisible(CurrentBlock[index], "east");
    47.             var west = IsFaceVisible(CurrentBlock[index], "west");
    48.  
    49.             if (top || bottom || north || south || east || west)
    50.             {
    51.                 CommandBuffer.AddComponent(Entities[index], new VisibleFaces
    52.                 {
    53.                     Top = top,
    54.                     Bottom = bottom,
    55.                     East = east,
    56.                     North = north,
    57.                     South = south,
    58.                     West = west
    59.                 });
    60.             }
    61.         }
    62.     }
    63.  
    64.     [Inject] private VisibleBlocks Blocks;
    65.     [Inject] private BlockBarrier Barrier;
    66.  
    67.     private NativeHashMap<int3, float> BlockPositions;
    68.  
    69.     protected override JobHandle OnUpdate(JobHandle inputDeps)
    70.     {
    71.         BlockPositions = new NativeHashMap<int3, float>(Blocks.Length, Allocator.Temp);
    72.  
    73.         for (var i = 0; i < Blocks.Length; i++)
    74.         {
    75.             BlockPositions.TryAdd(Blocks.Data.Position, Blocks.Data.Value);
    76.         }
    77.  
    78.         var checkVisibilty = new CheckBlockVisibilityJob
    79.         {
    80.             Entities = Blocks.Entities,
    81.             CurrentBlock = Blocks.Data,
    82.             Neighbors = BlockPositions,
    83.             CommandBuffer = new BlockBarrier().CreateCommandBuffer()
    84.         };
    85.  
    86.         return checkVisibilty.Schedule(Blocks.Length, 64, inputDeps);
    87.     }
    88.  
    89.     protected override void OnStopRunning()
    90.     {
    91.         BlockPositions.Dispose();
    92.     }
    93. }
    This example lacks of what was suggested in this thread, but the idea is there, if you have some examples that want to share will be cool, my idea is to have a voxel render system capable to render Cubic, Marching Cubes, Marching Tetrahedra (this 3 I already have in another project in unity, so will not be hard to convert to ECS when I can understand better this architecture), Surface Nets and Dual Contouring, when having all this implemented and decent performance will open source them.
     
  8. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
  9. illinar

    illinar

    Joined:
    Apr 6, 2011
    Posts:
    560
    I did chunks like this (abandoned the project):
    var chunkEntity = EntityManager.CreateEntity(ComponentType.FixedArray(typeof(byte), 10000), typeof(Chunk));


    So no monobehaviours. And to query chunks, I would put them all in a 3D array inside a system and query that. The performance would be quite good. I don't see a case where hashmap would be preferable..

     private bool IsFaceVisible(BlockData block, string visibleFace)


    Isn't ist very slow and bad practice using strings like that? Why not enum??
     
  10. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Thanks @Antypodish, I would check it out when I've got time to continue experimenting.

    @illinar thanks to point me out, also I didn't know if enums are treated like static variables, so I just ended up using strings, but if they work I just can change them. I didn't intend to do this the most optimal way, just to make it work and later on optimize it.

    Talking about enums if declare them as `enum Face: byte {}` is more performant to `enum Face {}` or is the same?

    I generally use a flat array and to get the value just use like this `blocks[x + y * height + z * depth]`, I'm quite sure that this way is faster than a multidimensional array.
     
  11. illinar

    illinar

    Joined:
    Apr 6, 2011
    Posts:
    560
    Yes, by 3D array I just mean a linear array with a 3D layout. Should be significantly faster than hashing if you need a lot of querying.

    enum Face: byte {}
    ?

    That probably would be a micro-optimization. Usually, default int is most performant anyway.

    I'm currently trying to figure out the best way of maintaining the internal arrays for querying. So far I think creating a new array is not a problem, but with the upcoming reactive systems, we might be able to update them more efficiently by updating only the elements that got changed. Looking forward to seeing how those systems actually work.
     
  12. dartriminis

    dartriminis

    Joined:
    Feb 3, 2017
    Posts:
    154
    The only potential problem with the FixedArray approach would be memory management, and it largely depends on how you're handling your entities, if your using an shared components, and how big that array is.
     
  13. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    Yep using strings is not the best idea to access element.
    I had always instead strings, and enumerators. It is also easy to look for all places, where such name (enum) occurred. Or even refactor. With string, not only is prone to errors, but harder to debug.

    Anyway, what I wanted to ask, is that in pure ECS I understand, there is no List? How dynamic arrays can be are handled, with changeable sizes? For example, you want to reference multiple voxels in array, by storing index, or maybe other method?
     
  14. dartriminis

    dartriminis

    Joined:
    Feb 3, 2017
    Posts:
    154
    @Antypodish I Think NativeList<> is what you are looking for.
     
  15. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Yes, this is pure ECS, right now each voxel is an entity, so they operate completely independent of each other. What I'm trying now (to remove the need of an NativeHashMap to check the neighbor chunks) is to add IComponentData that has a reference to a ISharedComponentData (the BlockData, this component has the float value, see my blocks are not only empty and full, they can be half empty, and a int 3position).

    So whenever I need to update the block and check the exposed faces I can just check the BlockNeighbors. Below is a representation of the components mentioned earlier.

    Code (CSharp):
    1. public struct BlockData: ISharedComponentData
    2. {    
    3.     public float Value;
    4.     public int3 Position;
    5. }
    6.  
    7. public struct BlockNeighbors: IComponentData
    8. {
    9.      public BlockData Top;
    10.      public BlockData Bottom;
    11.      public BlockData North;
    12.     public BlockData South;
    13.     public BlockData East;
    14.     public BlockData West;
    15. }
    I cannot tell you right now if this works or not because is a very early prototype, so I'm playing with different ideas on how I see the engine working with the basic knowledge I have about ECS.

    Also about List and dynamic arrays, with a voxel engine I don't think you need dynamic arrays, because you know how many voxels are in each chunk.

    Lastly I'm curious on your implementations anyway.
     
  16. illinar

    illinar

    Joined:
    Apr 6, 2011
    Posts:
    560
    @Antypodish So, in my example you can have Fixed arrays on entities, but they can contain any number of elements up to 16kb data per entity, so if memory is not an issue you could store a number of items in it separately. You can also have any Lists in ISharedComponentData just be aware of its downsides.

    I think collections support for IComponentData is coming soon though, which is great because FixedArrays are currently a mess without full API support.
     
  17. illinar

    illinar

    Joined:
    Apr 6, 2011
    Posts:
    560
    That's possibly a great way to do it, I considered something similar myself but in my case, it made things too complex, because every change to the block data must be propagated to its neighbors. Ideally, you would be able to just change the block and have ONE system copying changes to neighbors. So possibly Reactive systems to the rescue, or you could make it work if you design around it. Many pitfalls though.
     
  18. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,650
    I built a voxel engine a few months ago and I've discussed it a few times on here. Happy to answer any questions on the way i did it.

    An old screenshot can be found here: https://i.imgur.com/B6JlTQb.jpg

    Originally I tried the, every voxel is a entity but this ended up being a disaster. I changed to using the chunk approach and it works well. I've even built a pathfinding system and fog of war system on top of it.

    I'd post some code but I'm currently in process of refactoring it to cleanup the greedy meshing job as well as improving the back face culling.
     
    Last edited: Aug 1, 2018
  19. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    Surely that useful. But I believe, loosing on benefits of pure ECS performance?


    I will look into that thx. Still learning building something simple atm. Getting slowly there.


    My current OOP based project, involved structures voxel a like. Thing is, I could add and remove blocks, which respectively expanded, or shrunk whole voxel structure. Therefore I was interested in form of dynamic array / lists.
    In my design, I could have blocks, which are oriented in any of its principle 8 directions, with additional rotation. Each block having reference to its global neighbor, as if not rotated, and local neighbor, as if rotated. But with OOP that was relatively easy to do, using references to relevant blocks. Also, my structure could move, with all child blocks. Just like a build vehicle.

    I would like port my design to ECS. Hence, facing similar challenges.
    I presume, we are discussing about similar approach here, where blocks orientation is not necessary required.

    Additionally, I am currently learning and attempting to port octrees, to ECS, which could allow for fast raycast of blocks (node netities), or test for boundaries collisions (not using collider).
    Unity-Technologies/UnityOctree
    https://github.com/Unity-Technologies/UnityOctree
    There is not much to it, but while learning on ECS, I try to figure out, how to best implement it.


    tertle, I have been a bit nosy and looked into you posts.
    There are chances, that I missed most important one, but never the less.
    I found some interesting discussions ones

    Updating Meshes in Hybrid ECS
    Leading to Firefly at github https://github.com/keijiro/Firefly
    Great source.

    And also
    MeshInstanceRenderSystem (poor) performance

    +extra
    Greedy Voxel Meshing
    http://www.gedge.ca/dev/2014/08/17/greedy-voxel-meshing

    Surely you experience will be highly beneficial to the community ;)
     
    Last edited: Aug 2, 2018
  20. AriaBonczek

    AriaBonczek

    Unity Technologies

    Joined:
    Jul 20, 2018
    Posts:
    24
    We are planning to implement a better way of setting up groups of entities with a static topology that takes better advantage of their locality and empowers you to index these elements. That way, instead of storing references to adjacent blocks (which is not going to be burst-compatible), you can store indexes into your component stream and access them that way. No current timeline on it, but this gives us another great use case!
     
    Sarkahn, FROS7, Creepgin and 2 others like this.
  21. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Yes, I was experimenting with that and saw that burst was not working on that job, also was hopping that something like this works to take advantages of the reactive system (using tags) but was not a good idea, I will now go with Chunk system instead of one entity per voxel. But you gave me a good idea, I will try one more and my block data will only contain their current index in the chunk data values array (a shared component) and the chunk neighbors will also contain their index, so I think will be easier to access the data.

    The only concern about this issue I'm not sure of the cost of updating a shared component, because as far I know you need to instantiate a new shared component each time your data changes, so each time my data changed I created a new component, because I'm currently not aware on how to get the data from a job and pass it to another besides assign that data to a component data, will be very helpful to know a way to achieve this.
     
  22. illinar

    illinar

    Joined:
    Apr 6, 2011
    Posts:
    560
    @norman784 Look, if you don't have some weird sparse voxel structures and just have a fixed 3D grid (in a linear array) of chunks and a 3D grid of voxels in each chunk, you don't have to store the neighbors, you can just use their 3D positions to access them. For now, just copy all chunk entities into 3D indexed array each frame and access them directly by index. And when the new indexing of entities will be implemented as @AriaBonczek mentioned (great news!) you can switch to directly accessing chunk entities and their voxels from the injected component data streams.

    Storing copies of entity data can lead to a lot of bugs and headaches.
     
  23. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,650
    If you're storing a NativeArray<T> within your SharedComponent and that's all you modify, you don't need to set the shared component to update the array. It basically just holds a reference.

    The one thing to note is when editing references (native containers as well) within SharedComponents, ECS does not know this so can't properly schedule JobComponentSystems if you modify the array in 2 separate systems. A solution, and what they did in part of the nordeus demo, is to inject the JobComponentSystem into the final ComponentSystem that writes the data back to the mesh and call complete(). Not ideal, but it works. I'd love to here a better solution.
     
    Last edited: Aug 2, 2018
  24. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    I agree. Since you always know position and offset of any block you need.
    If you have 2x3x4 grid for example and size is always fixed, you can just access any element from the linear array, by multiplying offset, for each dimensions. First element will be index 0 on layers XYZ. You want to access second 0,1,0 layer, then index will be 2. If you want access 1,2,0 then you got index offset 1x3x4 + 2+2+0. Something like that, if I haven made mistake in logic.

    On other hand, I personally can not use it, as my dimensions on each axis may change.
     
  25. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    Regarding storing neighbors in general, I wrote a question in separate thread. Which I think this may be relevant here as well.

    Edit: This of course assume same type of componentsData, across parent/children.
     
    Last edited: Aug 2, 2018
  26. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Why do you want to use this approach? I was thinking in just maintain my chunks sizes across my world, but there is one think that you could do (at least in my case, because my world will have a tons of islands of different sizes and shapes), I would just have chunks where I needed, i.e. if my island has a C shape then the chunks will be on that positions only, the rest will be empty, also with the height of each chunk I just will put another chunk above only if theres a mountain that exceeds the height of the current chunk, and lastly but not least important you can add a flag maybe to your chunk, that will indicate in which row (Y axis) your chunk has the first solid block so you can save some iterations there.
     
  27. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    This is because, in my approach, the player is a designer and creates the construct of their desire. So in theory, it can be small as one voxel (block), or wide as 10k blocks while thin as 5 blocks. Or cubic 33x33x33. Then, I expect having multiple constructs on same scene. If I store chunks, with empty unused voxels, then the memory size will propagate dramatically, as number of constructs grows. Specially, I expect blocks, to have more than handful number of variables. But I try keep them down to minimum.
    If that makes sense?
     
  28. sterlingcrispin

    sterlingcrispin

    Joined:
    Oct 23, 2013
    Posts:
    12
  29. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    5,379
    I did study many approaches and had some brief discussions here and there.
    Problem with most existing libraries, is that they need to be completely rewritten for Unity ECS.
    So is better start from scratch.
    I wrote ECS Octree prototype with ray casting 500k cubes.
    I did mesh merging, for mesh count reduction. Something equivalent to greedy meshing, but actually without manipulating vertices.
    And I was experimenting with LOD. But I need back to it.

    Btw. thx for links.
     
    Enzi and wobes like this.
  30. norman784

    norman784

    Joined:
    Mar 9, 2014
    Posts:
    19
    Thanks @sterlingcrispin for the links.

    I really didn't get too much from the links that was provided about OpenVDB (because they are too complicated for me right now) but there is a talk from one of the authors explaining a lot of stuff. I recommend you to check it out when you have time
    .