I had to demo my progress to my professor this week so I worked on it a lot. Some changes I made are:
"Infinite" terrain. The world is now made of chunks of voxels. I add and remove chunks from a chunk buffer so that only chunks around the player are actually loaded and drawn. The generating is done asynchronously so it doesn't kill the framerate.
Caves, overhangs, and tunnels. I took some pointers from notch's post about terrain generation and so now terrain is now generated through a density map. I fill the 3D density map by sampling 3d Perlin noise, augmented by turbulence, at specific intervals. Then I just use trilinear interpolation to fill in the missing details. The resulting density map is then cut to form tunnels using another rigid multi fractal noise generator.
Basic materials (grass, dirt, sand, stone, water). These are determined using the density map described above and depth information. Densities less than 0 are air blocks. Other types of blocks are determined by a combination of depth and density. I'm still not happy with this because, as you can see from the video, areas under certain overhangs leave a silhouette of stone.
Much better performance (200 fps vs 19 fps). This is mainly thanks to face culling and only drawing faces that are touching air blocks. Right now I'm using display lists. I tried using VBOs but I'm still kind of confused on how to actually use it correctly. There is a bunch of conflicting information about deprecated functions and stuff. But I'm pretty happy with display lists so far.
For the future: textures, better and less weird terrain, skybox, better lighting, trees?, and flowing water?