Archive for the ‘Uncategorized’ Category.

Минутная задачка

Махонькая задачка на приятное щелканье в мозгу – аж три раза за одну задачку. Найти надо, разумеется, все решения. Спойлеры, традиционно для Кружочков, публикуются линками на http://gist.github.com – тыкайте осторожней!

http://public.closedcircles.com/posts/few-minute-problem

@Zeux: GDC Report – The Rendering Technologies of Crysis 3 – Tiago Sousa (Crytek)

Слайды к докладу здесь – http://crytek.com/cryengine/presentations/the-rendering-technologies-of-crysis-3

People in this conversation:
Arseny Kapoulkine (Zeux) Add
CREAT Studios, Saber3D, Sperasoft (EA Sports – FIFA). Currently making kids happy at ROBLOX. http://zeuxcg.org/

Zeux: The Rendering Technologies of Crysis 3 – Tiago Sousa (Crytek)
В целом у меня создалось впечатление что Тиаго весь этот рендер уже давно задолбал, ну или рассказывать про него по крайней мере :)
Значит, основные изменения в рендере Крайзис 3! (для тех, кто знает что-нибудь про Крайзис 2)
Continue reading ‘@Zeux: GDC Report – The Rendering Technologies of Crysis 3 – Tiago Sousa (Crytek)’ »

Publish @Zeux: Кто рендеры писал…

People in this conversation:
Simon Kozlov Add
Zeux Add

Zeux: @All
Работать с OGRE сплошное удовольствие, столько фана! Вот тут странный баг на ipad – есть код который делает texture compositing для персонажей, запекая все в одну текстуру в рантайме. И вот достаточно редко (типа 1 из 10 запусков) на одном из персонажей текстурка серая (ее clear color – серый, т.е. ощущение, что ничего не рисуется). После определенного количества дебага выяснилось, что при загрузке текстур не степени двойки через Ogre в OpenGL ES делается glClear текущим цветом (соответственно, есть timing condition – если пока FBO composit текстуры еще активен решить что нам срочно нужно загрузить текстуру определенных размеров, то проявляется баг). И вот почему! (ценители OpenGL оценят)

Есть код, который блитает из текстуры в текстуру методом “временно привязать target текстуру к FBO и нарисовать квад с первой текстурой”. Он зачем-то дергается при загрузке текстуры с несовпадающими размерами (типа хотели 143×127, а пришлось 256×128). Вот код из desktop opengl:

void GLTextureBuffer::blitFromTexture(GLTextureBuffer *src, const Image::Box &srcBox, const Image::Box &dstBox)
{
/// Store reference to FBO manager
GLFBOManager *fboMan = static_cast<GLFBOManager *>(GLRTTManager::getSingletonPtr());

/// Save and clear GL state for rendering
glPushAttrib(GL_COLOR_BUFFER_BIT | GL_CURRENT_BIT | GL_DEPTH_BUFFER_BIT | GL_ENABLE_BIT |
GL_FOG_BIT | GL_LIGHTING_BIT | GL_POLYGON_BIT | GL_SCISSOR_BIT | GL_STENCIL_BUFFER_BIT |
GL_TEXTURE_BIT | GL_VIEWPORT_BIT);

Вот эквивалент на OpenGL ES:

void GLESTextureBuffer::blitFromTexture(GLESTextureBuffer *src, const Image::Box &srcBox, const Image::Box &dstBox)
{
// Store reference to FBO manager
GLESFBOManager *fboMan = static_cast<GLESFBOManager *>(GLESRTTManager::getSingletonPtr());

// Save and clear GL state for rendering
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT);

Simon Kozlov: reply @Zeux
То есть, пацаны когда портировали не знали чем заменить glPushAttrib и нашли glClear?
Потому что мол некоторые флаги туда пролазят и в комментариях что-то про clear говорится?

Zeux: reply @Simon Kozlov
Ну да. Save не получилось так хоть clear сделаем!

This happened on #gamedeff

Publish: Про спеки iPad

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

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

Continue reading ‘Publish: Про спеки iPad’ »

ClosedCircles – Discovery story

Предыдущие части:

ClosedCircles – #gamedeff going social
ClosedCircles – How coversations work

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

Есть несколько способов:

Friend List

Можно тыкнуть на Friend List и посмотреть, кто вообще еще есть на сервисе:

В Friends of Friends много народу, добавляйте тех, кого знаете. Линк в имени ведет на Facebook/G+ profile, в будущем мы добавим ЖЖ, Твиттеры итд.

Intro threads

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

Если ответить на любое их этих сообщений (как обычно, тыкнув на него мышкой), то ответ увидят все 250 с лишним человек в этом треде. Кстати, я периодически устраиваю такие интро-треды на всех, чтобы новые люди про себя рассказали. Тусовка живая, часто бывают интересные продолжения.
Если тыкнуть на незнакомого человека в интро-треде, в контакт-листе справа появится возможность его добавить.

Кроме представлений, интро-треды можно использовать многими разными способами – я, например, транслировал в реалтайме доклады с GDC. Надо попробовать лекцию устроить – есть еще идеи?

Интро-треды может делать каждый – надо тыкнуть на кнопку New Intro (над edit box) и выбрать, кто в нем будет учавствовать, галочками в контакт-листе.

Постить интересные дискуссии

Мой настоящий мега-план про discovery – это постить интересные дискуссии. В будущем мы сделаем какую-то автоматическую систему, которая спросит у всех участников что можно постить, а что нельзя, а пока я буду вручную спрашивать и постить что можно время от времени. Следите за апдейтами!

О важном

Напоследок, самое главное – ClosedCircles создан прежде всего чтобы комфортно общаться с людьми, о которых что-то знаешь, а не чтобы гнаться за количеством френдов и добавлять всех подряд.
Более того, чтобы писать и общаться, а не пассивно читать, что пишут другие. Функция пассивного чтения уже и так хорошо выполняется твиттером, ЖЖ и прочим социальным добром.

Посему – даже с такими слабыми механизмами discovery, добавляйте осторожно.
“Скажи мне, кто твой друг, и я скажу тебе, кто ты”

Линки чтобы попробовать это все на себе – #gamedeff, #programming

Yappy!

Компания google выложила библиотечку компрессии snappy http://code.google.com/p/snappy/. Библиотечка сжимает и разжимает со скоростью работы  SSD дисков, правда коэффициент компрессии не фонтан, хуже gzip. Но с дурацкими lzo, quicklz и прочей шушерой вполне сравнима.

Сразу захотелось поглядеть внутрь, что там. Внутри вариации на тему lz, 70 годы прошлого века.  Отсюда  поинт – вечное не тухнет. Что такое lz? Это две команды. Первая команда “прочитай N байт из потока и положи в буфер распаковки”, вторая команда “прочитай из буфера распаковки по смещению OFFSET от текущей позиции MATCH байт и опять положи в буфер распаковки”.

Компрессор snappy так и жмет примерно.  Он умеет кодировать OFFSET с помощью 1, 2 или 4 байт.

Сразу захотелось написать свое. Выходные, все такое. Решил, что мой код будет еще проще. Буду кодировать OFFSET с помощью 1 байта, всегда. А методу распаковки выдам лимит в 32 строчки С++ кода.

Родилось вот такое: http://www.everfall.com/paste/id.php?o3ug124i2l7p . Назовем его yappy.

Код распаковки там со строчки 14 по 45. Кроме распаковки там нет ничего интересного. Разве что эвристика, как выбираются 224 разных значения пар [OFFSET / 256: MATCH].

Сразу захотелось измерить пипиську творению.

Возьмем тестовые данные от snappy,  положим их без компрессии в tar архив, сожмем.

SNAPPY: [b 4096K] bytes 4638720 -> 2165687 46.7%  comp 214.9 MB/s  uncomp 683.6 MB/s

SNAPPY: [b 4K] bytes 4638720 -> 2445428 52.7%  comp 226.9 MB/s  uncomp 681.2 MB/s

За буковкой b идет размер блока в килобайтах. А теперь сожмем yappy:

YAPPY: [b 4096K] bytes 4638720 -> 2021663  43.6%  comp  49.2 MB/s  uncomp 1432.3 MB/s

YAPPY: [b 4K] bytes 4638720 -> 2268955  48.9%  comp  49.2 MB/s  uncomp 1476.1 MB/s

Видно две вещи. Вещь первая – что google выложил неудачные тестовые данные. Они слишком короткие, чтобы snappy со своими смещениями в 2 и 4 байта мог развернуться. Очевидно, что на больших продакшн данных все должно сжиматься лучше. Вещь вторая, что программисты google кабаны, они сделали чертовски быструю компрессию.  Собственно, ради чего все и затевалось – чтобы быть всюду быстрее сети и диска.

А теперь… Возьмем одну из компонент продакшн индекса в Яндексе. Она блочная, блоки по 4k. Готовится оффлайн, время компрессии нас не очень волнует.

Сожмем snappy и yappy.

SNAPPY: [b 4K] bytes 1328385387 -> 750585721 56.5%  comp 182.2 MB/s  uncomp 623.4 MB/s

YAPPY: [b 4K] bytes 1328385387 -> 686910077  51.7%  comp  48.5 MB/s  uncomp 1399.8 MB/s

Отсюда  мораль. Тырьте хорошие идеи, тырьте у грандов. И, вдруг, получите немножко технического экселенса, который приятен.

Software Occlusion Culling

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

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

  1. Трансформировать треугольники в вьюпорт спейс
  2. Определить границы тайлов
  3. Распределить треугольнички по всем тайлам, которых они касаются
  4. Отсортировать от ближних к дальних очереди треугольников каждоготайла (использую zmin для тест треугольников и zmax для треугольников оклюдеров)
  5. Нарисовать отсортированные списки ( для тест треугольников проверяется виден ли какой либо пиксель его сканлайнов, для оклюдеров записываются битики сканлайнов в буфер тайла)

Вообщемто базовую версию алгоритма не сложно реализовать и проверить самим. Моя текущая имплементация может рисовать 300к+ треугольников снапшота с игровой камеры Death Track примерно за 20мсек ( 12 мсек трансформаци + 8 мсек растеризация ) в 720п, что не плохо. И надо понимать что это однопоточная синхронная версия. Думаю, на архитектурах с большим числом регистров будет чуть лучше. Если прикрутить потоки – опять же думают станет ощутимо лучше. Очень органично ложится на концепцию Job Manager. Интересным также выглядит попытка автоматической генерации оклюдеров и тест геометрии. Респекты и уважухи Пете за крутую идею и обсуждение деталей реализации.

А ещё опубликовал в своём секретном бложике

Три задачи с одним решением

Есть три задачи. Задача первая – решить матричное уравнение A x = b, где A – матрица, x – неизвестный вектор, а b – заданная правая часть, опять вектор. Коэффициенты – действительные числа.

Во второй задаче коэффициенты (и у матрицы и у векторов) – целые числа.

А в третьей задаче все то же самое, только коэффициенты целые положительные, и уравнение надо решить в целых положительных числах.

Накал пиздеца постепенно крепчает. Целые числа мы не всегда можем делить друг на друга. Впрочем, взяв пару чисел (a, b), мы можем вычесть из большего по модулю числа меньшее по модулю, и такая процедура редукции нам отлично заменит деление.

А целые положительные числа мы можем вычитать, только меньшее из большего.

Однако, алгоритм Гаусса решения линейных систем уравнений работает во всех трех случаях (на то он и Гаусс).

Умные дядьки про третью задачу пишут страшное, примерно такое: http://documents.kenyon.edu/math/CWendler.pdf Это страшные люди, разобраться в их алгебре практически невозможно.

Попытаюсь на пальцах.

Continue reading ‘Три задачи с одним решением’ »

Из штатного расписания

“n-way ассоциативный продьюсер”

Технологическая конференция Яндекса

Вот: http://company.yandex.ru/public/yac/

Ваш покорный слуга выступает в качестве содокладчика Ильи Сегаловича (это технический директор Яндекса). О чем успею рассказать за 30 минут – не знаю. Хотелось бы чуть-чуть о поисковом теке рассказать. Приходите, регистрация свободная, вам наверняка будет занятно послушать про совсем другие, нежели в игроделании, технические проблемы.

Примерные слайды: “что дешевле, железка или мозги”, “сжать до меньше энтропии”, “мегаэффективный нанопараллелизм”