Thursday, November 24, 2011

A while ago, I was playing with computing line-of-sight for game-like heightmap terrain.  I wanted to efficiently compute which tiles in it were visible from an eye at any given location and height.

http://web.tecgraf.puc-rio.br/publications/artigo_1999_efficient_lineofsight_algorithms.pdf suggested that heightmaps outperform turning the terrain into some kind of mesh, but they sample the grid using Bresenhams.

If I were to adopt that, I’d have to do a line-of-sight Bresenham’s line for each and every tile on the map. It occurred to me that it ought to be possible to reuse most of the calculations and compute the heightmap in a single pass if you fill outwards away from the eye - a scanline fill kind of approach perhaps?

Here is the O(n) sweep that I came up with; I seems the same as that given in the paper by Franklin and Ray, only in this case I am walking from eye outwards instead of walking the perimeter doing a Bresenham towards the centre; to my mind, my approach would have much better caching behaviour - i.e. be faster - and use less memory since it doesn’t have to track the vector for each tile, only remember a scanline’s worth:

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

Notes

  1. williamedwardscoder posted this

 ↓ click the "share" button below!