«Остров не считается - эта клякса нечаянно»
Л. Кассиль «Кондуит и Швамбрания»
Уже очень давно создана и работает программа, отображающая космонавтам движение МКС на карте земной поверхности.
МКС, конечно, двигается вовсе не по земной поверхности, а по орбите. Но если соединить станцию и центр Земли прямой, то точка пересечения этой прямой с земной поверхностью будет являться т.н. «подспутниковой» точкой. Совокупность этих точек составляет «трассу» полета. Другими словами, трасса – это проекция на земную поверхность плоскости орбиты. Если земная поверхность представлена схематичным изображением континентов в цилиндрической проекции, то трасса МКС (наклонение ее орбиты 51,8°) отобразится кривой, напоминающей синусоиду. И где-то на этой «синусоиде» обычно красным кружочком отображается текущее положение МКС, например, вот так:
Разумеется, такая карта слишком груба, чтобы что-то разглядеть на ней. Поэтому требуется отображать движение МКС и на более подробных картах, причем для удобства «движется» именно карта, т.е. ее видимый фрагмент размером с экран, а метка станции остается неподвижной и в центре. Ниже приведены отображения одного и того же положения станции на четырех фрагментах карт разной степени подробности.
И вот, когда идет отображение положения станции и отрезка трассы на сравнительно подробных картах, возникает немного странная и даже забавная проблема.
Поскольку две трети земной поверхности покрыто океанами, то на отображаемом положении МКС часто оказывается только трасса, метка самой станции и фрагмент «сплошного» океана в виде просто синего прямоугольника. И этот синий прямоугольник вместо карты может выдаваться минутами, что бессмысленно и не информативно. А ведь при таком наклонении орбиты до 27 минут подряд можно лететь, не встречая суши.
Хотелось бы, чтобы вместо пустого синего прямоугольника автоматически отображалась бы карта более грубого масштаба, где станет видна хоть какая-нибудь суша, пусть и удаленная.
Алгоритмически эта задача решается легко: надо просто сравнить все пиксели сформированного кадра между собой. Если они все одинаковы – значит надо отображать фрагмент карты более грубого масштаба. Если на фрагменте и такой карты все пиксели одинаковы – следует отображать еще более грубую карту и т.д.
И в любой графической библиотеке есть функция типа get_pixel, которая достает цвет заданной точки кадра (построенной сцены). Беда в том, что такое извлечение и сравнение точек одного изображения будет работать слишком долго. Разумеется, не требуется проверять обязательно каждый кадр и каждый пиксель. Можно проверять, к примеру, каждый второй кадр и сетку из каждой четвертой/восьмой/шестнадцатой точки. Но все равно это очень медленно. Недопустимо медленно для решения такой, в общем-то, второстепенной задачи.
Попробуйте сами придумать алгоритм быстрой проверки одинаковости пикселей. Например, можно проверять точки только по периметру кадра, поскольку суша как бы «вплывает» в кадр через его периметр. Однако тогда неудобно отслеживать небольшие острова (что и вынесено в заголовок этой статьи), так как придется отслеживать и выход острова из кадра. А как быть в начале работы, когда остров оказался сразу в центре, кадра, а мы отслеживаем только периметр? Например, вот типичное отображение трассы рядом с атоллами в Тихом океане:
Атоллы быстро появляются в кадре и быстро же исчезают из «поля зрения». И опять вместо карты остается только одноцветная океанская поверхность, отображать которую не имеет смысла.
Дальнейшее усложнение алгоритма, основанного на get_pixel, начинает напоминать изобретение самозахлопывающейся крышки у чернильницы, чтобы предотвратить разлив чернил при ее случайном опрокидывании. А в реальности чернильницы-«непроливайки» имели простую конструкцию и прекрасно справлялись с поставленной задачей без крышек вообще. Хотелось бы и в данном случае иметь предельно простой, не требующий больших затрат времени алгоритм определения «чистого» океана.
Можно, например, просто сравнивать целиком очередной кадр с предыдущим. Ведь за время формирования очередного кадра станция должна переместиться по орбите (т.е. при отображении карта должна сдвинуться под неподвижной отметкой станции). Если кадры строго совпали – значит, это те самые пустые и не меняющиеся синие прямоугольники. При этом способе не нужно извлекать никакие цвета пикселей, а, значит, все будет существенно быстрее. Но и здесь есть недостатки. При разрешении экрана 1920х1024 число точек в кадре будет порядка трех миллионов. А с учетом трех байт RGB на точку, кадр будет занимать около 9 Мбайт в памяти. И эти 9 Мбайт нужно постоянно переписывать в памяти, чтобы запомнить для сравнения как предыдущий кадр. А затем по 9 Мбайт сравнивать между собой. И пусть в архитектуре x86 для этого есть удобные «цепочечные» команды, все равно получается многовато действий для достижения второстепенной цели. Никакого кэша не хватит.
А мы решили эту задачу «не по правилам». Вместо того чтобы играть в «шахматы», т.е. придумывать алгоритмы быстрой проверки на основе базовых методов типа get_pixel или сравнения кадров, сыграли в «чапаевцев», используя тот факт, что графическая библиотека доступна нам для исправлений на самом низком уровне.
Я уже касался темы распаковки отображения карты на лету. Это позволяет сократить объем памяти, требуемый картами, и использовать старый формат PCX, очень удобный для изображений с небольшим числом цветов и большими одноцветными площадями (т.е. рисованные карты).
Ниже приведен фрагмент на ассемблере графической библиотеки работы с PCX-изображениями и распаковкой их на лету. Это место, где непосредственно записываются RGB каждой точки распакованного изображения в образ кадра перед тем, как передать этот кадр уже процедуре Direct-X.
И достаточно к этим командам добавить лишь 4 команды (выделены зеленым), как получается автоматический счетчик отличий, который обрабатывается один раз для всей группы повторяющихся пикселей, а не для каждого отдельного пикселя. Программа верхнего уровня просто постоянно проверяет, не стал ли счетчик отличий внутри очередного кадра меньше некоторой величины (скажем, 10) и вызывает более грубую карту в этом случае. Но любой, даже самый малый островок в океане будет сразу обнаружен по возрастающему в каждом кадре счетчику отличий (по мере вхождения островка в границы кадра).
В результате время отображения карт с таким встроенным подсчетом отличий возросло не более, чем на полпроцента, что, на мой взгляд, вполне приемлемо для решения сугубо второстепенной задачи.
Готовые библиотеки с их множеством классов и методов – одна из главных движущих сил всего процесса развития ИТ. Но иногда программист оказывается в плену предлагаемых методов, не позволяющих выйти за их рамки. В данном случае, использование только «разрешенных» функций типа get_pixel или get_image не позволило бы найти приемлемое с точки зрения быстродействия решение. А буквально ничтожная доработка самого нижнего уровня библиотеки сразу позволила получить простое и быстрое решение, хотя и, так сказать, «нечестным» способом.
Комментарии (12)
BioLogIn
26.01.2023 13:05+3Прошу прощения, если я неправильно понял задачу, но если нужно определять "комфортный" для наблюдателя уровень зума карты, то зачем его считать в реальном времени по "входящим" видеопикселям?
Если известна плановая траектория станции и/или фактические координаты станции, то можно же заранее рассчитать значение зума для каждой области карты / точки траектории. В масштабах многомегабайтных изображений на каждый кадр хранение одного дополнительного килобайтного массива [время -> зум левел] не должно быть проблемой...
Dukarav Автор
26.01.2023 20:31Да, можно моделировать полет как в прошлом (по архиву орбитальных данных) так и в будущем (по прогнозу). Эта основная задача программы. И можно запоминать времена переключения карт. Но делать это придется для всех масштабов карт и для заданного размера экрана. И в среднем каждые два дня орбитальные данные уточняются. И опять моделируй все сначала. А зачем, когда сейчас и так все успевает. Без всякого гемороя с запоминанием каких-то таблиц и их проверкой потом.
adeshere
26.01.2023 13:52+4Если у обработчика есть текущие координаты центра картинки, а не только само изображение, то я бы сделал проще. Я бы заранее составил табличку, в которую записал оптимальный масштаб картинки для каждой точки земной поверхности, где может оказаться МКС. И затем периодически проверял бы текущие координаты центра картинки по этой табличке, меняя при необходимости целевой масштаб.
Прикинем грубо размер такой таблички в простейшем варианте. В самом крупном масштабе картинка примерно 2х2 градуса? Тогда точность позиционирования центра картинки достаточно взять
с шагом в 0.3 градуса
Это дает точность позиционирования примерно 1/6 картинки. При такой точности, в зависимости от разметки, в двух крайних случаях масштаб будет меняться либо когда море заняло 5/6 изображения, либо когда ближайшая суша уехала на 1/6 за край картинки. На практике можно разметить карту так, чтобы был какой-то средний вариант, который почти всегда будет менять масштаб примерно в момент выхода суши за край изображения.
При такой точности нам нужно иметь в табличке 1200 записей - по одной для каждого значения долготы. Каждая запись будет содержать список диапазонов широт, где масштаб отличается от стандартного. Например, для долготы 0 градусов этот список может выглядеть
примерно так:
[-52:+5], Max_Size ! Южная Атлантика[36.5:37.8], Medium_Size ! Средиземное мореКаждый раз, когда долгота приближается к следующему размеченному значению, лезем в эту табличку и ищем: попадает ли текущая широта в один из предопределеных диапазонов. В большинстве случаев для каждой долготы будет всего несколько диапазонов (обычно меньше 10 шт) - проверка займет пренебрежимо малое время. Дальше все просто: если данная широта "особая" (т.е. она внутри одного из диапазонов == центр карты над океаном), то запрашиваем карту в том масштабе, который указан в табличке. Если нет - то используем стандартную карту.
Да, размер таблички получится не нулевой, но это все равно
кило (а не мега) байты
Даже если делать простой массив, а не список записей переменной длины, получим 1200 записей не более 100 байт в каждой. (Понятно, что при шаге по широте 0.4 градуса значения широт легко упаковываются в байт, а масштабов вообще будет несколько штук всего. Если нужна чуть большая точность, то можно не полениться и упаковать каждый диапазон в 4 байта - например, по 14 бит на широты и 4 бита на масштаб)..
Конечно, придется сперва разметить карту и заполнить табличку. Зато в ходе такой разметки при необходимости можно подобрать свой оптимальный масштаб для каждого региона, чтобы изображение было максимально информативным.
UPD: пока я разглагольствовал, BioLogIn уже выступил с почти той же идеей. Только он предлагает индексировать не координаты, а время. Это упростит табличку, но потребует регулярно ее обновлять, так как Земля вращается и траектория не повторяется на следующих витках...
В общем, альтернативных решений хватает ;-)
Dukarav Автор
26.01.2023 20:37Я бы заранее составил табличку, в которую записал оптимальный масштаб картинки для каждой точки земной поверхности, где может оказаться МКС.
МКС оказывается над любой точкой земной поверхности от 51,8 с.ш. до 51,8 ю.ш. Поэтому гипотетические таблицы нужны очень и очень большие. И постоянные проверки. А на другой чаше весов - всего лишь 4 (прописью: четыре) ассемблерные команды, которые делают ненужными и таблицы и проверки. И работают они одинаково для всех масштабов карт и всех размеров экрана.
adeshere
27.01.2023 00:52+2Поэтому гипотетические таблицы нужны очень и очень большие.
Зачем рассуждать гипотетически? Я в своем посте привел конкретные цифры: если таблицу не оптимизировать, плюс потребовать хорошую точность, то всего нужно около 1Мб. Если оптимизировать (переменная длина записи), то можно еще раз в пять сжать, т.к. для подавляющего большинства долгот 25 диапазонов не нужно.
И постоянные проверки.
Это да. Проверять придется каждые несколько секунд. А при обычном обновлении карты разве не так? В этом смысле все баш на баш. Зато сама проверка - это не сравнение пикселей (причем довольно многих), а поиск в индексированной таблице. По количеству операций это даст выигрыш на пару порядков примерно... Но, разумеется, выигрыш не бесплатный, а ценой 1Мб памяти на табличку плюс существенное усложнение кода. Впрочем, я согласен, что если алгоритм пиксельного анализа и так работает достаточно быстро, то более быстрые алгоритмы не особо нужны.
Главное достоинство (и одновременно недостаток) моего варианта - не в скорости, а в возможности индивидуальной "ручной" донастройки оптимального масштаба карты для каждой точки земной поверхности. Если чуть-чуть повозиться с разметкой, то можно удовлетворить любое пожелание БигБосса об индивидуальной подгонке масштаба для разных зон. Например, чтобы масштаб карты не укрупнялся (в ущерб отображению контуров материка) ради одного никому не нужного микроострова посреди океана, или наоборот.
Что лучше - полностью автоматический алгоритм, который не требует (не допускает) индивидуального подхода к отдельным точкам поверхности, или алгоритм, который позволяет эксперту что-то подкрутить на свое усмотрение - это, я думаю, вопрос философский. Т.е. все зависит от ситуации, а в общем случае он однозначного правильного решения не имеет. Материал в статье хорошо подан, поэтому задачка многим понравилась и стала поводом "мозгового штурма". Но мозговой штурм тем и интересен, что генерирует множество совершенно безумных идей, большинство из которых затем отбрасывается. А иногда такая идея вполне может и вырасти во что-то полезное.
AMDmi3
27.01.2023 14:03Я бы для этой задачи взял coastlines (а возможно и другие данные) из openstretmap, посчитал бы по ним distance field и определял бы зум за один (ну или 4 если хочется плавно) лукап. В общем виде это только так и решается, потому что если в качестве подложки использовать спутник, с одной стороны вода будет неоднородной, с другой - на сплошной лес тоже неинтересно смотреть.
Mingun
На самом деле, в грубом алгоритме незачем проверять весь экран, достаточно только новые пиксели. А если еще подумать, то нужно иметь размеченную карту, чтобы просто bounding box-ы объектов сравнивать с viewport-ом, а не пиксели
alex1t
Как с языка сняли. Тоже подумал, что тут какое-то велосипедостроение излишнее
An_private
Как я понимаю, описываемая автором программа по сути это GUI к некоей серверной части, которая отдает готовые картинки в заданном формате PCX. Поэтому в эту часть у него просто нету доступа.
Для грубого поиска неголубых пикселей можно было просто использовать прореживание - то есть проверять не все пиксели, а только сетку с шагом 8, например. Это бы уменьшило требуемые ресурсы в 64 раза. Да, есть небольшая вероятность пропустить маленькие объекты, что в данной задаче совершенно несущественно.
Dukarav Автор
Не понимаю, откуда взялось впечатление о какой-то серверной и клиентской части. Вроде нигде об этом не написано. Есть только одна программа, читающая файлы карт в память и распаковывающая отображаемый фрагмент в реальном времени. Если фрагмент получился одноцветным, отображать его бессмысленно и берется фрагмент другого масштаба. Вся программа полностью доступна, поэтому исправления получились такими маленькими.
Dukarav Автор
Что имеется ввиду? Например в программе одно из семейства карт - это бесплатная TrueMarble разрешением 1 пиксель - 250 м на земле.
Всего 32 файла размером 21600х21600х24бит. Если это представить в формате BMP то потребуется 44,8 Гбайт. И чего там должно быть размечено? И сколько еще Гигов это займет?
Mingun
В простейшем случае — просто квадратики, вмещающие в себя острова, большие континенты просто покрыты пересекающимися прямоугольниками чтобы более-менее следовать береговой линии. Нам же не требуется большая точность. Можно пойти дальше, и береговую линию рисовать все же полигонами. Когда в viewport-е нет ни одного полигона с сушей, вычисляете, насколько нужно увеличить viewport, чтобы произошло пересечение хоть с одним полигоном.
Думаю, эту информацию вполне можно впихнуть в несколько сотен мегабайт.