Дмитрий Артимович
Я – хакер! Хроника потерянного поколения
Троян должен был стащить файл с паролями от почтового клиента и отправить на мой адрес.
Настройки почтового сервера позволяли подменять отправителя в письме, что я и сделал. К сожалению, человек, от имени которого я разослал это письмо, оказался дома, и всю затею мне испортил.
Электронная доска объявлений: первый взлом
Кроме электронной почты, у нас в городе работала BBS (Bulletin Board System). Это электронная доска объявлений, проще говоря, система, которая использовалась для общения пользователей по телефонным линиям – через модем.
У нашей BBS телефонная линия была одноканальная, то есть общаться можно было только с оператором системы, сисопом[6].
Подключались к BBS с помощью так называемого модемного терминала. Это текстовое окно, похожее на Telnet. Вы отправляете команду напрямую модему, например, ATDP 8945444333 – набрать в импульсном режиме номер 8945444333 (Dial Pulse). После соединения на экране появлялось приветствие в виде разноцветного текста.
Там можно было поболтать, залить или, наоборот, скачать файлы. У этой BBS-ки был режим командной строки – практически тот же MS-DOS. Вы могли ходить по каталогам, где лежали файлы для скачивания. Еще там была та же досовская команда «type»[7]. А вот команда «cd C:», смена диска на C:, от непривилегированного пользователя, естественно, вызывала ошибку «недостаточно прав».
Разговорившись с сисопом, я скачал софт, который он использовал, – Tornado BBS.
Запустив Tornado BBS у себя на компьютере, я занялся исследованием. И практически сразу обнаружил две ошибки. Во-первых, при вводе неверного пароля Tornado BBS писал в лог следующее: «Введен пароль X вместо Y», где Y – истинный пароль. Во-вторых, команда type (вывод содержимого файла) не проверяла привилегии пользователя. То есть можно было легко прочитать любой файл на диске C:.
Пазл сложился, вот оно! Достаточно было совершить неудачную попытку входа в BBS от админа, после чего под обычным пользователем вывести лог. Это я и сделал ночью.
Имея пароль админа, я получил доступ ко всему диску компьютера. Но, честно говоря, ничего интересного там не нашлось. И, скачав файл с паролями других пользователей, потерев лог, я, полный удовлетворения, отключился.
Подсоединившись к BBS на следующий день, я зашел в систему под чужим аккаунтом. Решил поболтать с сисопом:
– Привет, как дела? – написал я.
– Да вот, меня вчера похакали.
– Неужели? Что-то стащили?
– А вот, ты и попался. С человеком, чей это аккаунт, я говорил час назад по телефону!
– Ладно, раскусил.
В общем, мы подружились. Я рассказал про ошибки. Позже мы частенько играли с ним по модему в Quake World.
На нем же я попробовал Win95 Nuke – и он отлично сработал. Windows просто вылетала в синий экран.
Visual Basic
После Pascal я взялся за язык программирования Visual Basic. Мой брат купил книжку по Visual Basic 6.0. Подкупало тем, что на нём можно было визуально рисовать окна и элементы на них. И очень просто обрабатывать события: щелчки мышкой, ввод с клавиатуры и т. д. Щелкаете по любому элементу, в открывшемся окне выбираете событие, пишете его обработчик.
Позже, как только я перешел на Visual C, я не мог понять, как же тут добавить окно и написать обработчик его событий? Почему он тоже «вижуал», но тут все по-другому.
На Visual Basic было легко написать простейший калькулятор, редактор текста. Но для серьезных проектов он не годился – он был медленный и тащил кучу библиотек с собой.
Хороший язык… для детей. Так пришло понимание, что для серьезного программирования нужно что-то еще.
Хакеры выбирают ассемблер и C/C++
Линус Торвальдс написал Linux на C и ассемблере. Выбор был очевиден.
Сначала я осуществил свою детскую мечту и стал изучать ассемблер. Компилятором был выбран TASM (Turbo Assembler). Для тех, кто не знает, ассемблер – язык программирования низкого уровня. Это система обозначений, используемая для представления в удобочитаемой форме программ, записанных в машинном коде. Другими словами, это самый низкий уровень. Здесь нет стандартных функций «вывести строчку на экране», «получить ввод от пользователя». Все это доступно через вызовы к операционной системе. Например, в MS-DOS, с чего я и начал изучение ассемблера, вызовы к ядру были реализованы через прерывание INT 21H.
Любая ошибка на языке ассемблера может привести к краху всей программы. Поэтому, если вы хотите стать настоящим профи, – вы обязаны понимать, как функционирует CPU, как он обращается к памяти, как он работает с устройствами и многое другое. Этот хороший опыт помог мне потом писать высоконагруженные и производительные системы при минимуме системных требований.
Как раз хорошим дополнением к учебнику по ассемблеру стала книга про архитектуру x86-процессоров. Вы знаете, что Биллу Гейтсу приписывают фразу «640 КБ памяти всем хватит»? Откуда взялось ограничение в 640 КБ памяти, как процессоры, начиная с 286-го, его обходили, как появилась многозадачность и защищенный режим работы процессора, скалярность и суперскалярность? Все это должен знать настоящий профи.
Конечно, на ассемблере сейчас уже не напишешь игру, да и хоть сколько-нибудь сложный проект. Этот язык в основном используется для тех случаев, когда нужно сделать что-то очень небольшое, элегантно, на низком уровне, и обычно в виде вставок в код C/C++.
Уже давно даже новые версии компиляторов языка C пишут на самом C.
Поэтому я принялся изучать язык C и сразу C++ по книгам Герберта Шилдта.
Первое мое более-менее серьезное творение – мини-операционная система. Загрузчик, написанный на ассемблере, записывался на первую дорожку дискеты размером 3,5 дюйма и загружал ядро, написанное на C. Ядро на C переводило процессор в многозадачный 32-битный режим. И на этом, в общем-то, все.
Но это реально круто. Я был горд собой! Даже такая простая вещь требовала хороших знаний системного программирования и архитектуры процессора.
Half-Life
В 1998 году выходит игра Half-Life. Эта игра поменяла очень много в отрасли. В отличие от темного Quake, коридоры и комнаты в Half-Life выглядели светлыми и совсем как настоящие.
Half-Life,разработчик Valve Corporation, издатель Valve Corporation, 1998
Подавляющая часть игр использует технологию Lightmaps.
Lightmap – метод освещения пространства в 3D-приложениях. Он заключается в том, что создается текстура, содержащая информацию об освещенности трехмерных моделей. Метод значительно экономит ресурсы компьютера, поскольку приложению не приходится рассчитывать падение света в режиме реального времени.
Так вот, первые игры, в которых начали считать освещение, подобные Quake, были ужасно темными – рядом с источником света светло, а в тени ничего не видно. Всё потому, что освещение рассчитывалось до первого падения луча на поверхность, без отражения. И мозг постоянно говорил, что здесь как-то нереалистично, что-то здесь не так.
Quake,разработчик id Software, издатель GT Interactive, 1996
А вот Half-Life одним из первых стал рассчитывать Lightmaps, учитывая отраженный свет. То есть тень теперь не была идеально черной, она стала реальной, «живой». Алгоритм расчета отраженного освещения называется Radiosity.
Суть Radiosity состоит в том, что все поверхности сцены разбиваются на небольшие фрагменты – патчи, каждый из которых наделен свойствами излучать, поглощать и отражать свет. Процесс вычисления освещения по алгоритму Radiosity состоит из набора итераций[8], каждая из которых уточняет результат расчета. Для отдельного патча на сцене подсчитывается полученная им от других патчей энергия, а также доля этой энергии, которая будет излучена патчем на следующей итерации.
В результате алгоритм Radiosity позволяет получать реалистичные эффекты вторичных отражений, неточечных источников света, мягких теней и т. д.
Half-LIfe получился настолько удачным, что к нему создали даже несколько модов, некоторые из которых показывали сюжетную линию глазами других персонажей. Один из самых удачных модов для игры по сети – это Counter-Strike.
Несколько лет спустя вышел Half-Life – 2. И опять разработчики из Valve сделали прорыв – они добавили реалистичную физику на движке Havok. Теперь брошенная банка из-под газировки не просто падала и прилипала к полу, а реалистично отскакивала, ящики плавали на воде, а убитые противники эффектно перекатывались по ступенькам лестницы.
Олимпиада
10-й класс. Мы сидим в кабинете физики, ждем начала урока. Заходит Виктор Валентинович, наш учитель: «Ребята, сегодня вы будете решать олимпиадные задачки. Кто наберет больше баллов, тот пойдет выступать за школу в район».
Задачи я решил достаточно быстро. А вот будущие золотые медалисты осадили меня и чуть ли не вырывали тетрадь: «Дай списать! Дай списать!». Внутренний голос завопил: «Это же не контрольная! Это олимпиада!». И тут я во весь голос закричал: «Отстань! Решай сам!». Сработало. Учитель обратил на нас внимание. А я заработал больше всех баллов в школе и в районе. Мне предстояла поездка в Питер на Ленинградскую областную олимпиаду.
В областной центр нас отправили группой на «девятке» – трое детей с 9 по 11-й класс и учитель. Было это зимой. Выезжали мы рано утром. Всю дорогу мело – видимость почти нулевая. Олимпиада проходила два дня – теория и практика. В первый день вечером мы возвращались домой, на следующий опять ехали в Питер. Ко второму дню остался только я и мой учитель физики. Ехать туда было страшно, внутренний голос постоянно нагнетал, что я не справлюсь и что хочу домой к маме. Позже, в следующем году, я ездил туда на олимпиаду и по информатике, и по физике.
Два раза я занимал призовое третье место в Ленинградской области по физике и четвертое место – по программированию. Места по программированию обычно занимали ребята из Выборга. Причем победитель прошлогодней олимпиады приезжал вне конкурсного отбора, поэтому от Выборга было два претендента, так они и спихнули меня на четвертое место.
На следующий день я увидел в холле школы поздравление с призовым местом. Это была моя личная победа. Я вспомнил все те же слова – «такого дурака взяли». А может, и не дурака?
Университет
ПУНК
В конце августа 2002-го я вместе с матерью стоял на крыльце общежития № 14 Петергофского учебно-научного комплекса (ПУНК). Светило солнце, погода была хорошая для конца лета. Мне было страшно. На крыльце мы ждали, когда закончится обед, чтобы попасть на распределение в общежитие к коменданту. Вокруг суетились другие студенты, вернувшиеся с каникул. Мой брат уже переходил на третий курс, а мне только предстояло пойти на первый.
Моя мать часто говорила обо мне в детстве: «Он маленький и несамостоятельный». Вот и сейчас я был скромным, застенчивым ребенком, покидающим родной дом и вступающим в самостоятельную жизнь. Мы добрались в ПУНК на старой машине моего отца, когда-то купленной в кредит под космические проценты Сбербанка – за $700–800. «Жигули»-тройка были 75-го года, желтого цвета, модель «финка» – для экспорта. Что стоит отметить, кузов был сделан из толстенной стали, с которой даже рядом не стояли те консервные банки, которые делают многие автопроизводители сейчас.
Поступил я на физический факультет Санкт-Петербургcкого государственного университета в 2002 году без экзаменов. Меня взяли за мои дипломы с областных олимпиад по физике. Я просто отправил сканы по электронной почте на адрес приемной комиссии, и мне ответили, чтобы я приезжал.
Наш студенческий городок состоял из комплекса общежитий: шесть четырнадцатиэтажных домов, стоящих кругом, и несколько сооружений поменьше. Замыкал кольцо общежитий Дворец культуры и науки, который студенты называли коротко – «шайба». Там крайне редко проводили мероприятия или дискотеки. Здания самих факультетов – физического (физфак), химического (химфак), прикладной математики и процессов управления (ПМПУ) и математико-механического (матмех) – находились чуть дальше, через небольшую зеленую зону.
Студенты физфака располагались в четырнадцатиэтажном здании общежития с цифрой 14. Корпус № 15 занимал ПМПУ, № 16 – семейное общежитие и т. д.
Общежития практически не ремонтировались, стояли они так с 80-х. В основном ремонт комнат делали сами студенты. Картина была удручающая: обшарпанные стены, старые лифты, половина из которых не работает.
На каждом этаже четырнадцатиэтажки было три крыла. В них находилось несколько блоков по две комнаты (на троих и на двоих человек) и общий раздельный санузел. Если комнаты студенты ремонтировали сами – клеили обои, красили шкафчики, то туалет и душевая были просто страшные. Старая пожелтевшая плитка на стенах, жуткая плитка на полу, проржавевшие краны и решетки, сливы в черной масляной грязи.
На всё крыло одна кухня, ключ от которой нужно было еще достать. Обычно старшекурсники пользовались кухней, а первокурсники готовили прямо у себя в комнате на электрической плитке. Запах еды стоял по всему блоку.
Кровати в комнатах были железные, советские, односпальные, с провисшей сеткой. Такие кровати ставились повсеместно – в детских лагерях, на турбазах, а также на зонах. Спать на ней было практически невозможно – сетка не держала вес. Поэтому под матрас на железный каркас кровати подкладывали либо доски, либо двери, оставшиеся после ремонта. Мне отец привез листы ламинированного ДСП. По-моему, это были боковины старых парт.
Здания факультетов вызывали, с одной стороны, ностальгические воспоминания о детстве – большие окна с алюминиевыми рамами, прямо как советские магазины и дома культуры. С другой стороны, печаль и уныние: аудитории, которые не ремонтировали вечность, но в них установили подвесной потолок Armstrong, исцарапанные кафедры, туалеты все черные, с разбитой сантехникой и без кабинок. За три курса я заходил по-маленькому в такой туалет от силы раза два. Там было просто противно. Пары вели старенькие преподаватели, люди науки в потертых пиджаках, с дешевыми портфелями, набитыми тетрадками.
На первом курсе я учился на хорошо и имел копеечную стипендию – где-то несколько сотен рублей в месяц. В общем-то, на нее можно было полтора-два раза сходить в столовую. И всё.
В середине недели я звонил домой из отделения связи в соседнем общежитии. Это было такое помещение с десятком кабинок. Звонок оплачивался как междугородний. Сотового телефона у меня тогда не было, он появился позже.
На выходные я уезжал домой. Электрички до Балтийского вокзала ходили примерно раз в полчаса. Платформа располагалась в лесу, примерно в километре от общежитий. Сама же поездка занимала минут 45. Очень часто мы, студенты, не платили за проезд, а просто на остановке, ближе к вокзалу обходили кондуктора по платформе. Денег катастрофически не хватало.
От Балтийского вокзала ходили автобусы до Кингисеппа. В пятницу вечером скапливалась огромная очередь перед кассами. И если обратный билет не был куплен заранее, то в очереди можно было провести несколько часов.
Часто к очереди подходили бомбилы и предлагали за 200–250 руб. на «Жигулях» доехать до Кингисеппа. Билет на автобус стоил тогда около 100 руб.
– Поеду за 150, – сказал я очередному бомбиле.
– Только если в багажнике…
Дома я полноценно проводил только субботу, в воскресенье уже нужно было возвращаться тем же путем назад, в университет. В 18:00 от вокзала Кингисеппа отходили от четырех до шести автобусов в Питер. Часто выходило так, что на одно место продавали по несколько билетов. Автобусы, по большей части, были старые. Один раз я ехал на сиденье со сломанной спинкой и два часа провел в страшном напряжении.
По вечерам в пятницу и субботу мы ходили с отцом на охоту – на уток, на зайцев. Поэтому я так и рвался домой. В общежитии у меня не было компьютера, так что я не мог убивать выходные в комьютерных игрушках, как делали многие.
Назад, в общагу, я тащил с собой большую сумку с колбасой, соком, сыром. Не знаю, почему мать давала продукты, а не деньги. Ведь то же самое я мог купить на месте. Видимо, она считала, что может купить лучше и дешевле, чем я.
Всем своим видом обстановка в университете демонстрировала мрачные перспективы – сомнительное будущее аспиранта, копеечную зарплату и переезд в семейное общежитие.
Хотя были и положительные моменты. На лабораторных работах иногда мы делали интересные опыты, например с жидким азотом. Температура жидкого азота составляет -195,75 градуса. Если туда поместить что-то органическое, например листочек растения, то вода, содержащаяся в нем, моментально замерзает. И такой лист можно расколоть о стол, прямо как в голливудовских боевиках, когда хороший герой засовывает руку злодея в жидкий азот, а потом разбивает. Если же быстро вставить и вытащить палец из азота, он не успевает замерзнуть. Азот начинает кипеть, образуя воздушную прослойку между кожей и холодным телом. Такой фокус показал нам преподаватель. Главное, делать все быстро.
Ремонтировать общежития никто не спешил. Зато позже вокруг нас возвели здоровенный забор из бетонных плит и поставили пропускной пункт. Назначение сего сооружения для меня так и осталось загадкой. Деньги, потраченные на строительство забора, можно было бы пустить на ремонт комнат или благоустройство территорий. Хотя некоторые предположения о нецелевом расходовании выделенных средств у меня все-таки были.
Сидя на лекции по математическому анализу и слушая про производные и интегралы, я думал: «Зачем они мне? Что мне с ними делать? Я хочу жить в своей квартире! Как все это мне поможет?». Так, мой интерес к науке постепенно угасал. На третьем курсе я уже перестал ходить на лекции и любые другие занятия.
Гиря
С собой из дома в общежитие я привез сделанную отцом штангу и 16-килограммовую гирю. Штанга представляла собой железную трубу с обкрученными синей изолентой местами для хвата и приваренными по бокам половинками кардана от машины. Кардан я нашел дома за гаражом, по диаметру он идеально подошел под «блины». Я распилил его ножовкой по металлу на две части, которые отец приварил на тонкую трубу. С внутренней стороны к половинкам отец приварил по два блокирующих прута, чтобы «блины» фиксировались. А для их фиксации с наружной стороны он по бокам насверлил дырок. Мы согнули буквой «Г» использованные электроды от сварки. Вот это-то я и вставлял в дырки, чтобы заблокировать «блины». Самих» «блинов» было всего четыре: два по 10 килограмм и два – по 20.
Качаться я начал еще в 9-м классе, чтобы избавиться от неуверенности и страха. Ведь меня обязательно побьют, если я выйду на улицу, как говорила моя мать.
На втором году обучения ребята из Ангарска позвали меня в качалку – небольшое помещение, смежное со спортзалом, в корпусе матмеха. Качалка представляла собой обшарпанную комнату с грудой железа, несколькими скамьями для жима и 3–4 тренажерами. А что, собственно, еще нужно? Это была лучшая качалка из тех, в которые я ходил.
Этажом ниже в комнате под нами жили студенты, плохо дружившие с головой. Имея колонки 100 Вт, они могли слушать музыку аж в два-три часа ночи. В ответ на это мы бросали штангу на пол. Возможно, правильнее было бы пойти и просто поговорить с ними. Но…
На очередных выходных, которые я провел дома, мои соседи последовали моему примеру и стали бросать гирю на пол при очередном концерте. Пришли ребята снизу и забрали эту гирю. При этом они еще настучали коменде, что нарушаем порядок мы.
Вернувшись в общагу, я рассказал об этом своему брату. Брат предложил сходить вниз и забрать украденное. Мне же он рекомендовал надеть маечку, чтобы были видны мои мускулы. Вообще, тогда я производил впечатление «не подходи к нему, а то прибьет». Только это скорее была защитная реакция от неуверенности. Я никогда ни с кем не дрался, да и где мне было драться? Во двор меня не пускали.
Мы спустились вниз. Позвонили в дверь, выглянули два парня:
– Где гиря? – спросил брат.
– Тут ее нет.
– Давай, неси. У тебя есть 15 минут.
Они закрыли дверь. Брат ударом руки сломал звонок, сделанный из мышки. Хоть что-то.
Через 30 минут в дверь постучали – выходите. В холле собралось человек 30. Брат Игорь взял пустую стеклянную бутылку и вышел. Я последовал за ним.
Бах – Игорь разбил бутылку о стену. В рухак у него красовалась розочка:
– Что, твари, охуели? Где гиря?
Адреналин зашкаливал, меня трясло. Я лихорадочно пытался прикинуть, сколько человек я сумею вырубить перед тем как вырубят меня, и чем это все закончится.
После некоторого препирательства толпа стала расходиться. Конфликт иссяк. Гирю нам так и не отдали. Я раньше никогда не замечал, что существует некий тип людей, которые, даже когда они совершенно не правы, постараются сделать виноватым тебя. Гнилой тип людей.
Зато урок разборок я получил хороший – тот урок, которого мне так не хватало в детстве.
Мексиканец
Во втором семестре первого курса к нам подселили мексиканца – Виктора Уго. Уго мечтал получить образование у нас в России и работать преподавателем на родине в Мехико, но с успеваемостью у него было плохо. Зато он рассказывал интересные истории: сколько травы он курил на родине, как учил русский мат и тому подобное.
Вроде бы все хорошо. Но был один маленький минус: Уго считал, что он тут как бы не живет, поэтому не будет убираться в блоке. А если мы хотим, то можем это делать сами. Его слова привели меня в ярость. Я со злостью кинул ему веник и сказал, что теперь он убирается здесь каждую неделю. Так он и делал следующие полгода. Видимо, я действительно производил тогда впечатление «не подходи, а то прибью».
Как-то днем я был один в комнате. В дверь постучали. Я открыл:
– Виктор дома? – с акцентом спросила загорелая девушка приятной латинской внешности.
– Нет, – ответил я и закрыл дверь.
Вечером мексиканец рассказал мне, что та девушка спрашивала про некоего накаченного парня. Я ей понравился. Какой же тормоз я был тогда!
Сеть
Завершив первый курс хорошо, я собрался домой. По дороге нужно было снять в Сбербанке стипендию за весь учебный год. Проторчал я в кассе около часа, подписывая кучу ненужных бумаг. В итоге мне выдали около 3000–4000 рублей.
Я решил, что мне все-таки нужен компьютер в общежитии. На новый денег не хватало, пришлось покупать б/у. Конфиг был практически такой же, как и домашний – процессор Celeron, 20 Гб винчестер, монитор чуть побольше 17 дюймов. Монитор был с кинескопом, имел плоский экран, но и дефект – во включенном состоянии на экране постоянно светились две горизонтальные тонкие линии. Стоил этот компьютер 6000–7000 рублей. Недостающие деньги мне дали родители.
Подключение к сети в общаге стоило денег – нужно было оплатить стоимость сетевого кабеля и работу по его прокладке. Этот вариант мне не подходил – денег не было совсем. Я жил на то, что давали родители, а на выходных мотался домой за продуктами. Поэтому вопрос с подключением я решил через Валю, моего соседа из другого блока. Он был подключен к общей сети, и в его компе было два сетевых адаптера. Через окно мы кинули сетевой провод, он воткнул его в свой системник и настроил мост. Я же прикупил себе дешевую сетевую карту PCI и вставил в свой блок.
Интернет у нас был дорогой штукой с оплатой за мегабайты, поэтому фильмы, музыку и программы мы искали в общей сети. Для размещения файлов использовали протокол Samba (виндовская шара). Каждый пользователь задавал имя своего компьютера и рабочую группу. Группы именовались по номерам общежитий: 14, 15, 16 и т. д. Заходя в группу № 15, можно было видеть компьютеры из 15-го общежития, а на компьютерах в открытых папках лежали фильмы, музыка, программы и т. п.
Для общения пользователей в сети использовался Windows Messenger Service, работавший по протоколу NetBEUI over TCP/IP. Под него писали различные мессенджеры сами студенты. Отправлять сообщения можно было как на конкретную машину, так и на всю группу.
А для поиска файлов по расшаренным каталогам в сети были свои поисковые машины. Такая поисковая машина представляла собой сервис, который последовательно перебирал все компьютеры из каждой группы и заносил в свою базу данных названия всех файлов. А также это был веб-интерфейс, позволяющий искать файл по маске названия и выдавать конечные пути на файлы.
Один из таких поисковиков ради интереса написал и я, на C++. Название я выбрал броское – НихуЯндекс, с соответствующим слоганом «Нихуя не найдется».
Мой сканирующий сервис не использовал сторонние базы данных, такие как MySQL, а просто писал все данные в файл на диске. Серверное приложение было написано на том же C++ под Apache. Конечно, топорное решение, но изучать PHP или подобный язык для небольшого сервиса тогда сильно не хотелось.
От других поисковиков мой отличался еще одной функцией: он читал сообщения, приходящие из сети, и, сверяясь со словарем, выделял в них мат и составлял рейтинг самых матерящихся машин в сети. Штука малополезная, зато смешная.
Графика
Начиная с последних классов школы, я увлекся компьютерной графикой. Меня очень интересовало, как отрисовываются объекты в таких играх как Doom, Quake, Half-Life. Ведь экран компьютера – это просто область памяти, в которой последовательно хранятся цвета пикселей. Компьютер не знает, что этот шар находится ближе к наблюдателю, чем тот куб. Более того, на игровой сцене могут быть тысячи статических и двигающихся объектов. Если рисовать их все, даже те, что не видны из данного ракурса, отрисовка одного кадра с ними может занять продолжительное время. А для нормального восприятия виртуального мира нужно обеспечить хотя бы 25–30 кадров в секунду.
Кроме того, отрисовка виртуального мира – это не единственная задача, которую решает компьютер. Еще нужно подумать за противников, передвинуть предметы, а если игра с реалистичной физикой, так еще и пересчитать весь физический мир. Как все это возможно?
Изучать разработку игр я начал с библиотеки OpenGL. Она позволяет достаточно просто рисовать трехмерные объекты на двухмерном экране. Настраиваете камеру (изометрическую или перспективу), загружаете текстуры, передаете в библиотеку трехмерные координаты граней, и она отрисовывает их на экране. Все преобразования в таких библиотеках (то же самое Direct 3D) в конечном итоге сводятся к перемножению матриц. Поэтому трехмерная графика так хорошо распараллеливается и рассчитывается на графических процессорах, как раз и заточенных под операции с матрицами.
Возвращаясь к примеру иллюстрации сверху – если сначала отрисовать куб, а потом сферу, все будет так, как надо. А вот если сделать это наоборот, то куб перекроет сферу, хоть и находится позади нее. Все это потому, что компьютер не знает, кто дальше находится от наблюдателя и кого нужно рисовать первым. Конечно, мы можем рассчитывать расстояния до объектов на каждом кадре, но что делать, если объектов слишком много, расчет расстояний для них становится затратным или объекты пересекаются (на рисунке куб заслонил сферу – возникнет артефакт)?
Самый простой алгоритм отсечения невидимых поверхностей – Z-буфер. Идея алгоритма в том, чтобы для каждого видимого пикселя на экране хранить его глубину, координату Z. При отрисовке глубина или значение Z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если новый пиксель расположен ближе к наблюдателю пикселя, находящегося в буфере кадра, то новый пиксель отрисовывается, а значение Z для него обновляется. Если же сравнение дает противоположный результат, то никаких действий не производится. Главное преимущество этого алгоритма – простота, так как все нужные расчеты выполнит сама графическая библиотека и графический ускоритель (при его наличии).
Конечно, такие игры как Quake и Half-Life, имели и программный визуализатор: в них, при отсутствии графического ускорителя, вся графика считалась на центральном процессоре.
Поэтому следующим моим шагом стало изучение алгоритмов, лежащих в основе визуализации Quake. Id Software (разработчик Quake) внесли много передовых технологий в разработку игр. Для визуализации виртуального мира они одними из первых использовали бинарное разделение пространства, популяризовав его.
Алгоритм двоичного разделения пространства (BSP – Binary Space Partition Tree) был первоначально разработан как эффективный метод упорядочивания множества многоугольников для решения проблемы определения видимых поверхностей. Алгоритм использует начальный этап предварительной обработки, что существенно экономит ресурсы при визуализации сцены.
Пусть дан набор многоугольников S = {s1;…; sn}. Мы можем построить BSP-дерево и разделить трехмерное пространство с использованием следующего простого рекурсивного алгоритма. Выбираем многоугольник из множества S. Плоскость, определяемая этим многоугольником, используется для создания корня дерева и делит пространство на два подпространства: заднее и переднее. Ссылка на многоугольник также сохраняется в узле дерева. Остальные многоугольники помещаются в два множества соответственно в зависимости от того, на какой стороне они лежат относительно выбранной плоскости. Любой многоугольник, частично лежащий в обоих подпространствах, разбивается по пересечению с плоскостью, и два фрагмента помещаются в соответствующие множества. Любой многоугольник, который оказался копланарным[9] с корневой плоскостью, сохраняется в корне вместе с корневым многоугольником (Рисунок 1).
Рисунок 1. Разбиение пространства и многоугольников плоскостью, определяемую многоугольником
Эта процедура повторяется рекурсивно снова. Многоугольник выбирается из каждого из двух множеств, а его плоскость образует корень соответствующего поддерева, которое далее разделяет пространство и остальные многоугольники. Это повторяется до тех пор пока не будут задействованы все многоугольники, а исходное пространство не будет разделено на однородные области (ячейки). На рис. 2 ячейки помечены от a до f и показаны как листья дерева.
Рисунок 2. Окончательное разбиение
BSP-дерево, подобное тому, которое построено выше на рис. 1 и 2, мы можем использовать для решения проблемы определения видимых граней. Для этого нужно пройти дерево от любой заданной точки обзора, чтобы получить отсортированный по удаленности к наблюдателю порядок многоугольников, хранящихся в узлах. А затем отрисовать многоугольники в указанном порядке. Многоугольники, находящиеся ближе к наблюдателю, закроют те, что находятся дальше.
Рисунок 3. Прохождение дерева для получения порядка дальше-ближе
Обход основан на том факте, что многоугольники на той же, ближней, стороне, что и точка обзора, не могут быть загорожены многоугольниками на другой стороне, дальней. Итак, чтобы получить обратный порядок многоугольников из дерева, можно использовать простой рекурсивный алгоритм, показанный на рис. 3: сравнить точку обзора с узловой плоскостью. Пройти по дальнему поддереву, отобразить корневой многоугольник(и), а затем пройти по ближнему поддереву.
