Введение.
После прочтения статьи на сайте HowStuffWorks.com, для меня стало очевидным, что авторы статьи скорее расхваливали программу и предлагали варианты ее использования, чем действительно объясняли как (по-настоящему) работает Google Earth.
Так что я подумал, что возможно читателям будет интересно узнать правду, но с учетом существующих проблем интеллектуальной собственности (ИС).
Имейте в виду, что эти проблемы ИС реальны. Keyhole (сейчас более известный как Google Earth) уже однажды была атакована претензиями, что создатели скопировали чью-то менее развитую технологию. Иск был полностью отклонено судьей, но только после многолетней тяжбы. Это все еще более вызывает нежелание даже говорить об этой технологии. Всем известно, что любой может утверждать, что это он изобрел то, что сделали Вы, лишь потому, что «звучит похоже». Суд между Skyline и Google доказал, что «звучит похоже» не достаточно для доказательства посягательств. Но не всегда судья принимает такое решение.
Во всяком случае, вариант решения проблемы обсуждения «Как работает Google Earth» - это привязываться к фактам, которые уже были раскрыты в различных формах, а особенно в собственных патентах Google, которых сравнительно немного. Чем меньше патентов, тем лучше. Но в таком случае, большее количество патентов обеспечивало бы нам большую свободу в обсуждении технологии, что собственно и было одной из целей введения патентирования – торговля ограниченными монопольными правами, в обмен на реальную пользу для общества: раскрытие. Но я с этим не согласен…
Более заинтересованные в рассмотрении технической стороны вопроса могут захотеть прочитать эти патенты непосредственно. Предупреждаю: юристы и технологи часто склонны использовать своего рода лингвистический майонез, так называемый Патентный Английский или Painglish сокращенно. Если Вы смелы готовы к трудностям интерпретации, то вот ссылки на неторные из патентов:
1. Asynchronous Multilevel Texture Pipeline
2. Server for geospatially organized flat file data
Есть еще несколько патентов Google относящихся к данной теме. Не знаю, почему эти патенты выделены большими буквами, возможно они очень важны для исследуемой области. Надеюсь, что в будущих статьях мы остановимся на них более подробно:
3. DIGITAL MAPPING SYSTEM
4. GENERATING AND SERVING TILES IN A DIGITAL MAPPING SYSTEM
5. DETERMINING ADVERTISEMENTS USING USER INTEREST INFORMATION AND MAP-BASED LOCATION INFORMATION
6. ENTITY DISPLAY PRIORITY IN A DISTRIBUTED GEOGRAPHIC INFORMATION SYSTEM
И вот еще ссылка more informative technical paper from SGI (PDF) на статью по теме «клип-картографирования» ("clipmapping"), на которую я буду ссылаться позже. Майкл Джонс, между прочим, один из ведущих специалистов Google Earth и продолжает развивать эту технологию.
Я хочу описать вещи, как можно более приближенные к обычным техническим знаниям. Но, надо надеяться, объяснять буду так, что поймет и, надеюсь, оценит большинство людей. По крайней мере – это моя цель. Если что-то не так, можете дать мне знать.
Большое предостережение: кодировка Google Earth вероятно была переписна несколко раз, с тех пор, как я работал с Keyhole, возможно даже после того, как эти патенты были утверждены. Достаточно сказать, что последние реализации могут быть значительно изменены. Но даже мои объяснения будут столь широкими, что никто не должен использовать эту статью для чего-либо кроме удовлетворения интеллектуального любопытства и понимания.
Также отметьте: мы собираемся рассказывать в обратном порядке, начиная с момента отображения виртуальной Земли на экране, и заканчивая моментом обслуживания данных. Я верю, что это поможет объяснить суть вещей и почему другие методы не работают почти также.
Часть 1. Результат: Отображение трехмерного виртуального глобуса.
Есть два принципиальных различия между Google Maps и Google Earth. Первое – это фиксированная точка обзора (обычно – сверху вниз) в двухмерных (Google Карты) и свободная перспектива в трехмерных исполнениях (Google Earth). Второе – между графикой в реальном времени и предварительно выполненной. Эти различия уходят на задний план с развитием обоих продуктов, но важны и по сегодняшний день.
Общее – это то что оба программных продукта базируются на традиционной цифровой фотографии (в основном – на одной гигантской фотографии Земли с высоким разрешением). Велико различие в том как они предоставляют эти данные.
Рассмотрим: Окружность Земли по экватору составляет приблизительно 40 000км. Не так уж и много, подумаете Вы. Но если Вы загрузили бы всего лишь один пиксель цветных данных для каждого квадратного километра поверхности Земли, то ее изображение целиком (плоское, в проекции Меркатора) составило бы 40 000 пикселей в ширину и почти половину из этого в высоту. Это значительно больше, чем могут обработать большинство современных аппаратных средств трехмерной графики. Ведь мы говорим об изображении размером не менее 800 Мегапикселей и объемом в 2,4 Гб. Большинство персональных компьютеров на сегодняшний день не обеспечены даже 2 Гб основной памяти.
И не забудьте, что это всего лишь базовое заурядное изображение Земли километр на пиксель. Максимум, что можно будет на нем рассмотреть – так это отрезок в 2 км (спасибо Вам, Mr. Nyquist): не видно ни дорог, ни рек, ни людей, ни домов. Но для большинства городов США, Google Earth может показывать объекты размером меньше полуметра, отображать изображения с в 4 000 раз большей плотностью пикселей и занимающие в 16 млн раз больше памяти чем предыдущий вариант.
Мы говорим об изображениях, которые исчислялись бы (и исчисляются) терабайтами. Современные компьютеры не способны прорисовать изображение таких масштабов, а особенно в режиме реального времени.
И тем не менее, это происходит каждый раз, когда Вы запускаете Google Earth.
Рассмотрим: Настоящий 3D виртуальный глобус вы можете произвольно вращать и наклонять для получения любого обзора, кроме, скажем, подземелья (хотя и это возможно, если иметь необходимые данные). Во всех трехмерных глобусах существуют некоторые исходные данные, обычно реальное изображение целой земной поверхности с высоким разрешением или хотя бы частей, для которых компания купила данные. Эти данные должны быть отображены на Вашем мониторе, спроецированы на какую-нибудь виртуальную сферу, а в идеале – на небольшие трехмерные поверхности (например, треугольники), которые имитируют реальный рельеф.
Если Вы, как сетевой дизайнер, решили не давать возможности пользователям вращать и наклонять изображение Земли, поздравляю, Вы упростили техническую проблему и можете отдохнуть. Но Вы в таком случае не получили бы Google Earth.
Сейчас существует большое количество схем, позволяющих «бродить» по составляющим этой огромной структуры. Другие картографические приложения решают эту проблему своим путем, часто со значительными ограничениями и визуальными артефактами. Многие просто «режут» их огромную Землю на небольшие размеренные слои, возможно, объединенные в дерево квадрантов (quadtree), и рисуют определенную их часть на Вашем экране в любое время в двухмерном (как Google Maps) либо трехмерном режиме представления (Virtual Earth компании Microsoft).
Но способ, которым создатели Google Earth решили эту проблему, стал настоящим новшеством и достоин программного патента (хотя я, в общем-то, противник программных патентов). Чтобы объяснить этот способ, нам понадобится воссоздать несколько основных понятий. Азы теории цифровых сигналов и компьютерной графики никогда не повредят, но я надеюсь, что мое объяснение будет достаточно легким и они не будут необходимы.
Я не буду объяснять, как работает трехмерное представление данных – об этом можно прочитать где угодно. Я же собираюсь сфокусироваться на текстурном картографировании и текстурной фильтрации в частности, так как эти детали очень важны при выполнении нашей работы. Продвижение от основных понятий к более продвинутой текстурной фильтрации также поможет вам понять, почему все работает таким образом и насколько интересна эта технология в действительности. Коль Вы терпеливы, то вот ускоренный курс в текстурную фильтрацию.
Основы
Проблема вращения, искривления и масштабирования двухмерных изображений была решена давно. Наиболее распространенное решение – так называемая билинейная фильтрация (Bilinear Filtering). Она заключается в том, что для каждого нового пикселя, который Вам необходимо вычислить, берутся 4 наиболее подходящих пикселя из исходника и сочетаются вместе. «Билинейная», потому, что сначала смешиваются 2 пикселя вдоль одной оси, а потом сочетаются с двумя другими (уже смешанными) вдоль другой оси.
[«Линейная смесь», в общем очень проста в понимании: возьмите 40% цвета А, 60% цвета Б и смешайте их вместе. Соотношение 40/60 изменчиво, в зависимости от «важности» каждого составляющего, учитывая, что общее кол-во равно 100%.]
Ваши графические 3D аппаратные средства поддерживают такие функции, на сегодняшний день ПК может делать миллиарды таких вычислений в секунду. Только не спрашивайте, почему Paint в таком случае настолько медленный.
Проблему, с которой мы сталкиваемся при работе с визуальной графикой, наглядно представить очень легко. Каждый раз, когда мы пытаемся спроецировать исходные пиксели на разные (повернутые, растянутые и т.д.) выходящие пиксели, мы терпим потери в визуальной информации.
Проблема эта называется «эффектом наложения» («aliasing», алиасинг), и возникает она вследствие того, что мы преобразовали изображение в цифровой растр одним способом, с некоторой заданной частотой (разрешением), а затем мы перепреобразовываем эти цифровые данные другим способом, который не соответствует первоначальному
Теперь, когда мы говорим о выходных пикселях, не имеет значения, является ли для нас целью битовое изображение в Paint, или окно трехмерного приложения, отображающего Землю. Эффект наложения случается каждый раз когда выходные пиксели не совпадают с дискретным интервалом (частотой, разрешением) исходного изображения. И алиасинг приводит к плачевным визуальным результатам. Решение проблемы алиасинга - это более половины того, чем занимается текстурное картографирование. Остальное - это в основном управление памятью.
Таким образом, задача заключается в минимизации эффекта наложения с помощью находчивости, а также в создании хорошего дизайна. Наилучший способ – это добиться соотношения наиболее близкого к 1:1 между исходными и выходными пикселями, или хотя бы создать столько дополнительных пикселей чтобы можно было безопасно изменять выходные пиксели, минимизируя эффект наложения (метод, известный также как анти-алиасинг). Мы используем оба способа.
Рассмотрим: При изменении размеров изображений все становится лишь хуже – каждый пиксель Вашего изображения должен соответствовать сотням пикселей исходника и наоборот. Вспомним, что билинейная интерполяция выбирает лишь 4 подходящих пикселя и игнорирует остальные. Следовательно, могут исчезнуть важные пиксели а с ними тени, края, подсветка и т.д. Если такой пиксель был отобран для смешивания в одном кадре, а в последующем исчез, то вы получите неприятное «выпрыгивание пикселей» или эффект сверкания. Я уверен, вы видели что-то подобное в некоторых видеоиграх. Теперь Вы знаете причину.
Наклон изображения (или любая другая трехмерная трансформация) даже более проблематична, так как теперь у нас появились не только элементы вращения и растягивания, но и большие вариации в плотности пикселей на отображаемой поверхности. Так, в «ближней» части сцены, Ваше изображение с высоким разрешением изменится так, что пиксели покажутся размазанными, а в «дальней» части может появиться эффект сверкания, потому как простой алгоритм 2х2 билинейной интерполяции упускает некоторые визуальные детали время от времени.
Вот пример того, как обычная фильтрация приводит к плачевным результатам. Текстовые надписи трудночитаемы (почему они нанесены на изображение поверхности – это уже отдельный вопрос)
Описание более совершенного алгоритма фильтрации
Большинство пользовательских трехмерных аппаратных средств поддерживает так называемую трилинейную фильтрацию. Используя трилинейную и тесно с ней связанную технику, называемую мип-маппинг, аппаратные средства вычисляют и сохраняют серии версий вашего исходного изображения или текстурной карты с более низким разрешением. Каждая мип-карта автоматически масштабируется с коэффициентом 2, пока не достигнет изображения в 1х1 пиксель, чей цвет будет средним из всех пикселей исходника.
Так, если бы Вы снабдили Ваше аппаратное средство хорошим исходником 512х512, то оно вычислило бы и сохраняло 8 дополнительных мип-уровней для Вас (256, 128, 64, 32, 16, 8, 4,2 и 1 кв. пиксель). Если бы еще и сложили их один на другой, то такой мип-стэк выглядел бы как перевернутая пирамида, в которой каждый уровень шире предыдущего нижнего в 2 раза.
Схема мип-мап пирамиды. Для точки Х трилинейная фильтрация подбирает пиксели из 2 мип-уровней, между которыми она находится, таким образом, избегая эффекта наложения
Во время трехмерного представления с использованием мип-мапинга и трилинейной фильтрации берется каждый целевой пиксель, подбирается 2 наиболее подходящих ему мип-уровня, в сущности делается билинейная смесь в обоих, а затем уже смешивается 2 полученных результата (линейно).
Покажем на примере, как пиксель не будет иметь эффекта наложения, в случае, если исходник имеет разрешение 47,5х47,5 пикселей. Система сохраняет мощность 2-х мип-карт (16, 32, 64…). Таким образом, аппаратное средство грамотно использует уровни в 64х64 и 32х32 пикселя, ближайшие к желаемой дискретизации 47,5, и затем вычисляет билинейный результат для каждого, а затем возьмет эти 2 результата и смешает их в третий раз.
Помните: мы говорим лишь о маленьких изображениях, таких как 512х512 пикселей. Наше изображение всей Земли будет иметь разрешение в миллионы пикселей. Вы можете сказать: «Мы можем создать гигантскую мип-карту нашего всеземного изображения, с самым высоким разрешением, скажем, в один метр. В чем проблема?». А теперь представьте мип-карту, пирамиду из 26 уровней, наивысший уровень в которой будет шириной в 66 миллионов пикселей. Ни одна видеокарта не выдержит такой нагрузки. По крайней мере, в ближайшее десятилетие.
Я догадываюсь, что Virtual Earth компании Microsoft борется с такими ограничениями путем нарезки их огромной земной текстуры на много меньших определенных участков площадью, скажем, в 256 кв. пикселей, каждый из которых мип-картографируется отдельно. Такой подход будет действенным в какой-то мере, но он будет сравнительно медленным и давать такие визуальные артефакты, как размытие и выстреливание пикселей при уменьшении и увеличении изображения.
И вот последнее, что нужно знать о мип-маппинге, прежде чем перейти к главной части статьи. Представьте на секунду, что пиксели в мип-картовой пирамиде окрашены так, что целый слой окрашен в красный цвет, другой в желтый и т.д. Отображая наклонный план, мы должны получить изображение, составленное из кусков, вырезанных из разных слоев пирамиды под интересующим нас углом.
Эта характерная черта мип-маппинга обеспечила существование Google Earth.
Типичное повернутое изображение в Google Earth
То же, но с использованием цветов для отображения какие мип-уровни являются ресурсом для определенного пикселя
На первом примере показан обычный трехмерный пейзаж из Google Earth. На втором показана цветовая диаграмма, показывающая где в мип-стэке система трехмерных аппаратных средств должна найти наилучшие исходные пиксели (цвета соответствуют мип-слоям).
Более близкие к точке обзора значения берутся из слоев более высокого разрешения (красный). Чем дальше, тем более генерализованный мин-слой включается в резльтирующее изображение. Это помогает избежать сверкания и разных других проблем эффекта наложения, о которых говорилось выше.
И при этом трилинейная фильтрация графики была улучшена так называемой анизотропной фильтрацией (anisotropic filtering)(еще одно предпочтение Google Earth). Ее принцип действия основан на выше описанных методах, но при выборке значений из текстуры для каждого пикселя мы вместо базовой выборки 2х2 пикселя или вместо окружности (характерной для трилинейной фильтрации) используем неквадратный фильтр, например, эллипс. Это очень существенно для качества визуализации, так как даже при высококачественном мип-картографировании если Вы захотите наклонить текстурированный полигон на очень острый угол, системе придется выбрать изображения с более низким разрешением, чтобы избежать сверкания на узких осях. Таким образом весь полигон будет с низким разрешением, хотя это необходимо лишь в одной его части. Таким образом, если ваше аппаратное средство поддерживает анизотропную фильтрацию, используя ее Вы получаете более качественное изображение.
А теперь к сути статьи.
Мы все еще не решили, как можно мип-прокартографировать текстуру в миллион пикселей в любом измерении. Универсальная Текстура (Universal Texture), запатентованная Google Earth решает эту проблему, все так же обеспечивая высококачественную фильтрацию. Эта технология очень качественно воссоздает одну гигантскую много-терабайтную всеземную виртуальную текстуру. Надо сказать, что мы не первые, кто изобрел ее. Крис Тэннэр выдумал способ делать на персональном компьютере то, что возможно было лишь на дорогих графических суперкомпьютерах. Способ этот называется Clip Mapping (для более детальной информации просмотрите SGI’s pdf paper,).Эта технология собственно и обеспечила существование Google Earth. И моей задачей в этом проекте было заставить эту технологию работать через интернет.
Так как он собственно работает?
Вместо загрузки и прорисовки этой гигантской всеземной текстуры сразу – что не позволяют и самые последние аппаратные средства – и вместо нарезки ее на миллионы слоев, теряя в качестве и эффективности отображения, мы всего лишь используем узкую вырезку или столбец из нашей полной пирамиды мип-карты. Угол и высота этого виртуального столбца изменяется в зависимости от нашей текущей трехмерной перспективы. Таким образом, хранится вся текстура целиком, а клиенту передается только то подмножество, которое клиенту в данный момент нужно.
Чтобы определить какое подмножество изначальной здоровой мипмэп пирамиды пересылать пользователю, алгоритм сначала вычисляет куда направлен "взгляд", какой уровень детализации пользователю нужен, и изо всей мипмэп пирамиды вырезает нужный кусок и его пересылает.
Универсальная текстура – это мип-карта плюс программное обеспечение, симулирующее стек клипов, то есть, она может имитировать мип-карту во много больше уровней и с более высоким разрешением верхнего уровня, чем может установиться в любых реальных аппаратных средствах.
Примечание: все же эта диаграмма не передает мысль так точно, как бумага, угол стека клипов постоянно «вращается вокруг», чтобы как можно точнее сохранять колонну отцентрированной.
Главное отличие от базового мипмэпинга заключается в том, что перевернутая пирамида это уже не просто пирамида, теперь она значительно, значительно выше и содержит вырезанный стек текстур, названный «стек клипа», высотой от 16 до 30 уровней и выше. В принципе, это то же самое, если бы у Вас была пирамида высотой в 16-30 уровней и в миллионы и миллиарды пикселей шириной, а Вы взяли и отрезали все ее стороны которые Вам сейчас не нужны.
Просто представьте Монумент Вашингтона, перевернутый к верху дном, и Вы поймете. А чтобы было точнее, представьте, что обелиск еще и наклоняется, наподобие Пизанской башни. Все что внутри башни-обелиска – это необходимые для отображения текущих данных пиксели, а все остальное – игнорируется.
При этом каждый клип-уровень все также имеет разрешение в 2 раза больше нижележащего, как и во всех мип-картах, и все также сохраняется качество отображения данных. Но так как стек клипа ограничивается фиксированным размером окна отображения, скажем размером в 512х512 пикселей (еще одно предпочтение разработчиков Google Earth), то выходит, что каждый клип-уровень оказывается с в 2 раза большим разрешением и в два раза меньшей областью охвата, чем предыдущий. А это как раз то, что нам нужно. Мы получаем все преимущества гигантской мип-карты, как угодно отображая всего-лишь ее часть.
С другой стороны Google Earth прогрессивно и искусно загружает информацию с высоким разрешением для места, находящегося в фокусном центре Вашего обзора (обозначено красным на рисунке выше), а остальное разрешение выбирается из двух уровней того места. Когда Вы вращаете, наклоняете поверхность Земли, или прокручиваете камеру от горизонта к горизонту, Универсальная Текстура оптимально посылает только наилучшие и наиболее полезные в текущее время уровни детализации на Ваше аппаратное средство. То, что не требуется, даже не затрагивается. Это одна из причин ее крайней эффективности.
Не забудем и об эффективности этого подхода при использовании памяти. Общий объем памяти, занимаемый нашей текстурой (базовая мип-карта с шириной верхнего слоя в 512 пикселей и, скажем, 20 дополнительных клип-уровней данных) составляет чуть более 17 мегабайт. Вот с такими данными уже можно работать, и с таким подходом они обрабатывались еще в 1999 году на трехмерных аппаратных средствах с объемом памяти не более 32 Мб.
Фактически, с лишь 20 клип-уровнями (плюс 9 мип-уровней базовой пирамиды), мы получаем 229 единиц виртуальной текстуры, отвечающих за более чем 536 млн. пикселей в каждом измерении. Умножьте это на половину по вертикали, и получите изображение площадью в несколько терапикселей, или в избытке достаточно возможности отображать характеристики размером до 0,15 м(при наличии данных). И это не фактический предел. Я просто посчитал разумным выбрать 20 клип-уровней.
К счастью, на сегодняшний день Google необходимо хранить только несколько дюжин терапикселей изображений. Еще одно преимущество системы заключается в том, что для отображения не обязательно чтобы были в наличии изображения с высоким разрешением для всей поверхности Земли. Какие бы ни было граничное разрешение, какие бы ни были пробелы в данных, система будет отображать только то, что имеет. Если доступны данные с более высоким разрешением, система их выберет и отобразит. Если же нету, то система не будет отображать пробел, пустое место, а выберет данные с предыдущего уровня (с более низким разрешением). Вот почему, когда Вы приблизите какую либо местность, одна ее часть может оказаться размытой, а другая – очень детальной. Все зависит лишь от наличия данных, а не от проблем в их трехмерном отображении. Если бы данные были доступны, то Вы смогли бы увидеть и сантиметровую щепку посреди океана.
Ключ к выполнению всей этой работы заключается в том, что пока вы бродите по виртуальной Земле, система может эффективно переносить данные текстуры из кеша локального диска и системной памяти в графическую память. В буквальном смысле подзагрузка текстуры происходит без осознания Вами этого процесса. Надеюсь, теперь Вы по достоинству оцените весь труд, проделанный для того чтобы система работала так гладко.
Наконец, есть еще один факт, который должен быть упомянут. Причина того, что система проявляет некоторую асинхронность в подзагрузке изображений, в том, что непрерывная подзагрузка битов текстуры в Ваше аппаратное средство занимает некоторое незначительное совокупное время, уходящее на плавное, не дрожащее отображение трехмерной графики или на обработку ввода пользователя – не говоря уже о собственной загрузке аппаратного средства.
Чтобы достигнуть устойчивых 60 кадров в секунду в большинстве аппаратных средств, загрузка текстуры подразделена на небольшие тонкие куски, благодаря чему графические данные для любой необходимой территории подзагружаются из ресурса значительно быстрее, непосредственно перед появлением необходимости в этих данных, а в худшем случае – сразу после. Что замечательно, так это то, что системе необходимо подзагружать лишь небольшие кусочки текстуры и этим она освобождает от необходимости ожидания. Таким образом, процесс отображения данных стает плавным, а пользовательский интерфейс – как можно более подвижным. Если не удалось быстро переслать кусок нужной детализации - для начала рисуется детализация похуже, а потом быстро подгружается нужное.
На сегодняшний день, другие виртуальные глобусы также могут виртуализировать всеземную текстуру, возможно, нарезая ее на слои или даже используя огромную мощность 2-х разрешений , как это делает Google. Но без компоненты Универсальной текстуры или чего-то получше, они остаются ограниченными устаревшим двухмерным представлением или станут использовать трехмерное отображение, но с неудовлетворительными результатами, смазыванием, сверканием, и зависанием.
И это вероятно даже больше, чем Вы хотели бы знать о том, как рисуется целая Земля на вашем экране в каждом кадре.
|
