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.