How to Sort a NativeArray

Unity Engine
, ,
1

Hi,

i want to sort a NativeArray using Jobs… i’m able to do this with standard Lists but can not make it work using native arrays…

How Sorting should be done ?

BVHTriangle is a struct like this

public struct BVHTriangle
{
    public Vector3 v0;
    public Vector3 v1;
    public Vector3 v2;
    public Vector3 centroid;
}

NativeArray<BVHTriangle> tris;
BVHTriangleSort trianglesSort = new BVHTriangleSort();
trianglesSort.SortArray(tris);

public struct BVHTriangleSort : IComparer<BVHTriangle>
{
    public void SortArray(NativeArray<BVHTriangle> triangles)
    {
        triangles.Sort(Compare);
    }

    public int Compare(BVHTriangle a, BVHTriangle b)
    {
        if (a.centroid.x - b.centroid.x < 0f)
        {
            return -1;
        }
        return 1;
    }
}

I tried a lot of things but i always get an error like this:

7469918--917714--upload_2021-9-3_12-40-17.png

2

Your code is almost correct. Working from memory, but if I recall correctly, you need to provide your comparer struct as the argument to Sort(). You can probably get rid of the SortArray method from the struct and just do this:

tris.Sort(new BVHTriangleSort());
3

Alternatively I think you can implement IComparable on BVHTriangle and use triangles.Sort() without any arguments.

Edit: Then you can also use triangles.SortJob() on the main thread to create a new job exclusively for sorting.

2 Likes
4

Hey, this doesn’t seems to help as the only error is actually in the “BVHTriangleSort” struct as visible in the screenshot above ! It’s hard to come up with a working solution as there are no examples i could find !

Any other idea is really welcome !

5

Hi, thanks for suggestion. I did try implement IComparable in the “BVHTriangle” struct at first, but i still get the same error… I also can’t simply call Sort() as i need a comparer to sort list based on a rule !

I really can’t understand the usage of the Sort method with a comparer, so any other idea is really appreciated !

6

Here was one I did with IComparer to sort float4s:

struct PointDataComparer : IComparer<float4> {
    public AABB GridBounds;
    public int3 CellsPerAxis;
 
    public int Compare(float4 a, float4 b) {
        int3 cellId = GetCellID(GridBounds, CellsPerAxis, a.xyz);
        int3 otherCellId = GetCellID(GridBounds, CellsPerAxis, b.xyz);
        int xDiff = cellId.x.CompareTo(otherCellId.x);
        if(xDiff == 0) {
            int yDiff = cellId.y.CompareTo(otherCellId.y);
            if(yDiff == 0) {
                return cellId.z.CompareTo(otherCellId.z);
            }
            return yDiff;
        }
        return xDiff;
    }
}

Then:

PointData.Sort(new PointDataComparer {
    GridBounds = GridBounds,
    CellsPerAxis = CellsPerAxis
});

You may find this performs far worse than .Sort() in an IJob, when I last tried earlier this year the difference was 7ms vs 12000ms.

7

Awesome, thanks @RecursiveEclipse

this is working perfectly :slight_smile: