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

  • 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 выложит статью о шейдерах!
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 41

    +1
    Увидел статью, обрадовался, поставил плюс не читая. Как оказалось, зря. Вы совсем не поняли смысл цикла. Он же не о замене for (i++) на for (i--), он вообще не про реализацию был, а про принципы. У вас же тут ничего о графике, одни ключи компилятора и шаблоны. Надо было как-то иначе оформить, а не как часть курса.
      +6
      Подождите, эта работа ортогональна общему курсу статей, но. Но для того, чтобы нам было удобно писать высокоуровневый код, нужна удобная геометрическая библиотека. gbg провёл много времени над тем, чтобы геометрический код было приятно читать.

      Вы ещё не видели новый растеризатор, сейчас треугольники честно рисуются проходом по всем пикселям описывающего прямоугольника! Да, это не статья про шейдеры, но так она и порядковый номер носит 3.1. Зато в пятой у нас будет простор и раздолье. Код готов, уже можете смотреть на гитхабе.
      +3
      Очень прошу, продолжайте оба ) Такого вот материала для понимания очень не хватает! ))
        +10
        Ваш трюк с циклом for мне кажется неуместным. Он хорош, когда действительно важно бежать с конца в начало, но, поскольку в ваших функциях вам все равно, то лучше использовать классический
        for (size_t i=0; i<Dim; ++i)
        
        Экономить 3 символа это, конечно, хорошо, но в отличие от классического варианта этот при прочтении прямо таки просит взять в руки бумажку и проверить, что тут нигде не налажали. Кроме того, отказ от него позволил бы вам сэкономить целый абзац в статье, раз уж вам это так нравиться.

        Кроме того, вносить действие в шапку цикла считается признаком плохого стиля, а когда тело цикла пустое, рекомендуется вместо незаметной ; на той же строке, что и шапка, писать так:
        for (size_t i=len; i--; ret[i]=v[i]) {}
        
        или так:
        for (size_t i=len; i--; ret[i]=v[i])
            ;
        

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

          +1
          Появление этого цикла тесно связано с использованием size_t для индексации массивов.

          В статье показана частая ошибка, когда для обхода массива в сторону уменьшения индекса забывают о том, что в беззнаковом случае i>=0 — всегда истина.

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

          Для закрепления и запоминания, этот пример используется повсеместно. Как дополнительная демонстрация того, как верно использовать size_t даже при обходе «задом наперед».

          Теперь о целесообразности такого обхода. Если не рассматривать случаи, когда алгоритм прямо требует движения «вниз», остается еще совет #61 Алена Голуба, автора книги «Веревка достаточной длины, чтобы выстрелить себе в ногу»:
          Циклы являются одним из тех мест, где малое повышение эффективности значительно улучшает выполнение программы, потому что их код выполняется многократно. Так как сравнение с нулем обычно более эффективно, чем сравнение с определенным числом, то цикл с уменьшающимся счетчиком, как правило, выполняется быстрее.

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

          Однако стоит также вспомнить, что в x86 действительно есть специальная инструкция loop, которая делает как раз то, что нужно:
          • Декремент CX,
          • затем проверка на равенство его 0
          • и если CX не 0, переход на метку


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

          Итого, мы показываем «а еще с for можно поступить вот так, и это корректно». Прочитавшие могут пополнить свою копилку интересностей.

          Относительно оформления — я с вами полностью согласен. Мой код этого метода в отдельной ветке на guthub оформлен так:
          /////////////////////////////сумма векторов
          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);
          }
          

          Как видите, лично я против переноса тела цикла в заголовок. И я холодно отношусь к стилю расстановки {}, который применяют K&R и haqreu. Но тон проекта (tinyrenderer, где «tiny» значит, чтобы исходники были покороче) задан ранее и я ему следую.
            –1
            ПОПРАВКА:
            Но мы можем заставить компилятор задействовать именно ее, поэтому данный аргумент — слабый.


            Но мы НЕ можем заставить компилятор задействовать именно ее, поэтому данный аргумент — слабый.
              0
              Со мной связался некто kyhtep и задал следующий вопрос:
              Здравствуйте.

              К сожалению, я не могу писать в комментарии к статьям.

              Если вам не сложно, ответье пожалуйста на вопрос к статье
              Краткий курс компьютерной графики 3.1

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

              Но разве при обратном проходе у вас не будут кэш мисы?

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


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

              Аргумент про совет #61 Голуба даже отсутствует в статье, потому как делать предположения о том, во что компилятор странслирует программу довольно опасно — С++ — штука кроссплатформенная, и трюк, который хорошо работает на одной архитектуре может развалится (или сильно деградировать) на другой.

              Конкретно в нашем случае (с -O3 -avx), компилятор и вовсе выбросит эти циклы и заменит их векторными инструкциями. Ассемблер можно посмотреть здесь, тесты по скорости — здесь.

              Данный код написан в очень наивной манере. По вопросам производительности материала еще нет, нужно посмотреть стандарты, провести тесты, составить мнение.

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

              Резюме — мы ходим по массивам задом наперед только лишь для закрепления самого способа хождения. Вопрос о том, что такой проход будет быстрее (как утверждает Голуб) — открыт и стоит в TODO.
              0
              100 и 1 способ выстрелить себе в ногу. Вы пишете на С++, почему бы не использовать стандартные алгоритмы?

              std::transform(lhs.begin(), lhs.end(), rhs.begin(), lhs.begin(), std::minus<int>());
              
                0
                К сожалению, ваше предложение серьезно нарушает идею KISS, которой мы стараемся придерживаться.

                Так как мы работаем в рамках C++98, мы к сожалению не располагаем std::array. Это значит, что нам придется адаптировать свой вектор для работы с STL (писать begin(), end(), возвращающие итератор (который тоже придется писать)). Польза от такого нововведения сомнительна.

                Второй вариант — хранить все данные внутри std::vector. Но вектор предназначен для хранения динамических массивов — он и память для своего содержимого берет из кучи (хотя на это еще можно повлиять, дав ему другой аллокатор), и хранит внутри себя количество элементов (а в нашем случае, это константа времени компиляции). Вместо обычного бинарного куска у нас появится экземпляр класса, который будет лопать память, просить время на конструктор / деструктор. Еще один кошмарик — вектор может пульнуть нам исключение. У него проверка выхода за границы включена всегда по стандарту и все тут. А мы свой assert() в релизной версии банально выключим флагом NDEBUG.

                Есть еще один довод — а сможет ли GCC развернуть и векторизовать цикл, спрятанный внутри transform? Это нужно проверять отдельно.
                  0
                  итератор (который тоже придется писать)
                  Можно простые указатели возвращать, они вполне себе итераторы. Можно даже набыдлокодить и написать как-нибудь так:
                  std::transform(&lhs[0], &lhs[0] + Dim, &rhs[0], &lhs[0], std::minus<int>())
                  
                    –1
                    У нас внутри реализации квадратных скобок стоит assert. Взяв таким варварским способом указатель мы этот assert обойдем и будем лезть в массив бесконтрольно.

                    Кроме того, все это с треском развалится, как только мы вздумаем откомпилировать этот код для С++11.
                      0
                      Взяв таким варварским способом указатель мы этот assert обойдем и будем лезть в массив бесконтрольно.
                      Это не страшно, ведь у нас оба массива фиксированной длины Dim. Это, конечно, быдлокод, но только лишь потому, что мы вместо вызовов begin() и end() взяли и подставили их реализацию.
                    0
                    У него проверка выхода за границы включена всегда по стандарту и все тут

                    Нет. Проверка есть в функции at(), а в операторе [] никакой проверки нет.
                      0
                      Про стандарт я действительно погорячился. Наличие проверки в операторе [] зависит от реализации STL. Например, здесь пишут, что реализация STL в Visual Studio 2005 и 2008 делает эту проверку и для at() и для [].
                      –2
                      У него проверка выхода за границы включена всегда по стандарту и все тут.

                      Ну просто юный недоумок!

                      Читай матчасть!
                      0
                      Согласно cppreference, lhs.begin() не может участвовать и как начало входного, и как начало выходного диапазона:
                      binary_op must not invalidate any iterators, including the end iterators, or modify any elements of the ranges involved.

                        0
                        Обратите внимание, там рядом пометка стоит, что эта гарантия требуется только с версии C++11, а мы работаем в рамках C++98, как бы печально это не было.

                        Да и вот пример на cplusplus.com:
                        Смотреть пример
                        // transform algorithm example
                        #include <iostream>     // std::cout
                        #include <algorithm>    // std::transform
                        #include <vector>       // std::vector
                        #include <functional>   // std::plus
                        
                        int op_increase (int i) { return ++i; }
                        
                        int main () {
                          std::vector<int> foo;
                          std::vector<int> bar;
                        
                          // set some values:
                          for (int i=1; i<6; i++)
                            foo.push_back (i*10);                         // foo: 10 20 30 40 50
                        
                          bar.resize(foo.size());                         // allocate space
                        
                          std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
                                                                          // bar: 11 21 31 41 51
                        
                          // std::plus adds together its two arguments:
                          std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
                                                                          // foo: 21 41 61 81 101
                        
                          std::cout << "foo contains:";
                          for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
                            std::cout << ' ' << *it;
                          std::cout << '\n';
                        
                          return 0;
                        }
                        

                          +1
                          Вы неправильно истолковали написанное, так сказано, что функциональный объект (std::minus<int>() в нашем случае) не имеет права менять объекты, а не то, что отрезки не могут перекрываться. Объект, собственно, ничего и не меняет, просто вычитает одно число из другого и выдает результат.
                            0
                            Спасибо за уточнение. Было бы очень хорошо, если бы вы привели дополнительный источник сведений по этому вопросу, потому как неясность действительно имеет место быть.
                              +1
                              Нашел эту функцию в стандарте, там даже примечание для неё есть (25.3.4p5):
                              Remarks: result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.
                              result в стандарте — это предпоследний параметр функции (итератор, по которому пишется ответ).
                                0
                                Большое спасибо.
                                Я пришел вот к какому выводу:
                                Наши реализации операций используют для доступа к массиву индексный оператор [].

                                Шаблон transform, в свою очередь, использует для доступа итератор. Это разные сущности.

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

                                Поэтому, чтобы вовсю использовать transform, мы обязаны требовать наличия в нашем векторе begin(), end() и итератора, а это дополнительный код, который нужен только для склейки с STL.

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

                                И вопрос раскрутки цикла внутри transform и его векторизации остается открытым, но я думаю, с этим как раз проблем не будет.
                                  +2
                                  дополнительный код, который нужен только для склейки с STL.
                                  Там кода то на 4 строчки. А ещё это даст возможность использовать range-for пользователям С++11.
                                    0
                                    Будем обсуждать с haqreu этот вопрос. Еще раз спасибо за продуктивное обсуждение!
                            +2
                            (опоздал с комментарием, ну и ладно)

                            std::minus<int> и не модифицирует диапазоны. Посмотрите пример по вашей ссылке, там как раз применяется toupper для in-place-модификации строки.
                              0
                              Согласен, в данном случае модифицирует не binary_op.

                              Позвольте тогда поинтересоваться, а если я напишу что-то в духе:

                              std::transform(V.begin(), V.end() - 1, V.begin() + 1, V.begin(), second_arg);
                              


                              Где second_arg(a, b) — функция, всегда возвращающая b, тогда что произойдёт с V? В зависимости от порядка применения (слева-направо или справа-налево) вектор V = {1, 2, 3, 4, 5} может перейти либо в {2, 3, 4, 5, 5}, либо в {5, 5, 5, 5, 5}.

                              Меня слегка сбило с толку то, что в русской версии в разделе «требования» написано следующее:
                              Целью этих требований является возможность параллельных или неупорядоченных реализаций функции std::transform.


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

                          Однако стоит также вспомнить, что в x86 действительно есть специальная инструкция loop, которая делает как раз то, что нужно:
                          — А это вообще антиоптимизация. На современных процессорах LOOP очень медленный по сравнению с наивным инкрементом, сравнением и переходом. Пример обсуждения на SO
                            0
                            Это затравка на будущую статью, которая обязательно когда-нибудь выйдет, как раз с указанием того, что многие советы из старых учебников уже никуда не годятся.
                            В данной статье никаких оптимизаций заведомо не делается

                            Спойлер к следующей статье
                            Например, при проходе по массиву задом наперед, GCC 4.9.2 наотрез отказывается делать векторизацию и все тут.
                            –3
                            Появление этого цикла тесно связано с использованием size_t для индексации массивов.

                            Это же насколько феерическим дегенератом нужно быть, чтобы 1/2 статьи + 1/2 комментариев посвятить "гениальной догадке" индексировать циклы size_t ?!
                            Устроить из этой "мечты идиота" обсуждения на 2 страницы.
                            0
                            Я думаю в следующей статье будет показано что обход в обратном порядке быстрее, равно как и префиксная запись инкрементов/декрементов (хотя эти вопросы на хабре уже разбирались). И хотя это конечно от флагов оптимизации зависит и в релизе может не тормозить, отлаживать программу которая на несколько порядков медленнее просто из за того что было лень взять бумажку и проверить как то не приятно.
                            0
                            3.1, 3.14 и 3.141
                            Нумерация по знакам числа пи? Или просто так совпало?
                              +2
                              А вы не сталкивались с номерами версий TeX?
                                +1
                                Вы верно догадались, нумерация по десятичным знакам числа Пи. Ход не очень оригинальный (о TeX уже упомянули), но это способ вместить практическую часть внутрь курса, а также показать, что эти статьи — отдельная сущность.
                                  +2
                                  а также показать, что эти статьи — отдельная сущность.
                                  Каким образом нумерация внутри цикла может показывать, что статьи не из цикла? Ваша статья сейчас называется «Краткий курс компьютерной графики». Про графику ни слова. Ну сделайте отдальный цикл статей.
                                    0
                                    После вашего разгромного комментария, я добавил в начало статьи (сразу после ката), огромное предупреждение. В нем указано, что все статьи с номерами 3.1, 3.14, 3.141 и далее по знакам числа Пи будут об аккуратной реализации теории на C++.
                                +2
                                Извините, но
                                81.7144592952612 356384634040296077728271484375
                                81.7144592952612 498493181192316114902496337890

                                разница в 16ой значащей цифе — вполне соответствует точности типа double. Лишние знаки не несут смысла.
                                Я почти уверен, что подобрав другие числа можно получить контрпример, когда умножение на обратный дает бОльшую точность, чем деление. Выразить деление через умножение на 1/x — это способ избежать дублирования кода.

                                И последнее — проводились ли какие-нибудь сравнения с существующими библиотеками линейной алгебры для графики? Советую обратить внимание на вот этот тред на SO
                                  +1
                                  Чисто математически, выполнение последовательных операций всегда приводит только к накоплению погрешности — с каждой новой операцией мы теряем информацию о младших разрядах.

                                  Избежав дублирования кода, мы заменяем одно округление(деление) на округление(умножение(округление(деление))).

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

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

                                  Ко второму вопросу:
                                  Мы пишем нашу библиотеку строго под нашу учебную задачу «построить миниатюрный отрисовщик, который будет собираться даже компилятором 15 летней давности».

                                  По этому критерию все эти, несомненно хорошие, библиотеки нам не подходят — ученикам придется еще и разбираться с тем, как привинтить в их среде стороннюю библиотеку. А если это компьютер в университете, да без прав администратора, без доступа к конфигурации IDE — мало чего у них получится.

                                  Если речь идет о «погонять в догонялки», я думаю, ATLAS или viennaCL уделают мой код, даже откомпилированный с -O3 -mavx и так далее. А может, и не уделают. Про это будет отдельная статья.

                                  Здесь можно выделить еще один аспект — очень общий — при академическом обучении программированию нужно показать, «как скомпоновать программу из библиотек», или же, «как написать свою библиотеку»?

                                  Дело в том, что наличие академического образования подразумевает, что выпускник не только может использовать черные ящики-библиотеки, но и может подробно (не фразой «Погугли!») разъяснить полному валенку, как внутри все устроено. А если может разъяснить, значит и свое может написать (потому как написание программы, это и есть разъяснение совершенно безмозглому валенку — компьютеру, чего от него хотят).

                                  Отдельный вопрос, что на рынке труда такой выпускник (способный в запертой комнате без интернета с голым linux и i386 написать quake за лето) маловостребован. Потому как востребован тот, кто склепает это же за неделю из готовых запчастей по ставке $1 в час.
                                  0
                                  Операция «проектирования вектора», судя по контексту, это всё-таки операция «проецирования». Операция «погружения вектора в пространство большей размерности», это просто «изменение размерности вектора», или, если совсем упрощать, изменение размера вектора (по аналогии с классами контейнеров), но «размерность» тут (в контексте графики), наверное, подходит больше.
                                    0
                                    «Проектирование вектора» — термин из проективной геометрии. Мы из проективного пространства к 3D (координаты в таком пространстве — четырехмерные векторы) получаем представление вектора в «обычном» (Евклидовом) пространстве 3D (координаты — трехмерные векторы).

                                    Ровно как и «погружение вектора» — когда в геометрии объект меньшей размерности помещают в пространство большей размерности, говорят именно о «погружении». Есть даже раздел такой «Дифференциальная геометрия погруженных многообразий».

                                    Мы стараемся построить язык именно геометрических терминов, а не «программистских» операций с массивами координат.
                                    –2
                                    а мы работаем в рамках C++98, как бы печально это не было.

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

                                    Позор Хабрахабру за такие публикации.
                                    И позор коллегам gbg, на которых он постоянно ссылается поимённо, что они просмотрели публикацию такого убожества! Этих он ославил на славу.

                                    Данная статья написана в тесном сотрудничестве

                                    Не дай вам Бог таких друзей!
                                      +1
                                      Бога нет.

                                    Only users with full accounts can post comments. Log in, please.