0

Is there any way in C# to resize arrays without making a copy? What I'm specifically looking for is a way to change the Length property of an array. The array has a fixed maximum length, and is only ever resized to a size smaller or equal to the maximum size (allows reusing the array).

The actual use case is procedural mesh generation in Unity3D. The built-in method of doing this is limited to using lists (very slow) and assigning, for example, an array of Vector3s to mesh.vertices. The array assigning method is what I want, but there's no way to specify the number of array elements to copy when you assign an array to mesh.vertices (mesh.vertices isn't an array, and copies the assigned array to the GPU).

When the number of vertices in a procedurally generated mesh is unknown beforehand, it's impossible to make an array of the right size and you have to resort to slow array resizing.

I know that C# normally doesn't allow the kind of array resizing I'm looking for, but I have to ask if there isn't some half decent low-level hackish way to still get it done.

The method I'm using now is to allocate an array of the maximum number of vertices (which is simply reused for each mesh that's generated), fill that, and then allocate another array of the right size and copy the right number of array elements to the new array (this is faster than Array.Resize, and certainly faster than anything using lists).

Edit: Updated with appropriate code as requested (NOT well documented, beware).

This calls the map generator for each chunk (test code):

for (int z = 0; z < size; z++)
{
    for (int x = 0; x < size; x++)
    {
        Vector3 position = new Vector3(x * 32, 0, z * 32);

        GameObject a = Instantiate(baseObject);
        a.transform.position = position;

        map.GenMap(position, model); // procedural model generation

        blockMesh.SetModel(model); // set the model to generate the mesh from
        blockMesh.GenMesh(); // generate actual mesh
        blockMesh.CopyMesh(a.GetComponent<MeshFilter>().mesh); // copy mesh data do the Unity mesh
    }
}

Simple test map generator:

public void GenMap(Vector3 position, Model map)
{
    map.Clear();

    double par1 = 1000;
    double par2 = 600;
    double par3 = 500;

    double par4 = 1.0 / 50.0;
    double par5 = 1.0 / 25.0;
    double par6 = 1.0 / 12.5;

    double factor = (par1 + par2 + par3) / 16;

    if (factor != 0.0)
    {
        par1 /= factor;
        par2 /= factor;
        par3 /= factor;
    }

    Color32 color150 = map.palette[150];

    for (int z = 0; z < map.realDepth; z++)
    {
        double zPos = position.z + z;

        for (int x = 0; x < map.realWidth; x++)
        {
            double xPos = position.x + x;

            int e = 16 + (int)
            (
                (noise.Noise(xPos * par4, zPos * par4) * par1) +
                (noise.Noise(xPos * par5, zPos * par5) * par2) +
                (noise.Noise(xPos * par6, zPos * par6) * par3)
            );

            for (int y = 0; y < map.realHeight; y++)
            {
                if (y <= e)
                {
                    int a = (255 - (32 - y) * 9);

                    if (a < 1)
                        a = 1;

                    color150.a = (byte)(a | 1);
                    map.voxel[x][y][z] = color150;
                }
            }
        }
    }
}

This is the actual mesh generator code (optimized for Mono 3.5 and not well documented right now):

using UnityEngine;
using System;

public class BlockMesh
{
    public Vector3[] vertices = new Vector3[65532];
    public Vector3[] normals = new Vector3[65532];
    public Vector2[] uvs = new Vector2[65532];
    public Color32[] colors = new Color32[65532];
    public int[] triangles = new int[65532 * 6 / 4];
    public int index = 0;
    public Model model;

    // set model and init arrays

    public void SetModel(Model model)
    {
        this.model = model;
    }

    // copy mesh data to mesh

    public void CopyMesh(Mesh mesh)
    {
        Vector3[] a = new Vector3[index * 4];

        Array.Copy(vertices, a, index * 4);
        mesh.vertices = a;

        Array.Copy(normals, a, index * 4);
        mesh.normals = a;

        Color32[] b = new Color32[index * 4];
        Array.Copy(colors, b, index * 4);
        mesh.colors32 = b;

        int[] c = new int[index * 6];
        Array.Copy(triangles, c, index * 6);
        mesh.triangles = c;

        Vector2[] d = new Vector2[index * 4];

        Array.Copy(uvs, d, index * 4);
        mesh.uv = d;
    }

    // ambient occlusion uv constants

    private const float pixelSize = 1.0f / 4096.0f;
    private const float tileSize = pixelSize * 256;
    private const float adjust1 = pixelSize * 64;
    private const float adjust2 = tileSize - 2 * adjust1;

    // cube faces

    private Vector3[] faceVertices1 = { new Vector3(0, 1, 0), new Vector3(0, 0, 0), new Vector3(0, 0, 0), new Vector3(0, 0, 1), new Vector3(0, 0, 1), new Vector3(1, 0, 1) };
    private Vector3[] faceVertices2 = { new Vector3(1, 1, 0), new Vector3(1, 0, 0), new Vector3(1, 0, 0), new Vector3(1, 0, 1), new Vector3(0, 0, 0), new Vector3(1, 0, 0) };
    private Vector3[] faceVertices3 = { new Vector3(0, 1, 1), new Vector3(0, 0, 1), new Vector3(0, 1, 0), new Vector3(0, 1, 1), new Vector3(0, 1, 1), new Vector3(1, 1, 1) };
    private Vector3[] faceVertices4 = { new Vector3(1, 1, 1), new Vector3(1, 0, 1), new Vector3(1, 1, 0), new Vector3(1, 1, 1), new Vector3(0, 1, 0), new Vector3(1, 1, 0) };

    private Vector3[] faceNormals = { Vector3.up, Vector3.down, Vector3.back, Vector3.forward, Vector3.left, Vector3.right };

    private void AddFace(int side, Vector3 position, Color32 color, int aop)
    {
        // mesh array indices

        int index4 = index * 4;
        int index6 = index * 6;

        // ambient occlusion uv cords

        float x1 = tileSize * (aop & 15) + adjust1;
        float y1 = tileSize * (aop >> 4) + adjust1;

        float x2 = x1 + adjust2;
        float y2 = y1 + adjust2;

        // put face into mesh

        vertices[index4 + 0] = position + faceVertices1[side];
        vertices[index4 + 1] = position + faceVertices2[side];
        vertices[index4 + 2] = position + faceVertices3[side];
        vertices[index4 + 3] = position + faceVertices4[side];

        uvs[index4 + 0].x = x1;
        uvs[index4 + 0].y = y1;
        uvs[index4 + 1].x = x2;
        uvs[index4 + 1].y = y1;
        uvs[index4 + 2].x = x1;
        uvs[index4 + 2].y = y2;
        uvs[index4 + 3].x = x2;
        uvs[index4 + 3].y = y2;

        normals[index4 + 0] = faceNormals[side];
        normals[index4 + 1] = faceNormals[side];
        normals[index4 + 2] = faceNormals[side];
        normals[index4 + 3] = faceNormals[side];

        colors[index4 + 0] = color;
        colors[index4 + 1] = color;
        colors[index4 + 2] = color;
        colors[index4 + 3] = color;

        int tri = 0x08790936 >> ((side & 1) << 4);

        triangles[index6 + 0] = index4 + ((tri >> 10) & 3);
        triangles[index6 + 1] = index4 + ((tri >> 08) & 3);
        triangles[index6 + 2] = index4 + ((tri >> 06) & 3);
        triangles[index6 + 3] = index4 + ((tri >> 04) & 3);
        triangles[index6 + 4] = index4 + ((tri >> 02) & 3);
        triangles[index6 + 5] = index4 + (tri & 3);

        index += 1;
    }

    // build mesh

    public void GenMesh()
    {
        index = 0;

        for (int z = 1; z <= model.depth; z++)
        {
            for (int y = 1; y <= model.height; y++)
            {
                for (int x = 1; x <= model.width; x++)
                {
                    Color32 voxelColor = model.voxel[x][y][z];

                    if (voxelColor.a == 0)
                        continue;

                    if (model.voxel[x][y + 1][z].a == 0) // top
                    {
                        AddFace(0, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x - 1][y + 1][z - 1].a) & 1) << 7) |
                            (((model.voxel[x + 0][y + 1][z - 1].a) & 1) << 6) |
                            (((model.voxel[x + 1][y + 1][z - 1].a) & 1) << 5) |
                            (((model.voxel[x - 1][y + 1][z + 0].a) & 1) << 4) |
                            (((model.voxel[x + 1][y + 1][z + 0].a) & 1) << 3) |
                            (((model.voxel[x - 1][y + 1][z + 1].a) & 1) << 2) |
                            (((model.voxel[x + 0][y + 1][z + 1].a) & 1) << 1) |
                            (((model.voxel[x + 1][y + 1][z + 1].a) & 1)));
                    }

                    if (model.voxel[x][y - 1][z].a == 0) // bottom
                    {
                        AddFace(1, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x - 1][y - 1][z - 1].a) & 1) << 7) |
                            (((model.voxel[x + 0][y - 1][z - 1].a) & 1) << 6) |
                            (((model.voxel[x + 1][y - 1][z - 1].a) & 1) << 5) |
                            (((model.voxel[x - 1][y - 1][z + 0].a) & 1) << 4) |
                            (((model.voxel[x + 1][y - 1][z + 0].a) & 1) << 3) |
                            (((model.voxel[x - 1][y - 1][z + 1].a) & 1) << 2) |
                            (((model.voxel[x + 0][y - 1][z + 1].a) & 1) << 1) |
                            (((model.voxel[x + 1][y - 1][z + 1].a) & 1)));
                    }

                    if (model.voxel[x][y][z - 1].a == 0) // back
                    {
                        AddFace(2, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x - 1][y - 1][z - 1].a) & 1) << 7) |
                            (((model.voxel[x + 0][y - 1][z - 1].a) & 1) << 6) |
                            (((model.voxel[x + 1][y - 1][z - 1].a) & 1) << 5) |
                            (((model.voxel[x - 1][y + 0][z - 1].a) & 1) << 4) |
                            (((model.voxel[x + 1][y + 0][z - 1].a) & 1) << 3) |
                            (((model.voxel[x - 1][y + 1][z - 1].a) & 1) << 2) |
                            (((model.voxel[x + 0][y + 1][z - 1].a) & 1) << 1) |
                            (((model.voxel[x + 1][y + 1][z - 1].a) & 1)));
                    }

                    if (model.voxel[x][y][z + 1].a == 0) // front
                    {
                        AddFace(3, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x - 1][y - 1][z + 1].a) & 1) << 7) |
                            (((model.voxel[x + 0][y - 1][z + 1].a) & 1) << 6) |
                            (((model.voxel[x + 1][y - 1][z + 1].a) & 1) << 5) |
                            (((model.voxel[x - 1][y + 0][z + 1].a) & 1) << 4) |
                            (((model.voxel[x + 1][y + 0][z + 1].a) & 1) << 3) |
                            (((model.voxel[x - 1][y + 1][z + 1].a) & 1) << 2) |
                            (((model.voxel[x + 0][y + 1][z + 1].a) & 1) << 1) |
                            (((model.voxel[x + 1][y + 1][z + 1].a) & 1)));
                    }

                    if (model.voxel[x - 1][y][z].a == 0) // left
                    {
                        AddFace(4, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x - 1][y - 1][z + 1].a) & 1) << 7) |
                            (((model.voxel[x - 1][y - 1][z + 0].a) & 1) << 6) |
                            (((model.voxel[x - 1][y - 1][z - 1].a) & 1) << 5) |
                            (((model.voxel[x - 1][y + 0][z + 1].a) & 1) << 4) |
                            (((model.voxel[x - 1][y + 0][z - 1].a) & 1) << 3) |
                            (((model.voxel[x - 1][y + 1][z + 1].a) & 1) << 2) |
                            (((model.voxel[x - 1][y + 1][z + 0].a) & 1) << 1) |
                            (((model.voxel[x - 1][y + 1][z - 1].a) & 1)));
                    }

                    if (model.voxel[x + 1][y][z].a == 0) // right
                    {
                        AddFace(5, new Vector3(x, y, z), voxelColor,
                            (((model.voxel[x + 1][y - 1][z + 1].a) & 1) << 7) |
                            (((model.voxel[x + 1][y - 1][z + 0].a) & 1) << 6) |
                            (((model.voxel[x + 1][y - 1][z - 1].a) & 1) << 5) |
                            (((model.voxel[x + 1][y + 0][z + 1].a) & 1) << 4) |
                            (((model.voxel[x + 1][y + 0][z - 1].a) & 1) << 3) |
                            (((model.voxel[x + 1][y + 1][z + 1].a) & 1) << 2) |
                            (((model.voxel[x + 1][y + 1][z + 0].a) & 1) << 1) |
                            (((model.voxel[x + 1][y + 1][z - 1].a) & 1)));
                    }
                }
            }
        }
    }
}
Thorham
  • 447
  • 3
  • 11
  • How about implementing a ReducableArray class that contains an array, and an int length up to the size of the array, and only uses the first part of the array up to the length? – Yair Halberstadt Sep 12 '17 at 21:52
  • @YairHalberstadt yea, he could call it `List`! (the thing you described is exactly what List already does) – Scott Chamberlain Sep 12 '17 at 21:53
  • 1
    Yes, but he said list is too slow @ScottChamberlain – Yair Halberstadt Sep 12 '17 at 21:54
  • 2
    So, therfor your solution would be too slow too because you described `List` – Scott Chamberlain Sep 12 '17 at 21:54
  • 7
    @Thorham Can you update your question showing a example of what you have tried so far that was too slow? – Scott Chamberlain Sep 12 '17 at 21:59
  • This looks like a limitation of this Unity API. If you know the theoretical upper bound, why don't you just use the maximum sized buffers and simply not using the last indices from the index buffer? Or you could come up with a heuristics. If the buffer is almost full then just use the whole buffer so you dont have to copy it, if it is rather empty then you can copy the items to a new array quickly because there are only a few of them – Tamas Hegedus Sep 12 '17 at 22:07
  • "The array has a fixed length", if you want to resize it then this statement is false, so the object you should use might not be a fixed sized array. But Mesh.vertices does not give you the choice right? I think that if understand you're problem, what you want is actually a sub part of the array so maybe you can look at this : https://stackoverflow.com/questions/943635/getting-a-sub-array-from-an-existing-array – Pierre Baret Sep 12 '17 at 22:07
  • The fastest way to do this sort of stuff in C# is using pointers. This should be as fast as C. – Ron Inbar Sep 12 '17 at 22:17
  • Not necessarily. There's probably other stuff going on in a list. He may be able to create a very limited version, and thus optimise it to be faster than list @ScottChamberlain – Yair Halberstadt Sep 12 '17 at 22:17
  • @Martin Liversage - That's not how it would work. I specifically said that the array is resized to a size smaller or equal to the original size (not larger). This means that only the array's Length property changes while the size of the allocated memory block doesn't change. This is useful for reusable buffers where you only know the upper size limit, but not the lower size limit (and where the upper size limit is something reasonable, such as 100000 array elements). – Thorham Sep 12 '17 at 22:37
  • @Thorham: I deleted my comment because it wasn't relevant after all. Perhaps you should change the title of your question to something like _Array shrinking in C#_? – Martin Liversage Sep 12 '17 at 22:44
  • @Pierre Baret - What I mean is an array of a fixed maximum size, where the Length property can be changed to be smaller or equal to the maximum size. That way you can reuse the array if you know the upper size limit. – Thorham Sep 12 '17 at 22:45
  • [Set Array's Length property](https://stackoverflow.com/q/34449392/150605) also deals with changing the size of an array of vertices in Unity, though that is more about _presenting_ an array as smaller than it actually is whereas this is about actually resizing the array object. – Lance U. Matthews Sep 12 '17 at 23:09
  • @Thorham so basically you want to only use a sub part of the array from index 0 to an index equal to the number of vertices that your mesh generation gave you. Then you can try this link, but I think the values are then copied : https://stackoverflow.com/questions/943635/getting-a-sub-array-from-an-existing-array – Pierre Baret Sep 12 '17 at 23:20
  • @Scott Chamberlain - Code added. – Thorham Sep 13 '17 at 12:24

1 Answers1

1

After much googling I stumbled across the unsafe hackish method I was looking for. I'm posting it for the sake of completeness, but it doesn't seem to be a solution anyone would want to use in production code.

Very dirty hack you don't want to use:

using System;
using UnityEngine;

public unsafe class DirtyHack
{
    public Vector3[] vertices = new Vector3[65532];
    public int index;

    public void DirtyCopy(Mesh mesh)
    {
        fixed (void* ptr = vertices)
        {
            *((UIntPtr*)ptr - 1) = (UIntPtr)(index * 4);
            mesh.vertices = vertices;
            *((UIntPtr*)ptr - 1) = (UIntPtr)(65532);
        }
    }
}

Edit: Changed the code to prevent the array being moved by the GC during the array resize.

Thorham
  • 447
  • 3
  • 11
  • What if the GC moves the vertices array between the constructor and the call to DirtyCopy. Then you're actually writing into random memory. Don't do this. You can't update the length of an array, that's the answer to your question. – Asik Sep 13 '17 at 02:56
  • @Asik - Yes, which is why I wrote that I posted this only for completeness, and not for actual production code. – Thorham Sep 13 '17 at 03:02
  • @Thorham That's quite an interesting hack, though I agree with you about its "dirtiness". So the size of an array is stored at `&array[0] - 1` in memory? That makes sense. I wonder if this could be made safe? Is there any way to prevent the array from being moved during the temporary size change? – piojo Sep 13 '17 at 03:12
  • 1
    @piojo - Yes, see updated code. Basically the array won't be moved inside the fixed code block. – Thorham Sep 13 '17 at 03:50
  • @Thorham Not so dirty anymore! – piojo Sep 13 '17 at 04:11
  • Since this is not writing into random memory anymore I removed the downvote. Wondering if this could have correctness implications for the runtime (now you have allocated memory that doesn't belong to any object). Maybe not. – Asik Sep 13 '17 at 05:31
  • @Asik - Which memory dosn't belong to any object? – Thorham Sep 13 '17 at 05:34
  • Memory that was part of the array and now isn't (because you overwrote the size). – Asik Sep 13 '17 at 05:43
  • @Asik - The size is restored to the original size afterwards. – Thorham Sep 13 '17 at 05:47
  • Only on the original reference, which you can lose. What if the runtime uses mesh.vertice.Length to determine what memory is being referenced, and compacts other objects into the hole now apparently left there. Then if you "re-expand" the array to its original size you're overwriting random objects. Hypothetical but still worrying to me. – Asik Sep 13 '17 at 05:56
  • @Asik - Mesh.vertices isn't an array, it's part of the Unity API. Assigning an array to mesh.vertices just copies the array to the GPU, so it may not be a problem. – Thorham Sep 13 '17 at 06:14
  • I see. If the reference isn't being kept around anywhere then it's probably ok. – Asik Sep 13 '17 at 06:47
  • Late to the party but this doesn't work. It does change the Length property of the array. But as far as I understand it doesn't update the administration of the Garbage Collector. So you're not actually freeing up memory with this trick. – Roy T. Jul 24 '22 at 18:11
  • 2
    @Roy T - It's not about freeing memory, it's about Unity copying only part of an array to the GPU (and reusing memory). Thankfully they've added proper functionality for this now, so this nasty hack isn't needed anymore. – Thorham Jul 25 '22 at 21:12