如何根据高度图计算可见区域？

Question

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

本论文表示，高差图的效果要好于将地形变成某种网格，但它们使用布列森哈姆斯对网格进行了采样。

如果我要采用这种方法，我就得为地图上的每一块瓷砖画一条布列森姆线。在我看来，应该可以重复使用大部分的计算，并在一次过计算高度图，如果你在远离眼睛的情况下向外填充--也许是一种扫描线填充方法？

但这种逻辑让我无法理解。逻辑是什么？

这里有一个高度图，上面有一个特定的vantagepoint (绿色立方体)的能见度(如“分水岭”中的“视图”？)画在上面：

​

​

这里是我想出的O(n)扫描；我似乎与如何根据高度图计算可见区域？ Franklin和Ray方法下面的答案中给出的结果相同，只是在这种情况下，我是从眼睛向外行走，而不是沿着周界向中心移动；在我看来，我的方法会有更好的缓存行为--即更快--并且使用更少的内存，因为它不需要跟踪每个瓷砖的向量，只需要记住一条扫描线的价值：

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);
    }
}

这是一个有效的方法吗？

• 它使用的是中心点，而不是LoS通过的‘内部’像素和它的邻居之间的斜率。
• 可以用因子乘法代替三角图来缩放向量吗？
• 它可以使用一个字节数组，因为高度本身就是字节。
• 它不是径向扫描，而是一次做一整条扫描线，但远离点；它只使用几条扫描线
• 如果它工作，你可以想象你可以很好地分配它使用一个径向扫描块；你必须先计算中心-最平瓦，但然后你可以分配所有相邻的瓷砖从它(他们只需要给边缘-最中间值)，然后反过来越来越多的平行度。

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

Answer 1

你想要的是一种扫描算法。基本上，你向每个周边细胞投射射线(Bresenham's)，但是当你走的时候要跟踪地平线，并标记你在路上经过的任何细胞为可见的或不可见的(如果可见的话更新光线的地平线)。这使您从朴素方法的O(n^3) (单独测试nxn DEM的每个单元格)降到O(n^2)。

在这个纸的5.1节中对算法进行了更详细的描述(如果您渴望使用非常巨大的高度图，您可能也会发现由于其他原因而感兴趣)。