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

  • Tutorial

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




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






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




Новый растеризатор и коррекция перспективных искажений


Тема сегодняшего разговора — это коррекция искажений интерполяции, посмотрите на разницу текстурирования на полу:



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

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

Нахождение барицентрических координат точки в двумерном треугольнике


Дан 2D треугольник ABC, точка P, всё в картезианских координатах. Наша задача найти барицентрические координаты точки P относительно треугольника ABC. Это тройка чисел (1-u-v, u, v), с помощью которых мы можем найти точку P:



Это означает, что если мы поместим веса (1-u-v, u, v) в соответствующие вершины треугольника, то центр масс системы окажется в точке P. Ровно это же самое можно переписать, сказав, что точка P будет иметь координаты (u,v) в репере (A, AB, AC):



Итак, даны векторы AB, AC, AP, нам нужно найти два вещественных u,v, которые отвечают следующему уравнению:



Это векторное уравнение, которое эквивалентно системе двух обычных уравнений.



Система двух линейных уравнений с двумя неизвестными, всё это дело весьма нетрудно решается. Я ленивый, честно выводить решение не хочу, давайте решим следующим образом. Перепишем нашу систему в матричном виде:



Это означает, что мы ищем вектор (u,v,1), который одновременно ортогонален двум данным векторам (ABx,ACx,PAx) и (ABy,ACy,PAy). Уже поняли, к чему я клоню? Правильно, мы просто векторно перемножим (ABx,ACx,PAx) x (ABy,ACy,PAy) и поделим на получившуюся третью компоненту.

Это мелкий хинт: в 2д пересечение двух прямых (а мы ведь именно это только что нашли) считается одним векторным произведением. Кстати, найти уравнение прямой, проходящей через две заданные точки считается ровно так же!

Новый растеризатор


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

Скрытый текст
#include <vector>
#include <iostream>
#include "geometry.h"
#include "tgaimage.h"

const int width  = 200;
const int height = 200;

Vec3f barycentric(Vec2i *pts, Vec2i P) {
    Vec3f u = cross(Vec3f(pts[2][0]-pts[0][0], pts[1][0]-pts[0][0], pts[0][0]-P[0]), Vec3f(pts[2][1]-pts[0][1], pts[1][1]-pts[0][1], pts[0][1]-P[1]));
    if (std::abs(u[2])<1) return Vec3f(-1,1,1); // triangle is degenerate, in this case return smth with negative coordinates
    return Vec3f(1.f-(u.x+u.y)/u.z, u.y/u.z, u.x/u.z);
}

void triangle(Vec2i *pts, TGAImage &image, TGAColor color) {
    Vec2i bboxmin(image.get_width()-1,  image.get_height()-1);
    Vec2i bboxmax(0, 0);
    Vec2i clamp(image.get_width()-1, image.get_height()-1);
    for (int i=0; i<3; i++) {
        for (int j=0; j<2; j++) {
            bboxmin[j] = std::max(0,        std::min(bboxmin[j], pts[i][j]));
            bboxmax[j] = std::min(clamp[j], std::max(bboxmax[j], pts[i][j]));
        }
    }
    Vec2i P;
    for (P.x=bboxmin.x; P.x<=bboxmax.x; P.x++) {
        for (P.y=bboxmin.y; P.y<=bboxmax.y; P.y++) {
            Vec3f bc_screen  = barycentric(pts, P);
            if (bc_screen.x<0 || bc_screen.y<0 || bc_screen.z<0) continue;
            image.set(P.x, P.y, color);
        }
    }
}

int main(int argc, char** argv) {
    TGAImage frame(200, 200, TGAImage::RGB);
    Vec2i pts[3] = {Vec2i(10,10), Vec2i(100, 30), Vec2i(190, 160)};
    triangle(pts, frame, TGAColor(255, 0, 0));
    frame.flip_vertically(); // to place the origin in the bottom left corner of the image
    frame.write_tga_file("framebuffer.tga");
    return 0;
}



Функция barycentric считает координаты точки P в данном треугольнике, мы это только что обсудили в предыдущем параграфе. Давайте разберёмся, как работает функция triangle. Перво-наперво она считает описывающий прямоугольник. Он задан двумя его углами — нижним левым и верхним правым. Мы проходим по всем точкам треугольника и находим наименьшие и наибольшие координаты. В добавление к тому я ещё нашёл пересечение описывающего прямоугольника с прямоугольником экрана, чтобы не тратить время попусту, если наш рисуемый треугольник выходит за пределы экрана.

Поздравляю вас, мы научились рисовать треугольник.



Коррекция перспективного отображения


Как нам использовать этот растеризатор в рендере? Казалось бы, замени строчку image.set(P.x, P.y, color) на вызов фрагментного шейдера, и дело с концом. К сожалению, это не совсем так.

Вот код, который так и делает. Результат его работы на заглавной картинке слева. А вот его исправление, которое нам даст правильный рендер. Изменение строго одно: я передал в шейдер не барицентрические координаты bc_screen, а барицентрические координаты bc_clip. Уф. Давайте разбираться.

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

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



Мы знаем барицентрические координаты точки P' относительно треугольника A'B'C' (это преобразованные вершины треугольника ABC):



Так вот, зная координаты треугольника A'B'C' и барицентрические координаты точки P' относительно него, нам нужно найти барицентрические координаты точки P относительно треугольника ABC:



Итак, запишем координаты точки P':



Умножим всё на rP.z+1:



Получили выражение P = [ABC]*[непонятный вектор]. Но ведь это и есть определение барицентрических координат! Осталась самая малость. Что нам известно и что нам неизвестно в определении этого вектора? Альфа-бета-гамма-всё-штрих нам известны. rA.z+1, rB.z+1, rC.z+1 нам известны, это координаты треугольника, переданные в растеризатор. Осталась одна вещь = rP.z+1. То есть, координата z точки P. И с её помощью мы определяем точку P. Не замкнутый ли это круг? К счастью, нет.

Давайте используем тот факт, что в (нормализованных) барицентрических координатах сумма координат даёт единицу, то есть, alpha+beta+gamma = 1:



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

Итак, чтобы найти, например, текстурные координаты, нам достаточно (скалярно) умножить (uv0 uv1 uv2) на (alpha beta gamma). Или (z0 z1 z2) на (alpha beta gamma). Или (vn0 vn1 vn2) на (alpha beta gamma). И вообще всё, что нам нужно интерполировать!

На хороших данных эта коррекция не очень-то нужна


Вот эта картинка — это одна заглавная картинка минус другая.



Голова полностью пропала, что говорит о слабой ошибке, внесённой неправильной интерполяции.

В качестве (необязательного) бонуса к курсу нам осталось разобраться с тем, как считать касательное пространство, чтобы использовать tangent-space текстуры нормалей, сделать светящиеся поверхности, посмотреть на то, что такое ambient occlusion.
Support the author
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 30

    0
    Здорово, что Вы умеете в несколько строчек простым языком объяснять такие вещи. Я в свое время читал более длинную статью и потом долго отлаживался, чтобы починить данный баг.
      +1
      Вот эта картинка — это одна заглавная картинка минус другая.
      Это немного нечестно. Из-за неравномерности sRGB значения в темном диапазоне слабо отличаются на глаз. Если инвертировать картинку (и протереть монитор от пыли), различия станут намного заметнее.

        +1
        Да, голова не исчезла полностью, оставила немного перхоти. Но это не повод копья ломать :)
          +2
          Тут скорее дело в том, что у головы близкие цвета в соседних точках текстуры.
          В итоге после изменения контрастности получилось это: image
            0
            Невооружённым глазом это не видно. В отличие от проблем на полу.
        0
         
          +1
          Хех, спасибо за статью, и за упоминание меня.
          Немного про оптимизации и triangle. bc_screen не нужен. Он у вас сейчас используется только чтобы определить принадлежность точки треугольнику. Если избавится от bc_screen — то и вычисления bc_clip будут оптимальнее. Я когда прошлый раз смотрел ваш код, не обратил внимание на то, как считается barycentric.
          Вообще красивее это сделать через сканлайны, тогда вообще не нужно будет проверять лежит точка в треугольнике или нет, и мы гарантированно будем рисовать только то, что лежит в треугольнике. Сканлайны не так страшны в реализации, как кажется на первый взгляд.
          Любой треугольник можно разбить максимум на 2 горизонтальной прямой, проходящей через одну вершину:

          Это дает нам возможность создать 2 цикла по Y, от верхней вершины до разделительной линии. И от разделительной линии до нижней вершины. Поэтому первый этап — сортировка 3-х вершины по Y, чтобы определиться с границами первого цикла.
          Второй этап — сортировка угловых коэффициентов линий треугольника, чтобы идти от левого ребра к правому.
          Буквально несколько месяцев назад набросал коллеге код такого целочисленного сканлайна в качестве примера. Сейчас нашел этот код в логах скайпа:
          Собственно код (паскаль)
          procedure Exchange(var p0, p1: TPoint); inline;
          var tmp: TPoint;
          begin
            tmp := p1;
            p1 := p0;
            p0 := tmp;
          end;
          
          procedure DrawTrinangle(canvas: TCanvas; p0,p1,p2: TPoint);
          var
            j, i: Integer;
            dirLeft, dirRight: TPoint;
          begin
            if p0.Y > p1.Y then Exchange(p0, p1); //сортируем вершины по Y
            if p1.Y > p2.Y then Exchange(p1, p2);
            if p0.Y > p1.Y then Exchange(p0, p1);
          
            dirLeft.X := p2.X - p0.X;
            dirLeft.Y := p2.Y - p0.Y;
          
            dirRight.X := p1.X - p0.X;
            dirRight.Y := p1.Y - p0.Y;
          
            if dirRight.X*dirLeft.Y < dirLeft.X*dirRight.Y then Exchange(dirRight, dirLeft); //сортируем угловые коэффициенты верхнего треугольника
          
            for j := p0.Y to p1.Y - 1 do
              for i := (j-p0.Y)*dirLeft.X div dirLeft.Y + p0.X to (j-p0.Y)*dirRight.X div dirRight.Y + p0.X do
                canvas.Pixels[i, j] := clBlue;
          
            dirLeft.X := p0.X - p2.X;
            dirLeft.Y := p0.Y - p2.Y;
          
            dirRight.X := p1.X - p2.X;
            dirRight.Y := p1.Y - p2.Y;
          
            if dirRight.X*dirLeft.Y > dirLeft.X*dirRight.Y then Exchange(dirRight, dirLeft); //сортируем угловые коэффициенты нижнего треугольника
          
            for j := p1.Y to p2.Y - 1 do
              for i := (j-p2.Y)*dirLeft.X div dirLeft.Y + p2.X to (j-p2.Y)*dirRight.X div dirRight.Y + p2.X do
                canvas.Pixels[i, j] := clBlue;
          end;
          


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

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

            Мне интересен более простой способ вычисления барицентрических координат в клип-пространстве из координат 2д пикселя. Вы упоминаете, что bc_clip можно проще вычислять. Я не вижу куда ещё упрощать, вы что можете предложить?

                        Vec3f bc_screen  = barycentric(pts2[0], pts2[1], pts2[2], P);
                        Vec3f bc_clip    = Vec3f(bc_screen.x/pts[0][3], bc_screen.y/pts[1][3], bc_screen.z/pts[2][3]);
                        bc_clip = bc_clip/(bc_clip.x+bc_clip.y+bc_clip.z);
            
              0
              Барицентрические координаты можно получать, умножая матрицу (A^-1)^T на вектор (x,y,1)
              Матрица А — это матрица, строками в которой являются координаты вершин треугольника, с заменой третьей координаты на 1.
              Матрицу нужно обратить один раз.
              Исходник примера
              #include <iostream>
               
              #include <iomanip>
              #include <vector>
               
              //#include <vec-simple.h>
               
              #ifndef VECSIMPLE_H
              #define VECSIMPLE_H
              #ifndef VEC_H
              #define VEC_H
              #include <ostream>
               
              #define ASSERT(n) (n);
              using namespace std;
               
              template <size_t Dim,typename Number> class vec
              {
               
              public:
              typedef Number NumberT;
              static const size_t DimN=Dim;
              Number items[Dim];
               
              vec()
              {
               
              }
               
              vec(const vec<Dim,Number >& src)
              {
              for(size_t i=Dim;i--;)
              {
              items[i]=src[i];
              }
              }
               
              vec(const Number* src)
              {
              for(size_t i=Dim;i--;)
              {
              items[i]=src[i];
              }
              }
               
              size_t maxPos() const
              {
              size_t ret=0;
              for(size_t i=Dim;--i;)
              {
              if(items[i]>items[ret])
              {
              ret=i;
              }
              }
              return(ret);
              }
               
              ostream& print(ostream& out) const
              {
              out<<"{ ";
              for(size_t i=0;i<Dim;i++)
              {
              out<<setw(6)<<items[i]<<" ";
              }
              out<<"} ";
              return(out);
              }
              static vec<Dim,Number > fill(const Number& val=0)
              {
              vec<Dim, Number> ret;
              for(size_t i=Dim;i--;)
              {
              ret[i]=val;
              }
              return(ret);
              }
               
              bool operator!=(const vec<Dim,Number>&v)
              {
              for(size_t i=Dim;i--;)
              {
              if(v[i]!=items[i])
              {
              return(true);
              }
              }
              return(false);
              }
               
              Number& operator [](size_t index)
              {
              return(items[index]);
              }
              const Number& operator [](size_t index) const
              {
              return(items[index]);
              }
              };
               
              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);
               
              }
               
              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);
              }
               
              template<size_t Dim,typename Number>vec<Dim,Number > operator*(vec<Dim,Number > lhs, const Number& rhs)
              {
              for(size_t i=Dim;i--;)
              {
              lhs[i]*=rhs;
              }
              return(lhs);
              }
               
               
               
              template<size_t Dim,typename Number>vec<Dim,Number > operator/(vec<Dim,Number > lhs, const Number& rhs)
              {
              for(size_t i=Dim;i--;)
              {
              lhs[i]/=rhs;
              }
              return(lhs);
              }
               
               
              template<size_t Dim,typename Number> Number operator*(const vec<Dim,Number >&lhs, const vec<Dim,Number >& rhs)
              {
              Number ret=0;
              for(size_t i=Dim;i--;)
              {
              ret+=lhs[i]*rhs[i];
              }
              return(ret);
              }
               
               
              template<size_t len,size_t Dim, typename Number> vec<len,Number > proj(const vec<Dim,Number> &v,size_t start=0)
              {
              return(vec<len,Number >(&v.items[start]));
              }
               
              template<size_t len,size_t Dim, typename Number> vec<len,Number > dive(const vec<Dim,Number> &v,size_t start=0)
              {
              vec<len,Number> ret(&v.items[start]);
              for(size_t i=Dim+start;i<len;i++)
              {
              ret[i]=1;
              }
              return(ret);
              }
               
              template<size_t Dim,typename Number> ostream& operator<<(ostream& os,const vec<Dim,Number >& v)
              {
              return(v.print(os));
              }
               
              template<size_t DimRows,size_t DimCols,typename Number> class mat;
               
              template<size_t DimCols,size_t DimRows,typename Number> struct dt
              {
              static Number det(const mat<DimRows,DimCols,Number>& src)
              {
              Number ret=0;
              for(size_t i=DimCols;i--;)
              {
              ret+=src[0][i]*src.algAdd(0,i);
              }
              return(ret);
              }
              };
               
              template<typename Number> struct dt<1,1,Number>
              {
              static Number det(const mat<1,1,Number>& src)
              {
              return(src[0][0]);
              }
              };
               
              template<size_t DimRows,size_t DimCols,typename Number> class mat
              {
              vec<DimCols,Number> rows[DimRows];
               
               
              public:
              typedef Number NumberT;
              static size_t shift(size_t in,const size_t& val)
              {
              return(in<val ? in : ++in);
              }
               
              mat()
              {
              }
              mat(const mat<DimRows,DimCols,Number >& src)
              {
              for(size_t i=DimCols;i--;)
              {
              for(size_t j=DimRows;j--;)
              {
              const Number t=src[i][j];
              rows[i][j]=t;
              }
              }
              }
               
              ostream& print(ostream& out) const
              {
              for(size_t i=0;i<DimRows;i++)
              {
              out<<rows[i]<<"\n";
              }
              return(out);
              }
              vec<DimCols,Number > minimums()
              {
              vec<DimCols,Number > ret=rows[0];
              for(size_t i=DimRows;--i;)
              {
              for(size_t j=DimCols;j--;)
              {
              ret[j]=min(ret[j],rows[i][j]);
              }
              }
              return(ret);
              }
               
              vec<DimCols,Number > maximums()
              {
              vec<DimCols,Number > ret=rows[0];
              for(size_t i=DimRows;--i;)
              {
              for(size_t j=DimCols;j--;)
              {
              ret[j]=max(ret[j],rows[i][j]);
              }
              }
              return(ret);
              }
              vec<DimCols,Number>& operator[] (size_t index)
              {
              return(rows[index]);
              }
               
              const vec<DimCols,Number>& operator[] (size_t index) const
              {
              return(rows[index]);
              }
              static mat<DimCols,DimRows,Number> ones()
              {
              mat<DimCols,DimRows,Number> ret;
              for(size_t i=DimRows;i--;)
              {
              for(size_t j=DimCols;j--;)
              {
              ret[i][j]=(i==j);
              }
               
              }
              return(ret);
              }
               
              Number det() const
              {
              return(dt<DimCols,DimRows,Number>::det(*this));
              }
               
              mat<DimRows-1,DimCols-1,Number> minor(size_t row,size_t col) const
              {
              mat<DimRows-1,DimCols-1,Number> ret;
              for(size_t i=DimRows-1;i--;)
              {
              for(size_t j=DimCols-1;j--;)
              {
              ret[i][j]=rows[ret.shift(i,row)][ret.shift(j,col)];
              }
              }
              return(ret);
              }
               
               
              Number algAdd(size_t row,size_t col) const
              {
              return(minor(row,col).det()*( (row+col)%2 ? -1 : 1));
              }
               
              mat<DimRows,DimCols,Number> Adjacent()const
              {
              mat<DimRows,DimCols,Number> ret;
              for(size_t i=DimRows;i--;)
              {
              for(size_t j=DimCols;j--;)
              {
              ret[i][j]=algAdd(i,j);
              }
              }
              return(ret);
              }
               
              mat<DimRows,DimCols,Number> invertT()const
              {
              mat<DimRows,DimCols,Number> ret=Adjacent();
              return(ret/(ret[0]*rows[0]));
              }
               
              void setCol(const Number& val,size_t col)
              {
              for(size_t i=DimRows;i--;)
              {
              rows[i][col]=val;
              }
              }
               
              };
               
              template<size_t Dim,typename Number>vec<Dim,Number > operator*(const mat<Dim,Dim,Number >& lhs, const vec<Dim,Number>& rhs)
              {
              vec<Dim,Number> ret;
              for(size_t i=Dim;i--;)
              {
              ret[i]=lhs[i]*rhs;
              }
              return(ret);
              }
               
              template<size_t DimCols,size_t DimRows,typename Number>mat<DimCols,DimRows,Number > operator/(mat<DimCols,DimRows,Number> lhs, const Number& rhs)
              {
              for(size_t i=DimRows;i--;)
              {
              lhs[i]=lhs[i]/rhs;
              }
              return(lhs);
              }
               
              template<size_t DimRows,size_t DimCols,typename Number> ostream& operator<<(ostream& os,const mat<DimRows,DimCols,Number>& v)
              {
              return(v.print(os));
              }
               
              typedef mat<2,2,float > tempMat;
               
              #endif // VEC_H
               
               
              #endif // VECSIMPLE_H
               
               
               
              using namespace std;
               
              typedef vec<3,float> pixel;
               
              class screen
              {
              vector<pixel > buffer;
              size_t width;
              size_t height;
              public:
              screen(size_t width,size_t height):width(width),height(height)
              {
              buffer.assign(width*height,pixel());
              }
              template<typename t> void putpixel(const t& location,const pixel& px)
              {
               
              buffer[location[0]+location[1]*width]=px;
              }
               
              ostream& print(ostream& out) const
              {
              for(size_t i=0;i<height;i++)
              {
              out<<"|";
              for(size_t j=0;j<width;j++)
              {
              const size_t mp=buffer[i+j*width].maxPos();
              static const char syms[]={' ','.','\'','-','+','*'};
              static const char syms2[]={'R','G','B'};
              if(buffer[i+j*width][mp] > static_cast<pixel::NumberT>(sizeof(syms)-1)/static_cast<pixel::NumberT>(sizeof(syms)))
              {
              cout<<syms2[mp];
              }
              else
              {
              const size_t idx=buffer[i+j*width][mp]*float(sizeof(syms)-1);
              out<<syms[idx];
              }
              }
              out<<"|\n";
              }
              return(out);
              }
              };
               
              typedef vec<3,float > v3i;
              typedef vec<2,float > v2i;
              typedef mat<3,3,float> m3i;
               
               
              template<typename V>class allPointsOfSquare
              {
              vec<V::DimN,typename V::NumberT> topLeft;
              vec<V::DimN,typename V::NumberT> bottomRight;
              vec<V::DimN,typename V::NumberT> pos;
              public:
              allPointsOfSquare(const V& topLeft,const V& bottomRight):topLeft(topLeft),bottomRight(bottomRight),pos(topLeft)
              {
              }
              const v2i& operator *() const
              {
              return(pos);
              }
              bool next()
              {
              const bool ret=(pos!=bottomRight);
              for(size_t i=V::DimN;i--;)
              {
              pos[i]++;
              if(pos[i]>bottomRight[i])
              {
              pos[i]=0;
              }
              else
              {
              break;
              }
              }
              return(ret);
              }
              };
               
              class IShader
              {
              public:
              virtual ~IShader()
              {
               
              }
               
              virtual pixel shade(const v3i& a)=0;
              };
               
              class baryShader:public IShader
              {
              public:
              virtual ~baryShader()
              {
               
              }
               
              virtual pixel shade(const v3i&a)
              {
              return(a);
              }
              };
               
               
              void fillTria(mat<3,3,float > coord,IShader* shader,screen& scr)
              {
              //находим углы прямоугольника, в котором лежит треугольник.
              //это соответственно минимумы и максимумы сторон, его содержащих
               
              v3i topLeft=coord.minimums();
              v3i bottomRight=coord.maximums();
               
              coord.setCol(1,2);
               
              mat<3,3,float > bcm=coord.invertT();
               
              mat<3,2,float > directions;
               
              for(size_t i=3;i--;)
              {
              directions[i]=proj<2>(coord[ (i+1) % 3 ])-proj<2>(coord[i]);
              }
               
              for(allPointsOfSquare<v2i> sweep=allPointsOfSquare<v2i>(
              proj<2>(topLeft),
              proj<2>(bottomRight))
              ;
              sweep.next()
              ;
              )
              {
              size_t i=0;
              for(;i<3;i++)
              {
              v2i curDirection=(*sweep)-proj<2>(coord[i]);
               
              tempMat crss;
              crss[0]=proj<2>(curDirection);
              crss[1]=proj<2>(directions[i]);
               
              if(crss.det()>0)
              {
              break;
              }
              }
              if(i==3)
              {
              v3i a=bcm*dive<3>(*sweep);
               
              scr.putpixel(*sweep,shader->shade(a));
               
              }
              }
              }
               
               
               
               
              ostream& operator<<(ostream& os,const screen& v)
              {
              return(v.print(os));
              }
               
               
               
               
              int main()
              {
              screen scr(80,80);
              // cout<<scr;
              mat<3,3,float > t;
              t[0][0]=5;
              t[0][1]=7;
              t[0][2]=3;
               
               
              t[1][0]=70;
              t[1][1]=13;
              t[1][2]=13;
               
               
               
              t[2][0]=20;
              t[2][1]=50;
              t[2][2]=21;
              cerr<<"started";
               
               
              baryShader bs;
              fillTria(t,&bs,scr);
              cerr<<"filled";
               
              cout<<scr;
               
              return 0;
              }
               
              
              он же на ideone
                0
                Внутри barycentric выкинуть проверку: if (std::abs(u[2])>1e-2)
                Отправить деление bc_screen.x/pts[0][3], bc_screen.y/pts[1][3], bc_screen.z/pts[2][3] внутрь barycentric, что позволит заменить деление на умножение. Так же отправить туда bc_clip = bc_clip/(bc_clip.x+bc_clip.y+bc_clip.z);
                Ну то есть это уже чисто CPU оптимизации, а не математические. Поэтому это скорее к вашему соавтору по части оптимизаций.
                  0
                  А, ну чуть укоротить код — это немного не то, что мне надо. При таких раскладах я оставлю bc_screen как есть, т.к. у него есть чёткая семантика, иначе становится совсем непонятно, что и когда мы считаем.
                0
                Этот алгоритм сразу вызывает вопрос — не наделает ли он дырок при построении смежных треугольников.
                  0
                  Не наделает:

                  На картинке отмечен лишний пиксель при растеризации верхнего треугольника. Его нужно отдельно учитывать для целочисленного алгоритма. Если цикл на float — этой проблемы не будет. Кроме того цикл на float позволит заменить постоянное деление в for по X на умножение. Ну а на современных процессорах операции с float уже такие же быстрые как и целочисленные.
                    0
                    Спасибо, вот и еще один кандидат на бенчмарк нарисовался.
                      0
                      Только обязательно переделать на float. А то лишние пиксели — это грубо говоря ошибка, да и деление на каждую строку сканлайна из-за целочисленности избыточно.
                  0
                  Скайнлайны — это традиционный и самый известный метод, но он нифига не подходит под определение красивого.
                  Ни в плане изящества кода, ни качества получаемого результата (он дает артефакты тонирования).
                    –4
                    Про артефакты тонирования — полный бред. Ознакомьтесь с методом, прежде чем так говорить.
                      +2
                      Ох. Давайте воздержимся от выражений типа «полный бред», по крайней мере, в публичной дискуссии, хорошо?

                      А по теме вот занимательное чтение, которое пробежало в конференции.
                  0
                  Нужно ли использовать коррекцию перспективы для Z-буфера?
                  У меня два куба, текстуры интерполируются нормально, но посмотрите на вертикальную линию пересечения кубов — в случае, когда я использую bc_clip, она кривая (кубы вверху), а когда использую bc_screen — она прямая (кубы внизу).

                    0
                    Да. Нужно. Вот тут объяснение на пальцах.
                  • UFO just landed and posted this here
                      0
                      Вы имеете в виду со сканирующей линией? Точно так же. Просто вместо билинейной интерполяции посчитайте барицентрические координаты текущего пикселя и сделайте поправку, описанную в этой статье.
                      • UFO just landed and posted this here
                          0
                          Вполне можно, нужно просто скорректировать координаты концов сканирующей линии.
                        • UFO just landed and posted this here
                        0
                        Кстати, было бы неплохо получить адд-он (здесь или на гитхабе) про то, как негру добавить глаза!
                          0
                          Эээ. Модель глаз лежит рядом с негром, достаточно её отрендерить вместе с головой, нет?
                            0
                            ааа, так это модель двух глаз сразу?
                              0
                              Да.
                        • UFO just landed and posted this here

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