Gamedev LectureСтатьи

Лекция #35. Компрессия векторных данных [Лектор - Rageous] (2 стр)

Автор:

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: проще всего будет ее понять, посмотрев рисунок:
timerror | Лекция #35. Компрессия векторных данных [Лектор - 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 младших бит. булевые данные, к примеру, в битстрим обычно пишутся одним битом
  • AnnyCh: а... ясно, спасибо
  • Joric: не проще ли по карте контрольные точки расставить и не заниматься ерундой?
  • Rageous: речь о сохранении данных, которые пришли со спутниковой системы, к примеру, и как раз о том, чтобы эти точки выбрать
  • AnnyCh: вы говорили, что данные о компонентах вектора при сжатии помещаются в буфер последовательно, и что распаковка идет напрямую из битстрима... т.е. при таком подходе пока не будут получены все части сжатого буфера распаковка все равно невозможна?
  • Rageous: распаковка может идти только при наличии всех данных одного пакета
  • AnnyCh: ясно
  • Rageous: хотя в принципе, если воспроизводить последовательно - можно воспроизводить и частично загруженные пакеты - при условии того, что загружен их заголовок и необходимый объем данных (от начала пакета до текущего времени). но т.к. это не особо часто требуется - например, если хочется делать что-то типа сетевого телевидения, то можно просто уменьшить длины пакетов, то подобной поддержки я не делал - она исключается построением индексов вида (время - позиция в потоке) при загрузке пакета, которые используются для ускорения перемотки
  • AnnyCh: да, пакет тут будет более правильным словом
  • Страницы: 1 2

    #аппроксимация, #битстрим, #векторные данные, #сжатие, #сплайны

    20 апреля 2008 (Обновление: 21 фев 2012)