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

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

Поэтому решением проблемы должна быть автоматическая
система, которая будет:

• Хранить комплексную информацию о здании;
• самостоятельно её анализировать;
• снабжать пользователя по запросу минимумом необходимых
  данных, полученных в результате анализа.

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

GPS (Global Positioning System) — спутниковая система навигации, обеспечивающая измерение расстояния, времени и определяющая местоположение во всемирной системе координат WSG 84. Система позволяет определить положение и скорость объектов практически при любой погоде, практически во всех областях земного шара и околоземном
пространстве, за исключением некоторых приполярных областей[1].

Система берёт свое начало в 50-х годах двадцатого века, когда в ходе наблюдения за советским спутником выяснилась интересная особенность: из-за эффекта Доплера частота сигнала увеличивается при приближении спутника и уменьшается при его удалении. Таким образом, точно зная своё положение на Земле, можно было точно определить положение и скорость спутника в пространстве. Обратное тоже верно.

Для определения местоположения объекта достаточно принять сигнал от трёх спутников системы находящихся на орбите и, соответственно, определить расстояния до них. Известны точные координаты трёх спутников, и расстояния до них. Данной информации достаточно для определения точных координат. Точность определения местоположения составляет около 6 м. Однако, в некоторых  странах имеются наземные системы дифференциальной коррекции (они снабжают приёмники дополнительной информацией об особенностях приёма сигнала в данной местности), позволяющие сократить погрешность до 1-2 метра.  С выведением на орбиту спутников нового стандарта, которое запланировано в ближайшем будущем, погрешность позиционирования должна уменьшиться до 60-90 см.

Недостатками системы является невозможность определения местоположения в некоторых условиях, среди которых: глубины железобетонных зданий, подвалы, тоннели. Иногда мешают помехи от наземных радиоисточников. Самый большой недостаток системы — её полная зависимость от министерства обороны США.

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

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

Поэтому на практике используется модификация алгоритма Дейкстры — алгоритм А*. Суть алгоритма проста: в качестве следующего пункта (вершина графа) выбирается тот, который имеет наименьшую оценку: сумма пройденного расстояния и предположительного расстояния до конечного пункта. Последнее принимается как расстояние до пункта по прямой, причём это специфика именно данной системы навигации. Сам алгоритм А* не указывает, какой именно метод предположительной оценки должен использоваться. Поэтому для GPS недостаточно описания местности в виде взвешенного графа: необходима информация о координатах каждого возможного пункта.

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

Глобальная навигационная спутниковая система (ГЛОНАСС) – советская и российская система спутниковой навигации. Инициатором создания является Министерство Обороны СССР. Вторая из действующих спутниковых систем навигации[2].

Предоставляет возможности для ориентации на суше, в воздухе и в море. Также, как и GPS, предоставляет различные возможности для различных пользователей. Так, спутники излучают сигналы двух типов: открытые обычной точности и защищённые повышенной точности. Последние доступны только авторизованным пользователям, к числу которых принадлежит и Министерство Обороны РФ. Открытые сигналы имеют право принимать и использовать в своих целях любые пользователи по всему земному шару на безвозмездной основе (на основании указа президента РФ).

Физические основы работы системы аналогичны таковым в GPS, однако аппаратная реализация имеет отличия. Так, вращение спутников ГЛОНАСС вокруг Земли не синхронизировано с вращением последней вокруг собственной оси. Это позволило расположить спутники на более устойчивой орбите, поэтому спутники не нуждаются в корректировке орбиты в течении срока службы (который, однако, заметно короче).

Приборы для использования ГЛОНАСС в обиходе появились относительно недавно. Первым из таковых стал профессиональный прибор Ashtech GG24, который был создан в 1995 году и рассчитан на две системы навигации. Спутниковый навигатор Glospace – первый потребительский навигационный прибор, поддерживавший навигацию с помощью ГЛОНАСС, был выпущен в продажу в 2007 году. Массово не изготовлялся, и потому не был доступен широкому кругу потребителей. Эта проблема была решена лишь в 2011 году, когда на рынке стали появляться навигационные приборы фирм Explay и Lexand. По мнениям аналитиков рынка навигационных систем, сейчас нет приборов, использующих только ГЛОНАСС – либо две системы используются одновременно, либо
только GPS. Причём, использование одновременно двух систем, позволяет повысить точность позиционирования.

Точность позиционирования системы колеблется, но в среднем наблюдается ухудшение точности по сравнению с GPS на 1-2 метра. Так, в условиях, когда погрешность GPS составляет 2-4 метра, ГЛОНАСС даёт погрешность в 3-6 метров. Совместное использование систем даёт погрешность не более 2-3 метра. В планах точность позиционирования для ГЛОНАСС составит 1.4 метра в 2015 г., 0.6 метра в 2020
году с дальнейшим уменьшением погрешности до 10 см. По некоторым наблюдениям, ГЛОНАСС обеспечивает большую точность навигации в северных широтах, причиной чему служит соответствующее расположение орбит спутников. Также, для повышения
точности позиционирования используются станции дифференциальной коррекции. В России функционируют 14 станций, и две за рубежом – в Антарктиде (станция “Беллинсгаузен”) и в Бразилии. Планируется постройка ещё большего числа станций, как в России, так и за рубежом.

С момента 30 марта 2010 года и по текущий момент времени навигационная система ГЛОНАСС имеет следующие показатели доступности хорошей и отличной точности позиционирования:

• Для всей России, кроме Владивостока: в течении 99% суток;
• для Владивостока: 95%;
• в среднем по миру: 92%;
• Худший показатель по миру: 80%.

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

Навигационная система Бэйдоу – спутниковая система навигации, предназначенная для использования только на территории КНР. Запущена в коммерческое использование 27 декабря 2012 года, однако выход системы на полную мощность запланирован на 2020 год. Окончательному запуску системы препятствуют также неясности по вопросу урегулирования частотных диапазонов.

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

Galileo (Галилео) – совместный проект Евросоюза и Европейского космического агентства по созданию спутниковой системы навигации. В настоящий момент находится на стадии формирования спутниковой группы. Полный запуск ожидается в 2014-2016 гг.
Имеются проблемы с навигационными приборами, совместимыми с данной системой: их количество на данный момент невелико. Система создаётся для решения геодезических и навигационных задач.

Данная система имеет серьёзное преимущество перед своими главными конкурентами (ГЛОНАСС и GPS): Галилео не зависит ни от какого военного ведомства. Однако, это не означает, что система не будет использоваться странами Европы в военных целях. Предполагается, что точность навигации составит до 30 см в районе низких широт, и до 1 м в полярных районах. Обеспечена данная точность атомными часами на спутниках системы и их более высокой орбитой, по сравнению со спутниками GPS.

Система будет предоставлять следующие службы:

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

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

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

- Правительственная служба – передача высокоточного и особо защищённого сигнала. Круг пользователей строго контролируется. Предназначен для использования спецслужбами, военными и антикризисными структурами. Имеется защита от симуляции сигнала.

- Поисково-спасательная служба – сервис, физические основы которого отличаются от таковых в других сервисов: обычно, пользователь по сигналам от спутников определяет их местоположение относительно себя, а поскольку положение спутников известно, то возможно рассчитать своё местоположение. В данной же службе, приёмом сигнала (в данном случае, это сигнал бедствия) занимаются спутники с целью определения местоположения источника. Данные о местоположении в дальнейшем будут учитываться для организации спасательной операции.

Google Maps (Карты Google) — набор приложений, построенных на основе бесплатного картографического сервиса, предоставляемого компанией Google. Сервис представляет собой карту и спутниковые снимки Земли, Луны и Марса. С ним интегрирован бизнес-справочник и карта автомобильных дорог, с поиском маршрутов.

Набор спутников снимков, предоставляемый данным сервисом, очень широк: в наличии имеются снимки высокого разрешения практически всех урбанизированных областей земного шара, хотя некоторые из них намеренно испорчены (замылены) из соображений безопасности. К таким областям относятся Капитолий США, Белый дом и Военно-морская обсерватория США. Однако, вопреки распространённому мнению, снимки Зоны 51 и пустыни Невада не испорчены. Снимки слабо заселённых территорий выполнены в невысоком разрешении.

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

Для городов с подготовленными картами сервис может предоставить услуги по проложению маршрута для широкого круга пользователей: возможно проложение маршрута для автомобилистов, пользователей общественного транспорта и пешеходов — для каждой из этих групп применяется своя методика. Какие именно алгоритмы построения оптимального маршрута не уточняется. Однако, картографический сервис предоставляет открытый API, поэтому сейчас имеется направление по созданию систем построения
кратчайших маршрутов на основе Google Maps.

Навигация внутри зданий – недавнее нововведение в данном сервисе, тем более, оно не является основной функцией. Применяемые в сервисе методы построения оптимального маршрута работают эффективно для открытой местности (в т.ч. урбанизированной территории). Чего нельзя сказать о новой возможности. Также, в этом сервисе не предоставляются трёхмерные карты. Поэтому, эффективность навигации внутри зданий посредством Google Maps – вопрос открытый.

Экспериментальная технология NAVVIS позволяет разрешить проблему навигации внутри зданий. Разработана в Мюнхенском техническом университете, основана на множественной съёмке фотографий помещения и сканирования его лазерными приборами. По полученным данным возможно построить 3d модель помещений.

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

Уральские учёные совместно с израильским университетом «Ариэль», которая позволяет решить одну из главных проблем GPS – невозможность точного определения местоположения внутри зданий. Данная система скоро станет доступна для пользователей мобильных устройств на платформе Android, несколько позже будет выпущена версия для устройств BlackBerry, Apple и Nokia. В лабораторных условиях система определяет положение пользователя с точностью до 3 см. Для реальных условий заявлена точность в пределах 1 м. Определение местоположения определяется относительно пунктов, связанных с клиентом по сети Wi-Fi. В будущем возможно применения для этих целей сетей 4G LTE. Помимо определения местоположения, разработанная система предоставляет возможность построения маршрута до указанного пункта. Среди достоинств системы отмечается высокая скорость формирования навигационных карт – около 60 мин на один объект.

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

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

• Для пользователя будет облегчена задача собственного позиционирования: бегло просмотрев модель здания, он сможет узнать место, в котором находится. Конечно, в удобстве данный подход уступает другим методам позиционирования, но требует минимум аппаратного обеспечения (точки доступа Wi-Fi, шагомеры, инерциальные и прочие сенсоры не требуются);
• указание пути возможно выполнить несколькими способами, из которых пользователь сможет выбрать наиболее удобный для себя. Плоские карты указывают путь единственным способом: в виде траектории, которой приходится следовать буквально. Запомнить путь в таком виде и воспроизвести его мысленно будет затруднительно.

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

Обзор алгоритмов построения оптимального маршрута

Алгоритм Дейкстры — алгоритм на графах, изобретён нидерландским учёным Э. Дейкстрой в 1959 году. С его помощью можно найти кратчайшее расстояние от одной вершины графа до любой другой. Неприменим к графам с ребрами, имеющим отрицательный вес.

Формальное определение задачи, которую решает данный алгоритм:

Дан взвешенный (ребрам которого сопоставлено значение — вес ребра) ориентированный (ребра имеют направление) граф $ G(V, E) $ без петель и дуг отрицательного веса. Необходимо найти кратчайший путь от заданной вершины a  до всех остальных вершин графа G.

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

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

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

Алгоритм Беллмана-Форда – аналогично, алгоритм основанный на графах. Допускает отрицательный вес рёбер. Постановка задачи у алгоритма такая же, как и у алгоритма Дейкстры.

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

Результат работы алгоритма удобно представить в виде массива, размер которого совпадает с количеством вершин графа. Обозначим этот массив r. Первоначальное состояние массива: r[s] = 0, r[i] = ∞, где s – начальная точка, i<>s. На каждом шаге алгоритма производится проверка всех рёбер графа с целью уменьшения r[i] (i – номер конечной вершины проверяемого ребра). Если оказывается, что r[i] ≤ r[j] + N (j – начало рассматриваемого ребра, N – его вес), то r[i] приобретает новое, меньшее значение. Процесс продолжается до тех пор, пока в ходе перебора всех ребёр происходит хотя бы одна такая замена. Если в ходе очередного обхода не удаётся произвести улучшение, работа алгоритма прекращается. Именно поэтому алгоритм не работает при наличии отрицательных циклов: тогда алгоритм будет вечно производить улучшения и никогда не остановится.

Алгоритм Левита – алгоритм поиска на графах, осуществляющий поиск кратчайшего расстояния от заданной вершины до всех остальных, аналогично алгоритмам Дейкстры и Беллмана-Форда. Работает на графах с рёбрами отрицательного веса.

Работа данного алгоритма предполагает разбиение всего множества вершин на подмножества:

• M0 – множество вершин, расстояние до которых уже вычислено. Однако это не означает, что оно не может быть пересчитано;
• M1 – множество вершин, для которых вычисление расстояния производится в данный момент (причём это множество имеет структуру очереди);
• M2 – множество вершин, расстояние до которых ещё не вычислено.

Изначально, все вершины, кроме начальной, помещаются во множество M2 (начальная помещается в M1). В ходе работы алгоритма перебираются вершины из очереди. Каждая выбранная вершина помещается во множество M0 и просматриваются все соседние по отношению к ней вершины. Для таковых возможны ситуации:

• Это вершина из множества M2. Тогда она переносится во множество M1 в конец очереди, вычислив расстояние до этой вершины как сумму длины рассматриваемого ребра и пройденного до этого расстояния;
• это вершина из множества M1. Тогда происходит попытка улучшить расстояние до этой вершины: из двух значений (текущее расстояние до вершины и сумма пройденного пути с длиной ребра) выбирается меньшее. Сама вершина не меняет положения в
  очереди;
• если вершина принадлежит множеству M0, то производим для неё улучшение (если возможно), и помещаем её в начало очереди M1.

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

На фазе с номером k разрешается проложить путь между двумя вершинами i и j через вершины 1..k. Поэтому изначально эта матрица совпадает с матрицей смежности графа, причём расстояние между несвязанными вершинами обозначается как бесконечность, а расстояние от любой вершины до самой себя равно 0.

При переходе на новую фазу с номером k во множество допустимых вершин добавляется новая, с номером k. Для каждой клетки результирующей матрицы производится попытка улучшения: если удаётся проложить новый путь (через новую вершину), который будет короче предыдущего, то значение клетки меняется на новое. В противном случае, считается, что кратчайший путь между вершинами не лежит через вершину k. Проверка на возможность улучшения, производится простым методом: расстояния от i до k и от k до j уже посчитаны, ведь в этих маршрутах k не является промежуточной вершиной. Новая возможная длина пути – сумма этих расстояний.

Процесс завершается на фазе k=n (количество вершин). Алгоритм корректно работает в случае отрицательных весов, однако отрицательные циклы недопустимы.

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

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

Поиск по первому наилучшему совпадению лежит в основе алгоритма поиска A* (А Звезда или А Стар). Критерием выбора лучшего узла графа служит сумма пройденного пути от начальной вершины до текущей, и предположительная длина пути от текущей вершины до конечной. Последняя может определяться по разному. Рассмотрим на примере. Плоское пространство можно разметить сеткой, начальной и конечной точке движения можно сопоставить узлы этой сетки. Тогда, это пространство будет описываться графом, вершины которого соответствуют узлам этой сетки. Путь от любой вершины до конечной принимается как движение сначала
строго по вертикали, потом строго по горизонтали (или наоборот), несмотря на то, что этот путь может оказаться неоптимальным или невозможным из-за препятствий на моделируемой местности.

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

• Длина построенного маршрута;
• время работы;
• требования к исходным данным;
• характер выходных данных.

Первую характеристику (длину маршрута) достоверно можно оценить только экспериментальным методом. Остальные же показатели можно оценить заранее, тем или иным методом. Время работы будет отличаться для разных аппаратно-программных платформ, поэтому вместо него следует оценить зависимость времени работы алгоритма от количества вершин в графе (т.н. асимптотика). Например, асимптотика O(n^3) означает, что время работы алгоритма пропорционально кубу числа вершин n.

Таблица 1 Сравнение алгоритмов построения оптимального пути

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

Обзор методов графической визуализации

OpenGL (англ. Открытая графическая библиотека) — спецификация, определяющая независимый от языка программирования программный интерфейс (API) для написания приложений, использующих двумерную и трёхмерную компьютерную графику.

На базовом уровне, OpenGL — это спецификация, документ, который описывает предоставляемые функции и их точное поведение. Этот документ предназначен для производителей оборудования, например, графических акселераторов, для создания ими реализаций
— библиотек работающий функций, которые соответствуют описанным в документации. Иногда возникают ситуации, когда не все функции могут быть реализованы аппаратно, оборудование не позволяет, в таком случае, это должно быть сделано программно. Реализация от производителя должна пройти тесты на соответствие, в случае успеха она будет официально признана реализацией OpenGL. Данная процедура позволяет прикладным программистам эффективно использовать функции этого интерфейса независимо от оборудования, не переучиваясь при смене оборудования, и не беспокоясь об эффективности реализации: это остается за производителем оборудования.

На сегодняшний день имеются эффективные реализации OpenGL для большинства платформ: Windows, семейство Unix, в т.ч. Mac OS. Обычно, их авторы — это производители видеоадаптеров. Причём возможности последних используются очень эффективно этими реализациями.

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

• Подача примитива на вход конвейера
• Конфигурирование конвейера

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

OpenGL представляет большой интерес ввиду следующих своих достоинств:

• Независимость от языка программирования;
• кроссплатформенность — реализации OpenGL имеются практически для всех программно-аппаратных платформ;
• открытость и, как следствие, доступность и бесплатность
  средств разработки для OpenGL.

Среди недостатков можно отметить только упомянутый выше императивный подход: сложность применения при больших возможностях.

Графическая библиотека Direct3D — часть прикладного программного интерфейса DirectX, предоставляющий возможности для визуализации 3d-изображений. Создана корпорацией Microsoft, полностью доступна для операционных систем Windows (Windows 95 и выше), на других платформах работа Direct3D затруднительна. Эта библиотека позволяет задействовать аппаратное ускорение видеоадаптера (если таковое возможно), а также использовать такие возможности 3D-визуализации, как Z-буфер,
сглаживание, смешивание, MIP-текстурирование (использование одной и той же текстуры в разных масштабах), атмосферные эффекты
(туман, например), перспективная коррекция текстур.

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

Также имеется встроенный эмулятор графического адаптера (последние версии эмулятора предоставляют полный набор возможностей Direct3D). Однако на практике он используется только для отладки, т. к. он не может обеспечить достаточную производительность.

История Direct3D начинается в 1992 году, когда была основана фирма RenderMorphics, занятая разработкой API для 3d графики под названием Reality Lab. Предполагалось, что он будет использоваться в CAD-системах и в медицине. Было создано две версии этого интерфейса. В 1995 году фирма была приобретена корпорацией Microsoft, а интерфейс включён в DirectX 2.0 и DirectX 3.0.

Изначально, Direct3D включал в себя два режима работы: статический и динамический. Статический режим использует объектную модель графической сцены, которая формируется и передаётся на отрисовку. Разработчик может только формировать сцену, не меняя
параметров отображения. Ввиду такой ограниченности, статический режим не получил распространения, и после DirectX 3.0 перестал поддерживаться.

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

В версиях библиотеки с 5.0 по 9.0 она развивалась планомерно. В Direct3D 6.0  появилось поддержка процессорных расширений SSE (Intel) и 3D Now! (AMD). В версии 7.0 появился формат текстур .dds и аппаратное ускорение афинных преобразований и освещения. В восьмой версии реализовано программирование в виде вершинных и пиксельных шейдеров, что снимает с разработчиков заботу о простое оборудования. Драйвер видеоадаптера теперь сам переводит инструкции в виде шейдеров в инструкции, понятные
аппаратному обеспечению.

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

Средства создания трёхмерной графики – главный инструмент создания будущего приложения. От его выбора зависят материальные затраты на разработку системы и её работоспособность. Следует провести сравнение двух главных возможных инструментов: OpenGL и Direct3D.

Выводы. Постановка задач исследования

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

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

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

1. Комаровский Ю. А. Ухудшение точности GPS-приёмника вблизи высоких объектов // Учёные записки Комсомольского-на-Амуре Государственного технического университета. – 2012. – №1. – С. 28-35
2. Урличич Ю. М. ГЛОНАСС – Российская национальная система Состояние, перспективы развития и применения системы ГЛОНАСС // T-COMM: Телекоммуникации и транспорт. – 2008. – №2. – С. 14-18
3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание – Вильямс 2013 – С. 607-708
4. Красильникова А. Н. Информационные технологии в градостроении // Красильникова А. Н., Александрова В. О., Абрамова О. Ф. // Успехи современного естествознания. -2012. – №6.- С. 32.

Все статьи автора «dron2065»