Як обчислити видиму область на основі карти висот?

У мене є карта висот. Я хочу ефективно обчислити, які плитки в ньому видно з очей в будь-якому місці і висоті.

В цій статті показано, що карти висот перевершують поворот місцевості в якусь сітку, але вони пробують сітку, використовуючи Bresenhams.

Якби я прийняв це, мені довелося б зробити лінію лінії Брешенхама лінії візування для кожної плитки на карті. Мені спадає на думку, що потрібно було б повторно використовувати більшу частину обчислень і обчислити карту висот за один прохід, якщо ви наберете зовнішню сторону від очі - чи можливо, наприклад, скануючий тип підходу?

Але логіка вислизає від мене. Яка буде логіка?

Ось карта висот з видимістю з певної точки зору (зелений куб) ( "видно", як в "вододілі"?) Над нею:

Ось розгортка 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.xx), y_diff = abs (eye.zy); 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 передає
• чи може тригер масштабувати вектори і замінити їх множенням на множники?
• він може використовувати масив байтів, так як висоти самі байти
• Його не було радіальна розгортка, вона робить цілу розгортку за раз, але далеко від точки; він використовує тільки пару додаткових рядків для сканування, які акуратно
• Якщо це спрацює, ви можете собі уявити, що ви могли б розподілити його за допомогою променевої розгортки блоків; вам спочатку потрібно обчислити саму центральну частину плитки, але потім ви можете розподілити все відразу суміжні плитки з неї (їм просто потрібно дати найостанніші крайні значення), а потім в свою чергу все більше і більше parallelism.

Отже, як найбільш ефективно обчислити цей режим перегляду?