Tesselation Shaders and View Dependant Tesselation

TESSELATION SHADERS 



 

Introduction 

In this blog post I will be talking about my project about tesselation shaders (In OpenGL), point normal triangle subdivision (pn-triangles) and rendering fur on objects using tesselation shaders.

What are Tesselation Shaders?

Tesselation is the process of creating more, and usually smaller, geometry from the existing geometry as shown in the figure below and nothing more.
 

 
 OK but then why do we need or want to use tesselation shaders. We want them becasue they can provide dynamic level of detail. 
 

Figure 1: Tesselated face mesh

 
In this way we don't have to render a high detail mesh if an object is far from our eye we can just render the mesh with low resolution and gain performance. If object comes closer we can use tesselation shaders to generate a higher resolution object on the fly.


We may also want to use tesselation shaders for another reason and that is again about performance. If you know a little bit about computer hardware and it's performance issues you know that most of it's performance issues are related to memory access and bandwidth. Therefore sending data from DRAM to GPU causes a lot of performance issues in many applications but if we use a low resolution mesh and a displacement map for instance we can still create a high detailed objects. You can see the memory cost of a monster frog mesh as it levels up in a game versus it's corresponding low resolution mesh and displacement map's memory cost. We can get performance
 
Figure 2: Monster Frog


Stages of Tesselation in OpenGL

Even though I will be talking about OpenGL in this blog post In OpenGL, tesselation concepts are pretty much alike across the graphics API's. Tesselation consists of three stages: tesselation control shader (Hull shader in D3D), tesselated primitive generation and tesselation evaluation shader.(Domain Shader in D3D). Below you can see the places of these stages in OpenGL's rendering pipeline. 
 
 


After vertex shader applies the necessary transformations to our vertices our tesselation control shader takes the input patches (we will talk about patches in a minute but for now think of them as arbitrary number of vertices packed together) and decides how much tesselation is needed and tesselation primitive generator takes these tesselation parameters and gives us newly generated primitives. Then tesselation evaluation shader acts just like a vertex shader and decides where this vertex should reside in 3D space. 

Tesselation Primitive Types

Good part is we can generate isolines, triangles and even quads with tesselation shaders.
Below you can see different tesselated primitives that can be generated from tesselation primitive generator. They are taken form 
 
 
 



 

And based on the primitive type our tesselation control shader takes an input 
 
in vec3 gl_TessCoord;

In quads and isolines it's first two elements are meaningfull and they represent a 2D coordinate system. In triangles they represent barycentric coordinates. They always have values between [0, 1]. Our tesselation can differentiates different vertices using these primitive coordinate parameters.

Patches 

Finally we will talk about patches. Unlike vertex just shaders a little bit like geometry shaders our tesselation shaders deal with sets of data at the same time. This means that just like geometry shaders we have more information about a vertex in a tesselation shaders. The difference is between geomtery shaders and tesselations shaders is that geometry shaders deal with predefined OpenGL primitives. We are restricted by what OpenGL gives us. But in Tesselation shaders we can say that I will have a patch of 16 vertices, I will have a patch of 54 vertices and generate complex primitives based on our arbitrary data, meaning we define what vertices mean. So if we want to deal with triangles we can say we will have a patch size of 3 or if we want to have a bezier curve we can say I will have a patch size with 4 vertices or 16 for bezier surfaces. That is the beauty of tesselation shaders. When tesselation primitive generator generates triangles or quads it just creates them and establishes their connections to each other but does nothing about their positions. That's where the tesselation evaluation shader comes in.

Tesselation Evaluation Shader

After the primitives are tesselated according to arguments set by tesselation control shader. We need to decide where they will be placed on 3D space. Just like a vertex shader our tesselation evaluation shader only outputs 1 vertex at a time but neat part is can access all the patch data plus the additional data what tesselation control shader may output. This allows us to do very interesting things. In the following parts of this blog post I will talk about a few examples of these intereseting things: PN- triangle tesselation, bezier patch rendering or fur rendering shaders.

For more Information about Tesselation Shaders in OpenGL you can visit the links below or read the following books' associated chapters.
https://www.khronos.org/opengl/wiki/Tessellation
https://www.khronos.org/opengl/wiki/Tessellation_Control_Shader
 
Books:
 

Point Normal Triangles

Point normal triangles (pn triangles) is an algorithm developed by A. Vlachos et al. . It basically takes an input triangle vertices and it's vertex normals and based on these data generates a triangular bezier patch then using that patch depending on the level of detail tesselates more triangles from the existing triangle.
My outputs from PN-trianglesFigure 3: PN bezier patch generation [2]
So we can have as many triangles as we want 
 
 
Figure 4: Tesselated PN-Bezier Patch [2]




I won't go into details of this algorithm in this blog post because then I would be telling the same thing in the actual paper instead you should read it yourself if you are interested(see reference [1]). Instead I will just give the my code which is an implementation of their formulas.

Figure 5: Bezier Control points of a pn triangle

Below you can see my code for the full tesselation evaluation shader's main function. Writers of the paper made it so easy to implement, they have given us formulas that can be directly coded. I have just implemented the formulas in PN-triangles paper in glsl. The code is mostly self explanatory.


void main()
{
    float u = gl_TessCoord.x,
          v = gl_TessCoord.y,
          w = gl_TessCoord.z;

    vec3 p0 = tese_in[0].fragWorldPos.xyz,
         p1 = tese_in[1].fragWorldPos.xyz,
         p2 = tese_in[2].fragWorldPos.xyz;

    vec3 n0 = normalize(tese_in[0].fragWorldNor),
         n1 = normalize(tese_in[1].fragWorldNor),
         n2 = normalize(tese_in[2].fragWorldNor);

    vec3 b300 = p0,
         b030 = p1,
         b003 = p2;

    float wNorms[3][3];

    for(int i=0; i < 3; i++)
    {
        for(int j=0; j < 3; j++)
        {
            wNorms[i][j] = dot(tese_in[j].fragWorldPos.xyz - tese_in[i].fragWorldPos.xyz, tese_in[i].fragWorldNor);
        }
    }

    vec3 b210 = (2*p0 + p1 - wNorms[0][1] * n0)/3.0,
         b120 = (2*p1 + p0 - wNorms[1][0] * n1)/3.0,
         b021 = (2*p1 + p2 - wNorms[1][2] * n1)/3.0,
         b012 = (2*p2 + p1 - wNorms[2][1] * n2)/3.0,
         b102 = (2*p2 + p0 - wNorms[2][0] * n2)/3.0,
         b201 = (2*p0 + p2 - wNorms[0][2] * n0)/3.0;

    vec3 E = (b210 + b120 + b021 + b012 + b102 + b201)/ 6.0;
    vec3 V = (p0 + p1 + p2)/3.0;

    vec3 b111 = E + (E - V) / 2.0;
    
    //calculate normal coefficients
    vec3 n200 = n0,
         n020 = n1,
         n002 = n2;
    
    float v01 = 2 * dot(p1 - p0, n0 + n1) / dot(p1 - p0, p1 - p0),
          v12 = 2 * dot(p2 - p1, n1 + n2) / dot(p2 - p1, p2 - p1),
          v20 = 2 * dot(p0 - p2, n2 + n0) / dot(p0 - p2, p0 - p2);

    vec3 n110 = normalize(n0 + n1 - v01 * (p1 - p0)),
         n011 = normalize(n1 + n2 - v12 * (p2 - p1)),
         n101 = normalize(n2 + n0 - v20 * (p0 - p2));

   
    tese_out.fragWorldPos = vec4( b300*w*w*w   + b030*u*u*u   + b003*v*v*v   +
                                  b210*3*w*w*u + b120*3*w*u*u + b201*3*w*w*v +
                                  b021*3*u*u*v + b102*3*w*v*v + b012*3*u*v*v +
                                  b111*6*w*u*v
                                  ,1.0);

    tese_out.fragWorldNor = n200*w*w + n020*u*u + n002*v*v +
                            n110*w*u + n011*u*v + n101*w*v;

    gl_Position = projectionMatrix * viewingMatrix * tese_out.fragWorldPos;
    //We are already in world coordinates no need for modelling transformation
}


To summarize this code it first takes all 3 input vertices and their normals and generates a triangular Bezier patch then using the (u, v, w) coordinates given by tesselation primitive generator to determine points actual position in 3D space and it's normal. One important catch here is that writers of the pn-triangle paper seen that after interpolating positions according to a cubic equation they could not use linear interpolation for  vertex normals and decided that even though they have used a cubic equation for vertex position sampling they have used a quadratic equation for vertex normal sampling. In figure 6 you can see the visual differences of the normal sampling.
Figure 6: PN-triangles and shading [1]

My outputs from PN-triangles












and below you can see an gif switching between different level of details. Pleased do not confused about aliasing artifacts caused by the gif's low resolution. As you can see above they are actually shaded much better.
 

View Dependant Level of Detail

Up to now have achieved dynamic different level of detail thats nice but still they have to be set manually. Many appliactions need them to be dynamic without setting them dynamic and the best example of this is computer games. In many computer games If an object is far from camera it is rendered with low level of detail (LOD) but their LOD is increased instantly if player gets closer to that object. in order to that I have written the tesselation control shader below(it is not the full shader but only the related part about view dependant tesselation.

        precise float zoomScale = 90.f/cameraFov;
        precise float d = distance(vec4(eyePos, 1.f), objCenter);

        precise float LOD = 30.f/(d*d) * levelOfDetail * zoomScale;

        gl_TessLevelOuter[0] = LOD;
        gl_TessLevelOuter[1] = LOD;
        gl_TessLevelOuter[2] = LOD;
        gl_TessLevelInner[0] = LOD ;

It takes the precomputed objCenter and dynamically changing cameraFov and eyePos  uniform variables from the OpenGL program and based on that determines the level of detail so that it would be inversely propotional to the square of eye distance. Probably a better function could be found for level of detail but for now I think it is not bad (I have got the idea from physics i.e magnetic and gravitational forces). Below you can see how view dependant tesselation works. 



Limitations of PN-triangle subdivision


Unlike most of the other subdivision algorithms like Catmull-Clark subdivision PN-triangles does not need the data of the adjacent primitives. This is very good because forward rendering pipeline, even with geometry and tesselation shaders, deal with one primtive at a time. This makes pn-triangles directly applicable to forward rendering pipeline. It is applicable to even pre-existing 3D meshes because most of the meshes already uses vertex normals. For ınstance the utah teapot I have used in the demonstrations above is modelled this way instead of bezier patches.

The downside of this method is that after some level of detail objects can not be tesselated. For instance if the 3D mesh is approximating a circle like in this teapot it can not be perfectly approximated no matter how many triangles we add to the model. This is due to we are approximating an already approximated model below you can see how the teapot still has it's sharp edges.
 
Figure 7: no pn triangles vs high pn-tesselation

In the original paper by A. Vlachos et al. this is mentioned they say that pn-triangles is not supposed replace designer level detail.

One other downside of pn triangles is that can create very tiny shading artifacts.
 
Figure 8: pn-triangle artifacts

In a very dyanamic computer game the user might not notice this but is still not very pleasant but when it is used with an model that is feasible for this method pn-triangles are very efficent and very simple to use.

How to overcome these limitations?

Well sometimes some algorithms or methods just have their limitations and should be replaced by others. And that is what I did in this situation. After implementing pn-triangles I wasn't very pleased with the aforemtioned artifacts and decided to implement another tesselation model. One of the most common ones: Bezier patches.

 

Implementing Bezier Patch Tesselor Program 

 Actually this part was very simple and straight forward for me because this was not the first time I was dealing with bezier patches (see my blog about bezier modelled flag https://bezierflag.blogspot.com/ ). After finding the data all I did was to set the patch size to 16 and write bezier formula's implementation in glsl. Below you can see my full code for bezier patch tesselation evaluation shader. The code should be self explanatory if you are familiar with Bezier surfaces. If not see Bezier Surface.

#version 460 core

#define M_PI 3.1415926535897932384626433832795
#define EPSILON 1e-2


layout (std140, binding = 0) uniform matrices
{
    mat4 modelingMatrix;
    mat4 viewingMatrix;
    mat4 projectionMatrix;
    vec3 eyePos;
};

layout (std140, binding = 1) uniform tessLevels
{
    float tessInner;
    float tessOuter;
    float levelOfDetail;
    int viewDependantTesselation;
    float cameraFov;
};

layout ( quads, equal_spacing, cw) in;


in TESC_TESE_INTERFACE
{
    vec3 fragWorldPos;
} tese_in[];

out TESE_FS_INTERFACE
{
    vec4 fragWorldPos;
    vec3 fragWorldNor;
    vec2 texCoord;
} tese_out;


float bern(int i, float u);

void main()
{
    float u = gl_TessCoord.x;
    float v = gl_TessCoord.y;

    tese_out.texCoord = vec2(u,v);
        
    vec3 vert = vec3(0.f, 0.f, 0.f);

    for(int i = 0; i <= 3; ++i)
    {
        for(int j = 0; j <= 3; ++j)
        {
            vert += bern(i, u) * bern(j, v) * tese_in[i*4 + j].fragWorldPos;
        }
    }

    vec3 du = vec3(0.f, 0.f, 0.f);
    vec3 dv = vec3(0.f, 0.f, 0.f);
    int dir = 1;

    float e1 = EPSILON;
    float e2 = EPSILON;
    if(u > 0.5){ e1 = -e1; dir = -dir;}
    if(v > 0.5){ e2 = -e2; dir = -dir;}


    for(int i = 0; i <= 3; ++i)
    {
        for(int j = 0; j <= 3; ++j)
        {
            du += bern(i, u+ e1/2.0) * bern(j, v+e2/3.0) * tese_in[i*4 + j].fragWorldPos;
            dv += bern(i, u+ e1/3.0) * bern(j, v+e2/2.0) * tese_in[i*4 + j].fragWorldPos;
        }
    }

    tese_out.fragWorldPos = vec4(vert,1);
    tese_out.fragWorldNor = cross(dv-vert, du-vert) *dir;

    gl_Position = projectionMatrix * viewingMatrix * tese_out.fragWorldPos;
}

float bern(int i, float u)
{
// Binomial lookup table
    const float bc[4] = {1.f, 3.f, 3.f, 1.f};
    return bc[i] * pow(u, i) * pow(1-u, 3-i);
}

You can see how much nicer it is to approximate the actual mathematical function compared to pn-triangles. This also show the actual power of tesselation shaders.


You may have seen a few artifacts, espacially on the teapots spout, that are caused by Z buffer because while I took this footage I had set a very big distance between near and far planes and if you didn't know z buffer stores z values between 0 and 1 so if you have a huge distance between near and far plane the Z buffer values of the fragments get squished in a very low interval and with the floating point errors caused by computer hardware causes such artifacts . If you decrease the distance between the near and far planes these artifact go away. I have left the footage this way so I can mention this extra bit of knowledge.


FUR RENDERING

Now that we I have implemented subdivision algorithms. I will now take a break of them with implementing another thing with tesselation shaders: FUR RENDERING!!
 
I have already mentioned that OpenGL support isolines as tesselated primitives. That's what I will be using for rendering furs on objects. The first step of rendering furs on a triangle was to determine how to place fur strangles on a triangle uniformly. We all know that medians of a triangle splits it into nice equal 6 pieces so I have directly tried to take advantage of that and after a few failed attempts I have came up with the following algorithm. 

Step 1 - Give unique hairID's to all fur pieces in a triangle from 0 to n-1 (for n hair pieces)
Step 2 - if the hair ID is equal to 0 them directly place it to the center of the triangle and finish
Step 2 - If it is not 0 then check it's remainder depending on the remainder of the hairID change the current triangle vertices to one of the 6 lesser triangles generated by the original triangles medians.
Step 3 - change the hairID to "hairID/6" but be carefull this has to be integer division and go to Step2
 
find the hairRoot normal (A.K.A hairDirection) by using the same algorithm using linear interpolation between vertex normals.
 
Since we are using integer division we are bound to reach 0 and using remainders of the hairID gives us a nice distribution across the triangle. As long as we keep dividing the triangles by this method we will get visually pleasing methods othervise some methods.

Of course I have said that give each hair a unique ID but how do we do that, our tesselation shaders only has tesselated (u,v) coordinates. well one of them (v) actually can be used to deduce the hairID by the following line snippet.

int hairID = int(round(v / (1.0f/gl_TessLevelOuter[0]))+0.001);
 
But you have to be careful and declare output primitives as.
 
layout ( isolines, equal_spacing, ccw) in;

in the tesselation evaluation shader. so that each primitve is tesselated with equal space.

then we take divide the total number hairs (gl_TessLevelOuter[0] represents that) and divide 1 by it that gives us the amount of each different hair gets in the v coordinates. and when we divide the v by this number we get the hairID.
For example let's say we have four hairs then they will get 0, 0.25, 0.5, 0.75 as their v coordinates. When since the gl_TessLevelOuter[0] is 4 (number of hairs)
 
1/4 = 0.25 and v/0.25 will give us a unique hairID for each of the lines in [0,3] interval.
 
 after finding hairs root position and root normal find the actual triangle normal by using vertices not the given vertex normals. Then use cross product find a vector perpendicular to both actual normal and the interpolated normal the rotate the interpolated normal along this axis by using a user defined hairCurvature amount(theta degrees) to find where this hair string will end. We will call this the hairTip naturally. After finding hairRoot and hairTip we will assign them direction vectors so we can generate hermite curves out of them. We will use the interpolated hairRoot normal as out first tangent vector for simplicity and we will rotate it two theta amounts along the same axis again to find the other hermite tangent vector. So the geometry looks like below
 




 After finding these convert these hairRoot hairTip points/tangents a bezier curve using the formula below.






Then we will finally get nice bezier curve furs. when we sample the using the gl_TessCoord[1] as bezier sampling parameter. We get the following results on stanford bunny.


But you can see that the are curvy but something is wrong. and that is of course lighting.
To solve that I have used the simplest hair shading technique (it is a lot like phong shading for hairs actually) mentioned in Cem Yuksel's Advanced Techniques in Real-time Hair Rendering and Simulation lecture notes. They have suggested the following





After implementing Kajiya-Kay Hair Shading I finally got the following result.


I am not going to explain the implementation details because it should be very straightforward for any person who have implemented phong shading. The fur rendering part can be improved I am not sure If I will spend time on this but you can clearly see that it can be better.

Having a little bit off fun 

Well since we rendered a bunny and I know how to implement perlin noise why don't we merge them.

A bunny with a perlin noise sampled fur.

References

 
[1] PN triangles paper https://dl.acm.org/doi/10.1145/364338.364387
[2] M. Bailey and S. Cunnignham, Graphics Shaders, ch. 9,
pp.315-351. 2012 AK Peters/CRC Press
[3] https://developer.nvidia.com/content/dynamic-hardware-tessellation-basics
[4] http://developer.download.nvidia.com/presentations/2009/GDC/GDC09_D3D11Tessellation.pdf
[5] The OpenGL® Programming Guide 9th Edition, John Kessenich, Graham Sellers, and Dave Shreiner
 [6] http://www.cemyuksel.com/courses/conferences/siggraph2010-hair/ 
[7] https://www.khronos.org/

Comments

Post a Comment