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

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

Внимание: просто рассматривать мой код, равно как и просто читать эту статью с чашкой чая в руке, смысла не имеет. Эта статья рассчитана на то, что вы возьмётесь за клавиатуру и напишете ваш собственный движок. Он наверняка будет лучше моего. Ну или просто смените язык программирования!

Итак, сегодня я покажу, как отрисовывать подобные картинки:

«Он снова это сделал!», — вот, что первое пришло мне в голову, когда я посмотрел на оборотную сторону флаера Pixar ^[1], полностью заполненную кодом. Скопление конструкций и выражений была подписана в правом нижнем углу не кем иным, как Эндрю Кенслером. Для тех, кто его не знает, скажу: Эндрю — это программист, придумавший в 2009 году 1337-байтный трассировщик лучей размером с визитку.

На этот раз Эндрю придумал нечто более объёмное, но с гораздо более интересным визуальным результатом. Так как я закончил писать свои Game Engine Black Books про Wolf3D и DOOM, у меня появилось время на изучение внутренностей его загадочного кода. И почти сразу меня буквально очаровали обнаруженные в нём техники. Они сильно отличались от предыдущей работы Эндрю, основанной на «стандартном» трассировщике лучей. Мне было интересно узнать о ray marching, функциях конструктивной объемной геометрии, рендеринге Монте-Карло/трассировкой пути, а также множестве других трюков, которые он использовал, чтобы ужать код в такой небольшой кусок бумаги.

Последние несколько недель я работал над реализацией алгоритма Форчуна на C++. Этот алгоритм берёт множество 2D-точек и строит из них диаграмму Вороного. Если вы не знаете, что такое диаграмма Вороного, то взгляните на рисунок:


Для каждой входной точки, которая называется «местом» (site), нам нужно найти множество точек, которые ближе к этому месту, чем ко всем остальным. Такие множества точек образуют ячейки, которые показаны на изображении выше.

В алгоритме Форчуна примечательно то, что он строит такие диаграммы за время $$ (что оптимально для использующего сравнения алгоритма), где $$ — это количество мест.

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

Как обычно, код выложен на github, а все использованные мной справочные материалы перечислены в конце статьи.

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

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

Всем привет!

Пока Леонид готовится к своему первому открытому уроку по нашему курсу «Администратор Linux», мы продолжаем рассказывать про загрузку ядра Linux-а.

Поехали!

Понимание работы системы, функционирующей без сбоев — подготовка к устранению неизбежных поломок

Древнейшая шутка в области ПО с открытым исходным кодом — заявление, что “код документирует сам себя”. Опыт показывает, что чтение исходного кода похоже на прослушивание прогнозов погоды: разумные люди все равно выйдут на улицу и посмотрят на небо. Ниже приводятся советы для проверки и изучения загрузки систем Linux с помощью знакомых инструментов отладки. Анализ процесса загрузки системы, которая работает хорошо, готовит пользователей и разработчиков к устранению неизбежных сбоев.

С одной стороны, процесс загрузки на удивление прост. Ядро операционной системы (kernel) запускается однопоточно и синхронно на одном ядре (core), что может показаться понятным даже жалкому человеческому уму. Но как запускается само ядро ОС? Какие функции выполняют initrd (диск в оперативной памяти для начальной инициализации) и загрузчики? И постойте, почему всегда горит светодиод в Ethernet-порте?

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

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

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

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

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

Часть 1. Математика

Введение

Мы так привыкли к взаимодействию с окружающим нас миром, что не задумываемся о том, насколько сложно двигаются наши руки и ноги. В академической литературе задача управления манипулятором робота называется инверсной кинематикой. Кинематика обозначает "движения", а понятие "инверсная" связано с тем, что обычно мы не управляем самой рукой. Мы управляем «двигателями», поворачивающими каждую отдельную часть. Инверсная кинематика — это задача определения того, как перемещать эти двигатели, чтобы сдвинуть руку в конкретную точку. И в своём общем виде эта задача чрезвычайно сложна. Чтобы вы понимали, насколько она сложна, то можете вспомнить о таких играх, как QWOP, GIRP или даже Lunar Lander, в которой вы выбираете не куда двигаться, а какие мускулы (или ускорители) приводить в действие.

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

Здравствуйте. Несколько недель назад я начинал серию переводов статей по изучению OpenGL. Но на 4 статье один хабровчанин заметил, что мои переводы могут нарушать лицензию, по которой распространяются учебные материалы, предоставленные в исходной статье. И действительно, мои переводы нарушали лицензию. Для разрешения этой проблемы я обратился к авторам того набора уроков, но так и не смог добиться нормального ответа. По этой причине я связался с автором другого, не менее (а возможно даже и более) крутого, набора уроков по OpenGL: Joey de Vries. И он дал полное разрешение на перевод его набора уроков. Его уроки гораздо более обширные, чем прошлый набор, поэтому эти переводы растянутся на долго. И я обещаю, будет интересно. Заинтересовавшихся прошу под кат.

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

На счет уроков по Vulkan: к сожалению мне тяжело сейчас написать уроки по данному API по причине скудной видеокарты на данный момент, которая просто не поддерживает Vulkan API, поэтому уроки по данному API будут только после обновления видеокарты.

Сглаживание

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


Беглый взгляд, возможно, и не заметит ничего, но стоит посмотреть внимательней и на гранях куба проявятся означенные зазубрины. Попробуем увеличить изображение:


Нет, это никуда не годится. Разве такое качество изображения хочется видеть в релизной версии своего приложения?

Йо-хо-хо, хабровчане!

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

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

Я помню тот момент, когда подумал «Как же медленно всё работает, что если я распараллелю вызовы?», а спустя 3 дня, взглянув на код, ничего не мог понять в жуткой каше из потоков, синхронизаторов и функций обратного вызова.

Тогда я познакомился с asyncio, и всё изменилось.

Данная статья основана на материале из различных статей по CQRS, а также проектов, где применялся такой подход.

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

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

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

В действительности же честный PBR сделать достаточно сложно, потому что легко достичь похожего результата, но сложно правильного. И в интернете полно статей, которые делают именно похожий результат, вместо правильного. Отделить мух от котлет в этом хаосе становится сложно.
Поэтому цель статьи не только разобраться, что же такое PBR и как он работает, но и научиться писать его. Как отлаживать, куда смотреть, и какие ошибки типично можно допустить.
Статья рассчитана на людей, которые в достаточной мере уже знают hlsl и неплохо знакомы с линейной алгеброй, и можете написать свой простейший неPBR Phong свет. В общем я постараюсь как можно проще объяснить, но рассчитываю на то, что некоторый опыт работы с шейдерами вы уже имеете.

Проблема

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

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

Адаптивность методов повышения точности динамических измерений следует понимать, как использование прогнозирования значений дисперсий и погрешности для следующего цикла измерений. Такое прогнозирование осуществляется в каждом цикле измерений. Для этой цели применяются фильтры Винера, работающие в частотной области. В отличии от фильтра Винера, фильтр Калмана работает во временной, а не в частотной области. Фильтр Калмана был разработан для многомерных задач, формулировка которых осуществляется в матричной форме. Матричная форма достаточно подробно описана для реализации на Python в статье [1], [2]. Описание работы фильтра Калмана, приведенная в указанных статьях, рассчитана на специалистов в области цифровой фильтрации. Поэтому возникла необходимость рассмотреть работу фильтра Калмана в более простой скалярной форме.

Картинки из сети, качество желает лучшего, но они достаточно точно отражают суть опыта по визуализации фигур. Зри в корень – основа мудрости поколений.

Немного истории

Ещё в школе на уроках физики я вглядывался в осциллограф, на экране которого, сменяя друг друга, появлялись разные фигуры: сначала простые – линия, парабола, круг, эллипс, потом фигуры становились всё более насыщенные непрерывными волнообразными линиями, напоминающие мне кружева. Автором этого кружевного дива был Жюль Антуан Лиссажу французский физик, член — корреспондент Парижской АН (1879) [1]. Сами фигуры — это замкнутые траектории, прочерчиваемые точкой, совершающей одновременно два гармонических колебания в двух взаимно перпендикулярных направлениях [2]. Думаю, что в те далёкие от современности годы основной заслугой Жюля, кроме конечно накопленных опытом знаний математики и физики, была простая механическая визуализация этих фигур подручными средствами. Захотелось конструировать подобно Жулю максимально просто и наглядно, реализовать его идеи применительно к современной задаче линейных измерений. Но сделать это путём математического моделирования с графической визуализацией его результатов на Python. Но сначала рассмотрим классический вариант [3] построения фигур.

В данной публикации представлена инструкция по моделированию электрической цепи методом переменных состояния.

От экрана дизайнера к экрану игрока

Карты разрабатывались дизайнером уровней в 2D с помощью редактора Doom Editor (DoomED). LINEDEFS описывали замкнутые секторы (SECTORS в исходном коде), а третье измерение (высота) указывалась посекторно. Первый уровень Doom E1M1 выглядит так:



После завершения работы над картой она нарезается методом двоичного разбиения пространства (Binary Space Partitioning, BSP). LINEDEF рекурсивно выбирались и их плоскости превращались в секущие плоскости. То есть LINEDEF разрезались на сегменты (SEGS) до тех пор, пока не оставались только выпуклые подсектора (SSECTOR в коде).

Интересный факт: И DoomED, и iBSP писались на… Objective-C на рабочих станциях NextStep. Пятнадцать лет спустя тот же язык почти в той же операционной системе выполняет игру на мобильном устройстве! [прим. пер.: в 2010 году Doom вышел на iPhone] Я немного поработал веб-археологом и мне удалось найти исходный код idbsp. На него стоит посмотреть.

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



Во многих процедурных генераторах карт, в том числе и некоторых моих предыдущих проектах, для генерирования карты высот используются функции шума (midpoint displacement, фракталы, diamond-square, шум Перлина и т.д.). Здесь я их не применял. Вместо неё я использовал структуру графов для моделирования элементов, определяемых ограничениями геймплея (высота, дороги, течение рек, места квестов, типы монстров) и функции шума для моделирования того, что не ограничивается геймплеем (форма побережья, расположение рек и деревьев).

— Не понимаю, почему люди так восхищаются этим Карузо? Косноязычен, гугнив, поёт — ничего не разберешь!
— А вы слышали, как поёт Карузо?
— Да, мне тут кое-что из его репертуара Рабинович напел по телефону.

Детектив по материалам IT. Часть первая

Я осознаю, что писать очередную статью на тему Модель-Вид-Контроллер это глупо и вредно для «кармы». Однако с этим «паттерном» у меня слишком личные отношения – проваленный проект, полгода жизни и тяжелой работы «в корзину».

Проект мы переписали, уже без MVC, просто руководствуясь принципами – код перестал быть похож на клубок спагетти и сократился наполовину (об этом позже, в обещанной статье про то, как мы применяли «принципы» в своем проекте). Но хотелось понять, что же мы сделали не так, в чем была ошибка? И в течении долгого времени изучалось все, что содержало аббревиатуру MVC. До тех пор пока не встретились исходные работы от создателя – Трюгве Реенскауга…

И тогда все встало на свои места. Оказалось что фактически на основе принципов мы пере-изобретали «original MVC». А то, что зачастую преподносится как MVC, не имеет к нему никакого отношения… впрочем также как и к хорошей архитектуре. И судя по тому сколько людей пишет о несостоятельности «классического MVC», спорит о нем и изобретает его всевозможные модификации, не одни мы столкнулись с этой проблемой.

Более 30 лет собранные в MVC идеи и решения остаются наиболее значимыми для разработки пользовательских интерфейсов. Но как ни странно, несмотря на существующую путаницу и обилие противоречивых трактовок, разработчики продолжают довольствоваться информацией «из вторых рук», черпая знания о MVC из википедии, небольших статей в интернете и фреймворков для разработки веб-приложений. Самые «продвинутые» читают Мартина Фаулера. И почему-то почти никто не обращается к первоисточникам. Вот этот пробел и хотелось бы заполнить. И заодно развеять некоторые мифы.

Статья на перевод предложена alessandro893. Материал взят с обширного справочного сайта, описывающего, в частности, принципы работы и устройство радаров.

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


Слева – изотропная антенна, справа – направленная

Дипольная антенна