0
\$\begingroup\$

I need to calculate what chunks are in the player's view, meaning I need the 3D positions (the bottom, back, left corner in world space) of each chunk that is in the player's view. I'm not worried about culling, this is mainly to prioritize the generation of new chunks that are in the player's view.

These are 3D chunks, meaning unlike Minecraft, the world is infinite in all directions, including up and down. The chunks are 32x32x32 right now.

The way I am doing it now is I will look at a giant cube of chunks around the player and then do the same exact thing but around points that are cast out in front of the player's camera. This works, but it is fairly slow, I have to check every chunk if it already exists in two different dictionaries before adding it to the right one because my algorithm isn't perfect and sometimes it checks the same position twice, and then after all of that I only use a few of the closest chunk positions because if I used them all it would continue generating those chunks even after the player has moved miles away from it.

So it would be great if I could figure out a fast way to create a list of all the chunk's positions that are in the player's view with no duplicates. Any ideas at all are very welcome! Thank you.

This is my current algorithm:

void CheckForNewChunksAroundMultiplePoints(Vector3 playerCameraPosition, Vector3 playerCameraForward, int startingRenDist, int renderDistIncrement) // checks the surroundings as well as the player's view
{
    Vector3Int chunkPosition = positionToChunkPosition(Vector3Int.CeilToInt(playerCameraPosition));
    chunksToGenerateHash.Clear();

    // checking the surroundings of the player
    Vector3Int startingPos = chunkPosition + new Vector3Int(-surroundRenderDistanceG * chunkRowSize, -surroundRenderDistanceG * chunkRowSize, -surroundRenderDistanceG * chunkRowSize); // the bottom, back, left point of the area we check, a cube of (surroundRenderDistanceG * 2) chunks cubed, or (that * chunkRowSize) voxels cubed 
    int surroundRenderRowSize = surroundRenderDistanceG * 2;

    for (int x = 0; x < surroundRenderRowSize; x++) // x
    {
        for (int z = 0; z < surroundRenderRowSize; z++) // z
        {
            for (int y = 0; y < surroundRenderRowSize; y++) // y
            {
                Vector3Int chunkToCheck = startingPos + new Vector3Int(x * chunkRowSize, y * chunkRowSize, z * chunkRowSize);

                if (!visibleChunksDictionary.ContainsKey(chunkToCheck))
                {
                    if (!chunksToGenerateHash.Contains(chunkToCheck))
                    {
                        chunksToGenerateHash.Add(chunkToCheck); // to be generated later
                    }
                }
            }
        }
    }


    // checking the surroundings of points cast out from the player's view
    Vector3[] points = GetPointsAlongPlayersView(playerCameraPosition, playerCameraForward, startingRenDist, renderDistIncrement, 3);
    for (int i = 0; i < viewPoints; i++)
    {
        chunkPosition = positionToChunkPosition(Vector3Int.CeilToInt(points[i]));

        int chunksRenderDistance = startingRenDist + (renderDistIncrement * i);
        int chunksRenderRowSize = chunksRenderDistance * 2;

        startingPos = chunkPosition + new Vector3Int(-chunksRenderDistance * chunkRowSize, -chunksRenderDistance * chunkRowSize, -chunksRenderDistance * chunkRowSize);


        for (int x = 0; x < chunksRenderRowSize; x++) // x
        {
            for (int z = 0; z < chunksRenderRowSize; z++) // z
            {
                for (int y = 0; y < chunksRenderRowSize; y++) // y
                {
                    Vector3Int chunkToCheck = startingPos + new Vector3Int(x * chunkRowSize, y * chunkRowSize, z * chunkRowSize);

                    if (!visibleChunksDictionary.ContainsKey(chunkToCheck))
                    {
                        if (!chunksToGenerateHash.Contains(chunkToCheck))
                        {
                            chunksToGenerateHash.Add(chunkToCheck); // to be generated later
                        }
                    }
                }
            }
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ What engine are you using? What is the algorithm you're currently using? It sounds like you want to use the same principle as frustum culling, so look into that if you haven't already. \$\endgroup\$
    – Kevin
    Apr 17, 2021 at 4:07
  • \$\begingroup\$ Unity, I explained my algorithm in the post, I am just looking at a cube of chunks around the player and chunks around points cast out from the player's view. And I've looked at frustum culling algorithms very briefly, it looks like it involves getting the objects geometry, I am trying to find out what chunks are in the player's view before I assign geometry to them. So it should be considerably simpler than typical frustum culling algorithms, I would think. \$\endgroup\$
    – Tristan367
    Apr 17, 2021 at 4:22
  • \$\begingroup\$ Writing a brief description of an algorithm is not the same as sharing the algorithm. It's very hard to analyze an algorithm based on so little. Yes, frustum culling considers an object's geometry. The chunk itself inherently has geometry - you said it's 32x32x32, so it's a perfect cube. I haven't built a voxel game before, but off the top of my head I can't think of how you would do any better than a flavor of frustum culling to determine what chunks are visible. \$\endgroup\$
    – Kevin
    Apr 17, 2021 at 4:38
  • \$\begingroup\$ You're right, I will edit some code in :) \$\endgroup\$
    – Tristan367
    Apr 17, 2021 at 5:43

2 Answers 2

0
\$\begingroup\$

I haven't built a voxel game before, so this is theoretical, but I think this is a good starting direction:

Unity has a function GeometryUtility.TestPlanesAABB() that can be used to check if a bounding box is inside or overlapping a plane array. One of the main uses for this is in determining what is within the camera's view frustum and thus potentially visible to the camera.

Basic use would be like this:

var frustumPlanes = GeometryUtility.CalculateFrustumPlanes(Camera.main);
foreach (var chunk in chunks) {
    if (GeometryUtility.TestPlanesAABB(frustumPlanes, chunk.Bounds)) {
        GenerateChunk(chunk);
    }
}

Obviously it's not practical to check against every possible chunk in the world, but you could easily filter chunks by distance from the player. You don't have to store the bounds for every single chunk; since all chunks are the same size you can easily calculate the bounds dynamically.

\$\endgroup\$
3
  • \$\begingroup\$ It works great! The only thing is I can't multi-thread that Unity function, but even still it not only seems faster but it obviously works better than my horrible algorithm haha but I use it to create the offsets for the bounding boxes in the beginning. Thanks so much! \$\endgroup\$
    – Tristan367
    Apr 17, 2021 at 6:51
  • \$\begingroup\$ You might be able to run CalculateFrustumPlanes on the main thread, then do the rest on worker threads, since then you're just using simple math types/functions (assuming you calculate your bounds objects using the regular chunk grid, rather than querying them from a renderer/collider). Most Unity math functions work just fine off the main thread, as long as you don't touch a UnityEngine.Object along the way. \$\endgroup\$
    – DMGregory
    Apr 17, 2021 at 13:34
  • \$\begingroup\$ Unfortunately, GeometryUtility.TestPlanesAABB is also enforced to the main thread. And yes I am calculating the bounds and using no Unity Gameobjects or colliders for my chunks. I actually restarted this project when I learned how to generate meshes without having to use GameObjects :) much better performance. Every thing except queing up what meshes to draw with Graphics.DrawMesh on the GPU is done on another thread. And obviously GeometryUtility.TestPlanesAABB now too \$\endgroup\$
    – Tristan367
    Apr 18, 2021 at 21:52
1
\$\begingroup\$

I later looked up an implementation of this algorithm so I could do it on another thread, I didn't even know it existed and it is actually fairly simple! My implementation still uses a Unity function Plane.GetSide(point) but it's thread safe. It just tells you if a point is on the positive side of a plane.

    foreach (plane in frustumPlanes)
    {
        int inCount = 8;

        foreach (corner in corners)
        {
            if (!plane.GetSide(corner)) // the Unity function, returns true if the point is on the positive side of the plane
            {
                inCount -= 1;
            }
        }
        if (inCount <= 0)
        {
            return false;
        }
    }
    return true;

Implemented like this:

bool ChunkIsInFrustum(Vector3Int chunk)
{
    for (int i = 0; i < 6; i++)
    {
        bool chunkInFrustum = false;
        for (int j = 0; j < 8; j++)
        {
            if (frustumPlanes[i].GetSide(chunk + cornersOffsets[j]))
            {
                chunkInFrustum = true;
                break;
            }
        }
        if (!chunkInFrustum)
        {
            return false;
        }
    }
    return true;
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .