Текстурирование Google Earth

На блоге RealityPrime Ави Бар-Зив (Avi Bar-Zeev) публикует серию постов под названием How Google Earth [Really] Works. Ави участвовал в разработке Google Earth на начальном этапе. Тогда это еще не имело отношение к Гуглу, называлось Earthviewer и было потом Гуглом куплено.
Первый пост был как раз о текстурировании. Их подход к текстурированию называется Universal Texture и защищен патентом. Ави как раз занимался реализацией Universal Texture. В его посте приведена ссылка на статью, подробно описывающую работу этого подхода. Он рассказывает о текстурировании очень подробно, останавливаясь на таких базовых вещах как билинейная фильтрация и мипмэппинг. Я это все опущу, если не знаете что это такое - я привела ссылки, да и самого Ави можно почитать. У меня здесь будет что-то вроде краткого пересказа статьи The Clipmap: A Virtual Mipmap, на которую ссылается Ави.

Вкратце отрисовка земного шара на клиенте выглядит так: надо нарисовать кусок земной поверхности и положить на него текстуру Земли, снятую со спутника.
Итоговая текстура у них получилась размером 40 млн на 20 млн текселов. Плюс мипмэп уровни, стандартные, по степеням двойки. Как уже можно догадаться размер получается большой. На самом деле примерно 11 петабайт. Много, короче. А это все надо передать по сети клиенту. И наложить на машине пользователя на кусок земного шара, а в оперативную память такое не влезет. Обычное решение в таком случае - текстуру порезать на куски, хранить не целиком, а кусками, и уже с ними работать. Тут, правда, всплывают проблемы с совмещением этих кусков, появляются ограничения на геометрию. Разработчики решили, что эти проблемы им не нужны, что у них Свой Путь и они ничего резать на куски не будут. А будут хранить всю текстуру целиком, а на клиента передавать только то подмножество, которое клиенту в данный момент нужно. В итоге получается, что клиенту нужно где-то 35 мегабайт. Тут все зависит от качества текстуры, его ведь можно варьировать, Ави пишет, что достаточно 17 мегабайт.

Чтобы определить какое подмножество изначальной здоровой мипмэп пирамиды пересылать пользователю, сначала смотрят куда направлен "взгляд", какой уровень детализации пользователю нужен, и изо всей мипмэп пирамиды вырезают нужный кусок и его пересылают. Если не удалось быстро переслать кусок нужной детализации - для начала рисуют детализацию похуже, потом быстренько подугружают нужное.

Чтобы фпс был плавным, загрузка текстуры на клиента происходит маленькими тоненькими кусочками. По максимуму стараются подгрузить до того как этот кусок понадобится. Если опоздали - то сразу после того как он понадобился.

В The Clipmap: A Virtual Mipmap это все описано подробно и загрузочно, с наглядными схемами.

По ходу своего рассказа Ави высказывает интересную идею - скрестить Google Earth и Second Life (Кстати, исходники клиента Second Life открыты, их можно посмотреть прямо сейчас).

Ссылки по теме:
Ланс Виллиамс изобрел мипмэппинг в 1983 году и описал его в работе Pyramidal parametrics.