如何基于高度图计算可见区域？

Question

我有一个高度图。我想要有效地计算出在任何给定的位置和高度，哪些瓷砖可以从眼睛看到。

This paper表明heightmaps优于将地形变成某​​种网格，但他们使用Bresenhams对网格进行采样。

如果我要采用这种方法，那么我必须为地图上的每个瓷砖做一条视线Bresenham的线。对我而言，如果你向外向外填充，应该可以重复使用大部分计算并计算高度贴图，这可能是扫描线填充的一种方法？

但逻辑逃避我。逻辑是什么？

这里是从特定的VantagePoint（绿色立方体）一个可视性的高度图（“视域”，如“分水岭”？）画了吧：

这里是为O（n ）扫我想出了;我看起来和Franklin和Ray的方法How to compute the visible area based on a heightmap?下的答案中的文章中给出的一样，只是在这种情况下，我是从眼睛向外走，而不是走边界，朝着中心走一条黑暗的街道;我的脑海里，我的做法将有更好的缓存行为 - 即更快 - 并使用更少的内存，因为它不必跟踪每个瓦片的向量，只记得一个扫描线的价值：

typedef std::vector<float> visbuf_t; 

inline void map::_visibility_scan(const visbuf_t& in,visbuf_t& out,const vec_t& eye,int start_x,int stop_x,int y,int prev_y) { 
    const int xdir = (start_x < stop_x)? 1: -1; 
    for(int x=start_x; x!=stop_x; x+=xdir) { 
     const int x_diff = abs(eye.x-x), y_diff = abs(eye.z-y); 
     const bool horiz = (x_diff >= y_diff); 
     const int x_step = horiz? 1: x_diff/y_diff; 
     const int in_x = x-x_step*xdir; // where in the in buffer would we get the inner value? 
     const float outer_d = vec2_t(x,y).distance(vec2_t(eye.x,eye.z)); 
     const float inner_d = vec2_t(in_x,horiz? y: prev_y).distance(vec2_t(eye.x,eye.z)); 
     const float inner = (horiz? out: in).at(in_x)*(outer_d/inner_d); // get the inner value, scaling by distance 
     const float outer = height_at(x,y)-eye.y; // height we are at right now in the map, eye-relative 
     if(inner <= outer) { 
      out.at(x) = outer; 
      vis.at(y*width+x) = VISIBLE; 
     } else { 
      out.at(x) = inner; 
      vis.at(y*width+x) = NOT_VISIBLE; 
     } 
    } 
} 

void map::visibility_add(const vec_t& eye) { 
    const float BASE = -10000; // represents a downward vector that would always be visible 
    visbuf_t scan_0, scan_out, scan_in; 
    scan_0.resize(width); 
    vis[eye.z*width+eye.x-1] = vis[eye.z*width+eye.x] = vis[eye.z*width+eye.x+1] = VISIBLE; 
    scan_0.at(eye.x) = BASE; 
    scan_0.at(eye.x-1) = BASE; 
    scan_0.at(eye.x+1) = BASE; 
    _visibility_scan(scan_0,scan_0,eye,eye.x+2,width,eye.z,eye.z); 
    _visibility_scan(scan_0,scan_0,eye,eye.x-2,-1,eye.z,eye.z); 
    scan_out = scan_0; 
    for(int y=eye.z+1; y<height; y++) { 
     scan_in = scan_out; 
     _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y-1); 
     _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y-1); 
    } 
    scan_out = scan_0; 
    for(int y=eye.z-1; y>=0; y--) { 
     scan_in = scan_out; 
     _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y+1); 
     _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y+1); 
    } 
} 

是它一个有效的方法？

• 它是使用中心点，而不是着眼于“内部”像素和其上侧，所述视距通过
• 可以在三角函数在缩放矢量和这样被替换邻居之间的斜率因子乘法？
• 它可以使用一个字节数组，因为高度本身是字节
• 它不是径向扫描，它一次完成一条扫描线但远离点​​;它只使用几条扫描线 - 价值更高的内存，如果它可以工作，那么它可以很好地分散它
• 您可以想象，您可以使用径向扫描块来很好地分配它;你必须首先计算最中心的瓦片，但是你可以分配所有紧邻的瓦片（他们只需要给出最边缘的中间值），然后再分配越来越多的并行性。

那么如何最有效地计算这个视域？

Answer 1

你想要什么叫做扫描算法。基本上你会将光线（Bresenham's）投射到每个周边细胞，但是随着时间的推移追踪地平线，并标记您在途中通过的任何细胞可见或不可见（并且如果可见，则更新光线的视界）。这会让你从天真方法的O（n^3）（单独测试一个nxn DEM的每个单元格）到O（n^2）。

该paper第5.1节中的算法更详细的描述（如果你渴望使用真正巨大的高度图，你可能会发现其他原因有趣）。