У меня есть карта высот.Я хочу эффективно вычислить, какие плитки в нем видны из глаза в любом заданном месте и высоте.
В этой статье предполагается, что карты высот превосходят превращение ландшафта в какую-то сетку, но ониПример сетки с помощью Брезенхамса.
Если бы я принял это, мне пришлось бы сделать линию Брезенхэма на линии прямой видимости для каждой плитки на карте.Мне приходит в голову, что должна быть возможность повторно использовать большую часть вычислений и вычислять карту высот за один проход, если вы заполняете наружу от глаз - возможно, подход с использованием линии сканирования -
Но логикаускользает от меняКакой должна быть логика?
Вот карта высот, на которой видимость с определенной точки обзора (зеленый куб) («видимость» как в «водоразделе»?) Закрашена:
Вот O (n) развертка, которую я придумал;Мне кажется, что это то же самое, что приведено в статье в ответе ниже Как вычислить видимую область на основе карты высот? Метод Франклина и Рэя, только в этом случае я иду от глаза наружу, а не иду попо периметру делаю брезенхамс к центру;На мой взгляд, мой подход будет иметь гораздо лучшее поведение при кэшировании - т.е. будет быстрее - и потреблять меньше памяти, поскольку он не должен отслеживать вектор для каждой плитки, только помните ценность сканлайна:
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 может передать
- .триггер для масштабирования векторов и тому подобного должен быть заменен умножением коэффициента?
- он мог бы использовать массив байтов, поскольку высоты сами по себе являются байтами
- это не радиальная развертка, это делает целоесканируй одновременно, но далеко от точки;он использует только пару строк развертки дополнительной памяти, которая составляет аккуратно
- , если она работает, вы можете себе представить, что вы могли бы распределить ее красиво, используя радиальную развертку блоков;сначала вы должны вычислить самый центральный фрагмент, но затем вы можете распределить все непосредственно смежные фрагменты из этого (им просто нужно дать промежуточные значения для самого края), а затем, в свою очередь, все больше и больше параллелизма.
Так как наиболее эффективно рассчитать этот видимость?