«Остров не считается - эта клякса нечаянно»
Л. Кассиль «Кондуит и Швамбрания»
Уже очень давно создана и работает программа, отображающая космонавтам движение МКС на карте земной поверхности.
МКС, конечно, двигается вовсе не по земной поверхности, а по орбите. Но если соединить станцию и центр Земли прямой, то точка пересечения этой прямой с земной поверхностью будет являться т.н. «подспутниковой» точкой. Совокупность этих точек составляет «трассу» полета. Другими словами, трасса – это проекция на земную поверхность плоскости орбиты. Если земная поверхность представлена схематичным изображением континентов в цилиндрической проекции, то трасса МКС (наклонение ее орбиты 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 не позволило бы найти приемлемое с точки зрения быстродействия решение. А буквально ничтожная доработка самого нижнего уровня библиотеки сразу позволила получить простое и быстрое решение, хотя и, так сказать, «нечестным» способом.