Pull to refresh

Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 3.1 из 6

Programming *C++ *Game development *
Tutorial

Содержание основного курса


Улучшение кода



Общение вне хабра

Если у вас есть вопросы, и вы не хотите задавать их в комментариях, или просто не имеете возможности писать в комментарии, присоединяйтесь к jabber-конференции 3d@conference.sudouser.ru

Данная статья написана в тесном сотрудничестве (спасибо создателям XMPP) с haqreu, автором данного курса.Мы начали масштабный рефакторинг кода, направленный на достижение максимальной компактности и читаемости. Мы сознательно пошли на отказ от ряда возможных и даже очевидных оптимизаций для получения максимально доступного для понимания кода учебных примеров.
P. S haqreu буквально на днях выложит статью о шейдерах!

UPD: ВНИМАНИЕ! Раздел, начиная с номера 3.1, 3.14 и 3.141 и далее, будет о тонкостях реализации основы основ компьютерной графики — линейной алгебры и вычислительной геометрии. О принципах графики пишет haqreu, я же буду писать о том, как это можно внятно запрограммировать!
UPD2: Я выражаю отдельную благодарность lemelisk за внимательное изучение статьи и указанные неточности.
image

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 единицу. Это действие вполне определено стандартом, так что ничего страшного не произойдет — мы просто получим значение, равное std::numeric_limits<size_t>::max(). Почему сделан именно этот цикл, а не традиционный 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) заполняет вектор константой. По умолчанию это ноль.
Исходный текст метода fill
 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.0/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 выложит статью о шейдерах!
Tags:
Hubs:
Total votes 51: ↑43 and ↓8 +35
Views 25K
Comments Comments 41