Пользователь
24,8
рейтинг
17 января 2015 в 23:01

Разработка → Краткий курс компьютерной графики: пишем упрощённый OpenGL своими руками, статья 1 из 6 из песочницы tutorial

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



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






Official translation (with a bit of polishing) is available here.




Постановка задачи


Цель этого цикла статей — показать, как работает OpenGL, написав его (сильно упрощённый!) клон самостоятельно. На удивление часто сталкиваюсь с людьми, которые не могут преодолеть первоначальный барьер обучения OpenGL/DirectX. Таким образом, я подготовил краткий цикл из шести лекций, после которого мои студенты выдают неплохие рендеры.

Итак, задача ставится следующим образом: не используя никаких сторонних библиотек (особенно графических) получить примерно такие картинки:



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

Я постараюсь не перевалить за 500 строк в конечном коде. Моим студентам требуется от 10 до 20 часов программирования, чтобы начать выдавать подобные рендеры. На вход получаем текстовый файл с полигональной сеткой + картинки с текстурами, на выход отрендеренную модель. Никакого графического интерфейса, запускаемая программа просто генерирует файл с картинкой.

Поскольку целью является минимизация внешних зависимостей, то я даю своим студентам только один класс, позволяющий работать с TGA файлами. Это один из простейших форматов, поддерживающий картинки в формате RGB/RGBA/чёрно-белые. То есть, в качестве отправной точки мы получаем простой способ работы с картинками. Заметьте, единственная функциональность, доступная в самом начале (помимо загрузки и сохранения изображения), это возможность установить цвет одного пикселя.

Никаких функций отрисовки отрезков-треугольников, это всё придётся писать вручную.

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

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

#include "tgaimage.h"

const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red   = TGAColor(255, 0,   0,   255);

int main(int argc, char** argv) {
        TGAImage image(100, 100, TGAImage::RGB);
        image.set(52, 41, red);
        image.flip_vertically(); // i want to have the origin at the left bottom corner of the image
        image.write_tga_file("output.tga");
        return 0;
}


output.tga должен выглядеть примерно так:



Алгоритм Брезенхэма


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

Как выглядит простейший код, рисующий отрезок между двумя точками (x0, y0) и (x1, y1)?
Видимо, как-то так:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    for (float t=0.; t<1.; t+=.01) {
        int x = x0*(1.-t) + x1*t;
        int y = y0*(1.-t) + y1*t;
        image.set(x, y, color);
    }
}



Снапшот кода доступен на гитхабе.




Проблема этого кода (помимо эффективности) это выбор константы, которую я взял равной .01.
Если вдруг мы возьмём её равной .1, то наш отрезок будет выглядеть вот так:



Мы легко можем найти нужный шаг: это просто количество пикселей, которые нужно нарисовать.
Простейший (с ошибками!) код выглядит примерно так:
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    for (int x=x0; x<=x1; x++) {
        float t = (x-x0)/(float)(x1-x0);
        int y = y0*(1.-t) + y1*t;
        image.set(x, y, color);
    }
}


Осторожно: наипервейший источник ошибок в подобном коде у моих студентов — это целочисленное деление типа (x-x0)/(x1-x0).

Далее, если мы попробуем этим кодом нарисовать вот такие линии:

line(13, 20, 80, 40, image, white);
line(20, 13, 40, 80, image, red);
line(80, 40, 13, 20, image, red);




То выяснится, что одна линия хороша, вторая с дырками, а третьей вовсе нет.
Обратите внимание, что первая и вторая строчки (в коде) дают одну и ту же линию разного цвета. Белую мы уже видели, она хорошо отрисовывается. Я надеялся перекрасить белую в красный цвет, не получилось. Это тест на симметричность: результат отрисовки сегмента не должен зависеть от порядка точек: сегмент (a,b) дожен быть ровно таким же, как и сегмент (b,a).




Дырки в одном из сегментов из-за того, что его высота больше ширины.
Мои студенты часто мне предлагают такой фикс: if (dx>dy) {for (int x)} else {for (int y)}.
Ну ёлки!

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    bool steep = false;
    if (std::abs(x0-x1)<std::abs(y0-y1)) { // if the line is steep, we transpose the image
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    if (x0>x1) { // make it left-to-right
        std::swap(x0, x1);
        std::swap(y0, y1);
    }

    for (int x=x0; x<=x1; x++) {
        float t = (x-x0)/(float)(x1-x0);
        int y = y0*(1.-t) + y1*t;
        if (steep) {
            image.set(y, x, color); // if transposed, de-transpose
        } else {
            image.set(x, y, color);
        }
    }
}






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

Итак, предыдущий код прекрасно работает, но он может быть оптимизирован.

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

Для тестов я рисую 1000000 раз 3 отрезка, которые мы рисовали перед этим. Мой процессор: is Intel® Core(TM) i5-3450 CPU @ 3.10GHz.
Этот код для каждого пикселя вызывает конструктор копирования TGAColor.
А это 1000000 * 3 отрезка * примерно 50 пикслей на отрезок. Немало вызовов.
Где начнём оптимизацию?
Профилировщик нам скажет.

Я откомпилировал код с ключами g++ -ggdb -g3 -pg -O0; затем запустил gprof:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 69.16      2.95     2.95  3000000     0.00     0.00  line(int, int, int, int, TGAImage&, TGAColor)
 19.46      3.78     0.83 204000000     0.00     0.00  TGAImage::set(int, int, TGAColor)
  8.91      4.16     0.38 207000000     0.00     0.00  TGAColor::TGAColor(TGAColor const&)
  1.64      4.23     0.07        2    35.04    35.04  TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)
  0.94      4.27     0.04                             TGAImage::get(int, int)


10% рабочего времени — это копирование цвета.
Но ещё 70% проводятся в вызове line()! Тут и будем оптимизировать.




Заметим, что каждое деление имеет один и тот же делитель, давайте его вынесем за пределы цикла.
Переменная error даёт нам дистанцию до идеальной прямой от нашего текущего пикселя (x, y).
Каждый раз, как error превышает один пиксель, мы увеличиваем (уменьшаем) y на единицу, и на единицу же уменьшаем ошибку.

Код доступен здесь.

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    bool steep = false;
    if (std::abs(x0-x1)<std::abs(y0-y1)) {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    if (x0>x1) {
        std::swap(x0, x1);
        std::swap(y0, y1);
    }
    int dx = x1-x0;
    int dy = y1-y0;
    float derror = std::abs(dy/float(dx));
    float error = 0;
    int y = y0;
    for (int x=x0; x<=x1; x++) {
        if (steep) {
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }
        error += derror;

        if (error>.5) {
            y += (y1>y0?1:-1);
            error -= 1.;
        }
    }
}

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 38.79      0.93     0.93  3000000     0.00     0.00  line(int, int, int, int, TGAImage&, TGAColor)
 37.54      1.83     0.90 204000000     0.00     0.00  TGAImage::set(int, int, TGAColor)
 19.60      2.30     0.47 204000000     0.00     0.00  TGAColor::TGAColor(int, int)
  2.09      2.35     0.05        2    25.03    25.03  TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)
  1.25      2.38     0.03                             TGAImage::get(int, int)






А зачем нам нужны плавающие точки? Едиственная причина — это одно деление на dx и сравнение с .5 в теле цикла.
Мы можем избавиться от плавающей точки, заменив переменную error другой, назовём её error2, она равна error*dx*2.
Вот эквивалентный код:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    bool steep = false;
    if (std::abs(x0-x1)<std::abs(y0-y1)) {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    if (x0>x1) {
        std::swap(x0, x1);
        std::swap(y0, y1);
    }
    int dx = x1-x0;
    int dy = y1-y0;
    int derror2 = std::abs(dy)*2;
    int error2 = 0;
    int y = y0;
    for (int x=x0; x<=x1; x++) {
        if (steep) {
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }
        error2 += derror2;

        if (error2 > dx) {
            y += (y1>y0?1:-1);
            error2 -= dx*2;
        }
    }
}

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 42.77      0.91     0.91 204000000     0.00     0.00  TGAImage::set(int, int, TGAColor)
 30.08      1.55     0.64  3000000     0.00     0.00  line(int, int, int, int, TGAImage&, TGAColor)
 21.62      2.01     0.46 204000000     0.00     0.00  TGAColor::TGAColor(int, int)
  1.88      2.05     0.04        2    20.02    20.02  TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)

Другой разговор, теперь достаточно убрать ненужные копии при вызове функции, передвая цвет по ссылке (или просто включив флаг компиляции -O3) и всё готово. Ни единого умножения, ни единого деления в коде.
Время работы снизилось с 2.95 секунды до 0.64.

Проволочный рендер.


Теперь всё готово для создания проволочного рендера. Снимок кода и тестовая модель находятся здесь.

Я использовал wavefront obj формат файла для хранения модели. Всё, что нам нужно для рендера, это прочитать из файла массив вершин вида

v 0.608654 -0.568839 -0.416318
[...]
это координаты x,y,z, одна вершина на строку файла

и граней
f 1193/1240/1193 1180/1227/1180 1179/1226/1179
[...]

Тут нас интересуют первое число после каждого пробела, это номер вершины в массиве, который мы прочитали ранее. Таким образом эта строчка говорит, что вершины 1193, 1180 и 1179 образуют треугольник.

Файл model.cpp содержит простейший парсер.

Пишем такой цикл в наш main.cpp и вуаля, наш проволочный рендер готов.

    for (int i=0; i<model->nfaces(); i++) {
        std::vector<int> face = model->face(i);
        for (int j=0; j<3; j++) {
            Vec3f v0 = model->vert(face[j]);
            Vec3f v1 = model->vert(face[(j+1)%3]);
            int x0 = (v0.x+1.)*width/2.;
            int y0 = (v0.y+1.)*height/2.;
            int x1 = (v1.x+1.)*width/2.;
            int y1 = (v1.y+1.)*height/2.;
            line(x0, y0, x1, y1, image, white);
        }
    }




В следующий раз будем рисовать 2D треугольники и подправлять наш рендер.
@haqreu
карма
250,2
рейтинг 24,8
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (102)

  • +12
    Чуть сердечный приступ не хватил, когда открыл главную хабра. За материал спасибо!)
  • +11
    Круто! Продолжайте пожалуйста =) Давно такого ждал.
  • +3
    Очень интересная статья. Примерно такой же материал нам читали в вузе, но, к сожалению, как-то не дочитали. Жду остальные части!
    • 0
      У нас так же читали и так же толком не дочитали, честно говоря так никто и не сделал алгоритм на лабораторных работах на сколько я помню — откуда-то честно вязли и даже все обещали разобраться… Вот видимо и настал этот момент.

      Вы молодец продолжайте цикл статей. С нетерпением жду продолжения.
  • +5
    Супер. Именно то, что нужно для понимания основ и того, «как все работает».
  • +1
    Жду продолжения! Обязательно хочу преодолеть этот самый
    первоначальный барьер обучения OpenGL/DirectX
  • +4
    Как печально, что Вы преподаете не в России. За такую статью я бы пошел учится к Вам. Я думаю каждый программист мечтает творить 3D, но времени на изучение тонны книг, не хватает. Вы за 5 минут объяснили, как отрисовать сетку.
    • +19
      Спасибо на добром слове, но ведь интернет для того и придумали, чтобы не сидеть рядом. Называйте темы, которые Вас интересуют, с меня обучающие статьи.
    • +19
      Эм. Извините заранее, не обижайтесь на сказанное дальше, просто накипело.
      Почему-то у нас каждый винит не себя, а надуманное отсутсвие хорошего образования, преподавателей, страну, президента, судьбу и нехватку времени. Я закончил обычный гос. ВУЗ, бесплатно, со стипендией и общагой, коих много по стране. У меня и в мыслях не было ругать наше образование… было куча интересных предметов: линейна алгебра, аналитическая геометрия, алгоритмы и структуры, инженерная, компьютерная графика, всякие схемотехники и т.д. и т.п. После всего этого заявлять «Как печально, что Вы преподаете не в России»? Что такого сверхъестественного в отрисовке сетки? Да после всего, что проходишь в ВУЗ-е, это все выглядит смешно. Если вам нужно объяснять как отрисовать сетку, а после этого вам не стыдно, то что вы за программист и как вообще вы закончили ВУЗ?
      Хватит ныть, вы инженер или кто? PHmaster еще мальчиком вон в 90-е рисовал 3Д кубики ( коммент снизу ). А сейчас в мире интернета — вообще лафа. Столько информации хоть попой кушай и благодаря таким людям как haqreu ее становится еще больше.
      Вам не хватает времени? Блин мне скоро 30 лет. Вам и не снилось сколько времени нужно уделять семье, работе, отдыхать еще надо и т.п. но я каждый день нахожу время изучить что-то новое. Работа у нас такая. Не можешь — иди в макдак.

      P.S. да статья очень понравилась. И я думаю многие преподаватели смогут перенять эту практику. А студенты могли бы просто преподавателю предложить данную статью как источник.
      • +7
        Обычный госвуз это прекрасно, и самообучение это прекрасно. Я вам только один пример приведу: родители у меня инженеры, и как-то так получилось, что я окончил матмех ЛГУ, и в итоге занимаюсь математикой и программированием.

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

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

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

        Цель моих статей в том, чтобы показать, что это под силу любому начинающему программисту. Если он захочет этим заниматься — прекрасно. Не захочет — его выбор. Я не хочу показать революционный метод, я хочу дать возможность человеку выбрать.
        • 0
          Обычно к 3му курсу люди уже вполне взрослые и осознают свою будущую профессию, пробуют лезть и туда и сюда. Интересуются кем же они могут стать в будущем. Люди пробуют работать в разных сферах. Приведу в пример моего одногруппника, который на 3м курсе понял, что хочет действительно стать пилотом гражданской авиации, сдал сессию, уехал в Ульяновск и сейчас летает международными рейсами. Кто-то осознает это раньше кто-то позже.
          Я не умаляю ценности вашей статьи особенно для студентов, стоящих перед выбором дальнейшего пути своего развития. Наоборот, целиком поддерживаю. И в наших ВУЗ-ах хорошо бы расширить круг спецкурсов, но это уже совсем другая история. И вполне возможно, что это даже не проблема вузов, но если учебное заведение возьмет на себя такую ответственность, то это, наверно, очень хорошо, но мы пока к этому еще только идем. А пока нужно писать побольше таких статей, что очень сильно поможет будущим профессионалам.
          P.S. но все-же я склоняюсь к тому, что всю ширину выбора можно и не показывать, интересующийся сам может придти к выбору. Но может я и ошибаюсь.
      • 0
        Я с Вами полностью согласен. Особенно, что касается "… Почему-то у нас каждый винит не себя, а надуманное отсутствие хорошего образования, преподавателей, страну, президента, судьбу и нехватку времени..."
        Но позвольте Вам рассказать историю преподавания ПРОФИЛЬНЫХ предметов в моем госвузе. Приходил преподаватель с ноутбуком и проектором. Заводил презентацию на стене, давал нам 15-20 минут на переписывание содержимого слайдов в тетрадь, выдавал бумажку с вариантами заданий, записывал кто какую задачу выбирал и уходил. И поверьте, задачи очень часто выходили за рамки той информации из слайдов. Кому было интересно — изучали, кому было безразлично — договаривались с теми, кому было интересно. А если, не дай Бог, ты обратишься за помощью к преподавателю… Сколько презрения можно было в свой адрес получить… Таким образом нас «научили» программировать на PHP, C/C++, Java, JS. Но оба доцента кафедры безгранично гордились(уверен, что и сейчас ничего не изменилось) своими познаниями двумерных списков на Pascal'e.

        ps Мне тоже скоро 30 лет :) И мне не только снится сколько времени нужно уделять семье, работе и отдыху, но даже получается все это вполне успешно совмещать. Да, работа у нас такая. Не можешь — иди в макдак! Тут в точку!
        • 0
          Спасибо за поддержку. Вы дополнили мою мысль. Универ — школа жизни, которая учит, что ты нахрен никому не нужен и, что никто тебе ничего не должен. Потому-то они и преподаватели, а не учителя.
      • +2
        Благодаря этой статье я за час написал рендер на javascript nooks.github.io/tinyrenderer/
        cl.ly/image/1e1y2f342H3S/Image%202015-01-20%20at%207.45.07%20PM.png
    • 0
      У меня в МФТИ курс сравнимого содержимого был, как тех.курс по выбору. И сейчас он все еще есть, если мне не изменяет склероз.
      • +1
        Зачем Вы это написали? Я рад за Вас. И в то же время печален, так как уверен, что спецкурса по современному танцу там наверняка не было. А вдруг бы из Вас получился отменный танцор?
        • 0
          Думаю, это к тому, что есть и нормальные заведения, где вполне неплохо преподают. Но что такое МФТИ в сравнении со среднестатистическим техническим вузом?
          • +1
            Я окончил матмех ЛГУ, это не среднестатистический техническое ВУЗ. И преподавали на нём весьма печально. Даже если забыть про кругозор, на кафедре геометрии отделения чистой математики наисвежайшие теоремы, которые упоминались, датировались в лучшем случае сороковым годом. Все достижения современной топологии прошли мимо.
            • 0
              Тут мне сказать нечего, может, в ЛГУ так и есть, не знаю. С другой стороны, на Хабре есть несколько циклов статей, созданных преподавателями из не самых крутых вузов, но при этом глубина и доступность изложения достойна MIT.
              И, если не секрет, какова общая картина по трудоустройству среди ваших одногруппников? Каков примерный процент уборщиц, охранников, слесарей?
              И не сочтите за оскорбление, но вуз — мужского рода и маленькими буквами.
              • –1
                По пунктам:
                1) Я вовсе не претендую на звание учителя года

                2) Я не отрицаю наличие хороших учителей ни в одной точке мира

                3) Среди моих одногруппников нулевой процент уборщиц, охранников, слесарей. Но это ни разу не говорит о качестве обучения. Реально, во время моего обучение приобретение адресной книги было во много, много раз ценнее приобретения знаний по функциональному анализу.

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

                5) ВУЗ может быть существительным, может быть аббревиатурой. Если уж на то пошло, то в моём сообщение вовсе было несогласование родов: «среднестатистический техническое».

                6) Я не знаю, как Вы, я этап граммар-наци прошёл очень, очень давно. Сообщения об ошибках уместны там, где текст можно поправить. Например, в теле статьи.
                • +3
                  4,5,6) У меня и в мысли не было Вас обидеть, извините. Я руководствуюсь тем, что поскольку мы находимся в публичном пространстве, вполне уместно указать на популярную ошибку, чтобы люди, прочитавшие моё сообщение, возможно, в будущем её не совершили. И я не грамма-наци, сам косячу регулярно, но я считаю, что указывать на подобные ошибки необходимо, и буду рад, если мне укажут на мои, особенно публично — так усвояемость лучше. :)
                  www.gramota.ru/spravka/rules/?rub=sokr
        • 0
          Я отвечал не вам, а inook. И ответ был к тому, что и в России можно (пока ещё?) найти правильные места и правильных преподавателей.
          А что до танца — ошибаетесь, на физтехе есть довольно приличная тусовка, занимающаяся историческим танцем, а что?
          • 0
            Вопрос качества обучения — холиворный, ни к чему, кроме как к подбитому глазу у каждого из собеседников привести не может. Предлагаю тему закрыть. Мне холиворы ещё в конце девяностых надоели.

            Я доволен пятью годами, проведёнными в на матмехе ЛГУ :)
  • +6
    Эх, аж ностальгия пробила. Помниться, в далекие 90-е, когда еще интернета у меня не было, попался мне в прокате диск с кучей текстовиков о программировании, в том числе и о 3д-графике. И долгое время я сидел под ДОСом на видеокарте без 3d-ускорения, не желая переходить на Win95, и изобретал свой собственный велосипед в виде 3D-рендера под 320x200 (без всяких там VESA с его космическими разрешениями и DOS4GW с его «безграничными» размерами оперативки, которые я все же открыл для себя немногим позже). И вот такого структурированного и последовательного цикла статей очень сильно мне тогда не хватало. Помню даже, мне удалось таки сделать вращающийся текстурированный 3D-кубик (и для текстур я тоже использовал формат TARGA), но потом я все-таки плюнул и ушел на Win+Direct3D.

    Респект за статью и за это ваше начинание. Сейчас очень многие вновь испеченные «программисты» хватают что-то вроде Unity 3D, и не обладая знаниями ни в программировании, ни в 3D-графике, сразу же бросаются в геймдев. Такие статьи помогут им хотя бы в общих чертах понять, как работает то, что они делают. Ну а для тех, кто изучает программирование систематически — это тоже может быть архиполезно.
    • +6
      Сейчас очень многие вновь испеченные «программисты» хватают что-то вроде Unity 3D, и не обладая знаниями ни в программировании, ни в 3D-графике, сразу же бросаются в геймдев

      И я часто им завидую… Иногда кажется, что я сижу в капкане «собственный костыль» в то время, как другие хватают «Юнити», «кокос 2д» и не зная толком «нутра» и внутренних алгоритмов, штампуют кросплатформенные приложения. Но, может, в этом и есть сила пришедшего времени и к этому все идет, что рядовой разработчик не должен уметь делать «сортировку» руками, а должен уметь подключить нужную библиотеку и использовать ее?

      Что толку от моих глубоких знаний и пониманий алгоритма, если он отлично реализован в доступных 100500 библиотеках? Может подрастающим программистам как раз и надо в основном учиться ориентироваться в том, что уже написано (а его — ОЧЕНЬ много)? Ведь большинство из них реже будет писать «свое» и чаще использовать «чужое». Я, честно, не знаю…

      Вот последний мой отрицательный пример: понадобилось на работе делать поиск пути в графе (С++). И мне проще было написать его самому, чем разбираться в boost::graph. Что же в этом хорошего?
      • +3
        Наипервейшая цель пониманий алгоритма не для того, чтобы его переписывать каждый раз. А для того, чтобы не напарываться на грабли, когда используешь чёрные корбоки. Вы себе, видимо, не представляете, как часто я вижу людей, хранящих указатели на элементы std::vector. А потом однажды случается reallocation. И сегфолт. Куку. И они вообще не знают, откуда это вдруг?!

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

        Мой проект рассчитан на тех, кто в ступоре останавливается перед четырёхмерными векторами в OpenGL. На тех, которые не понимают, откуда обратные (да и ещё транспонированные!) матрицы при подсчёте нормальных векторов.
        • +1
          Я не пытался поругать ваш проект. Его цель ясна и я ее поддерживаю. Я затронул немного философскую сторону.

          Хранение указателей на элементы std::vector… Если человек знает, как устроен вектор внутри, то он не совершит такой ошибки. Но ведь все-таки это не проблема «знай, как работает контейнер», а это проблема «знай, как пользоваться контейнером». В случае с вектором — это звучит немного абсурдно, конечно.

          Сейчас программисты в качестве кирпичей своих программ используют одиночные функции, небольшие классы, циклы, операторы и пр. Не идет ли все к тому, что через 100 лет мы будем использовать не кирпичи, а сразу огромные готовые дома? Уже сейчас, особенно в веб программировании, проявляются языки и библиотеки, где программа может выглядеть как-то так: {New HttpServer(); Create Forum();}. Не будетут ли через 100 лет программы выглядеть так: {do MakeVsioKruto(); SdelaiEschoKrucheNa(5%);} :-)

          За время обучения в среднего человека можно запихнуть ограниченный набор знаний и навыков. Умения искать, ориентироваться, подключать и использовать, выбирать инструменты — очень важны и не тривиальны. Человек будет лишен таких навыков, если чрезмерно нагрузить «базой», тем более, если эта «база» — база прошлых лет, а не настоящего.
          • +1
            Да, именно do MakeVsioKruto() и будет. На мощных компьютерах. А появится мириад маломощных. Нетребовательных к питанию. Ассемблер умрёт ой как не сейчас. Будет всё большее и большее разделение между классами программистов. Вам выбирать, куда вы хотите примкнуть.
            • +1
              Ну, я говорю про «серую массу большинства» программистов. 20 лет назад на ассемблере писали все программисты. Сейчас их, наверное, не стало меньше, но в процентном соотношении их число ничтожно. Почти так же, как ничтожно число тех, кто ДОЛЖЕН сам писать сортировку и алгоритмы схожего уровня. Нужно ли студентам учить эту «сортировку»?

              Опять же, я не ругаю ваш труд, я становлюсь на защиту «вновь испеченных «программистов»», о которых упомянул товарищ PHmaster.
      • +1
        Я тоже, признаться, немного завидую. Когда-то геймдев был моей мечтой, которую до сих пор я так и не осуществил. Одна поделка-клон для игры вчетвером с друзьями на одной клавиатуре не считается. А недавно я читал на хабре статью, как человек, не зная языков программирования, услышал о Unity3D, скачал, установил, научился заодно как-то что-то программировать, запилил несколько несложных игрушек и выложил их продаваться то ли в App Store, то ли в Google Play. Вот так вот незатейливо это сейчас делается. Понятно, что если дальше он захочет заниматься этим более серьезно и писать более сложные игры — ему придется разбираться в тонкостях. Рано или поздно настанет момент, когда возможностей Unity 3D ему станет не хватать. Не знаю, может, к тому времени он уже разбогатеет и сможет нанять команду толковых специалистов, а может его интерес не угаснет и он будет выискивать и читать такие вот статьи, чтобы самому участвовать в процессе разработки.
  • +3
    Могу всем, кому статья понравилась, посоветовать схожий цикл статей по написанию 3д движка «с нуля»:
    blogs.msdn.com/b/davrous/archive/2013/06/13/tutorial-series-learning-how-to-write-a-3d-soft-engine-from-scratch-in-c-typescript-or-javascript.aspx
    В качестве языков там используются c#, javascript или TypeScript одновременно.
    В принципе, всё то же самое, но подобная информация лишней не бывает.
    • +4
      Спасибо за ссылку, я пойду немного дальше, мне интересны шейдеры.
    • 0
      Есть еще уроки Nehe.
      • +2
        Тоже хорошая вещь. Но я не хочу трогать OpenGL до тех пор, покуда не перепишу его с нуля сам. Ну, на пять сотен строк перепишу :)
        Подобные уроки предполагают использование графической библиотеки в качестве чёрного ящика. Я хочу сделать ящик прозрачным.
  • +1
    Сейчас балуюсь с Irrlicht и шэйдерами и очень интересно было бы узнать побольше всяких вещей «под капотом». Жду продолжения!
  • 0
    А нет возможности это как то под # адаптировать? Для тех кто в С++ никак? Было бы очень интересно.
    • +4
      Так там вроде код ну очень простой. Я, зная только пару скриптовых веб-языков сумел его портировать на go без особых проблем (не имея опыта ни в плюсах, ни в go :-) )
      • 0
        Он в принципе не сложный (что очень радует) но надо же еще сопоставить библиотеки и форматы :). Но если что — будем брать то что есть :) Автору и так спасибо надо сказать.
    • +7
      У меня нет никакого опыта в шарпе (и винды под руками тоже нет).
      Но ценность моего кода почти нулевая. Весь цикл рассчитан на самостоятельное написание всего кода. Я только генеральную линию партии показываю. Пишите на шарпе, выкладывайте на гитхаб, я помогу (чтением, я не писатель на шарпе).

      У меня студенты не все пишут на C++. Разброс идёт от питона и R до чуть ли не ассемблера.
      • 0
        Спасибо!
    • +1
      Мне кажется в данном цикле(?) статей адаптация под какой то ЯП не очень важна. Главное знать суть/алгоритм, а язык реализации это уже одна из последних вещей.
    • –1
      — Вы за меня и есть будете?
      — Ага
      ©
    • –1
      Вы уверены, что вам это нужно? Статья обучающая, на практике для решения задачи надо использовать OpenGL или DirectX: они многое сделают из коробки, быстрее и лучше.
      • +1
        Хочется понимать механизм. После этого проще работать с готовыми библиотеками.
      • +2
        Я думал, что вполне очевидно, что моим кодом нельзя пользоваться в конечном продукте. Я даю проект, который обучает OpenGL и Direct3D. А вы предлагаете воспользоваться ими сразу.
        • 0
          Я, например, разбирался с OpenGL, неделю медитируя на Красную книгу и теперь, в принципе, знаю, как воссоздать основной конвеер «вертексный шейдер -> создание примитивов -> пиксельный шейдер». Понятно, что сначала придется подсмотреть пару алгоритмов, но сверхъестественных препятствий не вижу.
          • +7
            С чем вас и поздравляю. Я с этим разбирался, тупя в файлы заголовков .h на SGI без доступа к красной книге. Мне за это медаль выдать?

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

            Ещё один учебник — это ещё один учебник. Ни больше, ни меньше.
            Никакой революции я не предлагаю. У меня есть только одна особенность (не я первый, не я последний): я не приемлю долгого обучения без практики. Неделю медитировать не написав ни одной программы — не мой случай. Я не могу.
        • +1
          Я имел ввиду, что человек, не разбирающийся в вопросе, может подумать, что в реальных проектах так и надо — самому рисовать отрезки, реализовывать Брезенхэма и т.д. Чтобы этого не случилось, уточнил, что на практике используют OpenGL, DirectX.
  • 0
    Далее, если мы попробуем этим кодом нарисовать вот такие линии:

    line(13, 20, 80, 40, image, white);
    line(20, 13, 40, 80, image, red);
    line(80, 40, 13, 20, image, red);

    То выяснится, что одна линия хороша, вторая с дырками, а третьей вовсе нет.

    Понятно, что третьей вовсе нет — первая линия рисуется из точки (13,20) в точку (80,40), а третья из точки (80,40) в точку (13,20).
    Мне просто интересно, какой результат вы надеялись получить?
    • +7
      Третья другого цвета, я надеялся перекрасить первую в красный цвет. Это тест на симметричность: результат отрисовки сегмента не должен зависеть от порядка точек: сегмент (a,b) дожен быть ровно таким же, как и сегмент (b,a).
      • +1
        Желательно пояснить это в статье. Потому, что третья появится только, если тест на симметричность будет провален, во всех остальных случаях можно сказать, что третьей(n-ой) нет.
        • 0
          Ну, белую прямую мы видели на предыдущих тестах. В лучшем (худшем? :)) случае она будет закрашена красной. Сейчас поправлю, спасибо.
      • 0
        Спасибо за интересный материал.
        Еще поправочка:
        Обратите внимание, что первая и вторая третья строчки (в коде) дают одну и ту же линию разного цвета.
    • +1
      А что мешает так захотеть?
  • +1
    Великолепная статья, сейчас потихоньку ковыряю google go, решил практическую часть заодно писать на нём — пока никаких серьёзных проблем не возникло, а пользы — в два раза больше :-) Огромное спасибо за то, что так просто изложили очень интересные вещи. С нетерпением жду продолжения!
  • 0
    Подобный код ведь просто сожмет модель по оси Z и выведет её. А будете ли вы писать о матрицах трансформации (World, View, Projection и их аналоги в OpenGL) с переводом моделей в мировую систему координат, с реализацией камеры (View) для перевода в видовую систему координат и с Projection для перевода в «экранную» систему координат?
    • 0
      Да. Вся эта канитель с самописным OpenGL для того, чтобы рассказать, что такое шейдеры. Мне не очень ясно, почему сразу претензии к проволочному рендеру, я же дал в самом начале финальный рендер. Без шейдеров такого не получить. А для этого нужна геометрия и понимание разных систем координат.
      • +3
        Да, я сделал проволочный рендер с тупым преобразованием (v1.x+1.)*width/2.;
        Но это только для того, чтобы мои читатели не теряли интерес. Позже это будет заменено на нормальное преобразование ModelViewPort. Но для этого сначала надо рассказать, что такое однородные координаты.

        Я категорически против того, чтобы кирпичик за кирпичиком выкладывать код, который не даёт красивых картинок. Просто рисовать сегментики… Брр.

        Я люблю писать код, который будет потом выкинут (переписан). Я хочу видеть сразу как можно больше. Переписать код быстро, а интерес не теряется.
        • +1
          Не, вы все правильно сделали: если бы в статье я увидел только, как нарисовались отрезки, то закрыл и забыл бы. А теперь есть шанс, что узнаю, что такое шейдер внутри, если вы не поленитесь писать дальше :-)
      • 0
        Я ни в коем случае не имею претензий к статье, очень кстати будет для новичков! Вы молодец!
        Просто, я ожидал преобразование координат через матрицы ModelViewPort, и финт с (v1.x+1.)*width/2; не совсем понял.

        P.S.
        А пайплайн у вас в конечном счете будет иметь все стандартные этапы, типа вершинного шейдера, геометрического шейдера, растеризатора и пиксельного шейдера?
        • 0
          Геометрический шейдер посмотрим, у меня нет планов сделать программного монстра, хочется компактный код. Вершинный и фрагмент шейдеры будут точно.
          • 0
            Ну вы же ведь расстеризатору не будете передавать вершины, вы будете передавать собранные примитивы :)
            Всякие значение там интерполируются между вершинами собранного примитива: UV например, для пиксельного шейдера.
            • 0
              Сборщик примитивов — это не геометрический шейдер. Позже разберём.
              • 0
                А какая по вашему стадия следует перед растеризатором и пиксельным шейдером? :)
                • 0
                  Сборщик примитивов. А перед ним геометрический шейдер.
                  • 0
                    Подсказываю
                    image

                    А чем по вашему занят геометрический шейдер, какая у него функция в пайплайне? :)
                    • 0
                      Беру свои слова обратно, забыл, что GS способен оперировать соседними примитивами, а перед GS идет Primitive Assembly не программируемый :)
  • +1
    Есть замечательная книга, которую читал на заре обучения 3D, довольно старая, но там, так сказать, 3D с нуля.
    «Программирование трехмерных игр для Windows. Советы профессионала по трехмерной графике и растеризации» — Андре Ламот
    www.ozon.ru/context/detail/id/1692806/
    • +1
      Лично я был шокирован вот этой книгой. Даже без примеров с дискет она позволяла рассказать, как написать игру типа wolfenstein. И я это сделал. Да, это был 95й год, да, через полгода выйдет квейк. Но я сам написал игру. Это изменило мою жизнь :)
      • 0
        Шикарная книга. И сейчас стоит на полке. Но на ее освоение в то время у меня потребовалось много времени и сил.
  • 0
    Отличная статья! А как быстро планируете написать остальные части? А то после прочтения этой сразу хочется продолжения.
    • 0
      Я прямо сейчас в оффлайне читаю этот курс. Ну, чуть более развёрнутый, конечно. Так что, примерно раз в неделю, может чуть чаще.
      • 0
        Жуть какая :) Ну, надеюсь, следующие статьи будут намного более «ёмкие» и их содержания хватит, чтобы не сильно «голодать» в течение недели.
  • 0
    Автор по-видимому вдохновился книгами Андре Ламот? ;)
    p.s.: ага, увидел коммент выше, так и есть ))
    • +1
      У меня была одна его книга в 95м году. И я на неё уже даже ссылку дал. Да, она оставила неизгладимое впечатление.
  • 0
    Еще, кроме ламотовских, очень классная книжка Шикина и Борескова «Компьютерная графика. Полигональные модели». Очень рад был заполучить ее и эту в бумажном виде.
    С темы 2d/3d графики и начался мой путь как разработчика… Жаль, что утеряно все(
  • 0
    По моему опыту, бывает так, что профилировать имеет смысл только в Release-сборке с включенными оптимизациями. Когда профилируем сборку без оптимизаций, есть риск потратить время на то, с чем компилятор может справиться и сам. К тому же в Release могут отключаться разнообразные проверки на границы массива и т.п., что приведет к увеличению производительности библиотечных функций.
    • +1
      Согласен, но это всё не тема обсуждения. Спасибо за уточнение.

      Я вообще не хочу писать здесь оптимизированный код, я просто показал, как писать целочисленного брезенхема для расширения кругозора. Всего этого в моём коде не будет, оптимизированный код зачастую гораздо длиннее и нечитабельнее, не моя цель.
  • 0
    Автор молодец! Интересная тема, приятное и доступное изложение материала.
  • 0
    Большое спасибо! Очень важное дело делаете!
    Я ещё советую почитать как это делается в живых OpenGL либах к примеру на счёт линий: cgit.freedesktop.org/mesa/mesa/tree/src/mesa/swrast/s_lines.c (ну и ещё интересен вариант с AA)

    Ну и конечно не всё так просто и легко когда начинаешь работать с железом, там немного иной «язык».

    ЗЫ мне кажется mesa вообще классная библиотека для изучения компьютерной графики. К примеру реализация простого растеризатора через Gallium
    cgit.freedesktop.org/mesa/mesa/tree/src/gallium/drivers/softpipe
    мне кажется вполне простой и наглядной.
  • +1
    Реализация проволочного рендера на JS / canvas:
    jsfiddle.net/2wvyga24/3/
    • 0
      А Вы тестировали на производительность?
      Сколько примерно линий в секунду можете нарисовать?
    • 0
      А почему у вас тег открывается как
      script type=«text/objmodel» id=«model»
      а закрывается как
      /div
      ?
      • 0
        С div просто задумался, видимо, и закрыл не тем, да, это уже заметил.

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

        Вот немного продолжение:
        1. jsfiddle.net/2wvyga24/8/ — простейшая заливка по z-координате.
        2. jsfiddle.net/2wvyga24/15/ — свет. Очень долго не понимал, в чём проблема при рисовании, а, оказывается, при вычислении нормали использовал экранные координаты вместо мировых :)

        В вашей версии мне не совсем понятно использование EventEmitter и других библиотек :). Думаю, логичнее было бы подключить SylvesterJS, чтобы не писать матрицы и вектора заново.
        • 0
          В вашей версии мне не совсем понятно использование EventEmitter и других библиотек :).

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

          нативные линии рисуются быстрее пиксельных Брезенхэма

          У меня — наоборот, моя фукция где-то процентов, наверное, на 20 быстрее работает — я не слишком глубоко проводил сравнение, но на моей машине моя функция 300 тысяч линий рисовала за 2-3 секунды, а нативная — за 3-4 секунды.
        • 0
          Добавил динамического освещения ^_^
          jsfiddle.net/yecgozrt/2/
        • +1
          А я вот теперь задумался, а как же мне z-буфер делать, если не отказываться от использования нативных треугольников… :(
          Есть идеи?
          • 0
            Может, можно как-нибудь извратиться с globalCompositeOperation… Впрочем, лучшим вариантом, я думаю, будет всё же отказаться от нативных треугольников.

            Я переписал по-нормальному класс CanvasGL: если раньше любая точка вставлялась на canvas сразу же, то теперь функции изменяют лишь внутренний буфер класса, а функция put отдельно его вставляет.

            Результаты неплохие
            	Нативные / пиксельные
            	- 10: 0.8 / 10
            	- 100: 1 / 12
            	- 1000: 130 / 22
            	- 10000: 1350 / 65
            	- 100000: 18220 / 482
            	- 1000000: нет / 4700

            (думаю, доп. тормозом был ранд, но тем не менее).
            • 0
              Да, я сразу сделал отрисовку через ImageData и putImageData, и _линии_ отриовывались очень даже резво — даже быстрее, чем через beginPath-stroke, но вот треугольники оказались сразу в несколько десятков раз медленнее :(

              Вот думаю, как быть… Толи отказаться от производительности, то ли придумывать что…

              Ссылка предыдущая нерабочая оказалась. Вот тут освещение меняется, когда мышкой водишь: jsfiddle.net/yecgozrt/4/
              :)
              • 0
                Да, ссылку нашёл сразу, симпатично.

                С треугольниками ситуация та же:
                	Native / Pixel:
                	1		0.4 / 15
                	10		0.9 / 50
                	100		1.1 / 380
                	1000		10 / 3988
                	10000		69 / 47210


                Думаю, надо искать более подходящий алгоритм.
                Ну либо производительностью придётся пожертвовать.
              • 0
                Например, появилась идея заливать треугольник диагональными линиями:
                for(var ab_x = ax; ab_x < bx; ab_x++){
                    var t = (ab_x - ax) / (bx - ax),
                        ab_y = (1 - t)*ay + t*by | 0,
                        bc_x = (1 - t)*cx + t*bx | 0,
                        bc_y = (1 - t)*cy + t*by | 0;
                    this.line(ab_x, ab_y, bc_x, bc_y, color);
                }
                

                И да, это на самом деле оказалось быстрее, но треугольник получается с дырками.
    • 0
      Моя версия для JS без использования нативных команд рисования линий. Начинать читать лучше снизу :)

  • 0
    Я, наверное, тут не самого далекого ума, но я не очень понял как работает рендерер. Во-первых, почему face-ы определены три раза по три вертекса и, во-вторых, как-то не объеснено про сам рендер. Как он трехмерные полигоны выводит на двумерную плоскость. Цикл то простой, но понять его не получается.
    • +1
      Про z-координату треугольников в данном месте мы просто забываем, используем только xy. Это получается ортогональная проекция на плоскость Oxy.

      Массивы со строчками v, vn и vt задают вершины в геометрическом и в текстурном пространствах.
      f задаёт связь между этими вершинами, в строчках f хранятся индексы из массивов вершин v, vt и vn. Ссылка на формат obj в статье дана.
    • +1
      Во-первых, можете прочитать про алгоритм Брезенхэма и про устройство wavefront.obj.

      почему face-ы определены три раза по три вертекса

      Формат феса:

      f v1/vt1/vn1 v2/vt2/vn2 v3/vt3/vn3

      v* — это номер вершины в общем списке
      vn* — это номер описания позиции данной вершины на текстуре
      vt* — это номер нормали к поверхности в данной точке
  • 0
    Крутой цикл лекций, спасибо! Многое узнал.
    Интересно, в рендере пакета 3DS Max тоже используются все эти описанные Вами идеи? Или, например, в рендере V-Ray…
    • 0
      Там используется трассировка лучей. Это не совсем то же самое, о чём говорю я, но пересечение очень немаленькое.
  • 0
    Каждое ребро(кроме внешних) у нас дважды прорисовывается.
  • 0
    Расскажите, пожалуйста, зачем нужно вот это преобразование в конце?
                int x0 = (v0.x+1.)*width/2.;
                int y0 = (v0.y+1.)*height/2.;
                int x1 = (v1.x+1.)*width/2.;
                int y1 = (v1.y+1.)*height/2.;
    
    • 0

      Преобразование координат из диапазона [-1; 1] в диапазон [0; width] или [0; heigth]. Об этом есть в статье.

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