автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и средства определения видимости при сканировании земной поверхности

На правах рукописи

Польский Сергей Владимирович

МЕТОДЫ И СРЕДСТВА ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПРИ СКАНИРОВАНИИ ЗЕМНОЙ ПОВЕРХНОСТИ

Специальность 05.13.01. - "Системный анализ, управление и обработка информации"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2004

Работа выполнена в Московском государственном университете леса.

Научный руководитель: Доктор технических наук, профессор

Степанов Игорь Михайлович

Официальные оппоненты: Доктор технических наук, профессор

Чуркин Анатолий Васильевич

Кандидат технических наук, старший научный сотрудник Скрипник Александр Борисович

Ведущая организация: Федеральное государственное

унитарное предприятие Научно-исследовательский институт точных приборов

Защита состоится «12» марта 2004 г. в 14*® на заседании диссертационного совета Д212.146.04 при Московском государственном университете леса по адресу: 141005, г. Мытищи-5, Московская обл., МГУЛ.

С диссертацией можно ознакомиться в библиотеке МГУЛ. Автореферат разослан «_»_2004 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

Тарасенко П.А.

2004-4 27566

Актуальность работы. Задачу определения видимости (далее - задачу

видимости) приходится решать во многих ситуациях и областях, это удаление скрытых линий и поверхностей при визуализации геометрических данных, расчет освещения, распознавание геометрических фигур, управление роботами. Например, при расчёте освещения нужно определить, освещается ли некоторый геометрический объект источником света или же он частично или полностью находится в тени от других объектов. Нужно отметить, что если источник света точечный (лампа накаливания) — достаточно определить для каждой точки освещаемого объекта освещена эта точка или находится в тени (виден ли из этой точки источник света). Если же источник света имеет размер (лампа дневного света), то для точки объекта не будет однозначного признака видимости источника света, часть точек источника света может быть видима, часть - невидима (так называемая полутень).

заслонки Z

Рис. 1. Задача определения видимости

Можно сформулировать задачу видимости следующим образом. Даны два множества точек А и В, между которыми необходимо определить видимость, и загораживающее множество точек Ъ (см. рис. 1). Точки ЛеА и <)еВ являются взаимовидимыми, если (ИЛ + (1 — ОС?)Ъ для У1е[0..1] , где Я,

(} - векторы из начала координат в точки Я и р соответственно, X - некоторый параметр. То есть, если отрезок Яр не пересекает загораживающее множество. Между множествами точек А и В существует видимость, если существует хотя бы одна взаимовидимая пара точек Множества, между которыми

необходимо определить видимость, в дальнейшем будут называться площадками, загораживающие множества - заслонками, а отрезки Яр, соединяющие точки площадок — отрезками видимости. На плоскости в качестве площадок и заслонок обычно выступают либо точки, либо отрезки прямых, в трехмерном пространстве к ним добавляются многоугольники. Таким образом, решение задачи видимости - это определение наличия видимости между площадками. Для одних задач достаточно определения самого факта наличия видимости, для других необходимо определить какие части площадок являются взаимовидимыми, для третьих - получить коэффициент видимости (отношение числа взаимовидимых пар точек на площадках к числу всех возможных пар).

В зависимости от постановки задачи видимости будут эффективны разные методы её решения, например, для и

поверхностей используются одни методы, а для освещения - другие. В настоящей работе рассматривается задача видимости, возникающая при радиолокационном сканировании земной поверхности. Радиолокационная станция бокового обзора (РЛС БО) сканирует поверхность Земли с помощью радара, расположенного на самолете, летящем вдоль границы сканируемой зоны. Одной из задач РЛС является определение положения объектов, расположенных на дорогах в сканируемой зоне. Так как угол между осью луча антенны и земной поверхностью мал, то при сканировании необходимо учитывать элементы ландшафта, непроницаемые или плохо проницаемые для радиоволн, которые могут заслонить часть дорог, в результате чего отдельные объекты будут невидимы. К таким элементам ландшафта относятся рельеф земной поверхности и лесные массивы. Информация об участках местности, которые могут быть невидимы, позволит лучше спланировать сканирование и повысить степень доверия к его результатам. Особенности задач, возникающих при сканировании земной поверхности, таковы:

- необходимо определять видимость в трёхмерном пространстве между площадками-отрезками (участками дорог и участками траектории самолёта-носителя РЛС);

- для достаточно точной аппроксимации карты местности необходимы десятки и сотни тысяч многоугольников заслонок;

- задачи необходимо решать достаточно быстро (время решения не должно превышать нескольких минут).

Для решения задачи видимости в наиболее общем виде, а именно, между площадками-многоугольниками в трёхмерном объектном пространстве (том, в котором заданы заслонки и площадки), существует два известных метода -портальный и комплекс видимости, но время их работы сильно зависит от количества заслонок. Верхняя оценка времени решения составляет 0(Ы6) для портального метода и 0(№1) для комплекса видимости, где N - количество заслонок. Это делает практически невозможным решение поставленных задач не только в реальном времени, но и вообще за приемлемое время. Даже при относительно небольшом количестве заслонок в 5000 единиц количество операций составит Ю'5 (для комплекса видимости) что на современных процессорах, выполняющих миллиард операций в секунду, займет 106 секунд, то есть около 12 суток непрерывных расчетов. Дело в том, что существующие методы разрабатывались для определённых задач и условий, и одним из таких условий является то, что объекты значительно чаще являются невидимыми, чем видимыми. В качестве примера, можно привести этаж здания, когда из каждой комнаты видимы лишь несколько соседних комнат, а все остальные -невидимы. Существующие методы используют это обстоятельство, что позволяет им значительно сократить время расчётов. В случае с ландшафтом невидима лишь малая часть объектов, а большинство — видимы, поэтому время работы существующих методов приближается к верхним оценкам.

В связи с вышеизложенным, актуальным является нахождение методов, позволяющих эффективно решать задачи видимости применительно к

заданным условиям, то есть для ландшафтов и при большом количестве заслонок. Основным критерием эффективности является время решения. Во-первых, необходим метод для решения задачи видимости между площадками-отрезками, скорость которого имела бы небольшую зависимость от числа заслонок. Во-вторых, необходим метод представления данных о ландшафте, который позволит отсеивать заслонки, не влияющие на видимость между заданной парой площадок. Как правило, на видимость между двумя площадками влияет лишь некоторая часть заслонок. Определив, какие заслонки не влияют на видимость, можно значительно увеличить скорость решения задачи видимости, так как время её решения зависит от числа заслонок. Простой способ отсеять лишние заслонки - их последовательный перебор и проверка того, влияют они на видимость, или нет. Этот способ требует времени, пропорционального количеству заслонок. Так как количество заслонок, которыми представлен ландшафт велико, то требуется более эффективный метод, позволяющий отсеивать сразу группы заслонок, не проверяя каждую из них.

Цели исследования. Как отмечено выше, существующие методы решения задачи видимости требуют большого времени и не подходят для решения задач, возникающих при сканировании поверхности Земли. Поэтому целью данной работы является разработка метода и построение на его основе алгоритма для быстрого решения задачи видимости между площадками-отрезками для ландшафтов, аппроксимированных многоугольниками.

Научная новизна.

1. Разработан новый метод решения задачи видимости на плоскости и в трёхмерном пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками-отрезками. Отличительная особенность разработанного метода заключается в том, что решение происходит в пространстве отрезков видимости. Время его работы значительно меньше зависит от количества заслонок, чем у существующих методов, оно составляет 0(Ы21о£М)» тогда как для лучшего из существующих методов, комплекса видимости, требуется где N - количество заслонок. Это позволяет рассчитывать видимость при большом количестве заслонок за приемлемое время;

2. На основе использования нового метода разработан алгоритм для решения задачи видимости между двумя отрезками в пространстве;

3. Разработан способ хранения данных цифровой карты местности и алгоритм для выборки из нее заслонок на определенном участке карты. Способ основан на использовании тетрарного дерева, в данной работе рассмотрены особенности его применения для решения задачи видимости;

Достоверность и обоснованность полученных результатов обусловлена применением математически обоснованных методов решения. Кроме того, произведен ряд численных экспериментов, показавших, что результаты расчёта с помощью предложенного метода совпадают с результатами уже имеющихся методов решения задачи видимости.

Практическая ценность. Разработана программа расчета видимости участков дорог с траектории самолета-носителя радиолокационной системы бокового обзора. Разработанный метод также может быть использован для решения задачи видимости в других областях, например, в компьютерной графике.

Публикации. По результатам исследований опубликовано 8 печатных работ, список которых приведён в конце автореферата.

На защиту выносятся.

1. Разработанный метод решения задачи видимости между отрезками в пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками за время 0(Н21о{»М);

2. Разработанный способ хранения данных цифровой карты местности и алгоритм для эффективной выборки из нее заслонок, необходимых для решения задачи видимости.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (105 наименований), приложений и изложена на 128 страницах машинописного текста, содержит 3 таблицы и 69 рисунков. Приложение к диссертации представлено на 2-х страницах.

Содержаниера боты

Во введении сформулирована задача, показана актуальность темы диссертации, научная новизна предложенных методов и их практическая ценность.

В первой главе диссертации рассмотрены принципы, использующиеся при сканировании земной поверхности, особенности работы радиолокационных систем бокового обзора (РЛС БО) и сформулированы требования к разрабатываемым методам и алгоритмам решения задачи видимости, возникающей при сканировании. В главе рассмотрены существующие методы решения задачи видимости и сделан анализ их эффективности применительно к рассматриваемым задачам.

В РЛС БО сканирование производится с помощью антенны, расположенной вдоль фюзеляжа самолёта, летящего параллельно сканируемой зоне, луч антенны направлен вбок от самолёта на эту зону (см. рис. 2). Одной из задач сканирования является определение положения расположенных на дорогах объектов.

Из-за того, что угол между лучом радара и поверхностью земли очень мал (при высоте траектории полета самолёта 20 км и полосе сканирования 200 км он составляет 6° - 20°), даже небольшое по высоте препятствие, например, лес, может заслонить существенный участок дороги. Действительно, при высоте деревьев 20 м тень от деревьев достигает размеров 100 - 200 м в длину, то есть полностью закрывает дорогу (см. рис. 2). Таким образом, участок дороги оказывается полностью невидимым с самолета.

/

/ Траектория самолёта '____.____Лесные массивы

Рис. 2. Боковой обзор местности

В качестве антенны РЛС БО используется фазированная антенная решётка, которая позволяет электронно управлять направлением луча. Это даёт возможность сканировать один и тот же участок местности с различных точек траектории самолёта. Условия видимости участка дороги будут различны для разных точек траектории (см. рис. 3), поэтому возникает задача выбора участков траектории для сканирования конкретных участков дорог.

а) препятствие затеняет часть дороги б) препятствие не затеняет дорогу

Рис. 3. Видимость участка дороги при различной ориентации луча радара

В работе задача видимости сформулирована следующим образом. Задана сканируемая зона и траектория самолета, носителя антенны РЛС БО. Самолёт летит с постоянной скоростью и на постоянной высоте вдоль сканируемой

зоны. Заданы также все дороги в сканируемой зоне, лесные массивы и рельеф местности. Информация о сканируемой зоне задана цифровой картой местности (ЦКМ). По карте местности необходимо определить все видимые и невидимые участки дорог в сканируемой зоне. Для решения задачи видимости необходимо разработать соответствующие алгоритмы и реализовать их программно.

Для решения задачи видимости в заданной постановке необходимо:

- определить, какие участки дорог видимы при конкретном положении самолета на траектории;

- определить, для каких участков траектории самолета видимы заданные участки дорог;

- определить, какие участки дорог невидимы для любой точки траектории;

Все эти задачи сводятся к определению видимости между двумя отрезками в пространстве, один отрезок - участок дороги, другой - участок траектории самолета. В качестве заслонок выступают элементы ландшафта -рельеф и лесные массивы, представленные в виде набора многоугольников. Общее количество таких многоугольников зависит от точности с которой задана ЦКМ и её размеров. При размерах карты 100x100 км, и размере квадратной ячейки сетки рельефа 200 м количество ячеек составит 500x500=250000, а число треугольников - 500000.

Нужно отметить, что поставленные задачи требуют полного решения задачи видимости: необходимо найти не только какой-то один возможный отрезок видимости, но и определить взаимовидимые участки площадок, то есть, фактически, найти все возможные отрезки видимости.

Существует несколько вариантов постановки задачи видимости, и для каждого варианта существуют свои методы и алгоритмы решения, которые наиболее эффективны именно для этих вариантов. Например, методы удаления скрытых линий и поверхностей позволяют рассчитать видимость только с некоторой точки и не могут использоваться для расчёта освещения от неточечного источника света. В свою очередь, методы, ориентированные на расчёт освещения, требуют больших объёмов памяти и времени, что не позволяет их использовать для решения задачи удаления скрытых линий и поверхностей, которую, как правило, приходится решать в реальном времени.

Наиболее известная и исследованная задача - задача удаления скрытых линий и поверхностей. Она состоит в том, чтобы определить какие части объектов при проецировании на экран будут видны наблюдателю, а какие -заслонены другими объектами. Её решение сводится к поиску пересечения проекций объектов и требует времени 0(N2logN), где N — количество объектов. Этот метод можно применить, например, для определения видимости местности из заданной точки траектории самолета, но для определения видимости между двумя отрезками он неприменим. Задачу видимости для неточечных площадок можно решить с помощью портального метода или комплекса видимости.

Портальный метод состоит в разбиении объектного пространства на выпуклые объемы таким образом, что все заслонки лежат на гранях этих

объемов. Некоторые соприкасающиеся грани соседних объемов имеют области (порталы), не содержащие заслонок. Через такие области можно, находясь в одном объеме, видеть содержимое соседнего объема. После разбиения находятся цепочки порталов между площадками, через которые можно провести отрезок видимости, для этого решается задача пронизывания порталов. Верхняя оценка времени решения составляют где N -

количество заслонок.

Комплексом видимости называется некоторая структура в пятимерном пространстве прямых, заданных в координатах Плюкера, которая разделяет это пространство на области, соответствующие множеству прямых пересекающих одни и те же объекты. Время, необходимое для построения комплекса видимости, составляет О^Ь^), где N — количество заслонок. Задачу видимости между заданными площадками можно решить с помощью комплекса видимости, если выделить области пятимерного пространства, которые соответствуют прямым, проходящим, через обе площадки.

Использование существующих методов для решения задачи видимости даже при небольшом количестве заслонок потребует значительных вычислительных затрат, что делает их неприемлемыми для решения поставленных в работе задач, когда требуется решать задачу видимости с участием десятков и сотен тысяч заслонок.

Вторая глава посвящена разработке нового метода решения задачи видимости. Предложенный метод основан на использовании пространства отрезков видимости. Каждый отрезок видимости соответствует некоторой точке этого пространства. Каждая точка заслонки отображается в некоторое множество точек пространства отрезков видимости, это означает, что для соответствующих этому множеству отрезков видимости, видимость отсутствует (см. рис. 4).

участок, с которого полностью участок, с которого видима

участок, с которого полностью видима дорога

а) пространство отрезков видимости а) объектное пространство

Рис. 4. Определение видимости с помощью пространства отрезков видимости

Таким образом, необходимо определить множество точек пространства отрезков видимости, в которые не отображается ни одна из точек заслонок. Это множество соответствует множеству отрезков, для которых видимость существует, что и является решением задачи видимости.

В отличие от комплекса видимости, в котором используется пространство прямых, размерность пространства отрезков видимости не зависит от размерности объектного пространства, а зависит от размерности площадок, между которыми необходимо определять видимость. Это позволяет решать задачу видимости между отрезками в пространстве за то же время, что и между отрезками на плоскости.

Прежде чем решать пространственную задачу, рассмотрим задачу видимости между отрезками на плоскости. Отрезки заданы парами (точка, направляющий вектор) (Р|,Ьх) и (Рг,!^) (рис. 5).

а) объектное пространство б) пространство отрезков видимости

Рис. 5. Задача видимости между двумя отрезками

Пространство отрезков видимости в этом случае двумерное. Координаты точки \¥(и,у) в пространстве отрезков видимости является параметрами в уравнениях которыми заданы площадки-отрезки.

Точка W(u,v) эквивалентна отрезку видимости АВ, соединяющему площадки. Множество всех возможных отрезков видимости представляет собой квадрат с единичной стороной, находящийся в начале координат. Отрезки видимости Д1,Я2Д3Д4), представляются точками ^1'Д2'Д3'Д4'), точки заслонок (М и N - прямыми (М' и №), а сами заслонки - областями между этими прямыми (заслонка MN эквивалентна многоугольнику R1'R4'R3'R2').

Преобразование точки Р объектного пространства в пространство отрезков видимости (см. рис. 5) следует из условия, что точка Р должна лежать на прямой АВ, то есть расстояние ¡1Г от точки Р до прямой АВ равно нулю.

<1, =ат+Ьи + су + е1,

где

а = Ь = 1^{Р-Р1), с = (Р-Р1)%, ¿-(Р-^ПРг-Ъ)

¿г=0=>сплг+Ьи+су+<1=0 (1)

Операция с = а1Ь = агЬг -ауЬг- перпендикулярное скалярное произведение. Множество точек, принадлежащих заслонке можно задать в

параметрическом виде Р = М+к{Ы-М), где Коэффициент к

вычисляется из двух расстояний от точек М и N до прямой АВ:

Если-знаменатель положителен (Ли-й„ >0), это два условия ¿„¿0 и ¿„¿0. Условие положительности знаменателя, включается в эти два условия, кроме точки пересечения двух гипербол <!и ■=<!„, в которой знаменатель равен нулю. Но эту точку можно отбросить, потому что она никак не повлияет на непрерывное решение. Если знаменатель отрицателен (^-^<0), это два обратных условия йи £ 0 и ¿„ г 0 „ Таким образом, область пространства отрезков видимости, затененная одной, заслонкой ограничена двумя гиперболами йи =0 и <1„ =0, соответствующими точкам М и N. А также условиями того, что точка Р пересечения прямой отрезка АВ с заслонкой MN принадлежит отрезку АВ. Отрезок АВ можно задать параметрически Р^А+ЦВ-А) и ограничить параметр Параметр вычисляется из

расстояний йл и ¡1, от точек А и В до отрезка ММ

Рис. 6. Область, затенённая одной заслонкой

Можно заметить, что знаменатели дробей в выражениях (2) и (3) равны и отображаются в пространство отрезков видимости в виде

прямой. Поэтому достаточно рассмотреть два случая, при положительном и отрицательном знаменателе, при этом область, затеняемая заслонкой, тоже разбивается на две части. Условие 0^/51 в зависимости от знака знаменателя представляет собой либо пару (¿,2:0, ¿0) при положительном знаменателе, либо пару (</,¿0, (¡¡'¿.О) при отрицательном. Все ограничивающие линии пересекаются в одной точке Лл= <}и-с1„ =0 (см. рис. 6).

В общем случае уравнение (1) является уравнением гиперболы, но когда площадки параллельны, коэффициент (а) становится равным нулю и уравнение превращается в уравнение прямой. В этом случае затененная область является пересечением двух полуплоскостей, заданных прямыми (1М = 0 и =0. Кроме того, область ограничена квадратом 1x1 возможных решений. Таким образом, одна заслонка может затенить не более двух выпуклых областей, а N заслонок -максимум 2N областей. Если окажется, что эти области полностью покрывают квадрат возможных решений, значит между площадками нет видимости.

Первый алгоритм, позволяющий определить, есть ли незатененные участки, основан на последовательном отсечении от множества возможных решений затеняемых заслонками областей. Для этого создается список незатененных участков, в котором находятся выпуклые, непересекающиеся между собой многоугольники. Вначале в этот список заносится исходный квадрат 1x1. Очередная затенённая область отсекается от каждого многоугольника этого списка. Если после отсечения очередной области в списке не останется ни одного многоугольника - значит между площадками нет видимости. После того, как вычтены все области, многоугольники этого списка представляют множество возможных отрезков видимости. Нижняя оценка времени работы алгоритма Таким будет время в случае, когда область первой же проверяемой заслонки полностью закрывает квадрат. Верхняя оценка времени 0(Ы3), где N — количество заслонок...

Второй алгоритм решения основан на том, что если незатененные участки существуют, они должны иметь границу. Эта граница должна либо проходить по границам затененных заслонками областей, либо по границе исходного квадрата. Когда есть несколько затенённых областей, необходимо перебрать их границы и последовательно вычесть из них все участки, которые совпадают с остальными затенёнными областями. Участки ребер, несовпадающие ни с одной из затенённых областей, являются участками границы незатененных областей. Определить наличие незатененных областей на границе можно, отсортировав все общие участки вдоль границы. Эту операцию можно выполнить за время где N - количество участков, равное количеству

заслонок. Так как необходимо перебрать границы всех заслонок, общее время составит где N - количество заслонок.

Пример с параллельными площадками является лишь частным случаем, общим решением будет алгоритм, работающий с гиперболами. Несмотря на некоторое увеличение сложности вычислений, схема работы алгоритма и оценка времени его выполнения остается такой же, как и для прямолинейного

случая. Единственное отличие состоит в том, что граничные точки заслонок представляются гиперболами в пространстве отрезков видимости, следовательно, затененные и незатененные области также ограничены гиперболами. Если применить алгоритм нахождения границ незатененных областей, то потребуется найти отрезки гипербол, незатененные областями, ограниченными гиперболами.

Отличия от прямолинейного случая минимальны:

- потребуется искать пересечения не прямых, а гипербол, в отличие от прямых, две гиперболы могут пересекаться не в одной, а в двух точках;

- при параметрическом задании гипербол можно использовать одну из координат и или v в качестве параметра;

- области, ограниченные гиперболами, не являются выпуклыми;

Для решения поставленных задач требуется построить алгоритм определения видимости между отрезками в трехмерном пространстве. Этот алгоритм будет иметь минимальные отличия от плоского случая. Как и в плоском случае, отрезок АВ задается формулами А = Р1+иЬ1, и В = Р1+\Ь1, только теперь в них фигурируют трехмерные вектора. Заслонки заданы набором вершин С| и плоскостью (#,£>). Отрезок АВ пересекает плоскость заслонки в некоторой точке Р. Параметр I в параметрическом задании этой точки на отрезке вычисляется по формуле (4):

В качестве и выступают расстояния от соответствующих точек до плоскости заслонки. Условия, налагающиеся на ^ остаются прежними 0 5/51.

Условием принадлежности точки Р многоугольнику заслонки будет набор условий, что все точки лежат с одной стороны от ребер многоугольника, при условии, что многоугольник выпуклый.

((Р-С,)х(С,,,-С())Л';>0 (5)

Выражение (5) является смешанным произведением трех векторов, причем последние два - постоянны для заслонки и характеризуют ее ребро. Поэтому можно переставить векторное произведение (,(Р-С,)({СМ 0)

и заменить его правую часть на вектор Ец подставив в это выражение параметрически заданную точку получим:

где

(6)

В результате получается одно условие для знаменателя, который общий для всех выражений, два условия для ^ которые образуют горизонтальную и

вертикальную прямые, и несколько условий для ребер многоугольника заслонки, которые образуют гиперболы. Таким образом, области затененные заслонками в трехмерном пространстве образуются так же, как и на плоскости (см. рис. 6), но могут ограничиваться не только двумя, но и тремя и более гиперболами. Сам алгоритм решения задачи видимости и оценка времени его работы останутся прежними.

Применение нового метода для решения поставленных задач позволит получить решение за время 0(М21о§М), где N - количество заслонок.

В третьей главе разработаны структуры данных и алгоритмы, позволяющие хранить информацию о ландшафте и формировать данные о заслонках, для решения задачи видимости.

Исходные данные о карте местности представлены в виде плоского изображения (см. рис. 7а). Дороги заданы в виде ломаных, кроме того, у каждой дороги есть некоторая ширина. Лесные массивы ограничены замкнутыми контурами, каждый массив имеет определенную высоту деревьев. Рельеф определяется картой высот - двумерным массивом высот для точек карт расположенных в узлах наложенной на карту местности сетки.

лесные массивы

а) цифровая карта местности б) квадранты тетрарного дерева в) тетрарное дерево

Рис. 7. Хранение цифровой карты местности

Тетрарное дерево позволяет более компактно представить данные о рельефе, так как плоские участки карты можно хранить с меньшей детализацией, чем участки с сильно меняющимся рельефом (см. рис. 76). Такое представление позволяет уменьшить количество хранимых данных в 10-25 раз по сравнению с картой высот. Кроме того, оно позволяет эффективно искать участки дорог и лесных массивов, попадающие в некоторую область. Использование других иерархических методов хранения менее эффективно. Бинарное дерево будет иметь в два раза больше узлов, следовательно и время их обхода будет в два раза больше. Использовать восьмеричное дерево имеет смысл только для работы с трёхмерными данными, а хранение карты в трёхмерном виде потребует на порядок больше памяти, чем в плоском.

Перед расчетом видимости исходные данные преобразуются в тетрарное дерево. Преобразование включает в себя следующие этапы:

- контуры лесных массивов разбиваются на выпуклые многоугольники;

- из этих многоугольников вырезаются участки, соответствующие дорогам;

- карта высот преобразуется в тетрарное дерево;

- для многоугольников лесных массивов и участков дорог определяется, в какие ячейки тетрарного дерева они попадают;

Разбиение на выпуклые многоугольники контуров лесных массивов необходимо для ускорения работы алгоритмов отсечения многоугольников прямой (для выпуклого многоугольника может быть только две точки пересечения с прямой, тогда как для произвольного может быть больше, поэтому время отсечения выпуклого 0^), произвольного - О(Мс^К), где N -количество вершин многоугольника). Отсечение используется при вырезании окрестностей дорог из лесных массивов, определения попадания лесного массива в ячейку тетрарного дерева и для нахождения многоугольников, соответствующих лесным массивам.

Вырезание областей, соответствующих дорогам необходимо, из-за того, что в контурах лесных массивов они не были учтены, то есть лесной массив полностью покрывает внутреннее пространство контура, включая дороги, проходящие внутри него. Очевидно, что если не произвести вырезание окрестностей дорог, то все такие лесные дороги будут всегда заслонены многоугольниками лесного массива.

При решении задачи видимости между участком траектории и участком дороги формируется выпуклая область, в которой должны лежать заслонки, влияющие на видимость. Область сравнивается с корневым квадрантом тетрарного дерева, если квадрант полностью находится вне этой области, значит, любой объект, находящийся в этом квадранте, находится вне этой области. Если квадрант полностью внутри, следовательно, все объекты внутри него находятся в этой области. Если часть квадранта внутри, а часть снаружи, рекурсивно рассматриваются его дочерние квадранты. Таким образом, выделяются все квадранты, которые лежат в заданной области, а затем для этих квадрантов формируются заслонки.

В четвёртой главе рассмотрен пакет программ для расчета видимости участков дорог с траектории самолёта-носителя РЛС БО, разработанный на базе предложенного метода, а также результаты исследования характеристик нового метода. Для сравнения исследуются показатели двух существующих методов определения видимости (портального и комплекса видимости). Скорость работы оценивается для двумерного объектного пространства. Если сравнивать скорость работы в трёхмерном пространстве, то разработанный метод будет работать с площадками-отрезками, то есть с частным случаем задачи видимости, а существующие методы - с площадками-многоугольниками, то есть с более общим случаем. Очевидно, что сравнение будет не в пользу существующих методов. На плоскости все алгоритмы работают с площадками-отрезками и оказываются поставленными в одинаковые условия.

Исследуются три различных метода. Первый метод - портальный, верхняя оценка времени его работы для плоского случая 0(М31оёМ),, Второй метод - комплекс видимости, верхняя оценка времени его работы Третий метод - вновь разработанный, при этом тестируются две его

модификации, первая модификация использует отсечение для поиска незатенеиных областей, а вторая ищет границы этих областей. Оценки времени их работы 0(М3)и соответственно.

1200000

100 200 300 400 Количество заслонок

Рис. 8. Зависимость времени работы от количества заслонок

На диаграмме приведены показатели алгоритмов для количества заслонок от 20 до 500 (см. рис. 8). Здесь, начиная со 100 заслонок, видимости между площадками уже не существует, поэтому время работы всех методов, кроме отсечения, приближается к верхней оценке. Отчетливо видно, что время работы метода, использующего поиск границ незатененных областей, растет значительно медленнее, чем время портального метода и комплекса видимости. Время работы алгоритма, использующего отсечение, остается практически постоянным после некоторого числа заслонок. Это происходит потому, что после отсечения областей, затеняемых первой сотней заслонок, не остается ни одной незатененной области в пространстве отрезков видимости и дальнейшего отсечения не производится. Этот метод хорош, когда между площадками нет видимости, но если она существует, его показатели несколько хуже, чем при поиске границ, это видно в левой части графика. Кроме того, метод отсечения нельзя применить для общих случаев, когда области заслонок ограничены гиперболами.

Пакет программ, использующий разработанный метод определения видимости, позволяет:

- определять участки дорог в сканируемой зоне или на ее части, видимые с текущего положения самолёта-носителя РЛС БО (см. рис. 9);

- определять участки дорог в сканируемой зоне или на ее части, невидимые ни с одной точки траектории самолёта-носителя РЛС БО;

- определять участки траектории самолета-носителя РЛС БО, с которой будут видны все дороги в сканируемой зоне или на ее части;

- отображать сканируемую зону или ее часть в виде плоского изображения со всеми участками дорог, и выделить их невидимые участки;

отображать перспективную проекцию сканируемой зоны со всеми участками дорог, с выделенными невидимыми участками;

Рис. 9. Результаты работы программного комплекса

Программный пакет выполнен на языке C++ для операционной системы Microsoft Windows 95 и более поздних версий. Время расчета видимости на компьютере с процессором Intel Celeron 433 MHz варьируется от нескольких секунд до нескольких минут в зависимости от типа задачи, количества заслонок и участков дорог.

Основные выв оды ирезуль татыра боты

1. В результате исследования разработан новый метод решения задачи видимости, скорость работы которого не зависит от размерности объектного пространства, а зависит только от суммарной размерности площадок, между которыми нужно рассчитать видимость.

2. На основе метода построен алгоритм решения задачи видимости между двумя площадками-отрезками на плоскости и в трёхмерном пространстве, который позволяет найти все множество взаимовидимых пар точек целевых площадок за время 0(N2logN).

3. Для решения задач видимости, возникающих при сканировании земной поверхности, разработана структура хранения информации о цифровой карте местности, и алгоритм для эффективной выборки из нее информации о заслонках.

4. Разработан пакет программ для определения видимости между участками дорог и отрезками траектории самолёта-носителя РЛС БО использующий новый метод определения видимости.

Списокпубликаций

1. Методы и программные средства комплексной оптимизации РТА по критерию времени. Отчет по НИР. Отв. исполнитель Польский С.В. — М: МГУЛ, 1998.-81 с.

2. Программа расчета и отображения пятна радара на поверхности Земли. Отчет по НИР. Отв. исполнитель Польский С.В. - М: МГУЛ, 1999. - 8 с.

3. Программа расчета и отображения пятна радара на поверхности Земли, оценки флуктуации луча и определения координат радиолокационных отметок. Отчет по НИР. Отв. исполнитель Польский С.В. - М: МГУЛ, 1999. - 23 с.

4. Польский С.В. Быстрые алгоритмы вычисления элементарных функций в системах реального времени // Автоматизация и компьютеризация информационной техники и технологии / Научн. тр. Вып. 300. - М: МГУЛ,

1999.-с. 88-91.

5. Польский С.В. Эффективное решение задач видимости в области компьютерной графики на плоскости // Автоматизация и компьютеризация информационной техники и технологии / Научн. тр. Вып. 308. — М: МГУЛ,

2000.-С.71-78.

6. Польский С.В. Аппаратная реализация быстрых методов вычисления элементарных функций // Автоматизация и компьютеризация информационной техники и технологии / Научн. тр. Вып. 308. - М: МГУЛ, 2000. - с. 85 - 89.

7. Видимость участков зоны обзора. Описание пакета программ. Отчет по НИР. Отв. исполнитель Польский С.В. - М: МГУЛ, 2003. - 142 с.

8. Польский С.В. Эффективный метод определения видимости между отрезками на плоскости [Электронный ресурс]: Электрон, статья (1 файл 387584 Кб) // Электронный журнал МГУЛ. - М: МГУЛ, 2003. - Свободный доступ из сети Интернет. - http://www.mgul.ac.ru/journal/aiticles/000022r.zip

Отпечатано с готового оригинала

Лицензия ПД № 00326 от 14.02.2000 г. Подписано к печати ОЛ.О/.Of. Формат 60x88/16 Бумага 80 г/м2 " Снегурочка" Ризография Объем_Тираж /Й?экз._ Заказ № _

¿VTi.n.

Издательство Московского государственного университета леса. 141005. Мытищи-5, Московская обл., 1-я Институтская, 1, МГУЛ. Телефоны: (095) 588-57-62,588-53-48,588-54-15. Факс: 588-51-09. E-mail: izdat@mgul ac.ra

?/. 2181

РНБ Русский фонд

2004-4 27566

Содержание.

Введение.

Глава 1 Задачи видимости, возникающие при сканировании поверхности Земли, анализ существующих методов их решения.

1.1 Радиолокационные системы бокового обзора.

1.2 Задачи видимости в РЛС бокового обзора.

1.3 Требования к методам решения задачи видимости в РЛС бокового обзора.

1.4 Анализ существующих методов решения задачи видимости.

1.4.1 Методы удаления скрытых линий и поверхностей.

1.4.2 Методы расчёта освещения.

1.4.3 Методы построения потенциально видимых множеств, решение задачи видимости для площадок-полигонов.

1.4.4 Нахождение пронизывающих прямых.

1.5 Решение одиночной задачи видимости существующими методами

1.5.1 Решение задачи видимости на плоскости.

1.5.2 Решение задачи видимости в пространстве.

1.5.3 Использование комплекса видимости.

1.6 Анализ возможности использования существующих методов определения видимости в рассматриваемых условиях.

1.7 Выводы.

Глава 2 Разработка метода решения задачи видимости на базе перехода в пространство отрезков видимости.

2.1 Решение задачи видимости для точечных площадок.

2.1.1 Видимость точка-точка.

2.1.2 Видимость точка-отрезок.

2.1.3 Видимость точка-полигон.

2.2 Решение задачи видимости для произвольных площадок.

2.2.1 Видимость отрезок-отрезок.

2.2.2 Видимость отрезок-полигон.

2.2.3 Видимость полигон-полигон.

2.3 Обобщение алгоритма решения задачи видимости.

2.4 Применение алгоритма для решения задачи видимости при сканировании поверхности Земли.

2.5 Выводы.

Глава 3 Разработка метода формирования проблемно-ориентированной цифровой карты местности для решения задачи видимости.

3.1 Хранение информации о карте местности.

3.2 Формирование заслонок и площадок для решения задачи видимости

3.3 Отсеивание лишних заслонок при решении единичной задачи видимости.

3.4 Решение задачи видимости для двух отрезков в пространстве.

3.5 Выводы.

Глава 4 Пакет программ решения задачи видимости при сканировании земной поверхности: результаты эксперимента.

4.1 Состав программного пакета.

4.2 Характеристики программы расчета видимости.

4.3 Оценка эффективности разработанного метода для решения задачи видимости.

4.4 Внедрение разработанных методов и структур.

4.5 Выводы.

Актуальность темы.

Задачу определения видимости приходится решать во многих ситуациях и областях. Например, определение видимости является одним из важных этапов при визуализации трёхмерных геометрических данных, когда необходимо определить, какие части трёхмерных объектов при проецировании на картинную плоскость (экран) окажутся заслонены от наблюдателя другими объектами. Как правило, геометрические объекты представляются набором многоугольников - полигонов. При кажущейся простоте, эта задача требует больших объёмов вычислений даже при небольшом количестве объектов, так как необходимо проверить каждый объект на заслонённость от наблюдателя всеми остальными объектами. Кроме визуализации, существуют и другие области, где требуется решать задачу определения видимости (далее - задачу видимости). Это освещение, распознавание геометрических фигур, управление роботами и так далее (подробное описание областей применения приведено в [49]). Например, при расчёте освещения нужно определить, освещается ли объект источником света или же он частично или полностью находится в тени от других объектов. Нужно отметить, что постановка задачи видимости в этом случае несколько отличается от той, что имеет место при визуализации. Для визуализации необходимо определить видимость некоторого объекта из некоторой точки (точки схода пучка проецирующих прямых), при этом каждая точка каждого объекта может быть либо видима, либо невидима. Для расчёта освещения необходимо определять видимость между двумя объектами (источник света и освещаемый объект), каждый из которых имеет размер. В этом случае для каждой точки объекта не будет однозначного признака видимости источника света, часть точек источника света будет видима, часть -невидима.

Можно сформулировать задачу видимости следующим образом. Даны два множества точек А и В, между которыми необходимо определить видимость, и загораживающее множество точек Z. Точки Re А и QeB являются взаимовидимыми, если (Rt + (1 - t)Q) g Z для Vte[0.1] , где R, Q - векторы из начала координат в точки R и Q соответственно, t - некоторый параметр. То есть, если отрезок RQ не пересекает загораживающее множество. Между множествами точек А и В существует видимость, если существует хотя бы одна взаимовидимая пара точек ReA и QeB. Видимость является полной, если взаимовидима любая пара точек Re А и QeB. Множества, между которыми необходимо определить видимость, в дальнейшем будут называться площадками, загораживающие множества - заслонками, а отрезки RQ, соединяющие точки площадок - отрезками видимости. На плоскости в качестве площадок и заслонок обычно выступают либо точки, либо отрезки прямых, в трёхмерном пространстве к ним добавляются многоугольники. Таким образом, решение задачи видимости - это определение наличия видимости между площадками. Для одних задач достаточно определения самого факта наличия видимости, для других необходимо определить какие части площадок являются взаимовидимыми, для третьих - получить коэффициент видимости (отношение числа взаимовидимых пар точек на площадках к общему числу возможных пар).

Как отмечалось выше, задача видимости возникает в различных областях, и в зависимости от постановки задачи будут эффективны разные методы её решения. Например, для задач удаления скрытых линий и поверхностей используются одни методы, а для расчёта освещения - другие. В настоящей работе рассматривается задача видимости, возникающая при радиолокационном сканировании поверхности Земли. Радиолокационная станция бокового обзора (PJIC БО) сканирует поверхность Земли с помощью радара, расположенного на самолете, летящем вдоль границы некоторой зоны обзора по заданной траектории. Одним из режимов работы PJIC является определение положения объектов, расположенных на дорогах в зоне обзора. При сканировании необходимо учитывать то обстоятельство, что элементы ландшафта, непроницаемые или плохо проницаемые для радиоволн, могут заслонить часть дорог, в результате чего, некоторые объекты будут пропущены. К таким элементам ландшафта можно отнести рельеф и лесные массивы. При этом возникают следующие задачи:

- необходимо определить, какие участки дорог будут видимы при заданном положении самолёта;

- необходимо определить, с каких точек траектории самолёта будут видимы определенные участки дорог;

- необходимо определить, какие участки дорог будут невидимы с любой точки траектории самолёта;

Особенности поставленных задач таковы, что необходимы десятки и сотни тысяч полигонов заслонок для достаточно точной аппроксимации карты местности, а определять видимость необходимо быстро. Если последние две задачи можно решить на этапе планирования сканирования местности, то первую, необходимо решать в реальном времени, чтобы в каждый момент знать, какие участки местности можно сканировать при текущем положении самолёта, а какие сканировать бесполезно.

Для решения задачи видимости в наиболее общем виде, а именно, между площадками-полигонами в пространстве, существует несколько известных алгоритмов - портальный [39] и комплекс видимости [49,86], но время их работы сильно зависит от количества заслонок. Верхние оценки времени составляют 0(N6) для портального метода и 0(N4logN) для комплекса видимости, где N - количество заслонок. Это делает практически невозможным решение поставленных задач не только в реальном времени, но и вообще за приемлемое время. Даже при относительно небольшом количестве заслонок в 5000 единиц количество операций составит 1015 (для комплекса видимости) что на современных процессорах, выполняющих миллиард операций в секунду, займет 106 секунд, то есть около 12 суток непрерывных расчетов. Дело в том, что существующие методы разрабатывались для определённых задач и условий, и одним из таких условий является то, что объекты значительно чаще являются невидимыми, чем видимыми. В качестве примера, можно привести этаж здания, когда из каждой комнаты видимы лишь несколько соседних комнат, а все остальные - невидимы. Существующие методы используют это обстоятельство, что позволяет им значительно сократить время расчётов. В случае с ландшафтом (открытым пространством), невидима лишь малая часть объектов, а большинство - видимы, поэтому время работы существующих методов приближается к верхним оценкам.

Достичь более высокой скорости расчетов можно двумя способами. Во-первых, с помощью увеличения скорости вычислений, повышая быстродействие вычислительной системы и оптимизируя программу. Во-вторых, с помощью более эффективных методов решения. Если с помощью первого способа можно увеличить быстродействие лишь в несколько раз, то более эффективный метод позволит достичь увеличения скорости вычислений на несколько порядков. Например, если удастся снизить степень зависимости времени вычислений от количества заслонок хотя бы на единицу.

Таким образом, требуется метод, который позволит решать поставленные задачи более эффективно, чем существующие методы. Главным критерием эффективности является время решения. Как было показано выше, существующие методы анализа видимости для общих случаев требуют больших вычислительных затрат. Задачи видимости для частного случая можно решать более эффективно, чем такие общие задачи анализа. Если ровные участки наблюдаемых дорог аппроксимировать отрезками прямых, то вместо анализа видимости между площадками-полигонами, достаточно определить видимость между двумя отрезками: отрезком дороги и отрезком траектории самолета.

Кроме метода решения задачи видимости, требуется разработать способ представления данных о ландшафте, который позволит отсеивать заслонки, не влияющие на видимость между заданной парой площадок. Как правило, на видимость между двумя площадками влияет лишь некоторая часть заслонок. Определив, какие заслонки не влияют на видимость, можно значительно увеличить скорость решения задачи видимости, так как время её решения зависит от числа заслонок. Простой способ отсеять лишние заслонки - их последовательный перебор и проверка того, влияют они на видимость, или нет. Этот способ требует времени, пропорционального количеству заслонок. Так как количество заслонок, которыми представлен ландшафт велико, то требуется более эффективный метод, позволяющий отсеивать сразу группы заслонок, не проверяя каждую из них.

Цели исследования.

Как отмечалось выше, существующие методы решения задачи видимости требуют большого времени и не подходят для решения задач, возникающих при сканировании поверхности Земли. Поэтому целью данной работы является разработка метода и построение на его основе алгоритма для быстрого решения задачи видимости между площадками-отрезками для ландшафтов, аппроксимированных полигонами.

Научная новизна.

- Разработан новый метод решения задачи видимости на плоскости и в трёхмерном пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками-отрезками. Время его работы значительно меньше зависит от количества заслонок в сцене, чем у существующих методов, оно составляет 0(N logN), тогда как для лучшего из существующих методов, комплекса видимости, 0(N4logN), где N - количество заслонок. Это позволяет использовать разработанный метод для расчёта видимости при большом количестве заслонок;

- На основе нового метода разработан алгоритм для решения задачи видимости между двумя отрезками в пространстве;

- Разработан способ хранения данных цифровой карты местности и алгоритм для выборки из нее заслонок на определенном участке карты. Способ основан на использовании тетрарного дерева. В данной работе рассмотрены особенности его применения для решения задачи видимости.

Практическая ценность.

Разработана программа расчета видимости участков дорог с траектории самолета-носителя PJIC бокового обзора.

Публикации.

По результатам исследований опубликовано 8 печатных работ.

На защиту выносятся.

- Разработанный метод решения задачи видимости между отрезками в пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками за время 0(N2logN);

- Разработанный способ хранения данных цифровой карты местности и алгоритм для эффективной выборки из нее заслонок на определенном участке карты.

Структура и объем диссертации.

Диссертация состоит из введения, четырёх глав, заключения, списка

4.5 Выводы

Предложенные в диссертации методы и структуры данных позволили разработать программный пакет, который позволяет эффективно решать задачи видимости. Причем, время расчета сравнительно невелико: на вычислительных машинах средней мощности оно составляет от нескольких секунд до нескольких минут в зависимости от задачи, то есть решение практически можно производить в реальном масштабе времени. Кроме того, алгоритм решения задачи хорошо распараллеливается, и применение параллельных структур позволит решать задачи видимости еще быстрее.

Анализ временных показателей различных методов решения задачи видимости показал, что время решения с помощью разработанного метода меньше чем у существующих методов. Уже при количестве заслонок 500 единиц, время решения примерно в 10 раз меньше, чем у существующих методов. Также анализ показал, что время решения с помощью нового метода значительно медленнее растёт с увеличением количества заслонок, по сравнению с показателями существующих методов, что подтверждает оценку времени работы нового метода 0(N2logN), полученную теоретически.

Заключение

1. В результате исследования разработан новый метод решения задачи видимости, скорость работы которого не зависит от размерности объектного пространства, а зависит только от суммарной размерности площадок, между которыми нужно рассчитать видимость.

2. На основе метода построен алгоритм решения задачи видимости между двумя площадками-отрезками на плоскости и в трёхмерном пространстве, который позволяет найти все множество взаимовидимых пар точек целевых площадок за время 0(N2logN).

3. Для решения задач видимости, возникающих при сканировании земной поверхности, разработана структура хранения информации о цифровой карте местности, и алгоритм для эффективной выборки из нее информации о заслонках.

4. Разработан пакет программ для определения видимости между участками дорог и отрезками траектории самолёта-носителя РЛС БО использующий новый метод определения видимости.

1. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. М. : Издательский дом "Вильяме", 2000. - 384 е.: ил.

2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Лаборатория Базовых Знаний, 2000 г. - 624 е.: ил.

3. Вартанесян В.А. Радиоэлектронная разведка. М.: Воениздат, 1991. - 254 е.: ил.

4. Вельтмандер П.В. Машинная графика. Вводный курс: Уч. пос. Новосиб. ун-т. Новосибирск, 1997. - 123 е., ил.

5. Вендик О.Г. Фазированная антенная решётка глаза радиотехнической системы // Соросовский образовательный журнал. - 1997. - № 2. - с. 115120.

6. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. М.: Радио и связь, 1994.-224 с.

7. Козлов А.И. Радиолокация. Физические основы и проблемы // Соросовский образовательный журнал. 1996. - № 5. - с. 70-78.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 е., 263 ил.

9. Котов И.И. Алгоритмы машинной графики. М.: Машиностроение, 1977. -231 с.

10. Ю.Кузьмин С.З., Основы проектирования систем цифровой обработки радиолокационной информации. -М.: Радио и связь, 1986.

11. Ласло М. Вычислительная геометрия и компьютерная графика на С++.: Пер. с англ. М.: "Издательство БИНОМ", 1997. - 304 е.: ил.

12. Павлидис У. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1988.

13. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М. Мир, 1989. - 478 с.

14. Реутов А.П., Михайлов Б.А., Кондратенко Г.С., Бойко Б.В. Радиолокационные станции бокового обзора. М.: Советское радио, 1970. -360 с.

15. Соколенко П. Программирование SVGA-графики для IBM. СПб:ВНУ, 2001,- 432 с.

16. Тихомиров Ю. Программирование трехмерной графики. СПб:ВНУ, 1998. -256 с.

17. П.Финкельштейн М.И. Основы радиолокации. М: Радио и связь, 1983.

18. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистичные изображения. М.: ДИАЛОГ-МИФИ, 1998. - 288 с.

19. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели.- М.: ДИАЛОГ-МИФИ, 2000. 464 с.

20. Michael Abrash. Inside quake: Visible-surface determination // Dr. Dobb's Journal of Software Tools. 1996. - No. 21. - P. 21 -41.

21. D. Avis, M. Doskas. Algorithms for High Dimensional Stabbing Problems // Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science. 1990. - Vol. 27. - P. 39-48.

22. David Avis, J. M. Robert, R. Wenger. Lower Bounds for Line Stabbing // Information Processing Letters. 1989. - Vol. 33, No. 2. - P. 59-62.

23. D. Avis, R. Wenger. Polyhedral Line Transversals in Space // Discrete and Computational Geometry. 1998. - Vol. 3. - P. 257-265.

24. Marshall W. Bern, David P. Dobkin, David Eppstein, Robert L. Grossman. Visibility with a Moving Point of View // Algorithmica. 1994. - Vol. 11, No. 4.- P. 360-378.

25. Jiri Bittner. Global Visibility // In Proceedings of the CESCG '97. 1997. - P. 105-111.

26. J. Bittner, V. Havran, P. Slavik. Hierarchical visibility culling with occlusion trees // In Proceedings of Computer Graphics International '98 / IEEE Computer Society. Los Alamitos, California, 1998. - P. 207-219.

27. M. Cazzanti, L. De Floriani, G. Nagy, E. Puppo. Visibility Computation on a Triangulated Terrain // Progress in Image Analysis and Processing II / World Scientific Publishing. Singapore, 1991. - P. 721-728.

28. B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, J. Stolfi. Lines in space: combinatorics and algorithms // Algorithmica. 1996. - Vol. 15, No. 5. - P. 428447.

29. B. Chazelle, L. Guibas. Visibility and intersection problems in plane geometry // Discrete and Computational Geometry. 1989. - Vol. 4. - P. 551-581.

30. Norman Chin, Steven Feiner. Fast object-precision shadow generation for area light sources using BSP trees // Computer Graphics (1992 Symposium on Interactive 3D Graphics) . 1992. - Vol. 25, No. 2. - P. 21-30.

31. Norman Chin, Steven Feiner. Near Real-Time Shadow Generation Using BSP Trees // Computer Graphics (SIGGRAPH '89 Proceedings). 1989. - Vol. 23, No. 3.-P. 99-106.

32. Franklin S. Cho, David Forsyth. Interactive ray tracing with the visibility complex // Computers and Graphics. 1999. - Vol. 23, No. 5. - P. 703-717.

33. Y. Chrysanthou, M. Slater. Computing dynamic changes to BSP trees. Computer Graphics Forum (EUROGRAPHICS '92 Proceedings) / Eurographics Association. -Cambridge, 1992.-Vol. 11, No. 3.-P. 321-332.

34. Y. Chrysanthou, Daniel Cohen-Or, Dani Lischinski. Fast Approximate Quantitative Visibility for Complex Scenes // Proceedings of the Conference on Computer Graphics International 1998 / IEEE Computer Society. Los Alamitos, California, 1998.-P. 220-227.

35. Y. Chrysanthou, M. Slater. Shadow Volume BSP Trees for Computation of Shadows in Dynamic Scenes // Proceedings of the ACM Symposium on Interactive 3D Graphics / ACM SIGGRAPH. Monterey, California, 1995. - P. 45-49.

36. D. Cohen-Or, G. Fibich, D. Halperin, E. Zadicario. Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes //

37. Computer Graphics Forum / Eurographics Association. 1998. - Vol. 17, No. 3. -P. 243-253.

38. D. Cohen-Or, A. Shaked. Visibility and Dead-Zones in Digital Terrain Maps // Computer Graphics Forum / Eurographics Association. Maastricht, Netherlands, 1995.-Vol. 14, No. 3. - P. 171-180.

39. Richard Cole, Micha Sharir. Visibility Problems for Polyhedral Terrains // Journal of Symbolic Computation. 1989. - Vol. 7, No. 1. - P. 11 -30.

40. Satyan Coorg, Seth J. Teller. Real-Time Occlusion Culling for Models with Large Occluders // Proceedings of the Symposium on Interactive 3D Graphics. ACM Press. - New York, 1997. - P. 83-90.

41. Satyan Coorg, Seth J. Teller. Temporally Coherent Conservative Visibility // Computational Geometry. 1999. - Vol. 12, No. 1-2. - P. 105-124.

42. L. De Floriani, P. Magillo. Algorithms for Visibility Computation on Digital Terrain Models // Proceedings ACM Symposium on Applied Computing'93 / ACM Press. Indianapolis, 1993. - P. 380-387.

43. L. De Floriani, P. Magillo. Computing Visibility Maps on a Digital Terrain Model // Lecture Notes in Computer Science. 1993. - Vol. 716. - P. 248-269.

44. L. De Floriani, P. Magillo. Intervisibility on Terrains // Geographic Information Systems: Principles, Techniques, Managament and Applications. 1999. -Vol. 38.-P. 543-556.

45. L. De Floriani, P. Magillo. Visibility Algorithms on Triangulated Digital Terrain Models // International Journal of Geographic Information Systems. London, 1994.-Vol. 8, No. 1,P. 13-41.

46. L. De Floriani, P. Magillo. Visibility computations on hierarchical triangulated terrain models//Geoinforniatica. 1997. - Vol. 1, No. 3. - P. 219-250.

47. Jeong-In Doh, Kyung-Yong Chwa. Visibility problems for orthogonal objects in two- or three-dimensions // The Visual Computer. 1988. - Vol. 4, No. 2. - P. 8497.

48. G. Drettakis, Eugene Fiume. A Fast Shadow Algorithm for Area Light Sources Using Backprojection // Computer Graphics (ACM SIGGRAPH '94 Proceedings). 1994,- Vol.28. - P. 223-230.

49. George Drettakis, Francois X. Sillion. Interactive Update of Global Illumination Using a Line-Space Hierarchy // Computer Graphics. 1997. - Vol. 31. - P. 5764.

50. Fredo Durand. 3D Visibility: Analytical Study and Applications: Ph.D. thesis. -Universite Joseph Fourier, Grenoble, France. 1999. - 305 p.

51. Fredo Durand, George Drettakis, Joelle Thollot, Claude Puech. Conservative Visibility Preprocessing Using Extended Projections // Proceedings of SIGGRAPH 2000 / ACM Press. New York, 2000. - P. 239-248.

52. Fredo Durand, George Drettakis, Claude Puech. Fast and accurate hierarchical radiosity using global visibility // ACM Transactions on Graphics / ACM Press. -New York, 1999,- Vol. 18, No. 2.-P. 128-170.

53. Fredo Durand, George Drettakis, Claude Puech. The 3D Visibility Complex: A New Approach to the Problems of Accurate Visibility // Eurographics Rendering Workshop 1996 / Eurographics. New York, 1996. - P. 245-256.

54. Fredo Durand, George Drettakis, Claude Puech. The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tools // SIGGRAPH'97 Conference Proceedings / ACM SIGGRAPH. New York, 1997. - Vol. 31. - P. 89-100.

55. H. Fuchs, Z. M. Kedem, B. F. Naylor. On visible surface generation by a priori tree structures // SIGGRAPH'80 Proceedings/ ACM Press. Seattle, Washington, 1980,-Vol. 14, No. 3. - P. 124-133.

56. H. Fuchs, Z. ML Kedem, B. F. Naylor. Predetermining visibility priority in 3-D scenes // Computer Graphics (SIGGRAPH '79 Proceedings). Chicago, Illinois, 1979. - Vol. 13,No. 3.-P. 175-181.

57. Sherif Ghali, A. J. Stewart. Incremental update of the visibility map as seen by a moving viewpoint in two dimensions // Computer Animation and Simulation '96. -New York, 1996.-P. 3-13.

58. S. K. Ghosh, D. M. Mount. An output sensitive algorithm for computing visibility graphs // SIAM Journal on Computing. 1991. - Vol. 20, No. 5.-P. 888-910.

59. S. K. Ghosh, J. W. Burdick. Understanding discrete visibility and related approximation algorithms // Proceedings of the Ninth Canadian Conference on Computational Geometry. 1997. - P. 106-111.

60. S. Gottschalk, M. Lin, D. Manocha. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. // SIGGRAPH 96 Conference Proceedings / ACM SIGGRAPH. 1996,-Vol. 30. - P. 171-180.

61. D. Halperin, M. Sharir. New bounds for lower envelopes in three dimensions, with applications to visibility in terrains // Discrete and Computational Geometry. -1994,- Vol. 12.-P. 313-326.

62. J. Hershberger. An optimal visibility graph algorithm for triangulated simple polygon// Algorithmica. 1989. -Vol. 4. - P. 141-155.

63. Hinkenjann, H. Muller. Determining Visibility between Extended Objects // Proceedings of the Conference on Computer Graphics International 1998 / IEEE Computer Society. Los Alamitos, California, 1998. - P. 23-33.

64. C. Hornung. A Method for Solving the Visibility Problem // IEEE Computer Graphics & Applications. 1984,- Vol. 4, No. 7. - P. 26-33.

65. D. T. Lee, A. K. Lin. Computing the Visibility Polygon from an Edge // Computer Vision, Graphics and Image Processing. 1986. - Vol. 34, No. 1.- P. 1-19.

66. P. Magillo, L. De Floriani, E. Bruzzone. Updating Visibility Information on Multiresolution Terrain Models // Lecture Notes in Computer Science. 1995. -Vol. 988.-P. 279-296.

67. Dinesh Manocha, James Demmel. Algorithms for Intersecting Parametric and Algebraic Curves I: Simple Intersections // ACM Transactions on Graphics. -1994,-Vol. 13, No. 1,- P. 73-99.

68. K. Mulmuley. A fast planar partition algorithm II // Proceedings of the 5th Annual Symposium on Computational Geometry / ACM Press. 1989. - P. 33-43.

69. G. Nagy. Terrain visibility // Computers and Graphics. 1994. - Vol. 18, No. 6. -P. 763-773.

70. Bruce F. Naylor. Constructing good partition trees// In Proceedings of Graphics Interface '93/ Canadian Information Processing Society. Toronto, Ontario, Canada, 1993.-P. 181-191.

71. Karel Nechvile, Petr Tobola. Dynamic Visibility in the Plane // 15th Spring Conference on Computer Graphics. 1999. - P. 187-194.

72. J. O'Rourke. Open problems in the combinatorics of visibility and illumination// in Advances in Discrete and Computational Geometry / American Mathematical Society. Providence, 1998. - P. 237-243.

73. Rachel Orti, Stephane Riviere, Fredo Durand, Claude Puech. Radiosity for Dynamic Scenes in Flatland with the Visibility Complex // Computer Graphics Forum / Eurographics Association. Grenoble, France, 1996. Vol. 15, No. 3. - P. 237-248.

74. M. S. Paterson, F. F. Yao. Binary Partitions with Applications to Hidden-Surface Removal and Solid Modeling // Proceedings of ACM on Computational Geometry. -1989. P. 23-32.

75. M. Pellegrini, P. Shor. Finding stabbing lines in 3-space // Discrete & Computational Geometry. 1992. - No. 8. - P. 191 -208.

76. M. Pellegrini. Lower bounds on stabbing lines in 3-space // CGTA: Computational Geometry: Theory and Applications. 1993. - No. 3. - P. 53-58.

77. M. Pellegrini. On Lines Missing Polyhedral Sets in 3-Space. Proceedings of the 9th Annual Symposium on Computational Geometry / ACM Press. San Diego, 1993.-P. 19-28.

78. M. Pellegrini. Stabbing and Ray Shooting in 3 Dimensional Space // Proceedings of the Sixth Annual Symposium on Computational Geometry / ACM Press. -Berkeley, 1990.-P. 177-186.

79. Harry Plantinga. An Algorithm for Finding the Weakly Visible Faces from a Polygon in 3D // In Proceedings of Fourth Canadian Conference on Computational Geometry. 1992, P. 45-51.

80. Harry Plantinga. Conservative visibility preprocessing for efficient walkthroughs of 3D scenes // In Proceedings of Graphics Interface '93 / Canadian Information Processing Society. Toronto, Ontario, Canada, 1993. - P. 166-173.

81. H. Plantinga, C. R. Dyer. Visibility, occlusion, and the aspect graph // International Journal of Computer Vision. Netherlands, 1990. - Vol. 5, No. 2. -P. 137-160.

82. M. Pocchiola, G. Vegter. Computing the visibility graph via pseudo-triangulations // Proceedings of the 11th Annual Symposium on Computational Geometry / ACM Press. -New York, 1995.-P. 248-257.

83. M. Pocchiola, G. Vegter. The visibility complex // Proceedings of the 9th Annual Symposium on Computational Geometry / ACM Press. San Diego, 1993. - P. 328-337.

84. S. Riviere. Dynamic visibility in polygonal scenes with the visibility complex// In Proceedings of the 13th Annual ACM Symposium on Computational Geometry / ACM Press. New York, 1997.-P. 421-423.

85. S. Riviere. Visibility computations in 2D polygonal scenes: Ph.D. thesis. -Universite Joseph Fourier, Grenoble, France. 1997. - 143 p.

86. S. Riviere. Walking in the visibility complex with applications to visibility polygons and dynamic visibility // In 9th Canadian Conference on Computational Geometry. 1997. - P. 147-152.

87. Claudio Sansoni. Visual analysis: a new probabilistic technique to determine landscape visibility // Computer-aided Design / Elsevier Science. 1996. - Vol. 28, No. 4. - P. 289-299.

88. Carlos Saona-Vazquez, Isabel Navazo, Pere Brunet. The visibility octree. A data structure for 3D navigation // Computers & Graphics. 1999. - Vol. 23, No. 5. -P. 635-643.

89. D. Schmalstieg, R. F. Tobler. Exploiting Coherence in 2.5-D Visibility Computation // Computers & Graphics/ Pergamon Press / Elsevier Science. -1997.-Vol. 21, No. 1,- P. 121-123.

90. Cyril Soler, Francois X. Sillion. Fast calculation of soft shadow textures using convolution // SIGGRAPH 98 Conference Proceedings / ACM SIGGRAPH. -New York, 1998.-P. 321-332.

91. James Stewart, Sherif Ghali. Fast Computation of Shadow Boundaries Using Spatial Coherence and Backprojections // Computer Graphics / ACM SIGGRAPH, ACM Press Orlando, Florida, 1994. - Vol. 28. - P. 231-238.

92. J. Stewart. Hierarchical visibility in terrains // Eurographics Rendering Workshop 1997 / Eurographics. New York, 1997. - P. 217-228.

93. Seth J. Teller. Computing the Antipenumbra of an Area Light Source // Computer Graphics (Proceedings of SIGGRAPH 92). Chicago, Illinois, 1992. - Vol. 26, No. 2. - P. 139-148.

94. Seth J. Teller, Kavita Bala, Julie Dorsey. Conservative Radiance Interpolants for Ray Tracing // Eurographics Rendering Workshop 1996 / Eurographics. New York, 1996.-P. 257-268.

95. Seth J. Teller, Michael Hohmeyer. Determining the Lines Through Four Lines // Journal of Graphics Tools. 1999. - Vol. 4, No. 3. - P. 11-22.

96. Seth J. Teller, Pat Hanrahan. Global visibility algorithms for illumination computations // Proceedings of SIGGRAPH 93. Anaheim, California, 1993. - P. 239-246.

97. Seth J. Teller, Michael Hohmeyer. Stabbing oriented convex polygons inлrandomized 0(N ) time // Jerusalem Combinatorics '93: An International Conference in Combinatorics. Jerusalem, Israel, 1993. - P. 311-318.

98. Seth J. Teller. Visibility Computations in Densely Occluded Polyhedral Environments: Ph.D Thesis. University of California at Berkeley. - 1992. - 151 P

99. Seth J. Teller, Carlo H. Sequin. Visibility Preprocessing For Interactive Walkthroughs // SIGGRAPH'91 Proceedings. Las Vegas, Nevada, 1991. - Vol. 25, No. 4.-P. 61-69.

100. W. C. Thibault, B. F. Naylor. Set operations on polyhedra using binary space partitioning trees // In Proceedings of SIGGRAPH '87. Anaheim, California, 1987,-Vol. 21, No. 4.-P. 153-162.

101. Yigang Wang, Hujun Bao, Qunsheng Peng. Accelerated Walkthroughs of Virtual Environments Based on Visibility Preprocessing and Simplification // Computer Graphics Forum / Eurographics Association. 1998. - Vol. 17, No. 3. -P. 187-194.

102. Alan Watt 3D Computer Graphics. Third Edition. - Addison Wesley, 2000. - 592 p.

103. R. Yagel, W. Ray. Visibility computation for efficient walkthrough complex environments // Presence. 1995. - Vol. 5, No. 1. - P. 45-60.

104. ГосНИИ авиационных систем // www.gosniias.msk.ru. (20.01.2002).

105. Председатель комиссии: «/С Негинский Ю. М.

106. Члены комиссии: Рожнов М. А.

107. Рашевич Л. Н. Игнатов В.Е.