image

[Переклад першої частини перебуває тут.]

Успадкований код
Build — це видатний движок, а безліч ігор, які використовували його, принесли велику і заслужену славу і Кену Силверману, і 3D Realms.

Кен Силверман виконав умови договору: він надав двійковий файл приголомшливого 3D-движка з добре задокументованими методами і форматами ресурсів. Як визнання його заслуг 3D Realms вказала його ім'я в титрах як «Ken 'I can do that' Silverman» (Кен «Я можу це зробити» Силверман). Але розробка Build була зосереджена на можливостях і швидкості, а не зручність портування і читання. Після вивчення коду я думаю, що open source-розробники уникали його з наступних причин:

  • Його жахливо складно читати і отримувати з нього знання.
  • Він не був портируемым.
У цій статті я перерахував частину складнощів, з якими зіткнувся. Також я випустив порт Chocolate Duke Nukem 3D, покликаний вирішити ці проблеми. Я хотів, щоб люди запам'ятали, який рівень геніальності потрібен був для створення 3D-движка в той час. Крім того, я хотів, щоб вони усвідомили, як спонукуваний пристрастю підліток зміг внести вклад в одну найбільших ігор всіх часів.

Читати далі →

image

Пішовши з роботи в Amazon, я провів багато часу за читанням відмінного вихідного коду.

Розібравшись неймовірно чудовим кодом idSoftware я взявся за одну з кращих ігор всіх часів: Duke Nukem 3D і за її движок під назвою "Build".

Це виявився важкий досвід: сам движок має велику важливість і високо цінується за свою швидкість, стабільність і споживання пам'яті, але мій ентузіазм зіткнувся з вихідним кодом, суперечливим щодо упорядкованості, дотримання рекомендацій та коментарів/документації. Читаючи код, я багато дізнався про успадкованому коді і про те, що дозволяє програмного забезпечення жити довго.

Як звичайно, я переробив свої нотатки в статтю. Сподіваюся, вона надихне вас на читання вихідного коду і вдосконалення своїх навичок.

Читати далі →


: трасування каскадів воксельных конусів
Для The Tomorrow Children ми реалізували інноваційну систему освітлення, засновану на трасуванні воксельных конусів. Замість використання традиційних систем прямого або відстроченого освітлення ми створили систему, освещавшую все в світі трасуванням конусів через воксели.

Таким способом обробляється і пряме, і відбите освітлення. Він дозволяє нам розраховувати на PlayStation 4 три відображення глобального освітлення в полудинамических сценах. Ми трассируем конуси в 16 фіксованих напрямках через шість каскадів 3D-текстур і виконуємо поглинання світла за допомогою спрямованого затінення в екранному просторі (Screen Space Directional Occlusion) і сферичними окклюдерами динамічних об'єктів для отримання кінцевого результату. Движок також підтримує модель сферичного освітлення на основі гармонік, що дозволяє розраховувати освітлення частинок і реалізувати спецефекти, наприклад апроксимована підповерхневе розсіювання (approximating subsurface scattering) і преломляющие матеріали.

Читати далі →


Доброго часу, Хабр!

Купа часу пройшло з того моменту, як я написав свою першу статтю, і вже майже рік з того моменту, як прийшла в голову ідея для другої. В силу багатьох обставин (в першу чергу – ліні і забудькуватості), ця ідея так і не була реалізована раніше, але зараз я зібрався, написав весь цей матеріал і готовий представити його вашій увазі.

Почну з невеликої вступної. Будучи студентом 4-го, на той момент, курсу бакалаврату, я вивчав курс «Комп'ютерна графіка». Багато там було різних цікавих (і не дуже) завдань, але одне прямо особливо запало мені в душу: інтерполяцію кубічними сплайнами із заданими першими похідними на кінцях інтервалу. Користувач повинен був задавати значення перших похідних, а програма — вважати і виводити на екран интерполяционную криву. Особливість і основна складність завдання полягає в тому, що задаються саме перші похідні, а не другі, як у класичній постановці сплайн-інтерполяції.
Як я її вирішував, і до чого воно в підсумку прийшов, я як раз і викладу в цій статті. І так, якщо за описом завдання ви не зрозуміли ні в чому її сенс, ні в чому складність, не переживайте, все це я також постараюся розкрити. Отже, поїхали.

А, ні, стривайте один момент. Ось вам два числових ряду:
a) 2, 4, 6, 8, ?
b) 1, 3, ?, 7, 9

Які числа повинні стояти на місці питань і чому? Ви дійсно впевнені у своїй відповіді?

Читати далі →

Здравствуйте, дорогі мешканці Хабра! У цій публікації (а, швидше за все, і циклі) я розповім про мою реалізації одного з алгоритмів шифрування. Чому про реалізацію? Тому що ідея не нова, і стверджувати те, що задумка належить саме мені, не можна. Але спосіб досить цікавий, тому дізнатися про нього варто.

В цій частині я досить коротко опишу принцип роботи самого алгоритму і мою реалізацію.

Читати далі →

В минулому році в Академічному університеті пройшов перший конкурс студентських робіт з теоретичної інформатики та дискретної математики ім. Алана Тюрінга. Нещодавно ми оголосили другий конкурс (термін подачі робіт 10 травня 2017 року), а в цій статті ми розповімо про підсумки першого конкурсу.


Читати далі →

imageАлгоритми — це всього лише покрокові алгоритми рішення задач, і більшість таких задач вже були кимось вирішені, протестовані і перевірені. Можна, звичайно, поринути в глибоку філософію геніального Батога, вивчити багатосторінкові фоліанти з доказами та обґрунтуваннями, але хочете ви витрачати на це свій час?

Відкрийте чудово ілюстровану книжку, і ви відразу зрозумієте, що алгоритми — це просто. А грокать алгоритми — це веселе і захоплююче заняття.

Читати далі →

image
зрештою, я повинен був до цього прийти. Коли я опублікував статтю «Я написав швидку хеш-таблицю», а потім ще одну — «Я написав ще більш швидку хеш-таблицю». Тепер я завершив роботу над самою швидкою хеш-таблицею. І під цим я розумію, що реалізував самий швидкий пошук порівняно з усіма хеш-таблиць, які мені вдалося знайти. При цьому операції вставки та видалення також працюють дуже швидко (хоча і не швидше конкурентів).
Я використовував хешування за алгоритмом Robin Hood з обмеженням максимальної кількості наборів. Якщо елемент повинен бути на відстані більше Х позицій від своєї ідеальної позиції, то збільшуємо таблицю і сподіваємося, що в цьому випадку кожен елемент зможе бути ближче до своєї бажаної позиції. Схоже, такий підхід дійсно добре працює. Величина Х може бути відносно невелика, що дозволяє реалізувати деякі оптимізації внутрішнього циклу пошуку по хеш-таблиці.
Якщо ви хочете тільки спробувати її в роботі, то можете завантажити звідси. Або прокрутіть вниз до розділу «Вихідний код і використання». Хочете подробиць — читайте далі.
Читати далі →


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

Читати далі →