After reading a lot about this over the years, the advice that I see the most is to avoid doing it at all.

It might not feel like good advice at first, but the arguments are that the performance gains you get for making this kind of structure is totally overshadowed by the potential performance gain you would get by simply chopping your model into cubes at coarse resolution and doing basic culling. The reason is that modern GPUs are so efficient that they will render amazing amounts of geometry in the same time the CPU would use to be smart about it. To feed the GPU from an advanced structure vs. a simple flat format will incur all sorts of penalties in extra memory usage, memory fragmentation, cache misses etc.

EDIT: I decided to add some more tips for you after reading your question more thoroughly.

I have actually made such an engine myself, and my approach was this:

1. Define a deterministic density function like this: `float densityFunction(vec3 &point);` that returns the density at the given point in space. It should be fairly fast. There exist many such functions that you can use [out there][1], and they can often be combined for interesting results. TIP: Make sure they are continuous, that means that they don’t have any abrupt changes in the density. The "deterministic" and "fast" parts ensure that you can calculate this a lot on the fly, which is the key here.

2. Generate an isosurface based on this density function based on some triangulation algorithm such as [delaunay][2]. You should be able to pass your density function as input, and also you need to be able to specify the corners of a bounding box, and a resolution which basically states how many levels of subdivision you want to trangulate per axis. `void generateIsoSurfaces( func &densityFunction, std::vector<float> &vertices, std::vector<int> &indices, vec3 &low, vec3 &high, int resolution);`

3. Keep track of your "camera" during rendering, and divide the world into cubic chunks of a set size that makes sense. For each visible cube, pass its bounding box and resolution to the triangulation function. The resulting vertices/indices can then be rendered with your favourite graphics subsystem such as OpenGL (or some engine on top of that).

4. To avoid regenerating everything over and over which will be expensive, make sure to keep each chunk of vertices in memory in a pool. Whenever a chunk is outside the view for a predetermined amount of time (or memory gets low) you free the data. If you get really fancy like I did, you can persist the result on disk. Just make sure reading/writing to disk is faster than regenerating it first.

This way to do things is rather elegant, and has many upsides:

 - The density functions can be made as interesting and complex as you like and the engine will cope with them like any other density function.
 - The rendering is fast because you are in effect just making polygon soups in a native format for the graphics subsystem
 - Tweaking performance is really easy. Just change the resolution, bounding box size, chunk pool size etc to balance rendering between CPU and GPU. In my system I also made an adaptive [LOD][3] system so that when the chunks went far away from the camera, a new "less complex" version of the chunk was generated. I operated with resolutions in powers of two so that the poly-count will quadruple between levels. This might generate artifacts such as popping and mismatches at the boundaries between chunks of different levels of detail. In my application this was not important.
 - The density function can be used by other parts of the game, such as physics, and it can be much simpler to use than having to work with the polygons. You can simply use newtons method to probe for where a vector hits the "surface" of the density function, and calculate the normal on that surface by simply doing this 3 times in close proximity.
 - You can use the density function for procedurally generating shader or textures for the surface.
 - Using this landscape engine for multiplayer games is feasible even when you want to use lock-step or similar algorithm for synchronizing game state since it can be made to be portably deterministic (two computers will get the exact same result when calculating the same density function).

There you go. Hope this was helpful!



 [1]: http://www.volumesoffun.com/polyvox-about/
 [2]: http://paulbourke.net/papers/triangulate/
 [3]: http://en.wikipedia.org/wiki/Level_of_detail