С Новым Годом!

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

Итак, с Новым Годом! Который непременно принесет новые успехи, достижения, кучу денег и мешок счастья.

И напоследок бодрящий анекдот. Он не новогодний, а просто прикольный:
Two strings walk into a bar. The first one says, “Bartender! Bartender! I want a drink!”
The second one says, “Bartender! Bartender! I want a drink too! blaaaaaaaaah Eeeeeeeek yaaaaaaak oooooooh.”
The first one says, “Please excuse my friend. He isn't null terminated.”

Ожил блог My own little DirectX FAQ

Блог My own little DirectX FAQ посвящен, как следует из названия, DirectX. Он не обновлялся с 2003 года, но в этом месяце его автор, Tom Forsyth, написал несколько новых постов, и, надеюсь, его энтузиазм на этом не иссякнет. Том работает в RAD Game Tools и занимается разработкой утилит для разработчиков игр. Также советую заглянуть на домашнюю страничку Тома, там есть его публикации и слайды с различных выступлений.

C++0x

Update 27.12.2005: По поводу названия, почему C++0x. x будет заменен на номер года выхода стандарта. Это будет C++07, C++08, что-нибудь в этом роде. Разработка нового стандарта началась не недавно, о том, что принимаются предложения, было объявлено несколько лет назад. Процесс идет неспешно, сначала предложения копились, теперь рассматриваются...

"Упрочить доказанные достоинства C++ и двигаться вперед" - под таким девизом Бьерн Страуструп написал статью про разработку нового стандарта C++, C++0x.
C++0x планируется сделать почти на 100% совместимым с текущим стандартом, C++98. "Почти" потому что совсем на 100% сделать не получится. Страуструп в качестве примера приводит добавление нового ключевого слова. Код, который раньше использовал такое слово, уже не будет соответствовать новому стандарту.
Страуструп настивает на том, что C++ останется языком общего назначения. Более-менее специализированные вещи будут внесены в Стандартную Библиотеку.
Будет уделено внимание поддержке новичков. Сейчас, по мнению Страуструпа, язык больше ориентирован на экспертов и начинать на нем программировить довольно тяжело. Язык должен помогать новичку, защищать от внесения ошибок. Предназначенные для этого конструкции не должны стоять особняком, нужно чтобы они органично вписались в язык.
Сейчас можно отключить потенциально дорогие фичи, например RTTI, что положительно сказывается на производительности. Страуструпу очень нравится эта возможность и он пишет, что в C++0x в этом отношении ничего не изменится.
Я просмотрела по диагонали неполный список предложений по языку и список предложений по Стандартной библиотеке. Это именно предложения, не факт, что они буду включены в язык. Вот некоторые из них.
Неполный список предложений по языку:

• Возможность переопределения новых приведений типов static_cast, dynamic_cast, это может оказаться удобным при использовании умных указателей (smart pointers).
• Свойства (properties) в стиле Delphi/C#.
  
• Опциональная сборка мусора.
  
• Использование строк в switch.
  

  
  bool f(string s)
  {
    switch(s) {
    case "yes": return true;
    case "no": return false;
    default: throw Unexpected_string();
  }

  
  
• Ключевое слово final, которое в сочетании с виртуальной функцией, запретит дальнейшее перекрытие этой функции.
  

Список пожеланий для Стандартной библиотеки:

• Простой способ выводить на зкран содержимое контейнеров в красиво отформатированном виде. То есть cout << x должно "просто работать" для контейнеров.
  
• XML парсер
  
• Хорошая библиотека линейной алгебры (матрицы, векторы). Отдельно есть предложение по библиотеке для кватернионов специально для тех, кто разрабатывает 3Д игры.
  
• Библиотека для работы с графами.
  
• Паттерны проектирования. Особенно просят Singleton.
  

Ссылки по теме:
The C++ Standards Committee
Boost C++ Libraries

has-a отношение и IIITO

В ООП есть два родственных термина, которые разные люди понимают по-разному. Термины эти has-a отношение (иногда пишут HASA) и IIITO (Is Implemented In Terms Of). Вроде как оба они означают владение. И оба можно выразить через приватное наследование или через делегирование.

//Приватное наследование
class CB : private CA
{
  //...
}

//Делегирование
class CB
{
private:
  CA* pA;
  //... 
}

В различных источниках я читала разное мнение по их поводу. Что IIITO - это и приватное наследование, и делегирование, а has-a - это только приватное наследование. Или что has-a - это и приватное наследование, и делегирование, а IIITO - это только делегирование. В итоге о чем именно идет речь приходится понимать из контекста.

Ссылки по теме:
GotW#60: Exception-Safe Class Design, Part 2: Inheritance
comp.object IS A and HAS A relationships
is-a отношение

3D шутер на языке Haskell

Haskell - это язык функционального программирования. О функциональном программировании я имею весьма смутное представление, но я всегда думала, что оно предназначено для решения математических задач. Ан нет, умельцы могут на нем и игры писать. 3D шутер под названием Frag - это наиболее впечатляющий пример.


Он в исходниках и, честно говоря, мне было лень что-либо ставить, чтобы их скомпилять, так что в движении я его так и не посмотрела. Написан он с помощью Yampa - по документации "Yampa - это язык, встроенный в Haskell, предназначенный для описания реагирующих систем". В документации по Yampa рассказывается как с его помощью написать Space Invaders.

Вот еще игры на Haskell'е. Сайт, увы, на японском.
Это, судя по всему, аркада.

А это похоже на паззл.


Думаю, что эти игры вызывают скорее академический, нежели практический интерес. Но все равно, забавно.

По ссылкам с блога GrammerJack: "Arcade Games in Haskell"

is-a отношение

is-a отношение - это термин из теории объектно-ориентированного программирования. Кто-то считает, что этот термин не совсем корректный, да и вообще устаревший (В comp.object Роберт Мартин как-то бухтел по этому поводу). Но я натыкалась на него несколько раз, также как и на has-a. Про второе чуть позже, сегодня про is-a (иногда пишется ISA).
Если есть два объекта: A и B, то можно сказать, что B is-a A, если в программе везде, где используется A, можно использовать B. Несмотря на мудреное определение, все просто. Если у меня есть базовый класс CPrinter и я от него наследую CEpson, CHP и т.п., то логично будет чтобы функция, которая принимает в качестве параметра CPrinter, могла работать с любым отнаследованным принтером, поскольку по логике вещей CEpson is-a CPrinter.

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

Если я где-то определила публичное наследование вида:
class CBase
{
public:
virtual void VirtFunc();
// ...
};

class CDerived : public CBase
{
public:
virtual void VirtFunc();
// ...
};

void SomeFunc( const CBase& );

То я фактически говорю, что CDerived is-a CBase, а значит, что в функцию SomeFunc можно передавать как экземпляры CDerived, так и CBase, и они должны обрабатываться корректно. А если я реализовала функцию VirtFunc таким образом, что передавать в SomeFunc экземпляр CDerived по каким-либо причинам нельзя, то это как минимум странно.


Ссылки по теме:
comp.object IS A and HAS A relationships
GotW #40: Controlled Polymorphism

Статья Effective C++ Memory Allocation

В статье Effective C++ Memory Allocation, Аарон Дэйли (Aaron Dailey) рассказывает о реализации собственного менеджера памяти, обращаться к которому можно переопределив операторы new и delete. Это не абстрактная статья, таким образом организована работа с памятью в одной из разработанных Аароном встроенных систем. Несмотря на то, что статья адресована именно разработчикам встроенных систем, она может оказаться интересной и разработчикам игр.

Умер Джон Влиссидес

Джон Влиссидес (John Vlissides) был больше всего известен как один из соавторов книги "Приемы объектно-ориентированного проектирования. Паттерны проектирования" (Design Patterns: Elements of Reusable Object-Oriented Software). Всего авторов у этой очень известной книги по паттернам проектирования четыре: Эрих Гамма (Erich Gamma), Ричард Хелм (Richard Helm), Ральф Джонсон (Ralph Johnson) и Джон Влиссидес (John Vlissides). Иногда их называли "Банда четырех" (Gang of Four, GoF).

Martin Fowler's Bliki: JohnVlissides

Освобождение памяти, выделенной под vector

Некоторое время назад я писала про выделение памяти под vector и в конце немного затронула тему высвобождения памяти. В большинстве реализаций освободить память, выделенную под vector, можно только с помощью трюка, известного как swap trick. Недавно я вычитала, что в реализации STL из Visual C++ 7.1 память, выделенная под вектор, высвобождается при вызове метода clear(). 7.1 у меня нет, зато у меня есть Microsoft Visual C++ Toolkit 2003. Действительно, освобождается. Для такого кода:

vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.clear();
cout<<v.capacity()<<endl;

Вывод получается такой:

Microsoft Visual C++ Toolkit 2003:
17
0 //действительно, освободилась
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17


Я решила копать дальше. Я всегда считала, что метод clear для последовательных контейнеров эквивалентен erase всего контейнера. Нашла упоминание об этом в документации STL на sgi.com. Вот оттуда выдержка:
a.clear() Equivalent to a.erase(a.begin(), a.end())
Запускаю код:
vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.erase(v.begin(), v.end());
cout<<v.capacity()<<endl;

Получаю:
Microsoft Visual C++ Toolkit 2003:
17
17 //не освободилась
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17

Получается, что в случае вышеупомянутого тулкита нет обещанной эквивалентности. Так, а что говорит об этом Стандарт? Вот тут интересный момент. Там нет слова "эквивалентно". Там erase(begin(), end()) приписано к clear() в качестве assertion/note для последовательных контейнеров. А вот требование там одно, что post condition: size()==0. Оно тут выполняется.
Так что MSVC++2003 тут прав.
Я пробовала также v.resize(0). Пробовала удалить все элементы вектора с помощью pop_back'ов. Память не освобождается. Это происходит только при вызове clear.

Ссылки по теме:
STL vector and reserve

Непрерывная подгрузка уровней

Статья о непрерывной подгрузке уровней на примере игры Dungeon Siege. Кроме самой статьи есть также слайды.

Вообще идея подгружать уровни непрерывно, не показывать игроку картинки с заставками и тем самым не прерывать геймплей очень интересна. Сейчас я это реализую в Winding Trail, но у нас все значительно проще, сама игра значительно меньше. В статье о Dungeon Siege рассказывается об организации непрерывной подгрузки, которую они делают отдельным потоком, что породило огромное количество странных багов, которые они потом ловили. Кроме этого говорится и о других проблемах, о которых при организации такого вот непрерывного мира сразу и не подумаешь. Например, у них начали переполняться float'ы при подсчете расстояний. Кроме всего прочего у них игра поддерживает многопользовательский режим, что еще добавило сложности. В итоге у них получился Игровой Мир с неевклидовой геометрией и одному из дизайнеров удалось создать в буквальном смысле слова бесконечную пустыню.

Статья очень хорошая, там не просто говорится "мы сделали так-то и так-то", а рассказывается почему они пришли именно к таким решениям, и какие претензии к этим решениям у них остались.

Там же они рекомендуют слайды на ту же тему: Stuart Denman. Highly Detailed Continuous Worlds: Streaming Game Resources from Slow Media. (PPT)

Точки следования (sequence points)

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

О таинственном. Я пишу программу
int x=0;
x=x++;
cout<<x;

Вопрос: что выведется на экран? Ну что может быть проще - сейчас запустим да проверим. Я запустила MSVC++6.0, ответ получился 1.
Потом запустила gcc 3.4.4 и получился 0.
Если бы запустила что-то еще, то могло получиться нечто третье...
Кто из них прав? На самом деле все. А вот почему так в двух словах и не скажешь...

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

Точки следования (sequence points) - это некие точки в программе, где состояние реальной программы полностью соответствует состоянию абстрактной машины, описанной в Стандарте. С помощью точек следования стандарт объясняет, что может, а чего не может делать компилятор и что нам нужно сделать, чтобы написать корректный код.

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

Если код выглядит так:
int x;
x = 3;
cout << x << endl;
x = 4;

То нет никаких сомнений, что на печать будет выведено 3. Точка с запятой в конце выражения "x = 3;" как и любая точка с запятой в конце любого выражения - это точка следования. Перед тем как любой код после этой точки с запятой выполнится, побочный эффект от сохранения значения 3 в int объект x должен быть полностью завершен. И мы точно знаем, что вывод не будет равен 4, потому что вывод полностью завершен к тому моменту, как выполнение программы достигнет точки с запятой в конце выражения "cout << x << endl;". Побочный эффект от сохранения значения 4 в x в следующем выражении еще не случился.

Где находятся точки следования

1. В конце каждого полного выражения(Глава Стандарта 1.9/16). Обычно они помечены точкой с запятой ;


2. В точке вызова функции (1.9/17). Но после вычисления всех аргументов. Это и для inline функций в том числе.


3. При возвращении из функции. (1.9/17) Есть точка следования сразу после возврата функции, перед тем как любой другой код из вызвавшей функции начал выполняться.


4. (1.9/18) После первого выражения (здесь оно называется 'a') в следующих конструкциях:
   
   a || b
   
   a && b
   
   a , b
   
   a ? b : c
   
   Вычисление здесь идет слева направо. То есть левое выражение (по имени 'a') вычисляется и все побочные эффекты от такого вычисления завершаются. Потом, если все значение всего выражения известно, правое выражение не вычисляется, иначе вычисляется.
   Правило слево-направо не работает для переопределенных операторов. В этом случае переопределенный оператор ведет себя как обычная функция. Еще такой момент - ?: не может быть переопределен по стандарту.
   
   (Упомянутая запятая это оператор запятая. Она не имеет никакого отношения к запятой, разделяющей аргументы функции.)

Если рассмотреть пример "x = x++;", то здесь имеет место попытка изменить объект дважды.
Если программа пытается модифицировать одну переменную дважды не пересекая точку следования, то это ведет к undefined behavior. Так говорит Стандарт. И тут же в Стандарте приводятся примеры.

1) i = v[i++]; //unspecified behavior
2) i = 7, i++, i++; //i равно 9

3) i = ++i + 1; //unspecified behavior
4) i = i + 1; //значение i увеличено на 1

Что-то с чем-то не сходится. В первом и третьем примерах указано "unspecified behavior", хотя переменная изменяется дважды и только что было сказано, что это ведет к undefined behavior.
И точно в списке багов Стандарта это место упомянуто. В предложении по устранению бага советуют поменять слово unspecified на слово undefined.
Но на самом деле не так уж и важно, unspecified или undefined behavior. Важно то, что непонятно, что именно получится в итоге. Поэтому не надо модифицировать переменную больше одного раза между двумя точками следования, поскольку это может привести к весьма неожиданным последствиям. Вот, например
int x;
x = 3;
cout << (++ x + ++ x) + ++ x << endl;
x = 3;
cout << ++ x + (++ x + ++ x) << endl;

gcc 3.4.4:
16
18
Получилось, что операция сложения не ассоциативна!

MSVC++6.0:
18
18

Примеры:
i = ++i; // undefined behavior, переменная модифицируется дважды
i = i + 1; // все в порядке
i ? i=1 : i=5; // все в порядке (там, где знак ? есть точка следования, а потом выполнится лишь одно из выражений)
i=1; i++; // все в порядке (после каждого выражения находится точка следования)
i=1, i++; // все в порядке (на операторе запятая находится точка следования)

Пример с функциями:
void f(int, int);
int g();
int h();
f(g(), h());
По Стандарту неизвестно, какая из функций g или h будет вызвана первой, но известно, что f() будет вызвана последней.


Разработчикам gcc периодически сабмитят баги по этому поводу, в итоге в
Frequently Reported Bugs in GCC было внесено:

Результат следующих операций непредсказуем и это полностью соответствует стандарту
x[i]=++i
foo(i,++i)
i*(++i) /* special case with foo=="operator*" */
std::cout << i << ++i /* foo(foo(std::cout,i),++i) */

Вот пример такой баги: Bug13403. Их таких там очень много.

В следующей программе
#include <iostream>
int main(){
int i=0;
i = 6+ i++ + 2000;
std::cout << i << std::endl;
return 0;
}

Результат единица! А должен быть 2006.
Если убрать "i++", то результат правильный ("2006"). Но пока есть "i++" внутри выражения, я могу делить, умножать, вычитать, складывать, все равно результат всегда "1".
Например в выражении
i = (6+ i++ + 2000)/2;
"i" все равно единица.

Но если я заменю постфикс "i++" префиксом "++i" тогда все считается корректно.

Ну отвечают на это все - "это undefined behavior по Стандарту" и баг закрывают.

Несколько присваиваний подряд
Интересный момент с таким кодом:
int a=1, b=2, c=3;
a=b=c=0;
Стандарт как-то очень нечетко описывает такую ситуацию. Он говорит, что операция должна происходить справа налево, но ничего не говорит дополнительно по поводу того, когда должен быть результат этой операции записан в переменную. Точек следования внутри выражения нет, что значит, что компилятор может теоретически творить здесь что угодно и не обязательно все переменные в итоге будут равны 0. Так что, опять же теоретически, здесь имеет место unspecified behavior. По этому поводу периодически рождаются хвостатые флеймы в comp.lang.c++.moderated. Но на самом деле я не слышала о компиляторе, который делал бы в такой ситуации присвоение не справа налево. Вопрос этот известен, а компиляторы не садисты пишут.

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

Ссылки по теме:
Разница между unspecified behavior и undefined behavior
comp.lang.c++.moderated Undefined behavior?? I think not!
comp.lang.c++.moderated postfix increment and assignment
comp.lang.c++.moderated fresh look on copying objects and passing args by value
comp.lang.c++.moderated Evaluation precedence questions
comp.lang.c++.moderated = Operator?
comp.lang.c++.moderated How defined is undefined behaviour?
comp.lang.c++.moderated Case for post-increment/decrement
comp.lang.c++.moderated What is a sequence point?
comp.lang.c++.moderated Sequence point and evaluation order
comp.lang.c++.moderated sequence point and reference
comp.lang.c++.moderated sequence points and , operator

Открыт блог проекта Winding Trail

Мы с Джимом открыли блог нашего игрового проекта под рабочим названием Winding Trail, разработка которого идет полным ходом.
Честно говоря, меня мучали сомнения - "а не преждевременно ли?". Но сомнения такого рода меня мучают постоянно, поэтому я решила на них забить.

Aardvark'd - документальный фильм о работе программистов

Этим летом Джоэл Спольски затеял интересный проект. Он пригласил на работу стажеров и дал им задание за 12 недель создать готовый программный продукт. Обычно-то стажеров загружают всякой фигней. Стажеры вели блог о своей работе: Aardvark блог. Проект закончился успешно, продукт они выпустили.
Сейчас на DVD вышел документальный фильм о проекте Aardvark под названием Aardvark'd, 12 weeks with geeks.

Тесты Brainbench бесплатны до 15 ноября

Brainbench - сравнительно известный сервис по тестированию на самые различные знания, в том числе и на знание программирования. Оценка умения программировать таким образом кажется мне сомнительной, но Brainbench сделал свои тесты бесплатными до 15 ноября, почему бы и не попробовать? Бумажный сертификат высылается за деньги, как и было. Как говорит Brainbench, по "многочисленным просьбам" в апреле 2006 вновь пройдут какие-то их Игры и вот, чтобы народ мог к ним подготовиться они открывают всю библиотеку тестов.
Когда-то давно тесты постоянно были бесплатными и назывался он не Brainbench, а Tekmetrics. И бумажные сертификаты высылали бесплатно, а сейчас только за деньги...

Художественная литература для программистов

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

Just for fun. Рассказ нечаянного революционера Авторы: Линус Торвальдс, Дэвид Даймонд Биография Линуса Торвальдса, создателя Linux. Собственно о том, как он писал Linux и рассказывается в основном. Написано очень весело, с юмором, перевод хороший. online: Just for fun. Рассказ нечаянного революционера. Купить на Amazon.com: Just for Fun: The Story of an Accidental Revolutionary

Хакеры, герои компьютерной революции Автор: Стивен Леви О первых хакерах, не о тех, кого сейчас называют хакерами, а о людях, пытавшихся лучше понять и использовать компьютеры. О создании первых персональных компьютеров. О Старых Добрых Временах. Единственный минус - повествование несколько занудное. online: Хакеры, герои компьютерной революции Купить на Amazon.com: Hackers: Heroes of the Computer Revolution

Криптономикон Автор: Нил Стивенсон Полуфантастическое произведение о дешифровщиках времен Второй Мировой и о современных криптографах. Стиль у Стивенсона очень специфичный, он лихо переплетает несколько сюжетных линий и ведет рассказ о нескольких временных отрезках одновременно. Именно программирования в книге мало, в основном математика, криптография. Большим специалистом, чтобы это все понять, быть не надо, рассказано все очень простым языком. Написано несколько грубовато, там есть весьма неаппетитные описания боевых действий. (Нашла по ссылке с hints.ru) online: Криптономикон часть 1, Криптономикон часть 2. Купить на Amazon.com: Cryptonomicon

Сейчас разыскиваю чего бы еще почитать в том же духе. Меня заинтересовала Crypto Стивена Леви, хотя отзывы о ней на Амазоне неоднозначные. Может кто-нибудь еще чего присоветует?

std::remove и std::remove_if на самом деле ничего не удаляют

Два алгоритма из STL, remove и remove_if помогают удалять элементы из последовательных контейнеров, то есть из vector, string, deque и list.
Помощь заключается в том, что эти алгоритмы сдвигают элементы и возвращают итератор на начало мусора. Удалять мусор нужно отдельно, remove и remove_if не удаляют физически объекты из контейнера.

Например, пускай у нас есть vector <int>, содержащий следующие значения.
1 2 3 1 2 3 1 2 3

Если вызвать
remove( v.begin(), v.end(), 2 )
//удалить элемент со значением 2 из контейнера v

получится
1 3 1 3 1 3 ? ? ?
где ? - некий мусор. Итератор, который возвратит remove, указывает на первый мусорный элемент, в данном случае на третий с конца. Мусорные элементы могут иметь те же значения, что и до вызова remove, то есть 1 2 3, а могут иметь и любые другие, на это полагаться не стоит. Размер контейнера остается неизменным.

Чтобы избавиться от мусора, можно вызвать erase. Обычно оба вызова записывают одной строкой и получается что-то вроде.
v.erase( remove( v.begin(), v.end(), 2 ), v.end() );

Для list алгоритмы std::remove и std::remove_if работают крайне неэффективно. Поэтому в list есть собственная реализация удаления объектов, list::remove и она быстрая. Элементы там не двигаются, а лишь переставляются ссылки. erase вызывать уже не нужно, потому что list::remove уничтожает ненужные элементы сам.

Почему remove и remove_if работают именно так? Что мешает удалять элементы сразу и не мучаться лишний раз, вызвая erase? Дело в том, что remove не может определить из какого контейнера к нему пришли итераторы, а, следовательно, не может корректно удалить элементы из этого контейнера. Нельзя удалить элементы из контейнера или добавить элементы в контейнер, если на этот контейнер каким-либо образом не была передана ссылка.

Ссылки по теме:
Table of Contents: the Standard Template Library
GotW #51: Extending the Standard Library - Part I
comp.lang.c++.moderated "delete elements in associative container"
comp.lang.c++.moderated "The list.erase(remove...) idiom, doing half the job???"
comp.lang.c++.moderated "Two new STL Questions"

Steering behaviors и библиотека OpenSteer

В стратегиях, да и не только в них, часто возникает необходимость реализации следования некоторому пути. Например, пускай нужно для героя проложить путь из замка A в замок B. Рассчитали его по какому-нибудь path finding алгоритму, идем. И тут оказывается, что еще кто-то бредет из замка C в замок D и пересекает нам дорогу. По пути копошатся крестьяне и бродят коровы, их надо бы обойти. И что теперь? Постоянно перестраивать путь? Слишком накладно. Можно слегка изменить направление уже по ходу движения, чтобы избежать столкновения. С крестьянами можно вообще не церемониться, герой в доспехах может их всех просто распихать.
Виды изменения направления по ходу движения и есть steering behaviors. В русском языке адекватный перевод найти оказалось сложно, я встречала термин "стиринг", а также глагол "стирить".
Самый известный ресурс по steering behaviors - это Steering Behaviors For Autonomous Characters Крейга Рейнольдса (Craig Reynolds). Для его понимания достаточно школьного курса математики, той части, что относится к векторам. Кроме уже описанного уклонения от столкновений, там есть довольно много интересных стирингов таких как "преследование" (pursue), "шатание без дела" (wander), "следование пути" (path following) и еще много всяких разных. Если полководец войско ведет, то можно реализовать стиринг "следование за лидером" (leader following), чтобы для каждого юнита не строить свой путь и чтобы они друг другу не мешались.
На открытых пространствах они будут толпой идти, в узком ущелье в колбасу вытянутся.

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

OpenSteer - это open source библиотека стирингов, описанных на Steering Behaviors For Autonomous Characters. Реализованы не все, но многие. Библиотекой ее можно назвать с натяжкой. Вообще это демка, написанная с использованием OpenGL, где код стиринга и код демки намертво спаяны в единое целое. Что будет легче - выдрать оттуда код стиринга и использовать его в своем проекте или написать свой код, посматривая в эту реализацию, сказать сложно. Я пока выбрала второй путь.

OpenSteer: реализация преследования и уклонения

OpenSteer: следование пути, плюс огибание препятствий на этом пути встречающихся.

OpenSteer: игра в футбол с использованием стиринга

Ссылки по теме:
Steering Behaviors For Autonomous Characters
Graphics and Artificial Life - исследования по моделированию поведения пешеходов
dtf.dev.ai "хождение (movement and pathfinding)"

Technorati tag: game development

Статья "Физическая структура и C++"

Статья с блога Games from Within. Посвящена правильной организации кода, то есть как сделать так, чтобы код не был похож на эту иллюстрацию. В основном речь там идет об #include'ах.

Physical Structure and C++ - Part 1: A First Look
Physical Structure and C++ - Part 2: Build Times

Technorati tag: cpp

Результаты DARPA Grand Challenge 2005

Соревнования роботизированных машин DARPA Grand Challenge 2005 завершились и целых пять машин добрались до финиша. Что на пять больше, чем в прошлом году. Победу одержала машина "Стенли" Стэнфордского Университета со временем 6 часов, 53 минут и 58 секуны, двигалась она со средней скоростью 19.1 миль в час (30.7 км/ч). Всего стартовало 23 машины, но далеко не все смогли преодолеть 131.6 миль (211.7 км) по калифорнийской пустыне. Одна машина врезалась в мост, у каких-то машин возникли софтверные проблемы, у кого-то проблемы с сенсорами. Машина "Алиса" врезалась в заграждение, снесла его и поехала на репортеров и опрераторов, ее пришлось отключить.
Тяжело всем приходилось в туннелях, мало того, что там было темно, так еще и система глобального позиционирования GPS там не работала.
Событие вызвало бурное обсуждение на slashdot.org. Вот цитата оттуда "Это не столько развитие искусственного интеллекта, сколько развитие сенсоров. Машина смотрит вперед примерно на 30 футов (9.1 метров) и строит свой путь по довольно простому алгоритму. Препятствия-выбоины довольно сложно обнаружить сенсорами, сложнее, чем камень, преграждающий путь. Во время прошлых гонок Красную команду (Red Team) остановил поворот-шпилька. Их сенсоры смотрели прямо вперед, а по боками лишь чуть-чуть и когда она доехала до повотора-шпильки, машина чуть было не свалилась с горы."

Второй и третьей приехали машины из университета Carnegie Mellon (CMU). Интересные вещи рассказывают в форуме соревнований. Разработка "Стенли" была гораздо дешевле, чем разработки CMU, в "Стенли" и сенсоры использовались попроще, вообще оборудования было меньше. Зато "Стенли" система самообучающаяся, адаптирующаяся, использует нейронные сети. А машины CMU использовали алгоритмы "грубой силы". То есть получается, что выиграла более интеллектуальная машина.

DARPA говорит, что в следующем году они не будут проводить соревнования. Но вполне вероятно, что права на проведения соревнований кто-нибудь выкупит.

Ссылки по теме:
Grand Challenge Home
Stanford's Stanley wins DARPA Grand Challenge 2005 - самое полное из найденных мною описаний происходившего.
I don’t care about dancing robots…
Stanford Brings Home the Victory

Clocky

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

Эдсгер Дейкстра "Оператор go to вреден"

Классическая работа 1968-го года Go To Statement Considered Harmful.

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

Technorati tag: программирование

Среда разработки Code::Blocks Studio

Code::Blocks - это кроссплатформенная, бесплатная, Open Source среда разработки. В ней есть многие приятные вещи, которые современная среда разработки обязана уметь. Class browser, code completion, фолдинг (folding).

Есть импорт воркспейсов Microsoft Visual Studio и проектов Dev-C++.
Насколько мне известно, популярная среда разработки Dev-C++ умеет работать только с GCC-компиляторами. Так же как и у Code::Blocks у них есть версия с MinGW GCC, есть версия вообще без компилятора. Но к Code::Blocks еще можно подключать другие (не обязательно GCC) компиляторы через приятный интерфейс.

Причем для разных проектов можно подключить разные компиляторы, можно для одного и того же проекта попробовать различные компиляторы. Последнее должно быть особенно удобно для тех, кто разрабатывает open source проекты, которые просто обязаны компиляться всеми более-меннее распространенными компиляторами. Плюс переход на другой компилятор можно произвести очень быстро. Выбираешь в списке другой компилятор, работаешь с ним - не понравилось? Возвращаешь все обратно, настройки все сохранились. Никаких дополнительных сред разработки скачивать не надо, привыкать к ним не надо.
Список компиляторов, с которыми умеет работать Code::Blocks:

• GNU GCC (Linux)
• MinGW GCC (Win32)
• Microsoft's Visual C++ Free Toolkit 2003 (Win32)
• Borland's C++ Compiler 5.5 (Win32)
• DigitalMars (Win32)
• OpenWatcom (Win32)
• Small Device C Compiler (SDCC)

Code::Blocks позволяет держать разные настройки по умолчанию для разных компиляторов.

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

Если работа над Code::Blocks будет продолжаться в том же духе, он сможет составить весьма достойную конкуренцию Microsoft Visual Studio. Дело в том, что не так давно Microsoft выпустила Microsoft Visual C++ Toolkit 2003, который, в том числе, содержит консольную версию своего компилятора, которые они используют в Visual Studio .NET 2003 Professional. Плохо в нем то, что он - компилятор командной строки, сколь-нибудь большой проект таким образом разрабатывать сложно, все равно нужно какое-то средство разработки. И если раньше выбора особенного не было и приходилось работать с Visual Studio, то теперь есть Code::Blocks, появился выбор.
Но у меня с ним обнаружилась одна небольшая засада. Компилятор из тулкита не понимает пробелы в именах файлов и названиях директорий. Я же люблю все инсталлировать в директорию Program Files. Поскольку Microsoft утверждает, что это точь-точь тот же компилятор, что используется в Visual Studio .NET 2003 Professional, то, я думаю, что это среда Visual Studio заключает названия директорий в кавычки прозрачно для пользователя. Что-либо переделывать мне было лень, так что скомпилять я ничего так и не скомпиляла. В багтраке Code::Blocks есть бага по этому поводу, но когда они ее поправят и поправят ли, большой вопрос.

Еще мнение о Code::Blocks:
Code::Blocks Studio

Ссылки по теме:
Free Windows Editors
Dev-C++
Microsoft Visual C++ Toolkit 2003

Technorati tag: cpp

mutable и const_cast

Бывают случаи, когда строгое придерживание константности неудобно. Объект может оставаться логически константным ("logically const"), но при этом его физическая константность ("physically const") может быть нарушена. Пример: в неком классе на основании данных класса по очень сложному и долгому алгоритму считается некая величина. Хорошо бы эту величину закэшировать.

class CFoo
{
  int cachedValue;
  bool bCached;
  ...
public:
  int calculate() const
  {
    //долгое вычисление
    cachedValue = ...; //ошибка
    //нельзя делать присвоение данным класса в константной функции
  }
  ...
};

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

class CFoo
{
  mutable int cachedValue;
  mutable bool bCached;
  ...
public:
  int calculate() const
  {
    if(bCached) return cachedValue;
    //долгое вычисление
    cachedValue = ...; //все в порядке
    bCached = true;
  }
  ...
};

Подобное кэширование данных - это классический пример использования mutable.
mutable означает, что спецификатор const, примененный к классу, следует игнорировать. По стандарту только данные класса могут быть mutable.
Признак правильного использования mutable: если при доступе к данным через интерфейс класса все выглядит так, будто в классе ничего не менялось, то можно использовать mutable.
Еще один классический пример использования mutable - это синхронизация доступа к данным. Допустим, у нас есть класс, содержащий переменную, хранящую некоторое значение (data), и объект, отвечающий за синхронизацию доступа в многопоточных приложениях (sync_obj). Также есть две функции, отвечающие за доступ к данным: set_data и get_data. Функция get_data должна быть константной, она же не меняет данные класса, но как ей тогда залочить доступ к данным? Объявить sync_obj как mutable.

class mutable_test
{
  int     data;
  mutable sync  sync_obj;
public:

  void set_data (int i)
  {
      sync_obj.lock ();
      data = i;
      sync_obj.unlock ();
  }

  int get_data () const
  {
      sync_obj.lock ();
      int i = data;
      sync_obj.unlock ();
      return i;
  }
};

Если mutable вполне законное средство убрать константность, у него есть классические применения, то const_cast - это всегда некий хак. Используется обычно с библиотеками, которые не являются const-корректными. С помощью const_cast можно убрать только const, навешанный на объект, который изначально константным не является. Пример:

int i;
const int * pi = &i;
// *pi имеет тип const int,
// но pi указывает на int, который константным не является
int* j = const_cast<int *> (pi);

Если же попробовать убрать const с объекта, который на самом деле const, результатом будет undefined behaviour.

struct Foo { int val; };

int main()
{
  const Foo obj = { 1 };
  const_cast<Foo *>(&obj)->val = 3;  // undefined behaviour
  return obj.val;
}

Ссылки по теме:
comp.lang.c++.moderated "usefulness of const_cast"
comp.lang.c++.moderated "legitimate use of const_cast"
comp.lang.c++.moderated "mutable: why it's in the language"


Technorati tag: cpp

Лучшие друзья девушки

По ссылке с блога Human Disassembling Labs' Blog я нашла прелюбопытнейшую бижутерию: Zelle Catalog. С первого взгляда ничего необычного

Но если присмотреться поближе...

Ожерелье из фиолетовых сопротивлений.

Часть украшений поставляется в чашке Петри.

Ожерелье из конденсаторов в чашке Петри.

Фантазия у автора украшений работает на полную катушку. Ничто не пропадет даром. Микропроцессоры тоже пущены на ожерелья.

Вспоминается старый бородатый анекдот.
Новый русский хвастается другу ремонтом в своем новом доме. После осмотра друг говорит: "Да, все круто, но только плитка у тебя в туалете не очень. Простая коричневая." "Да ты посмотри внимательно, что на ней написано!". Друг смотрит внимательно: Pentium Pro.

Нашлось применение и дискетам.

Сумочка из дискет.

А я, наивная, на елку их вешаю...

Кстати, даже в таком известном магазине как ThinkGeek нет ничего подобного. Отдел украшений у них вообще очень убогий. Они, правда, продают один из браслетов из Zelle Style, далеко не самый красивый.

У них еще есть такая подвеска со светодиодом.

Идея оригинальная, но мне не нравится. Остается только завернуться в белую простыню и пугать админов по ночам. Не мой выбор.

Раз уж об этом зашла речь - еще один магазин околокомпьютерных сувениров: www.cafepress.com. И чего там только нет...

Тонкий способ намекнуть кому-либо что его блог не очень хороший.

В подарок любимому учителю математики.

Ну и напоследок

Использование const. Часть 2.

Продолжаем захватывающую беседу о возможных использованиях многоликого const. Начало было тут: Использование const. Часть 1.

const данные в классе
Значения const данных класса задаются один раз и навсегда в конструкторе.

class CFoo
{
  const int num;
public:
  CFoo(int anum);
};
CFoo::CFoo(int anum):num(anum)
{
...
}

Интересный момент со static const данными класса. Вообще для данных целого типа (enum, int, char) их значения можно задавать прямо в объявлении класса. Вот этот код правильный с точки зрения стандарта:

class CFoo
{
public:
  static const int num=50;
};

Но в Visual C++ 6.0 такое задание значения не работает, это один из багов Visual C++ 6.0. Тут задавать значение static const переменной следует отдельно. Не могу сказать, что эта бага меня сильно расстраивает. Вместо того, чтобы запоминать, когда можно при объявлении писать инициализацию, когда нельзя, лучше сразу так написать:

class CFoo
{
public:
  static const int num ;
};

const int CFoo::num = 20;

const функции в классе
Функция класса, объявленная const, трактует this как указатель на константу. Вообще тип this в методе класса X будет X*. Но если метод класса объявлена как const, то тип this будет const X*. В таких методах не может быть ничего присвоено переменным класса, которые не объявлены как static или как mutable (о mutable потом). Также const-функции не могут возвращать не const ссылки и указатели на данные класса и не могут вызывать не const функции класса. const-функции иногда называют инспекторами (inspector), а остальные мутаторами (mutator). Я пыталась найти для mutator перевод, который будет звучать получше, но в переводах я ничего подходящего не встречала, а Яндекс.Лингво смог мне предложить только "ртутный вентиль", что сюда явно не подходит.

class CFoo
{
public:
  int inspect() const;   // Эта функция обещает не менять *this
  int mutate();          // Эта функция может менять *this
};

В классе могут присутствовать две функции отличающиеся только const.

class CFoo
{
  ...
public:
  int func () const;
  int func ();
};

Не всякая функция может быть объявлена константной. Конструкторы и деструкторы не могут быть объявлены как const. Также не бывает static const функций.

class CFoo
{
  int i;
public:
  static int func () const;    //ошибка
};

Константный класс
Официально такого понятия как константный класс (const class) не существует. Но часто под этим понимается объявление вида const CFoo p;.
Экземпляр класса CFoo, объявленный таким образом, обещает сохранить физическое состояние класса, не менять его. Как следствие, он не может вызвать не const функции класса CFoo. Все данные, не объявленные как const, начинают трактоваться как const. То есть
int становится int const
int * становится int * const
const int * становится int const *const
и так далее.


На этом все о const, но будет еще отдельный пост о том, как избавиться от const, то есть о mutable и const_cast.


Ссылки по теме:
Advice From the C++ Experts: Be Const-Correct
Const Correctness in C++
comp.lang.c++.moderated Const member functions
comp.lang.c++.moderated static const member of class
comp.lang.c++.moderated const classes and const members

Technorati tag: cpp

Сегодня видела Никлауса Вирта

Побывала сегодня на широко разрекламированной лекции профессора Никлауса Вирта (Niklaus Wirth) "История и перспективы языка Оберон" в Политехническом музее (да, это тот самый Вирт, который придумал Паскаль). Не то чтобы я была большой поклонницей Оберона, но Вирт к нам не часто приезжает, такое событие пропускать нельзя.
Начал он разговор с Модулы-2, потом плавно перешел на Оберон. Я не буду подробно пересказывать, что он рассказывал об этих языках. Информацию о них можно найти по ссылкам с сайта www.oberon2005.ru.


Самой интересной частью встречи были вопросы из зала. Вирт отвечал на вопросы и иногда отвлекался от вопросов и пускался в рассуждения по теме. Вот самые интересные ответы профессора.

Вирт несколько раз повторил фразу, что задача преподавателей учить системному мышлению ("Teach clear systematic thinking").
"При обучении язык должен быть на втором плане. Не надо учить на C++."

"Индустрия влияет на программирование. Раньше цена ошибки была велика. А теперь, если что-то не работает, можно поменять. Раз поменял, не работает? Опять поменял. Это грустно."

"Современный программист как бы смотрит через библиотеки. Просто ищет нужную процедуру. Я бы никогда так не учил."

"Я слышал, что Sun купила Оберон. Значит ли это что для создания компилятора Оберона надо покупать лицензию?
Sun не покупала Оберон. Она купила исходники компилятора Оберон. Кстати, очень за дешево. А через 7 лет они выпустили Java, используя идеи Оберона в слегка извращенном виде.
Не нужно лицензии. Мы вообще поклонники open source."

"Что вы думаете о динамических языках?
Типизация должна быть статической. Динамическая медленнее. Ошибки в типизации должны быть пойманы на этапе компиляции."

"Вы рассказываете, что Оберон такой хороший, компактный. Почему бОльшая часть программ написана не на нем?
Я не знаю. Сила привычки. Например, если в компании работает 20 сотрудников и они знают Фортран, они будут писать на Фортране. C получил широкое распространение, потому что UNIX стал популярен. И за C, за PL/1 стоят большие организации с хорошими отделами продаж.
А вообще, я переадресую этот вопрос вам."

Много было просьб высказать отношение к какому-либо языку или технологии.

"Ваше мнение о языке C#.
C# - это реакция Микрософта на Java. Если вы хотите услышать что-либо позитивное, пожалуйста: C# гораздо лучше чем C++."

"Как вы относитесь к UML?
Я не поклонник UML. Эти графики годятся только для выражения небольших идей."

"Smalltalk годится чтобы учить возить черепашку по экрану. В остальном бесполезен."

"Ваше мнение по поводу логического программирования, Пролога.
Пролог - это прекрасная академическая забава."

"Что вы думаете об Object Pascal, о Delphi? Вы принимали участие в этой разработке?
Delphi - это Паскаль с пользовательским интерфейсом. Ничего фундаментально нового. Я никак не участвовал в этом."

"Ада слишком тяжела для преподавания. Но лучше чем C. В 77 году я был приглашен для консультаций по поводу Ады. Она слишком сложная, мы тогда предложили кое-что устранить, но это не было сделано. Военные хотели сложную систему."

Там был переводчик, который пытался переводить то, что говорил Вирт. Я понимаю, что синхронный перевод - это очень и очень непростая задача и переводчик имеет право на ошибку, но все равно, это было ужасно. Переводчик безусловно знал английский, но на этом все. Он постоянно перебивал Вирта, пытался говорить с ним одновременно, поэтому что именно произносит Вирт было не всегда слышно. При этом переводчик явно не понимал о чем вообще идет речь. Англоязычные термины, конечно, не всегда просто перевести на русский. Но это было слишком:
typing system - система печатания
tree structure - три структуры
variable - вариативный
programming language - программирующий язык
После этих и подобных "переводов" в зале раздавался радостный смех, что каждый раз несколько озадачивало Вирта, он явно не понимал, чему народ так радуется. Когда же Вирт говорил о чем-то простом и понятном, переводчик радостно добавлял туда отсебятину. Неудивительно, что последний вопрос из зала был встречен бурными аплодисментами.

"Как вы относитесь к созданию переводчика, который полностью заменит человека? Компьютера, который полностью заменит человека?
Совсем полностью заменит? Мне бы она не понравилась."

Как вы, наверное, заметили, Вирт несколько недолюбливает C и C++, противопоставляет им Оберон. Он создавал очень небольшой, строгий, не громоздкий язык, спецификация Оберона занимает всегдо 16 страниц, что гораздо меньше, чем спецификация C++, и Вирт этим гордится. Вообще поклонники Оберона очень часто противопоставляют Оберон и C++ [Oberon против С++, pdf]. И ставят такие акценты: возможно приведение типов - значит считай, что нет типизации. Можно объявить friend функции - значит считай, что нет инкапсуляции. И т.п. Имхо, неправильно это. Да я теоретически могу использовать приведение типов, но это не значит, что я это делаю постоянно. C++ предоставляет программисту свободу, за что я и люблю этот язык, но этой свободой надо пользоваться аккуратно.

Ссылки, рекомендованные Виртом:
www.Oberon.ethz.ch
www.Oberon.ethz.ch/WirthPubl
www.Oberon.ethz.ch/books.html

Еще мнения об этом событии:
Flying in a blue dream - несмотря на название, все на русском.
Wirth - тоже на русском

Technorati tag: программирование

Использование const. Часть 1.

Есть две точки зрения на использование const.
Первая: const - это плохо. От него больше хлопот, чем пользы, ошибки какие-то странные вылезать начинают, лучше им не пользоваться.
Вторая: const - это хорошо. const не дает менять объекты, которые не должны меняться, таким образом оберегает от ошибок, его надо использовать везде где только можно.
Я придерживаюсь второй точки зрения.
В английской литературе можно часто встретить термины const correctness и const correct code, для кода, который корректно использует const. const имеет немного разный смысл в зависимости от того где находится. В C++ FAQ Lite вопросу Const correctness посвящен отдельный раздел.

Объявление переменных
Самый простой случай, обычная переменная. Переменная объявляется, тут же инициализируется, менять ее значение больше нельзя.

const int p=4;
p=5; //ошибка

Про использование const с указателями есть известный C++ паззл, который любят давать на собеседованиях при приеме на работу.
Чем отличаются

int *const p1
int const* p2
const int* p3

Правило тут такое: провести мысленно вертикальную черту по звездочке. То, что находится справа относится к переменной. То, что слева - к типу, на который она указывает. Вот например:

int *const p1

Cправа находится p1, и это p1 константа. Тип, на который p1 указывает, это int. Значит получился константный указатель на int. Его можно инициализировать лишь однажды и больше менять нельзя.
Нужно так:

int q=1;
int *const p1 = &q; //инициализация в момент объявления
*p1 = 5; //само число можно менять

Вот так компилятор не пропустит, потому что идет попытка присвоения константе:

int q=1;
int *const p1;
p1 = &q; //ошибка

Объявления

int const* p2
const int* p3

это по разному записанное одно и то же объявление. Указатель на целое, которое нельзя менять.

int q=1;
const int *p;
p = &q; //на что указывает p можно менять
*p = 5; //ошибка, число менять уже нельзя

Обычно в реальных программах используется вариант объявления const int, а int const используется, чтобы запутать на собеседовании.

const можно использовать со ссылками, чтобы через ссылку нельзя было поменять значение переменной.

int p = 4;
const int& x=p; //нельзя через x поменять значение p
x=5; //ошибка

Константная ссылка - это нонсенс. Она по определению константная. Компилятор скорее всего выдаст предупреждение, что он проигнорировал const.

int& const x; //не имеет смысла

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

void f1(const std::string& s);
void f2(const std::string* sptr);
void f3(std::string s);

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


Приведение Foo** к const Foo** приводит к ошибке
Потому что такое приведение может позволить менять объекты, которые константны.

class Foo
{
...
public:
 void modify();  //вносит какие-либо изменения
};

int main()
{
 const Foo x;
 Foo* p;
 const Foo** q = &p;  // q теперь указывает на p; и это ошибка
 *q = &x;             // p теперь указывает на x
 p->modify();         // попытка изменить const Foo!!
}

Самый простой способ это исправить это поменять const Foo** на const Foo* const*.

В следующих постах речь пойдет об использовании const для данных и функций классов, а также о mutable и const_cast.

Ссылки по теме:
[18] Const correctness, C++ FAQ Lite
comp.lang.c++.moderated is const correctness a dogma ?

Technorati tag: cpp

Публикации и интервью Александра Степанова

Различные публикации и интервью Александра Степанова, создателя STL.

Перевод куска из его интервью журналу Dr. Dobb's Journal.
"Давайте разберемся, почему C - великий язык. Люди верят, что C - это хак, который был успешным, потому что на нем был написан Unix. Я не согласен. [...]. С, как отражение гения Денниса Ритчи, предоставлял минимальную модель компьютера, который к тому моменту развивался около 30 лет. С не был быстрым хаком. Пока компьютеры развивались, чтобы уметь решать все виды проблем, С, будучи минимальной моделью такого компьютера, стал очень мощным языком для очень эффетивного решения всех проблем в различных областях. В этом секрет переносимости С: это лучшее представление абстрактного компьютера, что у нас есть. Конечно, это абстракция сделана на множестве реальных компьютеров, а не на множестве воображаемых вычислительных машин."

Нашла на блоге GrammerJack, Essays on games and game programming.

Перевод выступления Кармака на Quakecon 2004

Это перевод выступления Кармака на Quakecon 2004, то есть прошлогоднего, не этого года. Там он рассказывает как что сделано в Doom'е, чем он недоволен и что собирается делать дальше. Видеозапись весит 350 Мб, но добрые люди не поленились послушать и записать ее в текстовом виде: John Carmack Quakecon 2004 Keynote. Кармак говорит так, что люди, для которых английский родной язык, понимают его с трудом. Что уж говорить, когда английский не родной. А вещи он рассказывает интересные. Я сочла это несправедливым и поэтому перевела его выступление на русский.
Я стремилась не просто сделать перевод на русский, а чтобы еще при этом стало понятнее о чем речь. Поэтому слегка пришлось текст изменить, но совсем слегка. Я старалась не только смысл оставить нетронутым, но и как можно меньше изменить стиль повествования.
Лохматую теорию я подсветила, поэтому если теория не интересует, эти части можно смело пропускать. Если же, напротив, интересует, там по ходу я ставила ссылки на объяснения теории. Ссылки в основном на англоязычные ресурсы.
Я разделила все повествование на части, чтобы было за что глазу зацепиться. Деление на части условное, потому что он плавно переходит от одной темы к другой.
Речь большая, поэтому прежде чем читать налейте себе чайку и сядьте поудобнее...

---

Выступление Джона Кармака на Quakecon 2004

Перевела Алёна: alenacpp.blogspot.com

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

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

Недостатки Doom 3

Итак, с точки зрения графики в Doom 3 есть несколько недостатков.

Видимые швы

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

Расчет спекуляра

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

В основном это результат того, что изначально движок делался на основе возможностей блоков объединения регистров (register combiners) железа класса NV10/NV20. С тем что может железо поколения DX9 и старше, то есть железо класса NV30/R300, вообще нет причин как-либо ограничивать себя в показателях степени спекуляра. Мы, как ни странно, не используем степени вообще, нет последовательности из косинусов, возведенных в степень, как обычно. В действительности в Doom используется что-то вроде вырезающей функции (windowed function), которая делает смещение и возведение в квадрат, это приемлемо работало на старом железе с фиксированной функцией и было на самом деле чуть проще контролировать, потому что при этом был очень ограниченный спад освещенности. Тогда как в теории классическое затенение Фонга с косинусом, возведенным в степень, не покрывает полностью спад и вы получаете небольшое сложение по всей области и это чуть лучше, чем полное разделение.

Фрагментная программа на самом деле использует ссылочную таблицу текстуры (texture lookup table) для степени спекуляра и я просто сделал эту текстуру такой, что она точно совпадает с тем, что вычислялось на старом железе с фиксированной функцией, но можно легко заменить эту текстуру на что угодно. Все, что я сделал в новых проходах рендерера - это сделал эту текстуру двумерной, таким образом вся выборка спекуляра происходит с дополнительной текстурой, которая содержит в себе коэффициент отраженного света (specularity factor). То, что мы называем картами спекуляра в Doom 3 более известно под названием "карты блеска" ("gloss maps"), где они действуют лишь на интенсивность пятна спекуляра.

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

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

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

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

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

В основном это из-за использования кубических карт окружения (cubic environment maps) для нормализации. Если это заменить на вычисления, то опять, только при ARB2 проходе, вы получаете пятно лучшего качества, но все еще немного не то... там получается две нормализации. Одну из них я заменил вычислениями, вторая все еще делается через выборку из текстуры. То есть есть возможность для небольшого улучшения, можно опять заменить выборку из текстуры математическими вычислениями.

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

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

Над чем идет работа сейчас

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

Улучшение спекуляра

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

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

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

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

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

Переход к буферам теней

Самое большое изменение, которое скорее всего случится в движке следующего поколения - это переход к буферам теней (shadow buffers) вместо теневых объемов (shadow volumes). Это было одно из тех больших ключевых стратегических решений, которые должны были быть сделаны в движке Doom'а на ранних этапах. У меня была, давно еще, версия кода, которая ренедрила и буферы теней, и теневые объемы, чтобы я мог сравнивать их производительность и качество изображения.

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

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

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

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

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

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

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

Даже если вы берете построенное на железе процентно близкое фильтрование (percentage closer filtering [PCF, ссылка на pdf]) и вы ренедерите карты теней неприлично большого разрешения (2000х2000 или больше), они все равно не выглядят хорошо. В целом, легко сделать их выглядящими гораздо хуже, чем стенсильные теневые объемы, когда вы делаете только начальный уровне фильтрации на железе. Вы получаете все эти проблемы со сдвигами и проблемы с пиксельной крупой и все это не очень-то и хорошо.

Однако, когда вы начинаете добавлять случайное дрожание (randomized jitter) в самплы (достаточно взять не так уж и много сэмплов, чтобы все выглядело пристойно), это полностью меняет картину. 4 рандомизированных сэмпла, возможно, будут нашей отправной точкой спецификации нормального вида на выходное качество для следующей игры. Это выглядит весьма неплохо.

Там есть немного... Если взглянуть на широкие мягкие тени, там возникает небольшое дрожание пикселов, когда объекты перемещаются вокруг, но при рандомизации это выглядит гораздо лучше, чем построенное статически. Это достаточно хороший уровень, и самая хорошая вещь это то, что потому что вычисление сэмплов теней совершенно отделено от других аспектов движка рендеринга, вы можете перемешивать столько сэмплов, сколько захотите. В моих текущих изысканиях у меня есть версия из 0 сэмплов, это аппаратный PCF, для сравнения. С одним случайно зашумленным сэмплом, с четырьмя сэмплами - это что-то вроде точки отсчета, и версия из 16 сэмплов, которая может дать вам очень хорошие, высококачественные мягкие тени.

Я возможно перемешаю и побольше, например 25 или 64 сэмплов, что скорее всего будет использовано для рендеринга офлайн, если люди захотят что-либо отрендерить и они не будут против, чтобы это работало со скорость несколько кадров в секунду. Вы можете получить качество теневых эффектов как в кино, просто меняйте количество сэмплов, с которыми работаете. Это оказывается очень близко к тому алгоритму, который Пиксар использовал во многих мультфильмах, основанных на Рендермене, это уже работает на сегодняшних CPU в реальном времени при маленьком количестве самплов.

Это очень воодушевляет, потому что в дополнении к мягким теням, которые являются модным словечком, на которое люди ориентируются... Хорошо, у вас есть линия тени на полу, будет ли при этом четкая разница между поверхностью внутри света и поверхностью внутри тени или у вас там приятные гладкие переходы, сначала затемнение (umbra), а потом высветление (penumbra)?

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

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

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

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

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

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

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

Часть этого из-за API железа. Сейчас я использую p-buffer из OpenGL и интерфейс рендеринга в текстуру, это ПРОСТО КОШМАРНЫЙ интерфейс, он слишком многое наследует из плохих дизайнерских решений времен SGI, и у меня были дни, когда я был особенно близок к переходу на D3D, потому что API были просто ужасающе плохими. И ATI, и NVidia имеют свои предпочтительные направления по эффективному рендерингу в текстуру, потому что проблема с существующими API была не только из-за того, что это были убогие API, там еще была довольно сильный удар по производительности, потому что вам требовалось переключить контексты рендеринга (rendering context) в OpenGL, а для буферов теней это нечто, что случается по 100 раз на кадр, и сегодня это слишком большой удар по производительности.

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

Проблемы с железом сейчас таковы: у NV40 есть несколько вещей, которые делают разработку для меня проще. У него есть блендинг с плавающей точкой, что экономит мне несколько проходов для того, что я делаю... Нет, ну конечно есть пути для отступления, так как все, что мы делаем с блендингом мы может делать с еще одни проходом и еще одной копией текстуры, чтобы это все работало на железе уровня NV30 и R300. Это неплохо, и там неограниченное число инструкций на NV40... Бывают времена, когда я пишу большие фрагментные программы и удобно записывать туда все больше и больше. Но я хорошо знаю, мне в итоге придется разделить это на куски, которые смогут работать на железе класса R300.

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

Есть замечания, например как в книжке по Рендермену, где говорится: "попробуйте сделать свет, отбрасывающий тень от объектов как спотлайт (spotlight) на 20 градусов и используйте текстуру размером 2k x 2k и у вас получатся хорошо выглядящие тени". Проблем в том, что в играх 99+ процентов всех теней это тени от точечных источников (omnidirectional point lights) света. Чтобы отрендерить точечный источник света с буфером теней потребуется замыкающий полигон. Который проще всего сделать с помощью шести проекций на плоскости. Теперь что выходит. В любой момент, как только какой-либо объект пересекает этот бордюр, он должен быть отрендерен несколько раз. И опять, в типичной графической демке, где у вас ваза с фруктами на плоской поверхности, весь объект помещается в ограничивающую область и очевидно вам нужно только один лишний раз отренедрить эту геометрию, чтобы сделать буфер теней, а потом его использовать.

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

Другой фактор, связанный с этим, это то, что вы видите в программах офлайнового рендеринга, которые часто используют буферы теней: вам приходится делать трюк со сдвигом, чтобы все выглядело правильно. Есть два вида стандартных проблем с буферами теней, два вида артефактов. Когда сдвиг установлен слишком маленький, у вас получается "теневая сыпь" ("shadow acne"), получаются темные мазки теней на тех поверхностях, что освещены, потому что значения в сдвиге недостаточны для того, чтобы убрать тень с поверхности совсем. Когда у вас наложен зашумленный сэмпл, он дает более сглаженный вид с небольшим лишним шумом и это уже не ужасно, но это не то, чего хотелось бы.

Другой артефакт вы получите, если у вас есть слишком большой сдвиг. Тени сползут. Если у вас есть поверхность которая касается пола, то тень не начинается, скажем, прямо от пятки персонажа, а начинается в нескольких пикселах позади него, потому что так работает сдвиг. И это довольно неприятный артефакт, когда вы смотрите и видите скамейки и объекты типа них, а тень падает не точно от них.

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

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

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

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

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

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

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

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

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

Решение, которое я ищу для освещения открытых пространств, это что-то вроде мипмэппинга для буферов теней, где буфер теней размером 1k x 1k используется для, скажем, 2000 единиц рядом с вами и он обрезан таким образом, чтобы покрыть это пространство динамически. Потом вы масштабируете на степени двойки, до тех пор пока вы не закроете весь мир, что может потребовать 5 или 6 буферов теней, в зависимости от того, насколько велико ваше открытое пространство. Это не так уж и сложно и заканчивается рендерингом шести видов для одного точечного источника для открытого пространства. Я думаю это вполне решаемая проблема.

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

Но вот что интересно, получается, что это не совсем то, чего бы вам хотелось. Чтобы сделать эффективный буфер теней в реальном игровом движке вам нужно менять разрешение этой карты теней все время. Если вы видите 50 источников света, то вы не можете рендерить буфер теней размером 2k x 2k для всего, особенно, если большинство источников света могут светить только на 50 пикселов.

Так вот, что я делаю, я динамически масштабирую все разрешения для каждого источника света, который будет отрисован, в зависимости от того, насколько он велик на экране, можно использовать другие параметры в эвристике, другую эвристику. Но потому что тот путь, что я использую для выбора областей, принимающих расчеты теней... я использую для них тесты стенсильного буфера, так что вся работа происходит со стенсильными буферами и за все алгоритмы оттуда приходится чем-то расплачиваться в новом движке, даже хотя мы не используем это напрямую для затенения. Но из-за способа, которым я выбираю области экрана, мне не требуются соединения, или даже текстуры степени двойки для буферов теней, потому что они будут ровно смасшатабированы от 2000 до 1900, 1800 и так далее, вместо скачков по степеням двойки от 2048 до 1024,и т.п. Это так же в итоге сохраняет значительное количество памяти. Посмотрите на большой буфер, размером 2k x 2k с буфером глубины в 24 бита, вы знаете, это 4 миллиона пикселов по 4 байта каждый. И если вы храните в нем полную кубическую карту, это хороший кусок вашей видеопамяти. Так что выгоднее рендерить одну сторону за раз, по крайней мере для источников света, которые близко.

В случае маленьких источников света, где не займет много места рендерить все прямо как кубическую карту, будет выигрыш по производительности. Довольно много 3Д железа на подходе, которое будет позволять рендерить кубическую карту в один проход. Я не сторонник этого. Я старался как мог убить эту идею на последнем Саммите по Графике Windows (Windows Graphics Summit). Это не сработало, все эти вещи прошли, и прозводители железа, я уверен, в итоге заставят все это работать правильно. Но я задаю вопрос о действительной пользе больших затрат на обработку геометрии, которые появятся с заменой всех отдельных нарезанных видов на 6 различных видов, с которыми можно работать одновременно.

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

Так что построение теней это БОЛЬШОЙ вопрос. У меня оно работает, выглядит хорошо. Сейчас оно не умеет работать с требовательными ситуациями. У меня не сделано освещение открытых пространств. У меня нет правильной спецификации отдельных источников света, насколько сильно размыты края, например.

Размытие краев, получаемое с помощью буфера теней, это не настоящее затенение и высветление. Мягкая часть теней реального мира зависит от размера источника света, расположения окклюдатора (occluder) и расположения поверхности, на которой он находится. И получаются различные эффекты, такие как расширение мягкой тени. От точки пересечения с окклюдатором и поверхностью она становится все шире и шире вплоть до того, что маленькие окклюдаторы полностью поглощаются широкой распространившейся областью источника света. Вы не получите точно такие эффекты, но опять это стандартное качество для многих ренедереров фильмов, которые делаются годами и которые дают дизайнерам контроль над тем, что им нужно. Они могут сказать "Ну этот свет будет иметь большой угол и мы хотим получить более смазанные тени, тогда как вон тот, вон там, распространяется на такую большую область, мы его должны уменьшить, чтобы уменьшить шум" и там будет немного подпихиваний различных параметров.

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

Поверхности

Так, будет еще одна важная вещь: много моделей поверхностей. Есть некоторые специфичные вещи, которые мы хотели бы сделать, добавляя такие возможности, как распространение света в материалах (subsurface scattering), чтобы цвет кожи выглядел лучше, частичная полупрозрачность, чтобы получить что-то вроде свечения через края частично прозрачных объектов, таких как уши, освещенные сзади. Приемы, чтобы сделать волосы лучше и т.п.

Прозрачность, не зависящая от порядка отрисовки

Я был удивлен, когда спросил Тима, что бы он хотел улучшить с точки зрения гейм дизайнера. Больше всего нужна полупрозрачность, не зависящая от порядка объектов (order independent translucency). В Doom'е нет хорошего решения для полупрозрачности, не зависящей от порядка объектов. Примерно такой же подход у нас был в Quake3, там различным материалам можно было присвоить значения для сортировки и маленькие значения всегда рисовались до больших значений. Есть ситуации, когда это никак не может работать, например, если у нас две поверхности с альфа блендингом и вы можете подойти с любой стороны, то есть объект A может располагаться перед объектом B, а может объект B располагаться перед объектом A. Мы не можем заставить текущий движок отобразить это корректно.

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

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

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

Еще один многообещающий путь, возможно это наше основное направление, работать с прозрачностью в одном буфере, но как бы иногда отделяя пикселы, которые прозрачны, чтобы они не перемешивались с другими пикселами, а потом использовать постобработку, чтобы все проблемы решить разом. Я пытался сделать это на ранних этапах разработки Doom'а, но тогда не было хороших возможностей сделать фильтры для постобработки. Получалось нечто совершенно неприемлемое, просто мешанина. Однако сейчас у нас есть некие общие возможности фильтрования, и чтобы улучшить различные моменты, я много работаю с фильтрованием на последней стадии обработки. Я сделал несколько демок по полупрозрачности, самый простой возможный вариант: например вам нужно, чтобы объект был прозрачен на 50 процентов. Вы используете для него отдельную пунктирную (stipple test) текстуру, у вас там используется только 50 процентов от пикселов и они совершенно непрозрачны, это важно для рендерера. Половина пикселов показывает сам объект, половина то, что находится за ним.
С точки зрения отрисовки все работает хорошо, освещение и затенение такие как надо и все работает, потому что это непрозрачная поверхность. А потом идет последний проход, который отрисовывает прозрачные объекты, по существу смешивает вместе четыре рядом стоящих пиксела.

Когда у вас фиксированная сетка пикселов, как, например, каждый второй или каждый четвертый пиксел, то есть маска регулярная, это выглядит отлично. Это идеальная полупрозрачность, на нее падают тени, на нее падает свет, из-за полупрозрачности видно то, что находится за ней, и работает все здорово. Дело в том, что на этом этапе мы можем еще улучшить то, что у нас есть. Если бы можно было для данного полупрозрачного объекта указать, какого вида пунктир будет, тогда имея объект A и объект B с непересекающимися пунктирами или пересекающимися только в определенных местах, вы бы получали полупрозрачность, не зависящую от сортировки и это работает замечательно. Гораздо хуже, если вам нужны произвольные уровни прозрачности.

Сейчас это можно сделать с помощью дизеринг-операций (dithering operations). Если вы используете дизер-маску размером 2x2 или 2x4, или маску пунктира, значения фиксированы, а затем, статически или случайным образом, сдвигаете полученное значение прозрачности, полученной либо из карты прозрачности, либо из альфа-интерполятора, из чего угодно, что вы для этого используете. Можно все это смешать и делать из этого случайные выборки, но я не доволен результатом, даже если я накладываю достаточно широкое ядро фильтра, и если выбирать случайным образом различные маски, это все еще визуально слишком зашумлено. У нас есть определенные уровни с хорошим качеством, это 25%, 50%, 75%, неважно, которые выглядят превосходно, а когда между ними интерполируешь, привносится все больше и больше шума. Это то направление, к которому я сейчас склоняюсь, но лишь позже, когда у нас будет больше результатов, мы сможем оценить все проблемы, которые возникают при этом подходе.

Разработка следующего движка

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

Что будет выставлено как программируемые фичи? Как будут происходить процесс создания контента и использование движка? Сложно сказать, насколько важна каждая из этих вещей, там внутри много моментов, который я считаю упущениями в движке Doom'а. Например деформации поверхностей с помощью автоспрайта или с использованием каких-либо других деформаций, иногда происходят в не том месте конвейера и освещаются. Безусловно, мы хотим это поправить в следующем движке, где вся геометрия будет освещена и затенена абсолютно корректно.

Интересные моменты связаны с написания ядра рендерера Doom'а 3. Оно может рендерить практически те же самые картинки, что у нас есть сейчас. Это было 4 года назад, и я делал это на С. Я взял Quake3, удалил оттуда рендерер, написал совершенно новый рендерер на C, встроил и начал тестировать. Когда вся команда начала работать над Doom'ом мы решили все делать на C++. Все было подключено, начали писать новые куски кода. Вся остальная работа над отрисовщиком делалась на C++, но там все еще есть наследие C, которого не будет в новом движке. Там все будет построено на обмене сообщениями между объектами, а не на передаче структур. Я наполовину поменял это в Doom'е, когда вы взглянете на заголовки SDK, вы увидите симпатичные новые интерфейсы классов. Но есть еще сетап, где вы передаете указатели на элементы отрисовки и отрисовываете источники света вместе со структурами данных, а на самом деле там должен быть просто класс.

Интересно, что когда я начал работу над следующим движком пару месяцев назад, когда я сел и стал тестировать некоторые вещи, сделал некоторые реальные фичи для теста рендеринга, я заметил, что этот экспериментальный режим опять отбросил меня назад на функциональное C программирование. В конце концов я сделал класс, который инкапсулировал ужасный pbuffer и интерфейс отрисовки в текстуру. Когда же я просто хачил графику, как-то было более естественно для этого использовать функциональный интерфейс программирования. Любопытно, это верно только для меня, или так на самом деле работают с графикой?

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

Многие проблемы с дизайном движка отрисовки на самом деле не связаны с рисованием картинок, потому что все рисуют все одинаково, вне зависимости от того, что рисуется это приводит к одному: линкуем фрагментную программу, вертексную программу, устанавливаем параметры, подгружаем текстуры, рисуем пачку треугольников, внутри это все абсолютно одинаково, все так делают для 3Д железа.

Так что в теории, все движки могут рисовать медию (media) всех других движков, потому что в основном они делают все то же самое. Все инновации и важные решения принимаются по поводу того, как именно вы определяете какая будет геометрия, какие будут текстуры, какие будут программы. На что я всегда ругался - это когда люди делают просмотровщики шейдеров и вещи типа этого и интегрируют шейдеры в утилиты типа 3D Studio and Maya, такие вот, не очень полезные вещи. Да, это позволит вам взять программу и скормить ей геометрию, но все интересное, что случается в движке, идет от таких вещей как взаимодействие и передача параметров, и как игровой мир определяет параметры, которые используются для отрисовки, как движок отрисовки составляет вместе различные слои эффектов и разные части программ. Так что у вас не будет большого количества таких вещей как просто "вот здесь фрагментная программа". У вас это все сделано для спецэффектов, для всех эти артефактных эффектов. У нас есть марево, я включил его в игру на позднем этапе и используется оно повсюду в игре, только потому что людям нравятся такие вещи. Такие спецэффекты как эти, показывают какая есть польза от того, что "здесь фрагментная программа делает этот спецэффект". Но так много вещей являются динамическим сочетанием различных программ. Если у вас накладывается карта прозрачности, где вы должны определить какие области должны быть отрисованы, все это объединяется с разными взаимодействующими программами: с различными программами затенения, с деформациями поверхностей высокого уровня. Здесь несомненно будет происходить динамическое комбинирование различных программ.

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

Один из самых простых путей, который я возможно попробую самым первым, это добавить что-то вроде макро возможностей в фрагментные программы, чтобы можно было сказать "вычисли свет здесь, положи результат в регистр R0", и можно будет объединить свет двух проецируемых текстур или произвести вычисления, зависящие от реального расстояния, или использовать 3Д свет. Есть некоторое количество вещей, которые хочется иметь для шейдеров освещения, которые могут быть скомбинированы с различными шейдерами поверхности. В итоге хочется иметь возможность накладывать деформацию при отрисовке произвольной поверхности. Хочется иметь возможность сказать "Я хочу, чтобы деформация "трава, обдуваемая ветром" была наложена в нескольких различных местах". У нас есть ветки и трава и всякие разные вещи, которые могут использоваться на статических поверхностях, но также хочется, чтобы их можно было деформировать.

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

У нас есть такие вещи как карты высот, которые могут быть включены в игру, даже хотя они гораздо хуже карт нормалей для характеристик поверхности, но карты высот могут быть использованы для других вещей, например: если у нас со временем появится возможность делать карты смещений (displacement mapping) в игре, потребуется карта высот, а не карта нормалей.

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

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

У меня есть интересные мысли сделать возможным что-то вроде карты смещений пространства экрана, где мы рендерим различные смещения в экран, а потом идем назад и рендерим сцену, деформируя при этом объекты надлежащим образом. Это решит проблему с Т-пересечением (T-junction (cracking) problem), которая получается, если использовать настоящую карту смещения на поверхностях, где края не обязательно выровнены.

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

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

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

Сравнения с офлайновыми рендерерами

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

Например, можно будет использовать настолько большие текстуры, насколько захочется, во многих местах можно будет включить уровни сэмплинга повыше. Если захочется сделать очень-очень точное сияние света с высоким динамическим диапазоном (High Dynamic Range), можно, скажем, вместо того, чтобы три раза уменьшать размер сэмпла, делать их на уровне родного фрейм буфера, а вместо того, чтобы делать отдельный фильтр по Гауссу (Gaussian filter), взять и использовать настоящий фильтр размером 100х100, если вам действительно очень нужны идеальные линии сияния, исходящие от объектов.

И там будут области, где изменение данных позволит вам поднять производительность или качество ценой производительности и можно будет сделать рендеринг такого качества как в кино. Этот термин ["как в кино"] упоминается постоянно, с наступлением аппаратно ускоренной отрисовки (hardware accelerated). Многие люди упоминали этот термин говоря о Doom'е, но мы все еще живем с ограниченным набором возможностей рендерера и все еще есть огромное количество вещей, которые нужны для офлайнового рендеринга, но которые игровой движок не может делать. Со следующим движком у вас не будет абсолютно всех возможностей, которые есть у офлайнового рендерера. Но вы сможете делать сцены, которые будут практических неотличимы от обычного офлайнового построчного рендерера, если вы подадите на вход соответствующие данные и будете избегать некоторых вещей, которые он не делает хорошо. Мы сейчас видим графику с аппаратным ускорением, особенно готовящуюся к выходу графику с многочиповыми, многокарточными опциями, где у вас будет возможность, имея одну систему, ваш обычный бежевый бокс, набить туда несколько PCI-express систем с видеокартами, подключенными друг к другу, и вы получите, с таким игровым движком и с таким железом, возможности отрисовки такие как у крупных студий, как у всей Пиксаровской фабрики, и все это будет в коробке стоимостью 10 000 долларов.

В итоге получится не только производительность фабрики по отрисовки. Если посмотреть на это в терминах общего числа возможных кадров в определенный промежуток времени, важным фактором является дробная задержка. Если отрендерить кадр такого качества как в фильме занимает 30 минут, мы можете на это бросить 1000 систем и рендерить кадры пачками, но первый кадр все равно отрендерится через 30 минут. Если получится убить задержку так, чтобы рендерить на самом деле за 1/1000 от этих 30 минут, это будет гораздо лучше с точки зрения креативности.

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

Опасность излишнего усложнения движка на примере звука в Doom 3

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

Когда мы начинали, мы знали, что у нас намного больше мощности CPU и мы можем делать более сложные вещи с аудио. Итак, изначальный аудио движок Doom'а имел моделирование головы, моделирование комнаты и весь этот обычный для DSP набор вещей, который есть когда вы думаете о виртуальных пространствах и эмуляциях. Это вроде как работало, но у нас были опции где можно было сказать "здесь использовать простой звук". И если звуковым дизайнером не нравилось как что звучит, потому что движок что-то не так делает со звуком, звук можно было поставить обычным.

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

Кода осталось меньше половины с тех пор как я за него взялся. Сейчас он хороший, добротный, предсказуемый и делает то, что звуковые дизайнеры от него хотят. Так что в этом случае кажется, что звук у нас феноменальный, и при этом все сделано очень просто. Дизайнерам для работы было предоставлено хорошее полотно, они знают что каким образом будет звучать. Они могут их сделать слегка потише, в зависимости от того где вы находитесь. У нас есть возможность дать им проигрывать нелокализованные стереозвуки, урезать звуки. У нас есть несколько базовых фич, вроде "Вы хотите, чтобы это было заглушено?" "Вы хотите сделать цепочку порталов?". Но в целом все что делается, это берутся звуки, домножаются на текущий коэффициент затухания и складываются вместе. Здесь всегда есть опасность излишне усложнить движок, и, я думаю, мы избежали этого со звуком, вернули все и сделали именно то, что нам было нужно.

Это всегда вызывает беспокойство в связи с графическими технологиями, где можно делать очень сложные вещи, которые будут корректны, особенно с перемещением света: мы точно знает как работает свет, мы его можем очень точно имитировать. Если мы хотим потратить на это время, то можно сделать трассировку фотонов (photon tracing) и излучательность (radiosity) и все такие вещи. Но во многих случаях выходит, что это не только не нужно, но во многих случаях это даже не то, что вы хотите сделать с точки зрения дизайна игры. Например, прямо сейчас, когда идет эта видеозапись, несколько источников света установлены таким образом, чтобы было лучше видно то, что записывается на видео, не нужно натуральное освещение комнаты, в которой я нахожусь. И в офлайновых рендерерах свет устанавливается таким образом, что он не ведет себя точно так как ведут себя настоящие источники света: либо игнорируют поверхности, либо не отбрасывают тени, свет, который падает только на определенные вещи.

Утилиты, использовавшиеся при разработке Doom 3

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

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

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

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

Следующая игра

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

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

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

Мы можем делать интересные игры. Мы думаем, что делаем хороший дизайн игр. Но если id Software хочет сыграть на наших сильных сторонах как компания, а у нас есть замечательная технология и медиа в дополнении к дизайну игры и геймплею, мы выпустим другую игру, добротную игру с погружением для одного игрока, с минималистским мультрплеером. Опять же, уровень Doom'а, где все это есть, это базис, если люди хотят больше этого, пускай, и потом у нас будут компании-партнеры, возможно они будут работать над тем, чтобы поднять это на супер высокий уровень совершенства, что сегодня непросто для многопользовательских игр.

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