如何基於高度圖計算可見區域？

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節中的算法更詳細的描述（如果你渴望使用真正巨大的高度圖，你可能會發現其他原因有趣）。