Общие сведения
Дата проведения: 19 апреля 2008 года
Продолжительность: 1 час
Место проведения: irc-канал сайта Ogre3D.ru
Опубликовали статью
Сайт Ogre3D.ru: ссылка
Коммунити "Gamedev Lecture" сайта Gamedev.ru: ссылка
Мой личный сайт: ссылка
Блог сайта Gamedeff.com: ссылка
Лог
18:01:04 Rageous: всем привет
18:01:11 Rageous: пару слов о том, как будет проходить лекция
18:01:21 Rageous: сначала я прочитаю то, что подготовил, после этого можно будет задать вопросы
18:01:34 Rageous: пожалуйста, не пишите их в личку :)
18:02:06 Rageous: лекция, которую я сегодня читаю, посвящена моим исследованиям в области компресси векторных данных
18:02:30 Rageous: в связи с тем, что мне уже задавали вопросы, что есть векторные данные, я проясню этот вопрос отдельно
18:02:52 Rageous: здесь и далее под векторными данными я буду подразумевать функции f(t), где t - время, а f(t) - функция, возвращающая некоторое рациональное значение
18:03:16 Rageous: с подобными данными мы работаем каждый день: в играх это анимации персонажей, пути перемещения объектов, траектории движения физических тел
18:03:35 Rageous: в софте это информация по трекингу машин автопарка, к примеру
18:03:58 Rageous: здесь, к примеру, можно увидеть сохраненный путь автомобиля. сохраненные данные используются для анализа скорости, времени и количества остановок: 
18:04:21 Rageous: здесь зеленоградский автопарк предоставил свои данные для анализа дорожной обстановки на одной из самых нагруженных московских трасс, чем облегчил жизнь множеству автомобилистов: 
18:04:47 Rageous: итак, векторные данные полезны. часто бывает полезно их сохранять. к сожалению их объем нередко далек от "незначительного"
18:05:17 Rageous: в связи с этим возникает вопрос об их компрессии
18:05:54 Rageous: к примеру, если вы хотите сохранить реплей заезда в автосимуляторе, чтобы поделиться им с друзьями, вам придется думать о том, как переслать по интернету до десятка мегабайт данных
18:06:56 Rageous: если же вы занимаетесь ПО и хотите хранить годами информацию по имеющимся в вашем распоражении автомобилям или морским судам или самолетам или еще чему - вы можете легко столкнуться с проблемой огромного объема этих сведений
18:07:19 Rageous: к счастью существуют архиваторы :)
18:07:48 Rageous: и к сожалению сжатие векторных данных - одно из самых низких для большинства современных алгоритмов
18:08:00 Rageous: так, например, zip сжимает такие данные в 2-3 раза
18:08:17 Rageous: rar и 7zip обеспечивают сжатие до 25 раз, но делают это весьма медленно
18:09:07 Rageous: слабым местом архиваторов является то, что они предоставляют lossless (без потерь) компрессию, а так же не располагают сведениями о структуре предоставленных им данных
18:10:17 Rageous: целью, которую я ставил перед собой, когда начинал заниматься компрессией векторных данных, было сжатие в 100-1000 раз при скорости достаточной, чтобы осуществлять это сжатие в реальном времени без серьезного удара по производительности основного приложения
18:10:34 Rageous: итак, что я делал
18:11:17 Rageous: первое - все данные были разбиты на отдельные потоки вида v(t), где v - это функция времени, возвращающая одно или несколько рациональных чисел
18:12:07 Rageous: имеющиеся данные были слегка изменены, чтобы избавиться от избыточности: вместо полных матриц 4*4 трансормации я писал вектора и нормализованные (3 компоненты) кватернионы
18:12:48 Rageous: потоки, объединяющие в себе несколько флоатов для одного момента времени пригодились для записи нормализованных кватернионов - уменьшив погрешность
18:13:27 Rageous: второе - так как данные нужно было сжимать и сохранять в реальном времени, все данные были разбиты на пакеты фиксированной длины (обычно порядка 30-90 секунд)
18:14:09 Rageous: в памяти одновременно находятся два пакета: текущий и прошлый. прошлый сжимается вместе с наполнением текущего, что позволяет избежать пиковых нагрузок при сохранении пакета в файл или иное хранилище
18:14:33 Rageous: после сохранения сжатого пакета его место, соот-но, занимает текущий, а текущий начинает наполняться новыми данными
18:16:08 Rageous: третье - данные в библиотеку приходят очень часто. в играх - раз в кадр. в софте - при каждом замере. в большинстве ситуаций это означает избыточность данных, т.к. объект, который движется почти прямолинейно, создает такой же объем сведений, как и объект, который бешенно меняет свою позицию и ориентацию
18:16:19 Rageous: чтобы избавиться от этой избыточности нужно провести аппроксимацию
18:16:54 Rageous: наиболее частым и простым подходом в данной ситуации является аппроксимация кусочно-линейным сплайном
18:17:01 Rageous: или, проще говоря, ломаной
18:17:31 Rageous: фиттинг (вычисление минимального набора необходимых ключей) для такого сплайна осуществляется очень просто и быстро
18:18:03 Rageous: но результат оставляет желать лучшего как с т.з. компрессии, так и с т.з. внешнего вида полученных после обработки данных
18:18:15 Rageous: машина начинает двигаться "угловато"
18:18:49 Rageous: вторым подходом является фиттинг сплайнов более высокого порядка - квадратичных и кубических сплайнов
18:19:25 Rageous: сразу скажу, несмотря на интуитивно-большую гибкость кубических, я остановился на квадратичных
18:19:46 Rageous: это связано с тем, что фиттинг кубических сплайнов - весьма сложный процесс, который требует тонкой настройки
18:20:02 Rageous: в противном случае на сплайне появляются выбросы, которые сводят на нет все преимущества
18:20:10 Rageous: либо же компрессия становится чрезвычайно низкой
18:20:41 Rageous: неплохая статья с исходниками по кубическим сплайнам находится здесь: http://alglib.sources.ru/interpolation/spline3.php
18:21:00 Rageous: про фиттинг можно почитать здесь: http://www.stanford.edu/~boyd/cvx/examples/cvxbook/Ch06_approx_fitting/html/fig6_20.html и здесь: http://ask.metafilter.com/50554/Generating-Bezier-curves-from-discrete-point-sets
18:21:22 Rageous: что же квадратичный сплайн. я взял сплайн безье: http://ru.wikipedia.org/wiki/Кривая_Безье
18:21:54 Rageous: он имеет очень простую формулу, которая легко обращается, дабы вычислить опорную точку по имеющимся точкам начала и конца, а так же некоторой промежуточной
18:22:05 Rageous: потому его фиттинг легко объяснить на пальцах:
18:22:24 Rageous: мы берем весь пакет данных, вычисляем для него усредненную опорную точку
18:22:55 Rageous: с ней прогоняем функцию оценки ошибки. если ошибка слишком велика, делим данные пополам - и проводим ту же процедуру с первой половиной
18:23:37 Rageous: так - до тех пор, пока не найдем кусок данных максимальной длины, который можно представить в виде начальной, конечной точек и опорного значения (P1 в формулах на вики)
18:24:09 Rageous: с оставшимися данными процесс повторяется до тех пор, пока весь пакет не будет представлен в виде наборов квадратичных сплайнов
18:24:26 Rageous: что дал квадратичный сплайн:
18:24:42 Rageous: скорость компрессии в сравнении с линейным примерно вдвое
18:25:11 Rageous: однако коэффициент компрессии в среднем вырос на порядок
18:25:39 Rageous: все, что оставалось - сохранить результаты в минимальном объеме
18:26:05 Rageous: для этого хорошо подходит квантование и дельта-компрессия
18:26:37 Rageous: мы анализируем данные в пределах пакета, находим макс. и мин. значения, а так же определяем характер функции: монотонная ли она. если да, то возрастает или убывает
18:27:28 Rageous: полученный диапазон, пользуясь размером допустимой ошибки как размером кванта, мы дискретизируем
18:28:20 Rageous: и сохраняем в заголовок пакета пределы отклонения, характер и функции. а в данные пишем целочисленные значения
18:28:34 Rageous: тут, разумеется, очень кстати битстрим
18:28:45 Rageous: за счет которого мы пишем дельты с минимально необходимым битрейтом
18:29:25 Rageous: на этом математические подходы заканчиваются, но мы можем выжать еще немного за счет более рациональной подготовки данных
18:29:48 Rageous: так, например, мы можем менять допустимую погрешность между пакетами и задавать ее отдельно для разных потоков данных
18:30:11 Rageous: это позволит нам уменьшать точность позиционирования удаленных от наблюдателя объектов
18:30:43 Rageous: но за счет этого сильно (до 10 раз и выше) экономить объем данных
18:31:15 Rageous: время, очевидно, мы так же подвергаем квантованию
18:31:26 Rageous: точнее говоря, можем это сделать, но здесь таится одна тонкость
18:31:36 Rageous: проще всего будет ее понять, посмотрев рисунок: 
18:32:15 Rageous: по горизонтали отложено время, вертикальными прямыми отмечены границы квантов
18:32:35 Rageous: черная кривая - начальные значения. серые коридор вокруг нее - макс. допустимая погрешность
18:32:42 Rageous: синяя кривая - восстановленные значения
18:33:06 Rageous: из рисунка видно, что из-за квантования первая точка излома сместилась на полкванта влево
18:33:20 Rageous: что привело к многократному превышению допустимой погрешности
18:33:36 Rageous: если бы вы писали юнит-тесты на систему, этот тест провалился бы. мой провалился :)
18:34:01 Rageous: к счастью подобные ошибки строго локализованы во времени - и не могут длиться дольше длины кванта
18:34:36 Rageous: что по сути означает, что ваш объект не улетит в неизвестность и не проедет в стене, а всего лишь чуть медленнее сменит ориентацию или позицию
18:34:47 Rageous: скажем, не за 1мс, а за 2мс - по размеру кванта времени
18:35:09 Rageous: итак, результаты всей этой математики
18:35:18 Rageous: сводная таблица: http://www.everfall.com/paste/id.php?vv6fv52bihxg
18:35:37 Rageous: поясню заголовки столбцов в ней: length - продолжительность теста в секундах
18:35:47 Rageous: packet - длина пакета в секундах
18:35:58 Rageous: quantum - размер кванта времени в секундах
18:36:09 Rageous: maxerror - предельно допустимая погрешность
18:36:19 Rageous: quantize - использовалось ли квантование времени
18:36:47 Rageous: RESULT состоит из двух значений. знак + или - означает, прошел ли данный тест проверку на макс. погрешность
18:36:57 Rageous: xNNNN - это степень компрессии, записанная в разах
18:37:55 Rageous: к примеру, превый тест Default длился чуть больше 8 минут, использовал пакеты по полторы минуты, погрешность в 1мм и квант времени 20мс
18:38:18 Rageous: данные после компрессии занимают в 630 раз меньше тех, что пришли в библиотеку
18:38:35 Rageous: так же стоит отметить по этой таблице некоторые закономерности:
18:39:00 Rageous: 1. размер погрешности и кванта влияют на качество нелинейно, потому придется повозиться с их тонкой настройкой под конкретный проект
18:39:26 Rageous: 2. квантование времени дает дополнительные 30% сжатия, но имеет недостатки, которые я описал выше
18:39:47 Rageous: 3. размер пакета в большинстве случае можно варьировать не опасаясь серьезной потери компрессии
18:40:11 Rageous: однако, слишком маленькие пакеты дают низкое соотношение размера заголовка пакета к полезным данным, что все же сказывается на силе сжатия
18:40:47 Rageous: как известно, любые данные можно сжать до одного байта. к сожалению, до сих пор не найден алгоритм их декомпрессии из этого байта )
18:41:03 Rageous: дабы не оставлять это щекотливый момент в стороне, пара слов про декомпрессию
18:41:26 Rageous: декомпрессия имеет линейную сложность при непрерывном воспроизведении и логарифмическую при перемотке
18:41:51 Rageous: перемотку, кстати, пользуясь обычными архиваторами, сделать было бы значительно более затруднительно - без декомпрессии всех данных целиком
18:42:14 Rageous: детальный отчет по одному из тестов можно найти здесь: http://www.everfall.com/paste/id.php?ittkm4w5swo0
18:42:30 Rageous: опять же, ключевые моменты: Performance 38.1 Mb/s
18:42:43 Rageous: это скорость сжатия в мегаБИТах в секунду
18:43:00 Rageous: что такое 5МБ/сек. это 10 мегабайт десятиминутного реплея сжатые за 2 секунды
18:43:09 Rageous: то есть сжатие съест менее 1% от времени работы вашего приложения
18:43:26 Rageous: статистика по объемам данных: Floats 80%, Time 15% и Headers 3%
18:43:58 Rageous: как мы и отмечали раньше - размер заголовков сравнительно мал, а квантованное время значительно меньше влияет на объем, чем сами данные
18:44:33 Rageous: если сравнить показатели по затраченному времени - это 29 + 88мсек для сжатия и 32мсек для декомпрессии - станет ясно, что декомпрессия втрое быстрее сжатия
18:45:50 Rageous: библиотека обеспечивает желаемый уровень компрессии при соблюдении заданных требований
18:46:09 Rageous: так что на этом все. и я готов ответить на ваши вопросы
Вопросы и ответы
- Five_Stars: потоки это несколько параллельных, или несколько последовательных?
- Rageous: потоки идут параллельно. например, позиция - это один поток из трех флоатов или три потока по одному
.
- Five_Stars: интересно, а как ты устроил передаваемые пакеты? все потоки в нём пишутся последовательно одним большим куском (поток1, поток2, поток3), или всё как-то в зависимости от времени(10сек Потока1, 10сек Потока2... и сначала)... или по-байтно(10байт Потока1, 100байт Потока2... и сначала)
- Rageous: в каждом пакете набор потоков. в нем они лежат последовательно - все данные одного потока целиком, потом второго и т.д.
.
- Five_Stars: а это удобно? нет, я понимаю, что у тебя были не очень большие пакеты и декомпресс может отработать всё сразу, чтобы незаметно, но, а насчёт варианта разбивки (по времени, например, там, правда, наверное, синхронизировать придётся ) ты не думал? Для баальших баальших пакетов...
- Rageous: это как раз регулируется длиной пакета. если ее поставить меньше, в памяти он будет не настолько велик - и проблема отпадет
- Rageous: с этим нельзя не согласиться
- Wraith: декомпресс тоже выполняется с двойной буферизацией: один буфер ты играешь, другой заполняется данными
- Rageous: нет, при декомпрессе там не нужно двойной буферизации, только загрузка асинхронная
- Wraith: даже так?
- Rageous: у воспроизведения сложность очень низкая: библиотека играет много быстрее, чем жмет
.
- AnnyCh: вы говорили о "битстриме", за счет которого достигается минимально возможный битрейт... к сожалению мне не понятен этот термин... это какая-то разновидность энтропийного сжатия?
- Rageous: нет, это всего лишь класс, обеспечивающий упаковку данных в поток бит. то есть, к примеру, числа можно записать не в 32 бита, а в любое заданное количество. разумеется, если значение числа в это количество не умещается, произойдет своеобразное переполнение: будут записаны лишь N младших бит. булевые данные, к примеру, в битстрим обычно пишутся одним битом
.
- Joric: не проще ли по карте контрольные точки расставить и не заниматься ерундой?
- Rageous: речь о сохранении данных, которые пришли со спутниковой системы, к примеру, и как раз о том, чтобы эти точки выбрать
.
- AnnyCh: вы говорили, что данные о компонентах вектора при сжатии помещаются в буфер последовательно, и что распаковка идет напрямую из битстрима... т.е. при таком подходе пока не будут получены все части сжатого буфера распаковка все равно невозможна?
- Rageous: распаковка может идти только при наличии всех данных одного пакета
- AnnyCh: ясно
- Rageous: хотя в принципе, если воспроизводить последовательно - можно воспроизводить и частично загруженные пакеты - при условии того, что загружен их заголовок и необходимый объем данных (от начала пакета до текущего времени). но т.к. это не особо часто требуется - например, если хочется делать что-то типа сетевого телевидения, то можно просто уменьшить длины пакетов, то подобной поддержки я не делал - она исключается построением индексов вида (время - позиция в потоке) при загрузке пакета, которые используются для ускорения перемотки
- AnnyCh: да, пакет тут будет более правильным словом