The image below shows the result from my kd-tree based heightmap traversal for terrain rendering. I alternately split the terrain in two in either the x- or z-directions. Each node in the tree stores the minimum and maximum height of the terrain in that node. This gives a very tight fit to the terrain, so when an intersection check against a terrain triangle is done the hit probability is rather high, and only a few triangles per ray need intersecting.
The heightmap and texture represent the Puget Sound area, and can be found at the Large Geometric Models Archive.
Terrain Guided Multi-Level Instancing of Highly Complex Plant Populations
Large Geometric Models Archive