Мне давно было интересно, как сжимаются данные, в том числе в Zip-файлах. Однажды я решил удовлетворить своё любопытство: узнать, как работает сжатие, и написать собственную Zip-программу. Реализация превратилась в захватывающее упражнение в программировании. Получаешь огромное удовольствие от создания отлаженной машины, которая берёт данные, перекладывает их биты в более эффективное представление, а затем собирает обратно. Надеюсь, вам тоже будет интересно об этом читать.

В статье очень подробно объясняется, как работают Zip-файлы и схема сжатия: LZ77-сжатие, алгоритм Хаффмана, алгоритм Deflate и прочее. Вы узнаете историю развития технологии и посмотрите довольно эффективные примеры реализации, написанные с нуля на С. Исходный код лежит тут: hwzip-1.0.zip.

^{Итоговый результат — ключ размером с флешку}

Повсеместное шифрование и, как следствие, обилие ключей заставляет задуматься об их надежном хранении. Хранение ключей на внешних устройствах, откуда они не могут быть скопированы, уже давно считается хорошей практикой. Я расскажу о том, как за 3$ и 2 часа сделать такой девайс.

… в котором я пытаюсь разыграть лже-Анну, но она готова на всё верит всему.

Навигация по предыдущим «действиям»:

• Действие третье, в котором я получаю документацию о том, что моя банковская ячейка создана
• Действие второе, в котором я срываюсь и бегу до ближайшего банкомата
• Действие первое, в котором мне любезно рассказывают о других мошенниках

Вступление

Мне кажется, что нам надо использовать меньше тригонометрии в компьютерной графике. Хорошее понимание проекций, отражений и векторных операций (как в истинном значении скалярного (dot) и векторного (cross) произведений векторов) обычно приходит с растущим чувством беспокойства при использовании тригонометрии. Точнее, я считаю, что тригонометрия хороша для ввода данных в алгоритм (для понятия углов это интуитивно понятный способ измерения ориентации), я чувствую, что что-то не так, когда вижу тригонометрию, находящуюся в глубинах какого-нибудь алгоритма 3D-рендеринга. На самом деле, я думаю, что где-то умирает котенок, когда туда закрадывается тригонометрия. И я не так беспокоюсь о скорости или точности, но с концептуальной элегантностью я считаю… Сейчас объясню.

Раньше облака в играх рисовались обычными 2D спрайтами, которые всегда повернуты в направлении камеры, но последние годы новые модели видеокарт позволяют рисовать физически корректные облака без заметных потерь в производительности. Считается, что объемные облака в игры принесла студия Guerrilla Games вместе с игрой Horizon Zero Dawn. Конечно, такие облака умели рендерить и раньше, но студия сформировала что-то вроде промышленного стандарта на исходные ресурсы и используемые алгоритмы, и в настоящее время любая реализация объемных облаков так или иначе этому стандарту соответствует.

UPD. Картинка обновлена. Изменения описаны в конце статьи.

Речь пойдёт о “Weighted blended order-independent transparency” (далее WBOIT) — приёме, описанном в JCGT в 2013 г. (ссылка).

Привет! Это очередной традиционый список книг, оказавшихся полезными за год. Сугубо субъективный, конечно. Но я серьёзно рассчитываю, что вы подскажете ещё классных штук почитать.



Думай медленно, решай быстро — Даниэль Канеман
Это самое волшебное, что случалось за последние годы в плане гиковой литературы. Эта штука последовательно открывает когнитивные искажения и учит настраивать мышление. При этом увлекательно. Вообще, подход к тому, что мышление — это набор техник, которые можно тренировать и оттачивать, он, наверное, правильнее подхода «это шаманство». Канеман в отличие от следующей в списке книги, показывающей особенности реверсивного мышления, не даёт новых техник — но показывает, где и какие ошибки мы совершаем при обычных процессах. Такой серьёзный дебаг мозга.

Эта статья — продолжение статьи про громадные числа. Но сейчас мы пойдем еще дальше — в бесконечности бесконечностей.

Введение

Умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверточных слоях неронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию. Почему так происходит? Ответ кроется в очень эффективной реализации этого алгоритма для процессоров, графических ускорителей (а в последнее время и специальных ускорителей матричного умножения). Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому не удивительно, что многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.

Так как реализован алгоритм матричного умножения? Хотя сейчас существуют множество реализаций данного алгоритма, в том числе и в открытых исходных кодах. Но к сожалению, код данных реализаций (большей частью на ассемблере) весьма сложен. Существует хорошая англоязычная статья, подробно описывающая эти алгоритмы. К моему удивлению, я не обнаружил аналогов на Хабре. Как по мне, этого повода вполне достаточно, чтобы написать собственную статью. С целью ограничить объем изложения, я ограничился описанием однопоточного алгоритма для обычных процессоров. Тема многопоточности и алгоритмов для графических ускорителей явно заслуживает отдельной статьи.

Процесс изложения будет вестись ввиде шагов с примерами по последовательному ускорению алгоритма. Я старался писать максимально упрощая задачу, но не более того. Надеюсь у меня получилось…

Тема переезда в Европу, США или другие приятные регионы мира довольно часто поднимается на Хабре. Я решил собрать в одном месте список онлайн-сервисов, которые будут полезны тем, кто всерьез задумался об иммиграции. На удивление, «живых» и активных стартапов в этой сфере не так и много. Для статьи я отобрал четыре проекта.

Привет, Хабр! Представляю вашему вниманию перевод статьи «Reflective Shadow Maps» автора Eric Polman.

Reflective Shadow Maps (RSM) (отражающие карты теней) ― это алгоритм, расширяющий “простые” shadow map. Алгоритм учитывает свет, рассеянный после первого попадания на поверхность (diffuse). Это означает, что кроме прямого освещения, вы получаете непрямое освещение. В данной статье я разберу алгоритм из официальной статьи, чтобы объяснить его по-человечески. Я также кратко расскажу о shadow mapping.

Нередко слышишь мнение, что составление Технического задания по ГОСТ 34 (ТЗ) занятие не только трудоемкое, но и крайне раздражающее, поскольку приходится писать много всякой ерунды, воды. Но подумайте: разработкой этого ГОСТа занимались целые НИИ, это был проект на государственном уровне, обобщен опыт сотен проектов автоматизации, сложных проектов. Неужели они могли написать чушь?

На самом деле, при грамотном подходе ГОСТ очень сильно помогает не только при разработке ТЗ, но и в ходе реализации проекта автоматизации в целом (и не только в госконтрактах, но и для коммерческой разработки). Грамотные люди его писали. Но чтобы воспользоваться плодами их трудов, нужно немного понять замысел не только ТЗ, но и ГОСТ 34 в целом.

В данной статье мы пункт за пунктом разберем все требования ГОСТа и попробуем сделать разработку ТЗ по ГОСТ 34 не обременением, а большой помощью в проекте.

Привет!

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



Почему это важно сделать на бумаге? Потому что она без батарейки, не требует подключения к сети и содержит самые важные номера законов. В общем, бумага очень отказоустойчивая. Естественно, есть и PDF, которую можно просто залить на телефон.

В жизни можно ставить любые цели, и потом упорно искать пути их достижения. Если в ваших планах было что-то вроде «стать волшебником», то поспешите. У вас еще есть возможность реализовать свою мечту и стать настоящим Дедом Морозом до конца этого года!

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

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

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

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

Концепция кватернионов была придумана ирландским математиком сэром Уильямом Роуэном Гамильтоном в понедельник 16 октября 1843 года в Дублине, Ирландия. Гамильтон со своей женой шёл в Ирландскую королевскую академию, и переходя через Королевский канал по мосту Брум Бридж, он сделал потрясающее открытие, которое сразу же нацарапал на камне моста.

$$

Памятная табличка на мосту Брум Бридж через Королевский канал в честь открытия фундаментальной формулы умножения кватернионов.

В этой статье я постараюсь объяснить концепцию кватернионов простым для понимания образом. Я объясню, как можно визуализировать кватернион, а также расскажу о разных операциях, которые можно выполнять с кватернионами. Кроме того, я сравню использование матриц, углов Эйлера и кватернионов, а затем попытаюсь объяснить, когда стоит использовать кватернионы вместо углов Эйлера или матриц, а когда этого делать не нужно.

Физически-корректный рендеринг

PBR, или физически-корректный рендеринг (physically-based rendering) это набор техник визуализации, в основе которых лежит теория, довольно хорошо согласующаяся с реальной теорией распространения света. Поскольку целью PBR является физически достоверная имитация света, он выглядит гораздо более реалистичным по сравнению с использованными нами ранее моделями освещения Фонга и Блинна-Фонга. Он не только лучше выглядит, но и дает неплохое приближение к реальной физике, что позволяет нам (и в частности художникам) создавать материалы, основанные на физических свойствах поверхностей, не прибегая к дешевым трюкам дабы заставить освещение выглядеть реалистично. Главным преимуществом такого подхода является то, что создаваемые нами материалы будут выглядеть как задумано независимо от условий освещения, чего нельзя сказать о других, не PBR подходах.

Parallax Mapping

Техника текстурирования Parallax Mapping по своему эффекту несколько схожа с Normal Mapping’ом, но основана на другом принципе. Схожесть в том, что, как и Normal Mapping, данная техника значительно увеличивает визуальную сложность и детализацию поверхности с нанесенной текстурой заодно создавая правдоподобную иллюзия наличия на поверхности перепадов высот. Parallax Mapping отлично работает в связке с Normal Mapping для создания весьма достоверных результатов: описываемая техника передает эффект рельефа гораздо лучше Normal Mapping, а Normal Mapping дополняет его для правдоподобной имитации динамического освещения. Parallax Mapping вряд ли можно считать техникой, прямо относящейся к методам имитации освещения, но все же я выбрал этот раздел для его рассмотрения, поскольку метод является логическим развитием идей Normal Mapping. Также отмечу, что для разбора этой статьи требуется хорошее понимание алгоритма работы Normal Mapping, в особенности понятия касательного пространства или tangent space.

Часть 1. Знакомство с Marching cubes

Как создать меш из любого хаоса
В Minecraft мы можем копать в любом направлении, убирая за раз по одному блоку с чётко заданными краями. Но в других играх разработчикам удаётся разрушать рельеф плавно, без кубичности Minecraft.

Вот пример из No Man’s Sky: видео.

Аналогичная техника применяется для отображения изображений с МРТ, metaball-ов и для вокселизации рельефа.

В этой части я расскажу о технике создания разрушаемого рельефа Marching Cubes, а в более общем применении — для создания плавного граничного меша твёрдого объекта. В этой статье мы начнём с рассмотрения двухмерной техники, затем трёхмерной, а в третьей части рассмотрим Dual Contouring. Dual Contouring — это более совершенная техника, создающая тот же эффект.

В последние годы вопрос обхода различных блокировок сайтов стоит достаточно остро. Проще всего решить ее можно с помощью прокси-расширений для браузера. А поскольку самым популярным браузером сейчас является Chrome, то я решил собрать в одном материале все самые адекватные варианты прокси и VPN-расширений для него.