Содержание курса
- Статья 1: алгоритм Брезенхэма
- Статья 2: растеризация треугольника + отсечение задних граней
- Статья 3: Удаление невидимых поверхностей: z-буфер
- Статья 3.1: Настала пора рефакторинга
- Статья 4: Необходимая геометрия: фестиваль матриц
- Статья 5: Пишем шейдеры под нашу библиотеку
- Статья 6: Чуть больше, чем просто шейдер: просчёт теней
Данная статья написана в тесном сотрудничестве (спасибо создателям XMPP) с haqreu, автором данного курса.Мы начали масштабный рефакторинг кода, направленный на достижение максимальной компактности и читаемости. Мы сознательно пошли на отказ от ряда возможных и даже очевидных оптимизаций для получения максимально доступного для понимания кода учебных примеров.
P. S haqreu буквально на днях выложит статью о шейдерах!
UPD: ВНИМАНИЕ! Раздел, начиная с номера 3.1, 3.14 и 3.141 и далее, будет о тонкостях реализации основы основ компьютерной графики — линейной алгебры и вычислительной геометрии. О принципах графики пишет haqreu, я же буду писать о том, как это можно внятно запрограммировать!
1 Общие положения
Предыдущие статьи цикла показывают, что для написания программного отрисовщика нужно реализовать изрядную долю алгоритмов и математических объектов, относящихся к линейной алгебре и геометрии. В первую очередь, речь идет, конечно же, о векторах и матрицах. Мы используем векторы и матрицы мелких размерностей, поэтому нам удобно размещать их на стеке. Мы реализовали их при помощи шаблонов vec<size_t Dim, typename number_t> и mat<size_t size, typename number_t>. В комментариях к одной из статей я показал, что (по крайней мере, когда в роли компилятора GCC), использование циклов даже в таких мелких случаях дает более короткий и компактный машинный код, а также страхует от глупых опечаток при поэлементном наборе, например, операции матричного умножения.
Код в данной статье написан для стандарта версии C++98, поэтому страшноват (верните мне auto!). Возможно, я подготовлю отдельную статью с тем же кодом, но с применением свежего стандарта. Держитесь, шаблоны с переменным количеством параметров, для вас будет работенка!
2 Что интересного случилось в процессе слияния и рефакторинга?
2.1 Повсеместное использование size_t для индексов массивов
Напомню, что пункт 18.1 стандарта С++, ссылаясь на пункт 7.11 стандарта C, определяет size_t как беззнаковый целый тип. Для нас это удобно, потому как, во-первых, это прямо соответствует смыслу индекса в массиве, а во-вторых, для проверки того факта, что i действительно находится в границах массива, нам достаточно проверить одно условие: (i < размер_массива) вместо двух: (i >= 0) && (i < размер_массива). Неуместный int будет изо всех мест убран.
2.2 Странный цикл for
Вот цикл for, который некоторые могут счесть странным: for(size_t i=Dim;i--;) {}; Этот цикл переберет все значения i от Dim-1 до 0. Перебор начнется с Dim-1, потому как перед входом в тело цикла будет выполнена сначала проверка, что i отлична от нуля, затем декремент i, и только после этого — вход в цикл. После заключительной итерации мы получим i=0 (цикл должен завершиться), но все равно должны будем (по смыслу операции i--) вычесть из беззнаковой i единицу. Это действие вполне определено стандартом, так что ничего страшного не произойдет — мы просто получим значение, равное 
. Почему сделан именно этот цикл, а не традиционный for(size_t i=0;i<Dim;i++)? Две причины. Первая: показать пример правильного прохода по i в сторону убывания с беззнаковой переменной. Часто можно встретить ошибку: for(size_t i=Dim-1;i>=0;i--) Умница-компилятор, увидев тождественно истинное выражение [беззнаковое целое] >=0 просто заменит его на истину: for(size_t i=Dim-1;true;i--), что приведет к бесконечному зацикливанию. Вторая: такая запись короче на целых три символа. К циклу for (а также к вопросу, «Что быстрее, ++i или i++»), мы в дальнейших статьях вернемся.
Мы можем пойти дальше:
дело в том, что большинство наших операций очень тривиальны, и тело цикла, их выполняющего, состоит из одной строки. haqreu предложил поступить так:
template<size_t Dim,typename Number>vec<Dim,Number > operator-(vec<Dim,Number > lhs, const vec<Dim,Number >& rhs) {
for (size_t i=Dim; i--; lhs[i]-=rhs[i]);
return lhs;
}
Фактически, мы убрали нашу операцию внутрь заголовка цикла, сделав тело цикла пустым.
2.3 Код шаблона для вектора
В нашем шаблоне для вектора определены на настоящий момент пять методов, два из которых являются операторами: это операторы взятия константной и не константной ссылки на элемент вектора []. При помощи макроса assert из <assert.h> они проверяют, что переданный им индекс остается в пределах массива, что очень важно для обнаружения совсем глупых ошибок. В релизной версии мы добавим к ключам компилятора -D NDEBUG, что приведет к удалению макроса из кода. По закону Мерфи, после этого все должно будет сломаться, но мы это преодолеем.
number_t& operator [](size_t index) {
assert(index<Dim);
return items[index];
}
const number_t& operator [](size_t index) const {
return items[index];
}
Метод fill(const number_t& val=0) заполняет вектор константой. По умолчанию это ноль.
static vec<Dim,number_t> fill(const number_t& val=0) {
vec<Dim, number_t> ret;
for (size_t i=Dim; i--; ret[i]=val);
return ret;
}
Методы norm() и normalize() предназначены для вычисления длины вектора и его нормировки, соответственно.
number_t norm() const { return std::sqrt( (*this) * (*this) ); }
Для вычисления нормы используется тот факт, что это всего лишь корень квадратный из скалярного произведения вектора с самим собой. Очень кратко, емко, и в то же время тесно связано с теорией.
Теперь нормировка вектора:
vec<Dim,number_t> normalize() const { return (*this)/norm(); }
Опять же, все точно по определению: взяли себя и поделили на свою же длину. Обратите внимание, что эта функция возвращает отнормированную копию исходного вектора, а не изменяет его координаты таким образом, чтобы он стал единичным.
Также отмечаю повсеместное использование const в данном коде. Это, с одной стороны, защищает от глупых ошибок, причем уже на этапе компиляции. С другой стороны, const дает компилятору больше сведений для проведения оптимизаций. Также замечу, что здесь нет ни одной директивы inline. Это связано с тем, что мы всю оптимизацию будем делать позже. Кроме того, с -O3 GCC становится настолько сообразительным, что сам выполняет встраивание. Станет ли он автоматически встраивать наши функции без явного inline, мы опять же будем рассматривать в последующих статьях.
2.4 Бинарные операции над векторами и скалярами
Операторы бинарных операций вынесены за пределы класса vec. Они полностью соответствуют определениям этих операций в теории:
template<size_t Dim,typename number_t> number_t operator*(const vec<Dim,number_t>&lhs, const vec<Dim,number_t>& rhs) {
number_t ret=0;
for (size_t i=Dim; i--; ret+=lhs[i]*rhs[i]);
return ret;
}
template<size_t Dim,typename number_t>vec<Dim,number_t> operator+(vec<Dim,number_t> lhs, const vec<Dim,number_t>& rhs) {
for (size_t i=Dim; i--; lhs[i]+=rhs[i]);
return lhs;
}
template<size_t Dim,typename number_t>vec<Dim,number_t> operator-(vec<Dim,number_t> lhs, const vec<Dim,number_t>& rhs) {
for (size_t i=Dim; i--; lhs[i]-=rhs[i]);
return lhs;
}
template<size_t Dim,typename number_t>vec<Dim,number_t> operator*(vec<Dim,number_t> lhs, const number_t& rhs) {
for (size_t i=Dim; i--; lhs[i]*=rhs);
return lhs;
}
Заостряю ваше внимание на тактике применения левого операнда (lhs) в трех последних реализациях. На вход мы получаем его копию, после чего над этой копией работаем и возвращаем. Если бы мы получали его по константной ссылке, нам пришлось бы делать копирование самостоятельно. Здесь очень удачно совпали свойства наших векторов и языка C++, чем мы и воспользовались. В реализации же скалярного умножения нам и вовсе не нужно копировать векторы — всю работу мы выполняем по константной ссылке.
2.5 Отдельно — о реализации деления вектора на скаляр
Так как все мы знаем математику, можем с удовольствием сказать «Для деления вектора на скаляр мы можем использовать умножение на величину, обратную этому скаляру». И настрочить вот такое:
/////////////////////////////деление вектора на скаляр
template<size_t Dim,typename Number>vec<Dim,Number> operator/(vec<Dim,Number > lhs, const Number& rhs)
{
return(lhs*(static_cast<Number>(1)/rhs));
}
Важный момент — как мы поступили с единицей — мы обернули ее в static_cast<>, чтобы у нее всегда был правильный тип при делении. Однако, проведя простой тест:
#include <iostream>
using namespace std;
int main()
{
const double a=100.8765;
const double b=1.2345;
cout.precision(100);
cout << a/b <<'n' << a*(1/b)<<'n';
return 0;
}
Мы можем увидеть, что результаты не сошлись:
81.7144592952612 356384634040296077728271484375
81.7144592952612 498493181192316114902496337890625
Получим более точное значение отношения при помощи maxima:
(%i5) fpprec:100;
(%i6) bfloat(100.8765/1.2345);
(%o6) 8.17144592952612 356384634040296077728271484375b1
Видим, что значение, полученное прямым делением, является более точным. Это связано с накоплением погрешности при арифметических операциях. Поэтому не будем жадничать, а напишем отдельную реализацию оператора деления:
template<size_t Dim,typename number_t>vec<Dim,number_t> operator/(vec<Dim,number_t> lhs, const number_t& rhs) {
for (size_t i=Dim; i--; lhs[i]/=rhs);
return lhs;
}
2.6 Операция погружения вектора в пространство большей размерности
Она нам понадобится в одной из версий растеризатора. Суть операции состоит в том, что мы формируем вектор большей размерности, методом fill заполняем его константой, которую нам передали, а потом копируем в него координаты нашего вектора меньшей размерности.
template<size_t len,size_t Dim, typename number_t> vec<len,number_t> embed(const vec<Dim,number_t> &v,const number_t& fill=1) { // погружение вектора
vec<len,number_t> ret = vec<len,number_t>::fill(fill);
for (size_t i=Dim; i--; ret[i]=v[i]);
return ret;
}
2.7 Операция проектирования вектора
Эта операция наоборот, из вектора большей размерности делает вектор меньшей размерности, лишние координаты при этом просто отбрасываются:
template<size_t len,size_t Dim, typename number_t> vec<len,number_t> proj(const vec<Dim,number_t> &v) { //проекция вектора
vec<len,number_t> ret;
for (size_t i=len; i--; ret[i]=v[i]);
return ret;
}
2.8 Переопределение оператора << для вывода векторов в поток ostream
Для отладки потребовалось реализовать вывод наших векторов на терминал. Для этого мы доопределили оператор << для случая, когда левый аргумент — ссылка на ostream, а правый — наш вектор или матрица. Теперь мы можем просто и привычно писать cout<<myvec:
template<size_t Dim,typename number_t> std::ostream& operator<<(std::ostream& out,const vec<Dim,number_t>& v) {
out<<"{ ";
for (size_t i=0; i<Dim; i++) {
out<<std::setw(6)<<v[i]<<" ";
}
out<<"} ";
return out;
}
3 Заключение
В последующих уточняющих статьях раздела 3.1… мы покажем подробности реализации работы с матрицами. Там будет даже рекурсия на шаблонах. До скорой статьи!
И да, напоминаю, что скоро haqreu выложит статью о шейдерах!
Автор: gbg
