Ray-Heightfield intersection testing

• very important for picking and visibility calculation
• the current algorithm implemented in vtHeightFieldGrid::CastRayToSurface
  • it is usable, although not as fast as algorithms which store extra data
  • consists of breaking the ray into a series of points, then checking each point the terrain (above/below)
  • when a pair of points is found which straddle the terrain, it refines the segment in a binary-search fashion
  • since the length of the test is proportional to a single grid element, there is a small chance that it will give results that are off by a small distance (less than 1 grid element)
• Possible improvements:
  1. Convert the 3D ray to a 2D ground ray, then do an iterative walk across the grid (Bresenham-like traversal)
     • e.g. adapt the code from Fast Computation of Terrain Shadow Maps
     • that would eliminate the rare cases of being off by 1 element
     • however, care would need to be taken to deal with cases of near-vertical rays
  2. Store extra data, such as a height extents quadtree

Resources

• Musgrave's QAEB Tracing for Procedural Height Fields
  • no source available, but perhaps good for normal grid heightfields
• many other algorithms, from the ray-tracing field?
• Tom Forsyth says:
  • "Raytracing of heightfields is extremely quick if you have a quadtree with min/max height values in each node of course :-)"
    Wide-bresenham-line-draw through the quadtree at the level of the node you are testing for visibility to see if any nodes fully cover the plane of view. The bresenham scan is three blocks wide to be sure it doesn't miss anything, and it can obviously take advantage of higher levels of the quadtree to be quick.
    Sounds annoying to code up, but should be fairly swift to run
    
    .