How to effectively check for object visibility prior to object creation?

Question

I'm using pseudo-random noise to create a cube world a la Minecraft. So I've got my noise generators up and running, working great. Right now I'm just directly scaling the noise output to a height and assuming everything below that is solid, I intend to go back later and add some caves, pits, etc. My problem right now is taking these three dimensional integer arrays, and turning them into blocks. I'm hitting a big wall there.

After the numerical list, it's taking almost 30 seconds for a chunk(16x128x16) to generate. That's not counting rendering, that's fast enough iff I don't draw every block in the chunk at one time.

My first approach wast to draw all 20,000+ blocks every frame. I figured out that was bad really fast because I was getting maybe 2 fps.

Then I decided it was better to check if the block was exposed before rendering it. That is when I started to get a huge slowdown. If my list indicated a block existed, then I would check the value of the array in all six directions surrounding the cube with my integer list to see if they also held a cube. This works great, but as I said, my generation time for just one chunk is ~30 sec.

My Exposure check code:

        public bool determineExposed(int x, int y, int z)
    {
        try
        {
            if (_list[x + 1, y, z] == 1 && _list[x - 1, y, z] == 1 && _list[x, y + 1, z] == 1 && _list[x, y - 1, z] == 1 &&
                _list[x, y, z + 1] == 1 && _list[x, y, z - 1] == 1) return false;
            else return true;
        }
        catch
        {
            return false;
        }
    }

How Can I speed this up?

Answer 1

This is not your problem, im guessing. You need to create a single vertex array for every block in the view frustum, and send that to your gpu shader in a draw call. The code you pasted is probably part of your generation call, which usually isnt as much of a problem as the tesselation call. Look at my Techcraft code on codeplex.com for an example of how this can be done single threaded.

Answer 2

Okay, I forgot to post the answer to this problem. Come to find out, the try-catch running a few thousand times per chunk was the bottleneck. Once I circumvented it with if/elseif(s) is sped up immensely, generating a chunk in a few ms! Thanks for the help!

Answer 3

Two things come to mind:

1) Cache your results. You shouldn't be looking at the neighbors. Any block should always know if it's invisible (6 opaque neighbors) and if so it doesn't participate in the rendering at all. Store this as visible/invisible/unknown, only do the calculation if it's unknown. When you edit a block you set it's 6 neighbors to unknown or else you recalculate them at that time. It's probably not worth saving this flag to disk, though.

2) My inclination would be to floodfill your drawing rather than even consider most of the blocks. Take an array big enough to hold a flag (render/transparent/unseen/unknown) for every cell out to your max render distance. Init it to unknown and start from your viewpoint, traverse this like a tree but you only process cells that are unknown so you do each cell only once. For each non-opaque block you add each of it's neighbors to the list. Once you have the list you only render the ones with a status of render. Beware recursion depth here, a breadth-first traversal is a lot safer.

I have done this once, the approach based on rendering all surfaces failed badly, the second try was based on such a traversal and rendered far faster than I needed so I didn't tweak it any more. Doing it breadth-first also gave me an easy way to know the light level (although I did NOT do it like Minecraft--I did the light level at the vertices rather than the blocks. This made things smoothly fade to black when they were too far away rather than the pixellated effect you get with Minecraft.

You can chop the problem even further by not even considering cells outside the player's field of view.

Note that unless your render distance is huge the number of blocks that actually make it to the render list is not much more than the surface area that you can see.