А не замахнуться ли нам на Эдсгера нашего Дейкстру?

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

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

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

Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.

Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.

В прошлый раз мы пришли к выводу, что для эффективной работы пространственного индекса на основе Z-order необходимо сделать 2 вещи:

• эффективный алгоритм получения подинтервалов
• низкоуровневую работу с B-деревом

Вот именно этим мы и займёмся под катом.

Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:

• реализован как обычное B-дерево, а мы знаем что
• страницы B-дерева имеют лучшую заполняемость, кроме того,
• Z-ключи сами по себе более компактны
• B-дерево имеет естественный порядок обхода, в отличие от R-дерева
• B-дерево быстрее строится
• B-дерево лучше сбалансировано
• B-дерево понятнее, не зависит от эвристики расщепления/слияния страниц
• B-дерево не деградирует при постоянных изменениях
• ...

Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.

Результат: информация о цвете занимает 1/64 от исходной площади при достаточно высоком качестве результата. Тестовое изображение взято с этого сайта.

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

Речь пойдёт о картографии, имеющей дело с фантастическими мирами.

Положение дел с процедурной генерацией карт

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

На дворе конец 2016 года, наконец-то, вызвав бурю восторга среди фанатов, вышла третья часть «Казаков»… А мне всё не давала покоя странная ошибка в сетевой компоненте первой части. Странность заключалась в том, что при создании игры в локальной сети нормально запустить игру могли только два человека. При трёх игроках индикатор загрузки рос мучительно медленно, а начиная с четырёх и вовсе оставался на отметке 0%. Что ж, начнём расследование!

Далее будет рассказано о том, как реализовать метод расчета рассеянного освещения Screen Space Ambient Occlusion на языке программирования С++ с использованем API DirectX11.

Лог-линейные модели и их представления в виде марковских сетей позволяют показать структуру взаимосвязей между случайными величинами. Однако полученная визуализация может оказаться трудна для восприятия из-за большого числа равнозначных ребер в графе такой модели. При работе с порядковыми и бинарными переменными гауссовы копулы (Gaussian copula graphical models, сокр. GCGM) дают возможность повысить наглядность и упростить интерпретацию модели. В статье приведен краткий обзор теории и построен пример GCGM для European Social Survey данных.

Привет всем. Многие из вас знакомы с лагом ввода. Это бывает, когда вас в очередной раз убивают в компьютерной игре, и вы кричите: «Ну я же нажал блок/атаку/уворот». Ну а затем джойстик летит в стену. Знакомо? Происходит это потому, что между нажатием клавиш и появлением результата на экране проходит значительное время. Фактически, когда вы смотрите в экран — вы видите прошлое состояние, которое может абсолютно не отражать действительность.

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

Алиасинг представляет одну из фундаментальных проблем компьютерной графики, и для борьбы с ним придумано множество разнообразных алгоритмов антиалиасинга. Появление MLAA привлекло интерес к алгоритмам, работающим на этапе постобработки. Одним из таких алгоритмов (с небольшой оговоркой) является Geometry Buffer Anti-Aliasing (GBAA). В этом материале описана попытка модификации оригинального алгоритма для улучшения качества антиалиасинга в некоторых случаях.

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



Создание качественных скелетных 3D анимаций сегодня, пожалуй, самая труднодоступная для инди разработчиков задача. Вероятно поэтому так мало инди игр в 3D, и так много проектов в стилях пиксель арта или примитивизма, а также бродилок без персонажей в кадре. Но теперь это соотношение может измениться…

«Давным-давно, кажется, в прошлую пятницу» автору попалась на глаза статья, в которой сравниваются разные популярные методы индексации небесных объектов. По причине неровного дыхания к этой теме пришлось разбираться в тонкостях и делать выводы.

Вы спросите: «Кому вообще интересны эти небесные объекты?» и даже: «Ну и при чём здесь 2ГИС?» и будете отчасти правы. Ведь методы пространственного индексирования являются универсальной ценностью.

Обычно, имея дело с геоданными, мы работаем с локальной проекцией на плоскость и тем самым отмахиваемся от искажений. В масштабах планеты это сделать труднее — начинают выпирать астрономические проблемы.
Что касается объёмов данных, уже сейчас в OSM более 4 млрд точек и 300 млн дорог. Это соизмеримо с масштабами, характерными для звёздных объектов. Да и помимо всего прочего, звёздные атласы — отличный стенд для разработки и отладки пространственных алгоритмов.

Обещанные тонкости и выводы под катом.

Сегодня поговорим о фонтанных кодах. Их ещё называют «кодами нефиксированной скорости». Фонтанный код позволяет взять, например, какой-нибудь файл, и преобразовать его в практически неограниченное количество закодированных блоков. Имея некоторое подмножество этих блоков, можно восстановить исходный файл, при условии, что размер этого подмножества немного превышает размер файла. Другими словами, такой код позволяет создавать «фонтан» из кодируемых данных. Получатель может восстановить исходные данные, собрав достаточно «капель» из фонтана, при этом неважно – какие именно «капли» у него есть, и какие именно он пропустил.

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

Определение 1. Однородный контейнер – это такой контейнер, в котором хранятся объекты строго одного типа.

Определение 2. Неоднородный контейнер — это такой контейнер, в котором могут храниться объекты разного типа.

Определение 3. Статический контейнер — это контейнер, состав которого полностью определяется на этапе компиляции.

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

Определение 4. Динамический контейнер — это контейнер, состав которого частично или полностью определяется на этапе выполнения.

По такой классификации, очевидно, существуют четыре вида контейнеров:

1. Статические однородные

   
   
   Сможете придумать пример?

   Обычный массив — int[n].

   
   

2. Статические неоднородные

   
   
   Примеры?

   Наиболее яркий пример такого контейнера — это кортеж. В языке C++ он реализуется классом std::tuple<...>.

   
   

3. Динамические однородные

   
   
   Догадались?

   Правильно, std::vector<int>.

   
   

4. Динамические неоднородные

   
   

   Вот об этом виде контейнеров и пойдёт речь в данной статье.

   
   

Знакомый линуксоид упрекнул меня, мол, в винде ни переключения языка Caps Lock'ом нет, ни даже раскладку нельзя отредактировать. Посмотрел я, и правда, все раскладки содержатся в файлах C:\Windows\System32\kbd*.dll, и редактировать такое hex-редактором ну никак не назвать удобным.

Как достичь удобства? Для переключения раскладок Caps Lock'ом можно использовать всякие навесные программы, тяжёлые вроде Punto Switcher, или простые вроде lswitch. Для редактирования раскладок есть MSKLC, но он малофункционален и неудобен, а аналоги вроде KbdEdit или KLM32 платные.

И тогда я решил написать на flat assembler'е код, собирающий DLL раскладки.

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

У меня тут синхронизируется VM надолго, поэтому есть время рассказать про то, что я недавно читал.
Например, про GoogLeNet.
GoogLeNet — это первая инкарнация так называемой Inception architecture, которая референс всем понятно на что:

(кстати, ссылка на него идет первой в списке референсов статьи, чуваки жгут)

Она выиграла ImageNet recognition challenge в 2014-м году с результатом 6.67% top 5 error. Напомню, top 5 error — метрика, в которой алгоритм может выдать 5 вариантов класса картинки и ошибка засчитывается, если среди всех этих вариантов нет правильного. Всего в тестовом датасете 150K картинок и 1000 категорий, то есть задача крайне нетривиальна.

Чтобы понять зачем, как и почему устроен GoogLeNet, как обычно, немного контекста.

Компьютерные системы с управлением без помощи контроллеров — новый этап во взаимодействии человека и компьютера. К этой области относятся технологии, воспринимающие физическую среду, включая распознавание жестов, распознавание голоса, распознавание лица, отслеживание движения, реконструкцию среды. Камеры Intel RealSense F200 и R200 реализуют ряд возможностей из этой области. Благодаря возможности съемки с определением глубины камеры F200 и R200 позволяют выстраивать трехмерную среду и отслеживать движение устройства по отношению к среде. Реконструкция среды вместе с отслеживанием движения позволяет реализовать возможности виртуальной реальности, в которой виртуальные предметы вписываются в реальный мир.

Цель этой статьи — ознакомление с автономной навигацией и описание ее применения в приложениях дополненной реальности. Разработанный пример использует камеру Intel RealSense R200 и игровой движок Unity 3D. Рекомендуется заранее ознакомиться с возможностями Intel RealSense SDK и Unity. Сведения об интеграции Intel RealSense SDK с Unity см. в статьях Разработка игр с Unity и камерой Intel RealSense 3D и Первый взгляд: дополненная реальность в Unity с Intel RealSense R200.