Proto Chunks and Visibility Rays

Home --> Programming Projects --> Fractal Block Engine --> Coordinate Systems

The Problem

We do not want to render a chunk that is not visible. Even though we are using view frustum culling, we do not want to render chunks that are completely occluded by blocks in front of them.

Moreover, we do not want to expand a block into a chunk in the first place if that block is not visible.

The Solution: Proto Chunks and Visibility Rays

To solve these problems, every second we shoot thousands of rays from the camera into the world. Call these visibility rays. What these rays hit determine when we should render a chunk and when we should expand a block into a chunk.

We shoot more rays closer to the direction of where the player is looking.

What is a Proto Chunk?

For a given level of detail, a block is expanded into a chunk when it is a certain distance from the player. However when it is first expanded, it is a proto chunk. This is an empty shell. It has not yet been loaded (procedurally generated) and behaves as if it is still just a block.

Once a proto chunk is hit by a visibility ray, a request is made to load the chunk (procedurally generate it and update it with any changes that have previously been saved).

When Do We Render Chunks?

When do we render a chunk (including proto chunks)?

First, to render a chunk, it must intersect the view frustum. We do a little math to perform this test every frame. We even do this for proto chunks, although perhaps that is not worth it.

Assume that a chunk has passed the view frustum test.

Rendering all 6 sides of a Proto Chunk?

When we do render a proto chunk P, we probably do not need to render all 6 sides of the cube. This is because some of the sides of P may be adjacent to either Not rendering certain sides of a proto chunk might seem like only a small optimization. However keep in mind that each of these proto chunk cubes takes up a large amount of the screen, so drawing these would draw many pixels.

Code for shooting visibility rays

Here is code for shooting a visibility ray into the world. We start at a point, and then repeatedly move the point by 0.9 (a block is 1.0 wide). So if a chunk is visible, it is possible to hit it with a visibility ray. If a chunk is NOT visible, then it is very unlikely to be hit by a visibility ray (but it is theoretically possible). We are trading speed for accuracy.

Once the point is no longer inside a chunk on the current level, we consider the point on the next coarsest level. That is, we have to change coordinates systems from a level L to a level L-1.

The FastBlockHolder is a class that holds all the blocks of a chunk. 
void ShootVisRay(
    ChunkGetter * chunk_getter,
    CoordConverter * coord_converter,
    int start_level,
    const Vector & start_pos,
    const Vector & dir)
{
    int cur_level = start_level;
    Vector cur_pos = start_pos;
    Vector add = dir;
    Normalize(add);
    add *= 0.9f;

    //We cache the last chunk that we considered.
    //If our vcp has not changed, we reuse that chunk's
    //fast block holder.
    
    bool              have_cached = false;
    ViewerCentricPos  cached_chunk_vcp;
    FastBlockHolder * cached_chunk_fbh = 0;

    while(true) {
        //Only shooting a ray through the 5 finest levels.
        if( start_level - cur_level >= 5 ) return;
    
        //The reader can figure out how to
        //write fast versions of these next two functions.
        //We might want to inline them.
        
        ViewerCentricPos cur_vcp = VectorToVCP(cur_pos);
        LocalBlockPos cur_lbp = VectorToLBP(cur_pos);

        //Fast track if we are in same chunk as last time.
        if( have_cached &&
            cached_chunk_vcp == cur_vcp )
        {
            bool solid = cached_chunk_fbh->IsSolid(cur_lbp);
            if( solid ) return;
            cur_pos += add;
            continue;
        }

        //At this point, we do not have any cached information
        //about the current chunk.

        Chunk * chunk = chunk_getter->GetChunk(cur_level, cur_vcp);
        if( !chunk ) {
            //The chunk does not exist.
            //Going one level closer to the root
            //(going to a coarser level).
            
            have_cached = false;

            if( cur_level-1 < 0 ) return;

            //Converting the vector cur_pos
            //for level cur_level to a vector
            //for level cur_level-1.
            Vector new_pos;
            coord_converter->ConvertPos(
                cur_pos,
                cur_level,
                cur_level-1,
                new_pos);

            cur_pos = new_pos;
            cur_level = cur_level-1;
        } else {
            //The first time within a particular chunk.
            have_cached = true;
            cached_chunk_vcp = cur_vcp;

            //Telling the chunk that is has been hit
            //by a visibility ray.
            chunk->MarkVisRay();
            
            //If the chunk is a proto chunk, the
            //solid function will return true.
            //That is important.
            if( chunk->IsSolid(cur_lbp) ) return;

            //At this point, the chunk is not a proto chunk,
            //and so the fbh will be non-null.
            cached_chunk_fbh = chunk->GetFastBlockHolder();

            cur_pos += add;
        }
    }
}

Different types of solid

There are actually several different notions of what it means for a block to be solid: A block is physically solid if the player cannot move through it. A block is visibly solid if it appears solid for rendering. A block is visray solid if and only if it is both physically and visibly solid.

The code above should really be asking if the blocks are visray solid.

Cocoon Rendering a Chunk

Given a chunk, we say that we "cocoon render" the chunk if we just render the block that occupies the same position as the chunk instead of rendering anything inside the chunk of its children. In the case that the block type of the chunk is visibly solid, we should say that we "solid cocoon render" the chunk as a single block. In the case that the block type is NOT visibly solid, then there is nothing to do if we wanted to "empty cocoon render" the chunk.

The concept of (solid) cocoon rendering a chunk is related to the concept of proto chunks, because when we render a proto chunk, we can only cocoon render it. However, if a chunk is an actual chunk (and not a proto chunk), there is a situation when we might want to cocoon render it. Namely, the situation when the chunk has not been hit by a visibly ray in 10 seconds or so.

In terms of (solid) cocoon rendering a chunk, there are at least two important rules we want to follow. Rule 1: If we (solid) cocoon render a chunk, then we should not render any descendent chunks of that chunk at all. Otherwise, we might get an ugly "Z fighting" rendering glitch. Note that we are assuming the solid block being rendered has no transparency (otherwise that causes a problem). Rule 2: We should not (solid) cocoon render any chunk whose VCP is (0,0,0). If we did do this, then because of Rule 1 and since the player is in every chunk with vcp (0,0,0), then parts of the world would not be rendered when they should be.

One might wonder why we have proto chunks at all. A big reason is because we clear the depth buffer after rending each level. "Fertile" proto chunks are rendered along with other chunks on their same level before we clear the depth buffer. "Non-fertile" proto chunks on level L are instead rendered with the chunks on level L-1 before we clear the depth buffer. Without the existence of proto chunks, parts of the world might be rendered in the wrong order. An engine that does not clear the depth buffer at all would be much simpler, and the reader can figure out how to organize things in that situation. Instead of having a proto chunk, we could simply render the corresponding block as part of the parent chunk. Once a block is subdivided into a chunk, it is automatically populated.

The IsVisiblySolidMod1 Function

The following is an important function for figuring out what to render: IsVisiblySolidMod1. This is a member function of the chunk class. It takes a local block position as an argument and returns a bool. If the local block position is for a child chunk (including a proto chunk), the function automatically returns true. Otherwise, the function returns true iff the block type of the block at that position is "visible solid". This function is used to figure out what is the block surface to render when we render a chunk.

"Mod1" stands for the first modified version of the IsVisiblySolid function. The IsVisiblySolid function just returns if a block is visibly solid (ignoring whether or not it is a child chunk).