[ShowOff] ECS based Voronoi Generation learning process

Hey all,

Thank you to everyone who has taken the time to answer my numerous, and often stupid, questions over the last couple of days. You have all been really helpful, and in the interest of giving back, I wanted to type of a rather detail post about what I recently built as a learning process.

I already had this implemented in "standard" Unity as an Editor based tool, but I wanted to re-implement it using runtime ECS.

Essentially what this does is build a relaxed Voronoi diagram. The end result is a series of entities, with each rep[resenting a final MapCell based on the Sites of the Voronoi Diagram. As a last step I spawn GameObjects in order to render the actual edges of each cell for visualization to verify it generated what I expected it to.



This project uses four Entity Archetypes, four Components, and Three different Systems. It is fully "reactive" rather than a hardcoded series of steps as suggested by @5argon in one of my many threads. This means that the "map generation" is always running and looking for the proper entities and just does its thing when its sees them, each step proceeding as the data is transformed along the way. When the "Generate" button is clicked in the UI (not seen in the screenshot), a series of entities is created. The systems then see those entities and shepherd them through the process, not caring.

Components
VoronoiPositionData : float2

Code (CSharp):

1.     public struct VoronoiPositionData : IComponentData
2.     {
3.         public float2 Value;
4.     }
5.  

VoronoiRelaxationData : int

Code (CSharp):

1.     public struct VoronoiRelaxationData : IComponentData
2.     {
3.         public int RelaxationsRemaining;
4.     }
5.  

DynamicBuffer<VoronoiEdgePoint> : float2[]

Code (CSharp):

1.     [InternalBufferCapacity(12)]
2.     public struct VoronoiEdgePointElement : IBufferElementData
3.     {
4.         public float2 Value;
5.  
6.         public static implicit operator float2(VoronoiEdgePointElement element)
7.         {
8.             return element.Value;
9.         }
10.  
11.         public static implicit operator VoronoiEdgePointElement(float2 f)
12.         {
13.             return new VoronoiEdgePointElement {Value = f};
14.         }
15.     }
16.  

GameObjectRepFlag

Code (CSharp):

1.     public struct GameObjectRepFlag : IComponentData {}
2.  

Entity Archetypes
I know these aren't really defined exactly, but it helps me to think of them as a way to provide scope to what I'm seeing. One of the largest problems I am having adapting to ECS code in general are the mental demands of seeing the big picture, so this helps a bit.

MapSeedPoint : VoronoiPositionData, VoronoiRelaxationData
When the "Generate" button is clicked, these entities are what are created to jump start the process. A MapSeedPoint is essentially a candidate point that will eventually be used to generate the Voronoi diagram. These entities have a VoronoiPositionData component and a VoronoiRelaxationData component.

MapSite: VoronoiPositionData, VoronoiRelaxationData, DynamicBuffer<VoronoiEdgePoint>
Seed points are consumed to generate the Voronoi diagram. As a byproduct of that transformation, these new entities are emitted. Each represents one site in the Voronoi diagram. In addition to copying over the Position and Relaxation data, we add a DynamicBuffer<VoronoiEdgePoint> component to the new entities. This buffer is a list of points which make up the geometric edges of the site in the diagram.

MapCell: VoronoiPositionData, DynamicBuffer<VoronoiEdgePoint>
These represent the final, fully relaxed, Voronoi Site which is now a Cell in the map. These entities contain Position and EdgePoints, but Lose the Releaxation data once they are fully relaxed.

VisualMapCell : VoronoiPositionData, DynamicBuffer<VoronoiEdgePoint>, GameObjectRepFlag
These are essentially the same thing as the MapCell, but have been processed as a final step to create visual GameObject representations. The flag component is added so that they don't get created again to infinity and beyond.

Systems
We start by generating MapSeedPoints which are just random points in a defined space along the XY plane, and contain a preset Relaxation value representing how many times the final diagram will be relaxed. For this right now I used a value of 10, so the final Voronoi Diagram represents a diagram with 10 relaxation iterations.

The first system, PointsToSitesSystem, is probably the most complicated. It gathers up any seed points it finds, and puts the points positions into a NativeArray, as well as noting the Relaxation number. It then deletes the entities. Next, it generates the Voronoi Diagram from the points stored in the NativeArray. This is a main thread job as I'm using a backend library that isn't setup for Unity ECS. Once the diagram is generated, the system iterates through all of the Sites in the diagram, and creates a new MapSite entity from each site. It stores the same Position point that was from the original Seed point, as well as the points that make up the edges of this site. It also sets the Relaxation to what was recorded. If the relaxation is <= 0 it removes that component. This was an important thing I learned. Instead of checking the value of Relaxation at various points to see if it was above 0, it is simpler to just remove the component once it drops below 0. Then if the component is present you know it is above 0 by the very nature of its existence.

Code (CSharp):

1.  
2. using Unity.Collections;
3. #if USE_ENTITIES
4. using System.Collections.Generic;
5. using Unity.Entities;
6. using Unity.Jobs;
7. using Unity.Mathematics;
8. using UnityEngine;
9. using VoronoiLib;
10. using VoronoiLib.Structures;
11.  
12. namespace voronoi.Entities
13. {
14.  
15.     /// <summary>
16.     /// Looks for seed points, if found, generates a voronoi diagram from the seed points, and creates site entities
17.     /// </summary>
18.     public class PointsToSitesSystem : JobComponentSystem
19.     {
20.         // gather up all the points into an array
21.         // generate voronoi from points
22.         // add edges to each point as appropriate (should we try to keep the same entities and just add the new data or make new entities and destroy the old ones?)
23.         private EntityQuery query;
24.         private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
25.        
26.         protected override void OnCreate()
27.         {
28.             var queryDesc = new EntityQueryDesc
29.             {
30.                 All = new ComponentType[]{ComponentType.ReadOnly<VoronoiPositionData>(), typeof(VoronoiRelaxationData)},
31.                 None = new ComponentType[]{typeof(VoronoiEdgePointElement)}
32.             };
33.             query = GetEntityQuery(queryDesc);
34.             endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
35.         }
36.  
37.         protected override JobHandle OnUpdate(JobHandle inputDeps)
38.         {
39.             var relaxationsArray = new NativeArray<int>(1, Allocator.TempJob);
40.             var positionArray = new NativeArray<VoronoiPositionData>(query.CalculateEntityCount(), Allocator.TempJob);
41.             var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer().ToConcurrent();
42.  
43.             // Get all entities that have a position for a voronoi point, and a relaxation
44.             // Store the relaxation and positions and delete the entities
45.             JobHandle getPositions = Entities.WithNone<VoronoiEdgePointElement>()
46.                 .ForEach((Entity entity, int entityInQueryIndex, in VoronoiPositionData position, in VoronoiRelaxationData relaxations) =>
47.             {
48.                 positionArray[entityInQueryIndex] = position;
49.                 relaxationsArray[0] = relaxations.RelaxationsRemaining;
50.                 ecb.DestroyEntity(entityInQueryIndex, entity);
51.             }).Schedule(inputDeps);
52.             endSimulationCommandBufferSystem.AddJobHandleForProducer(getPositions);
53.             getPositions.Complete();
54.            
55.             // Now we have an array of point positions, so generate a voronoi diagram from those
56.             List<FortuneSite> sites = new List<FortuneSite>(positionArray.Length);
57.             foreach (var positionData in positionArray)
58.             {
59.                 sites.Add(new FortuneSite(positionData.Value.x, positionData.Value.y));
60.             }
61.             positionArray.Dispose();
62.             FortunesAlgorithm.Run(sites, 0, 0, 1000, 1000);
63.            
64.             // Next, take the voronoi sites generated and make new entities with the site positions and the edges
65.             // Also copy over the relaxation from the previous point set
66.             EntityManager manager = World.EntityManager;
67.             EntityArchetype archetype = manager.CreateArchetype(typeof(VoronoiPositionData), typeof(VoronoiRelaxationData), typeof(VoronoiEdgePointElement));
68.             foreach (var site in sites)
69.             {
70.                 Entity newEntity = manager.CreateEntity(archetype);
71.                 manager.SetComponentData(newEntity, new VoronoiPositionData{Value = new float2(site.x, site.y)});
72.                 if (relaxationsArray[0] >= 0)
73.                 {
74.                     manager.SetComponentData(newEntity, new VoronoiRelaxationData{RelaxationsRemaining = relaxationsArray[0]});
75.                 }
76.                 else
77.                 {
78.                     manager.RemoveComponent<VoronoiRelaxationData>(newEntity);
79.                 }
80.                 DynamicBuffer<VoronoiEdgePointElement> buffer = manager.AddBuffer<VoronoiEdgePointElement>(newEntity);
81.                 foreach (Vector2 sitePoint in site.Points)
82.                 {
83.                     buffer.Add(new VoronoiEdgePointElement {Value = new float2(sitePoint.x, sitePoint.y)});
84.                 }
85.             }
86.  
87.             relaxationsArray.Dispose();
88.  
89.             return default;
90.         }
91.     }
92. }
93.  
94. #endif

The next system, RelaxSitesSystem, is rather simple. It is simply looking for MapSite entities (which the previous system emitted) and when it finds them it calculates the centroid of that site, updates its Position to be that point, then removes the EdgePoints component. Finally it decrements the Relaxation data. The end result is we have a new MapSeedPoint but one that has been moved slightly by the relaxation. That means the first system, PointsToSitesSystem, will pick it up as if it was a freshly created point and generate a new diagram. I find the elegance of this to be sweet.

Code (CSharp):

1. using Unity.Entities;
2. using Unity.Jobs;
3. using Unity.Mathematics;
4.  
5. namespace voronoi.Entities
6. {
7.     public class RelaxSitesSystem : JobComponentSystem
8.     {
9.         // Looks for entities that represent voronoi sites with > 0 relaxations left on them
10.         // Then relaxes them by computing a new centroid
11.         // The EdgePoints data is then removed making them valid to get turned into a new voronoi
12.         private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
13.         protected override void OnCreate()
14.         {
15.             endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
16.         }
17.         protected override JobHandle OnUpdate(JobHandle inputDeps)
18.         {
19.             var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer().ToConcurrent();
20.  
21.             JobHandle relaxPoints = Entities.ForEach((Entity entity, int entityInQueryIndex, ref VoronoiPositionData position, ref VoronoiRelaxationData relaxation,
22.                 in DynamicBuffer<VoronoiEdgePointElement> edgePoints) =>
23.                 {
24.                     relaxation.RelaxationsRemaining = relaxation.RelaxationsRemaining - 1;
25.                     float2 centroid = float2.zero;
26.                     float determinant = 0;
27.                     int numVertices = edgePoints.Length;
28.  
29.                     for (var i = 0; i < numVertices; i++)
30.                     {
31.                         int j;
32.                         if (i + 1 == numVertices)
33.                             j = 0;
34.                         else
35.                         {
36.                             j = i + 1;
37.                         }
38.                
39.                         // compute the determinant
40.                         float2 thisPoint = edgePoints[i].Value;
41.                         float2 refPoint = edgePoints[j].Value;
42.                         float tempDeterminant = thisPoint.x * refPoint.y - refPoint.x * thisPoint.y;
43.                         determinant += tempDeterminant;
44.  
45.                         centroid.x += (thisPoint.x + refPoint.x) * tempDeterminant;
46.                         centroid.y += (thisPoint.y + refPoint.y) * tempDeterminant;
47.                     }
48.            
49.                     // divide by the total mass of the polygon
50.                     centroid.x /= 3 * determinant;
51.                     centroid.y /= 3 * determinant;
52.  
53.                     position.Value.x = centroid.x;
54.                     position.Value.y = centroid.y;
55.                    
56.                     ecb.RemoveComponent<VoronoiEdgePointElement>(entityInQueryIndex, entity);
57.                 }).Schedule(inputDeps);
58.            
59.             endSimulationCommandBufferSystem.AddJobHandleForProducer(relaxPoints);
60.             return relaxPoints;
61.         }
62.     }
63. }

The entities will essentially just bounce back and forth between those two systems, generating a diagram, relaxing the points, generating a new diagram, etc until the relaxation count reaches 0. At that point we end up with an Entity that has a Position, and EdgePoints but no Relaxation component which means both systems will ignore it, and its Archetype is now a MapCell.

The last system, VoronoiSiteToMapCellSystem, sees these final MapCell entities, and creates a GameObject with a LinRenderer from them so that there is a visual result.

Code (CSharp):

1. using Unity.Entities;
2. using Unity.Jobs;
3. using UnityEngine;
4. using voronoi.Entities;
5.  
6. namespace galaxias.ecs
7. {
8.     // This system makes a GameObject from the final voronoi site for visualization
9.     [AlwaysSynchronizeSystem]
10.     public class VoronoiSiteToMapCellSystem : JobComponentSystem
11.     {
12.         private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
13.         protected override void OnCreate()
14.         {
15.             endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
16.         }
17.         protected override JobHandle OnUpdate(JobHandle inputDeps)
18.         {
19.             var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer();
20.             Entities.WithNone<GameObjectRepFlag>().WithNone<VoronoiRelaxationData>().ForEach((Entity entity, int entityInQueryIndex, in VoronoiPositionData position, in DynamicBuffer<VoronoiEdgePointElement> edgePoints) =>
21.             {
22.                 string name = $"MapCell {position.Value.x},{position.Value.y}";
23.                 ecb.AddComponent<GameObjectRepFlag>(entity);
24.                 GameObject go = new GameObject(name);
25.                 LineRenderer lineComponent = go.AddComponent<LineRenderer>();
26.                 Vector3[] points = new Vector3[edgePoints.Length];
27.                 for (int i = 0; i < edgePoints.Length; i++)
28.                 {
29.                     points[i] = new Vector3(edgePoints[i].Value.x, edgePoints[i].Value.y, 0f);
30.                 }
31.  
32.                 lineComponent.positionCount = edgePoints.Length;
33.                 lineComponent.SetPositions(points);
34.                 lineComponent.loop = true;
35.                 lineComponent.widthMultiplier = 0.5f;
36.             }).WithoutBurst().Run();
37.  
38.             return default;
39.         }
40.     }
41. }

 

Now I want to stress that this was a first learning effort, done in pretty much a GameJam style over just a couple days. I'm 100% certain what I have here is not the best way to do any of this. In some cases I may even be completely going in the wrong direction! The performance (which I sort of showed in the screenshot) for generating a 1,000 point diagram is not really as good as I was hoping. I think the editor version I have is faster.

I would very much appreciate any constructive criticism as to what I may be doing wrong, could do better, etc. And if anyone wants to look at the profiler data, I will attach it here. Actually its too big to attach here, but I can make it available on request through Dropbox or something if anyone actually wants to dig into it.

 

Hi I read them roughly, but note that I am not familliar with generative CG

relaxationsArray is a "utility" NativeArray intended to be a return portal from your job, you can allocate it in OnCreate and dispose in OnDestroy. Then you could keep reusing it on any OnUpdate.

The gather job (linearize a single component to NativeArray not connected to ECS database) for your external lib could be changed to eq.ToComponentDataArray to do the same in a faster way. You collect things one by one but that method do it with memcpy per chunk. You then can remove this entire job.

(As a side note if you do not want to remove this job, use .Run() instead of .Schedule() then .Complete is sometimes faster if the job is so small it is not worth the job scheduling cost. But you have to see if what you get from multithreading would counter that or not.)

For relaxation count it seems you are fine with any value from any entity that you keep reading it out and overwrite to the array. (They are all the same and decreasing together?) In this case how about using a singleton. Remove VoronoiRelaxationData from all archetypes. Create a single entity with VoronoiRelaxationData component (maybe in this system's OnCreate so it is there automatically), then you can use GetSingleton<VoronoiRelaxationData> SetSingleton<VoronoiRelaxationData>

CreateArchetype could be done in OnCreate and you keep using it. This contains garbage as it uses managed array IIRC so it is important to keep your OnUpdate garbage free.

I see you try to set back result from your external library to ECS. If you could turn it back to NativeArray, there is eq.CopyFromComponentDataArray to work in the opposite direction of eq.ToComponentDataArray. You need to ensure exact array length matching the query. This method maybe troublesome if order matters but it is again a fast copy back.

Your plan to work with 4 archetypes and try to morph them around with ECB add/set/remove could be improved.

There are a lot of similarities between these. It maybe possible to use only a single archetype of everything combined (VoronoiPositionData, VoronoiRelaxationData, DynamicBuffer<VoronoiEdgePoint>, GameObjectRepFlag) from the start (from the entity's creation) but have their default data (instead of no component). The point is that these all contains data, and by adding removing them constantly the chunk need to always adjust its shape.

This create query problems as you no longer have the right criteria to start working as they are all there. (WithNone no longer works, etc.) Instead, you use a tag component (no data) called something like NeedEdgePoint/HasEdgePoint instead. It is easier on the chunks when the component has no data when you keep adding removing it to bounce between 2 systems. You can read more about doing something for the sole purpose of separating away what you don't want to work with (existential processing) in here : http://www.dataorienteddesign.com/dodbook/node4.html tag component is a Unity version of that.

Finally even if you keep using your 4 archetype scheme, (or even with my new tag component scheme) the add remove component you use with ECB is one by one. You can gain easy performance by using EntityQuery overload instead which is available on both EM and ECB (you cannot bring EQ into jobs to use with ECB, it is a class).

For example this manager.RemoveComponent<VoronoiRelaxationData>(newEntity); when relaxationsArray[0] >= 0 applies to everyone. So instead CreateEntityQuery with only VoronoiRelaxationData at OnCreate, then here EntityManager.RemoveComponent<VoronoiRelaxationData>(eqRelaxation) instead of any single entity. It is a chunk operation, and if this VoronoiRelaxationData was replaced with a tag component (no data inside) this will be very fast as no chunk change its shape at all.

Again here in an another system ecb.RemoveComponent<VoronoiEdgePointElement>(entityInQueryIndex, entity); it seems like finally everyone matching this ForEach would be removed its component. It is a shame that at playback entity will be migrating the chunk one by one. Instead, use .WithStoreEntityQueryInField(ref eq) to get a hold of underlying EQ of this ForEach, then perform ecb.RemoveComponent<VoronoiEdgePointElement>(eq) next to that ForEach job. (this make it an ECB enqueue on main thread, doesn't matter as the playback is where the performance matters not when adding commands)

I think maybe the ECB need to be targeting BeginInitialization instead as because we enqueue the command now, the ForEach job above may not run yet and the component was removed first? By targeting Initialization it means you are playing them the next round of frame and ensure the job finishing.

 

Thank you very much for your in depth comments. I will address a few of them now, some of them though I need time to absorb

Yeah I threw that in I think a bit last minute when I realized I had no way to get that data out. I should refactor that. The whole thing feels -- meh -- to me.

That is what I originally wanted to do, but I was a little unsure of how this ToComponentArray worked. For example if my EntityQuery is specifying multiple components in order to "narrow down" the entities I want, but the data I want in the array is just the PointData component? Not sure how that worked, so it was simpler to do it this way.

Again though, I should spend some time here and see what I can do. Even if I did refactor it out to ToComponentArray though I would need a way to delete the entities from the query?

My hope was given that I would be processing thousands of points, that even just the act of copying out their data would benefit from multiple threads, but I see what you mean. It being such a simple thing maybe I am introducing extra overhead that defeats the purpose.

TECHNICALLY I should be caring about it per entity, but currently I'm not and the complexity goes WAY up if I do. So I made the assumption that I would be only ever working on a single "map" at one time, and thus all the values would be the same. I'll look into the Singleton thing. I wasn't aware of that feature set. Sounds handy.

I would prefer to just create the entity with all the component values in a single call, but I couldn't find any examples of doing that. I'm not too keen on this method of creating an "empty" entity from an archetype and then setting each component individually. It feels bad.

Unfortunately the data structure I am getting back is pretty complex. Even though I am not using most of the data it contains, the act of refactoring the library to return a NativeArray would require so much pre-processing that the gains would be little if anything.

Yeah I wasn't sure what the "best practice" here was, so good to have some more insight on that.

The rest of your comments I need more time to absorb and understand

 

Hmm just to make sure I get my point across this one I mean just move this line :

EntityArchetype archetype = manager.CreateArchetype(typeof(VoronoiPositionData), typeof(VoronoiRelaxationData), typeof(VoronoiEdgePointElement));

To OnCreate as :

archetype = manager.CreateArchetype(typeof(VoronoiPositionData), typeof(VoronoiRelaxationData), typeof(VoronoiEdgePointElement));

Then declare a field on the system class :

EntityArchetype archetype;

Then your manager.CreateEntity(archetype); can stay as it is and you get all the components with their default values from start. The archetype is just a specification how to create an entity. It could be allocated only once. The real create is CreateEntity.

Also your World.EntityManager could be simplified, anywhere you want the EntityManager, just type EntityManager (protected property). It is the same thing. World = world that this system resides, EntityManager = manager of the World that this system resides

 

What I mean is this whole process of creating a "blank" entity from an archetype and then filling in the values feels ugly to me. I'd much rather do something like:

Code (CSharp):

1. Entity newEntity = manager.CreateEntity({ new VoronoiPositionData{Value = new float2(x,y), new VoronoiRelatationData {Value = 10}});  

or even better, because I like descriptive easy to follow code:

Code (CSharp):

1. var pos = new VoronoiPositionData {Value = new float2(x,y));
2. var relaxation = new VoronoiRelaxationData {Value = 10];
3. var newEntity = EntityManager.CreateEntity({pos, relaxation});
4.  

Or something like that. In otherwords do the whole thing in one go.

That said, I do know what you are saying and it makes sense. I just don't like the entire pattern

 

This "ugly" pattern only make sense from the API designer standpoint because it related to how the data is stored.. creating a blank entity with premade archetype get it to the right home from the get go and all SetComponentData would be in-place. If you create a really empty entity then Add multiple times it would have to move home multiple times.

Now your wrapper API do looks nice to use and could be translated to CreateArchetype by just types and Set Set Set.. to gain the same performance, it now affect an another design of the lib how it wants to work with types.

This kind of wrapper means you must have a bunch of CreateEntity<T> CreateEntity<T1, T2,..> prepared (ForEach style) so that it can get typing information converted to type index inside and I can see why Unity team decided against this as you can never get enough combinations. The same for an equivalent in ECB except it maybe even harder over there (jobs) to turn type into indexes. (ForEach could, as you usually work on just a part of all components. Creating entity usually requries more amount of types and could get really diverse)

To alleviate this they want to bake types to indexes ahead of time (and thats EntityArchetype) now C# lose its generic typing propagation though, so we are back to our current Archetype + Set implementation because Set you add back the type on each call (a pain when you get it wrong but then they patch that up with runtime error). While I also feel unwieldly about this at times, when I know there is no way out performance wise I could get along with it ...more willingly. And not by inventing a new programming language. The whole thing sometimes feel like we are driving C# to do what it couldn't and it always bite us back at some point, and we can just move that problem to different place. (Then we have something like DOTS Visual Scripting that escaped C# entirely to codegen from graph, but still max performance would have to be by coding with the API)

In 2019.3 version they add a new IL magic feature to the engine, that could potentially make your API possible by having CreateEntity(params object) or something and have custom IL processor turn it into something statically typed.. I imagine it would be a big trouble to implement. The intention of this IL feature sometimes feel like we have already chased C# to the deadend but we drill the wall and make a bit more path that ECS really needs to finish its final polish. (The JobComponentSystem lambda capture thing recently added, etc.)

 

Hi @5argon are you aware of any documentation or examples of this Set/GetSingleton that you mentioned? I'm not finding it in the Entities package docs.

 

https://docs.unity3d.com/Packages/c...on__1_Unity_Entities_ComponentSystemBase___0_
and SetSingleton<T> at the bottom of page redirect to additional info.