Showcase Dots Plus

Recently, I got really invested in dots and developed lots of fun projects like:
- ECS RPG

- Navmesh on ecs

- Local avoidance package

- Adaptive split screen package

During development I noticed I kept reimplementing some of the APIs like NativePriorityQueue, KdTree, Geometry, Mathematics operations... That kind of gave me the idea to create a package out of it as extension to existing Unity Dots.



In case you ever needed more DOTS compatible collections or math operations you can check package link below. Keep in mind its early initiative so its not going to have much, but it is really good place for requests.

Package

 

Ah yeah, I have seen you posting project on reddit
Really nice of you sharing DOTS assets.

 

Thanks .


Will add some operations with 3d shapes in version 1.2 (By request from user). It is now in review.

 

For next I am thinking maybe adding voronoi.

 

Voronoi going quite well in progress. Got finally VoronoiBuilder fully in HPC#.

Did small test with sites 10000 single bursted job that yield 155ms on my machine.
It uses Fortunes Algorithm, but there is still place to optimize as in some place it still does linear searches.

Also I put huge focus that API would be simple and highly customizable.

Code (CSharp):

1.  
2. public unsafe struct VoronoiBuilder : IDisposable
3. {
4. // To add point
5. public void Add(double2 point)
6.  
7. // Output voronoi
8. public void Construct<T>(ref T output) where T : IVoronoiDiagram
9. }
10.  
11. public unsafe interface IVoronoiDiagram
12. {
13. void AddVertex(Vertex vertex);
14. void AddEdge(Edge edge);
15. void Build();
16. }
17.  

It is a bit inspired from boost, so you can even roll out your own custom voronoi diagram.

 

Looks nice! I grabbed the package since it's on sale and I'll definitely be needing some of those algorithms sooner or later.

Not gonna object, since in my project I have a utility class called

mathex

, with function names such as

projectnormal

,

anglesigned

,

angleprecise

, etc. I've noticed some community packages have also adopted lowercase naming for math-related utils (eg MaxMath). I don't think there's any sane way out of the lowercase

math

mess, I guess it's time to get used to it...

 

Yea, I do have mixed feelings about the unity math lowercase choice. On one side I agree if you treat them as instricts you can give them exception as special syntax and allow this, especially as they used often and also combined with

using static Unity.Mathematics.math

makes typing faster (As those are very common operations in game code) and also sits so well with HLSL portability. Now for the types like

float2/float3...

I think it is smart choice as they basically primitives especially with burst compiler treating them like this (Personally I never liked writing Vector ).
However that creates problem where do you draw the line which function is instrict and which one is not, same goes for types (in primitives sense). Especially I seen some library going ahead and adapting it for other types like

line, polygon...

, which makes the line even more blurry.

For this package I decided to draw the line within the

math2

namespace. I am following the general rule of thumb stuff that would made sense if they were in

using static Unity.Mathematics.math

the first place. I actually going to push the idea to Unity developers making

using static Unity.Mathematics.math

as partial class, this way re'using the same class with same name.

 

The

math

class is partial already, if you use an AssemblyReference you can easily extend it with more functions.

 

Can you enlighten me ? I thought you couldn't extend partial types from other assemblies. I'm looking online and can't find anything.

 

If you use an Assembly Reference (https://docs.unity3d.com/Manual/class-AssemblyDefinitionReferenceImporter.html) then you can add additional files to an already existing assembly/package. In this case you could reference the

Unity.Mathematics

assembly and extend the partial

math

class (which I did in our internal library at work).

 

Now with new

VoronoiBuilder

delaunay generated.

Code (CSharp):

1.  
2.         using (var builder = new VoronoiBuilder(1, Allocator.Temp))
3.         {
4.             foreach (var transform in Transforms)
5.                 builder.Add(transform.position.asfloat().xy);
6.  
7.             var delaunay = new DelaunayTriangulation(builder.NumSites, Allocator.Temp);
8.             builder.Construct(ref delaunay);
9.  
10.             for (int i = 0; i < delaunay.Indices.Length; ++i)
11.             {
12.                 var indices = delaunay.Indices[i];
13.                 var triangle = new Triangle(delaunay.Points[indices.x].asfloat3(), delaunay.Points[indices.y].asfloat3(), delaunay.Points[indices.z].asfloat3());
14.                 DrawTriangleGizmos(triangle, new Color(0, 1, 0, 0.3f));
15.                 DrawWireTriangle(triangle, Color.green);
16.             }
17.  
18.             delaunay.Dispose();
19.          }
20.  

 

Now the actual voronoi diagram is finished.

Code (CSharp):

1.  
2.         using (var builder = new VoronoiBuilder(1, Allocator.Temp))
3.         {
4.            
5.             foreach (var transform in Transforms)
6.                 builder.Add(transform.position.asfloat().xy);
7.  
8.             var diagram = new VoronoiDiagram(bounds, Allocator.Temp);
9.             {
10.                 builder.Construct(ref diagram);
11.  
12.                 for (int cellIndex = 0; cellIndex < diagram.Cells.Length; ++cellIndex)
13.                 {
14.                     var color = Color.HSVToRGB((float)cellIndex / diagram.Cells.Length, 1, 1);
15.                     color.a = 0.3f;
16.                     DrawVoronoiCell(diagram, diagram.Cells[cellIndex], color);
17.                 }
18.             }
19.             diagram.Dispose();
20.  

Code (CSharp):

1.  
2.     static void DrawVoronoiCell(in VoronoiDiagram voronoiDiagram, VoronoiCell cell, Color color)
3.     {
4. #if UNITY_EDITOR
5.         int count = 0;
6.         for (var itr = cell.Begin; itr != cell.End; itr.MoveNext())
7.             count++;
8.  
9.         if (count == 0)
10.             return;
11.  
12.         var points = new Vector3[count];
13.         var index = 0;
14.         for (var itr = cell.Begin; itr != cell.End; itr.MoveNext())
15.             points[index++] = voronoiDiagram.Vertices[itr.Value.ToVertexIndex].Point.asvector3();
16.  
17.         UnityEditor.Handles.color = color;
18.         UnityEditor.Handles.DrawAAConvexPolygon(points);
19. #endif
20.     }
21.  

As you can see it uses same

VoronoiBuilder

as used in

DelaunayTriangulation

construction. API is very powerful and you can create you own custom output, by simply implementing interface and calling

VoronoiBuilder.Construct

:

Code (CSharp):

1.  
2.     /// <summary>
3.     /// Interface of the voronoi output used by <see cref="VoronoiBuilder.Construct{T}(ref T)"/> to construct voronoi shape.
4.     /// </summary>
5.     public interface IVoronoiOutput
6.     {
7.         /// <summary>
8.         /// Callback after <see cref="VoronoiBuilder"/> processes the site.
9.         /// </summary>
10.         /// <param name="point">The point of site.</param>
11.         /// <param name="index">Index of site.</param>
12.         void ProcessSite(double2 point, int index);
13.         /// <summary>
14.         /// Callback after <see cref="VoronoiBuilder"/> processes the vertex.
15.         /// </summary>
16.         /// <param name="point">The point of vertex.</param>
17.         /// <returns>The index of the vertex.</returns>
18.         int ProcessVertex(double2 point);
19.         /// <summary>
20.         /// Callback after <see cref="VoronoiBuilder"/> processes the edge.
21.         /// </summary>
22.         /// <param name="a">Standard line a coefficient.</param>
23.         /// <param name="b">Standard line b coefficient.</param>
24.         /// <param name="c">Standard line c coefficient.</param>
25.         /// <param name="leftVertexIndex"></param>
26.         /// <param name="rightVertexIndex"></param>
27.         /// <param name="leftSiteIndex"></param>
28.         /// <param name="rightSiteIndex"></param>
29.         void ProcessEdge(double a, double b, double c, int leftVertexIndex, int rightVertexIndex, int leftSiteIndex, int rightSiteIndex);
30.         /// <summary>
31.         /// Callback after <see cref="VoronoiBuilder"/> finished building.
32.         /// </summary>
33.         void Build();
34.     }
35.  

 

Version 1.3 is under review now.

## [1.3.0] - 2022-08-10
- Changed NativeLinkedList Add/Insert to return iterator
- Changed com.unity.burst dependency version from 1.3.0-preview.12 to 1.6.6
- Changed com.unity.mathematics dependency version from 1.1.0 to 1.2.1
- Changed com.unity.collections dependency version from 0.9.0-preview.6 to 1.4.0
- Added Sort/Middle/Count to NativeLinkedList
- Added EnqueueUnique to the NativePriorityQueue
- Added new helper class ShapeGizmos for drawing 2d geometry
- Added VoronoiBuilder/DelaunayTriangulation/VoronoiDiagram
- Added to math functions isclockwise/iscclockwise/iscollinear/sq/sort/line/curve/parabola/bazier/swap
- Added Voronoi sample
- Added Curves sample

 

Version 1.3 is live

 

In case anyone has any particular API request that they would love to see in 1.4 version don't hesitate to ask.
I am thinking implementing AABBTree that might be useful with given geometry that is in package.

 

AABB Tree full in dots! AABB tree allows quickly finding the volumes that can overlap with requested volume. In this case the volume is 2D rectangle, but also scale to 3D.

Code (CSharp):

1.  
2. struct Volume : ISurfaceArea<Volume>, IUnion<Volume>
3. {
4.     public Rectangle Rectangle;
5.     public Volume(Rectangle rectangle)
6.     {
7.        Rectangle = rectangle;
8.     }
9.     public float SurfaceArea() => Rectangle.Perimeter;
10.     public Volume Union(Volume value) => new Volume(Rectangle.Union(Rectangle, value.Rectangle));
11. }
12.  
13. ...
14.  
15. var tree = new UnsafeAABBTree<Volume>(1, Allocator.Temp);
16.  
17. tree.Add(new Volume(new Rectangle(transform.position.asfloat().xy - 0.5f, 1)));
18.  
19. DrawNode(tree.Root);
20.  
21. tree.Dispose();
22.  

 

Nice API! I like the stuff that C# lets you do with interfaces + constrained generics. Burst pretty much inlines all of that and generates optimal code (unlike Mono, where the JIT is pretty naive, and I don't think IL2CPP helps much either).

I also like that the asset imports straight into /Packages/ instead of /Assets/. I didn't even know this was possible because I've never seen any asset do this, even when it's already nicely structured like an UPM package (eg. @Acegikmo's Shapes ).

I also hereby award you the Very Nice Comment To Code Ratio Award!

Code (csharp):

1. /Packages/com.projectdawn.dotsplus$ cloc .
2.       87 text files.
3.       87 unique files.
4.       48 files ignored.
5.  
6. github.com/AlDanial/cloc v 1.81  T=0.34 s (114.3 files/s, 21934.6 lines/s)
7. -------------------------------------------------------------------------------
8. Language                     files          blank        comment           code
9. -------------------------------------------------------------------------------
10. C#                              39            921           1931           4632
11. -------------------------------------------------------------------------------
12. SUM:                            39            921           1931           4632
13. -------------------------------------------------------------------------------

 

Yes, I really enjoy the HPC# + burst. Coding with it feels like having the best of c++ and C#, performance and safe/clean syntax combined.

Yes this is new upload workflow. I am one of the earliest adopter of it, I think in the future there will be more packages following it.

Thanks! Really humbling to see that my effort on code goes unnoticed .

 

Just played around a bit more with AABB tree, tried for fun to use circle instead of rectangle and surprisingly it works out of the box .

Basically you just need to use this structure as generic type.

Code (CSharp):

1.  
2.     struct Volume : ISurfaceArea<Volume>, IUnion<Volume>
3.     {
4.         public Circle Circle;
5.         public Volume(Circle rectangle)
6.         {
7.             Circle = rectangle;
8.         }
9.         public float SurfaceArea() => Circle.Perimeter;
10.         public Volume Union(Volume value) => new Volume(Circle.Union(Circle, value.Circle));
11.     }
12.  

Of course rectangles probably going to be more efficient as it is more cheaper to compute overlap/union operation.

 

What is the current stress test benchmark?

Did you try any stress test and profiling?

 

Unit Test:
- 5k Shapes
- 5k Line and Shape overlap test

Brute Force Rectangle:
124ms (0ms build, 124ms find)

AABRectangle:
24ms (12ms build. 12ms find)

Brute Force Circle (Circumscribed of same rectangle)"
67ms (0ms build, 67ms find)

AABCircle:
41ms(19ms build, 22ms find)

All tests are bursted. Rectangle shows more than 5x improvement over brute, in case tree is re-used that would be 10x.
As expected circle is not showing that much of the win compared to brute force, not even 2x. It is mostly, because union and overlap functions more expensive. Also in case you wonder why brute force circle is faster, it just circle and line test is much cheaper.

 

Released

## [1.4.0] - 2022-08-25
- Changed geometry overlap/intersection not include borders
- Changed overlap logic to be more faster
- Added to geometry structures debug display
- Added AABBTree

 

For version 1.5 plan to add MeshSurface and VertexData for very fast mesh reading/writing/processing.
Plan to release dots mesh slicer that will use dots plus, to also show the advantages of this package.

Here is demo of mesh slicer in dots that is powered by DelaunayTriangulation and upcoming MeshSurface from dots plus. As example full sphere mesh slice takes somewhere 0.1ms on my *machine.

 

That's really cool, can't wait to try making a sequel to Metal Gear Revengeance.
.

 

Hey Luckas,

Purchased this package yesterday, and while I still haven't had a chance to check out absolutely everything, it's looking great!

I did notice an issue during building though where the struct Node in UnsafeAABBTree.cs has a variable

Code (CSharp):

1. #if ENABLE_UNITY_COLLECTIONS_CHECKS
2.     public bool IsFree;
3. #endif

Other places in the script there is logic which uses IsFree without the same wrappers which causes builds to terminate. I just wrapped that other logic with the same preprocessor logic and it worked fine.

Just wanted to let you know.

Anyways thanks for all your work!

 

Oh darn. Fixed in 1.4.1 added for review.

 

New additions to upcoming version 1.5. Generating three primitives (Only positions currently).

Box - 0.004ms
Icosphere (2 subdivisions, 42 vertices, 240 indices) - 0.012ms
Icosphere (4 subdivisions, 642 vertices, 3840 indices) - 0.28ms

Box generation in this image

Code (CSharp):

1.  
2.         var attributes = new NativeArray<VertexAttributeDescriptor>(1, Allocator.Temp);
3.         attributes[0] = new VertexAttributeDescriptor(VertexAttribute.Position, VertexAttributeFormat.Float32, 3);
4.         var surface = new MeshSurface(1, attributes, Allocator.TempJob);
5.         JobHandle dependency = surface.Box(Box, default);
6.         if (TryGetComponent(out MeshFilter meshFilter))
7.         {
8.             var meshDataArray = Mesh.AllocateWritableMeshData(1);
9.             dependency = surface.Write(meshDataArray[0], MeshUpdateFlags.Default, dependency);
10.             dependency.Complete();
11.             if (meshFilter.sharedMesh == null)
12.                 meshFilter.sharedMesh = new Mesh();
13.             Mesh.ApplyAndDisposeWritableMeshData(meshDataArray, meshFilter.sharedMesh);
14.         }
15.         attributes.Dispose();
16.         surface.Dispose();
17.  

 

Landed

## [1.5.0] - 2022-09-27
- Changed IVoronoiOutput.ProcessVertex signature
- Improved performance of DelaunayTriangulation drastically
- Added VertexData structure for processing vertex information
- Added MeshSurface structure for processing/reading/writing Mesh
- Added box/icosphere/icohedron/icocapsule generation suing MeshSurface
- Added NativeStructureList/UnsafeStructureList for building SoA (structure of array)
- Added Plane structure (Exposed from Unity Collection package)
- Added 3d/2d Capsule structure

 

Release dots mesh slicer that uses this package as dependency https://assetstore.unity.com/packages/tools/modeling/dots-mesh-slicer-233259.

 

Going to make short break on this package to finish my local avoidance new version (In case anyone is interested https://forum.unity.com/threads/local-avoidance-3-0-0.1299813/). Feel free to put requests here or in discord.

 

I recently played around with fixed point type, basically the same as float just that point is fixed.
The main two advantages of fixed type over float type:

• More control over precision. As example, in my mesh slicer package (https://assetstore.unity.com/packages/tools/modeling/dots-mesh-slicer-233259) I used integers as it makes easier to identify similar slices and zero check is more trivial.
• Deterministic as it uses integer types behind the hood. Will be familiar for those who attempted lock step networking model.
• There is possibility for some mathematically functions to be faster. For example, sin and cos could use lookup maps on lower precisions (Not confirmed yet).

Made small test with this new type.

Code (CSharp):

1.  
2. // See https://aka.ms/new-console-template for more information
3. using System.Diagnostics;
4. using ProjectDawn.Mathematics;
5. using ProjectDawn.Assertion;
6. // Int
7. Assert.AssertEqual(new fixe(5), 5);
8. Assert.AssertEqual(new fixe(39), 39);
9. Assert.AssertEqual(new fixe(625), 625);
10. // Float
11. Assert.AssertEqual(new fixe(1.5f), 1.5f);
12. Assert.AssertEqual(new fixe(2.25f), 2.25f);
13. Assert.AssertEqual(new fixe(0.625f), 0.625f);
14. // Add
15. Assert.AssertEqual(new fixe(1.5f) + new fixe(1.25f), 2.75f);
16. Assert.AssertEqual(new fixe(10.5f) + new fixe(6.5f), 17f);
17. // Sub
18. Assert.AssertEqual(new fixe(1.5f) - new fixe(1.25f), 0.25f);
19. Assert.AssertEqual(new fixe(10.5f) - new fixe(6.5f), 4f);
20. // Mul
21. Assert.AssertEqual(new fixe(1.5f) * new fixe(1.25f), 1.875f);
22. Assert.AssertEqual(new fixe(10.5f) * new fixe(6.5f), 68.25f);
23. // Div
24. Assert.AssertEqual(new fixe(1.5f) / new fixe(2f), 0.75f);
25. Assert.AssertEqual(new fixe(10.5f) / new fixe(4), 2.625f);
26. // ToString
27. fixe number = 5.625f;
28. Console.WriteLine($"number = {number}");
29. // Mul performance
30. float[] floats = new float[]
31. {
32.     0.5f,
33.     1.5f,
34.     2.5f,
35.     0.25f,
36.     1.45f,
37. };
38. {
39.     float result = 1;
40.     var sw = new Stopwatch();
41.     sw.Start();
42.     for (int i = 0; i < 200; ++i)
43.     {
44.         result = result * floats[i % floats.Length];
45.     }
46.     sw.Stop();
47.     Console.WriteLine($"Float result:{result} time:{sw.Elapsed.TotalMilliseconds}");
48. }
49. {
50.     float result = 1;
51.     var sw = new Stopwatch();
52.     sw.Start();
53.     for (int i = 0; i < 200; ++i)
54.     {
55.         result = result * floats[i % floats.Length];
56.     }
57.     sw.Stop();
58.     Console.WriteLine($"Float result:{result} time:{sw.Elapsed.TotalMilliseconds}");
59. }
60. {
61.     fixe[] fixes = new fixe[floats.Length];
62.     for (int i = 0; i < floats.Length; ++i)
63.         fixes[i] = floats[i];
64.     fixe result = 1;
65.     var sw = new Stopwatch();
66.     sw.Start();
67.     for (int i = 0; i < 200; ++i)
68.     {
69.         result = result * fixes[i % fixes.Length];
70.     }
71.     sw.Stop();
72.     Console.WriteLine($"Fixe result:{(float)result} time:{sw.Elapsed.TotalMilliseconds}");
73. }
74.  

Result:
number = 5.625
Float result:1.9605227E-07 time:0.0046
Float result:1.9605227E-07 time:0.0003
Fixe result:0.00024414062 time:0.0004

Performance is almost same, result differs, because in this test there is only 8bits after the point.

I am curious if anyone would found this useful if it was in the package? Of course, it would also have vectorized variations too, with all same math functions.

 

100%. I would have purchased the asset just for the fixed math xD and I know us DOTS Devs working on Sanctuary have been curious about exploring fixed math for a while.

I would love to see some more benchmarks -- especially inside bursted jobs!

 

Yes, definitely!
Also requesting it to have its own suffix like float does.
For example, just writing 1.05fx instead of new fixe(1.05f).

 

I checked that C# has no support for custom type suffixes (At least that is response from stack https://stackoverflow.com/questions/11268213/create-custom-constant-suffix-in-c-sharp).

However, C# allows overloading implicit conversion. So you will be able to do this:

Code (CSharp):

1. void Foo(fixe value)
2. {
3. ...
4. }
5.  
6. Foo(1.5f);

I am actually already doing this in tests:

Code (CSharp):

1. Assert.AssertEqual(new fixe(5), 5);

As AssertEqual expects integers here, fixe gets converted to integer.

In any case, I would expect in most cases vectorized variation would be used fixe3, so it would not differ much from using float3.

 

One of the users complained that NativePriorityQueue is quite slow in big data, which is true as it uses linked list behind the hood. For this reason, I created additional NativePriorityQueue that is heap based. Also, added suffix to clarify each queue backend and heap one uses key instead of comparer for simplicity.

Code (CSharp):

1. struct AscendingOrder : IComparer<int>
2. {
3.     public int Compare(int x, int y) => x.CompareTo(y);
4. }
5.  
6. var queue = new NativeLinkedPriorityQueue<int, AscendingOrder>(Allocator.Temp, new AscendingOrder());
7.  
8. queue.Enqueue(2);
9. queue.Enqueue(1);
10.  
11. Assert.AreEqual(1, queue.Dequeue());
12. Assert.AreEqual(2, queue.Dequeue());
13.  
14. queue.Dispose();

Code (CSharp):

1. var queue = new NativeHeapPriorityQueue<int, int>(Allocator.Temp);
2.  
3. queue.Enqueue(2, 2);
4. queue.Enqueue(1, 1);
5.  
6. Assert.AreEqual(1, queue.Dequeue());
7. Assert.AreEqual(2, queue.Dequeue());
8.  
9. queue.Dispose();

## [1.7.0] - 2022-12-21
- Added NativeHeapPriorityQueue that uses heap
- Added NativeLinkedPriorityQueue that uses linked list
- Deprecated NativePriorityQueue should use now either NativeHeapPriorityQueue or NativeLinkedPriorityQueue

Heap Priority Queue, Peek = O(1), Enqueue = O(log n), Dequeue = O(log n).
LinkedList Priority Queue, Peek = O(1), Enqueue = O(n), Dequeue = O(1).

There is benchmark test that validates big O complexity

 

Documentation https://lukaschod.github.io/dots-plus-docs/manual/index.html

 

Hi @Lukas_Ch When you get a chance, can you change the

bool Equals(object other)

overrides (for Circle, Rectangle, etc...) to something like:

Code (CSharp):

1. public override bool Equals(object other) => other is Rect other1 && this.Equals(other1);

Currently, they are all

throw new NotImplementedException()

.

 

I could add it, but keep in mind this operation will be used with boxing, thus not working in Burst. What is ure use case?

 

Not really for an use case, but rather it seems that the EntityEditor (plus UI Toolkit binding) is using this? So if left unimplemented, there will be nonstop errors in the console if you click on an entity that has an compdata that's using Rectangle for example.

 

Ohh k, that needs to be fixed for sure, will add to my backlog

 

Added for review should land in few days

## [1.8.2] - 2023-08-03
- Added to geometry structures Equals(object) implementations
- Added Box and Box transformed overlap test
- Added Box and Triangle overlap test

 

Landed

 

I don't think the description of Sphere.ClosestPoint(float3) is entirely correct.
It says it will return a point on the perimeter, but that is not the case if the point is inside the sphere.

You might want to clarify this in the documentation and possibly provide a second function that will return a point on the perimeter irregardless if the given point is inside the sphere.

 

Thanks that is really good point. In terms of the name I guess it is indicate more intention that volume is included. Maybe I need to create ClosestPointOnSurface as second function as you said.