Importance sampling GGX NDF - fireflies and bright final result https://schuttejoe.github.io/post/ggximportancesamplingpart1/ - I have problem implementing this method. Somebody asked question about this before ( Can't understand the Importance sampling GGX ) but it doesn't fully answer my question/problem.
Above blog post describe importance sampling method based on importance sampling NDF. Let's start with Cook-Torrance BRDF:
$$
f_r = \frac{F(w_i, w_m) ~ G_2(w_i, w_o, w_m) ~ D(w_m)}{4 ~ |w_i \cdot w_g| ~ |w_o \cdot w_g|}
$$
After finding PDF for Normal Distribution Function and applying
$$
|w_i \cdot w_g|
$$
term from rendering equation + found PDF, we have final equation:
$$
\frac{F(w_i, w_m) ~ G_2(w_i, w_o, w_m) ~ |w_o \cdot w_m|}{|w_o \cdot w_g| ~ |w_m \cdot w_g|}
$$
I'm adding final equation just for completion sake. All transformations are rather long and it's better to check blog post that I've sent. At the end of post, there is code that should be working correctly. However, it doesn't give correct results in my case and my suspicion is that I'm filling gaps in a wrong way:
I'm using Correlated Multi-Jittered Sampling here:
float SmithGGXMaskingShadowing(float3 n, float3 l, float3 v, float a2)
{
    float dotNL = saturate(dot(n, l));
    float dotNV = saturate(dot(n, v));

    float denomA = dotNV * sqrt(a2 + (1.0f - a2) * dotNL * dotNL);
    float denomB = dotNL * sqrt(a2 + (1.0f - a2) * dotNV * dotNV);

    return 2.0f * dotNL * dotNV / (denomA + denomB);
}

float a2 = roughness * roughness;
float theta = acos(sqrt((1.0f - brdfSample.x) / ((a2 - 1.0f) * brdfSample.x + 1.0f)));
float phi = 2.0f * PI * brdfSample.y;

float3 normalTS = float3(0, 1, 0);

float3 wo = -incomingRayDirTS;
float3 wm = float3(sin(theta) * cos(phi), cos(theta), sin(theta) * sin(phi));
float3 wi = 2.0f * dot(wo, wm) * wm - wo;

float3 F = Specular_F_Schlick(specularAlbedo.rgb, saturate(dot(wi, wm)));
float G = SmithGGXMaskingShadowing(wm, wi, wo, a2);
float weight = abs(dot(wo, wm) / (dot(normalTS, wo) * dot(normalTS, wm)));

rayDirWS = normalize(mul(wi, tangentToWorld));

if (dot(normalTS, wi) > 0.0f && dot(wi, wm) > 0.0f)
    throughput = F * G * weight;
else
    throughput = 0.0f;

My main concern is - am I using normal in tangent space (w_g) in a correct way? Schutte Joe mentions in a comment that:

// -- Ensure our sample is in the upper hemisphere
// -- Since we are in tangent space with a y-up coordinate
// -- system BsdfNDot(wi) simply returns wi.y

That's why I decided to use w_g (or normalTS) as float3(0, 1, 0).
Here is how it looks for 1024 samples with path length equal 4:

In comparison, here is method based on visible normals described here - https://schuttejoe.github.io/post/ggximportancesamplingpart2/ ; For 1024 samples, path length 4, results are much better. However, based on data provide by author of the post, there shouldn't be that much difference:

Edit: @B_old is right, I mixed TS and WS. I present corrected results above -   image is slightly better but still has very high variance and some bright spots.

I've made a few changes in my code, so let's start with basic image that I had problem we that we'll state as a problem at the beginning:

After changing part of the code from:
float weight = abs(dot(wo, wm) / (dot(normalTS, wo) * dot(normalTS, wm)));
if (dot(normalTS, wi) > 0.0f && dot(wi, wm) > 0.0f)

To this (i.e. moving part of calculations to world-space):
float weight = abs(dot(wo, wm) / (dot(triangleNormal, incomingRayDirWS) * dot(normalTS, wm)));
if (dot(triangleNormal, rayDirWS) > 0.0f && dot(wi, wm) > 0.0f)

I am getting better results. Here are series of images with different settings:
1024 spp, 4 bounces

5000 spp, 4 bounces

5000 spp, 1 bounce

Notice that 4 bounces version is having more fireflies and noise. Long specular paths might be a reason of introducing noise. Also, 5000 spp are getting darker than 1000 spp. Reason is that path is probably introducing no changes, therefore average color is getting darker. You can see it in the last line of main post. I'm going to put it below for reference:
if (dot(triangleNormal, rayDirWS) > 0.0f && dot(wi, wm) > 0.0f)
    throughput *= F * G * weight;
else
    throughput *= 0;

Last thing. Here is image generated with better method ( https://schuttejoe.github.io/post/ggximportancesamplingpart2/ ). 1024 spp, 4 bounces:

Overall, I got rid of weird noise and artifacts. Algorithm got closer to better method and I think it can be treated as fixed.


Heirarchy in Euler rotations Why is there necessarily a hierarchy in Euler rotations?

For example I need to decide that I want

x to affect y and z
z to affect y
y to affect nothing.

What if I wanted to have something like:

x to affect y and z
z to affect x and y
y to affect nothing

(x, y and z refer to rotations about x, y and z)

I understand for a physical gimbal there is a restriction, but that need not be necessary for a computer graphics system, right?

Euler rotations work around the axes. This is represented in 3 angles (rot_x, rot_y, rot_z). The order of the rotation needs to be determined as the order affects the result.

For example, if we have a point (1, 0, 0) and we rotate 90 degrees around the Y and then 90 degrees around the Z, then the result will be

v1 = (1,0,0)
v2 = rotate_y(v1, 90) # v2 = (0,0,1)
v3 = rotate_z(c2, 90) # v3 = (0,0,1)

When doing the other order first Z and then Y, the result is different:

v1 = (1,0,0)
v2 = rotate_z(v1, 90) # v2 = (0,1,0)
v3 = rotate_y(c2, 90) # v3 = (0,1,0)

In computer graphics systems, quaternion rotations are often used, which allows rotation around any axis. This then solves many of the problems with Euler systems.


Why are inverse transformations applied to rays rather than forward transformations to objects? When computing ray-object intersections against a transformed object, most raytracers apply the inverse transform to each ray and compute the intersection against a non-transformed object.  Wouldn't applying the forward transform, putting the object into a flat world-space, be faster and more efficient, because you only need to compute the transform once?

Most raytracers do both!

Have you ever seen a ray-triangle intersection test where the triangle is transformed so that one vertex is at the origin and the triangle is flat along one of the axes? That would simplify the test, but storing the inverse transformation to apply it to the ray takes more space than the triangle itself. So you could say that almost all ray-triangle tests do apply the forward transformation to the object.

And yet most of the time you are rendering a mesh of many triangles, and "most raytracers" don't transform every vertex in the mesh by the object's transform matrix, they inverse transform the ray into object space. There isn't necessarily a good reason for this—it can definitely be more performant in some cases to preprocess the mesh and put every vertex in world space.

But then say you're doing animation studio-scale path tracing. Now your scene geometry might not all fit in RAM at once. It's no longer a performance win to pre-transform all your vertices/control points, because (a) you need one copy of the object per instance, and (b) you need to transform it each time you read it into RAM. When data bound, the cost of two matrix multiplies per ray is insignificant anyway.

Floating point precision is a potential reason as well: when you have an object a long way from the origin, you get more error from floating point positions, and if you pre-transform the object you apply that error in different directions to each vertex, whereas if you inverse transform the ray you have one fixed error amount from the imprecise position of the ray, but your vertices have less error relative to each other.

Although I suspect the real answer to "why do most raytracers inverse transform the ray" is that most raytracers with public source code implement a wide range of geometric primitives, either for educational purposes or as a proof-of-concept, and it's easier to implement one cheap ray inverse transform than N shape forward transforms. (Plus, as has been mentioned, some intersection algorithms are much simpler if the object is in its canonical space.)


How to use shadow mapping and deferred rendering to create a large amount of lights? Ok so I am trying to understand how to combine these 2 techniques and I am failing.

The main goal is to reach the O(lights+fragments) complexity of deferred rendering, instead of O(lights*fragments) of naive/forward rendering.

This is how I am currently doing things:

Say we have n lights. Then we generate n shadow maps O(n)

Now we do one render pass to generate the normal, diffuse color, depth.... information in the geometry buffers.

Then we check for every fragment whether it is occluded in ALL lights. and shadow it if it is.

This has an O(Lights*Fragments) complexity, which is wrong, so how can you reach the ideal asymptotic complexity? What should you do?

Deferred rendering does not have an asymptic complexity of O(lights+fragments). It has a complexity of O(fragments+visibleFragments*lights).

What you are doing in deferred rendering is preventing having to calculate lighting for many fragments that cover the same screen pixel. Once you have found which ones are visible, all of those still have to calculate lighting from every light source.

This is faster than forward rendering on the premise that lighting calculations are heavier than geometry calculations and that most fragments are ocluded by other fragments.


List of triangles to minimum amount of convex polygons I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic.

The input mesh can be very complex and could contain several holes. The position of the vertices are not constrained to a grid.

The use case for this is the creation of multiple polygon shapes for the Box2D physics engine.

Additional information:

The result does not need to be deterministic.
The result does not need to be vertically striped.
As trichoplax noted, the right part of the picture does not resemble the minimal polygon count that can be achieved. It's just an example.
It's not necessary that it will find the absolute minimum of convex polygons. A fast algorithm is preferred over a "best solution" one.

If a edge corner is concave then it needs to border 2 of the output polygons.

So one algorithm would be to find all concave corners (including the ones in the holes) and making cuts starting from them to other concave corners. This will split the polygon in two or join 2 holes into 1 or connect a hole to the outside.

The cut from a concave corner should be constrained by the angle or it will create a new concave corner that then needs to be cut again.


Ray intersection with Sun positions throughout the year I need to highlight(colour) sun reflections(through the year) off a mirror surface. It was easy having one Sun like in the below image but how about if it is to determine if a ray hits the entire surface that represents sun positions throughout the year.
Update:
Suppose the house surfaces are all mirror, so that from specific angles the viewer might see the reflection of the sun off the house surfaces. this is easy to render an image that simulate this but how about rendering an image that shows the reflection of not just one Sun, in a specific day time, but all the Suns, one for every second throughout the year. It's not efficient to dump in all these Suns into model and intersect them for each surface point. So I need to check if a ray intersects the entire surface that represents the path of the sun throughout the year.

The function that calculates sun position in the sky takes as input
local latitude, longitude and local date time. The output is a vector
which is sun position:

Inversing the above means using the ray direction(sun position in the sky) and retrieving back the local date time. If the date time is valid then the ray must hit the sun path throughout the year.

Here is the inverse function of the above:

public DateTime GetLocalDatetime(double haSolar, double vaSolar)
{
    double latitude = Helper.ToRadian(Latitude);
    double longitude = Helper.ToRadian(Longitude);

    double zenithTheta = Helper.PiOver2 - vaSolar;

    double sinSolarDeclination = (Math.Cos(Math.PI - haSolar) * Math.Cos(latitude) * Math.Sin(zenithTheta)) + Math.Sin(latitude) * Math.Cos(zenithTheta);
    double solarDeclination = Math.Asin(sinSolarDeclination);

    double cosH = (Math.Sin(vaSolar) - Math.Sin(latitude) * sinSolarDeclination) / (Math.Cos(latitude) * Math.Cos(solarDeclination));
    if (Math.Abs(cosH) > 1) return DateTime.MinValue;

    double H = Math.Acos(cosH);
    if (haSolar < 0) H *= -1;

    double declratio = solarDeclination / Helper.ToRadian(23.45);
    if (Math.Abs(declratio) > 1) return DateTime.MinValue;

    double beta = Math.Asin(declratio);
    int n = (int)Math.Round(beta / Helper.ToRadian(360d / 365d) + 81d, 1);

    DateTime localtime = new DateTime(DateTime.Now.Year, 1, 1).AddDays(n - 1);
    DateTime solartime = new DateTime(localtime.Year, localtime.Month, localtime.Day, 12, 0, 0);
    solartime = solartime.AddMinutes(4 * Helper.ToDegree(H));

    double eot = 9.87 * Math.Sin(2d * beta) - 7.53 * Math.Cos(beta) - 1.5 * Math.Sin(beta);
    double deltatimezone = 4d * (longitude - (Timezone * 15d));
    return solartime.AddMinutes(-(eot + deltatimezone));
}

And the image where each band represent each month in the year:


Algorithm for adjusting the speed of a progress bar animation I am trying to figure out an algorithm for handling an otherwise simple animation. I have a progress bar that "ticks down" from a user specified amount of time to zero. I wanted a smooth animation, so I chose to update it in a timer class at approximately 24 frames-per-second. This works just fine.

The problem I am trying to figure out is how to speed up the animation at an arbitrary point in the animation cycle (the user will initiate it by pressing an "Update Now" type of button. So, say the timer/progress bar is running down from a 10 minute wait and they press "Update Now", I want the animation to "hurry up" and complete. This new rate would be as if the total wait time was 1 second. To put it another way, if the user waited half way though the normal timer even and pressed "Update Now", then there would only be a half-second left to animate. If they waited 75% of the time, then there would only be 250 ms left to animate, etc.

I have tried too many things to list and all have failed. Most notably, the progress bar jumps to a later time, and then finishes the animation--I can't get it to animate fast from the point where it has left off. I'm sure this is easy, I just can't quite grasp the correct algorithm.

Givens:

My timer is running at 24 frames-per-second for a smooth animation.
My current algorithm works by taking the countdown timer's initial value (in ms) and subtracting how much time has passed, also in ms, then calculating what percentage of time has passed for the progress bar.
One thing I tried of note, that does not work for me was to have a counter of how many frames I had to consume, and subtract a frame count every time my timer even entered. I then assumed I could increase the frame rate to simulate the faster time. This all failed miserably. I'm not sure why, but increasing the frame rate did not appear to do much on my computer--the speed increased, but not to the extent I wished for. Further, my timer is not reliable enough even when not doing the faster animation. It would gain approximately 1 second for every 10 seconds of original wait time. So, that method is off the table. If the user wanted to wait 60 seconds and didn't press "Update Now", then the timer would consistently run for approximately 70 seconds, a 120 seconds would become 140 seconds, etc. I'm doing this on an i7-6700 and the CPU is not strained (7-8% total), but something is causing the timer to be otherwise unreliable...

I'm sure the answer will turn out easy, but any help would be appreciated. I'm doing this in c#, but I am sure I can figure out any algorithm presented and translate it if needed.

You will need to persist the percent completed across frames and update it based on the time elapsed since last frame and the total time.

percentCompleted = 0;
totalTime = 10; //in seconds

void onUpdate(float deltaTime){
    percentCompleted += deltaTime/totalTime;
}

void hurryUp(){
    totalTime = 1;
}


Where do the coefficients in the Catmull-Clark subdivision algorithm come from? I'm learning about subdivision surface algorithms. The "Catmull-Clark" algorithm seems to be one of the most widely-used classical algorithms.

The introduction of new face points and edges is straightforward, but I'm confused by the following formula for modifying the locations of original points

$$ \frac{F + 2R + (n-3)P}{n} $$

where:

$P$ is the original point
$R$ is the average of all $n$ edges midpoints touching $P$
$F$ is the average of all $n$ face points touching $P$

I understand the result is a weighted average of three points $F$, $R$ and $P$, but where do the coefficients $1$, $2$, and $(n-3)$ come from? Why $2R$? Why not $2.01R$? Or $1R$ and $2F$?

All the introductions I've seen just present the formula without presenting a justification.

The derivation is presented in the original paper that introduced CC subdivisions as a generalisation of B-Spline patches: https://people.eecs.berkeley.edu/~sequin/CS284/PAPERS/CatmullClark_SDSurf.pdf


What's the difference between orthographic and perspective projection? I have been studying computer graphics, from the book Fundamentals of Computer Graphic (but the third edition), and I lastly read about projections. Though, I didn't exactly understand what's the difference between orthographic and perspective projection? Why do we need both of them, where are they used? I also would like to learn what is perspective transform that is applied before orthographic projection in perspective projection. Lastly, why do we need the viewport transformation? I mean we use view transformation if the camera/viewer is not looking at $-z$-direction, but what about the viewport?

Orthographic projections are parallel projections. Each line that is originally parallel will be parallel after this transformation. The orthographic projection can be represented by a affine transformation.

In contrast a perspective projection is not a parallel projection and originally parallel lines will no longer be parallel after this operation. Thus perspective projection can not be done by a affine transform.

Why would you need orthographic projections? It is useful for several artistic and technical reasons. Orthographic projections are used in CAD drawings and other technical documentations. One of the primary reasons is to verify that your part actually fits in the space that has been reserved for it on a floor plan for example. Orthographic projections are often chosen so that the dimensions are easy to measure. In many cases this is just a convenient way to represent a problem in a different basis so that coordinates are easier to figure out.

Image 1: A number of useful orthographic projections for same object (and projection rule). The last on on the right is a special case called isometric having the property that cardinal axe directions are all in same scale.

A perspective projection is needed to be able to do 2 and 3 point perspectives, which is how we experience the world. A specific perspective projection can be decomposed as being a combination of a orthographic projection and a perspective divide.

Image 2: 2 point perspective note how the lines in prespective direction no longer are parallel

Viewport transformation allows you to pan/rotate/scale the resulting projection. Maybe because you want a off center projection like in cameras with film offset, or you have a anisotropic medium for example. It can also be convenient for the end user to zoom into image without changing the perspective in the process.


Overlaying a grid on to a height map What is the method used in overlaying a grid (agonostic of the grid type) on to a height map? It seems it's some sort of projection, but what are the technical details in how to implement it?

An example here is a hexagon grid overlayed onto the map in Civ5 that nicely handles spatial distance regardless of how high the height map is at a position -

Deferred decals are a common way to achieve this without re-rendering the same geometry. It also allows you to change the appearance, i.e. add some gap or smooth out the details.

The algorithm:

Draw a box around your height field, the size should be as tight as possible to avoid over draw.
sample the depth buffer to get the world-space position of the current pixel (the height field / other geo)
Project your box down in world space
Use the projected box coordinate to sample from your overlay texture.


Why is Russian Roulette used in ray tracing? Why should we use Russian Roulette? Does it reduce ray tracing artifacts?

The most usual way of employing Russian roulette in path tracing is to cut paths with high attenuation (low throughput) without adding bias into the resulting estimator, which would occur if you just use constant maximum path length.

Although Russian roulette incorporates additional variance into the resulting estimator, it helps throwing away long paths consuming a lot of processing power while contributing little into the resulting image, possibly leading to increased performance of a renderer.


Does programs like After effects and Unity engine use graphics library to render custom guis? I was always interested how programs like: Unity, AE, godot engine and other render their custom guis. So my question is, do they use graphics library to render custom guis or something else. If they don't use graphics library, should I use it? Thanks :).

So:

All GUI are somehow graphics. They don't have to be accelerated by the GPU but these days most are. In the old times, they could be rendered on the CPU (X11 times).
You need to be careful between making a distinction between the frameworks/libraries that are potentially being used for building up UIs and what these libraries use to render the graphics making up these UIs.

A lot of applications like Maya for instance use libraries for creating their UIs (Maya uses Qt so as most products developed by the Foundry: Nuke, Marri, etc.) which is why a lot of these applications look the same ... (sadly).

Qt and most UI library/framework use a graphics API to accelerate the rendering of widgets.

Some applications like Unity do not use "commercial" libraries like Qt. They develop their own, but in the end they also use the GPU to render their GUIs.


Trying to implement Microfacet BRDF but my result images are wrong I am trying to implement microfacet BRDF model. I am reading Sebastien Lagarde's slides. I implemented formulas to my code but i think result image is wrong.

Yellow is base color of material. Specular color is red to see properly.

My code:

// Fragment Shader
#version 330 core

in vec3 Position;
in vec2 TexCoord0;
in vec3 Normal;
in vec3 Tangent;
out vec4 FinalColor;

uniform vec3 uCameraPosition; // init value: vec3(0, 0, 5)

#define PI 3.1415926f
#define EPSILON 10e-5f
#define saturate(value) clamp(value, 0.0f, 1.0f);

float BRDF_Lambert(float NdotL)
{
    return NdotL;
}

// Got these BRDF formulas Moving Frostbite to PBR slide by Sebastien Lagarde & Charles de Rousiers
// http://www.frostbite.com/wp-content/uploads/2014/11/course_notes_moving_frostbite_to_pbr_v2.pdf
float BRDF_D_GGX(float NdotH, float Roughness)
{
    float Roughness2 = Roughness * Roughness;
    float f = (NdotH * Roughness2 - NdotH) * NdotH + 1.0f;
    return Roughness2 / (f * f + EPSILON);
}

float BRDF_F_FresnelSchlick(float LdotH, float F0)
{
    float f = F0 + (1.0f - F0) * pow((1.0f - LdotH), 5);
    return f;
}

float BRDF_G_SmithGGXCorrelated(float NdotL, float NdotV, float Roughness)
{
    float Roughness2 = Roughness * Roughness;
    float GV = NdotL * sqrt((-NdotV * Roughness2 + NdotV) * NdotV + Roughness2);
    float GL = NdotV * sqrt((-NdotL * Roughness2 + NdotL) * NdotL + Roughness2);

    return 0.5f / (GV + GL + EPSILON);
}

float BRDF_Specular(float NdotV, float NdotL, float NdotH, float LdotH, float Roughness, float F0)
{
    float D = BRDF_D_GGX(NdotH, Roughness);
    float F = BRDF_F_FresnelSchlick(LdotH, F0);
    float G = BRDF_G_SmithGGXCorrelated(NdotL, NdotV, Roughness);
    return (D * F * G) / PI;
}

void main()
{
    FinalColor = vec4(1.0f, 1.0f, 1.0f, 1.0f);
    vec4 BaseColor = vec4(1.0f, 1.0f, 0.0f, 1.0f);
    vec4 SpecularColor = vec4(1.0f, 0.0f, 0.0f, 1.0f);
    vec3 LightDirection = normalize(vec3(0, 4, 4));
    vec3 ViewDirection = normalize(Position - uCameraPosition);
    vec3 HalfVector = normalize(ViewDirection + LightDirection);
    float Roughness = 0.9f; // [0.04 - 0.1f] -> Dielectric, [0.7, 1.0f] -> Metallic

    float RefractiveIndex = 0.27049f; // RI for Gold materials. I got this from http://refractiveindex.info/
    float F0 = pow(((1.0f - RefractiveIndex) / (1.0f + RefractiveIndex)), 2);

    float NdotL = saturate(dot(LightDirection, Normal));
    float NdotV = abs(dot(ViewDirection, Normal)) + EPSILON; // Avoid artifact - Ref: SIGGRAPH14 - Moving Frosbite to PBR
    float LdotH = saturate(dot(LightDirection, HalfVector));
    float NdotH = saturate(dot(Normal, HalfVector));

    float DiffuseFactor = BRDF_Lambert(NdotL);
    float SpecularFactor = BRDF_Specular(NdotV, NdotL, NdotH, LdotH, Roughness, F0);

    FinalColor = BaseColor * DiffuseFactor + SpecularColor * SpecularFactor;
}

EDIT

Roughness = 0.2f;

Roughness = 0.04f;

Problem fixed by RichieSams, trichoplax and xpicox. Thanks all of you for the answers.

I lower the roughness, change the color of material and reversed the ViewDirection then finally I start to see proper specular :).

Fixed Code:

#version 330 core

in vec3 Position;
in vec2 TexCoord0;
in vec3 Normal;
in vec3 Tangent;
out vec4 FinalColor;

uniform vec3 uCameraPosition;

#define PI 3.1415926f
#define EPSILON 10e-5f
#define saturate(value) clamp(value, 0.0f, 1.0f);

float BRDF_Lambert(float NdotL)
{
    return NdotL;
}

// Got these BRDF formulas Moving Frostbite to PBR slide by Sebastien Lagarde & Charles de Rousiers
// http://www.frostbite.com/wp-content/uploads/2014/11/course_notes_moving_frostbite_to_pbr_v2.pdf
float BRDF_D_GGX(float NdotH, float Roughness)
{
    float Roughness2 = Roughness * Roughness;
    float f = (NdotH * Roughness2 - NdotH) * NdotH + 1.0f;
    return Roughness2 / (f * f + EPSILON);
}

float BRDF_F_FresnelSchlick(float LdotH, float F0)
{
    float f = F0 + (1.0f - F0) * pow((1.0f - LdotH), 5);
    return f;
}

float BRDF_G_SmithGGXCorrelated(float NdotL, float NdotV, float Roughness)
{
    float Roughness2 = Roughness * Roughness;
    float GV = NdotL * sqrt((-NdotV * Roughness2 + NdotV) * NdotV + Roughness2);
    float GL = NdotV * sqrt((-NdotL * Roughness2 + NdotL) * NdotL + Roughness2);

    return 0.5f / (GV + GL + EPSILON);
}

float BRDF_Specular(float NdotV, float NdotL, float NdotH, float LdotH, float Roughness, float F0)
{
    float D = BRDF_D_GGX(NdotH, Roughness);
    float F = BRDF_F_FresnelSchlick(LdotH, F0);
    float G = BRDF_G_SmithGGXCorrelated(NdotL, NdotV, Roughness);
    return (D * F * G) / PI;
}

void main()
{
    vec3 normal = normalize(Normal);

    vec4 BaseColor = vec4(1.0f, 0.0f, 0.0f, 1.0f);
    vec4 SpecularColor = vec4(1.0f, 1.0f, 1.0f, 1.0f);

    vec3 LightDirection = normalize(vec3(0, 4, 4) - Position);
    vec3 ViewDirection = normalize(uCameraPosition - Position);
    vec3 HalfVector = normalize(ViewDirection + LightDirection);
    float Roughness = 0.04f;

    float RefractiveIndex = 0.24f; // RI for Gold materials. I got this from http://refractiveindex.info/
    float F0 = pow(((1.0f - RefractiveIndex) / (1.0f + RefractiveIndex)), 2);

    float NdotL = saturate(dot(LightDirection, normal));
    float NdotV = abs(dot(ViewDirection, normal)) + EPSILON; // Avoid artifact - Ref: SIGGRAPH14 - Moving Frosbite to PBR
    float LdotH = saturate(dot(LightDirection, HalfVector));
    float NdotH = saturate(dot(normal, HalfVector));

    float DiffuseFactor = BRDF_Lambert(NdotL);
    float SpecularFactor = 0.0f;
    if(DiffuseFactor > 0.0f)
    {
        SpecularFactor = BRDF_Specular(NdotV, NdotL, NdotH, LdotH, Roughness, F0);
    }
    FinalColor = BaseColor * DiffuseFactor + SpecularColor * SpecularFactor;
}

Final Image:


If the OS uses a frame-buffer with potentially different textures being displayed each frame why dont we? At least on iOS every frame you are likely to get a completely new texture that you need to draw to due to the OS switching between a couple textures each frame.

My question is essentially if the OS feels the need to use multiple textures should we also be using multiple textures for some reason when doing full screen post processing? Is there ever a time where switching between off screen textures can improve performance?

The compositor in the OS wants to run at a consistent 60 FPS whatever rate your application runs at. If there were a single framebuffer for your application, then you might end up writing to it at the same time the compositor or overlay hardware wants to read from it to put it into the final frame. This would cause tearing. (Tearing could be avoided with a lock, but then the compositor might get stuck waiting for your frame to finish, which would also stop the user using the system GUI to get out of your slow/hanging app.)

This is pretty much the same reason double buffering is used when you're drawing to a monitor directly, just earlier in the pipeline.

This doesn't usually apply for processing within your application, because generally everything has to run at the same rate, and you can't run multiple stages in parallel. Say you draw some 3D stuff and then use a full-screen fragment shader to add some film grain and vignetting. It doesn't help if your full-screen shader can run faster than the 3D work, because you'll just be processing the same intermediate frames again.

I can think of two situations really where it might help. The first is if it's not a post-process but something different, such as if you have a GUI or HUD that you want to run at full frame-rate even if you get frame drops in the main content. (This is the case the OS's window compositor falls into.)

The second is if you can run the multiple stages of your processing pipeline in parallel, e.g. on multiple GPUs. That way, you can start rendering the next 3D frame while the full-screen shader is vignetting your previous frame. You'd have to know your hardware pretty well to split the work appropriately. On something like a gaming PC or graphics workstation that's using SLI to use multiple GPUs, you might find your parallel processing is slower because the workload is unbalanced and one GPU is idling a lot.


How's this laser cutting effect with backlight achieved? Sorry for the general question, I don't even know how to tag it:
https://www.youtube.com/watch?v=61UkkpsASwQ

In this video, the effect is such as if there were a laser cutting a shape with a light source behind it, and then the cut is closed again (like some trail effect).
How is this made and with which kind of software/programming? Is 3D involved here or can this be achieved with procedural 2D programming and shaders?

This question may be off-topic here, but this is almost certainly a 2D effect, and it's achievable without much difficulty in After Effects or any similar package once you've broken the effect down into individual elements.
This isn't exactly the same effect, but it gives most of the ideas: https://www.youtube.com/watch?v=uHFmWu__Q4k
The key point here is that you need to look not at the effect as a whole, but break it down into the individual elements that make it up. The parts make the whole.


How to map square texture to triangle? I want to find the texture coordinates for point P. I have the vertices of the triangle and their corresponding uv coordinates.

The numbers in the little squares in the texture represent color values.

What are the steps of computing the uv coordinates of P?

This is achieved via Barycentric Interpolation.

First, we find the barycentric coordinates of $P$. Barycentric coordinates represent how much weight each vertex contributes to the point, and can be used to interpolate any value which is known at the vertices across the face of a triangle.

Consider the 3 inner triangles $ABP$, $PBC$ and $PCA$.

We can say that the barycentric coordinate, or weight of the vertex $A$ on the point $P$ is proportional to the ratio of the area of inner triangle $PBC$ to the area of the whole triangle $ABC$.

This is intuitively evident if we consider that as $P$ approaches $A$ the triangle $PBC$ grows larger and the other two become smaller.

Also intuitively evident should be that the sum of the barycentric coordinates of a point inside a triangle always equals $1$. So, it is enough to find only two of the coordinates to derive the 3rd.

The method for computing the barycentric coordinates is:

$$\begin{aligned}
{Bary}_A &= \frac{(B_y-C_y)(P_x-C_x) + (C_x-B_x)(P_y-C_y)}{(B_y-C_y)(A_x-C_x) + (C_x-B_x)(A_y-C_y)}\\
{Bary}_B &= \frac{(C_y-A_y)(P_x-C_x) + (A_x-C_x)(P_y-C_y)}{(B_y-C_y)(A_x-C_x) + (C_x-B_x)(A_y-C_y)}\\
{Bary}_C &= 1 - {Bary}_A - {Bary}_B
\end{aligned}$$

The derivation and reasoning is explained in the wikipedia article.

Once you have coordinates, you can determine the texture coordinates of $P$ by interpolating the values at the vertices using the barycentric coordinates as weights:

$$P_{uv} = {Bary}_A \cdot A_{uv} + {Bary}_B \cdot B_{uv} + {Bary}_C \cdot C_{uv}$$

The reasoning is also explained very nicely in this presentation.

Also see this question for efficient methods of computation.


Is there a general way how to specify the "image compression loss"? For JPG, i can choose the "quality" from 100 to 0, which means that any pixel information is divided by 1 (quality = 100) or a very high number (quality = 0).
This results in less or more "artifacts", which are regions of the same color. The sizes of that regions depend on the image content and the selected "quality level".
But there are other compression formats using other algorithms. The common characteristic is that the resulting image has less information than the original uncompressed data.

Is there any way to specify those losses independently from both the used file format and the image content?

First off, it's worth noting that not all artefacts are regions of the same colour. Artefacts just means structured errors introduced by the compression, as opposed to noise or blurring. JPEG artefacts include flattened colours as you mention, but also edges introduced at block boundaries, and "ringing" around sharp edges in the image.

There are two popular metrics for specifying the losses, but they're not independent of the image content, and they measure the whole loss, not just structured artefacts. PSNR is most commonly used to quantify the loss of image and video compression algorithms. It's not a very useful measure, because it measures the absolute reconstruction error: it doesn't take into account what kind of artefacts are introduced and how they appear. Structural similarity (SSIM) is better because it takes the structure of the image and the errors into account in the measure.

The measure can't be independent of the image, for several reasons. Different images are easier or harder to reconstruct. For example, a completely flat colour will be perfectly reconstructed even with some very lossy algorithms and parameters. At the opposite end, completely random white noise will suffer some loss in almost any algorithm. Some images just contain more information than others. In addition, different domains have different requirements, so algorithms can be tuned for different kinds of images. JPEG is tuned for photographs, and performs badly on hard-edged synthetic images like diagrams. A texture compression algorithm might be tuned specifically to avoid block artefacts for tileable textures. JBIG2 is tuned for black-and-white document scans. A single generic measure wouldn't help you to understand the performance of the algorithm on the kind of image you're interested in.

To get a broader measure, it's common for researchers to quote a mean PSNR and/or SSIM measured across a corpus of images. The Kodak PCD0992 corpus has been used for many years, so it's an easy way to compare different papers, but it is waning in popularity now.


How can I concentrate points in areas of higher curvature? How can I distribute points over an implicit surface, to concentrate them more densely in areas of higher curvature?

I've considered adding points randomly and rejecting points not required based on the curvature, but I'd like to know if there is a better approach giving a more even distribution over areas of similar curvature, while still giving the higher density required in high curvature regions.

I'm looking specifically at using these points for a triangulation of the surface, and I don't want to create more triangles than I need for relatively flat parts.

This will be applied to shapes with a known derivative so the curvature at a given point can be calculated.

This does not need to be a real-time approach.

The idea I would try to apply would be the following: I make the example for the curve, but it should be straightforward for the application for the surface.

Let's say we have a curve $\gamma$ uniformly parametrized. Let's say the parameter of the curve is $s$. Your goal is to sample point corresponding to value of $s$ such that the curvature is high.

If you get the magnitude of the curvature $c$, this will be function of $s$ too. So, if you normalize the function $|c|$, you will get a probability distribution. If you get the integral of such distribution, you will have the cumulative distribution. Let's call this cumulative function $C(s)$.

The sampling problem from a distribution given by the cumulative function is well known, so basically once you have sampled a set of value $s_0,s_1,\dots,s_n$, such value will be related to the points of interest.

The application of this method to the case of surface should be straight, since basically you have a two dimensional cumulative distribution function, but the sampling problem is exactly the same.

Just to give some detail, it is basically sampling from a distribution given the cumulative function involves two steps:

take a random value in the interval $[0,1]$, let's say $k$
solve the equation $C(s) = k$.

This approach is exact, of course it is expensive, but if you like such approach you can work on optimization.


How to generate the stereographic projection of a 3D model Given a 3D model, is there a way to stereographically project it to a 2D image? In particular, I would only need a little more than half the model (the lower half) to be mapped to the plane (mapping the whole 3D model would be impossible, since the stereographic projection is infinite).

I am using Linux, if that makes any difference. Also, I would prefer to use free software.

(Note: If I could increase the viewing angle, I could do this with most any 3D viewing software, since the stereographic projection is just the view from a certain point with a wide viewing angle. In particular, I was able to get a small portion of the stereographic projection from meshlab.)

If instead of stereographic projection you can use other conformal projection. I would recommend you the "Least Squares Conformal Maps" algorithm. There are several implementations out there, including the prominent CGAL (https://doc.cgal.org/latest/Surface_mesh_parameterization/index.html).


How is that possible that matrices can be thought as coordinate systems? I've been reading around that matrices (for example, rotation matrices, but not only) can be thought somehow as coordinate systems.

My question is: how is that possible?

I've seen for example that if we're using row-major conventions, the rows of the matrices involved in the transformations (specifically I've seen about rotations) can be thought as the vectors representing some coordinate system (specifically it should be a local coordinate system).

Why is this the case? And why specifically a local coordinate system? What does it even mean local coordinate system in this context? Are there any other type of matrices, apart from the rotation matrices, which can be thought as coordinate systems? If yes, which ones, and why?

Matrices usually represent a transformation (linear or not, maybe also affine in computer graphics), but it's new to me to think about matrices as coordinate systems.

If you have a 3x3 matrix representing some transformation, you will actually have the X,Y,Z vectors of that transformation in the rows or columns (depending on if it's a row major or column major matrix).

In other words, if you have a 3x3, you can look at it and immediately get the up, right(*), forward vectors (asterisk due to handedness, it could be the left vector).

3x3 Details:

let's say you have a 3x3 matrix $M$:

$
M_{ij} =
\begin{bmatrix}
M_{1,1} & M_{1,2} & M_{1,3} \\
M_{2,1} & M_{2,2} & M_{2,3} \\
M_{3,1} & M_{3,2} & M_{3,3} \\
\end{bmatrix}
$

Let's see what happens when you multiply that by a vector $\begin{bmatrix}1,0,0 \end{bmatrix}$:

$
\begin{bmatrix}
M_{1,1} & M_{1,2} & M_{1,3} \\
M_{2,1} & M_{2,2} & M_{2,3} \\
M_{3,1} & M_{3,2} & M_{3,3} \\
\end{bmatrix}
*
\begin{bmatrix}
1 \\
0 \\
0 \\
\end{bmatrix}
=
\begin{bmatrix}
M_{1,1} \\
M_{2,1} \\
M_{3,1} \\
\end{bmatrix}
$

Now let's try vector $\begin{bmatrix}0,1,0\end{bmatrix}$:

$
\begin{bmatrix}
M_{1,1} & M_{1,2} & M_{1,3} \\
M_{2,1} & M_{2,2} & M_{2,3} \\
M_{3,1} & M_{3,2} & M_{3,3} \\
\end{bmatrix}
*
\begin{bmatrix}
0 \\
1 \\
0 \\
\end{bmatrix}
=
\begin{bmatrix}
M_{1,2} \\
M_{2,2} \\
M_{3,2} \\
\end{bmatrix}
$

And lastly, vector $\begin{bmatrix}0,0,1\end{bmatrix}$:

$
\begin{bmatrix}
M_{1,1} & M_{1,2} & M_{1,3} \\
M_{2,1} & M_{2,2} & M_{2,3} \\
M_{3,1} & M_{3,2} & M_{3,3} \\
\end{bmatrix}
*
\begin{bmatrix}
0 \\
0 \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
M_{1,3} \\
M_{2,3} \\
M_{3,3} \\
\end{bmatrix}
$

This shows that whatever matrix $M$ is, the first column is the X axis vector of the coordinate space defined by the matrix.  The second column is the Y axis vector, and the third column is the Z axis vector.

These vectors are in global space.

$
M =
\begin{bmatrix}
X_x & Y_x & Z_x \\
X_y & Y_y & Z_y \\
X_z & Y_z & Z_z \\
\end{bmatrix}
$

You can even see that this is true in an identity matrix, where the X,Y and Z vectors are just what you'd expect them to be:

$
M =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
$

A 3x3 matrix is much like a vector in that it describes directions but has no position.

If you have a 4x4 matrix that represents a 3d transform and uses homogeneous coordinates for a translation, you can then use that to get the X,Y,Z orientation vectors, but also can get the translation from the origin.

Hopefully this is helpful, and not misleading for less common matrix types.  I saw an answer deleted which said similar, so fingers crossed :P


How RGB images are formed I have a noob level question about RGB images-
Pixels in RGB images are in the range of (0-255), so technically each channel ranges from 0(black) to 1(white), then why we say that each image has a Red, Green, Blue channel component, although they are only Gray channel. In short, how the image is formed?

Each channel ranges not from black to white, but from off to full intensity. What colour is meant by full intensity is down to convention and the presentation technology.

For example, a given image file format might say there are three bytes, of which the first is the red channel, the second is the green channel, and the third is the blue channel. There are many different colours, so to be a real standard, it has to say exactly what that "red" means, usually by reference to a particular colour standard such as sRGB or CIELAB. These international standards provide an absolute way to describe colours.

After some processing, your red, green, and blue values find their way to your LCD monitor. There, the electronics uses them to control the intensity of three sub-pixels: one of which is a red filter, one a green filter, and one a blue filter. The 0-255 value in the red channel is turned into some voltage which controls the transparency of the liquid crystal behind the red filter, turning it from completely opaque at 0 to lets all light through at 255. Since this is attached to a red filter, it contributes black or red to the image.

The same idea is everywhere in computers. The only things inside a computer are numbers. They only mean what we say they mean because of conventions (all software interprets them the same way) and/or because they control some values inside some output hardware. e.g. one number means the red channel in a pixel on your screen, another number means a letter of the alphabet in an email, another number is a pressure sample in an audio file which will be sent to your sound card and control the voltage to a speaker, and so on.


Do operating programs such as Microsoft Office or Windows Explorer use OpenGL to draw? I have a server and my only monitor is plugged into its graphics card.

My question is - do all programs (Windows explorer, Excel whatever) draw their output using the graphics card and more specifically an API such as OpenGL?

The output is coming from the graphics card so I do not see how it could not be but it seems like that would require anyone who is using a server to have a GPU to any visual output.

In general, no. Most applications, unless they are games, or 3D applications like CAD or animation software, will use OS APIs to do their drawing. On Windows, this can be things like GDI or GDI+. On macOS you would usually use CoreGraphics or one of its derivatives.

At a lower level than the application level, the operating system talks to the graphics driver to tell  it to draw things on the screen. They may do so using OpenGL or a proprietary API that's not usually exposed directly to applications. (For example on older macOS versions, the Window Server used OpenGL directly to do its compositing. I believe it uses Metal now.) Additionally, some drawing may not be done by the graphics card at all, but the results may be sent to the graphics card for display. For example, the original Windows GDI did its drawing using the CPU, as hardware accelerated graphics were not included on every machine.

So really, there are a variety of ways for applications to do their drawing. They rarely use OpenGL, DirectX, etc. directly unless they have heavy graphics requirements. However, under the hood, the OS may be using those technologies or something similar, or something even lower-level.


What tris and quads need for? I know that 3D artists make a 3D model with quads. And they advise to remesh with quads only (if it's possible).

So I have some questions:

Why do we use quads in CG (for games, cartoons, film, etc) if the graphic card (or render, I'm not sure) convert quads to tris all the same?
Why many 3D apps (Max, Blender, Maya, etc) have a triangulate function? Eventually, the graphic card (or render) does that.

I want to clarify this question for myself since I know it incompletely.

Because the geometry will be subdivided into quads. Anyway the primary reason for this is if you have a function with 2 directions it is easer for humans to think it out andcanticipate results if its a quad.

Software renderers dont have to rely on triangles. And did not for a long time. But then if you microdice your surface who cares its not like you can see the micropolygon anyway.

For more on this read this post
You might want to control the triangulation yourself. Interpolation does not happen the same way regardless of how the triangles are laid out. So being able to triangulate and then flip offending triangles is useful.


What kind of image processing was used in the Facebook "Celebrate Pride" filter? I am trying to recreate a filter that Facebook released back in 2015 when gay marriage was legalized in the US.

Unfortunately, that filter no longer works/exists so people are left with only knockoff ones that dont do quite as good as a job. None of them manage to do quite what the actual one did espeically in the red, yellow, and purple stripes.

I am trying to figure out what kind of filter they used to achieve this.

I have tried a bunch of colors with each of the blend modes available in my photo editing software with no luck. Perhaps it is more complicated than just one math equation? Perhaps they processed the background image before putting on the overlay?

I did find in the blog that the algorithm to achieve this was a O(n^2) algorithm but that is about all I know.

Any ideas of what could have caused this?

Below are some reference photos I used to attempt to find a pattern.

Example 1: Mark Zuckerburg (note this isn't exact. I couldn't perfectly recreate the crop they used)

Example 2: Facebook logo with colors pulled out on the right

The top Zuckerberg image looks like you first convert your background Zuckerberg image to grayscale. Then you can add a second layer with the rainbow texture but use the 'Screen' blending mode, this will cause it to colourise the layers beneath it, but in such a way the whites are preserved. You could also try 'Multiply' mode too if the results are too bright.

The second one with the facebook logo looks like alpha blending. This can be done using a default layer in photoshop but setting the layer opacity to some midway value, i'd guess around 75% opacity. In this version the rainbow texture is the background, and the layer contains the 'F' logo.


Do you need to use a lowpass filter before downsizing an image? Apparently bicubic pixel interpolation is good for scaling up or down an image (in real time or not).

Is it recommended to use a lowpass filter before downsizing though, or does the bicubic sampling handle aliasing problems at all?

If the downsampling pass is properly designed, it will effectively perform low-pass filtering as part of the downsampling.  There is no need for a separate low-pass filter operation.

Essentially, when you downsample, you are performing a filter over the source (high-res) image pixels, but only evaluating it at the locations of the destination (low-res) pixels.  The footprint of this filter needs to be approximately the spacing between destination pixels, to avoid missing information by skipping over in-between source pixels.  But that means the filter footprint will be several source pixels wide, so it will effectively low-pass the source.

For example, let's suppose you downsample an image by exactly 10x on each axis.  With a box filter (for example's sake), you would set each destination pixel to the average of a 10x10 box of source pixels.  That would wipe out any features smaller than 10px, so it's effectively a low-pass filter.

You mention bicubic interpolation; we have to make a distinction between filtering and interpolation here.  Interpolation is appropriate for upsampling, not downsampling.  Bicubic interpolation works by fitting a bicubic spline patch to a 4x4 neighborhood of pixels, then evaluating the patch at interpolated points. While it may work well enough for downsampling images by a small factor (up to 2x or so), it will fail if you go much further than that.  For instance, if downsampling by 10x as in the previous example, you can see that bicubic will miss the majority of the source pixels, and the result may be quite aliased.

On the other hand, bicubic filtering is just standard filtering, using a kernel that's a bicubic function (as opposed to a box, triangle, Gaussian, Lanczos, etc. kernel).  The Mitchell-Netravali kernel is the classic example of this type.  If used for downsampling, the kernel should be sized appropriately for the destination pixel spacing as discussed earlier, and you would sum over all the pixels in the footprint, not just a 4x4 or other fixed-size neighborhood.


Graphics engines during the sixth console generation From my understanding game developers used mostly proprietary, in-house graphics engines during the sixth console generation (Xbox, PS2, GC, DC) on a game to game basis. Why didn't standard engines like Unreal (for consoles), Unity etc. emerge earlier?
Wasn't it very inefficient to develop a new engine just for one (or probably a few) games?

Bonus question: Are there any good ressources on graphics development during that time? I'm especially interested in articles about the effort needed to develop an engine for any of the mentioned consoles.

Renderware was common on the PS2.

List of PS2 Renderware titles

I would guess because these platforms were proprietary and none-standard from a graphics and resources POV that it would be a bigger effort to port Unreal along with all their existing content creation tools.


How is measured BRDF data recorded? How is measured BRDF data recorded? Like the MERL BRDF Database.

What kind of equipment is used and what are the key values that need to be recorded?

I know one place this data was used was in the Disney PBR paper.

Section 6 of Microfacet Models for Refraction through Rough Surfaces has a good description of how they did it to validate their own model. That may not be everything needed to build a full database (eg. more automation) but it's an interesting read.


Make a texture a clickable Button What would be the best way to make a texture a clickable button? Suppose I have a Room (respresented by a 2D texture), where there are buttons.

Would I in the main loop:

check when the mouse is clicked if it is in any region of a button? ($\mathcal{O}(n_{Button})$)
Do something entirely different that I can't think of?

I may be overthinking this, maybe this isn't a problem at all, but somehow, what I came up with sounds way to "stupid" to me to be the right solution. It sounds like a hack to me, but maybe this is the way to do it? In 3D Games, would the check than be just radial coordinates ($r,\phi,\theta$)?

In games and other 3D scenes, generally when the user clicks the mouse, a ray is cast into the scene in the direction the camera is facing, and a check is done to see what geometry in the scene it intersects. If it intersects nothing, it is ignored. If it intersects a single object, then the application processes a click on that object (at the location of the intersection). If more than one object is intersected, then usually the front-most object is assumed to be the on the user wanted to click on, so that is processed.

In general, geometry is stored using x,y,z coordinates rather than spherical coordinates, as the GPU hardware works in cartesian coordinates.


Creating an "ink spread" effect with a glsl fragment shader I have dealt with glsl before, but I still have problems with my understanding of how to achieve certain kinds of effects with per-pixel processing. What I am looking to do is use a fragment shader to emulate ink spreading across paper. Simply put, I want to emulate a large drop of ink being dropped on paper, with the ink spreading out from the source, perhaps with some capillary effect. Instead of one drop, this will apply to an entire image.

Ive done some brainstorming for the implementation. There is a random initial "mass" applied to each pixel, and one method I'm considering is having the texture scale outwards with the value of the initial "mass" decreasing until 0.

What might I be missing in trying to implement this? Does anyone know of a similar shader effect that I could consult while building this?

If you want to implement this with GLSL, the general concept that could be applied is multi-pass rendering. In a first render pass, draw some ink on the screen and write the result in a frame buffer object (FBO). Then in the second render pass, draw a screen-size quad and attach the texture of the FBO. In this second render pass you could use a GLSL shader that distributes the ink. In the example below I used a simple Erode and a Gauss filter but more complicated effects are possible here. The result is then used as the background for the first render pass that draws more ink, which is passed on to the second render pass, and so on...

I have generated the example above with an online tool called "GSN Composer", which uses GLSL shaders and WebGL. You find the corresponding node graph here:

https://www.gsn-lib.org/index.html#projectName=foruminkspread&graphName=erode

Currently, in this very simple implementation, the spreading of ink will never stop. To achieve this you would need to remember a per-pixel state (e.g. a "mass" or "reservoir", as you have mentioned in your question) and use this per-pixel state in the shader that performs the spreading. This state could be encoded in the texture output (e.g. in the alpha channel) or could be written into a second texture that is passed along the shader pipeline.


Is "generative art" the best term for describing graphical techniques like ASCII art or photo mosaics? I'm researching generative art using computers, and I'm looking to see if there's a more specific term for types of image manipulation techniques like ASCII art or photo mosaics that can narrow down my search. Basically it's anything that uses a real image as input and outputs something other than individual pixels from the image. Some examples would be  or this plotter print of a woman.

My sense is that "generative art" is a phrase that properly describes what these techniques do. However, there are other generative art techniques that don't rely on images for input and have a more abstract art look to them when final images come out, so I feel like the term is more broad than the techniques I'm describing.

Generative art (Wikipedia) doesn't necessarily start with an image as the input, and ASCII art can be drawn/typed by hand (in a text editor) especially for ASCII line art (which I've often used for diagrams) or "oldskool" ASCII art.

While there may be overlap, generative art is neither a synonym nor a hypernym for ASCII art.  Note that your pen-plotter example is different again in that the computer-controlled physical output (e.g. choice of pen or even brush on similar devices) is a crucial part of the process but a human is likely to do a fair bit of image manipulation first.  ASCII art and photo-mosaics are essentially the same on screen or printed.

Sticking with Wikipedia, algorithmic art seems closer, if you exclude hand-typed ASCII art, but this still doesn't fit the robotic drawing of your second example (not robotic art, which is art consisting of robots rather than made by robots).

What you're looking for is actually quite broad, and computer art may be as close as you're going to get, though computer art includes things like this:

 (example borrowed from a previous answer of mine)


How do correlated samples influence the behavior of a Monte Carlo renderer? Most descriptions of Monte Carlo rendering methods, such as path tracing or bidirectional path tracing, assume that samples are generated independently; that is, a standard random number generator is used that generates a stream of independent, uniformly distributed numbers.

We know that samples that are not chosen independently can be beneficial in terms of noise. For example, stratified sampling and low-discrepancy sequences are two examples of correlated sampling schemes that almost always improve render times.

However, there are many cases where the impact of sample correlation is not as clear-cut. For example, Markov Chain Monte Carlo methods such as Metropolis Light Transport generate a stream of correlated samples using a Markov chain; many-light methods reuse a small set of light paths for many camera paths, creating many correlated shadow connections; even photon mapping gains its efficiency from reusing light paths across many pixels, also increasing sample correlation (although in a biased way).

All of these rendering methods can prove beneficial in certain scenes, but seem to make things worse in others. It's not clear how to quantify the quality of error introduced by these techniques, other than rendering a scene with different rendering algorithms and eyeballing whether one looks better than the other.

So the question is: How does sample correlation influence the variance and the convergence of a Monte Carlo estimator? Can we somehow mathematically quantify which kind of sample correlation is better than others? Are there any other considerations that could influence whether sample correlation is beneficial or detrimental (e.g. perceptual error, animation flicker)?

There is one important distinction to make.

Markov Chain Monte Carlo (such as Metropolis Light Transport) methods fully acknowledge the fact that they produce lots of highly correlated, it is actually the backbone of the algorithm.

On other hand there are algorithms as Bidirectional Path Tracing, Many Light Method, Photon Mapping where the crucial role plays Multiple Importance Sampling and its balance heuristics. Optimality of balance heuristic is proven only for samples that are independent. Many modern algorithms have correlated samples and for some of them this causes troubles and for some it doesn't.

The problem with correlated samples was acknowledged in the paper Probabilistic Connections for Bidirectional Path Tracing. Where they have altered balance heuristics to take into account the correlation. Have a look at figure 17 in the paper to see the result.

I would like to point out that correlation is "always" bad. If you can afford to make brand new sample than do it. But most of the time you can't afford it so you hope that the error due to the correlation is small.

Edit to explain the "always": I mean this in the context of MC integration

Where you measure the error with variance of the estimator

If the samples are independent that the covariance term is zero. Correlated samples make always this term nonzero thus increasing variance of the final estimator.

This is at first sight somewhat contradictory what we encounter with stratified sampling because stratification lowers the error. But you can't prove that stratified sampling converges to the desired result just from the probabilistic point of view, because in the core of stratified sampling there is no probability involved.

And the deal with stratified sampling is that it is basically not a Monte Carlo method. Stratified sampling comes from standard quadrature rules for numerical integration which works great for integrating smooth function in low dimensions. This is why it is used for handling direct illumination which is low dimensional problem, but its smoothness is disputable.

So stratified sampling is yet different kind of correlation than for example correlation in Many Light methods.


In a shader, how to store fragment coordinates in a spatial partitioning from one pass to the next? I have a post-effect camera-shader in which I want to implement a simple spatial partitioning of the screen between two passes of the fragment shader.

The first pass should divide the screen into cells of size = 30x30 pixels, and then for each green fragment, store somehow which of those screen cells the coordinate of such green fragment  is located. That information should then be available for the second pass to work with.

Well, merely dividing the screen into cells is trivial, considering that it's easy to calculate the row and column indexes of such screen-grid:

static float2 _Pixels = float2(_ScreenParams.x, _ScreenParams.y);
float2 griduv = round(input.uv * _Pixels) * _invPixels; //pixel-screen space coordinate of the current fragment being evaluated
half cellsize = 30.0f;

float gridX = griduv .x/cellsize;
float gridY = griduv .y/cellsize;

int gridrow = gridX  - frac(gridX);
int gridcol = gridY  - frac(gridY);

If that was not a shader task but rather a standard CPU code, it would be just a matter of saving the ith griduv into an array-of-list or array-of-array (e.g. float2[][] grid = new float2[gridrow*gridcol][maxNfloat2]) at position grid[gridrow*gridcol+gridrow][i].

However, in a shader, for most hardwares and most DirectX and OpenGL versions, it seems to me that 1) we can't have multi-dimensional arrays, 2) we can't have resizable containers like lists and 3) we also can't pass variables and containers from one pass to the next.

As one can easily see, this situation is also not well suited for using a simple texture to store values from one pass to the next, since I would need multiple float2 into each grid cell and I can have quite many floats to store.

So, how could I proceed in such a situation? In other words, how could I store the pixel-screen coordinates of given fragments in a spatial-partitioning of the screen (in this case a simple fixed size grid of the screen), to be passed from one shader pass to the next?

Though I have never used them myself OpenGL in modern versions gives you something called "Shader Storage Buffer Object" These are buffers that you can fill with your data. They are guaranteed to be able to hold up to 16 MB of data and most implementations seem to have no problem with them taking up the whole GRAM.

This feature is core since OpenGL version 4.3.
The SSBOs are basically just a buffer that you can put any datatype in (a struct for example) and a huge amount of them.

I cannot really tell you how to use them, but I think with the name you will find some resource in the web.


How to read illum value from mtl file using Assimp library? I am loading an OBJ file using the ASSIMP library. Following is the MTL file associated with the obj file.

newmtl initialShadingGroup
Kd 0.50 0.50 0.50
Ka 0.09 0.09 0.09
Tf 1.00 1.00 1.00
Ns 10.0
map_Ka sphere_roughness.jpg
map_Kd sphere_albedo.jpg
map_Ks sphere_metallic.jpg
bump sphere_normal.jpg
disp sphere_bump.jpg
illum 7

I want to read the illum value so that I can choose an appropriate sharding model in my shaders. The code I'm using is

int shadingModel;
material->Get(AI_MATKEY_SHADING_MODEL, shadingModel);
std::cout << "ShadingModel: " << shadingModel<< std::endl;

But the output I'm getting is

ShadingModel: 2

when the value is 7. Is there something that I'm doing it wrong or is it the wrong way to retrieve the shading model.
Thanks for your help!

According to the source (https://github.com/assimp/assimp/blob/b7df376836e36c4b6998ce95d97626e30f61c2f0/code/AssetLib/Obj/ObjFileImporter.cpp#L594) only illum values of 0, 1, 2 are supported:
    // convert illumination model
    int sm = 0;
    switch (pCurrentMaterial->illumination_model) {
    case 0:
        sm = aiShadingMode_NoShading;
        break;
    case 1:
        sm = aiShadingMode_Gouraud;
        break;
    case 2:
        sm = aiShadingMode_Phong;
        break;
    default:
        sm = aiShadingMode_Gouraud;
        ASSIMP_LOG_ERROR("OBJ: unexpected illumination model (0-2 recognized)");
    }


Passing Colour from program to vertex shader New to opengl! I am having issues with passing colours from the program to vertex shader.

I am creating a grid where I want to control the color of each cell.Thus I am generating each cell and having two vbo's, one for the vertices, and another for the colour. I want my grid to look like this:

But I end up with:

I have confirmed if I generate the colour data in the vertex shader and then pass it to the fragment, I get the first case. It is only when I grab the colour data from the program that I get the second case.

Code for creating each vbo(written in go):

var vbo [2]uint32
gl.GenBuffers(2, &vbo[0])
gl.BindBuffer(gl.ARRAY_BUFFER, vbo[0])
gl.BufferData(gl.ARRAY_BUFFER, 4*len(points), gl.Ptr(points), gl.STATIC_DRAW)
gl.BindBuffer(gl.ARRAY_BUFFER, vbo[1])
gl.BufferData(gl.ARRAY_BUFFER, 4*3, gl.Ptr([]float32{0.5,0.5,0.0}), gl.STATIC_DRAW)
var vao uint32
gl.GenVertexArrays(1, &vao)
gl.BindVertexArray(vao)
gl.EnableVertexAttribArray(0)
gl.BindBuffer(gl.ARRAY_BUFFER, vbo[0])
gl.VertexAttribPointer(0, 3, gl.FLOAT, false, 0, nil)

gl.EnableVertexAttribArray(1)
gl.BindBuffer(gl.ARRAY_BUFFER, vbo[1])
gl.VertexAttribPointer(1, 3, gl.FLOAT, false, 0, nil)

Vertex Shader:

#version 410
/*layout (location=0) */in vec3 vp;
/*layout (location=1)*/ in vec3 colour;
/*layout (location=2)*/  out vec3 outcolour;
void main(){
    gl_Position = vec4(vp,1.0);
    //outcolour = vec3(0.5,0.5,0.0);
    outcolour = vec3(colour);
}

Fragment Shader

#version 410
in vec3 outcolour;
out vec4 frag_colour;
void main(){
    frag_colour = vec4(outcolour,1.0);
}

I don't know what language that is, but I'm going to hazard a guess that the arrays points and gl.Ptr([]float32{0.5,0.5,0.0}) are not the same size. If you intend to provide per-vertex colors, then you must provide one color for every vertex. If you want to provide a single color that all vertices share, then that would be a uniform, not a vertex shader input.

Also, commenting out your layout declarations isn't helping. Though if you are going to declare a location for the VS output variable, then the matching FS input needs to have the same location declared.


Spring damping in Energy Function Supposing a behavior function $C(x_1, \ldots, x_n)$, then we have a scalar potential energy function

$E = \frac{k_s}{2}C\cdot C$ where $k_S$ is stiffness constant.

Hence, the force is as follows $f_i = -\frac{\partial E}{\partial x_i} = -k_sC\frac{\partial C}{\partial x_i}$

I caught up so far, but couldn't understand when adding damping.

The paper read $f_i = (-k_sC - k_d\dot{C})\frac{\partial C}{\partial x_i}$ , where $k_d$ is damping constant and $\dot{C}$ is derivative of $C$.

How to derive the damping part?

I know damping equation is $f_d = -k_dv$,

In detail, supposing there are two end of points in a spirng, called $p_a, p_b$.

then the damping force $f_d = -k_d\frac{\dot{l}\cdot l}{|l|}\frac{l}{|l|}$ in 3D sapce ($\dot{l}$ is $v_a - v_b$, $l = p_a - p_b$)

However, I could not correspond this equation to the above damping part.

The damping force you mentioned $f=-k \frac{\dot{l} \cdot l}{|l|} \frac{l}{|l|}$ is a special case of $f=-k \dot{C} \frac{\partial C}{\partial \mathbf{x}}$.

Let
$$
\begin{align}
C(\mathbf{x}) &= \lVert\mathbf{l}\rVert-l_0 \\
\mathbf{l} &= \mathbf{x}_1 - \mathbf{x}_2 \\
\mathbf{\dot{l}} &= \mathbf{v}_1 - \mathbf{v}_2 \\
\mathbf{v} &= \dot{\mathbf{x}} = \begin{pmatrix}\mathbf{v}_1 \\ \mathbf{v}_2\end{pmatrix}
\end{align}
$$
where $l_0$ is the rest length of the spring, and $\mathbf{x}_1$, $\mathbf{x}_2$ are the positions of two end points.
The damping force is
$$
\begin{align}
\mathbf{f} &= -k \dot{C} \frac{\partial C}{\partial \mathbf{x}} \\
&= -k (\frac{\partial C}{\partial \mathbf{x}})^T \dot{\mathbf{x}} \frac{\partial C}{\partial \mathbf{x}}\\
&= -k (\mathbf{l}^T\mathbf{l})^{-1/2} \mathbf{l}^T \begin{pmatrix}\mathbf{I}& -\mathbf{I} \end{pmatrix} \dot{\mathbf{x}} (\mathbf{l}^T\mathbf{l})^{-1/2} \begin{pmatrix}\mathbf{I}& -\mathbf{I} \end{pmatrix}^T \mathbf{l} \\
&= -k (\mathbf{l}^T\mathbf{l})^{-1} \begin{pmatrix}\mathbf{l}^T& -\mathbf{l}^T \end{pmatrix} \mathbf{v} \begin{pmatrix}\mathbf{l} \\ -\mathbf{l} \end{pmatrix}\\
&= -k \frac{(\mathbf{l}\cdot \mathbf{\dot{l}}) }{\lVert \mathbf{l} \rVert^2}
\begin{pmatrix}\mathbf{l} \\ -\mathbf{l} \end{pmatrix}
\end{align}
$$

This matches your damping force equation. The $-\mathbf{l}$ part is just the force for the other particle, which has the opposite direction as expected. Bold letters are used to denote vector quantities.

As mentioned in [baraff98], this damping force is along the direction $\frac{\partial C}{\partial \mathbf{x}}$,
and its magnitude is the projected component of velocity $\frac{\partial C}{\partial \mathbf{x}}^T \mathbf{v}=\frac{\partial C}{\partial \mathbf{x}}^T \mathbf{\dot{x}}=\dot{C}$.


basic of image dithering Is just read about image-dithering ? So I tried to implement that. Here is my result. Can someone verify it?

My code :

import numpy as np
from numpy.random import default_rng
import matplotlib.pyplot as plt

n = 300
real = np.random.randint(low = 0, high=256, size=(n,n), dtype='l')
#print(real)

dn = 3
rng = default_rng()
dither = rng.choice(dn*dn, size=(dn,dn), replace=False)
print(dither)

res = np.zeros((n,n))
for y in range (0,n):
    for x in range (0,n):
        i = x % dn
        j = y % dn
        res[x][y] = 255 if (real[x][y] > dither[i][j]) else 0
#print(res)

fig = plt.figure()

ax1 = plt.subplot(1, 3, 1)
ax1.title.set_text('Real Image(300x300)')
plt.imshow(real, cmap="gray")

ax2 = plt.subplot(1, 3, 2)
ax2.title.set_text('Dithering Matrix(3x3)')
plt.imshow(dither, cmap="gray")

ax3 = plt.subplot(1, 3, 3)
ax3.title.set_text('Resultant Image(300x300)')
plt.imshow(res, cmap="gray")

plt.show()

reduced value of  n to 6, so that image may become easily understandable.

Result :

There is a small issue in the original code. Indeed, real array values ranging between [0, 255]. However, the mask values ranging between [0, 3*3] (as dn = 3 in the example above).

After fixing the issue:

The correct code (with image reading and all data normalized between [0, 1.0]):

import numpy as np
from numpy.random import default_rng
import matplotlib.pyplot as plt
from PIL import Image

# Read an image from the disk
real = Image.open("example.jpeg")
real = np.array(real) / 255.0
# If it is a RGB image, transform it to a gray image
# TODO: Could use any function (like luminance)
real = (real[:,:,0] + real[:,:,1] + real[:,:,2]) / 3.0

# Create the mask by shuffling
dn = 6
rng = default_rng()
# In the original code, there was a problem here.
# Indeed, the mask values ranging between [0, dn*dn]
# So the generated mask needs to be properly normalized
dither = rng.choice(dn*dn, size=(dn,dn), replace=False) / float(dn*dn)
print(dither)

# Generate the results
res = np.zeros_like(real)
width, height = res.shape[1], res.shape[0]
for y in range (0,width):
    for x in range (0,height):
        i = x % dn
        j = y % dn
        res[x][y] = 1.0 if (real[x][y] > dither[i][j]) else 0.0

# Display the result
fig = plt.figure()
ax1 = plt.subplot(1, 3, 1)
ax1.title.set_text('Real Image(300x300)')
plt.imshow(real, cmap="gray")
ax2 = plt.subplot(1, 3, 2)
ax2.title.set_text('Dithering Matrix(3x3)')
plt.imshow(dither, cmap="gray")
ax3 = plt.subplot(1, 3, 3)
ax3.title.set_text('Resultant Image(300x300)')
plt.imshow(res, cmap="gray")
plt.show()


Defocus blur: Computing the pixel plane distance I'm following Peter Shirley book, Ray tracing in one weekend. In the last chapter, he talks about how to make defocus blur by using thin len approximation. His camera class accepts a parameter called focus_dist, which he then uses to compute the distance to the image plane.

lower_left_corner = origin  - half_width*focus_dist*u -half_height*focus_dist*v - focus_dist*w; // lower_left_corner of image plane

This subject was new to me, so I went searching around online. From what i understand, the distance to the image plane is governed by the equation 1/f = 1/d + 1/d prime with f being focal length and d being the focus distance. d prime will be the answer. The lack of this equation in Peter Shirley's code and the fact that he seems to be putting the image plane at the focus distance makes me completely lost. Can anyone explain it to me?

Here's the link to the code I talked about.
https://github.com/petershirley/raytracinginoneweekend/blob/master/camera.h

You don't need that equation.

You know your focus point (point on y-axis with focus_distance as z component) and the ray origin. All that needs to be done then is to compute the ray direction from the origin through that focus point.

For what it's worth, I think a camera space formulation of a thin lens makes it easier to understand the concept:

float fov = 2.0f * atan((sensorWidth / (2.0f * focal_length))); // in radians
float tan_fov = tanf(fov / 2.0f);

// create point on lens, screen space samples are in [-1, 1] domain
vec3 p(screen_space_sample_x * tan_fov, screen_space_sample_y * tan_fov, 1.0);

// calculate direction vector from origin to point on lens
dir = normalize(p - origin);

// get uniformly distributed points on the unit disk
vec2 lens(0.0, 0.0);
concentricDiskSample(random1, random2, &lens);

// scale points in [-1, 1] domain to actual aperture radius
lens *= apertureRadius;

// new origin is these points on the lens
origin.x = lens.x;
origin.y = lens.y;
origin.z = 0.0;

// Compute point on plane of focus, intersection on z axis
float intersection = std::abs(focus_distance / dir.z);
vec3 focusPoint = dir * intersection;
dir = normalize(focusPoint - origin);

// now looking down -Z (optional depending on your coordinate system)
dir.z *= -1.0;


Coloring arbitrary closed regions I'm trying to implement the following paper in modern OpenGL

http://web.media.mit.edu/~lieber/Publications/Coloring-Book.pdf

The issue is that the algorithm described requires you to consider interior points in an orderly fashion -- horizontally first, then vertically. You also need a way to remember throughout the entire coloring process which parts have been already colored.

I initially thought of putting the logic in a fragment shader, but that will clearly not work because I have no control over the order in which it is called, and also no way to remember state between different invocations.

Maybe we can perform this logic on the CPU and use it to make a texture? The problem here is that I don't know of any way to access and modify specific pixels outside of shaders.

Note that doing this using the fixed function pipeline would be much more straightforward, but I want to learn modern OpenGL.

I'm very new to OpenGL and graphics programming, so would appreciate any suggestions on how one would go about this.

Flood filling is not a very GPU-friendly operation to begin with, and the algorithm described in the paper is not a very good way to go about flood-filling on the GPU either. It might be possible to make it happen with some heroic efforts and compute shaders, but if flood-filling is what you want to do, I would use a different approach altogether. For example this answer describes how to do flood-filling with a multi-pass approach where each pass extends the filled region by 1 pixel in all directions. It will take a lot of passes to fill a large region. You could probably use some variant of jump flooding for a more efficient method.

However, if you don't actually care about flood filling but are just looking to do exercises to learn GPU programming, I'd recommend trying things like: blur filters, outlining, color transforms, image warping, and so on as those will be a lot more straightforward than any kind of flood fill.


Sampling against geometry normals I am writing a basic raytracer and have implemented normal maps. However, when using normal maps, sometimes the rays generated are opposite to the surface's geometry normal, so that the rays are reaching light sources behind the object. If I kill the ray, the shading results looked faceted and the surface normals are apparent. If I don't kill the ray, the ray reaches light sources on the opposite side of the geometry.

How is this handled normally?

That is, to my knowledge, a problem without a proper solution. You're seeing the discrepancy between shading normal and geometry normal and it becomes obvious, that the shading normal is just a trick. PBRT has a paragraph on this, their solution is to look at the geometric normal to determine whether to call the BRDF (reflection) or the BTDF (transmission), then to pass the shading normal to the BxDF. Still, this doesn't work robustly in all situations.

This problem is also known and described for production proven render engines:
http://blog.irayrender.com/post/29042276644/shadow-acne-and-the-shadow-terminator
The solution suggested for iRay is to use displacement mapping instead of normal maps. This way, shading and geometry normal are in agreement again.


What is the difference between importance sampling and mutiple importance sampling? I can't understand math equations. I'm a graphic designer.

What is "importance sampling"?
What is "multiple importance sampling"?

Could you explain easily, using illustrations and no math equations? What is the difference between "importance sampling" and "multiple importance sampling"?

When shading a point on an opaque surface, you need to gather incoming light and weight it with the bidirectional reflectance distribution function (BRDF) of the material.

The naive approach is to distribute samples equally over the hemisphere and probe all directions equally for incoming light. This is called uniform sampling (Fig. 1). While this works in most cases, it can take a long time to converge towards the correct result.

Figure 1: Uniform sampling on the hemisphere

To speed things up, let's consider the properties of the surface in question. A diffuse surface needs to take light from all directions on the hemisphere into account, where light coming from flat angles has less influence. A perfect mirror only needs a single direction according to the law of reflection. Importance sampling takes this into account and distributes samples where light is expected to have a greater influence, judging from the BRDF. For the diffuse surface, a cosine sampling would be used (Fig. 2), resulting in fewer samples at flat angles that presumably have a lower influence. For the perfect mirror, only a single ray is shot because all other directions have zero influence anyway.

Figure 2: Cosine sampling on the hemisphere

Now, the BRDF is not the only thing that can be taken into account. When you have known light sources with strong intensity, it is often desirable to direct more rays towards these light sources, as these directions presumably have a greater impact on the result (i.e. there is more light coming from these directions). The idea to combine various different importance sampling strategies into one is called multiple importance sampling. This technique is not limited to the given example of BRDF + known lights, but can be used with any kind of sensible heuristic you can come up with.

Images were generated using Holger Dammertz' Hammersley Points on the Hemisphere.


Albedo image map to color's Light Reflectance Value (LRV) In many datasets in the literature of both Computer Vision and Computer Graphics there is the albedo map of a scene represented as RGB images, which in principle corresponds to the diffuse reflecting component. The diffuse reflectance factor though of a material/surface is represented a one value, usually as ρ (rho), e.g. in the radiosity formulation. Thus, I am trying to understand how to go from an RGB representation to the corresponding diffuse value. I saw some people averaging the RGB values of the albedo map, e.g. for a pixel value (0, 168, 170) this would give:
((0/255) + (168/255) + (170/255)) / 3 = 0.441830065359477
however is just averaging enough/correct or there is a specific formulation.
I am puzzled quite some time now about it and I cannot really find a good answer. Thus, I would appreciate any feedback.

I am not aware of what LRV is and what is a usage of it. However, I can recommend using luma instead of simply averaging RGB values with equal weight:

https://en.wikipedia.org/wiki/Luma_(video)
https://en.wikipedia.org/wiki/Relative_luminance
Example of using luma - http://blog.simonrodriguez.fr/articles/30-07-2016_implementing_fxaa.html

Human eyes are more sensitive to green colors [1], that's why 16 bit (aka high color [2]) palettes, might prefer to use R5G6B5 format.
[1] https://en.wikipedia.org/wiki/Color_vision
[2] https://en.wikipedia.org/wiki/High_color


Formula for the ambient light intensity of a scene? I understand that ambient light is light that occurs a result of light from a given source refecting off an infinite number of points in a scene, thereby illuminating all objects in the scene uniformly and explains why areas not directly illuminated by a light source in a scene aren't pitch black.

So I guess ambient light gives everything in the scene the same basic "brightness". But how does one determine this value? I presume the ambient light is proportional to the primary light source intensity (a floodlight in a bedroom will surely produce more ambient light than a lit match in the same room) and inversely proportional to the scene size (a lamp in a closet surely produces more ambient light than a lamp in a hall). Is there a formula that gives ambient light "brightness" as a function of scene volume, light source intensity, and any other variables please?

Please excuse my naivety, as I'm a noob to computer graphics, and only a hobbyist at that.

Using an 'ambient light' term in your lighting calculations is an approximation of the indirect light reflected around the scene. Usually it's up to the artist to choose an appropriate value. There isn't really a formula, because the indirect light is dependent on many factors:

Light intensity
Light shape
The BRDFs of the surfaces the light will bounce off of
Visibility to the light source (Think the back of a deep cave)
etc.

You could use some kind of formula to get an approximate value, based on these factors, but, in my opinion, it's simpler just to do it manually per scene. Or, you can remove it entirely, and use more sophisticated methods to calculate indirect lighting.


3D rotation matrix around vector I am using matrix for performing 3D rotations. I know that in 3D space the matrix product order is important - changing the order of the matrices can effect the rotate result.

So I am interesting about how can I create a rotate matrix that perform rotation (clockwise) around some vector, say $(1, 0, 1)$.

I thought that $R_{(1,0,1)}(\theta) = R_X(\theta) \cdot R_Z(\theta)$ but it seems wrong because if I tries to rotate the $(1, 0, 1)$ with $45^{\circ}$ it moves out from $(1, 0, 1)$ but it should stay in place.

So how can I build such a rotation matrix as product of 3D trasformation matrices?

There is a direct formula for the rotation matrix for an arbitrary axis and angle. Given a unit vector $a = (a_x, a_y, a_z)$ and angle $\theta$, the matrix can be constructed as follows (derivation from Wikipedia):

First build a matrix $C$ from the components of $a$ according to the following formula:

$$ C =
\begin{bmatrix}
  0 & -a_z & a_y \\
  a_z & 0 & -a_x \\
  -a_y & a_x & 0
\end{bmatrix} $$

Then you can construct the rotation matrix from $C$ as follows:

$$ R_a(\theta) = I + C \sin \theta + C^2 (1 - \cos \theta) $$

where $I$ is the 3×3 identity matrix. This assumes you're using a column-vector convention; if you're using row vectors instead, transpose $C$.

By the way, this formula has a neat geometric interpretation. The matrix $C$ has the effect of calculating cross products with $a$. In other words, for any vector $v$, $Cv = a \times v$. If you imagine rotating some vector $v$ about $a$, the tip of $v$ traces out a circle perpendicular to $a$; $Cv$ is a vector tangent to that circle, and $C^2 v$ (which equals $a \times (a \times v)$) is a vector normal to the circle. So with those two vectors, you have a basis for the plane of the circle; then you can apply a variation of the usual sine/cosine formula for points on a circle.


Calculating the gradient of a tetrahedral mesh How can I compute the gradient for a tetrahedral mesh (3D)? For triangular mesh, I got an answer from the following post Calculating the gradient of a triangular mesh
How can I get a similar formula for 3D mesh?
Thanks in advance.

Assuming a value is assigned to each vertex of the mesh and we use purely linear interpolation, then there will be a constant gradient vector within each tetrahedron.
Linear interpolation can be expressed using barycentric coordinates, like
$$
f(x,y,z) = f_1 w_1(x,y,z) + f_2 w_2(x,y,z) + f_3 w_3(x,y,z) + f_4 w_4(x,y,z)
$$
where $f_1 \ldots f_4$ are the values of the function at the four vertices, and $w_1 \ldots w_4$ are the barycentric weights for each vertex. Then, finding the gradient of $f$ reduces to finding the gradients of all of the weights.
This can be worked out geometrically by noting that each $w_i$ is 1 at the $i$th vertex, falling off to 0 at the plane formed by the other three vertices. The gradient vector will therefore be normal to that plane, pointing back towards the $i$th vertex, with a magnitude equal to 1 / the distance from the plane to the vertex.
Once you've calculated those barycentric gradients, you can multiply them by $f_1 \ldots f_4$ and sum them up to arrive at the gradient of $f$ overall.
This reasoning works for triangles too, by the way, only replace "plane" with "line".


How to get the nearest polygon face and height of intersection point I have multiple 3D polygons meshes (sketchup format) in the world, for any specified point (x,y,z), how do I get the direct closest polygon face below this point? and how to get the height for the projected intersection point on the face?

Can someone point me the direction how to get started?

To get the height intersection once you have found the polygon, you can build a plane of the polygon and calculate the distance to the plane. For example you can displace the point along the planes normal and calculate the length of the normal for when the point is displaced into the plane. Implicit planes are neat for this, they are build with the normal of the plane (which is the normal of the polygon) and one constant $d$. $d$ can be calculated by arbitrary point on the plane (e.g. one of your polygon vertices).

$d = -\vec{n} \cdot q$ and $\vec{n} + d = 0$ (where $\vec{n}$ is the normal and $q$ the point/vertex).

The neat part is: if you calculate the dot product of your point you want the distance of, you have the signed distance toward the plane, i.e. if $p$ is your point and $l$ is the distance between the point and the plane, then

$l = (\vec{n} + d) \cdot p$ (for this you assume the fourth coordinate of a point as $1$)

Now that you have the distance to the plane, you need to check, weather the intersection of normal through point with plane also intersects the polygon. You could for example take the vectors $\vec{v}_i = v_i - p$ where $v_i$ are your polygons, and then take the dot product $\vec{n} \cdot \vec{v}$. If they all have the same sign, your intersection doesn't hit the polygon (assuming the polygon to be convex).

Iff it doesn't hit the vertices you need the distance to the closest two vertices. Since you have already done the dot product test (with the sign) for all polygon vertices, you know that the shortest distance can't be to the edge between the two vertices, and thus it suffices to take the shortest of the two point->vertex distances.

As to which polygon is closest, I'm not sure if there is a better trick, but I'd just transform the point into Model Space of the mesh and calculate the distance to any front facing face.


Bug with the Bresenham's line drawing algorithm? I know how to draw lines with DDA, but I want to learn a more efficient way and Google suggests Bresenham's line drawing algorithm is better than DDA.

Here is my implementation:

int x0 = Math.round(m_start.getPosition().getX());
int y0 = Math.round(m_start.getPosition().getY());
int x1 = Math.round(m_end.getPosition().getX());
int y1 = Math.round(m_end.getPosition().getY());

int dx = x1 - x0;
int dy = y1 - y0;

int parameter = 2 * dy -  dx;

Point k = new Point(new Vector2D(x0, y0), m_display, PixelData.white());
k.DrawPoint();

for(int i = x0 + 1; i < x1; i++){
   if(parameter < 0){
       y0 += 1;
       Point p = new Point(new Vector2D(i, y0), m_display, PixelData.white());
       p.DrawPoint();

       parameter += 2 * dy;
   }
   else{
       y0 += 1;
       Point p = new Point(new Vector2D(i, y0 + 1), m_display, PixelData.white());
       p.DrawPoint();

       parameter += 2 * dy - 2 * dx;
   }
}

And here is the output:

As you can see, the line is not ending at the desired coordinate. That small dot is where it should end.

I checked the slope, dx and dy.

System.out.println(dx + " " + dy + " " + (dy/(float)dx));

Output:

100 50 0.5

The slope is below tan (pi/4).

How do I find the bug?

Note that the approach you appear to be taking will only work for lines with a slope in a single octant. For the other seven octants the algorithm requires changing the approach, for example by changing the roles of x and y. Wikipedia gives a table of cases that can be used for this conversion.

For this answer I will assume you are simply trying to get the code working for the first octant.

int parameter = 2 * dy -  dx;

parameter starts off negative only if dx > 2 * dy.

In this case the total horizontal distance to be covered by the line is more* than twice the vertical distance, which means the first step should be purely horizontal. So if parameter is negative then y0 should not change.

Here is the source of the problem:

if(parameter < 0){
           y0 += 1;

y0 should only be incremented if parameter is not negative. This y0 += 1 is causing vertical movement even if the first step should be purely horizontal.

The same problem applies on later steps too. The code causes parameter to switch back and for between negative and non-negative in proportion to the ratio between 2 * dx and dy. y0 must only be incremented when parameter is non-negative. That additional occurrence of y0 += 1 prevents y0 from ever staying still, causing a slope of 1 regardless of the inputs. Simply remove that line and it should work correctly.

*If you are wondering why the algorithm only steps purely horizontally when the parameter is less than zero, rather than less than or equal to zero, bear in mind that the horizontal distance to be covered is one less than the number of pixel columns displayed. If x0 is 0 and x1 is 3, then dx is 3, but 4 columns of pixels will be displayed. So a line 4 pixels across and 2 pixels down actually has xd as 3 and yd as 1. In this case the number of pixels across is exactly twice the number of pixels down, but xd is more than twice yd, so this still results in the parameter being negative and the line moving purely horizontally on the first step.


fix over exposure in importance sampling in screen space reflections I am having my first encounter with the rendering of indirect reflections in the form of screen space reflections in a game engine, but i am struggling to get correct looking results.

(patterns arise from a bad way of generating noise for montecarlo integration)

(image taken at low ray count. otherwise the color values end up going to NaN)

From what i've gathered, a common formulation of the rendering equation is as follows:

$$L_o(p,\omega_o)=L_e(p,\omega_o)+\int_{\Omega}L_i(p,\omega_i)fr(\omega_i,\omega_o)(n\cdot\omega_i)d\omega_i$$

which, dropping the $L_e(p,\omega_o)$ term, can be approximated using the following monte carlo estimator:

$$L_o(p,\omega_o)\approx\frac{1}{N}\sum_{i=1}^{N}\frac{L_i(p,\omega_i)fr(\omega_i,\omega_o)(n\cdot\omega_i)}{p(\omega_i)}$$

where $n$ is a unit vector perpendicular to the surface.

for actual computation of values, all of these terms must be specified.

$L_i(p,\omega_i)$ is found through raymarching in screen space

$fr(\omega_i,\omega_o)$ is the Cook-Torrance BRDF:$\frac{FGD}{4(n\cdot\omega_i)(n\cdot\omega_o)}$

if we name the angle between $n$ and $m$ $\theta$, we get that the GGX NDF is:$D=\frac{\alpha^2}{\pi(\cos^2(\theta)(\alpha^2-1)+1)^2}$

where $m$ is the microfacet normal $m=\frac{\omega_i+\omega_o}{|\omega_i+\omega_o|}$

$p(\omega_i)$ Is the PDF that can be derived from the GGX NDF $\frac{\alpha^2\cos(\theta)\sin(\theta)}{\pi(\cos^2(\theta)(\alpha^2-1)+1)^2}$

When put all together we get:

$$L_o(p,\omega_o)\approx\frac{1}{N}\sum_{i=1}^{N} \frac{L_i(p,\omega_i)\frac{FG}{4(n\cdot\omega_i)(n\cdot\omega_o)}\frac{\alpha^2}{\pi(\cos^2(\theta)(\alpha^2-1)+1)^2}(n\cdot\omega_i)}{\frac{\alpha^2\cos(\theta)\sin(\theta)}{\pi(\cos^2(\theta)(\alpha^2-1)+1)^2}}$$

After simplifying, we get:

$$L_o(p,\omega_o)\approx\frac{1}{N}\sum_{i=1}^{N} \frac{L_i(p,\omega_i)FG}{4(n\cdot\omega_o)\cos(\theta)\sin(\theta)}$$

This procedure seems correct to me but the images produced by my implementation have over exposed reflections at sharp incidence angles or at low roughness values. However, when i remove the $\sin(\theta)$ factor from the denominator it looks plausible (not sure about correctness though).

Thanks in advance.

After some testing and some research I have found that both the $\sin(\theta)$ and the $\cos(\theta)$ should be removed from the denominator.

the reasoning is that, since we want a probability function of steradians instead of angles, the $\sin(\theta)$ factor (which is essentially used to convert from steradians on a unit sphere to radians on the two polar axis) should be dropped.

Also, $\cos(\theta)$ (as Nathan Reed explains in this blog post) is there to convert from microfacet area to macrosurface area. Since we are generating microsurface samples, this should be removed.

After these corrections we get the formula

$$L_o(p,\omega_o)\approx\frac{1}{N}\sum_{i=1}^{N}\frac{L_i(p,\omega_i)FG}{4(n\cdot\omega_o)}$$

which is free of the artifacts of the formula on the question.


What mechanisms are being used by Directx12 and Vulkan APIs in order to communicate with graphic card drivers internally? I am trying and learning to develop a low level graphics API.

I want to know, how do modern graphics APIs manage to communicate with graphic card drivers (to tackle GPU) so efficiently and in an optimized manner?
Which technologies should I understand other than C/C++ and Assembly?

It's very different between the Khronos standards (including Vulkan) and DirectX.

In DirectX, Microsoft implements the API, but they publish to GPU vendors a HAL API. There's actually two HALs: one that runs in kernel-mode, to communicate with the card directly; and one that runs in user-space, to do other tasks (like manage memory, set up data structures, and compile shaders).

In Vulkan, Khronos only publishes the specification and a test suite. It's up to each GPU vendor to ship an implementation of the library. The application's interface to the driver is a normal C API, like any other library. You'll get confused if you try to think of an "API part" communicating with a "graphics card driver": the driver is the API implementation.

This is why it's very hard for third-parties to make open-source OpenGL (or Vulkan) implementations: you need to know all the details of the GPU hardware to do it. These graphics APIs are defined by industry groups consisting of the same people who design the hardware (at a high level), and deep understanding of the GPU architecture is what you need to design an efficient graphics API.