3D Game Geometry

Question

I have a simple game that uses a 3D grid representation, something like:

Blocks grid[10][10][10];

The person in the game is represented by a point and a sight vector:

double x,y,z, dx,dy,dz;

I draw the grid with 3 nested for loops:

for(...) for(...) for(...)
   draw(grid[i][j][k]);

The obvious problem with this is when the size of the grid grows within the hundreds, fps drop dramatically. With some intuition, I realized that:

• Blocks that were hidden by other blocks in the grid don't need to be rendered
• Blocks that were not within the person's vision field also don't need to be rendered (ie. blocks that were behind the person)

My question is, given a grid[][][], a person's x,y,z, and a sight vector dx,dy,dz, how could I figure out which blocks need to be rendered and which don't?

Answer 1

I looked into using JMonkeyEngine, a 3D game engine, a while back and looked at some of the techniques they employ. From what I remember, they use something called culling. They build a tree structure of everything that exists in the 'world'. The idea then is that you have a subset of this tree that represents the visible objects at any given time. In other words, these are the things that need to be rendered. So, say for example that I have a room with objects in the room. The room is on the tree and the objects in the room are children of the tree. If I am outside of the room, then I prune (remove) this branch of the tree which then means I don't render it. The reason this works so well is that I don't have to evaluate EVERY object in the world to see if it should be rendered, but instead I quickly prune whole portions of the world that I know shouldn't be rendered.

Even better, then when I step inside the room, I trim the entire rest of the world from the tree and then only render the room and all its descendants.

I think a lot of the design decisions that the JMonkeyEngine team made were based on things in David Eberly's book, 3D Game Engine Design. I don't know the technical details of how to implement an approach like this, but I bet this book would be a great starting point for you.

Here is an interesting article on some different culling algorithms:

• View Frustum Culling
• Back-face Culling
• Cell-based occlusion culling
• PVS-based arbitrary geometry occlusion culling
• Others

Answer 2

First you need a spatial partitioning structure, if you are using uniform block sizes, probably the most effective structure will be an octree. Then you will need to write an algorithm that can calculate if a box is on a particular side of (or intersecting) a plane. Once you have that you can work out which leaf nodes of the octree are inside the six sides of your view frustum - that's view culling. Also using the octree you can determine which blocks occlude others (sometimes called frustum masking), but get the first part working first.

Answer 3

It sounds like you're going for a minecraft-y type thing. Take a look at this android minecraft level renderer. The points to note are:

• You only have to draw the faces of blocks that are shared with transparent blocks. e.g.: don't bother drawing the faces between two opaque blocks - the player will never see them.
• You'll probably want to batch up your visible block geometry into chunklets (and stick it into a VBO) and determine visibility on a per-chunklet basis. Finding exactly which blocks can be seen will probably take longer than just flinging the VBO at the gpu and accepting the overdraw.
• A flood-fill works pretty well to determine which chunklets are visible - limit the fill using the view frustum, view direction (if you're facing in the +ve x direction, don't flood in the -ve direction), and simple analyses of chunklet data (e.g.: if an entire face of a chunklet is opaque, don't flood through that face)