Тесселяция в современном OpenGL

patch out float myValue;				// per-patch value

Ниже приводится пример простейшего тесселляционного шейдера, который просто передает входные вершины на выход и задает параметры тесселляции в соответствии с uniform-параметром level.

#version 410

layout ( vertices = 3 ) out;            // input patch consists of 3 vertices

uniform float level;

void main ()
{                                       // copy current vertex to output
    gl_out [gl_InvocationID].gl_Position = gl_in [gl_InvocationID].gl_Position;
    
    if ( gl_InvocationID == 0 )         // set tessellation level, can do only for one vertex
    {
        gl_TessLevelInner [0] = level;
        gl_TessLevelOuter [0] = level;
        gl_TessLevelOuter [1] = level;
        gl_TessLevelOuter [2] = level;
    }
}

Обратите внимание, что шейдер имеет доступ не только к входным данным для каждой вершины, но также и к выходным данным для каждой вершины патча (независимо от того для какой вершины он был вызван в данный момент). Это позволяет при расчете одних вершин патча обращаться к результатам обработки других вершин того же патча.

Однако это несется в себе опасность, поскольку порядок вызова шейдера для обработки вершин одного и того же примитива, неопределен. Для того, чтобы избежать опасности доступа к данным, которые еще не просчитаны, в tesselation control shader добавлена функция барьерной синхронизации - barrier() (аналогичная __syncthreads() в CUDA). Если при обработке вершины встречается вызов этой функции, то дальнейшая обработка этой вершины приостанавливается до тех пор, пока при обработке всех остальных вершин этого патча, не будет вызвана эта функция. Только после этого обработка вершин данного патча будет продолжена.

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

Тесселяция примитивов

Поддерживается три типа тесселляции примитивов - triangles, quads и isolines (см. рис. 2).

Рис 2. Типы тесселляции.

Сам тип тесселляции задается в tesselation evaluation shader при помощи директивы layout. Также в этой директиве задается способ разбиения отрезков (equal_spacing, fractional_even_spacing и fractional_odd_spacing) и способ упорядочивание вершин (cw, ccw).

layout ( triangles, equal_spacing, ccw ) in;

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

Ключевую роль в тесселляции играют параметры тесселляции. По стандарту наличие tesselaction control shader'а не является обязательным, в этом случае используются значения параметров тесселляции по умолчанию. Для задания этих значений служит функция glPatchParameterfv:

void glPatchParameterfv ( GLenum pname, const float * values );

Если параметр pname равен константе GL_PATCH_DEFAUL_OUTER_LEVEL, то values задают массив из четырех чисел. В случае, когда параметр pname равен GL_PATCH_DEFAULT_INNER_LEVEL, то values задают массив из двух чисел.

Если для примитива любой из используемых внешних уровней тесселляции меньше или равен нулю, то примитив отбрасывается тесселлятором. Для режима тесселляции quads используются все четыре внешних уровня, для режима тесселляции треугольников triangles используются только первые три и для режима isolines используется только первые два внешних уровня тесселляции.

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

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

int	maxLevel;
	
glGetIntegerv ( GL_MAX_TESS_GEN_LEVEL, &maxLevel );

Если в качестве способа разбиения отрезков выбран equal_spacing (это выбор по умолчанию), то соответствующий уровень тесселляции будет сперва отсечен по (приведен к) отрезку [1,max] (обозначим отсеченное значение через f), после чего полученное значение будет округлено вверх к ближайшему целому числу n и соответствующее ребро будет разбито на n равных частей.

Ниже приводятся скриншоты тесселляции треугольника для разных значений внешнего и внутреннего уровней тесселляции.

Рис 3. Пример тесселляции треугольника для разных значений параметра (equal_spacing).

Если в качестве способа разбиения выбран fractional_even_spacing, то соответствующий уровень разбиения будет приведен к отрезку [2,max], после чего округлен вверх к ближайшему четному целому числу n. Для способа разбиения fractional_odd_spacing отсечение производится по отрезку [1,max-1] и округляется вверх к ближайшему нечетному целому числу n.

Таблица 1. Допустимые значение параметра pname для функции glGetActiveUniformBlockiv.

Способ разбиения	Отсекается по отрезку	Округляется вверх к
equal_spacing	[1,max]	ближайшему целому
fractinal_even_spacing	[2,max]	ближайшему четному целому
fractional_odd_spacing	[1,max-1]	ближайшему нечетному целому

Если полученное таким образом значение n равно единице, то соответствующий отрезок не разбивается вообще. В противном случае (для fractional_even_spacing и fractional_odd_spacing) отрезок разбивается на n-2 отрезка одинаковой длины и два дополнительных отрезка. Длины этих дополнительных отрезков равны между собой и они располагаются симметрично относительно концов разбиваемого отрезка.

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

Ниже показаны скриншоты тесселляции треугольника, соответствующие дробным уровням тесселляции и режимам разбиения fractional_even_spacing и fractional_odd_spacing.

Рис. 4. Разбиение сторон треугольника для дробных уровней тесселляции.

Тесселлятор генерирует примитивы (треугольники и отрезки) с вершинами, упорядоченными либо по часовой стрелке (cw), либо против часовой стрелки (ccw). По умолчанию используется упорядочение против часовой стрелки. Упорядочивание понимается в смысле координат (u,v,w), назначаемых каждой вершине, генерируемого примитива.

Можно в tessellation evalutation shader в директиве layout задать ключевое слово point_mode, тогда на выходе тесселлятора будут не треугольники или отрезки, а точки.

layout ( equal_spacing, point_mode ) in;

Тесселляция треугольников (triangles)

Первым шагом тесселляции треугольника является построение набора вложенных друг в друга треугольников (см. рис. 5).

Рис 5. Построение системы вложенных треугольников.

Если после отсечения и округления все используемые уровни тесселляции равны единице, то генерируется только один треугольник с координатами вершин равными (0,0,1), (0,1,0) и (1,0,0). Если внутренний уровень равен единице и хотя бы один из внешних уровней больше единицы, то считается, что внутренний уровень задан как 1+eps, после чего производится округление (в соответствии со способом разбиения) к 1 или 2.

Для построения набора вложенных треугольников используется следующая процедура - сперва все три ребра текущего треугольника (начиная с исходного) разбиваются на n (отсеченное и округленное значение первого внутреннего уровня тесселляции) одинаковых отрезков. Если n равно двум, то мы получаем вырожденный внутренний треугольник (точка пересечения серединных перпендикуляров к сторонам треугольника). В противном случае от точек разбиения, соседних с вершинами проводятся перпендикуляры, пересечения которых и дают три вершины для вложенного треугольника (рис. 6).

Рис 6. Построение внутреннего треугольника.

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

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

После этого производится разбиение ребер всех этих треугольников. Далее для каждого такого треугольника (кроме исходного) область между ним и вложенным в него треугольником заполняется треугольниками, построенными на вершинах разбиения.

Рис 7. Заполнение областей между вложенными треугольниками.

Для этих шагов используется только первый внутренний уровень тесселляции и первые три внешние уровня.

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

Каждой вершине для всех сгенерированных треугольников назначаются барицентрические координаты (u,v,w), однозначно определяющие положение вершины в исходном треугольнике. Для этих координат выполнены следующие условия - все компоненты лежат на отрезке [0,1] и u+v+w=1.

Конкретный детали тесселляции зависят от реализации и могут отличаться для различных GPU.

Тесселяция четырехугольников (quads)

Тесселляция четырехугольников заметно проще тесселляции треугольников. Сначала два вертикальных ребра (соответствующих u=0 и u=1) разбиваются на равное число одинаковых отрезков, задаваемое первым внутренним уровнем тесселляции. После этого два горизонтальных ребра (соответствующих v=0 и v=1) разбиваются аналогичным образом, но здесь число отрезков определяется уже вторым внутренним уровнем тесселляции.

При этом получается блок из прямоугольников (в координатах (u,v)) и все прямоугольники, не касающиеся сторон исходного четырехугольника, разбиваются на пары треугольников.

Рис 8. Тесселляция четырехугольника - внутренние полосы.

Далее каждое из четырех ребер исходного четырехугольника разбивается в соответствии с четырьмя внешними уровнями тесселляции (каждому ребру соответствует свой уровень) и оставшаяся полоса заполняется треугольниками, построенными на точках разбиения и вершинах. Каждая вершина каждого треугольника получает свои координаты (u,v) (обе координаты лежат на отрезке [0,1]), определяющие ее положение в исходном четырехугольнике.

Тесселяция четырехугольников в режиме isolines

В этом режиме тесселляции поступающий на вход четырехугольник разбивается на набор горизонтальных (v=const) ломаных (см. рис. 9). Сначала используя второй внешний уровень разбиения два вертикальных отрезка (соответствующих u=0 и u=1) разбиваются на равные части (способ разбиения для этого режима не играет никакой роли). Через точки разбиения проводятся горизонтальные отрезки (u=const), которые разбиваются в соответствии с первым внешним уровнем тесселляции. На выходе тесселлятора - набор отрезков, каждой вершине сопоставляются координаты (u,v), аналогично случаю тесселляции четырехугольника.

Рис 9. Тесселляция в режиме изолиний.

Tesselation Evaluation Shader

Обратите внимание, что при тесселляции треугольников и четырехугольников (triangles и quads) явно задается разбиение для каждого из ребер исходного примитива. Это позволяет избегать разрывов при выводе большого числа патчей - необходимо только назначать одинаковые внешние уровни разбиения для ребер, принадлежащих сразу двум примитивам (см. рис 10).

Рис 10. Согласование уровней тесселляции для набора патчей.

Tesselation evaluation shader (GL_TESS_EVALUATION_SHADER) вызывается отдельно для каждой вершины созданного тесселлятором примитива. При этом он получает координаты вершины ((u,v) или (u,v,w)). Шейдер имеет доступ сразу ко всем вершинам исходного патча, к uniform-переменными и текстурам.

Этому типу шейдера доступны следующие стандартные входные переменные:

• gl_in выходные значения для всех вершин патча от tessellation control shader'а (gl_Position, gl_PointSize gl_ClipDistance);
• gl_PatchVerticesIn - число вершин исходного патча;
• gl_PrimitiveID - номер примитива (в текущей команде glDraw*);
• gl_TessCoord (u,v,w) - трехмерный вектор с координатами, идентифицирующими положение вершины в патче;
• gl_TessLevelInner - массив внутренних уровней тесселляции;
• gl_TessLevelOuter - массив внешних уровней тесселляции.

Также шейдер могут получать входные данные от tessellation control shader'а, они описываются как входные (т.е. имеют спецификатор in) и описаны как массивы. Также шейдеру доступны входные переменные типа patch, задающие значения для всего примитива.

Результаты своей работы шейдер записывает с стандартные выходные переменные - gl_Position gl_PointSize и gl_ClipDistance.

Ниже приводится пример простого tessellation evalutaion shader'а.

#version 410 core

layout(triangles, equal_spacing) in;

void main(void)
{

    gl_Position = gl_TessCoord.x * gl_in [0].gl_Position + 
                  gl_TessCoord.y * gl_in [1].gl_Position +
                  gl_TessCoord.z * gl_in [2].gl_Position;
}

Тесселляция поверхности Безье

Одним из наиболее известных примеров сплайновый поверхностей является кубическая поверхность Безье. Она задается набором из 16 контрольных точек p_ij и по ним для каждого значения параметров u и v из отрезка [0,1] следующая формула задает соответствующую точку на поверхности:

Здесь через B_i³ обозначен полином Бернштейна

Для вывода поверхности Безье в качестве патча выступает набор из 16 контрольных точек, tessellation control шейдер применяет матрицы преобразований к контрольным точкам, а tessellation evaluation шейдер по параметрам осуществляет вычисление координат.

Ниже приводятся два скриншота, соответствующие выводу поверхности Безье с разными уровнями тесселляции.

Рис 11. Тесселляция поверхности Безье.

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

//
// Bezier qubic patch
//

-- vertex

#version 410 core

uniform mat4 proj;
uniform mat4 mv;

in vec3 position;

void main(void)
{
    gl_Position = proj * mv * vec4 ( position, 1.0 );
}

-- tesscontrol

#version 410 core

uniform int inner;
uniform int outer;

layout(vertices = 16) out;

void main(void)
{
    gl_TessLevelInner [0] = inner;
    gl_TessLevelInner [1] = inner;
    gl_TessLevelOuter [0] = outer;
    gl_TessLevelOuter [1] = outer;
    gl_TessLevelOuter [2] = outer;
    gl_TessLevelOuter [3] = outer;

    gl_out [gl_InvocationID].gl_Position = gl_in [gl_InvocationID].gl_Position;
}

-- tesseval

#version 410 core

layout(quads, equal_spacing) in;

void main(void)
{
    float   x = gl_TessCoord.x;                 // u,v coordinates for Bezier patch
    float   y = gl_TessCoord.y;
    vec4    u = vec4 ( 1.0, x, x*x, x*x*x );
    vec4    v = vec4 ( 1.0, y, y*y, y*y*y );
    mat4    b = mat4 (  1,  0,  0, 0,
                       -3,  3,  0, 0,
                        3, -6,  3, 0,
                       -1,  3, -3, 1 );
                       
    vec4    bu = b * u;                 // vector or Bernstein polynoms at u, bu.x is B0(u)
    vec4    bv = b * v;                 // vector or Bernstein polynoms at v

    vec4 p00 = gl_in [ 0].gl_Position;
    vec4 p10 = gl_in [ 1].gl_Position;
    vec4 p20 = gl_in [ 2].gl_Position;
    vec4 p30 = gl_in [ 3].gl_Position;
    vec4 p01 = gl_in [ 4].gl_Position;
    vec4 p11 = gl_in [ 5].gl_Position;
    vec4 p21 = gl_in [ 6].gl_Position;
    vec4 p31 = gl_in [ 7].gl_Position;
    vec4 p02 = gl_in [ 8].gl_Position;
    vec4 p12 = gl_in [ 9].gl_Position;
    vec4 p22 = gl_in [10].gl_Position;
    vec4 p32 = gl_in [11].gl_Position;
    vec4 p03 = gl_in [12].gl_Position;
    vec4 p13 = gl_in [13].gl_Position;
    vec4 p23 = gl_in [14].gl_Position;
    vec4 p33 = gl_in [15].gl_Position;  

    gl_Position = bu.x * (bv.x * p00 + bv.y * p01 + bv.z * p02 + bv.w * p03) +
                  bu.y * (bv.x * p10 + bv.y * p11 + bv.z * p12 + bv.w * p13) +
                  bu.z * (bv.x * p20 + bv.y * p21 + bv.z * p22 + bv.w * p23) +
                  bu.w * (bv.x * p30 + bv.y * p31 + bv.z * p32 + bv.w * p33);
}

-- fragment

#version 410 core

out vec4 color;

void main(void)
{
    color = vec4(1.0);
}

Полезные ссылки

First Contact with OpenGL 4.0 GPU Tessellation

Hardware Tessellation on Radeon in OpenGL (Part 1/2)

Hardware Tessellation on Radeon in OpenGL (Part 2/2)

Hardware Tessellation on Radeon in OpenGL: Radeon HD 5000 Tessellators Details

Спецификация расширения ARB_tessellation_shader.

По этой ссылке можно скачать весь исходный код к этой статье. Также доступны для скачивания откомпилированные версии для M$ Windows и Linux.