Методы и средства определения видимости при сканировании земной поверхности тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Польский, Сергей Владимирович

• Польский, Сергей Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Польский, Сергей Владимирович

Содержание.

Введение.

Глава 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. Разработан пакет программ для определения видимости между участками дорог и отрезками траектории самолёта-носителя РЛС БО использующий новый метод определения видимости.

Список литературы диссертационного исследования кандидат технических наук Польский, Сергей Владимирович, 2004 год

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. Рашевич Л. Н. Игнатов В.Е.