To start out, the world will be made up of two discrete types of objects. The first will be a simple triangulated heightfield as the underlying terrain. The second will be structures of arbitrary geometry resting on that terrain (houses, towers, bridges, etc...). In the end, I'm hoping to turn this engine into a role playing game of some variety. Well, as for VSD, I thought that using separate methods for the two different types of geometry would be the best approach.
For the terrain I thought I'd just test where the viewing frustum intersects the terrain and render everything within those boundries. That's the fastest method I could figure out to render an arbitrary heightfield.
As for the structures that rest on top of the terrain, I came up with a sort of two part VSD method. It involves breaking them up into smaller "chunks", each being of relatively small size and constant texture and then computing the bounding spheres/boxes for these chunks and testing them against the viewing frustum. As these primitives are easier to clip and this could quickly eliminate the portions of the structure that are outside of the viewable area. Then I could use front-side (done before transformation and lighting) backface removal on the remaining polygons to come up with a smaller visible set. The problem with this method is that it only culls out the polygons that either are outside the viewable area, or not facing the user. It does nothing for polygons that are occluded by other polygons. Here is where I was really wondering if anybody had any better ideas or even possible improvements on my idea.