Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Would it be better to write this algorithm in a vetex shader?

Discussion in 'Scripting' started by unity_bzkabR87OIGiaw, Apr 9, 2021.

  1. unity_bzkabR87OIGiaw

    unity_bzkabR87OIGiaw

    Joined:
    Apr 9, 2021
    Posts:
    2
    Hi all.
    I am making a game like minecraft.
    the game has problems with loading chunks. (chunk is place in terrain 16 * 16 blocks) it works very slowly, like in old minecraft versions. I have a third diserminal array with types of the blocks. If next to the block is an air block, i add to the mesh a voxel.
    This is a code:
    Code (CSharp):
    1. public void Optimize()
    2.     {  
    3.         Mesh mesh = new Mesh();
    4.  
    5.         List<Vector3> verts = new List<Vector3>();
    6.         List<int> tris = new List<int>();          
    7.         List<Vector2> uvs = new List<Vector2>();
    8.  
    9.         //Vector3 Vplus = new Vector3(1f, 0f, 1f);
    10.  
    11.         for(int x = 1; x < 17; x++){
    12.             for(int z = 1; z < 17; z++){
    13.                 for(int y = 1; y < maxHeight + 20; y++){
    14.                     if(true)
    15.                     {
    16.                         Vector3 blockPos = new Vector3(x-1, y, z-1);
    17.                         int numFaces = 0;
    18.                         bool [] transparentTiles = new bool[6];
    19.                         if(bloks[x, y, z] != BlockType.Air) {
    20.                             transparentTiles = Block.blocks[bloks[x, y, z]].isTransparent;
    21.                         } else {
    22.                             transparentTiles = new bool[]{false, false, false, false, false, false};
    23.                         }
    24.  
    25.                         BlockType thisBT = bloks[x, y, z];
    26.                         Vector3 [] Vpos = new Vector3[4];
    27.  
    28.                         //up
    29.                         if(!transparentTiles[2] && bloks[x, y+1, z] != BlockType.Air){
    30.                             blockPos = new Vector3(x, y+1, z);
    31.                             Vpos = Block.blocks[bloks[x, y+1, z]].returnVerts(1);
    32.                             verts.Add(blockPos + Vpos[0]);
    33.                             verts.Add(blockPos + Vpos[1]);
    34.                             verts.Add(blockPos + Vpos[2]);
    35.                             verts.Add(blockPos + Vpos[3]);
    36.                             numFaces++;
    37.                             uvs.AddRange(Block.blocks[bloks[x, y+1, z]].bottomPos.GetUVs());
    38.                         }
    39.  
    40.                         //bottom
    41.                         if(!transparentTiles[0] && bloks[x, y-1, z] != BlockType.Air){
    42.                             blockPos = new Vector3(x, y-1, z);
    43.                             Vpos = Block.blocks[bloks[x, y-1, z]].returnVerts(0);
    44.                             verts.Add(blockPos + Vpos[0]);
    45.                             verts.Add(blockPos + Vpos[1]);
    46.                             verts.Add(blockPos + Vpos[2]);
    47.                             verts.Add(blockPos + Vpos[3]);
    48.                             numFaces++;
    49.                             uvs.AddRange(Block.blocks[bloks[x, y-1, z]].topPos.GetUVs());
    50.                         }
    51.  
    52.                         //front
    53.                         if(!transparentTiles[2] && bloks[x, y, z-1] != BlockType.Air){
    54.                             blockPos = new Vector3(x, y, z-1);
    55.                             Vpos = Block.blocks[bloks[x, y, z-1]].returnVerts(4);
    56.                             verts.Add(blockPos + Vpos[0]);
    57.                             verts.Add(blockPos + Vpos[1]);
    58.                             verts.Add(blockPos + Vpos[2]);
    59.                             verts.Add(blockPos + Vpos[3]);
    60.                             numFaces++;
    61.                             uvs.AddRange(Block.blocks[bloks[x, y, z-1]].sidePos.GetUVs());
    62.                         }
    63.  
    64.                         //right
    65.                         if(!transparentTiles[2] && bloks[x+1, y, z] != BlockType.Air){
    66.                             blockPos = new Vector3(x+1, y, z);
    67.                             Vpos = Block.blocks[bloks[x+1, y, z]].returnVerts(5);
    68.                             verts.Add(blockPos + Vpos[0]);
    69.                             verts.Add(blockPos + Vpos[1]);
    70.                             verts.Add(blockPos + Vpos[2]);
    71.                             verts.Add(blockPos + Vpos[3]);
    72.                             numFaces++;
    73.                             uvs.AddRange(Block.blocks[bloks[x+1, y, z]].sidePos.GetUVs());
    74.                         }
    75.  
    76.                         //back
    77.                         if(!transparentTiles[2] && bloks[x, y, z+1] != BlockType.Air){
    78.                             blockPos = new Vector3(x, y, z+1);
    79.                             Vpos = Block.blocks[bloks[x, y, z+1]].returnVerts(2);
    80.                             verts.Add(blockPos + Vpos[0]);
    81.                             verts.Add(blockPos + Vpos[1]);
    82.                             verts.Add(blockPos + Vpos[2]);
    83.                             verts.Add(blockPos + Vpos[3]);
    84.                             numFaces++;
    85.                             uvs.AddRange(Block.blocks[bloks[x, y, z+1]].sidePos.GetUVs());
    86.                         }
    87.  
    88.                         //left
    89.                         if(!transparentTiles[2] && bloks[x-1, y, z] != BlockType.Air){
    90.                             blockPos = new Vector3(x-1, y, z);
    91.                             Vpos = Block.blocks[bloks[x-1, y, z]].returnVerts(3);
    92.                             verts.Add(blockPos + Vpos[0]);
    93.                             verts.Add(blockPos + Vpos[1]);
    94.                             verts.Add(blockPos + Vpos[2]);
    95.                             verts.Add(blockPos + Vpos[3]);
    96.                             numFaces++;
    97.                             uvs.AddRange(Block.blocks[bloks[x-1, y, z]].sidePos.GetUVs());
    98.                         }
    99.  
    100.                         int tl = verts.Count - 4 * numFaces;
    101.                         for(int i = 0; i < numFaces; i++)
    102.                         {
    103.                             tris.AddRange(new int[] { tl + i * 4, tl + i * 4 + 1, tl + i * 4 + 2, tl + i * 4, tl + i * 4 + 2, tl + i * 4 + 3 });
    104.  
    105.                         }
    106.                     }
    107.                 }
    108.             }
    109.         }
    110.  
    111.         mesh.vertices = verts.ToArray();
    112.         mesh.triangles = tris.ToArray();
    113.         mesh.uv = uvs.ToArray();
    114.  
    115.         mesh.RecalculateNormals(); //g
    116.  
    117.         GetComponent<MeshFilter>().mesh = mesh;
    118.         GetComponent<MeshCollider>().sharedMesh = mesh;
    119.  
    120.         isOptimized = true;
    121.     }
    122.  
    will it work faster if I write it in a vertex shader?
     
  2. Suddoha

    Suddoha

    Joined:
    Nov 9, 2013
    Posts:
    2,824
    There are certainly other techniques and APIs to generate these kind of values for meshes more efficiently and way faster. Custom threading, JobSystem, ComputerBuffers, existing and optimized libraries...

    However, these type of algorithms can still be pretty fast on a potato CPU when optimized properly.
    The thing is: the code you posted is not even optimized. You've got lots of unnecessary allocations and operations in the most-inner loop, which already take a good amount of time for sure.
     
  3. unity_bzkabR87OIGiaw

    unity_bzkabR87OIGiaw

    Joined:
    Apr 9, 2021
    Posts:
    2
    what can be optimized in my loop?
    How much is it possible to optimize this algorithm? I want the game to run on msi wind u160 (intel atom n450), the weakest device i have.

    this is code of the class Block:
    Code (CSharp):
    1. using System;
    2. using System.Collections;
    3. using System.Collections.Generic;
    4. using UnityEngine;
    5. using System.Xml.Serialization;
    6.  
    7. public class Block
    8. {
    9.     public Tile top, side, bottom;
    10.  
    11.     public float height;
    12.     public RenderType rend;
    13.     public bool [] isTransparent = new bool[6];
    14.     public Vector3 [] standartVerts = new Vector3 [8];
    15.  
    16.     public Vector3 [ , ] tileVerts = new Vector3 [6, 4];
    17.     public TilePos topPos, sidePos, bottomPos;
    18.  
    19.     public Block(Tile tile, float height, RenderType Rend, bool[] transparent)
    20.     {
    21.         top = side = bottom = tile;
    22.         this.isTransparent = transparent;
    23.         GetPositions();
    24.         GetVerticles(Rend);
    25.     }
    26.  
    27.     public Block(Tile top, Tile side, Tile bottom, float height, RenderType Rend, bool[] transparent)
    28.     {
    29.         this.top = top;
    30.         this.side = side;
    31.         this.bottom = bottom;
    32.         this.isTransparent = transparent;
    33.         GetPositions();
    34.         GetVerticles(Rend);
    35.     }
    36.  
    37.     public Block(RenderType rend){
    38.         this.isTransparent = new bool[]{false, false, false, false, false, false};
    39.     }
    40.  
    41.     void GetPositions()
    42.     {
    43.         topPos = TilePos.tiles[top];
    44.         sidePos = TilePos.tiles[side];
    45.         bottomPos = TilePos.tiles[bottom];
    46.     }
    47.  
    48.     public void GetVerticles(RenderType thisBlockRender){
    49.         if(thisBlockRender == RenderType.fullBlock){
    50.             standartVerts[0] = new Vector3(0, 1, 0); //0
    51.             standartVerts[1] = new Vector3(0, 1, 1); //1
    52.             standartVerts[2] = new Vector3(1, 1, 1); //2
    53.             standartVerts[3] = new Vector3(1, 1, 0); //3
    54.             standartVerts[4] = new Vector3(0, 0, 0); //4
    55.             standartVerts[5] = new Vector3(1, 0, 0); //5
    56.             standartVerts[6] = new Vector3(1, 0, 1); //6
    57.             standartVerts[7] = new Vector3(0, 0, 1); //7
    58.         } else {
    59.             if(thisBlockRender == RenderType.transparentBlock){
    60.                 standartVerts[0] = new Vector3(0, 1, 0); //0
    61.                 standartVerts[1] = new Vector3(0, 1, 1); //1
    62.                 standartVerts[2] = new Vector3(1, 1, 1); //2
    63.                 standartVerts[3] = new Vector3(1, 1, 0); //3
    64.                 standartVerts[4] = new Vector3(0, 0, 0); //4
    65.                 standartVerts[5] = new Vector3(1, 0, 0); //5
    66.                 standartVerts[6] = new Vector3(1, 0, 1); //6
    67.                 standartVerts[7] = new Vector3(0, 0, 1); //7
    68.             } else {
    69.                 if(thisBlockRender == RenderType.upper_halfBlock){
    70.                     standartVerts[0] = new Vector3(0, 1, 0);
    71.                     standartVerts[1] = new Vector3(0, 1, 1);
    72.                     standartVerts[2] = new Vector3(1, 1, 1);
    73.                     standartVerts[3] = new Vector3(1, 1, 0);
    74.                     standartVerts[4] = new Vector3(0, 0.5f, 0);
    75.                     standartVerts[5] = new Vector3(1, 0.5f, 0);
    76.                     standartVerts[6] = new Vector3(1, 0.5f, 1);
    77.                     standartVerts[7] = new Vector3(0, 0.5f, 1);
    78.                 } else {
    79.                     if(thisBlockRender == RenderType.lower_halfBlock){
    80.                         standartVerts[0] = new Vector3(0, 0.5f, 0);
    81.                         standartVerts[1] = new Vector3(0, 0.5f, 1);
    82.                         standartVerts[2] = new Vector3(1, 0.5f, 1);
    83.                         standartVerts[3] = new Vector3(1, 0.5f, 0);
    84.                         standartVerts[4] = new Vector3(0, 0, 0);
    85.                         standartVerts[5] = new Vector3(1, 0, 0);
    86.                         standartVerts[6] = new Vector3(1, 0, 1);
    87.                         standartVerts[7] = new Vector3(0, 0, 1);
    88.                     }
    89.                 }
    90.             }
    91.         }
    92.        
    93.         //up
    94.  
    95.         tileVerts[0, 0] = standartVerts[0];
    96.         tileVerts[0, 1] = standartVerts[1];
    97.         tileVerts[0, 2] = standartVerts[2];
    98.         tileVerts[0, 3] = standartVerts[3];
    99.        
    100.         // bottom
    101.        
    102.         tileVerts[1, 0] = standartVerts[4];
    103.         tileVerts[1, 1] = standartVerts[5];
    104.         tileVerts[1, 2] = standartVerts[6];
    105.         tileVerts[1, 3] = standartVerts[7];
    106.        
    107.         //front
    108.        
    109.         tileVerts[2, 0] = standartVerts[4];
    110.         tileVerts[2, 1] = standartVerts[0];
    111.         tileVerts[2, 2] = standartVerts[3];
    112.         tileVerts[2, 3] = standartVerts[5];
    113.        
    114.         //right
    115.        
    116.         tileVerts[3, 0] = standartVerts[5];
    117.         tileVerts[3, 1] = standartVerts[3];
    118.         tileVerts[3, 2] = standartVerts[2];
    119.         tileVerts[3, 3] = standartVerts[6];
    120.        
    121.         //back
    122.        
    123.         tileVerts[4, 0] = standartVerts[6];
    124.         tileVerts[4, 1] = standartVerts[2];
    125.         tileVerts[4, 2] = standartVerts[1];
    126.         tileVerts[4, 3] = standartVerts[7];
    127.        
    128.         //left
    129.        
    130.         tileVerts[5, 0] = standartVerts[7];
    131.         tileVerts[5, 1] = standartVerts[1];
    132.         tileVerts[5, 2] = standartVerts[0];
    133.         tileVerts[5, 3] = standartVerts[4];
    134.        
    135.     }
    136.     public Vector3 [] returnVerts(int tileNum){
    137.         Vector3 [] returnV = new Vector3[4];
    138.         for(int i = 0; i < 4; i++){
    139.             returnV[i] = tileVerts[tileNum, i];
    140.         }
    141.         return returnV;
    142.     }
    143.  
    144.     public static Dictionary<BlockType, Block> blocks = new Dictionary<BlockType, Block>(){
    145.         {BlockType.Air, new Block(RenderType.NORENDERING)},
    146.         {BlockType.Grass, new Block(Tile.Grass, Tile.GrassSide, Tile.Dirt, 1.0f, RenderType.fullBlock, new bool[]{true, true, true, true, true, true})},
    147.         {BlockType.Dirt, new Block(Tile.Dirt, 1.0f, RenderType.fullBlock, new bool[]{true, true, true, true, true, true})},
    148.         {BlockType.Stone, new Block(Tile.Stone, 1.0f, RenderType.fullBlock, new bool[]{true, true, true, true, true, true})},
    149.         {BlockType.Trunk, new Block(Tile.TreeCX, Tile.TreeSide, Tile.TreeCX, 1.0f, RenderType.fullBlock, new bool[]{true, true, true, true, true, true})},
    150.         {BlockType.Leaves, new Block(Tile.Leaves, 1.0f, RenderType.transparentBlock, new bool[]{false, false, false, false, false, false})},
    151.         {BlockType.StoneL, new Block(Tile.Stone, Tile.StoneL, Tile.Stone, 0.5f, RenderType.lower_halfBlock, new bool[]{false, false, false, true, false, false})},
    152.         {BlockType.StoneU, new Block(Tile.Stone, Tile.StoneU, Tile.Stone, 0.5f, RenderType.upper_halfBlock, new bool[]{false, false, false, false, true, false})},
    153.     };
    154.  
    155.  
    156.     public static Dictionary<BlockType, RenderType> render = new Dictionary<BlockType, RenderType>(){
    157.         {BlockType.Grass, RenderType.fullBlock},
    158.         {BlockType.Dirt, RenderType.fullBlock},
    159.         {BlockType.Stone, RenderType.fullBlock},
    160.         {BlockType.Trunk, RenderType.fullBlock},
    161.         {BlockType.Leaves, RenderType.transparentBlock},
    162.         {BlockType.StoneL, RenderType.lower_halfBlock},
    163.         {BlockType.StoneU, RenderType.upper_halfBlock},
    164.         {BlockType.Air, RenderType.NORENDERING},
    165.     };
    166. }
    167. [Serializable]
    168. public enum BlockType {Air, Dirt, Grass, Stone, Trunk, Leaves, StoneU, StoneL}
    169.  
    170. public enum RenderType {lower_halfBlock, upper_halfBlock, fullBlock, transparentBlock, NORENDERING}
     
  4. Suddoha

    Suddoha

    Joined:
    Nov 9, 2013
    Posts:
    2,824
    Probably many things, I didn't check the entire piece of code.

    Just a few basic examples:

    First code snippet, line 18. An allocation of throw-away array. You never use that instance, instead you get the arrays from your blocks or re-allocate it just a few lines later in the 'else' case (line 22).

    Here you've already got 16*16*(20+maxHeight) allocations that are simply not required.

    For the else-case, you could re-use a single array that's allocated outside of the loops, which would also reduce the number of allocations by few more thousands.

    How to improve that? For instance, allocate it once and whenever you do not get the array from your blocks, use the pre-allocated array rather than allocating one again and again. That's possible since you do not seem to use them anywhere else, and you do not pass them around so "noone relies" on them in the next iteration and you're save to re-use it.

    Similar issue in line 26: The allocation can be omitted completely, as you only get the array from your blocks. That's another 16*16*(20+maxHeight) = 5120 + (256*maxHeight) allocations less.

    I cannot tell how much performance that would gain, probably quite a bit already but it won't be the only thing to look for. I also cannot tell how much performance you can gain in general. That's something you'll find out as you optimize it more and more...

    However, let's face reality: you need to be aware that there are also probably way more efficient ways to generate the data. Yours is rather trivial, kind of the brute-force attempt to generate all the mesh data.

    Minecraft and all these type of games have usually faced many of these problems too, and hence a lot of time was spent optimizing them or even switching to different algorithms and techniques over the years. As easy as the concept might seem, there's a lot of experience and hard work required.